zharkevich.ru
Тихая работа malloc

Тихая работа malloc

· 14 мин чтения

malloc и free — это две функции родом из начала семидесятых, чей код у Кернигана и Ритчи помещался на одной странице. С тех пор их переписывали раз двадцать, через них взламывали браузеры, серверы и игровые консоли, на их устройство писали диссертации, ради их скорости платили зарплаты в Google, Facebook*, Microsoft и FreeBSD. В каждой работающей сейчас программе живёт одна из их вариаций.

Этот пост о людях, которые сделали malloc таким, какой он есть сегодня.

200 строк, которые перевернули C

В 1978 году вышла «The C Programming Language» Брайана Кернигана и Денниса Ритчи. Тонкая жёлтая книжка стала каноном для двух поколений программистов. Глава 8.7 называлась просто: Example: A Storage Allocator. Двести строк кода, односвязный список свободных блоков, поиск first-fit: первый встреченный подходящий кусок отдают наружу. При освобождении блок цепляется обратно в список и склеивается с соседями, если они тоже свободны.

Этого хватило бы для системы, где программа одна, поток один, конкуренции за память ни с кем нет. Юникс семидесятых был как раз таким. В академических курсах по C этот malloc до сих пор используется как первый пример. Не потому что хорош, а потому что в нём видно всё устройство сразу.

Беда была в том, что 200-строчный malloc был слишком примитивен. На каждое выделение он проходил список свободных блоков от начала до подходящего куска, на каждое освобождение проверял соседей. Чем дольше работала программа, тем длиннее становился список и тем медленнее обслуживалась каждая аллокация. В больших программах сам malloc довольно быстро превращался в самую медленную операцию во всём коде, обгоняя по затратам времени и арифметику, и обращения к диску.

Дуг Ли, заведующий своим аллокатором

Дуг Ли преподавал в SUNY Oswego, небольшом университете на берегу озера Онтарио, штат Нью-Йорк. Его специализация — параллельное программирование, синхронизация, языки программирования. В 1987-м он сел и написал свой malloc, назвав его dlmalloc, Doug Lea’s malloc. Это была побочная работа. Главным проектом Ли всегда оставалась java.util.concurrent, стандартный пакет конкурентных коллекций Java, которым теперь пользуется каждый Java-программист на планете.

Но dlmalloc оказался слишком хорош, чтобы остаться побочной работой. Дуг ввёл бины. Бин (от английского bin, корзина) — это отдельный список свободных блоков примерно одинакового размера. Один бин хранит только блоки около 16 байт, другой около 24, третий около 32 и так далее. Когда программа просит у malloc сколько-то байт, аллокатор сразу идёт в нужный бин и снимает с верхушки его списка готовый блок, не перебирая ничего лишнего. Ещё Дуг добавил boundary tags, служебные поля по краям каждого блока, чтобы при освобождении мгновенно узнавать о соседях. Сделал быстрый путь для мелких выделений и медленный для крупных. Десятилетие dlmalloc стоял в стандартной библиотеке Linux, FreeBSD, в массе встроенных систем и даже в самом GCC.

Дуг выпускал новые редакции dlmalloc вплоть до 2012 года. Его страничка gee.cs.oswego.edu/dl/html/malloc.html выглядит так, будто её сверстали во FrontPage в 1996-м: серый фон, моноширинный шрифт, ссылки голубым цветом. Последняя версия, dlmalloc 2.8.6, выложена в декабре 2012-го. Сорок килобайт исходного текста, который тридцать пять лет служил эталоном.

Гонка с потоками: Вольфрам Глогер и Эмери Бергер

К концу девяностых процессоры стали многоядерными, программы многопоточными, и dlmalloc сдулся. Один мьютекс на всё приводит к тому, что в момент аллокации все потоки выстраиваются в очередь.

Решение нашёл немец Вольфрам Глогер, аспирант Технического университета Мюнхена. В середине девяностых он работал над проектом GNU Hurd, и для него ему нужен был аллокатор, который не блокирует целые процессы. Глогер форкнул dlmalloc и заменил единую кучу на несколько независимых, каждая со своим набором свободных блоков и со своим мьютексом. Такие независимые кучи он назвал аренами. Поток, не нашедший свободной арены, создаёт ещё одну. Спор за общий ресурс распадался на десятки независимых очередей, и потоки переставали друг другу мешать.

