Раздел 32 · Системное программирование: Zig, ассемблер, Verilog
Сборка мусора и десять ошибок с памятью
открытый урокЭтот раздел читается без входа. Войди, чтобы отмечать прогресс, вести заметки и решать задачи в редакторе. войти
Сборка мусора и десять ошибок с памятью
В прошлом уроке куча
zlпереехала на твой аллокатор: пул ячеек одним массивом, свободный список черезcdr. И сразу стало видно, чего не хватает:fib.zlвыделяет 175 159 ячеек, ни одной не возвращает и в пул на 65 536 ячеек не помещается, хотя живых ячеек в каждый момент меньше трёхсот. Сегодня закрываем блок про виртуальную память двумя темами, которые выглядят разными, а на деле об одном: кто отвечает за то, чтобы память вернулась, и что бывает, когда этот кто-то ошибся. Первая половина про сборщик мусора: что такое достижимость, как работает Mark&Sweep, как собирать мусор в языке, где указатель неотличим от числа, и чем за это платят. В проектеzlпоявится настоящий сборщик, иfib.zlуложится в 8 КБ. Вторая половина про десять классических ошибок с памятью: каждую воспроизведём на C, посмотрим, что скажут valgrind и ASan, а потом попробуем сделать ту же глупость на Zig в трёх режимах сборки и честно запишем, что он поймал, а что нет.
Цели урока
- Объяснять сборку мусора через граф достижимости и отличать мусор от утечки.
- Пройти Mark&Sweep руками: корни, рабочий список, метки, проход Sweep по куче.
- Понимать, почему сборщик для C вынужден быть консервативным, что такое ложное удержание и почему такой сборщик не может двигать объекты.
- Написать сборщик для
zl: точный обход кучи по тегам, консервативный скан машинного стека и сохраняемых регистров, сборка свободного списка заново. - Узнавать в коде десять классических ошибок с памятью и знать, какую из них ловит компилятор Zig, какую проверки
DebugиReleaseSafe, какуюDebugAllocator, а какую не ловит никто. - Читать отчёты valgrind и AddressSanitizer и понимать, на чём держится каждый из инструментов.
Идея: память как граф
До сих пор в блоке про кучу действовал один закон: взял блок через malloc, верни через free. Аллокатор из урока 57 сам ничего не решает, он только ведёт учёт. Решает программист, и программист ошибается в обе стороны: забывает вернуть (утечка) или возвращает то, чем ещё пользуется (об этом вторая половина урока).
Сборщик мусора снимает с программиста вторую половину договора. Программа зовёт только malloc, а free за неё зовёт сборщик, когда убедится, что блок больше никому не нужен. Придумал это Джон Маккарти в 1960 году, и придумал ровно для той задачи, которая у нас в руках: для cons-ячеек Lisp. Программа на Lisp порождает ячейки тысячами на каждом шаге вычисления, и требовать от неё ручного free для каждого промежуточного списка значило бы убить язык.
Главный вопрос: как узнать, что блок никому не нужен? Будущее программы сборщик предсказать не может. Поэтому “не нужен” он заменяет на более грубое и проверяемое свойство: “до блока нельзя добраться”.
Представь память как ориентированный граф. Вершины двух сортов. Первые это блоки кучи. Вторые это корни: места вне кучи, где программа может держать указатель на блок. Это регистры процессора, слова на стеке и глобальные переменные. Ребро из p в q значит, что где-то внутри p лежит указатель на q.
Блок достижим, если к нему ведёт путь от какого-нибудь корня. Недостижимый блок это мусор: у программы нет его адреса и взять его неоткуда, значит, она не прочитает его уже никогда, и память можно забирать.
Обрати внимание на зазор между “не нужен” и “недостижим”. Недостижимый блок точно не нужен. А вот достижимый может быть не нужен тоже: кэш, в который только кладут и никогда не смотрят, достижим целиком. Сборщик такой блок не тронет. Поэтому в языках со сборкой мусора утечки тоже бывают, просто выглядят иначе: это забытая ссылка в долгоживущей структуре.
Mark&Sweep
Самый старый алгоритм, тот самый из статьи Маккарти, состоит из двух фаз.
Mark. Обходим граф от корней и на каждом блоке, до которого дошли, ставим метку. Под метку нужен один бит на блок. В аллокаторе с заголовками для него есть место: размер блока кратен 16, младшие биты слова заголовка свободны, один из них занят флагом “выделен”, соседний берём под метку.
Sweep. Идём по всем блокам кучи подряд, по адресам, как шёл бы неявный список. Блок выделен и помечен: живой, снимаем метку до следующего раза. Блок выделен и не помечен: мусор, освобождаем. Блок свободен: пропускаем.
Вот оба прохода целиком на игрушечной куче из пяти узлов. Ссылка здесь это номер узла, так что программа запускается где угодно:
const std = @import("std");
/// Узел кучи: два поля-ссылки, как у cons-ячейки. Ссылка это номер узла.
const Node = struct {
name: u8,
refs: [2]?u8 = .{ null, null },
allocated: bool = true,
marked: bool = false,
};
fn mark(heap: []Node, roots: []const u8) void {
var stack: [16]u8 = undefined;
var top: usize = 0;
for (roots) |r| {
heap[r].marked = true;
stack[top] = r;
top += 1;
}
while (top > 0) {
top -= 1;
for (heap[stack[top]].refs) |ref| {
const next = ref orelse continue;
if (heap[next].marked) continue;
heap[next].marked = true;
stack[top] = next;
top += 1;
}
}
}
fn sweep(heap: []Node, out: *std.Io.Writer) !void {
for (heap) |*node| {
if (node.allocated and !node.marked) {
node.allocated = false;
try out.print("освобождён {c}\n", .{node.name});
}
node.marked = false;
}
}
pub fn main(init: std.process.Init) !void {
var buf: [256]u8 = undefined;
var w = std.Io.File.stdout().writer(init.io, &buf);
const out = &w.interface;
// a -> b -> a (живой цикл), a -> c; x -> y -> x (мусорный цикл), y -> c.
var heap = [_]Node{
.{ .name = 'a', .refs = .{ 1, 2 } },
.{ .name = 'b', .refs = .{ 0, null } },
.{ .name = 'c' },
.{ .name = 'x', .refs = .{ 4, null } },
.{ .name = 'y', .refs = .{ 3, 2 } },
};
mark(&heap, &.{0});
try sweep(&heap, out);
try out.flush();
}$ zig run ms_mini.zig
освобождён x
освобождён yПосмотри на три вещи, они вернутся в настоящем сборщике.
Первая: узлы a и b ссылаются друг на друга, и обход на этом цикле не зависает. Узел помечается в тот момент, когда попадает в рабочий стек, а помеченный второй раз туда не кладётся.
Вторая: узлы x и y тоже ссылаются друг на друга, на каждый есть ссылка, и оба мусор. От корня к ним пути нет, и этого достаточно. Запомни эту пару до разговора о подсчёте ссылок.
Третья: рекурсии нет. В книге mark написана рекурсивно, так короче. Но рекурсивная пометка списка из миллиона узлов это миллион кадров машинного стека, и сборщик, которого позвали потому что кончилась память, упадёт от нехватки стека. В жизни вместо рекурсии всегда рабочий список.
Попробуй руками
Пройди первый сценарий кнопкой “шаг” до конца. Слева корень, по кругу блоки в порядке адресов, под графом та же куча лентой: по ней пойдёт Sweep. Зелёный блок помечен, двойная обводка значит, что блок ждёт в рабочем списке. Потом переключи список с очереди на стек: порядок обхода сменится с обхода в ширину на обход в глубину, а множество помеченных останется тем же. Для корректности порядок неважен, важен для кэша: обход в глубину по списку идёт по соседним адресам.
Во втором сценарии посмотри, как Mark дважды упирается в уже помеченный блок и как Sweep забирает x и y. Третий и четвёртый сценарии понадобятся через минуту.
Сколько это стоит
Mark трогает только живое: его цена пропорциональна числу достижимых блоков. Sweep трогает всё: его цена пропорциональна размеру кучи. Отсюда практическое правило: Mark&Sweep дёшев, когда живого мало, а куча невелика, и дорог, когда куча на гигабайты, даже если мусора в ней почти нет.
Вторая цена это пауза. Пока идёт пометка, граф менять нельзя: если программа перевесит указатель из ещё не просмотренного блока в уже просмотренный, сборщик этого не увидит и освободит живое. Простейшее решение так и называется, остановка мира: программа стоит, сборщик работает. На куче в десятки гигабайт это секунды, и вся история сборщиков после 1960 года это борьба с этой паузой.
Консервативный сборщик: когда указатель не отличить от числа
В Lisp, Java или Go среда исполнения знает про каждое слово памяти, указатель это или нет: у значений есть теги, у объектов описания полей, у кадров стека карты. Такой сборщик называют точным.
В C ничего этого нет. Слово 0x7f3a5c001040 в памяти может быть указателем на блок кучи, а может быть long, хешем, восемью байтами строки или временем в наносекундах. Компилятор типы знал, но в исполняемый файл они не попали. И всё же сборщик для C написать можно, если согласиться на одну уступку.
Консервативный сборщик считает указателем любое слово, значение которого попадает внутрь какого-нибудь выделенного блока. Ошибиться он может только в одну сторону. Настоящий указатель всегда выглядит как адрес внутри блока, поэтому живое не пострадает никогда. А вот число, случайно совпавшее с адресом, удержит блок, который на деле мусор. Отсюда и слово: сборщик перестраховывается.
Из этого определения вырастают три инженерные задачи.
Найти блок по адресу внутри него. Функция isPtr(p) из книги должна по произвольному числу ответить, попадает ли оно в выделенный блок, и если да, то где у блока начало. Указатель в C вправе смотреть в середину: на третий элемент массива, на поле структуры. Значит, заголовок по адресу p - 8 искать бессмысленно, нужен поиск по диапазонам. Книга предлагает сбалансированное дерево выделенных блоков с ключом по адресу, а указатели на левого и правого соседа кладёт в заголовок блока. Настоящие сборщики обходятся дешевле: куча нарезана на страницы, в каждой странице блоки одного размера, и по адресу начало блока считается делением. Ровно так ответит и наш пул в zl: ячейки одного размера лежат подряд, номер ячейки это смещение, делённое на 32.
Решить, где искать. Корни консервативного сборщика это весь стек от текущей вершины до дна, все регистры и все сегменты данных программы. Внутри блока тоже неизвестно, где указатели, поэтому каждый блок просматривается целиком, слово за словом.
Смириться с ложным удержанием. Открой в виджете сценарий “Ложный указатель” и пройди его дважды: в точном режиме и в консервативном. В блоке a лежит обычное целое, которое совпало с адресом внутри мусорного блока g. Точный сборщик знает, что это число, и освобождает g вместе с h. Консервативный видит пунктирное ребро и оставляет обоих. Одно неудачное число удержало не один блок, а всё, что достижимо из него: если бы g был головой списка на гигабайт, остался бы гигабайт. Сценарий “Указатель в середину” про первую задачу: корень смотрит на третий элемент массива, и сборщик обязан найти блок по внутреннему адресу.
На 64-битной машине ложное удержание редкость: адреса кучи занимают ничтожную долю из 2^64 значений, и случайное целое туда почти не попадает. На 32-битных машинах с кучей в сотни мегабайт это была настоящая беда: каждое десятое случайное слово выглядело как адрес.
Есть и четвёртое следствие, самое тяжёлое. Консервативный сборщик не может двигать объекты. Чтобы переместить блок, нужно поправить все указатели на него. Но если сборщик не уверен, что слово это указатель, править его нельзя: вдруг это число, и программа потом получит другое число. Значит, никакого уплотнения кучи и никакой борьбы с фрагментацией: все проблемы из урока 57 остаются.
Что делает Boehm GC
Сборщик Бёма, Демерса и Уэйзера (первая версия вышла в 1988 году, живёт до сих пор) это и есть консервативный Mark&Sweep для C и C++, доведённый до промышленного состояния. Подключается он как библиотека, которая подменяет malloc:
#include <gc.h>
int main(void) {
GC_INIT();
for (int i = 0; i < 10000000; i++) {
int **p = GC_MALLOC(sizeof(int *));
*p = GC_MALLOC_ATOMIC(sizeof(int)); /* внутри указателей нет */
}
return 0; /* ни одного free */
}Что у него внутри, по пунктам, и каждый пункт это ответ на одну из задач выше:
- Корни: стек каждого потока от вершины до дна, регистры (снимаются приёмом, похожим на
setjmp), сегменты.dataи.bssпрограммы и всех загруженных библиотек. Дно стека на Linux он узнаёт из/proc/self/statили/proc/self/maps, и мы сделаем так же. - Куча нарезана на страницы с блоками одного размера, поэтому
isPtrэто пара делений и проверка по таблице страниц кучи, без дерева. GC_MALLOC_ATOMICэто подсказка “в этом блоке указателей нет”: строки, картинки и числовые массивы сборщик не просматривает. Это и быстрее, и убирает главный источник ложных указателей: сжатые данные выглядят как случайные числа.- Чёрный список: если сборщик видит на стеке число, которое указывает в ещё не выделенную страницу кучи, он запоминает страницу и не выдаёт оттуда память. Когда в неё что-то ляжет, это число уже не станет ложным указателем.
- Инкрементальный режим опирается на виртуальную память из нашего блока: страницы кучи закрываются от записи через
mprotect, первая запись в страницу даёт сбой, обработчик помечает страницу грязной и открывает её. К концу пометки сборщик перепроверяет только грязные страницы, и пауза сокращается. Это тот же приём, что копирование при записи в уроке 56.
Boehm GC стоял под GCJ и Mono, до сих пор работает в GNU Guile, Inkscape и множестве интерпретаторов, авторы которых решили не писать сборщик сами. Ещё его используют как детектор утечек для обычных программ на C: сборщик ничего не освобождает, а только сообщает о блоках, которые стали недостижимы без free.
Что дальше: три идеи без подробностей
Mark&Sweep это точка отсчёта. Дальше сборщики расходятся в три стороны, и тебе достаточно знать, какую проблему решает каждая.
Подсчёт ссылок. В каждом блоке счётчик входящих указателей; упал до нуля, блок освобождается сразу, без пауз и без обхода. Так живут CPython, Swift, Rc в Rust, shared_ptr в C++. Цена: запись в память на каждое копирование указателя и, главное, циклы. Вспомни x и y из примера: у каждого счётчик равен единице навсегда. CPython поверх счётчиков держит отдельный обходящий сборщик только ради циклов, а в Swift и Rust циклы разрывают руками через слабые ссылки.
Копирующие сборщики. Куча делится пополам; живые объекты копируются из одной половины в другую плотно, друг за другом, а старая половина объявляется свободной целиком. Фазы Sweep нет вообще, цена пропорциональна только живому, выделение превращается в сдвиг указателя, а фрагментация исчезает. Плата: половина памяти простаивает, и сборщик обязан быть точным, ведь он двигает объекты.
Поколения. Наблюдение, на котором стоят все современные сборщики: большинство объектов умирает молодыми. Промежуточный список живёт микросекунды, таблица настроек живёт вечно. Поэтому кучу делят на молодое поколение (маленькое, собирается часто, обычно копированием) и старое (большое, собирается редко). Так устроены сборщики JVM, .NET и V8. Go пошёл другим путём: у него сборщик без перемещения и без поколений, зато пометка идёт одновременно с программой, и пауза остановки мира держится в пределах долей миллисекунды.
Наш fib.zl, кстати, идеальная иллюстрация гипотезы поколений: из 175 159 выделенных ячеек в каждый момент живы меньше трёхсот.
Проект zl: сборщик для cons-ячеек
Теперь то же самое по-настоящему. Исходное состояние ты помнишь по прошлому уроку: пул ячеек есть, release есть, но звать его некому.
$ zl --stats programs/fib.zl
6765
пул: 524288 ячеек, 8192 КБ
занято: 175159, свободно: 349129, пик: 175159
выделено за прогон: 175159
свободных участков: 1, самый длинный: 349129, раздробленность: 0.00
$ zl --cells 65536 programs/fib.zl
ошибка: OutOfMemory
error: OutOfMemoryДвадцатое число Фибоначчи стоит 2,7 МБ, и ни один байт из них не возвращается. К концу шага та же программа пройдёт в пуле на 256 ячеек, то есть в 4 КБ.
Пять решений до первой строки кода
Сборщик это тот случай, когда неверное решение на входе стоит недели отладки. Поэтому сначала решения, потом листинги.
Где живёт бит пометки. В аллокаторе с заголовками бит берут из заголовка. У нашей ячейки заголовка нет: это два слова по 8 байт. Зато в уроке про выравнивание мы нарочно оставили в теге значения свободный бит: бит 1 (0b0010) не занят ни у числа, ни у адреса, ни у номера. Значит, он свободен в любом слове ячейки, что бы в нём ни лежало, и пометку можно поставить прямо в слово car. Отдельной памяти она не просит, и признак «помечена» читается из той же линии кэша, из которой пометка потом читает поля.
Цена у решения тоже есть, и её стоит знать. Пометка пишет в страницы ячеек, а sweep гасит её в каждой выжившей ячейке, так что сборка трогает на запись всю живую кучу. Если процесс с большой кучей сделал fork, такая сборка скопирует каждую страницу кучи (вспомни копирование при записи). Пометка в отдельной битовой карте, рядом с live, копировала бы только карту: по этой причине Ruby в версии 2.0 перенёс биты пометки из объектов в отдельные карты. Нам важнее ноль лишней памяти и то, что бит тега уже был оплачен, поэтому пометка живёт в теге. Второе правило вытекает из первого: слово с поднятым битом это уже не значение (nil с ним выглядит как пара по адресу ноль), поэтому сборщик снимает бит, прежде чем читать слово как значение.
Что считать корнями. Корней у zl три рода.
- Глобальные имена: всё, что связано через
define, включая замыкания вместе с их окружениями. Таблица символов сама ячеек не держит: символ это номер, а имя лежит в памяти от аллокатора. - Явный список корней. Читатель собирает элементы списка в срез
std.ArrayList(Value), срез лежит в памяти от аллокатора, и со стека его содержимое не видно. Кто держит значения в таком месте, тот сам объявляет срез корнем на время работы. - Машинный стек и регистры.
evalнаписан рекурсией на Zig, и все его промежуточные значения (вычисленные аргументы, наполовину собранное окружение) живут в кадрах Zig.
Как читать стек: точно или консервативно. Точный путь называется теневым стеком: каждая функция интерпретатора регистрирует свои локальные значения в списке корней на входе и снимает на выходе. Это eval, apply, evalList, bind, evalCond и каждый примитив. Одна забытая переменная, и раз в тысячу прогонов сборка попадёт ровно между выделением ячейки и записью её адреса в структуру, и программа прочитает освобождённую память. Такие ошибки не воспроизводятся и не лечатся.
Консервативный путь: пройти машинный стек от текущего кадра до дна и любое слово, похожее на адрес занятой ячейки пула, считать корнем. В eval при этом не меняется ни строки. И есть второй довод, решающий: код, который порождает JIT из урока 19, держит значения в слотах своего кадра, и карт этих кадров нет по построению. Их найдёт только скан.
Заметь, как это отличается от Boehm. Консервативен у нас только стек. Сама куча обходится точно: внутри ячейки тег значения говорит, пара это или число, и гадать не приходится. Такую схему называют “преимущественно точной”, так работали ранние версии сборщика Go и до сих пор работает JavaScriptCore в Safari.
Что считать попаданием. Слово засчитывается корнем, если попадает в любое место занятой ячейки, а не только на её начало. Оптимизатор вправе держать в регистре адрес поля cdr, а саму пару нигде не хранить. И вот тут окупается карта live из прошлого урока: слово, которое попало в свободную ячейку, корнем не считается. Без этой проверки старый адрес в мёртвом кадре стека потянул бы за собой через cdr весь свободный список.
Когда запускать. Когда свободный список пуст. take зовёт сборку и пробует ещё раз; если пусто и после сборки, cons возвращает error.OutOfMemory. Пул не растёт: так числа в статистике остаются честными, и сразу видно, сколько памяти программе нужно на самом деле.
Как собрать кольцо: set-car! и set-cdr!
До этого урока zl был чисто функциональным: готовую ячейку изменить нельзя, значит, любая ячейка ссылается только на те, что старше неё, и циклов не бывает. Чтобы проверить сборщик на циклическом мусоре, нужен способ цикл собрать. В primitives.zig в конец таблицы добавляются две строки (номера первых двенадцати примитивов не меняются, а на них опирается JIT):
.{ "set-car!", primSetCar },
.{ "set-cdr!", primSetCdr },И сами примитивы, рядом с primEq:
/// `(set-car! пара значение)`: единственный способ изменить готовую ячейку,
/// а значит и единственный способ собрать цикл. Возвращает саму пару.
fn primSetCar(vm: *Vm, args: Value) Error!Value {
_ = vm;
const pair = try takeTwo(args);
if (!pair[0].isCons()) return error.NotAPair;
pair[0].asCell().car = pair[1];
return pair[0];
}
fn primSetCdr(vm: *Vm, args: Value) Error!Value {
_ = vm;
const pair = try takeTwo(args);
if (!pair[0].isCons()) return error.NotAPair;
pair[0].asCell().cdr = pair[1];
return pair[0];
}У этих двадцати строк есть последствие, о котором легко не подумать. set-cdr! возвращает саму пару, диалог тут же пытается её напечатать, а печать кольца не кончается никогда. Я на это наступил: проверочный прогон успел выдать больше 5 ГБ единиц, прежде чем его убили. Поэтому у печати появляются два предела: сколько ячеек печатаем всего и как глубоко идём по car.
//! Печать значений zl.
//!
//! Обратная к читателю операция, с одним исключением: замыкание напечатать
//! нечем, для него есть форма `#<closure>`, которую читатель обратно не примет.
const std = @import("std");
const primitives = @import("primitives.zig");
const value = @import("value.zig");
const Vm = @import("vm.zig").Vm;
const Value = value.Value;
/// Сколько ячеек печатаем, прежде чем оборвать вывод многоточием, и как
/// глубоко идём по `car`. С появлением `set-car!` и `set-cdr!` список может
/// замкнуться в кольцо, и печать без предела не кончилась бы никогда.
pub const max_cells = 1 << 16;
pub const max_depth = 256;
pub fn write(w: *std.Io.Writer, vm: *const Vm, v: Value) std.Io.Writer.Error!void {
var budget: usize = max_cells;
try writeBounded(w, vm, v, &budget, 0);
}
fn writeBounded(
w: *std.Io.Writer,
vm: *const Vm,
v: Value,
budget: *usize,
depth: usize,
) std.Io.Writer.Error!void {
switch (v.tag()) {
.nil => try w.writeAll("nil"),
.fixnum => try w.print("{d}", .{v.asFixnum()}),
.symbol => try w.writeAll(vm.nameOf(v.asSymbol())),
.closure => try w.writeAll("#<closure>"),
.primitive => try w.print("#<{s}>", .{primitives.nameOf(v.asPrimitive())}),
.cons => {
if (depth >= max_depth) return w.writeAll("...");
try w.writeByte('(');
var rest = v;
var first = true;
while (true) {
if (!first) try w.writeByte(' ');
first = false;
if (budget.* == 0) {
try w.writeAll("...");
break;
}
budget.* -= 1;
try writeBounded(w, vm, rest.asCell().car, budget, depth + 1);
const tail = rest.asCell().cdr;
if (tail.isNil()) break;
if (!tail.isCons()) {
// Точечная пара печатается только тогда, когда хвост не список.
try w.writeAll(" . ");
try writeBounded(w, vm, tail, budget, depth + 1);
break;
}
rest = tail;
}
try w.writeByte(')');
},
}
}
/// Напечатать значение в свежую строку. Строка принадлежит вызывающему.
pub fn toOwned(gpa: std.mem.Allocator, vm: *const Vm, v: Value) std.mem.Allocator.Error![]u8 {
var out: std.Io.Writer.Allocating = .init(gpa);
defer out.deinit();
write(&out.writer, vm, v) catch return error.OutOfMemory;
return out.toOwnedSlice();
}Теперь (set-cdr! a a) печатает 65 536 элементов и многоточие. Настоящие реализации Lisp умеют печатать кольца метками вида #1=(1 . #1#), для этого нужен предварительный обход с таблицей посещённых; нам хватит обрыва.
Куча: что изменилось
heap.zig показываю целиком, изменений много. Что нового относительно прошлого урока: поле marker, корни globals и roots с парой pushRoots и popRoots, дно стека stack_bottom, рабочий стек пометки mark_stack, счётчики collections и freed_total с двумя полями в Stats, вызов сборщика в take. И пул по умолчанию стал в восемь раз меньше: 1 << 16 вместо 1 << 19. Новых битовых карт нет: пометке хватает бита в теге.
//! Куча zl: пул cons-ячеек одним регионом.
//!
//! До этого шага ячейки жили на арене и не освобождались никогда. Теперь
//! куча своя. Весь пул это один непрерывный массив ячеек, взятый у внешнего
//! аллокатора одним запросом. Свободные ячейки связаны в список, и отдельной
//! памяти под него не нужно: свободной ячейке её `cdr` ни к чему, поэтому в
//! нём лежит ссылка на следующую свободную. Выделение это снять голову списка,
//! освобождение это надеть голову обратно, то и другое за O(1).
//!
//! Внешний аллокатор это параметр `std.mem.Allocator`. Сюда встаёт аллокатор
//! из malloclab: через него приходят регион пула, битовые карты, имена
//! символов и таблица глобальных имён, то есть всё, у чего размер переменный.
//! Ячейкам общий аллокатор не нужен: они одного размера, и пул обслуживает их
//! быстрее и без заголовков.
//!
//! Замыкание тоже сложено из ячеек: `(параметры . (тело . окружение))`. Так
//! в куче остаётся один вид объектов, и сборщику мусора не приходится знать
//! ни про какие другие.
//!
//! Когда свободный список пуст, куча зовёт сборщик из `gc.zig` и пробует ещё
//! раз. Для сборщика здесь лежат корни (глобальные имена и явный список
//! корней). Пометки в отдельной карте не нужны: сборщик ставит их в свободный
//! бит тега прямо в слове `car` ячейки.
const std = @import("std");
const gc = @import("gc.zig");
const symbols = @import("symbols.zig");
const value = @import("value.zig");
pub const Cell = value.Cell;
const Value = value.Value;
const Allocator = std.mem.Allocator;
const BitSet = std.DynamicBitSetUnmanaged;
pub const Options = struct {
/// Сколько ячеек в пуле. Ячейка это 16 байт, так что по умолчанию 1 МБ.
/// Пока мусор никто не собирал, `fib.zl` сюда не помещался. Теперь
/// помещается в пул в сотни раз меньше.
cells: usize = 1 << 16,
/// Как сборщик обходит граф при пометке.
marker: gc.Marker = .stack,
};
/// Глобальные имена: символ в значение. Живут в куче, потому что это её
/// главный набор корней.
pub const Globals = std.AutoHashMapUnmanaged(symbols.SymbolId, Value);
/// Список значений, которые лежат вне машинного стека и вне глобальных имён,
/// но должны пережить сборку.
pub const RootList = std.ArrayList(Value);
/// Снимок состояния пула.
pub const Stats = struct {
capacity: usize,
used: usize,
free: usize,
/// Наибольшее число одновременно занятых ячеек за жизнь кучи.
peak: usize,
/// Сколько раз запускался сборщик и сколько ячеек он вернул за всё время.
collections: usize,
freed_total: usize,
/// Сколько непрерывных свободных участков в регионе.
free_runs: usize,
/// Длина самого длинного из них, в ячейках.
largest_free_run: usize,
/// Доля свободной памяти, которая лежит вне самого длинного участка.
/// Ноль означает, что всё свободное место это один кусок. Выделению
/// ячеек раздробленность не мешает, они все одного размера, зато от неё
/// зависит, лягут ли соседние ячейки нового списка в одну линию кэша.
pub fn fragmentation(self: Stats) f64 {
if (self.free == 0) return 0;
const largest: f64 = @floatFromInt(self.largest_free_run);
const free: f64 = @floatFromInt(self.free);
return 1.0 - largest / free;
}
};
pub const Heap = struct {
backing: Allocator,
/// Регион пула: все ячейки кучи, занятые и свободные вперемешку.
cells: []Cell,
/// Голова свободного списка. Следующая свободная лежит в `cdr` головы.
free_list: ?*Cell = null,
/// Бит на ячейку: занята ли она. Свободный список отвечает на вопрос
/// "какую ячейку отдать", а карта на вопрос "занята ли вот эта". Пометки
/// сборщика здесь нет: она живёт в теге слова `car` самой ячейки.
live: BitSet,
marker: gc.Marker,
/// Корни первого рода: глобальные имена.
globals: Globals = .empty,
/// Корни второго рода: явный список. Сюда записывается тот, кто держит
/// значения в памяти от аллокатора, где сборщик их не увидит.
roots: std.ArrayList(*const RootList) = .empty,
/// Дно машинного стека, старший адрес. Узнаётся при первой сборке.
stack_bottom: ?usize = null,
/// Рабочий стек пометки. Живёт между сборками, чтобы не выделяться заново.
mark_stack: std.ArrayList(*Cell) = .empty,
collections: usize = 0,
freed_total: usize = 0,
used: usize = 0,
peak: usize = 0,
/// Сколько пар и замыканий выделено за жизнь кучи.
cells_allocated: usize = 0,
closures_allocated: usize = 0,
pub fn init(backing: Allocator, options: Options) Allocator.Error!Heap {
const cells = try backing.alloc(Cell, options.cells);
errdefer backing.free(cells);
var live: BitSet = try .initEmpty(backing, options.cells);
errdefer live.deinit(backing);
var self: Heap = .{
.backing = backing,
.cells = cells,
.live = live,
.marker = options.marker,
};
self.threadFreeList();
return self;
}
pub fn deinit(self: *Heap) void {
self.mark_stack.deinit(self.backing);
self.roots.deinit(self.backing);
self.globals.deinit(self.backing);
self.live.deinit(self.backing);
self.backing.free(self.cells);
self.* = undefined;
}
/// Продеть свободный список через все незанятые ячейки, от старших адресов
/// к младшим: тогда голова списка это первая свободная ячейка региона,
/// и подряд выделенные ячейки лежат в памяти подряд.
pub fn threadFreeList(self: *Heap) void {
self.free_list = null;
var i = self.cells.len;
while (i > 0) {
i -= 1;
if (!self.live.isSet(i)) self.pushFree(&self.cells[i]);
}
}
fn pushFree(self: *Heap, cell: *Cell) void {
cell.* = .{
.car = .nil,
.cdr = if (self.free_list) |next| .fromCell(next) else .nil,
};
self.free_list = cell;
}
/// Объявить список корнем на время работы с ним. Снимать в обратном порядке.
pub fn pushRoots(self: *Heap, root_list: *const RootList) Allocator.Error!void {
try self.roots.append(self.backing, root_list);
}
pub fn popRoots(self: *Heap) void {
_ = self.roots.pop();
}
/// Снять ячейку с головы свободного списка. Если список пуст, сначала
/// собрать мусор. Сборка консервативная: нас позвали из глубины `eval`,
/// и живые значения лежат в кадрах Zig, про которые знает только стек.
fn take(self: *Heap) Allocator.Error!*Cell {
if (self.free_list == null) _ = try gc.collect(self, .conservative);
const cell = self.free_list orelse return error.OutOfMemory;
self.free_list = if (cell.cdr.isCons()) cell.cdr.asCell() else null;
self.live.set(self.indexOf(cell));
self.used += 1;
self.peak = @max(self.peak, self.used);
return cell;
}
/// Вернуть ячейку в пул. Вызывающий отвечает за то, что на неё никто
/// больше не ссылается.
pub fn release(self: *Heap, cell: *Cell) void {
const index = self.indexOf(cell);
std.debug.assert(self.live.isSet(index));
self.live.unset(index);
self.used -= 1;
self.pushFree(cell);
}
/// Номер ячейки в регионе.
pub fn indexOf(self: *const Heap, cell: *const Cell) usize {
return (@intFromPtr(cell) - @intFromPtr(self.cells.ptr)) / @sizeOf(Cell);
}
/// Ячейка пула, внутрь которой показывает адрес, или null, если адрес
/// лежит вне региона.
pub fn cellAt(self: *Heap, addr: usize) ?*Cell {
const base = @intFromPtr(self.cells.ptr);
if (addr < base or addr >= base + self.cells.len * @sizeOf(Cell)) return null;
return &self.cells[(addr - base) / @sizeOf(Cell)];
}
pub fn cons(self: *Heap, a: Value, d: Value) Allocator.Error!Value {
const cell = try self.take();
cell.* = .{ .car = a, .cdr = d };
self.cells_allocated += 1;
return .fromCell(cell);
}
/// Замыкание это две ячейки: `(параметры . (тело . окружение))`.
pub fn closure(self: *Heap, params: Value, body: Value, env: Value) Allocator.Error!Value {
const rest = try self.cons(body, env);
const head = try self.cons(params, rest);
self.closures_allocated += 1;
return .fromClosure(head.asCell());
}
/// Собрать список из готового среза значений, справа налево.
pub fn list(self: *Heap, items: []const Value) Allocator.Error!Value {
var acc: Value = .nil;
var i = items.len;
while (i > 0) {
i -= 1;
acc = try self.cons(items[i], acc);
}
return acc;
}
pub fn stats(self: *const Heap) Stats {
var runs: usize = 0;
var largest: usize = 0;
var run: usize = 0;
for (0..self.cells.len) |i| {
if (self.live.isSet(i)) {
run = 0;
continue;
}
if (run == 0) runs += 1;
run += 1;
largest = @max(largest, run);
}
return .{
.capacity = self.cells.len,
.used = self.used,
.free = self.cells.len - self.used,
.peak = self.peak,
.collections = self.collections,
.freed_total = self.freed_total,
.free_runs = runs,
.largest_free_run = largest,
};
}
};
const testing = std.testing;
test "свежий пул это один свободный участок, и ячейки выдаются подряд" {
var heap: Heap = try .init(testing.allocator, .{ .cells = 8 });
defer heap.deinit();
const a = try heap.cons(.fromFixnum(1), .nil);
const b = try heap.cons(.fromFixnum(2), .nil);
try testing.expectEqual(@as(usize, 0), heap.indexOf(a.asCell()));
try testing.expectEqual(@as(usize, 1), heap.indexOf(b.asCell()));
const s = heap.stats();
try testing.expectEqual(@as(usize, 2), s.used);
try testing.expectEqual(@as(usize, 1), s.free_runs);
try testing.expectEqual(@as(usize, 6), s.largest_free_run);
try testing.expectEqual(@as(f64, 0), s.fragmentation());
}
test "освобождённая ячейка возвращается первой" {
var heap: Heap = try .init(testing.allocator, .{ .cells = 4 });
defer heap.deinit();
const a = try heap.cons(.fromFixnum(1), .nil);
_ = try heap.cons(.fromFixnum(2), .nil);
heap.release(a.asCell());
const c = try heap.cons(.fromFixnum(3), .nil);
try testing.expectEqual(a.asCell(), c.asCell());
}Три места стоят отдельного взгляда.
take зовёт сборку в режиме .conservative, и комментарий объясняет почему: нас позвали из глубины eval, живые значения лежат в кадрах Zig. Точный режим .precise существует, но годится только в безопасной точке, когда ни один кадр не держит ничего нужного. Им пользуются тесты, которым нужны точные числа.
cellAt это наш isPtr из книги. Никакого дерева: проверка диапазона и деление на размер ячейки. Вся сложность поиска блока по внутреннему адресу исчезла, потому что блоки одного размера лежат подряд.
mark_stack живёт в куче между сборками и память берёт у внешнего аллокатора. Это слабое место: сборщик, которого позвали из-за нехватки памяти, сам просит память. У нас пул и внешний аллокатор разные, так что противоречия нет, но в худшем случае рабочий стек вырастает до слова на ячейку. Как обойтись совсем без него, покажет задание со звёздочкой.
Сборщик
//! Сборщик мусора Mark&Sweep для пула ячеек.
//!
//! Живой считается ячейка, до которой можно дойти от корней. Корней три рода:
//!
//! 1. глобальные имена (`heap.globals`): всё, что связано через `define`,
//! включая замыкания и их окружения. Таблица символов сама ячеек не
//! держит: символ это номер, а его имя лежит в памяти от аллокатора.
//! Значение глобального символа и есть запись в `globals`;
//! 2. явный список корней (`heap.roots`): значения, которые кто-то держит в
//! памяти от аллокатора, например срез элементов в читателе;
//! 3. машинный стек и регистры, только в консервативном режиме.
//!
//! Третий род это стек интерпретатора. `eval` написан рекурсией на Zig, его
//! промежуточные значения лежат в кадрах Zig, и карты этих кадров у нас нет.
//! Теневой стек потребовал бы регистрировать каждую локальную переменную в
//! `eval`, `apply`, `evalList` и в каждом примитиве, и одна забытая переменная
//! давала бы повреждение памяти раз в тысячу прогонов. Поэтому стек читается
//! консервативно: любое слово, которое выглядит как адрес занятой ячейки
//! пула, считается корнем. Так же находятся значения в кадрах кода из JIT, у
//! которого карт стека нет по построению. Цена: число, случайно совпавшее с
//! адресом ячейки, удержит мусор. Двигать ячейки при таком сборщике нельзя,
//! но Mark&Sweep их и не двигает.
//!
//! Куча при этом обходится точно: внутри ячейки тег значения говорит, где
//! указатель, а где число, и гадать не приходится.
//!
//! Пометка живёт в самой ячейке: это бит 1 слова `car`, который тег значения
//! оставляет свободным при любом виде. Отдельной карты пометок нет, зато
//! пометка пишет в страницы пула, а sweep гасит её в каждой выжившей ячейке.
const std = @import("std");
const builtin = @import("builtin");
const dsw = @import("gc_dsw.zig");
const heap_mod = @import("heap.zig");
const sys = @import("sys.zig");
const value = @import("value.zig");
const Cell = value.Cell;
const Heap = heap_mod.Heap;
const Value = value.Value;
const Allocator = std.mem.Allocator;
pub const Scan = enum {
/// Только глобальные имена и явные корни. Годится лишь в безопасной точке,
/// когда ни один кадр Zig не держит значение, нужное после сборки.
precise,
/// Плюс машинный стек и регистры. Так куча собирает себя сама.
conservative,
};
pub const Marker = enum {
/// Пометка волной с явным рабочим стеком.
stack,
/// Пометка разворотом указателей, без дополнительной памяти.
pointer_reversal,
};
/// Собрать мусор. Возвращает число освобождённых ячеек.
pub fn collect(heap: *Heap, scan: Scan) Allocator.Error!usize {
try markValues(heap);
if (scan == .conservative) try markMachineStack(heap);
return sweep(heap);
}
// --- Mark ---
fn markValues(heap: *Heap) Allocator.Error!void {
var globals = heap.globals.valueIterator();
while (globals.next()) |v| try markFrom(heap, v.*);
for (heap.roots.items) |list| {
for (list.items) |v| try markFrom(heap, v);
}
}
/// Помечена ли ячейка: бит сборщика в слове `car`.
pub fn isMarked(cell: *const Cell) bool {
return cell.car.gcBit();
}
/// Поставить или снять пометку. Что лежит в `car`, неважно: свободный бит
/// есть у значения любого вида.
pub fn setMark(cell: *Cell, on: bool) void {
cell.car = cell.car.withGcBit(on);
}
/// Нужно ли идти в эту ячейку: она в пуле, занята и ещё не помечена.
/// Занятость проверяется первой: в свободной ячейке пометку не ищут.
pub fn unvisited(heap: *const Heap, cell: *const Cell) bool {
return heap.live.isSet(heap.indexOf(cell)) and !isMarked(cell);
}
/// Пометить всё достижимое из значения.
pub fn markFrom(heap: *Heap, root: Value) Allocator.Error!void {
const cell = root.heapCell() orelse return;
if (!unvisited(heap, cell)) return;
switch (heap.marker) {
.stack => try markWave(heap, cell),
.pointer_reversal => dsw.mark(heap, root),
}
}
/// Волна от одной ячейки. Рекурсии по `car` нет: список из миллиона ячеек
/// иначе стоил бы миллион кадров машинного стека. Вместо неё рабочий стек
/// в куче, а ячейка помечается в момент, когда на него попадает, поэтому
/// дважды туда не попадёт и цикл волну не зациклит.
fn markWave(heap: *Heap, start: *Cell) Allocator.Error!void {
setMark(start, true);
try heap.mark_stack.append(heap.backing, start);
while (heap.mark_stack.pop()) |cell| {
// В `car` уже стоит пометка: слово становится значением, только
// когда бит снят.
for ([_]Value{ cell.car.withGcBit(false), cell.cdr }) |child| {
const next = child.heapCell() orelse continue;
if (!unvisited(heap, next)) continue;
setMark(next, true);
try heap.mark_stack.append(heap.backing, next);
}
}
}
// --- Консервативный скан ---
/// Регистры, которые вызываемая функция обязана сохранить. В любом из них
/// может лежать единственная ссылка на ячейку: вызывающий положил её туда и
/// вправе рассчитывать, что она переживёт вызов. Остальные регистры
/// вызывающий перед вызовом сам сбросил на стек.
const saved_count = switch (builtin.cpu.arch) {
.x86_64 => 6,
.aarch64 => 11,
else => @compileError("консервативный скан: опиши сохраняемые регистры этой архитектуры"),
};
/// Сложить сохраняемые регистры в массив. Это тот же приём, которым `setjmp`
/// снимает слепок регистров, только без libc.
inline fn spillRegisters(regs: *[saved_count]usize) void {
switch (builtin.cpu.arch) {
.x86_64 => asm volatile (
\\ movq %%rbx, (%%rax)
\\ movq %%rbp, 8(%%rax)
\\ movq %%r12, 16(%%rax)
\\ movq %%r13, 24(%%rax)
\\ movq %%r14, 32(%%rax)
\\ movq %%r15, 40(%%rax)
:
: [regs] "{rax}" (regs),
: .{ .memory = true }),
.aarch64 => asm volatile (
\\ stp x19, x20, [%[regs], #0]
\\ stp x21, x22, [%[regs], #16]
\\ stp x23, x24, [%[regs], #32]
\\ stp x25, x26, [%[regs], #48]
\\ stp x27, x28, [%[regs], #64]
\\ str x29, [%[regs], #80]
:
: [regs] "r" (regs),
: .{ .memory = true }),
else => unreachable,
}
}
/// Пройти машинный стек от текущего кадра до дна и пометить всё, на что
/// показывают слова, похожие на адреса ячеек.
noinline fn markMachineStack(heap: *Heap) Allocator.Error!void {
// Регистры сбрасываются в локальный массив, он лежит в этом же кадре,
// и дальше его читает общий цикл вместе со всем стеком.
var regs: [saved_count]usize = undefined;
spillRegisters(®s);
const top = std.mem.alignForward(usize, @intFromPtr(®s), @sizeOf(usize));
if (heap.stack_bottom == null) heap.stack_bottom = sys.stackBottom(top);
// Без дна стека скан невозможен, а сборка без скана освободила бы живое.
const bottom = heap.stack_bottom orelse return error.OutOfMemory;
var at = top;
while (at < bottom) : (at += @sizeOf(usize)) {
const word = @as(*const usize, @ptrFromInt(at)).*;
try markWord(heap, word);
}
}
/// Слово как возможный корень. Адрес засчитывается, если попадает в любое
/// место занятой ячейки, а не только на её начало: оптимизатор вправе держать
/// в регистре адрес поля `cdr`, а не самой ячейки.
pub fn markWord(heap: *Heap, word: usize) Allocator.Error!void {
const cell = heap.cellAt(word) orelse return;
if (!unvisited(heap, cell)) return;
// Тег тут неважен: пометка идёт по ячейкам, а не по значениям.
try markFrom(heap, .fromCell(cell));
}
// --- Sweep ---
/// Всё занятое и не помеченное освобождается, пометки гасятся, свободный
/// список собирается заново по возрастанию адресов.
fn sweep(heap: *Heap) usize {
var freed: usize = 0;
for (heap.cells, 0..) |*cell, i| {
if (!heap.live.isSet(i)) continue;
if (isMarked(cell)) {
setMark(cell, false);
} else {
heap.live.unset(i);
freed += 1;
}
}
heap.used -= freed;
heap.collections += 1;
heap.freed_total += freed;
heap.threadFreeList();
return freed;
}Пройдём по частям.
Пометка волной. markWave это тот же цикл, что в игрушечном примере: ячейка помечается в момент, когда попадает в рабочий стек. У ячейки ровно два поля, car и cdr, и оба просматриваются одинаково: heapCell() вернёт ячейку и для пары, и для замыкания (замыкание сложено из двух ячеек), а для числа, символа и nil вернёт null. Вот она, точность: тег сказал, и мы поверили. Одна тонкость: ячейка, снятая с рабочего стека, уже помечена, и её car несёт бит пометки. Поэтому car читается через withGcBit(false), а isMarked и setMark в начале файла это единственные места, которые знают, в каком слове живёт пометка.
Регистры. Единственная ссылка на ячейку может лежать не на стеке, а в регистре. Каком? Вспомни соглашение о вызовах из урока 14: регистры делятся на те, что сохраняет вызывающий, и те, что сохраняет вызываемый. Первые вызывающий перед вызовом сам сбросил на стек, если они ему нужны, и там их найдёт общий скан. Вторые (%rbx, %rbp, %r12 до %r15 на x86-64; x19 до x29 на arm64) могут дойти до сборщика нетронутыми через десять вызовов. Их spillRegisters складывает в локальный массив, а массив лежит в кадре markMachineStack, то есть на том же стеке, и дальше читается общим циклом. Это тот же слепок регистров, который делает setjmp из урока 51; Boehm так и поступает, зовёт setjmp. У нас libc на Linux нет, поэтому шесть инструкций movq руками.
Две мелочи, на которых я потерял время. Отладочный бэкенд Zig 0.16 для x86-64 не принимает операнд вида 0(%[regs]) с именованным входом, только регистр напрямую, поэтому вход привязан к %rax. И функция помечена noinline: если оптимизатор встроит её в вызывающую, массив regs окажется в другом кадре, и “вершина стека” съедет.
Скан. От адреса массива regs до дна стека, по слову за шаг. Каждое слово идёт в markWord, тот спрашивает у кучи cellAt, занята ли ячейка и не помечена ли уже, и запускает от неё обычную точную волну.
Дно стека. Вершину стека мы знаем: это адрес локальной переменной. Дно нужно спросить у системы. В sys.zig добавляется одна функция:
extern "c" fn pthread_get_stackaddr_np(thread: std.c.pthread_t) usize;
/// Дно стека текущего потока: старший адрес, с которого стек растёт вниз.
/// `inside` это любой адрес внутри стека, например адрес локальной переменной.
///
/// На macOS ответ знает libc. На Linux libc у нас нет, зато есть
/// `/proc/self/maps`: находим область, в которую попадает `inside`, и берём
/// её верхнюю границу. Так же поступает сборщик Boehm. Если ответа нет,
/// возвращается null, и консервативно сканировать стек нельзя.
pub fn stackBottom(inside: usize) ?usize {
if (!is_linux) return pthread_get_stackaddr_np(std.c.pthread_self());
const fd_raw = linux.open("/proc/self/maps", .{}, 0);
if (linux.errno(fd_raw) != .SUCCESS) return null;
const fd: i32 = @intCast(fd_raw);
defer _ = linux.close(fd);
// Файл читается кусками, строка может порваться на границе куска, поэтому
// разбор идёт автоматом по байту: нас интересуют только два числа в
// начале каждой строки, "начало-конец".
var chunk: [4096]u8 = undefined;
var field: enum { start, end, rest } = .start;
var start: usize = 0;
var end: usize = 0;
while (true) {
const n = linux.read(fd, &chunk, chunk.len);
if (linux.errno(n) != .SUCCESS or n == 0) return null;
for (chunk[0..n]) |ch| switch (field) {
.start => if (ch == '-') {
field = .end;
} else {
start = start * 16 + (std.fmt.charToDigit(ch, 16) catch return null);
},
.end => if (ch == ' ') {
if (start <= inside and inside < end) return end;
field = .rest;
} else {
end = end * 16 + (std.fmt.charToDigit(ch, 16) catch return null);
},
.rest => if (ch == '\n') {
field = .start;
start = 0;
end = 0;
},
};
}
}Это zt pmap из урока 54 в миниатюре: та же строка начало-конец права ..., только нужна нам одна область, та, в которую попадает наш собственный адрес. Обрати внимание на ветку отказа в markMachineStack: если дно узнать не удалось, сборка возвращает ошибку, а не продолжает без скана. Сборка без скана освободила бы живое, а это хуже, чем отказ. Дно запоминается в куче при первой сборке; для одного потока это верно, а про несколько потоков поговорим в уроке про потоки и общую кучу.
Sweep. По сравнению с книгой он стал короче. Освобождать блоки по одному и сливать соседей не нужно: гасим бит live у непомеченных, у помеченных гасим саму пометку, чтобы car снова стал обычным значением, и продеваем свободный список заново по возрастанию адресов. Это сохраняет свойство из прошлого урока: подряд выделенные ячейки лежат в памяти подряд.
Мелкие правки вокруг
В value.zig свободный бит тега получает имя и два метода. Рядом с остальными константами раскладки:
/// Свободный бит, которым пользуется сборщик мусора.
const gc_bit: u64 = 0b0010;И в конце Value:
/// Бит сборщика: стоит ли он в этом слове ячейки. Слово с поднятым битом
/// это уже не значение (nil с ним выглядит как пара по адресу ноль),
/// поэтому сборщик снимает бит, прежде чем читать слово как значение.
pub fn gcBit(self: Value) bool {
return self.bits & gc_bit != 0;
}
/// То же слово с поднятым или сброшенным битом сборщика. Вид и нагрузку
/// бит не задевает: ни у одного вида он не занят.
pub fn withGcBit(self: Value, on: bool) Value {
return .{ .bits = if (on) self.bits | gc_bit else self.bits & ~gc_bit };
}Правило «к значению ходят только через методы» держится и здесь: gc.zig не знает, какой именно бит свободен, он знает только gcBit и withGcBit.
Глобальные имена переезжают из Vm в кучу. Причина прозаическая: Vm.init возвращает Vm по значению, адрес структуры до возврата нестабилен, и хранить в куче указатель на Vm нельзя. Проще отдать карту куче, тем более что это её главный набор корней. В vm.zig исчезает поле globals и строка в deinitPartial, а два метода теперь выглядят так:
pub fn define(self: *Vm, id: SymbolId, v: Value) std.mem.Allocator.Error!void {
// Лексическое окружение это список пар в куче, а глобальное это карта:
// его ищут последним и часто. Карта лежит в куче, потому что глобальные
// имена это корни для сборщика мусора.
try self.heap.globals.put(self.gpa, id, v);
} pub fn lookupGlobal(self: *const Vm, id: SymbolId) ?Value {
return self.heap.globals.get(id);
}В читателе срез элементов списка объявляется корнем. В reader.zig, в разборе списка, сразу после defer items.deinit(self.vm.gpa);:
// Элементы лежат в памяти от аллокатора, а не на стеке, и сборщик
// мусора их там не увидит. Поэтому срез объявляется корнем.
try self.vm.heap.pushRoots(&items);
defer self.vm.heap.popRoots();Те же две строки для среза forms встают в readAll. Но у readAll остаётся ловушка: после возврата срез уже не корень, а формы в нём лежат в памяти от аллокатора. Поэтому evalSource в eval.zig перестаёт им пользоваться и читает формы по одной:
/// Прочитать исходник и вычислить все формы подряд, вернув значение последней.
pub fn evalSource(vm: *Vm, source: []const u8) SourceError!Value {
// Формы читаются по одной: прочитанная форма живёт в кадре этой функции,
// где её найдёт сборщик мусора, а не в срезе от аллокатора.
var r: reader.Reader = .init(vm, source);
var last: Value = .nil;
while (try r.next()) |form| last = try eval(vm, form, .nil);
return last;
}Это и есть единственная правка в eval.zig, ради которой затевался консервативный скан. У неё есть видимый побочный эффект: ошибка чтения в третьей форме теперь случается после вычисления первых двух, а раньше не вычислялось ничего.
Остаётся мелочь. В main.zig в printStats добавляется строка формата сборок: {d}, возвращено ячеек: {d} и пара аргументов s.collections, s.freed_total. В root.zig две строки:
pub const gc = @import("gc.zig");
pub const gc_dsw = @import("gc_dsw.zig");И в build.zig список шагов становится таким (пока не дошёл до звёздочки, "59_dsw" и строку gc_dsw в root.zig можно не добавлять, а в gc.zig убрать импорт dsw и ветку .pointer_reversal):
const steps = [_][]const u8{ "05", "06", "13", "14", "15", "19", "56", "58", "59", "59_dsw" };Последняя правка касается байткод-машины из урока про циклы и switch. Её константы и стек значений это std.ArrayList(Value) в памяти от аллокатора: сборщик их не видит, как не видел среза читателя. Константы держат ячейки тел функций, а скомпилированное тело машина находит по адресам этих ячеек. Не объяви их корнями, и сборка вернёт ячейки тела в пул, другая lambda ляжет на те же адреса и получит чужой код. Поэтому оба списка становятся корнями на всю жизнь машины, а init начинает возвращать ошибку:
/// Константы всех скомпилированных функций. Команда хранит только номер.
constants: *RootList,
/// Стек значений: аргументы, промежуточные результаты, вызванные функции.
stack: *RootList, /// Константы и стек значений лежат в памяти от аллокатора, где сборщик
/// мусора их не видит, поэтому оба списка объявлены корнями на всю жизнь
/// машины. Сами списки тоже от аллокатора: куча хранит их адреса, и они
/// не должны переезжать вместе с копией `Machine`.
pub fn init(vm: *Vm) std.mem.Allocator.Error!Machine {
const gpa = vm.gpa;
const constants = try gpa.create(RootList);
errdefer gpa.destroy(constants);
const stack = try gpa.create(RootList);
errdefer gpa.destroy(stack);
constants.* = .empty;
stack.* = .empty;
try vm.heap.pushRoots(constants);
errdefer vm.heap.popRoots();
try vm.heap.pushRoots(stack);
return .{ .vm = vm, .constants = constants, .stack = stack };
}
/// Корни снимаются в обратном порядке, поэтому машины разрушаются в
/// порядке, обратном созданию, как и всё под `defer`.
pub fn deinit(self: *Machine) void {
const gpa = self.vm.gpa;
var chunks = self.functions.valueIterator();
while (chunks.next()) |chunk| {
chunk.*.deinit(gpa);
gpa.destroy(chunk.*);
}
self.functions.deinit(gpa);
self.frames.deinit(gpa);
self.vm.heap.popRoots();
self.vm.heap.popRoots();
self.stack.deinit(gpa);
self.constants.deinit(gpa);
gpa.destroy(self.stack);
gpa.destroy(self.constants);
self.* = undefined;
}Ключ кэша тел тоже кладётся среди констант, в compileFunction перед functions.put:
// Ключ держим среди констант, то есть среди корней. Иначе сборщик
// освободил бы ячейки тела, отдал их другой `lambda`, и та нашла бы
// здесь по тем же адресам чужой код.
try self.constants.appendSlice(gpa, &.{ key.params, key.body });В bytecode.zig добавляются const heap_mod = @import("heap.zig"); и const RootList = heap_mod.RootList;, в main.zig и в тестах шагов 13 и 14 перед .init(&vm) у машины появляется try.
Тесты шага
//! Шаг 59: Mark&Sweep для cons-ячеек.
//!
//! Тесты с точными числами зовут сборщик в режиме `.precise` из безопасной
//! точки: там на исход не влияет мусор, оставшийся в мёртвых кадрах стека.
//! Консервативный режим проверяется там, где он нужен по делу: куча сама
//! зовёт его из глубины `eval`, а значения живут в кадрах Zig и в кадре кода
//! из JIT. Про него утверждаем только то, что он обязан гарантировать: живое
//! не погибает, а долгая программа укладывается в маленький пул.
const std = @import("std");
const zl = @import("zl");
const bytecode = zl.bytecode;
const eval = zl.eval;
const gc = zl.gc;
const jit = zl.jit;
const printer = zl.printer;
const programs = zl.programs;
const Heap = zl.heap.Heap;
const Value = zl.Value;
const Vm = zl.Vm;
const testing = std.testing;
fn run(vm: *Vm, source: []const u8) !void {
_ = try eval.evalSource(vm, source);
}
fn expectPrinted(vm: *Vm, v: Value, expected: []const u8) !void {
var out: std.Io.Writer.Allocating = .init(testing.allocator);
defer out.deinit();
try printer.write(&out.writer, vm, v);
try testing.expectEqualStrings(expected, out.written());
}
// --- Достижимость ---
test "сборка оставляет достижимое из глобальных имён и освобождает остальное" {
var vm: Vm = try .initWith(testing.allocator, .{ .cells = 256 });
defer vm.deinit();
try run(&vm, "(define xs (list 1 2 3))");
try run(&vm, "(list 4 5 6 7 8)");
try testing.expect(vm.heap.stats().used > 3);
const freed = try gc.collect(&vm.heap, .precise);
try testing.expect(freed > 0);
// Остался ровно список из трёх ячеек. Прочитанные формы, списки
// аргументов и второй список ушли.
try testing.expectEqual(@as(usize, 3), vm.heap.stats().used);
try expectPrinted(&vm, vm.lookupGlobal(try vm.intern("xs")).?, "(1 2 3)");
}
test "замыкание держит своё окружение" {
var vm: Vm = try .initWith(testing.allocator, .{ .cells = 256 });
defer vm.deinit();
try run(&vm, "(define make (lambda (n) (lambda (x) (+ x n))))");
try run(&vm, "(define add5 (make 5))");
_ = try gc.collect(&vm.heap, .precise);
try expectPrinted(&vm, try eval.evalSource(&vm, "(add5 37)"), "42");
}
test "циклический мусор собирается, а живой цикл не зацикливает пометку" {
var vm: Vm = try .initWith(testing.allocator, .{ .cells = 256 });
defer vm.deinit();
_ = try gc.collect(&vm.heap, .precise);
const baseline = vm.heap.stats().used;
// Две ячейки показывают друг на друга: a -> b -> a. Счётчик ссылок не
// освободил бы их никогда, у каждой ссылок всегда не меньше одной.
try run(&vm, "(define a (cons 1 nil))");
try run(&vm, "(define b (cons 2 a))");
try run(&vm, "(set-cdr! a b)");
// Пока имена живы, цикл жив, и пометка на нём останавливается.
_ = try gc.collect(&vm.heap, .precise);
try testing.expectEqual(baseline + 2, vm.heap.stats().used);
// Имена отпущены. Ячейки по-прежнему ссылаются друг на друга, но от
// корней до них не дойти.
try run(&vm, "(define a nil)");
try run(&vm, "(define b nil)");
_ = try gc.collect(&vm.heap, .precise);
try testing.expectEqual(baseline, vm.heap.stats().used);
}
test "печать кольца обрывается многоточием, а не идёт вечно" {
var vm: Vm = try .initWith(testing.allocator, .{ .cells = 256 });
defer vm.deinit();
// set-cdr! возвращает саму пару, и диалог тут же пытается её напечатать.
try run(&vm, "(define ring (list 1 2))");
const ring = try eval.evalSource(&vm, "(set-cdr! (cdr ring) ring)");
var out: std.Io.Writer.Allocating = .init(testing.allocator);
defer out.deinit();
try printer.write(&out.writer, &vm, ring);
try testing.expect(std.mem.startsWith(u8, out.written(), "(2 1 2 1 2"));
try testing.expect(std.mem.endsWith(u8, out.written(), " ...)"));
// Кольцо через car уходит в глубину, и предел там свой.
const knot = try eval.evalSource(&vm, "(define k (cons nil nil)) (set-car! k k)");
out.clearRetainingCapacity();
try printer.write(&out.writer, &vm, knot);
try testing.expect(std.mem.endsWith(u8, out.written(), "..." ++ ")" ** printer.max_depth));
}
test "пометка идёт волной, а не рекурсией: длинный список не роняет стек" {
const n = 200_000;
var vm: Vm = try .initWith(testing.allocator, .{ .cells = n + 16 });
defer vm.deinit();
var xs: Value = .nil;
for (0..n) |i| xs = try vm.heap.cons(.fromFixnum(@intCast(i)), xs);
try vm.defineNamed("xs", xs);
const freed = try gc.collect(&vm.heap, .precise);
try testing.expectEqual(@as(usize, 0), freed);
try testing.expectEqual(@as(usize, n), vm.heap.stats().used);
}
test "sweep собирает свободный список заново, по возрастанию адресов" {
var heap: Heap = try .init(testing.allocator, .{ .cells = 8 });
defer heap.deinit();
var keep: zl.heap.RootList = .empty;
defer keep.deinit(testing.allocator);
try heap.pushRoots(&keep);
// Занимаем всё, корнями объявляем ячейки 1 и 5.
for (0..8) |i| {
const cell = try heap.cons(.fromFixnum(@intCast(i)), .nil);
if (i == 1 or i == 5) try keep.append(testing.allocator, cell);
}
try testing.expectEqual(@as(usize, 6), try gc.collect(&heap, .precise));
const expected = [_]usize{ 0, 2, 3, 4, 6, 7 };
var cell = heap.free_list;
for (expected) |index| {
try testing.expectEqual(index, heap.indexOf(cell.?));
cell = if (cell.?.cdr.isCons()) cell.?.cdr.asCell() else null;
}
try testing.expect(cell == null);
const s = heap.stats();
try testing.expectEqual(@as(usize, 3), s.free_runs);
try testing.expectEqual(@as(usize, 1), s.collections);
try testing.expectEqual(@as(usize, 6), s.freed_total);
}
// --- Запуск по исчерпанию пула ---
test "долгая программа укладывается в маленький пул" {
// `fib.zl` выделяет 175 тысяч ячеек и без сборщика не помещался даже в
// 65 536. Живых из них в каждый момент меньше 256, то есть 8 КБ.
var vm: Vm = try .initWith(testing.allocator, .{ .cells = 256 });
defer vm.deinit();
const v = try eval.evalSource(&vm, programs.get("fib.zl").?.source);
try expectPrinted(&vm, v, "6765");
const s = vm.heap.stats();
try testing.expect(vm.heap.cells_allocated > 500 * s.capacity);
try testing.expect(s.collections > 500);
try testing.expect(s.peak <= 256);
// Всё, что выделено и сейчас не занято, вернул сборщик.
try testing.expectEqual(vm.heap.cells_allocated - s.used, s.freed_total);
}
test "каждая программа из каталога проходит в пуле, который меньше её аппетита" {
// `list-sum.zl` держит живым список из тысячи чисел и тысячу кадров
// нехвостовой рекурсии с окружениями, поэтому ему нужно 16 384 ячейки.
// Сборщик не уменьшает живое, он возвращает мёртвое.
for (programs.all) |program| {
var vm: Vm = try .initWith(testing.allocator, .{ .cells = 16384 });
defer vm.deinit();
try expectPrinted(&vm, try eval.evalSource(&vm, program.source), program.expected);
}
var vm: Vm = try .initWith(testing.allocator, .{ .cells = 512 });
defer vm.deinit();
const meta = programs.get("eval.zl").?;
try expectPrinted(&vm, try eval.evalSource(&vm, meta.source), meta.expected);
try testing.expect(vm.heap.collections > 0);
}
test "байткод под сборщиком: константы и стек машины это корни" {
for (programs.all) |program| {
for ([_]bytecode.Dispatch{ .loop, .labeled }) |dispatch| {
var vm: Vm = try .initWith(testing.allocator, .{ .cells = 16384 });
defer vm.deinit();
var m: bytecode.Machine = try .init(&vm);
defer m.deinit();
try expectPrinted(&vm, try m.runSource(program.source, dispatch), program.expected);
}
}
// Байткоду не нужны окружения под аргументы, поэтому fib идёт в пуле
// меньше, чем у обхода дерева, и сборка при этом случается сотни раз.
var vm: Vm = try .initWith(testing.allocator, .{ .cells = 128 });
defer vm.deinit();
var m: bytecode.Machine = try .init(&vm);
defer m.deinit();
try expectPrinted(&vm, try m.runSource(programs.get("fib.zl").?.source, .labeled), "6765");
try testing.expect(vm.heap.stats().collections > 100);
}
test "ячейки скомпилированного тела не достаются другой lambda" {
// Скомпилированное тело машина находит по адресам ячеек `lambda`, и эти
// ячейки лежат среди её констант, то есть среди корней.
var vm: Vm = try .initWith(testing.allocator, .{ .cells = 256 });
defer vm.deinit();
var m: bytecode.Machine = try .init(&vm);
defer m.deinit();
try expectPrinted(&vm, try m.runSource("((lambda (x) (+ x 1)) 0)", .loop), "1");
_ = try gc.collect(&vm.heap, .precise);
// Свободный список после сборки идёт по возрастанию адресов. Будь первая
// форма освобождена, вторая того же вида легла бы в те же ячейки, машина
// нашла бы по ним старое тело и вернула бы единицу.
try expectPrinted(&vm, try m.runSource("((lambda (x) (+ x 2)) 0)", .loop), "2");
}
test "когда живого больше, чем пул, сборка не спасает" {
var vm: Vm = try .initWith(testing.allocator, .{ .cells = 64 });
defer vm.deinit();
try run(&vm, "(define grow (lambda (n acc) (cond ((= n 0) acc) (t (grow (- n 1) (cons n acc))))))");
try testing.expectError(error.OutOfMemory, eval.evalSource(&vm, "(grow 1000 nil)"));
try testing.expect(vm.heap.collections > 0);
}
test "значение, которое держит только кадр Zig, переживает сборку" {
var vm: Vm = try .initWith(testing.allocator, .{ .cells = 64 });
defer vm.deinit();
// Ни глобального имени, ни явного корня: про `kept` знает только стек.
const kept = try vm.heap.cons(.fromFixnum(42), .nil);
for (0..10_000) |i| _ = try vm.heap.cons(.fromFixnum(@intCast(i)), .nil);
try testing.expect(vm.heap.collections > 100);
try testing.expectEqual(@as(i64, 42), kept.asCell().car.asFixnum());
try testing.expect(vm.heap.live.isSet(vm.heap.indexOf(kept.asCell())));
}
// --- Консервативный режим ---
test "слово считается корнем, если попадает внутрь занятой ячейки" {
var heap: Heap = try .init(testing.allocator, .{ .cells = 8 });
defer heap.deinit();
const a = try heap.cons(.fromFixnum(1), .nil);
const b = try heap.cons(.fromFixnum(2), a);
const c = try heap.cons(.fromFixnum(3), .nil);
const free_cell = heap.free_list.?;
// Адрес поля cdr, а не начала ячейки: тоже корень, и тянет за собой `a`.
try gc.markWord(&heap, @intFromPtr(&b.asCell().cdr));
// Адрес свободной ячейки, адрес вне пула и просто число: не корни.
try gc.markWord(&heap, @intFromPtr(free_cell));
try gc.markWord(&heap, @intFromPtr(&heap));
try gc.markWord(&heap, 12345);
try testing.expect(gc.isMarked(a.asCell()));
try testing.expect(gc.isMarked(b.asCell()));
try testing.expect(!gc.isMarked(c.asCell()));
try testing.expect(!gc.isMarked(free_cell));
// Пометка это бит в слове car, а само значение в car не изменилось.
try testing.expectEqual(@as(i64, 2), b.asCell().car.withGcBit(false).asFixnum());
for ([_]Value{ a, b }) |v| gc.setMark(v.asCell(), false);
}
/// Строит мусорный список и возвращает адрес его головы как голое число.
/// Отдельной функцией, чтобы значения-пары остались в её мёртвом кадре.
noinline fn garbageAddress(heap: *Heap) !usize {
var xs: Value = .nil;
for (0..10) |i| xs = try heap.cons(.fromFixnum(@intCast(i)), xs);
return @intFromPtr(xs.asCell());
}
test "ложное удержание: число на стеке, похожее на адрес, держит мусор" {
var heap: Heap = try .init(testing.allocator, .{ .cells = 64 });
defer heap.deinit();
// Это не указатель, а целое число. Оно могло бы быть хешем, длиной
// или куском строки: сборщик отличить не может и обязан перестраховаться.
var lookalike: usize = try garbageAddress(&heap);
const word: *volatile usize = &lookalike;
_ = try gc.collect(&heap, .conservative);
// Голова списка удержана, а за ней и все десять ячеек.
try testing.expectEqual(@as(usize, 10), heap.stats().used);
try testing.expect(heap.cellAt(word.*) != null);
// Точный режим стек не читает, и мусор уходит.
_ = try gc.collect(&heap, .precise);
try testing.expectEqual(@as(usize, 0), heap.stats().used);
}
// --- Сборка под работающим JIT ---
const Word = jit.Value;
fn toValue(w: Word) Value {
if (w == jit.nil) return .nil;
if (jit.isFixnum(w)) return .fromFixnum(jit.fixnumOf(w));
return .fromCell(@ptrFromInt(w));
}
/// `cons` для кода из JIT. Ячейка пула выровнена на шестнадцать, её адрес
/// кончается четырьмя нулями, а нулевой тег это пара и в представлении JIT.
fn consPrim(vm: *Vm, a: Word, b: Word) callconv(.c) Word {
const cell = vm.heap.cons(toValue(a), toValue(b)) catch return jit.nil;
return @intFromPtr(cell.asCell());
}
var churn_scan: gc.Scan = .conservative;
/// Намусорить на четыре пула. В обычном режиме куча соберёт себя сама,
/// консервативно. В режиме `.precise` сборку зовём руками, без скана стека:
/// так выглядел бы сборщик, который про кадры JIT не знает.
fn churnPrim(vm: *Vm, a: Word, b: Word) callconv(.c) Word {
_ = b;
if (churn_scan == .precise) _ = gc.collect(&vm.heap, .precise) catch return jit.nil;
for (0..vm.heap.cells.len * 4) |_| {
_ = vm.heap.cons(.fromFixnum(-1), .nil) catch return jit.nil;
if (churn_scan == .precise and vm.heap.free_list == null) {
_ = gc.collect(&vm.heap, .precise) catch return jit.nil;
}
}
return a;
}
/// Достать `car` из ячейки пула обратно в представление JIT.
fn carPrim(vm: *Vm, a: Word, b: Word) callconv(.c) Word {
_ = vm;
_ = b;
const cell: *zl.value.Cell = @ptrFromInt(a);
return if (cell.car.tag() == .fixnum) jit.fixnum(cell.car.asFixnum()) else jit.nil;
}
// (car* (cons x x) (churn x x)): пара создаётся первой и ждёт во временном
// слоте кадра JIT, пока churn перемалывает пул. Кроме этого слота, на пару
// не ссылается никто.
const jit_param: jit.Expr = .param;
const jit_pair: jit.Expr = .{ .call = .{ .prim = &consPrim, .a = &jit_param, .b = &jit_param } };
const jit_churn: jit.Expr = .{ .call = .{ .prim = &churnPrim, .a = &jit_param, .b = &jit_param } };
const jit_keep: jit.Expr = .{ .call = .{ .prim = &carPrim, .a = &jit_pair, .b = &jit_churn } };
test "пара из кадра JIT переживает сборку благодаря скану стека" {
if (!jit.canRun()) return error.SkipZigTest;
var vm: Vm = try .initWith(testing.allocator, .{ .cells = 64 });
defer vm.deinit();
var code = try jit.jit(&jit_keep);
defer code.deinit();
churn_scan = .conservative;
const result = code.body()(&vm, jit.fixnum(7));
try testing.expect(vm.heap.collections >= 4);
try testing.expectEqual(@as(i64, 7), jit.fixnumOf(result));
}
test "без скана стека та же пара погибает, и код из JIT читает чужую ячейку" {
if (!jit.canRun()) return error.SkipZigTest;
var vm: Vm = try .initWith(testing.allocator, .{ .cells = 64 });
defer vm.deinit();
var code = try jit.jit(&jit_keep);
defer code.deinit();
churn_scan = .precise;
defer churn_scan = .conservative;
const result = code.body()(&vm, jit.fixnum(7));
// Ячейку освободили, пока код из JIT на неё рассчитывал. Что в ней теперь,
// зависит от того, кто успел последним: звено свободного списка (тогда
// car это nil) или чужая пара с -1. Семёрки там нет в обоих случаях.
try testing.expect(result == jit.nil or jit.fixnumOf(result) == -1);
}$ zig build test -Dstep=59 --summary all
Build Summary: 5/5 steps succeeded; 40/42 tests passed (2 skipped)
test success
+- run test 26 pass (26 total) 325ms MaxRSS:4M
+- run test 14 pass, 2 skip (16 total) 1s MaxRSS:8MЭто macOS на Apple M4 Max; пропущены два теста, которые прыгают в машинный код x86-64. В контейнере linux/amd64 проходят все шестнадцать.
На что посмотреть в тестах.
Точные числа только в точном режиме. Тест про достижимость утверждает, что после сборки занято ровно три ячейки. Такое можно обещать только в режиме .precise и только из безопасной точки. В консервативном режиме в мёртвых кадрах стека лежат старые значения от прошлых вызовов, и сколько мусора они удержат, зависит от компилятора, режима сборки и платформы. Про консервативный режим тесты утверждают только то, что он обязан гарантировать: живое не погибает, а долгая программа укладывается в маленький пул.
Циклический мусор. a показывает на b через set-cdr!, b на a. Пока имена живы, кольцо живо, и пометка на нём не зацикливается. После (define a nil) и (define b nil) число занятых ячеек возвращается ровно к исходному. Подсчёт ссылок это кольцо не освободил бы никогда.
Ложное удержание, воспроизведённое нарочно. garbageAddress строит список из десяти ячеек и возвращает адрес головы как голое usize. Для компилятора это число, не указатель. Консервативная сборка удерживает все десять ячеек, точная освобождает все десять. Это сценарий “Ложный указатель” из виджета, только на твоей машине. Функция помечена noinline, а переменная читается через volatile, иначе оптимизатор вправе вообще не класть число на стек.
Байткод под сборщиком. Все программы проходят у обоих диспетчеров в пуле на 16 384 ячейки, а fib.zl под labeled switch даже в 128 ячейках, со счётом сборок за сотню: байткоду не нужны окружения под аргументы, и живого у него меньше, чем у обхода дерева. Второй тест ловит ошибку, о которой шла речь выше: без констант среди корней вторая lambda получила бы тело первой и вернула бы единицу вместо двойки.
Пара в кадре JIT. Самый интересный тест. Выражение (car* (cons x x) (churn x x)) компилируется в машинный код. Пара создаётся первой и ждёт во временном слоте кадра, по адресу -24(%rbp), пока churn четырежды перемалывает пул на 64 ячейки. Кроме этого слота, на пару не ссылается никто: ни глобальное имя, ни список корней, ни кадр Zig. Со сканом стека ответ 7. Второй тест зовёт сборку в режиме .precise, как поступил бы сборщик, не знающий про кадры JIT: пара погибает, и код читает чужую ячейку. Что в ней окажется, зависит от того, кто успел последним: nil, если ячейка стала звеном свободного списка, или -1, если её уже выдали мусорной паре. Тест принимает оба исхода. Вот так выглядит использование освобождённой памяти изнутри: не падение, а тихо неверный ответ. Ко второй половине урока это лучший мост.
Что получилось
$ zl --cells 256 --stats programs/fib.zl
6765
пул: 256 ячеек, 4 КБ
занято: 175, свободно: 81, пик: 256
выделено за прогон: 175159
сборок: 1341, возвращено ячеек: 174984
свободных участков: 8, самый длинный: 53, раздробленность: 0.35
$ zl --cells 128 --stats programs/fib.zl
ошибка: OutOfMemory
error: OutOfMemory
$ zl --cells 4096 programs/list-sum.zl
ошибка: OutOfMemory
error: OutOfMemoryБыло 2,7 МБ, стало 4 КБ, и 175 159 выделений прошли через 256 ячеек за 1341 сборку. Это macOS arm64, сборка ReleaseFast. В контейнере linux/amd64 та же программа даёт 1771 сборку и 216 занятых ячеек на выходе: на другом стеке лежит другой мусор, и консервативный скан находит другие ложные корни. Не жди совпадения до единицы и на своей машине. А вот выделено за прогон: 175159 совпадает везде, это свойство программы, а не сборщика.
Два отказа внизу тоже важны. В 128 ячеек fib.zl не помещается: глубина рекурсии 20, у каждого вызова окружение и список аргументов, и живого в пике больше 128. А list-sum.zl держит живым список из тысячи чисел и тысячу кадров нехвостовой рекурсии, ему нужно около восьми тысяч ячеек при любом сборщике (в ReleaseFast хватает 8000, в Debug не хватает и 8192: у отладочных кадров больше слотов со старыми значениями). Сборщик не уменьшает живое, он возвращает мёртвое.
Со звёздочкой: пометка без стека
Вернёмся к слабому месту: рабочий стек пометки в худшем случае занимает слово на ячейку, и просить эту память приходится ровно тогда, когда памяти нет. В 1967 году Шорр и Уэйт (и независимо Дойч) придумали, как обойти граф вообще без дополнительной памяти. Идея: путь назад хранится в самих ячейках.
Уходя из ячейки вглубь через поле, записываем в это поле ссылку на ту ячейку, из которой пришли. Получается цепочка развёрнутых указателей от текущей ячейки до корня: это и есть стек, только вплетённый в граф. Возвращаясь, кладём в поле то, что там лежало, и идём дальше. Нужен один лишний бит на ячейку: через какое из двух полей мы ушли, car или cdr. Памяти он тоже не просит. В слове car свободный бит тега уже занят пометкой, а в слове cdr он свободен, туда и кладём флаг «развёрнут cdr». Развёрнутое поле при этом хранит не своё значение, а ссылку назад, так что флаг едет вместе с ней и исчезает, когда поле возвращается на место.
Проследи на списке (1 2), это две ячейки: A = (1 . B), B = (2 . nil). Держим две переменные, prev и cur. Начало: prev = nil, cur = A, помечаем A. В car у A число, идти некуда. В cdr лежит B, она не помечена: пишем в A.cdr значение prev (то есть nil) с поднятым флагом, сдвигаемся: prev = A, cur = B, помечаем B. У B оба поля не ячейки: назад. Смотрим на prev, это A, в A.cdr стоит флаг, значит, уходили через cdr: читаем оттуда сохранённый путь (nil), кладём в A.cdr обратно B без флага, сдвигаемся: cur = A, prev = nil. У A оба поля уже помечены, обходить нечего, prev пуст: конец. Граф снова цел.
Листинг gc_dsw.zig и тесты
//! Пометка без стека: алгоритм Дойча, Шорра и Уэйта.
//!
//! Волне из `gc.zig` нужен рабочий стек, в худшем случае по слову на ячейку,
//! и просить эту память приходится ровно тогда, когда памяти нет. Разворот
//! указателей обходится без неё: путь назад хранится в самих ячейках. Уходя
//! вглубь через поле, мы записываем в это поле ссылку на предыдущую ячейку,
//! а возвращаясь, кладём на место то, что там было. Нужен один лишний бит на
//! ячейку: через какое из двух полей мы ушли. Отдельной памяти он не просит.
//! Это тот же свободный бит тега, что под пометкой, только в слове `cdr`:
//! пометка стоит в `car`, флаг "развёрнут cdr" в `cdr`.
//!
//! Пока идёт пометка, граф сломан: развёрнутые поля показывают назад. Поэтому
//! алгоритм годится только для сборки с остановкой мира.
const std = @import("std");
const gc = @import("gc.zig");
const Heap = @import("heap.zig").Heap;
const Value = @import("value.zig").Value;
fn wanted(heap: *const Heap, v: Value) bool {
const cell = v.heapCell() orelse return false;
return gc.unvisited(heap, cell);
}
/// Пометить всё достижимое из `root`. Корень обязан быть непомеченной ячейкой.
pub fn mark(heap: *Heap, root: Value) void {
// Значения ходят по кругу целиком, вместе с тегом: на обратном пути в поле
// возвращается ровно то значение, которое там лежало, пара или замыкание.
var prev: Value = .nil;
var cur: Value = root;
gc.setMark(cur.heapCell().?, true);
while (true) {
const cell = cur.heapCell().?;
// В `car` стоит пометка, значение из него читается со снятым битом.
const head = cell.car.withGcBit(false);
if (wanted(heap, head)) {
// Вглубь через car: поле теперь показывает назад, пометка на месте.
cell.car = prev.withGcBit(true);
prev = cur;
cur = head;
gc.setMark(cur.heapCell().?, true);
continue;
}
if (wanted(heap, cell.cdr)) {
// Вглубь через cdr, и бит в том же слове запоминает, что развёрнут
// именно он.
const next = cell.cdr;
cell.cdr = prev.withGcBit(true);
prev = cur;
cur = next;
gc.setMark(cur.heapCell().?, true);
continue;
}
// Здесь делать больше нечего: назад.
const parent = prev.heapCell() orelse return;
if (parent.cdr.gcBit()) {
// Уходили через cdr: вернуть его на место, флаг уходит вместе с
// развёрнутым словом. Оба поля родителя теперь помечены, и на
// следующем круге он сам отправит нас дальше назад.
const saved = parent.cdr.withGcBit(false);
parent.cdr = cur;
cur = prev;
prev = saved;
} else {
// Уходили через car: вернуть его, не потеряв пометку родителя.
// У родителя ещё остался cdr.
const saved = parent.car.withGcBit(false);
parent.car = cur.withGcBit(true);
cur = prev;
prev = saved;
}
}
}Включается настройкой .marker = .pointer_reversal при создании кучи. Тесты сверяют разворот указателей с волной бит в бит:
//! Шаг 59 со звёздочкой: пометка без стека по Дойчу, Шорру и Уэйту.
//!
//! Два требования. Пометить ровно то же множество ячеек, что и волна со
//! стеком. И вернуть граф в исходное состояние: алгоритм на ходу переписывает
//! `car` и `cdr`, и после него каждое поле обязано показывать туда же, куда
//! показывало до.
const std = @import("std");
const zl = @import("zl");
const eval = zl.eval;
const gc = zl.gc;
const printer = zl.printer;
const programs = zl.programs;
const Cell = zl.value.Cell;
const Vm = zl.Vm;
const testing = std.testing;
/// Граф со всем, на чём разворот указателей любит спотыкаться: общий хвост,
/// цикл через car, цикл через cdr, ячейка, которая показывает сама на себя,
/// замыкание и мусор рядом.
const graph =
\\(define tail (list 1 2 3))
\\(define left (cons 0 tail))
\\(define right (cons (cons 9 tail) tail))
\\(define ring (list 1 2 3))
\\(set-cdr! (cdr (cdr ring)) ring)
\\(define knot (cons nil nil))
\\(set-car! knot knot)
\\(set-cdr! knot knot)
\\(define up (cons nil nil))
\\(set-car! up (cons up (cons up nil)))
\\(define add (lambda (n) (lambda (x) (+ x n))))
\\(define add2 (add 2))
\\(list 1 2 3 4 5)
;
fn build(marker: gc.Marker) !Vm {
var vm: Vm = try .initWith(testing.allocator, .{ .cells = 512, .marker = marker });
errdefer vm.deinit();
_ = try eval.evalSource(&vm, graph);
return vm;
}
test "разворот указателей помечает то же, что волна, и возвращает граф на место" {
var wave = try build(.stack);
defer wave.deinit();
var reversal = try build(.pointer_reversal);
defer reversal.deinit();
// Обе кучи строились одной программой, значит раскладка ячеек совпадает.
const before = try testing.allocator.dupe(Cell, reversal.heap.cells);
defer testing.allocator.free(before);
const freed_wave = try gc.collect(&wave.heap, .precise);
const freed_reversal = try gc.collect(&reversal.heap, .precise);
try testing.expect(freed_wave > 0);
try testing.expectEqual(freed_wave, freed_reversal);
try testing.expect(wave.heap.live.eql(reversal.heap.live));
// Каждая выжившая ячейка побайтно та же, что до сборки.
for (reversal.heap.cells, before, 0..) |now, was, i| {
if (!reversal.heap.live.isSet(i)) continue;
try testing.expect(now.car.eql(was.car));
try testing.expect(now.cdr.eql(was.cdr));
}
// Служебные биты за собой убраны: ни пометок, ни флагов разворота.
for (reversal.heap.cells) |cell| {
try testing.expect(!cell.car.gcBit());
try testing.expect(!cell.cdr.gcBit());
}
}
test "стеку пометки память не нужна вовсе" {
var vm = try build(.pointer_reversal);
defer vm.deinit();
_ = try gc.collect(&vm.heap, .precise);
try testing.expectEqual(@as(usize, 0), vm.heap.mark_stack.capacity);
}
test "длинный список помечается без стека и без рекурсии" {
const n = 200_000;
var vm: Vm = try .initWith(testing.allocator, .{ .cells = n + 16, .marker = .pointer_reversal });
defer vm.deinit();
var xs: zl.Value = .nil;
for (0..n) |i| xs = try vm.heap.cons(.fromFixnum(@intCast(i)), xs);
try vm.defineNamed("xs", xs);
try testing.expectEqual(@as(usize, 0), try gc.collect(&vm.heap, .precise));
try testing.expectEqual(@as(i64, n - 1), xs.asCell().car.asFixnum());
}
test "программы проходят в маленьком пуле и с этим обходом" {
for (programs.all) |program| {
var vm: Vm = try .initWith(testing.allocator, .{ .cells = 16384, .marker = .pointer_reversal });
defer vm.deinit();
const v = try eval.evalSource(&vm, program.source);
var out: std.Io.Writer.Allocating = .init(testing.allocator);
defer out.deinit();
try printer.write(&out.writer, &vm, v);
try testing.expectEqualStrings(program.expected, out.written());
}
// И главный потребитель: `fib.zl` в 256 ячейках, полторы тысячи сборок.
var vm: Vm = try .initWith(testing.allocator, .{ .cells = 256, .marker = .pointer_reversal });
defer vm.deinit();
const v = try eval.evalSource(&vm, programs.get("fib.zl").?.source);
try testing.expectEqual(@as(i64, 6765), v.asFixnum());
try testing.expect(vm.heap.collections > 500);
}$ zig build test -Dstep=59_dsw --summary all
...
+- run test 4 pass (4 total)Плата за ноль дополнительной памяти двойная. Каждая ячейка посещается до трёх раз, и в неё пишут не только пометку, но и оба поля по очереди. И пока идёт пометка, граф сломан: развёрнутые поля показывают назад, и читать кучу в это время нельзя никому. Поэтому алгоритм годится только для сборки с остановкой мира и в современных сборщиках почти не встречается. Но как упражнение на указатели он не имеет равных.
Десять ошибок с памятью
Вторая половина урока про мир без сборщика. В книге глава про виртуальную память заканчивается списком из десяти ошибок, которые программисты на C делают с памятью десятилетиями. Список стоит знать наизусть: девять из десяти уязвимостей, о которых ты читаешь в новостях, это один из его пунктов.
Устроим честный эксперимент. Каждую ошибку покажу на C, коротко, как в оригинале. Для пяти самых коварных приведу настоящий вывод valgrind и ASan. Потом попробуем сделать ту же глупость на Zig и посмотрим, что выйдет в трёх режимах сборки. Условия опытов:
- C:
gcc 12.2.0,valgrind 3.19.0, Debian 12 в контейнереlinux/amd64на Apple M4 Max (под эмуляцией; адреса в отчётах от этого не страдают, а время нам не нужно). - Zig: 0.16.0, macOS arm64, та же машина. Трассы стека в выводах я сократил до первой строки и убрал из путей каталог.
Сначала два инструмента, без которых на C работать нельзя.
Valgrind (Memcheck) исполняет твою программу на синтетическом процессоре: каждая инструкция разбирается и переводится в код, который делает то же самое, но попутно ведёт теневую память. На каждый бит программы приходится бит “определён ли он”, на каждый байт кучи бит “можно ли к нему обращаться”. Перекомпиляция не нужна, работает с любым бинарником. Цена: замедление в 20 до 50 раз.
AddressSanitizer (ASan) это ключ компилятора -fsanitize=address. Компилятор сам вставляет проверку перед каждым обращением к памяти, а подменённый malloc окружает каждый блок отравленными “красными зонами” и держит освобождённые блоки в карантине, не выдавая их заново. Теневая память грубее: байт на восемь байт программы. Замедление примерно вдвое, поэтому с ASan гоняют тесты постоянно. Неинициализированные чтения он не видит (для них отдельный MemorySanitizer, только в clang).
1. Разыменование плохого указателя
int val;
scanf("%d", val); /* нужно &val */scanf получил содержимое val вместо адреса и запишет введённое число по этому “адресу”. Если повезёт, там неотображённая страница, и программа упадёт сразу. Если нет, запись пройдёт в чужие данные, и последствия всплывут через час в другом модуле. Современный gcc ловит именно этот случай предупреждением о формате, но только потому, что знает scanf в лицо.
В Zig число и указатель это разные типы, и неявного перехода между ними нет:
const std = @import("std");
fn readNumber(into: *i64) void {
into.* = 42;
}
pub fn main() void {
var val: i64 = 0;
readNumber(val);
std.debug.print("{d}\n", .{val});
}$ zig build-exe b01_badptr.zig
b01_badptr.zig:9:16: error: expected type '*i64', found 'i64'
readNumber(val);
^~~Сделать из числа указатель можно, но только явно, через @ptrFromInt, и это слово потом легко найти поиском.
Родственная беда это NULL. В C любой указатель может оказаться нулевым, и тип об этом молчит. В Zig обычный указатель *T нулевым быть не может, а тот, что может, имеет другой тип, ?*T, и без проверки не разыменовывается:
const std = @import("std");
const Node = struct { value: u32, next: ?*Node };
fn second(head: *Node) u32 {
return head.next.?.value;
}
pub fn main(init: std.process.Init) !void {
var buf: [256]u8 = undefined;
var w = std.Io.File.stdout().writer(init.io, &buf);
const out = &w.interface;
var only: Node = .{ .value = 7, .next = null };
try out.print("{d}\n", .{second(&only)});
try out.flush();
}Оператор .? это утверждение “здесь не null”. Что будет, если соврать:
$ zig build-exe b01_optional.zig && ./b01_optional # Debug
thread 6735074 panic: attempt to use null value
b01_optional.zig:6:21: 0x104f9a5b3 in second (b01_optional)
return head.next.?.value;
^
$ zig build-exe -O ReleaseSafe b01_optional.zig && ./b01_optional
thread 6735202 panic: attempt to use null value
$ zig build-exe -O ReleaseFast b01_optional.zig && ./b01_optional; echo $?
139В Debug и ReleaseSafe паника с точной строкой. В ReleaseFast проверки нет, программа разыменовывает нулевой указатель и погибает от сигнала, как программа на C (139 это 128 плюс 11, SIGSEGV). Запомни эту картину, она повторится: ReleaseFast превращает Zig в C. Проверки безопасности в нём выключены, и всё, что они ловили, становится неопределённым поведением. Правильный способ жить с ?*T это не .?, а if (head.next) |next| или orelse: тогда ветка для null написана явно, и врать не приходится.
2. Чтение неинициализированной памяти
#include <stdio.h>
#include <stdlib.h>
int main(void) {
int n = 4;
long *y = malloc(n * sizeof(long));
for (int i = 0; i < n; i++)
y[i] += i; /* y[i] никто не обнулял */
if (y[3] > 100)
printf("много\n");
free(y);
return 0;
}malloc память не обнуляет, в отличие от calloc. Свежая страница от ядра действительно придёт нулевой, поэтому в маленьком тесте ошибка не видна. А в живой программе блок уже побывал в употреблении, и в нём лежит то, что оставил прошлый хозяин.
$ gcc -g -O0 -o uninit uninit.c && ./uninit; echo $?
0
$ valgrind ./uninit
==17== Conditional jump or move depends on uninitialised value(s)
==17== at 0x1091D8: main (uninit.c:9)
==17==
==17== Use --track-origins=yes to see where uninitialised values come from
==17== ERROR SUMMARY: 1 errors from 1 contexts (suppressed: 0 from 0)
$ gcc -g -O0 -fsanitize=address -o uninit.asan uninit.c && ./uninit.asan; echo $?
0Обрати внимание, на что именно ругается valgrind. Не на y[i] += i: складывать мусор с числом можно сколько угодно, Memcheck просто протащит биты “не определено” через сложение. Он ругается на if, в тот момент, когда от мусора начинает зависеть поведение программы. ASan промолчал: это не его класс ошибок.
В Zig неинициализированная память называется по имени: undefined. И в режимах с проверками компилятор заполняет её байтом 0xaa:
const std = @import("std");
pub fn main(init: std.process.Init) !void {
var buf: [256]u8 = undefined;
var w = std.Io.File.stdout().writer(init.io, &buf);
const out = &w.interface;
const y = try init.gpa.alloc(u64, 4);
defer init.gpa.free(y);
var local: u32 = undefined;
const peek: *volatile u32 = &local;
try out.print("y[0] = 0x{x}\n", .{y[0]});
try out.print("local = 0x{x}\n", .{peek.*});
try out.flush();
}$ zig build-exe b02_uninit.zig && ./b02_uninit # Debug
y[0] = 0xaaaaaaaaaaaaaaaa
local = 0xaaaaaaaa
$ zig build-exe -O ReleaseSafe b02_uninit.zig && ./b02_uninit
y[0] = 0xaaaaaaaaaaaaaaaa
local = 0xaaaaaaaa
$ zig build-exe -O ReleaseFast b02_uninit.zig && ./b02_uninit
y[0] = 0x00
local = 0x0Почему именно 0xaa? Это 10101010 в двоичной записи. Как указатель 0xaaaaaaaaaaaaaaaa неканоничен на x86-64 (вспомни урок 53: старшие 16 бит обязаны повторять 47-й) и даёт сбой при первом же разыменовании. Как число оно огромно и бросается в глаза в отладчике. Как длина оно не пройдёт ни одну проверку границ. Важно понимать, что это не обнаружение, а отрава: Zig не говорит “ты прочитал undefined”, он делает так, чтобы последствия были громкими и узнаваемыми. В ReleaseFast отравы нет, и ты читаешь нули от свежей страницы, ровно как в C. Присмотрись к первой строке: ноль напечатан как 0x00, с лишней цифрой. Чтение undefined в этом режиме это неопределённое поведение, и оптимизатор вправе собрать вокруг него любой код, в том числе такой, где форматирование числа идёт не по той ветке. Мелочь, но хорошо показывает, что “прочитаю мусор, ничего страшного” это неверная модель.
3. Переполнение буфера на стеке
char buf[64];
gets(buf); /* длину ввода никто не проверяет */Про это был целый урок 16: gets пишет, пока не встретит перевод строки, и длинная строка затирает адрес возврата. В Zig у среза есть длина, и индексация её проверяет:
const std = @import("std");
fn copyLine(dst: []u8, src: []const u8) void {
for (src, 0..) |byte, i| dst[i] = byte;
}
pub fn main(init: std.process.Init) !void {
var buf: [256]u8 = undefined;
var w = std.Io.File.stdout().writer(init.io, &buf);
const out = &w.interface;
var canary: u64 = 0x1122334455667788;
var line: [8]u8 = undefined;
const watch: *volatile u64 = &canary;
copyLine(&line, "sixteen bytes!!!");
try out.print("canary = 0x{x}\n", .{watch.*});
try out.flush();
}$ ./b03_stack # Debug и ReleaseSafe
thread 6719069 panic: index out of bounds: index 8, len 8
b03_stack.zig:4:33: 0x1005c1c6f in copyLine (b03_stack)
for (src, 0..) |byte, i| dst[i] = byte;
^
$ zig build-exe -O ReleaseFast b03_stack.zig && ./b03_stack
canary = 0x1122334455667788В ReleaseFast паники нет. Что стало с восемью лишними байтами, решил оптимизатор: canary в этом прогоне уцелела, но гарантий никаких, запись за границу массива это неопределённое поведение, и компилятор вправе как затереть соседа, так и выбросить копирование целиком. Правильный Zig здесь это @memcpy(dst[0..src.len], src) после явной проверки длины или std.mem.copyForwards со срезами равной длины: тогда проверка одна, а не на каждом байте.
4. Указатель и то, на что он показывает, разного размера
int **A = malloc(n * sizeof(int)); /* нужно sizeof(int *) */
for (int i = 0; i < n; i++)
A[i] = malloc(m * sizeof(int));На 32-битной машине int и int * одного размера, и код работал годами. На 64-битной массив указателей вдвое длиннее выделенного, и запись во вторую половину уходит за блок, в заголовок соседа. Программа упадёт позже, внутри free, и отладка начнётся не с того места.
В Zig эту ошибку негде сделать: размер в байтах руками не пишется.
const a = try gpa.alloc([]u32, n); // n срезов, размер посчитает компилятор
for (a) |*row| row.* = try gpa.alloc(u32, m);alloc(T, n) принимает тип и число элементов и возвращает срез []T с длиной. Перепутать u32 и []u32 можно, но тогда не сойдутся типы в следующей же строке.
5. Ошибка на единицу
#include <stdlib.h>
int main(void) {
int n = 4;
long *a = malloc(n * sizeof(long));
for (int i = 0; i <= n; i++) /* должно быть i < n */
a[i] = i;
free(a);
return 0;
}$ ./offbyone; echo $?
0
$ valgrind ./offbyone
==31== Invalid write of size 8
==31== at 0x10918F: main (offbyone.c:7)
==31== Address 0x4a39060 is 0 bytes after a block of size 32 alloc'd
==31== at 0x48417B4: malloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==31== by 0x109168: main (offbyone.c:5)
$ ./offbyone.asan
==37==ERROR: AddressSanitizer: heap-buffer-overflow on address 0x603000000060 at pc 0x5555555551e1 bp 0x7ffffffcab90 sp 0x7ffffffcab88
WRITE of size 8 at 0x603000000060 thread T0
#0 0x5555555551e0 in main /tmp/w/offbyone.c:7
0x603000000060 is located 0 bytes to the right of 32-byte region [0x603000000040,0x603000000060)
allocated by thread T0 here:
#1 0x555555555198 in main /tmp/w/offbyone.c:5
0x0c067fff8000: fa fa 00 00 00 fa fa fa 00 00 00 00[fa]fa fa faБез инструментов программа завершилась с кодом 0: запись попала в заголовок следующего блока или в хвост кучи, и на этот раз обошлось. Оба инструмента говорят одно и то же, каждый на своём языке: запись на 0 байт правее блока в 32 байта, блок выделен в строке 5. В последней строке отчёта ASan видна сама теневая память: 00 это восемь доступных байт, fa это красная зона, квадратные скобки вокруг байта, в который пришлась запись.
На Zig:
const std = @import("std");
pub fn main(init: std.process.Init) !void {
var buf: [256]u8 = undefined;
var w = std.Io.File.stdout().writer(init.io, &buf);
const out = &w.interface;
const n: usize = 4;
const a = try init.gpa.alloc(u64, n);
defer init.gpa.free(a);
var i: usize = 0;
while (i <= n) : (i += 1) a[i] = i;
try out.print("a[3] = {d}\n", .{a[3]});
try out.flush();
}$ ./b05_offbyone # Debug и ReleaseSafe
thread 6719517 panic: index out of bounds: index 4, len 4
b05_offbyone.zig:13:32: 0x100fb1b5b in main (b05_offbyone)
while (i <= n) : (i += 1) a[i] = i;
^
$ zig build-exe -O ReleaseFast b05_offbyone.zig && ./b05_offbyone
a[3] = 3Чтобы ошибиться, мне пришлось писать цикл while со счётчиком руками. Идиоматичный for (a, 0..) |*item, i| перебирает ровно элементы среза, и единице просто неоткуда взяться.
6. Указатель вместо объекта
int *binheapDelete(int **binheap, int *size) {
int *packet = binheap[0];
binheap[0] = binheap[*size - 1];
*size--; /* нужно (*size)-- */
heapify(binheap, *size, 0);
return packet;
}Унарные * и -- в C имеют равный приоритет и применяются справа налево, поэтому *size-- уменьшает сам указатель, а не число, на которое он показывает. Компилятор молчит: выражение законно. Размер кучи не изменился, а size теперь показывает на соседнее слово стека вызывающего.
В Zig эта ошибка непредставима дважды. Оператора -- нет, уменьшение пишется как size.* -= 1, и разыменование стоит после имени, так что спорить о приоритетах не с чем. И арифметика над указателем на один объект, *usize, запрещена вовсе: size -= 1 не скомпилируется.
7. Непонимание арифметики указателей
int *search(int *p, int val) {
while (*p && *p != val)
p += sizeof(int); /* нужно p++ */
return p;
}Арифметика указателей в C считает в элементах, а не в байтах: p += 4 для int * это шаг на 16 байт. Функция проверяет каждый четвёртый элемент и уходит за конец массива.
В Zig арифметика разрешена только для указателя на много элементов, [*]T, и устроена так же, так что ошибиться можно:
const std = @import("std");
pub fn main(init: std.process.Init) !void {
var buf: [256]u8 = undefined;
var w = std.Io.File.stdout().writer(init.io, &buf);
const out = &w.interface;
const data = [_]u32{ 10, 20, 30, 40, 50, 60, 70, 80 };
var p: [*]const u32 = &data;
p += 1;
try out.print("p += 1 показывает на {d}\n", .{p[0]});
p += @sizeOf(u32);
try out.print("p += @sizeOf(u32) показывает на {d}\n", .{p[0]});
try out.flush();
}$ ./b07_ptrarith # все три режима
p += 1 показывает на 20
p += @sizeOf(u32) показывает на 60Проверок тут нет ни в одном режиме: у [*]T нет длины, сверять не с чем. Поэтому такой указатель в Zig это инструмент для стыка с C и для самого низа аллокаторов, а во всём остальном коде живут срезы. Сам факт, что для опасной арифметики нужен отдельный тип, уже половина защиты: в рецензии [*] видно издалека.
8. Ссылка на переменную, которой уже нет
#include <stdio.h>
long *stackref(void) {
long val = 0x1111;
long *p = &val;
return p; /* кадр умрёт раньше указателя */
}
long overwrite(void) {
volatile long junk[4] = {0x2222, 0x2222, 0x2222, 0x2222};
return junk[0] + junk[3];
}
int main(void) {
long *p = stackref();
overwrite();
printf("*p = 0x%lx\n", *p);
return 0;
}$ gcc -g -O0 -o stackref stackref.c && ./stackref
*p = 0x2222
$ valgrind ./stackref
==71== Use of uninitialised value of size 8
==71== at 0x48A5A42: _itoa_word (_itoa.c:178)
==71== by 0x48A665A: printf (printf.c:33)
==71== by 0x1091D7: main (stackref.c:17)
*p = 0x2222
$ ./stackref.asan
*p = 0x1111
$ ASAN_OPTIONS=detect_stack_use_after_return=1 ./stackref.asan
==13==ERROR: AddressSanitizer: stack-use-after-return on address 0x7ffffce00020 at pc 0x5555555553e2 bp 0x7ffffffcaae0 sp 0x7ffffffcaad8
READ of size 8 at 0x7ffffce00020 thread T0
#0 0x5555555553e1 in main /tmp/w/stackref.c:17
Address 0x7ffffce00020 is located in stack of thread T0 at offset 32 in frame
#0 0x5555555551c8 in stackref /tmp/w/stackref.c:3Кадр stackref умер, на его месте побывал кадр overwrite, и по старому адресу лежит 0x2222. Это самая плохо ловимая ошибка из десяти. Valgrind что-то почуял, но отчёт ведёт в недра printf и говорит про неинициализированное значение: стек для Memcheck это просто память, которая снова стала “не определена”. ASan по умолчанию не заметил ничего и даже показал правдоподобное 0x1111. Поймал только режим detect_stack_use_after_return, в котором ASan переносит локальные переменные в кучу и держит мёртвые кадры в карантине. Прямой return &val; gcc ловит предупреждением -Wreturn-local-addr, поэтому в примере адрес сначала кладётся в p: одного присваивания хватило, чтобы компилятор потерял след.
Теперь Zig. Прямой возврат адреса он ловит на этапе компиляции:
$ zig build-exe b08_direct.zig
b08_direct.zig:5:13: error: returning address of expired local variable 'val'
return &val;
^~~
b08_direct.zig:4:9: note: declared runtime-known hereНо стоит спрятать адрес в срез внутри структуры, и след теряется точно так же:
const std = @import("std");
const Line = struct { text: []const u8 };
noinline fn makeLine() Line {
var storage = [_]u8{ 'h', 'e', 'l', 'l', 'o', '!', '!', '!' };
const view: []u8 = &storage;
return .{ .text = view };
}
noinline fn overwrite() u64 {
var junk = [_]u64{ 0x2323232323232323, 0x2323232323232323, 0x2323232323232323, 0x2323232323232323 };
const p: *volatile [4]u64 = &junk;
return p[0] + p[3];
}
pub fn main(init: std.process.Init) !void {
var buf: [256]u8 = undefined;
var w = std.Io.File.stdout().writer(init.io, &buf);
const out = &w.interface;
const line = makeLine();
_ = overwrite();
try out.print("{s}\n", .{line.text});
try out.flush();
}$ zig build-exe b08_dangling.zig && ./b08_dangling | xxd # Debug
00000000: 6865 6c6c 6f21 2121 0a hello!!!.
$ zig build-exe -O ReleaseSafe b08_dangling.zig && ./b08_dangling | xxd
00000000: 0800 0000 0000 0000 0a .........
$ zig build-exe -O ReleaseFast b08_dangling.zig && ./b08_dangling | xxd
00000000: c895 056b 0100 0000 0a ...k.....Вот это и есть место, где Zig не помогает. Ни паники, ни 0xaa, ни предупреждения ни в одном режиме. В Debug программа даже печатает правильный ответ: кадры легли так, что overwrite до массива не дотянулась. В ReleaseSafe на месте строки лежит число 8 (похоже на длину того самого среза), в ReleaseFast чей-то адрес. Три режима, три разных ответа, ни одной диагностики. Времён жизни в системе типов Zig нет, это сознательный выбор языка, и висячий указатель на стек остаётся на совести программиста. Правило простое: всё, что переживает функцию, живёт либо у вызывающего (он передал буфер), либо в куче (он передал аллокатор).
9. Обращение к освобождённому блоку
#include <stdio.h>
#include <stdlib.h>
int main(void) {
long *x = malloc(4 * sizeof(long));
x[0] = 0x1234;
free(x);
long *y = malloc(4 * sizeof(long));
y[0] = 0x5678;
printf("x[0] = 0x%lx\n", x[0]); /* x уже освобождён */
free(y);
return 0;
}$ ./uaf
x[0] = 0x5678
$ valgrind ./uaf
==44== Invalid read of size 8
==44== at 0x1091A3: main (uaf.c:10)
==44== Address 0x4a39040 is 0 bytes inside a block of size 32 free'd
==44== at 0x484417B: free (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==44== by 0x109185: main (uaf.c:7)
==44== Block was alloc'd at
==44== by 0x10916A: main (uaf.c:5)
x[0] = 0x1234
$ ./uaf.asan
==50==ERROR: AddressSanitizer: heap-use-after-free on address 0x603000000040 at pc 0x555555555262 bp 0x7ffffffcac20 sp 0x7ffffffcac18
READ of size 8 at 0x603000000040 thread T0
#0 0x555555555261 in main /tmp/w/uaf.c:10
freed by thread T0 here:
#1 0x555555555206 in main /tmp/w/uaf.c:7
previously allocated by thread T0 here:
#1 0x5555555551ca in main /tmp/w/uaf.c:5Без инструментов программа напечатала 0x5678: glibc отдал только что освобождённый блок следующему malloc того же размера, и x с y теперь один и тот же адрес. Ты уже видел это изнутри: свободный список с дисциплиной LIFO из урока про аллокатор устроен ровно так. Так выглядят настоящие уязвимости: атакующий добивается, чтобы на месте освобождённого объекта оказались его данные, а программа продолжает ходить по старому указателю. Под valgrind вывод другой, 0x1234: его malloc освобождённые блоки придерживает, чтобы поймать именно такие обращения. Три строки отчёта (где читали, где освободили, где выделили) это всё, что нужно для починки.
В Zig за эту ошибку отвечает не язык, а аллокатор, и помогает здесь DebugAllocator:
const std = @import("std");
pub fn main(init: std.process.Init) !void {
var buf: [256]u8 = undefined;
var w = std.Io.File.stdout().writer(init.io, &buf);
const out = &w.interface;
var debug: std.heap.DebugAllocator(.{}) = .init;
defer _ = debug.deinit();
const gpa = debug.allocator();
const neighbor = try gpa.alloc(u64, 4);
defer gpa.free(neighbor);
const x = try gpa.alloc(u64, 4);
x[0] = 0x1234;
gpa.free(x);
const y = try gpa.alloc(u64, 4);
defer gpa.free(y);
y[0] = 0x5678;
try out.print("x.ptr == y.ptr: {}\n", .{x.ptr == y.ptr});
try out.print("x[0] = 0x{x}\n", .{x[0]});
try out.flush();
}$ ./b09_uaf # Debug и ReleaseSafe
x.ptr == y.ptr: false
x[0] = 0xaaaaaaaaaaaaaaaa
$ zig build-exe -O ReleaseFast b09_uaf.zig && ./b09_uaf
x.ptr == y.ptr: false
x[0] = 0x1234Две защиты сразу. free в режимах с проверками заливает блок тем же 0xaa (это строка @memset(bytes, undefined) в std/mem/Allocator.zig), а DebugAllocator не спешит выдавать освобождённый слот заново, поэтому y получил другой адрес, и чтение по x видит отраву, а не чужие данные. Паники нет: чтение само по себе законно, страница отображена. Но 0xaaaaaaaaaaaaaaaa в роли длины, индекса или указателя уронит программу на следующем же шаге.
А теперь честная оговорка. Убери из программы блок neighbor и пересобери:
$ ./b09_uaf_alone # все три режима
x.ptr == y.ptr: true
x[0] = 0x5678Когда освобождённый блок был единственным жильцом своей страницы, DebugAllocator вернул страницу системе, следующий alloc получил её же, и мы снова в мире C: тот же адрес, чужие данные, полная тишина. Защита вероятностная, не гарантия.
Двойное освобождение он ловит надёжнее:
const std = @import("std");
pub fn main() !void {
var debug: std.heap.DebugAllocator(.{}) = .init;
defer _ = debug.deinit();
const gpa = debug.allocator();
const neighbor = try gpa.alloc(u64, 4);
defer gpa.free(neighbor);
const x = try gpa.alloc(u64, 4);
gpa.free(x);
gpa.free(x);
}$ ./b09_double # Debug
error(DebugAllocator): Double free detected. Allocation:
b09_double.zig:11:28: 0x1006b5a1f in main (b09_double)
const x = try gpa.alloc(u64, 4);
^
First free:
b09_double.zig:12:13: 0x1006b5ad7 in main (b09_double)
gpa.free(x);
^
Second free:
b09_double.zig:13:13: 0x1006b5af3 in main (b09_double)
gpa.free(x);
^
$ zig build-exe -O ReleaseFast b09_double.zig && ./b09_double; echo $?
139Те же три адреса, что у valgrind: где выделили, где освободили первый раз, где второй. Программа при этом не падает, DebugAllocator пишет отчёт и идёт дальше. В ReleaseSafe отчёт тот же, но вместо строк стоит (empty stack trace): число кадров трассы вне Debug равно нулю. В ReleaseFast проверки аллокатора выключены, и второй free ломает его структуры до SIGSEGV. И та же оговорка: без соседа второй free в Debug приходит в уже отданную системе страницу и вместо отчёта даёт Segmentation fault at address ... внутри memset. Тоже громко, но уже без подсказки.
10. Утечка
#include <stdlib.h>
void leak(int n) {
long *x = malloc(n * sizeof(long));
x[0] = 1;
} /* x потерян навсегда */
int main(void) {
leak(4);
return 0;
}$ valgrind --leak-check=full ./leak
==57== 32 bytes in 1 blocks are definitely lost in loss record 1 of 1
==57== at 0x48417B4: malloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==57== by 0x109154: leak (leak.c:4)
==57== by 0x109174: main (leak.c:9)
$ ./leak.asan
==63==ERROR: LeakSanitizer: detected memory leaks
Direct leak of 32 byte(s) in 1 object(s) allocated from:
#1 0x555555555184 in leak /tmp/w/leak.c:4
#2 0x5555555551c5 in main /tmp/w/leak.c:9
SUMMARY: AddressSanitizer: 32 byte(s) leaked in 1 allocation(s).Как valgrind отличает “definitely lost” от “still reachable”? Перед выходом он делает ровно то, чему была посвящена первая половина урока: консервативный Mark от корней (стек, регистры, сегменты данных) по всем живым блокам. Блок, до которого не дошли, потерян наверняка. Детектор утечек это сборщик мусора, у которого фаза Sweep заменена на отчёт. LeakSanitizer внутри ASan устроен так же.
Для короткой программы утечка безобидна: ядро заберёт всё адресное пространство при выходе. Опасна она для серверов и демонов, которые живут месяцами.
На Zig ты это уже делал в уроке про аллокаторы:
const std = @import("std");
fn leak(gpa: std.mem.Allocator) !void {
const x = try gpa.alloc(u64, 4);
x[0] = 1;
}
pub fn main() !void {
var debug: std.heap.DebugAllocator(.{}) = .init;
defer std.debug.print("deinit: {t}\n", .{debug.deinit()});
try leak(debug.allocator());
}$ ./b10_leak # Debug
error(DebugAllocator): memory address 0x104d00000 leaked:
b10_leak.zig:4:28: 0x104ba9983 in leak (b10_leak)
const x = try gpa.alloc(u64, 4);
^
deinit: leak
$ zig build-exe -O ReleaseFast b10_leak.zig && ./b10_leak
deinit: okВ отличие от valgrind, DebugAllocator ничего не обходит: он просто ведёт таблицу выданных блоков и на deinit печатает те, что не вернулись. Достижим блок или нет, ему безразлично. В ReleaseFast таблицы нет, и ответ ok означает “не проверял”. Главная же защита от утечек в Zig стоит раньше: defer gpa.free(x) пишется в строке сразу после alloc, а std.testing.allocator делает любую утечку в тесте красной.
Чего Zig не ловит
Соберём честный список. Висячий указатель на стек ты видел: ноль диагностики. Второе слепое пятно это гонки данных:
const std = @import("std");
var counter: u64 = 0;
fn bump() void {
for (0..1_000_000) |_| counter += 1;
}
pub fn main(init: std.process.Init) !void {
var buf: [256]u8 = undefined;
var w = std.Io.File.stdout().writer(init.io, &buf);
const out = &w.interface;
const a = try std.Thread.spawn(.{}, bump, .{});
const b = try std.Thread.spawn(.{}, bump, .{});
a.join();
b.join();
try out.print("counter = {d}\n", .{counter});
try out.flush();
}$ for i in 1 2 3 4 5; do ./b11_race; done # Debug
counter = 2000000
counter = 1517647
counter = 1922516
counter = 1109876
counter = 1398654
$ for i in 1 2 3 4 5; do ./b11_race; done # ReleaseSafe
counter = 1225454
counter = 1883904
counter = 2000000
counter = 2000000
counter = 2000000
$ for i in 1 2 3 4 5; do ./b11_race; done # ReleaseFast
counter = 2000000
counter = 2000000
counter = 2000000
counter = 2000000
counter = 2000000Правильный ответ 2 000 000. В Debug потоки теряют обновления друг друга, и число при каждом запуске новое, причём иногда правильное, что хуже всего. В ReleaseSafe то же самое, только реже. В ReleaseFast пять раз подряд вышло два миллиона, но это не корректность, а скорость: цикл стал таким коротким, что первый поток успевает закончить раньше, чем стартует второй. Под нагрузкой или на другой машине везение кончится. Ни один режим не сказал ни слова. Гонкам посвящён отдельный блок раздела, а пока запомни: проверки Zig смотрят на одно обращение к памяти, а гонка это свойство двух.
| ошибка | компилятор Zig | Debug, ReleaseSafe | DebugAllocator | ReleaseFast |
|---|---|---|---|---|
1. число вместо указателя, null | ошибка типов, ?*T | паника на .? | SIGSEGV | |
| 2. чтение неинициализированного | отрава 0xaa | тишина | ||
| 3. переполнение буфера на стеке | паника по границе среза | тишина | ||
4. sizeof не того типа | непредставимо: alloc(T, n) | |||
| 5. ошибка на единицу | паника по границе среза | тишина | ||
6. *size-- | непредставимо | |||
| 7. арифметика указателей | только у [*]T | нет | тишина | |
| 8. адрес мёртвой локальной | только прямой return &x | нет | тишина | |
9. обращение к освобождённому, двойной free | 0xaa после free | отчёт о двойном free, слот не переиспользуется сразу | тишина или SIGSEGV | |
| 10. утечка | отчёт на deinit | тишина | ||
| гонка данных | нет | тишина |
Мораль у таблицы двойная. Первая: Zig не делает память безопасной, как Rust с его временами жизни или язык со сборщиком. Он делает ошибки громкими в отладочных режимах, а три из десяти убирает формой языка. Вторая: правый столбец целиком про C. Поэтому всё, что принимает данные снаружи, собирают в ReleaseSafe, а ReleaseFast оставляют для кода, где проверка в цикле измерена профилировщиком и действительно мешает, и то точечно, через @setRuntimeSafety(false) в одном блоке.
На macOS. Все опыты с Zig в этом уроке сняты на macOS arm64 и воспроизводятся там как есть; на Linux x86-64 отличаться будут только адреса. С инструментами для C сложнее. Valgrind на Apple Silicon не работает вовсе, и сборки для arm64 macOS нет. ASan есть в системном clang (
clang -fsanitize=address), и переполнения с обращением к освобождённому блоку он ловит так же, но LeakSanitizer в сборке Apple выключен. Вместо него есть штатная утилитаleaks:leaks --atExit -- ./leakзапускает программу и перед выходом делает тот же консервативный обход от корней, что и valgrind. Переменные окруженияMallocScribble=1иMallocPreScribble=1включают в системномmallocотраву: освобождённая память заливается0x55, свежая0xaa, та же идея, что у Zig. Для шага проекта на macOS важно одно отличие: дно стека там отдаётpthread_get_stackaddr_np, файла/proc/self/mapsнет. А всё, что в уроке подписаноlinux/amd64, снималось в контейнере:docker run --platform linux/amd64с образом Debian и пакетамиgccиvalgrind.
Упражнения
Итоги
- Сборщик мусора заменяет вопрос “нужен ли блок” на проверяемый: достижим ли он от корней по указателям. Недостижимое точно мусор; достижимое может быть не нужно, и это утечка в языке со сборщиком.
- Mark&Sweep это два прохода. Mark идёт от корней по живому с рабочим списком вместо рекурсии и стоит как живой граф. Sweep идёт по всей куче и стоит как куча. Циклы он собирает, в отличие от подсчёта ссылок.
- В C указатель не отличить от числа, поэтому сборщик для C консервативен: любое слово, попавшее внутрь выделенного блока, считается указателем. Живое он не освободит, но может удержать мусор (ложное удержание) и не может двигать объекты. Boehm GC это промышленная версия той же идеи: страницы с блоками одного размера вместо дерева, блоки без указателей, чёрный список страниц, грязные страницы через
mprotect. - В
zlкуча обходится точно, по тегам значений, а консервативен только скан машинного стека и сохраняемых регистров. Это избавилоevalот теневого стека и заодно покрыло кадры кода из JIT, для которых карт нет. Бит пометки живёт в свободном бите тега в словеcar, флаг обхода без стека в том же бите словаcdr: ни одной битовой карты сверхlive, зато сборка пишет в страницы живых ячеек.fib.zlс 175 159 выделениями проходит в пуле на 256 ячеек. - Пометка без стека по Дойчу, Шорру и Уэйту хранит путь назад в развёрнутых полях самих ячеек и стоит один бит на ячейку, но пишет в кучу и ломает граф на время обхода.
- Десять ошибок из книги: плохой указатель, неинициализированная память, переполнение на стеке,
sizeofне того типа, ошибка на единицу,*size--, арифметика указателей в байтах, адрес мёртвой локальной переменной, обращение к освобождённому блоку, утечка. - Zig три из них делает непредставимыми формой языка, ещё четыре превращает в панику или отраву
0xaaвDebugиReleaseSafe, двойное освобождение и утечку ловитDebugAllocator. Висячий указатель на стек (кроме прямогоreturn &x) и гонки данных он не ловит никак. ВReleaseFastпроверок нет, и поведение совпадает с C. - Valgrind исполняет бинарник на синтетическом процессоре с теневой памятью по биту и ловит в том числе неинициализированные чтения. ASan вставляет проверки при компиляции, окружает блоки красными зонами и держит освобождённое в карантине. Детектор утечек в обоих это консервативный Mark без Sweep.
Дальше
Блок про виртуальную память закрыт. Ты знаешь, как адрес превращается в байт, откуда берутся области процесса, как устроен аллокатор и что бывает, когда память возвращают не вовремя или не возвращают вовсе. Следующий блок про то, как процесс разговаривает с внешним миром. В следующем уроке начнём с самого низа: файловые дескрипторы, read и write как системные вызовы, и почему read вправе вернуть меньше, чем ты просил, а программа, которая этого не ждёт, работает на диске и ломается на сети.
домашка