Аллокатор K&R

TL;DR

Аллокатор K&R — учебный распределитель динамической памяти из §8.7 книги «The C Programming Language» (2-е изд., 1988): он выдаёт блоки произвольного размера и принимает их обратно в произвольном порядке. Метаданные лежат в заголовке Header непосредственно перед полезной областью (payload), а свободные блоки связаны в циклический список, упорядоченный по адресам, с нулевым сторожевым узлом base. Выдача идёт по стратегии first-fit: находится первый подходящий блок, при необходимости от него отрезается хвост; освобождение вставляет блок в список и сливает его с соседями. Когда свободной памяти нет, morecore запрашивает у системы новый участок через sbrk. Это не bump-аллокатор из §5.4: там память только выдаётся и освобождается строго в обратном порядке, здесь же работает полноценный список свободных блоков.

Свойство	Значение
Класс	Распределитель динамической памяти общего вида на списке свободных блоков
Стратегия	First-fit с «плавающим» указателем freep, отрезание хвоста, слияние соседей
Изобретение	Учебный пример K&R: 2-е изд. 1988, §8.7 [1]; пример есть уже в 1-м изд. 1978 [2]. Не первый аллокатор: схемы с границами блоков и first-fit описаны у Кнута [3]
Операции	Alloc(n) — выдать блок; Afree(p) — вернуть блок; Morecore(nu) — получить память у системы
Время Alloc	[math]\displaystyle{ O(k) }[/math] по числу просмотренных свободных блоков, худшее [math]\displaystyle{ O(m) }[/math]; при исчерпании добавляется Morecore
Время Afree	[math]\displaystyle{ O(k) }[/math] на поиск места вставки
Время Morecore	[math]\displaystyle{ O(k) }[/math] на Afree плюс стоимость системного вызова sbrk; модель [math]\displaystyle{ O(nu + k) }[/math] — если sbrk считать за [math]\displaystyle{ O(nu) }[/math]
Память	[math]\displaystyle{ O(1) }[/math] служебной сверх блоков; заголовок [math]\displaystyle{ H }[/math] байт на блок; внутренние потери до [math]\displaystyle{ H-1 }[/math] байт
Порядок	Свободный список упорядочен по адресам циклически; порядок выдачи зависит от истории операций
Фрагментация	Внешняя возможна; внутренняя не больше [math]\displaystyle{ H-1 }[/math] байт на блок; компактификации нет
Выравнивание	Полезная область выровнена по alignof(Header); в K&R — по границе long
Потокобезопасность	Нет: глобальные base и freep, общий список, нет блокировок
Альтернативы	Bump-аллокатор §5.4, dlmalloc/ptmalloc, jemalloc/tcmalloc, mmap, арены и пулы объектов
Где встречается	Обучение C и указателям, исторические Unix-аллокаторы, встраиваемые арены, простые пулы

Определения

Распределитель памяти (storage allocator) — программный компонент, который по запросу выдаёт участок памяти заданного размера и принимает его обратно; формально это пара операций [math]\displaystyle{ Alloc : \mathbb{N} \to P \cup \{\mathrm{NIL}\} }[/math] и [math]\displaystyle{ Afree : P \to \{\mathsf{ok}\} }[/math], где [math]\displaystyle{ P }[/math] — множество указателей на полезные области. Аллокатор поддерживает инвариант: выданные области не пересекаются между собой и со свободными.

Куча (heap) — область памяти, из которой берутся динамические объекты; арена (arena) — конкретный непрерывный участок, из которого аллокатор нарезает блоки. В K&R арена — это область, получаемая последовательными вызовами sbrk; в нашей реконструкции — статический массив arena.

Блок (block) — непрерывный участок арены из [math]\displaystyle{ s \ge 1 }[/math] единиц, первая из которых занята заголовком, а остальные [math]\displaystyle{ s-1 }[/math] — полезной областью (payload). Блок задаётся парой [math]\displaystyle{ (h, s) }[/math], где [math]\displaystyle{ h }[/math] — индекс единицы заголовка, [math]\displaystyle{ s }[/math] — размер в единицах; блок занимает единицы [math]\displaystyle{ [h, h+s) }[/math].

Заголовок (header) — служебная запись в начале блока. В K&R это объединение Header с полями next (указатель на следующий свободный блок) и size (размер блока в единицах, включая сам заголовок). Заголовок есть у каждого блока — и свободного, и занятого; у занятого блока поле next не используется.

Единица (unit) — квант размера, равный [math]\displaystyle{ H = \text{sizeof(Header)} }[/math] байт. Все размеры блоков и все смещения в алгоритме считаются в единицах, а не в байтах. Это избавляет от деления и округления на каждом шаге и гарантирует, что полезная область начинается с выровненного адреса.

Список свободных блоков (free list) — циклический список, в который включены все свободные блоки. В K&R он упорядочен по адресам: если идти по ссылкам next, адреса блоков возрастают, а последний блок замыкает кольцо на base.

Циклический список со сторожевым узлом (circular list with base sentinel) — список, замкнутый в кольцо, с фиктивным узлом base размера 0. Он убирает особые случаи пустого списка, головы и хвоста: кольцо всегда непусто, а поиск места вставки не требует отдельной проверки на пустоту.

First-fit — стратегия выбора блока: просматривать свободные блоки по порядку и взять первый, чей размер не меньше требуемого. Она не ищет лучший блок и не оптимизирует остаток; её достоинство — простота и ранний выход.

Отрезание хвоста (split) — если свободный блок больше запроса, он делится на две части: префикс остаётся свободным, а хвост ровно нужного размера выдаётся. В K&R отрезается именно хвост, чтобы заголовок свободного блока остался на прежнем месте и ссылки списка не пришлось менять.

Слияние (coalescing) — при освобождении блок объединяется с непосредственными соседями по адресу, если они тоже свободны. Слияние уменьшает внешнюю фрагментацию и предотвращает «распад» арены на мелкие куски.

Внешняя фрагментация (external fragmentation) — ситуация, когда суммарно свободной памяти достаточно, но она разбита занятыми блоками на несмежные участки, каждый из которых меньше запроса. Аллокатор K&R не перемещает блоки, поэтому справиться с ней не может.

Внутренняя фрагментация (internal fragmentation) — неиспользуемый остаток внутри выданного блока. Здесь он возникает из-за округления размера до целых единиц: не более [math]\displaystyle{ H-1 }[/math] байт на блок. Сам заголовок [math]\displaystyle{ H }[/math] байт — это отдельные служебные накладные расходы, а не внутренняя фрагментация; вместе округление и заголовок дают не более [math]\displaystyle{ 2H-1 }[/math] байт потерь на блок.

Выравнивание (alignment) — требование, чтобы адрес объекта был кратен его выравниванию. Полезная область начинается с адреса [math]\displaystyle{ p+1 }[/math], где [math]\displaystyle{ p }[/math] — выровненный заголовок, а [math]\displaystyle{ H }[/math] кратен alignof(Header); поэтому payload выровнен не хуже заголовка. Для переносимого кода, которому нужно выравнивание под любой фундаментальный тип, ориентируются на alignof(max_align_t) [7].

morecore — служебная операция, которая запрашивает у операционной системы новый участок памяти и вставляет его в список свободных блоков. В K&R она вызывает sbrk, в учебной реконструкции — берёт очередной кусок статической арены.

sbrk — системный вызов (точнее, обёртка над brk), изменяющий границу сегмента данных процесса. sbrk(delta) увеличивает границу на delta байт и возвращает прежнее значение границы; при ошибке возвращает (void *) -1. В POSIX не входит и считается устаревшим [6].

Двойное освобождение (double free) — повторный вызов Afree для уже освобождённого указателя. Список свободных блоков при этом может замкнуться сам на себя, а размеры — сложиться неверно; в C это неопределённое поведение, а в алгоритме K&R — ещё и потенциальное зацикливание.

Обозначения. [math]\displaystyle{ n }[/math] — размер запроса в байтах; [math]\displaystyle{ H = \text{sizeof(Header)} }[/math]; [math]\displaystyle{ u }[/math] (в коде nunits) — размер блока в единицах, включая заголовок; [math]\displaystyle{ k }[/math] — число свободных блоков; [math]\displaystyle{ m }[/math] — общее число блоков; NALLOC — минимум единиц, запрашиваемых у системы за один раз; ALLOCSIZE — размер буфера в примере §5.4. Все смещения и размеры в псевдокоде и трассировке — в единицах, нумерация единиц 0-based. Запись [h, s) означает блок с началом [math]\displaystyle{ h }[/math] и размером [math]\displaystyle{ s }[/math] (не конец); например, [7, 3) — единицы 7, 8, 9. Запись p + u означает адрес заголовка через [math]\displaystyle{ u }[/math] единиц после p.

Мотивация и интуиция

Программе нужны объекты переменного размера, время жизни которых заранее неизвестно: узлы списка, строки, буферы ввода-вывода, таблицы. Стек не подходит, потому что время жизни объекта не обязано совпадать с временем жизни функции. Фиксированный массив тоже не подходит: его размер нужно знать заранее, а «запас» тратится впустую.

Первый учебный ответ на эту задачу — bump-аллокатор (аллокатор с продвижением указателя) из §5.4 той же книги. Там память выдаётся сдвигом указателя:

