2.2 - (5) Linking

1. Basic

1. Source file

• Compiler : Translate HLL (Source file) to machine language (Object file)

2. Object file

• linker : translate object files to executable program with Static libraries

3. Executable file

• load : Executable file in HDD or SSD is transferred into the memory

• 전체적인 과정 : Source file -> Compile -> Object file -> Linking
  -> Executable file
  
  
• 세부적인 과정

1. .c 파일은 전처리기를 거쳐서 .i 파일로 변환
   -> 전처리기는 주석 없애기, 매크로 / define 정보 substitution, 헤더 파일 함수 원형 선언 등
2. .i 파일은 어셈블러를 통해 .s 파일로 변환
3. .s 파일은 .o 파일인 object 파일로 변환
4. linker를 통해 개별 Relocatable object 파일들을 연결해서 하나의 실행 가능한 파일로 만들어준다.
5. Disk에 있는 실행 가능한 파일을 loader를 통해 memory에 적재한다.

• Buile VS Compile

  • Build : 소스파일들을 하나의 실행가능한 파일로 만드는 과정 전체
  • Compile : 링커 이전까지의 과정 -> 개별 object file 생성까지의 과정

• Compiler VS Interpreter

	Compiler	Interpreter
Translate Unit	Entire source code of a HLL into executable machine code	Runs source code line by line
Performance	a large amount of time to analyze the entire source code	less amount of time to analyze the source code
Execution time	faster	slower
Memory allocation	a lot of memory	less memory
Example	C, C++	Python, Ruby

---

2. Linking

• Linking : 여러개의 개별 object file들을 연결해서 하나의 executable file로 만드는 과정
  • Input : seperate relocatable object files
  • Output : fully linked executable object file
• Static linking : 실행가능한 목적파일을 만들 때 라이브러리들도 모두 포함하여 .exe 파일을 만드는 linking
  -> 미리 라이브러리를 포함하여 컴파일이 되어있기 때문에 컴파일 시간이 단축되지만 메모리 공간을 많이 차지한다.
  • Symbol resolution : object 파일에 있는 각각의 Symbol (변수,함수 등)들을 정확하게 단 하나의 Symbol Definition에 매핑
  • Relocation : 여러 object파일들에게 할당된 공간을 재배치
• Dynamic linking : 실행 가능한 목적파일을 만들 때 라이브러리들의 모듈 주소만을 가지고 있다가 프로그램의 Run time, load time (HDD -> Memory) 때 필요한 모듈만을 연결 하는 방식
  -> 메모리 공간을 효율적으로 사용가능하지만 라이브러리가 저장되어있는 주소로 점프해야하는 동작과정이 있어 overhead 및 추가적인 코드가 필요하다.
• Why linkers?
  • Modularity : 작고 간단한 소스파일들의 더미로 작성될 수 있다.
  • Efficiency : 작고 간단한 소스파일들의 개별 컴파일로 인한 시간 절약 및 공통되는 소스들을 공유함으로써 공간 절약
• What do linkers do?

  1. Symbol resolution

  • Collect all defined and undefined symbol information (function, variables)
    
  • Make a symbol table (including name, size, location)
  • Associate each symbol reference with exactly only one symbol definition
    
    

  2. Relocation

  • Merge seperate code and data sections into single sections
  • Update all references to these symbol to reflect their new positions
  • Adjust memory addresses in code and data to reflect relocated segment addresses

---

3. Three kinds of object files

1. Relocatable object file : The output of compile
2. Execuatable object file : The output of linking
3. Shared object file (Dynamic Linker Libraries) : 공통으로 사용하는 함수, 라이브러리 파일들을 load 또는 run time에 동적으로 필요할때마다 메모리에 로드 & 링킹
   -> 실행가능 파일에 모든 정보가 있는건 아니지만 메모리를 효율적으로 사용할 수 있음
   -> 개별 프로세스가 라이브러리를 요구하면 메모리 안에 Shared object file의 위치만 제공함

---

4. ELF (Executable and Linkable Format)

• Standard binary format for object files
• To better support for shared libraries
  

  • ELF header : object file 해석, 변환을 위한 기본 정보들을 포함
    • Word size, byte ordering, file type, machine type
  • Program header table
    • Page size, virtual addresses of memory segments
    • Executable object file 같은 경우에는 메모리에 어떤 형식으로 load 될지 결정 되어 있어야함
    • Relocatable object file에 필요하지 않음
  • text section : Machine code 영역
  • rodata section : Read only data 영역
    -> loader는 rodata section을 제외하고 memory에 적재 (메모리 효율성을 위해)
  • data section : Initialized global variables
  • bss section (Better Save Space) : Uninitialized global variables
    -> Executable file의 크기를 줄이기 위해 initialized, uninitialized 구별!
    ex) int a[100] => 100개의 int공간이 필요하다는 정보만 가지고있으면 executable file 크기를 줄일 수 있다.
  • symtab section : Symbol table
  • rel text section : Relocation info for text section, addresses of instructions that will need to be modified in the executable
  • rel data section : Relocation info for data section, addresses of pointer data that will need to be modified in the executable
    -> Executable file에서는 relocation 정보들이 이미 linking을 통해 merge 된 상태이므로 존재하지 않는다.

---

5. Life and Scope Of Variables

• Life : 변수를 위해 할당된 메모리 공간의 존재(valid) 여부
  • ex) 함수 호출 : stack에 variable 할당, 함수 리턴 : 변수를 위한 memory공간 사라짐 (dead)
• Scope : 해당 변수를 접근할 수 있는 범위

• Local variable : 함수 안에서 선언된 변수
  • Stored in stack frame
  • Life : when this function completes
  • Scope : function scope
    
• Static local variable : 프로그램의 life동안 사용하고자하는 지역변수를 선언할 때 사용한다.
  • compile 할 때부터 stored in data section or bss section (uninitialized)
  • Life : when program completes
  • Scope : function scope
  • 함수 재호출시에 특정 변수를 계속해서 사용하기 위해, scope을 함수내로 제한하기 위해서 (다른 곳에서 사용하는것을 막기 위해!)
• Global variable : 함수 바깥에서 선언된 변수
  • stored in data section
  • Life : when program completes
  • Scope : entire program
    

---

6. Three Types Of Linker Symbols

• Symbol : a variable or a function

  • Global symbols : module m에서 정의되서 다른 module들도 참조할 수 있는 Global symbols
    -> non-static 함수, 전역변수 등
  • External symbols : module m에서 사용되지만 다른 module에서 정의 된 Global symbols
  • Local symbols : module m 안에서 정의되고 module m만 사용할 수 있는 Symbols
    -> static 함수 등
    

• Example
  

---

7. Strong and Weak Symbols

• Strong : Initialized globals

• Weak : Uninitialized globals
  

• Rules

  1. Multiple strong symbols are not allowed
     
     
     
  2. Choose the strong symbol when there is a strong symbol and multiple weak symbols
     
     
     
  3. If there are multiple weak symbols, an arbitrary symbol will be picked
     

• Problem
  

  • 첫 번째 경우에는 weak symbols -> 만약 linker가 double x를 선택한다면 8바이트를 차지하므로 y는 overwrite 될 수도 있다.
  • 두 번재 경우에는 strong symbol인 int x=7 선택 -> p2에서 x값을 변경하면 p1의 x도 변경되는데 8바이트를 차지하고있는 상태에서 변경되므로 y값이 overwrite 된다.
    => static variable의 필요성!