7. Linking

1. Static Linking

• 대부분의 compilation system에는 compiler driver를 제공하고 이는 언어 전처리기, 컴파일러, 어셈블러, 링커를 호출하게 됨
• 언어 전처리기(language preprocessor) : C preprocessor(cpp)는 C언어 소스 파일을 ASCII 파일로 바꾸어 줌(main.c → main.i)
• 컴파일러(cc1) : ASCII 어셈블리 언어 파일로 바꿔주는 역할임(main.i → main.s)
• 어셈블러(as) : relocatable object file로 바꾸어 줌(main.s → main.o)
• 링커 : relocatable object file들을 모아서 executable object file을 만들어줌

• 소스 코드들 → 재배치 가능한 오브젝트 파일 → 실행가능한 오브젝트 파일

• 컴파일러, 어셈블러 → 재배치 가능한 오브젝트 파일 생성

• 링커 → 실행가능한 오브젝트 파일 생성

a) Object Files

• Object module은 byte 코드, Object file은 그 byte코드를 디스크에 저장한것.

• 단지 byte블록의 집합. 이 블록들 중에는 프로그램의 코드, 프로그램 데이터, 링커와 로더를 가이드하는 자료구조가 포함되어 있음

i) Relocatable Object File(재배치 가능한 오브젝트 파일)

• 이진코드와 데이터를 포함하며 다른 재배치 가능한 오브젝트 파일과 컴파일 단계에서 결합되어 실행가능한 오브젝트 파일을 만들게 됨

• ELF header는 이 파일을 만든 시스템의 워드 사이즈, 바이트 순서와 같은 정보와 링커가 이 오브젝트파일을 이해하고 파싱 하는데 필요한 정보가 포함되어 있음
각 Section 별 포함하고 있는 정보

.text	컴파일된 프로그램의 기계어 코드
.rodata	읽기 전용 데이터(eg. printf의 format string, jump tables for switch statements)
.data	초기화된 전역 C 변수들. 지역 변수들은 실행 중 stack에서 관리되게 되고 .data와 .bss 섹션에서는 나타나지 않음
.bss(Block Storage Start)	초기화되지 않은 전역 변수들. 이 섹션은 실제로 공간을 차지하지는 않음(초기화되지 않았기에). 프로그램이 실행되면서 메모리를 차지하게 됨
.symtab	프로그램 안에서 정의되고 참조되는 함수와 전역변수들의 정보를 모은 Symbol table
.rel.text	링커가 다른 오브젝트 파일과 결합할때 .text 섹션에서 변경되어야 할 위치의 리스트가 있음. 일반적으로 다른 위치에서 선언된 전역변수를 참조하거나 외부의 함수를 호출할는 부분이 수정되어야 할 부분임
.rel.data	어떤 모듈에 의해 참조되거나 정의된 전역변수의 재배치 정보가 저장됨
.strtab	.symtab의 symbol 테이블과 .debug 섹션 그리고 section header의 섹션 이름들을 위한 문자열 테이블

ii) Symbols and Symbol Tables

• local linker symbol ≠ 지역 변수 ⇒ 지역변수들은 Symbol Table에 존재하지 않음! 얘네들은 실행 중에 stack에서 관리됨

• Symbol은 컴파일러에 의해서 생성됨

iii) Executable Object File

• 이진코드와 데이터를 포함하며 메모리로 복사되어 바로 실행가능한 파일임

• ELF header : 전반적인 파일의 포맷에 대해 서술. 프로그램이 실행할 때 제일 처음 instruction의 주소도 포함함

• .text, .rodata, .data는 relocatable object file과 비슷하지만 이들의 메모리 주소는 run time memory 주소로 relocate된 상태임

• 모든 오브젝트 파일이 relocate 되면서 서로 연결되었기에 .rel 영역은 필요가 없음

• ELF executable object file은 메모리에 쉽게 올릴 수 있도록 디자인되었음(인접한 덩어리들은 인접한 메모리 영역으로 할당되도록 하여서 ← 이 매핑은 segment header table에 서술되어있음)

iv) Shared Object File(↔ Shared Libraries)

• 재배치 가능한 오브젝트 파일의 특별한 형태로 load time(프로그램을 메모리에 올릴 때)이나 run time(프로그램 실행 중)에 임의의 주소에 로드되고 동적으로 링크 될수 있는 오브젝트 파일임

• 정적 라이브러리의 단점을 극복하기 위해 도입됨
• 단점 1 : 정적 라이브러리도 주기적으로 업데이트가 되는데 업데이트가 될 때마다 프로그램을 relink해주어야 함
• 단점 2 : 거의 모든 C 프로그램이 standard I/O 함수를 사용하는데 그로 인해 모든 프로세스 들이 이 함수에 대한 text segment를 각각 가지고 있어야 함 → 메모리 자원의 낭비임