Так появился ptmalloc, потом ptmalloc2. В 2006 году ptmalloc2 попал в glibc и до сих пор остаётся аллокатором по умолчанию для всего Linux. Каждое приложение Ubuntu, Debian, Red Hat, каждая Java-виртуалка, каждый сервер на nginx или PostgreSQL дёргает за ниточки, которые натянул Глогер двадцать лет назад. Имя его не знает почти никто, кроме людей, читавших исходники glibc.

Параллельно с ним университетский исследователь Эмери Бергер из Массачусетского университета в Амхерсте опубликовал в 2000-м работу «Hoard: A Scalable Memory Allocator for Multithreaded Applications». Hoard стал первым аллокатором, доказавшим, что многопоточная аллокация может масштабироваться линейно по числу ядер: чем больше ядер, тем выше пропускная способность, и при этом мьютексы вообще не появляются в типичной последовательности вызовов malloc/free. Hoard сегодня используют Adobe и пара крупных проектов, но важнее другое: он стал идейной основой для целого поколения последующих работ. После Hoard у Бергера вышла целая линейка аллокаторов с упором на безопасность и борьбу с фрагментацией: Mesh, DieHard, Snowflake. На YouTube у него один из самых живых каналов в этой области: серьёзные академические лекции, прочитанные простым разговорным языком.

Тройка корпоративных гигантов

В 2005 году во FreeBSD появился новый аллокатор за авторством Джейсона Эванса. Эванс был аспирантом, пишущим базу данных, и ему нужен был аллокатор для собственного проекта. Результат, jemalloc, оказался настолько хорош, что его сделали стандартным для FreeBSD, потом для Firefox, а в 2009-м Эванса позвали в Facebook*, где jemalloc стал основой всей серверной инфраструктуры. До 2019-го jemalloc был аллокатором по умолчанию в Rust. Сейчас это, пожалуй, самый изученный и стабильный аллокатор в опенсорсе.

В Google в том же 2005-м Санджай Гхемават, легендарный соавтор Джеффа Дина по MapReduce, BigTable и почти всему, что сделало Google Google, написал tcmalloc, thread-cached malloc. Идея простая: каждый поток держит свой локальный кеш свободных блоков и почти никогда не лезет в общую кучу. Tcmalloc лёг в основу аллокатора Go и задал шаблон, по которому с тех пор строят все остальные. У Санджая нет твиттера, нет публичной фотографии в полный рост, нет селфи на конференциях. Только код и научные статьи. Журнал The New Yorker написал про него и Дина большой биографический очерк в 2018-м, и это, наверное, самое подробное описание их рабочей кухни в открытых источниках.

В 2019-м Microsoft Research выпустила mimalloc. Автор, голландский исследователь Дан Лейен, известен также как соавтор языка Koka и парсер-комбинаторов Parsec в Haskell. Mimalloc написан как академический эксперимент, но в бенчмарках быстро обогнал и jemalloc, и tcmalloc на типовых нагрузках. Главный трюк — free-list sharding.

То самое разбиение на корзины, которое ввёл Дуг Ли, в современной литературе называют классами размеров (size class в английской терминологии). Любой запрос округляется вверх до ближайшего класса, и для каждого класса аллокатор ведёт свой бин. Лейен заметил, что один общий бин на класс размеров на многоядерных машинах становится узким местом, и раздробил его: теперь у каждой страницы памяти собственный маленький список, и аллокация чаще всего сводится к тому, чтобы снять верхушку короткого списка. На той же конференции Microsoft показала snmalloc, ещё один аллокатор, в основе которого лежит идея обмена сообщениями между потоками. Авторы — команда Мэттью Паркинсона.

Анатомия современного malloc

Когда программа на Linux в 2026-м вызывает malloc(24), происходит вот что.

Сначала проверяется tcache, локальный кеш потока. Каждый поток держит 64 односвязных списка, по одному на каждый класс размеров от 24 до 1032 байт. Если в нужном списке есть блок, он возвращается за наносекунды, без блокировок и без системных вызовов. Это самый быстрый путь, и он покрывает большинство аллокаций.

