24장: 정밀 가비지 컬렉터

새 파일

• rt/src/copying.rs
• src/liveness.rs
• src/llvm/roots.rs

변경된 파일

• src/llvm/control.rs
• src/llvm/values.rs
• rt/src/heap.rs
• rt/src/apply.rs
• src/llvm/mod.rs
• src/llvm/primitives.rs
• src/native.rs
• src/main.rs
• rt/src/lib.rs
• src/lib.rs

동기

지금까지 Boehm 덕분에 우리는 살아 있는 포인터가 모두 어디에 있는지 컬렉터에 알려 주지 않고도 객체를 할당할 수 있었습니다. 언어를 만들어 가는 동안에는 그 점이 유용했습니다. 이제 우리 컴파일러는 어떤 값이 다시 사용될 수 있는지 알고, 우리 런타임은 어떤 필드가 그 값을 담고 있는지 압니다. 우리만의 정밀 컬렉터를 만들 만큼 충분한 정보가 갖춰진 것입니다.

우리는 복사 컬렉터를 사용하겠습니다. 살아 있는 객체는 새 공간으로 옮겨지고, 이전 공간은 다시 사용할 수 있게 됩니다. 이 아이디어는 놀라울 만큼 간결합니다. 문제는 옮겨진 객체를 가리키는 모든 참조가 그 객체를 따라가야 한다는 점입니다.

클로저가 리스트를 캡처한다고 가정해 봅시다. 리스트를 옮긴 뒤에 클로저의 필드를 갱신하더라도, 여전히 레지스터에 이전 주소를 들고 있는 호출자에게는 도움이 되지 않습니다. 그런 참조를 최신 상태로 유지하려면 생성된 코드와 런타임 사이의 협력이 필요합니다(Henderson 2002). Boehm을 계속 쓰면서 이 장을 건너뛰어도 되지만, 컬렉터를 직접 만들어 보는 것은 메모리 이야기 전체가 하나로 맞물리는 모습을 볼 수 있는 훌륭한 방법입니다.

현재의 언어

새로운 Fun 구문은 없습니다. 실행 파일을 빌드할 때 컬렉터를 선택하십시오:

$ cd crates/ch24_gc
$ cargo run -q -- build tests/programs/gc/partial.fun \
    -o ../../build/partial --gc=copying --lint
$ FUN_GC_STRESS=1 ../../build/partial
100
αβγ

add x y z = x <> y <> z

main = do
  let f = add "α"
  let g = f "β"
  print (length (map show [1..100]))
  putStrLn (g "γ")

일반적인 --gc=boehm 모드가 여전히 기본값입니다. 인터프리터는 Rust 표현을 그대로 유지하고, JIT는 Boehm 루트를 그대로 유지합니다. 복사 수집은 네이티브 실행 파일에서 선택할 수 있는 옵션입니다. 이 힙은 하나의 스레드에 속하며, 이는 Fun에 동시성이 없다는 점과 맞아떨어집니다. 수집기 선택은 전역 초기화보다 먼저 이루어집니다.

이론

도달 가능한 그래프 복사하기

힙을 두 영역으로 나눕니다. 할당은 from-space라고 부르는 활성 영역 안에서 포인터를 전진시킵니다. 수집 시에는 루트에서 도달 가능한 객체를 to-space로 복사합니다. 대피시킨 각 객체의 기존 헤더는 포워딩 표식으로, 첫 번째 페이로드 워드는 새 주소로 교체합니다. 그 객체를 가리키는 두 번째 참조는 포워딩 주소를 따라가므로 공유와 순환이 보존됩니다.

여기가 Cheney 알고리즘의 아름다운 부분입니다. 복사된 객체들 자체가 작업 큐를 이루므로, 그래프를 순회하기 위한 별도의 스택이 필요하지 않습니다 (Cheney 1970). 진행 상황을 추적하는 데는 포인터 두 개면 충분합니다.

from-space                         to-space
+------------+                     +----------+-------------+--------+
| FORWARD ---+-------------------->| scanned  | copied,     | free   |
| old object |                     | objects  | not scanned | space  |
+------------+                     +----------+-------------+--------+
                                   ^          ^             ^
                                   start      scan          free

scan 앞에 있는 것은 모두 검사를 마친 것입니다. scan과 free 사이에는 복사는 했지만 아직 검사하지 않은 객체들이 있습니다. 그중 하나를 스캔하면 그 필드를 통해 더 많은 객체를 발견할 수 있으며, 이 객체들은 free 위치에 덧붙입니다. 결국에는 scan이 따라잡습니다. 이로써 살아 있는 그래프 전체를 찾아냈습니다!

