Страничная организация памяти windows

Уровень сложностиПростой

Время на прочтение15 мин

Количество просмотров13K

Картинка с сайта: habr.com

В этом посте я буду говорить о страничной организации только в контексте PML4 (Page Map Level 4), потому что на данный момент это доминирующая схема страничной организации x86_64 и, вероятно, останется таковой какое-то время.

Окружение

Это необязательно, но я рекомендую подготовить систему для отладки ядра Linux с QEMU + gdb. Если вы никогда этого не делали, то попробуйте такой репозиторий: easylkb (сам я им никогда не пользовался, но слышал о нём много хорошего), а если не хотите настраивать окружение самостоятельно, то подойдёт режим практики в любом из заданий по Kernel Security на pwn.college (вам нужно знать команды vm connect и vm debug).

Я рекомендую вам так поступить, потому что считаю, что самостоятельное выполнение команд вместе со мной и возможность просмотра страниц (page walk) на основании увиденного в gdb — хорошая проверка понимания.

Что такое страница

В x86_64 страница — это срез памяти размером 0x1000 байтов, выровненный по 0x1000 байтам.

Именно поэтому при изучении /proc/<pid>/maps видно, что все диапазоны адресов начинаются и заканчиваются адресами, заканчивающимися на 0x000, ведь минимальный размер распределения памяти в x86_64 равен размеру страницы (0x1000 байтов), а страницы должны быть «выровнены по страницам» (последние 12 битов должны быть равны нулю).

При помощи MMU виртуальную страницу (Virtual Page) можно резолвить в единую физическую страницу (Physical Page) (она же «блок страницы», Page Frame), хотя и многие виртуальные страницы могут ссылаться на одну физическую.

Что такое виртуальный адрес

Как можно догадаться, PML4 имеет четыре уровня структур страничной организации памяти; эти структуры называются таблицами страниц (Page Table). Таблица страниц — это область памяти размером со страницу, содержащая 512 8-байтных элементов таблицы страниц. Каждый элемент таблицы страниц ссылается или на таблицу страниц следующего уровня или на конечный физический адрес, в который резолвится виртуальный адрес.

Элемент таблицы страниц, используемый для трансляции адресов, основан на виртуальном адресе доступа к памяти. Так как на каждый уровень используется 512 элементов, 9 битов виртуального адреса применяются на каждом уровне для индексации в соответствующей таблице страниц.

Допустим, у нас есть такой адрес:

0x7ffe1c9c9000

Последние 12 битов адреса обозначают смещение внутри физической страницы:

0x7ffe1c9c9000 & 0xfff = 0x0

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

После последних 12 битов, которые являются смещением внутри конечной страницы, виртуальный адрес состоит из индексов таблиц страниц. Как говорилось выше, каждый уровень страничной организации памяти использует 9 битов виртуального адреса, поэтому самый нижний уровень структур страничной организации, то есть таблица страниц, индексируется по следующим 9 битам адреса (благодаря битовому маскированию при помощи & 0x1ff для сдвинутого значения). На следующих уровнях нам просто нужно каждый раз выполнять сдвиг вправо ещё на девять битов и снова маскировать нижние девять битов в качестве нашего индекса. Выполнение этой операции для показанного выше адреса даёт нам следующие индексы:

Level 1, Page Table (PT):
Index = (0x7ffe1c9c9000 >> 12) & 0x1ff = 0x1c9

Level 2, Page Middle Directory (PMD):
Index = (0x7ffe1c9c9000 >> 21) & 0x1ff = 0x0e4

Level 3, Page Upper Directory (PUD):
Index = (0x7ffe1c9c9000 >> 30) & 0x1ff = 0x1f8

Level 4, Page Global Directory (PGD):
Index = (0x7ffe1c9c9000 >> 39) & 0x1ff = 0x0ff

База

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

У каждого потока CPU есть базовый регистр таблицы страниц под названием cr3.

cr3 содержит физический адрес самого верхнего уровня структуры страничной организации, называемого Page Global Directory (PGD).

При отладке ядра через gdb содержимое cr3 можно считать следующим образом:

gef➤  p/x $cr3
$1 = 0x10d664000

В зависимости от используемых функций процессора в регистре cr3 наряду с адресом PGD может храниться и дополнительная информация, поэтому более универсальный способ получения физического адреса PGD из регистра cr3 заключается в маскировании нижних 12 битов его содержимого:

gef➤  p/x $cr3 & ~0xfff
$2 = 0x10d664000

Элементы таблиц страниц

Давайте рассмотрим в gdb физический адрес, полученный нами из cr3. Команда monitor xp/... раскрытая gdb благодаря QEMU Monitor, позволяет нам выводить физическую память vm, а команда monitor xp/512gx ... печатает всё содержимое (512 элементов) PGD, на который ссылается cr3:

gef➤  monitor xp/512gx 0x10d664000
...
000000010d664f50: 0x0000000123fca067 0x0000000123fc9067
000000010d664f60: 0x0000000123fc8067 0x0000000123fc7067
000000010d664f70: 0x0000000123fc6067 0x0000000123fc5067
000000010d664f80: 0x0000000123fc4067 0x0000000123fc3067
000000010d664f90: 0x0000000123fc2067 0x000000000b550067
000000010d664fa0: 0x000000000b550067 0x000000000b550067
000000010d664fb0: 0x000000000b550067 0x0000000123fc1067
000000010d664fc0: 0x0000000000000000 0x0000000000000000
000000010d664fd0: 0x0000000000000000 0x0000000000000000
000000010d664fe0: 0x0000000123eab067 0x0000000000000000
000000010d664ff0: 0x000000000b54c067 0x0000000008c33067

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

Вероятно, этот вывод пока для вас не имеет особого смысла, но мы можем заметить в данных определённые паттерны, например, многие 8-байтные элементы заканчиваются на 0x67.

Расшифровка записей PGD

Возьмём из показанного выше вывода PGD в качестве примера запись PGD по адресу 0x000000010d664f50 со значением 0x0000000123fca067, чтобы понять, как расшифровать запись.

И давайте сделаем это с двоичной формой значения этой записи:

gef➤  p/t 0x0000000123fca067
$6 = 100100011111111001010000001100111

Вот небольшая схема с объяснениями, что означает каждый бит записи:

~ PGD Entry ~                                                   Present ──────┐
                                                            Read/Write ──────┐|
                                                      User/Supervisor ──────┐||
                                                  Page Write Through ──────┐|||
                                               Page Cache Disabled ──────┐ ||||
                                                         Accessed ──────┐| ||||
                                                         Ignored ──────┐|| ||||
                                                       Reserved ──────┐||| ||||
