간단한 점화식 반복 문제를 계기로 x86-64 JIT 컴파일러를 직접 만들어, 실행 가능한 메모리를 할당하고 호출 규약에 맞춰 기계어를 생성·실행하는 방법을 설명한다.
URL: https://nullprogram.com/blog/2015/03/19/
Title: A Basic Just-In-Time Compiler
2015년 3월 19일
nullprogram.com/blog/2015/03/19/
(저자는 현재 미국 내 취업 기회에 열려 있습니다.)
이 글은 Hacker News와 reddit에서 논의되었습니다.
월요일 /r/dailyprogrammer 도전 과제는 점화식 정의를 읽어 들인 뒤, 해석(인터프리터) 방식으로 이를 어떤 항 수까지 반복 계산하는 프로그램을 작성하는 것이었습니다. 초기항(u(0))과 이전 항에 적용할 연산들의 시퀀스 f가 주어지며(u(n + 1) = f(u(n))), 이를 통해 다음 항을 계산합니다. 쉬운 과제이기 때문에 연산은 덧셈, 뺄셈, 곱셈, 나눗셈으로 제한되어 있고, 각 연산은 피연산자 하나씩만 가집니다.
예를 들어 점화식 u(n + 1) = (u(n) + 2) * 3 - 5 는 입력으로 +2 *3 -5 처럼 주어집니다. u(0) = 0 이라면,
u(1) = 1u(2) = 4u(3) = 13u(4) = 40u(5) = 121연산 시퀀스를 적용하는 인터프리터를 작성하는 대신, 내 제출물 (미러)에서는 이 기회에 간단한 x86-64 Just-In-Time(JIT) 컴파일러를 작성했습니다. 즉, 연산을 하나씩 해석하며 실행하는 대신, 프로그램이 연산들을 네이티브 기계어로 변환한 뒤 하드웨어가 직접 일을 하도록 합니다. 이 글에서는 그것이 어떻게 동작하는지, 그리고 어떻게 구현했는지 설명하겠습니다.
업데이트: 후속 도전 과제는 더 복잡한 표현식을 허용하기 위해 역폴란드 표기법(Reverse Polish notation)을 사용합니다. 저는 내 제출물 (미러)로 또 다른 JIT 컴파일러를 작성했습니다.
현대 운영체제는 프로세스 메모리의 서로 다른 부분에 대해 페이지 단위(page-granularity)로 보호 속성(read, write, execute)을 둡니다. 코드는 해당 페이지에 실행(execute) 비트가 설정된 메모리에서만 실행될 수 있고, 메모리는 쓰기(write) 비트가 설정된 경우에만 변경될 수 있으며, 어떤 페이지는 읽기(read) 자체가 허용되지 않기도 합니다. 실행 중인 프로세스에서 프로그램 코드와 로드된 라이브러리를 담고 있는 페이지는 보통 쓰기 비트가 꺼져 있고 실행 비트가 켜져 있습니다. 나머지 대부분의 페이지는 실행 비트가 꺼져 있고 쓰기 비트가 켜져 있습니다.
이렇게 하는 이유는 두 가지입니다. 첫째, 시스템 보안을 크게 향상시킵니다. 신뢰할 수 없는 입력이 실행 가능한 메모리에 읽혀 들어갈 수 있다면, 공격자는 버퍼에 기계어( 셸코드(shellcode) )를 집어넣고, 프로그램의 취약점을 이용해 제어 흐름을 그 코드로 점프시켜 실행할 수 있습니다. 공격자가 실행 불가능한 메모리에만 코드를 쓸 수 있다면 이 공격은 훨씬 어려워집니다. 공격자는 실행 가능한 페이지에 이미 로드되어 있는 코드에 의존해야 합니다(return-oriented programming).
둘째, 프로그램 버그를 더 빨리 잡아내고 그 영향을 줄입니다. 그 결과 결함 있는 프로그램이 사용자 데이터를 실수로 손상시킬 가능성이 줄어듭니다. 잘못된 방식으로 메모리에 접근하면 세그멘테이션 폴트(segmentation fault)가 발생하며, 보통 프로그램이 종료됩니다. 예를 들어 NULL은 읽기/쓰기/실행이 모두 비활성화된 특수한 페이지를 가리킵니다.
malloc() 등으로 반환된 메모리는 읽기/쓰기는 가능하지만 실행은 불가능합니다. JIT 컴파일러가 malloc()으로 메모리를 할당하고, 여기에 기계어 명령을 채운 뒤, 추가 작업 없이 그곳으로 점프하면 세그멘테이션 폴트가 발생합니다. 따라서 대신 다른 메모리 할당 호출을 사용해야 하며, 그 세부 사항을 asmbuf 구조체로 감춥니다.
#define PAGE_SIZE 4096
struct asmbuf {
uint8_t code[PAGE_SIZE - sizeof(uint64_t)];
uint64_t count;
};
여기서는 단순하게 페이지 크기가 4kB라고 가정합니다. 실제 프로그램이라면 sysconf(_SC_PAGESIZE)로 런타임에 페이지 크기를 알아내야 합니다. x86-64에서 페이지는 4kB, 2MB, 1GB일 수 있지만, 이 프로그램은 어쨌든 올바르게 동작합니다.
malloc() 대신 컴파일러는 익명 메모리 맵(anonymous memory map)인 mmap()으로 메모리를 할당합니다. 익명이라는 것은 파일을 백업 저장소로 사용하지 않는다는 뜻입니다.
struct asmbuf *
asmbuf_create(void)
{
int prot = PROT_READ | PROT_WRITE;
int flags = MAP_ANONYMOUS | MAP_PRIVATE;
return mmap(NULL, PAGE_SIZE, prot, flags, -1, 0);
}
Windows에는 POSIX mmap()이 없으므로, 그 플랫폼에서는 VirtualAlloc()을 대신 사용합니다. 아래는 Win32에서의 동등한 코드입니다.
struct asmbuf *
asmbuf_create(void)
{
DWORD type = MEM_RESERVE | MEM_COMMIT;
return VirtualAlloc(NULL, PAGE_SIZE, type, PAGE_READWRITE);
}
주의 깊게 읽는 사람이라면 제가 실제로 메모리를 실행 가능(executable)하게 요청하지 않았다는 걸 알아차릴 것입니다. 이게 사실 전부의 핵심인데 말이죠! 의도적으로 그렇게 했습니다. 일부 운영체제는 W^X라는 보안 기능을 사용합니다. “write xor execute” 즉, 메모리는 쓰기 가능하거나 실행 가능 둘 중 하나이며, 동시에 둘 다일 수는 없다는 뜻입니다. 이는 앞서 설명한 셸코드 공격을 더 어렵게 만듭니다. 정상적으로 동작하는 JIT 컴파일러라면 코드 생성 후 실행 전에 메모리 보호 속성을 조정해야 합니다.
POSIX의 mprotect() 함수는 메모리 보호 속성을 바꾸는 데 사용합니다.
void
asmbuf_finalize(struct asmbuf *buf)
{
mprotect(buf, sizeof(*buf), PROT_READ | PROT_EXEC);
}
Win32에서는(마지막 인자는 NULL이면 안 됩니다),
void
asmbuf_finalize(struct asmbuf *buf)
{
DWORD old;
VirtualProtect(buf, sizeof(*buf), PAGE_EXECUTE_READ, &old);
}
마지막으로 free() 대신 매핑을 해제합니다.
void
asmbuf_free(struct asmbuf *buf)
{
munmap(buf, PAGE_SIZE);
}
Win32에서는,
void
asmbuf_free(struct asmbuf *buf)
{
VirtualFree(buf, 0, MEM_RELEASE);
}
여기서는 정의를 나열하진 않겠지만, 버퍼에 명령과 즉시값(immediate value)을 삽입하는 두 가지 “메서드”가 있습니다. 이건 순수 기계어이므로, 호출자는 어셈블러처럼 직접 바이트를 넣게 됩니다.
asmbuf_ins(struct asmbuf *, int size, uint64_t ins);
asmbuf_immediate(struct asmbuf *, int size, const void *value);
x86-64의 많은 레지스터 중에서 우리는 세 개만 신경 쓰겠습니다: rdi, rax, rdx. 이들은 원래의 16비트 8086 레지스터를 64비트(r)로 확장한 것입니다. 연산 시퀀스는 C에서 일반 함수처럼 호출할 수 있는 함수로 컴파일됩니다. 프로토타입은 아래와 같습니다. 부호 있는 64비트 정수 하나를 받아 부호 있는 64비트 정수를 반환합니다.
long recurrence(long);
System V AMD64 ABI 호출 규약에 따르면, 첫 번째 정수/포인터 인자는 rdi 레지스터로 전달됩니다. 우리 JIT 컴파일된 프로그램이 제어권을 받으면 입력은 거기에 준비되어 있습니다. ABI에 따르면, C 프로그램은 제어가 반환될 때 결과가 rax에 있기를 기대합니다. 점화식이 단순한 항등 함수(연산이 하나도 없음)라면, 하는 일은 rdi를 rax로 복사하는 것뿐입니다.
mov rax, rdi
하지만 함정이 있습니다. 플랫폼 의존적인 지저분한 부분이 모두 asmbuf에 캡슐화되어 있다고 생각할 수도 있지만, 꼭 그렇지는 않습니다. 늘 그렇듯 Windows는 특이 케이스이며 자기만의 호출 규약이 있습니다. 여기서 중요한 차이는 첫 번째 인자가 rdi가 아니라 rcx로 들어온다는 점입니다. 다행히 이는 맨 첫 명령에만 영향을 주며, 나머지 어셈블리는 동일합니다.
마지막으로, 결과가 rax에 있다고 가정하면 호출자에게 반환합니다.
ret
그러면 어셈블리는 알겠는데, asmbuf_ins()에는 무엇을 넘겨야 할까요? 이제 손으로 직접 바이트를 만져야 합니다.
이걸 “정석대로” 하려면 x86-64 문서를 내려받아 사용하려는 명령을 찾아보고, 필요한 바이트와 피연산자가 어떤 식으로 들어가는지 직접 계산해야 합니다. 60년대에는 필요에 의해 그렇게 했죠.
다행히 훨씬 쉬운 방법이 있습니다. 실제 어셈블러가 해주는 일을 보고 그대로 복사하면 됩니다. 위 두 명령을 peek.s 파일에 넣고 nasm에 넘깁니다. 그러면 기계어가 담긴 원시 바이너리가 만들어지고, 이를 NASM 디스어셈블러인 nidsasm로 디스어셈블합니다.
$ nasm peek.s
$ ndisasm -b64 peek
00000000 4889F8 mov rax,rdi
00000003 C3 ret
간단합니다. 첫 명령은 3바이트이고 ret는 1바이트입니다.
asmbuf_ins(buf, 3, 0x4889f8); // mov rax, rdi
// ... 코드 생성 ...
asmbuf_ins(buf, 1, 0xc3); // ret
각 연산에 대해, 연산자와 관계없이 피연산자가 미리 rdi에 로드되도록 구성할 것입니다. 이는 처음에 인자가 전달된 방식과 비슷합니다. 더 똑똑한 컴파일러라면 즉시값이 작을 때(32비트 이하) 연산 명령 자체에 즉시값을 포함시켰겠지만, 여기서는 단순하게 유지하겠습니다. 이 명령의 “템플릿”을 슬쩍 잡아내기 위해 피연산자로 0x0123456789abcdef를 사용하겠습니다.
mov rdi, 0x0123456789abcdef
이를 ndisasm로 디스어셈블하면,
00000000 48BFEFCDAB896745 mov rdi,0x123456789abcdef
-2301
명령 뒤에 피연산자가 리틀 엔디언으로 바로 이어져 있는 것이 보입니다. 이것도 쉽습니다!
long operand;
scanf("%ld", &operand);
asmbuf_ins(buf, 2, 0x48bf); // mov rdi, operand
asmbuf_immediate(buf, 8, &operand);
지원할 각 연산자마다 같은 발견 과정을 적용하고, 매번 결과를 rax에 누적하도록 합니다.
switch (operator) {
case '+':
asmbuf_ins(buf, 3, 0x4801f8); // add rax, rdi
break;
case '-':
asmbuf_ins(buf, 3, 0x4829f8); // sub rax, rdi
break;
case '*':
asmbuf_ins(buf, 4, 0x480fafc7); // imul rax, rdi
break;
case '/':
asmbuf_ins(buf, 3, 0x4831d2); // xor rdx, rdx
asmbuf_ins(buf, 3, 0x48f7ff); // idiv rdi
break;
}
연습 삼아 나머지 연산자(%), XOR(^), 비트 시프트(<, >) 지원을 추가해 보세요. 이런 연산자들을 더하면 점화식으로 꽤 괜찮은 PRNG를 정의할 수 있습니다. 또한 이 문제의 폐형(closed form) 해를 없애서, 우리가 실제로 이런 걸 할 이유가 생기게 해줍니다! 또는, 아예 전부를 부동소수점으로 바꾸는 방법도 있습니다.
코드 생성을 모두 마치면, 버퍼를 finalize해서 실행 가능하게 만들고, 함수 포인터로 캐스팅한 뒤 호출합니다. (중복을 피하기 위해 void *로 캐스팅했는데, 그러면 올바른 함수 포인터 프로토타입으로 암시적으로 캐스팅됩니다.)
asmbuf_finalize(buf);
long (*recurrence)(long) = (void *)buf->code;
// ...
x[n + 1] = recurrence(x[n]);
상당히 멋지지 않나요! 다만 이건 극도로 단순화된 상황이었습니다. 분기도 없고, 중간 값도 없고, 함수 호출도 없으며, 스택(push, pop)도 전혀 건드리지 않았습니다. 이 도전 과제의 점화식 정의는 사실상 자체적으로 어셈블리 언어에 가깝기 때문에, 초기 설정 이후에는 1:1 변환에 불과합니다.
언젠가 이보다 더 고급 JIT 컴파일러를 만들어 보고 싶습니다. 다만 이 문제보다 복잡해서 JIT 컴파일러가 어울리면서도, 한편으로는 LLVM을 쓰지 않는 것을 어느 정도는 정당화할 수 있을 만큼 충분히 단순한, 적절한 문제를 찾아야 합니다.