이제 두 공간을 맞바꾸고 free 이후부터 할당을 재개합니다. 공유와 순환은 포워딩 주소로 처리되며, 스캔 자체는 결코 Rust의 호출 스택을 통해 재귀하지 않습니다.

객체 종류는 수집기에게 무엇을 검사해야 하는지 알려 줍니다. 생성자 페이로드에는 값이 들어 있습니다. 클로저는 추적되지 않는 코드 주소와 항수로 시작하고, 그 뒤에 캡처가 이어집니다. PAP에는 클로저 하나, 원시 인자 개수, 그리고 인자들이 들어 있습니다. double과 문자열에는 포인터가 들어 있지 않습니다. 인자 없는 생성자와 정수는 최하위 비트가 설정되어 있으므로 추적기가 이를 건너뜁니다. 정적 문자열 주소는 from-space 밖에 있으며 이동하지 않습니다.

루트를 쓰기 가능하게 만들기

섀도 스택(shadow stack)은 머신 스택과 나란히 유지되는 루트 범위의 명시적인 스택입니다. 생성된 각 함수는 태그된 워드 슬롯의 배열을 소유합니다. 네이티브 정수와 부동소수점 중간값에는 루트가 필요하지 않습니다. 포인터일 수 있는 태그된 결과는 슬롯에 저장되며, 이후에 사용할 때마다 다시 읽어 들입니다. 수집이 슬롯을 변경하므로, 다시 읽어 들이면 새 주소를 보게 됩니다.

인자에도 같은 주의가 필요합니다. 뒤쪽의 Double 인자를 박싱하다가 앞쪽 인자가 옮겨질 수 있습니다. 코드 생성은 먼저 변환된 인자를 스크래치 루트에 저장한 다음, 호출을 위해 그 인자들을 모두 다시 불러옵니다. 생성자 할당은 할당기 호출 동안 필드를 보호한 뒤, 재배치된 주소를 새 객체에 저장합니다. Rust가 소유한 인자 버퍼도 같은 등록 계약을 따릅니다. 그 API는 복사된 워드나 원시 ABI 포인터를 반환하며, 수집이 갱신할 수 있는 셀을 가리키는 공유 Rust 슬라이스는 결코 반환하지 않습니다.

반환하는 함수는 자신의 프레임을 제거합니다. 알려진 꼬리 호출은 피호출자에 진입하기 전에 프레임을 제거합니다. 마지막 인자를 불러오는 시점과 피호출자가 자신의 매개변수를 등록하는 시점 사이에는 할당이 없습니다. 따라서 꼬리 재귀는 섀도 프레임을 쌓지 않습니다. 알려지지 않은 호출에는 여전히 21장에서 다룬 eval/apply 제약이 있습니다.

살아 있는 값만 유지하기

반환할 때까지 모든 값을 유지하면 주소 측면에서는 안전하겠지만, 루프 안에서 커다란 죽은 구조를 붙잡아 둘 수 있습니다. 역방향 활성 분석(backward liveness)은 어떤 바인딩이 다시 읽힐 수 있는지 결정합니다. 각 Flat 노드는 자신의 피연산자를 기여합니다. 그 후속 노드들은 자신의 살아 있는 변수를 기여하되, 해당 간선에서 정의되는 바인딩은 제외합니다. 점프의 후속 노드는 그 조인 본문이며, 조인 매개변수는 제거됩니다.

이 방정식들은 단조적입니다. 빈 집합에서 시작하고, 후속자가 바뀌면 선행자를 다시 방문하십시오. 최소 고정점은 일반적인 분기뿐 아니라 조인 역방향 간선도 처리합니다. 코드 생성기는 계산을 내보내기 전에 죽은 바인딩의 슬롯을 비우고 스크래치 범위를 비웁니다. 활성 분석은 제어 흐름에 대해 보수적이지만, 추적되는 0이 아닌 슬롯에는 언제나 태그된 값이 들어 있으며, 박싱되지 않은 수치 중간값은 결코 들어 있지 않습니다.

구현

liveness.rs는 명시적인 작업 목록으로 제어 흐름 그래프를 구성합니다. 솔버도 또 하나의 작업 목록이므로, 소스의 중첩이 Rust 재귀로 바뀌지 않습니다:

#![allow(unused)]
fn main() {
let mut queue = nodes.keys().copied().collect::<VecDeque<_>>();
let mut queued = nodes.keys().copied().collect::<BTreeSet<_>>();
while let Some(id) = queue.pop_front() {
    queued.remove(&id);
    let n = &nodes[&id];
    let mut live = n.uses.clone();
    for (next, defined) in &n.edges {
        live.extend(result.before[next].difference(defined).cloned());
    }
    if result.before[&id] != live {
        result.before.insert(id, live);
        for p in predecessors.get(&id).into_iter().flatten() {
            if queued.insert(*p) {
                queue.push_back(*p);
            }
        }
    }
}
}

llvm/roots.rs는 루트 슬롯을 할당하고, 포인터를 담는 위치를 SSA 워드에서 다시 읽어 들일 수 있는 슬롯으로 바꿉니다. 이 주소들은 활성화 동안 안정적으로 유지됩니다:

#![allow(unused)]
fn main() {
pub(super) fn root_binding(
    &self,
    v: &Id,
    loc: Loc<'ctx>,
) -> Result<Loc<'ctx>> {
    let Some(frame) = &self.frame else {
        return Ok(loc);
    };
    if !matches!(loc, Loc::Word(_) | Loc::Root(_)) {
        return Ok(loc);
    }
    let p = self.slot(frame.array, frame.slots[v])?;
    let w = self.loc_word(loc)?;
    self.builder.build_store(p, w)?;
    Ok(Loc::Root(p))
}
}

런타임의 대피(evacuation) 단계는 고정된 워드를 그대로 두거나, 포워딩 주소를 따라가거나, 객체 하나를 복사합니다. 헤더의 크기에는 페이로드 워드만 포함되므로, 할당할 때는 헤더 자리도 함께 확보합니다:

#![allow(unused)]
fn main() {
fn evacuate(
    from: &mut [Word],
    used: usize,
    to: &mut [Word],
    free: &mut usize,
    w: Word,
) -> Word {
    let base = from.as_ptr() as usize;
    let address = w as usize;
    // Immediates, null placeholders, and static string/code addresses never move.
    if layout::is_immediate(w)
        || address < base
        || address >= base + used * 8
    {
        return w;
    }
    assert_eq!((address - base) % 8, 0);
    let start = (address - base) / 8;
    let header = from[start];
    if layout::kind(header) == layout::FORWARD {
        return from[start + 1];
    }
    let words = 1 + layout::size(header);
    assert!(words >= 2 && start + words <= used);
    let dest = *free;
    to[dest..dest + words].copy_from_slice(&from[start..start + words]);
    *free += words;
    let pointer = to.as_mut_ptr().wrapping_add(dest) as Word;
    from[start] = layout::header(layout::FORWARD, 0, 1);
    from[start + 1] = pointer;
    pointer
}
}

수집기는 루트를 스캔한 다음 to-space의 큐를 소비합니다. 힙은 필요할 때 커지며, 객체를 옮기기 전에 목적지를 먼저 할당합니다. 활성 from-space의 크기를 조정해도 기존 주소가 무효화되는 일은 결코 없습니다.

#![allow(unused)]
fn main() {
fn collect(&mut self, reserve: usize) {
    let capacity = if self.used + reserve > self.from.len() {
        self.from
            .len()
            .saturating_mul(2)
            .max(self.used.checked_add(reserve).expect("heap overflow"))
    } else {
        self.from.len()
    };
    self.spare.resize(capacity, 0);
    let mut free = 0;
    for (&address, &len) in &self.roots {
        for i in 0..len {
            let slot = (address as *mut Word).wrapping_add(i);
            // SAFETY: registered ranges remain writable throughout collection.
            unsafe {
                slot.write(evacuate(
                    &mut self.from,
                    self.used,
                    &mut self.spare,
                    &mut free,
                    slot.read(),
                ));
            }
        }
    }
    let mut scan = 0;
    while scan < free {
        let header = self.spare[scan];
        let size = layout::size(header);
        let first = match layout::kind(header) {
            layout::CON => 0,
            layout::CLOSURE => 2, // code and arity are raw, not values
            layout::PAP => 0,
            layout::DOUBLE | layout::STRING => size,
            _ => panic!("invalid object in to-space"),
        };
        for field in first..size {
            if layout::kind(header) == layout::PAP && field == 1 {
                continue;
            }
            let slot = scan + 1 + field;
            let value = self.spare[slot];
            self.spare[slot] = evacuate(
                &mut self.from,
                self.used,
                &mut self.spare,
                &mut free,
                value,
            );
        }
        scan += size + 1;
    }
    std::mem::swap(&mut self.from, &mut self.spare);
    self.used = free;
    self.collections += 1;
    self.copied_words += free;
}
}

