Программисты, работающие с языком C, несомненно, узнают стандартную функцию malloc(). Это главный аллокатор памяти в языке, который тесно связан со всем известными ошибками сегментирования. Функция malloc() – именно то средство, при помощи которого программы приобретают память во время выполнения. Зачастую она также превращается в основной инструмент создания объектов и управления ими. Учитывая такой центральный статус malloc(), удивлён, что большинство программистов обращаются с ней как с чёрным ящиком. Этот пост призван немного исправить ситуацию, и в нём рассказано, что именно происходит под капотом. Также рассмотрим одну из возможных реализаций этой функции.

Как правило, на практике память выделяется так: функция malloc() вызывается с параметром, в котором указывается запрошенное количество байт. Функция malloc() возвращает указатель, через который память можно использовать, а когда она больше не будет нужна — возвратить в систему, вызвав free() :

/* Выделить память для структуры типа [struct article] */
struct article *my_article = malloc(sizeof *my_article);

if(my_article != NULL) {
    /* ... использовать *my_article ... */
    free(my_article);
}

Этот простой фрагмент кода поднимает не менее трёх важных вопросов:

• Откуда именно берётся память?

• Как именно можно выделять переменные любого типа, даже не сообщая malloc(), какой тип нам нужен?

• Как именно malloc() отслеживает адрес и размер любого выделяемого нами объекта?

Позволим себе небольшую авантюру и попытаемся ответить на все эти вопросы.

TL;DR для самых нетерпеливых: речь пойдёт о наилучшем совпадении разделённых фрагментов с использованием 16 классов, код однопоточный, совершенно стандартный.

Куча берётся из системы

Первый вопрос «Откуда именно берётся память?» подводит нас к разговору о системе, и вот вам короткий ответ, которого вы, возможно, уже дожидаетесь: «её предоставляет операционная система». Вполне хороший ответ, но как нам перейти от такой абстрактной концепции к конкретному указателю, в который мы сможем записывать данные?  

Картина в классическом пользовательском пространстве

В классических операционных системах каждый процесс из пользовательского пространства обитает в собственном адресном пространстве, где загружены его код, все библиотеки и данные. Наличие отдельного адресного пространства для каждого процесса — это ключевой аспект проектирования операционных систем, я уже не помню, сколько раз об этом рассказывал. Если коротко — процессы не пишут данные в память других процессов и не читают данные оттуда (в настоящее время это делается в основном по соображениям безопасности). Эта работа организуется на аппаратном уровне при помощи блоков управления памятью.

От конкретной операционной системы зависит, как именно в ней уложено адресное пространство. В принципе, оно может быть любым; можно подготовить вариант такой компоновки как готовится завтрак, и это будет нормально. Это настолько маловажный вопрос, что в Linux информация просто распределяется по произвольным адресам для более качественной защиты от атак, основываясь на информации о том, где именно в виртуальной памяти расположен код. Простой пример может выглядеть примерно так (чуть ниже мы его разберём):

Такое адресное пространство называется виртуальным, поскольку никакой памяти под него не отведено. Реальная память, установленная в компьютере (чип ОЗУ) существует одним большим блоком в так называемом физическом адресном пространстве. Здесь я немного упрощаю; на самом низком уровне оперативная память может выглядеть в физическом адресном пространстве фрагментированной. На самом деле, в архитектуре x86 она может содержать что угодно; если у вас ещё осталась лишняя вера в людей, от которой вам требуется избавиться — познакомьтесь с вызовом BIOS e820. В конце концов, это не важно, так как вся память разбита на страницы. Разумеется, любой процесс, обладающий полным доступом ко всей оперативной памяти, будет работать в «режиме бога», поэтому только у ядра есть такая привилегия. Обычные процессы получают доступ к памяти, когда ядро выдаёт им некоторую долю памяти, отображая её на их виртуальное адресное пространство:

