Привет! Эту статью я задумал довольно давно. Речь в ней пойдет о простейшем копирующем сборщике мусора на С++. У него довольно много ограничений (часть не мешает, часть можно обойти, если задаться целью написать какую-то серьезную библиотеку, а для кое-чего неплохо было бы заиметь зачаточную поддержку от языка), зато и кода в нем чуть больше 100 строк. Заинтересовавшихся прошу под кат. Там минимум ООП, простейшие шаблоны и жуткие магические ритуалы с указателями.
Начнем с начала. Что такое сборщик мусора и для чего он нужен?
Сборщик мусора (Gargabe Collector, GC) — это такой способ управления ресурсами, обычно — оперативной памятью, выделяемой в куче. Суть проста — программист просит сборщик мусора выделить ему кусок памяти, а тот уже сам определяет, когда он станет не нужен и может быть освобожден. Это решает большинство проблем с утечками памяти, хотя и лишает возможности героически превознемогать ошибки сегментации. Какая жалость.
Сборщики мусора бывают двух видов — консервативные и копирующие.
Нечто вроде первого типа реализовано в последнем стандарте. Механизм shared_ptr позволяет отказаться от явного использования операторов new и delete. Он считает ссылки, которые указывают на объект и избавляется от него, когда их число становится нулевым. Проблемы с этим подходом возникают, когда создается множество мелких объектов с коротким, но не одинаковым сроком жизни. В результате, куча превращается в кровавое месиво из валидных объектов и лоскутков свободной памяти по несколько десятков байт. Из-за этого создание новых объектов начинает занимать целую вечность и нативный код начинает завидовать Питону.
Для решения этой проблемы — фрагментации кучи – придуман второй тип сборщиков — копирующий. До поры до времени, его стратегия борьбы с мусором — созерцание. Когда же его становится слишком много, он делает следующее:
1. Копирует все нужные данные в другую область памяти.
2. Меняет все указатели на актуальные.
3. Освобождает всю память, которая уже не используется.
Сразу уточню, что я не смотрел вплотную ни одного алгоритма сборки мусора, ни как работают «взрослые» библиотеки GC для С++. Вероятно, у алгоритма, который я сейчас опишу, есть название, возможно, именное, но в тут я обойдусь без ссылок на источники.
Чтобы определить объекты, которые еще нужны программе, предлагаю рассматривать память как обычный граф. Тогда «живыми» объектами после сборки мусора будут считаться те, которые достижимы через цепочку указателей. Здесь возникают вопросы. Во-первых — как для любого возможного объекта, который программист может попросить создать, определить, где у него находятся указатели. Первый способ — с помощью шаблонной магии для каждого класса объектов создавать свой собственный аллокатор. Ужасная идея по многим причинам. Второй — в заголовке каждого объекта писать всю информацию, которая нужна для работы GC (ах да, для классов с виртуальными функциями эта реализация не годится. Пара идей у меня есть, при необходимости).
Заголовок тоже можно использовать многими способами. Мой — самый простой, который вообще может быть (для реализации, но не использования). Во-первых, каждый объект, который планирует создаваться через сборщик мусора, должен иметь в начале своего определения эту структурку:
enum { STRUCT_SZ = 0, REF_COUNT = 1 };
struct gcHeader {
union {
int gcData[2];
gcHeader* post_gcAddress;
};
};
Во-вторых, сразу после заголовка, и нигде более, должны идти все указатели, которые также относятся к сборщику мусора. Соответственно, в gcData[REF_COUNT] будет хранится их количество. Это одно из ограничений, которое накладывает моя реализация. В gcData[STRUCT_SZ] будет храниться размер структуры в байтах. Назначение указателя я раскрою позднее. Что удобно, размер структуры оказался равен размеру указателя (сейчас 2014, народ!).
Отлично, теперь мы сможем обойти всю нашу память. Вопрос в том, откуда начать обход. Единственная область памяти, которая нам стопроцентно доступна в любой момент — это стек. Проблема та же, что и с указателями в структурах — мы понятия не имеем, какая кучка байт указывает на объект GC. Поэтому, нужно расположение каждого такого указателя записывать явно.
vector<gcHeader**> referencesStack;
template <class T>
class stackRef {
public:
T* ref;
stackRef(){
ref = nullptr;
referencesStack.push_back(reinterpret_cast<gcHeader**>(&ref));
}
~stackRef(){
referencesStack.pop_back();
}
};
Класс stackRef действует просто. При инициализации, он всего-лишь добавляет свой адрес в стек ссылок. Деструктор, соответственно, удаляет неактуальный адрес из того же стека. Работа стека вызовов и конструкторов с деструкторами синхронизирована, так что аномалий возникать не будет.
В классе нужно переопределить кучу операторов — разыменования, присваивания, etc, но этим появится смысл заниматься не раньше, чем со мной свяжутся парни из Boost Foundation.
Вспомогательные структуры готовы. Можно перейти к выделению памяти.
Классной фичей такого способа управления ресурсами является именно способ их выделения. Стандартному аллокатору С++ приходится после каждого delete обновлять списки свободных блоков, а после new находить среди блоков подходящий, потом дробить его на два мелких блока, а потом что-то еще, что там делают современные аллокаторы. В случае сборщика мусора, операция delete просто не нужна, так что вся занятая память будет идти одним сплошным блоком. Чтобы создать новый объект, нужно всего лишь увеличить размер этого блока, т. е. сдвинуть один указатель. Простая операция, которая выполняется за O(1). Реально перестало это казаться такой уж замечательной идеей, из-за того, что провоцирует кучу сборок тогда, когда можно было бы просто переиспользовать уже не нужную память, но пока можно остановиться на этом.
Разделим память, подконтрольную сборщику мусора на куски по 4 килобайта и свяжем их в список. На самом деле, чуть больше 4 килобайт, но это вопрос моей лени.
const int CHUNK_SIZE = 4096;
const int OVERDRAFT = 128;
const int ACTUAL_SIZE = CHUNK_SIZE + OVERDRAFT; //Я только что сэкономил себе минут 15 на отладку, если где-то ошибусь в арифметике.
struct gcChunk {
gcChunk* next;
char data[ACTUAL_SIZE];//Эта память и будет выдаваться программе.
};
gcChunk* firstChunk;
gcChunk* currentChunk;
int chunkCount;
int currentOffset;
firstChunk — начало списка, currentChunk — последний созданный блок памяти. сurrentOffset — начало свободного сегмента памяти относительно currentChunk.
gcHeader* gcRawAlloc(int size, int refCount){
if (size > CHUNK_SIZE)// Ради proof of concept, уметь создавать большие объекты необязательно
return nullptr;
if (currentOffset + size > CHUNK_SIZE){ // Было бы правильнее использовать list<gcChunk> из STL, но мне показалось, что лучше будет явно показать весь процесс.
++chunkCount;
currentChunk->next = new gcChunk();
currentChunk = currentChunk->next;
currentChunk->next = nullptr;
currentOffset = 0;
}
gcHeader* new_obj = reinterpret_cast<gcHeader*>(&(currentChunk->data[currentOffset]));
new_obj->gcData[STRUCT_SZ] = size;
new_obj->gcData[REF_COUNT] = (refCount << 1)| 1;
currentOffset += size;
if (currentOffset % 4)//выравнивание по 4 байтам. Скорее всего, условие не сработает никогда, т.к. компилятор сам будет дополнять все структуры до нужного размера.
currentOffset += 4 - currentOffset % 4;
return new_obj;//Возвращается сырой указатель Если сборка мусора начнется до того, как этот указатель будет скопирован куда надо, всё закончится плохо — появится висящая ссылка.
}
Здесь неочевидных моментов уже больше. Разберем 12-ую строчку.
На этом этапе нам удобнее не думать о том, какой именно тип у нового объекта. Мы точно знаем, что у него есть наш gcHeader, и этого пока достаточно.
После того, как мы выделили память для нового объекта, нужно инициализировать его заголовок. Что может означать загадочное присваивание
temp->gcData[REF_COUNT] = (refCount << 1)| 1;
?
Для этого снова посмотрим на определение заголовка
struct gcHeader {
union {
int gcData[2];
gcHeader* post_gcAddress;
};
};
Ключевое слово union означает, что и массив gcData и указатель post_gcAddress располагаются по одному адресу. Это полезно для экономии памяти, но проблема в том, что С++ не запоминает, как данные в union использовались в последний раз — как массив, или как ссылка. Помогает такая особенность архитектур процессоров, как необходимость выравнивания данных.
Если вкратце, то любые переменные длиннее одного байта, должны располагаться на адресах, которые кратны машинному слову в байтах. Нарушение выравнивания на современных процессорах сильно замедляет работу программы, а старые ARM вообще отказываются в таких условиях работать. В результате, 2 или 3 младших бита указателя могут быть использованы как угодно по усмотрению программиста. Например, при реализации красно-черных деревьев, последний бит часто задействуют вместо булевой переменной.
Тут — то же самое. Если младший бит равен единице, то эти восемь байт — гарантированно массив из двух int. Можно, например, использовать еще один бит, чтобы указывать сборщику мусора, что-то типа «это ссылка на полиморфный объект, у него есть указатель vtable, не затри его».
Ну и небольшая обертка над функцией, чтобы использование аллокатора не вызывало особой боли.
template <class T>
T* gcAlloc(){
return reinterpret_cast<T*>(gcRawAlloc(sizeof(T), T::refCount));
}
Тут следует поставить emplace new, чтобы корректно инициализировались объекты с конструкторами. Как видно, класс объекта, который мы хотим создать, должен иметь статическую константу refCount. Её можно вычислять автоматически с помощью внешнего препроцессора. В противном случае, я вижу тут как минимум три способа отстрелить себе ногу.
Перед тем, как пользоваться этой функцией, нужно инициализировать кучу.
void gcInit(){
firstChunk = currentChunk = new gcChunk;
firstChunk->next = nullptr;
currentOffset = 0;
chunkCount = 1;
}
Пора посмотреть на реализацию самой сборки мусора.
Первая функция, gcCollect, должна начать кучу с чистого листа, не забыв сохранить указатели на старый список. Эти строки почти повторяют инициализацию.
void gcCollect(){
//execvp("rm", "cppgc.cpp");//Без этой строки алгоритм просто нельзя назвать корректным.
gcChunk* newFirstChunk = currentChunk = new gcChunk;
currentChunk->next = nullptr;
currentOffset = 0;
chunkCount = 1;
Далее, мы с каждого указателя, который хранится на стеке, начинаем процесс сборки.
for (auto i = referencesStack.begin();i != referencesStack.end(); ++i )
gcMove(*i);
А теперь просто освобождаем ненужную память.
//Сборка завершена, достижимые данные перемещены в другую область памяти, старые можно безболезненно удалить
gcChunk iter = firstChunk;
firstChunk = newFirstChunk;
while (iter != nullptr){
gcChunk* t = iter->next;
delete[] iter;
iter = t;
}
}
Обратите внимание, delete вызывается только для больших блоков памяти. Таким образом, деструкторы объектов в сборщике мусора никогда не будут вызваны. Это не проблема для классов, у которых деструкторы только освобождают память, но нет возможности, например, автоматически закрывать соединения и файловые дескрипторы. Mark & Sweep-алгоритмы могут помочь с этим, но и писать их сильно сложнее.
Последний штрих — функция gcMove.
bool isPointer(gcHeader a){
return (a.gcData[REF_COUNT] & 1) == 0;
}
void gcMove(gcHeader** current){
if (*current == nullptr)
return;
if (isPointer(**current)){//Ссылка на уже перемещенный объект. Перенаправляем куда надо, и дело с концом.
(*current) = (*current)->post_gcAddress;
return;
}
gcHeader* new_obj = gcRawAlloc((*current)->gcData[STRUCT_SZ], (*current)->gcData[REF_COUNT]);
memcpy(new_obj, (*current), sizeof(char) * (*current)->gcData[STRUCT_SZ]);
gcHeader** iterator = reinterpret_cast<gcHeader**>(new_obj) + 1;
(*current)->post_gcAddress = new_obj;
(*current) = new_obj;
int refCount = new_obj->gcData[REF_COUNT] >> 1;
for (int i = 0; i < refCount; ++i, ++iterator)
gcMove(iterator);
}
Разберем функцию с середины. Нам нужна возможность перенаправлять ссылки, поэтому в функцию передается указатель на указатель на данные.
GC выделяет объекту нужное количество памяти в новой куче (он знает, сколько, из заголовка) и копирует все данные из старой инкарнации в новую. Потом он пишет новый адрес объекта в старый заголовок. Теперь, если на объект указывает несколько ссылок, алгоритм сможет определить, что объект уже один раз перемещался (младший бит, гарантированно, 0) и не станет копировать его лишний раз впоследствии. Осталось перенаправить старый указатель на новую копию объекта.
Теперь, нужно разобраться с указателями, самого объекта. С ними нужно сделать то же самое. Строчка
gcHeader** iterator = reinterpret_cast<gcHeader**>(temp) + 1;
получает указатель на первую ссылку в структуре (если она есть, конечно). Помним, что sizeof(gcHeader) == sizeof(void*). В противном случае, это будет занимать на пару строк больше.
Что делать дальше, вопрос уже спорный. Я просто для каждого указателя рекурсивно вызываю функцию gcMove. Такой алгоритм соответствует обходу графа в глубину. Однако, это не лучший выбор.
Киллер-фича копирующих сборщиков мусора для меня — это возможность поддерживать локальность по ссылкам. Если коротко, объекты, которые ссылаются друг на друга, и в памяти тоже должны находиться как можно ближе. Так процессор сможет эффективнее использовать свою кэш-память.
Мой GC такого не умеет. Я выбрал обход в глубину из-за простоты. Желательно перемещать объекты в порядке обхода в ширину. Будет совсем здорово заморочиться и выстраивать объекты в памяти в соответствии со статистикой обращений к ним, как в этом алгоритме, чтобы добиться оптимального количества промахов.
На этом всё. Осталось продемонстрировать работу со сборщиком.
В качестве примера возьму простейшее дерево поиска.
struct searchTree {
gcHeader gc;
searchTree* left;
searchTree* right;
int key;
static const int refCount = 2;
};
Как уже упоминалось, в начале должен стоять заголовок, а после заголовка все указатели на объекты нашей кучи.
void stAdd(searchTree* &target, int key){
if (target == nullptr){
target = gcAlloc<searchTree>();
target->left = target->right = nullptr;
target->key = key;
return;
}
if (target->key == key)
return;
if (target->key < key)
stAdd(target->left, key);
else
stAdd(target->right, key);
}
Обычное добавление в дерево. Обратите внимание, как используется gcAlloc.
searchTree* stFind(searchTree* target, int key){
if (target == nullptr || target->key == key)
return target;
if (target->key < key)
return stFind(target->left, key);
else
return stFind(target->right, key);
}
void stPrint(searchTree* t, int indent = 0){
if (t == nullptr)
return;
for (int i = 0; i < indent; ++i)
cout << " ";
cout << t << ' ' << t->key << endl;
stPrint(t->left, indent + 1);
stPrint(t->right, indent + 1);
}
void stCut(searchTree* &target, int key){
if (target == nullptr || target->key == key){
target = nullptr;
return;
}
if (target->key < key)
stCut(target->left, key);
else
stCut(target->right, key);
}
stFind возвращает ссылку на поддерево с нужным ключом, stPrint распечатывает ключи и адреса поддеревьев, stCut обрезает поддерево, в котором хранится искомый ключ.
Наконец, main.
int main(){
gcInit();
stackRef<searchTree> root;
stAdd(root.ref, 2);
stAdd(root.ref, 1);
stAdd(root.ref, 3);
stAdd(root.ref, 6);
stAdd(root.ref, 5);
stAdd(root.ref, 4);
stAdd(root.ref, 8);
stackRef<searchTree> additionalRef;
additionalRef.ref = stFind(root.ref, 3);
cout << "Before GC" << endl;
cout << additionalRef.ref << ' ' << currentOffset << endl <<endl;
stPrint(root.ref);
cout << endl;
gcCollect();
cout << "After GC" << endl;
cout << additionalRef.ref << ' ' << currentOffset << endl << endl;
stPrint(root.ref);
cout << endl;
stCut(root.ref, 5);
gcCollect();
cout << "Deleted some elements and GC'd." << endl;
cout << additionalRef.ref << ' ' << currentOffset << endl << endl;
stPrint(root.ref);
return 0;
}
Before GC
0xd92058 224
0xd92018 2
0xd92058 3
0xd92078 6
0xd920d8 8
0xd92098 5
0xd920b8 4
0xd92038 1
After GC
0xd93108 224
0xd930e8 2
0xd93108 3
0xd93128 6
0xd93148 8
0xd93168 5
0xd93188 4
0xd931a8 1
Deleted some elements and GC'd.
0xd92038 160
0xd92018 2
0xd92038 3
0xd92058 6
0xd92078 8
0xd92098 1
Как видно работа со структурами для программиста особо не меняется. Что тут происходит:
1. Мы произвольно заполняем дерево поиска.
2. Создаем еще одну стековую ссылку на один из элементов, чтобы проверить, как GC реагирует на множественные ссылки на один объект.
3. Распечатываем дерево, additionalReference и currentOffset.
4. Вхолостую вызываем сборку мусора.
5. Снова распечатываем дерево. Все указатели, которые нужны — поменялись.
6. Обрезаем одно поддерево и снова вызываем сборку мусора. Всё снова работает как надо. Обратите внимание currentOffset уменьшился, а корень дерева вернулся на тот же адрес, по которому находился в первый раз.
Выводы
Итак, в С++ можно использовать Garbage Collector. Причем, вполне себе симпатичный, на мой замыленный взгляд, да еще и с минимальным оверхедом. Попробую перечислить всё, что нужно сделать, чтобы он был действительно удобным и полезным.
Сначала — организационные моменты.
1. Глобальные переменные — это, конечно, совсем не клёво. Нужно всё оформить как человеческий класс иили аллокатор С++.
2. Заставлять в каждый класс вставлять хедер — почти садизм. Нужно просто давать отнаследоваться от абстрактного класса, у которого должны быть два метода — getSize и getLayout. Последний должен возвращать ссылку на массив, в котором хранятся относительные координаты всех указателей (затея с «все ссылки стоят начале» ну совсем не годится для чего-то серьезного). Этот массив однозначно должен заполняться автоматически, но я пока что не представляю, как это можно реализовать.
Следующий вопрос — автоматическая сборка. Когда выдвинули саму идею GC, никто не подразумевал, что кто-то реально будет постоянно вызывать что-то вроде функции gcCollect, всё должно происходить само по себе. Но С++ — особый случай. Он славится тем, что весь поток выполнения под носом, или, по крайней мере, предсказуем. Своенравный Garbage Collector любого другого языка здесь — это практически идеологическое преступление. Так что, у него должно быть как минимум два режима:
1. Прозрачный.
2. Бросок исключения после исчерпания некой квоты памяти. Тут уже программисту решать — убраться или выделить память форсированно.
И еще один вопрос. Многопоточность. Тут всё плохо. Чтобы начать сборку мусора, нужно приостановить все потоки, чтобы ничего не сломать. В итоге придется написать половину JVM. Самым лучшим решением мне кажется его отсутствие. Для каждого потока можно просто создавать свой выделенный GC, а если понадобится передать что-то другому подпроцессу, то обычные shared_ptr никто не отменял. Без разделяемой памяти жить, как правило, гораздо веселее.
Закончим на печальной ноте. Такой сборщик мусора тотально несовместим ни с одной готовой библиотекой. Их объекты не смогут предоставлять необходимые данные. Несмотря на то, что std::list, std::map и std::set только выиграют, если переписать их специально под GC, переделывать N гигабайт исходников Boost, например, совершенно бесперспективно. Однако, для борьбы с фрагментацией в случае маленьких объектов, мне такая штука кажется очень даже полезной.
Скачать и поиграться можно отсюда.
Автор: Salabar
