링크(Linkers) 와 로더(Loaders)

문서 정보

원문: http://www.linuxjournal.com/article/6463
출처 : http://blog.naver.com/simz/20024938289
저자: Sandeep Grover, 2002.11.26
정리: 이동우(leedw at ssrnet.snu.ac.kr), 2005.11.26

Linkers and Loaders

링킹(Linking)이란 코드와 데이타들을 한데 묶어 메모리에 로드될 수 있는 하나의 실행파일 형태로 만드는 작업을 말한다. 링킹은 compile time, load time(로더에 의해) 혹은 run time(어플리케이션에 의해)에도 이루어질 수 있다. 링킹의 유래는 1940년까지 거슬러 올라가는데 당시에는 수작업으로 이루어졌다고 한다. 현재는 링커(Linker)가 있어서 동적으로 링크되는 공유 라이브러리(shared library)와 같은 복잡한 작업을 수행해 주고 있다. 이 문서에서는 재배치(relocation)부터 심볼 해석(symbol resolution)까지 이르는 링킹의 각 측면들을 간단히 살펴보도록 하겠다. 편의상 x86 아키텍쳐에서 구동되는 Linux 기반의 ELF 포맷과 GNU 컴파일러(gcc)/링커(ld)에 촛점을 맞추어서 논의하도록 하겠다. 그러나 링킹의 기본 컨셉은 프로세서나 운영체제, 오브젝트 포맷과 상관없이 모두 동일하다고 보면 된다.

 

Compiler, Linker and Loader in Action: the Basics

 

다음과 같이 a.c와 b.c 두 개의 프로그램이 있다고 생각해 보자. 쉘에서 두 코드들을 gcc에 입력할 때 다음과 같은 작업들이 수행된다.

gcc a.c b.c

· a.c에 대해 전처리기(preprocessor)가 실행되어 전처리기 중간 파일(a.i)이 생성된다.

   cpp other-command-line options a.c /tmp/a.i

· a.i에 대해 컴파일러가 실행되어 a.s라는 어셈블러 코드가 생성된다.

   cc1 other-command-line options /tmp/a.i -o /tmp/a.s

· a.s에 대해 어셈블러가 실행되어 a.o라는 object 파일이 생성된다.

   as other-command-line options /tmp/a.s -o /tmp/a.o

cpp, cc1과 as는 각각 GUN 전처리기, 컴파일러, 어셈블러로서 표준 GCC 배포본에 들어있는 툴들이다.
위의 3단계 과정이 다시 b.c에 적용되어 b.o가 생성이 된다. 이제 링커는 2개의 오브젝트 파일(a.o, b.o)을 입력받아 최종 실행파일을 만들게 된다.

   ld other-command-line-options /tmp/a.o /tmp/b.o -o a.out

최종으로 생성되는 실행파일(a.out)은 이제 메모리에 로드될 수 있다. 실행파일을 실행하기 위해선 shell prompt 상에서 파일 이름만 타이핑해 주면 된다.

./a.out

쉘은 로더 함수를 호출하게 되고 로더는 실행파일 a.out속에 있는 코드와 데이타를 메모리에 복사한다. 그리고 프로그램의 시작 주소로 제어권을 넘겨주게 된다. 로더는 execve라 불리는 프로그램으로서 실행파일속에 들어 있는 코드와 데이타를 메모리에 로드하고 코드의 첫번째 주소에 위치한 instruction으로 점프하여 프로그램을 실행시키는 작업을 수행한다.
a.out는 a.out 오브젝트 파일들의 "Assembler OUTput"이라는 의미에서 명명되었다.. 이후로 오브젝트 포맷은 변해갔지만 그 이름은 계속 사용되었다.

 

Linkers vs. Loaders

링커와 로더는 여러 유사한, 그러나 개념적으로는 다른 작업들을 수행한다.

