Linkers and Loaders

reference)

https://sepang2.tistory.com/34

Linkers and Loaders

Loader는 absolute loader (focus on only loading process)와 linking loader로 나눠 볼 수 있다.

 

Linking Loader

- program relocation, linking, loading(absolute loader와 같음)기능을 수행

- relocation solutions

"modification record" & "Relocation bit"

 

Relocation with M record  (절대 instruction의 실제 위치를 고려해 수정해주는 것)
•A general method for specifying relocation as part of object program: “Modification record scheme” for SIC/XE
   –Fig. 3.4, the source program equal to Fig. 2.6
      Most of the instructions use relative or immediate addr essing
  –Fig. 3.5, the object program corresponding to Fig. 3.4

•Not well suited for all machine architectures, such as SIC basic version

SIC에선 대부분의 instruction을 수정할 필요가 있기에 modification record가 너무 많음 overhead -> relocation bit를 이용! 
–Fig. 3.6, the relocatable program written for the standard SIC
  Most instructions must be modified for program relocation (because of direct addressing)
 This requires 31 Modification records, which results in an object program more than twice as large as the one in Fig.3.5

 

Fig. 3.5 Object Program with Relocation by Modification Records
•There is one Modification record for each value that must be changed during relocation (in this case, 3 instructions)
_ Each Modification record specifies the starting address and length of the field whose value is to be altered. It then describes the modification to be performed
–Here, all modifications add the value of the symbol COPY, which represents the starting address of the program

만약, 실제 시작 주소가 1000이라면, Loarder에 의해 B101036은 B102036이 됌

 

현재 변경해야 하는 명령어들은 모두 immediate addressing을 사용하고 있다. 현재 addr field의 값은 RDREC, WRREC이 프로그램 시작주소에서 얼마나 떨어져 있는가를 나타낸다. 하지만 해당 레이블의 절대적인 주소는 현재 addr field값에 프로그램 시작주소인 COPY를 더한 값이다. 때문에 M record에서는 해당 addr field에 프로그램 시작 주소를 가리키는 symbol인 COPY를 더하라고 되어 있는 것이다.

  하지만 M record를 이용한 재배치는 SIC 기본 버전 같은 모든 기계 아키텍처에 적합하지는 않다. 밑의 fig 8은 표준 SIC용으로 작성된 재배치 가능 프로그램이다. 여기서는 대부분의 명령어가 direct addressing을 사용하기 때문에 M record가 너무나 많이 추가될 것이다. 때문에 program size 측면에서 너무나 비효율적이다.

 

Fig. 3.6 Relocatable Program for a standard SIC Machine

Fig. 3.6 Relocatable Program for a standard SIC Machine

 

Relocation with Bit Mask

주로 direct addressing을 사용하고 고정된 명령어 형식을 갖는 기계에 유용하다(SIC!!).
•An alternative method for specifying relocation as part of object program: “Relocation bit mask” for SIC
–Useful for a machine primarily using direct addressing and having a fixed instruction format
–Observation of modification record
Record format: [address to be modified, length]
   If instruction format is fixed, the length part can be removed 
   Instead of address field, bit-vector (= relocation bit) can be used.
–The relocation bit can be set either to 1 or 0:
   “1” -> program’s starting address is to be added to this word when relocated
   "0” ->no modification is necessary

 

계속 봐왔던 M record를 한번 살펴보자. [수정할 주소, 길이]라는 형식을 가지고 있었는데 여기서는 고정된 명령어 형식을 갖기에 '길이'는 제거할 수 있다. 그리고 '수정할 주소' 대신에 bit-vector(=relocation bit)를 사용할 수 있다. 이는 1 or 0으로 설정할 수 있다. '1'인 경우에는 재배치 시 프로그램의 시작 주소가 해당 word에 추가되고 '0'인 경우에는 수정이 불필요하다. 이런 방식을 적용한 object code가 바로 fig 3.7이다.

relocation bit, 1이면 해당 instruc를 로더가 수정 (시작주소를 address field에 더해줌),0이면 수정 필요 X

해당 레코드의 object code의 길이를 표현하는 열 이후에  'FFC' 를 확인할 수 있다.FFC를 이진수로 나타냈을 때, 1인 부분은 수정되어야함. 예시에서는 10개의 비트가 다 1이므로, 그 후의 10개의 object code (instruction)을 수정해야함