Этот процесс называется подкачкой страниц. В сущности, как виртуальное, так и физическое адресное пространство разделены на страницы (размер страниц может варьироваться, но чаще всего страница памяти занимает 4 КБ), а ядро решает, какие страницы виртуальной памяти должны отображаться на какие страницы физической памяти. Когда программа обращается к памяти, ЦП проверяет, относится ли к отображённой странице тот указатель, по которому это обращение произошло. Если так, то ядро обращается к ассоциированной с ней физической странице. В противном случае доступ строго запрещён, и программа вылетает в результате ошибки сегментирования. Термин «ошибка сегментирования» сохранился с давних времён, когда память ещё не выделялась постранично, а нарезалась сегментами. Если вы не знаете, что такое «сегментирование» - не вникайте, всё равно это была ужасная техника. Отказы страниц также происходят лишь в том случае, если ядро отображает страницы по требованию, такой случай я здесь рассматривать не буду. В таком случае ядро полностью контролирует, какую именно информацию может читать и записывать каждый процесс в памяти. Так обеспечивается необходимое разделение, о котором я писал выше.

Итак, вернёмся к обсуждению компоновки, этот вопрос мы затрагивали выше. Далее мы рассмотрим:

• Программный код: он загружается прямо из исполняемого файла программы.

• Библиотеки: динамические библиотеки, загружаемые при пуске программы, в принципе, функционально аналогичны коду.

• Сегмент статических данных: в этом сегменте содержатся глобальные и статические переменные.

• Стек: в нём сохраняются локальные переменные функций.

• Куча: это область памяти, управляемая malloc().

Поскольку код предназначен только для чтения, а сегмент с данными статичный (то есть, перед запуском кода размер этого сегмента является фиксированным), в памяти остаётся всего два участка, которые могут расти во время выполнения программы — это стек и куча. Сам стек довольно маленький; под Linux команда ulimit -s сообщит вам его максимальный размер, который обычно равен 8 МБ. Кроме того, время жизни стека очень строго ограничено; любой созданный объект уничтожается, как только возвращается создавшая его функция. Остаётся поговорить о куче. На ПК или смартфоне именно в куче находится основная масса памяти в программах используется именно теми данными, которые лежат в куче. Когда ваш браузер отжирает 5 ГБ памяти — то можно считать, что это 5 ГБ кучи. Если в Linux требуется выделить большой кусок памяти, для этого у ядра обычно запрашивается полный набор страниц. Для этого используется системный вызов mmap(2). Я отношу его к той же категории, что и malloc(). Забавно: 32-битные виртуальные пространства слишком тесные, поэтому фрагментация быстро начинает доставлять неудобства. 

Куча, как и всё прочее в виртуальном адресном пространстве, создаётся, когда ядро отображает страницы физической памяти на подходящий виртуальный адрес. Следовательно, на вопрос «откуда берётся память?» отвечаем так: «ядро отображает новые страницы на адресное пространство». Процесс запрашивает такую операцию, выполняя системный вызов sbrk(2), после чего ядро эту операцию разрешает. Тогда новые страницы отображаются на память, и указатели на эти страницы начинают работать. Наблюдать развитие этого процесса можно практически в любом аллокаторе, поддерживающем работу с Linux. Например, аллокатор glibc реализует этот примитив «нужно больше памяти» в morecore.c, а сам вызов сводится к непрямой активации sbrk(2).

Итак, что тут происходит: malloc() получает память от ядра через вызов sbrk(2), а ядро предоставляет память, от отображая целые страницы (по 4 кБ или более). Задача malloc() — разбить эти страницы на блоки такого размера, как нужно пользователю, и при этом отслеживать, какая память используется, а какая свободна.

Картина во встраиваемых системах

Естественно, не каждая система оснащена полнофункциональным ядром с виртуальной памятью, работающей по принципу подкачки страниц. Существует и множество других вариантов, но механизмы действуют одни и те же. Во многих встраиваемых системах под кучу предоставляется фиксированная область памяти; в таком случае malloc() просто некуда расширяться. Аллокаторы достаточно хорошо справляются с памятью фиксированного или переменного размера — им всё равно. Суть проектируемой системы в том, как именно нарезается выдаваемая память, и как она управляется.

