Перейти к содержанию

malloc и free: как это работает внутри

Когда вы вызываете malloc(100), происходит больше, чем просто «выделить 100 байт». glibc поддерживает сложную структуру — heap — чтобы сотни тысяч маленьких аллокаций не превращались в сотни тысяч syscall'ов.

Реализация в glibc называется ptmalloc2, написанная Wolfram Gloger на основе dlmalloc Дуга Ли.

Heap и syscalls

Heap — регион виртуальной памяти, начинающийся сразу за BSS-сегментом. glibc расширяет его двумя способами:

  • brk(2) — сдвигает «program break», верхнюю границу heap. Используется для обычных аллокаций.
  • mmap(MAP_ANONYMOUS) — выделяет отдельный анонимный регион. Используется для блоков ≥ 128 KB; при free возвращается через munmap.

brk нельзя двигать бесконечно: heap ограничен RLIMIT_DATA (ulimit -d) и виртуальным адресным пространством. Когда sbrk для main arena возвращает (void*)-1, glibc не падает сразу — sysmalloc() делает fallback на mmap(MAP_ANONYMOUS). NULL из malloc получается только если и mmap тоже не смог выделить память. На 64-битных системах до этого доходит редко (128 TB виртуального адресного пространства на процесс), но на 32-битных (3 GB user space) это была реальная проблема.

# Посмотреть, что реально делает malloc в вашей программе
strace -e trace=brk,mmap,munmap ./prog

Chunk

Каждый блок памяти — занятый или свободный — имеет header. У занятого chunk'а структура такая:

          ┌────────────────────────────────┐
chunk ──▶ │ prev_size           (8 байт)   │  размер предыдущего chunk,
          │                                │  если он свободен; иначе — данные
          ├────────────────────────────────┤
          │ size | P | M | N   (8 байт)    │  размер + флаги в младших битах
          ├────────────────────────────────┤
ptr ────▶ │ данные пользователя            │  ← malloc возвращает указатель сюда
          │ ...                            │
          └────────────────────────────────┘

Флаги в поле size (размер всегда кратен 16, поэтому три младших бита свободны):

Флаг Бит Значение
PREV_INUSE (P) 0 предыдущий chunk занят
IS_MMAPPED (M) 1 chunk выделен через mmap, не из heap
NON_MAIN_ARENA (N) 2 chunk принадлежит не main arena

Минимальный размер chunk на x86-64 — 32 байта.

У свободного chunk'а данные пользователя не нужны, поэтому то же пространство используется для указателей бина:

          ┌────────────────────────────────┐
chunk ──▶ │ prev_size           (8 байт)   │
          ├────────────────────────────────┤
          │ size | flags        (8 байт)   │
          ├────────────────────────────────┤
          │ fd                  (8 байт)   │  forward ptr — следующий chunk в bin
          ├────────────────────────────────┤
          │ bk                  (8 байт)   │  back ptr — предыдущий chunk в bin
          ├────────────────────────────────┤
          │ fd_nextsize         (8 байт)   │  только у largebins:
          │ bk_nextsize         (8 байт)   │  прыжок к следующему размеру
          └────────────────────────────────┘

Bins

Когда вы вызываете free, glibc не отдаёт память сразу обратно в ОС — chunk попадает в один из bins. При следующем malloc подходящего размера glibc достаёт chunk оттуда. Это на порядки быстрее, чем каждый раз делать syscall.

Bin Диапазон Структура Особенность
tcache 16–1032 байт per-thread LIFO без блокировок, без coalescing
fastbins 16–112 байт LIFO без immediate coalescing
smallbins 32–1008 байт FIFO, doubly-linked coalescing при free
largebins ≥ 1024 байт sorted, doubly-linked best-fit поиск
unsorted bin любой FIFO буфер временное хранилище

Tcache

Tcache появился в glibc 2.26 и сейчас — самый быстрый путь. Каждый поток имеет свою tcache_perthread_struct с 64 односвязными списками (LIFO) для размеров от 16 до 1032 байт с шагом 16:

tcache_perthread_struct (per-thread)
┌────────────┬────────────┬─────────────┬─────┐
│ counts[64] │            │             │ ... │  ← кол-во chunk'ов в каждом списке
├────────────┴────────────┴─────────────┴─────┤
│ entries[0]  entries[1]  entries[2]    ...   │  ← head-указатели
└──────┬──────────┬───────────────────────────┘
       │          │
       ▼          ▼
  [chunk]    [chunk] ──▶ [chunk] ──▶ NULL
  size=32    size=48

Каждый список вмещает до 7 chunks. Если список полон — chunk идёт в fastbin или дальше.

Tcache не делает coalescing и не проверяет целостность указателей — отсюда его уязвимость к атакам типа tcache poisoning.

Fastbins

Fastbins — односвязные LIFO-списки для небольших chunks (16–112 байт, 10 bins с шагом 16). Верхняя граница определяется константой DEFAULT_MXFAST = 128 байт (chunk size) на x86-64, что соответствует 112 байтам полезной нагрузки. Каждый bin хранит только chunks одного размера:

fastbin[0] (size=32)
┌──────┐
│ head │──▶ [chunk] ──▶ [chunk] ──▶ [chunk] ──▶ NULL
└──────┘       fd          fd          fd

Fastbins намеренно не делают immediate coalescing — это их главное свойство. Если вы выделяете и освобождаете много маленьких объектов одного размера, fastbin позволяет переиспользовать их мгновенно. Объединение со свободными соседями происходит позже, при вызове malloc_consolidate().

Smallbins и largebins

Smallbins (32–1008 байт) — кольцевой двусвязный список. Каждый chunk хранит два указателя: fd (forward, на следующий) и bk (backward, на предыдущий). Голова списка — запись bins[] в malloc_state.

smallbin[n]  —  кольцевой двусвязный список, FIFO

 malloc_state           самый старый             самый новый
 ┌──────────┐    fd    ┌──────────┐    fd    ┌──────────┐    fd
 │  bins[n] │ ────────▶│ chunk A  │ ────────▶│ chunk B  │ ────────▶ bins[n]
 │  (head)  │ ◀────────│          │ ◀────────│          │ ◀────────
 └──────────┘    bk    └──────────┘    bk    └──────────┘    bk
       ▲                     │
       │                     └── malloc() заберёт chunk A первым (FIFO)
       └── free() вставляет новый chunk сюда (через bk от head)

Все chunks в одном smallbin — одного размера. malloc всегда берёт самый старый chunk (FIFO), что снижает фрагментацию.

Largebins устроены так же, но chunks разного размера и отсортированы по убыванию. Дополнительные указатели fd_nextsize/bk_nextsize формируют второй список только из уникальных размеров — чтобы при best-fit поиске не перебирать все chunks, а прыгать сразу к нужному размеру.

Unsorted bin

Любой освобождённый chunk (кроме tcache/fastbin) попадает сначала в unsorted bin. При следующем malloc glibc перебирает unsorted bin: chunk подходящего размера возвращается сразу, остальные раскладываются по smallbins/largebins.

Top chunk

Top chunk — большой свободный кусок в самом верху heap, всегда выровненный по странице. Если ни один bin не подошёл — malloc отрезает от него кусок нужного размера. Если top chunk кончился — brk или mmap расширяет heap.

heap (main arena, растёт вправо через brk)

низкие адреса                                                   program break
│                                                                     │
▼                                                                     ▼
┌─────────────┬──────────────┬─────────────┬──────────────────────────┐
│   chunk A   │   chunk B    │   chunk C   │       top chunk          │
│   (busy)    │   (free)     │   (busy)    │                          │
│   32 байт   │   128 байт   │   64 байта  │    всё свободное         │
│   P=1       │   P=1        │   P=0 (!)   │    P=1                   │
└─────────────┴──────────────┴─────────────┴──────────────────────────┘
                    │
                    └──▶ в unsorted bin (или smallbin/fastbin)

Arenas

Если бы все потоки шарили один heap, каждый malloc требовал бы захвата глобального mutex'а. Под высокой нагрузкой это узкое место убивает масштабируемость.

Решение — arenas: независимые heap-структуры, каждая со своим mutex'ом. Структура malloc_state описывает одну arena:

malloc_state (arena)
┌──────────────────────────────────┐
│ mutex                            │  ← блокировка arena
│ flags                            │
│ top           ──▶ top chunk      │
│ fastbinsY[10] ──▶ fastbin lists  │
│ bins[128]     ──▶ small/largebins│
│ next          ──▶ следующая arena│
└──────────────────────────────────┘

Когда поток вызывает malloc:

  1. Пробует захватить mutex своей текущей arena
  2. Если arena занята — перебирает linked list arena, ищет свободную
  3. Если все заняты — создаёт новую arena через mmap (до 2 × num_cpu arena)
Thread 1 ──▶ Arena 1 [mutex: free]  ✓ захватывает
Thread 2 ──▶ Arena 1 [mutex: busy]  → ищет дальше
             Arena 2 [mutex: free]  ✓ захватывает
Thread 3 ──▶ Arena 2 [mutex: busy]  → создаёт Arena 3

Main arena (одна) расширяется через brk — у неё доступ к program break. Все остальные arenas выделяют память через mmap кусками по 64 MB (HEAP_MAX_SIZE). В virtual memory это выглядит так:

Virtual memory process (высокие адреса наверху)

┌───────────────────────────────────┐  0xffff...
│           kernel space            │
├───────────────────────────────────┤
│             stack                 │ ↓ растёт вниз
├╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌┤
│                                   │
│  ┌─────────────────────────────┐  │
│  │   Arena 3   (mmap, 64 MB)   │  │  ← дополнительная arena
│  └─────────────────────────────┘  │
│                                   │
│  ┌─────────────────────────────┐  │
│  │   Arena 2   (mmap, 64 MB)   │  │  ← дополнительная arena
│  └─────────────────────────────┘  │
│                                   │
│   libc.so, libstdc++.so, ...      │  ← динамические библиотеки
│                                   │
├╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌╌┤  ← program break (brk)
│   Main Arena heap                 │  ↑ растёт вверх через brk
│   [chunk][chunk] ... [top chunk]  │
├───────────────────────────────────┤
│   BSS / data / text               │
└───────────────────────────────────┘  0x0000...