· 프 로그램 로딩(Program loading). 이것은 하드 디스크에 저장되어 있는 프로그램 이미지를 메인 메모리에 복사하여 실행상태로 만드는 것을 말한다. 어떤 경우에는 프로그램 로딩은 디스크 페이지에 가상 주소를 매핑하거나 저장 영역을 할당하는 것도 포함된다.

· 재 배치(relocation). 컴파일러와 어셈블러는 입력받은 각 모듈에 대해 0번지로 시작하는 오브젝트 코드를 생성한다. 재배치는 같은 타입의 모든 section을 하나의 단일 section으로 통합함으로써 프로그램의 각 파트에 로딩 주소를 할당하는 작업이다.

· 심 볼해석(Symbol resolution). 하나의 프로그램은 여러 서브 프로그램으로 구성되어 있다. 하나의 서브 프로그램이 다른 프로그램을 참조할 때 심볼이 사용된다. 링커가 하는 일은 심볼의 위치를 기억해 두었다가 심볼을 사용하는 호출모듈의 오브젝트 코드를 패치하여 심볼 참조를 해석(resolve)한다.

링커와 로더의 기능 사이에는 겹치는 부분이 상당히 많다. 한가지 생각해 볼 수 있는 방법은, 로더는 프로그램 로딩을 수행하고, 링커는 심볼 해석(symbol resolution)을 담당며 둘 다 재배치(relocation)을 할 수 있다는 것이다.

 

Object Files

오브젝트 파일은 다음과 같이 3개의 형태로 나뉜다.

· 재배치 가능한 오브젝트 파일(relocatable object file). compile-time에 다른 재배치 가능한 오브젝트 파일과 통합할 수 있어 하나의 실행파일이 생성될 수 있는 형태의 바이너리 코드와 데이타를 포함한다.

· 실행 오브젝트 파일(executable object file). 메모리에 직접 로딩되어 실행될 수 있는 형태의 바이너리 코드와 데이타를 포함한다.

· 공유 오브젝트 파일(shared object file). load-time이나 run-time에 동적으로 메모리에 로드되고 링크될 수 있는 특수한 타입의 재배치 가능한 오브젝트 파일.

컴파일러와 어셈블러는 재배치 가능한 오브젝트 파일(또한 공유 오브젝트 파일도)을 생성한다. 링커는 그러한 오브젝트 파일을 통합하여 실행파일을 생성한다.
오 브젝트 파일은 시스템에 따라 각기 다른 형태를 가지는데 최초 unix 시스템에서는 a.out 포맷을 사용했었다. system V의 초기 버전에서는 COFF(common object file format)을 사용했고 windows NT는 PE(portable executable)라 불리는 COFF의 변종을 사용한다. IBM은 자체적으로 설계한 IBM 360 포맷을, Linux나 Solaris와 같은 현대 unix 시스템은 UNIX ELF(execuatble and linking format)를 사용한다.
이 문서에서는 주로 ELF에 대해 촛점을 두겠다.

표1. 전형적인 재배치 가능한 ELF오브젝트 파일 형식

ELF Header

.text

.rodata

.data

.bss

.symtab

.rel.text

.rel.data

.debug

.line

.strtab

위 그림은 전형적인 ELF relocatable object file의 포맷을 보여주고 있다. ELF 헤더는 4바이트 magic string('0x7f', 'E', 'L', 'F')으로 시작된다. ELF relocatbale object file 내에 있는 여러 section들을 살펴보면 다음과 같다.

· .text : 컴파일된 프로그램의 기계어 코드

· .rodata : 읽기 전용 데이타(read-only data). printf 구문에 들어가는 format string등이 이 영역에 저장된다.

· .data : 초기화된 전역 변수가 저장되는 영역

· .bss : 초기화되지 않은 전역 변수가 저장되는 영역. BSS는 "Block Storage Start"의 약자이다. 이 section은 실제로는 오브젝트 파일내에서 아무 공간도 차지하지 않고 있다.