┌─ NX          ┌─ Reserved                             Ignored ──┬──┐ |||| ||||
|┌───────────┐ |┌──────────────────────────────────────────────┐ |  | |||| ||||
||  Ignored  | ||               PUD Physical Address           | |  | |||| ||||
||           | ||                                              | |  | |||| ||||
0000 0000 0000 0000 0000 0000 0000 0001 0010 0011 1111 1100 1010 0000 0110 0111
       56        48        40        32        24        16         8         0

Вот что означает каждая из этих меток:

• NX (неисполняемый) — если этот бит установлен, никакое из отображений памяти, являющихся потомком этого PGD, не будет исполняемым.

• Reserved — эти значения должны быть равны нулю.

• PUD Physical Address — физический адрес PUD, связанного с этой записью PGD.

• Accessed — если эта запись или её потомки ссылаются на какую‑то страницу, то этот бит устанавливается MMU и может быть сброшен операционной системой.

• Page Cache Disabled (PCD) — страницы‑потомки этой записи PGD не должны попадать в иерархию кэшей CPU; иногда этот бит также называют Uncacheable (UC).

• Page Write Through (WT) — записи в страницы‑потомки этой записи PGD должны сразу же выполнять запись в ОЗУ, а не буферизировать записи в кэш CPU перед обновлением ОЗУ.

• User/Supervisor — если этот бит сброшен, к страницам‑потомкам этой PGD невозможно выполнить доступ ни из какого режима, за исключением supervisor.

• Read/Write — если этот бит сброшен, в страницы‑потомки этой PGD нельзя выполнять запись.

• Present — если этот бит сброшен, то процессор не будет использовать эту запись для трансляции адресов и ни один из остальных битов не будет применяться.

Здесь нас волнует бит Present, биты, определяющие физический адрес следующего уровня структур страничной организации, биты PUD Physical Address и биты разрешений: NX, User/Supervisor, and Read/Write.

• Бит Present очень важен, потому что без него вся остальная часть записи игнорируется.

• PUD Physical Address позволяет нам продолжить просмотр страниц (page walk), сообщая, где находится физический адрес следующего уровня структур страничной организации памяти.

• Биты Permission применяются к страницам, являющимся наследниками записи PGD; они определяют, как можно выполнять доступ к этим страницам.

Остальные биты для наших целей не так важны:

• Бит Accessed устанавливается, если запись используется при трансляции доступа к памяти, он не важен для просмотра страниц.

• Page Cache Disabled и Page Write Through не используются для обычного отображения страниц и не влияют на трансляцию страниц и разрешения, так что не будем обращать на них внимания.

Итак, декодировав эту запись, мы получим:

PUD является Present:

gef➤  p/x 0x0000000123fca067 & 0b0001
$18 = 0x1

Отображения в PUD и ниже могут быть Writable:

gef➤  p/x 0x0000000123fca067 & 0b0010
$19 = 0x2

Отображения в PUD и ниже могут быть доступны для User:

gef➤  p/x 0x0000000123fca067 & 0b0100
$20 = 0x4

Физический адрес PUD (биты (51:12] ) — 0x123fca000:

gef➤  p/x 0x0000000123fca067 & ~((1ull<<12)-1) & ((1ull<<51)-1)
$21 = 0x123fca000

Отображения в PUD и ниже могут быть Executable:

gef➤  p/x 0x0000000123fca067 & (1ull<<63)
$22 = 0x0

Декодирование записей для всех уровней

Разобравшись, как декодировать запись PGD, нам будет легко декодировать остальные уровни, по крайней мере, в общем случае.

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

PGD

~ PGD Entry ~                                                   Present ──────┐
                                                            Read/Write ──────┐|
                                                      User/Supervisor ──────┐||
                                                  Page Write Through ──────┐|||
                                               Page Cache Disabled ──────┐ ||||
                                                         Accessed ──────┐| ||||
                                                         Ignored ──────┐|| ||||
                                                       Reserved ──────┐||| ||||
┌─ NX          ┌─ Reserved                             Ignored ──┬──┐ |||| ||||
|┌───────────┐ |┌──────────────────────────────────────────────┐ |  | |||| ||||
||  Ignored  | ||               PUD Physical Address           | |  | |||| ||||
||           | ||                                              | |  | |||| ||||
XXXX XXXX XXXX 0XXX XXXX XXXX XXXX XXXX XXXX XXXX XXXX XXXX XXXX XXXX 0XXX XXXX
       56        48        40        32        24        16         8         0

Эту диаграмму мы уже видели, я подробно описал её в предыдущем разделе, но здесь у неё не указана конкретная запись PGD.

PUD

~ PUD Entry, Page Size unset ~                                  Present ──────┐
                                                            Read/Write ──────┐|
                                                      User/Supervisor ──────┐||
                                                  Page Write Through ──────┐|||
                                               Page Cache Disabled ──────┐ ||||
                                                         Accessed ──────┐| ||||
                                                         Ignored ──────┐|| ||||
                                                      Page Size ──────┐||| ||||
┌─ NX          ┌─ Reserved                             Ignored ──┬──┐ |||| ||||
|┌───────────┐ |┌──────────────────────────────────────────────┐ |  | |||| ||||
||  Ignored  | ||               PMD Physical Address           | |  | |||| ||||
||           | ||                                              | |  | |||| ||||
XXXX XXXX XXXX 0XXX XXXX XXXX XXXX XXXX XXXX XXXX XXXX XXXX XXXX XXXX 0XXX XXXX
       56        48        40        32        24        16         8         0

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

PMD

~ PMD Entry, Page Size unset ~                                  Present ──────┐
                                                            Read/Write ──────┐|
                                                      User/Supervisor ──────┐||
                                                  Page Write Through ──────┐|||
                                               Page Cache Disabled ──────┐ ||||
                                                         Accessed ──────┐| ||||
                                                         Ignored ──────┐|| ||||
                                                      Page Size ──────┐||| ||||
┌─ NX          ┌─ Reserved                             Ignored ──┬──┐ |||| ||||
|┌───────────┐ |┌──────────────────────────────────────────────┐ |  | |||| ||||
||  Ignored  | ||                PT Physical Address           | |  | |||| ||||
||           | ||                                              | |  | |||| ||||
XXXX XXXX XXXX 0XXX XXXX XXXX XXXX XXXX XXXX XXXX XXXX XXXX XXXX XXXX 0XXX XXXX
       56        48        40        32        24        16         8         0

Диаграмма PMD тоже очень похожа на предыдущую, и, как и в случае с записью PUD, мы игнорируем бит Page Size.

PT

~ PT Entry ~                                                    Present ──────┐
                                                            Read/Write ──────┐|
                                                      User/Supervisor ──────┐||
                                                  Page Write Through ──────┐|||
                                               Page Cache Disabled ──────┐ ||||
                                                         Accessed ──────┐| ||||
