gc
1.0.0
gc — это реализация консервативного, локального по потокам сборщика мусора с маркировкой и очисткой. Реализация обеспечивает полнофункциональную замену стандартных вызовов POSIX malloc() , calloc() , realloc() и free() .
Целью gc является предоставление концептуально чистой реализации GC с маркировкой и очисткой, не углубляясь в глубины оптимизации, специфичной для архитектуры (см., например, GC Boehm для такой задачи). Он должен быть особенно пригоден для учебных целей и открыт для всех видов оптимизации (PR приветствуются!).
Первоначальной мотивацией для gc было мое желание написать свой собственный LISP на C полностью с нуля, а это потребовало сборки мусора.
Эта работа была бы невозможна без возможности читать работы других, в первую очередь Boehm GC, tgc Orangeduck (который также следует идеалам компактности и простоты) и 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, дополнительные сведения см. gc.h , а также низкоуровневый API.
Чтобы инициализировать и запустить сбор мусора, используйте функцию 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() . Просто используйте соответствующую вспомогательную функцию:
void * gc_malloc_static ( GarbageCollector * gc , size_t size , void ( * dtor )( void * )); Статическое распределение ожидает указатель на функцию финализации; просто установите значение NULL если финализация не требуется.
Обратите внимание, что gc в настоящее время не гарантирует определенный порядок при сборе статических переменных. Если статические переменные необходимо освободить в определенном порядке, пользователь должен вызвать для них gc_free() в желаемой последовательности перед вызовом gc_stop() , см. ниже. .
Также возможно вызвать явное освобождение памяти, используя
void gc_free ( GarbageCollector * gc , void * ptr ); Вызов gc_free() гарантированно (а) завершает/уничтожает объект, на который указывает ptr , если это применимо, и (b) освобождает память, на которую указывает ptr , независимо от текущего планирования сборки мусора, а также будет работать, если GC был приостановлено с помощью gc_pause() выше.
gc также предлагает реализацию strdup() , которая возвращает копию, собранную мусором:
char * gc_strdup ( GarbageCollector * gc , const char * s );Фундаментальная идея сборки мусора заключается в автоматизации цикла выделения/освобождения памяти. Это достигается путем отслеживания всей выделенной памяти и периодического освобождения памяти, которая все еще выделена, но недоступна.
Многие продвинутые сборщики мусора также реализуют свой собственный подход к выделению памяти (т.е. заменяют malloc() ). Это часто позволяет им размещать память более эффективно или для более быстрого доступа, но за это приходится платить архитектурными реализациями и повышенной сложностью. gc обходит эти проблемы, возвращаясь к реализации POSIX *alloc() и разделяя метаданные управления памятью и сборки мусора. Это делает gc намного проще для понимания, но, конечно же, менее эффективно с точки зрения пространства и времени, чем более оптимизированные подходы.
Базовая структура данных внутри gc представляет собой хеш-карту, которая сопоставляет адрес выделенной памяти с метаданными сборки мусора в этой памяти:
Элементы хэш-карты представляют собой распределения, смоделированные с помощью struct Allocation :
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 ; это вместе с набором static функций внутри gc.c обеспечивает семантику хэш-карты для реализации общедоступного API.
AllocationMap — это центральная структура данных в структуре GarbageCollector , которая является частью общедоступного API:
typedef struct GarbageCollector {
struct AllocationMap * allocs ;
bool paused ;
void * bos ;
size_t min_size ;
} GarbageCollector ; При наличии базовых структур данных любой запрос выделения памяти gc_*alloc() представляет собой двухэтапную процедуру: во-первых, выделение памяти с помощью системных функций (т. е. стандартных функций malloc() ), а во-вторых, добавление или обновление связанных метаданных в хеш-карта.
Для gc_free() используйте указатель, чтобы найти метаданные в хэш-карте, определить, требует ли освобождение вызова деструктора, вызвать при необходимости, освободить управляемую память и удалить запись метаданных из хеш-карты.
Эти структуры данных и связанные с ними интерфейсы позволяют управлять метаданными, необходимыми для создания сборщика мусора.
gc запускает сбор при двух обстоятельствах: (а) когда какой-либо из вызовов системного выделения завершается неудачно (в надежде освободить достаточно памяти для выполнения текущего запроса); и (b) когда количество записей в хеш-карте превышает динамически корректируемую верхнюю отметку.
Если происходит любой из этих случаев, gc останавливает мир и запускает сборку мусора по всем текущим выделениям. Эта функциональность реализована в функции gc_run() , которая является частью общедоступного API и делегирует всю работу функциям gc_mark() и gc_sweep() , которые являются частью частного API.
Задача gc_mark() — найти корни и пометить все известные выделения, на которые ссылаются из корня (или выделения, на которые ссылаются из корня, т. е. транзитивно), как «используемые». Как только разметка завершена, gc_sweep() перебирает все известные выделения и освобождает все неиспользуемые (т.е. немаркированные) выделения, возвращается в gc_run() , и мир продолжает работать.
gc сохранит доступные выделения памяти и соберет все остальное. Распределение считается достижимым, если выполняется любое из следующих условий:
gc_start() (т. е. bos — это наименьший адрес стека, рассматриваемый на этапе маркировки).gc_*alloc() есть указатель, который указывает на выделенное содержимое.GC_TAG_ROOT .Наивный алгоритм маркировки и очистки работает в два этапа. Во-первых, на этапе маркировки алгоритм находит и помечает все корневые выделения и все выделения, достижимые из корней. Во-вторых, на этапе очистки алгоритм пропускает все известные выделения, собирая все выделения, которые не были помечены и поэтому считаются недостижимыми.
В начале этапа маркировки мы сначала просматриваем все известные распределения и находим явные корни с помощью набора тегов GC_TAG_ROOT . Каждый из этих корней является отправной точкой для рекурсивной маркировки в глубину.
gc впоследствии обнаруживает все корни в стеке (начиная с указателя нижней части стека bos , который передается в gc_start() ) и регистры (путем сброса их в стек до фазы маркировки) и использует их в качестве отправных точек для маркировка тоже.
При наличии корневого выделения маркировка состоит из (1) установки поля tag в объекте Allocation в значение 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() . Чтобы отметить корни, мы делаем один полный проход по всем известным распределениям. Затем мы приступаем к сбросу регистров в стек.
Чтобы сделать содержимое регистра ЦП доступным для поиска root, gc сбрасывает его в стек. Это реализовано несколько переносимым способом с помощью setjmp() , который сохраняет их в переменной jmp_buf прямо перед тем, как мы разметим стек:
...
/* 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 );
... Обход с использованием указателя volatile функции _mark_stack к функции gc_mark_stack() необходим, чтобы избежать встраивания вызова в gc_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 ;
} Мы перебираем все распределения в хеш-карте (цикл for ), следуя каждой цепочке (цикл while с chunk = chunk->next update) и либо (1) снимаем пометку с фрагмента, если он был отмечен; или (2) вызвать деструктор фрагмента и освободить память, если она не была помечена, сохраняя промежуточный итог объема освобождаемой памяти.
На этом марка и подметание завершаются. Остановленный мир возобновляется, и мы готовы к следующему запуску!
