Управление свободной памятью

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

Когда вы в Go пишете make([]byte, 100) (и значение убегает в кучу) или в C вызываете malloc(100), кто-то должен найти в куче свободные 100 байт, отдать их вам, а потом, когда они станут не нужны, принять обратно. Этот «кто-то» — аллокатор памяти. В C это код библиотеки (например, glibc), в Go — часть рантайма. Ядро ОС в этом почти не участвует: как мы видели в главе API памяти, аллокатор берёт у ядра память большими кусками через brk или mmap и дальше распоряжается ею сам.

Работа аллокатора похожа на работу администратора гостиницы, где номера можно нарезать произвольного размера. Он ведёт журнал свободных мест, по запросу находит подходящее и записывает, что оно занято, а когда гость уезжает (free), возвращает номер в журнал.

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

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

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

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) может потратить на заголовки больше памяти, чем на данные. (Ниже увидим, что аллокаторы с классами размеров, включая аллокатор Go, у мелких объектов заголовков не хранят и узнают размер иначе.)

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. Реальные аллокаторы идут другим путём.

Buddy-аллокатор: как ядро раздаёт страницы

Есть приём, который делает склейку почти бесплатной. Buddy-аллокатор (buddy — «приятель») работает только с блоками размером в степень двойки. Именно так ядро Linux раздаёт физические страницы: блоками по 1, 2, 4, …, 1024 страницы (4 КБ … 4 МБ).

Выделение. Пусть есть свободный блок 64 КБ, а просят 7 КБ. Запрос округляется до ближайшей степени двойки, 8 КБ. Блок делится пополам, пока половина ещё вмещает запрос:

  64 КБ
  ├── 32 КБ                         ├── 32 КБ (свободен)
  │   ├── 16 КБ                     │
  │   │   ├── 8 КБ ← отдали         │
  │   │   └── 8 КБ (свободен)       │
  │   └── 16 КБ (свободен)          │
 
  Внутренняя фрагментация: 8 − 7 = 1 КБ

Две половины одного деления называются приятелями (buddies). Свободные блоки каждого размера лежат в своём списке.

Освобождение. Когда блок освобождают, аллокатор проверяет, свободен ли его приятель. Если да, они склеиваются в блок вдвое больше, и проверка повторяется уровнем выше. Адрес приятеля вычисляется одной операцией: смещение блока XOR его размер. Блок 8 КБ со смещением 8 КБ (0x2000) имеет приятеля со смещением 0x2000 XOR 0x2000 = 0x0000. Никакого поиска соседей по списку.

Плата за простоту — внутренняя фрагментация от округления до степени двойки: запрос на 33 КБ получит 64 КБ. Поэтому buddy используют там, где запросы и так кратны странице.

На Linux состояние buddy-аллокатора видно в /proc/buddyinfo: сколько свободных блоков каждого размера в каждой зоне памяти. Если блоков больших размеров почти нет, физическая память фрагментирована, и выделение, например, huge pages на 2 МБ (см. TLB) может не удаться, хотя свободной памяти в сумме много.

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

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

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

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

   tcmalloc/jemalloc, упрощённо:
 
   поток 1 ─► [локальный кэш: списки по классам 8/16/32/...]
   поток 2 ─► [локальный кэш: ...]          пусто? взять пачку из ↓
                                   ┌──────────────────────────┐
                                   │ центральный пул (общий)   │
                                   └────────────┬─────────────┘
                                  нет страниц? попросить у ↓
                                   ┌──────────────────────────┐
                                   │ ОС: mmap / brk            │
                                   └──────────────────────────┘

Быстрый путь — локальный кэш потока, без блокировок. Если там пусто, поток берёт пачку ячеек из общего пула. Если и там мало, аллокатор просит у ОС новые страницы.

Slab в ядре. Ядро Linux постоянно создаёт и удаляет объекты одних и тех же типов: task_struct для процессов, inode для файлов, структуры сокетов. Slab-аллокатор держит для каждого типа заранее нарезанные страницы с ячейками ровно под этот объект. Это те же классы размеров, только под конкретные типы. В современных ядрах реализация называется SLUB; статистика по кэшам видна в /proc/slabinfo и утилите slabtop.

Связь с Go

Аллокатор Go устроен как tcmalloc. У него 67 классов размеров для объектов до 32 КБ, локальный кэш на каждый P (mcache), центральные списки по классам (mcentral) и куча страниц (mheap), которую рантайм получает у ОС через mmap. Объекты больше 32 КБ выделяются сразу целыми страницами. Когда escape analysis (см. API памяти) решает, что объект уходит в кучу, его размер округляется до класса.

Классы у Go идут так: 8, 16, 24, 32, 48, 64, 80, 96, … Отсюда практические следствия:

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

Частые ошибки

• Считать, что склейка (coalescing) соединяет любые свободные куски. Склеить можно только смежные по адресам.
• Путать splitting с фрагментацией. Splitting — способ не терять остаток; мелкие остатки, которые никому не подходят, — уже внешняя фрагментация.
• Думать, что free или освобождение объекта сборщиком мусора возвращает память ОС. Обычно память возвращается в аллокатор и переиспользуется процессом.

Проверьте себя

1. Free list: куски 12, 7, 25 (в этом порядке). Запрос на 6. Какой кусок возьмут first fit, best fit и worst fit? Что останется в списке после best fit?
2. Аллокатор с заголовком 16 байт. Сколько байт реально уйдёт на malloc(20), если блоки выравниваются по 16 байт?
3. Buddy-аллокатор, свободен блок 128 КБ, запрос на 20 КБ. Какой блок отдадут и сколько будет внутренней фрагментации?
4. Блок 16 КБ со смещением 48 КБ освобождается. По какому смещению лежит его приятель?

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

• В чём разница между внутренней и внешней фрагментацией? Внешняя — свободное место разбито на несмежные куски, большой запрос не влезает. Внутренняя — выдали больше, чем просили (округление до класса, заголовок, выравнивание), и лишнее простаивает внутри блока.
• Как 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, потеря локальности кэша процессора.
• Как работает buddy-аллокатор и где он используется? Блоки степеней двойки, деление пополам при выделении, склейка с «приятелем» (адрес через XOR) при освобождении; так ядро Linux раздаёт физические страницы.