#define ALLOCSIZE 10000

static char allocbuf[ALLOCSIZE];   /* буфер */
static char *allocp = allocbuf;    /* следующая свободная позиция */

char *alloc(int n)
{
    if (allocbuf + ALLOCSIZE - allocp >= n) {
        allocp += n;
        return allocp - n;
    }
    return 0;
}

void afree(char *p)
{
    if (p >= allocbuf && p < allocbuf + ALLOCSIZE)
        allocp = p;
}

Этот код выдаёт память за [math]\displaystyle{ O(1) }[/math] и почти не имеет накладных расходов, но освобождать умеет только «вершину»: afree просто откатывает указатель назад. Если освободить блок из середины, следующий alloc затрёт ещё живые данные; если освобождать в другом порядке, память не переиспользуется. Формально это стек, а не куча.

Пусть в программе 10 000 объектов по 48 байт, и в каждый момент живёт около 10% из них. Bump-аллокатору понадобится буфер на все [math]\displaystyle{ 10\,000 }[/math] объектов, то есть [math]\displaystyle{ 10\,000 \cdot 48 = 480\,000 }[/math] байт, и после его исчерпания он откажет, хотя одновременно занято лишь около 48 000 байт. Список свободных блоков переиспользует освобождённые участки и снижает пиковое потребление примерно до максимума одновременно живых данных плюс фрагментация.

Второй наивный вариант — вызывать malloc из стандартной библиотеки на каждый объект. Это работает, но каждый вызов может приводить к системному вызову и к работе с общей кучей; системный вызов на порядки дороже арифметики указателей, а метаданные библиотеки рассчитаны на общий случай. Учебный аллокатор амортизирует обращения к системе: morecore берёт сразу NALLOC единиц (в K&R — 1024 единицы, то есть 16 КиБ при [math]\displaystyle{ H=16 }[/math]), и следующие запросы обслуживаются уже из полученного участка.

Ключевая идея §8.7 в одном абзаце: хранить метаданные внутри самой памяти и связать свободные блоки в адресно упорядоченное кольцо. Тогда выдача — это поиск первого подходящего блока и, возможно, разрезание его на две части; освобождение — это вставка блока в кольцо и слияние с соседями по адресу. Никаких внешних таблиц, никакого копирования живых объектов, только указатели и арифметика.

Два примера из книги нужно различать явно. В §5.4 функции называются alloc и afree, память — статический буфер allocbuf, освобождение — LIFO. В §8.7 функции называются malloc и free, память берётся у системы через sbrk, а свободные блоки живут в кольцевом списке. В этой статье операции §8.7 называются Alloc и Afree, а в коде — kr_alloc и kr_free, чтобы не путать их со стандартными malloc/free и с примером §5.4.

Свойство	§5.4, alloc/afree	§8.7, аллокатор K&R
Память	статический allocbuf	участки, получаемые через sbrk
Порядок освобождения	строго LIFO	любой
Повторное использование	только последнего участка	любого подходящего блока
Метаданные	нет	заголовок Header у каждого блока
Поиск блока	[math]\displaystyle{ O(1) }[/math]	[math]\displaystyle{ O(k) }[/math]
Слияние соседей	нет	да
Двойное освобождение	тихо ломает указатель	ломает список и может зациклить поиск

Именно вторая схема и называется в этой статье аллокатором K&R.

Устройство

Заголовок — объединение (union), а не структура. Это нужно, чтобы заголовок имел выравнивание самого «строгого» из своих полей и одновременно занимал целое число единиц:

typedef union Header {
    struct {
        union Header *next;   /* следующий свободный блок в адресном порядке */
        size_t size;          /* размер блока в единицах, включая заголовок */
    } s;
    long double align;        /* выравнивание полезной области */
} Header;

В оригинале K&R заголовок выглядит иначе:

typedef long Align;

union header {
    struct {
        union header *ptr;
        unsigned size;
    } s;
    Align x;
};
typedef union header Header;

Отличия современной реконструкции: ptr переименован в next для читаемости, unsigned заменён на size_t для работы с большими адресными пространствами, а long — на long double, чтобы выравнивание заголовка покрывало выравнивание любого фундаментального типа на распространённых платформах. Логика алгоритма от этих замен не меняется.

Размер блока считается в единицах, и в него входит заголовок. Если запрос равен [math]\displaystyle{ n }[/math] байт, то

[math]\displaystyle{ u = \left\lfloor \frac{n + H - 1}{H} \right\rfloor + 1 . }[/math]

Слагаемое [math]\displaystyle{ +1 }[/math] — это заголовок, а округление вверх даёт полезную ёмкость [math]\displaystyle{ (u-1)H \ge n }[/math]. Внутренние потери при округлении равны [math]\displaystyle{ (u-1)H - n }[/math] и лежат в диапазоне [math]\displaystyle{ 0 \ldots H-1 }[/math]. Полные накладные расходы на блок — заголовок плюс округление, то есть не более [math]\displaystyle{ 2H-1 }[/math] байт сверх запроса. При [math]\displaystyle{ H=16 }[/math] и [math]\displaystyle{ n=1 }[/math] блок занимает 2 единицы: 16 байт заголовка и 16 байт полезной области, из которых использован 1 байт.

Указатель, который возвращается вызывающему, указывает не на заголовок, а на следующую единицу: если блок начинается в [math]\displaystyle{ p }[/math], полезная область начинается в [math]\displaystyle{ p+1 }[/math]. Заголовок при этом остаётся «позади» указателя, и по ap - 1 в Afree можно восстановить начало блока.

Почему payload выровнен? sizeof(Header) всегда кратен alignof(Header) — это свойство полного типа в C. Заголовок блока лежит по адресу, выровненному по границе единицы: арена — массив Header, а sbrk в классических Unix возвращает выровненную границу сегмента данных. Сдвиг на [math]\displaystyle{ H }[/math] байт сохраняет выравнивание, поэтому [math]\displaystyle{ p+1 }[/math] выровнен не хуже [math]\displaystyle{ p }[/math]. Объединение с long double поднимает alignof(Header) до выравнивания самого строгого поля: на Linux x86-64 это 16 байт, на MSVC x64 — 8; sizeof(Header) в обоих случаях равен 16 байтам (указатель 8 байт плюс size_t 8 байт).

Свободные блоки связаны в кольцо. Узел base — это статическая переменная типа Header с size = 0; он не является блоком арены, но всегда присутствует в кольце. Инициализация выполняется при первом Alloc:

base.s.next = freep = prevp = &base;
base.s.size = 0;

После этого кольцо состоит из одного base, а freep указывает на него же. Первый morecore вставит в кольцо настоящий блок, и оно примет вид base → блок → base. Сторожевой узел защищён от слияния с обеих сторон по-разному. Нижнее слияние (p + p->s.size == bp) не может поглотить base: его размер равен нулю, поэтому для p = base условие не выполняется. Верхнее слияние (bp + bp->s.size == p->s.next) размер base не использует: если base находится сразу за ареной, блок, заканчивающийся ровно на &base, поглотил бы сторожевой узел. В исходном K&R корректность здесь опирается на раскладку: base размещён ниже кучи и не примыкает к ней сверху. В реконструкции это запрещено явной проверкой p->s.next != &base в kr_free. Это важная деталь, а не случайность.

Указатель freep — не голова списка, а «плавающая» точка старта поиска. После каждой выдачи он указывает на узел, предшествующий обработанному свободному блоку. Благодаря этому последовательные выдачи не начинают поиск с одного и того же места: нагрузка распределяется по кольцу, а не концентрируется в начале. Гарантий по фрагментации это не даёт, но может снизить концентрацию выдач в начале кольца.

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

Раскладка блока и кольцо свободных блоков показаны на рис. 1 и рис. 2.

Рис. 1. Раскладка блока: заголовок Header и полезная область; единица — это sizeof(Header), поэтому payload всегда начинается с p + 1.

Рис. 2. Свободные блоки связаны в кольцо в порядке адресов; base — сторожевой узел размера 0, пунктирная стрелка — переход через кольцо.

Операции и алгоритмы

Операция: Alloc

Идея. Найти в кольце первый свободный блок размера не меньше [math]\displaystyle{ u }[/math]; если он ровно нужного размера — изъять его из кольца, иначе отрезать от него хвост нужного размера и вернуть хвост. Если подходящего блока нет, получить новый участок через Morecore и повторить поиск.

Шаги.

1. Отвергнуть [math]\displaystyle{ n = 0 }[/math] и запросы, при которых [math]\displaystyle{ n + H - 1 }[/math] переполняет size_t.
2. Вычислить [math]\displaystyle{ u = \lfloor (n+H-1)/H \rfloor + 1 }[/math].
3. При первом вызове инициализировать кольцо из одного base.
4. Начать просмотр с freep.s.next, запоминая предыдущий блок prevp.
5. Если p.s.size >= u, обработать блок: при равенстве изъять, при строгом неравенстве отрезать хвост.
6. Записать freep = prevp и вернуть p + 1.
7. Если просмотр вернулся к freep, вызвать Morecore; при отказе вернуть NIL.
8. После успешного Morecore повторить проверку: новый блок заведомо достаточен.