Если tcache пуст, идёт обращение в fastbins. Это те же LIFO-списки, но уже на уровне арены, под мьютексом. Без слияния с соседями и без сортировки.

Если и fastbins пусты, аллокатор лезет в unsorted bin — карантин, куда падают недавно освобождённые блоки. По дороге через unsorted bin блоки разбираются и разносятся по small bins (точные размеры) и large bins (отсортированные диапазоны).

Если ни в одном бине ничего не нашлось, отрезается кусок от top chunk, верхушки кучи. Если кончился и top chunk, вызывается sbrk(), который двигает границу процесса в адресном пространстве, или mmap(), если запрошен большой блок (от 128 КБ).

Каждый chunk помимо самих данных хранит метаданные: размер, флаги (PREV_INUSE, IS_MMAPPED, NON_MAIN_ARENA), указатели fd/bk для свободных блоков. Минимальный размер блока на 64-битной машине — 32 байта. Это значит, что malloc(1) всё равно выделяет 32 байта; полезная нагрузка теряется в шуме служебной информации.

Phrack и тёмная сторона malloc

Метаданные блоков лежат в той же куче, что и пользовательские данные. Если код записал в свой блок слишком много, он залез в указатели соседа. Если потом аллокатор возьмёт этот соседний блок в работу, получится запись по адресу, который выбрал атакующий.

С 2001 года это знание расцвело пышным цветом. В номере 57 журнала Phrack вышли две легендарные статьи. Vudo malloc tricks за подписью Michel «MaXX» Kaempf разобрала, как переписать произвольный участок памяти, подсунув аллокатору специально подготовленный «освобождённый» блок с фальшивыми указателями fd/bk. Once Upon a free(), опубликованная анонимно, описала ту же атаку под другим углом. Через четыре года, в 2005-м, появилась статья Malloc Maleficarum за подписью Phantasmal Phantasmagoria, чья личность до сих пор неизвестна. Phantasmal каталогизировал восемь техник эксплуатации dlmalloc и дал каждой пышное название: House of Force, House of Mind, House of Lore, House of Spirit, House of Prime. За следующее десятилетие к ним добавили House of Einherjar, House of Orange, House of Roman.

Эти названия не шутка. На зачётах по информационной безопасности студенты до сих пор разбирают, как через House of Force подсунуть в malloc гигантский псевдоразмер, чтобы top chunk пересёк границу с GOT и при следующем выделении вернул указатель прямо в таблицу импортов libc. Дальше дело техники.

Microsoft и Google по своим CVE-сводкам говорят одно: около 70 процентов критических уязвимостей в их продуктах связаны с управлением памятью в C/C++. Хром, ядро Windows, ядро Linux, glibc, Firefox, OpenSSL, sudo. Каждые две недели в bugtraq появляется свежая дыра, которую закрывают и которую кто-то уже использовал. Гонка вооружений между разработчиками glibc (safe unlinking, проверки целостности списков, шифрование указателей в tcache начиная с glibc 2.32) и теми, кто пишет следующий House of, идёт без остановки.

Развод Rust и jemalloc

В январе 2019-го в блоге Rust появляется сухое сообщение: начиная с версии Rust 1.32 jemalloc больше не используется по умолчанию, его место занял системный аллокатор операционной системы. Этому решению предшествовал RFC 1974, в котором замена и предлагалась; его обсуждали полтора года, и обсуждение шло нервно.

Аргументы за развод накопились. На Windows jemalloc вызывал дедлоки, ломал работу Valgrind, добавлял триста килобайт к каждому бинарнику. При встраивании Rust-кода в процессы с собственным malloc (Ruby, Firefox) два аллокатора в одном адресном пространстве начинали мешать друг другу и тормозить.

Прагматики настаивали: просто берите то, что даёт операционная система. Идеалисты возражали, что это шаг назад: сам rustc терял на компиляции до десяти процентов скорости. И теряет до сих пор: команда rustc оставила jemalloc у себя в компиляторе, потому что отказ от него означал заметное замедление сборки. Атрибут #[global_allocator] теперь точечный инструмент: хочешь jemalloc — добавь tikv-jemallocator в зависимости и одну строчку в main.rs. Хочешь mimalloc — три строчки.