Лепим переменные из сырой памяти при помощи "максимального выравнивания"

Выше мы обсуждали память исключительно как сырые данные — последовательности байт, упорядоченные в виде страниц, доступные для чтения и записи. Но главная возможность malloc(), которая нас интересует — создавать переменные. В языке C постоянно делается упор на то, что мы обязаны объявлять тип переменных. Каким же тогда образом можно создавать их при помощи malloc(), зная лишь размер?

/* Для локальной переменной требуется указать тип... */
int i;
/* ... но каким-то образом malloc() без этого обходится? */
int *j = malloc(4);

Можно подумать, что я уже объявил тип для фрагмента выделяемой памяти, когда написал int* j, но на самом деле это не так. Применительно к типизации, второе определение на самом деле состоит из двух этапов. Сначала компилятор типизирует malloc(4) саму по себе, без какого-либо контекста, а затем убеждается, что такое присваивание является допустимым, то есть, что тип malloc(4) можно преобразовать в int . Это важное свойство языка C: выражения всегда типизируются вне контекста, независимо от того, что вы с ними делаете. Специалистам по C++ эта концепция, пожалуй, более известна в такой формулировке: «возвращаемые типы не участвуют в разрешении перегрузок». Такой резкий контраст с типизацией в функциональных языках, где типы выводятся в направлении снизу вверх, а проверка типов идёт сверху вниз, и обычно типы дополняют друг друга в рамках так называемой «двунаправленной типизации» [Dunfield2021]. В C/C++ типизация идёт только снизу вверх. 

В данном случае имеем дело с malloc(4) типа void *, т.e., с универсальным указателем, который можно преобразовать в любой указатель нефункционального типа. Никакая информация, касающаяся типа j, не сообщается malloc().Таким образом, сохраняется вопрос: как malloc() удаётся выделить подходящий участок памяти, когда желаемый тип неизвестен?

Оказывается, что подходящая память, в сущности, сводится к двум свойствам. Чтобы в некоторой области памяти могла содержаться переменная типа T, эта область обязана:

1. Иметь размер как минимум sizeof(T);

2. Иметь выравнивание большее или равное выравниванию T.

Выравнивание данных понимается как максимальная степень двойки, на которую делится адрес. По архитектурным соображениям значения определённых базовых типов могут храниться только в участках памяти, идущих от одной до другой границы в пределах такого выравнивания. Как правило, значения примитивов, занимающие N байт (где N — степень двойки) будут храниться исключительно по адресам, кратным N. Таким образом, однобайтный char можно сохранить по любому адресу, но двухбайтный short — только по чётным адресам, а 4-байтный int — по адресам, кратным 4 и т.д.

Лишь к базовым типам (целые числа, числа с плавающей точкой и указатели) применяются архитектурные требования к выравниванию. Поэтому, если вы хотите выяснить, какова компоновка структур, объединений и других составных типов, то узнаете, что каждый тип в итоге приходит к требованиям выравнивания, предъявляемым к базовому типу. Также можно затребовать для типа или переменной более крупное значение выравнивания, это указывается при помощи атрибута, специфичного для конкретного компилятора. В таком случае речь идёт о так называемом типе с нестандартным выравниванием. В данном случае локальные переменные, создаваемые с таким типом, будут правильно выровнены, но malloc() не будет уважать это требование. Поэтому данный аспект требуется учитывать вручную или с использованием функции aligned_alloc() из C11 [ISOC11 §7.22.3.1]. 

Таким образом, требование к максимальному выравниванию для любого базового типа (max_align_t в C++, обычно 4 байта в 32-разрядных архитектурах и 8 байт в 64-разрядных архитектурах) применимо к каждому отдельному типу в языке.

Та загадка, с которой мы столкнулись, решается благодаря универсальному выравниванию, поскольку malloc() может просто возвращать указатели с максимальным выравниванием, приспосабливаясь таким образом к работе с любым типом данных. Неудивительно, что именно это требуется от него в старом добром C99 [ISOC99 §7.20.3.1]:

Явно не указывается как порядок следующих друг за другом вызовов к функциям calloc, malloc и realloc, так и непрерывность области, выделенной для их хранения. Если операция выделения памяти пройдёт успешно, то возвращаемый при этом указатель будет подходящим образом выровнен, так, что может быть присвоен указателю, направленному на объект любого типа, а затем использоваться для обращения к такому объекту или массиву таких объектов во всём выделенном пространстве (пока выделение этого пространства не будет явным образом отменено).

В большинстве реализаций malloc() параметризуются именно этим выравниванием. Я работаю с 32-разрядной архитектурой, поэтому максимальное выравнивание, с которым мне приходится иметь дело — 4. Как вы вскоре увидите, это сказывается на размере блоков и заголовков; эти величины должны быть кратны 4-м.

Знакомство с реализацией, в которой применяется наилучшее совпадение разделённых фрагментов

Таким образом, вот что, в сущности, должна уметь реализация malloc():

• Управлять областью памяти, которая может быть либо фиксируемой, либо расширяемой. Для этого нужно отображать на неё новые страницы при помощи sbrk();

• В ответ на запросы о выделении памяти вырезать блоки, максимально выровненные по границам памяти;

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

Именно из третьего пункта проистекает всё разнообразие реализаций. Можно сказать, что существует миллион разновидностей стратегий выделения памяти, структур данных, не говоря уже о сборщиках мусора. Я бы солгал, если бы заявил, что могу дать вам наглядный обзор всего этого. Общее введение в эту тему вы найдёте в потрясающей статье Dynamic storage allocation: A survey and critical review [Wilson1995].

Вот и вся общая информация, которую я хотел вам сообщить. В оставшейся части статьи мы разберём ту реализацию алгоритма наилучшего совпадения разделённых фрагментов, которую я написал для gint. Оригинальный код можете посмотреть в репозитории gint по адресу src/kmalloc/arena_gint.c; здесь я сначала помогу вам сформировать впечатление о задаче, а затем перейду к, надеюсь, вполне понятным версиям malloc() и free(). Буду перемежать иллюстрации и код на C.

Обратите внимание: предполагается, что этот код вполне можно читать без контекста, однако этот код несколько неполон (в большинстве примеров частично пропущен код, касающийся инициализации).

Блочная структура и как сориентироваться в последовательности

Как обычно при работе с аллокаторами общего назначения, я буду отслеживать метаданные для каждого выделенного фрагмента памяти. Эта информация пойдёт в коротком заголовке, который будет предшествовать самому выделенному пространству. Таким образом, куча будет сложена из блоков следующей формы:

Блоки самого простого типа — задействованные (used): они состоят из 4-байтного заголовка, за которым следуют пользовательские данные, представленные как хешированная область. Функция malloc() возвращает указатель на пользовательские данные — и только этот указатель можно будет увидеть снаружи. В заголовке записывается размер блока, а также информация, которая может пригодиться для навигации по куче, чтобы найти другие блоки. Вот определение соответствующей структуры:

typedef struct {
    uint            :5;
    uint last       :1;     /* помечает последний блок в последовательности */
    uint used       :1;     /* Указывает, используется ли блок */
    uint prev_used  :1;     /* Указывает, используется ли предыдущий блок (граничная метка) */
    uint size       :24;    /* Размеры блоков в байтах (< 16 МБ) */
} block_t;

У свободных блоков — такой же 4-байтный заголовок, но у них ещё есть дополнительные данные в «подвале» файла. Эта черта свободных блоков особенно приятна: никакие данные в них не хранятся, поэтому их свободное пространство вполне можно использовать для поддержки структуры данных. prev_link и next_link используются для соединения некоторых связных списков; сейчас к этому перейдём. Пока нам достаточно знать, что это — указатели на другие блоки.