Инвариант. Перед каждой итерацией prevp — предшественник p в кольце, а все блоки от freep.s.next до prevp уже проверены и не подошли. Кольцо остаётся упорядоченным по адресам; Alloc не может выбрать base, потому что его размер 0 меньше любого [math]\displaystyle{ u \ge 2 }[/math].

Операция Alloc(n)
Вход:  n — размер запроса в байтах, n ≥ 1; H — размер Header в байтах;
       единицы и смещения 0-based, адреса блоков кратны H
Выход: указатель на полезную область блока ёмкостью ≥ n байт либо NIL
Инвариант: free list — непустое кольцо блоков, упорядоченное по адресам;
           base — сторожевой узел размера 0; свободные блоки не пересекаются

1  if n > SIZE_MAX − (H − 1)
2      return NIL                        # иначе переполнится n + H − 1
3  u ← ⌊(n + H − 1) / H⌋ + 1            # +1 — заголовок
4  if freep = NIL
5      base.s.next ← base
6      base.s.size ← 0
7      freep ← base
8  prevp ← freep
9  p ← prevp.s.next
10 while true
11     if p.s.size ≥ u
12         if p.s.size = u
13             prevp.s.next ← p.s.next          # точное совпадение: изъять
14         else
15             p.s.size ← p.s.size − u          # префикс остаётся свободным
16             p ← p + p.s.size                 # p — начало хвоста
17             p.s.size ← u
18         freep ← prevp
19         return p + 1
20     if p = freep                             # сделан полный круг
21         p ← Morecore(u)
22         if p = NIL
23             return NIL
24     prevp ← p
25     p ← p.s.next

Сложность: O(k) просмотренных свободных блоков, k ≤ m; худшее O(m).
Корректность: см. раздел «Корректность»; split сохраняет адресный порядок.

Разбор. Пусть кольцо содержит единственный свободный блок [0, 10), а запрос требует [math]\displaystyle{ u = 3 }[/math] единицы. Блок больше запроса, поэтому выполняется ветка split:

• p.s.size становится [math]\displaystyle{ 10 - 3 = 7 }[/math];
• p сдвигается на 7 единиц и указывает на хвост [7, 3);
• p.s.size хвоста становится 3;
• возвращается p + 1, то есть единица 8; полезная область хвоста — единицы 8 и 9.

Свободный блок [0, 7) остался на прежнем адресе, ссылка prevp.s.next по-прежнему указывает на него, и список менять не нужно. Именно поэтому K&R отрезает хвост, а не голову: при отрезании головы пришлось бы переписывать ссылку предшественника. Процесс показан на рис. 3.

Рис. 3. First-fit с отрезанием хвоста: из свободного блока [0, 10) выделен блок [7, 3); префикс [0, 7) остаётся в списке на прежнем месте.

Сложность. В худшем случае просматриваются все [math]\displaystyle{ k }[/math] свободных блоков, то есть [math]\displaystyle{ O(k) }[/math], где [math]\displaystyle{ k \le m }[/math]. Если подходящего блока нет, добавляется один вызов Morecore, который сам стоит [math]\displaystyle{ O(k) }[/math] плюс стоимость получения памяти. Среднее время зависит от нагрузки и не оценивается лучше худшего; амортизированной границы, улучшающей [math]\displaystyle{ O(k) }[/math], у операции нет. Один Alloc вызывает Morecore не более одного раза: новый блок имеет размер не меньше [math]\displaystyle{ u }[/math], поэтому повторный проход находит его (в худшем случае — после полного круга, если новый блок слился с левым соседом, то есть с предшественником), и второго вызова не происходит.

Крайние случаи.

• [math]\displaystyle{ n = 0 }[/math]: K&R не оговаривает это отдельно и предполагает [math]\displaystyle{ n \gt 0 }[/math]; в реконструкции возвращается NIL.
• [math]\displaystyle{ n }[/math] близко к SIZE_MAX: без проверки переполнения выражение [math]\displaystyle{ n + H - 1 }[/math] обернётся, и будет выделен блок неверного размера.
• Точное совпадение: блок изымается целиком, префикса не остаётся.
• Арена исчерпана: Morecore возвращает NIL, Alloc возвращает NIL.
• [math]\displaystyle{ u = 2 }[/math]: минимальный блок — заголовок плюс одна единица полезной области.

Операция: Afree

Идея. Восстановить заголовок по указателю, найти в кольце место, где блок должен стоять по адресу, вставить его и слить с непосредственными соседями, если они свободны.

Шаги.

1. Получить заголовок bp = ap - 1.
2. Найти предшественника p, между p и p.s.next в циклическом адресном порядке лежит bp.
3. Если блок справа (p.s.next) примыкает к bp, слить: увеличить размер bp и переставить его ссылку через правый сосед.
4. Если блок слева (p) примыкает к bp, слить: увеличить размер p и направить его ссылку через bp.
5. Записать freep = p.

Инвариант. Кольцо остаётся упорядоченным по адресам; bp встречается в нём ровно один раз; размеры слитых блоков равны сумме размеров; base не поглощается нижним слиянием, потому что его размер 0, а верхнее слияние с base запрещено проверкой p->s.next != &base.

Операция Afree(ap)
Вход:  ap — указатель на полезную область блока, ранее выданный Alloc
       и ещё не освобождённый; адреса и размеры — в единицах
Выход: блок возвращён в free list; соседние свободные блоки объединены
Инвариант: free list упорядочен по адресам циклически; блоки не пересекаются

1  bp ← ap − 1                        # заголовок освобождаемого блока
2  p ← freep
3  while not (bp > p and bp < p.s.next)
4      if p ≥ p.s.next and (bp > p or bp < p.s.next)
5          break                     # bp у края кольца, переход last → first
6      p ← p.s.next
7  if p.s.next ≠ base and bp + bp.s.size = p.s.next
8      bp.s.size ← bp.s.size + p.s.next.s.size
9      bp.s.next ← p.s.next.s.next
10 else
11     bp.s.next ← p.s.next
12 if p + p.s.size = bp
13     p.s.size ← p.s.size + bp.s.size
14     p.s.next ← bp.s.next
15 else
16     p.s.next ← bp
17 freep ← p

Сложность: O(k) на поиск места вставки; O(1) дополнительной памяти.
Корректность: см. раздел «Корректность»; слияние сохраняет дизъюнктность.

Разбор. Пусть после трёх выдач свободны блоки [0, 2) и [4, 4), а освобождается блок [2, 2) — третья выдача. Поиск находит p = [0, 2), потому что bp = 2 лежит между p = 0 и p.s.next = 4. Верхнее слияние: [math]\displaystyle{ 2 + 2 = 4 }[/math], то есть bp примыкает к [4, 4); размер bp становится [math]\displaystyle{ 2 + 4 = 6 }[/math], ссылка bp.s.next — через правый сосед. Нижнее слияние: [math]\displaystyle{ 0 + 2 = 2 }[/math], то есть [0, 2) примыкает к bp; размер p становится [math]\displaystyle{ 2 + 6 = 8 }[/math], а p.s.next — через bp. В кольце остаётся один блок [0, 8). Этот случай показан на рис. 4.

Рис. 4. Afree: блок bp вставляется между соседями и сливается с теми, что примыкают к нему по адресу.

Как работает поиск. Внешнее условие продолжает цикл, пока bp не лежит строго между p и p.s.next. Если p и p.s.next — не соседние по адресу, а «замыкающая» пара кольца, то обычное условие невозможно: p.s.next меньше p. Именно для этого случая служит внутренняя проверка p >= p.s.next: она распознаёт переход через кольцо и прерывает поиск, если bp находится выше p или ниже p.s.next, то есть у края арены.

Запись p >= p.s.next, а не p > p.s.next, существенна. В кольце из одного base (base.s.next = base) равенство p = p.s.next — единственный признак того, что список просмотрен; с > внутреннее условие не сработало бы никогда, и Afree зациклился бы на первом же освобождении. В наших обозначениях это выглядит безобидно, но в коде это одна из самых частых опечаток.

Сложность. Поиск места вставки просматривает до [math]\displaystyle{ k }[/math] блоков; слияния выполняются за [math]\displaystyle{ O(1) }[/math]. Дополнительная память не нужна. Среднее и амортизированное время совпадают по порядку с худшим: каждая операция выполняет собственный поиск, и амортизировать его нечем.

Крайние случаи.

• Освобождаемый блок выше всех свободных: он вставляется в «шов» кольца, сразу после последнего блока.
• Освобождаемый блок ниже всех свободных: он вставляется сразу после base.
• Список пуст (в кольце только base): внутреннее условие срабатывает сразу, блок вставляется после base.
• ap = NULL: в реконструкции это no-op; в K&R такой проверки нет.
• Двойное освобождение: блок уже в кольце, bp совпадает с одним из узлов. Условия поиска могут не сработать, а размеры — сложиться дважды; поведение не определено. В кольце из одного блока это приводит к бесконечному циклу.

Операция: Morecore

Идея. Когда свободных блоков нужного размера нет, попросить у системы новый участок, оформить его как свободный блок и вставить в кольцо; затем вернуть указатель, с которого Alloc продолжит поиск.

Шаги.

