[CSAPP] 7.7 Relocation(재배치)

7.7 Relocation(재배치)

• linker가 symbol resolution 단계를 끝내면 코드의 각 symbol reference를 하나의 symbol definition = input object modules 중 하나의 symbol table entry와 연결한다.
• 이 때 linker는 input object modules의 code, data section의 정확한 size를 알고 있다.
• 이제 input module을 합치고 각 symbol에 run time 주소를 할당하는 relocation 단계를 할 준비가 다 된 것이다.
• relocation은 다음 2단계로 진행이 된다.

1. Relocating sections and symbol definitions (함수, 변수 선언 된 것)
   1. 이 단계에서는 같은 type의 모든 section을 합쳐서 새로운 같은 type의 aggregate section으로 만든다.
   2. 예를 들어 input modules의 .data sections는 다 합쳐져서 하나의 section이 되는데 이 section은 output executable object file의 .data section이 된다.
   3. 그리고 linker가 새로운 aggregate section에게 run time address를 부여한다. 이때 input modules로부터 정의된 각 section과 symbol들에게 주소 부여하는 것이다.
   4. 이 단계가 끝나면 각 명령어와 전역 변수는 고유한 run time memory 주소 갖게 되는 것이다.
2. Relocating symbol references within sections (코드 내의 symbol을 위의 주소로)
   1. 이 단계에서는 code의 body와 data section에 있는 모든 symbol reference를 정확한 run time 주소를 가리킬 수 있도록 바꾼다.
   2. 이 단계를 수행하기 위해서 linker는 relocatable object modules의 자료구조에 도움을 받는데 relocation entries다. 이것은 다음에 나온다.

7.7.1 Relocation Entries

• assembler가 object module을 만들면 이것은 code와 data가 메모리 어느 부분에 저장되어 있는지 알지 못한다.
• 그리고 object module은 module이 참조하는 외부에 정의된 함수나 전역 변수의 위치도 알지 못한다.
• 그래서 assembler가 위치를 알 수 없는 object의 reference를 만나면 이것은 relocation entry를 만들어낸다.
• relocation entry는 linker에게 object file을 executable로 합칠 때 reference를 어떻게 바꾸는지 알려주는 것이다.
• code에 대한 relocation entries는 .rel.text에 있고 data에 대한 relocation entires는 .rel.data에 있다.
• 아래 그림이 ELF relocation entry의 format을 보여준다.



• 각 entry는 relocation해야 하는 reference를 확인하고 reference를 바꾸는 방법을 지정한다.
• offset은 변경될 reference의 section offset이다.
• symbol은 변경될 reference를 가리키는 symbol을 지정한다.
• type은 reference를 변경하는 방법을 linker에게 알려주는 것이다.
• addend는 위의 type에 사용되는 것이다. 변경될 reference의 값에 더하기 위해 사용되는 signed 상수다.
• 이제 위에서 말한 type에 대한 설명이다.
• ELF는 32개의 다른 relocation type이 있고 대부분 어렵다.
• 우리는 2개의 가장 기본적인 relocation type만 볼 것이다.

1. R_X86_64_PC32.
   1. 32 bit PC relative 주소를 사용해서 reference를 relocate하는 것이다.
   2. PC relative 주소는 PC의 현재 run time 값의 offset이다.
   3. CPU가 PC relative 주소를 사용하는 명령어를 실행하면 PC의 현재 run time value에 명령어에 encoding된 32 bit 값을 더해서 유효 주소를 형성한다.
   4. 이 유효 주소는 항상 메모리에 있는 다음 명령어의 주소가 된다.
2. R_X86_64_32.
   1. 32 bit 절대 주소를 사용해서 reference를 relocate한다.
   2. 절대 주소를 사용하면 CPU는 명령어에 encoding된 32bit 값을 변경 없이 바로 유효 주소로 사용할 수 있다.

• 이 2개의 relocation type은 x86-64 small code model을 지원한다.
• 이 model은 executable object file에 code와 data의 전체 크기가 2GB보다 작다고 가정하는 것이다. 그래서 32bit PC relative 주소를 사용해서 run time에 accesss할 수 있는 것이다.
• 이 small code model은 gcc에서 default이다.
• 2GB보다 큰 프로그램은 -mcmodel=medium (medium code model), -mcmodel=large (large code model) flag를 사용해서 컴파일할 수 있지만 여기선 다루지 않는다.

7.7.2 Relocationg Symbol References

아래 그림은 linker의 relocation 알고리즘의 pseudo code를 보여준다.

• 1, 2 line은 각 section s와 각 section과 연결된 relocation entry r을 반복하는 for문이다.
• 좀 더 구체적으로 section s가 바이트 배열이고 각 relocation entry r이 위의 7.9 그림에서 본 Elf64_Rela 타입의 구조체로 가정한 것이다.

• 그리고 알고리즘이 동작할 때 linker가 각 section (ADDR(s)로 지칭)과 각 symbol(ADDR(r.symbol)로 지칭)에 대한 run time 주소를 이미 정했다고 가정한다.

 

• 3 line은 s 배열의 한 element 중에 relocate 되어야 할 것의 주소를 계산하는 것이다.
• 만약에 이 reference가 PC relative 주소를 사용하면 line 5~9에서 relocate되고 절대 주소를 사용하면 line 11~ 13에서 relocate 되는 것이다.

 

