“Давным-давно, кажется в прошлую пятницу”, автор разбирался, как устроен механизм THP (transparent huge pages) в Linux и поразился, насколько отличная идея не соответствует корявой реализации. Как водится, далее последовала цепочка вопросов: “кто виноват?”,  “что делать?” и “а что если?”. Кто виноват - понятно, особенности архитектуры, аппаратные ограничения. Второй вопрос открыт, а вот с “что если” стоит разобраться.

Механизм виртуальной памяти в современных вычислительных системах позволяет программе использовать физическую память как кэш для доступа к собственному виртуальному адресному пространству. Для этого требуется решить две большие задачи - 

1. научиться максимально дёшево преобразовывать виртуальный адрес в физический

2. уметь прозрачно сохранять содержимое физической памяти на внешний носитель и читать обратно (механизм подкачки)

Обмен данными с внешним носителем осуществляется фрагментами фиксированного размера, страницами. Это совершенно объективно и налагает отпечаток на всю работу с виртуальными адресами.

Пусть размер страницы 4К, что соответствует действительности в большинстве случаев. Для адресации внутри страницы (как физической так и виртуальной) используются 12 младших разрядов. А адреса распадаются на две части - старшие разряды составляют номер страницы, младшие - смещение внутри страницы. И преобразование адресов сводится к механизму трансляции виртуального номера страницы в физический.

Такой механизм двухступенчатый - на первом этапе работает TLB (translation lookaside buffer), в случае неуспеха - процедура под названием page walk, которая просматривает таблицу известных страниц (page table). TLB - это ассоциативный массив фиксированного размера, который по предъявлении ключа - номера виртуальной страницы умеет находить соответствующий номер физической страницы (если он ему известен). За содержимым TLB присматривает ядро ОС.

Таблица страниц (page table) традиционно имеет древовидную структуру (radix-tree). На вершину дерева указывает один из регистров (ex: CR3 в AMD64) либо он указан в контексте процесса (SPARC V8). Узлы дерева являются физическими страницами, в каждый узел такой страницы помещается фиксированное к-во элементов. Так в 4-килобайтную  страницу помещается 512  64-разрядных элементов. Элемент дерева страниц содержит актуальную информацию о физической странице - адрес, находится ли она в памяти или на диске, флаги защиты, изменена ли она … Поэтому можно просто отдать физический указатель либо предварительно страницу придётся прочитать с диска (положение в файле подкачки в этом случае находится в элементе вместо номера физ. страницы).

Насколько эффективна данная конструкция? Достаточно эффективна, хотя, пожалуй, могла бы работать и быстрее. В большинстве практических задач TLB срабатывает в 98-99% случаев. Это удивительно, учитывая, что (например) 4Гб занятого виртуального пространства соответствуют миллиону страниц. А типичный объем TLB - несколько сот элементов. Выручает сильно неоднородное распределение обращений к памяти в типичных программах.

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

Попытки повысить эффективность преобразования адресов предпринимались изначально разными способами. Самый очевидный - увеличить размер TLB, сделать многоуровневым (как кэш). Менее очевидный - увеличить размер физической страницы. При этом при прочих равных вырастет покрытие памяти элементами TLB и увеличится его эффективность. 

При необходимости использовать страницы разного размера не меняя структуру page table, это можно сделать лишь за счет спуска по дереву не на полную глубину. Размер страниц при этом (в случае AMD64) меняется в 512 раз: 4К => 2 Мб => 1 Гб. Например, если элемент страницы PDE содержит включённый флаг конечного элемента, значит этот элемент смотрит не на страницу PTE, а описывает физическую страницу размером 2 Мб.

Увеличивая размер страницы, мы с одной стороны ускоряем работу с памятью из-за возросшей эффективности кэша TLB, а с другой стороны увеличиваем издержки при записи/чтении увеличенных объемов данных во время работы механизма подкачки. Шаг в 512 раз слишком грубый.

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

Почему 4K

Есть простой и неправильный ответ на этот вопрос.
“Потому что i386 32-разрядный и дерево page table у него двухуровневое, 12 (разрядов в 4К странице) + 10 (1024 32-разрядных указателей на 4К странице дерева первого уровня) + 10 (1024 32-разрядных указателей на 4К странице дерева второго уровня) = 32”.