1. Поднять запрос до NALLOC единиц, если он меньше.
2. Проверить, что nu * sizeof(Header) не переполняет размер.
3. Вызвать sbrk(nu * sizeof(Header)).
4. При результате (char *) -1 вернуть NIL.
5. Оформить полученный участок как заголовок с size = nu.
6. Вызвать Afree(up + 1), чтобы вставить блок и слить его с соседом, если участки смежны.
7. Вернуть freep: если слияния с левым соседом не было, это предшественник нового блока, иначе — сам слитый блок.

Операция Morecore(nu)
Вход:  nu — минимально нужное число единиц, nu ≥ 1; NALLOC — порог
Выход: freep — состояние поиска после вставки: предшественник нового блока
       (если левого слияния не было) либо сам слитый блок; NIL при отказе
Инвариант: новый участок не пересекается с существующими блоками

1  if nu < NALLOC
2      nu ← NALLOC
3  if nu > SIZE_MAX / H
4      return NIL                       # защита от переполнения; в K&R её нет
5  cp ← sbrk(nu · H)
6  if cp = (char *) −1
7      return NIL
8  up ← cp
9  up.s.size ← nu
10 Afree(up + 1)
11 return freep

Сложность: O(k) на Afree плюс стоимость системного вызова sbrk;
           оформление блока — O(1). Модель O(nu + k) — если sbrk стоит O(nu).
Корректность: sbrk отдаёт новый участок; Afree вставляет его по адресу.

Разбор. При [math]\displaystyle{ H = 16 }[/math] и NALLOC = 1024 (значение из K&R; в нашей реконструкции NALLOC = 64) вызов sbrk(1024 * 16) запрашивает 16 КиБ. Если Alloc просил [math]\displaystyle{ u = 5 }[/math] единиц, Morecore всё равно возьмёт 1024 единицы: лишние 1019 единиц останутся в свободном блоке и будут использованы следующими запросами. Так системный вызов амортизируется на много выдач.

Почему Afree(up + 1), а не ручная вставка? Потому что новый участок может примыкать к уже свободному блоку (например, предыдущий вызов sbrk вернул соседний участок, и тот успели освободить). Afree выполняет поиск места и слияние по общим правилам; отдельный код вставки дублировал бы эту логику и легко разошёлся бы с ней.

Почему возвращается freep, а не up? Потому что Afree не возвращает новый блок, а оставляет состояние поиска в глобальной переменной freep, и именно с него Alloc продолжает цикл. Если слияния с левым соседом не было, freep указывает на предшественника нового блока: Alloc делает prevp = p; p = p.s.next и сразу попадает на новый (или слитый с правым) блок. Если же новый блок слился с левым соседом, freep указывает на сам слитый блок F′: Alloc начинает с F′.s.next и доходит до F′ только после полного круга по кольцу. В обоих случаях возвращается не начало нового блока, а узел кольца, с которого надо продолжить поиск; поэтому up здесь не годится — после слияния начало блока может не совпадать с up.

Сложность. Afree просматривает до [math]\displaystyle{ k }[/math] блоков, sbrk стоит столько, сколько стоит системный вызов и выделение страниц. При [math]\displaystyle{ nu \ge NALLOC }[/math] накладные расходы на единицу памяти составляют [math]\displaystyle{ O(1 + k/nu) }[/math].

Крайние случаи.

• sbrk вернул (char *) -1: памяти нет, Alloc вернёт NIL.
• nu * sizeof(Header) переполняется: без проверки sbrk получил бы отрицательное или малое значение. В K&R этой проверки нет.
• sbrk возвращает невыровненный указатель: тогда заголовок и payload окажутся невыровненными. На классических Unix граница сегмента данных выровнена, но полагаться на это без проверки не стоит.
• Участки, полученные разными вызовами, не обязаны быть смежными; слияние тогда не происходит, и в кольце появляются отдельные блоки.
• В нашей реконструкции вместо sbrk работает статическая арена; её исчерпание — это аналог отказа sbrk.

Процесс показан на рис. 5.

Рис. 5. Morecore: sbrk отдаёт новый участок, Afree вставляет его и сливает с примыкающим свободным блоком, после чего Alloc повторяет поиск.

Реализация на C

Ниже — современная реконструкция, а не дословный текст K&R. Переименованы malloc/free в kr_alloc/kr_free (иначе конфликт со стандартной библиотекой), unsigned заменён на size_t, long Align — на long double, добавлены проверки [math]\displaystyle{ n = 0 }[/math] и переполнения. Логика first-fit, отрезания хвоста, слияния, сторожевого узла base и цикла поиска в Afree сохранена.

Чтобы тест был воспроизводим на Windows, где нет sbrk, память берётся из статического массива arena. Это не настоящий sbrk: арена фиксирована, растёт только указатель arena_used, а «системный вызов» заменён проверкой границы массива. Вариант с sbrk для Unix показан отдельно после основного кода.

Блок A — ядро аллокатора:

/* kr_alloc_demo.c — современная реконструкция аллокатора K&R (гл. 8, §8.7).
 * Вместо sbrk используется статическая арена: так тест воспроизводим и на Windows. */
#include <assert.h>
#include <stddef.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>

#define NALLOC     64      /* минимум единиц за один запрос к системе */
#define HEAP_UNITS 4096    /* размер арены в единицах */

typedef union Header {
    struct {
        union Header *next;   /* следующий свободный блок в адресном порядке */
        size_t size;          /* размер блока в единицах, включая заголовок */
    } s;
    long double align;        /* выравнивание полезной области */
} Header;

static Header arena[HEAP_UNITS];   /* замена памяти, получаемой через sbrk */
static size_t arena_used;          /* сколько единиц арены уже отдано */
static Header base;                /* нулевой сторожевой узел списка */
static Header *freep;              /* начало очередного поиска */

static void kr_free(void *ap);

static Header *kr_morecore(size_t nu)
{
    Header *up;

    if (nu < NALLOC)
        nu = NALLOC;
    if (nu > HEAP_UNITS - arena_used)
        return NULL;                       /* арена исчерпана */
    up = arena + arena_used;
    arena_used += nu;
    up->s.size = nu;
    kr_free((void *)(up + 1));             /* вставить; возможно слияние */
    return freep;
}

void *kr_alloc(size_t n)
{
    Header *p, *prevp;
    size_t nunits;

    if (n == 0)
        return NULL;                       /* K&R предполагает n > 0 */
    if (n > SIZE_MAX - (sizeof(Header) - 1))
        return NULL;                       /* иначе переполнится n + H − 1 */

    nunits = (n + sizeof(Header) - 1) / sizeof(Header) + 1;

    if ((prevp = freep) == NULL) {         /* первый вызов: список пуст */
        base.s.next = freep = prevp = &base;
        base.s.size = 0;
    }
    for (p = prevp->s.next; ; prevp = p, p = p->s.next) {
        if (p->s.size >= nunits) {
            if (p->s.size == nunits)
                prevp->s.next = p->s.next;         /* точное совпадение */
            else {                                 /* отрезать хвост */
                p->s.size -= nunits;
                p += p->s.size;
                p->s.size = nunits;
            }
            freep = prevp;
            return (void *)(p + 1);                /* payload за заголовком */
        }
        if (p == freep)                            /* сделали полный круг */
            if ((p = kr_morecore(nunits)) == NULL)
                return NULL;
    }
}

void kr_free(void *ap)
{
    Header *bp, *p;

    if (ap == NULL)
        return;                            /* free(NULL) — no-op */
    bp = (Header *)ap - 1;                 /* заголовок блока */
    assert(bp->s.size >= 1);
    for (p = freep; !(bp > p && bp < p->s.next); p = p->s.next)
        if (p >= p->s.next && (bp > p || bp < p->s.next))
            break;                         /* bp у края кольца */
    if (p->s.next != &base &&              /* base не поглощаем верхним слиянием */
        bp + bp->s.size == p->s.next) {    /* слияние с правым соседом */
        bp->s.size += p->s.next->s.size;
        bp->s.next = p->s.next->s.next;
    } else
        bp->s.next = p->s.next;
    if (p + p->s.size == bp) {             /* слияние с левым соседом */
        p->s.size += bp->s.size;
        p->s.next = bp->s.next;
    } else
        p->s.next = bp;
    freep = p;
}

Блок B — тестовая обвязка. Она добавляется в тот же файл; между блоками A и B ничего не вставляется.

/* ---------------- тестовая обвязка: карта владения ---------------- */

#define SLOTS 512
#define OPS   20000

static unsigned char owner[HEAP_UNITS];   /* 0 — свободна, 1 — занята живым блоком */
static size_t live_units;

static size_t hindex(const Header *h)
{
    assert(h >= arena && h < arena + HEAP_UNITS);
    return (size_t)(h - arena);
}

static size_t free_block_count(void)
{
    size_t blocks = 0;
    Header *p = &base;

    while (p->s.next != &base) {
        p = p->s.next;
        blocks++;
    }
    return blocks;
}

static int base_in_ring(void)
{
    Header *p = &base;
    size_t steps = 0;

    while (p->s.next != &base) {
        p = p->s.next;
        if (p < arena || p >= arena + HEAP_UNITS)
            return 0;                       /* узел вне арены */
        if (++steps > HEAP_UNITS)
            return 0;                       /* кольцо не вернулось к base */
    }
    return 1;
}

