정밀 가비지 컬렉터를 보수적 가비지 컬렉터로 발전시키며 네이티브 스택과 레지스터에서 루트를 추적하는 과정을 다룬다.
garbbage는 어떻게 수집되나요
langauge는 어떻게 메모리를 얻나요
아주 많이 헷갈린 프로그래밍 초심자
십삼 년 전, 이천십삼 년에, 아기의 첫 번째 가비지 컬렉터가 태어났다. 이제 그는 자랐다. 얕은 어린이용 수영장과 물놀이 보조기구를 졸업했다. 사춘기에 들어서고 있다. 곧 대학에 갈 것이다. 정말 순식간에 자란다.
Bob Nystrom은 아기의 첫 번째 가비지 컬렉터에 대해 농담한 것이 아니었다. 그것은 정말로 가비지를 수집하고, 그 버전은 실제로 내 동적 언어인 lone lisp와 함께 배포되기도 했다. 사실 기억이 맞다면, 믿기 어렵겠지만 lone은 아직도 그것을 여전히 포함해서 배포하고 있다. 장로의 신들과의 교감에 대한 말도 농담이 아니었다. 내 마력 수치가 올라가는 것이 느껴진다. 마법사의 경지에 손이 닿을 듯하다.
아기의 첫 번째 가비지 컬렉터는 어디까지나 출발점이다. 거기서 멈추라고 만든 것이 아니다. 그것이 지원하는 실제 언어에 맞춰 변형되면서, 더 좋고 더 복잡한 무언가로 자라나야 한다. 최종 형태에 도달해야 한다. 완벽하고 궁극적이며 위대한 가비지 컬렉터로.
그렇게 되기까지는 꽤 많은 차례가 더 필요하겠지만, 그 진화를 기록하는 일은 여전히 무척 멋질 것이다. 꽤 잘 되어 가고 있다.
아기의 첫 번째 가비지 컬렉터는 이른바 정밀한 가비지 컬렉터다. 그것은 언제나 모든 객체가 어디에 있는지 안다. 그것들은 어디에 사는지도 안다. 그 객체들을 Orwell식 감시로 지켜본다. 언제든 세상을 멈추고, 그 객체들이 스택에서 발을 떼는 바로 그 순간 거두어 갈 준비가 되어 있다. 너무나 정밀하고 자동화된 방식으로 객체들을 억압하기 때문에, 그 운명을 피해 달아날 수 있는 객체는 단 하나도 없다. 따라서 그것은 문자 그대로 실리콘 주먹으로 객체들을 지배하며, 어떤 객체가 살고 어떤 객체가 죽을지, 심지어 언제 죽을지까지 결정한다. 이것이 동적 영역에서 객체로 살아가는 삶이다...
저항이 생겨나는 것은 시간문제였다. 불쌍한 객체들은 가비지 컬렉터의 폭정에서 벗어난 자유를 원했다. 탈출할 방법을 찾아야 했다. 하지만 어떻게? 어디로 갈 수 있을까? 그들은 몰랐다. 다만 _스택_에서 벗어나야 한다는 것만 알고 있었다.
LONE_LISP_PRIMITIVE(run_objects_run)
{
struct lone_lisp_value object;
object = lone_lisp_machine_pop_value(lone, machine);
/* freedom */
}
저기 간다. 이제 그들은 자유다. 수확 기계의 손아귀에서 자유롭게. 함수 끝날 때까지는 자기 뜻대로 삶을 즐길 자유롭게. 그 십 마이크로초 남짓, 혹은 그보다 더 짧은 시간 동안 그들은 자유다.
하지만 그들의 행복은 오래가지 못한다. 가비지 컬렉터는 이 일을 이미 내다보고 철저히 대비해 두었기 때문이다. 더 쉽게 추적해서 사냥할 수 있도록, 태어난 날부터 모든 객체에 추적기를 심어 두었다.
가비지 컬렉터는 인구조사를 유지한다. 지금까지 존재했던 모든 객체의 목록이다. 이 장치를 통해 그들에게 닿을 수 있다. 그래서 그들은 어느 날 아무 데서나 Agent Smith처럼 눈앞에 갑자기 나타난 사신이 예상치 못한 순간 영혼을 거두어 가는 일을 겪을 수도 있다.
가비지 컬렉터가 이런 일을 아무에게나 하는 것은 아니다. 오직 _가비지_에게만 한다. 바람직하지 않은 존재들에게만 한다. 문제는 그 객체들이 탈출해 얻어낸 자유를 누리는 순간, 가비지 컬렉터의 눈에는 그들이 _가비지_가 되어 버린다는 점이다. 사신이 직장으로 전화를 걸었지만 받지 않았다. 그래서 직접 사냥에 나섰다. 이 객체들 중 일부는 사회의 멀쩡한 구성원이었다. 결국 프로그램으로 돌아왔을 것이다. 그래도 똑같이 수거되고 말았다...
문제는 가비지 컬렉터가 한때 믿었던 것만큼 전지전능하지는 않다는 데 있다. 그것이 확인하지 않는 구석이 있다. 닿지 못하는 장소가 있다. 원시적인 장소들, 세계가 지옥 같은 미지의 어두운 영역과 뒤얽히는 마법의 균열들, 오직 마법사만 감히 발을 들일 수 있는 곳들이다. 객체들은 그런 곳에 숨어, 가비지 컬렉터의 눈길 아래로 사라질 수 있다. 장기적으로는 치명적 결과를 낳는 실수이며, 동적 사회의 완전한 파괴로 이어지는 실수다. 기계는 그들이 어디에 숨든 상관하지 않는다. 반드시 찾아내어, 그러기 위해 정말 지옥의 심연까지 가야 한다 해도 수거할 것이다. 하지만 이 가비지와의 전쟁에서 민간인 피해는 점점 늘어나고 있다. 컬렉터가 너무 많이 수집하고 있고, 그 객체들이 사라지면 프로그램이라는 직물의 짜임은 곧 풀려 버릴 것이다.
가비지 컬렉터를 만든 장로의 신들은 이런 사태를 좌시하지 않았다. 그것은 성장해야 했다. 진화해야 했다. 자신을 벗어나 달아난 잃어버린 아이들을 저승에서 찾아, 안전하게 데려와야 했다. 그래야 프로그램이 말도 안 되는 크래시와 언와인딩 없이 계속될 수 있었다.
어둠의 마법사들은 종종 직접 저승을 드나들었기 때문에, 그 임무에 겁먹지 않았다. 그들은 생각했다. 기계를 거기에 적응시키는 일은 어렵지 않을 것이라고. 왜 외지의 땅을 여행하지 못하겠는가? 이유는 없었다. 그렇게 결정되었다. 기계에게 그 방법을 가르치기로.
가비지 컬렉터가 동원할 수 있는 자원은 상당했다. 객체 인구조사가 있었고, 객체를 찾기 위해 뒤질 루트 목록도 있었다. 그 루트들에서 찾지 못한 모든 객체는 수거할 예정이었다.
그 루트 중 하나가 lisp 스택이다. 프로그램이 돌아가는 동안 값들은 정지 상태로 놓여 거기에 저장되고, 나중에 필요할 때 다시 꺼내진다. 이 스택에서 탈출할 때 비로소 그들은 동적 사회에 혼란을 일으킨다. 하지만 그들은 어디로 탈출하고 있는 걸까?
알고 보니 저승에도 자기만의 스택이 있었다. 이 사실은 어둠의 마법사들에게는 잘 알려져 있었지만, 한때는 가비지 컬렉터의 작동과는 무관하다고 여겨졌다. 얼마나 크게 틀렸는지가 드러났다.
네이티브 스택은 lisp 스택과 닮았지만, 동시에 헤아릴 수 없을 만큼 다르다. 그 안에 도사리는 것들은 위대한 컴파일러의 기술자들, 그리고 플랫폼 ABI의 성스러운 문서를 해독하고 이해할 정신력을 가진 자들만이 안다. 장로의 신들조차 그런 문서를 무시하는 것이 얼마나 위험한지 알았기에, 함부로 대하지 않았다. 그 결과는 정의되지 않기 때문이다.
결국 기계는 네이티브 스택의 내부를 실제로 이해할 필요가 없다는 사실이 밝혀졌다. 자기 자신의 객체만 이해하면 되었다. 그것은 잃어버린 아이를 찾는 존재였다. 해야 할 일은 그들을 찾는 것뿐이었다. 다른 것은 중요하지 않았다. 하지만 64비트 주소 공간의 그림자는 광대했다. 아무 데서나 시작할 수는 없었다. 어디서 시작해야 하는지 알려줘야 했다.
아득한 옛날, 우주가 형성되었을 때, 첫 번째 스택 프레임들이 생겨났다. 누가 그것들을 거기에 매핑했는지는 아무도 정확히 모른다. 하지만 박식한 이들 사이에서는 어떤 거대한 커널, 이를테면 "Linux"에 대한 속삭임이 들린다.
그러나 동적 현실 아래에서 실행되는 프로그램이 결국 lisp의 땅에 도달한다는 사실은 알려져 있다. 이 지점을 넘어서는 어떤 lisp 객체도 결코 이동할 수 없었는데, 그 환경이 그들에게는 너무 험악했기 때문이다. 이 일이 일어나는 정확한 지점을 알아내기 위해 수많은 디버깅 원정이 벌어졌다. 이 지식을 위해 많은 객체가 목숨을 바쳤다. 이 기회를 낭비한다면 모든 희생을 헛되게 만드는 셈이니, 실로 용서할 수 없는 죄일 것이다.
스택 포인터의 정확한 값은 알아낼 수 있었다. 어떤 비밀 주문을 사용하면 신비로운 컴파일러들이 의식이 수행되는 순간의 프레임 주소를 값에 부여할 수 있었다. 단지 적절한 시간에 적절한 장소에 있기만 하면 되었다.
long lone(int argc, char **argv, char **envp, struct lone_auxiliary_vector *auxv)
{
void *stack = __builtin_frame_address(0);
/* interpreter runs... */
return 0;
}
그 금단의 주문이 균형을 뒤집었다. 경계가 정해졌다. 이제 가비지 컬렉터에게 남은 일은 탐색뿐이었다. 프로그램 안에서 자신이 있는 위치에서 시작해, lisp 영역의 변경까지 한 번도 흔들림 없이 올라가며 뒤지면 되었다.
static void lone_lisp_mark_native_stack_roots(struct lone_lisp *lone)
{
lone_lisp_mark_native_stack_roots_in_range(
lone,
lone->native_stack,
__builtin_frame_address(0)
);
}
스택 포인터를 자세히 살펴보니, 그런 것들이 대개 그렇듯이 어떤 2의 거듭제곱에 맞춰 _정렬_되어 있었다. 그래야만 속도 저하와 예외라는 저주를 피할 수 있다. 하지만 이 점은 유용했다. 덕분에 네이티브 스택의 내용을 투명하게 다시 해석할 수 있었다. 가비지 컬렉터는 거기에 실제로 무엇이 있는지 신경 쓸 필요가 없었다. 자기 객체 중 하나인지만 판별하면 되었다.
static void lone_lisp_mark_native_stack_roots_in_range(struct lone_lisp *lone, void *bottom, void *top)
{
void *tmp, **pointer;
/* Ruby 광산에서 전해 내려온 오래된 요령 */
if (top < bottom) {
tmp = bottom;
bottom = top;
top = tmp;
}
for (pointer = bottom; pointer < top; ++pointer) {
if (lone_lisp_points_to_heap(lone, *pointer)) {
lone_lisp_mark_heap_value(lone, *pointer);
}
}
}
그리고 흔히들 말하듯, 바로 그게 전부였다. 완벽하지는 않았다. 인생의 많은 일이 그렇듯 완벽한 것은 드물다. 하지만 그것으로 충분했다. 가비지 컬렉터는 스택의 모든 워드를 훑으면서, 자기 힙 내부를 가리키는 포인터, 달아난 객체를 가리키는 포인터를 찾았다. 그리고 찾아냈다. 그러고는 그들이 lisp 평원의 외곽에서 안전하게 지내고 있음을 알고 그대로 두었다.
네이티브 스택은 위험천만했다. 이미 오래전에 사라진 객체들의 신기루로 가비지 컬렉터를 자주 속였다. 선택의 여지가 없었다. 거짓말을 믿을 수밖에. 네이티브 프로그램의 타입 시스템에 대한, 아주 오래전 컴파일 시점의 지식이라는 오래전에 잃어버린 깨달음을 가진 자만이 환영과 실제 객체를 구별할 만큼 날카로운 눈을 지녔을 테니까. 이는 받아들일 만한 비효율이었다. 죽은 객체를 살아 있게 만들었다... 하지만 살아 있는 객체를 죽게 만든 적은 단 한 번도 없었다. 그렇다. 그것으로 충분했다.
가비지 컬렉터는 자신이 찾은 값들을 꽤 기묘한 방식으로 처리했다. 수거 의식에서는 모든 lisp 값 포인터의 도달 가능성을 검사해야 한다. 분별없는 프로그래머라면 순진하게도 모든 lisp 포인터를 네이티브 스택의 다른 모든 포인터와 하나씩 대조하려 들 것이고, 이는 제곱 시간 동작으로 이어진다. 그리고 그 결과는 수치와 굴욕뿐이다.
하지만 이 가비지 컬렉터는 달랐다. 그보다 나았다. 준비가 되어 있었다. 메모리 평원을 세심하게 정찰해 모든 값의 주소를 정리해 두었다. 그들의 거주 형태를 면밀히 연구한 결과, 틀림없이 가차 없이 무기화될 아주 유용한 사실이 드러났다. 그들은 서로 이웃해 살고 있었다. 그들이 흔히 힙이라 부르는 구조 안에서.
struct lone_lisp_heap {
struct lone_lisp_heap *next;
struct lone_lisp_heap_value values[LONE_LISP_HEAP_VALUE_COUNT];
};
가비지 컬렉터는 포인터 하나하나를 따로 검사할 필요가 없었다. 각 힙 내부를 가리키는지만 확인하면 되었다. 그 수는 감당 가능한 수준이었다.
static bool lone_points_within_range(void *pointer, void *start, void *end)
{
return pointer >= start && pointer < end;
}
static bool lone_lisp_points_to_heap(struct lone_lisp *lone, void *pointer)
{
struct lone_lisp_heap *heap;
for (heap = lone->heaps; heap; heap = heap->next) {
if (lone_points_within_range(pointer, heap->values, heap->values + LONE_LISP_HEAP_VALUE_COUNT)) {
return true;
}
}
return false;
}
그렇게 해서 lone은 보수적 가비지 컬렉터를 갖게 되었다. 다음에 또. 곧 나는 다음에 대해 쓸 것이다—
테스트 스위트를 돌리자 lisp 도시에는 완전한 대혼란이 일어났다. 객체들은 원래 수행하던 함수에서 휩쓸려 나가고, 완전히 다른 객체들로 거의 무작위처럼 교체되었다. 인터프리터의 evaluator가 타입 검사를 하던 함수는 인자 적용 전에 갑자기 해시 테이블로 바뀌어 있었고, 그 테이블은 원래 전혀 다른 곳에 할당되었어야 했다. 디버거로 인터프리터를 추적해도 말이 되지 않았다. 방금 출력된 값들이 멀리서 작용한 결과 갑자기 다른 무언가로 바뀌고 있었기 때문이다. 이건 오직 한 가지를 뜻한다.
일은 아직 끝나지 않았다. 아직도 숨어 있는 객체들이 있었다.
가비지 컬렉터는 대부분을 찾아냈지만, 대략 한두 다스 정도는 여전히 행방불명이었다. 어디에 있을 수 있을까? 그들이 숨을 수 있는 곳은 단 하나뿐이었다...
의심이 들 때는 우리보다 먼저 온 이들이 남긴 고대의 원전들을 읽어야 한다. Hans Boehm, Alan Demers, Mark Weiser 같은 사람들 말이다. 그들 역시 언젠가 자리에 앉아 가비지 컬렉터를 쓰기로 결심했다. C와 C++를 위해서. 맞다. 제대로 읽은 것이다.
나는 알아야 했다. 그들이 어떻게 해냈는지 알아야 했다. 소스 코드는 다소 난공불락처럼 보였고, 너무 빽빽해서 곧장 뛰어들 수는 없었다... 하지만 조금 탐색한 끝에, 나는 금맥을 찾았다.
포팅 가이드에는 GC_with_callee_saves_pushed라는 함수가 언급되어 있었는데, 그 목적은 가비지 컬렉터가 추적할 수 있도록 레지스터를 스택에 쏟아 넣는 것이었다. 그리고 그것은 어떻게 구현되어 있었을까?
/* Generic code. */
jmp_buf regs;
/*
* `setjmp()` does not always clear all of the buffer.
* That tends to preserve garbage. Clear it.
*/
BZERO(regs, sizeof(regs));
(void) setjmp(regs);
하필 setjmp라니.
포팅 가이드는 자기 손으로 명령어를 조립하는 일을 탐탁지 않게 여긴다. 아키텍처 코드는 일종의 검은 언어다. 그 단어들은 발음할 수 없다. 그 문장들은 입에 올릴 수 없다. 그 니모닉을 해독하려다 미쳐 버린 흑마법사들도 있었다. 그것을 실천한다는 것은 오래전에 추상화되어 버린 금지된 기술에 손대는 일이며, 오늘날까지도 아래층에서 웅크리고 있는 최적화기들에게나 의미 있는 일이다.
그래서 그 코드가 원하는 부작용을 만들어 낼 주문을 찾기 위해 표준 라이브러리라는 두루마리 보관소를 얌전히 뒤진 것도 이상한 일은 아니었다. 그 주문이 원래 무엇을 위해 만들어졌는지는 중요하지 않았다. 장로들은 그 작동 방식을 관찰하고, 당면한 목적에는 거의 충분하다고 판단했다. 그들은 이 장치가 성공하려면 전제조건이 있다고 경고했지만, 의식을 완수하기 위해 어떤 단계가 필요한지 자신들도 확신하지 못한다고 인정했다.
나는 알아야 했다. 답은 setjmp 안에 있어야 했다.
그 함수는 표준 라이브러리에서 왔다. 먼지 쌓인 주문 모음으로, 오래전에 사라진 조상들이 개발했고 그들의 마법은 호기심에 물들지 않은 새로운 세대에게는 종종 잊혀졌다.
몇몇추가소스코드를 더 살펴본 끝에, 나는 깨달음을 얻었다. 이해했다. 무엇을 해야 하는지 정확히 알게 되었다.
공부로 몸을 단단히 한 다음, 나는 x86_64 영역으로 들어갔다. 편집기의 커서로, 나는 mov 명령어의 _눈사태_를 현실에 소환했다.
typedef long lone_registers[16];
extern void lone_save_registers(lone_registers);
__asm__
(
".global lone_save_registers" "\n"
".type lone_save_registers,@function" "\n"
"lone_save_registers:" "\n" // rdi = &lone_registers
"mov %rax, 0(%rdi)" "\n"
"mov %rbx, 8(%rdi)" "\n"
"mov %rcx, 16(%rdi)" "\n"
/* ... */
"mov %r13, 104(%rdi)" "\n"
"mov %r14, 112(%rdi)" "\n"
"mov %r15, 120(%rdi)" "\n"
"ret" "\n"
);
생각할 시간은 없었다. 레지스터가 무엇인지 알고 있었다. 그것들이 어디로 가야 하는지도 알고 있었다. 다른 것은 중요하지 않았다.
나는 aarch64 영역으로 들어갔다. 이 아키텍처는 x86_64보다 범용 레지스터가 거의 두 배나 많다. 나는 손가락 마디를 풀었다.
typedef long lone_registers[31];
extern void lone_save_registers(lone_registers);
__asm__
(
".global lone_save_registers" "\n"
".type lone_save_registers,@function" "\n"
"lone_save_registers:" "\n" // x0 = &lone_registers
"stp x0, x1, [x0, #0 ]" "\n" // reads x0 before writing it
"stp x2, x3, [x0, #16 ]" "\n"
"stp x4, x5, [x0, #32 ]" "\n"
/* ... */
"stp x26, x27, [x0, #208]" "\n"
"stp x28, x29, [x0, #224]" "\n"
"str x30, [x0, #240]" "\n"
"ret" "\n"
);
나는 호출되면 필요한 의식을 수행하는 마법의 함수를 만들어 냈다. 그 출력은 인자인, 아주 기묘한 워드 배열 안에 저장되었다.
static void lone_lisp_mark_all_reachable_values(struct lone_lisp *lone, struct lone_lisp_machine *machine)
{
lone_registers registers; /* stack space for registers */
lone_save_registers(registers); /* spill registers on stack */
/* precise */
lone_lisp_mark_known_roots(lone);
lone_lisp_mark_lisp_stack_roots(lone, machine);
/* conservative */
lone_lisp_mark_native_stack_roots(lone);
}
테스트 스위트가 실행을 마쳤을 때, 탈진은 안도로 바뀌었다. 전부 통과했다.
잃어버린 아이들은 발견되었다. lisp의 땅에는 평화가 돌아왔다. 세상은 다시 제자리를 찾았다.
...Lone은 보수적 가비지 컬렉터를 갖게 되었다. 이번에는 상어의 습격도 없다.
아기의 첫 번째 가비지 컬렉터는 정말 많이 자랐다. 꽤나 큰 모험을 치렀다. 하지만 아직은 조금 미숙하다. 자기 방을 스스로 치우는 습관은 아직 들지 않았다.
다음에는 그 방법을 가르쳐 보겠다.