대용량 바이너리
Source: Hacker News
박사 과정을 진행하고 학술 논문을 제출하던 중 겪은 문제는, 효과적이고 가치 있게 만들기 위해 극적인 규모가 필요한 문제들에 대한 해결책을 구축했었다는 점이다. 논문 제출에 대한 피드백에서는 그런 문제는 존재하지 않는다며 부정했지만, 나는 산업 현장(예: 구글)에서 그런 문제들을 직접 목격했음에도 인용할 수 없었다.
이러한 초대형 코드베이스에서만 나타나는 문제 중 하나가 거대한 바이너리이다. 여러분이 본 가장 큰 바이너리(ELF 파일)는 무엇인가? 나는 디버그 심볼을 포함해 25 GiB를 초과하는 바이너리를 목격했다. 이것이 어떻게 가능한가?
이들 기업은 서비스의 시작 시간을 단축하고 배포를 단순화하기 위해 정적 빌드를 선호한다. 세계에서 가장 큰 코드베이스 중 일부에 모든 코드를 정적으로 포함시키는 것은 거대한 바이너리를 초래하는 레시피와 같다.
음속 장벽과 마찬가지로, 코드 크기가 문제가 되는 시점이 존재하며 우리는 링크와 빌드 방식을 재고해야 한다. x86_64의 경우, 그 지점은 **2 GiB “재배치 장벽(Relocation Barrier)”**이다.
왜 2 GiB? 🤔
포지션‑인디펜던트 코드가 어떻게 구성되는지 살펴보겠습니다.
간단한 예제
/* simple-relocation.c */
extern void far_function();
int main(void) {
far_function();
return 0;
}파일을 컴파일합니다:
gcc -c simple-relocation.c -o simple-relocation.oobjdump 로 오브젝트 파일을 확인합니다:
objdump -dr simple-relocation.o0000000000000000 :
0: 55 push %rbp
1: 48 89 e5 mov %rsp,%rbp
4: b8 00 00 00 00 mov $0x0,%eax
9: e8 00 00 00 00 call e
a: R_X86_64_PLT32 far_function-0x4
e: b8 00 00 00 00 mov $0x0,%eax
13: 5d pop %rbp
14: c3 rete8 바이트는 CALL opcode이며 (32‑비트 부호 있는 상대 오프셋)을 사용합니다.
현재 오프셋은 0(네 바이트의 0)입니다. objdump는 이 코드를 최종화할 때 **재배치(relocation)**가 필요하다고 알려줍니다.
Note
-0x4가 필요한 이유는 오프셋이 명령 포인터가 4‑바이트 피연산자를 지나고 난 뒤의 위치를 기준으로 하기 때문입니다.
readelf 로 재배치 엔트리를 확인할 수 있습니다:
readelf -r simple-relocation.o -dRelocation section '.rela.text' at offset 0x170 contains 1 entry:
Offset Info Type Sym. Value Sym. Name + Addend
00000000000a 000400000004 R_X86_64_PLT32 0000000000000000 far_function - 4이 엔트리는 링커에게 오프셋 0x0a에 있는 4‑바이트 피연산자( CALL의 즉시값 시작)를 far_function의 주소로 패치해야 한다고 알려줍니다.
호출 함수 추가
/* far-function.c */
void far_function(void) {
}컴파일합니다:
gcc -c far-function.c -o far-function.o두 오브젝트 파일을 링크합니다:
gcc simple-relocation.o far-function.o -o simple-relocation최종 실행 파일을 확인합니다:
objdump -dr simple-relocation0000000000401106 :
401106: 55 push %rbp
401107: 48 89 e5 mov %rsp,%rbp
40110a: b8 00 00 00 00 mov $0x0,%eax
40110f: e8 07 00 00 00 call 40111b
401114: b8 00 00 00 00 mov $0x0,%eax
401119: 5d pop %rbp
40111a: c3 ret
000000000040111b :
40111b: 55 push %rbp
40111c: 48 89 e5 mov %rsp,%rbp
40111f: 90 nop
401120: 5d pop %rbp
401121: c3 ret링커가 상대 오프셋(0x07)을 계산하고 CALL 명령을 올바르게 패치했습니다.
The 2 GiB Barrier
CALL opcode (e8)는 32‑비트 부호 있는 변위를 사용하므로 점프 범위가 ±2 GiB (2³¹ 바이트)로 제한됩니다.
따라서 호출 지점은 앞뒤로 2 GiB 안에 있는 코드만 접근할 수 있습니다. 이 제한을 **2 GiB 재배치 장벽(2 GiB Relocation Barrier)**이라고 합니다.
What happens when the target is farther than 2 GiB?
링커 스크립트를 사용하여 far_function을 멀리 배치하도록 강제할 수 있습니다.
/* overflow.lds */
SECTIONS
{
/* 1. Standard low‑address sections */
. = 0x400000;
.text : {
simple-relocation.o(.text.*)
}
.rodata : { *(.rodata .rodata.*) }
.data : { *(.data .data.*) }
.bss : { *(.bss .bss.*) }
/* 2. Move the location counter far away */
. = 0x120000000; /* ≈4.5 GiB */
.text.far : {
far-function.o(.text*)
}
}이제 LLVM의 lld로 링크합니다(오류 메시지가 조금 더 명확합니다).
gcc simple-relocation.o far-function.o -T overflow.lds \
-o simple-relocation-overflow -fuse-ld=lld출력:
ld.lld: error: :(.eh_frame+0x6c):
relocation R_X86_64_PC32 out of range:
5364513724 is not in [-2147483648, 2147483647]; references section '.text'
ld.lld: error: simple-relocation.o:(function main: .text+0xa):
relocation R_X86_64_PLT32 out of range:
5364514572 is not in [-2147483648, 2147483647]; references 'far_function'
>>> referenced by simple-relocation.c
>>> defined in far-function.o링커는 필요한 변위가 부호 있는 32‑비트 필드에 들어가지 않기 때문에 재배치 오버플로우(relocation overflow) 를 보고합니다.
Source: https://maskray.me/blog/2023-05-14-relocation-overflow-and-code-models
장벽 다루기
이 문제에 직면했을 때 우리는 여러 옵션을 가질 수 있는데, 이는 코드 모델이라는 더 넓은 주제에 해당합니다. 적절한 해결책은 우리가 접근하고 있는 것이 다음 중 어느 것인지에 따라 달라집니다:
- 데이터 (정적 변수, 상수)
- 코드 (함수, 점프 대상)
이러한 기술에 대한 훌륭하고 심도 있는 논의는 @maskray가 작성한 블로그 포스트 “Relocation overflow and code models”에서 확인할 수 있습니다.
TL;DR
- x86‑64 CALL/JMP 명령은 32‑비트 부호 있는 상대 오프셋을 사용하므로 직접 점프가 ±2 GiB 로 제한됩니다.
- 거대한 정적 바이너리는 이 제한을 쉽게 초과하여 링크 시 relocation overflow 오류가 발생합니다.
- 해결책은 서로 다른 코드 모델(예: small, medium, large, 혹은 PIE) 사용, 간접 점프, 트램폴린, 혹은 동적 링크 등을 통해 모든 호출 대상이 도달 가능한 범위에 있도록 하는 것입니다.
수십 기가바이트 규모의 바이너리를 생성하는 mega‑codebase를 다룰 때 2 GiB 재배치 장벽을 이해하고 우회하는 것은 필수입니다.
com/maskray — lld의 작성자.
가장 간단한 해결책은 -mcmodel=large 옵션을 사용하는 것으로, 이는 모든 상대 CALL 명령을 절대 JMP 로 바꿉니다.
# Build the overflow example
gcc simple-relocation.o far-function.o -T overflow.lds -o simple-relocation-overflow
# Compile with the large code model
gcc -c simple-relocation.c -o simple-relocation.o -mcmodel=large -fno-asynchronous-unwind-tables
# Link again
gcc simple-relocation.o far-function.o -T overflow.lds -o simple-relocation-overflow
# Run
./simple-relocation-overflowNote
이 시연을 위해 오버플로를 일으킬 수 있는 추가 데이터를 비활성화하기 위해-fno-asynchronous-unwind-tables옵션을 추가해야 했습니다.
이제 디스어셈블리는 어떻게 보일까?
objdump -dr simple-relocation-overflow0000000120000000 :
120000000: 55 push %rbp
120000001: 48 89 e5 mov %rsp,%rbp
120000004: 90 nop
120000005: 5d pop %rbp
120000006: c3 ret
00000000004000e6 :
4000e6: 55 push %rbp
4000e7: 48 89 e5 mov %rsp,%rbp
4000ea: b8 00 00 00 00 mov $0x0,%eax
4000ef: 48 ba 00 00 00 20 01 movabs $0x120000000,%rdx
4000f6: 00 00 00
4000f9: ff d2 call *%rdx
4000fb: b8 00 00 00 00 mov $0x0,%eax
400100: 5d pop %rbp
400101: c3 ret이제 단일 CALL 명령이 사라지고 MOVABS 뒤에 CALL이 붙은 형태가 되었습니다 😲. 이는 명령 크기를 5바이트(Opcode + 4‑바이트 상대 오프셋)에서 무려 12바이트(2‑바이트 ABS Opcode + 8‑바이트 절대 주소 + 2‑바이트 CALL)로 증가시킵니다.
눈에 띄는 단점
- 명령 크기 증가 – 호출당 5바이트에서 12바이트로 늘어났습니다. 수백만 개의 호출 지점이 있는 바이너리에서는 금방 큰 차이가 됩니다.
- 레지스터 압박 – 점프를 수행하기 위해 일반 목적 레지스터(
%rdx)를 사용하게 됩니다.
Caution
큰mcmodel에서 IPC(클록당 명령 수)가 더 낮아지는 것을 보여주는 벤치마크를 만드는 데 많은 어려움을 겪었으니, 제 말을 믿어 주세요. 🤷
우리는 작은 코드 모델을 유지하고 싶습니다. 어떤 다른 전략을 시도할 수 있을까요?
다음 글에서 더 자세히 다루겠습니다.