static int check_all(void)
{
    size_t free_units = 0;
    Header *prev = NULL;
    Header *q = base.s.next;

    while (q != &base) {
        size_t qi, k;

        if (q < arena || q >= arena + HEAP_UNITS)
            return 0;                       /* блок вне арены */
        if (q->s.size == 0)
            return 0;
        qi = hindex(q);
        if (qi + q->s.size > HEAP_UNITS)
            return 0;
        if (prev != NULL && !(prev < q))
            return 0;                       /* нарушен адресный порядок */
        for (k = 0; k < q->s.size; k++)
            if (owner[qi + k])
                return 0;                   /* свободный блок наложился на живой */
        free_units += q->s.size;
        prev = q;
        q = q->s.next;
    }
    return free_units == arena_used - live_units;
}

static void *t_alloc(size_t n)
{
    void *ap = kr_alloc(n);
    Header *h;
    size_t idx, sz, k;

    if (ap == NULL)
        return NULL;
    assert((uintptr_t)ap % _Alignof(max_align_t) == 0);
    h = (Header *)ap - 1;
    idx = hindex(h);
    sz = h->s.size;
    assert(sz >= 2);                        /* заголовок и хотя бы одна единица */
    for (k = 0; k < sz; k++) {
        assert(owner[idx + k] == 0);
        owner[idx + k] = 1;
    }
    live_units += sz;
    return ap;
}

static void t_free(void *ap)
{
    Header *h = (Header *)ap - 1;
    size_t idx = hindex(h), sz = h->s.size, k;

    for (k = 0; k < sz; k++) {
        assert(owner[idx + k] == 1);
        owner[idx + k] = 0;
    }
    live_units -= sz;
    kr_free(ap);
}

int main(void)
{
    static void *ptr[SLOTS];
    static size_t len[SLOTS];
    size_t total = 0, k;
    int i;

    assert(kr_alloc(0) == NULL);
    assert(kr_alloc(SIZE_MAX) == NULL);

    srand(12345);
    for (i = 0; i < OPS; i++) {
        int s = rand() % SLOTS;

        if (ptr[s] != NULL) {
            unsigned char *c = ptr[s];
            size_t n = len[s];

            for (k = 0; k < n; k++)
                assert(c[k] == (unsigned char)(0xA5u ^ (unsigned)(s * 31 + (int)k)));
            t_free(c);
            ptr[s] = NULL;
            len[s] = 0;
        } else {
            size_t n = 1u + (size_t)(rand() % 200);
            unsigned char *c = t_alloc(n);

            if (c != NULL) {
                for (k = 0; k < n; k++)
                    c[k] = (unsigned char)(0xA5u ^ (unsigned)(s * 31 + (int)k));
                ptr[s] = c;
                len[s] = n;
            }
        }
        total++;
        if (i % 1000 == 0)
            assert(check_all());
    }

    for (i = 0; i < SLOTS; i++)
        if (ptr[i] != NULL) {
            t_free(ptr[i]);
            ptr[i] = NULL;
            len[i] = 0;
        }
    assert(check_all());
    assert(free_block_count() == 1);
    assert(base_in_ring());
    assert(base.s.size == 0);

    /* если арена ещё не исчерпана, добиваем её мелкими блоками */
    if (arena_used < HEAP_UNITS) {
        void *many[HEAP_UNITS];
        size_t cnt = 0;

        while (cnt < HEAP_UNITS) {
            void *c = t_alloc(1);
            if (c == NULL)
                break;
            many[cnt++] = c;
        }
        assert(cnt > 0);
        assert(base_in_ring());             /* base не поглощён верхним слиянием */
        assert(base.s.size == 0);
        for (k = 0; k < cnt; k++)
            t_free(many[k]);
        assert(check_all());
        assert(free_block_count() == 1);
    assert(base_in_ring());
    assert(base.s.size == 0);
    }

    printf("ok: %zu ops, arena %zu/%d units, free blocks %zu\n",
           total, arena_used, HEAP_UNITS, free_block_count());
    return 0;
}

Что проверяет тест.

• 20 000 случайных операций над 512 слотами; размер запроса — от 1 до 200 байт.
• Каждый выданный блок заполняется байтовым шаблоном, зависящим от номера слота; перед освобождением шаблон сверяется. Это ловит перекрытия блоков и порчу полезной области.
• Карта owner отмечает каждую единицу арены как занятую или свободную. Проверка check_all требует, чтобы свободные блоки лежали внутри арены, не пересекались с занятыми единицами, шли строго по возрастанию адресов, а сумма их размеров равнялась arena_used - live_units.
• После освобождения всех блоков в кольце должен остаться ровно один блок: все соседние свободные участки обязаны слиться.
• Затем арена добивается мелкими блоками и освобождается целиком; снова проверяется, что остался один блок. Это проверяет слияние при массовом освобождении. Дополнительно проверяется, что после заполнения арены base всё ещё входит в кольцо и его размер остался нулевым.
• Проверяются [math]\displaystyle{ n = 0 }[/math], [math]\displaystyle{ n = \text{SIZE_MAX} }[/math] (переполнение) и выравнивание каждого указателя по _Alignof(max_align_t).

Сборка и запуск. На машине с clang:

clang -std=c11 -O2 -Wall -Wextra kr_alloc_demo.c -o kr_alloc_demo
./kr_alloc_demo

На Windows исполняемый файл называется kr_alloc_demo.exe. Компилятор не выдал предупреждений, программа напечатала:

ok: 20000 ops, arena 4096/4096 units, free blocks 1

Это означает, что 20 000 операций прошли без нарушений инварианта, арена из 4096 единиц исчерпана, а после освобождения всего в кольце остался один блок. Ассерты включены: сборка шла без -DNDEBUG.

Вариант с sbrk для Unix. В K&R morecore вызывает sbrk. Фрагмент ниже заменяет kr_morecore из блока A; он не компилируется на Windows и на этой машине не проверялся.

#include <unistd.h>

static Header *kr_morecore_unix(size_t nu)
{
    char *cp;
    Header *up;

    if (nu < NALLOC)
        nu = NALLOC;
    if (nu > SIZE_MAX / sizeof(Header))
        return NULL;                       /* nu * sizeof(Header) переполнилось */
    cp = sbrk((intptr_t)(nu * sizeof(Header)));
    if (cp == (char *)-1)                  /* система не дала памяти */
        return NULL;
    up = (Header *)cp;
    up->s.size = nu;
    kr_free((void *)(up + 1));
    return freep;
}

Историческая деталь: в K&R sbrk объявлен как char *sbrk(int), а выражение nu * sizeof(Header) имеет тип unsigned; современный прототип использует intptr_t. Проверка nu * sizeof(Header) добавлена потому, что в исходном коде её нет.

Сводная таблица сложности

Операция	Худшее время	Среднее	Амортизированное	Память	Комментарий
Alloc	[math]\displaystyle{ O(k) }[/math]	[math]\displaystyle{ O(k) }[/math]	не лучше [math]\displaystyle{ O(k) }[/math]	[math]\displaystyle{ O(1) }[/math]	[math]\displaystyle{ k }[/math] — число свободных блоков, [math]\displaystyle{ k \le m }[/math]
Afree	[math]\displaystyle{ O(k) }[/math]	[math]\displaystyle{ O(k) }[/math]	[math]\displaystyle{ O(k) }[/math]	[math]\displaystyle{ O(1) }[/math]	поиск предшественника в кольце
Morecore	[math]\displaystyle{ O(k) }[/math] + стоимость sbrk	[math]\displaystyle{ O(k) }[/math] + стоимость sbrk	[math]\displaystyle{ O(1 + k/nu) }[/math] на единицу	[math]\displaystyle{ O(1) }[/math]	Afree даёт [math]\displaystyle{ O(k) }[/math]; модель [math]\displaystyle{ O(nu + k) }[/math] — если sbrk стоит [math]\displaystyle{ O(nu) }[/math]
Alloc при исчерпании	[math]\displaystyle{ O(k) }[/math] + стоимость Morecore	то же	—	[math]\displaystyle{ O(1) }[/math]	один вызов Morecore на Alloc; его стоимость — [math]\displaystyle{ O(k) }[/math] + sbrk

Несколько оговорок. Во-первых, «среднее» здесь не означает вероятностную оценку: распределение запросов не задано, и first-fit не даёт гарантий. Во-вторых, амортизация Morecore относится только к стоимости получения памяти: сам поиск свободного блока выполняется на каждой операции и не амортизируется. В-третьих, [math]\displaystyle{ k }[/math] может быть порядка [math]\displaystyle{ m }[/math], а [math]\displaystyle{ m }[/math] растёт с числом блоков, поэтому в худшем случае одна операция стоит линейно по числу блоков.

Примечание. Аллокатор K&R не рандомизирован и не балансирует дерево поиска: это простой линейный просмотр кольца. Его преимущество — компактность и предсказуемость кода, а не асимптотика.

Трассировка примера

