HWW Portfolio

Software and Hardware Developer

Управление памятью в SOOT: от reference count к простому сборщику мусора

Оглавление

Введение

Управление памятью — одна из самых сложных тем в проекте. Идеального решения здесь не существует: каждое имеет цену, и вопрос только в том, какую цену ты готов заплатить.

Первоначальная задача звучала скромно: передавать аргументы и данные между исполнением на C++ и исполнением скрипта. Данные должны доходить целыми и невредимыми, по крайней мере в течение какого-то периода времени. Из этого требования выросла целая подсистема, и в этой статье рассказано, как она менялась и почему стала такой, какая она сейчас.

Первые версии

Значения вместо указателей

Сначала для простоты строки передавались по значению, а не по указателю. Сложные структуры не планировалось передавать вообще: только скалярные величины. Но по мере роста проекта от этого пришлось отказаться.

Reference count

Первой версией менеджера памяти стал reference count. Объекты создавались в куче, а ссылка на объект указывала на сами данные. Несколько байт перед данными хранили метаинформацию менеджера: счётчик ссылок и отладочные поля.

Система казалась простой и эффективной, но при росте проекта и тестировании выяснилось, что проблем в ней больше, чем пользы. Виртуальная машина работает со своими регистрами и, конечно, управляет счётчиками. Но такое же управление пришлось бы добавлять во весь остальной код, который так или иначе оперирует с этими указателями. Появлялось всё больше сущностей, которые должны были гарантировать, что счётчик в нужный момент увеличится, а в другой уменьшится. Сложность разрасталась лавинообразно, и от этой схемы я отказалась.

Данные на один кадр

Тогда я начала сначала и сначала зафиксировала соглашение: данные, которые передаются между двумя исполнительными системами, живут недолго и не сохраняются на протяжении нескольких кадров. По этому правилу любые произведённые данные просто удаляются в конце кадра. Это не уборка мусора: сбрасываются все созданные контейнеры во всех пулах. Операция фактически бесплатна, ведь она меняет лишь несколько переменных, отвечающих за наполненность пула.

Но в процессе реализации стало понятно, что это полумера. Долгоживущие данные нужны: например, конечный автомат в скрипте может создать структуру и удерживать её какое-то время. Без этого проект не завершить.

Сборщик мусора

У меня был негативный опыт работы со сборщиками мусора в C# и Unity, поэтому я потратила немало сил, чтобы обойтись без него. Но в итоге в рабочем варианте всё равно появился именно сборщик мусора. Это не самый эффективный способ управления памятью, и реализация далека от самой лучшей или быстрой. Простая реализация в стиле SOOT меня вполне устраивает, а сам сборщик я считаю неизбежным злом, которое пришлось написать.

Как менеджер памяти не зависит от VM

Код виртуальной машины находится на более высоком уровне, чем менеджер памяти. Менеджер не должен знать о VM: иначе получится циклическая зависимость, при которой VM знает о памяти, память знает о VM, и ни одну из частей нельзя собрать или протестировать отдельно.

Чтобы разорвать эту зависимость, я сделала систему дескрипторов типов. Внутри менеджера памяти есть таблица, в которую виртуальная машина регистрирует краткое описание своих типов: какие у них поля, где в структуре лежат указатели и как их обходить. Сборщик мусора читает эту таблицу и обходит структуры, посещая все указатели, при этом не зная, что это за типы и откуда они взялись. В результате менеджер памяти не зависит от VM, а VM не зависит от конкретной реализации сборщика.

Устройство сборщика мусора

Общая схема

SOOT использует неперемещающий mark-and-sweep сборщик. Две особенности отличают его от учебного варианта.

Во-первых, сборщик сам не ищет корни. Корнями считается всё, что VM держит достижимым: регистры, глобальные слоты, стек. В mark-фазе VM обходит их и для каждого вызывает mark_object. Сборщик полагается на то, что VM пометит всё нужное.

Во-вторых, фазы по-разному вписываются в кадр. Маркировка выполняется целиком, пока скрипты не работают (stop-the-world). Sweep можно растянуть на несколько кадров: он идёт с бюджетом и обрабатывает по несколько блоков за вызов.

Объект, помеченный в текущем проходе, остаётся жить. Объект, который за проход никто не пометил, считается мусором и освобождается. Перемещения объектов и компакции нет, указатели на объекты не меняются.

Память: регион и арены

Вся куча — один зарезервированный регион виртуального адресного пространства размером до max_mb. На Linux он создаётся через mmap с флагом MAP_NORESERVE, и физические страницы выделяются при первом обращении. На Windows используется VirtualAlloc: сейчас регион резервируется и сразу коммитится целиком, это место для доработки.

Внутри региона bump-указатель нарезает арены, по умолчанию по 1 МБ. Каждый объект попадает в одну из девяти size-class: 16, 32, 64, 128, 256, 512, 1024, 2048 и 4096 байт. Для каждого класса есть своя арена, а если она заполнилась, создаётся следующая.

Внутри арены все блоки одного размера. Блок выдаётся либо из freelist (освобождённые блоки), либо из bump-области (новые блоки в конце арены). В каждой арене есть bitmap занятости: один бит на блок. Благодаря ему sweep обходит блоки напрямую, без отдельного списка объектов.

Заголовок объекта

Перед данными каждого объекта лежит GCHeader: 8 байт, или 16, если включено отладочное имя.

