Поиск корней для сборки мусора в C
Я пытаюсь реализовать простой сборщик мусора и метки в C. Первым шагом алгоритма является поиск корней. Итак, мой вопрос: как мне найти корни в программе на C?
В программах, использующих malloc, я буду использовать пользовательский распределитель. Этот пользовательский распределитель - это все, что будет вызываться из программы на C, и может быть пользовательским init().
Как сборщик мусора знает, что все указатели (корни) находятся в программе? Кроме того, учитывая указатель пользовательского типа, как он получает все указатели внутри этого?
Например, если есть указатель p, указывающий на список классов, в котором есть другой указатель.. скажем, q. Как сборщик мусора знает об этом, чтобы он мог пометить его?
Обновление: как насчет того, чтобы отправить все имена и типы указателей в GC при его инициализации? Точно так же структура различных типов также может быть отправлена так, что GC может пройти по дереву. Это даже вменяемая идея или я просто схожу с ума?
2 ответа
Прежде всего, сборщики мусора в C, без обширной поддержки компилятора и ОС, должны быть консервативными, потому что вы не можете различить допустимый указатель и целое число, которое, как оказалось, имеет значение, похожее на указатель. И даже консервативные сборщики мусора трудно реализовать. Мол, очень тяжело. И часто вам нужно будет ограничить язык, чтобы получить что-то приемлемое: например, может быть невозможно правильно собрать память, если указатели скрыты или запутаны. Если вы выделите 100 байтов и сохраните указатель только на десятый байт распределения, ваш GC вряд ли поймет, что вам все еще нужен блок, так как он не увидит ссылки на начало. Другим очень важным ограничением для контроля является выравнивание памяти: если указатели могут быть на невыровненной памяти, ваш сборщик может быть замедлен в 10 раз или хуже.
Чтобы найти корни, вам нужно знать, где начинаются ваши стеки и где заканчиваются ваши стеки. Обратите внимание на форму множественного числа: каждый поток имеет свой собственный стек, и вам может потребоваться учитывать это в зависимости от ваших целей. Чтобы узнать, где начинается стек, не вдаваясь в подробности, относящиеся к платформе (что я, вероятно, не смог бы предоставить в любом случае), вы можете использовать ассемблерный код внутри основной функции текущего потока (просто main в непотоковом исполняемом файле), чтобы запросить регистр стека (esp на х86, rsp на x86_64 назвать только эти два). Gcc и clang поддерживают расширение языка, которое позволяет вам постоянно присваивать переменную регистру, что должно упростить вам задачу:
register void* stack asm("esp"); // replace esp with the name of your stack reg
(register это стандартное ключевое слово языка, которое в большинстве случаев игнорируется современными компиляторами, но в сочетании с asm("register_name"), это позволяет вам делать некоторые неприятные вещи.)
Чтобы вы не забыли важные корни, вам следует отложить реальную работу main функция к другому. (На платформах x86 вы также можете запросить ebp/rbpбазовые указатели стекового фрейма, вместо этого, и все еще выполняют вашу реальную работу в основной функции.)
int main(int argc, const char** argv, const char** envp)
{
register void* stack asm("esp");
// put stack somewhere
return do_main(argc, argv, envp);
}
После того, как вы введете GC для сбора, вам нужно запросить текущий указатель стека для прерванного потока. Для этого вам потребуются вызовы, связанные с дизайном и / или платформой (хотя, если вы получите что-то для выполнения в том же потоке, описанный выше метод все равно будет работать).
Настоящая охота на корни начинается сейчас. Хорошая новость: большинство ABI требуют, чтобы стековые кадры были выровнены по границе, превышающей размер указателя, а это означает, что если вы доверяете каждому указателю в выровненной памяти, вы можете рассматривать весь свой стек как intptr_t* и проверьте, выглядит ли какой-либо шаблон внутри любого из ваших управляемых указателей.
Очевидно, есть и другие корни. Глобальные переменные могут (теоретически) быть корнями, а поля внутри структур тоже могут быть корнями. Регистры также могут иметь указатели на объекты. Вы должны отдельно учитывать глобальные переменные, которые могут быть корнями (или вообще запрещать это, что, на мой взгляд, неплохая идея), потому что автоматическое обнаружение их будет трудным (по крайней мере, я бы не знал, как это сделать на любой платформе).
Эти корни могут привести к ссылкам в куче, где все может пойти не так, если вы не позаботитесь.
Поскольку не все платформы предоставляют malloc Самоанализ (насколько я знаю) требует реализации сканированной памяти, то есть памяти, о которой знает ваш GC. Нужно знать хотя бы адрес и размер каждого такого распределения. Когда вы получаете ссылку на один из них, вы просто сканируете их на наличие указателей, так же, как вы делали для стека. (Это означает, что вы должны позаботиться о том, чтобы ваши указатели были выровнены. Обычно это происходит, если вы позволяете компилятору выполнять свою работу, но вам все же нужно быть осторожным при использовании сторонних API).
Это также означает, что вы не можете помещать ссылки на собираемую память в места, где GC не может достичь ее. И именно здесь это причиняет боль больше всего, и где вы должны быть очень осторожны. В противном случае, если ваша платформа поддерживает malloc самоанализ, вы можете легко определить размер каждого выделения, на которое вы получаете указатель, и убедиться, что вы не переполняете его.
Это просто царапает поверхность темы. Сборщики мусора чрезвычайно сложны, даже если они однопоточные. Когда вы добавляете темы в микс, вы попадаете в новый мир боли.
Apple внедрила такой консервативный GC для языка Objective-C и окрестила его libauto. Они открыли его, наряду с хорошей частью низкоуровневых технологий Mac OS X, и вы можете найти источник здесь.
Я могу только процитировать Hot Licks здесь: удачи!
Хорошо, прежде чем идти дальше, я забыл кое-что очень важное: оптимизация компилятора может сломать GC. Если ваш компилятор не знает о вашем GC, он вполне может никогда не помещать определенные корни в стек (имея дело только с ними в регистрах), и вы пропустите их. Это не слишком проблематично для однопоточных программ, если вы можете просматривать регистры, но, опять же, огромный беспорядок для многопоточных программ.
Также будьте очень осторожны с прерываемостью выделения: вы должны убедиться, что ваш GC не может сработать, пока вы возвращаете новый указатель, потому что он может собрать его непосредственно перед тем, как он будет назначен корню, и когда ваша программа возобновит свое назначение этот новый висячий указатель на вашу программу.
А вот обновление для исправления:
Обновление: как насчет того, чтобы отправить все имена и типы указателей в GC при его инициализации? Точно так же структура различных типов также может быть отправлена так, что GC может пройти по дереву. Это даже вменяемая идея или я просто схожу с ума?
Я думаю, вы могли бы выделить нашу память, а затем зарегистрировать ее в GC, чтобы сказать, что это должен быть управляемый ресурс. Это решило бы проблему прерывистости. Но тогда будьте осторожны с тем, что вы отправляете сторонним библиотекам, потому что, если они сохранят ссылку на него, ваш GC может не обнаружить его, так как они не зарегистрируют свои структуры данных в вашем GC.
И вы, вероятно, не сможете сделать это с корнями в стеке.
Корни в основном все статические и автоматические указатели объектов. Статические указатели будут связаны внутри модулей нагрузки. Автоматические указатели должны быть найдены путем сканирования кадров стека. Конечно, вы понятия не имеете, где в кадрах стека находятся автоматические указатели.
Когда у вас есть корни, вам нужно сканировать объекты и находить все указатели внутри них. (Это будет включать в себя массивы указателей.) Для этого вам необходимо идентифицировать объект класса и каким-то образом извлечь из него информацию о расположении указателей. Конечно, в C многие объекты не являются виртуальными и не имеют указателя класса внутри них.
Удачи!!
Добавлено: Одна из техник, которая может сделать ваш квест неопределенным, - это "консервативный" сбор мусора. Поскольку вы намереваетесь иметь свой собственный распределитель, вы можете (каким-то образом) отслеживать размеры и местоположения выделения, чтобы вы могли выбрать любой блок размером с указатель из хранилища и спросить: "Может ли это быть указателем на один из моих объектов?" Конечно, вы никогда не узнаете наверняка, поскольку случайные данные могут "выглядеть" как указатель на один из ваших объектов, но все же вы можете с помощью этого механизма сканировать кусок памяти (например, кадр в стеке вызовов, или отдельный объект) и определить все возможные объекты, к которым он может обратиться.
С консервативным сборщиком вы не можете безопасно выполнять перемещение / сжатие объектов (когда вы изменяете указатели на объекты по мере их перемещения), поскольку вы можете случайно изменить "случайные" данные, которые выглядят как указатель объекта, но на самом деле являются значимыми данными для некоторого приложения. Но вы можете идентифицировать неиспользуемые объекты и освободить место, которое они занимают для повторного использования. При правильном дизайне можно получить очень эффективный некомпактный ГХ.
(Тем не менее, если ваша версия C допускает, что сканирование невыровненных указателей может быть очень медленным, так как вам придется попробовать все варианты выравнивания байтов.)