Рассмотрим условную арену из 10 единиц. Смещения и размеры — в единицах; блок [h, s) занимает единицы [math]\displaystyle{ h \ldots h+s-1 }[/math], заголовок — единица [math]\displaystyle{ h }[/math], полезная область — единицы [math]\displaystyle{ h+1 \ldots h+s-1 }[/math]. Для трассировки отвлечёмся от NALLOC: считаем, что Morecore(10) отдал ровно 10 единиц одним блоком, а base находится ниже арены и участвует в кольце как сторожевой узел.

Шаг	Операция	Действие	Блоки	Свободный список
0	инициализация	Morecore(10)	свободен [0, 10)	base → [0, 10)
1	Alloc, [math]\displaystyle{ u=2 }[/math]	отрезан хвост [8, 2)	свободен [0, 8); занят [8, 2)	base → [0, 8)
2	Alloc, [math]\displaystyle{ u=4 }[/math]	отрезан хвост [4, 4)	свободен [0, 4); заняты [4, 4), [8, 2)	base → [0, 4)
3	Alloc, [math]\displaystyle{ u=2 }[/math]	отрезан хвост [2, 2)	свободен [0, 2); заняты [2, 2), [4, 4), [8, 2)	base → [0, 2)
4	Afree блока шага 2	bp = 4; вставка после [0, 2), слияний нет	свободны [0, 2), [4, 4)	base → [0, 2) → [4, 4)
5	Afree блока шага 3	bp = 2; слияние с [4, 4), затем с [0, 2)	свободен [0, 8)	base → [0, 8)
6	Afree блока шага 1	bp = 8; слияние с [0, 8)	свободен [0, 10)	base → [0, 10)

Разберём ключевые шаги.

Шаг 1. Кольцо содержит [0, 10), запрос [math]\displaystyle{ u = 2 }[/math]. Блок больше, поэтому p.s.size становится 8, p сдвигается на 8, хвост получает размер 2 и возвращается как p + 1, то есть единица 9. Свободный префикс — единицы 0–7.

Шаг 2. Свободный блок [0, 8) больше [math]\displaystyle{ u = 4 }[/math]; префикс становится [0, 4), хвост [4, 4) выдаётся; полезная область — единицы 5–7.

Шаг 3. Аналогично [0, 4) делится на [0, 2) и [2, 2); полезная область выданного блока — единица 3.

Шаг 4. Освобождается блок [4, 4). Поиск начинается с freep; после шага 3 freep указывает на base, поэтому первым проверяется [0, 2). Внешнее условие требует одновременно [math]\displaystyle{ 4 \gt 0 }[/math] и [math]\displaystyle{ 4 \lt \text{base} }[/math], но второе ложно: base лежит ниже арены, и [0, 2) — последний блок кольца. Внутренняя проверка p >= p.s.next распознаёт замыкающую пару и прерывает поиск, потому что bp = 4 выше p. Блок вставляется после [0, 2). Слияний нет: [math]\displaystyle{ 0 + 2 = 2 \ne 4 }[/math] и [math]\displaystyle{ 4 + 4 = 8 }[/math], а следующий узел — base, а не блок с адресом 8.

Шаг 5. Освобождается блок [2, 2). Поиск находит p = [0, 2): [math]\displaystyle{ 2 \gt 0 }[/math] и [math]\displaystyle{ 2 \lt 4 }[/math]. Верхнее слияние: [math]\displaystyle{ 2 + 2 = 4 }[/math], правый сосед — [4, 4), поэтому размер bp становится [math]\displaystyle{ 2 + 4 = 6 }[/math], а ссылка ведёт через правый сосед на base. Нижнее слияние: [math]\displaystyle{ 0 + 2 = 2 }[/math], поэтому размер p становится [math]\displaystyle{ 2 + 6 = 8 }[/math], а p.s.next — base. В кольце один блок [0, 8).

Шаг 6. Освобождается блок [8, 2). Поиск находит p = [0, 8): [math]\displaystyle{ 8 \gt 0 }[/math], а следующий узел — base, поэтому блок ставится в шов. Верхнего слияния нет: [math]\displaystyle{ 8 + 2 = 10 }[/math], но следующего блока с адресом 10 не существует. Нижнее слияние: [math]\displaystyle{ 0 + 8 = 8 }[/math], поэтому p.s.size становится [math]\displaystyle{ 8 + 2 = 10 }[/math], а p.s.next — base. В кольце снова один блок [0, 10), то есть вся арена.

Трассировка подтверждает два свойства: слияние восстанавливает исходный блок после освобождения всех трёх выдач, а поиск в Afree корректно обрабатывает и обычный случай (шаг 5), и шов кольца (шаги 4 и 6). Схема слияния — на рис. 4.

Корректность и оценка сложности

Сформулируем инвариант, который поддерживают все операции. Доказательство опирается на плоскую модель памяти: адреса образуют линейный порядок, и блоки можно сравнивать реляционными операторами. В терминах стандарта C это допущение, а не гарантия; практические реализации на плоской адресации ему удовлетворяют.

Инвариант I. Пусть в арене используется arena_used единиц, а кольцо содержит [math]\displaystyle{ k }[/math] свободных блоков и имеет вид [math]\displaystyle{ b_0 = \text{base}, b_1, \ldots, b_k }[/math], где [math]\displaystyle{ b_i.s.next = b_{i+1} }[/math] и [math]\displaystyle{ b_k.s.next = \text{base} }[/math] (при [math]\displaystyle{ k=0 }[/math] это base.s.next = base). Тогда:

1. [math]\displaystyle{ b_0.s.size = 0 }[/math], а для [math]\displaystyle{ i \ge 1 }[/math] выполнено [math]\displaystyle{ b_i.s.size \ge 1 }[/math].
2. При [math]\displaystyle{ k \ge 1 }[/math] адреса [math]\displaystyle{ b_1, \ldots, b_k }[/math] строго возрастают; адрес base либо меньше адреса [math]\displaystyle{ b_1 }[/math], либо больше адреса [math]\displaystyle{ b_k }[/math], поэтому кольцо совпадает с порядком адресов.
3. Блоки [math]\displaystyle{ b_1, \ldots, b_k }[/math] попарно не пересекаются и лежат внутри арены, не выходя за arena_used.
4. Каждая единица арены либо принадлежит ровно одному свободному блоку, либо ровно одному занятому блоку; единицы за пределами arena_used не принадлежат никому.
5. freep указывает на один из узлов кольца.

Лемма 1 (Alloc сохраняет I). Если Alloc возвращает блок, инвариант сохраняется.

Доказательство. Рассмотрим два случая.

Точное совпадение: [math]\displaystyle{ p.s.size = u }[/math]. Тогда p — не base, так как [math]\displaystyle{ u \ge 2 \gt 0 = \text{base}.s.size }[/math]. Ссылка prevp.s.next направляется через p, и p исчезает из кольца. Остальные блоки не меняются, их адресный порядок сохраняется, дизъюнктность сохраняется, а выданный блок [math]\displaystyle{ [p, p+u) }[/math] был свободен и становится занятым. freep = prevp — узел кольца.

Отрезание хвоста: [math]\displaystyle{ p.s.size = s \gt u }[/math]. Новый размер префикса [math]\displaystyle{ s - u \ge 1 }[/math], поэтому пункт 1 выполняется. Хвост начинается в [math]\displaystyle{ p + (s-u) }[/math] и имеет размер [math]\displaystyle{ u \ge 2 }[/math]; префикс и хвост не пересекаются и вместе дают исходный блок [math]\displaystyle{ [p, p+s) }[/math]. Ссылка prevp.s.next по-прежнему указывает на префикс, так что кольцо не меняется; хвост в кольцо не входит. Адресный порядок и дизъюнктность сохраняются, выданный хвост был свободен и стал занятым. freep = prevp. [math]\displaystyle{ \blacksquare }[/math]

Лемма 2 (Afree находит правильное место). Если bp — корректный заголовок освобождаемого блока, не входящего в кольцо, то цикл поиска завершается и p оказывается предшественником bp в циклическом адресном порядке.

Доказательство. На каждой итерации p заменяется на p.s.next, то есть поиск продвигается по кольцу. Кольцо конечно; за не более чем [math]\displaystyle{ k+1 }[/math] шагов p достигает «замыкающей» пары, для которой [math]\displaystyle{ p \ge p.s.next }[/math]. Если bp лежит строго между какими-то соседними блоками, внешнее условие сработает раньше и цикл остановится. Если bp не лежит ни в одном таком промежутке, он находится в «шве» — выше последнего блока или ниже первого. В этом случае на замыкающей паре внутреннее условие p >= p.s.next and (bp > p or bp < p.s.next) истинно, и цикл прерывается. В обоих случаях p — предшественник bp. [math]\displaystyle{ \blacksquare }[/math]

Лемма 3 (Afree сохраняет I). После вставки и слияний инвариант сохраняется.

Доказательство. Возможны четыре комбинации соседей.