┌─── NX                                                    Dirty ──────┐|| ||||
|┌───┬─ Memory Protection Key              Page Attribute Table ──────┐||| ||||
||   |┌──────┬─── Ignored                               Global ─────┐ |||| ||||
||   ||      | ┌─── Reserved                          Ignored ───┬─┐| |||| ||||
||   ||      | |┌──────────────────────────────────────────────┐ | || |||| ||||
||   ||      | ||            4KB Page Physical Address         | | || |||| ||||
||   ||      | ||                                              | | || |||| ||||
XXXX XXXX XXXX 0XXX XXXX XXXX XXXX XXXX XXXX XXXX XXXX XXXX XXXX XXXX XXXX XXXX
       56        48        40        32        24        16         8         0

В записи Page Table всё становится интереснее: мы видим несколько новых полей/атрибутов, которых не было на предыдущих уровнях.

Вот какие это поля/атрибуты:

• Memory Protection Key (MPK или PK): это расширение x86_64, позволяющее назначать страницам 4-битные ключи, что можно использовать, чтобы конфигурировать разрешения памяти для всех страниц с этим ключом.

• Global: этот атрибут связан с тем, как TLB (Translation Lookaside Buffer — кэш MMU для трансляции виртуальных адресов в физические) кэширует трансляцию для страницы; если этот бит установлен, то страница не будет удалена из TLB при переключении контекста; обычно он включён для страниц ядра, чтобы снизить количество промахов TLB.

• Page Attribute Table (PAT): если значение установлено, то MMU должно обратиться к Page Attribute Table MSR, чтобы определить Memory Type страницы, например, является ли эта страница Uncacheable, Write Through или имеет один из нескольких других типов памяти.

• Dirty: этот бит похож на бит Accessed, он устанавливается MMU, если в эту страницу выполнена запись, и должен быть сброшен операционной системой.

Ничто из этого не влияет на саму трансляцию адреса, однако конфигурация Memory Protection Key может означать, что ожидаемые разрешения доступа к памяти для страницы, на которую ссылается эта запись, могут быть строже, чем закодированные в самой записи.

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

В общем случае просмотр страниц выполняется всего за несколько этапов:

• Преобразуем виртуальный адрес в индексы и смещение страницы, сдвинув адрес и применив битовые маски

• Считываем cr3, чтобы получить физический адрес PGD

• Чтобы достичь каждого уровня до последнего:

  • Используем индексы, вычисленные из виртуального адреса, чтобы узнать, какую запись из таблицы страниц использовать

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

• На последнем уровне снова находим запись, соответствующую индексу из виртуального адреса

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

• Добавляем смещение внутри страницы от виртуального адреса до физического адреса страницы

• Готово!

Увеличиваем масштаб

Как говорилось выше, диаграммы PUD и PMD рассчитаны на общий случай, когда не установлен бит Page Size.

А что происходит, если он установлен?

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

Но это ещё не всё: физический адрес в записях, где установлен бит Page Size, предназначен не для обычной страницы на 4 КБ (0x1000 байтов), это Huge Page, имеющая два варианта: Huge Page на 1 ГБ и Huge Page на 2 МБ.

Когда бит Page Size установлен у записи PUD, то он ссылается на 1-гигабайтную Huge Page, а когда бит Page Size установлен у записи PMD, он ссылается на 2-мегабайтную Huge Page.

Но откуда берутся числа 1 ГБ и 2 МБ?

Каждый уровень таблиц страниц хранит до 512 записей, то есть PT может ссылаться на не более чем 512 страниц и 512 * 4 КБ = 2 МБ. То есть Huge Page на уровне PMD, по сути, означает, что запись ссылается на страницу, имеющую тот же размер, что и полный PT.

Расширяя это на уровень PUD, мы просто снова умножаем на 512 и получаем размер полного PMD, содержащего полные PT: 512 * 512 * 4 КБ = 1 ГБ.

PUD страницы Huge Page

~ PUD Entry, Page Size set ~                                     Present ─────┐
                                                             Read/Write ─────┐|
                                                       User/Supervisor ─────┐||
                                                   Page Write Through ─────┐|||
                                                Page Cache Disabled ─────┐ ||||
                                                          Accessed ─────┐| ||||
                                                            Dirty ─────┐|| ||||
┌─── NX                                                Page Size ─────┐||| ||||
|┌───┬─── Memory Protection Key                         Global ─────┐ |||| ||||
||   |┌──────┬─── Ignored                             Ignored ───┬─┐| |||| ||||
||   ||      | ┌─── Reserved           Page Attribute Table ───┐ | || |||| ||||
||   ||      | |┌────────────────────────┐┌───────────────────┐| | || |||| ||||
||   ||      | || 1GB Page Physical Addr ||      Reserved     || | || |||| ||||
||   ||      | ||                        ||                   || | || |||| ||||
XXXX XXXX XXXX 0XXX XXXX XXXX XXXX XXXX XX00 0000 0000 0000 000X XXXX 1XXX XXXX
       56        48        40        32        24        16         8         0

Когда бит Page Size установлен, можно заметить, что запись PUD выглядит больше похожей на запись PT, чем на обычную запись PUD, что логично, ведь она также ссылается на страницу, а не на таблицу страниц.

Однако существуют некоторые отличия от PT:

1. Бит Page Size находится там, где находится в PT бит Page Attribute Table (PAT), поэтому бит PAT перенесён в бит 12.

2. Физический адрес 1-гигабайтной Huge Page должен иметь выравнивание в физической памяти по 1 ГБ; именно поэтому существуют новые биты Reserved и поэтому бит 12 можно задействовать как бит PAT.

В целом здесь нет ничего особо нового, при работе Huge Page с другие различия заключаются в том, что для получения физического адреса страницы к адресу нужно применить другую битовую маску; кроме того, выравнивание по 1 ГБ означает, что при вычислении физического адреса виртуального адреса в странице нам нужно использовать маску, основанную на выравнивании по 1 ГБ, а не по 4 КБ.

PMD страницы Huge Page

~ PMD Entry, Page Size set ~                                     Present ─────┐
                                                             Read/Write ─────┐|
                                                       User/Supervisor ─────┐||
                                                   Page Write Through ─────┐|||
                                                Page Cache Disabled ─────┐ ||||
                                                          Accessed ─────┐| ||||
                                                            Dirty ─────┐|| ||||
┌─── NX                                                Page Size ─────┐||| ||||
|┌───┬─── Memory Protection Key                         Global ─────┐ |||| ||||
||   |┌──────┬─── Ignored                             Ignored ───┬─┐| |||| ||||
||   ||      | ┌─── Reserved         Page Attribute Table ─────┐ | || |||| ||||
||   ||      | |┌───────────────────────────────────┐┌────────┐| | || |||| ||||
||   ||      | ||     2MB Page Physical Address     ||Reserved|| | || |||| ||||
||   ||      | ||                                   ||        || | || |||| ||||
XXXX XXXX XXXX 0XXX XXXX XXXX XXXX XXXX XXXX XXXX XXX0 0000 000X XXXX 1XXX XXXX
       56        48        40        32        24        16         8         0