Четыре языка, четыре философии

Современные языки решают задачу управления кучей по-разному. Подходы расходятся настолько, что код, выглядящий снаружи похоже, под капотом ведёт себя совершенно несовместимо.

C: голая мощь

char *p = malloc(1024);
if (!p) abort();
free(p);

Шесть строк, сорок восемь лет истории, бесконечная цепочка способов наломать дров. Полный ручной контроль, никакой защиты.

Rust: безопасность через тип

В Rust ручной malloc спрятан за ключевым словом unsafe, и эта пометка — главное психологическое препятствие, которое язык ставит между программистом и катастрофой. Обычный код пользуется Vec, Box, String, HashMap, и за каждой такой структурой стоит вызов глобального аллокатора, по умолчанию системного.

Подменить аллокатор на mimalloc, три строки:

#[global_allocator]
static GLOBAL: mimalloc::MiMalloc = mimalloc::MiMalloc;

fn main() {
    let v: Vec<i32> = (0..1000).collect();
    println!("{}", v.len());
}

Все стандартные коллекции автоматически переходят на новый аллокатор. Ownership и borrow checker не дают пользоваться уже освобождённой памятью, а двойное освобождение в безопасном коде попросту не пройдёт через компилятор.

Полный пример: alloc_demo.rs.

Go: аллокатор, которого нет в коде

В Go программист никогда не пишет malloc. Вся аллокация прячется за make, new, литералами слайсов и мап. Под капотом стоит трёхуровневый аллокатор, скопированный с tcmalloc: mcache без блокировок на каждом логическом процессоре, mcentral с блокировкой на span-лист и mheap как глобальная куча с системными вызовами.

v := make([]int, 0, 1000)
for i := range 1000 {
    v = append(v, i)
}

Главный механизм оптимизации — escape analysis: компилятор смотрит, не утекает ли указатель за границы функции, и если нет, переменная едет на стек, и mcache вообще не дёргается. Команда go build -gcflags='-m' показывает решения escape analysis по строкам.

Полный пример: alloc_demo.go.

Zig: явный параметр

В Zig нет ни сборщика мусора, ни глобального malloc по умолчанию. Каждая структура данных, которая может выделять память, требует на вход аллокатор. Это самая чистая инкарнация принципа «никаких скрытых аллокаций» в современных языках.

const std = @import("std");

pub fn main() !void {
    var dbg: std.heap.DebugAllocator(.{}) = .init;
    defer _ = dbg.deinit();
    const gpa = dbg.allocator();

    var list: std.ArrayList(i32) = .empty;
    defer list.deinit(gpa);
    for (0..1000) |i| try list.append(gpa, @intCast(i));
    std.debug.print("len={d} cap={d}\n", .{ list.items.len, list.capacity });
}

Стандартная библиотека предлагает: page_allocator (тонкая обёртка над mmap/VirtualAlloc), FixedBufferAllocator (выделение из заранее заданного буфера, может жить на стеке), ArenaAllocator (bump allocation, освобождение всего разом, в 0.16 стал потокобезопасным и lock-free), DebugAllocator (с проверкой use-after-free, double-free и переполнений; пришёл на смену GeneralPurposeAllocator), c_allocator (обёртка над libc malloc), smp_allocator (быстрый thread-aware вариант).

В Zig 0.16 появилась «сочная» точка входа std.process.Init, которая подаёт в main уже готовые arena, gpa и io. Получается, что разработчик начинает работать с памятью с первой строчки, а не с ритуала её настройки.

Полный пример, проверенный на Zig 0.16.0: alloc_demo.zig.

Nim: ARC, ORC и доступ к голому железу

Nim — язык с синтаксисом уровня Python, который компилируется в C и при этом даёт выбор стратегии управления памятью на уровне ключа компилятора. С версии 2.0 (2023) по умолчанию работает ORC: подсчёт ссылок плюс отдельный сборщик циклических ссылок. Освобождение детерминированное, без stop-the-world пауз. Если циклов гарантированно нет, можно компилироваться с --mm:arc и получить чистый ref-count без накладных расходов.

import std/posix

# Стандартная куча Nim (под управлением ORC)
var s: seq[int] = @[]
for i in 0..<1000: s.add i
echo "seq len=", s.len

