[CS] Linking - Computer System 3rd Edition by Bryant

Linking

Linking이란 다양한 코드와 데이터를 메모리에 로드(복사)하여 실행할 수 있는 단일 파일로 수집 및 결합하는 프로세스이다. Linking 실행 시간에 따라 두 가지 방식으로 나뉘게 되는데, 첫 번째는 Static Linking이다. 이는 Compile Time에 수행이 되는데, relocatable object files들과 command line arguments를 취한 다음 Linked된 Executable Object를 생성하게 된다. 다음으로는 Dynamic Linking이다. 이 방식은 load time이나 run time에 수행될 수 있으며 Shared Library가 여러개의 Process에 의해 공유될 수 있다. Application은 이 Shared Library를 Link하거나 Load하기 위해서 Dynamic Linker를 요청할 수 있다. 

 

본 포스팅에서는 Static Linking 위주로 다루겠다.

 

그렇다면 왜 Linker를 사용하는가?

Linker는 우선적으로 분할 컴파일을 가능하게 해준다. 이로인한 이점은 크게 두 가지로 나눌 수 있다.

1. Modularity

우리가 10000줄이 넘는 긴 코드를 사용한다고 해보자. 이러한 코드를 하나의 monolothic mass라고 할 수 있는데, 협업이 빈번한 개발자들의 입장에서는 하나의 코드 파일에 이런 방식의 작업 하는게 매우 불편하다. 예를 들어 gitHub에 push하는데 개발자들이 동시에 push하는 경우 코드를 merge할 때 충돌이라도 나면 머리가 매우 아파진다. 그래서 Program을 작은 단위의 source file로 작성하고, 공유하는 자원들을 Library 형태로 사용한다면 각각의 개발자들이 효율적으로 작업을 할 수 있다.

2. Efficiency

시간적으로나 공간적으로 Linker를 사용하면 효율성의 측면에서 좋다. 시간적으로는 comilpe을 분리할 수 있다는 장점이 있다. 필드에서 코드를 컴파일 하려면 30분, 1시간 넘게 걸리는 코드들이 있다고 한다. 이러한 코드들에서 수정하고 다시 맞는지 확인을 하려면 다시 compile하고 link하는데 시간이 상당히 소모될 수도 있다. 버그를 하나 잡으려고 하루 종일 컴파일만 하다가 끝날 수도 있다고 한다. 이렇게 전체의 파일을 한번에 컴파일 하는 것이 아니라 Program을 작은 부분들로 나누게 되면 작은 부분들을 수정하고 그 파일만Re-Compile하게되면 다른 source file들을 Recompile할 필요가 없어지므로 시간을 매우 아낄 수 있다.

공간적으로는 Library 활용을 통해서 코드 사이즈를 줄일 수 있다. 예를 들어서 자주 사용하는 사용자 정의 함수 같은 경우는 하나의 source file내에 두는 것이 아니라 Library Archive 파일에 두어 다른 코드에서도 재사용 할 수 있고, 복잡하게 보이는 monolothic 파일에 사용되는 함수들을 Library로 빼게 되면 핵심 코드들만 남길 수 있어 Code Review를 하는데에도 좋다. 

Object Files

Linking에 대해 자세히 알아보기 전에 Object Files에 대해 잠깐 알아보자.

Relocatable Object Files는 확장자가 .o 로 끝나는 파일들이다. 이는 Executable Object File을 만들기 위한 중간 형태로 code와 data를 포함하고 있다. .c file로 부터 생성이 되는 파일이다.

Executable Object File은 확장자가 .out 처럼 우리가 실행할 수 있는 파일들을 말한다. a.out은 Linux에서 gcc로 컴파일 할때 이름을 붙여주지 않으면 자동적으로 나오게 된다. Executable Object File은 메모리에 직접 copy될 수 있는 code와 data의 형태를 지니고 있고, 올라가면 바로 execute된다. 

Shared Object File은 .so(Linux), .dll(Windows), .dylib(MAC) 로 끝나는 아카이브 파일이다. Relocatable Object Files의 특별한 타입이며, 컴파일시간에 메모리에 load되거나 dynamic하게 load time이나 run time에 load될 수 있는 파일이다.

 

