malloc и free под капотом — brk, mmap и аллокаторы

malloc(size) — одна из самых частых функций в любой программе на C/C++. И в Python, и в Go, и в любом другом языке внутри runtime в какой-то момент вызывается malloc (или его аналог). Но что физически делает эта функция? Когда вы запрашиваете 100 байт памяти, что происходит между этой строчкой кода и моментом, когда у вас в руках указатель?

Naivно можно подумать: «malloc вызывает kernel, тот выделяет память, возвращает указатель». Это правда лишь в половине случаев. На самом деле malloc — это userspace-функция из libc (или другой библиотеки), которая управляет пулом памяти, заранее запрошенной у kernel. Поход в kernel за памятью — редкое событие, дорогая операция (системный вызов + работа с page tables). Хороший аллокатор минимизирует эти походы.

В этом уроке: системные вызовы brk и mmap, аллокаторы glibc ptmalloc2 / jemalloc / tcmalloc, arenas, fragmentation, и почему один и тот же malloc(100) в разные моменты времени работает с разной задержкой.

Кто кому отдаёт память

Иерархия выглядит так: ваш код -> libc.malloc -> аллокатор -> (иногда) kernel. Аллокатор сидит между вашей программой и kernel как кэш-прослойка.

Ключевая идея: malloc избегает kernel. Большинство вызовов попадают в уже подготовленные free-lists и возвращаются за наносекунды. Поход в kernel (через brk или mmap) — это микросекунды, потому что переключение режима + работа с page tables + zeroing страниц.

Системный вызов brk — двигаем границу кучи

Исторически (с эпохи Unix V7) куча — это просто продолжение data-сегмента процесса. У каждого процесса есть program break — адрес границы между «выделенной памятью кучи» и «свободным виртуальным пространством». Системный вызов brk(addr) устанавливает эту границу в указанный адрес, либо sbrk(delta) сдвигает её на дельту.

Посмотрим на это в strace:

# strace показывает все syscalls. Фильтруем brk и mmap:
strace -e brk,mmap -ff /bin/echo hello 2>&1 | head -20

# Типичный вывод (упрощённо):
# brk(NULL)                = 0x55a3b6e28000     -- запрос текущего break
# mmap(NULL, 8192, ...)    = 0x7f1234567000     -- libc подгружает свои структуры
# mmap(NULL, ...libc.so..) = 0x7f1234500000     -- mapping библиотеки
# brk(NULL)                = 0x55a3b6e28000
# brk(0x55a3b6e49000)      = 0x55a3b6e49000     -- расширили кучу до этого адреса
# write(1, "hello\n", 6)   = 6
# +++ exited with 0 +++

Шаг brk(0x55a3b6e49000) — это libc увеличила кучу на 132 КБ (0x21000 байт). За эту операцию kernel зарегистрировал расширение VMA (Virtual Memory Area) — физическая память пока не выделена. Это и есть «overcommit»: kernel обещает память на бумаге, выделяет физически только по первому обращению.

Ограничение brk: он расширяет один непрерывный регион. Если кто-то аллоцировал mmap-регион сразу за кучей — brk дальше не пройдёт. Поэтому brk используется только для маленьких аллокаций, а большие идут через mmap.

mmap MAP_ANONYMOUS — запрос виртуальной памяти напрямую

Альтернатива brk — системный вызов mmap(NULL, size, PROT_READ|PROT_WRITE, MAP_ANON|MAP_PRIVATE, -1, 0). Kernel находит свободный регион в адресном пространстве (обычно в mmap-region между кучей и стеком), регистрирует VMA и возвращает указатель. MAP_ANONYMOUS означает «без бэкинга файлом» — просто страницы памяти.

Преимущества mmap для аллокатора:

• Гибкое расположение. Каждый кусок — отдельная область, не привязанная к program break.
• Дёшево возвращать. munmap сразу возвращает память в kernel — RSS процесса падает.
• Подходит для больших блоков — не фрагментирует основную кучу.

Поэтому glibc по умолчанию использует mmap для аллокаций >= 128 КБ (MMAP_THRESHOLD):

# Поиграем с порогом через переменную окружения:
cat > big_alloc.c << 'CEOF'
#include <stdio.h>
#include <stdlib.h>

int main(void) {
    void* small = malloc(100);          // через brk
    void* big = malloc(200 * 1024);     // через mmap (200 КБ > 128 КБ)
    printf("Small (brk): %p\n", small);
    printf("Big (mmap):  %p\n", big);
    free(small);
    free(big);
    return 0;
}
CEOF

gcc big_alloc.c -o big_alloc
strace -e brk,mmap,munmap ./big_alloc 2>&1 | grep -E '(brk|mmap|munmap)' | head -10

# Типичный вывод:
# brk(NULL) = 0x55a3b6e28000
# brk(0x55a3b6e49000) = 0x55a3b6e49000          -- расширили кучу
# mmap(NULL, 208896, ...) = 0x7f1234123000      -- 200 КБ отдельным mmap
# munmap(0x7f1234123000, 208896) = 0            -- free для 200 КБ -> munmap

Видно: маленькая аллокация — brk, большая — отдельный mmap, и free для неё сразу триггерит munmap.

ptmalloc2 — штатный аллокатор glibc

glibc по умолчанию использует ptmalloc2 — наследник Doug Lea’s malloc, оптимизированный для многопоточности. Базовые концепции:

• Chunk — единица аллокации. Состоит из заголовка (размер, флаги) и пользовательских данных. Минимальный chunk — 32 байта на x86_64.
• Bin — бакет свободных chunks. Существуют fastbins (для маленьких, 32-128 байт), smallbins, largebins, unsorted bin (промежуточный для слияний).
• Arena — независимая структура аллокатора со своими bins и top chunk. Главная arena — одна, но создаются дополнительные при contention в многопоточке.
• Top chunk — последний (самый верхний) свободный chunk арены. Если запрос не нашёл в bins — режется от top chunk-а. Если top тоже не хватает — arena растёт через brk или mmap.

Алгоритм malloc(size) упрощённо:

1. Округлить size до кратного 16 + добавить заголовок.
2. Если запрос >= MMAP_THRESHOLD — сразу mmap, возвращаем.
3. Найти arena (своя для потока).
4. Поискать в fastbins (для маленьких) или unsorted bin — O(1).
5. Поискать в smallbins/largebins по размеру.
6. Если ничего — отрезать от top chunk.
7. Если top chunk мал — расширить arena (brk или mmap нового сегмента).

free(ptr):

1. По указателю восстановить заголовок chunk (он за 16 байт до ptr).
2. Положить в fastbin (если маленький) или попробовать слить с соседями и положить в unsorted bin.
3. Изредка консолидировать unsorted -> small/large bins.
4. Если chunk был mmap-ed — сразу munmap, возвращаем kernel.

Альтернативы: jemalloc, tcmalloc, mimalloc

ptmalloc2 — не единственный. Большие проекты часто используют альтернативы:

• jemalloc (Facebook, BSD-shipped). Снижает фрагментацию, scalable на много ядер. Используется в FreeBSD по умолчанию, в Redis, в Rust до 2018 года. Лучше распределяет аллокации по arenas.
• tcmalloc (Google). Thread-Caching malloc. У каждого потока локальный кэш для маленьких chunks — нулевая contention. Используется в Chrome, в Google-инфре.
• mimalloc (Microsoft). Современный, упор на скорость и low-latency. Используется в .NET 7+.

Подключение — через LD_PRELOAD без перекомпиляции:

# Установить jemalloc:
sudo apt install libjemalloc2

# Запустить программу с jemalloc вместо glibc malloc:
LD_PRELOAD=/usr/lib/x86_64-linux-gnu/libjemalloc.so.2 ./my_program

# Проверить, какой malloc используется:
ldd ./my_program | grep -E 'libjemalloc|libtcmalloc|libc.so'

В реальных проектах смена аллокатора часто даёт 5-20% ускорение на нагруженных серверах. Например, Redis под jemalloc стабильно быстрее и с меньшей фрагментацией. Cassandra и Kafka рекомендуют jemalloc.

Фрагментация — невидимый враг

Идеальная аллокация — когда вся выделенная память используется. На практике у вас бывает фрагментация: суммарно свободного места много, но непрерывного куска нужного размера нет.

Два вида:

1. External fragmentation. Свободные chunks разбросаны между занятыми. malloc(1MB) не находит непрерывный 1 МБ, хотя свободных байт суммарно 5 МБ. ptmalloc2 борется через consolidation — сливает соседние свободные chunks.

2. Internal fragmentation. Аллокатор выдал больше, чем запрошено, потому что размеры округляются до bin-size. malloc(33) вернёт chunk на 48 байт — 15 байт впустую.

Симптомы фрагментации в проде: RSS процесса растёт со временем, хотя живой памяти осталось столько же. У long-running серверов это частая проблема. Решения:

• jemalloc / tcmalloc — меньше склонны к фрагментации, чем ptmalloc2.
• Размер chunks под нагрузку — если знаете, что много аллокаций по 200 байт, можно использовать pool allocator.
• malloc_trim(0) — попросить glibc вернуть свободные страницы kernel.
• Перезапуск процесса — грубый, но рабочий способ.

# Посмотреть статистику malloc у процесса (glibc):
cat > stats.c << 'CEOF'
#include <malloc.h>
#include <stdio.h>
#include <stdlib.h>

int main(void) {
    void* ptrs[10000];
    for (int i = 0; i < 10000; i++) ptrs[i] = malloc(rand() % 1024);
    for (int i = 0; i < 10000; i += 2) free(ptrs[i]);  // free каждый второй
    malloc_info(0, stdout);  // вывод XML со статистикой
    return 0;
}
CEOF

gcc stats.c -o stats && ./stats 2>&1 | head -20
# Видите статистику по arenas, sizes, available chunks

Попробуй сам

Запустите простую программу и посмотрите, сколько brk/mmap делает glibc:

# Подсчитать кол-во brk и mmap при старте echo:
strace -c -e brk,mmap,munmap /bin/echo hello

# Типичный вывод:
# % time     seconds  usecs/call     calls    errors syscall
# ------ ----------- ----------- --------- --------- ----------------
#  60.00    0.000060          15         4           mmap
#  40.00    0.000040          20         2           brk
# ------ ----------- ----------- --------- --------- ----------------
# 100.00    0.000100                     6                  total

Теперь сделайте то же для Python:

strace -c -e brk,mmap,munmap python3 -c 'pass' 2>&1 | tail -10

# У Python стартовая инициализация делает сотни mmap-ов
# (загружает стандартную библиотеку, инициализирует свои арены)

Сравните с подменой аллокатора:

LD_PRELOAD=/usr/lib/x86_64-linux-gnu/libjemalloc.so.2 \
  strace -c -e brk,mmap,munmap python3 -c 'pass' 2>&1 | tail -10

# Будет немного другая картина -- jemalloc не использует brk вовсе,
# только mmap

Это даёт интуицию: каждая программа на старте делает десятки syscalls только для инициализации памяти. И именно поэтому fork/exec дорог — надо заново строить адресное пространство.