Здесь ситуация очень похожа на запись PUD с установленным битом Page Size; единственное изменение заключается в том. что поскольку на этом уровне выравнивание для 2-мегабайтных страниц меньше, установлено меньше битов Reserved.

Выравнивание по 2 МБ означает, что смещение внутри huge page должно вычисляться при помощи маски, основанной на выравнивании по 2 МБ.

Просматриваем страницы

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

Подготовка

Запустив vm и подключив gdb, я сначала выберу адрес для выполнения просмотра страниц; в качестве примера я использую текущий указатель стека при работе ядра:

gef➤  p/x $rsp
$42 = 0xffffffff88c07da8

Итак, у нас есть адрес для просмотра, давайте получим физический адрес PGD из cr3:

gef➤  p/x $cr3 & ~0xfff
$43 = 0x10d664000

Я воспользуюсь этой небольшой функцией на Python, чтобы извлечь смещения таблиц страниц из виртуального адреса:

def get_virt_indicies(addr):
    pageshift = 12
    addr = addr >> pageshift
    pt, pmd, pud, pgd = (((addr >> (i*9)) & 0x1ff) for i in range(4))
    return pgd, pud, pmd, pt

На выходе получаем следующее:

In [2]: get_virt_indicies(0xffffffff88c07da8)
Out[2]: (511, 510, 70, 7)

PGD

Полученный нами индекс для PGD на основании виртуального адреса — это 511. Умножив 511 на 8, мы получим байтовое смещение в PGD, с которого начинается запись PGD для нашего виртуального адреса:

gef➤  p/x 5118
$44 = 0xff8

Добавив это смещение к физическому адресу PGD, мы получим физический адрес записи PGD:

gef➤  p/x 0x10d664000+0xff8
$45 = 0x10d664ff8

А считывание физической памяти по этому адресу даёт нам саму запись PGD:

gef➤  monitor xp/gx 0x10d664ff8
000000010d664ff8: 0x0000000008c33067

Похоже, у записи установлены последние три бита (present, user и writeable), а старший бит (NX) сброшен, то есть пока нет никаких ограничений на разрешения страниц, связанных с этим виртуальным адресом.

Маскирование битов [12, 51) даёт нам физический адрес PUD:

gef➤  p/x 0x0000000008c33067 & ~((1<<12)-1) & ((1ull<<51) - 1)
$46 = 0x8c33000

PUD

Индекс, полученный для PUD на основании виртуального адреса — это 510. Умножив 510 на 8, мы получим байтовое смещение в PUD, с которого начинается запись PUD для нашего виртуального адреса:

gef➤  p/x 5108
$47 = 0xff0

Добавив это смещение к физическому адресу PUD, мы получим физический адрес записи PUD:

gef➤  p/x 0x8c33000+0xff0
$48 = 0x8c33ff0

А считывание физической памяти по этому адресу даёт нам саму запись PUD:

gef➤  monitor xp/gx 0x8c33ff0
0000000008c33ff0: 0x0000000008c34063

На этом этапе нам нужно начать обращать внимание на Size Bit (бит 7), потому что если это 1-гигабайтная страница, мы остановим на этом просмотр страниц.

gef➤  p/x 0x0000000008c34063 & (1<<7)
$49 = 0x0

Похоже, в этой записи от сброшен, так что мы продолжим просмотр страниц.

Также обратим внимание, что запись PUD заканчивается на 0x3, а не на 0x7, как на предыдущем уровне, младшие два бита (present, writeable) по-прежнему установлены, а бит user теперь сброшен. Это значит, что доступ в пользовательском режиме к страницам, принадлежащим к этой записи PUD, приведёт к page fault из-за безуспешной проверки разрешения на доступ.

Бит NX по-прежнему сброшен, поэтому страницы, принадлежащие к этому PUD, по-прежнему могут быть исполняемыми.

Маскирование битов [12, 51) даёт нам физический адрес PMD:

gef➤  p/x 0x0000000008c34063 & ~((1ull<<12)-1) & ((1ull<<51)-1)
$50 = 0x8c34000

PMD

Индекс, полученный нами для PMD на основании виртуального адреса — это 70, поэтому умножение 70 на 8 позволит нам получить байтовое смещение в PMD с которого начинается запись PMD для нашего виртуального адреса:

gef➤  p/x 708
$51 = 0x230

Добавив это смещение к физическому адресу PMD, получим физический адрес записи PMD:

gef➤  p/x 0x8c34000+0x230
$52 = 0x8c34230

А считывание физической памяти по этому адресу даёт нам саму запись PMD:

gef➤  monitor xp/gx 0x8c34230
0000000008c34230: 0x8000000008c001e3

На этом уровне нам тоже нужно обращать внимание на Size Bit, потому что если это страница на 2 МБ, мы остановим на этом просмотр страниц.

gef➤  p/x 0x8000000008c001e3 & (1<<7)
$53 = 0x80

Похоже, наш виртуальный адрес ссылается на 2-мегабайтную Huge Page! Поэтому физический адрес в записи PMD — это физический адрес Huge Page.

Кроме того, судя по битам разрешений, страница по-прежнему Present и Writeable, а бит User по-прежнему сброшен, так что доступ к этой странице есть только из режима supervisor (ring-0).

В отличие от предыдущих уровней, здесь старший бит NX установлен:

gef➤  p/x 0x8000000008c001e3 & (1ull<<63)
$54 = 0x8000000000000000

То есть Huge Page — это не исполняемая память.

Применив битовую маску к битам [21:51), мы получим физический адрес huge page:

gef➤  p/x 0x8000000008c001e3 & ~((1ull<<21)-1) & ((1ull<<51)-1)
$56 = 0x8c00000

Теперь нам нужно применить маску к виртуальному адресу, основанному на 2-мегабайтному выравниванию страниц, чтобы получить смещение в Huge Page.

2 МБ эквивалентно 1<<21, поэтому применив битовую маску (1ull<<21)-1, мы получим смещение:

gef➤  p/x 0xffffffff88c07da8 & ((1ull<<21)-1)
$57 = 0x7da8

Добавив это смещение к базовому адресу 2-мегабайтной Huge Page, мы получим физический адрес, связанный с виртуальным адресом, с которого мы начинали:

gef➤  p/x 0x8c00000 + 0x7da8
$58 = 0x8c07da8

Похоже, виртуальный адрес 0xffffffff88c07da8 имеет физический адрес 0x8c07da8!

Проверка

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

Физический:

gef➤  monitor xp/10gx 0x8c07da8
0000000008c07da8: 0xffffffff810effb6 0xffffffff88c07dc0
0000000008c07db8: 0xffffffff810f3685 0xffffffff88c07de0
0000000008c07dc8: 0xffffffff8737dce3 0xffffffff88c3ea80
0000000008c07dd8: 0xdffffc0000000000 0xffffffff88c07e98
0000000008c07de8: 0xffffffff8138ab1e 0x0000000000000000