· .symtab : 프로그램 내에서 정의되거나 참조되고 있는 전역 변수와 함수에 대한 정보를 담고 있는 심볼 테이블. 이 테이블에는 로칼 변수에 대한 정보는 담고 있지 않은데 이는 스택이 그 정보를 담고 있기 때문이다.

· .rel.text : 링커가 이 오브젝트 파일과 다른 오브젝트 파일을 combine할 때 .text 내에서 변경되어야 할 위치들의 리스트를 담고 있는 영역.

· .rel.data : 현재 모듈에서 참조만 되고 정의되어 있지 않은 전역 변수의 재배치 정보

· .debug : 지역 및 전역 변수를 엔트리로 가지는 디버깅 심볼 테이블. 이 섹션은 컴파일러 옵션 -g가 주어졌을 때 생성된다.

· .line : 원본 c소스 프로그램의 라인번호와 .text 섹션에 있는 머신 코드간의 매핑 정보. 디버거 프로그램에서 이 정보를 사용한다.

· .strtab : .symtab과 .debug 섹션에 있는 심볼 테이블들의 스트링 테이블

Symbols and Symbol Resolution

재배치 가능한 모든 오브젝트 파일에는 심볼 테이블과 그와 관련된 심볼들을 가지고 있다. 링커의 맥락으로 살펴보면 심볼은 다음과 같은 종류가 있다.
· 입력 모듈에서 정의되어 있는 global symbol. 다른 모듈에서 참조할 수 있다. 일반 함수와 전역 변수가 여기에 속한다.

· 입력 모듈에서 참조하는 하고 있지만 다른 곳에 정의된 global symbol. extern으로 선언된 함수와 변수가 여기에 해당

· 입력 모듈에서 정의되어 해당 모듈에서만 배타적으로 참조할 수 있는 local symbol. 정적 함수와 정적 변수가 이 범주에 속한다.

링커는 입력으로 들어온 재배치 가능한 오브젝트 파일의 심볼 테이블에 있는 엔트리를 검색해서 심볼 참조(symbol reference)를 해석한다. local symbol은 한 모듈에서 다중으로 정의할 수 없기 때문에 local symbol의 해석은 간단한 편이다. 반면에 global symbol은 약간의 기교를 필요로 한다. 컴파일할 때 캄파일러는 각각의 global symbol을 '약'하게, 혹은 '강'하게 export할 수 있다. 함수와 초기화된 전역 변수들은 강한 무게로 export되는 반면 초기화 되지 않은 전역 변수들은 약한 무게로 export된다. 링커는 다음과 같은 규칙을 사용해 심볼을 해석하게 된다.

   1. 여러 개의 strong symbol은 허락되지 않는다.

   2. 하나의 strong symbol과 여러 개의 weak symbol이 주어질 때, strong symbol을 선택한다.

   3. 여러 개의 weak symbol이 있을 경우 그 중 아무거나 선택한다.

예를 들어, 다음과 같은 두 개의 프로그램을 링크시킬 경우 링커는 에러를 발생시키게 된다.

/* foo.c */               /* bar.c */

int foo () {               int foo () {

   return 0;                  return 1;

}                          }

                           int main () {

                              foo ();

                           }

foo(전역 함수로서 strong symbol에 해당한다.)가 두 번 정의되어 있으므로 링커는 에러 메시지를 출력한다.

gcc foo.c bar.c

/tmp/ccM1DKre.o: In function 'foo':

/tmp/ccM1DKre.o(.text+0x0): multiple definition of 'foo'

/tmp/ccIhvEMn.o(.text+0x0): first defined here

collect2: ld returned 1 exit status

collect2는 링커 ld의 wrapper로서 gcc에 의해 호출된다.

 

Linking with Static Libraries

