Этот пост станет итерацией туториала и знакомством с реализацией сборки мусора, описанной в классической статье. Мы продолжим работать с простыми сборщиками мусора, но на этот раз немного повысим сложность.
Я подумал, что это будет здорово, ведь в коде из статьи уже имелся крошечный, но функциональный мутатор, а набор тестов был призван это подчеркнуть; это значит, что мы можем сравнивать производительность и реализацию копирующего сборщика и обычного сборщика.
▍ Исходный код для этого поста
Исходный код можно найти в репозитории github.
Кроме того, код хостится локально на моём сайте, поэтому его можно скачать следующей командой:
wget https://jennyjams.net/copygc/src.zipКопирующие сборщики
Копирующим называется сборщик мусора, тесно связывающий себя с базовой системой распределения: у нас есть два логических (а здесь и физических) областей памяти. Одна из них делается активной областью, и вся новая память распределяется из этой области.
Затем подсистема сборки мусора определяет, что использовано достаточное для сбора мусора количество памяти, после чего активная область становится неактивной, и наоборот, а сборщик мусора определяет множество живых объектов и эвакуирует эти области из уже неактивной области в новую активную. Затем мы берём все указатели в перемещённом объекте и проверяем, были ли уже перенаправлены указатели, на которые они указывают в старой области. Если да, используем перенаправленный указатель, если нет, выполняем эвакуацию.
Если объект уже был перемещён, то объект в неактивной области можно использовать заново, чтобы он содержал указатель на его эвакуированную копию; это помогает сохранять топологию графа объекта и устранять все циклические ссылки, которые склонен создавать код.
Алгоритм Чейни
В посте мы будем использовать алгоритм Чейни, придуманный в далёких 1970-х.
- Заменяем активную кучу.
- Обходим множество корней и эвакуируем указатель на новую кучу.
- После эвакуации всех объектов начинаем обходить все заново распределённые объекты и изучать каждое из их полей. Если поле оказывается указателем и указывает на старую область, то проверяем, имеет ли оно адрес перенаправления. Если да, то записываем в поле адрес перенаправления. Если нет, то эвакуируем его.
Как это выглядит в виде псевдокода:
def collect_garbage():
swap_heap()
for root in roots:
if field in old_region:
root.pointer = evacuate(root.pointer)
while not worklist.is_empty():
obj = worklist.pop()
for field in obj.fields():
if field.pointer is in old_region:
field.pointer = evacuate(root.pointer)
def evacuate(ptr):
if has_forward_address(ptr):
return ptr.forward
new_object = allocate_from_active()
copy(new_object, ptr)
ptr.forward = new_object
worklist.append(new_object)Однако мне кажется, что многое связанное со сборкой мусора может казаться крайне абстрактным, особенно когда начинаешь разбираться с квазирекурсивностью, поэтому я лучше объясню всё в картинках.
Алгоритм Чейни, на этот раз в картинках
Сначала наше исходное состояние показывает, что одна из куч забита памятью, поэтому сборщик решает начать сборку мусора. Набор прямоугольников слева — это множество корней (представленное в виде стека с тремя активными членами), а два прямоугольника справа — это две области кучи.
Мы начинаем с обхода каждого из корней. Синим обозначены ещё не обработанные объекты.
Первый корень указывает на ещё не переданный объект кучи, из которой производится копирование, поэтому мы переносим его в кучу, куда производится копирование, и изменяем объект из первой кучи так, чтобы он указывал на него (обозначенный сиреневым цветом и кривой пунктирной линией).
Теперь, когда мы переслали то, на что указывал первый корень, мы меняем его так, чтобы он указывал на эвакуированный объект в куче, куда выполняется копирование, и удаляем его из важного нам множества объектов, снова обозначив его коричневым.
Далее мы обрабатываем второй корень. Поскольку он указывает на объект, который мы уже переслали, потому что обрабатывали его ранее, просто делаем так, чтобы корень указывал на эвакуированный объект во второй куче, и удаляем второй корень.
Затем мы обрабатываем последний корень. Он указывает на объект, который сам имеет указатель, так что сначала мы эвакуируем его и изменяем объект из первой кучи так, чтобы он указывал на него. Однако поскольку мы его только что скопировали, эвакуированный объект сам по-прежнему указывает на объект из первой кучи.
Далее мы изменяем последний корень так, чтобы он указывал на эвакуированный указатель. Мы закончили со всем множеством корней, и теперь должны начать обработку объектов во второй куче, чтобы переместить все объекты, на которые не было прямых указателей из корней.
Мы обрабатываем первый объект из первой кучи. Так как он просто хранит в себе integer, нет необходимости выполнять какую-то другую работу, и можно переходить к следующему объекту.
Второй элемент во второй куче — это объект, содержащий указатель на объект в первой куче. Мы должны эвакуировать и переслать этот объект, а также добавить его во множество важных для нас объектов.
Теперь, когда второй элемент во второй куче указывает на переданный указатель, мы можем исправить его указатель так, чтобы он указывал на эвакуированный объект во второй куче, таким образом убрав его из списка важных для нас.
Далее мы обрабатываем последний объект. Так как он не содержит указателей, мы просто удаляем его из множества важных нам объектов.
Наконец у нас не осталось элементов для обработки ни в одном из корней или в куче. Можно очистить старую кучу и уничтожить все предыдущие объекты.
Сборка мусора завершена.
Самый маленький в мире распределитель памяти
В отличие от сборщика Mark&Sweep, копирующий сборщик использует для освобождения памяти собственный распределитель, поэтому мы не можем использовать функцию
malloc() и free() стандартной библиотеки — вместо того, чтобы вызывать функцию для освобождения памяти для каждого объекта, который мы определили как неживой, мы неявным образом освобождаем её, когда меняем местами кучи, потому что все данные в нашем распределителе повторно используются для будущего распределения.Значит, нам нужен распределитель!
Простейший возможный распределитель — это bump-распределитель: просто большая непрерывная область памяти и смещение. При каждом выполнении вызова
allocate(size) он возвращает указатель на память, которая находится по смещению offset байтов в области памяти. Затем выполняется инкремент смещения (offset) на этот размер.У такого распределителя нет целостной операции
free() — даже если мы заранее логически освободим память в распределителе, сам распределитель не сможет повторно использовать её. Таким образом, единственный реальный способ сброса памяти заключается в удалении всех распределений и в сбросе offset на 0.Благодаря этому свойству, этот паттерн распределения становится полезным в таких ситуациях, как веб-серверы или видеоигры, где запрос или отдельный кадр могут генерировать большие объёмы данных, которые неразумно хранить после него; операция
clear() будет гораздо быстрее, чем попытки освобождения каждого из этих объектов.
На этой схеме показано множество объектов, которое будет заполнено указателями на объекты, распределённые bump-распределителем, а также сам bump-распределитель. Bump-распределитель состоит из смещения (или указателя) на базовое распределение, а также из большого блока памяти.
Распределение выполнено — указатель объекта теперь указывает на блок памяти плюс смещение. Затем смещение перемещено вниз, чтобы указывать на следующую свободную часть памяти.
И снова, с другим размером.
И снова.
Затем мы вызываем
clear() и сбрасываем смещение, чтобы оно указывало на начало блока памяти, по сути, освобождая память; если системе требуется повышенная защита, можно выполнить memset() распределённых частей памяти на ноль, чтобы предотвратить потенциальную утечку информации. Все предыдущие указатели на память теперь стали висячими — хоть они и указывают на отображённую валидную память, указатели на эту память с большой вероятностью будут иметь неверный тип или значение и будут указывать на середину другого объекта.
Далее мы снова распределяем память и начинаем распределение с начала блока памяти.
А теперь перейдём к коду
Ниже я представлю код для каждой из основных частей сборщика, которые мы будем менять, и прокомментирую строки, в котором я переписываю старый код.
Исправляем нашу единую модель объектов
Так как мы дополняем готовую кодовую базу, чтобы заменить стратегию сборки мусора, для этих изменений нам нужно выполнить некий код.
Сначала мы изменим модель объектов нашей VM, чтобы удалить указатель на внедрённый связанный список и чтобы добавить к нашему ещё один случай для union перенаправляющего указателя. Это одно из канонических преимуществ копирования перед более традиционными схемами mark-sweep, mark-compact и reference-counting: нам не нужны никакие дополнительные метаданные внутри заголовка.
Однако нам нужно использовать перенаправляющий указатель. Можно подумать, что это должно означать необходимость траты дополнительных ресурсов на ещё один указатель, но так как объект, который мы модифицируем, чтобы он указывал на новый объект, не будет иметь другого предназначения, то можно повторно использовать пространство для одного из его полей.
typedef struct sObject {
ObjectType type;
// Удалили ``struct sObject* next;``
union {
/* OBJ_INT */
int value;
/* OBJ_PAIR */
struct {
struct sObject* head;
struct sObject* tail;
};
struct sObject* forward; // <-- Новая строка
};
} Object;Также нам нужна новая метка, чтобы показать, что объект перенаправлен.
typedef enum {
OBJ_INT,
OBJ_PAIR,
OBJ_FRWD // <-- Новая строка
} ObjectType;Далее мы изменим модель VM так, чтобы она хранила код для начала и конца списка работ кучи.
typedef struct {
Object* stack[STACK_MAX];
int stackSize;
/* Первый и последний объект в куче */
Object* firstObject;
Object* lastObject; // <-- Новая строка
/* Общее количество текущих распределённых объектов */
int numObjects;
/* Количество объектов, требуемое для запуска сборки мусора */
int maxObjects;
} VM;Самый маленький в мире распределитель, в двух экземплярах
На самом деле, в нашем случае нужно два bump-распределителя. Мы можем хранить одно смещение, а также дополнительный бит состояния, определяющий используемый пул. Можно использовать скучные имена наподобие Область 1 и Область 2 или Область А и Область Б, но мне хотелось чего-то более милого, поэтому я назвал их Областями Буба и Кики.
Для начала нам нужно подобрать максимальный размер, я просто остановился на 2^16:
#define HEAP_MAX 65536Далее нужно задать структуру данных. Следуя терминологии алгоритма Чейни и других статей, мы назовём её кучей (heap).
typedef struct {
size_t bump_offset;
Region region;
unsigned char region_boba[HEAP_MAX];
unsigned char region_kiki[HEAP_MAX];
} Heap;Для начала нам нужен код генерации нового объекта Heap. Мы выполняем
memset() памяти на ноль, чтобы не осталось никаких предыдущих данных.// Распределяем память и создаём новую Heap
Heap* newHeap() {
Heap* heap = malloc(sizeof(Heap));
memset(heap->region_boba, 0, sizeof heap->region_boba);
memset(heap->region_kiki, 0, sizeof heap->region_kiki);
heap->region = RGN_BOBA;
heap->bump_offset = 0;
return heap;
}Немного странно то, что после написания собственного распределителя мы просто выполняем
malloc(), чтобы получить память для распределителя, но такое встречается довольно часто: если только вы сами не реализуете malloc() или распределитель памяти более низкого уровня, вы обычно используете для получения памяти вызов какой-нибудь функции. И у нас под рукой как раз есть malloc()!А теперь переходим к распределению!
void* heapAlloc(Heap* heap, size_t size) {
assert(heap->bump_offset + size < HEAP_MAX,
"Attempted to allocate more items that can be in heap");
void* pointer = NULL;
if (heap->region == RGN_BOBA) {
pointer = heap->region_boba + heap->bump_offset;
}
else {
pointer = heap->region_kiki + heap->bump_offset;
}
heap->bump_offset += size;
return pointer;
}Мы не можем использовать этот распределитель, если только у нас нет способа очистки bump-распределителя. Вместо применения рассмотренного выше интерфейса
clear() мы заменяем активную кучу, а затем сбрасываем смещение в ноль. При этом также обновляются некоторые данные в VM, чтобы позже мы могли исправить указатели, так что мы передаём указатель виртуальной машине, а не куче.void swapHeap(VM* vm) {
if (vm->heap->region == RGN_BOBA) {
vm->heap->region = RGN_KIKI;
vm->firstObject = vm->lastObject = (Object*) vm->heap->region_kiki;
}
else {
vm->heap->region = RGN_BOBA;
vm->firstObject = vm->lastObject = (Object*) vm->heap->region_boba;
}
vm->heap->bump_offset = 0;
}Кроме того, поскольку мы больше не используем
malloc() для распределения объектов, нам нужно изменить функцию newObject().Также мы изменяем способ распределения объектов, чтобы убрать код из внедрённого связанного списка.
Object* newObject(VM* vm, ObjectType type) {
if (vm->numObjects == vm->maxObjects) gc(vm);
Object* object = heapAlloc(vm->heap, sizeof(Object)); // <-- Новая строка
object->type = type;
vm->numObjects++; // <-- Новая строка
return object;
}Наконец, нам нужно дополнить объект VM, чтобы он содержал указатель на Heap. Также добавим поле указателя
lastObject, которое мы используем на этапе сборки мусора.VM* newVM() {
VM* vm = malloc(sizeof(VM));
vm->stackSize = 0;
vm->firstObject = NULL;
vm->lastObject = NULL; // <-- Новая строка
vm->numObjects = 0;
vm->maxObjects = INIT_OBJ_NUM_MAX;
vm->heap = newHeap(); // <-- Новая строка
return vm;
}В конце мы, как ответственные пользователи C, при освобождении VM освобождаем объект кучи, который распределили при помощи
malloc().void freeVM(VM *vm) {
vm->stackSize = 0;
gc(vm);
free(vm->heap); // <-- Новая строка
free(vm);
}Никакого больше mark, только пересылка
Так как мы никогда не задействуем ни marking, ни sweeping, можно удалить почти весь код, связанный с кодом mark&sweep (который больше не будет корректно компилироваться, потому что мы изменили наши типы VM и Object).
Сначала нам нужно обработать все наши корни. Для этого мы просто обходим каждый из корней и выполняем эвакуацию и пересылку для каждого из объектов, на которые есть указатели:
void processRoots(VM* vm) {
for (int i = 0; i < vm->stackSize; i++) {
vm->stack[i] = forward(vm, vm->stack[i]);
}
}При передаче объекта мы сначала проверяем, не был ли он уже передан.
Если был, мы просто возвращаем переданный указатель, поскольку знаем, что он в куче, в которую выполняется копирование (обозначим её to-heap).
Object* forward(VM* vm, Object* object) {
assert(inFromHeap(vm->heap, object), "Object must be in from-heap.");
if (object->type == OBJ_FRWD) return object->forward;
//...
}Если не был, то мы распределяем новый объект в to-heap и копируем содержимое объекта в куче, из которой выполняется копирование (from-heap). Затем мы изменяем поле
vm->lastObject так, чтобы оно указывало на объект за текущим распределённым объектом. Это один из случаев в кодовой базе, когда я пользуюсь тем, что все объекты имеют одинаковый общий размер; если бы они были разного размера, то это бы выглядело примерно так: vm->lastObject = (Object*) ((char*)copied + getObjectSize(copied).Object* forward(VM* vm, Object* object) {
assert(inFromHeap(vm->heap, object), "Object must be in from-heap.");
if (object->type == OBJ_FRWD) return object->forward;
Object* copied = heapAlloc(vm->heap, sizeof(Object));
vm->numObjects++;
memcpy(copied, object, sizeof(Object));
vm->lastObject = copied + 1;
return copied;
}В конце мы записываем в наш старый объект перенаправляющий указатель:
Object* forward(VM* vm, Object* object) {
assert(inFromHeap(vm->heap, object), "Object must be in from-heap.");
if (object->type == OBJ_FRWD) return object->forward;
Object* copied = heapAlloc(vm->heap, sizeof(Object));
vm->numObjects++;
memcpy(copied, object, sizeof(Object));
vm->lastObject = copied + 1;
// задаём перенаправляющий указатель
object->type = OBJ_FRWD;
object->forward = copied;
return copied;
}Перейдём ко всем косвенно обходимым объектам, которые я не обрабатывал
Теперь, когда у нас есть механизм для перенаправления указателей, мы обработали все объекты, на которые указывали корни. Далее нам нужно обработать объекты, на которые по-прежнему указывают эти перемещённые объекты.
В изначальной схеме mark-sweep проблема достижимости решалась до выполнения всего управления памятью: мы рекурсивно обходили граф объекта, выходили, если объект уже был помечен, чтобы избежать зацикленности, а затем обходили связанный список, чтобы удалить все непомеченные объекты.
Здесь же достижимость и разметка перемешаны между собой: мы итеративно обходим каждый из объектов в новой куче, а когда видим, что у него есть поле, указывающее на from-heap, перемещаем его и помещаем в конец нашей кучи, а когда добираемся до её сканирования, чиним все её указатели, пока не дойдём до конца.
Воспользовавшись тем, что все объекты в нашей VM имеют одинаковый размер, мы можем просто выполнять инкремент указателя. Если бы это было не так, нам бы пришлось выполнять дополнительную работу по инкременту на размер объекта.
void processWorklist(VM* vm) {
while (vm->firstObject != vm->lastObject) {
// Перенаправляем подуказатели объекта Pair
if (vm->firstObject->type == OBJ_PAIR) {
vm->firstObject->head = forward(vm, vm->firstObject->head);
vm->firstObject->tail = forward(vm, vm->firstObject->tail);
}
vm->firstObject++;
}
}Завязываем мешок с мусором
В конце изменим функцию
gc(), чтобы теперь мы могли выполнять вызов в нашу новую схему mark&compact.void gc(VM* vm) {
int numObjects = vm->numObjects;
vm->numObjects = 0;
swapHeap(vm); // <-- Новая строка
processRoots(vm); // <-- Новая строка
processWorklist(vm); // <-- Новая строка
vm->lastObject = NULL; // <-- Новая строка
vm->firstObject = NULL; // <-- Новая строка
vm->maxObjects = vm->numObjects == 0 ? INIT_OBJ_NUM_MAX : vm->numObjects * 2;
printf("Collected %d objects, %d remaining.\n", numObjects - vm->numObjects,
vm->numObjects);
}Плюсы и минусы копирующего сборщика
Итак, мы получили копирующий сборщик. Что мы получили и о чём сильно пожалеем?
▍ Плюс: устранили лишние траты на список объектов
Мы непосредственно избавились от лишних трат на дополнительный указатель, который VM использует только при сборке мусора; это позволяет нам экономить по 8 байтов на объект, а подобные затраты могут оказаться достаточно большими.
Но кроме того, вдобавок к пространственным затратам, мы также избавились и от временных — нам не нужно больше обходить связанный список, и из-за когерентности кэша это может стать очень важным изменением. Поскольку мы всегда обходим только массив, нам не нужно очищать кэш и у нас может больше не возникать проблем (потенциально) с удалением кэша памяти и повторным его заполнением.
Кроме того, мы получили гораздо более простой распределитель, чем системный
malloc()/free(), но за это пришлось расплачиваться гибкостью системы, а также отказаться от всей защиты от возможных эксплойтов и гонок данных. Это не особая проблема для нашего крошечного мутатора, находящегося в системе, которая никогда не доберётся до продакшена, но в более серьёзных проектах это необходимо учитывать.▍ Плюс: активная работа зависит от количества живых объектов
Сборщик mark&sweep должен при подчистке объектов обходить графы объектов целиком. В отличие от него, копирующему сборщику достаточно поработать с каждым из корней и с каждым из объектов, которые были перемещены в кучу to-heap. Если у нас есть очень большое количество мёртвых объектов и очень малое количество живых, то это может стать огромным преимуществом перед реализацией mark&sweep.
▍ Плюс: снижение фрагментации
Сборщику мусора mark&sweep, использующему
malloc() (или любой другой распределитель, имеющий дело с данными переменного размера) приходится мириться с фрагментацией — может оказаться так, что после долгих циклов освобождения памяти у нас достаточно памяти для распределения, но отсутствуют достаточно большие сплошные блоки памяти. Когда копирующие сборщики перемещают объекты, они просто выталкивают их все в одну сторону кучи, благодаря чему образуется большое сплошное пространство, из которого можно распределить новую память, и отсутствуют пробелы с неудобным размером.▍ Минус: уменьшение эффективного свободного пространства вдвое
Все эти разговоры об удобстве и преимуществах когерентности кэша — это, конечно, здорово, но мы не учли очень важный фактор:
При этом всегда используется только половина нашего пространства распределения. Остальная часть просто лежит на месте мёртвой, ничего не делая. От такого объёма пространства страшно просто так отказываться — обычно, когда мы говорим о лишних тратах или потенциально неиспользуемом пространстве, это небольшие блоки, а не сразу огромное снижение размеров.
▍ Минус: невозможно выполнять дополнительную работу с каждым удалённым объектом?
Тоже довольно странный аспект: одно из самых важных преимуществ bump-распределителей одновременно является и их слабым местом — мы удаляем всю неиспользуемую память одной командой. Для маленького мутатора, с которым мы работаем, это идеальная ситуация, но если бы мы работали на C++ и эти объекты имели нетривиальные деструкторы, или если бы мы реализовывали язык с финализаторами, то потеряли бы все эти объекты, для которых могло бы потребоваться выполнение дополнительного кода, и нам бы пришлось добавить некий механизм, чтобы находить и обрабатывать все объекты, которые должны быть уничтожены.
▍ Минус: указатели на объекты нестабильны, и нам нужно патчить корневые объекты
Многим языкам программирования требуется способность реализации кода, не обрабатываемого в рамках системы сборки мусора, например, расширений C в CPython. В схемах Mark&Sweep (или, в случае CPython, гибридной схеме reference-counting/sweep) обрабатываемые сборщиком мусора указатели на объекты стабильны до своего освобождения, поэтому можно расширить систему, приказав сборщику мусора обрабатывать такие объекты как корни и не отменять их распределение, пока они не будут помечены, как не являющиеся корнями. Но в системе, перемещающей объект, нам нужно изменять все указатели на старые объекты так, чтобы они указывали на их эвакуированные копии, а это существенно усложняет API языка.
Заключение
Собственно, вот и всё о копирующем сборщике! Почти как и исходный проект, он был довольно тривиальным, а реализация его в продакшене, вероятно, выявит огромное количество узких мест и потенциальных проблем, но это совершенно точно не какая-то бесполезная игрушка — когда-то его исследования были передовыми! И его версии используются в продакшене, например, в среде исполнения Android.
Telegram-канал со скидками, розыгрышами призов и новостями IT 💻