Виртуальный:

gef➤  x/10gx 0xffffffff88c07da8
0xffffffff88c07da8:	0xffffffff810effb6	0xffffffff88c07dc0
0xffffffff88c07db8:	0xffffffff810f3685	0xffffffff88c07de0
0xffffffff88c07dc8:	0xffffffff8737dce3	0xffffffff88c3ea80
0xffffffff88c07dd8:	0xdffffc0000000000	0xffffffff88c07e98
0xffffffff88c07de8:	0xffffffff8138ab1e	0x0000000000000000

На мой взгляд, выглядит неплохо!

Ещё один способ проверки — использовать команду monitor gva2gpa (гостевой виртуальный адрес в гостевой физический адрес), раскрытую gdb благодаря QEMU Monitor:

gef➤  monitor gva2gpa 0xffffffff88c07da8
gpa: 0x8c07da8

Если предположить, что QEMU выполняет трансляцию адресов правильно (вероятно, это справедливое предположение), то у нас есть ещё одно подтверждение успешности просмотра страниц!

Подведём итог

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

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

Если эта публикация вас вдохновила и вы хотите поддержать автора — не стесняйтесь нажать на кнопку

Литература

• Современные операционные системы, Э. Таненбаум, 2002, СПб, Питер, 1040 стр., (в djvu 10.1Мбайт) подробнее>>
• Сетевые операционные системы Н. А. Олифер, В. Г. Олифер (в zip архиве 1.1Мбайт)
• Сетевые операционные системы Н. А. Олифер, В. Г. Олифер, 2001, СПб, Питер, 544 стр., (в djvu 6.3Мбайт) подробнее>>

6.1 Основные понятия

Менеджер памяти — часть операционной системы, отвечающая за управление памятью.

Основные методы распределения памяти:

• Без использования внешней памяти (например: HDD)

• С использованием внешней памяти

6.2 Методы без использования внешней памяти

6.2.1 Однозадачная система без подкачки на диск

Память разделяется только между программой и операционной системой.

Схемы разделения памяти:

Схемы разделения памяти

Третий вариант используется в MS-DOS. Та часть, которая находится в ПЗУ, часто называется BIOS.

6.2.2 Распределение памяти с фиксированными разделами.

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

Системы могут иметь:

• общую очередь ко всем разделам

• к каждому разделу отдельную очередь

Картинка с сайта: moodle.kstu.ru

Распределение памяти с фиксированными разделами

Недостаток системы многих очередей очевиден, когда большой раздел может быть свободным, а к маленькому выстроилась очередь.

Алгоритмы планирования в случае одной очереди:

• поочередный

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

Также может быть смешанная система.

6.2.3 Распределение памяти динамическими разделами

В такой системе сначала память свободна, потом идет динамическое распределение памяти.

Распределение памяти динамическими разделами.

Недостатки:

• Сложность

• Память фрагментируется

Перемещаемые разделы

Это один из методов борьбы с фрагментацией. Но на него уходит много времени.

Картинка с сайта: moodle.kstu.ru

Перемещаемые разделы

Рост разделов

Иногда процессу может понадобиться больше памяти, чем предполагалось изначально.

Картинка с сайта: moodle.kstu.ru

Рост разделов

Настройка адресов и защита памяти

В предыдущих примерах мы можем увидеть две основные проблемы.

• Настройка адресов или перемещение программ в памяти

• Защита адресного пространства каждой программы

Решение обоих проблем заключается в оснащении машины специальными аппаратными регистрами.

• Базовый (указывает начало адресного пространства программы)

• Предельный (указывает конец адресного пространства программы)

6.3 Методы с использованием внешней памяти (свопинг и виртуальная память)

Так как памяти, как правило, не хватает. Для выполнения процессов часто приходится использовать диск.

Основные способы использования диска:

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

• Виртуальная память — процесс может быть частично загружен в память для работы

6.3.1 Свопинг (подкачка)

При нехватке памяти процессы могут быть выгружены на диск.

Картинка с сайта: moodle.kstu.ru

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

Как мы видим процесс А второй раз загрузился в другое адресное пространство, должны создаваться такие условия, которые не повлияют на работу процесса.

Свопер — планировщик, управляющий перемещением данных между памятью и диском.

Этот метод был основным для UNIX до версии 3BSD.

Управление памятью с помощью битовых массивов

Вся память разбивается на блоки (например, по 32бита), массив содержит 1 или 0 (занят или незанят).

Чтобы процессу в 32Кбита занять память, нужно набрать последовательность из 1000 свободных блоков.

Такой алгоритм займет много времени.

Картинка с сайта: moodle.kstu.ru

битовые массивы и списки

Управление памятью с помощью связных списков

Этот способ отслеживает списки занятых (между процессами) и свободных (процессы) фрагментов памяти.

Запись в списке указывает на:

• занят (P) или незанят (H) фрагмент

• адрес начала фрагмента

• длину фрагмента

Картинка с сайта: moodle.kstu.ru

Четыре комбинации соседей для завершения процесса X

Алгоритмы выделения блока памяти:

• первый подходящий участок.

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

• самый подходящий участок (медленнее, но лучше использует память).

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

6.3.2 Виртуальная память

Основная идея заключается в разбиении программы на части, и в память эти части загружаются по очереди.

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

Картинка с сайта: moodle.kstu.ru

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

Страничная организация памяти

Страницы — это части, на которые разбивается пространство виртуальных адресов.

Страничные блоки — единицы физической памяти.

Страницы всегда имеют фиксированный размер. Передача данных между ОЗУ и диском всегда происходит в страницах.

Х — обозначает не отображаемую страницу в физической памяти.

Страничное прерывание — происходит, если процесс обратился к странице, которая не загружена в ОЗУ (т.е. Х). Процессор передается другому процессу, и параллельно страница загружается в память.

Таблица страниц — используется для хранения соответствия адресов виртуальной страницы и страничного блока.

Таблица может быть размещена:

• в аппаратных регистрах (преимущество: более высокое быстродействие, недостаток — стоимость)

• в ОЗУ

Картинка с сайта: moodle.kstu.ru

Типичная запись в таблице страниц

Присутствие/отсутствие — загружена или незагружена в память

Защита — виды доступа, например, чтение/запись.

Изменение — изменилась ли страница, если да то при выгрузке записывается на диск, если нет, просто уничтожается.

Обращение — было ли обращение к странице, если нет, то это лучший кандидат на освобождение памяти.

Информация о адресе страницы когда она хранится на диске, в таблице не размещается.

Для ускорения доступа к страницам в диспетчере памяти создают буфер быстрого преобразования адреса, в котором хранится информация о наиболее часто используемых страниц.

Страничная организация памяти используется, и в UNIX, и в Windows.