Блоки сохраняются непосредственно друг за другом без всяких зазоров и образуют длинную последовательность, которая покрывает целую область кучи (арену) за исключением небольшой структуры-индекса, размещаемой в начале этой области:

В заголовке block_t есть два нетривиальных флага, и оба они относятся к этой последовательности: last отмечает последний блок, а prev_used — это копия флага used из предыдущего блока. Вот какое (весьма вкусное!) применение предусмотрено для этого блока.

Обратите внимание, как легко продвигаться по этой последовательности вперёд: имея указатель на начало блока, можно найти указатель на его конец (то есть, на начало следующего блока), поскольку размер блока сообщается в заголовке.

Ожидаемо, что код очень прост:

	block_t *next_block(block_t *b)
{
    if(b->last)
        return NULL;
    return (void *)b + sizeof(block_t) + b->size;
}

Что ж, оказывается, свободные блоки устроены так, что можно сделать и прямо противоположное: найти начало свободного блока, если известно, где он заканчивается. Эта практика сводится к тому, что мы узнаём размер блока, опираясь на информацию из «подвала», и это действительно работает:

• Если размер свободного блока составляет ≥ 12, то информация о размере такого блока просто хранится со сдвигом -12 от его конца.

• Может показаться, что свободный блок размером 8 будет целиком заполнен prev_link и next_link, но, если присмотреться — оказывается, что в каждом из них есть 4 свободных бита. Дело в том, что prev_link и next_link — это указатели на другие блоки и, следовательно, по размеру кратны 4 (поскольку для блоков действует выравнивание 4). Следовательно, есть 2 разряда низшего порядка, указатели на которые всегда равны 0, и можно утащить один из них под хранение флага, который будет идентифицировать 8-байтные блоки.

Итак, теперь, когда у нас есть указатель, направленный на конец свободного блока, можно поискать бит низшего порядка у next_link; если этот бит равен 1, то перед нами блок размером 8, в противном случае его размер можно прочитать, взяв сдвиг -12. В обоих случаях можно восстановить указатель, направленный на начало блока:

Разумеется, чтобы задействовать этот механизм для надёжной навигации при продвижении в обратном направлении, необходимо знать, свободен ли в самом деле предыдущий блок или нет. Именно для этого и используется флаг  prev_used в заголовке блока, а сама эта техника называется «оптимизацией с разметкой границ» (boundary tag optimization) — ценой одного бита можем позволить себе роскошь надёжно продвигаться назад, ориентируясь по пустым блокам.

	block_t *previous_block_if_free(block_t *b)
{
    if(b->prev_used)
        return NULL;
    uint32_t *footer = (void *)b;
    uint32_t previous_size = (footer[-1] & 1) ? 8 : footer[-3];
    return (void *)b - previous_size - sizeof(block_t);
}

В следующем разделе станет понятнее, в чём польза этой небольшой операции, но, если вам очень любопытно, то уже можете попробовать выяснить это самостоятельно.

Небольшое отступление. Очевидно, что при экономном подходе к работе с памятью, когда хочется не растратить впустую ни капли, самый разумный подход — плотно укладывать блоки. Но при таком подходе смертельно опасен становится выход за границы массива при записи, когда массивы выделяются динамически, поскольку в случае такого выхода немедленно повреждается следующий блок. Если сложится такая ситуация, то программа практически гарантированно откажет при следующем вызове malloc() или free(). На первый взгляд, это проблема, но на самом деле такая ситуация на пользу, поскольку выход за границы массива сразу проявляется, поэтому на практике баги  устраняются быстрее. На самом деле, когда данный новый аллокатор внедрили в gint, это спровоцировало мини-волну новых отказов — как оказалось, все они обусловлены багами в приложениях.

Объединение и разделение последовательных блоков

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

Если коротко — такая путаница неизбежна. Пользователь целиком контролирует все выделенные блоки и, в частности, имеет право высвобождать их в любом порядке, то есть, в любой момент оставлять «дыры». Поскольку в момент выделения блока нам не известно, как долго он просуществует (вполне возможно, и пользователю тоже не известно!), что-то распланировать здесь сложно. 