Заголовок учитывается при выборе класса. Размер блока считается так: заголовок плюс данные, округлённые вверх до 16 байт, затем подбирается класс. Максимальный объект вместе с заголовком не может превышать 4096 байт.

Номер прохода вместо сброса меток

Главная особенность схемы: «живой» означает «помеченный в текущем проходе», а не «имеющий поднятый флаг». Каждый проход получает номер от 1 до 15 (0 пропускается), и pass_cycle в заголовке хранит номер последнего прохода, в котором объект был помечен.

Благодаря этому не нужно перед началом прохода сбрасывать метки у всех объектов. Новый номер сам делает все старые метки недействительными. Пятнадцати значений достаточно, потому что каждый проход доводится до конца sweep, и номер должен отличаться лишь от предыдущего.

Типы

TypeRegistry хранит для каждого типа размер, выравнивание, список указательных полей (PtrField: type_index, offset, array_count) и два делегата:

Индекс 0 зарезервирован как sentinel: «нетипизированный блок». Такие блоки сборщик не сканирует.

Один проход сборки

Схематично порядок такой:

gc::start_pass();            // новый номер прохода, сброс курсора sweep
// VM обходит корни и для каждого вызывает gc::mark_object(...)
while (!gc::sweep_pass(64)) {
    // отдаём управление кадру и продолжаем в следующий раз
}
gc::finish_pass();

Mark

mark_object(payload):

Делегат обходит указатели внутри объекта и для каждого вызывает всё тот же mark_object через небольшой trampoline. Благодаря этому вложенные структуры обходятся тем же кодом, а циклические ссылки не приводят к зацикливанию: повторный заход в уже помеченный объект сразу возвращается.

Sweep

sweep_pass(budget) обходит арены и блоки с бюджетом, то есть за вызов обрабатывает ограниченное число занятых блоков и возвращает false, пока работа не закончена. Для каждого занятого блока:

Бюджет нужен, чтобы sweep не блокировал игру надолго. Функция collect() крутит sweep_pass с огромным бюджетом до завершения. Корни она не обходит, поэтому годится только там, где всё нужное уже помечено или где допустимо освободить всё остальное.

Объекты, выделенные во время sweep

Новый объект получает в заголовок номер текущего прохода. Поэтому sweep, который идёт в этот момент, его не тронет: объект считается живым в текущем проходе. Это упрощает инкрементальный sweep: между вызовами скрипты могут выделять память, и новые объекты не пропадут. В следующем проходе такой объект будет освобождён, если его никто не пометит.

Из этого следует правило для mark-фазы: пока она идёт, скрипты не выполняются. Новый объект с текущим номером считался бы уже помеченным, и mark_object не обошёл бы его указатели.

DArray<T> и нетипизированные блоки

DArray<T> — динамический массив в куче. Буфер выделяется через gc::alloc(/*sid=*/0, ...), то есть как нетипизированный блок, который сборщик не сканирует.

Сам буфер тоже живёт по общим правилам. Если никто не пометил его в проходе, sweep его освободит, поэтому тот, кто владеет массивом, обязан пометить буфер в своём делегате mark.

Инспекция

for_each_live обходит все живые объекты кучи и вызывает посетителя с типом, указателем и размером. Им пользуются инспектор gcls и отладка.

Как отличить управляемый указатель от неуправляемого

Время от времени коду нужно понять, на что указывает указатель: на объект, которым управляет сборщик мусора, или на какие-то посторонние данные. В SOOT это решается просто. Все арены лежат в одном непрерывном регионе с известными началом и концом, а небольшая функция-предикат is_in_heap проверяет, попадает ли указатель в этот диапазон. Этого достаточно, чтобы ответить на вопрос.

Есть одно условие. Проверка отвечает только «адрес внутри региона». Чтобы заголовок читался правильно, указатель должен указывать именно на начало данных объекта, а не на его внутреннее поле.

Ограничения

Что можно улучшить

Специализированные пулы для векторов и кватернионов. Это самые частые структуры, и сейчас для них заголовок обходится дорого. Вектор из 16 байт плюс заголовок в 8 байт даёт 24 байта, но размеры округляются до 16 и затем до класса, поэтому вектор занимает блок класса 32. Накладные расходы составляют 100%. Если хранить такие объекты в отдельном пуле, где блок состоит только из данных, а тип известен по самому пулу, вектор будет занимать 16 байт, то есть вдвое меньше. Заодно исчезнут поиск size-class и запись заголовка. Это не переписывание сборщика, а добавление одного-двух специализированных пулов рядом с общим.

Явный стек маркировки вместо рекурсии избавил бы от риска переполнения системного стека.

Крупные объекты. Отдельный путь для блоков больше 4 КБ убрал бы ограничение на размер, в частности для DArray.

Быстрый поиск арены и выделение из любой арены класса снизили бы стоимость освобождения и фрагментацию. Поиск арены можно заменить, например, делением адреса на размер арены (арены одинакового размера лежат в регионе подряд).

Итог

Сборщик мусора в SOOT не претендует на эффективность. Он неперемещающий, без компакции, без параллельности, и поколений в классическом смысле в нём нет, хотя номер прохода в заголовке даёт что-то похожее на возраст. Зато он простой, предсказуемый и достаточный для задач, которые стоят перед языком: игровой код, где большинство данных живёт один кадр, а долгоживущие структуры встречаются редко и их немного.

Как и в остальных частях проекта, здесь выбран простой вариант там, где сложный не оправдан. Ограничения известны и записаны, а пути их преодоления понятны.

Статус проекта