gc
1.0.0
gc 는 보수적인 스레드 로컬 마크 앤 스윕 가비지 수집기의 구현입니다. 구현은 표준 POSIX malloc() , calloc() , realloc() 및 free() 호출에 대한 완전한 기능적 대체를 제공합니다.
gc 의 초점은 아키텍처별 최적화의 깊이를 탐구하지 않고 개념적으로 표시 및 청소 GC의 깔끔한 구현을 제공하는 것입니다(이러한 작업에 대해서는 Boehm GC 참조). 특히 학습 목적에 적합해야 하며 모든 종류의 최적화에 열려 있습니다(PR 환영!).
gc 의 원래 동기는 완전히 처음부터 C로 나만의 LISP를 작성하려는 욕구였으며 이를 위해서는 가비지 수집이 필요했습니다.
이 작업은 다른 사람들의 작업, 특히 Boehm GC, orangeduck의 tgc(작고 단순하다는 이상을 따르는) 및 The Garbage Collection Handbook의 작업을 읽을 수 있는 능력이 없었다면 불가능했을 것입니다.
gc 구현에 적용된 기본 개념과 디자인 결정을 설명합니다. $ git clone [email protected]:mkirchner/gc.git
$ cd gc
clang 컴파일러를 사용하여 컴파일하려면:
$ make test
GNU 컴파일러 컬렉션(GCC)을 사용하려면:
$ make test CC=gcc
테스트가 성공적으로 완료되어야 합니다. 현재 적용 범위 보고서를 생성하려면:
$ make coverage
...
#include "gc.h"
...
void some_fun () {
...
int * my_array = gc_calloc ( & gc , 1024 , sizeof ( int ));
for ( size_t i = 0 ; i < 1024 ; ++ i ) {
my_array [ i ] = 42 ;
}
...
// look ma, no free!
}
int main ( int argc , char * argv []) {
gc_start ( & gc , & argc );
...
some_fun ();
...
gc_stop ( & gc );
return 0 ;
} 이는 핵심 API에 대해 설명합니다. 자세한 내용과 하위 수준 API는 gc.h 참조하세요.
가비지 수집을 초기화하고 시작하려면 gc_start() 함수를 사용하고 스택 하단 주소를 전달하세요.
void gc_start ( GarbageCollector * gc , void * bos ); 스택 하단 매개변수 bos 스택에 할당된 변수를 가리켜야 하며 루트 찾기(스캔)가 시작되는 스택의 하단을 표시해야 합니다.
가비지 수집을 중지, 일시 중지 및 재개할 수 있습니다.
void gc_stop ( GarbageCollector * gc );
void gc_pause ( GarbageCollector * gc );
void gc_resume ( GarbageCollector * gc );수동 가비지 수집은 다음을 통해 트리거될 수 있습니다.
size_t gc_run ( GarbageCollector * gc ); gc malloc() , calloc() 및 realloc() 스타일 메모리 할당을 지원합니다. 각 함수 서명은 POSIX 함수를 모방합니다(가비지 수집기를 첫 번째 인수로 전달해야 한다는 점은 제외).
void * gc_malloc ( GarbageCollector * gc , size_t size );
void * gc_calloc ( GarbageCollector * gc , size_t count , size_t size );
void * gc_realloc ( GarbageCollector * gc , void * ptr , size_t size );확장된 인터페이스를 통해 소멸자 함수에 대한 포인터를 전달할 수 있습니다.
void * dtor ( void * obj ) {
// do some cleanup work
obj -> parent -> deregister ();
obj -> db -> disconnect ()
...
// no need to free obj
}
...
SomeObject * obj = gc_malloc_ext ( gc , sizeof ( SomeObject ), dtor );
... gc gc_stop() 통해 GC가 종료될 때만 가비지 수집되는 정적 할당을 지원합니다. 적절한 도우미 함수를 사용하세요.
void * gc_malloc_static ( GarbageCollector * gc , size_t size , void ( * dtor )( void * )); 정적 할당에는 종료 함수에 대한 포인터가 필요합니다. 마무리가 필요하지 않은 경우에는 NULL 로 설정하면 됩니다.
gc 현재 정적 변수를 수집할 때 특정 순서를 보장하지 않습니다. 정적 변수를 특정 순서로 할당 해제해야 하는 경우 사용자는 gc_stop() 호출하기 전에 원하는 순서로 gc_free() 호출해야 합니다. 아래를 참조하세요. .
다음을 사용하여 명시적인 메모리 할당 해제를 트리거하는 것도 가능합니다.
void gc_free ( GarbageCollector * gc , void * ptr ); gc_free() 호출은 (a) 해당되는 경우 ptr 이 가리키는 객체를 종료/파괴하고 (b) 가비지 수집에 대한 현재 일정에 관계없이 ptr 이 가리키는 메모리를 해제하며 GC가 실행된 경우에도 작동합니다. 위의 gc_pause() 사용하여 일시 중지되었습니다.
gc 또한 가비지 수집된 복사본을 반환하는 strdup() 구현을 제공합니다.
char * gc_strdup ( GarbageCollector * gc , const char * s );가비지 수집의 기본 아이디어는 메모리 할당/할당 취소 주기를 자동화하는 것입니다. 이는 할당된 모든 메모리를 추적하고 여전히 할당되어 있지만 연결할 수 없는 메모리에 대한 할당 해제를 주기적으로 트리거하여 수행됩니다.
많은 고급 가비지 수집기는 메모리 할당에 대한 자체 접근 방식도 구현합니다(예: malloc() 대체). 이를 통해 더 공간 효율적인 방식으로 또는 더 빠른 액세스를 위해 메모리를 레이아웃할 수 있지만 아키텍처별 구현 비용과 복잡성이 증가하는 대가를 치르게 됩니다. gc POSIX *alloc() 구현을 사용하고 메모리 관리와 가비지 수집 메타데이터를 별도로 유지함으로써 이러한 문제를 회피합니다. 이는 gc 이해하기 훨씬 쉽게 만들지만, 물론 최적화된 접근 방식보다 공간 및 시간 효율성이 떨어집니다.
gc 내부의 핵심 데이터 구조는 할당된 메모리의 주소를 해당 메모리의 가비지 수집 메타데이터에 매핑하는 해시 맵입니다.
해시 맵의 항목은 Allocation struct 로 모델링된 할당입니다.
typedef struct Allocation {
void * ptr ; // mem pointer
size_t size ; // allocated size in bytes
char tag ; // the tag for mark-and-sweep
void ( * dtor )( void * ); // destructor
struct Allocation * next ; // separate chaining
} Allocation ; 각 Allocation 인스턴스는 할당된 메모리에 대한 포인터, 해당 위치에 할당된 메모리의 크기, 표시 및 스윕을 위한 태그(아래 참조), 소멸자 함수에 대한 선택적 포인터 및 다음 Allocation 인스턴스에 대한 포인터( 별도의 연결에 대해서는 아래를 참조하세요).
할당은 AllocationMap 에 수집됩니다.
typedef struct AllocationMap {
size_t capacity ;
size_t min_capacity ;
double downsize_factor ;
double upsize_factor ;
double sweep_factor ;
size_t sweep_limit ;
size_t size ;
Allocation * * allocs ;
} AllocationMap ; 이는 gc.c 내부의 static 함수 세트와 함께 공개 API 구현을 위한 해시 맵 의미를 제공합니다.
AllocationMap 은 공개 API의 일부인 GarbageCollector 구조체의 중앙 데이터 구조입니다.
typedef struct GarbageCollector {
struct AllocationMap * allocs ;
bool paused ;
void * bos ;
size_t min_size ;
} GarbageCollector ; 기본 데이터 구조가 갖춰진 상태에서 모든 gc_*alloc() 메모리 할당 요청은 2단계 절차입니다. 먼저 시스템(예: 표준 malloc() ) 기능을 통해 메모리를 할당하고, 두 번째로 관련 메타데이터를 추가하거나 업데이트합니다. 해시 맵.
gc_free() 의 경우 포인터를 사용하여 해시 맵에서 메타데이터를 찾고, 할당 해제에 소멸자 호출이 필요한지 결정하고, 필요한 경우 호출하고, 관리되는 메모리를 해제하고 해시 맵에서 메타데이터 항목을 삭제합니다.
이러한 데이터 구조 및 관련 인터페이스를 통해 가비지 수집기를 구축하는 데 필요한 메타데이터를 관리할 수 있습니다.
gc 두 가지 상황에서 수집을 트리거합니다. (a) 시스템 할당에 대한 호출 중 하나라도 실패할 때(현재 요청을 이행하기에 충분한 메모리 할당을 해제하기 위해); (b) 해시 맵의 항목 수가 동적으로 조정된 최고 워터마크를 통과할 때.
이러한 경우 중 하나가 발생하면 gc 세계를 중지하고 모든 현재 할당에 대해 표시 및 청소 가비지 수집 실행을 시작합니다. 이 기능은 공개 API의 일부인 gc_run() 함수에서 구현되며 모든 작업을 비공개 API의 일부인 gc_mark() 및 gc_sweep() 함수에 위임합니다.
gc_mark() 에는 루트를 찾고 루트(또는 루트에서 참조되는 할당, 즉 전이적으로)에서 참조되는 모든 알려진 할당에 "사용됨"으로 태그를 지정하는 작업이 있습니다. 표시가 완료되면 gc_sweep() 알려진 모든 할당을 반복하고 사용되지 않은(즉 표시되지 않은) 할당을 모두 할당 해제하고 gc_run() 으로 반환되며 세계는 계속 실행됩니다.
gc 도달 가능한 메모리 할당을 유지하고 다른 모든 것을 수집합니다. 다음 중 하나라도 해당되면 할당에 도달 가능한 것으로 간주됩니다.
gc_start() 에 전달된 스택 하단 변수만큼 호출 스택 깊이에 있는 스택 프레임에 있어야 합니다(즉 bos 표시 단계에서 고려되는 가장 작은 스택 주소입니다).gc_*alloc() 할당 콘텐츠 내부에는 할당 콘텐츠를 가리키는 포인터가 있습니다.GC_TAG_ROOT 태그가 지정됩니다.순진한 표시 및 청소 알고리즘은 두 단계로 실행됩니다. 먼저 표시 단계에서는 알고리즘이 모든 루트 할당과 해당 루트에서 도달할 수 있는 모든 할당을 찾아서 표시합니다. 둘째, 스윕 단계에서 알고리즘은 알려진 모든 할당을 통과하여 표시되지 않아 도달할 수 없는 것으로 간주되는 모든 할당을 수집합니다.
표시 단계가 시작될 때 먼저 알려진 모든 할당을 검색하고 GC_TAG_ROOT 태그 세트를 사용하여 명시적인 루트를 찾습니다. 이러한 각 루트는 깊이 우선 재귀 표시의 시작점입니다.
gc 이어서 스택의 모든 루트( gc_start() 에 전달된 스택 하단 포인터 bos 에서 시작)와 레지스터(표시 단계 전에 스택에 덤프하여)를 검색하고 이를 시작점으로 사용합니다. 마킹도 그렇고.
루트 할당이 있는 경우 표시는 (1) Allocation 개체의 tag 필드를 GC_TAG_MARK 로 설정하고 (2) 할당된 메모리에서 알려진 할당에 대한 포인터를 검색하여 프로세스를 반복적으로 반복하는 것으로 구성됩니다.
기본 구현은 잠재적인 참조를 찾기 위해 모든 메모리 내용을 검색하는 간단하고 재귀적인 깊이 우선 검색입니다.
void gc_mark_alloc ( GarbageCollector * gc , void * ptr )
{
Allocation * alloc = gc_allocation_map_get ( gc -> allocs , ptr );
if ( alloc && !( alloc -> tag & GC_TAG_MARK )) {
alloc -> tag |= GC_TAG_MARK ;
for ( char * p = ( char * ) alloc -> ptr ;
p < ( char * ) alloc -> ptr + alloc -> size ;
++ p ) {
gc_mark_alloc ( gc , * ( void * * ) p );
}
}
} gc.c 에서 gc_mark() gc_mark_roots() 호출을 통해 스택에 알려진 루트를 표시하여 표시 프로세스를 시작합니다. 루트를 표시하기 위해 알려진 모든 할당에 대해 한 번의 전체 전달을 수행합니다. 그런 다음 스택에 레지스터를 덤프합니다.
루트 찾기에 CPU 레지스터 내용을 사용할 수 있도록 gc 해당 내용을 스택에 덤프합니다. 이것은 스택을 표시하기 직전에 jmp_buf 변수에 저장하는 setjmp() 사용하여 다소 이식 가능한 방식으로 구현됩니다.
...
/* Dump registers onto stack and scan the stack */
void ( * volatile _mark_stack )( GarbageCollector * ) = gc_mark_stack ;
jmp_buf ctx ;
memset ( & ctx , 0 , sizeof ( jmp_buf ));
setjmp ( ctx );
_mark_stack ( gc );
... gc_mark_stack() gc_mark_stack() 함수에 대한 volatile 함수 포인터 _mark_stack 사용하는 우회가 필요합니다.
도달 가능하여 잠재적으로 여전히 사용 중인 모든 메모리를 표시한 후에는 도달할 수 없는 할당을 수집하는 것이 쉽지 않습니다. 다음은 gc_sweep() 의 구현입니다.
size_t gc_sweep ( GarbageCollector * gc )
{
size_t total = 0 ;
for ( size_t i = 0 ; i < gc -> allocs -> capacity ; ++ i ) {
Allocation * chunk = gc -> allocs -> allocs [ i ];
Allocation * next = NULL ;
while ( chunk ) {
if ( chunk -> tag & GC_TAG_MARK ) {
/* unmark */
chunk -> tag &= ~ GC_TAG_MARK ;
chunk = chunk -> next ;
} else {
total += chunk -> size ;
if ( chunk -> dtor ) {
chunk -> dtor ( chunk -> ptr );
}
free ( chunk -> ptr );
next = chunk -> next ;
gc_allocation_map_remove ( gc -> allocs , chunk -> ptr , false);
chunk = next ;
}
}
}
gc_allocation_map_resize_to_fit ( gc -> allocs );
return total ;
} 모든 체인(청크가 있는 while chunk = chunk->next 업데이트)을 따라 해시 맵( for 루프)의 모든 할당을 반복하고 (1) 청크가 표시된 경우 청크 표시를 해제합니다. 또는 (2) 청크에서 소멸자를 호출하고 메모리가 표시되지 않은 경우 메모리를 해제하여 해제된 메모리 양의 총계를 유지합니다.
이로써 마크 앤 스윕 실행이 종료됩니다. 멈춰 있던 세계가 재개되고 다음 달릴 준비가 완료되었습니다!
