Сборка мусора без unsafe-кода

Ник Фицджеральд, работающий над Wasmtime и Cranelift, написал небольшую GC-библиотеку для Rust под названием safe-gc, а затем подробно описал, почему в ней нет unsafe - ни в публичном API, ни во внутренностях. Этот материал интересен даже не столько как руководство по GC, сколько как наглядный пример того, как форма API позволяет вытеснить целые категории багов за пределы достижимого пространства состояний.

Главный трюк: индексировать, а не разыменовывать

Большинство библиотек сборки мусора для Rust предоставляют нечто вроде Gc<T>, у которого можно вызвать .deref(). Именно там всегда и прячется unsafe: возврат &T из указателя, время жизни которого borrow checker не видит, вынуждает библиотеку заявлять время жизни, непроверяемое компилятором.

safe-gc обходит это ограничение. Gc<T> здесь не является разыменовываемым указателем. Чтобы прочитать объект, вы индексируете кучу:

let value = &heap[&gc_ref];

Теперь borrow checker видит совершенно обычную реализацию Index для совершенно обычной структуры. Возвращаемая ссылка &T привязана к &Heap, которую заимствовал вызов индексации - в точности так же, как это происходит с любым Vec<T>. Здесь не нужно ничего подделывать, потому что время жизни не протаскивается контрабандой через сырой указатель.

Всё остальное логически вытекает отсюда: алгоритм GC работает с простыми структурами данных Rust по стандартным правилам владения Rust.

Два типа ссылок

• Gc<T> - дешёвый, Copy, не удерживает корень (root). Его безопасно хранить внутри других GC-объектов или во время выполнения кода, который не может инициировать сборку.
• Root<T> - удерживает корень для своей цели, не Copy, а побочный эффект его Drop снимает корень. Необходим для удержания ссылки через участки кода, которые могут аллоцировать память и, соответственно, запускать сборку.

Удержание корня - это операция времени выполнения (обновление таблицы корней), а не уровня системы типов. Вклад системы типов заключается в том, что она заставляет пользователя выбирать между двумя видами ссылок ещё на этапе создания, делая дисциплину удержания корней локальной, а не глобальной.

Heap как HashMap<TypeId, Box<dyn ArenaObject>>

Куча представляет собой по одной арене на каждый конкретный тип:

pub struct Heap {
    arenas: HashMap<TypeId, Box<dyn ArenaObject>>,
}

Каждая Arena<T> - это Vec<Slot<T>> с отдельным FreeList<T>. Никакого ручного управления памятью, никакой адресной арифметики: аллокация сводится к "взять из free list или запушить в Vec".

В результате состояние сборщика - это самые обычные данные Rust: Vec, HashMap, Box<dyn Trait>. Когда фаза разметки (mark) хочет зафиксировать, что слот жив, она переключает бит в арене; когда фаза очистки (sweep) хочет освободить слот, она выполняет drop и добавляет его индекс во free list. Ничему из этого не требуется unsafe.

Mark-and-sweep: выбран из-за неудачи с копирующим сборщиком

Первой попыткой Фицджеральда был копирующий сборщик (copying collector). Он отказался от него, столкнувшись с тем, что сам описывает как неразрешимый конфликт заимствований: обновление forwarding-указателей требует мутабельного доступа ко всему from-space, но обход уже удерживает проекцию в конкретную арену. Mark-and-sweep позволил этого избежать: объекты не перемещаются, поэтому перезаписывать данные по старому адресу не требуется.

Переход занял около тридцати минут. Подобная смена архитектуры случается только тогда, когда вы зажаты в рамки системы типов, не позволяющей срезать углы: копирующий сборщик прекрасно реализуется с помощью unsafe, поэтому все остальные GC-библиотеки для Rust его и используют.

Сам алгоритм ничем не примечателен: стеки разметки для каждой арены, цикл до неподвижной точки (fixed-point loop), опустошающий их, и фаза sweep, которая вызывает drop для недостижимых слотов и возвращает их во free list. Арены резервируют дополнительную ёмкость, когда свободное место падает ниже 25%.

Свойства безопасности, доставшиеся даром

Финализаторы не могут воскрешать объекты или приводить к use-after-free. Метод Drop::drop получает &mut self, но не получает &Heap, а единственный способ прочитать Gc<T> - через &Heap. Поэтому деструктор буквально не способен дотянуться ни до какого другого GC-объекта. Грабли, из-за которых во всех остальных языках советуют избегать финализаторов, здесь физически недостижимы.

Трейту Trace не требуется быть unsafe. В классическом GC, если забыть обойти связь при трассировке, живой объект будет освобождён, а чтение по указателю на него приведёт к UB. В safe-gc пропуск связи означает, что живой объект освобождается, его слот используется повторно, а последующая индексация всё равно возвращает валидную память: либо объект всё ещё на месте, либо возникает panic, либо вы наблюдаете переиспользование в духе ABA. Все три варианта безопасны с точки зрения памяти, поэтому Trace остаётся безопасным трейтом.

Висячий Gc<T> - это логическая ошибка, а не UB. Удержание Gc<T> через сборку мусора, которую он не должен был пережить, приводит к одному из исходов: объект случайно всё ещё жив (тихий баг), слот пуст и происходит panic, либо возникает ABA (слот занял кто-то другой). Счётчики поколений позволяют превратить ABA в гарантированный panic. Ни один из сценариев не повреждает память.

Почему это интересно за пределами Rust

Этот паттерн универсален. Всякий раз, когда возникает абстракция, фундаментально нарушающая правила безопасности языка (GC, арены, самоссылающиеся структуры, циклические графы), стандартный ход - спрятать unsafe под тщательно проверенным API. Фицджеральд же меняет форму API так, чтобы запрещённые языком операции было невозможно выразить. Вы платите за это синтаксисом (heap[&gc] вместо *gc) и теряете часть гибкости, которую дал бы копирующий GC, но взамен реализация схлопывается до обычного безопасного Rust.

Это ровно тот же приём, что и "newtype-обёртка без публичного конструктора", только масштабированный до целой подсистемы времени выполнения.

См. также

• pointer-provenance - обратное направление: точная спецификация того, что несут в себе указатели, чтобы внешне разумные оптимизации компилятора оставались корректными. Safe-gc полностью снимает этот вопрос за счёт отсутствия сырых указателей.
• simplified-model-of-fil-c - безопасность памяти, добавленная в C/C++ через рантайм-проверки возможностей (capabilities). Другая точка в пространстве компромиссов "чем приходится жертвовать ради безопасности".
• arena-allocation - тот же подход "индекс вместо указателя": поколенческие арены выдают целочисленные индексы вместо &T, чтобы одновременно обойти borrow checker и use-after-free.
• garbage-collection-handbook - обзорная книга, к которой стоит перейти, если заинтересовала алгоритмическая часть: mark-sweep, копирующие, поколенческие и конкурентные сборщики с низкими паузами вместе с компромиссами, с которыми столкнулся Фицджеральд, в их общем виде.
• safe-gc - сам крейт.