정적 라이브러리(static library)는 비슷한 유형의 오브젝트 파일들을 모아 놓은 것이다. 이 라이브러리는 아카이브(archive) 형태로 디스크에 저장되어 있다. 아카이브에는 검색을 빠르게 하기 위해 디렉토리 정보도 포함되어 있다. ELF archive는 매직 스트링 "!<arch>\n"로 시작한다.
정적 라이브러리는 컴파일러 툴(링커)에 인자로 넘겨진다. 유닉스 시스템에서는 libc.a는 대부분의 프로그램이 사용하는 printf, fopen를 포함한 모든 c라이브러리 함수를 포함하고 있다.

gcc foo.o bar.o /usr/lib/libc.a /usr/lib/libm.a

libm.a는 표준 수학 라이브러리(math library)로 sqrt, sin, cos등등의 수학 함수가 정의된 오브젝트 모듈들을 포함하고 있다.

static library를 사용해 심볼 해석을 진행하는 과정에서 링커는 커맨드 라인에서 입력으로 들어온 인자의 왼쪽부터 오른쪽 방향으로 재배치 가능한 오브젝트 파일과 아카이브를 검색한다. 이 검색중에 링커는 실행 파일로 만들어질 재배치 가능한 오브젝트 파일의 묶음인 O집합, 해석되지 않은 심볼 리스트를 담고있는 U집합, 입력 모듈에서 정의된 심볼들을 나타내는 D집합을 관리하게 된다. 초기에는 이 세개의 집합은 비어있게 된다.
· 링커는 커맨드 라인에서 입력으로 들어온 인자가 오브젝트 파일인지 아카이브인지를 결정한다. 만약 입력 모듈이 재배치 가능한 오브젝트 파일이라면 링커는 그것을 O집합에 추가하고 U와 D를 업데이트한 후 다음 입력 파일로 진행한다.

· 만 약 입력 모듈이 아카이브라면 아카이브를 구성하는 모듈 멤버들을 쭉 검색해서 U집합에 들어있는 해석되지 않은 심볼과 매치되는지 살펴본다. 만약 아카이브 멤버중에서 해석되지 않았던 심볼을 정의해 놓은 모듈이 있다면 그 모듈은 O리스트에 추가되고 U와 D는 업데이트된다. 이 과정은 모든 오브젝트 파일 멤버들에게 행해진다.

· 입력 모듈에 대해 위와 같은 두 단계가 모두 행해진 후 만약 U집합이 비어있지 않다면 링커는 에러를 리포팅하고 종료한다. U집합이 비어있다면 O집합에 있는 오브젝트 파일들은 merge되고 재배치되어 실행파일이 만들어진다.

이 과정을 통해 왜 정적 라이브러리가 링커 커맨드의 마지막에 위치하는지 알 수 있게 된다. 두 개의 라이브러리가 서로 순환적 의존 관계에 있는 경우에는 특별히 주의를 기울여야 한다. 커맨드 라인에 라이브러리를 입력할 때 심볼들이 아카이브의 멤버 라이브러리에 의해 참조될 수 있도록 순서를 가지고 입력되어야 한다. 심볼이 정의된 라이브러리가 그것을 참조하는 라이브러리보다 앞선 순으로 입력되어야 하고 만약 해석안된 심볼이 한 개 이상의 정적 라이브러리 모듈에서 정의되어 있을 때는 커맨드 라인에서 첫번째로 입력된 라이브러리의 정의를 따르게 된다.

 

Relocation

 

링커가 심볼의 해석을 모두 끝내게 되면 각각의 심볼 참조는 오직 하나의 심볼 정의를 갖게 된다. 이 시점에서 링커는 다음과 같은 두 단계의 재배치(relocation) 작업을 시작하게 된다.

· section 과 심볼 정의(symbol definition)들을 재배치한다. 링커는 같은 타입의 섹션들을 묶어 하나의 새로운 섹션으로 통합한다. 예를 들어 링커에 입력된 재배치 가능한 파일들에 있는 각각의 .data 세션을 하나의 단일한 .data 섹션으로 머지하여 최종 실행파일을 생성한다. .code 섹션에도 같은 작업이 수행된다. 그리고 링커는 이렇게 통합하여 생성된 섹션들과 입력 모듈에서 정의한 섹션들, 그리고 각각의 심볼들에게 run-time 메모리 주소를 할당한다. 이 단계가 끝나면 프로그램 내에 있는 모든 인스트럭션과 전역 변수들은 고유한 load-time 주소를 갖게 된다.