• .so 파일로 저장됨. 해당 파일의 코드와 데이터는 해당 라이브러리를 사용하는 모든 executable object file에게 공유됨

b. Symbol Resolution

• 오브젝트 파일은 Symbol(변수, 함수..)을 정의하기도 하고 참조하기도 함. Symbol Resolution의 목적은 각각의 Symbol 참조를 해당하는 선언에 연관 지어 주는 것임

i) 동일한 정의가 여러 개 일때의 규칙

• 컴파일러가 컴파일 시 전역 symbol들을 assembler에게 넘겨주며 strong 혹은 weak 라고 구분해서 넘겨 주게 됨
• Strong symbols : 함수, 초기화된 전역 변수
• Weak symbols : 초기화되지 않은 전역 변수

• Rule 1: 강한 symbol이 여러 개 있는 경우는 허용하지 않음

• Rule 2: Strong symbol과 multiple weak symbol이 주어졌을 때 Strong symbol을 선택

• Rule 3: 여러 개의 weak symbol이 있을 때 아무거나 선택함

ii) 정적 라이브러리를 활용한 Linking

• 실용적으로, 모든 컴파일 시스템은 관련된 오브젝트 모듈을 하나의 파일(static library)로 패키징하는 메커니즘을 제공함 ⇒ 장점 : 디스크, 메모리 상에서의 크기 감소

• 정적 라이브러리를 사용하지 않고 이를 가능케 하는 방법? → 단점이 너무 많다
1. 컴파일러에서 standard function(standard I/O, string manipulation, integer math functions)에 대한 호출을 인지한 후 그것에 대한 코드를 생성해주는 방법 → 컴파일러에게 너무나 많은 복잡성을 야기함
2. 하나의 relocatable object 모듈로 standard C 함수들을 몰아 넣는 방법(거대해짐) → 모든 executable file들이 해당하는 standard function에 대한 복사본을 가지고 있어야 하기에 디스크 공간의 낭비가 발생함, standard function에 대한 아무리 작은 수정이라도 전체 코드를 다시 컴파일 해야 함
3. 각각의 standard 함수별로 relocatable object file을 만드는 방법 → link시 모든 오브젝트 모듈들을 다 명시해주어야함 ⇒ 불편함..
• unix> gcc main.c /usr/lib/printf.o /usr/lib/scanf.o ...

• ⇒ 정적 라이브러리 도입 : 관련된 함수들이 각각의 분리된 모듈로 컴파일 되고 하나의 정적 라이브러리 파일로 패키징됨
• 프로그램에서 standard C library와 math library에서의 함수를 활용할 때
• unix> gcc main.c /usr/lib/libm.a /usr/lib/libc.a
• 위와 같이 실행하면 링크 시, 링커가 프로그램에서 사용하는 함수에 대한 오브젝트 모듈만을 복사해서 executable 오브젝트 파일에 넣게 됨 → 디스크, 메모리 상에서의 크기 감소

• Unix 시스템에서는 정적 라이브러리는 archive 형태로 저장이 됨(.a suffix, ex) libvector.a)

iii) How Linkers Use Static Libraries to Resolve References

• E : relocatable object files의 집합

• U : unresolved symbol의 집합

• D : 입력 파일들에서 정의된 symbol의 집합

• unix > gcc foo.c libx.a libz.a liby.a
• 커맨드 라인에서 각각의 입력 파일에 대해 순차적으로 진행함 ⇒ ordering이 중요함 library가 해당 함수를 사용하는 오브젝트 파일보다 먼저 나오면 에러 발생 ⇒ 그래서 library는 input의 제일 끝에 위치시킴
• 입력 파일 f가 오브젝트 파일이면 E에 추가하고 U(참조는 하는데 정의되지 않은 unresolved symbols)와 D(정의된 symbol들)를 업데이트
• 입력 f가 아카이브 일 때, 아카이브의 멤버들을 대상으로 U에 매치되는 symbol이 있는지 확인. 매치되는 symbol이 있을 경우 해당 오브젝트 파일을 E에 추가하고 U에서 unresolved symbol 삭제. D에는 그 정의 추가
• 링커가 입력 파일에 대한 스캔을 끝냈을 때, U에 값이 남아있다면 에러가 발생함

c. Relocation ⇒ Executable Object Files

• Symbol resolution 단계가 끝나고 나면 각각의 입력 오브젝트 모듈에 대해 code와 data 섹션의 정확한 크기 알게 됨. 그 후 입력 모듈들을 통합하며 각각의 symbol들에 대해 run-time address를 할당하는 과정
• Relocating sections and symbol definitions : 링커가 각 입력 모듈들(relocatable object files) 에서 각 섹션(.data, .bss .code ..)을 통합하여 통합된 섹션을 만듦. 그 후 런타임 시의 메모리 주소를 통합된 섹션에 대해 할당함
• Relocating symbol references within sections : code와 data 섹션에서 symbol reference의 값들을 런타임 메모리 주소를 가리키도록 변경함

