Упрощённая модель Fil-C

Разбор от Peter Cawley проекта Fil-C - реализации C/C++ с гарантией безопасности памяти. Настоящий Fil-C переписывает LLVM IR; упрощённая модель Cawley представлена как преобразование исходного кода C в C, о котором проще рассуждать и от которого рукой подать до релизной версии.

Основной механизм: теневые capability

Каждая локальная переменная указательного типа получает переменную-компаньона типа AllocationRecord*:

T1* p1;               T1* p1; AllocationRecord* p1ar = NULL;

Где AllocationRecord хранит границы диапазона:

struct AllocationRecord {
  char* visible_bytes;
  char* invisible_bytes;
  size_t length;
};

Обычные операции с указателями перемещают компаньона вместе с указателем: p1 = p2 превращается в p1 = p2, p1ar = p2ar. Адресная арифметика сохраняет того же компаньона (p1 = p2 + 10 сохраняет p1ar = p2ar). Приведение из целочисленного типа обнуляет компаньона.

Вызовы функций передают компаньона рядом с каждым аргументом-указателем, а конкретные функции стандартной библиотеки заменяются версиями из Fil-C: malloc становится filc_malloc, free - filc_free, и так далее.

filc_malloc выделяет три сущности

void* filc_malloc(size_t length) {
  AllocationRecord* ar = malloc(sizeof(AllocationRecord));
  ar->visible_bytes  = malloc(length);
  ar->invisible_bytes = calloc(length, 1);
  ar->length = length;
  return {ar->visible_bytes, ar};
}

Три выделения памяти на каждый вызов malloc: сама запись, видимые пользователю байты и параллельный "невидимый" массив того же размера, что и пользовательский буфер.

Проверка границ при разыменовании

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

assert(p1ar != NULL);
uint64_t i = (char*)p1 - p1ar->visible_bytes;
assert(i < p1ar->length);
assert((p1ar->length - i) >= sizeof(*p1));
x = *p1;

Теневая память для указателей в куче

Самая изящная деталь: когда указатели лежат в куче, компилятор не может просто завести локального компаньона. Вместо этого invisible_bytes выступает параллельным массивом с такой же индексацией, как у visible_bytes, но с типом элементов AllocationRecord*. Если указатель лежит по адресу visible_bytes + i, его capability лежит по адресу invisible_bytes + i. Для корректного доступа i должен быть выровнен по sizeof(AllocationRecord*).

Чтение или запись указателя через другой указатель выполняет два чтения/записи: одно для значения, второе для компаньона. Именно поэтому вызов memmove для восьми выровненных байтов ведёт себя иначе, чем восемь раздельных вызовов memmove по 1 байту: выровненная версия также переносит теневую память, а невыровненная - нет.

Сборщик мусора (GC)

filc_free освобождает visible_bytes и invisible_bytes, но не саму структуру AllocationRecord. Этим занимается сборщик мусора, который проходит по цепочкам AllocationRecord и освобождает недостижимые. В продакшене Fil-C использует FUGC - параллельный конкурентный инкрементальный сборщик; упрощённая модель может обойтись stop-the-world.

GC берёт на себя две дополнительные задачи:

1. При освобождении недостижимого AllocationRecord вызывается filc_free. Соответственно, забытый free больше не приводит к утечке - память подчистит GC. Явный вызов free лишь ускоряет освобождение.
2. Если AllocationRecord имеет нулевую длину (length == 0), указатели на него переписываются так, чтобы указывать на единую каноническую запись нулевой длины. Это даёт безопасную обработку use-after-free.

Когда сборщик мусора уже есть, появляется соблазн переложить на него больше работы. Fil-C так и поступает: если у локальной переменной берётся адрес и компилятор не может доказать, что он не утекает наружу, переменная перемещается в кучу. Парный вызов free не требуется - всё соберёт GC.

Сложности продакшен-реализации

Упрощённая модель опускает четыре сложных аспекта настоящего Fil-C:

• Потоки. filc_free не может сразу освобождать память - другой поток в этот момент может выполнять чтение. Атомарные операции с указателями требуют отдельной магии, поскольку базовое преобразование разбивает одно чтение на два (значение + компаньон), нарушая атомарность.
• Указатели на функции. Дополнительное поле в AllocationRecord помечает исполняемый код. Вызовы проверяют p1 == p1ar->visible_bytes и этот флаг. Для защиты от атак через несоответствие типов (type confusion) ABI вызовов унифицирован: каждая функция принимает единственный AllocationRecord с упакованной структурой аргументов.
• Оптимизация памяти. Велик соблазн выделять invisible_bytes лениво, объединять запись и видимые байты в одно выделение памяти и переиспользовать метаданные базового аллокатора.
• Оптимизация производительности. Устранение лишних проверок границ (bounds-check elimination) и схожие приёмы для снижения накладных расходов.

Когда это использовать

Четыре сценария от Cawley:

1. Большие существующие кодовые базы на C/C++, которые, вероятно, безопасны, но это не доказано. В них можно пойти на затраты по GC и производительности ради безопасности, например, как промежуточный шаг перед переписыванием на Rust/Go/Java.
2. Санитайзер - аналог ASan с более сильными гарантиями для поиска ошибок.
3. Безопасное вычисление на этапе компиляции в языках, где compile-time и runtime используют один и тот же язык (в качестве примера приводится Zig), даже если рантайм остаётся небезопасным.
4. Наглядный практический пример концепции pointer-provenance. Компаньон AllocationRecord* как раз и является provenance. Fil-C наглядно показывает, почему компиляторы не могут в общем случае заменять if (p1 == p2) { f(p1); } на if (p1 == p2) { f(p2); }: одинаковые битовые представления могут нести разный provenance, и Fil-C передал бы в f разные capability.

См. также

• fil-c - сам проект
• memory-safety-absolutists - полемика вокруг Fil-C: делают ли его гарантии Rust избыточным, и какие двери закрывают несовместимость по ABI и наличие GC
• pointer-provenance - концепция модели памяти, которую Fil-C воплощает на практике
• abi-stability - защита указателей на функции в Fil-C требует унифицированного ABI, что открывает другой взгляд на проектирование ABI
• meta-tracing - ещё одна техника вида "перепишем программу ради нужного свойства", но ради скорости, а не безопасности
• raii / stroustrup-memory-leaks - вариант той же цели на уровне договоренностей: Страуструп говорит "пишите код без утечек", а Fil-C обеспечивает это механически, когда на дисциплину полагаться нельзя