Linux에서 gcc -o foo something.c else.c 이렇게 하면 각각의 컴파일러는 각각의 c파일들을 Relocatable Object Files의 형태인 main.o, sum.o 이렇게 변환해준다. 이때의 Object File은 우리딴에서 읽을 수 없는 In-Complete Binary 파일이다. 이제 Linker는 이 Object File들을 합쳐 foo라는 이름을 가진 Executable Binary로 만들게 되는 것이다. 

Linker

그래서 결과적으로 Linker는 뭘 하는 놈이냐라는 의문이 드는 것은 당연하다. Executable File을 만들어 주려면 Linker는 아래의 두 가지의 Main Tasks를 수행해야 한다.

1. Symbol Resolution

뒤에서 자세히 언급이 될 부분이지만 각각의 Symbol Reference를 하나의 Symbol Definition에 연관시키는 것이다.

2. Relocation

이는 동일 유형의 모든 섹션을 하나의 새로운 섹션으로 합친다. 그리고 Relocatable Object Files에 들어있는 Symbol들을 새로운 섹션에 재배치 시키게 된다. 그리고 나서 새로운 위치를 반영하기 위해 Symbol들에 대한 참조를 업데이트한다.

 

말이 좀 어렵다. 결과적으로 Linker는 Resolution -> Merge -> Relocation 이 작업들을 순차적으로 수행하며, Symbol Unit을 다룬다고 정리할 수 있다. 위의 Main Task에 대해서는 아래에서 알아보자.

 

그러나 들어가기 전에 앞서서 Define과 Declare의 차이를 명확히 짚고 넘어가야 할 필요가 있다. 우리나라 언어로 번역하면 그놈이 그놈인것 같은데 CS를 전공하는 사람에 있어서 이 차이를 더 명확하게 해야한다. C에서 Macro를 위한 Define말고 실제 할당을 하는 Define의 특성은 변수나 함수에 대한 선언이다. 이는 당연하게도 새로운 메모리 공간이 할당이 되는 것이다. int x = 10; int foo(int a, int b) { ...... } 이런 것이 Define이다.

반면에 Declare하는 것은 Compile을 위한 관련 정보를 적어놓는 것이다. 다시말해 다른 곳에서 정의한 것을 사용하겠다 라는 정도의 의미이다. 컴파일 정보, 즉 주소 정보만 전달을 하게 된다. 이는 메모리 공간의 할당이 전혀 이루어 지지 않는다. 예를 들어 extern int x; int sum(int a, int b); 이런 정보들이라고 할 수 있겠다. 

 

Symbol

Symbol은 name function과 variable에 대한 Lexical Entities라고 정의가 된다. 말이 좀 어렵지만 쉽게 말하자면 function과 variable의 이름이다. 

컴파일러는 Relocatable Object File에 Symbol을 generate한다. 이때 Symbol Definition은 Object File에 있는 Symbol Table에 저장이된다. Symbol Table은 Symbol들의 요약정보이다. 이는 Debugging과 Linking의 위한 정보이다. 특히 Debugging시 많이 사용된다. 이러한 Symbol Table은 ELF format을 따른다. ELF format에 대해서는 뒤에서 다루겠다. 

 

Symbol은 위에서 정의한대로 크게 두 가지로 나뉜다. 이는 function과 object인데, 이때 object는 global variable이나 static variable을 의미한다. 지역변수는 Stack에 저장되기에 Symbol로 취급하지 않는다. Object를 data object 정도로 생각하는 것도 좋은 방법이다. 

함수 자체는 Symbol이지만 함수 안에 있는 데이터는 locally하게 취급되기 때문에 Symbol이 되지 않는다. 

Relocatable Object File에는 define된 데이터와 reference symbol이 있다. 예를 들어서 main 파일 외부에 작성한 function이 있다고 해보자. 그렇다면 그 함수를 사용하기 위해서는 main 파일에서는 그 함수를 reference해야한다. define되지 않아도 우선적으로 Symbol로 취급할 수 있다. 

 

Symbol은 세 가지 형태로 Binding된다.

1. Local Symbols

Local Symbol은 현재 모듈, 즉 현재 파일에서만 베타적으로 defined되거나 reference된 것이다. static attributes가 하나의 예가 되겠다. 

2. Global Symbols

Global Symbol은 말 그대로 전역변수이다. 다른 모듈에서 reference할 수 있는 defined된 Symbol들을 의미한다. 예를 들어 non-static function이나 variables들이 그 예가 되겠다. 

3. External Symbols

