[컴퓨터 SW] Static Linking

이 글은 포스텍 김종 교수님의 컴퓨터SW시스템개론(CSED211) 강의를 기반으로 재구성한 것입니다.

 이 글에서는 Linking에 대해 알아본다.

 

Linking

 Linking은 프로그램 코드와 데이터를 합쳐 실행할 수 있는 파일을 만드는 과정이고, Linker는 Linking을 수행하는 프로그램이다.

 

 

Linking의 장점

 Linking의 개념이 등장하기 이전에는 모든 소스코드를 한 번에 컴파일해 실행가능한 프로그램을 만들었는데, 이 방식의 경우 소스코드가 조금만 바뀌어도 프로그램 전체를 재컴파일해야하는 비효율적인 방식이다. 그러나 Linker의 등장으로 프로그램을 작은 소스파일의 단위로 모듈화했고, 소스코드가 수정된 부분의 모듈만 재컴파일해 기존 모듈들과 Linking을 할 수 있게 되었다. 즉슨 기존에 있는 소스파일들을 컴파일할 필요가 없어져 프로그램을 실행하는 시간도 줄게 되었다.

 

또한 공통된 기능과 함수를 묶어둔 library라는 개념도 만들어졌다. 이 때 static linking이냐 dynamic linking이냐에 따라 library를 가져오는 방식이 다르다.

• static linking의 경우 실행 파일이 library를 포함하기 때문에 메모리에도 library가 올라간다. 이 경우 필요한 부분만 실행파일에 복사하기 때문에 컴파일 시간이 줄어든다는 장점이 있지만 실행 파일이 library를 포함하기 때문에 메모리를 많이 먹는다는 단점이 있다.
• dynamic linking의 경우 실행 파일에 library가 없는 대신 모든 process가 library를 공유한다.(프로그램이 실행될 때 linking이 수행된다.) 따라서 library가 메모리에 하나만 올라가기 때문에 static linking보다 메모리를 덜 사용한다는 장점이 있다.

 

 

Static Linker가 하는 일

 static linker는 relocatable object file을 받아 하나의 executable file을 만든다. 이 과정에서 symbol resolution과 relocation을 수행한다.

 

Symbol Resolution

 symbol은 프로그램에서 정의된 변수와 함수이다. (non static local variable은 포함하지 않는다.) 즉슨 다른 scope에서 참조할 수 있는 무언가를 symbol이라고 이해하면 좋을 것 같다. 이 symbol들은 struct array인 symbol table에 저장된다.

 프로그램은 symbol을 정의하고 참조한다. Symbol Resolution은 프로그램에서 사용하는 symbol reference를 찾아 정확히 하나의 symbol definition에 묶어주는 작업을 의미한다. 

 

 아래 예시를 보자.

symbol resolution example

 non-static local variable을 제외한 나머지는 모두 symbol이기에  두 소스코드에서 array, main, sum은 모두 symbol이다.

 main.c에서 sum() 함수를 사용하는 것을 볼 수 있는데, 이는 sum.c에 정의된 symbol을 reference하는 것이다.

 

Relocation

 relocation은 분리되어 있는 코드와 data 영역을 하나의 section으로 합치는 과정이다. compiler와 assembler가 만든 .out file들은 주소가 0부터 시작하기 때문에 이 section들을 적당한 virtual address로 relocation하고, symbol에는 virtual address를 부여해 symbol reference가 올바른 symbol definition을 가리키게 수정한다.

 

 

Object Files

 object file은 아래 3가지 형태가 있다.

• relocatable object file : linker가 다른 relocatable object file과 결합해 executable object file을 만들 수 있는 binary code나 data를 포함한 파일. C/C++에서는 .o 파일들이며 .c 파일 하나당 .o 파일 하나씩 만들어지며 compiler나 assembler가 만든다.
• executable object file : memory에 직접 복사되어 실행할 수 있는 code와 data를 가지고 있는 object file.
• shared object file : 특별한 종류의 relocatable object file로써 load time이나 run time에 메모리에 로드되어 dynamic linking을 할 수 있다.

 

 executable object file의 형식은 시스템마다 다른데 Linux는 Executable and Linkable Format - ELF - 형식을 사용하며 Window는 Portable Executable - PE -, Mac은 Mach-O 형식을 사용한다.

 

이름
ELF Header	word size, byte ordering, file type, machine type 등의 system의 정보가 들어간다.
Segment header table	page size, virtual address memory segment(section), segment size 등
.text	코드가 들어간다.
.rodata	jump table 등의 read-only data가 들어간다.
.data	0이 아닌 값으로 초기화된 global/static variable이 들어간다.
.bss	0으로 초기화되거나 초기화되지 않은 global/static variable이 들어간다.
.symtab	모든 symbol에 대한 정보가 들어있는 symbol table이 저장된다.
.rel .txt
.rel .data
.debug
Section header table	section의 크기와 위치에 대한 정보가 들어간다.

 

local static variable은 초기화 여부에 따라 .bss나 .data에 저장되지만, local non-static variable은 stack에 저장된다.

 

 

Symbol and Symbol Table

 symbol의 종류는 아래 3가지가 있다.