# Прямой mmap через posix
let pagesize = sysconf(SC_PAGESIZE)
let p = mmap(nil, pagesize, PROT_READ or PROT_WRITE,
             MAP_PRIVATE or MAP_ANON, -1, 0)
if p == MAP_FAILED: quit "mmap failed"
cast[ptr UncheckedArray[byte]](p)[0] = 42
discard munmap(p, pagesize)
echo "mmap → ", pagesize, " байт получены и возвращены"

Главное достоинство Nim, которое часто упускают: возможность плавно переходить между уровнями. На 90 % кода можно писать в стиле Python с автоматической памятью, а в местах, где важна каждая микросекунда, спуститься к alloc/dealloc (обычный malloc), allocShared (разделяемая между потоками куча) или прямому mmap через модуль posix. Один и тот же файл может содержать высокоуровневый ORC-код и ручную работу со страницами ОС.

Полный пример: alloc_demo.nim.

Арены: возвращение к простоте

Слово «арена» в мире malloc обозначает две похожие, но не одинаковые вещи. У Глогера арена была самостоятельным экземпляром обычной кучи: со своими бинами, своим списком свободных блоков, своим мьютексом. Несколько таких арен внутри одного процесса нужны были для того, чтобы потоки не упирались друг в друга на блокировках.

После сорока лет усложнений набирает популярность совсем другая разновидность арены, гораздо более примитивная. Программа берёт у ОС один большой кусок памяти, скажем, 64 килобайта или 16 мегабайт. Внутри этого куска она держит один-единственный указатель, его обычно называют bump pointer, «толкаемый указатель». При каждой просьбе выделить N байт указатель сдвигается на N вперёд, а адрес, где он стоял до сдвига, возвращают вызвавшему. Освобождать отдельные объекты нельзя: указатель назад не двигается. Зато в нужный момент весь кусок отдают системе целиком или просто сбрасывают bump pointer в начало, и арена снова пустая.

Ни списка свободных блоков, ни учёта, ни слияния соседей. Служебных данных у такой арены нет, само выделение обычно укладывается в одну машинную инструкцию.

Этот подход живёт в компиляторах (узлы синтаксического дерева в rustc, GCC и LLVM никогда не освобождают по одному, они просто исчезают вместе с обработкой исходного файла), в игровых движках (одна арена на кадр, после отрисовки кадра арена очищается), в веб-серверах (одна арена на HTTP-запрос, после ответа всё стирается), в DNS-резолверах, в JIT-компиляторах. Цена удобства: программист должен заранее знать, у каких объектов общая судьба, чтобы их можно было выкинуть одновременно.

Zig принял такую арену в стандартную библиотеку с первого дня, а в версии 0.16 она ещё стала потокобезопасной. В Rust ту же роль играют пакеты bumpalo и typed-arena. В Go близкий по духу инструмент — sync.Pool для переиспользования объектов. В Nim арену поверх alloc пишут за тридцать строк.

В каком-то смысле это возврат к мысли Дуга Ли тридцатилетней давности: аллокатор должен делать одну простую вещь хорошо, всё остальное это уровень приложения.

Сорок восемь лет

Деннис Ритчи умер в октябре 2011-го, через несколько дней после Стива Джобса. Брайан Керниган преподаёт в Принстоне и пишет книги. Дуг Ли по-прежнему в Освего. Вольфрам Глогер давно ушёл из активной разработки glibc, но его арены крутятся в каждом запущенном Linux. Джейсон Эванс много лет вёл jemalloc внутри Facebook*, потом ушёл в стартап. Санджай Гхемават всё ещё в Google. Дан Лейен в Microsoft. Эмери Бергер в Массачусетском университете.

Их код работает, когда вы открываете браузер, отправляете сообщение, оплачиваете покупку, заходите в банк, играете в любую игру, печатаете в IDE этот текст. Никто из них не получил «Тьюринга». Их работа лежит на четырёх или пяти уровнях ниже того, что обычно замечают.

И это, наверное, главная мораль истории malloc. Самая важная инфраструктура та, о которой не думают.

* Facebook принадлежит корпорации Meta, признанной в Российской Федерации экстремистской организацией и запрещённой на её территории.

Источники

Предыдущий
Наверх