Хранение страничной памяти на диске

Статическая область свопинга

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

На диске всегда есть дубликат страницы, которая находится в памяти.

Этот механизм наиболее простой.

Картинка с сайта: moodle.kstu.ru

Статический и динамический методы организации свопинга.

Динамическая область свопинга

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

Этот механизм сложнее, так как процессы не привязаны к какому-то пространству на диске, и нужно хранить информацию (карту диска) о местоположении на диске каждой страницы.

Презентацию к данной лекции Вы можете скачать здесь.

Введение

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

Откачка и подкачка

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

Откачка и подкачка (swapping) – это действия операционной системы по откачке (записи) образа неактивного процесса на диск или подкачке (считыванию) активного процесса в основную память. Необходимость выполнения подобных действий вызвана нехваткой основной памяти.

Файл откачки (backing store) — область дисковой памяти, используемая операционной системой для хранения образов откачанных процессов. Файл откачки организуется максимально эффективно: обеспечивается прямой доступ ко всем образам процессов в памяти (например, через таблицу по номеру процесса).

Популярная разновидность стратегии откачки и подкачки – roll out / roll in: откачка и подкачка на базе приоритетов; более приоритетные процессы исполняются, менее приоритетные – откачиваются на диск.

Наибольшие временные затраты на откачку – это затраты на передачу данных: полный образ процесса может занимать большую область памяти. Общее время откачки пропорционально размеру откачиваемых данных.

В распространенных ОС – UNIX, Linux, Windows и др. – реализованы различные стратегии откачки и подкачки.

Схема откачки и подкачки изображена на
рис.
16.1.

Картинка с сайта: intuit.ru

Рис.
16.1.
Схема откачки и подкачки.

Смежное распределение памяти

Наиболее простая и распространенная стратегия распределения памяти – смежное распределение памяти –
распределение памяти для пользовательских процессов в одной смежной области памяти. Основная память разбивается на
две смежных части (partitions), которые «растут» навстречу друг другу: резидентная часть ОС и вектор прерываний –
по меньшим адресам. Для пользовательских процессов память распределяется в
одном и том же смежном участке памяти. Для каждого процесса регистр перемещения указывает на начало выделенной ему
области памяти, регистр границы содержит длину диапазона логических адресов. Каждый логический адрес должен быть меньше
содержимого регистра границы. Физический адрес вычисляется аппаратно как сумма логического адреса и значения регистра
перемещения. Схема адресации с аппаратной поддержкой регистров перемещения и границы изображена на
рис.
16.2.

Общая задача распределения памяти и стратегии ее решения

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

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

Для решения данной задачи применяются следующие стратегии: метод первого подходящего (first-fit), метод наиболее подходящего (best-fit) и метод наименее подходящего (worst-fit).Рассмотрим каждую из них подробнее.

Метод первого подходящего:Выбирается первый по списку свободный участок подходящего размера (не меньшего, чем n ). На первый взгляд, данная стратегия оптимальна, но далее мы увидим, что это не всегда так.

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

Метод наименее подходящего: Выбирается из списка подходящая область наибольшего размера. Почему наибольшего? Чтобы избежать фрагментации (проблема фрагментации подробно рассмотрена далее в данной лекции).

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

Фрагментация

Фрагментация – это дробление памяти на мелкие не смежные свободные области маленького размера. Фрагментация возникает после выполнения системой большого числа запросов на память, таких, что размеры подходящих свободных участков памяти оказываются немного больше, чем требуемые. Например, если имеется 100 смежных свободных областей памяти по 1000 слов, то после выполнения 100 запросов на память по 999 слов каждый в списке свободной памяти останутся 1000 областей по одному слову.

Фрагментация бывает внутренняя и внешняя. При внешней фрагментации имеется достаточно большая область свободной памяти, но она не является непрерывной. Внутренняя фрагментация может возникнуть вследствие применения системой специфической стратегии выделения памяти, при которой фактически в ответ на запрос память выделяется несколько большего размера, чем требуется, — например, с точностью до страницы (листа ), размер которого – степень двойки. Страничная организация памяти подробно рассматривается далее в данной лекции.

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

При компактировке памяти и анализе свободных областей может быть выявлена проблема зависшей задачи: какая-либо задача может «застрять» в памяти, так как выполняет ввод-вывод в свою область памяти (по этой причине откачать ее невозможно). Решение данной проблемы: ввод-вывод должен выполняться только в специальные буфера, выделяемой для этой цели операционной системой.

Страничное преобразование
Отложенное копирование
Свопинг
Адресное пространство процесса

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

Но время диктует свои законы. Изменились микропроцессоры, и появились новые операционные системы. Однако у многих профессионалов осталась иллюзия того, что ОС от Microsoft — это лишь красивые картинки на экране и простейшее ядро внутри, а для серьезных задач требуются «серьезные» системы. На примере системы управления памятью покажем, что Windows NT — серьезная операционная система, построенная в соответствии с классическими принципами.

Организация виртуальной памяти

Страничное преобразование

Виртуальная память в Windows NT имеет страничную организацию, принятую во многих современных операционных системах. В общем виде схема страничной организации описывается следующим образом: линейный адрес разбивается на несколько частей. Старшая часть адреса содержит в себе номер элемента в корневой таблице. Этот элемент содержит адрес таблицы следующего уровня. Следующая часть линейного адреса содержит номер элемента уже в этой таблице и так далее, до последней таблицы, которая содержит номер физической страницы. А самая младшая часть адреса уже является номером байта в этой физической странице.

Процессоры Intel начиная с Pentium Pro позволяют операционным системам применять одно-, двух- и трехступенчатые схемы. И даже разрешается одновременное использование страниц различного размера. Эта возможность, конечно, повысила бы эффективность страничного преобразования, будь она внедрена в Windows NT. Увы, эта ОС возникла раньше и поддерживает только двухступенчатую схему преобразования с фиксированным размером страниц. Размер страниц для платформы Intel составляет 4 Кбайт, а для DEC Alpha — 8 Кбайт. Схема страничного преобразования (рис. 1) выглядит так:

Рисунок 1.
Схема страничного преобразования адреса для платформы Intel

32-разрядный линейный адрес разбивается на три части. Старшие 10 разрядов адреса определяют номер одного из 1024 элементов в каталоге страниц, адрес которого находится в регистре процессора CR3. Этот элемент содержит физический адрес таблицы страниц. Следующие 10 разрядов линейного адреса определяют номер элемента таблицы. Элемент, в свою очередь, содержит физический адрес страницы виртуальной памяти. Размер страницы — 4 Кбайт, и младших 12 разрядов линейного адреса как раз хватает (212 = 4096), чтобы определить точный физический номер адресуемой ячейки памяти внутри этой страницы.

Рассмотрим отдельный элемент таблицы страниц (PTE — Page Table Element) более подробно, так как он содержит массу полезной информации (рис 2).