1. Ни один не примыкает: bp.s.next направляется на правого соседа, p.s.next — на bp. Блок вставлен между p и правым соседом, адресный порядок сохранён, размеры не менялись, дизъюнктность следует из корректности bp.
2. Примыкает только правый: [math]\displaystyle{ bp + bp.s.size = p.s.next }[/math]. Новый размер bp равен сумме двух смежных блоков, а ссылка ведёт через правый сосед. Объединение не пересекается с остальными, потому что оба блока были дизъюнктны с ними, а их общая граница совпадает.
3. Примыкает только левый: [math]\displaystyle{ p + p.s.size = bp }[/math]. Размер p увеличивается на размер bp, ссылка p.s.next направляется через bp. Симметрично случаю 2.
4. Примыкают оба: сначала bp поглощает правого соседа, затем p поглощает bp. Итоговый блок — объединение трёх смежных блоков; его размер равен сумме, ссылка ведёт через правого соседа правого соседа. Все три блока были дизъюнктны с остальными, поэтому итог тоже.

Отдельно оговорён правый сосед base: проверка p->s.next != &base не даёт блоку поглотить сторожевой узел, даже если блок заканчивается ровно на &base. Нижнее слияние с base невозможно из-за base.s.size = 0. Поэтому base остаётся в кольце во всех четырёх случаях.

Во всех случаях freep = p — узел кольца, а bp встречается в кольце ровно один раз. [math]\displaystyle{ \blacksquare }[/math]

Теорема 4 (безопасность выдачи). Любой указатель, возвращённый Alloc, указывает на полезную область блока, который не пересекается ни с одним другим живым или свободным блоком и имеет ёмкость не меньше [math]\displaystyle{ n }[/math] байт.

Доказательство. Индукция по операциям. База — пустая арена, инвариант тривиален. Шаг для Alloc и Afree — леммы 1–3. Ёмкость: [math]\displaystyle{ u - 1 }[/math] единиц полезной области, то есть [math]\displaystyle{ (u-1)H \ge n }[/math] по определению [math]\displaystyle{ u }[/math]. Выравнивание: [math]\displaystyle{ p }[/math] выровнен по alignof(Header), а [math]\displaystyle{ H }[/math] кратен этой величине, значит [math]\displaystyle{ p+1 }[/math] выровнен не хуже заголовка. [math]\displaystyle{ \blacksquare }[/math]

Теорема 5 (сложность). Alloc и Afree стоят [math]\displaystyle{ O(k) }[/math], где [math]\displaystyle{ k \le m }[/math] — число свободных блоков; Morecore стоит [math]\displaystyle{ O(k) }[/math] на вызов Afree плюс стоимость получения памяти (sbrk). Если моделировать sbrk как [math]\displaystyle{ O(nu) }[/math], суммарно получается [math]\displaystyle{ O(nu + k) }[/math].

Доказательство. За один проход Alloc просматривает каждый свободный блок не более одного раза: старт — freep.s.next, конец — возврат к freep; при исчерпании добавляется один полный в худшем случае второй проход после Morecore. Afree выполняет не более [math]\displaystyle{ k+1 }[/math] переходов по кольцу (лемма 2) и [math]\displaystyle{ O(1) }[/math] работы на слияния. Morecore вызывает Afree, который просматривает [math]\displaystyle{ O(k) }[/math] блоков, и оформляет [math]\displaystyle{ nu }[/math] единиц за [math]\displaystyle{ O(1) }[/math]; стоимость sbrk учитывается отдельно (в модели sbrk = [math]\displaystyle{ O(nu) }[/math] итог [math]\displaystyle{ O(nu + k) }[/math]). [math]\displaystyle{ \blacksquare }[/math]

Рекуррентных соотношений здесь нет: все операции итеративные, а оценка получается прямым подсчётом шагов цикла. Поэтому вместо решения рекурренты в доказательстве используется инвариант кольца.

Граница кольца. Отдельно разберём случай, когда свободных блоков нет вообще: в кольце только base, и base.s.next = base. Тогда для любого корректного bp внешнее условие bp > base and bp < base ложно, а внутреннее base >= base and (bp > base or bp < base) истинно, поэтому цикл сразу прерывается и блок вставляется после base. Если заменить >= на >, внутреннее условие не сработает, и цикл будет бесконечно ходить по base. Это не теоретическая придирка: такое кольцо возникает при первом же освобождении, если арена была полностью занята.

Фрагментация. Внутренняя фрагментация ограничена: не более [math]\displaystyle{ H-1 }[/math] байт на блок из-за округления. Заголовок [math]\displaystyle{ H }[/math] байт — отдельные служебные накладные расходы, поэтому полные потери не превышают [math]\displaystyle{ 2H-1 }[/math] байт на блок. Внешняя фрагментация не ограничена сверху: например, в арене из 10 единиц свободны блоки [0, 3) и [7, 3), а между ними занят [3, 4); запрос [math]\displaystyle{ u = 5 }[/math] невыполним, хотя суммарно свободно 6 единиц. Аллокатор не перемещает блоки и не может сложить эти участки. Именно поэтому first-fit без компактификации непригоден для длительной работы с разнородными размерами.

Сравнение с альтернативами

Вариант	Выдача	Освобождение	Фрагментация	Возврат ОС	Потоки	Выравнивание	Детерминизм
Bump §5.4	[math]\displaystyle{ O(1) }[/math]	только LIFO	неиспользованный остаток буфера	нет	нет	по типу буфера	полный
K&R §8.7	[math]\displaystyle{ O(k) }[/math]	любой порядок	внешняя возможна	нет	нет	alignof(Header)	полный при данной истории
dlmalloc/ptmalloc	[math]\displaystyle{ O(1) }[/math]–[math]\displaystyle{ O(\log n) }[/math]	любой	ниже за счёт бинов и границ	частично	да, арены	16 байт на x86-64	зависит от реализации
jemalloc/tcmalloc	[math]\displaystyle{ O(1) }[/math] на класс размера	любой	низкая за счёт классов	да	да, кэши	16 байт на x86-64	зависит от реализации
mmap/арена	страницы	сброс арены	нет на уровне блоков	да	по желанию	страницы	полный

Вердикт. K&R — учебный и встраиваемый аллокатор, а не промышленный распределитель общего назначения. Он хорош там, где важны компактность кода, отсутствие зависимостей и предсказуемость: в курсе C, в статической арене микроконтроллера, в простом пуле. Он плох там, где нужны потоки, возврат памяти операционной системе, устойчивость к фрагментации и защита от ошибок: глобальные base/freep не потокобезопасны, память не возвращается, а двойное освобождение не диагностируется.

Современные библиотеки устроены иначе. В glibc крупные запросы обслуживаются через mmap (по умолчанию от 128 КиБ), а для многопоточности создаются дополнительные арены с собственными блокировками [5]. jemalloc и tcmalloc используют классы размеров и кэши на поток, а dlmalloc — границы блоков и бины. Общего с K&R у них только базовая идея: метаданные рядом с блоком и повторное использование освобождённой памяти. Код K&R в них не используется.

Внешняя фрагментация и обусловленный ею отказ показаны на рис. 6.

Рис. 6. Внешняя фрагментация: свободно 6 единиц, но запрос 5 единиц невыполним — занятый блок B разделяет свободные участки.

Где применяется

1. Обучение C и указателям. Пример §8.7 — один из немногих коротких текстов, где в одном месте собраны union, выравнивание, арифметика указателей, циклический список, сторожа и доказательство инварианта. Студент видит, как из примерно ста строк получается работающий аллокатор. Именно поэтому пример живёт в книге с 1978 года [1], [2].
2. Исторические Unix-аллокаторы. В 1970-х и 1980-х память процесса наращивалась через brk/sbrk, а библиотечный malloc был надстройкой над непрерывной кучей. Схема K&R — упрощённая модель таких аллокаторов: заголовок в блоке, свободный список, слияние соседей. Она объясняет, откуда взялись термины «заголовок блока» и «first-fit» [3], [4].
3. Встраиваемые системы с фиксированной ареной. На микроконтроллере нет ни sbrk, ни виртуальной памяти, зато есть статический массив. Аллокатор K&R легко переносится: достаточно заменить morecore на выдачу кусков из массива, как в нашем тесте. Выигрыш — отсутствие зависимости от libc и полный контроль над адресами; проигрыш — фиксированный размер арены и отсутствие потокобезопасности.
4. Пулы и арены в играх и серверах. Игровой кадр или серверный запрос часто имеют общий жизненный цикл: всё, что выделено за кадр, освобождается целиком. Простейший пул — это арена с bump-выдачей и сбросом; если же объекты освобождаются по отдельности, берут вариант со свободным списком и слиянием. K&R показывает минимальную рабочую конструкцию, на которую такие пулы опираются концептуально.
5. Кастомные аллокаторы интерпретаторов и СУБД. Интерпретатору нужны мелкие объекты одинакового размера (ячейки, узлы AST), а СУБД — буферы страниц. Промышленные решения используют slab-аллокаторы и классы размеров, но отправная точка та же: метаданные рядом с объектом и список свободных участков. K&R полезен как минимальная модель, а не как готовый компонент.
6. Лабораторные по операционным системам. Задание «реализуйте malloc/free» почти всегда начинается с first-fit и слияния соседей; пример K&R — эталонная постановка задачи и источник тестовых сценариев (фрагментация, двойное освобождение, исчерпание арены).

Историческая справка

