Зачем вообще что-то «управлять»

Когда ты в Go пишешь make([]byte, 100) или в C зовёшь malloc(100), кто-то должен найти в куче (heap) свободные 100 байт, отдать их тебе, а потом, когда ты закончишь, принять обратно. Этот «кто-то» — аллокатор памяти.

Аллокатор — это как администратор гостиницы. У него есть здание (область кучи), разбитое на номера разного размера. Гости (твои объекты) приходят и просят комнату под свои нужды: кому одноместный на 16 байт, кому люкс на 4 КБ. Админ ведёт журнал: какие номера заняты, какие свободны, какого они размера. Когда гость выезжает (free), номер снова идёт в журнал свободных.

Главная боль аллокатора — фрагментация: свободного места вроде много, но оно раскидано мелкими кусочками, и большой запрос разместить некуда. Представь гостиницу, где свободны комнаты 1, 3, 5, 7 — всего четыре комнаты пустуют, но семью из четырёх человек в одну смежную комнату не поселить.

Эта глава — про то, как аллокатор ведёт учёт свободного места и принимает решения. Тесно связана с двумя соседними:

• В главе API памяти, стек vs куча мы разобрали, кто и когда зовёт malloc/free и почему куча — это «ручной» режим. Здесь — что происходит внутри malloc.
• В главе Сегментация и фрагментация фрагментация возникала на уровне физической памяти и сегментов. Здесь та же беда, но внутри одной кучи процесса. Идеи (splitting, склейка) — те же.

Free list: журнал свободных кусков

Аллокатор хранит список свободных кусков памяти — free list (список свободного). Это связный список: каждый свободный кусок содержит свой размер и указатель на следующий свободный кусок. Сам список живёт прямо внутри свободной памяти — ведь она всё равно никем не используется, почему бы не записать туда служебные данные.

Представим кучу размером 30 байт. Заняты байты 10–19 (там лежит чей-то объект), а свободны 0–9 и 20–29. Free list выглядит так:

            куча (30 байт), адреса 0..29
   ┌──────────┬──────────────┬──────────┐
   │ свободно  │   ЗАНЯТО     │ свободно  │
   │  0..9     │   10..19     │  20..29   │
   └──────────┴──────────────┴──────────┘
        ▲                          ▲
        │                          │
   head ─┘                          │
        │  size=10                  │  size=10
        │  next ───────────────────┘
        │                          next = NULL
        └─► [блок A]            [блок B]
 
   free list:  head → A(addr=0,len=10) → B(addr=20,len=10) → NULL

Что здесь нарисовано: куча на 30 байт, посередине занятый кусок, а два свободных куска связаны в цепочку. head — точка входа аллокатора в список. Когда придёт запрос «дай N байт», аллокатор пойдёт по этой цепочке и будет искать подходящий кусок.

Заголовки блоков: где спрятан размер

Тут возникает хитрый вопрос. Ты зовёшь free(ptr), передавая только указатель. Откуда аллокатор узнает, сколько байт освобождать? Ведь ты не передаёшь размер.

Ответ: аллокатор хранит размер сам — в заголовке блока (header), расположенном чуть перед тем указателем, что он тебе вернул. Когда ты просишь N байт, аллокатор на самом деле откусывает N + размер_заголовка, в начале пишет заголовок, а возвращает тебе указатель уже после заголовка.

   что выделил аллокатор при malloc(20):
   ┌────────────────────┬───────────────────────────────┐
   │   HEADER (напр.16)  │      твои данные (20 байт)     │
   │  size=20            │                               │
   │  magic=0x1234567    │   <─ ptr, который ты получил   │
   └────────────────────┴───────────────────────────────┘
    ▲                     ▲
    │                     │
 ptr-16                  ptr   (free(ptr) читает ptr-16,
                                 находит size и magic)

Что здесь нарисовано: реальный блок состоит из заголовка и пользовательских данных. free(ptr) просто отступает назад на размер заголовка, читает оттуда размер и кладёт весь блок (header + данные) обратно в free list.

magic — это контрольное число. Если при free оно не совпало — значит ты испортил память до начала блока (классический buffer overflow) или передал не тот указатель. Так аллокаторы ловят порчу кучи.

Важный вывод для джуна: каждая аллокация стоит дороже, чем кажется. Просишь 20 байт — реально тратится 20 + заголовок (часто 8–16 байт) + выравнивание. Вот почему миллион мелких malloc(8) — это катастрофа по памяти: накладные расходы на заголовки могут превысить полезные данные.

Splitting: отрезаем кусок от большого