Рисунок 2.
Элемент таблицы страниц в Windows NT

Старшие пять бит определяют тип страницы с точки зрения допустимых операций. Win32 API поддерживает три допустимых значения этого поля: PAGE_NOACCESS, PAGE_READONLY и PAGE_READWRITE. Следующие 20 бит определяют базовый физический адрес страницы в памяти. Если дополнить их 12 младшими разрядами линейного адреса, они образуют физический адрес ячейки памяти, к которой производится обращение. Следующие четыре бита PTE описывают используемый файл подкачки. Комбинацией этих битов ссылаются на один из 16 возможных в системе файлов. Последние три бита определяют состояние страницы в системе. Старший из них (T-Transition) отмечает страницу как переходную, следующий (D-Dirty) — как страницу, в которую была произведена запись. Информация об изменениях в странице необходима системе для того, чтобы принять решение о сохранении страницы в файле подкачки при ее вытеснении (принудительном освобождении занятой памяти). Действительно, если страница не изменялась в памяти после загрузки, то ее можно просто стереть, ведь в файле подкачки сохранилась ее копия. И наконец, младший бит (P-Present) определяет, присутствует ли страница в оперативной памяти или же она находится в файле подкачки. Конечно, 16 файлов подкачки явно недостаточно. В дальнейшем мы увидим, что в качестве файлов подкачки могут выступать исполняемые файлы, а также файлы, отображаемые в память. Официальная документация Microsoft весьма скупа на комментарии по этой ситуации. Отмечается лишь, что при отсутствии страницы в памяти 28 бит рассмотренного элемента таблицы страниц не несут никакой полезной информации и используются для определения местонахождения выгруженной страницы.

Для ускорения страничного преобразования в процессоре имеется специальная кэш-память, называемая TLB (Translation Lookaside Buffer). В ней хранятся наиболее часто используемые элементы каталога и таблиц страниц. Конечно, переключение процессов и даже потоков приводит к тому, что данные внутри этого буфера становятся неактуальными, т. е. недействительными. Это влечет за собой дополнительные потери производительности при переключении. К счастью, временной промежуток, выделяемый системой процессу, составляет 17 мс. Даже на машине с производительностью всего 20 MIPS за это время успеет выполниться непрерывный участок программы длиной (17 мс Ё 20 MIPS) 340 тыс. команд. Этого более чем достаточно, чтобы пренебречь потерями производительности при выполнении начального участка процесса.

Каждый процесс Windows NT имеет свой отдельный каталог страниц и свое собственное независимое адресное пространство, что очень хорошо с точки зрения защиты процессов друг от друга. Но за это удовольствие приходится платить ресурсами. Независимым процессам почти всегда приходится обмениваться информацией друг с другом. Windows NT предоставляет большое количество способов обмена, в том числе и при OLE. Но все они имеют в основе одно и то же действие: один процесс пишет нечто в некоторую ячейку памяти, а другой из нее читает. Это означает, что должны быть участки памяти, доступные разным процессам. На первый взгляд, это не проблема — могут же различные PTE ссылаться на одну и ту же страницу. Однако в каждом PTE хранятся атрибуты страницы, а ссылка на страницу со стороны PTE делается только в одну сторону. Это означает, что при изменении какого-либо атрибута в одном из PTE невозможно сделать то же самое для всех других PTE, ссылающихся на ту же страницу. Именно поэтому для совместно используемых страниц применяется механизм прототипов элементов таблицы страниц (Prototype Page Table Entry). Для совместно используемых страниц создается прототип PTE, который и содержит актуальные атрибуты страницы. Все PTE, принадлежащие различным процессам, ссылаются не на саму страницу, а на этот прототип, атрибуты которого и являются актуальными (рис. 3).

Рисунок 3.
Совместное использование страниц процессами

Сам прототип хранится в старших адресах каждого процесса. Общий размер памяти, отводимый для хранения прототипов, не превышает 8 Мбайт.

Отложенное копирование

Все гениальное — просто. Многие программисты получили истинное наслаждение, впервые ознакомившись с тем, как изящно в Unix реализовано порождение процессов. В результате исполнения системного вызова fork(), призванного создавать новые процессы, два независимых процесса начинают совместно использовать одну и ту же область кода. Прошло немало времени, прежде чем пытливая инженерная мысль нашла возможность совместно использовать одну и ту же область данных. Действительно, нет необходимости каждому процессу иметь отдельный экземпляр данных, если эти данные только читаются. Проблема состоит в том, как определить, будут ли данные читаться в будущем или нет. Неважно, области кода или данных принадлежит совместно используемая память. Существенно лишь то, производится или нет изменение данных процессами. Если процесс производит запись, он должен иметь свою отдельную копию изменяемых данных. Если же в записи нет необходимости, то он может совместно использовать данные с остальными процессами. Подобный подход называется отложенным копированием (lazy evaluation): решение о необходимости копирования страницы откладывается до того момента, когда процесс попытается что-либо записать в нее. Все страницы порожденного процесса защищаются от записи. При попытке изменения защищенной страницы возникает процессорное исключение, страница копируется системой, и только после этого в нее разрешается запись.

Данный механизм, едва появившись, сразу же стал классическим и сегодня является составной частью многих систем Unix. Нет ничего удивительного, что он изначально присутствует в архитектуре и более молодой системы Microsoft Windows NT. Наиболее активно он используется при работе различных процессов с совместно используемыми динамически загружаемыми библиотеками (DLL), а также при запуске программ.

Свопинг

Конечно, компьютер может и не иметь 4 Гбайт оперативной памяти, адресуемых процессорами Intel для того, чтобы обеспечить все линейное адресное пространство процесса физическими ячейками памяти. Windows NT, как и все другие операционные системы, применяет свопинг (swapping). Не используемые в конкретный момент страницы памяти могут быть вытеснены на диск в так называемый файл подкачки. В соответствующем элементе таблицы страниц эта страница помечается как отсутствующая, и при попытке обращения к ней возникает исключительная ситуация — «сбой» страницы. Обрабатывая ее, операционная система находит страницу на диске и переписывает ее в память, соответствующим образом подстраивая элемент таблицы страниц. После этого попытка выполнить команду, вызвавшую исключение, повторяется.

С понятием свопинга неразрывно связаны три стратегии: выборка (fetch), размещение (placement) и замещение (replacement).

