rokdocs
v0.1

7.3. GC 알고리듬

rok 의 GC 는 Immix mark-regionimmix 위에 sticky mark-bit 세대 수집whippet 을 얹은 수집기입니다. minor 수집과 evacuation 은 stop-the-world 이며 mutator 는 safepoint (8.4) 에서 멈춥니다. full 수집의 mark 는 동시에 할 수 있습니다 (7.5). 루트와 write barrier 는 7.4 에서 정의합니다.

7.3.1. Immix mark-region

block 과 line

block (32 KiB) = line (128 B) × 256

block 은 OS 에서 받습니다 (mmap). 객체는 line 경계를 넘을 수 있습니다. mark 는 객체와 함께 그 객체가 걸친 line 을 표시하며, sweep 은 표시 없는 line 을 회수합니다. 산 객체 사이의 작은 틈도 line 단위로 다시 씁니다.

sweep: block 분류

분류상태처리
clean모든 line 이 비어 있음free pool 로
recyclable일부 line 만 살아 있음빈 line 을 할당에 다시 씀
full거의 모든 line 이 살아 있음그대로 둠

sweep 은 비밀 buffer (WIPE, 7.1.2) 를 빼고는 죽은 객체를 0 으로 지우지 않습니다. 할당기가 TLAB 을 채울 때 line 을 0 으로 지웁니다.

opportunistic evacuation

full 수집은 단편화된 block 의 산 객체를 다른 block 으로 옮길 수 있습니다.

  • 후보는 직전 sweep 이 남긴 line 상태로 고릅니다 (절반 이하로 찬 block). 단편화 임계를 넘었을 때만 옮깁니다.
  • 옮긴 객체의 옛 자리에는 forwarding pointer 를 남기고, 같은 수집 안에서 모든 정밀 참조를 새 위치로 고칩니다.
  • 옮기지 않는 객체: 루트가 직접 가리키는 객체 (7.4.1), 모호한 word (AMBIGUOUS_WORD: type id 2 buffer, untagged union) 가 가리키는 객체, PINNED / NOMOVE 객체, LOS 객체.
  • 다음 cycle 의 할당 예산을 넘는 빈 block 은 OS 에 돌려줍니다.
  • 테스트용 ROK_GC_EVAC=always 는 full 수집마다 evacuation 합니다 (9.9.8).

7.3.2. sticky mark-bit 세대 수집

nursery 공간을 따로 두지 않고, 헤더의 STICKY 비트 (8.1.3) 로 세대를 나눕니다. 수집에서 살아남은 객체는 STICKY 를 켜고 old 가 됩니다. 객체는 제자리에 있으며 promotion 복사가 없습니다.

수집mark 의 출발점범위
minor (young)루트, remembered set, dirty card (7.4.2)old 객체 안으로 들어가지 않음. sweep 은 지난 수집 뒤 나눠 준 line 만
full (old)루트STICKY 를 모두 지우고 전체 mark / sweep
  • young line 은 객체 조회가 닿은 block 만 파싱합니다.
  • full 수집은 old 객체의 바이트가 max(4 MiB, 직전 full 수집 뒤 live × 2) 에 닿을 때, 또는 rok_gc_collect 를 부를 때 일어납니다.

7.3.3. mark 의 절차

  1. 루트 (7.4.1) 에서 시작합니다.
  2. 도달한 객체마다 헤더의 MARK 를 켜고, 걸친 line 을 표시하고, type_id 의 ScanTable 로 자식을 따라갑니다.
  3. 큐가 비면 끝납니다.

ScanTable 은 rok_gc_register_type (8.5.1) 으로 등록됩니다.

참고 문헌

immix Blackburn & McKinley, Immix: A Mark-Region Garbage Collector with Space Efficiency, Fast Collection, and Mutator Performance, PLDI 2008.

whippet Wingo, Whippet: a sub-toolkit for embeddable garbage collection. https://wingolog.org/tags/whippet

GitHub에서 이 페이지 고치기