Program linking

 

하나의 프로그램은 관련된 모든 Control Section들이 결합된 logical entity이다. 그런데 로더의 관점에서는 프로그램이라는 개념이 없고 CS들은 각각 링크하고 재배치하고 로드할 독립된 개체들인 것이다.

•You should review Section 2.3.5 Control Sections and Program Linking
•Brief Summary on “program linking”
–A program can be thought as a logical entity that combines all of the related control sections.
–However, from the loader’s point of view, there are only control sections that are to be linked, relocated, and loaded –i.e., no such thing as a program in this sense.

 

EXTDEF & EXTREF Directive for Program linking 

•EXTDEF (External Definition)

'EXTDER   BUFFER'라고 하면 현재 CS에 있는 BUFFER가 다른 CS에서도 사용할 수 있는 '외부 기호'가 되는 것이다.
_The EXTDEF statement in a control section names symbols, called external symbols, that are defined in this (present) control section and may be used by other sections
–e.g.) EXTDEFBUFFER, BUFFEND, LENGTH
          EXTDEFLISTA, ENDA

•EXTREF (External Reference)

'EXTREF   RDREC'라고 하면 다른 CS에서 EXTDEF로 정의된 RDREC이라는 외부 기호를 현재 CS에서 사용할 수 있게 되는 것이다.
–The EXTREF statement names symbols used in this (present) control section and are defined elsewhere
–e.g.) EXTREFRDREC, WRREC
          EXTREF LISTB, ENDB, LISTC, ENDC

 

Fig. 3.8
•Sample programs illustrating linking and relocation
•Each control section defines a list of items and the end of the list:
–Control section PROGA: LISTA, ENDA (LISTA: defines a list of items / ENDA: defines the end of the list)
–Control section PROGB: LISTB, ENDB
–Control section PROGC: LISTC, ENDC

•Each control section contains exactly the same set of references to these lists:
–REF1 through REF3: instruction operands
–REF4 through REF8: values of data words

LISTA는 local reference in PROA

세 개의 프로그램이 하나의 control section를 가짐 (PROGA, PROGB, PROC)

PROB에서 LISTA는 또 다른 control section에서 가져오는 external symbol (=어셈블러가 직접 번역할 수 없음->0를 address field에 할당)

Fig. 3.9
•Object programs corresponding to Fig. 3.8
•Find the differences in the way these identical expressions are handled within the three control sections.
–REF1: Simply a local reference in control section A (thus, it can be assembled using a PC-relative addressing, and no modification for relocation or linking is necessary), but an external reference in control sections B and C (thus, it cannot be assembled and just can be modified later by the loader)
–Also, look at REF2 and REF3

PROGA

PROGB LISTA에 대한 Modification Record 존재

 

PROGC

Fig. 3.10(a)
•General approach (어셈블러가 external symbol을 다룰때)
–Assembler evaluates as much of the expression as it can.
–The remaining terms are passed on to the loader via M records.
–As an example, consider REF4

초록 형광펜; REF4 / 54 _1modification record

•Fig 3.10(a) shows the programs of Fig 3.8 in memory after linking and loading.
_After relocation and linking is performed, each of REF4 through REF8 have resulted in the same value in each of the 3 control sections.

_However, for the references that are instruction operands, the calculated values after loading do not always appear to be equal -> REF1~3처럼 instruction의 operand인 경우에는 CS들이 어디에 로드되는지에 따라 다른 값이 나타난다.

loader가 linking과 relocation을 다 끝낸 후, memory state / 3 parts have same object code because they are defined with same constant value but,instruction 부분 object code (ex. 4020,4090-40A0...)은 format이 다를 수 있고, pc relative addressing을 이용(address fileld에 상대적 값인 displacement값이 들어감)할 수도 있기에 살짝 다름

linking 과정

 

PROGA의 REF4의 linking 과정이다. M record의 +LISTC를 읽는다. 이는 LISTC의 메모리상 절대주소를 더해야 하는 것이다. 때문에 PROGC의 시작주소와 해당 CS에서의 LISTC 상대주소를 더한뒤에 이 값을 '000014'에 더해주고 이 값이 메모리에 로드되는 것이다.

 