Что если в free list лежит кусок на 20 байт, а просят всего 1 байт? Отдавать весь кусок жалко — 19 байт пропадут. Аллокатор делает splitting (расщепление): отрезает от большого блока ровно нужный кусочек, а остаток оставляет в списке.

   ДО splitting — просим 4 байта, в списке два куска по 10:
   head → [A: addr=0, len=10] → [B: addr=20, len=10] → NULL
 
   аллокатор берёт, скажем, кусок B, режет его:
   ┌─────────────────────────────────────────┐
   │ B был:  addr 20 ......... 29  (len=10)    │
   │ режем:  [20..23]=отдаём  [24..29]=остаток │
   └─────────────────────────────────────────┘
 
   ПОСЛЕ splitting:
   head → [A: addr=0, len=10] → [B': addr=24, len=6] → NULL
                                  ▲
                                  остаток в списке
   а адреса 20..23 ушли пользователю (с заголовком).

Что здесь нарисовано: из свободного куска на 10 байт отрезали 4 байта пользователю, а 6 байт «обрезок» остались в free list под новым адресом. Так список не теряет память, но кусков становится больше и они мельче — зародыш фрагментации.

Coalescing: склеиваем соседей

Обратная операция. Освобождаешь кусок, а рядом в куче уже лежит свободный сосед. Если просто кинуть освобождённый блок в список, получится два мелких соседних свободных куска — и большой запрос между ними не влезет, хотя физически место смежное. Поэтому при free аллокатор проверяет соседей и coalescing (склеивает) смежные свободные куски в один большой.

   ДО coalescing — освободили средний блок:
   ┌──────────┬──────────┬──────────┐
   │ свободно  │свободно→ │ свободно  │
   │  len=10  │  len=10  │  len=10  │
   └──────────┴──────────┴──────────┘
   free list: 3 отдельных куска по 10  (макс. запрос = 10!)
 
   ПОСЛЕ coalescing — три соседа смежны, склеиваем:
   ┌──────────────────────────────────┐
   │          свободно len=30          │
   └──────────────────────────────────┘
   free list: 1 кусок на 30  (теперь влезает запрос до 30)

Что здесь нарисовано: три смежных свободных куска по 10 байт сливаются в один на 30. До склейки мы не могли выдать даже 11 байт подряд, после — можем выдать до 30. Это лечит внешнюю фрагментацию.

Внутренняя vs внешняя фрагментация

Два разных вида потерь — джуны их путают, на собесе любят спросить разницу.

Внешняя фрагментация (external) — свободная память есть, но разбита на мелкие несмежные куски, и большой непрерывный запрос разместить негде. Это та самая «гостиница с разбросанными пустыми номерами». Лечится склейкой (coalescing) и удачным выбором куска.

Внутренняя фрагментация (internal) — аллокатор выдал больше, чем просили, и лишнее внутри блока простаивает. Например, аллокатор работает блоками фиксированного размера 16 байт, а ты попросил 9 — 7 байт внутри блока пропадут. Сюда же относятся накладные расходы на заголовки и выравнивание.

   ВНЕШНЯЯ: место есть (4+4=8 свободно), но не подряд
   [занято][своб 4][занято][своб 4]   <- запрос на 6 не влезает
 
   ВНУТРЕННЯЯ: выдали блок 16 под запрос 9
   ┌────────────────────────────────┐
   │ данные(9) │ ПРОСТОЙ(7) впустую   │
   └────────────────────────────────┘

Стратегии выбора: first / best / worst fit

Когда в free list несколько подходящих кусков, какой взять? Это и есть стратегия размещения. Разберём на одном примере. В списке есть куски: 10, 30, 20 (в порядке цепочки). Приходит запрос на 15 байт.

   free list:  head → [10] → [30] → [20] → NULL
   запрос: 15
 
   FIRST FIT  — берём первый, куда влезает:
       10? нет.  30? да! → режем 30 на (15 отдаём)+(15 остаток)
       результат: head → [10] → [15] → [20]
       плюс: быстро (не сканируем весь список)
       минус: засоряет начало списка мелкими обрезками
 
   BEST FIT  — сканируем ВЕСЬ список, берём самый маленький подходящий:
       подходят 30 и 20; меньший — 20 → режем 20 на (15)+(5)
       результат: head → [10] → [30] → [5]
       плюс: оставляет крупные куски целыми, малый остаток
       минус: медленно (полный обход), плодит крошечные обрезки (тут 5)
 
   WORST FIT — берём самый БОЛЬШОЙ кусок:
       самый большой — 30 → режем на (15)+(15)
       результат: head → [10] → [15] → [20]
       идея: остаток будет крупным и пригодным. на практике — худший:
       и список сканирует целиком, и крупные куски быстро мельчают

Что здесь нарисовано: один и тот же запрос три стратегии обслуживают по-разному и оставляют разный «мусор». First fit жертвует качеством ради скорости; best fit — наоборот; worst fit обычно проигрывает обоим.

На практике чистый best/worst fit почти не используют — слишком дорого сканировать список на каждый malloc. Реальные аллокаторы идут другим путём.

Как это устроено в реальных аллокаторах

Один глобальный free list со сканированием — это медленно и плохо масштабируется на многоядерных системах (за список дерётся блокировка). Промышленные аллокаторы вроде tcmalloc (Google) и jemalloc (изначально FreeBSD/Facebook) делают умнее.

Size classes (классы размеров). Вместо «кусок любого размера» память бьётся на фиксированные классы: 8, 16, 32, 48, 64, … байт. Запрос округляется вверх до ближайшего класса. Для каждого класса — свой отдельный список свободных. Тогда выделение — это просто «сними первый блок со списка нужного класса», без всякого поиска и splitting. Цена — внутренняя фрагментация (округление вверх).

Per-thread кэши. У каждого потока (в Go — у каждого P, процессора рантайма) свой локальный кэш блоков. Большинство аллокаций обслуживаются без блокировок, вообще не трогая общий пул. Это ключ к скорости в многопоточке.

   архитектура tcmalloc/jemalloc (упрощённо):
 
   поток1 ─► [thread cache: списки по классам 8/16/32/...]
   поток2 ─► [thread cache: ...]            пусто? добери из ↓
                                   ┌─────────────────────────┐
                                   │ central / arena (общий)  │
                                   └──────────┬──────────────┘
                                    мало страниц? возьми у ↓
                                   ┌─────────────────────────┐
                                   │ ОС: mmap / sbrk (страницы)│
                                   └─────────────────────────┘

Что здесь нарисовано: трёхуровневая иерархия. Быстрый путь — локальный кэш потока (без блокировок). Если там пусто — поток добирает пачку блоков из общего пула. Если и там мало — аллокатор просит у ОС новые страницы через mmap (про это — Память в проде).

Slab-аллокатор в ядре. В ядре Linux объекты одного типа (например, структуры task_struct для процессов) создаются и удаляются постоянно. Slab-аллокатор держит «плиты» (slab) — заранее нарезанные массивы объектов фиксированного типа. Выделить объект = взять готовую ячейку из плиты, освободить = вернуть. Никакого поиска и фрагментации внутри типа. Это частный случай идеи size classes, доведённой до объектов конкретного типа.

Связь с Go и проддействительностью

Аллокатор Go идейно — родственник tcmalloc: те же size classes (около 70 классов), per-P кэши (mcache), центральный пул (mcentral) и куча страниц (mheap). Когда escape analysis (см. API памяти) решает, что объект «убегает» в кучу, его размер округляется до ближайшего класса — отсюда внутренняя фрагментация даже в Go.

Практические следствия, которые реально всплывают в проде:

• Мелкие частые аллокации дороги не только из-за заголовков, но и из-за давления на GC: чем больше объектов, тем чаще и дольше сборки. Отсюда sync.Pool для переиспользования буферов и предвыделение слайсов через make([]T, 0, n).
• Размер имеет значение. Запрос 33 байта округлится до класса 48 — 15 байт внутренней фрагментации. Иногда выгодно подгонять структуры под границы классов.
• Фрагментация кучи — причина, по которой RSS процесса (см. Память в проде) может не падать после освобождения объектов: память вернулась в free list аллокатора, но не отдана ОС.

Что спрашивают на собесе

• В чём разница между внутренней и внешней фрагментацией? Внешняя — свободное место разбито на несмежные куски, большой запрос не влезает. Внутренняя — выдали больше, чем просили (округление до класса, заголовок, выравнивание), и лишнее простаивает внутри блока.
• Как free(ptr) узнаёт размер освобождаемого блока, если ему дали только указатель? Из заголовка блока, который лежит непосредственно перед ptr; аллокатор отступает назад и читает оттуда размер (и magic для проверки порчи).
• Что такое splitting и coalescing и зачем они нужны? Splitting режет большой свободный кусок под мелкий запрос (чтобы не терять остаток). Coalescing склеивает смежные свободные куски в один большой (лечит внешнюю фрагментацию).
• Сравни first fit, best fit, worst fit. First — первый подходящий, быстро, но засоряет начало списка. Best — наименьший подходящий, бережёт крупные блоки, но медленный и плодит крошечные обрезки. Worst — наибольший, на практике худший.
• Почему промышленные аллокаторы (tcmalloc/jemalloc/аллокатор Go) используют size classes и per-thread кэши? Классы размеров убирают поиск и splitting (выделение за O(1)), per-thread кэши убирают борьбу за блокировку на каждом malloc — это критично для многопоточности.
• Почему миллион мелких аллокаций — это дорого? Накладные расходы на заголовки и выравнивание, рост внутренней фрагментации, давление на GC, потеря локальности кэша процессора.