• global symbol : 모듈 m에 의해 정의되고 다른 모듈들이 참조하는 symbol. non-static C function / non-static global variable이 여기에 속한다.
• external symbol : 모듈 m이 참조하지만 다른 모듈에서 정의된 symbol. m 이외의 모듈에서 정의된 non-static C funtion / non-static global variable이 여기에 속한다.
• local symbol : 모듈 m에 의해 정의되고 참조되는 symbol이며 다른 모듈에서 참조되지 않는다. 만약 같은 이름으로 정의되었을 때는 symbol name을 다르게 해서 구분한다. static C function, static variable, static global variable이 여기에 속한다.

 

 

Symbol Resolution

 앞에서 다음과 같이 symbol resolution을 정의했다.

 Symbol Resolution은 symbol table에서 symbol reference를 찾아 정확히 하나의 symbol definition에 묶어주는 작업을 의미한다. 

 

 이 때 동일한 symbol이 여러 개일 수도 있다. 이 때 global 또는 external symbol이 초기화 되었다면 strong symbol, 초기화되지 않았다면 weak symbol로 저장된다. 이렇게 symbol이 나뉠 때 아래는 resolution rule 3가지이다.

1. 동일 이름의 strong symbol은 존재할 수 없다. (Strong symbol은 단 하나만 존재할 수 있다.)
2. 동일 이름의 strong symbol 1개와 weak symbol 여러 개가 있는 경우 strong symbol을 사용한다.
3. 동일 이름의 weak symbol 여러 개가 있는 경우 weak symbol 중 아무거나 하나를 사용한다.
   • weak symbol이 여러 개일 경우 아무거나 하나를 고르기 때문에 주의해서 사용해야 한다. 예를 들어 하나는 int x; 다른 하나는 double x;로 symbol이 구성된 경우 int가 골라졌는지 double이 골라졌는지 프로그래머는 모른다.

 

symbol 분류

대분류	중분류	종류
global symbol external symbol	strong symbol	non-static C function 초기화된 non-static global variable
	weak symbol	초기화되지 않은  non-static global variable
local symbol		static C function, static variable, static global variable

 

 

Reloation

 위에서 다음과 같이 relocation을 정의했다.

 relocation은 분리되어 있는 코드와 data 영역을 하나의 section으로 합치는 과정이다. compiler와 assembler가 만든 .out file들은 주소가 0부터 시작하기 때문에 이 section들을 적당한 virtual address로 relocation하고, symbol에는 virtual address를 부여해 symbol reference가 올바른 symbol definition을 가리키게 수정한다.

 

 symbol resolution 과정을 거져 symbol resolution이 끝났다면 모든 symbol reference는 하나의 symbol definition과 연결된 상태일 것이다. 이 상태에서 relocation은 다음 과정을 거친다.

1. section과 symbol defintion을 재배치. 같은 종류의 모든 section을 하나의 section으로 합친다. 이 때 적당한 virtual address를 할당한다.
2. section 내의 symbol reference 재배치 : .text와 .data section의 모든 symbol reference를 수정해 runtime에 참조할 수 있는 정확한 주소를 가리키게 한다. 이 전 단계가 끝나면 모든 symbol들의 virtual address를 알 수 있으며, relocation entry라는 data structure로 이 작업을 수행한다.

 

relocation 예시

relocation 예시

 위 그림과 같이 section과 symbol definition을 재배치 : .text section은 .text section끼리, .data section은 .data section끼리 모은다.

 

Relocaiton Entry

 relocation entry에는 크게 4가지 정보가 들어있다.

• offset : relocate할 reference의 offset.
• type : relocation type. R_X86_64_PC32와 R_X86_64_32 2가지 종류가 있다.
  • R_X86_64_PC32 : 32-bit PC-relative address 형식을 사용해 relocation하는 경우
  • R_X86_64_32 : 32-bit absolute address 형식을 사용해 relacation하는 경우
• symbol : symbol table index.
• addend : 특정 relocation type에 대해 relocation expression의 constant part이다.

 

 linker는 모든 section과 symbol의 runtime address를 알고 있는 상태에서 이 때 ADDR(s)를 symbol s의 runtime address, 각 symbol의 relocation entry를 r이라 할 때 모든 symbol에 대해 아래 로직을 수행해 symbol reference를 relocation한다.

refptr = s + r.offset;

if(r.type == R_X86_64_PC32){
    refaddr = ADDR(s) + r.offset;
    // symbol reference virtual address
    
    *refptr = ADDR(r.symbol) + r.addend - refaddr;
    // symbol runtime address
}
else if(r.type == R_X86_64_32){
    *refptr = ADDR(r.symbol) + r.addend;
    // symbol runtime address
}

 

 

 

Executable Object File

executable object file to memory

 이러한 과정을 거쳐 executable object file을 실행하면 위 그림과 같이 프로그램이 메모리에 올라간다. 이 때 code segment는 항상 0x400000에서부터 시작한다. 그 위에는 malloc 등으로 사용자가 동적 할당한 값들이 저장되는 heap, 그 위에는 shared library를 올리기 위해 예약한 공간, 그 위에는 user stack이 위치한다. 이 위로는 OS에 해당하는 kernal code/data 영역이며 user는 접근할 수 없다.

 

 

 

 

 

 

잘못된 내용이나 지적, 오탈자 등은 언제나 환영합니다.