· section내에 있는 심볼 참조를 재배치한다. 링커는 이 단계에서 코드 및 데이타 섹션에 있는 모든 심볼 참조를 변경하여 심볼이 정의된 정확한 load-time 주소를 가리키게 만든다.

어셈블러가 unresolved 심볼을 만나게 되면 해당 오브젝트에 relocation entry를 생성하고 이를 .relo.text/.relo.data 섹션에 저장한다. relocation entry에는 해당 심볼의 참조를 어떻게 해석할 것인지에 대한 정보를 담고 있다. 전형적인 ELF relocation entry에는 다음과 같은 정보들로 구성되어 있다.

· Offset : 재배치 해야할 심볼 참조의 section offset. 재배치 가능한 파일에서 보면 이 값은 섹션의 시작부터 심볼 참조 위치까지의 바이트 옵셋 값이다.

· Symbol : 변경된 심볼 참조가 가리켜야할 심볼. 각각 재배치가 될 심볼 테이블의 인덱스라고 보면 된다.

· Type : 재배치 타입, 정상적인 경우 프로그램 카운터(PC) 상대 주소 방식(PC-relative addressing)을 의미하는 "R_386_PC32"이다. "R_386_32"는 절대 주소 방식(absolute addressing)을 의미한다.

링커는 재배치 가능한 오브젝트 모듈에 있는 모든 relocation entry를 조사해서 unresolved symbol을 type에 따라 재배치하게 된다. 가령 심볼이 "R_386_PC32" 타입인 경우, 재배치 주소는 S+A-P로 계산이 이루어지고 "R_386_32" 타입인 경우 S+A 식으로 계산이 된다. 여기서 'S'는 relocation entry의 심볼 값, 'P'는 section offset이나 재배치될 주소값(relocation entry에 저장된 offset값을 사용해 계산한다.), 'A'는 relocatable field의 값을 계산할 때 필요한 주소를 의미한다.

 

Dynamic Linking: Shared Libraries

 

정적 라이브러리(static library)는 몇몇 심각한 단점을 가지고 있다. 예를 들어 printf나 scanf와 같은 표준 라이브러리 함수를 생각해 보자. 이런 함수들은 거의 모든 어플리케이션에서 사용하고 있다. 만약 시스템이 50-100개의 프로세스를 실행하게 되면 각각의 프로세스는 printf, scanf 함수가 구현된 실행 코드를 가지게 될 것이다. 이것은 중요한 메모리 공간을 차지하게 되는 원인이 된다. 반면 공유 라이브러리(shared library)는 이런 정적 라이브러리의 결함을 해결하고 있다. 공유 라이브러리는 run-time시 어느때나 임의의 메모리 주소에 로딩될 수 있는 object module로서 이미 메모리에서 실행중인 프로그램에 의해서 링크될 수 있다. 공유 라이브러리는 때때로 공유 오브젝트(shared object)라고도 불린다. 대부분의 unix 시스템에서는 이런 공유 오브젝트를 ".so" 접미사로 표기하지만 HP-UX에서는 ".sl"로, MS 시스템에서는 DLL(dynamic link library)로 표기하기도 한다.
공유 오브젝트를 빌드하기 위해선 컴파일러에 특별한 옵션을 주어 실행시킨다.

gcc -shared -fPIC -o libfoo.so a.o b.o

위 커맨드는 컴파일러 드라이버에게 2개의 오브젝트 모듈 "a.o", "b.o"를 묶어 "libfoo.so"라는 이름의 공유 라이브러리를 생성하게 만드는 커맨드이다.1 "-fPIC" 옵션은 position independent code(PIC)를 생성하도록 지시하는 옵션이다.

