Введение

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

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

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

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

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

• Не всегда достаточно непрерывного участка линейного адресного пространства, иногда нужен именно непрерывный участок физической памяти. Например, для 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 * [размер блока] * [размер страницы].

Структуры данных

Для каждой зоны памяти создаётся свой buddy аллокатор. Таким образом, их три: для DMA, для NORMAL и для HIGH.

Инициализация памяти на старте

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

arch/arm64/mm/init.c:     zone_sizes_init /* заполняет max_zone_pfn */
mm/page_alloc.c:    free_area_init /* проходится по всем зонам и инициализирует их */
            free_area_init_node /* инициализирует ноду */
            free_area_init_core /* инициализирует каждую зону в ноде */
            memmap_init /* инициализирует memmap для зоны с заданным диапазоном страниц */
            memmap_init_zone /* инициализирует страницы для диапазона конкретной зоны */
            __init_single_page /* инициализирует страницу */
            set_page_address /* устанавливает виртуальный адрес для страницы */

Пока не совсем про buddy аллокатор, скорее просто про загрузку устройство и инициализацию памяти. Помечу абзац соответствующим заголовком.

Продолжим изыскания, откатившись чуть-чуть назад, в функцию free_area_init_core:

mm/page_alloc.c:    free_area_init_core
            init_currently_empty_zone /* вызывается для каждой зоны. Именно эта функция выставляет zone->initialized = 1 */
            zone_init_free_lists /* заполняет zone->free_area: инициализирует списки, выставляет nr_free = 0 — так для каждого значения из for_each_migratetype_order */

for_each_migratetype_order меня заинтересовал. Во что же этот макрос раскрывается?

#define for_each_migratetype_order(order, type) \
    for (order = 0; order < MAX_ORDER; order++) \
        for (type = 0; type < MIGRATE_TYPES; type++)

Вижу значение MAX_ORDER. Полагаю, речь о группах buddy аллокатора. Взглянет на определение этого макроса:

#ifndef CONFIG_FORCE_MAX_ZONEORDER
#  define MAX_ORDER 11
#else
#  define MAX_ORDER CONFIG_FORCE_MAX_ZONEORDER
#endif

Да, это то, о чём я писал выше. Стандартное значение даже совпало с книжечным[^1]: 11 групп. Добавляем struct free_area из zone->free_area к используемым данным.

[^1]: "An array consisting of eleven elements of type free_area, one element for each group size. The array is stored in the free_area field of the zone descriptor." — Understanding Linux Kernel, p. 313.

Кстати о книжке: она по ядру v2.6. В ней говорится о некой zone_mem_map — поле struct zone, которое является подмножеством mem_map. Однако, я смотрю в v5.10 и здесь нет такого поля. Его выкосили в коммите a0140c1d8563 ("remove zone_mem_map") ещё в v2.6.17. Зато у pgdat есть поле node_mem_map, которое в том же коммите и предложили использовать вместо. Надо бы посмотреть: что это такое вообще.

Вернёмся к стеку вызовов, продолжим с функции free_area_init_node.

mm/page_alloc.c:        free_area_init_node
                alloc_node_mem_map /* заполняет node_mem_map с помощью memblock_alloc_node */
include/linux/memblock.h:    memblock_alloc_node
mm/memblock.c:            memblock_alloc_try_nid
                memblock_alloc_internal
                memblock_alloc_range_nid
                memblock_find_in_range_node 
                ... /* по сути всё упирается в обход memblock и поиска в нём свободного куска памяти */

А сам memblock заполняется на старте ядра. Для arm64 это происходит в функции arm64_memblock_init. По сути, node_mem_map содержит все дескрипторы страниц, которые принадлежат конкретной ноде. По zone_start_pfn можно, собственно, определить какое подмножество всех страниц относится к конкретной зоне.

• pgdat->node_zones содержит массив struct zone по количеству зон. Это дескрипторы зон;
• zone->free_area содержит массив struct free_area по количеству групп buddy аллокатора. Эта структура нужна для учёта свободных страниц, каждая такая структура относится к своей группе.
• zone->zone_start_pfn содержит номер первой страницы для определения диапазона страниц конкретной зоны.