Algorithm & Data Structures for a Linking Loader
•We use Modification records for relocation so that the linking and relocation functions are performed using the same mechanism.
•The algorithm for a linking loader is more complicated than the absolute loader algorithm.
–Usually makes two passes over its input

 

  Linking loader는 Modification Record를 사용하여 linking과 재배치(relocation)를 동시에 해결하려고 한다. 때문에 더 복잡한 알고리즘을 가진다. linking까지 해줘야 하기 떄문에 당연히 absolute loader보다 복잡한 알고리즘을 가진다. 큰 차이점은 input(여러 CS의 집합)에 대해 2-pass를 이용한다는 것이다.

 

Linking Loader Algorithm (1/2)
•Pass 1: Assign addresses to all external symbols
–Decides where each module will be located (PROGADDR & CSADDR).
   PROGADDR is the beginning address in memory where the linked program is to be loaded
       »This information may be given by OS.
   CSADDR is the starting address assigned to the control section currently being scanned by the loader

 

–Prepare an external symbol table (ESTAB), for each external symbol.
  ESTAB is used to store information of external symbols
  [control section, symbol name, symbol address]

 

Pass 1에서는 모든 external symbol에 주소를 할당한다. 우선 PROGADDR과 CSADDR이라는 변수를 사용하여 각 모듈(=CS)의 위치를 결정한다. PROGADDR은 링크된 프로그램이 메모리에 로드될 때의 시작주소를 나타내는데 기본적으로 OS한테 넘겨받는다. 즉 OS가 메모리에서 어디가 비어있는지 확인하고 로드될 위치를 정해주는 것이다. CSADDR은 현재 로더에 의해 스캔된 각 CS에 할당된 시작 주소이다.

  그리고 external symbol table(ESTAB)을 준비한다. 이 자료구조는 각 external symbol의 정보를 저장하는데 사용되는데 [CS, symbol이름, symbol 주소]가 저장된다. 아래와 같은 형식을 가진다. 이러한 ESTAB를 이용하여 pass-2에서 실제 linking과 relocation에 사용이 된다. 

Fig. 3.11

Linking Loader –Algorithm (2/2)
•Pass 2: Perform actual loading, relocation, and linking
   –For a modification record, search the external symbol table
   –Modify absolute addresses as defined in modification record in the code itself.
   –Transfer the control to the program loaded

 

Pass 2에서는 실제 로딩, 재배치, linking이 수행된다. M record의 경우에는 ESTAB을 이용하여 주소를 찾는다. 그리하여 코드 자체의 M record에 정의된 대로 절대 주소를 수정한다. 그리고 로드된 프로그램에 control을 넘긴다. 해당 알고리즘은 다음과 같이 표현될 수 있다.

•Refer to Fig 3.11 for the linking loader algorithm

 

Dynamic Linking _ 해당 code 호출시, linking이 이루어짐

 

방금전까지 다뤘던 linking은 일반적으로 static linking이라고 한다. 이는 프로그램 실행전에 모든 필요한 object code들이 메모리에 load&linking이 된다는 의미이다. 지금 알아볼 dynamic linking은 프로그램 실행 도중 어떤 object code가 필요할 때 그때 해당 코드를 메모리에 로드하고 linking을 수행하는 것이다.

•Postpone linking process until the object code is actually used
–A subroutine or library is loaded and linked to the rest of the program when it is first called
•Achieve substantial savings of time and memory space
–No need to load and link parts of a library that will not be used by the program
–Allow several executing programs to share one copy of a subroutine or library
•Object codes are stored in a “dynamic link library”

 

상당한 시간 및 메모리 공간 절약이 가능. 

어떤 라이브러리 전체를 로드하고 linking 하는 것이 아니고 프로그램에서 필요한 일부만을 로드하고 linking하기 때문이다.

또 하나의 장점은 여러 프로그램이 하나의 서브루틴 or 라이브러리 사본을 공유할 수 있다는 것이다. 

 

User program이 Library의 함수를 이용할 때, load-and-call 서비스를 OS에 요청 -> Dynamic Loader가 메모리(ERRHANDL)에 올려줌

Code flow를 jump (호출하지 않을 때에는 실행하지 않도록 dynamic loader가 handle할 수 있도록 복잡한 code flow를 가지고 있음)