Entry tags:

программинг

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

Вам не повезло. Или наоборот -- повезло. Как посмотреть. В общем, тему защищённого режима x86 я знаю довольно туго. Поэтому получилось длинно, подробно и с кучей ссылок свои на собственные статьи :) Вот только код пока заленился писать. Придётся, конечно, но чуть позже.

Разбил на две части, иначе как-то многовато, слишком высока вероятность, что не прочитает никто :)

Intel x86 (32-битные)

Про устройство памяти в защищённом режиме Intel x86 с отключенной страничной адресацией я подробно писал тут.

Внимательный читатель мог заметить, что я переполз на народ-ру. Это связано с тем, что писем-нет сошёл с ума. Переполз буквально недавно, пока частично и коряво. Когда-нибудь (ха-ха) сделаю это менее коряво. А ещё мне хочется всё нафиг переписать, но тоже, видимо, чуть позже.

Кратко напомню основные тезисы.

• Адрес, выставляемый процессором на системную шину называется физическим. В рассматриваемой серии Intel x86 максимум -- 36-и разрядов. Для краткости "физическое адресное пространство" я буду по бытовому называть "ОЗУ".


• Адреса, которые используют прикладные программисты -- логические, имеют форму <сегмент>:<смещение>. Смещение -- 32 разряда.


• Логические адреса преобразуются в линейные, по формуле <база сегмента> + <смещение>. В типичной современной ОС базы типичных сегментов -- 0 (могут быть специальные сегменты, например сегмент FS в Windows NT). Линейный адрес тоже ограничен 32-я разрядами (да, действительно можно устроить переполнение).


• Линейные адреса преобразуются в физические. Если страничная адресация отключена, то <физический> = <линейный>. Если включена, то начинается то, ради чего мы тут собрались :)

Итак, табличная адресация включена.

Для этого нужно всего лишь установить в 1 31-й бит регистра CR0; бит называется PG, от слова paging.

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

Важно, обратите внимание! Если явно не оговорено обратное, то все выполняет процессор, незаметно не только для прикладного программиста, но и для ОС! Т.е. все ужасные структуры с битовыми полями, которые появятся далее -- это не разработчики какой-то ОС придумали, это придумали в Intel и это поддерживается процессором напрямую. ОС должна эти структуры правильно сформировать, и немного помогать по ходу, но в основном оно само.

Таблички

Вот как-то так:



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

Что тут нарисовано в общих чертах:

• 32-х разрядный линейный адрес разбивается на три части.


• Первая часть -- старшие десять разрядов -- используются для поиска записи в каталоге страниц (page directory; запись называется PDE, page directory entry ). Найденная запись указывает нужную таблицу страниц (page table).


• Вторая часть линейного адреса -- следующие десять разрядов -- используется для поиска записи в таблице страниц (PTE, page table entry). Найденная запись указывает на нужную страницу.


• Третья часть линейного адреса -- оставшиеся 12 бит -- это смещение в рамках найденной страницы.


• А начало каталога страниц хранится в регистре CR3 (PDBR это просто Page Directory Base Register).

И ещё несколько деталей:

• На смещение нам дано 12 бит, значит размер страницы -- 4 Кб. Как там и написано.


• PTE ссылается на страницу при помощи чего-то 20-и разрядного. Это старшие 20 разрядов 32-х разрядного физического адреса. Да, пока мы не вышли за рамки 4 Гб.


• Младшие 12 бит физического адреса страницы всегда нули, значит страница выровнена по границе 4 Кб.

Записи

Формат PDE и PTE очень похож. И там и там есть куча ненужных полей, которые мы сейчас рассматривать не будем. А некоторые не будем и потом.

• Размер PTE и PDE -- по 4 байта. Значит размер каталога страниц и таблицы страниц тоже 4 Кб. Очень удобно.


• Главное, что есть в PTE и PDE это нулевой бит -- флаг Present (P). Строго говоря, картинку надо было бы озаглавить "формат PTE и PDE в предположении, что P равен 1". Потому что если он сброшен в 0, на формат остальной части нет никаких ограничений. Если флаг P установлен, процессор считает, что формат правильный и "сущность следующего уровня" в памяти есть, и можно к ней обратиться. Если же P сброшен, то при попытке использовать такую PDE/PTE будет выброшено исключение #PF (page fault).


• Ели P установлен, то на втором месте по значимости Хxx Base Address. Это старшие 20 бит физического адреса "сущности следующего уровня" -- страницы или таблицы страниц. Соответственно, таблицы страниц тоже выровнены по границе 4 Кб. Да вообще-то и каталог страниц тоже должен быть выровнен так же.


• Accessed (A) -- очень полезный флаг. Процессор устанавливает его в 1, каждый раз, когда PDE/PTE используется для поиска страницы. Это позволяет определить редко используемые страницы. Подробнее об этом будет ниже.


• Dirty (D) -- ещё один полезный флаг. Автоматически устанавливается процессором в 1 при записи на страницу. Так ОС может найти страницы, которые менялись "с последнего раза". Подробнее тоже будет ниже.

Для расширения сознания два флага, смещающих функциональность механизма в сторону от простой переадресации:

• Флаг Read/write (R/W) разрешает/запрещает запись на страницу/страницы. 0 -- только чтение, 1 -- чтение и запись.


• Флаг User/Supervisor (U/S) разрешает/запрещает доступ пользовательского кода к странице/страницам. 0 -- пользователям нельзя, только для ОС, 1 -- можно всем. Пользователем считается код с CPL 3, ОС -- все остальные (про уровни привилегий рассказывать долго, было тут).

И два бесполезных, но зато самых понятных поля:

• Available -- ОС может использовать эти биты в меру своей испорченности. Пометки какие на память, али ещё чего..


• Reserved (0) -- должен быть 0.

А всё, что серенькое -- пока мысленно заполняйте нулями, не ошибётесь :)

Исключение #PF

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

Именно этой цели служит исключение #PF. Про исключения можно писать много, я уже даже писал тут, так что ограничусь кратким ТТХ:

• Номер -- 14


• Тип -- fault. Т.е. по умолчанию после возврата управления, привёдшая к исключению инструкция процессора начинает выполняться заново.


• Код ошибки есть. Для тех, кто в курсе про реальный режим, но не в курсе про защищённый: некоторые исключения теперь принимают в стеке параметр, 4 байтный "код ошибки". Формат у каждого исключения свой; формат для #PF описан чуть ниже.


• В регистре CR2 сохранён линейный адрес, который не удалось преобразовать в физический. Следствие: если обработчик #PF может привести к повторному выбросу #PF, нужно где-то сохранить этот адрес или быть готовым к его потере, т.к. CR2 будет перезаписан.

Ну и код ошибки:

• P. Если 0, то проблема в PDE или PTE, сигнализирующей об отсутствующей таблице/странице. Если 1, то дело в чём-то другом. Возможно, в безопасности: флажки R/W и U/S в PDE и PTE.


• R/W. Если 0, это была попытка чтения, если 1 -- записи.


• U/S. Если 0, процессор был в "режиме супервизора" (CPL = 0,1,2), если 1 -- пользователя (CPL = 3).

Как это работает

Инициализация:

• ОС формирует страничный каталог и хотя бы одну таблицу страниц. Хотя бы одна нужна -- после включения страничной адресации вся адресация будет проходить через этот адский механизм, даже поиск следующей выполняемой инструкции. И, конечно, вызов обработчиков прерываний/исключений, включая обработчик #PF.


• Заносит физический адрес каталога страниц в CR3 и включает страничную адресацию.


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

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

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


• Кстати, несложно заметить, что на 4 Гб нужно 1024 * 4 Кб == 4 Мб места на одни только таблицы страниц. Создавая не все сразу, а только нужные, можно неплохо сэкономить.


• Ещё можно сэкономить на общих таблицах. Каталог страниц должен быть у каждого свой, тут никуда не деться, но часть таблиц можно разделять между несколькими процессами. Например, в Windows NT старшие 2 Гб (пространство ядра) скорее всего у всех общие на уровне таблиц страниц.

Когда количество свободных страниц в ОЗУ сокращается ниже определённого предела, ОС запускает процесс сброса неиспользуемых страниц на диск.

• Обычно его изображают как часы с двумя минутными стрелками, сдвинутыми минут на 20 :)


• Первая стрелка проходит по всем каталогам и таблицам страниц в системе и сбрасывает у всех флаг Accessed


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


• Если флаг Accessed сброшен, страница считается редко используемой и ставится в очередь на сброс на диск.


• В процессе сброса на диск играет роль флаг Dirty. Если на диске уже есть копия страницы (с прошлого раза), и флаг Dirty сброшен, то копия в памяти не менялась, её можно просто удалить. Если флаг Dirty установлен, нужно сохранить изменённую версию.


• Сбрасываемую страницу следует пометить сброшенным флагом Present. В остальной части PTE можно записать что-нибудь о том, где она лежит.


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

Если страницы нет в памяти:

• У неё сброшен флаг Present, значит обращение к ней вызовет исключение #PF


• Обработчик исключения находит в памяти свободную страницу, подкачивает туда данные с диска и обновляет PTE.


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

Кэш

Давайте прикинем. На каждую операцию преобразования адреса нужно:

• Обратиться в память по адресу CR3 + <старшие 10 бит> * 4, прочитать оттуда PDE


• Обратиться в память по адресу <адрес таблицы страниц> + <средние 10 бит> * 4, прочитать PTE

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

В таких ситуациях главного инженера спасает яд кэш. В данном случае он называется Translate Lookaside Buffer (TLB), и в нём хранятся данные о наиболее часто используемых страницах. В Intel x86 TLB появился одновременно с обычным кэшем, начиная с 486-го процессора. Доступные механизмы управления TLB:

• При перезаписи CR3 (обычно это происходит при переключении задач) содержимое TLB сбрасывается.


• Инструкция invlpg m удаляет из TLB информацию о странице, содержащей адрес m. Доступна только при CPL=0. Предназначена для решения проблемы синхронизации кэша: при удалении страницы из памяти, ОС должна удалять её и из TLB.

Возможности добавить чего-нибудь в TLB нет.

---

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