Вот что можно сделать, чтобы поддерживать последовательность в максимально аккуратном виде: объединять смежные свободные блоки, укрупняя их. Так возрастают шансы, что нам удастся удовлетворить крупные запросы  malloc(), а также гарантируется, что, если пользователь решит освободить все блоки, то мы получим один большой свободный блок, простирающийся на всю кучу.

Теперь, вооружившись столь простой идеей, можем определиться, что именно должны будут у нас делать malloc() и free(). Пока будем придерживаться общей процедуры, а конкретный код рассмотрим ближе к концу..

malloc(N):

• Ищем b, мельчайший свободный блок размера ≥ N, присутствующий в последовательности.

• Если такой блок не найден — значит, нам не хватило памяти (out of memory). Мы возвращаем NULL (... или используем sbrk(), чтобы получить ещё памяти и попробовать снова).

• Если размер b строго больше, чем N+4, то делим b надвое, чтобы приберечь немного свободной памяти.

• Помечаем b как использованный и возвращаем его.

Именно шаг 1 в этом алгоритме — залог наилучшего совпадения, так как на данном этапе мы находим «наилучший» блок, который можно выделить (то есть, максимально, насколько это возможно, соответствующий запрошенному размеру памяти). Вариант обманчив в том смысле, что не всегда является наилучшим — есть и много других стратегий. Основной недостаток такого подхода в том, что всякий раз при отсутствии идеального совпадения приходится отщипывать крохи от блока, который чуть крупнее запрошенного; в результате получаем уйму мелких свободных блоков, которые очень сложно использовать.

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

Функция для этой цели очень проста. Единственная тонкость заключается в том, как поддерживать флаги prev_used в близлежащих блоках.

block_t *split(block_t *b, int N)
{
    size_t extra_size = b->size - N;
    /* Разделяем лишь в том случае, если остаётся достаточно места для нового блока  */
    if(extra_size < sizeof(block_t) + 8)
        return NULL;

    block_t *second = (void *)b + sizeof(block_t) + N;
    second->last = b->last;
    second->used = false;
    second->prev_used = b->used;
    second->size = extra_size - sizeof(block_t);

    block_t *third = next_block(second);
    if(third)
        third->prev_used = second->used;

    b->last = false;
    b->size = N;
    return second;
}

Естественно, хочется, чтобы такое разделение получалось временным, насколько это возможно. Если в будущем оба блока вновь освободятся, то нам потребуется объединить их обратно. К счастью, это достаточно легко отслеживается. Во всех случаях, когда в результате работы free() в куче образуются смежные свободные блоки, можно отловить их все и просто объединить недавно освободившиеся блоки с соседними.

free(ptr):

• Найти ассоциированный с указателем блок b = ptr-4.

• Пометить блок b как свободный.

• Если за b следует другой блок, который свободен — объединить его с b.

• Если b предшествует другой блок, который свободен — объединить его с b.

В наилучшем случае, когда соседствуют свободные блоки, операция выглядит так:

Объединять блоки будет даже проще, если мы станем стирать заголовки, а не складывать их:

void merge(block_t *left, block_t *right)
{
  size_t extra_size = sizeof(block_t) + right->size;
  left->last = right->last;
  left->size += extra_size;

  /* Подвал блока обновляется отдельно */

  block_t *next = next_block(left);
  if(next)
      next->prev_used = left->used;
}

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

Разделённые связные списки

Теперь можете переходить к наивной реализации шага #1 в алгоритме malloc() (найдите мельчайший блок размера ≥ N), для этого проверьте по порядку все блоки в последовательности. У вас получится рабочий стандартный аллокатор памяти, действующий по принципу наилучшего совпадения — честно говоря, такое решение наиболее жизнеспособно в небольших встраиваемых системах. Однако, если у вас большая куча (скажем, 1 МБ), то вам в итоге придётся проверять много блоков и программ, часто выделяющих память. В таком случае, аллокатор превратится в узкое место.