이제 "a.o", "b.o"에 의존적인 메인 오브젝트 모듈 "bar.o"를 가정해 보자. 이 경우 링커는 다음과 같은 커맨드로 실행된다.

gcc bar.o ./libfoo.so

이 커맨드를 통해 load-time에 "libfoo.so"를 링크할 수 있는 형태의 "a.out" 실행파일이 생성된다. 이 "a.out"에는 공유 라이브러리를 링크했기 때문에 "a.o", "b.o"가 포함되어 있지 않다. 만약 공유 라이브러리 대신 정적 라이브러리를 포함했다면 그 2개의 오브젝트 모듈 코드가 모두 들어 있을 것이다.
여기서 실행파일은 단지 "libfoo.so"의 데이타나 코드를 참조할 수 있도록 심볼 테이블 및 재배치 정보만 담고 있다가 run-time에 해석이 이루어진다. 따라서 "a.out"은 "libfoo.so"에 의존성을 가진 불완전한 실행파일이라고 할 수 있다. 또한 실행파일은 ".interp"라는 섹션을 가지고 있는데 여기에는 동적 링커(dynamic linker)의 이름이 포함되어 있다. 이것 또한 linux 시스템에 포함된 공유 오브젝트(ld-linux.so)이다. 그래서 실행파일이 메모리에 로딩될 때 로더는 이 동적 링커에 실행 제어를 넘긴다. 동적 링커는 공유 라이브러리를 프로그램의 주소 영역에 매핑시키는 start-up 코드를 포함하고 있다. 동적 링커는 다음과 같은 작업을 수행한다.
· "libfoo.so"의 텍스트와 데이타를 실행파일의 memory segment로 재배치한다.

· "libfoo.so"에 정의된 심볼을 참조하는 "a.out"내의 모든 심볼 참조를 재배치한다.

마지막으로 이 작업이 끝나면 동적 링커는 어플리케이션에 실행 제어를 넘긴다. 이때부터 공유 오브젝트의 위치가 메모리에 고정된다.

 

Loading Shared Libraries from Applications

 

공유 라이브러리는 어플리케이션이 실행중이더라도 언제든 로딩이 가능하다. 공유 라이브러리를 실행 파일로 링크하지 않아도 어플리케이션은 동적 링커에게 공유 라이브러리를 메모리에 로딩하고 링크하도록 명령을 내릴 수가 있다.2 리눅스, 솔라리스와 그외 다른 시스템에서는 공유 오브젝트를 동적으로 로딩할 수 있는 일련의 함수 콜을 제공하고 있다.
리눅스에서는 공유 오브젝트를 로딩할 때 사용할 수 있는 "dlopen", "dlsym, "dlclose"등의 system call을 지원하고 있는데 각각 공유 오브젝트를 로딩하고 공유 오브젝트내에 있는 심볼을 검색하고 공유 오브젝트를 close하는 기능을 제공하고 있다. 윈도우즈 시스템에서는 "LoadLibrary", "GetProcAddress" 함수가 각각 "dlopen", "dlsym"에 해당하는 함수들이다.

Tools for Manipulating Object Files (Object File 관리하는 Tool)

 

다음은 리눅스에서 오브젝트나 실행파일을 관리하는데 사용할 수 있는 툴들을 소개한 것이다.

ar : 정적 라이브러리를 생성한다.

objdump : 가장 중요한 바이너리 툴. 오브젝트 바이너리 파일내의 모든 정보를 출력할 수 있다.

strings : 바이너리 파일내에 printable string을 나열한다.

nm : 해당 오브젝트 파일의 심볼 테이블에 정의된 심볼들을 나열한다.

ldd : 오브젝트 바이너리가 의존하고 있는 공유 라이브러리들을 나열한다.

strip : 심볼 테이블 정보를 삭제한다.