Tcache не входит в arena — это per-thread структура, живёт на heap'е основного потока, без mutex'а.

Как работает malloc

malloc(size):
  1. size > MMAP_THRESHOLD (≈128 KB)
         → mmap(MAP_ANONYMOUS) напрямую, минуя arenas, IS_MMAPPED = 1

  2. Ищем в tcache своего потока (без блокировки)
         → нашли: возвращаем, готово

  3. Захватываем mutex arena

  4. size <= 112 байт: ищем в fastbins (exact fit)
         → нашли: возвращаем

  5. size <= 1008 байт: ищем в smallbins (exact fit)
         → нашли: возвращаем

  6. Перебираем unsorted bin:
       - exact fit → возвращаем сразу
       - не подходит → раскладываем chunk в small/largebin

  7. Ищем в largebins (best-fit, closest size ≥ запрошенного)
         → нашли: возможно split, возвращаем

  8. Берём кусок от top chunk (split)
         → top chunk кончился: brk/mmap расширяем heap

Как работает free

free(ptr):
  1. ptr == NULL → ничего (гарантия стандарта C)

  2. chunk.IS_MMAPPED == 1 → munmap, готово

  3. Подходит под tcache (≤ 1032 байт, список не полон)
         → кладём в tcache, готово

  4. Подходит под fastbin (≤ 112 байт)
         → кладём в fastbin без coalescing, готово

  5. Иначе — coalescing:
       a. PREV_INUSE == 0: предыдущий chunk свободен
              → backward coalescing: объединяем с prev chunk
       b. Следующий chunk свободен (смотрим его PREV_INUSE)
              → forward coalescing: объединяем с next chunk
       c. Следующий chunk == top chunk
              → объединяем с top, heap «сжимается»
       d. Кладём результат в unsorted bin

Coalescing

Coalescing — объединение смежных свободных chunks, чтобы уменьшить фрагментацию heap'а.

Пример: forward coalescing

До free(B):
┌──────────┬──────────┬──────────────┐
│ chunk A  │ chunk B  │   chunk C    │
│  (busy)  │  (busy)  │   (free)     │
│  P=1     │  P=1     │  P=1 (B=busy)│
└──────────┴──────────┴──────────────┘

После free(B) — C свободен (видно по header'у C), объединяем:
┌──────────┬───────────────────────────┐
│ chunk A  │        chunk B+C          │
│  (busy)  │         (free)            │
│  P=1     │  P=1                      │
└──────────┴───────────────────────────┘

Пример: backward + forward coalescing

До free(B):
┌──────────┬──────────┬──────────────┐
│ chunk A  │ chunk B  │   chunk C    │
│  (free)  │  (busy)  │   (free)     │
│          │  P=0 (!) │  P=1 (B=busy)│
└──────────┴──────────┴──────────────┘

После free(B) — A свободен (P=0 в header'е B), C свободен, объединяем:
┌──────────────────────────────────────┐
│             chunk A+B+C              │
│              (free)                  │
└──────────────────────────────────────┘

glibc определяет, свободен ли предыдущий chunk, по флагу PREV_INUSE в header'е текущего chunk'а. Адрес предыдущего chunk'а — (char*)chunk - prev_size.

Fastbins не делают immediate coalescing — ради скорости. Объединение происходит при malloc_consolidate(), который вызывается, например, при запросе размера в диапазоне largebin.

Фрагментация

После многих аллокаций и free разного размера суммарно свободной памяти может хватать, но непрерывного блока нужного размера нет. glibc не гарантирует устранение фрагментации.

Фрагментированный heap:
┌──────┬────────┬──────┬────────┬──────┬────────┐
│ busy │  free  │ busy │  free  │ busy │  free  │
│  64  │  128   │  64  │   64   │  64  │  128   │
└──────┴────────┴──────┴────────┴──────┴────────┘
Свободно суммарно: 320 байт, но malloc(256) не сработает — нет непрерывного блока

Что делать:

  • Object pool — выделять блоки одного размера, никакой внешней фрагментации.
  • Bump-аллокатор — для данных с одним временем жизни, освобождается целиком.
  • Альтернативные аллокаторы: jemalloc, tcmalloc (Google), mimalloc (Microsoft) — меньше фрагментируются в многопоточных сценариях.

Отладка heap

# Valgrind: утечки, use-after-free, double-free
valgrind --leak-check=full ./prog

# AddressSanitizer: быстрее Valgrind, ловит те же классы ошибок
gcc -fsanitize=address -g prog.c -o prog && ./prog

# Статистика glibc heap прямо из кода
#include <malloc.h>
malloc_stats();          // выводит в stderr
malloc_info(0, stdout);  // детальный XML-формат

Связанные темы

Источники