Reference된 Global Symbol들이다. 현재 파일에서 정의되지 않아 다른 모듈에서 defined 된 것을 referencing해야하기 때문에 UNDEFINED Symbol이라고도 불린다. External Symbol은 Relocatable Object File에만 있다. Linker로 인해 합쳐지면 Executable Object File에서는 자기의 자리를 찾아가기 때문에 사라지게 된다. 

 

위와 같은 코드가 있다고 하면 왼쪽에서 Global Symbol은 buf, main이 되고, change함수는 External일 것이다. 

오른쪽에서는 buf가 External, Global은 *temp0, swap 정도가 되겠고, Local Symbol은 *temp1이 되겠다.

 

ELF Format

우선 Section에 대해 이해를 해보자. Section이란 뜻 그대로 Object File 내게 같은 속성을 가진 연속적인 공간을 묶고 분리한 공간이다. ELF Format에 따라 Symbol들을 각각의 성격에 맞게 Section 분류할 수 있는데 이는 아래와 같다.

• .text : machine code가 들어있는 공간이다. 우리가 쓴 텍스트들이 Machine Language로 변환되어 들어간다.
• .rodata: Read Only Data가 들어가는 공간이다. const로 선언된 변수들이나 문자열 등이 여기에 들어갈 수 있다.
• .data: Initialize된 Global, Static Variables들이 들어있는 공간이다. (ex. int temp = 10; stataic int tmp = 100;)
• .bss : Uninitialize된  Global, Static Variables들이 들어있는 공간이다. (ex. int i; static int bss; ) 
• .symtab : Symbol Table이 저장된 공간이다. Symbol Table을 보기 위해서는 objdump -t file.o, nm file.o, readelf -s file.o 등의 방식으로 Shell에서 볼 수 있다. 

.bss는 특이한 공간이다. 어차피 변수가 Declare 되었으니 그냥 data section에 넣으면 되지 않을까라는 생각을 할 수도 있겠지만 이렇게 분리시킨 데에는 다 이유가 있다. 이는 Spacial Efficiency를 위한 것이다. 예를 들어 그래프 문제에 대해 PS를 한다고 해보자. 인접 행렬을 사용한다면 대부분 그래프를 넣을 이차원배열을 선언할 것이다. 1000X1000 사이즈의 int형 배열을 만든다고 해보자. 만약 이를 전부 1로 초기화 한다면 메모리 공간은 아마 10^6 * 4byte의 공간을 차지해버릴 것이다. .bss 영역에 들어가면 메모리 공간에 큰 영향을 주지 않는다. .bss 공간에 있는 변수들이 처음부터 막대한 메모리 공간을 차지해서 프로그램의 공간을 확보하는데 도움을 준다. 추가적으로 이런 의미에서 0으로 초기화 된 변수들도 .bss 공간에 들어가게 된다. 

 

다른 섹션들도 있지만 이정도만 책에서 기술하고 있기 때문에 이를 중심적으로 보았다.

ELF는 (Executable and Linkable Format)의 약자이다. 이는 Linux Object File에서의 Standard Binary Format이다.

그러나 Object File의 Format은 ISA 혹은 시스템마다 다를 수 있다. 예전 UNIX에서는 a.out이 사용되었고, COFF(Common Object File Format)는 System V의 초기버전에서 사용되었다. PE(Portable Executable)은 MS에서 COFF에서 떨어져나왔으며 현대 UNIX에서는 ELF를 사용하고 있다. 

왼쪽 그림은 ELF Executable Object File의 Format이며, 오른쪽이 그 전에 봤던 ELF Relocatable Object File Format이다. ELF헤더 및 다른 Section이 거의 비슷한 것을 볼 수 있다. ELF Header는 word size, byte ordering 등 전반적인 메타데이터에 대한 정보를 담고 있다. Segment Header Table은 Linking 후에 Executable 파일에 생성이 되면 loading을 위한 정보가 저장된다. Relocatable Object File의 .rel text나 .rel data 같은 경우는 Linker가 나중에 처리해야할 작업들 정도로 생각하면 될 것이다. 

 

여기까지가 Symbol Resolution을 위한 Symbol의 도입부이다. 

본격적으로 Linker가 수행하는 첫 번째 일인 Symbol Resolution에 대해 알아보자.

 

 

 

Reference

Randal E. Bryant, & David R. O’Hallaron. (2016). Computer Systems A Programmer’s Perspective Third edition. Carnegie Mellon University: Pearson.