• 1978. Первое издание «The C Programming Language» Брайана Кернигана и Денниса Ритчи выходит в Prentice Hall. В главе 8, посвящённой интерфейсу Unix, есть пример распределителя памяти; в издании 1978 года нумерация подразделов может отличаться от второго издания [2].
• 1988. Второе издание книги фиксирует пример как §8.7 «Example — A Storage Allocator». Именно этот текст с функциями malloc и free, объединением header, base, freep, morecore и NALLOC считается каноническим [1]. В коде используются unsigned size и typedef long Align.
• 1970-е–1980-е. sbrk — стандартный способ расширить сегмент данных процесса в Unix; malloc библиотеки C строится над ним. Позже sbrk объявляют устаревшим: SUSv2 помечает его как LEGACY, а POSIX.1-2001 исключает из стандарта [6]. Современный glibc использует brk для небольших запросов и mmap для крупных [5].
• 1989. ANSI C (C89/C90) стандартизует malloc, free, calloc и realloc в <stdlib.h>; реализация остаётся делом библиотеки. Пример K&R не становится стандартом — он остаётся учебной моделью, по которой студенты понимают, что скрывается за этими функциями.
• 1960-е–1970-е. Задача динамического распределения памяти изучалась задолго до K&R: Кнут в §2.5 первого тома TAOCP описывает схемы с границами блоков, first-fit и best-fit, а также проблемы фрагментации [3]. Поэтому K&R — не первый аллокатор, а удачная учебная компиляция известных идей.
• 1995. Обзор Wilson, Johnstone, Neely и Boles систематизирует стратегии распределения, фрагментацию и метрики; он показывает, что first-fit — лишь одна точка в большом пространстве решений [4].
• 2000-е. Появляются масштабируемые аллокаторы (jemalloc, tcmalloc), ориентированные на многопоточность и классы размеров; K&R остаётся учебным примером, а не рабочей реализацией.

Типичные ошибки и подводные камни

• Двойное освобождение. Повторный Afree вставляет уже вставленный блок. Размеры складываются дважды, кольцо может замкнуться на себя. В кольце из одного блока (base или единственный свободный блок) цикл поиска не завершится. Диагностика: магическое число в заголовке, проверка «блок уже свободен» по флагу, санитайзеры.
• Освобождение чужого указателя. ap обязан быть результатом Alloc. Указатель на середину блока, на статический массив или на malloc из libc приведёт к чтению мусора в качестве заголовка и к порче арены.
• Переполнение при вычислении [math]\displaystyle{ u }[/math]. Выражение n + sizeof(Header) - 1 переполняется, если [math]\displaystyle{ n }[/math] близко к SIZE_MAX. Без проверки аллокатор вернёт блок заведомо недостаточного размера. Проверка должна стоять до деления.
• [math]\displaystyle{ n = 0 }[/math]. K&R предполагает [math]\displaystyle{ n \gt 0 }[/math]; стандартный malloc(0) может вернуть уникальный указатель или NULL. В учебной реконструкции выбран NULL, и это надо документировать.
• Путаница единиц и байт. size хранится в единицах, а не в байтах. Если записать туда байты, все проверки размеров и слияния станут неверными; ошибка проявляется далеко от места записи.
• p > p->s.next вместо p >= p->s.next. В кольце из одного узла равенство — единственный признак конца; с > Afree зацикливается. Это самая коварная однобуквенная ошибка в алгоритме.
• Сравнение указателей из разных объектов. base — отдельный статический объект, а блоки — элементы массива arena; реляционные сравнения bp > p между ними формально не определены стандартом C. K&R опирается на плоскую адресацию; переносимый вариант — сравнивать приведённые к uintptr_t значения.
• Ненулевой размер base. Если base.s.size случайно станет больше нуля, сторожевой узел начнёт «поглощать» соседей, и границы блоков перестанут соответствовать реальным. Размер base должен оставаться нулевым всегда.
• Отрезание головы вместо хвоста. Формально возможно, но требует обновления prevp.s.next и повышает шанс ошибки. K&R отрезает хвост, чтобы не трогать ссылки; при переписывании «по-своему» это легко потерять.
• Невыровненный sbrk. Если система вернула невыровненный указатель, заголовок и payload окажутся невыровненными. На классических Unix граница выровнена, но переносимый код должен проверять или выравнивать вручную.
• Переполнение nu * sizeof(Header) в morecore. В K&R этой проверки нет; при больших nu произведение может обернуться, и sbrk получит неверный размер.
• freep как канал возврата из morecore. Глобальная переменная используется и как состояние поиска, и как результат операции. Это работает, но делает код хрупким: любое изменение freep между Afree и возвратом ломает контракт.
• Потокобезопасность. base и freep — глобальные; одновременные Alloc/Afree из разных потоков портят список. Нужен мьютекс или арена на поток.
• Отсутствие возврата памяти. K&R никогда не отдаёт память обратно: даже полностью свободная арена остаётся занятой процессом. Для длительной работы это неприемлемо.
• Неблагоприятная нагрузка. Чередование запросов разных размеров может довести число свободных блоков до линейного и сделать каждую операцию линейной. First-fit не защищает от такого сценария.

Задачи для практики

1. Базовая реализация. Реализуйте kr_alloc, kr_free, kr_morecore и проверьте их на 20 000 случайных операциях с картой владения. Подсказка: отметьте каждую единицу арены и сверяйте шаблон перед освобождением. Ответ: при корректной реализации все ассерты проходят, после освобождения остаётся один блок.
2. Двойное освобождение. Воспроизведите зависание в кольце из одного блока и объясните, какое условие не срабатывает. Подсказка: подставьте base.s.next = base в цикл. Ответ: внешнее условие ложно, а внутреннее с > не срабатывает; нужен признак «блок уже свободен».
3. Best-fit против first-fit. Реализуйте обе стратегии и сравните суммарную внешнюю фрагментацию на смешанной нагрузке. Подсказка: best-fit просматривает всё кольцо, first-fit останавливается на первом подходящем. Ответ: best-fit уменьшает число отказов, но платит полным просмотром.
4. realloc. Реализуйте расширение блока на месте, если следующий блок свободен, иначе — alloc + копирование + free. Подсказка: слияние с правым соседом и последующее отрезание хвоста. Ответ: амортизированная стоимость копирования — как у динамического массива.
5. Потокобезопасность. Добавьте мьютекс вокруг Alloc/Afree и измерьте, как падает пропускная способность при 8 потоках. Подсказка: один глобальный мьютекс сериализует всё; арена на поток масштабируется лучше. Ответ: выигрыш даёт не блокировка, а разделение арен.
6. Границы блоков. Добавьте в конец блока копию размера (footer) и указатель на предыдущий свободный блок. Подсказка: тогда Afree находит соседей за [math]\displaystyle{ O(1) }[/math] без поиска. Ответ: ценой нескольких служебных полей на блок и усложнения split/merge.
7. Перенос на Linux. Соберите вариант с sbrk, запустите под strace и посчитайте число системных вызовов. Подсказка: NALLOC снижает число вызовов, но не отменяет их при исчерпании. Ответ: число brk много меньше числа Alloc.
8. Краевые случаи. Проверьте [math]\displaystyle{ n = 0 }[/math], [math]\displaystyle{ n = \text{SIZE_MAX} }[/math], выравнивание по _Alignof(max_align_t) и поведение при исчерпании арены. Подсказка: проверка переполнения должна стоять до умножения и деления. Ответ: все случаи возвращают NULL без неопределённого поведения.

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

• Динамический массив — реаллокация, геометрический рост и амортизация; realloc в задаче 4 опирается на те же идеи.
• Связный список — циклический список, сторожевой узел и вставка; кольцо свободных блоков устроено так же.
• Асимптотическая сложность — [math]\displaystyle{ O(k) }[/math], [math]\displaystyle{ O(m) }[/math] и различие худшего и амортизированного случаев.
• Амортизационный анализ — почему NALLOC удешевляет системные вызовы и почему это не улучшает худший случай.
• Виртуальная память — brk, sbrk, mmap и гранулярность страниц.
• Сборка мусора — альтернативный способ вернуть память без явного Afree.

Источники

1. Kernighan B. W., Ritchie D. M. The C Programming Language. 2nd ed. — Prentice Hall, 1988. — Ch. 8, §8.7 «Example — A Storage Allocator».
2. Kernighan B. W., Ritchie D. M. The C Programming Language. 1st ed. — Prentice Hall, 1978. — Ch. 8 (пример распределителя памяти; точная нумерация подраздела в первом издании может отличаться).
3. Knuth D. E. The Art of Computer Programming. Vol. 1: Fundamental Algorithms. 3rd ed. — Addison-Wesley, 1997. — §2.5 «Dynamic Storage Allocation».
4. Wilson P. R., Johnstone M. S., Neely M., Boles D. Dynamic Storage Allocation: A Survey and Critical Review // Proc. International Workshop on Memory Management (IWMM'95). — Springer, 1995. — LNCS 986.
5. Linux man-pages: malloc(3), free(3). URL: https://man7.org/linux/man-pages/man3/malloc.3.html.
6. Linux man-pages: brk(2), sbrk(2). URL: https://man7.org/linux/man-pages/man2/brk.2.html.
7. ISO/IEC 9899:2011. Information technology — Programming languages — C. — §6.2.8 (Alignment of objects), §7.22.3 (Memory management functions).