모든 할당 전에 수집을 수행하게 하는 FUN_GC_STRESS=1을 설정하면 낡은 포인터(stale pointer) 버그를 훨씬 쉽게 재현할 수 있습니다. 클로저나 PAP는 그것을 구성하는 단계 사이에 수집이 일어나더라도 살아남아야 합니다. 공유된 참조는 여전히 하나의 객체를 가리켜야 하고, 순환은 순환으로 남아야 하며, 원시 Double 비트를 추적할 필드로 오인해서는 결코 안 됩니다.

실행해 보기

$ cd crates/ch24_gc
$ cargo run -q -- dump --pass=llvm tests/programs/gc/partial.fun --gc=copying
; ... root arrays, rt_roots_push, reloads, rt_roots_pop ...
$ cargo test -p fun-rt-24 --test copying
$ cargo test --test copying

덤프는 LLVM 최적화 이전의 루트 프로토콜을 보여 줍니다. 스트레스 수집은 의도적으로 비용이 큽니다. 점점 커지는 살아 있는 리스트를 반복해서 복사하면 이차(quadratic) 작업이 듭니다. 스트레스 수집은 낡은 주소를 드러내는 데 사용하고, 일반 수집은 따로 측정하십시오. 어느 백엔드도 운영체제 할당 실패로부터의 복구를 약속하지 않습니다.

네이티브 복사 방식 실행 파일은 별도의 copying-only 런타임 아카이브를 링크합니다. 그 빌드에서는 Boehm 임포트와 링크 플래그가 제외됩니다. 일반 런타임 rlib은 여전히 JIT의 Boehm 힙을 지원합니다. just build는 두 아카이브를 모두 준비하고 각각의 네이티브 링크 플래그를 기록합니다. 한 테스트는 수집 스트레스 아래에서 실행 파일의 출력뿐 아니라 동적 의존성도 검사합니다.

힙 확장

추적이 올바른 것만으로는 충분하지 않습니다. 세미스페이스의 거의 전부가 살아 있으면, 각 수집은 큰 그래프를 복사하면서도 겨우 몇 워드만 회수할 수 있습니다. 용량 때문에 촉발된 수집 후에는, 살아 있는 데이터와 대기 중인 할당이 공간의 절반을 넘게 차지할 경우 우리는 공간을 키웁니다. 스트레스 수집은 여전히 모든 할당마다 실행되지만, 그 자체로 확장을 강제하지는 않습니다. 한 회귀 테스트는 공간의 8분의 7을 살아 있는 상태로 유지하고, 할당이 반복되는 동안 복사된 워드의 총량에 상한을 둡니다. 이 상한은 기계마다 다른 타이머에 의존하지 않고 수집기의 작업량을 측정합니다.

연습 문제

1. 준비 운동. 같은 객체를 가리키는 두 루트를 추적해 보십시오. 왜 복사본이 하나만 만들어지는지, 그리고 각 루트가 결국 어디를 가리키게 되는지 설명하십시오.
2. 중급. 클로저/PAP 그래프를 그리고 수집기가 건너뛰어야 하는 모든 페이로드 워드를 표시하십시오. 원시 메타데이터와 Double 비트에 대해 하위 비트 검사만으로는 왜 불충분한지 설명하십시오.
3. 중급. 생존성(liveness) 반복이 두 번 이상 필요한 join 역방향 간선(back-edge)의 예를 드십시오. 집합이 커져 가는 모습을 보이십시오.
4. 고급. 생존 범위가 겹치지 않는 루트 슬롯을 재사용하십시오. 기존 스트레스 테스트를 유지하고 생성된 프레임 크기를 비교하십시오.
5. 고급. 세대별 확장을 설계하십시오. 구현하기 전에, 재귀 클로저 패칭에 필요한 쓰기 장벽을 찾아내십시오.

더 읽을거리

Cheney는 비재귀 복사 알고리즘을 제시합니다 (Cheney 1970). Henderson은 다른 면에서는 협조적이지 않은 컴파일 환경에서 명시적 루트를 다루는 방법을 설명합니다 (Henderson 2002). 이 핸드북은 복사, 세대, 동시 수집을 전체적인 맥락 속에서 설명합니다 (Jones et al. 2023). 이 루트 계약을 Boehm과 Weiser의 보수적 접근 방식과 비교해 보십시오 (Boehm and Weiser 1988).