• linker가 reference를 relocate 하기 위해서 이 알고리즘을 어떻게 사용하는지 보자. 7.1의 예제 프로그램에 대해서 볼 것이다.

• 아래 그림은 main.o의 disassembled code를 보여준다.

• main 함수에서 보면 sum과 array라는 2개의 global symbol을 reference한다.
• 각 reference 마다 assembler는 relocation entry를 만든다. 위의 그림에서 5, 7줄에서 볼 수 있다.
• relocation entry는 linker에게 다음과 같은 정보를 알려주는 것이다.
• sum의 reference는 32 bit relative 주소를 사용해서 relocate 해야 한다.
• array의 reference는 32 bit absolute 주소를 사용해서 relocate 해야 한다.
• 다음 2개의 section에서 linker가 이 reference들을 어떻게 relocate하는지 보자.

Relocating PC-Relative References

• 위의 그림의 6번째 줄에서 main 함수가 module sum.o에 정의되어 있는 sum 함수를 호출한다.
• call 명령어는 section offset 0xe에서 시작하고 1바이트 opcode 0xe8로 구성되어 있다.
• 그리고 call 명령어 뒤에 sum의 32 bit PC relative reference가 나온다.

 

• relocation entry r은 아래 4개의 field로 구성된다.
  • r.offset = 0xf
  • r.symbol = sum
  • r.type = R_X86_64_PC32
  • r.addend = -4

 

• 이 field들은 0xf offset에서 시작하는 32 bit PC relative reference를 바꾸라고 linker에게 알려주는 것이다.
• 그래서 바꾸면 linker가 sum 함수를 run time에 가리키게 되는 것이다.

 

• linker가 아래처럼 정했다고 가정해보자. (relocation 1단계에서 구한 것)
• ADDR(s) = ADDR(.text) = 0x4004d0
• and
• ADDR(r.symbol) = ADDR(sum) = 0x4004e8 (sum 함수가 선언된 주소)
  • (여기서 ADDR(s)는 section의 run time 주소, ADDR(r.symbol)은 symbol의 run time 주소. 즉 section이 0x4004d0에서 시작하고 sum 함수가 0x4004e8에서 시작한다는 의미 같다.)

• 위의 relocating 알고리즘을 사용하면 linker가 먼저 7번째 줄의 reference에 대한 run time 주소를 계산한다.

 

• refaddr = ADDR(s) + r.offset
• = 0x4004d0 + 0xf
• = 0x4004df

 

• 이렇게 하면 reference를 업데이트한다. 그리고 이 reference는 run time에 sum 함수를 가리키게 되는 것이다. 8번째 줄이다.

 

• *refptr = (unsigned) (ADDR(r.symbol) + r.addend - refaddr)
• = (unsigned) (0x4004e8 + (-4) - 0x4004df)
• = (unsigned) (0x5)

• executable object file에서 결과를 보면 call 명령어는 아래와 같은 relocated된 형태 가진다.

 

• 4004de: e8 05 00 00 00 callq 4004e8 <sum> sum()

 

• 그러면 run time에 call 명령어는 0x4004de 주소에 위치한다.
• CPU가 call 명령어를 실행하면 PC는 0x4004e3값을 가진다.
• 이것의 의미는 call 명령어 다음 명령어의 주소다.

 

• call 명령어를 실행하기 위해 CPU는 다음과 같은 단계를 거친다.

1. PC를 stack에 올리다.
2. PC에 0x5 더함 = PC + 0x5 = 0x4004e3 + 0x5 = 0x4004e8

• 그러므로 다음에 실행할 명령어는 sum 함수의 첫번째 명령어가 되는 것이다.

Relocating Absolute References

• 절대 주소 Relocating 하는 것은 간단하다.
• 위의 그림에서 4번째 줄에 mov명령어는 array의 주소를 %edi 레지스터로 복사한다.
• mov 명령어는 section offset 0x9에서 시작하고 1바이트 opcode 0xbf로 이뤄져 있다.
• 그리고 뒤에 array의 32 bit absolute reference가 나온다.

• relocation entry r은 아래 4개 field로 구성되어 있다.
  • r.offset = 0xa
  • r.symbol = array
  • r.type = R_X86_64_32
  • r.addend = 0
• 이 field들은 linker에게 offset 0xa에서 시작하는 absolute reference를 바꾸라고 한다.
• 바꾸면 reference가 run time에 array의 첫번째 바이트를 가리킬 것이다.

 

• linker가 아래와 같이 결정했다고 가정하자.
• ADDR(r.symbol) = ADDR(array) = 0x601018 (array가 선언된 주소가 여기다)

• linker는 relocation 알고리즘의 13번째 줄을 사용해서 reference를 업데이트 한다.
• *refptr = (unsigned) (ADDR(r.symbol) + r.addend)
• = (unsigned) (0x601018 + 0)
• = (unsigned) (0x601018)

 

• executable object file에서 보면 reference는 아래와 같은 relocated된 형태로 변경되어 있다.
• 4004d9: bf 18 10 60 00 mov $0x601018,%edi %edi = &array

 

• 지금까지 한 것 다 더해서 아래 그림은 final executable object file에서 relocated된 .text와 .data section을 보여준다.

• load time에서 loader는 이 section들에서 메모리로 바로 바이트들을 복사할 수 있다.
• 그리고 다른 변경없이 바로 명령어를 실행할 수 있다.
  • 예제 설명: https://it-eldorado.tistory.com/49