i) Relocation Entries

• 어셈블러가 오브젝트 모듈을 만들 시, 외부에서 참조한 code와 data는 현재 오브젝트 모듈에서 주소값을 찾을수가 없음. 그래서 어셈블러가 메모리 위치를 모르는 오브젝트를 만날 때, relocation entry라는 것을 생성함 ⇒ linker가 이 relocation entry를 이용하여 symbol의 참조 주소를 어디로 변경해야 할지 결정함

• code에 대한 relocation entry는 .rel.text에, 초기화된 data에 대한 relocation entry는 .rel.data에 위치함

• offset : 해당 section에서 참조를 재배치 해야 할 symbol의 offset

• symbol : 수정된 참조가 가리켜야 할 symbol

• type : relocation하는 방법의 타입

ii) Relocating 동작 과정

• object 모듈 안에서의 메모리 주소 ↔ 런타임 시의 메모리 주소

• .text의 주소 : 0x0 ↔ 0x80483b4

• call instruction의 주소 : 0x6 ↔ 0x80483ba

• reference를 재배치 해야 할 곳의 주소 : 0x7(refptr) ↔ 0x80483bb(refaddr)

• ADDR(swap) : 0x80483c8

• reference가 swap함수가 위치한 곳을 가리키게 하기 위하여 refptr의 value를 업데이트 해줌(Fig7.9 : line 8)

• 위의 과정을 거쳐서 relocating이 완료되면 executable object file에는 아래와 같이 구성됨

iii) 함수 호출 과정

• 런타임 시, call instruction은 0x80483ba의 주소에 위치해 있고 CPU가 이 call instruction을 실행할 시, PC의 값은 0x80483bf임

• 이 때의 PC값에 대해 *refptr(0x9)의 값을 더하면 ADDR(r.symbol)의 값을 가리키게 되어 swap함수를 가리키고 실행하게됨

Dynamic Linking

• 동적 링킹의 기본 아이디어는 executable file이 생성될 때 어느 정도의 링킹과정을 진행하고 프로그램이 로드될 때 링킹 프로세스를 완료하는 것임

• executable file 생성 시, 동적 라이브러리의 코드와 데이터를 다 복사하지 않고 relocation정보와 symbol table 정보만을 복사함. 그리하여 런타임 시 참조가 해결될 수 있도록 함

a. 동적 라이브러리를 활용한 Dynamic Linking

• loader가 p2를 로드하고 실행시킬 시 p2가 .interp section(dynamic linker의 경로 이름, shared object의 경로)을 가지고 있다는 것을 확인하고 application을 바로 실행시키지 않고 dynamic linker를 로드하고 실행시킴

• 그 후 libc.so와 libvector.so의 text와 data를 임의의 메모리 영역에 relocate함

• p2에서 libc.so와 libvector.so의 symbol들을 참조하는 부분들에 대해 relocate진행하고 링크 완료함

• 동적 라이브러리의 위치는 프로그램의 실행 동안에는 바뀌지 않음

b. Application runtime 중 동적라이브러리 로드 & 링크

• dlopen이라는 함수를 통하여 동적 라이브러리를 부르고 dlsym이라는 함수를 통해 그 symbol에 대한 주소를 얻어서 필요한 함수를 호출할 수 있게 됨

Loader

• executable object file p를 실행시키기 위해 unix> ./p 를 실행하면 메모리에 상주하는 운영체제 코드인 loader가 이를 호출해줌(built-in shell command가 아니기에)

• loader는 executable object file의 코드와 데이터를 디스크에서 메모리로 복사하고 프로그램의 first instruction위치(etnry point)로 점프하면서 프로그램을 실행시켜줌

i) Loader의 프로그램 실행 & 종료 과정

1. 실행 가능한 오브젝트 파일에서 코드와 데이터 영역을 메모리 상으로 복사함

2. 프로그램의 entry point 부분으로 점프함(_start symbol의 주소). _start 주소에 위치한 startup code는 crt1.o 오브젝트 파일로 정의되어 있고 이는 모든 C프로그램에 대해서 동일함

3. .text와 .init 영역에서의 초기화 routine들을 호출한 후 startup code가 atexit routine을 호출함 → 이 routine은 애플리케이션이 정상적으로 종료되기 위해 호출되어야 할 루틴들을 뒤에 추가함

4. exit 함수는 atexit에 의해 추가된 함수들을 실행시키고 운영체제로 제어권을 넘김