• Выборка определяет, в какой момент необходимо переписать страницу с диска в память. В Windows NT используется классическая схема выборки с упреждением: система переписывает в память не только выбранную страницу, но и несколько следующих по принципу пространственной локальности, гласящему: наиболее вероятным является обращение к тем ячейкам памяти, которые находятся в непосредственной близости от ячейки, к которой производится обращение в настоящий момент. Поэтому вероятность того, что будут востребованы последовательные страницы, достаточна высока. Их упреждающая подкачка позволяет снизить накладные расходы, связанные с обработкой прерываний.
• Размещение определяет, в какое место оперативной памяти необходимо поместить подгружаемую страницу. Для систем со страничной организацией данная стратегия практически не имеет никакого значения, и поэтому Windows NT выбирает первую попавшуюся свободную страницу.
• Замещение начинает действовать с того момента, когда в оперативной памяти компьютера не остается свободного места для размещения подгружаемой страницы. В этом случае необходимо решить, какую страницу вытеснить из физической памяти в файл подкачки. Можно было бы отделаться общими словами [6], сказав, что в данном случае Windows NT использует алгоритм FIFO: вытесняется страница, загруженная раньше всех, т. е. самая «старая». Однако механизм замещения настолько интересен, что заслуживает более пристального внимания, и мы еще расскажем о нем.

Несомненный теоретический интерес представляет тот факт, что Windows NT — это система, в которую включены средства динамического анализа рабочего множества процесса, которые используются при организации свопинга. Но обо всем по порядку.

Часть ядра Windows NT, которая занимается управлением виртуальной памятью, называется VMM — Virtual Memory Manager. Это независимый привилегированный процесс, постоянно находящийся в оперативной памяти компьютера. VMM поддерживает специальную структуру, называемую базой данных страниц (page-frame database). В ней содержатся элементы для каждой страницы. Состояние каждой страницы описывается с помощью следующих категорий:

Valid — страница используется процессом. Она реально существует в памяти и помечена в PTE как присутствующая.

Modified — содержимое страницы было изменено. В PTE страница помечена как отсутствующая (P=0) и переходная (T=1).

Standby — содержимое страницы не изменялось. В PTE страница помечена как отсутствующая (P=0) и переходная (T=1).

Free — страница, на которую не ссылается ни один PTE. Страница свободна, но подлежит обнулению, прежде чем будет использована.

Zeroed — свободная и обнуленная страница, пригодная к непосредственному использованию любым процессом.

Bad — страница, которая вызывает аппаратные ошибки и не может быть использована ни одним процессом.

Все состояния, за исключением Modified и Standby, можно обнаружить в большинстве операционных систем. Страница, находящаяся в одном из этих состояний, реально располагается в памяти, в PTE содержится ее реальный адрес, но сама страница помечена как отсутствующая. При обращении к этой странице возникает аппаратное исключение, однако его обработка не вызывает больших временных затрат. Необходимо просто пометить страницу как присутствующую (Valid, P=1) и еще раз запустить последнюю команду.

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

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

Важнейшее понятие при организации свопинга — рабочее множество процесса (working set). В соответствии с принципом локальности процесс не использует всю память одновременно. Состав и количество страниц, с которыми процесс работает, меняется на протяжении его жизни. Страницы, с которыми процесс работает в течение фиксированного интервала времени, есть его рабочее множество на этом интервале. Переход от одного рабочего множества к другому осуществляется не равномерно, а скачками. Это вызвано семантикой процесса: переходами от обработки одного массива к обработке другого, от подпрограммы к подпрограмме, от цикла к циклу и т. д. Не нужно, чтобы в оперативной памяти размещались все страницы процесса, однако необходимо, чтобы в ней помещалось его рабочее множество. В противном случае возникает режим интенсивной подкачки, называемый трешингом (trashing), с которым сталкивается любой пользователь PC, запустивший одновременно слишком много приложений. В таком режиме затраты системы на переписывание страниц с диска в память и обратно значительно превышают время, выделяемое на полезную деятельность. Фактически система перестает заниматься чем-либо, кроме перемещения головок жесткого диска.

Теперь настало время разрешить интригу, которая возникла несколько абзацев назад, и подробно рассмотреть стратегию замещения страниц Windows NT. В классической теории операционных систем идеальной считается следующая стратегия: замещению подлежит страница, которая не будет использоваться в будущем дольше других. В той же классической теории эта стратегия признается неосуществимой, поскольку нет никакого разумного способа определить, какая из страниц подпадает под этот критерий. К счастью, в мире еще есть инженеры, готовые ломать голову над неосуществимыми идеями. Программистам Microsoft удалось приблизиться к этой стратегии на основе анализа рабочего множества процесса. В Windows NT используется весьма близкая стратегия: из памяти вытесняются страницы, вышедшие из рабочего множества процесса. Как же VMM узнает, какие страницы больше не принадлежат рабочему множеству? А очень просто! Периодически VMM просматривает список страниц с атрибутом Valid и пытается похитить их у процесса. Он помечает их как отсутствующие (P=0), но на самом деле оставляет их на месте, только переводит в разряд Modified или Standby в зависимости от значения бита D из PTE. Если похищенная страница принадлежит рабочему множеству, то к ней в ближайшее время произойдет обращение. Это, конечно, вызовет исключение — ведь страница-то помечена как отсутствующая. Но VMM очень быстро сделает эту страницу вновь доступной процессу, поскольку она реально находится в памяти. Если страница находится вне рабочего множества, то обращений к ней не будет и она со временем перейдет в разряд Free, а затем Zeroed и станет доступна другим процессам системы.

Адресное пространство процесса

В Windows NT используется плоская (flat) модель памяти. Каждому процессу выделяется «личное» изолированное адресное пространство. На 32-разрядных компьютерах размер этого пространства составляет 4 Гбайт и может быть расширен до 32 Гбайт при работе Windows NT 5.0 на процессоре Alpha. Это пространство разбивается на регионы, различные для разных версий системы (рис. 5).

В Windows NT 4.0 младшие 2 Гбайт памяти выделяются процессу для произвольного использования, а старшие 2 Гбайт резервируются и используются операционной системой. В младшую часть адресного пространства помещаются и некоторые системные динамически связываемые библиотеки (DLL). Желание расширить доступное процессу адресное пространство привело к тому, что Windows NT 4.0 Enterprise процессу выделяется дополнительный 1 Гбайт за счет сокращения системной области (рис. 5).

Разработчики Windows NT 5.0 для платформы Alpha пошли дальше. Alpha — 64-разрядный процессор, но под управлением Windows NT версии до 4.0 включительно в его адресном пространстве используются только 2 Гбайт старших и 2 Гбайт младших адресов (рис. 5).

Дело в том, что в Win32 API для хранения адреса используются 32-разрядные переменные. Windows NT расширяет их до 64-разрядных с учетом знака. Спецификация VLM (Very Large Memory), которая будет реализована в Windows NT 5.0 для процессора Alpha, подразумевает использование 64-разрядных переменных для хранения адресов (рис. 5).

Если системе, которую вы разрабатываете, недостаточно для работы 32 Гбайт физической памяти, то, вероятно, вам стоит выбрать другую операционную систему. Если же вы готовы потесниться и произвести некоторую оптимизацию своего кода, то, возможно, вам подойдет и Windows NT.