Неправильный, т.к. на i386 свет клином не сошелся. В SPARC V8 таблица страниц трёхуровневая и распределена так: 8 разрядов в верхнем уровне, по 6 в нижних и 12 на страницу. Тоже 4К.

Правда, SPARC (1987) появился после i386(1985), а что было до него?

32-разрядный VAX (1977) имел физические страницы по 512 байт. BSD группировал их в пакеты по 8 штук, так что с точки зрения программиста страница имела размер в те же 4К.

Еще раньше, PDP-11(1970). 16-разрядное адресное пространство было разделено на 8 областей по 8К, которые формально можно считать страницами.

Еще раньше, Multics (1965) имела два размера страниц - 64 и 1024 36-разрядных слов.
Вообще, кажущаяся нам естественной разрядность компьютеров в степень двойки окончательно сложилась в 70-х годах. Размер страницы в 4К - в начале 80-х.

До этого делали кто во что горазд и размер страницы был предметом научных споров и битв математических моделей. В конце концов пришли к выводу, что 4К - оптимальный размер для задач, типичных для 80-х.

С тех пор прошло немало времени, и задачи подросли и системы стали 64-разрядными. Неслучайно разработчики архитектуры ARM ввели два базовых размера страниц - 4К или 64К. Intel патентует таблицу страниц, которая поддерживает и то и другое одновременно. Проблема назрела.

THP (transparent huge pages)

В ядре linux-2.6.38 появилась (Andrea Arcangeli, 2012) остроумная техника - прозрачные большие страницы  (transparent huge pages). Суть её в следующем:

• при любой возможности ядро старается использовать большие (2Mb) страницы

• при выделении памяти, насколько это возможно, создаются большие страницы

• при чтении 4K страницы из файла подкачки, по возможности создаётся большая страница, при этом объединяются мелкие страницы и упоминание о них удаляется из TLB и page table

• большие страницы подлежат подкачке, но при этом могут расщепляться на маленькие

• системные вызовы mlock, mprotect так же приводят к расщеплению большой страницы на маленькие

• специальный поток ядра khugepaged просматривает в фоне таблицы страниц и по возможности сливает мелкие страницы в крупные

Происходит всё это прозрачно для пользовательских программ. Замеры показывают, что за счет сокращения page table и высоты дерева в общем случае имеется выигрыш в производительности порядка 10%. Тем не менее, нередко, такая техника замедляет работу приложений, особенно тех, что рассчитаны (явно или неявно) на работу с мелкими страницами. Так что при необходимости THP можно (и нужно) выключить.

Самое время приступить к обещанному “а что если”.

Преобразование адреса в TLB

Прикладная программа обычно не знает ни про какие страницы, но для работы необходимо уметь преобразовывать виртуальные адреса в физические. В идеале хотелось бы, чтобы виртуальное адресное пространство процесса целиком покрывалось записями TLB, ведь несколько сот больших страниц - это не так уж и мало, учитывая что большинство программ просят память не напрямую у ядра, а через runtime библиотеку, которая предпочитает большие размеры и сама раздаёт память.

Первый шаг - проверить наличие виртуальной страницы в кэше TLB

• страницы всех размеров обрабатываются в едином кэше TLB

• минимальный размер страницы - 8К или 13 разрядов. Гранулярность диска в современных ОС от 8 до 64К, 4К страницы - наследие 32-разрядного прошлого (шутка).

• младшие 12 разрядов отбрасываем (4К), один разряд в строке TLB избыточный, нужен для кодирования длины

• размер страницы закодирован в самой строке TLB - младшие разряды ключа вплоть до первого нуля

• при поиске сравниваются только разряды ключа, отвечающие за найденный размер страницы

• если подходящая строка найдена, из исходного адреса подставляется требуемое для найденного размера ключа недостающее число разрядов

Однако это работает только если физические страницы тоже идут подряд.
Это легко обеспечить только при относительно небольших страницах (навскидку 16...64К).

Page walk