На данном этапе вы уже можете переходить к глубоким и увлекательным исследованиям паттернов выделения памяти в различных программах. Например, можно отдельно обрабатывать блоки, срок жизни которых отличается, проектировать более качественные и информативные API, обеспечивающие более качественное планирование памяти, а также иными способами оттачивать время отклика до абсолютного совершенства.

Здесь я просто возьмусь предположить, что объём работы, совершаемой над блоком, коррелирует с его размером. Таким образом, поскольку с маленькими блоками приходится работать мало, malloc() должна реагировать на них быстро, иначе превратится в узкое место. С блоками  покрупнее и работы будет больше, поэтому в данном случае приемлемо, чтобы функция реагировала медленно. Конечно же, это приближение, но, как правило, оно верное.

Чтобы сократить время отклика при работе с небольшими блоками (которые и попадаются чаще всего) я разделю все свободные блоки на связные списки, так, чтобы блоки, входящие в состав каждого списка, были близки по размеру:

Это стандартные двусвязные списки, работающие с опорой на атрибуты prev_link и next_link, сохраняемые в подвалах свободных блоков. Рисунок можно понять превратно — на самом деле, блоки в составе каждого связного списка не обязательно сортировать по возрастанию адреса. Просто, если их изобразить именно таким образом, то иллюстрация получается нагляднее.

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

• Малые блоки (14 списков): 8 байт, 12 байт,..., 60 байт

• Средние блоки: 64 — 252 байт

• Крупные блоки: ≥ 256 байт

	int size_class(size_t size)
{
    if(size < 64)
        return (size - 8) >> 2;
    if(size < 256)
        return 14;
    return 15;
}

Для содержания указателей на эти списки и нужна индексная структура, которую я упоминал выше. В ней также отслеживается статистика кучи, но для простоты картины я не рассматриваю здесь эту информацию.

typedef struct {
    block_t *classes[16];   /* входные точки для разделённых связных списков */
    stats_t *stats;         /* статистика (её разбор выходит за рамки этой статьи)  */
} index_t;

Ключевая идея здесь заключается в том, что время, уходящее на обработку мелкого запроса, обычно является константным, поскольку первые 14 списков с небольшими блоками вообще не требуется обходить. Все блоки в них взаимозаменяемы, поэтому всегда можно просто взять первый. Только два последних списка действительно требуется прогнать через поиск наилучшего совпадения, и мы задействуем их для ответа на мелкие запросы лишь в случае, когда все подходящие малые списки пусты.

Не буду показывать вам код для манипуляции связными списками, поскольку он совершенно стандартный. Скажу лишь, что remove_link() удаляет свободный блок из ассоциированного с ней списка, а prepend_link() добавляет его обратно, ставя в самом начале списка. Функция best_fit(list, N) ищет в списке самый маленький блок размером ≥ N.

	/* Удалить b из ассоциированного связного списка */
void remove_link(block_t *b, index_t *index);
/* Добавить b в самом начале ассоциированного связного списка */
void prepend_link(block_t *b, index_t *index);
/* Найти в списке самый маленький блок размером ≥ N */
block_t *best_fit(block_t *list, size_t N);

Вероятно, вы уже и сами догадались, почему алгоритм называется именно так, но нужно пояснить, откуда взялась формулировка «наилучшее совпадение разделённых фрагментов»: блоки разного размера распределяются (разделяются) по двусвязным спискам, формируемым из блоков схожего размера.

Итоговая реализация malloc() и free()

Теперь давайте запишем функции malloc() и free() целиком. В malloc() мы округляем размер запроса вверх, а затем ищем свободный блок в ассоциированном связном списке. Если список пуст, то переходим к следующему связному списку, и так до тех пор, пока либо не найдём крупный блок, который можно разделить, либо не обнаружим, что полностью израсходовали память.

index_t *index = /* ... */;

