Major GC: mark, sweep, compact

Почему old space нужен другой сборщик

Копирующему Scavenger’у нужна вторая область размером с живое множество, куда копировать; это нормально для нескольких мегабайт молодых объектов, но невозможно для old generation в гигабайт. Поэтому old space использует mark-sweep-compact (MSC): найти живые объекты на месте (mark), освободить мёртвые на месте (sweep) и лишь изредка переместить выживших, чтобы бороться с фрагментацией (compact). Major GC трассирует весь достижимый граф, а не маленькую область, поэтому его стоимость принципиально больше — и поэтому V8 столь усиленно вкладывается в сокрытие этой стоимости.

Разметка: трёхцветная абстракция

Разметка — это обход графа с приёмом, делающим его паузируемым. Каждый объект концептуально один из трёх цветов (хранится в двух mark-битах):

• white (белый) — ещё не достигнут (предполагается мёртвым);
• grey (серый) — достигнут, но его исходящие ссылки ещё не просканированы (в рабочей очереди / «marking worklist»);
• black (чёрный) — достигнут и полностью просканирован (все его ссылки уже посерены/обработаны).

Алгоритм:

1. Покрасить всё в white. Покрасить прямых референтов корней в grey (положить их в worklist).
2. Извлечь grey-объект, просканировать его ссылки — покрасить каждого белого референта, на которого он указывает, в grey — затем покрасить сам объект в black.
3. Повторять, пока не останется grey-объектов.
4. Каждый всё ещё white объект недостижим → мусор.

Серое множество — это фронт волны, идущей по графу; когда оно истощается, трассировка завершена. Ключевой инвариант, который это поддерживает: чёрный объект никогда не должен указывать напрямую на белый («трёхцветный инвариант»). Если бы это требовалось только для stop-the-world трассировки, было бы тривиально, — но V8 не останавливает мир для разметки, и вот тут становится интересно.

Инкрементальная и конкурентная разметка

Наивный MSC останавливает весь JavaScript, размечает всю кучу, затем возобновляет — пауза stop-the-world в сотни миллисекунд на большой куче. V8 атакует это с двух сторон:

• Incremental marking разбивает трассировку на маленькие шаги, перемежающиеся с исполнением JS. Движок размечает чуть-чуть, запускает JS, размечает ещё чуть-чуть — амортизируя работу, чтобы ни одна пауза не была длинной. Шаги планируются в простой и во время аллокации.
• Concurrent marking идёт дальше: фоновые вспомогательные потоки обходят граф объектов пока главный поток продолжает исполнять JavaScript. Основная масса работы разметки происходит полностью вне главного потока.

Оба создают одну и ту же опасность: главный поток может изменить граф объектов посреди трассировки — записать указатель, которого маркер не видел, — и нарушить трёхцветный инвариант, заставив чёрный объект указать на белый. Тогда маркер завершится, увидит этот белый объект как недостигнутый и ошибочно соберёт живой объект. Решение — write barrier, целиком предмет следующего урока: он перехватывает записи указателей во время разметки и пересеривает затронутый объект, чтобы инвариант держался. Держите эту нить; здесь просто зафиксируйте, что инкрементальная/конкурентная разметка корректна только благодаря write barriers.

После конкурентной разметки короткая финальная атомарная пауза («finalize») пересканирует корни и любые объекты, помеченные барьерами, истощая последнее серое множество. Эта финальная пауза — единицы миллисекунд даже на больших кучах — в этом и выигрыш.

Sweep: освобождаем white в free lists

Когда разметка закончена, каждый белый объект мёртв. Sweep обходит страницы old space и добавляет память, занятую белыми объектами, в free lists по классам размеров — учёт, позволяющий будущим аллокациям old space найти дыру нужного размера. Sweep ничего не двигает; он лишь записывает свободные области. V8 делает sweep конкурентно и лениво: free lists перестраиваются в фоновых потоках, а страница может быть подметена по требованию при первой аллокации, которой нужно место из неё. Поскольку sweep касается мёртвых объектов (на которые нет ссылок), он естественно распараллеливается и в основном вне критического пути.

Compaction: эвакуация для дефрагментации

Один mark-sweep оставляет фрагментацию: живые и мёртвые объекты перемешаны, поэтому со временем old space становится швейцарским сыром — свободных байтов масса, но нет непрерывной дыры, достаточной для большой аллокации. Compaction чинит это эвакуацией (evacuation): выбрать самые фрагментированные страницы, скопировать их живые объекты на свежую плотно упакованную страницу и обновить каждый указатель, ссылавшийся на перемещённые объекты. Это та же машинерия copy-and-forward, что у Scavenger’а, применённая выборочно. Compaction дорогой (он двигает объекты и переписывает указатели), поэтому V8 делает его выборочно — только на страницах, чья фрагментация это оправдывает, а не на всей куче каждый цикл.