По заветам Никласа Лумана я начал пользоваться ящиком для заметок. Конечно, я приложил его на свой рабочий поток. Соответственно, некие статьи, интерпретации каких-то технических вещей стали появляться у меня сами собой. И я подумал: почему бы не выкладывать их хоть куда-то? Предлагать хабру свои статьи у меня совести не хватит, но сюда можно и выложить. Представляю вашему вниманию: заметка по buddy аллокатору в Linux.

Существует проблема при управлении памятью, которая заключается в том, что выделения и освобождения участков разных размеров приводит к фрагментации свободной памяти. Таким образом, несмотря на достаточный объём свободной памяти, может быть невозможным выделение непрерывного участка памяти требуемого размера — назовём это негативным эффектом фрагментации.

Для того, чтобы избежать негативного эффект от фрагментации, можно:

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

Оба варианта дорогие. У второго это по формулировке видно, а первый так или иначе потребует трансляции адресов (хорошо, если аппаратной) и управление этой трансляцией для каждого выделенного кусочка памяти.

Ядро предпочло второй вариант. На это есть несколько причин:

• Не всегда достаточно непрерывного участка линейного адресного пространства, иногда нужен именно непрерывный участок физической памяти. Например, для DMA, большинство реализаций которого не смогут транслировать адрес. Хотя да, есть аппаратные средства, например, у ARM это SMMU(System Memory Management Unit), который позволяет транслировать адреса как со стороны CPU, так и со стороны других подсистем машины. В частности, это помогает реализовывать виртуализацию аппаратных блоков, а также полезно для DPDK.
• Для реализации проецирования памяти пришлось бы реализовать механизм, который бы часто изменял таблицу страниц памяти, которая отвечает за трансляцию, что привело бы к повышению среднего времени доступа к памяти. Это не совсем очевидно, но чтобы обновить таблицу трансляций, нужно также очистить кэш как на локальном, так и на остальных CPU, т.к. в момент изменения таблицы трансляций, записи в кэше станут невалидными (физический адрес записи в кэше мог поменяться).
• Большие участки физической памяти могут быть доступны через страницы по 4 МБ, что сокращает промахи в TLB (Translation Lookaside Buffer). Таким образом, уменьшается среднее время доступа к памяти.

Разработчики Linux назвали свой алгоритм "buddy memory allocation" в честь так называемой "системы приятелей". Система приятелей заключается в том, что два человека могут объединить усилия в каком-либо деле, тем самым контролируя друг друга.

В рамках этого алгоритма все свободные страницы формируются в группы по 1,2,4,8..1024 (и т.д., в зависимости от аппаратной платформы) блоков. Начальный адрес каждой группы является произведением размера этой группы. Например, для группы по 16 страниц начальным адресом будет 16 * 2^12, где 2^12 — типичный размер страницы в 4 КБ. Понятно, что речь идёт о смещение относительно некоторого начала памяти для buddy allocator.

Приведу пример работы этого алгоритма:

Допустим, мы хотим выделить 1 МБ непрерывной физической памяти, то есть 256 страниц. Первым делом алгоритм проверит наличие свободного блока по 256 страниц. Если такой блок есть, то алгоритм отдаёт его, и работа закончена. Если такого блока нет, то алгоритм будет искать свободный блок по 512 страниц. Если такой блок есть, то алгоритм разобьёт его на два блока по 256 страниц, один отдаст пользователю, второй сохранит в группе других блоков по 256 страниц. Если и по 512 страниц блока не нашлось, тогда алгоритм попробует найти блок по 1024 страницы. Таким образом, блок по 1024 страницы будет разбит на три блока: один по 512, два по 256. Как только алгоритм дошёл до группы наибольшего размера и не нашёл свободной памяти, способной удовлетворить запрос, алгоритм безуспешно завершает свою работу и сигнализирует об ошибке.

Обратное действие — освобождение памяти — отсылает к названию алгоритма. Если мы хотим освободить участок непрерывной памяти размером в 1 МБ, то алгоритм попытается найти рядом свободный блок такого же размера и слить их в один блок. Таким образом, если рядом с только что освобождённым блоком по 256 страниц имеется ещё один блок по 256 страниц, то алгоритм объединит их в один блок по 512 страниц. В свою очередь, новообразованный блок по 512 страниц также может быть объединён с соседом в блок по 1024 страницы, если таковой сосед, конечно, имеется.

Формально описать правила для "приятелей", которых следует объединить, можно так:

• Оба блока одинакового размера.
• Оба блока находятся в одном непрерывном диапазоне физических адресов.
• Физический адрес первой страницы в первого блока является произведением 2 * [размер блока] * [размер страницы].

UPD:

Есть дополненная версия этой статьи здесь.