void *malloc(size_t size)
{
    /* Округляем размер запроса вверх до значения, кратного 4, то есть, как минимум, до 8 */
    size = (size < 8) ? 8 : ((size + 3) & ~3);

    /* Пытаемся найти класс, в котором есть свободный блок нужного размера */
    block_t *alloc = NULL;
    for(int c = size_class(size); c <= 15 && !alloc; c++) {
        block_t *list = index->classes[c];
        /* Применительно к 14 самым мелким классам подойдёт любой блок, поэтому возьмём первый */
        alloc = (c < 14) ? list : best_fit(list, size);
    }
    if(!alloc)
        return NULL;

    /* Удаляем выбранный блок из списка */
    remove_link(alloc, index);

    /* Если он больше, чем требуется, то разделяем его и вставляем остаток обратно */
    block_t *rest = split(alloc, size);
    if(rest)
        prepend_link(rest, index);

    /* Помечаем блок как использованный и возвращаем указатель на его данные */
    block_t *next = next_block(alloc);
    alloc->used = true;
    if(next)
        next->prev_used = true;
    return (void *)alloc + sizeof(block_t);
}

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

void free(void *ptr)
{
    block_t *b = ptr - sizeof(block_t);
    block_t *prev = previous_block_if_free(b);
    block_t *next = next_block(b);

    /* Помечаем блок как использованный */
    b->used = false;
    if(next)
        next->prev_used = false;

    /* Если следующий за ним блок свободен — объединяем их */
    if(next && !next->used) {
        remove_link(next, index);
        merge(b, next);
    }
    /* Если предшествующий ему блок свободен — объединяем их */
    if(prev) {
        remove_link(prev, index);
        merge(prev, b);
        b = prev;
    }

    prepend_link(b, index);
}

Заключительные ремарки

Производительность

Мне особенно нечего добавить по поводу оценки производительности. Честно говоря, этот алгоритм не имеет особых достоинств кроме того, что, как правило, обеспечивает быстрый отклик на мелкие запросы. Что касается фрагментации (большая область кучи чрезмерно дробится на мелкие кусочки, и из-за этого память расходуется впустую), алгоритм наилучшего совпадения действительно не слишком хорош в этом отношении, но всего нескольких приложений gint достаточно, чтобы оказывать на кучу серьёзное давление и, следовательно, чтобы память быстро израсходовалась. Так что это тема для другой статьи.

realloc() и её расширения

Если заглянете в src/kmalloc/arena_gint.c, то найдёте там ряд функций, которые я здесь не разбирал. Для полноты картины упомяну их:

• realloc(), ещё одна стандартная функция для расширения блока. Она объединяет возможности malloc() и free(), но не привносит никаких новых сложностей, связанных с реализацией.

• malloc_max(), gint‑специфичная функция, выделяющая настолько крупный блок, насколько возможно. Время от времени она может пригодиться — когда требуется выделить память под данные, но заранее не известно, сколько памяти понадобится, а к тому же вы не хотите предварительно фиктивно их генерировать, как в случае с asprintf(). (realloc() может ужать блок, как только он заполнится.)

• Набор функций kmallocdbg_*(), проверяющих структурные инварианты. Полезны при поиске багов, а также для того, чтобы заставить программиста прописывать законы, которым обязаны следовать функции‑аллокаторы.

Управление множественными аренами

Поскольку ядро gint — специализированное, в нём не предоставляется функция sbrk(), и поэтому область кучи (арена) имеет фиксированный размер. Но в памяти есть весьма многочисленные несмежные области, используемые приложениями gint, поэтому в такой реализации необходимо обеспечивать поддержку множества арен, так, чтобы можно было создавать независимые кучи. Также можно создавать расширения с пользовательскими аллокаторами.

Присмотревшись к gint_malloc() и gint_free(), вы заметите этот дополнительный параметр void *data; это обобщённый пользовательский указатель, в каждой реализации передаваемый менеджеру арены. С его помощью я обращался к структуре индекса.

Заключение

Что ж, на этом пока всё. Надеюсь, что эта статья поможет вам более интуитивно понимать процесс управления памятью, а также разобраться, что именно делает функция malloc().