Процедура с таким названием выполняется (операционной системой или процессором, по-разному в разных архитектурах) при промахе в TLB. Традиционно выполняется как спуск по дереву (radix-tree) фиксированной глубины, где ключами на страницах являются последовательные фрагменты виртуального адреса. В нашем случае никакого дерева нет.

• в таблице страниц только один (нижний) уровень - PTE

• каждый элемент PTE смотрит на 8К физическую страницу

• таблица страниц находится в обычном (транслируемом) адресном пространстве и подлежит подкачке (аналогично VAX, там для этого использовалось адресное пространство ядра)

• таблица страниц находится в одном непрерывном куске виртуального адресного пространства, стартовый адрес этого куска (пусть, BEG) хранится в специально отведенном для этого регистре (аналогично CR3 в AMD64)

• адрес, где хранится описание любой страницы, может быть вычислен из виртуального адреса как BEG + ((virt_addr >> 10) & 7), где 10 получаются вычитанием 3 (8 байт на описание страницы) из 13 - т.к. 2¹³ - минимальный размер страницы

• элемент PTE вполне традиционным образом описывает физическую страницу, ее права и  состояние, дополнительно, в нём записан также фактический размер виртуальной страницы, фрагментом которой являются те 8К, на которые указывает данный элемент PTE

• поскольку фактический размер виртуальной страницы кодируется логарифмом от логарифма, на его хранение надо совсем немного, например, 3 разряда позволяют использовать 8 уровней степеней 2 - от 8К (минимум) до 2Мб. 3 разряда в PTE найти можно. А 4 разряда, кстати, увеличат максимальный размер виртуальной страницы до 512Мб.

• длину можно было бы разместить в самом адресе аналогично ключу TLB, но это подразумевало бы что и в физическом адресном пространстве и на диске (файл подкачки) 8К страницы будут расположены непрерывно.

• чтение с диска и запись на диск осуществляются вполне традиционным путём, при этом остаётся свобода, работать ли с большой (виртуальной) страницей целиком или по - прежнему 8K кусками

Раздача виртуальной памяти

Даже если на хранение PTE требуется 1/1000 от адресного пространства, это всё равно слишком много для виртуальной памяти пусть даже в 2⁴⁸ байт. Из этого следует, что нельзя раздавать виртуальные сегменты беспорядочно, требуется некоторая система. Причем, система, которая будет минимизировать диапазон адресов используемой части виртуального адресного пространства, избегая по возможности его фрагментации.

Очевидный кандидат - метод двойников/близнецов (buddy allocator), дальше просто “аллокатор”.

• аллокатор работает с областью памяти фиксированного размера

• память выделяется фрагментами размером в степень двойки, причем адрес начала фрагмента (относительно области памяти аллокатора) кратен размеру блока

• минимальный размер - 8 байт, которые соответствуют 8К адресного пространства. Минимальный размер соответствует элементу PTE, т.е. минимальная виртуальная страница соответствует физической.

• при старте процесса ОС создаёт для него область в виртуальном адресном пространстве под PTE + служебные данные аллокатора

• страницы, занятые самим PTE и служебными данными аллокатора тоже учтены в PTE

• начальный размер невелик, чтобы не делать лишнюю работу для мелких процессов. Например, для работы с 64 Мб виртуальной памяти потребуется 64К для работы аллокатора, т.е. 8 физических страниц по 8К, которые должны быть изначально учтены в 8 записях PTE (и в аллокаторе)

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

• по мере роста виртуального адресного пространства аллокатор может исчерпать имеющуюся память после чего область памяти под PTE удваивается, аллокатор учитывает это в своих внутренних структурах

Стоит отметить, что сам алгоритм близнецов был разработан 1963 Г.Марковицем (H.Markowitz), открыт заново и опубликован в 1965 (CACM 8, 1965, 623...625) К.Ноултоном (K.Knowlton).

В ядре UNIX он используется как минимум со времен BSD 4.2 (1983), правда для раздачи памяти под объекты ядра как раз в связи с его способностью избегать внешней фрагментации памяти.

У автора насыщенная история взаимоотношений с этим алгоритмом, что в частности, отражено здесь.

Создание области виртуальной памяти

