--- tags: [kernel] verified: 2026-09-07 --- # Физическая память: от карты firmware до аллокатора ## Что ядро получает и чего у него ещё нет Первые четыре статьи цикла разбирают виртуальную сторону: зачем трансляция, как устроены таблицы, что лежит в карте ядра, где живут стеки. Всё это предполагает, что физическая память уже есть — что откуда-то берутся кадры под таблицы страниц, под массив дескрипторов, под стек нового потока. Эта статья про то, откуда они берутся, и начинается она с вопроса, который в учебниках обычно проскакивают одной фразой: откуда ядро вообще знает, сколько в машине памяти и какие её куски трогать нельзя. Ответ на этот вопрос ядро не вычисляет, а получает — от прошивки, от загрузчика или из отдельного описания железа. И получает в виде, который почти никогда не годится для прямого использования: карта не отсортирована, не покрывает всё физическое адресное пространство, часть её описывает память, которая ядру не принадлежит, а сама карта лежит в памяти, которую ядро собирается забрать себе. Разбор этого — первая половина статьи. Вторая половина про задачу, на которой спотыкается всякая своя ОС и которая нигде не сформулирована как задача. Чтобы построить таблицы страниц, нужна память. Чтобы выделять память, нужен аллокатор. Чтобы аллокатор заработал, нужна память под его метаданные — и выделить её пока нечем. Из этого состояния выбираются лестницей: каждая ступень использует то, что построила предыдущая, и почти все ступени потом выбрасываются. Лестница разбирается явно, потому что вписать её в готовый код дороже, чем сразу написать код под неё. Граница со статьёй про загрузку проходит по моменту передачи управления: там — что происходит до первой инструкции ядра, здесь — что ядро делает с тем, что ему передали. Граница с наблюдаемым поведением работающей системы (страничный кэш, вытеснение, OOM) проходит по другой оси: там разбирают, что аллокатор делает под давлением, здесь — как он устроен и как поднимается. ## Карта памяти: что в ней есть и чего в ней нет ### Что описывает карта Первое и самое частое заблуждение — что карта памяти описывает физическое адресное пространство. Она его не описывает. Она описывает установленную оперативную память и те диапазоны, которые прошивка объявила своими; всё остальное в ней просто отсутствует, и отсутствие ничего не значит. Спецификация ACPI говорит об этом прямо про оба интерфейса, которыми пользуются на x86. Диапазоны, отведённые устройствам на шине, прошивка не возвращает вовсе — «потому что у ОС есть механизмы для их обнаружения»; стандартные адреса вроде видеопамяти в области `A0000`–`BFFFF` не описываются; регионы, за которыми стоит железо, но обращаться к которым операционной системе не следует, обязаны быть помечены как зарезервированные. UEFI формулирует то же самое ещё резче: прошивка «не возвращает описание для областей адресного пространства, за которыми не стоит физическое оборудование», а «ОС вправе использовать адреса диапазонов, не описанных в карте памяти, по своему усмотрению». Отсюда практическое следствие, которое стоит принять до того, как писать разбор карты. Карта отвечает на два вопроса — «где RAM» и «что из этой RAM занято прошивкой», — и ни на какие другие. Где регистры контроллера, где дыра под PCI, куда можно положить отображение устройства — это выясняется перечислением шин и разбором таблиц описания оборудования, а не чтением карты. Ядро, которое строит окно прямого отображения по формуле «от нуля до максимального адреса из карты», отобразит в него дыры и регистры. ### E820: восемь типов и то, чего в них не хватает Интерфейс `INT 15h, E820h` — старший из живых способов получить карту на x86, и он же самый простой: последовательность вызовов возвращает записи «база, длина, тип». Типы определяет не BIOS, а спецификация ACPI: 1 — доступная RAM, 2 — зарезервировано, 3 — память с таблицами ACPI, которую можно забрать после того, как таблицы прочитаны, 4 — энергонезависимая область ACPI, которую забирать нельзя никогда, 5 — память с обнаруженными ошибками, 6 — выключенная память, 7 — постоянная (энергонезависимая) память, 8 — непринятая память. Всё, чего OSPM не знает, спецификация велит трактовать как тип 2, и это правило важнее самого списка: оно позволяет добавлять типы, не ломая старые ядра. Восьмой тип стоит отдельного слова, потому что он моложе остальных и вводит поведение, которого раньше не было. Непринятая память — это механизм конфиденциальных вычислений: на платформе, где память гостя шифруется, гость обязан явно «принять» диапазон, прежде чем им пользоваться, и до этого момента диапазон в карте помечен восьмым типом. То есть карта перестала быть чисто описательной: одна из её строк требует действия. Про ограничения E820 спецификация тоже честна, хотя главное о них узнаёшь не из неё. Вся нижняя память объявляется обычной — «ОС обязана сама разобраться со стандартными местами вроде таблицы векторов прерываний по адресу нуль», — а области прошивки размазаны по трём местам: ниже мегабайта, около шестнадцати мегабайт и у верхнего края четырёхгигабайтного пространства. Ни упорядоченности записей, ни отсутствия перекрытий спецификация не обещает нигде, и это отсутствие обещания стоит читать буквально. Как оно выглядит на живом железе, записано в комментарии к функции нормализации в Linux: «некоторые раскладки E820 содержат перекрывающиеся записи», и карта заменяется новой, из которой перекрытия убраны, а конфликт типов разрешён в пользу типа с бо́льшим номером — то есть в пользу более ограничительного. Разбор, который не сортирует записи и не сливает перекрытия, работает на одной машине и падает на другой. ### UEFI: две таблицы владения и петля с ключом UEFI устроен иначе, и разница не в формате, а в модели владения. До вызова `ExitBootServices()` картой владеет прошивка: всякий работающий образ обязан просить у неё память вызовами `AllocatePages()` и `AllocatePool()`, и прошивка ведёт карту сама. После вызова владельцем становится загрузчик ОС. Смысл шестнадцати типов `EFI_MEMORY_TYPE` целиком в том, что у них два разных значения — до этого вызова и после. Спецификация приводит две таблицы, и читать надо вторую. `EfiBootServicesCode` и `EfiBootServicesData` до вызова — это код и данные загруженных драйверов прошивки, после — «память, доступная для общего использования»: сервисы загрузки кончились, их код больше не нужен. То же с `EfiLoaderCode` и `EfiLoaderData`, с той оговоркой, что образ, вызвавший `ExitBootServices()`, сам в них исполняется. `EfiConventionalMemory` свободна всегда. `EfiACPIReclaimMemory` держит таблицы ACPI и становится свободной после того, как ACPI разобран. А `EfiRuntimeServicesCode` и `EfiRuntimeServicesData` не освобождаются никогда: сервисы времени исполнения продолжают работать и после передачи управления ядру, их код и данные обязаны сохраниться «в рабочем состоянии и состояниях ACPI S1–S3». `EfiACPIMemoryNVS`, `EfiReservedMemoryType`, `EfiPalCode` — то же самое, память прошивки навсегда. Что бывает, когда об этом забывают, видно по симптому, а не по сообщению об ошибке. Ядро, забравшее себе `EfiRuntimeServicesData`, работает — до первого вызова сервиса времени исполнения, то есть до первого обращения к переменным прошивки, к часам реального времени или до попытки перезагрузиться штатным способом. Отладить это тяжело именно потому, что порча происходит задолго до того, как проявляется, и в диапазоне, который отладчику выглядит обычной кучей. Отдельная тонкость — сам порядок получения карты. `GetMemoryMap()` возвращает вместе с картой ключ, и прошивка меняет ключ при каждом изменении карты; `ExitBootServices()` принимает этот ключ и отвечает `EFI_INVALID_PARAMETER`, если он устарел. Замкнутый круг здесь очевиден: чтобы получить карту, нужен буфер, а выделение буфера меняет карту и обесценивает ключ. Спецификация решает его советом — «размер буфера для следующего вызова следует брать с запасом, поскольку выделение нового буфера может увеличить размер карты» — и рекомендацией звать `GetMemoryMap()` непосредственно перед `ExitBootServices()`, а при отказе повторять оба вызова. Ещё одна ловушка того же рода: размер одной записи карта сообщает отдельным полем `DescriptorSize`, и спецификация требует шагать по массиву именно им, а не `sizeof`, потому что структуру обещано расширять с сохранением совместимости. ### Device tree: описание железа отдельным форматом данных На ARM64 и RISC-V карту чаще получают не от интерфейса, а из данных: загрузчик передаёт ядру двоичное дерево устройств, и память в нём описана так же, как всё остальное железо. Причина, по которой описание оборудования вынесено в отдельный формат данных, ровно та же, по которой в ядре нет таблицы моделей материнских плат: на этих архитектурах нет универсального способа перечислить оборудование опросом, вариантов плат много, они различаются мелочами, и вшивать различия в код ядра означает пересобирать ядро под каждую плату. Узел `/memory` обязателен и состоит из пар «адрес, длина» в свойстве `reg`; диапазонов может быть несколько, хоть в одном узле, хоть в нескольких. Зарезервированные области описаны двумя независимыми механизмами, и учитывать надо оба. Первый — блок резервирования в заголовке самого блоба: массив пар 64-битных чисел, завершённый нулевой парой, унаследованный от Open Firmware и предназначенный для того, что загрузчик обязан защитить от затирания (сам блоб, таблицы IOMMU, код прошивки, который продолжит работать). Второй — узел `/reserved-memory` с потомками, и он богаче: у потомка может быть либо `reg` для статической области, либо `size` с необязательными `alignment` и `alloc-ranges` для области, которую ОС должна выделить сама. Два свойства потомков описывают взаимоисключающие режимы, и различие между ними — это ровно то различие, которое [третья статья цикла](./os-kernel-memory-map.md) разбирает со стороны карты ядра. Свойство `no-map` означает, что ОС «не должна создавать виртуальное отображение области в составе своего обычного отображения системной памяти и не должна допускать спекулятивных обращений к ней». То есть область вырезается из окна прямого отображения — с той самой ценой, которую платят за дробление блочных отображений. В Linux это ровно один вызов: `no-map` превращается в флаг `MEMBLOCK_NOMAP`, а он документирован как «не добавлять в прямое отображение и считать зарезервированным»; дескрипторы таких кадров при этом остаются и помечаются как зарезервированные. Свойство `reusable`, наоборот, разрешает ОС пользоваться областью, пока владеющий ею драйвер не потребует её назад, — и это уже механизм непрерывной памяти под устройства, о котором ниже. Типичный случай `no-map` — область, защищённая аппаратно. На RISC-V прошивка M-режима выгораживает себе диапазон записями PMP и описывает его в дереве; на ARM64 то же делает защищённый мир. Проверка регионов из [первой статьи цикла](./os-address-space-models.md) здесь всплывает как строчка в описании памяти: ядро не может обратиться туда физически, и ему сообщают, чтобы оно не пыталось. Наконец, два формата умеют встречаться на одной машине, и приоритет спецификация проводит прямо: при загрузке через UEFI карта берётся из `GetMemoryMap()`, а узлы `/memory`, если они есть, ОС обязана проигнорировать. Статические области `/reserved-memory` при этом обязаны присутствовать и в карте UEFI — с типом `EfiReservedMemoryType` для областей с `no-map` и `EfiBootServicesData` для остальных, — иначе прошивка отдаст их своему же приложению. ### ACPI: SRAT, SLIT и жизнь без них Разбитая по узлам память описывается уже не картой, а таблицами ACPI, и обе относящиеся к делу таблицы объявлены необязательными. SRAT связывает диапазоны памяти, процессоры, ускорители и порты с доменами близости; спецификация подчёркивает, что ОС читает её только при инициализации, потому что на этом этапе интерпретатор пространства имён ACPI ещё не работает, а привязка нужна уже сейчас. SLIT — матрица относительных расстояний между теми же доменами: диагональ нормирована на 10, недостижимость кодируется значением 255, значения от 0 до 9 зарезервированы. Смысл нормировки в том, что расстояние здесь не физическая величина, а отношение: 21 означает «вдвое дороже локального доступа с небольшим довеском». Что бывает, когда таблиц нет, показывает откат в Linux: `dummy_numa_init()` заводит один узел, покрывающий всю память, печатает «No NUMA configuration found» и, по комментарию в коде, «не имеет права провалиться». Это правильная конструкция, и стоит её перенять: система всегда работает в терминах узлов, просто узел бывает один. Обратный вариант — код, у которого есть ветка «с NUMA» и ветка «без NUMA», — даёт две плохо протестированные реализации вместо одной. ### Готовая карта от загрузчика Разбирать всё перечисленное руками необязательно: карту может отдать загрузчик. Но «отдать карту» у разных протоколов означает настолько разное, что это первое, что стоит выяснить, выбирая протокол. Limine передаёт карту нормализованной, и выигрыш здесь не в экономии кода, а в снятых гарантиях. Протокол обещает, что записи отсортированы по возрастанию базы, что записи типов «свободно» и «возвращаемо загрузчиком» выровнены на 4096 байт и по базе, и по длине, и что они не пересекаются ни с чем. Это ровно те три свойства, которых карта от прошивки не даёт и ради которых пишут собственный проход слияния. Платят за это разрешением типов. Соответствие типов UEFI типам протокола в Limine зафиксировано и одностороннее: `EfiLoaderCode`, `EfiLoaderData`, `EfiBootServicesCode` и `EfiBootServicesData` схлопываются в один тип «возвращаемо загрузчиком», а всё, что не перечислено явно, — в «зарезервировано». Постоянная память, непринятая память и диапазоны, помеченные прошивкой как содержащие ошибки, при загрузке через UEFI приходят к ядру неразличимыми. Часть типов протокол к тому же объявляет иллюстративными: записи про образ, модули и кадровый буфер не годятся как источник адресов, и добывать эти адреса надо отдельными возможностями протокола, а не разбором карты. Multiboot2 не обещает ничего из этого, и распространённое мнение, будто «протокол отдаёт нормализованную карту», к нему не относится вовсе. В описании тега карты памяти нет ни слова о сортировке, слиянии перекрытий и выравнивании; единственная гарантия формата — что размер записи кратен восьми. Занятое из карты тоже не вычтено, и спецификация говорит об этом прямо: «Предоставленная карта гарантированно перечисляет всю обычную RAM, которая должна быть доступна для нормального использования. Этот тип, однако, включает области, занятые ядром, mbi, сегментами и модулями. Ядро обязано позаботиться о том, чтобы не затереть эти области». То есть образ ядра, структура с ответами протокола и загруженные модули лежат внутри записей типа 1 «доступная RAM» и ничем в ней не выделены. Отдельная оговорка добавляет, что на платформах EFI некоторые загрузчики этот тег могут не отдать вообще, если сервисы загрузки не завершены, — то есть карты может не быть. Контраст между двумя протоколами и есть содержательная часть раздела: нормализованность карты — свойство конкретного протокола, а не жанра загрузчиков. Практический вывод неприятный. Multiboot2 через GRUB — самый вероятный первый протокол для своей ОС, и весь проход сортировки, слияния перекрытий и вычитания занятого писать под него придётся ровно тот же, что и для карты от прошивки; сэкономлен будет только опрос интерфейса. Остаётся цена, общая для всех загрузчиков, и под Multiboot2 она выше. Ответы протокола, включая саму карту, лежат в памяти, которую ядро вот-вот заберёт себе, — там же, где стек, на котором оно начинает исполняться, и таблицы страниц, по которым оно работает. Значит порядок жёсткий: скопировать карту к себе, построить свои таблицы, переехать на свой стек — и только потом объявить эту память свободной. У Limine она хотя бы названа своим типом «возвращаемо загрузчиком», то есть предупреждение встроено в саму карту; у Multiboot2 такого типа нет, и структура с ответами сидит в обычной «доступной RAM» без всякой пометки. То же верно и без всякого загрузчика: карта UEFI лежит в памяти сервисов загрузки, то есть в той самой памяти, которую вы после `ExitBootServices()` собираетесь забрать. Ошибка здесь не диагностируется никак: аллокатор просто выдаёт кому-то кадр, в котором ещё лежит список свободных кадров. ## Раскрутка: аллокатор нужен раньше, чем есть чем выделять ### Замкнутый круг целиком Сформулируем задачу полностью, потому что по частям она выглядит решаемой, а целиком — нет. Ядру нужны свои таблицы страниц: те, по которым оно исполняется сейчас, построены загрузчиком или прошивкой, лежат в чужой памяти и покрывают не то, что нужно. Таблица страниц — это выровненный на страницу физический кадр, и его надо откуда-то взять. Взять его можно у аллокатора физических страниц. Аллокатор физических страниц держит дескриптор на каждый кадр в системе — на машине с 64 ГиБ это гигабайт метаданных, — и этот массив тоже надо где-то разместить. Разместить его можно только в физической памяти, которую надо выделить. И обратиться к нему можно только по виртуальному адресу, то есть через таблицы страниц, которых ещё нет. Круг замыкается трижды, и все три раза — по одной и той же причине: на каждом уровне механизм требует ресурса, который производит уровень выше. Выход всегда один и тот же по форме: ввести уровень, который ресурса не требует, потому что ресурс ему выдали статически при сборке. Дальше стройте лестницу. | Ступень | Чем на ней выделяют память | Что она делает возможным | Чего на ней ещё нельзя | После загрузки | | --- | --- | --- | --- | --- | | Основание: карта памяти от прошивки | ничем — выделять ещё нечем, есть только описание того, где память и что из неё чужое | узнать, где оперативная память и что из неё занято прошивкой навсегда | выдать хоть один кадр; и саму карту нельзя объявить свободной, пока она не скопирована к себе | выбрасывается, если не сохранена отдельно | | Нулевая: таблицы от компоновщика | инкремент индекса по пулу, отведённому при сборке; освобождения нет вовсе | построить свои таблицы страниц и дотянуться до памяти, которой нет в чужом отображении | выделить что-либо, кроме самих таблиц: запас задан при сборке и не растёт | выбрасывается вместе с данными инициализации | | Первая: аллокатор диапазонов | найти в списке «что есть» кусок, не пересекающийся со списком «что занято», и вписать его во второй; освободить — вычеркнуть | выделять области любого размера, неся флаги из карты и номер узла; строить линейное отображение | о состоянии отдельного кадра не знает ничего: ни ссылок, ни владельца, ни очередей | выбрасывается, кроме систем, которым исходная карта нужна в работе | | Вторая: дескрипторы кадров и страничный аллокатор | свободные списки по порядкам; сосед вычисляется, а не ищется, и при освобождении блоки склеиваются | счётчик ссылок и флаги на кадр, а с ними разделяемая память, копирование при записи и вытеснение | пользоваться массивом дескрипторов нельзя, пока ранний аллокатор не отдал остаток памяти; непрерывности выше своего потолка не даёт и внешней фрагментации не лечит | остаётся, и дескрипторы — постоянный расход на всю память | | Третья: объектный аллокатор | страницы берёт у ступени ниже и режет на объекты одного типа; свободные — списком внутри, кэш на процессор сверху | структуры ядра в сотни байт, не теряя почти всего кадра на каждой; часть состояния переживает возврат в кэш | запрос крупнее нескольких страниц не обслуживает — тот идёт прямо к ступени ниже | остаётся | Строки идут в порядке подъёма, снизу вверх, и колонка «чего на ней ещё нельзя» — это ответ на вопрос, почему ступени не переставить: то, чего не умеет ступень, умеет ровно следующая за ней. Нумерация в первой колонке сквозная, и дальше по тексту ступени называются этими же номерами. Обязательны при этом только основание и нулевая ступень — разбор карты и способ выдать первый кадр. Всё остальное есть не у всякого ядра: система, отдающая распределение памяти наружу, обходится без старших ступеней вовсе, и в конце статьи это разобрано на примере. ### Ступень нулевая: то, что выделил компоновщик Самый первый кадр памяти выделяет не код, а компоновщик. Никакого другого способа нет: любой код, способный выделить кадр, сам должен где-то лежать и чем-то пользоваться. Три архитектуры дают три разных ответа на вопрос «сколько именно кадров зарезервировать», и различие между ними поучительно. x86-64 резервирует фиксированный пул. В образе лежит массив `early_dynamic_pgts` из `EARLY_DYNAMIC_PAGE_TABLES` страниц — эта константа равна 64, — а рядом целочисленный индекс `next_early_pgt`. Всё раннее построение таблиц берёт страницы из этого пула инкрементом индекса, то есть простейшим bump-аллокатором. Интересно, что происходит при исчерпании пула: не паника, а `reset_early_page_tables()` — очистка корневой таблицы, сброс индекса в ноль, перезапись `CR3` и повтор операции. Очистка при этом неполная, и вторая половина ответа именно в этом: `memset()` берёт на одну запись меньше, чем в таблице есть, а комментарий над функцией говорит, какую именно оставляют, — «стереть все ранние таблицы страниц, кроме карты символов ядра». Сброс законен потому, что ранние отображения создаются по отказу страницы и восстанавливаются тем же путём; но отображение самого ядра обязано уцелеть, иначе следующую инструкцию будет неоткуда взять. Получается аллокатор без операции освобождения, у которого единственный способ вернуть память — обнулить всё разом, кроме того, на чём он стоит сам. ARM64 идёт от противного: не «сколько влезет», а «сколько нужно». В `arch/arm64/include/asm/kernel-pgtable.h` живёт арифметика, которая на этапе препроцессирования считает, сколько страниц таблиц требуется, чтобы покрыть диапазон от начала образа до его конца при выбранном числе уровней трансляции, с поправкой на перемещаемое ядро (оно может лечь так, что заденет две соседние записи верхнего уровня, и тогда на каждом нижнем уровне нужна лишняя страница). Результат — константы `INIT_DIR_SIZE` и `INIT_IDMAP_DIR_SIZE`, а скрипт компоновки просто оставляет столько байт. Показательно, где именно: начальные таблицы тождественного отображения лежат в разделе инициализации, то есть выбрасываются после загрузки вместе со всем остальным одноразовым кодом, а `init_pg_dir` — в области нулевой инициализации сразу за `.bss`. Механика разделов, которые выбрасывают после загрузки, разобрана в [статье про ядро как программу](./os-kernel-as-program.md); здесь важно, что ранние таблицы страниц — её первый и самый ранний потребитель. RISC-V резервирует по одной таблице на уровень — `early_pg_dir`, `early_pmd`, `early_pud`, `early_p4d`, все помеченные как данные инициализации, — и этого хватает, потому что раннее отображение делается большими блоками и глубоко в дерево не спускается. Ни один из трёх вариантов не лучше двух других. Пул с общим индексом гибче и переживает неизвестное заранее число отображений ценой того, что размер пула взят с потолка. Вычисленный размер точен и не тратит ни страницы лишней, но требует, чтобы охват раннего отображения был известен на этапе сборки. Для своей ОС проще начать с пула: посчитать охват вы сможете, когда раскладка перестанет меняться каждый день. ### Ступень первая: аллокатор на списке диапазонов Как только есть чем отобразить память и есть куда положить структуру данных, появляется первый настоящий аллокатор. Он устроен так, как устроил бы его любой, кому нужно выделять память до появления метаданных: карта хранится не как состояние каждого кадра, а как список диапазонов. В Linux это `memblock`, и его устройство стоит разобрать, потому что оно почти целиком продиктовано условиями задачи. Есть два списка диапазонов — `memory` (что вообще есть) и `reserved` (что уже занято), — и выделение состоит в том, чтобы найти в первом кусок, не пересекающийся со вторым, и добавить его во второй. Никакого состояния помимо этих двух списков нет; освобождение — вычёркивание диапазона из второго списка. Каждый диапазон несёт базу, длину, флаги и номер узла NUMA, а флаги — это ровно те свойства, которые сообщила прошивка: `MEMBLOCK_NOMAP` для областей, которые нельзя отображать, `MEMBLOCK_MIRROR` для зеркалированных, `MEMBLOCK_HOTPLUG` для тех, что могут быть извлечены. Массивы диапазонов заведены статически, по 128 записей на список, — и вот здесь снова возникает круг. Когда 128 записей не хватает, массив надо удвоить, а удвоить его можно только выделив память тем же `memblock`. Функция `memblock_double_array()` именно это и делает, с двумя предосторожностями. Первая: пока изменение размера явно не разрешено, она не возвращает ошибку, а паникует — `panic("memblock: cannot resize %s array")`, с объяснением в комментарии рядом: «мы не разрешаем менять размер, пока не известны зарезервированные области памяти, непригодные для выделения». Разница для проектировщика существенная. Неразрешённый рост считается ошибкой в порядке загрузки, а не исчерпанием ресурса, и обрабатывать его вызывающему не предлагают; когда рост уже разрешён, но места не нашлось, та же функция как раз печатает сообщение и возвращает ошибку. Вторая предосторожность: функция получает в аргументах диапазон, который вот-вот будет зарезервирован, чтобы не выделить новый массив поверх него. Обе предосторожности — про порядок, и порядок здесь действительно ломается на практике. В RISC-V разрешение изменять размер пришлось отдельным коммитом перенести на момент, когда готово линейное отображение, и объяснение стоит привести целиком: начальные массивы лежат в образе ядра и доступны через его отображение, а переселённые лежат в обычной памяти и доступны только через линейное — «поэтому изменение размера не должно допускаться, пока линейное отображение не готово. Заметим, что при построении линейного отображения происходят выделения из memblock». Круг тот же самый, только на уровень выше: аллокатор растёт за счёт отображения, которое строится за счёт аллокатора. ### Ступень вторая: переключение и подмена Дальше ранний аллокатор делает то, ради чего он существовал: выделяет память под метаданные кадров, после чего становится не нужен. В Linux переключение выражено одной функцией — `memblock_free_all()`, которая отдаёт все незанятые диапазоны страничному аллокатору; документация формулирует зависимость прямо: массив дескрипторов «непригоден к использованию до вызова `memblock_free_all()`, передающего всю память страничному аллокатору». Тонкость в том, что переключение не мгновенное и затрагивает не только аллокатор страниц. Код, который строит таблицы, продолжает работать всё это время, и источник кадров под таблицы у него меняется дважды. RISC-V сделал эту смену явной и потому читается лучше всех: структура `pt_ops` из указателей на функции переключается тремя вызовами. `pt_ops_set_early()` — «MMU не включён, таблицы выделяются прямо из `early_pmd`/`pud`/`p4d`, и возвращается физический адрес». `pt_ops_set_fixmap()` — кадры берутся у `memblock_phys_alloc()`, а добираются до них через фиксированный слот отображения, потому что окна прямого отображения ещё нет. `pt_ops_set_late()` — «MMU включён и настройка таблиц завершена, начиная с этого момента можно пользоваться обычными функциями выделения страниц». Три реализации одной операции, сменяющие друг друга по мере того, как поднимаются нижние уровни, — это и есть форма ответа на исходную задачу. Не «сначала одно, потом другое», а «одна и та же операция, у которой три реализации, и переключение между ними — часть последовательности загрузки». ### Что выбрасывают и что оставляют Ранний аллокатор — одноразовый механизм, и после загрузки от него избавляются. В Linux его структуры помечены как данные инициализации, и документация говорит: «если архитектура не включила `CONFIG_ARCH_KEEP_MEMBLOCK`, структуры данных memblock будут выброшены после завершения инициализации системы». Оговорка про `CONFIG_ARCH_KEEP_MEMBLOCK` содержательна, и три архитектуры отвечают на неё по-разному. ARM64 оставляет карту всегда — она нужна ему в работающей системе, в частности для `pfn_is_map_memory()`, то есть для ответа на вопрос «стоит ли за этим физическим адресом обычная память», который возникает при каждом отображении устройства. RISC-V оставляет её при включённых ACPI или kexec. x86-64 выбрасывает — кроме сборок с поддержкой доверенных доменов Intel, где она снова понадобилась. Урок отсюда не про Linux. Выброс раннего аллокатора — не догма, а решение о том, нужна ли исходная карта после загрузки, и ответ на этот вопрос меняется от появления одной новой возможности. Это довод хранить карту в отдельной структуре, а не растворять её в состоянии страничного аллокатора: растворённую вернуть будет неоткуда. ### Учебный минимум и где он кончается Для своей ОС лестница сокращается до трёх ступеней, и вот они по порядку. Ступень нулевая — статически выделенные таблицы в образе. Резервируйте пул с запасом и берите из него индексом; ориентир есть — x86-64 обходится шестьюдесятью четырьмя страницами, — а точный расчёт отложите до того, как раскладка устоится. Ступень первая — bump-аллокатор поверх карты. Отсортируйте карту, слейте перекрытия, вычтите из неё занятое (свой образ, блоб дерева устройств, начальный диск, карту, которую вы ещё не скопировали) и выдавайте кадры подряд из первого достаточно большого диапазона. Освобождения нет вовсе, и оно не нужно: на этом этапе всё, что вы выделяете, — таблицы страниц, метаданные и области, живущие до конца. Ступень вторая — дескрипторы кадров и двойственный аллокатор поверх них. Битовая карта — очевидный кандидат на это место, и её надо пропустить, а не пройти. Бит на кадр, поиск свободного — сканирование слов; она добавляет ровно одно, чего не умеет bump: освобождение. Кончается она предсказуемо и по двум причинам сразу. Выделение непрерывного диапазона в ней — линейный поиск подряд идущих нулей, то есть операция, дорожающая с размером памяти и с фрагментацией; и никакой информации о кадре, кроме «занят или свободен», в ней нет, так что ни разделить кадр между двумя процессами, ни вытеснить его, ни сделать копирование при записи вы не сможете. В обе границы вы упрётесь не тогда, когда станет медленно, а тогда, когда впервые захотите отобразить один кадр в два адресных пространства или выдать больше одного кадра за раз. Двойственный аллокатор с дескрипторами не сложнее битовой карты и не имеет ни той, ни другой границы; почему именно — в двух следующих разделах. ## Метаданные на физический кадр ### Что в дескрипторе и что он делает возможным Структура на каждый физический кадр появляется в системе ради одного вопроса: сколько ссылок на этот кадр и откуда. Битовая карта отвечает «одна или ноль», и этого достаточно ровно до того момента, пока кадр принадлежит одному владельцу. Всё, что делает виртуальную память интересной, — общий доступ к кадру. Копирование при записи после порождения процесса: обе таблицы указывают на один кадр, и первая запись обязана его размножить, а для этого надо знать, что ссылок больше одной. Разделяемая память: несколько процессов держат один кадр. Страничный кэш: кадр принадлежит файлу и отображён в неизвестное заранее число процессов. Вытеснение: чтобы забрать кадр, надо найти и снять все его отображения, то есть иметь обратную связь от кадра к таблицам. Ни один из четырёх механизмов не строится на бите. Поэтому дескриптор кадра во всех системах содержит примерно одно и то же: счётчик ссылок, набор флагов состояния, указание на владельца (объект или отображение, которому кадр принадлежит, и смещение внутри него) и место в списках, по которым кадр кочует, — списки свободных, списки очередей вытеснения, очереди на процессор. ### Сколько это стоит Расход считается тривиально и оказывается больше, чем ожидаешь. В Linux на x86-64 `struct page` занимает 64 байта; это не оценка, а число, которым пользуется сама документация ядра, выводя формулу экономии дескрипторов для больших страниц («`sizeof(struct page) / sizeof(pte_t) = 64 / 8 = 8` страниц»). При странице в 4 КиБ это 1,5625 % всей физической памяти — на машине с 64 ГиБ ровно гигабайт, потраченный на описание памяти. Число складывается из восьми байт флагов, пяти машинных слов объединения (тех самых, в которых умещается всё, что зависит от роли кадра), четырёх байт под тип или счётчик отображений, четырёх байт счётчика ссылок и восьми байт учёта по контрольным группам — ровно 64. Без учёта по группам вышло бы 56, но структуру всё равно выровняли бы обратно до 64: x86 требует от неё выравнивания на двойное машинное слово, потому что объектный аллокатор меняет пару соседних полей одной атомарной операцией. Величина линейно зависит от размера страницы, и это один из главных доводов в пользу страниц крупнее четырёх килобайт, разобранных во [второй статье](./os-paging-and-tlb.md): при 16 КиБ те же 64 байта дают уже 0,39 %, вчетверо меньше. Второй способ сократить расход — не описывать каждый кадр отдельно там, где они заведомо однородны. Для больших страниц Linux это делает буквально: у страницы в 2 МиБ 512 дескрипторов занимают 8 кадров, из которых семь заполнены одинаковыми хвостовыми записями, и оптимизация переотображает эти семь кадров на одну общую страницу, доступную только для чтения, а освободившиеся отдаёт аллокатору. Экономия — семь восьмых метаданных всей памяти, отданной под большие страницы. ### Одна структура на все роли `struct page` — учебный пример структуры, в которую за тридцать лет сложили всё. Один и тот же кадр бывает страницей файлового кэша, анонимной страницей, куском slab-объекта, таблицей страниц, буфером сетевого пула, памятью устройства — и у каждой роли свой набор полей. Организовано это объединением: комментарий над структурой описывает пять доступных машинных слов и предупреждает, что нулевой бит первого слова занят признаком хвостовой страницы, поэтому остальные пользователи объединения обязаны его не трогать. Ответ на это — расщепление дескриптора по ролям. В нынешнем дереве уже есть `struct folio` (набор физически и виртуально непрерывных кадров, степень двойки по размеру, выровненный по своему размеру), `struct ptdesc` (кадр, занятый таблицей страниц) и `struct slab`. Все они пока наложены на `struct page`: совпадение полей обеспечивается статическими утверждениями вида `TABLE_MATCH`, а размер — утверждением `sizeof(struct ptdesc) <= sizeof(struct page)`. То есть тип уже разделён, а хранение ещё нет. Дальняя цель этой работы — восьмибайтовый дескриптор памяти вместо шестидесятичетырёхбайтового: в кадре остаётся указатель на настоящий дескриптор нужного типа, а сам дескриптор выделяется по потребности. К дате сверки цель не достигнута, и Мэтью Уилкокс называет её отдалённой; промежуточные результаты (сокращение `struct page` до 32 байт для части типов) упираются в миграцию страниц, которая требует полей в самом кадре. Для автора своей ОС отсюда следует не «подождите, пока сделают», а обратное: разделяйте дескрипторы по ролям с самого начала, пока у вас три роли, а не тридцать. ### FreeBSD: та же задача, другой дескриптор FreeBSD решает ту же задачу структурой `vm_page`, и различия показательны. Общего много: объединение под место в очередях, указатель на объект и смещение в нём, счётчик ссылок, состояние, обновляемое атомарно. Различия три, и все три — в сторону большего размера. Первое: физический адрес кадра хранится в самом дескрипторе полем `phys_addr`, а не выводится из его позиции в массиве. Второе: в дескриптор встроена машинно-зависимая часть `md_page`, а в ней на amd64 и arm64 лежит голова списка отображений этого кадра — то есть обратное отображение хранится прямо в дескрипторе, а не в отдельной структуре. Третье: две битовые карты `valid` и `dirty` описывают состояние кадра с точностью до блока устройства, а не целиком, — «эти поля обязаны поддерживать один бит на каждые `DEV_BSIZE` в странице», то есть восемь бит при странице 4 КиБ и шестьдесят четыре при 32 КиБ. По объявлению на amd64 при странице 4 КиБ набегает 88 байт: числа этого в дереве нет, оно посчитано по полям структуры с учётом выравнивания. Вывод из сравнения простой и полезный: разница в весе дескриптора — это в основном вопрос о том, что вы храните на кадре, а что рядом. Обратное отображение в дескрипторе экономит одно косвенное обращение на горячем пути снятия отображений и стоит по два слова на каждый кадр в машине, включая те, у которых отображений не бывает никогда. Начинать стоит с лёгкого дескриптора, как в Linux: физический адрес выводить из индекса, обратное отображение держать снаружи. Довод не в экономии как таковой, а в том, какая из двух цен известна заранее. Вес дескриптора платится за каждый кадр в машине всегда, считается на этапе проектирования и выражается в процентах от всей памяти; лишнее косвенное обращение платится только на пути снятия отображений, и стоит ли оно двух слов на кадр, станет видно, когда этот путь появится и окажется горячим, — то есть не раньше вытеснения. Встроить обратное отображение в дескриптор потом можно, ничего, кроме самого дескриптора, не трогая; выселить его оттуда потом — значит перебрать всех, кто успел дотянуться до поля напрямую. ### Где лежит массив дескрипторов Дескрипторы надо расположить так, чтобы по номеру кадра получать дескриптор дёшево, а на дырки в физическом пространстве не тратить память. Требования противоречат друг другу, и способов их совместить ровно три. ![Три способа получить дескриптор кадра по его номеру: индексация плоского массива, двухуровневый поиск через таблицу секций и индексация виртуально непрерывного массива; для каждого показано, сколько обращений к памяти стоит преобразование и куда деваются дырки физического адресного пространства](./assets/os-physical-memory-pfn-to-descriptor.svg) Плоский массив — один массив на всю память, индекс равен номеру кадра за вычетом номера первого кадра. Преобразование в обе стороны — арифметика, но дырки оплачиваются полностью: под кадры, которых нет, дескрипторы всё равно заведены и просто не инициализированы. Это годится, пока физическая память более или менее непрерывна, и перестаёт годиться, когда между банками зияют гигабайты. Разреженная модель бьёт физическое пространство на секции фиксированного размера и заводит массив описаний секций; дескриптор находится в два шага — старшие биты номера кадра выбирают секцию, младшие индексируют массив внутри неё. Дырки оплачиваются с точностью до секции, а преобразование дорожает: вместо арифметики — обращение в память и разыменование. Третий вариант объединяет достоинства обоих и стоит того, чтобы понять его целиком. Массив дескрипторов кладут в отдельную область виртуального адресного пространства, и он там виртуально непрерывен: дескриптор кадра лежит по адресу «база области плюс номер кадра, умноженный на размер дескриптора», то есть преобразование снова арифметическое. Но физически этот массив собран из разрозненных кадров, и под дырки физического пространства страницы просто не отображают. Разрежённость переехала из структуры данных в таблицы страниц, которые для того и существуют. В Linux эта модель называется `SPARSEMEM_VMEMMAP`, и на 64-битных архитектурах она умолчание; область под неё — та самая `vmemmap` из карты ядра, разобранной в [третьей статье](./os-kernel-memory-map.md). У этого решения есть цена, которую видно не сразу: массив обязан быть выровнен в виртуальном пространстве согласованно с секциями, и это выравнивание протекает вниз, на раскладку физической памяти. На ARM64 начало физической памяти округляется вниз до величины, которая одновременно годится для блочных отображений линейной карты и для выравнивания области дескрипторов, — и вторая из двух причин записана в коде отдельным комментарием. FreeBSD выбирает между первыми двумя вариантами прямо в параметрах архитектуры: amd64 объявляет `VM_PHYSSEG_DENSE` («физическое адресное пространство плотно заселено»), arm64 и riscv — `VM_PHYSSEG_SPARSE`. То есть развилка та же, а выбор сделан по архитектуре, а не по машине. Для своей ОС порядок такой. Начинайте с плоского массива: он проще всего и на машине без дырок правилен. Переходите на виртуально непрерывный, а не на секционный, как только дырки появятся, — он требует ровно одного, чтобы у вас была своя область виртуальных адресов и умение отображать в неё страницы, а это у вас к тому моменту уже есть. ### Альтернатива: только битовая карта Отказаться от дескрипторов целиком — законное решение для учебной ОС, и стоит понимать, что именно оно покупает и чем оплачено. Покупает оно 1/32768 расхода вместо 1/64 (один бит вместо 64 байт на кадр) и полное отсутствие ступени «выделить метаданные» в лестнице раскрутки: битовая карта сама и есть метаданные, и её можно выделить bump-аллокатором за один приём. Оплачено оно тем, что кадр становится неделимым владением. Нет копирования при записи — `fork` обязан копировать всю память процесса. Нет разделяемой памяти между процессами. Нет страничного кэша, разделяемого отображениями. Нет вытеснения, потому что снять отображения кадра можно, только зная их все. Это не «упрощение на первое время»: это выбор модели, в которой процесс владеет своими кадрами единолично. В такой модели можно написать работающую многозадачную систему, и её даже удобно отлаживать. Но переход от неё к общей памяти — не добавление счётчика, а введение обратного отображения и переписывание всего кода, который освобождает кадры. Если в планах есть `fork` или отображение файлов, дескриптор дешевле завести сразу, пусть даже из двух полей: счётчика и флагов. ## Аллокатор физических страниц ### Почему степени двойки Двойственный аллокатор (buddy) выделяет блоки размером в степень двойки от одного кадра до некоторого потолка, и выбор степеней двойки здесь не про удобство арифметики, а про одну конкретную операцию: найти соседа. Блок порядка `n` начинается по адресу, кратному своему размеру, и его сосед — соседний блок того же порядка, вместе с которым он образует блок порядка `n+1`. Номер соседа получается из номера блока переключением одного бита, а база объединённого блока — обнулением того же бита. Весь механизм освобождения умещается в цикл: ```c while (order < max_order) { unsigned long buddy = pfn ^ (1UL << order); if (!frame_is_free(buddy) || frame_order(buddy) != order) break; list_del(&frame[buddy].link); pfn &= buddy; /* оба блока выровнены, так что И даёт базу пары */ order++; } list_add(&frame[pfn].link, &free_area[order]); ``` Никакого поиска и никакой дополнительной структуры данных: сосед вычисляется, а не ищется, и именно эта возможность и есть причина, по которой размеры — степени двойки. Обратите внимание, чего требует цикл от дескриптора кадра: уметь ответить, свободен ли кадр и какого он порядка. Это первые два поля, ради которых заводят метаданные. Одну вещь этот цикл прячет, и спотыкаются на ней первой. Вычисленный сосед может вообще не существовать: исключающее ИЛИ уводит за верхний край описанной памяти или в дырку физического адресного пространства, и дескриптора там нет. Проверку на это несёт `frame_is_free()`, и написать её надо раньше всего остального — иначе первое же освобождение у края памяти прочитает чужую структуру и склеит блок с тем, чего нет. Потолок — величина, которую полезно знать точно, потому что она определяет максимальный размер непрерывного куска, который аллокатор способен выдать в принципе. В Linux это `MAX_PAGE_ORDER`, по умолчанию равный 10: 2¹⁰ кадров, то есть 4 МиБ при странице 4 КиБ. Здесь стоит быть осторожным с текстами старше 2023 года: до версии 6.4 та же константа называлась `MAX_ORDER`, равнялась 11 и означала не максимальный порядок, а количество порядков, — автор изменения так и написал, что определение «контринтуитивно и породило множество ошибок по всему ядру», а в 6.8 константу ещё и переименовали, чтобы старый код не собирался молча с новым смыслом. FreeBSD задаёт потолок иначе и по другой причине: на amd64 и на arm64 с 4-килобайтной страницей `VM_NFREEORDER` равен 13, то есть максимальный блок — 16 МиБ. Комментарий объясняет мотив, и он не про запросы приложений: 64-байтная строка кэша вмещает не более восьми записей второго уровня, отображающих в сумме 16 МиБ, поэтому, выдавая память крупными кусками, аллокатор уменьшает число различных 16-мегабайтных областей, которыми пользуется объектный аллокатор, и тем сокращает и промахи TLB на двухмегабайтных страницах, и промахи кэша при обходе таблиц, вызванные этими промахами. Потолок здесь выбран из соображений кэша, а не из соображений спроса, — хороший пример того, что число в аллокаторе может быть продиктовано совсем не тем уровнем, на котором оно записано. ### Внешняя фрагментация и почему buddy её не лечит Двойственный аллокатор часто представляют как средство от фрагментации. Это неверно, и понимать, почему именно, важно. Что buddy действительно делает — так это гарантирует, что два свободных соседа одного порядка всегда будут склеены. Чего он не делает — не влияет на то, какие блоки освободят. Достаточно, чтобы в каждом четырёхмегабайтном блоке остался один занятый кадр, и запрос на 4 МиБ не будет удовлетворён при том, что свободно 99,9 % памяти. Внутренняя фрагментация — округление запроса вверх до степени двойки — у buddy есть и не превышает половины выданного блока; внешняя же от него не зависит вовсе, она зависит от того, как долго живут выделенные объекты и вперемешку ли они лежат. Отсюда вырастает механизм, который существует ровно потому, что кому-то нужны непрерывные физические куски, и без этой потребности не понадобился бы никогда. ### Группировка по переносимости и уплотнение Идея в том, чтобы разделить кадры не по размеру, а по тому, можно ли их куда-нибудь передвинуть. Кадр, содержащий страницу файлового кэша или анонимную страницу процесса, переносим: его содержимое можно скопировать в другой кадр и поправить записи в таблицах страниц тех, кто на него ссылается. Кадр, в котором лежит структура ядра, непереносим: на неё указывают обычные указатели, которые никто не отследит. Кадр, занятый освобождаемым кэшем (например, метаданными файловой системы), — промежуточный случай: передвинуть его нельзя, но можно выбросить и потом создать заново. Linux делит по этому признаку не отдельные кадры, а блоки кадров (`pageblock`) и хранит тип блока отдельно от дескрипторов. Размер блока конфигурируется и потому «размером с большую страницу» бывает не всегда: при включённых больших страницах `pageblock_order` — это их порядок, обрезанный сверху отдельной константой, которая по умолчанию равна потолку двойственного аллокатора, а при выключенных — сам этот потолок. На x86-64 в обычной конфигурации получается 2 МиБ, то есть действительно большая страница. Основных типов три — непереносимый, переносимый, освобождаемый, — плюс служебные: блоки высокоприоритетного резерва, блоки области непрерывной памяти, блоки, изолированные на время операции. Смысл разделения в том, чтобы запросы разных типов не перемешивались в одном блоке: пока переносимые кадры лежат отдельно, из любого блока переносимых кадров можно собрать непрерывный кусок. Собирает его уплотнение (compaction), и его устройство — два встречных сканера. Один идёт снизу вверх и собирает занятые переносимые кадры, второй идёт сверху вниз и собирает свободные; содержимое первых переезжает во вторые, и работа кончается, когда сканеры встретились. Kconfig ядра описывает роль механизма без оговорок: «уплотнение — единственный компонент управления памятью, надёжно формирующий непрерывные блоки высокого порядка», а его отсутствие «может приводить к неожиданным срабатываниям OOM-killer на запросах высокого порядка». Запускается уплотнение тремя способами — фоновым потоком на узел, прямо в контексте обратившегося процесса и упреждающе по оценке фрагментированности; развилка между первыми двумя и её цена разобраны во [второй статье](./os-paging-and-tlb.md) со стороны больших страниц. ### Резервирование вместо уплотнения FreeBSD отвечает на ту же задачу иначе, и сравнение двух ответов — самая содержательная часть этого раздела. Вместо того чтобы дефрагментировать память постфактум, FreeBSD резервирует непрерывность заранее. Механизм резервирований описан в исходниках как «спекулятивное выделение больших физических страниц»: при первом обращении к области объекта аллокатор откладывает под неё целую суперстраницу, отдаёт из неё кадры по мере надобности и, если объект действительно вырастет до полного размера, отображает её одной записью. Ключевая фраза комментария — «спекулятивное выделение обеспечивает полностью автоматическое использование суперстраниц: никаких программных указаний не требуется». Уровней резервирования два на arm64 и один на amd64 и riscv, и размеры на arm64 читаются как прямая отсылка ко [второй статье](./os-paging-and-tlb.md): уровень 0 — это 16 кадров, то есть 64 КиБ, ровно та величина, которую даёт бит непрерывности в записи таблицы, а уровень 1 — 32 таких резервирования, то есть 2 МиБ, размер блочного отображения. Аппаратная подсказка о непрерывности и структура аллокатора здесь согласованы намеренно. Фонового уплотнителя как отдельного потока у FreeBSD нет. Утверждение отрицательное, поэтому стоит сказать, чем оно известно: в `sys/vm/vm_pageout.c` нет ни одного вхождения `contig`, `compact` или `defrag`, а страничный демон заводит вызовами `kthread_add()` ровно четыре потока — `vm_pageout_worker`, `vm_pageout_helper`, `vm_pageout_laundry_worker` и `uma_reclaim_worker`, и уплотнения среди них нет. Перемещение запускается по конкретному запросу: `vm_page_reclaim_contig()` «освобождает выделенную непрерывную физическую память, удовлетворяющую заданным условиям, перемещая пользующиеся ею виртуальные страницы», и вызывается он из пути выделения непрерывной памяти, когда прямая попытка не удалась. Вердикт для своей ОС здесь однозначный, и он в пользу резервирования. Уплотнение — дорогой механизм: ему нужна миграция страниц, а миграции нужно обратное отображение, изоляция блоков и умение атомарно подменить кадр под работающими процессами. Резервирование требует только одного: чтобы аллокатор при первом выделении в новой области брал крупный кусок и отдавал из него. Оно не даёт гарантии — если память фрагментирована, резервировать не из чего, — но гарантии не даёт и уплотнение. Начинайте с резервирования; уплотнение добавляйте, когда появится потребитель, которому непрерывность нужна не для скорости, а для правильности. ### Горячий путь Последняя деталь страничного аллокатора, без которой он не масштабируется: на каждом процессоре стоит свой небольшой список свободных кадров, и подавляющее большинство выделений и освобождений обслуживается из него, не трогая общую структуру и её замок. Пополняется и опустошается он пачками. Документация ядра называет такие списки «жизненно важным механизмом» и описывает выделение как двухступенчатое — сначала список процессора, потом двойственный аллокатор. Это тот же приём, который через раздел появится у объектного аллокатора под именем магазинов, и это не совпадение: задача одна и та же — снять замок с горячего пути ценой того, что часть памяти оседает в кэшах процессоров. ### Вердикт по страничному аллокатору Для своей ОС порядок такой. Двойственный аллокатор — сразу за bump'ом, минуя битовую карту: он даёт склейку соседей бесплатно, а склейка — единственное, что вообще спасает от постепенного измельчания памяти. Битовая карта на этом месте выглядит промежуточной ступенью, но ею не является: освобождение она добавляет, склейки не даёт, и переписывать её придётся на первом же запросе больше чем на один кадр. Списки свободных по размерам (без склейки) выглядят проще, но проигрывают ровно в этом: освобождённые блоки в них не сливаются, и запрос на крупный кусок будет отвергаться при формально свободной памяти. Потолок порядка ставьте не меньше того, что нужно самому крупному вашему выделению. Стоит проверить это заранее: например, стек ядра фиксированного размера, разобранный в [четвёртой статье](./os-stacks.md), — это непрерывное выделение порядка 2 или 3, и оно случается при создании каждого потока, то есть регулярно и на возможно фрагментированной памяти. Группировку по переносимости закладывайте позже, но закладывайте место под неё сразу: тип блока — это два-три бита, которые надо где-то хранить, и вводить хранилище задним числом дороже, чем зарезервировать поле. ## Объектный аллокатор поверх страничного ### Что не так со страницей как единицей Страничный аллокатор оперирует кадрами, а ядро — структурами в сотни байт, которых у него десятки тысяч. Выдавать под каждую по странице означает выбросить больше девяти десятых памяти. Класть их вперемешку в общую кучу означает получить фрагментацию худшего рода — не блочную, которую лечит склейка, а разноразмерную, которую не лечит ничто. Граница между двумя аллокаторами проводится по размеру, и в Linux она проходит по двум страницам: запросы до `KMALLOC_MAX_CACHE_SIZE`, равного двум страницам, обслуживаются кэшами объектов, а всё, что крупнее, идёт прямо к страничному аллокатору. Логика деления понятна: объект в две страницы уже почти не теряет на округлении, и заводить ради него отдельный механизм незачем. ### Slab: кэш типа и конструктор Ответ, ставший общим для всех Unix-подобных систем, дал Джефф Бонвик в 1994 году, и главная его идея не та, которую обычно называют. Обычно называют раскладку: страница (или несколько подряд) делится на объекты фиксированного размера, свободные связываются в список, и выделение — это снятие головы списка. Это верно и это дёшево, но так умеет любой аллокатор с разделением по размерам. Существеннее вторая идея — кэш на тип, а не на размер, и конструктор. Объект, возвращённый в кэш, не разрушается полностью: части его состояния, которые не зависят от конкретного использования — инициализированные замки, вложенные списки, счётчики в начальном положении, — остаются такими, какими были. Конструктор вызывается один раз при заселении slab'а, а не при каждом выделении. Заголовок статьи это и говорит: «аллокатор с кэшированием объектов», а не «аллокатор с разделением по размерам». Экономия здесь не на поиске свободного места, а на повторной инициализации, и она тем больше, чем сложнее объект. Указатель на конструктор жив в Linux до сих пор — поле `ctor` в описании кэша, — хотя пользуются им немногие. ### Магазины и то, как они вернулись Второй работой Бонвик и Адамс в 2001 году добавили к slab'у механизм магазинов: на каждом процессоре лежит небольшой массив готовых объектов, выделение снимает объект оттуда, освобождение кладёт обратно, и общая структура с её замком трогается только когда магазин пуст или полон. Дальше история в Linux сложилась так, что общеизвестное про неё сегодня неверно, и это стоит отметить прямо. В ядре долго сосуществовали три реализации: SLAB (близкая к работам Бонвика, с очередями на процессор), SLUB (написанная в 2007-м как более простая и масштабируемая, без очередей — вместо них на каждом процессоре держался «активный» slab) и SLOB (минимальная, для крошечных систем). SLOB удалили в 6.4, SLAB — в 6.8, после чего `CONFIG_SLUB` стал безусловным, а вместо SLOB появился режим `SLUB_TINY` «для самых маленьких систем, которые пользовались SLOB», с рекомендацией не применять его при памяти больше 16 МиБ. А затем SLUB отрастил магазины обратно. Механизм называется sheaves и появился в 6.18 как выбираемый на кэш: ёмкость массива задавал вызывающий, а ноль означал «без sheaves». Проверяется это тем же способом, что и удаление SLOB и SLAB, — содержимым файла в тегах: в `mm/slub.c` версии 6.17 слова `sheaf` нет ни разу, в 6.18 оно встречается больше трёхсот раз. Схему с активным slab'ом на процессоре sheaves вытеснили не сразу, а в 7.0: `kmem_cache_cpu` держится и в 6.18, и в 6.19 и исчезает только там, и в той же версии переписан заголовок файла: SLUB описан там как «аллокатор с малозатратными массивами кэширования на процессор». Комментарий поясняет устройство: «SLUB заводит на каждом процессоре два массива объектов, называемых sheaves, для кэширования выделений и освобождений, и общий на узел NUMA barn для балансировки между процессорами; выделения и освобождения обслуживаются главным образом из этих массивов». Ёмкость массива теперь считается по размеру объекта — 60 объектов для мелких, 4 для тех, что от страницы и больше, — и округляется так, чтобы сам массив попадал ровно в размерный класс `kmalloc`. То есть утверждение «SLUB отказался от очередей на процессор, и в этом его отличие от SLAB» было верным пятнадцать лет и перестало быть верным. Общий вывод для проектировщика важнее частности: снятие замка с горячего пути кэшированием на процессоре — не деталь реализации, а требование, к которому конструкция возвращается, из скольких бы соображений простоты от него ни отказывались. ### UMA: четыре ступени вместо трёх FreeBSD реализует те же идеи в UMA, и её терминология разделяет то, что в Linux слито в одно понятие. Зона описывает тип выделения и владеет кэшами на процессор. Keg описывает раскладку — размер объекта, выравнивание, источник страниц — и владеет slab'ами. Одна зона может опираться на несколько kegs, и наоборот; в подавляющем большинстве случаев соответствие взаимно однозначное, а разделение нужно ради случаев вроде выделения сетевых буферов. Порядок обслуживания записан в заголовке `uma_int.h` четырьмя ступенями: кэш процессора, кэш вёдер на домен памяти, slab из любого из kegs, поставщик страниц. Заметна вторая ступень: вёдра сгруппированы по доменам NUMA, то есть локальность узла встроена в объектный аллокатор, а не надстроена над ним. Тут же оговорено ограничение, которое из локальности следует: строгого соблюдения нет, потому что освобождение может случиться на любом процессоре и объект вернётся в его локальный кэш независимо от того, откуда он родом. Отдельно стоит правило размещения заголовка slab'а: обычно он лежит в конце той же страницы, но «для размеров объектов, при которых потери превысили бы 10 % памяти, заголовок выносится наружу», если это увеличивает число объектов на slab. Худший случай назван честно: объекты чуть больше половины страницы дают почти 50 % потерь, и от них не спасает ничто, кроме динамического размера slab'а. ### seL4: аллокатора в ядре нет Третий ответ на вопрос об объектном аллокаторе — не иметь его. seL4 формулирует это как проектное решение: «микроядро seL4 не выделяет память под объекты ядра динамически». Вместо этого при загрузке ядро резервирует память под себя — код, данные, единственный стек — и передаёт всю оставшуюся память начальному пользовательскому потоку в виде мандатов на нетипизированную память. Дальше пользовательский код превращает нетипизированную память в объекты ядра операцией `seL4_Untyped_Retype()`, и ядро только проверяет права и учитывает происхождение. Устройство самой операции стоит того, чтобы его увидеть: для каждой области ядро хранит «отметку уровня, показывающую, сколько области уже было выделено ранее»; новые объекты создаются на уровне отметки, отметка растёт, и сбрасывается она только тогда, когда удалены все мандаты на ранее созданные в этой области объекты. Это ровно тот bump-аллокатор, с которого начинается всякая раскрутка, — только поднятый до уровня системного интерфейса и снабжённый учётом ссылок, который решает, когда его можно перезапустить. Следствие сформулировано в том же разделе: «произвольных ограничений на ресурсы в ядре нет, кроме продиктованных оборудованием, и потому многие атаки на отказ в обслуживании через исчерпание ресурсов исключены». Цена — вся политика распределения памяти переезжает в пользовательское пространство, и её кто-то должен написать. ### Что нужно в учебной ОС Объектный аллокатор — не первое, что стоит писать, и не последнее. Пока структур ядра три вида, обходитесь без него: заведите по списку свободных объектов на тип поверх страничного аллокатора, это двадцать строк на тип и оно правильно работает. Общий кэш объектов заводите тогда, когда типов станет с десяток, — примерно на этом рубеже ручные списки начинают дублировать друг друга. Начинайте с одного уровня: кэш с фиксированным размером объекта, slab в одну страницу, список свободных внутри slab'а, три списка slab'ов (полный, частичный, пустой). Конструктор добавляйте только если у вас есть объект, инициализация которого действительно дорога, — обычно такой один, и это структура с замком и вложенными списками. Кэши на процессор откладывайте до появления второго процессора, но закладывайте под них место в описании кэша, потому что вставлять уровень в готовый путь выделения неприятно. Отдельно: `kmalloc`-подобный интерфейс с размерными классами делайте поверх кэшей объектов, а не рядом. Это один набор кэшей на степени двойки и одна таблица перевода размера в класс; заводить для него отдельный механизм незачем. ## Зоны, узлы и непрерывность ### Зона — это свойство устройства, а не памяти Разбиение физической памяти на зоны часто читают как свойство самой памяти. Оно им не является: зона существует потому, что какие-то устройства в машине не умеют адресовать всю память, а граница зоны — это предел адресации самого слабого из них. Дальше начинается разница между архитектурами, и она полезная. На x86-64 обе границы — константы, зашитые в заголовки, и обе исторические: 16 МиБ («зона ISA DMA») и 4 ГиБ («зона для сломанного оборудования PCI/AGP, ведущего передачу»). Комментарии в `arch/x86/include/asm/dma.h` названы именно так, и это честно: оба числа описывают оборудование, а не архитектуру. На ARM64 нижняя граница не константа, а вычисляется при загрузке — из описания оборудования. Ядро спрашивает у дерева устройств максимальный адрес, доступный устройствам на шине (`of_dma_get_max_cpu_address()`), и то же самое у таблицы IORT в случае ACPI, берёт минимум и получает границу зоны. Комментарий рядом называет мотивирующий пример: «по умолчанию зона DMA покрывает 32-битно адресуемую память, если платформа не накладывает ограничения — например, 30 бит на Raspberry Pi 4». Более того, если ограничение оказалось строже 32 бит, вторая зона занимает остаток 32-битного диапазона, а если нет — остаётся пустой. На RISC-V нижней зоны нет вовсе: ядро заводит только зону 32-битной адресации и обычную. Шестнадцатимегабайтный предел — наследие шины ISA, о чём прямо сказано в комментарии на x86, и на архитектуре, которая эту шину не наследовала, описывать такой зоной нечего. FreeBSD решает ту же задачу не зонами, а свободными списками, и различие в числах говорит само за себя: три списка на amd64 (обычный, до 4 ГиБ, до 16 МиБ), два на arm64 (обычный и до 4 ГиБ), один на riscv. То есть систем две, а вывод один: количество классов памяти по адресуемости — это функция от парка устройств архитектуры, и заранее оно не известно. Для своей ОС отсюда следует конкретное требование к интерфейсу, а не к структурам. Выделение кадра должно с самого начала принимать ограничение на физический адрес — «дай мне кадр с адресом ниже такого-то», — даже если у вас пока одна зона и ограничение всегда выполнено. Классы по адресуемости добавляются потом легко; переписать все вызовы выделения — нет. Со стороны устройств та же граница выглядит как разрядность адреса контроллера и его способность работать с рассеянными списками; про это — [статья про интерфейсы накопителей](./storage-interfaces.md). ### NUMA: узлы и то, что нельзя заложить неправильно Неоднородный доступ к памяти вносит в аллокатор одно понятие — узел, — и одно правило: выделять по возможности там, где исполняется тот, кто просит. Структурно это выражается в том, что почти всё состояние аллокатора становится массивом по узлам: свои списки свободных, свои пороги свободной памяти, свои потоки вытеснения и уплотнения, свой список зон в порядке предпочтения. Последнее — важная деталь: список зон описывает не только зоны своего узла, но и чужие, и порядок в нём и есть политика отката, когда локальная память кончилась. Автору своей ОС на старте это не нужно, и на однопроцессорной или односокетной машине не понадобится никогда. Но одно решение принять придётся сразу, потому что переделывать его дорого: узел должен быть параметром выделения, а не глобальной переменной. Иными словами, функция выделения кадра принимает «предпочтительный узел» с самого начала — пусть он всегда нулевой и пусть реализация его игнорирует. Всё остальное — расстояния, политики, миграция между узлами — надстраивается потом. Ровно так и устроен откат в Linux: один поддельный узел на всю память, и код выше об этом не знает. ### CMA: непрерывность, купленная заранее Остаётся случай, ради которого приходится заводить отдельный механизм: устройству нужен непрерывный физический буфер в десятки мегабайт, а взять его негде — уплотнение не гарантирует, потолок двойственного аллокатора ниже запроса, и запрос приходит не при загрузке, а когда система уже поработала. Ответ — купить непрерывность заранее и не дать ей пропасть. Область резервируется при загрузке (в дереве устройств это узел `/reserved-memory` со свойством `reusable`), и её блоки помечаются особым типом переносимости, из которого следует правило: в этой области размещаются только переносимые выделения. Пока устройство не просит, областью пользуется страничный кэш и анонимная память; когда просит — содержимое мигрирует наружу, и область освобождается целиком. Резервирование при этом не пропадает даром, чем и отличается от простого «отложить кусок памяти под драйвер». Цена у механизма конкретная и проявляется далеко от него. Кадры в такой области нельзя закрепить надолго: закрепление означает, что мигрировать их уже нельзя, а без миграции гарантия рушится. Заголовок в исходниках Linux формулирует правило одной строкой — «блоки типа CMA и зоны переносимой памяти не допускают долгого закрепления кадров», — и функция быстрого пути закрепления в `gup.c` при таком запросе просто отказывается работать, отправляя вызывающего на медленный путь, который сначала перенесёт кадры в другое место. То есть запрос «закрепи мне эту страницу пользовательской памяти надолго» может оказаться операцией с копированием, и виноват в этом механизм, о котором вызывающий не знает. Для своей ОС вывод простой: если в вашей системе есть устройство, требующее непрерывного буфера, резервируйте под него область при загрузке и не пытайтесь решить задачу общим аллокатором. Разрешать использовать эту область под переносимые выделения — вторая по счёту задача, и она требует миграции; до неё область может просто простаивать. ## Как это сделано в трёх системах | | Linux | FreeBSD | seL4 | | --- | --- | --- | --- | | Ранний аллокатор | список диапазонов (`memblock`), выбрасывается, если архитектура не попросила обратного | вырезание из массива доступных диапазонов в `vm_page_startup()`; число кадров считается с учётом веса дескриптора | резерв под ядро при загрузке, остальное — пользователю | | Дескриптор кадра | одна структура на все роли, 64 байта на x86-64; расщепление по ролям идёт, хранение общее | своя структура с встроенной машинно-зависимой частью и обратным отображением | дескрипторов нет: тип кадра выражен мандатом | | Размещение дескрипторов | плоский массив или разреженная модель; на 64 битах умолчание — виртуально непрерывный массив | выбор между плотной и разреженной моделью задан архитектурой | не применимо | | Страничный аллокатор | двойственный, потолок 4 МиБ, списки на процессор | двойственный, потолок 16 МиБ на amd64, резервирования суперстраниц | нет: `Retype` с отметкой уровня | | Непрерывность высокого порядка | группировка по переносимости плюс уплотнение двумя сканерами | спекулятивное резервирование вперёд, перемещение по запросу | забота пользовательского кода | | Объектный аллокатор | единственный, с массивами на процессор и общим складом на узел | зона, keg, ведро, slab; вёдра по доменам памяти | нет | | Классы по адресуемости | зоны; границы константны на x86-64 и вычисляются из прошивки на ARM64 | свободные списки: три, два или один по архитектуре | нет; деление нетипизированной памяти на обычную и память устройств — про права, а не про адресуемость | Из таблицы стоит унести две вещи. Первая: расхождение между Linux и FreeBSD проходит не по качеству, а по тому, где добывается непрерывность, — постфактум уплотнением или авансом резервированием, — и оба ответа работают. Вторая: seL4 показывает, что вся вторая половина статьи (страничный аллокатор, объектный аллокатор, зоны, политика) — не обязательная часть ядра, а следствие решения держать распределение памяти внутри него. Обязательны только две вещи: разбор карты и способ выдать первый кадр. ## Вердикт для своей ОС Порядок ниже — это и порядок работы, и порядок необратимости. Карту разбирайте в свою структуру и никогда не работайте с чужой на месте. Отсортируйте, слейте перекрытия, вычтите занятое, скопируйте к себе — и только потом объявляйте свободной память, в которой она лежала. Это единственный шаг, ошибка в котором не диагностируется вообще: следствием будет порча случайной структуры через несколько секунд после загрузки. Типы карты сохраняйте, а не схлопывайте в «свободно/занято». Разница между «занято прошивкой навсегда», «освободится после разбора таблиц» и «нельзя отображать» вам понадобится, а восстановить её будет неоткуда. Флаг «не отображать» проведите до построения окна прямого отображения — иначе получите отображение на адреса, которых нет, и спекулятивное обращение туда в самый неудобный момент. Ранний аллокатор пишите на диапазонах, а не на битах. Список из сотни записей «база, длина, флаги» — это тридцать строк кода, он работает до появления любых метаданных, и в нём естественно живут те самые флаги из карты. Битовая карта на этом этапе требует, чтобы вы заранее знали объём памяти, и не умеет хранить ничего, кроме занятости. Ступени раскрутки делайте явными, а переключение между ними — одним местом в коде. Указатели на функции, как в `pt_ops`, лучше цепочки проверок «а мы уже включили MMU?»: проверка размазывается по коду и однажды окажется не в том порядке. Дескриптор кадра заводите с самого начала, даже если в нём два поля. Не потому что он нужен сразу, а потому что все места, где вы освобождаете кадр, придётся переписать, когда вы его заведёте, а мест этих будет много. Двойственный аллокатор пишите сразу за bump'ом, минуя битовую карту. Он не сложнее — вся разница в вычислении соседа через исключающее ИЛИ и в цикле склейки, — а измельчания памяти не допускает. Ограничение на физический адрес и предпочтительный узел закладывайте в сигнатуру выделения немедленно, даже если оба параметра пока игнорируются. Это единственные два параметра, добавление которых потом означает правку каждого вызова в дереве. Объектный аллокатор и всё, что связано с непрерывностью высокого порядка, откладывайте до появления потребителя. У них есть общее свойство: они не меняют интерфейсов, которые вы уже написали, и потому их добавление дёшево в любой момент. Дальше — загрузка, где разбирается, что происходит до первой инструкции ядра и как включают трансляцию, и структура ядра, где выясняется, что модель ядра меняет и половину этой статьи тоже: у микроядра аллокатор в ядре может не понадобиться вовсе. Состав и порядок — в [плане цикла](./os-knowledge-base-plan.md). ## Источники - [Unified Extensible Firmware Interface Specification 2.11, раздел 7 «Services — Boot Services»](https://uefi.org/specs/UEFI/2.11/07_Services_Boot_Services.html) — перечисление `EFI_MEMORY_TYPE`, две таблицы значения типов до и после `ExitBootServices()`, владение картой прошивкой до вызова, ключ карты и требование его актуальности, совет брать буфер с запасом и использовать `DescriptorSize`, оговорка про области, не описанные в карте - [Advanced Configuration and Power Interface Specification 6.6, раздел 15 «System Address Map Interfaces»](https://uefi.org/specs/ACPI/6.6/15_System_Address_Map_Interfaces.html) — таблица типов диапазонов E820 (включая тип 8, непринятую память), правило трактовать неизвестные типы как зарезервированные, ограничения E820 и UEFI: диапазоны устройств не возвращаются, стандартные адреса ПК не описываются, области прошивки в трёх местах - [Advanced Configuration and Power Interface Specification 6.6, раздел 5 «ACPI Software Programming Model»](https://uefi.org/specs/ACPI/6.6/05_ACPI_Software_Programming_Model.html) — SRAT и SLIT как необязательные таблицы, чтение SRAT только при инициализации, нормировка диагонали SLIT на 10, значение 255 для недостижимости и резерв 0–9 - [Devicetree Specification, глава 3 «Device Nodes»](https://devicetree-specification.readthedocs.io/en/latest/chapter3-devicenodes.html) — узел `/memory`, узел `/reserved-memory` и его потомки, свойства `no-map` и `reusable` и их взаимоисключающесть, `size`/`alignment`/`alloc-ranges` для динамических областей, приоритет карты UEFI над узлами `/memory` и требование дублировать статические резервы в карте UEFI - [Devicetree Specification, глава 5 «Flattened Devicetree Format»](https://devicetree-specification.readthedocs.io/en/latest/chapter5-flattened-format.html) — блок резервирования памяти в заголовке блоба, формат `fdt_reserve_entry` и нулевая завершающая запись - [Boot time memory management — документация ядра Linux](https://docs.kernel.org/core-api/boot-time-mm.html) — устройство `memblock`, три типа коллекций, перечисление флагов диапазонов, включая `MEMBLOCK_NOMAP`, освобождение памяти страничному аллокатору в `mem_init()`, выброс структур при отсутствии `CONFIG_ARCH_KEEP_MEMBLOCK` - [Physical Memory Model — документация ядра Linux](https://docs.kernel.org/mm/memory-model.html) — плоская и разреженная модели, две разновидности разреженной, устройство виртуально непрерывного массива дескрипторов, непригодность массива до вызова `memblock_free_all()` - [Physical Memory — документация ядра Linux](https://docs.kernel.org/mm/physical_memory.html) — узлы, зоны и их назначение, списки зон как политика отката, списки свободных страниц на процессор и двухступенчатое выделение - [A vmemmap diet for HugeTLB and Device DAX — документация ядра Linux](https://docs.kernel.org/mm/vmemmap_dedup.html) — вывод размера метаданных большой страницы, где `sizeof(struct page)` равен 64, и схема переотображения семи из восьми кадров дескрипторов на общую страницу - [Jeff Bonwick. The Slab Allocator: An Object-Caching Kernel Memory Allocator, USENIX Summer 1994](https://www.usenix.org/conference/usenix-summer-1994-technical-conference/slab-allocator-object-caching-kernel) — кэш на тип объекта, конструктор и сохранение состояния между использованиями - [Jeff Bonwick, Jonathan Adams. Magazines and Vmem: Extending the Slab Allocator to Many CPUs and Arbitrary Resources, USENIX ATC 2001](https://www.usenix.org/conference/2001-usenix-annual-technical-conference/magazines-and-vmem-extending-slab-allocator-many) — слой магазинов: кэш готовых объектов на каждом процессоре и линейное масштабирование по числу процессоров - [seL4 Reference Manual](https://sel4.systems/Info/Docs/seL4-manual-latest.pdf) — раздел 2.4: ядро не выделяет память под объекты динамически, передача остатка памяти начальному потоку мандатами на нетипизированную память, отметка уровня в `seL4_Untyped_Retype()` и её сброс после отзыва всех потомков, разделение на обычную память и память устройств - [Multiboot2 Specification version 2.0, раздел 3.6.8 «Memory map»](https://www.gnu.org/software/grub/manual/multiboot2/multiboot.html#Memory-map) — структура тега карты, кратность `entry_size` восьми как единственная гарантия формата, отсутствие каких-либо обещаний о сортировке, слиянии и выравнивании, включение областей ядра, структуры информации и модулей в тип «доступная RAM», оговорка о том, что на платформах EFI при незавершённых сервисах загрузки тега может не быть - [Limine Boot Protocol](https://github.com/Limine-Bootloader/limine-protocol/blob/trunk/PROTOCOL.md) — типы записей карты, гарантии сортировки, выравнивания и непересечения для свободных и возвращаемых записей, иллюстративный статус остальных типов, соответствие типов UEFI типам протокола, размещение ответов протокола в возвращаемой памяти - Исходники ядра Linux (выверялось на mainline 7.3-rc2; стабильной на дату сверки была 7.2.3): [`include/linux/mm_types.h`](https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/tree/include/linux/mm_types.h) — поля `struct page`, комментарий о пяти доступных словах, `struct folio`, `struct ptdesc` и статические утверждения `TABLE_MATCH`; [`include/linux/mmzone.h`](https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/tree/include/linux/mmzone.h) — `MAX_PAGE_ORDER` и его значение по умолчанию, перечисление типов переносимости, `PAGE_BLOCK_MAX_ORDER` по умолчанию равный `MAX_PAGE_ORDER`; [`include/linux/pageblock-flags.h`](https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/tree/include/linux/pageblock-flags.h) — вывод `pageblock_order` из порядка большой страницы с обрезкой сверху и его значение при выключенных больших страницах; [`mm/memblock.c`](https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/tree/mm/memblock.c) — 128 записей в каждом статическом массиве, `memblock_double_array()`, паника при росте до того, как он разрешён, и ошибка при нехватке места, `memblock_mark_nomap()` и его описание, `memblock_free_all()`; [`mm/slub.c`](https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/tree/mm/slub.c) — описание sheaves и склада на узел, расчёт ёмкости массива по размеру объекта; [`mm/Kconfig`](https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/tree/mm/Kconfig) — безусловный `SLUB`, назначение `SLUB_TINY`, формулировка про уплотнение как единственный надёжный источник блоков высокого порядка, описание CMA, включение `SPARSEMEM_VMEMMAP` по умолчанию там, где архитектура его разрешила; [`arch/x86/Kconfig`](https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/tree/arch/x86/Kconfig), [`arch/arm64/Kconfig`](https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/tree/arch/arm64/Kconfig) и [`arch/riscv/Kconfig`](https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/tree/arch/riscv/Kconfig) — `SPARSEMEM_VMEMMAP_ENABLE` на всех трёх при 64 битах и разная судьба `ARCH_KEEP_MEMBLOCK`: безусловно на ARM64, по условию на RISC-V, только ради поддержки доверенных доменов Intel на x86; [`mm/compaction.c`](https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/tree/mm/compaction.c) — встречные сканеры и условие остановки; [`include/linux/mm.h`](https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/tree/include/linux/mm.h) — `folio_is_longterm_pinnable()` и запрет долгого закрепления в областях CMA и переносимой зоне; [`include/linux/slab.h`](https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/tree/include/linux/slab.h) — граница между кэшами объектов и страничным аллокатором в две страницы; [`arch/x86/kernel/head64.c`](https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/tree/arch/x86/kernel/head64.c) и [`arch/x86/kernel/head_64.S`](https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/tree/arch/x86/kernel/head_64.S) — пул `early_dynamic_pgts`, индекс `next_early_pgt` и сброс ранних таблиц при исчерпании пула с сохранением карты символов ядра; [`arch/x86/include/asm/dma.h`](https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/tree/arch/x86/include/asm/dma.h) — константы 16 МиБ и 4 ГиБ с их комментариями; [`arch/x86/kernel/e820.c`](https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/tree/arch/x86/kernel/e820.c) — комментарий к `e820__update_table()` про перекрывающиеся записи в реальных раскладках и разрешение конфликта типов в пользу большего номера; [`arch/x86/mm/numa.c`](https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/tree/arch/x86/mm/numa.c) — `dummy_numa_init()` и требование не проваливаться; [`arch/arm64/include/asm/kernel-pgtable.h`](https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/tree/arch/arm64/include/asm/kernel-pgtable.h) и [`arch/arm64/kernel/vmlinux.lds.S`](https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/tree/arch/arm64/kernel/vmlinux.lds.S) — расчёт `INIT_DIR_SIZE` и `INIT_IDMAP_DIR_SIZE` и их резервирование скриптом компоновки; [`arch/arm64/mm/init.c`](https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/tree/arch/arm64/mm/init.c) — вычисление границы зоны из дерева устройств и IORT, комментарий про 30 бит на Raspberry Pi 4, выравнивание начала физической памяти под блочные отображения и под область дескрипторов; [`arch/riscv/mm/init.c`](https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/tree/arch/riscv/mm/init.c) — статические ранние таблицы в данных инициализации, три набора `pt_ops` и комментарии к ним, отсутствие нижней зоны; [`drivers/of/of_reserved_mem.c`](https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/tree/drivers/of/of_reserved_mem.c) — превращение `no-map` в `memblock_mark_nomap()` - Коммиты ядра Linux: [`23baf831a32c`](https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/commit/?id=23baf831a32c) — переопределение `MAX_ORDER` включающим (v6.4) с формулировкой про контринтуитивность прежнего определения; [`5e0a760b4441`](https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/commit/?id=5e0a760b4441) — переименование в `MAX_PAGE_ORDER` (v6.8), чтобы привлечь внимание к смене смысла; [`85fadc0d0411`](https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/commit/?id=85fadc0d0411) — перенос `memblock_allow_resize()` на RISC-V за момент готовности линейного отображения, с объяснением про два разных отображения начальных и переселённых массивов; [`6630e950d532`](https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/commit/?id=6630e950d532) и [`16a1d968358a`](https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/commit/?id=16a1d968358a) — удаление SLOB и SLAB; принадлежность версиям проверялась наличием `mm/slob.c` и `mm/slab.c` в тегах v6.3, v6.4, v6.7 и v6.8 (SLOB исчезает в 6.4, SLAB — в 6.8); тем же способом по содержимому `mm/slub.c` в тегах v6.17, v6.18, v6.19 и v7.0 датированы sheaves — слово `sheaf` появляется в 6.18, `kmem_cache_cpu` исчезает в 7.0, и там же переписан заголовок файла - Исходники FreeBSD (ветка `main` на дату сверки): [`sys/vm/vm_page.h`](https://cgit.freebsd.org/src/tree/sys/vm/vm_page.h) — поля `struct vm_page`, встроенная `md_page`, битовые карты `valid` и `dirty`; [`sys/vm/vm_page.c`](https://cgit.freebsd.org/src/tree/sys/vm/vm_page.c) — учёт веса дескриптора при расчёте числа кадров, описание `vm_page_reclaim_contig()`; [`sys/vm/vm_pageout.c`](https://cgit.freebsd.org/src/tree/sys/vm/vm_pageout.c) — четыре потока страничного демона и отсутствие в файле упоминаний уплотнения и непрерывности; [`sys/vm/vm_reserv.c`](https://cgit.freebsd.org/src/tree/sys/vm/vm_reserv.c) — спекулятивное выделение суперстраниц без программных указаний; [`sys/vm/uma_int.h`](https://cgit.freebsd.org/src/tree/sys/vm/uma_int.h) — зона, keg, ведро, slab, четыре ступени обслуживания, вёдра по доменам, правило выноса заголовка slab'а при потерях больше 10 %; [`sys/amd64/include/vmparam.h`](https://cgit.freebsd.org/src/tree/sys/amd64/include/vmparam.h), [`sys/arm64/include/vmparam.h`](https://cgit.freebsd.org/src/tree/sys/arm64/include/vmparam.h) и [`sys/riscv/include/vmparam.h`](https://cgit.freebsd.org/src/tree/sys/riscv/include/vmparam.h) — плотная и разреженная модели, число свободных списков, `VM_NFREEORDER` и мотивировка потолка через строку кэша, уровни и размеры резервирований - [Separating memory descriptors from struct page — LWN.net](https://lwn.net/Articles/1073425/) — вторичный источник о состоянии работы над восьмибайтовым дескриптором: промежуточное сокращение до 32 байт, упор в миграцию страниц, оценка цели как отдалённой --- ## Связанные заметки - [Страничная трансляция: таблицы, TLB, разрядность](./os-paging-and-tlb.md) — вторая статья цикла: требование выравнивания к большим страницам и цена размера страницы, из которых растёт вся возня с непрерывностью и весом метаданных - [Карта памяти ядра: половины, прямое отображение, KASLR](./os-kernel-memory-map.md) — третья статья цикла: куда попадают окно прямого отображения и область дескрипторов, которые здесь выделяются, и что значит вырезать из окна страницу - [Стеки: ядра, прерываний, пользовательские](./os-stacks.md) — четвёртая статья цикла: стек ядра как регулярное непрерывное выделение высокого порядка — первый потребитель, на котором проверяют потолок аллокатора - [Ядро как программа: freestanding, компоновка, ABI, выбор языка](./os-kernel-as-program.md) — восьмая статья цикла: скрипт компоновки, резервирующий ранние таблицы страниц, и разделы инициализации, вместе с которыми выбрасывают ранний аллокатор - [Адресное пространство: зачем трансляция и какие есть альтернативы](./os-address-space-models.md) — первая статья цикла: PMP и MPU, из-за которых области прошивки приходят в карту с пометкой «не отображать» - [Устройство ОС — план цикла статей](./os-knowledge-base-plan.md) — состав и порядок цикла; загрузка и структура ядра разбираются отдельными статьями - [SATA, SAS и NVMe](./storage-interfaces.md) — та же граница со стороны устройства: разрядность адреса контроллера и рассеянные списки, из-за которых существуют классы памяти по адресуемости - [Linux — справочник команд: память](./linux-tldr-memory.md) — наблюдаемая сторона тех же механизмов на живой системе: зоны, порядки свободных блоков, кэши объектов - [Загрузка: от питания до первой инструкции ядра](./os-boot-sequence.md) — шестая статья цикла: откуда берётся карта памяти и в каком состоянии машина оказывается к первой инструкции ядра - [Структура ядра: монолит, микроядро и что между](./os-kernel-structure.md) — девятая статья цикла: почему у seL4 аллокатора в ядре нет и что из этого следует для всей подсистемы