Раздел 32 · Системное программирование: Zig, ассемблер, Verilog
Как устроен malloc: куча, блоки и неявный список
открытый урокЭтот раздел читается без входа. Войди, чтобы отмечать прогресс, вести заметки и решать задачи в редакторе. войти
Как устроен malloc: куча, блоки и неявный список
В прошлом уроке ты увидел, как
mmapсоздаёт в адресном пространстве новые области и как ядро лениво подкладывает под них страницы. Этого достаточно, чтобы получить у системы память, но совершенно недостаточно, чтобы программе было удобно ей пользоваться: ядро торгует страницами по 4 или 16 КБ, а программе нужны 24 байта под узел списка, потом 100 байт под строку, потом снова 24. Между ядром и программой стоит посредник, аллокатор. Он берёт у системы память оптом и раздаёт в розницу. Сегодня мы разберём, как он устроен изнутри: что лежит в куче кроме твоих данных, откудаfreeзнает размер блока, почему свободной памяти может быть много, аmallocвсё равно идёт к ядру за новой, и что такое граничный тег. А потом соберём первую версию своего аллокатора на Zig, с неявным списком блоков и тремя стратегиями поиска. В следующем уроке она получит интерфейсstd.mem.Allocator, две более быстрые организации и замеры.
Цели урока
- Объяснять, зачем нужно динамическое распределение и какие ограничения делают задачу аллокатора трудной: запросы в любом порядке, немедленный ответ, занятые блоки нельзя двигать.
- Считать две метрики аллокатора, throughput и пиковую utilization, и понимать, почему они тянут в разные стороны.
- Различать внутреннюю и внешнюю фрагментацию и находить обе в дампе кучи.
- Читать и писать заголовок блока: размер и бит занятости в одном слове, выравнивание на 16, минимальный блок.
- Сравнивать first fit, next fit и best fit на одной трассе: кто сколько блоков просмотрел и у кого куча выросла.
- Реализовать разбиение блока и слияние за константное время через граничные теги, разобрав все четыре случая.
- Знать, откуда аллокатор берёт память:
brkпротивmmap, что на самом деле делает порогM_MMAP_THRESHOLDв glibc и почему в стандартной библиотеке Zig основные аллокаторыbrkне трогают. - Собрать проект
our-alloc: модель кучи с проверяльщиком, неявный список,mallocиfree, трассы в формате malloclab и тесты шага.
Зачем программе куча
У программы три места, где живут данные. Глобальные переменные лежат в .data и .bss, их размер известен компоновщику. Локальные лежат в кадре стека, их размер известен компилятору, а время жизни равно времени работы функции. Остаётся всё, про что до запуска ничего не известно: сколько строк окажется в файле, сколько клиентов подключится, насколько глубоким выйдет дерево разбора. Для этого есть куча: область адресного пространства, которую программа занимает и отпускает по кускам, когда ей нужно.
Кучей управляет аллокатор. Он бывает двух видов. Явный ждёт, что программа сама вернёт каждый блок: malloc и free в C, alloc и free у std.mem.Allocator в Zig, new и delete в C++. Неявный находит ненужные блоки сам, это сборщик мусора, ему посвящён урок 59. Сегодня только явные.
Посмотри, что аллокатор делает с адресами. Программа четыре раза подряд просит одинаковые блоки у двух аллокаторов стандартной библиотеки Zig и печатает расстояние между соседними ответами:
const std = @import("std");
fn show(out: *std.Io.Writer, name: []const u8, gpa: std.mem.Allocator, size: usize) !void {
try out.print("{s}, по {d} байт:\n", .{ name, size });
var previous: usize = 0;
for (0..4) |_| {
const block = try gpa.alloc(u8, size);
const addr = @intFromPtr(block.ptr);
const step: usize = if (previous == 0) 0 else addr -% previous;
try out.print(" 0x{x} шаг {d}\n", .{ addr, step });
previous = addr;
}
}
pub fn main(init: std.process.Init) !void {
var buf: [4096]u8 = undefined;
var w = std.Io.File.stdout().writer(init.io, &buf);
const out = &w.interface;
try show(out, "page_allocator", std.heap.page_allocator, 24);
try show(out, "smp_allocator", std.heap.smp_allocator, 24);
try show(out, "smp_allocator", std.heap.smp_allocator, 100);
try out.flush();
}page_allocator, по 24 байт:
0x10274c000 шаг 0
0x102750000 шаг 16384
0x102754000 шаг 16384
0x102758000 шаг 16384
smp_allocator, по 24 байт:
0x102760000 шаг 0
0x102760020 шаг 32
0x102760040 шаг 32
0x102760060 шаг 32
smp_allocator, по 100 байт:
0x102770000 шаг 0
0x102770080 шаг 128
0x102770100 шаг 128
0x102770180 шаг 128Снято на Apple M4, macOS 26, Zig 0.16.0; сами адреса у тебя будут другими, шаги те же.
page_allocator это не аллокатор в нашем смысле, а тонкая обёртка над mmap: на каждый запрос он идёт в ядро и получает целые страницы. На Apple Silicon страница занимает 16 КБ, поэтому 24 байта обошлись в 16 384. Полезных из них 0,15 процента, и каждый вызов это системный вызов. На Linux x86-64 с его страницами по 4 КБ картина вчетверо мягче, но смысл тот же.
smp_allocator ведёт себя как настоящий аллокатор: блоки по 24 байта стоят через 32, блоки по 100 байт через 128. Он один раз взял у системы большой кусок и режет его сам, округляя запрос до степени двойки. Лишние 8 и 28 байт это плата за простоту учёта. Запомни эти числа, через пару разделов у них появится имя.
Условия задачи
Аллокатор общего назначения играет по жёстким правилам, и именно они делают задачу интересной.
- Запросы приходят в любом порядке. Программа вправе выделить миллион блоков и освободить их через один. Аллокатор не может рассчитывать, что блок, выделенный последним, освободят первым, как на стеке.
- Отвечать надо сразу. Нельзя отложить запрос, чтобы накопить несколько и разложить их получше.
- Вся служебная информация живёт в самой куче. У аллокатора нет другой памяти, кроме той, которой он управляет: сведения о блоках лежат рядом с блоками.
- Блоки выровнены. Программа положит в блок что угодно, значит адрес обязан подходить самому требовательному типу. На 64-битных системах
mallocотдаёт адреса, кратные 16: этого хватает иlong double, и векторным регистрам SSE. - Занятые блоки неприкосновенны. Как только адрес отдан программе, блок нельзя ни сдвинуть, ни сжать: указатель уже разошёлся по её структурам данных, и аллокатор не знает, где он лежит. Уплотнить кучу, как уплотняют диск, не получится.
Пятое правило самое болезненное. Из него вырастает вся фрагментация: дыру, которая образовалась между двумя живыми блоками, нельзя убрать, можно только попытаться удачно заполнить.
Две цели, которые мешают друг другу
Работу аллокатора оценивают двумя числами.
Throughput, пропускная способность: сколько запросов в секунду аллокатор успевает выполнить. 5000 вызовов malloc и 5000 вызовов free за одну секунду это 10 000 операций в секунду. Хороший аллокатор тратит на free константное время, а на malloc в худшем случае время, пропорциональное числу свободных блоков.
Пиковая utilization, использование памяти. Пусть после k-го запроса программа держит блоки с суммарной полезной нагрузкой Pk (это то, что она просила, без округлений и служебных слов), а куча занимает Hk байт. Тогда
Uk = max(P0, …, Pk) / Hk
Максимум в числителе стоит не случайно. Наша куча умеет только расти, поэтому честно сравнивать её размер с самой большой нагрузкой, которую она когда-либо держала. Если программа выделила 100 МБ, всё освободила и теперь держит один байт, аллокатор не виноват, что куча большая.
Цели конфликтуют. Самый быстрый аллокатор устроен в одну строку: на каждый запрос сдвинуть границу кучи и ничего никогда не переиспользовать. Throughput у него рекордный, utilization стремится к нулю. Самый экономный перебирал бы все варианты размещения и тратил бы на запрос секунды. Вся инженерия аллокаторов это поиск разумной середины, и в следующем уроке мы измерим, где эта середина у трёх организаций кучи.
Фрагментация
Низкая utilization почти всегда означает фрагментацию: память есть, но пустить её в дело нельзя. У неё два вида, и лечатся они по-разному.
Внутренняя фрагментация сидит внутри занятых блоков: блок больше того, что просили. Причин три. Служебные слова: заголовок, а у нас ещё и тег. Выравнивание: запрос на 17 байт округляется вверх. Минимальный размер блока: на запрос в 1 байт всё равно уйдёт 32. Считается она просто, как сумма разностей между размером блока и нагрузкой, и зависит только от того, какие запросы уже пришли. Те самые 8 байт из 32 у smp_allocator это она.
Внешняя фрагментация сидит между блоками: свободной памяти в сумме хватает, но она разбита на куски, каждый из которых меньше запроса. Измерить её одним числом трудно, потому что она зависит от будущего. Куча со свободными блоками по 32 байта через один идеальна, если дальше пойдут запросы по 16 байт, и бесполезна, если придёт запрос на 64. Раз будущее неизвестно, аллокаторы держатся эвристики: лучше мало крупных свободных блоков, чем много мелких.
В виджете ниже есть трасса “Шахматная доска” ровно про это: шесть блоков, три из них освобождены через один, свободно 96 байт, наибольший свободный блок 32, и запрос на 64 байта растит кучу при любой стратегии.
Четыре вопроса к любому аллокатору
Чтобы написать аллокатор, надо ответить на четыре вопроса.
- Организация. Как отличить свободные блоки от занятых и как перебирать свободные?
- Размещение. Какой из подходящих свободных блоков выбрать под запрос?
- Разбиение. Что делать с остатком, если блок больше запроса?
- Слияние. Что делать с блоком, который только что освободили?
Сегодня мы отвечаем на них самым простым способом, и ответ на первый вопрос называется неявным списком.
Неявный список: заголовок блока
free(p) получает один указатель и никакого размера. Значит размер блока аллокатор хранит сам, и хранит он его прямо перед данными, в заголовке блока. Блок выглядит так:
заголовок нагрузка добивка
+-----------+---------------------------------+---------------+
| размер, a | то, что просила программа | до кратности |
+-----------+---------------------------------+---------------+
^
адрес, который вернул mallocРазмер в заголовке это размер всего блока, с заголовком и добивкой. Зная его, от любого блока можно шагнуть к следующему: прибавь размер к адресу. Получается цепочка, в которой блоки связаны не указателями, а самими размерами. Отсюда и название, неявный список: списка как структуры данных нет, он следует из раскладки.
Теперь про бит занятости. Раз все блоки выровнены на 16, размер любого блока кратен 16, и четыре младших бита размера всегда равны нулю. Было бы расточительно хранить четыре вечных нуля, поэтому в них кладут признаки. Нам пока нужен один: младший бит равен 1, если блок занят. Чтение размера это заголовок с маской, чтение признака это заголовок и единица:
заголовок 0x31 = 0b0011_0001 размер 0x30 = 48, блок занят
заголовок 0x80 = 0b1000_0000 размер 0x80 = 128, блок свободенТот же приём ты встречал в записи таблицы страниц в уроке 55: адрес страницы кратен 4096, и двенадцать младших бит PTE заняты флагами.
Наши числа: слово 8, выравнивание 16, минимум 32
В книге CS:APP учебный аллокатор 32-битный: слово 4 байта, выравнивание 8. Мы живём в 64-битном мире, поэтому удваиваем всё. Заголовок занимает слово в 8 байт. Нагрузка выровнена на 16. Чтобы это выполнялось само собой, заголовки стоят по адресам вида 16k + 8: тогда нагрузка, которая идёт сразу за заголовком, попадает на 16k + 16.
Размер блока под запрос считается в две операции: прибавить служебные слова и округлить вверх до 16. Служебных слов у нас два, заголовок и граничный тег в конце блока, зачем он нужен, выяснится в разделе про слияние. И есть нижняя граница в 32 байта: заголовок, тег и 16 байт между ними. В этих 16 байтах свободный блок в следующем уроке будет хранить две ссылки списка, так что меньше нельзя.
const std = @import("std");
const word: usize = 8;
const alignment: usize = 16;
const min_block: usize = 32;
fn pack(size: usize, allocated: bool) usize {
return size | @intFromBool(allocated);
}
fn adjust(size: usize) usize {
return @max(min_block, std.mem.alignForward(usize, size + 2 * word, alignment));
}
pub fn main(init: std.process.Init) !void {
var buf: [4096]u8 = undefined;
var w = std.Io.File.stdout().writer(init.io, &buf);
const out = &w.interface;
try out.print("запрос блок служебных и пустых заголовок занятого\n", .{});
for ([_]usize{ 1, 8, 16, 17, 24, 32, 33, 100, 4080, 4081 }) |size| {
const block = adjust(size);
try out.print("{d:>6} {d:>5} {d:>19} 0x{x}\n", .{ size, block, block - size, pack(block, true) });
}
const header = pack(4112, true);
try out.print("\nзаголовок 0x{x}: размер {d}, занят {}\n", .{ header, header & ~@as(usize, 15), header & 1 == 1 });
try out.flush();
}запрос блок служебных и пустых заголовок занятого
1 32 31 0x21
8 32 24 0x21
16 32 16 0x21
17 48 31 0x31
24 48 24 0x31
32 48 16 0x31
33 64 31 0x41
100 128 28 0x81
4080 4096 16 0x1001
4081 4112 31 0x1011
заголовок 0x1011: размер 4112, занят trueТретья колонка это внутренняя фрагментация каждого блока. Она гуляет от 16 до 31 байта и не зависит от размера запроса: на блоке в 4 КБ это доли процента, на блоке в 1 байт это 97 процентов. Отсюда практический вывод, который верен для любого malloc: миллион отдельных выделений по 8 байт это расточительство, даже если аллокатор идеален. Мелкие одинаковые объекты берут из пула, и в следующем уроке такой пул появится у интерпретатора zl.
Края кучи: пролог и эпилог
Обходу нужно где-то начаться и где-то закончиться, а слиянию нужно не выпасть за край. Вместо проверок на каждом шагу куча получает два вечно занятых служебных блока. В начале стоит пролог: заголовок и тег без нагрузки, 16 байт. В конце стоит эпилог: одинокий заголовок с размером ноль и битом занятости. Перед прологом лежит одно пустое слово, оно сдвигает заголовки на нужные адреса 16k + 8.
base brk
| пусто 8 | пролог 16/1 | пролог 16/1 | hdr | нагрузка | ftr | ... | эпилог 0/1 |
^
first: отсюда начинается любой обходПустая куча занимает 32 байта: четыре слова. Обход это цикл “пока размер блока не ноль, шагай на размер”. Когда куча растёт, новый блок встаёт ровно на место старого эпилога, а эпилог переезжает в конец: его слово становится заголовком нового блока, и ничего двигать не приходится.
Размещение: first, next и best fit
Запрос пришёл, размер блока посчитан, пора искать свободный блок не меньше нужного. Стратегий три.
First fit идёт от начала кучи и берёт первый подходящий. Просто и в среднем неплохо по памяти: крупные блоки оседают в конце кучи и доживают до крупных запросов. Плата: начало кучи со временем забивается мелкими осколками, и каждый поиск сначала продирается сквозь них.
Next fit начинает поиск с того места, где закончил прошлый, а дойдя до конца, заворачивает в начало. Идея Дональда Кнута: если в прошлый раз подходящий блок нашёлся здесь, вероятно, остаток от него тоже пригодится. Поиск выходит заметно короче. Но осколки размазываются по всей куче ровным слоем, и по памяти next fit обычно хуже.
Best fit просматривает всё и берёт самый тесный из подходящих. По памяти он лучший из трёх: большие блоки не режутся без нужды. За это он платит полным обходом кучи на каждый запрос, если не повезло с точным попаданием.
Реальные числа с нашего аллокатора, который ты соберёшь ниже, на трассе mixed.trace (шесть тысяч запросов, мелкие объекты вперемешку со средними и редкими крупными): utilization 89,2 процента у first fit, 73,1 у next fit и 92,0 у best fit. При этом next fit на той же трассе быстрее first fit примерно в тринадцать раз, а best fit в полтора раза медленнее first fit (Apple M4 Max, Zig 0.16.0, ReleaseFast, 2026-09-21; машина была под нагрузкой, так что верь порядкам, а не второй цифре). Подробный разбор замеров ждёт в следующем уроке, здесь важно одно: выбор стратегии это не вкусовщина, он двигает обе метрики, и в разные стороны.
Разбиение
Нашли свободный блок на 128 байт, а нужно 48. Если отдать все 128, внутренняя фрагментация этого блока составит 80 байт. Поэтому блок режут: первые 48 байт становятся занятым блоком, оставшиеся 80 становятся новым свободным. Вся операция это четыре записи в память, два заголовка и два тега.
Но резать можно не всегда. Остаток обязан быть полноценным блоком, то есть не меньше 32 байт. Если в свободном блоке 64 байта, а нужно 48, остаток в 16 байт вместил бы заголовок с тегом и ни байта нагрузки. Такой блок никому нельзя выдать, он бы только удлинял обход. Поэтому правило такое: остаток меньше минимального блока не отрезается, блок занимается целиком, и 16 лишних байт уходят во внутреннюю фрагментацию.
Слияние и граничные теги
Программа освободила блок. Сбросить бит занятости в заголовке недостаточно. Представь два соседних свободных блока по 32 байта и запрос на 48: памяти 64 байта подряд, но поиск увидит два блока, каждый из которых мал, и пойдёт растить кучу. Это называется ложной фрагментацией, и лечится она слиянием: освобождая блок, аллокатор склеивает его со свободными соседями.
С правым соседом всё просто: его заголовок лежит сразу за нашим блоком, адрес известен. Если сосед свободен, прибавляем его размер к своему. С левым соседом беда. Мы знаем, где он кончается, прямо перед нашим заголовком, но не знаем, где он начинается: размер записан в его заголовке, а заголовок на неизвестном расстоянии слева. В односвязной цепочке назад не ходят. Остаётся обойти кучу с начала, и тогда free стоит столько же, сколько поиск.
Кнут предложил изящный выход: граничный тег. В последнее слово каждого блока кладётся копия заголовка. Теперь слово прямо перед нашим заголовком это тег левого соседа: из него читаются и занятость, и размер, а адрес начала получается вычитанием. Слияние в обе стороны стоит константу.
Соседей двое, каждый либо занят, либо свободен, выходит четыре случая:
случай 1: занят | наш | занят ничего не сливаем
случай 2: занят | наш | свободен наш + правый, адрес блока прежний
случай 3: свободен | наш | занят левый + наш, блок начинается с левого
случай 4: свободен | наш | свободен все три, блок начинается с левогоКрая кучи отдельной проверки не требуют: слева от первого блока стоит занятый пролог, справа от последнего занятый эпилог. Вот за что мы платили 32 байтами служебных слов.
Цена тегов это 8 байт на каждый блок, и для мелких блоков она чувствительна. На трассе cells.trace, где почти все запросы по 32 байта, наша utilization упирается в 80,8 процента при любой стратегии: на 32 байта нагрузки приходится 16 служебных. Есть известная оптимизация: тег нужен только свободному блоку, потому что сливаются только свободные. Занятому хватит одного бита “сосед слева занят” в заголовке соседа справа. В эталон она сознательно не вошла, это первое домашнее задание.
Посмотри на всё это сразу
Три дорожки показывают одну и ту же последовательность запросов на трёх стратегиях. У каждого блока по краям заголовок и граничный тег в виде размер/занят, ширина пропорциональна размеру. Кнопка “шаг трассы” применяет следующую операцию ко всем трём кучам, под каждой дорожкой журнал: какие блоки поиск просмотрел, где остановился, было ли разбиение, какой случай слияния сработал. Свои запросы добавляются кнопками malloc, а клик по занятому блоку его освобождает.
Что стоит проделать:
- Дырки разного размера. Пройди трассу до конца. После серии
freeв куче три дыры: 96, 32 и 64 байта. Дальше идут запросы на 16, 48 и 80 байт. First fit кладёт первый же мелкий запрос в большую дыру и портит её, последний запрос на 80 байт не влезает никуда, и куча растёт до 448 байт. Best fit раскладывает каждый запрос в свою дыру и остаётся в 320. Посмотри на счётчик просмотренных блоков: экономия памяти у best fit оплачена самым длинным поиском. - Шахматная доска. Внешняя фрагментация в чистом виде: свободно 96 байт, наибольший блок 32. Стратегия не помогает никому, и это важный урок: от плохой последовательности
freeне спасает умный поиск. - Четыре случая слияния. Порядок освобождения подобран так, что журнал покажет случаи 1, 2, 3, снова 1 и в конце 4. Следи за тегами: после слияния у большого блока один заголовок и один тег, а старые служебные слова внутри него стали обычным мусором в свободной памяти.
- На дорожке next fit стрелка отмечает бегунок. Освободи блок, на котором он стоит, так, чтобы сработало слияние, и посмотри, куда бегунок денется. К этому вопросу мы вернёмся в коде, там он стоил эталону вечного цикла.
Откуда берётся память: brk против mmap
Поиск ничего не нашёл, слияние не помогло. Аллокатор идёт к ядру, и у него два пути.
brk: граница, которая ездит вверх
Классическая куча Unix это область сразу за .bss. Ядро хранит для процесса её верхнюю границу, она называется brk. Системный вызов brk(addr) переставляет границу, библиотечная обёртка sbrk(n) сдвигает её на n байт и возвращает старое значение. Память между старой и новой границей сразу принадлежит процессу: это анонимная область с нулевыми страницами, которые ядро, как всегда, подложит при первом касании. Именно на sbrk построен учебный аллокатор в книге.
У стандартной библиотеки Zig обёртки sbrk в std.posix нет, но сырой системный вызов доступен как std.os.linux.brk. Попробуем:
const std = @import("std");
const linux = std.os.linux;
pub fn main(init: std.process.Init) !void {
var buf: [4096]u8 = undefined;
var w = std.Io.File.stdout().writer(init.io, &buf);
const out = &w.interface;
// brk(0) заведомо не выполнится, и ядро вернёт текущую границу.
const start = linux.brk(0);
try out.print("граница кучи: 0x{x}\n", .{start});
const grown = linux.brk(start + 4096);
try out.print("после brk(+4096): 0x{x} выросла на {d}\n", .{ grown, grown - start });
// Память между старой и новой границей уже наша: страница из нулей.
const bytes: [*]u8 = @ptrFromInt(start);
bytes[0] = 42;
try out.print("первый байт кучи: {d}, последний: {d}\n", .{ bytes[0], bytes[4095] });
const back = linux.brk(start);
try out.print("после brk(start): 0x{x}\n", .{back});
const mapped = linux.mmap(null, 1 << 20, .{ .READ = true, .WRITE = true }, .{ .TYPE = .PRIVATE, .ANONYMOUS = true }, -1, 0);
try out.print("mmap на 1 МБ: 0x{x}\n", .{mapped});
try out.print("от кучи до mmap: {d} ГБ\n", .{(mapped - start) >> 30});
_ = linux.munmap(@ptrFromInt(mapped), 1 << 20);
try out.flush();
}граница кучи: 0x1090000
после brk(+4096): 0x1091000 выросла на 4096
первый байт кучи: 42, последний: 0
после brk(start): 0x1090000
mmap на 1 МБ: 0x7fffff5e0000
от кучи до mmap: 131071 ГБСнято в контейнере Debian 12 на x86-64 (zig build-exe brk.zig -target x86_64-linux, статический бинарник без libc, поэтому граница не рандомизирована и от запуска к запуску одна и та же).
Обрати внимание на приём в первой строке программы. Ядерный brk при неудаче не возвращает ошибку, а возвращает текущую границу. Запрос brk(0) заведомо невыполним, и это штатный способ границу узнать; так же поступает и sbrk(0) в libc.
Последние две строки показывают вторую дорогу. mmap с флагами MAP_PRIVATE | MAP_ANONYMOUS создаёт новую область где-то наверху адресного пространства, в 128 терабайтах от кучи. Ей не нужно быть продолжением чего-либо.
Чем они отличаются
brk | mmap | |
|---|---|---|
| Что даёт | продолжение одной непрерывной области | новую область где угодно |
| Сколько таких | одна на процесс | сколько угодно |
| Вернуть память системе | только с конца: одна живая страница у самой границы держит всю кучу | любую область целиком через munmap |
| Цена вызова | дешевле: ядро двигает одно поле и правит одну область | дороже: новая область в дереве областей процесса, позже её разбор |
| Потоки | граница общая, нужна блокировка | области независимы |
Для неявного списка непрерывность критична: обход шагает от заголовка к заголовку, и дыра в адресах его ломает. Поэтому простые аллокаторы любят brk. Серьёзным аллокаторам нужнее вторая и третья строки таблицы: отдельная арена на каждый поток и возможность вернуть системе большой блок сразу после free.
Что делает glibc на самом деле
malloc из glibc использует обе дороги. Обычно это пересказывают так: запросы меньше 128 КБ идут в кучу через brk, запросы от 128 КБ через mmap, порог называется M_MMAP_THRESHOLD. Проверим, прежде чем верить:
#include <malloc.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
static uintptr_t heap_start;
static void *show(const char *what, size_t size) {
uintptr_t before = (uintptr_t)sbrk(0);
char *p = malloc(size);
uintptr_t after = (uintptr_t)sbrk(0);
int in_heap = (uintptr_t)p >= heap_start && (uintptr_t)p < after;
printf("%-22s %8zu %-4s %p brk +%lu\n", what, size, in_heap ? "brk" : "mmap", (void *)p,
(unsigned long)(after - before));
return p;
}
int main(void) {
heap_start = (uintptr_t)sbrk(0);
setvbuf(stdout, NULL, _IONBF, 0);
show("мелкий", 100);
show("ровно порог, top пуст", 128 * 1024);
show("100 КБ, top пуст", 100 * 1024);
show("ровно порог, top есть", 128 * 1024);
void *big = show("1 МБ", 1 << 20);
void *mid = show("300 КБ", 300 * 1024);
free(big);
free(mid);
puts("-- free(1 МБ), free(300 КБ)");
show("300 КБ ещё раз", 300 * 1024);
show("2 МБ", 2 << 20);
return 0;
}мелкий 100 brk 0x5555555592a0 brk +135168
ровно порог, top пуст 131072 brk 0x555555559310 brk +0
100 КБ, top пуст 102400 brk 0x555555579320 brk +233472
ровно порог, top есть 131072 brk 0x555555592330 brk +0
1 МБ 1048576 mmap 0x7fffff4e3010 brk +0
300 КБ 307200 mmap 0x7fffff497010 brk +0
-- free(1 МБ), free(300 КБ)
300 КБ ещё раз 307200 brk 0x5555555b2340 brk +438272
2 МБ 2097152 mmap 0x7fffff3e3010 brk +0Снято в контейнере Debian 12, glibc 2.36, gcc 12.2, x86-64. Колонки выровнены вручную: printf считает ширину в байтах, и кириллица её сбивает.
Здесь три наблюдения, и второго с третьим в пересказах обычно нет.
Куча растёт с запасом. Первый же malloc(100) сдвинул границу на 135 168 байт: это 132 КБ, запрос плюс запас M_TOP_PAD в 128 КБ, округлённые до страницы. Системный вызов дорог, и glibc платит за него один раз на много запросов. Наш аллокатор делает то же самое константой chunk.
Порог проверяется только тогда, когда куче нечем ответить. Запрос ровно в 131 072 байта дважды ушёл в кучу, хотя он не меньше порога. Причина в порядке действий: malloc сначала ищет в своих свободных списках и в хвостовом свободном блоке кучи (в исходниках glibc он называется top), и только если там пусто, решает, как просить у системы: mmap для запросов от порога, brk для остальных. В обоих случаях хвоста хватило, и до порога дело не дошло.
Порог плавает. После free блока в 1 МБ тот же запрос на 300 КБ, который минуту назад ушёл в mmap, пришёл из кучи. Это динамический порог: когда программа освобождает блок, взятый через mmap, glibc поднимает порог до его размера, вплоть до 32 МБ на 64-битных системах. Логика такая: раз программа выделяет и освобождает блоки такого размера, они временные, и гонять ради них mmap с munmap каждый раз дороже, чем держать в куче. Явный вызов mallopt(M_MMAP_THRESHOLD, n) фиксирует порог и отключает подстройку.
Зачем вообще отдавать большие блоки в mmap? Из-за третьей строки таблицы. Блок в 100 МБ посреди кучи после free останется за процессом, пока жив хоть один блок выше него. Тот же блок, взятый через mmap, возвращается системе в момент free.
А что в Zig
Основные аллокаторы стандартной библиотеки Zig 0.16 к brk не прикасаются. page_allocator это прямой mmap и munmap (на Windows VirtualAlloc), smp_allocator и DebugAllocator берут у него крупные куски и режут сами. Причин три, и все они из таблицы выше. Граница brk одна на процесс: если программа слинкована с libc, то malloc уже считает её своей, и второй хозяин испортит кучу первому. Переносимости нет: на Windows такого вызова не существует, на macOS он объявлен устаревшим. И потокам с общей границей тесно.
При этом в 0.16 есть std.heap.brk_allocator, файл lib/std/heap/BrkAllocator.zig. Он работает только в однопоточной сборке, иначе останавливает компиляцию, на Linux честно предупреждает в первой же строке документации, что рассчитывает на единоличный доступ к brk, а на WebAssembly использует тот же код поверх @wasmMemoryGrow: у wasm линейная память тоже умеет только расти с конца. Собственно, под именем WasmAllocator он и появился.
Нам для учебного аллокатора нужна непрерывная растущая область, то есть поведение sbrk, но без войны с libc и с работой на macOS. Решение в один ход: резервируем большой регион одним mmap и двигаем внутри него собственную границу. Нетронутый хвост региона ничего не стоит: в уроке 56 ты видел, что анонимная область получает физические страницы только при первом касании. Резерв в 64 МБ, из которых используется 100 КБ, занимает в памяти 100 КБ. Так же, к слову, устроены кучи многих виртуальных машин: большой резерв адресов и своя граница внутри.
На macOS. Весь код этого урока, кроме двух программ из этого раздела, собирается и работает на macOS напрямую.
brk.zigиthreshold.cзапускай в контейнере Linux. Первую собери прямо на macOS кросс-компиляцией,zig build-exe brk.zig -target x86_64-linux -femit-bin=brk-linux, и запусти какdocker run --rm --platform linux/amd64 -v "$PWD":/w -w /w debian:bookworm ./brk-linux; для второй возьми любой образ с gcc. На macOS функцияsbrkформально существует, но объявлена устаревшей: это эмуляция поверх заранее выделенного буфера фиксированного размера, и системный аллокатор её не использует вовсе. Системныйmallocтам это libmalloc: блоки делятся по размеру на несколько зон, и каждая зона режет свои регионы, полученные у ядра черезmach_vm_allocate, аналогmmap. Страница на Apple Silicon занимает 16 КБ против 4 КБ на x86-64, это ты уже видел по шагуpage_allocator. ПорогаM_MMAP_THRESHOLDи функцииmalloptна macOS нет. Наш регион от этих различий не зависит:page_allocatorсам выбираетmmapс правильным размером страницы.
Проект our-alloc: куча и неявный список
Пора писать. Проект называется our-alloc, это наша версия лабораторной malloclab из курса CS:APP. Сегодня в нём появятся модель кучи, неявный список с тремя стратегиями, malloc с free, трассы и тесты. Раскладка каталога:
our-alloc/
build.zig
src/
root.zig корень модуля alloc
heap.zig регион, слова и теги, place, coalesce, проверяльщик
implicit.zig first, next и best fit, индекс с бегунком
allocator.zig malloc, free, рост кучи
trace.zig разбор трасс malloclab
gen.zig генератор трасс
traces/ сюда генератор положит восемь файлов
tests/
step_57.zigГлавное проектное решение стоит проговорить заранее. Три версии аллокатора, которые мы строим за два урока, отличаются только тем, как они находят свободный блок. Заголовки, теги, разбиение, слияние, рост кучи у них общие. Поэтому код разрезан на два слоя. Нижний, heap.zig, знает про блоки и ничего не знает про поиск. Верхний называется индексом: он отвечает на вопрос “где свободный блок не меньше такого-то” и узнаёт от каркаса, когда блок стал свободным и когда перестал. У неявного списка индекс почти пуст, ему нечего помнить, кроме бегунка next fit. В следующем уроке на его место встанут явный список и сегрегированные списки, а heap.zig не изменится ни на строку.
heap.zig: модель кучи
Файл длинный, но устроен как четыре полки, сверху вниз.
Слой sbrk. Region это то самое решение из прошлого раздела: один mmap на весь запас через page_allocator.alignedAlloc и своя граница brk, которая умеет только расти. sbrk возвращает старую границу или null, если запас кончился. Адреса дальше по файлу это обычные usize, а не указатели: арифметика над адресами блоков здесь основное занятие, и с числами она читается проще, чем с приведениями типов на каждом шаге.
Слова и теги. get и put читают и пишут слово по адресу, pack собирает слово из размера и бита. Адрес блока по всему проекту называется bp и указывает на нагрузку, как в книге: заголовок лежит на слово раньше, headerOf(bp). Самая хитрая функция тут prevBlock: она читает слово по адресу bp - 16, а это граничный тег левого соседа, и вычитает его размер. mark пишет заголовок и тег разом, и больше никто в проекте служебные слова блока не трогает. adjust ты уже видел в демонстрации.
place и coalesce. place делает разбиение и возвращает адрес остатка или null: остаток надо сообщить индексу, и это забота вызывающего. coalesce сливает блок с соседями и возвращает адрес результата. Посмотри, как четыре случая уложились в два if без единого else: правый сосед добавляет размер, левый добавляет размер и сдвигает начало, а mark в конце один на все случаи. Параметр index имеет тип anytype: от индекса нужен единственный метод remove, и Zig проверит его наличие при компиляции. Соседа надо убрать из индекса до слияния, потому что после слияния его как отдельного блока уже нет. Для неявного списка и для тестов есть NoIndex с пустым remove.
Куча и проверяльщик. Heap.reset раскладывает четыре начальных слова. extend растит кучу, и в нём тот самый фокус с эпилогом: sbrk возвращает старую границу, старая граница это адрес сразу за старым эпилогом, и если считать её адресом нагрузки нового блока, то заголовком нового блока окажется слово старого эпилога. lastFree нужен для экономного роста, о нём ниже. А check это проверяльщик кучи, и про него отдельный разговор.
Ошибка в аллокаторе не падает там, где она сделана. Перепутал размер в place, и программа проживёт ещё тысячу операций, пока обход не наступит на испорченный заголовок и не уедет в случайный адрес. Искать такое отладчиком мучительно. Поэтому первое, что пишут в malloclab, это функция, которая обходит кучу и проверяет всё, что должно быть правдой всегда: пролог на месте, каждый блок выровнен, не меньше минимального и не вылезает за границу, заголовок равен тегу, двух свободных блоков подряд нет, обход заканчивается ровно на эпилоге. Тесты зовут её после каждой операции, и сломанный инвариант ловится на той самой операции, которая его сломала. Каждая ошибка у нас именованная, так что тест падает с error.NotCoalesced, а не с общим “что-то не так”.
//! Модель кучи: непрерывный регион, блоки с заголовком и граничным тегом.
//!
//! Раскладка та же, что в учебном аллокаторе из главы про виртуальную
//! память, только слово здесь 8 байт, а выравнивание 16:
//!
//! ```
//! base brk
//! | пусто 8 | пролог hdr | пролог ftr | hdr | payload | ftr | ... | эпилог hdr |
//! ```
//!
//! Заголовок и граничный тег (footer) хранят одно и то же слово: размер
//! блока целиком, в младшем бите признак занятости. Размер кратен 16,
//! поэтому младшие четыре бита свободны. Адрес блока (`bp`) это адрес его
//! полезной нагрузки: заголовок лежит на слово раньше. Так как заголовок
//! занимает 8 байт и стоит по адресу вида 16k + 8, нагрузка выровнена на 16.
//!
//! Функции этого файла не знают про списки свободных блоков. Всё, что
//! зависит от способа поиска, живёт в индексе (`implicit.zig`,
//! `explicit.zig`, `segregated.zig`), а сюда индекс приходит параметром.
const std = @import("std");
/// Размер слова: столько занимает заголовок и столько же граничный тег.
pub const word: usize = 8;
/// Выравнивание полезной нагрузки и шаг размеров блоков.
pub const alignment: usize = 16;
/// Минимальный блок: заголовок, тег и 16 байт, в которые свободный блок
/// кладёт две ссылки списка.
pub const min_block: usize = 32;
/// На сколько байт куча растёт за один раз, если просят меньше.
pub const chunk: usize = 4096;
// ---------------------------------------------------------------------------
// Слой sbrk
// ---------------------------------------------------------------------------
/// Непрерывный регион с границей `brk`, которая умеет только расти.
///
/// Настоящего `sbrk` на macOS нет, а на Linux он общий на процесс и мешал бы
/// системному аллокатору. Поэтому регион резервируется одним `mmap` сразу на
/// весь запас: ядро выдаёт физические страницы лениво, при первом касании,
/// так что нетронутый хвост ничего не стоит.
pub const Region = struct {
memory: []align(std.heap.page_size_min) u8,
brk: usize = 0,
pub fn init(reserve: usize) !Region {
const memory = try std.heap.page_allocator.alignedAlloc(
u8,
.fromByteUnits(std.heap.page_size_min),
reserve,
);
return .{ .memory = memory };
}
pub fn deinit(self: *Region) void {
std.heap.page_allocator.free(self.memory);
self.* = undefined;
}
/// Сдвигает границу на `bytes` и возвращает старую. `null`, если запас
/// исчерпан.
pub fn sbrk(self: *Region, bytes: usize) ?usize {
if (bytes > self.memory.len - self.brk) return null;
const old = self.base() + self.brk;
self.brk += bytes;
return old;
}
pub fn base(self: *const Region) usize {
return @intFromPtr(self.memory.ptr);
}
};
// ---------------------------------------------------------------------------
// Слова и теги
// ---------------------------------------------------------------------------
pub fn pack(size: usize, allocated: bool) usize {
return size | @intFromBool(allocated);
}
pub fn get(addr: usize) usize {
return @as(*const usize, @ptrFromInt(addr)).*;
}
pub fn put(addr: usize, value: usize) void {
@as(*usize, @ptrFromInt(addr)).* = value;
}
pub fn headerOf(bp: usize) usize {
return bp - word;
}
pub fn footerOf(bp: usize) usize {
return bp + blockSize(bp) - 2 * word;
}
pub fn blockSize(bp: usize) usize {
return get(headerOf(bp)) & ~@as(usize, alignment - 1);
}
pub fn isAllocated(bp: usize) bool {
return get(headerOf(bp)) & 1 == 1;
}
pub fn nextBlock(bp: usize) usize {
return bp + blockSize(bp);
}
/// Предыдущий блок находится через его граничный тег: он лежит прямо перед
/// нашим заголовком.
pub fn prevBlock(bp: usize) usize {
return bp - (get(bp - 2 * word) & ~@as(usize, alignment - 1));
}
/// Пишет заголовок и граничный тег блока.
pub fn mark(bp: usize, size: usize, allocated: bool) void {
put(headerOf(bp), pack(size, allocated));
put(bp + size - 2 * word, pack(size, allocated));
}
/// Размер блока под `size` байт нагрузки: плюс заголовок и тег, вверх до 16.
pub fn adjust(size: usize) usize {
return @max(min_block, std.mem.alignForward(usize, size + 2 * word, alignment));
}
/// Сколько байт нагрузки помещается в блок.
pub fn payloadSize(bp: usize) usize {
return blockSize(bp) - 2 * word;
}
// ---------------------------------------------------------------------------
// place и coalesce
// ---------------------------------------------------------------------------
/// Занимает `asize` байт в начале свободного блока `bp`. Если остаток тянет
/// на самостоятельный блок, отрезает его и возвращает: вызывающий вернёт
/// остаток в свой индекс. Иначе блок занимается целиком и возвращается `null`.
pub fn place(bp: usize, asize: usize) ?usize {
const size = blockSize(bp);
if (size - asize < min_block) {
mark(bp, size, true);
return null;
}
mark(bp, asize, true);
const rest = bp + asize;
mark(rest, size - asize, false);
return rest;
}
/// Индекс, которому нечего обновлять: для неявного списка.
pub const NoIndex = struct {
pub fn remove(_: *NoIndex, _: usize) void {}
};
/// Сливает свободный блок `bp` со свободными соседями и возвращает адрес
/// получившегося блока. Сам `bp` в индексе ещё не числится, а вот соседей
/// перед слиянием нужно из индекса убрать: за это отвечает `index.remove`.
///
/// Четыре случая: оба соседа заняты, свободен правый, свободен левый,
/// свободны оба. Пролог и эпилог заняты всегда, поэтому краёв кучи отдельно
/// проверять не нужно.
pub fn coalesce(bp: usize, index: anytype) usize {
const prev = prevBlock(bp);
const next = nextBlock(bp);
const prev_free = !isAllocated(prev);
const next_free = !isAllocated(next);
var size = blockSize(bp);
var start = bp;
if (next_free) {
index.remove(next);
size += blockSize(next);
}
if (prev_free) {
index.remove(prev);
size += blockSize(prev);
start = prev;
}
mark(start, size, false);
return start;
}
// ---------------------------------------------------------------------------
// Куча
// ---------------------------------------------------------------------------
pub const Heap = struct {
region: Region,
/// Адрес блока-пролога: с него начинается любой обход.
first: usize,
pub fn init(reserve: usize) !Heap {
var heap: Heap = .{ .region = try Region.init(reserve), .first = 0 };
errdefer heap.region.deinit();
try heap.reset();
return heap;
}
pub fn deinit(self: *Heap) void {
self.region.deinit();
}
/// Возвращает кучу в исходное состояние, страницы региона остаются за
/// процессом. Так бенчмарк гоняет трассу много раз, не платя каждый раз
/// за `mmap` и сбои страниц.
pub fn reset(self: *Heap) !void {
self.region.brk = 0;
const start = self.region.sbrk(4 * word) orelse return error.OutOfMemory;
put(start, 0); // выравнивающее слово
put(start + word, pack(2 * word, true)); // заголовок пролога
put(start + 2 * word, pack(2 * word, true)); // тег пролога
put(start + 3 * word, pack(0, true)); // эпилог
self.first = start + 2 * word;
}
/// Размер кучи: сколько байт отдал `sbrk`. Знаменатель utilization.
pub fn size(self: *const Heap) usize {
return self.region.brk;
}
/// Адрес, по которому стоял бы блок после последнего: `headerOf` от него
/// это эпилог.
pub fn end(self: *const Heap) usize {
return self.region.base() + self.region.brk;
}
/// Растит кучу на `bytes` (кратно 16). Новый свободный блок встаёт на
/// место старого эпилога, эпилог переезжает в конец. Со свободным
/// соседом слева блок не сливается: это дело вызывающего.
pub fn extend(self: *Heap, bytes: usize) ?usize {
std.debug.assert(bytes % alignment == 0 and bytes >= min_block);
const bp = self.region.sbrk(bytes) orelse return null;
mark(bp, bytes, false);
put(headerOf(nextBlock(bp)), pack(0, true));
return bp;
}
/// Последний настоящий блок кучи, если он свободен.
pub fn lastFree(self: *const Heap) ?usize {
const last = prevBlock(self.end());
return if (last != self.first and !isAllocated(last)) last else null;
}
pub const Stats = struct {
blocks: usize = 0,
free_blocks: usize = 0,
free_bytes: usize = 0,
allocated_bytes: usize = 0,
};
pub const CheckError = error{
BadPrologue,
BadEpilogue,
Misaligned,
TooSmall,
TagMismatch,
NotCoalesced,
OutOfBounds,
};
/// Проверяльщик кучи: обходит все блоки и сверяет инварианты.
pub fn check(self: *const Heap) CheckError!Stats {
if (blockSize(self.first) != 2 * word or !isAllocated(self.first)) return error.BadPrologue;
var stats: Stats = .{};
var prev_free = false;
var bp = nextBlock(self.first);
while (blockSize(bp) != 0) : (bp = nextBlock(bp)) {
const size_here = blockSize(bp);
if (bp % alignment != 0) return error.Misaligned;
if (size_here < min_block) return error.TooSmall;
if (bp + size_here > self.end()) return error.OutOfBounds;
if (get(headerOf(bp)) != get(footerOf(bp))) return error.TagMismatch;
const free = !isAllocated(bp);
if (free and prev_free) return error.NotCoalesced;
prev_free = free;
stats.blocks += 1;
if (free) {
stats.free_blocks += 1;
stats.free_bytes += size_here;
} else {
stats.allocated_bytes += size_here;
}
}
if (bp != self.end() or !isAllocated(bp)) return error.BadEpilogue;
return stats;
}
};implicit.zig: три стратегии
Три функции поиска чистые: адрес, с которого начинать, и размер на входе, адрес блока или null на выходе. Кучу они видят только через heap.blockSize, heap.isAllocated и heap.nextBlock. bestFit обрывает обход при точном попадании: лучше уже не будет.
Самое поучительное место файла это nextFit и три метода индекса вокруг бегунка. Бегунок это адрес блока, и опасность в том, что блок под ним может исчезнуть. Сценарий: бегунок стоит на свободном блоке B, программа освобождает его левого соседа A, слияние делает из A и B один блок. Граница, на которую смотрел бегунок, теперь середина чужого блока, слово по этому адресу стало мусором, и следующий поиск прочтёт мусор как заголовок. Лечится это в двух местах. remove зовётся до слияния для каждого поглощаемого блока: если бегунок стоял на нём, он отходит на блок назад, эта граница слияние переживёт. insert зовётся после слияния для итогового блока: если бегунок оказался строго внутри него, он возвращается на начало.
И вторая ловушка, уже в самом nextFit. Отходя назад, бегунок может оказаться на прологе. Второй цикл обходит кучу от первого настоящего блока и ждёт встречи с бегунком, но пролог лежит до первого блока, и встречи не будет никогда. Без проверки на эпилог в условии цикл уходит за конец кучи. В эталоне эту ошибку поймал тест, комментарий в коде остался на память.
//! Неявный список: свободные блоки нигде не записаны, поиск идёт по всем
//! блокам кучи подряд, от заголовка к заголовку.
//!
//! Три стратегии поиска переключаются полем `fit`. Сами функции поиска
//! чистые: им нужен только адрес, с которого начинать, и размер.
const std = @import("std");
const heap = @import("heap.zig");
pub const Fit = enum { first, next, best };
/// Первый свободный блок не меньше `asize`, начиная с `from` и до эпилога.
pub fn firstFit(from: usize, asize: usize) ?usize {
var bp = from;
while (heap.blockSize(bp) != 0) : (bp = heap.nextBlock(bp)) {
if (!heap.isAllocated(bp) and heap.blockSize(bp) >= asize) return bp;
}
return null;
}
/// Самый тесный из подходящих блоков. Точное попадание обрывает поиск.
pub fn bestFit(from: usize, asize: usize) ?usize {
var best: ?usize = null;
var best_size: usize = std.math.maxInt(usize);
var bp = from;
while (heap.blockSize(bp) != 0) : (bp = heap.nextBlock(bp)) {
const size = heap.blockSize(bp);
if (heap.isAllocated(bp) or size < asize or size >= best_size) continue;
if (size == asize) return bp;
best = bp;
best_size = size;
}
return best;
}
/// Поиск с места прошлой находки: от `rover` до эпилога, потом от `from`
/// до `rover`.
pub fn nextFit(from: usize, rover: usize, asize: usize) ?usize {
if (firstFit(rover, asize)) |bp| return bp;
var bp = from;
// Эпилог в условии нужен на случай, когда бегунок отошёл на пролог: до
// него обход от первого блока не доберётся никогда.
while (bp != rover and heap.blockSize(bp) != 0) : (bp = heap.nextBlock(bp)) {
if (!heap.isAllocated(bp) and heap.blockSize(bp) >= asize) return bp;
}
return null;
}
/// Индекс неявного списка. Хранить ему нечего, кроме бегунка next fit.
pub const Index = struct {
fit: Fit = .first,
rover: usize = 0,
pub fn reset(self: *Index) void {
self.rover = 0;
}
pub fn findFit(self: *Index, h: *const heap.Heap, asize: usize) ?usize {
const from = heap.nextBlock(h.first);
switch (self.fit) {
.first => return firstFit(from, asize),
.best => return bestFit(from, asize),
.next => {
if (self.rover == 0) self.rover = from;
const found = nextFit(from, self.rover, asize) orelse return null;
self.rover = found;
return found;
},
}
}
/// Блок стал свободным. Если слияние поглотило блок, на который смотрел
/// бегунок, бегунок оказался бы внутри чужой нагрузки: возвращаем его на
/// начало слитого блока.
pub fn insert(self: *Index, bp: usize) void {
if (self.rover > bp and self.rover < heap.nextBlock(bp)) self.rover = bp;
}
/// Блок перестал быть свободным: его заняли или поглотил сосед. Во втором
/// случае граница блока исчезнет, поэтому бегунок, стоявший на нём,
/// отходит на блок назад: та граница слияние переживёт.
pub fn remove(self: *Index, bp: usize) void {
if (self.rover == bp) self.rover = heap.prevBlock(bp);
}
/// У неявного списка нет своей структуры, сверять нечего.
pub fn check(_: *const Index, _: *const heap.Heap, _: heap.Heap.Stats) !void {}
};allocator.zig: malloc и free
Каркас HeapAllocator(Index) это функция времени компиляции, которая по типу индекса строит тип аллокатора. Файл ниже приведён целиком, в финальном виде, и часть его относится к следующему уроку. Сегодня читай три вещи: malloc с mallocAligned, free и пару grow с extendTail. Ветки over_aligned, функцию resizeInPlace и весь хвост файла про std.mem.Allocator с таблицей из четырёх функций alloc, resize, remap, free мы подробно разберём в уроке 58; пока достаточно знать, что malloc зовёт mallocAligned с выравниванием 16, и тогда over_aligned ложно, а обе связанные с ним ветки не выполняются.
Без этих веток malloc читается в пять строк: посчитать размер блока, спросить блок у индекса, а если индекс ответил null, вырастить кучу; сообщить индексу, что блок больше не свободен; разместить с разбиением, остаток отдать индексу. Цепочка orelse в одной строке выражает ровно это: нашли, или вырастили, или вернули null.
free ещё короче: сбросить бит, слить, отдать результат индексу.
В grow спрятана экономия. Если последний блок кучи свободен, но мал, незачем просить у системы полный размер запроса: после слияния хвоста со свежим куском нужно только недостающее. Тест шага проверяет это числом: в хвосте свободно 3984 байта, нужен блок на 8016, куча растёт на 4096, а не на 8016. И куча никогда не растёт меньше чем на chunk: тот же запас, что M_TOP_PAD у glibc, только скромнее.
//! Аллокатор поверх модели кучи. Способ поиска свободного блока приходит
//! параметром `Index`, всё остальное у трёх версий общее: рост кучи,
//! разбиение, слияние, изменение размера на месте и vtable
//! `std.mem.Allocator`.
//!
//! От индекса нужны пять функций:
//!
//! * `findFit(heap, asize) ?usize` ищет свободный блок не меньше `asize`;
//! * `insert(bp)` принимает новый свободный блок;
//! * `remove(bp)` забывает блок, который сейчас займут или сольют;
//! * `reset()` и `check(heap, stats)` для сброса и самопроверки.
//!
//! Потоки аллокатор не защищает: один экземпляр на один поток.
const std = @import("std");
const heap = @import("heap.zig");
const Alignment = std.mem.Alignment;
pub fn HeapAllocator(comptime Index: type) type {
return struct {
heap: heap.Heap,
index: Index,
const Self = @This();
pub fn init(reserve: usize, index: Index) !Self {
return .{ .heap = try heap.Heap.init(reserve), .index = index };
}
pub fn deinit(self: *Self) void {
self.heap.deinit();
}
/// Пустая куча на тех же страницах.
pub fn reset(self: *Self) void {
self.heap.reset() catch unreachable; // четыре слова в регион помещаются всегда
self.index.reset();
}
// -------------------------------------------------------------------
// malloc, free, realloc на месте
// -------------------------------------------------------------------
pub fn malloc(self: *Self, size: usize) ?usize {
return self.mallocAligned(size, heap.alignment);
}
/// Выделяет `size` байт по адресу, кратному `alignment`.
///
/// Обычные 16 байт даёт сама раскладка. Для большего выравнивания
/// блок берётся с запасом, а подходящий адрес ищется внутри него.
/// Зазор перед этим адресом становится отдельным свободным блоком,
/// так что возвращённый указатель это честный `bp` со своим
/// заголовком, и `free` ничего не нужно знать о выравнивании.
pub fn mallocAligned(self: *Self, size: usize, alignment: usize) ?usize {
if (size == 0) return null;
const asize = heap.adjust(size);
const over_aligned = alignment > heap.alignment;
// Зазор не бывает больше alignment + min_block - 16.
const wanted = if (over_aligned) asize + alignment + heap.min_block else asize;
var bp = self.index.findFit(&self.heap, wanted) orelse self.grow(wanted) orelse return null;
self.index.remove(bp);
if (over_aligned) {
var aligned = std.mem.alignForward(usize, bp, alignment);
// Зазор короче минимального блока блоком стать не может:
// сдвигаемся на следующий подходящий адрес.
if (aligned != bp and aligned - bp < heap.min_block) aligned += alignment;
if (aligned != bp) {
const total = heap.blockSize(bp);
const gap = aligned - bp;
heap.mark(bp, gap, false);
heap.mark(aligned, total - gap, false);
// Слева от зазора занятый блок: свободные соседи слиты заранее.
self.index.insert(bp);
bp = aligned;
}
}
if (heap.place(bp, asize)) |rest| self.index.insert(rest);
return bp;
}
pub fn free(self: *Self, bp: usize) void {
heap.mark(bp, heap.blockSize(bp), false);
self.index.insert(heap.coalesce(bp, &self.index));
}
/// Меняет размер блока, не двигая его. Уменьшение удаётся всегда,
/// рост только за счёт свободного соседа справа или конца кучи.
pub fn resizeInPlace(self: *Self, bp: usize, new_size: usize) bool {
const asize = heap.adjust(new_size);
if (heap.blockSize(bp) < asize) {
var room = roomAt(bp);
// Блок у самого конца кучи дорастает через sbrk.
if (room < asize and bp + room == self.heap.end()) {
_ = self.extendTail(@max(asize - room, heap.min_block)) orelse return false;
room = roomAt(bp);
}
if (room < asize) return false;
self.index.remove(heap.nextBlock(bp));
heap.mark(bp, room, true);
}
// Лишний хвост возвращается в кучу.
if (heap.place(bp, asize)) |rest| {
self.index.insert(heap.coalesce(rest, &self.index));
}
return true;
}
/// Размер блока вместе со свободным соседом справа.
fn roomAt(bp: usize) usize {
const next = heap.nextBlock(bp);
return heap.blockSize(bp) + if (heap.isAllocated(next)) 0 else heap.blockSize(next);
}
/// Растит кучу так, чтобы в конце оказался свободный блок не меньше
/// `asize`. Если последний блок уже свободен, просим у `sbrk` только
/// недостающее.
fn grow(self: *Self, asize: usize) ?usize {
const have = if (self.heap.lastFree()) |last| heap.blockSize(last) else 0;
return self.extendTail(@max(asize - have, heap.chunk));
}
/// Добавляет в конец кучи `bytes` байт и возвращает свободный блок, в
/// который они влились. Блок уже числится в индексе.
fn extendTail(self: *Self, bytes: usize) ?usize {
const fresh = self.heap.extend(bytes) orelse return null;
const merged = heap.coalesce(fresh, &self.index);
self.index.insert(merged);
return merged;
}
// -------------------------------------------------------------------
// Самопроверка
// -------------------------------------------------------------------
/// Проверяльщик кучи: инварианты блоков плюс согласие индекса с кучей.
pub fn check(self: *const Self) !heap.Heap.Stats {
const stats = try self.heap.check();
try self.index.check(&self.heap, stats);
return stats;
}
// -------------------------------------------------------------------
// std.mem.Allocator
// -------------------------------------------------------------------
pub fn allocator(self: *Self) std.mem.Allocator {
return .{ .ptr = self, .vtable = &vtable };
}
const vtable: std.mem.Allocator.VTable = .{
.alloc = vtAlloc,
.resize = vtResize,
.remap = vtRemap,
.free = vtFree,
};
fn vtAlloc(ctx: *anyopaque, len: usize, alignment: Alignment, _: usize) ?[*]u8 {
const self: *Self = @ptrCast(@alignCast(ctx));
const bp = self.mallocAligned(len, alignment.toByteUnits()) orelse return null;
return @ptrFromInt(bp);
}
fn vtResize(ctx: *anyopaque, memory: []u8, _: Alignment, new_len: usize, _: usize) bool {
const self: *Self = @ptrCast(@alignCast(ctx));
return self.resizeInPlace(@intFromPtr(memory.ptr), new_len);
}
/// Перенос блока с копированием `std.mem.Allocator` сделает сам, когда
/// получит `null`: вызовет `alloc`, скопирует байты и вызовет `free`.
fn vtRemap(ctx: *anyopaque, memory: []u8, alignment: Alignment, new_len: usize, ret_addr: usize) ?[*]u8 {
return if (vtResize(ctx, memory, alignment, new_len, ret_addr)) memory.ptr else null;
}
fn vtFree(ctx: *anyopaque, memory: []u8, _: Alignment, _: usize) void {
const self: *Self = @ptrCast(@alignCast(ctx));
self.free(@intFromPtr(memory.ptr));
}
};
}trace.zig и gen.zig: трассы
Аллокатор проверяют на трассах: записанных последовательностях запросов. Формат взят из malloclab, строка это операция:
a 3 128 выделить 128 байт, запомнить под номером 3
r 3 512 изменить размер блока 3 до 512 байт
f 3 освободить блок 3Из trace.zig сегодняшним тестам нужны parse, slotCount и payloadAfter, которая ведёт сумму живой нагрузки, числитель utilization. Функции apply и run проигрывают трассу через std.mem.Allocator, они заработают в следующем уроке, а сегодня тест играет трассы сам, через голые malloc и free.
//! Трассы в формате malloclab и их проигрыватель.
//!
//! Строка трассы это одна операция:
//!
//! ```
//! a 3 128 выделить 128 байт, запомнить под номером 3
//! r 3 512 изменить размер блока 3 до 512 байт
//! f 3 освободить блок 3
//! ```
//!
//! Строки с `#` и пустые пропускаются. Проигрыватель работает с любым
//! `std.mem.Allocator`, поэтому одна и та же трасса меряет и наши версии,
//! и аллокаторы стандартной библиотеки.
const std = @import("std");
pub const Kind = enum { alloc, free, realloc };
pub const Op = struct {
kind: Kind,
id: u32,
size: u32 = 0,
};
pub const ParseError = error{ BadOp, BadNumber, OutOfMemory };
pub fn parse(gpa: std.mem.Allocator, text: []const u8) ParseError![]Op {
var ops: std.ArrayList(Op) = .empty;
errdefer ops.deinit(gpa);
var lines = std.mem.tokenizeScalar(u8, text, '\n');
while (lines.next()) |raw| {
const line = std.mem.trim(u8, raw, " \t\r");
if (line.len == 0 or line[0] == '#') continue;
var fields = std.mem.tokenizeScalar(u8, line, ' ');
const tag = fields.next() orelse return error.BadOp;
const kind: Kind = if (std.mem.eql(u8, tag, "a"))
.alloc
else if (std.mem.eql(u8, tag, "f"))
.free
else if (std.mem.eql(u8, tag, "r"))
.realloc
else
return error.BadOp;
const id = try number(fields.next());
const size = if (kind == .free) 0 else try number(fields.next());
try ops.append(gpa, .{ .kind = kind, .id = id, .size = size });
}
return ops.toOwnedSlice(gpa);
}
fn number(field: ?[]const u8) ParseError!u32 {
return std.fmt.parseInt(u32, field orelse return error.BadNumber, 10) catch error.BadNumber;
}
/// Сколько ячеек нужно проигрывателю: наибольший номер блока плюс один.
pub fn slotCount(ops: []const Op) usize {
var max: usize = 0;
for (ops) |op| max = @max(max, op.id + 1);
return max;
}
/// Как меняется сумма живой нагрузки после операции. Ячейки `sizes` ведёт
/// вызывающий: так и тест, и бенч считают числитель utilization одинаково.
pub fn payloadAfter(op: Op, sizes: []u32, live: usize) usize {
const before = sizes[op.id];
sizes[op.id] = op.size;
return live - before + op.size;
}
/// Пик живой нагрузки за всю трассу: числитель utilization.
pub fn peakPayload(gpa: std.mem.Allocator, ops: []const Op) !usize {
const sizes = try gpa.alloc(u32, slotCount(ops));
defer gpa.free(sizes);
@memset(sizes, 0);
var live: usize = 0;
var peak: usize = 0;
for (ops) |op| {
live = payloadAfter(op, sizes, live);
peak = @max(peak, live);
}
return peak;
}
pub const RunError = error{ OutOfMemory, Corrupted };
/// Выполняет одну операцию. С `verify` каждый блок заливается байтом своего
/// номера, а перед `free` и после `realloc` заливка сверяется: если два блока
/// перекрылись или `realloc` потерял данные, проверка это увидит.
pub fn apply(a: std.mem.Allocator, op: Op, slots: [][]u8, comptime verify: bool) RunError!void {
const slot = &slots[op.id];
const fill: u8 = @truncate(op.id *% 31 +% 7);
switch (op.kind) {
.alloc => {
slot.* = try a.alloc(u8, op.size);
if (verify) @memset(slot.*, fill);
},
.realloc => {
const kept = @min(slot.len, op.size);
slot.* = try a.realloc(slot.*, op.size);
if (verify) {
if (!std.mem.allEqual(u8, slot.*[0..kept], fill)) return error.Corrupted;
@memset(slot.*, fill);
}
},
.free => {
if (verify and !std.mem.allEqual(u8, slot.*, fill)) return error.Corrupted;
a.free(slot.*);
slot.* = &.{};
},
}
}
/// Проигрывает трассу целиком. `slots` должен вмещать `slotCount(ops)` ячеек.
pub fn run(a: std.mem.Allocator, ops: []const Op, slots: [][]u8, comptime verify: bool) RunError!void {
@memset(slots, &.{});
for (ops) |op| try apply(a, op, slots, verify);
}
test "parse читает три вида операций и пропускает комментарии" {
const ops = try parse(std.testing.allocator, "# пример\na 0 16\n\nr 0 40\nf 0\n");
defer std.testing.allocator.free(ops);
try std.testing.expectEqualSlices(Op, &.{
.{ .kind = .alloc, .id = 0, .size = 16 },
.{ .kind = .realloc, .id = 0, .size = 40 },
.{ .kind = .free, .id = 0 },
}, ops);
try std.testing.expectEqual(@as(usize, 40), try peakPayload(std.testing.allocator, ops));
}
test "parse отвергает мусор" {
try std.testing.expectError(error.BadOp, parse(std.testing.allocator, "x 1 2\n"));
try std.testing.expectError(error.BadNumber, parse(std.testing.allocator, "a 1\n"));
}Трассы у нас свои, их пишет генератор с фиксированными зёрнами: повторный запуск даёт те же файлы байт в байт. Две короткие трассы можно проверить глазами, шесть длинных моделируют разные беды. mixed похожа на обычную программу. binary чередует блоки по 64 и 448 байт, освобождает крупные и просит 512: дыры от 448 не вмещают 512, это внешняя фрагментация в чистом виде, и utilization у всех стратегий на ней 53,7 процента. coalescing без слияния растила бы кучу на каждом витке. realloc растит буфер, random равномерно случайна, cells имитирует кучу интерпретатора с ячейками по 32 байта.
//! Генератор трасс: `zig build gen` переписывает каталог `traces/`.
//!
//! Все трассы свои, с фиксированными зёрнами: повторный запуск даёт те же
//! файлы байт в байт. Каждая трасса заканчивается освобождением всего
//! живого, поэтому проигрыватель ничего не теряет и на чужих аллокаторах.
const std = @import("std");
const Trace = struct {
gpa: std.mem.Allocator,
text: std.Io.Writer.Allocating,
live: std.ArrayList(u32) = .empty,
next_id: u32 = 0,
fn init(gpa: std.mem.Allocator, title: []const u8) !Trace {
var self: Trace = .{ .gpa = gpa, .text = .init(gpa) };
try self.text.writer.print("# {s}\n", .{title});
return self;
}
fn alloc(self: *Trace, size: usize) !u32 {
const id = self.next_id;
self.next_id += 1;
try self.text.writer.print("a {d} {d}\n", .{ id, size });
try self.live.append(self.gpa, id);
return id;
}
fn realloc(self: *Trace, id: u32, size: usize) !void {
try self.text.writer.print("r {d} {d}\n", .{ id, size });
}
fn free(self: *Trace, id: u32) !void {
const at = std.mem.indexOfScalar(u32, self.live.items, id).?;
_ = self.live.swapRemove(at);
try self.text.writer.print("f {d}\n", .{id});
}
fn freeRandom(self: *Trace, random: std.Random) !void {
const at = random.uintLessThan(usize, self.live.items.len);
try self.free(self.live.items[at]);
}
/// Освобождает всё живое в порядке выделения и отдаёт текст трассы.
fn finish(self: *Trace) ![]const u8 {
std.mem.sort(u32, self.live.items, {}, std.sort.asc(u32));
while (self.live.items.len > 0) try self.free(self.live.items[0]);
return self.text.written();
}
};
/// Две короткие трассы для тестов: их можно проверить глазами.
const short1 =
\\# short1: разбиение и все четыре случая слияния
\\a 0 24
\\a 1 100
\\a 2 24
\\a 3 500
\\a 4 24
\\f 1
\\f 3
\\f 2
\\a 5 600
\\f 0
\\f 4
\\f 5
\\
;
const short2 =
\\# short2: realloc на месте, с переездом и с уменьшением
\\a 0 64
\\a 1 64
\\r 0 128
\\f 1
\\r 0 200
\\a 2 32
\\r 0 4000
\\r 0 16
\\r 2 48
\\f 0
\\f 2
\\
;
/// Похоже на обычную программу: много мелких объектов, немного средних,
/// редкие крупные, освобождение вперемешку.
fn mixed(gpa: std.mem.Allocator) ![]const u8 {
var prng = std.Random.DefaultPrng.init(0x57);
const random = prng.random();
var t = try Trace.init(gpa, "mixed: мелкие, средние и редкие крупные объекты вперемешку");
for (0..6000) |_| {
if (t.live.items.len > 0 and random.uintLessThan(u8, 100) < 45) {
try t.freeRandom(random);
continue;
}
const dice = random.uintLessThan(u8, 100);
const size: usize = if (dice < 70)
random.intRangeAtMost(usize, 8, 128)
else if (dice < 95)
random.intRangeAtMost(usize, 129, 1024)
else
random.intRangeAtMost(usize, 1025, 16384);
_ = try t.alloc(size);
}
return t.finish();
}
/// Два размера через один, потом крупные освобождаются, и приходят запросы
/// чуть больше дыр: внешняя фрагментация в чистом виде.
fn binary(gpa: std.mem.Allocator) ![]const u8 {
var t = try Trace.init(gpa, "binary: 64 и 448 через один, потом 512 в дыры от 448");
var big: [1000]u32 = undefined;
for (&big) |*id| {
_ = try t.alloc(64);
id.* = try t.alloc(448);
}
for (big) |id| try t.free(id);
for (0..1000) |_| _ = try t.alloc(512);
return t.finish();
}
/// Два соседа освобождаются, и сразу нужен блок на их общий размер: без
/// слияния куча растёт на каждом витке.
fn coalescing(gpa: std.mem.Allocator) ![]const u8 {
var t = try Trace.init(gpa, "coalescing: два блока по 4095, потом один на 8190");
for (0..600) |_| {
const left = try t.alloc(4095);
const right = try t.alloc(4095);
try t.free(left);
try t.free(right);
const both = try t.alloc(8190);
try t.free(both);
}
return t.finish();
}
/// Буфер растёт через realloc, а между шагами появляются мелкие блоки,
/// которые мешают ему расти на месте.
fn reallocGrow(gpa: std.mem.Allocator) ![]const u8 {
var t = try Trace.init(gpa, "realloc: растущий буфер и мелкие блоки между шагами");
const buffer = try t.alloc(512);
var previous: ?u32 = null;
for (1..1500) |i| {
try t.realloc(buffer, 512 + 128 * i);
const small = try t.alloc(128);
if (previous) |id| try t.free(id);
previous = small;
}
return t.finish();
}
/// Равномерные размеры до 32 КБ, выделение и освобождение пополам.
fn uniform(gpa: std.mem.Allocator) ![]const u8 {
var prng = std.Random.DefaultPrng.init(0x58);
const random = prng.random();
var t = try Trace.init(gpa, "random: размеры от 1 до 32768, выделение и освобождение пополам");
for (0..5000) |_| {
if (t.live.items.len > 0 and random.boolean()) {
try t.freeRandom(random);
} else {
_ = try t.alloc(random.intRangeAtMost(usize, 1, 32768));
}
}
return t.finish();
}
/// Куча интерпретатора: cons-ячейки по 32 байта, короткие строки, потом
/// половина ячеек умирает и приходят векторы.
fn cells(gpa: std.mem.Allocator) ![]const u8 {
var prng = std.Random.DefaultPrng.init(0x59);
const random = prng.random();
var t = try Trace.init(gpa, "cells: cons-ячейки по 32 байта, строки, потом векторы");
var cons: std.ArrayList(u32) = .empty;
for (0..6000) |i| {
try cons.append(gpa, try t.alloc(32));
if (i % 8 == 0) _ = try t.alloc(random.intRangeAtMost(usize, 8, 64));
}
for (cons.items, 0..) |id, i| {
if (i % 2 == 0) try t.free(id);
}
for (0..400) |_| _ = try t.alloc(random.intRangeAtMost(usize, 256, 2048));
for (0..2000) |_| _ = try t.alloc(32);
return t.finish();
}
pub fn main(init: std.process.Init) !void {
const gpa = init.arena.allocator();
const io = init.io;
var dir = try std.Io.Dir.cwd().openDir(io, "traces", .{});
defer dir.close(io);
try dir.writeFile(io, .{ .sub_path = "short1.trace", .data = short1 });
try dir.writeFile(io, .{ .sub_path = "short2.trace", .data = short2 });
try dir.writeFile(io, .{ .sub_path = "mixed.trace", .data = try mixed(gpa) });
try dir.writeFile(io, .{ .sub_path = "binary.trace", .data = try binary(gpa) });
try dir.writeFile(io, .{ .sub_path = "coalescing.trace", .data = try coalescing(gpa) });
try dir.writeFile(io, .{ .sub_path = "realloc.trace", .data = try reallocGrow(gpa) });
try dir.writeFile(io, .{ .sub_path = "random.trace", .data = try uniform(gpa) });
try dir.writeFile(io, .{ .sub_path = "cells.trace", .data = try cells(gpa) });
}root.zig и build.zig
Корень модуля на этом шаге короткий: три файла и один готовый тип. В следующем уроке в него добавятся ещё два индекса и два типа.
//! Корень модуля alloc: malloclab на Zig.
const allocator = @import("allocator.zig");
pub const heap = @import("heap.zig");
pub const implicit = @import("implicit.zig");
pub const trace = @import("trace.zig");
pub const HeapAllocator = allocator.HeapAllocator;
/// Аллокатор с неявным списком: общий каркас плюс индекс из `implicit.zig`.
pub const ImplicitAllocator = HeapAllocator(implicit.Index);
test {
_ = heap;
_ = implicit;
_ = trace;
}build.zig собирает модуль alloc, генератор и тесты по шагам. Тесты читают трассы из traces/, поэтому рабочим каталогом для них назначен корень проекта. Список steps в следующем уроке вырастет до двух номеров, и там же появится шаг сборки для замеров.
//! Сборка our-alloc.
//!
//! `zig build test` гоняет тесты всех шагов, `zig build test -Dstep=57` один
//! шаг, `zig build gen` переписывает трассы.
const std = @import("std");
/// Шаги проекта по номерам уроков.
const steps = [_][]const u8{"57"};
pub fn build(b: *std.Build) void {
const target = b.standardTargetOptions(.{});
const optimize = b.standardOptimizeOption(.{});
const only_step = b.option([]const u8, "step", "Прогнать тесты одного шага, например -Dstep=57");
const alloc = b.addModule("alloc", .{
.root_source_file = b.path("src/root.zig"),
.target = target,
.optimize = optimize,
});
const gen = b.addExecutable(.{
.name = "gen",
.root_module = b.createModule(.{
.root_source_file = b.path("src/gen.zig"),
.target = target,
.optimize = optimize,
}),
});
const gen_cmd = b.addRunArtifact(gen);
gen_cmd.setCwd(b.path("."));
gen_cmd.has_side_effects = true;
b.step("gen", "Переписать трассы в traces/").dependOn(&gen_cmd.step);
const test_step = b.step("test", "Прогнать тесты всех шагов");
// Тесты самого модуля лежат рядом с кодом.
const module_tests = b.addTest(.{ .root_module = alloc });
test_step.dependOn(&b.addRunArtifact(module_tests).step);
inline for (steps) |step_name| {
const path = "tests/step_" ++ step_name ++ ".zig";
if (only_step == null or std.mem.eql(u8, only_step.?, step_name)) {
const tests = b.addTest(.{
.root_module = b.createModule(.{
.root_source_file = b.path(path),
.target = target,
.optimize = optimize,
.imports = &.{.{ .name = "alloc", .module = alloc }},
}),
});
const run_tests = b.addRunArtifact(tests);
// Тесты читают трассы из `traces/`: рабочий каталог это корень проекта.
run_tests.setCwd(b.path("."));
test_step.dependOn(&run_tests.step);
}
}
}Создай пустой каталог traces и запусти генератор:
$ mkdir traces
$ zig build gen
$ wc -l traces/*.trace
6001 traces/binary.trace
18301 traces/cells.trace
3601 traces/coalescing.trace
6607 traces/mixed.trace
5145 traces/random.trace
4500 traces/realloc.trace
13 traces/short1.trace
12 traces/short2.trace
44180 totalТесты шага
Тесты идут от малого к большому. Сначала арифметика: adjust и pack. Потом куча, собранная руками: вспомогательная layout одним вызовом extend берёт кусок нужного размера и нарезает его через place на занятые блоки, а release освобождает блок без всякого индекса. На такой куче проверяются оба исхода place, все четыре случая coalesce и то, что проверяльщик действительно ловит рассогласование заголовка с тегом и неслитых соседей: проверяльщик, который ничего не ловит, хуже, чем никакого. Отдельный тест разводит три стратегии на куче с дырами 64, 128 и 48: тот же пример, что в код-задаче ниже.
Дальше аллокатор целиком. 64 блока разных размеров заливаются каждый своим байтом, заливка сверяется, потом освобождаются чётные и следом нечётные: так срабатывают все случаи слияния, и в конце в куче обязан остаться ровно один свободный блок. Короткие трассы идут с проверяльщиком после каждой операции на всех трёх стратегиях. Длинные проверяют кучу раз в 97 операций и сверяют utilization с порогами. Пороги сняты с запасом в пару пунктов от реальных чисел: тест должен ловить поломку разбиения или слияния, а не шум.
//! Шаг 57: модель кучи и неявный список.
//!
//! Проверяются слова и теги, `place`, четыре случая `coalesce`, три
//! стратегии поиска на куче, собранной руками, и аллокатор целиком на
//! трассах: после каждой операции куча обязана пройти проверяльщик.
const std = @import("std");
const alloc = @import("alloc");
const testing = std.testing;
const heap = alloc.heap;
const implicit = alloc.implicit;
const trace = alloc.trace;
const reserve = 64 << 20;
/// Раскладывает в конце кучи занятые блоки заданных размеров и возвращает их
/// адреса. Дальше тест освобождает нужные сам.
fn layout(h: *heap.Heap, comptime sizes: []const usize) [sizes.len]usize {
var total: usize = 0;
for (sizes) |size| total += size;
var blocks: [sizes.len]usize = undefined;
var bp = h.extend(total).?;
for (sizes, 0..) |size, i| {
blocks[i] = bp;
bp = heap.place(bp, size) orelse break;
}
return blocks;
}
fn release(bp: usize) usize {
var no_index: heap.NoIndex = .{};
heap.mark(bp, heap.blockSize(bp), false);
return heap.coalesce(bp, &no_index);
}
test "adjust добавляет заголовок с тегом и округляет до 16" {
try testing.expectEqual(@as(usize, 32), heap.adjust(1));
try testing.expectEqual(@as(usize, 32), heap.adjust(16));
try testing.expectEqual(@as(usize, 48), heap.adjust(17));
try testing.expectEqual(@as(usize, 48), heap.adjust(32));
try testing.expectEqual(@as(usize, 4112), heap.adjust(4095));
}
test "pack кладёт признак занятости в младший бит" {
try testing.expectEqual(@as(usize, 0x41), heap.pack(64, true));
try testing.expectEqual(@as(usize, 0x40), heap.pack(64, false));
}
test "пустая куча это пролог и эпилог" {
var h = try heap.Heap.init(reserve);
defer h.deinit();
try testing.expectEqual(@as(usize, 32), h.size());
try testing.expectEqual(@as(usize, 0), h.first % heap.alignment);
const stats = try h.check();
try testing.expectEqual(@as(usize, 0), stats.blocks);
try testing.expectEqual(@as(?usize, null), h.lastFree());
}
test "extend ставит свободный блок на место эпилога" {
var h = try heap.Heap.init(reserve);
defer h.deinit();
const bp = h.extend(4096).?;
try testing.expectEqual(@as(usize, 0), bp % heap.alignment);
try testing.expectEqual(@as(usize, 4096), heap.blockSize(bp));
try testing.expect(!heap.isAllocated(bp));
try testing.expectEqual(h.end(), heap.nextBlock(bp));
try testing.expectEqual(h.first, heap.prevBlock(bp));
try testing.expectEqual(@as(?usize, bp), h.lastFree());
const stats = try h.check();
try testing.expectEqual(@as(usize, 1), stats.free_blocks);
try testing.expectEqual(@as(usize, 4096), stats.free_bytes);
}
test "sbrk отказывает, когда запас кончился" {
var region = try heap.Region.init(1 << 16);
defer region.deinit();
try testing.expect(region.sbrk(1 << 16) != null);
try testing.expectEqual(@as(?usize, null), region.sbrk(16));
}
test "place отрезает остаток, если он тянет на блок" {
var h = try heap.Heap.init(reserve);
defer h.deinit();
const bp = h.extend(128).?;
const rest = heap.place(bp, 48).?;
try testing.expectEqual(bp + 48, rest);
try testing.expectEqual(@as(usize, 48), heap.blockSize(bp));
try testing.expect(heap.isAllocated(bp));
try testing.expectEqual(@as(usize, 80), heap.blockSize(rest));
try testing.expect(!heap.isAllocated(rest));
_ = try h.check();
}
test "place занимает блок целиком, если остаток меньше минимального" {
var h = try heap.Heap.init(reserve);
defer h.deinit();
const bp = h.extend(64).?;
try testing.expectEqual(@as(?usize, null), heap.place(bp, 48));
try testing.expectEqual(@as(usize, 64), heap.blockSize(bp));
try testing.expect(heap.isAllocated(bp));
_ = try h.check();
}
test "coalesce: оба соседа заняты" {
var h = try heap.Heap.init(reserve);
defer h.deinit();
const b = layout(&h, &.{ 64, 64, 64 });
try testing.expectEqual(b[1], release(b[1]));
try testing.expectEqual(@as(usize, 64), heap.blockSize(b[1]));
_ = try h.check();
}
test "coalesce: свободен правый сосед" {
var h = try heap.Heap.init(reserve);
defer h.deinit();
const b = layout(&h, &.{ 64, 64, 64 });
_ = release(b[2]);
try testing.expectEqual(b[1], release(b[1]));
try testing.expectEqual(@as(usize, 128), heap.blockSize(b[1]));
_ = try h.check();
}
test "coalesce: свободен левый сосед" {
var h = try heap.Heap.init(reserve);
defer h.deinit();
const b = layout(&h, &.{ 64, 64, 64 });
_ = release(b[0]);
try testing.expectEqual(b[0], release(b[1]));
try testing.expectEqual(@as(usize, 128), heap.blockSize(b[0]));
_ = try h.check();
}
test "coalesce: свободны оба соседа" {
var h = try heap.Heap.init(reserve);
defer h.deinit();
const b = layout(&h, &.{ 64, 64, 64 });
_ = release(b[0]);
_ = release(b[2]);
try testing.expectEqual(b[0], release(b[1]));
try testing.expectEqual(@as(usize, 192), heap.blockSize(b[0]));
const stats = try h.check();
try testing.expectEqual(@as(usize, 1), stats.blocks);
}
test "проверяльщик ловит несогласие заголовка с тегом и неслитых соседей" {
var h = try heap.Heap.init(reserve);
defer h.deinit();
const b = layout(&h, &.{ 64, 64, 64 });
heap.put(heap.headerOf(b[1]), heap.pack(64, false));
try testing.expectError(error.TagMismatch, h.check());
heap.mark(b[1], 64, false);
heap.mark(b[2], 64, false);
try testing.expectError(error.NotCoalesced, h.check());
}
test "три стратегии выбирают разные блоки" {
var h = try heap.Heap.init(reserve);
defer h.deinit();
// свободные: 64, 128 и 48, между ними занятые по 32
const b = layout(&h, &.{ 64, 32, 128, 32, 48, 32 });
_ = release(b[0]);
_ = release(b[2]);
_ = release(b[4]);
const from = heap.nextBlock(h.first);
try testing.expectEqual(@as(?usize, b[0]), implicit.firstFit(from, 48));
try testing.expectEqual(@as(?usize, b[4]), implicit.bestFit(from, 48));
try testing.expectEqual(@as(?usize, b[2]), implicit.nextFit(from, b[1], 48));
// next fit заворачивает в начало кучи
try testing.expectEqual(@as(?usize, b[0]), implicit.nextFit(from, b[5], 64));
try testing.expectEqual(@as(?usize, b[2]), implicit.firstFit(from, 100));
try testing.expectEqual(@as(?usize, null), implicit.firstFit(from, 256));
try testing.expectEqual(@as(?usize, null), implicit.bestFit(from, 256));
try testing.expectEqual(@as(?usize, null), implicit.nextFit(from, b[3], 256));
}
test "malloc: выравнивание 16, блоки не перекрываются, free всё сливает" {
var a = try alloc.ImplicitAllocator.init(reserve, .{});
defer a.deinit();
var blocks: [64]usize = undefined;
for (&blocks, 1..) |*bp, n| {
bp.* = a.malloc(n * 7).?;
try testing.expectEqual(@as(usize, 0), bp.* % heap.alignment);
try testing.expect(heap.payloadSize(bp.*) >= n * 7);
@memset(@as([*]u8, @ptrFromInt(bp.*))[0 .. n * 7], @intCast(n));
_ = try a.check();
}
for (blocks, 1..) |bp, n| {
try testing.expect(std.mem.allEqual(u8, @as([*]u8, @ptrFromInt(bp))[0 .. n * 7], @intCast(n)));
}
// сначала чётные, потом нечётные: проходят все случаи слияния
for (blocks, 0..) |bp, i| if (i % 2 == 0) a.free(bp);
_ = try a.check();
for (blocks, 0..) |bp, i| if (i % 2 == 1) a.free(bp);
const stats = try a.check();
try testing.expectEqual(@as(usize, 1), stats.blocks);
try testing.expectEqual(@as(usize, 1), stats.free_blocks);
}
test "malloc(0) ничего не выделяет, а нехватка памяти это null" {
var a = try alloc.ImplicitAllocator.init(1 << 16, .{});
defer a.deinit();
try testing.expectEqual(@as(?usize, null), a.malloc(0));
try testing.expectEqual(@as(?usize, null), a.malloc(1 << 20));
try testing.expect(a.malloc(1000) != null);
_ = try a.check();
}
test "куча растёт только на недостающее, если в конце свободный блок" {
var a = try alloc.ImplicitAllocator.init(reserve, .{});
defer a.deinit();
const small = a.malloc(100).?; // куча выросла на 4096, в хвосте свободно 3984
_ = small;
const before = a.heap.size();
_ = a.malloc(8000).?;
// блоку нужно 8016, в хвосте было 3984: просим у sbrk max(4032, chunk)
try testing.expectEqual(before + heap.chunk, a.heap.size());
}
// ---------------------------------------------------------------------------
// Трассы через голый интерфейс malloc/free
// ---------------------------------------------------------------------------
const max_trace_bytes = 1 << 20;
fn readOps(name: []const u8) ![]trace.Op {
var dir = try std.Io.Dir.cwd().openDir(testing.io, "traces", .{});
defer dir.close(testing.io);
const text = try dir.readFileAlloc(testing.io, name, testing.allocator, .limited(max_trace_bytes));
defer testing.allocator.free(text);
return trace.parse(testing.allocator, text);
}
fn bytes(bp: usize, len: usize) []u8 {
return @as([*]u8, @ptrFromInt(bp))[0..len];
}
/// Проигрывает трассу без `std.mem.Allocator`: до vtable урок 57 ещё не
/// дошёл. Возвращает utilization в процентах.
fn play(a: *alloc.ImplicitAllocator, ops: []const trace.Op, check_every: usize) !usize {
const gpa = testing.allocator;
const slots = try gpa.alloc(usize, trace.slotCount(ops));
defer gpa.free(slots);
const sizes = try gpa.alloc(u32, slots.len);
defer gpa.free(sizes);
@memset(sizes, 0);
var live: usize = 0;
var peak: usize = 0;
for (ops, 0..) |op, i| {
const fill: u8 = @truncate(op.id);
const old = sizes[op.id];
switch (op.kind) {
.alloc => slots[op.id] = a.malloc(op.size) orelse return error.OutOfMemory,
.free => {
try testing.expect(std.mem.allEqual(u8, bytes(slots[op.id], old), fill));
a.free(slots[op.id]);
},
.realloc => if (!a.resizeInPlace(slots[op.id], op.size)) {
const moved = a.malloc(op.size) orelse return error.OutOfMemory;
@memcpy(bytes(moved, @min(old, op.size)), bytes(slots[op.id], @min(old, op.size)));
a.free(slots[op.id]);
slots[op.id] = moved;
},
}
if (op.kind != .free) {
const bp = slots[op.id];
try testing.expectEqual(@as(usize, 0), bp % heap.alignment);
try testing.expect(heap.payloadSize(bp) >= op.size);
if (op.kind == .realloc) {
try testing.expect(std.mem.allEqual(u8, bytes(bp, @min(old, op.size)), fill));
}
@memset(bytes(bp, op.size), fill);
}
live = trace.payloadAfter(op, sizes, live);
peak = @max(peak, live);
if (i % check_every == 0) _ = try a.check();
}
const stats = try a.check();
try testing.expectEqual(@as(usize, 0), stats.allocated_bytes);
try testing.expect(stats.free_blocks <= 1);
return peak * 100 / a.heap.size();
}
test "короткие трассы: проверяльщик после каждой операции, все стратегии" {
inline for (.{ "short1.trace", "short2.trace" }) |name| {
const ops = try readOps(name);
defer testing.allocator.free(ops);
inline for (.{ implicit.Fit.first, implicit.Fit.next, implicit.Fit.best }) |fit| {
var a = try alloc.ImplicitAllocator.init(reserve, .{ .fit = fit });
defer a.deinit();
_ = try play(&a, ops, 1);
}
}
}
const Floor = struct { name: []const u8, first: usize, next: usize, best: usize };
/// Нижние границы utilization в процентах. Сняты с запасом в пару пунктов от
/// реальных чисел: тест ловит поломку разбиения или слияния, а не шум.
const floors = [_]Floor{
.{ .name = "mixed.trace", .first = 85, .next = 68, .best = 88 },
.{ .name = "binary.trace", .first = 50, .next = 50, .best = 50 },
.{ .name = "coalescing.trace", .first = 95, .next = 95, .best = 95 },
.{ .name = "realloc.trace", .first = 95, .next = 94, .best = 88 },
.{ .name = "random.trace", .first = 87, .next = 80, .best = 88 },
.{ .name = "cells.trace", .first = 76, .next = 76, .best = 76 },
};
test "длинные трассы: корректность и порог utilization" {
for (floors) |floor| {
const ops = try readOps(floor.name);
defer testing.allocator.free(ops);
inline for (.{ implicit.Fit.first, implicit.Fit.next, implicit.Fit.best }) |fit| {
var a = try alloc.ImplicitAllocator.init(reserve, .{ .fit = fit });
defer a.deinit();
const util = try play(&a, ops, 97);
const min = @field(floor, @tagName(fit));
if (util < min) {
std.debug.print("{s}, {s} fit: utilization {d}% ниже порога {d}%\n", .{ floor.name, @tagName(fit), util, min });
return error.UtilizationTooLow;
}
}
}
}$ zig build test --summary all
Build Summary: 5/5 steps succeeded; 21/21 tests passed
test success
+- run test 3 pass (3 total) 315ms MaxRSS:2M
| +- compile test Debug native success 1s MaxRSS:277M
+- run test 18 pass (18 total) 4s MaxRSS:70M
+- compile test Debug native success 1s MaxRSS:278MТри теста лежат в самом модуле (в trace.zig), восемнадцать в tests/step_57.zig. Одна ловушка Zig 0.16: любой std.debug.print внутри теста превращает шаг в run test с перехватом вывода, и zig build печатает failed command, хотя тесты прошли и код выхода ноль. Отладочную печать из тестов убирай, а смотреть на кучу удобнее отдельной программой.
Дамп кучи
Вот она. В проект её класть не обязательно, она запускается одной командой без правки build.zig:
//! Проигрывает трассу и после каждой операции печатает кучу блок за блоком.
//!
//! zig run --dep alloc -Mroot=dump.zig -Malloc=src/root.zig -- traces/short1.trace first
const std = @import("std");
const alloc = @import("alloc");
const heap = alloc.heap;
fn dump(out: *std.Io.Writer, a: *const alloc.ImplicitAllocator) !void {
const base = a.heap.region.base();
var bp = heap.nextBlock(a.heap.first);
while (heap.blockSize(bp) != 0) : (bp = heap.nextBlock(bp)) {
const mark: u8 = if (heap.isAllocated(bp)) 'a' else 'f';
try out.print(" [{d}:{d}/{c}]", .{ bp - base, heap.blockSize(bp), mark });
}
try out.print(" куча {d}\n", .{a.heap.size()});
}
pub fn main(init: std.process.Init) !void {
const gpa = init.arena.allocator();
var buf: [4096]u8 = undefined;
var w = std.Io.File.stdout().writer(init.io, &buf);
const out = &w.interface;
const args = try init.minimal.args.toSlice(gpa);
if (args.len != 3) return error.Usage;
const fit = std.meta.stringToEnum(alloc.implicit.Fit, args[2]) orelse return error.Usage;
const text = try std.Io.Dir.cwd().readFileAlloc(init.io, args[1], gpa, .limited(1 << 20));
const ops = try alloc.trace.parse(gpa, text);
const slots = try gpa.alloc(usize, alloc.trace.slotCount(ops));
var a = try alloc.ImplicitAllocator.init(1 << 20, .{ .fit = fit });
defer a.deinit();
for (ops) |op| {
switch (op.kind) {
.alloc => {
slots[op.id] = a.malloc(op.size) orelse return error.OutOfMemory;
try out.print("a {d} {d:<4}", .{ op.id, op.size });
},
.free => {
a.free(slots[op.id]);
try out.print("f {d} ", .{op.id});
},
.realloc => return error.ReallocIsNextLesson,
}
try dump(out, &a);
_ = try a.check();
}
try out.flush();
}$ zig run --dep alloc -Mroot=dump.zig -Malloc=src/root.zig -- traces/short1.trace first
a 0 24 [32:48/a] [80:4048/f] куча 4128
a 1 100 [32:48/a] [80:128/a] [208:3920/f] куча 4128
a 2 24 [32:48/a] [80:128/a] [208:48/a] [256:3872/f] куча 4128
a 3 500 [32:48/a] [80:128/a] [208:48/a] [256:528/a] [784:3344/f] куча 4128
a 4 24 [32:48/a] [80:128/a] [208:48/a] [256:528/a] [784:48/a] [832:3296/f] куча 4128
f 1 [32:48/a] [80:128/f] [208:48/a] [256:528/a] [784:48/a] [832:3296/f] куча 4128
f 3 [32:48/a] [80:128/f] [208:48/a] [256:528/f] [784:48/a] [832:3296/f] куча 4128
f 2 [32:48/a] [80:704/f] [784:48/a] [832:3296/f] куча 4128
a 5 600 [32:48/a] [80:624/a] [704:80/f] [784:48/a] [832:3296/f] куча 4128
f 0 [32:48/f] [80:624/a] [704:80/f] [784:48/a] [832:3296/f] куча 4128
f 4 [32:48/f] [80:624/a] [704:3424/f] куча 4128
f 5 [32:4096/f] куча 4128Каждый блок напечатан как смещение нагрузки от начала региона, размер и признак: a занят, f свободен. Пройди по строкам, здесь весь урок на одном экране.
- Первая строка: куча была пуста,
growвзял у регионаchunkв 4096 байт, итого 32 служебных плюс 4096. Запрос на 24 байта стал блоком в 48, остаток в 4048 отрезан. a 1 100дал блок в 128 байт, как и обещала таблицаadjust.f 1это случай 1: оба соседа заняты, блок просто сменил признак.f 3тоже случай 1: справа занятый блок 4.f 2это случай 4. Слева свободный блок на 128, справа свободный на 528, посередине наш на 48: три блока стали одним на 704 байта.a 5 600занял 624 байта в этом блоке, остаток в 80 отрезан. Куча не выросла: без слияния двух дыр в 128 и 528 байт этот запрос ушёл бы в хвост.f 4снова случай 4: свободны сосед слева на 80 и хвост на 3296.- После
f 5в куче один свободный блок на 4096 байт. Ровно это и требует тест: после трассы, которая освобождает всё, остаётся не больше одного блока.
Запусти ту же команду с next и best. На такой короткой трассе раскладки совпадут, расходятся стратегии на длинных.
Практика
В задаче те же две функции, что держат malloc: поиск блока и размещение. Настоящей памяти в песочнице нет, поэтому куча задана срезом слов []usize, а блок называется не адресом, а индексом своего заголовка в срезе. Раскладка прежняя: пустое слово, пролог, блоки, эпилог, в заголовке и теге размер в байтах и бит занятости. В заготовке уже есть pack, sizeAt, isAllocated, nextHeader, mark и build, который собирает кучу из списка блоков.
Напиши findFit с тремя стратегиями и place. Скрытые тесты проверяют:
- три стратегии на куче с дырами 64, 128 и 48 байт, где на запрос в 48 байт они дают три разных ответа;
- пропуск занятых блоков подходящего размера;
- выбор best fit при двух одинаковых дырах;
- заворот next fit в начало кучи и полный круг без находки: здесь легко написать вечный цикл;
- пустую кучу из одного пролога с эпилогом;
placeс остатком ровно в минимальный блок и с остатком в 16 байт, который отрезать нельзя;- согласие заголовков с тегами после
placeи нетронутые слова нагрузки.
Упражнения
Итоги
- Аллокатор стоит между ядром, которое выдаёт память страницами, и программой, которой нужны блоки любого размера. Он берёт оптом и раздаёт в розницу.
- Правила игры: запросы в любом порядке, ответ немедленно, служебные данные в самой куче, выравнивание на 16, занятые блоки двигать нельзя. Из последнего правила вырастает фрагментация.
- Метрик две. Throughput это операции в секунду. Пиковая utilization это наибольшая суммарная нагрузка за историю, делённая на текущий размер кучи. Улучшить одну обычно значит ухудшить другую.
- Внутренняя фрагментация это лишние байты внутри занятых блоков: служебные слова, округление, минимальный размер. Внешняя это свободная память, разбитая на куски меньше запроса; она зависит от будущих запросов, и стратегия поиска от неё не спасает.
- В неявном списке блоки связаны размерами: заголовок хранит размер всего блока, а в свободных из-за выравнивания младших битах лежит признак занятости. У нас слово 8 байт, блок кратен 16, минимум 32, размер блока это
max(32, alignForward(size + 16, 16)). - Пролог и эпилог это вечно занятые служебные блоки по краям кучи. Они убирают проверки границ из обхода и слияния.
- First fit прост и неплох по памяти, next fit быстрее всех и хуже по памяти, best fit лучший по памяти и самый медленный. На
mixed.traceэто 89,2, 73,1 и 92,0 процента. - Разбиение отрезает остаток, только если он тянет на минимальный блок. Иначе остаток уходит во внутреннюю фрагментацию.
- Граничный тег, копия заголовка в конце блока, даёт слияние с левым соседом за константу. Четыре случая слияния сводятся к двум независимым проверкам. Цена: 8 байт на блок, на мелких блоках это заметно.
- Бегунок next fit обязан пережить слияние: перед поглощением блока он отходит назад, после слияния возвращается на начало блока, а цикл поиска всегда проверяет эпилог.
brkдаёт одну непрерывную растущую область на процесс,mmapсколько угодно независимых областей, которые можно вернуть системе по одной. glibc использует оба пути; порогM_MMAP_THRESHOLDпроверяется, только когда куче нечем ответить, и сам растёт послеfreeбольших блоков.- Основные аллокаторы Zig 0.16 работают через
mmap.std.heap.brk_allocatorсуществует, но только для однопоточных сборок и с единоличным доступом кbrk. Наш регион это одинmmapс запасом и своя граница внутри: непрерывность как уsbrk, без конфликта с libc и с работой на macOS. - Проверяльщик кучи пишется первым и зовётся в тестах после каждой операции: ошибка аллокатора проявляется далеко от места, где сделана.
Дальше
У нас есть правильный аллокатор с одним серьёзным недостатком: каждый malloc шагает по всем блокам кучи, включая занятые. На трассе с тысячами живых блоков это доли миллиона операций в секунду там, где системный malloc делает десятки миллионов. В следующем уроке мы это исправим. Свободные блоки свяжутся в явный двусвязный список прямо через свою пустующую нагрузку, вот зачем минимальному блоку 16 байт между заголовком и тегом. Потом список распадётся на шестнадцать списков по классам размеров. Каркас получит таблицу std.mem.Allocator, и наш аллокатор можно будет подставить в любой код на Zig, от std.ArrayList до кучи интерпретатора zl. А в конце мы снимем utilization и throughput всех версий на шести трассах и поставим рядом page_allocator, c_allocator, DebugAllocator и smp_allocator.
домашка