Допустим, процесс (runtime library?) попросил создать ему область виртуальной памяти в 100Мб.

• аллокатор умеет работать только с непрерывными фрагментами размером в степень двойки, так что самый простой вариант - фактически выделить массив PTE под 128 Мб физической памяти.

• в принципе, аллокатор можно научить выделить сначала 128 Мб а потом откусить от конца и пометить как свободные избыточные 28 Мб. В этом случае наша область превратится в три подряд идущие занятые страницы в 64 Мб + 32 Мб + 4 Мб плюс хвост из свободных страниц в  4 Мб + 8 Мб + 16 Мб.

• Но это только если размер максимальной страницы >= 128 Мб. Если же предположить, что размер страницы ограничен 2 Мб, их придётся нарезать 50 штук (плюс 14 свободных).

• для каждой вновь созданной страницы (какого бы она ни была размера) требуется

  • пройтись по всем её записям PTE (которые соответствуют 8К)

  • прописать в запись PTE фактический размер страницы. Это делается для того, чтобы иметь возможность по произвольному указателю найти размер и начало виртуальной страницы. А иначе как мы узнаем виртуальную страницу по произвольному адресу, если этой страницы нет в TLB.

  • связать маленькую 8К страницу с её физическим образом или пометить как uncommitted, задать флаги защиты  …

  • отнять BEG, сдвинуть влево на 10 разрядов и вернуть клиенту как указатель на вновь выделенную область виртуальной памяти

• требуется внести информацию об этой виртуальной странице в TLB

Освобождение области виртуальной памяти

Процесс может как создавать области виртуальной памяти, так и удалять их. При удалении происходит следующее:

• для начала необходимо проверить, что такая область действительно выделялась. Для этого находим первый элемент PTE, соответствующий данному сегменту и получаем его размер виртуальной страницы. Т.к. память выделяется фрагментами размером в степень 2, начало фрагментов должно быть кратно степени 2. Это позволяет диагностировать ошибку, если удаляется сегмент, который не выделялся.

• пройдёмся по всем элементам PTE данной виртуальной страницы и пометим их как удалённые (просто для порядка)

• отдадим аллокатору (освободим) этот фрагмент данных. После чего он возможно будет рекурсивно слит со своим двойником (buddy) в целях дефрагментации.

• вычистим информацию об этой виртуальной странице из TLB.

Раздача физической памяти

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

Предположим, у нас имеется аллокатор физической памяти, который умеет выделять области размером в степень 2, адрес которой кратен её размеру. Логично предположить, что это тоже buddy allocator или один из набора таковых, хотя это и необязательно.

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

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

В случае, когда свободной физической памяти в достаточном объеме нет, какие-то страницы придётся выталкивать в файл подкачки. Возможно, аналогично THP, одну или несколько больших страниц придётся распилить на фрагменты меньшего размера. Но в отличие от THP, страницу не нужно резать сразу на 512 частей, можно и более аккуратно, например, отрезать половинки от большой страницы пока не останется сколько надо, после чего вытолкнуть на диск.

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

• если памяти в системе хватает, страницы останутся нетронутыми.

• если в системе идёт интенсивная работа со свопом и не ограничен искусственно минимальный размер страницы, постепенно всё перемелет (ну т.е. станет как сейчас). Впрочем, это как раз крайний вариант, которого лучше избегать.

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

Итого

Предложенная идея выглядит простой и интуитивно понятной. Если концепция действительно рабочая, такой подход позволит заметно удешевить преобразование виртуального адреса и упростить работу MMU, особенно в ситуации с аппаратным page walk.

Предложенная идея находится на стыке hardware & software и требует работ с обеих сторон. Здесь есть и большие возможности и значительные трудности т.к. занимаются этим обычно совсем разные люди.

Трудность заключается в том, что для того, чтобы разработчики процессора хоть пальцем пошевелили, им требуется более-менее живая операционная система, поддерживающая эти изменения. А для того, чтобы такая ОС появилась, неплохо бы иметь рабочее “железо”.

Параллельная разработка, пожалуй, возможна только для soft процессоров, таких как MicroBlaze, Nios или OpenRisc. Впрочем, всё это сугубо мнение автора.