[Перевод] Пишем операционную систему на Rust. Реализация страничной памяти (новый вариант)28.03.2019 00:04

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

Этот цикл статей опубликован выложен на GitHub. Если у вас какие-то вопросы или проблемы, открывайте там соответствующий тикет. Все исходники для статьи лежат в этой ветке.

Ещё одна статья о страничной организации памяти?
Если вы следите за этим циклом, то видели статью «Страничная память: продвинутый уровень» в конце января. Но меня раскритиковали за рекурсивные таблицы страниц. Поэтому решил переписать статью, применив иной подход для доступа к фреймам.
Здесь представлен новый вариант. Статья по-прежнему объясняет, как работают рекурсивные таблицы страниц, но мы используем более простую и мощную реализацию. Предыдущую статью удалять не будем, но пометим её как устаревшую и не будем обновлять.

Надеюсь, новый вариант вам понравится!

Из прошлой статьи мы узнали о принципах страничной организации памяти и о том, как работают четырёхуровневые страничные таблицы на x86_64. Мы также обнаружили, что загрузчик уже настроил иерархию таблиц страниц для нашего ядра, поэтому ядро работает на виртуальных адресах. Это повышает безопасность, так как несанкционированный доступ к памяти вызывает page fault вместо произвольного изменения физической памяти.

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

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

Обновления зависимостей

Эта статья требует прописать в зависимостях bootloader версии 0.4.0 или выше и x86_64 версии 0.5.2 или выше. Можете обновить зависимости в Cargo.toml:

[dependencies]
bootloader = "0.4.0"
x86_64 = "0.5.2"

Изменения в этих версиях см. в журнале bootloader и в журнале x86_64.
Доступ к таблицам страниц из ядра не так прост, как может показаться. Чтобы понять проблему, ещё раз взглянем на четырёхуровневую иерархию таблиц из предыдущей статьи:

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

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

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

Тождественное отображение

Простое решение — тождественное отображение всех таблиц страниц.

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

Однако этот подход захламляет виртуальное адресное пространство и мешает найти большие непрерывные области свободной памяти. Скажем, мы хотим создать область виртуальной памяти размером 1000 КиБ на приведённом выше рисунке, например, для отображения файла в памяти. Мы не можем начать с региона 28  KiB, потому что он упрётся в уже занятую страницу на 1004  KiB. Поэтому придётся искать дальше, пока не встретим подходящий большой фрагмент, например, с 1008  KiB. Возникает та же проблема фрагментации, как и в сегментированной памяти.

Кроме того, создание новых таблиц страниц значительно усложняется, поскольку нам необходимо найти физические фреймы, соответствующие страницы которых еще не используются. Например, для нашего файла мы зарезервировали область 1000 КиБ виртуальной памяти, начиная с адреса 1008  KiB. Теперь мы больше не можем использовать ни один фрейм с физическим адресом между 1000  KiB и 2008  KiB, потому что его не получится тождественно отобразить.

Карта с фиксированным смещением

Чтобы избежать загромождения виртуального адресного пространства, можно отображать таблицы страниц в отдельной области памяти. Поэтому вместо тождественного отображения мы сопоставляем фреймы с фиксированным смещением в виртуальном адресном пространстве. Например, смещение может составлять 10 ТиБ:

Выделив этот диапазон виртуальной памяти чисто для отображения таблиц страниц мы избежим проблем тождественного отображения. Резервирование такой большой области виртуального адресного пространства возможно только в том случае, если виртуальное адресное пространство намного больше размера физической памяти. В x86_64 это не проблема, потому что 48-битное адресное пространство составляет 256 ТиБ.

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

Отображение полной физической памяти

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

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

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

Однако на x86_64 мы можем использовать для отображения огромные страницы по 2 МиБ вместо размера по умолчанию 4 КиБ. Таким образом, для отображения 32 ГиБ физической памяти требуется всего 132 КиБ на таблицы страниц: только одна таблица третьего уровня и 32 таблицы второго уровня. Огромные страницы также более эффективно кэшируются, поскольку используют меньше записей в буфере динамической трансляции (TLB).

Временное отображение

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

На этом рисунке таблица уровня 1 управляет первыми 2 МиБ виртуального адресного пространства. Такое возможно, потому что доступ осуществляется из регистра CR3 через нулевые записи в таблицах уровней 4, 3 и 2. Запись с индексом 8 транслирует виртуальную страницу по адресу 32 KiB в физический фрейм по адресу 32 KiB, тем самым тождественно отображая саму таблицу уровня 1. На рисунке это показано горизонтальной стрелкой.

Путём записи в тождественно отображённую таблицу уровня 1 наше ядро может создать до 511 временных сопоставлений (512 минус запись, необходимая для тождественного отображения). В приведённом примере ядро создаёт два временных сопоставления:

• Сопоставление нулевой записи таблицы уровня 1 с фреймом по адресу 24 KiB. Это создаёт временное сопоставление виртуальной страницы по адресу 0 KiB с физическим фреймом таблицы страниц уровня 2, обозначенным пунктирной стрелкой.
• Сопоставление 9-й записи таблицы уровня 1 с фреймом по адресу 4 KiB. Это создаёт временное сопоставление виртуальной страницы по адресу 36 KiB с физическим фреймом таблицы страниц уровня 4, обозначенным пунктирной стрелкой.

Теперь ядро может получить доступ к таблице уровня 2 путём записи в страницу, которая начинается по адресу 0 KiB и к таблице уровня 4 путём записи в страницу, которая начинается по адресу 33 KiB.

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

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

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

Рекурсивные таблицы страниц

Ещё один интересный подход, который вообще не требует дополнительных таблиц страниц, — это рекурсивное сопоставление.

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

Рассмотрим пример, чтобы понять, как это всё работает:

Единственное отличие от примера в начале статьи — это дополнительная запись с индексом 511 в таблице уровня 4, которая сопоставляется с физическим фреймом 4 KiB, который находится в самой этой таблице.

Когда CPU идёт по этой записи, то обращается не к таблице уровня 3, а опять обращается к таблице уровня 4. Это похоже на рекурсивную функцию, которая вызывает сама себя. Важно, что процессор предполагает, что каждая запись в таблице уровня 4 указывает на таблицу уровня 3, поэтому теперь он обрабатывает таблицу уровня 4 как таблицу уровня 3. Это работает, потому что у таблиц всех уровней в x86_64 одинаковая структура.

Следуя рекурсивной записи один или несколько раз, прежде чем начать фактическое преобразование, мы можем эффективно сократить количество уровней, которые проходит процессор. Например, если мы следуем за рекурсивной записью один раз, а затем переходим к таблице уровня 3, процессор думает, что таблица уровня 3 является таблицей уровня 2. Идя дальше, он рассматривает таблицу уровня 2 как таблицу уровня 1, а таблицу уровня 1 как сопоставленный фрейм в физической памяти. Это означает, что теперь мы можем читать и писать в таблицу страниц уровня 1, потому что процессор думает, что это сопоставленный фрейм. На рисунке ниже показаны пять шагов такой трансляции:

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

Пройдёмся по этой процедуре шаг за шагом. Сначала CPU следует рекурсивной записи в таблице уровня 4 и думает, что достиг таблицы уровня 3. Затем снова следует по рекурсивной записи и думает, что достиг уровня 2. Но на самом деле он все ещё находится на уровне 4. Затем CPU идёт по новому адресу и попадает в таблицу уровня 3, но думает, что уже находится в таблице уровня 1. Наконец, на следующей точке входа в таблице уровня 2 процессор думает, что обратился к фрейму физической памяти. Это позволяет нам нам читать и писать в таблицу уровня 2.

Так же происходит доступ к таблицам уровней 3 и 4. Для доступа к таблице уровня 3 мы трижды следуем рекурсивной записи: процессор думает, что уже находится в таблице уровня 1, а на следующем шаге мы достигаем уровня 3, который CPU рассматривает как сопоставленный фрейм. Для доступа к самой таблице уровня 4 мы просто следуем рекурсивной записи четыре раза, пока процессор не обработает саму таблицу уровня 4 как отображённый фрейм (синим цветом на рисунке ниже).

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

Вычисление адреса

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

Предположим, что мы хотим получить доступ к таблице уровня 1, отображающей определённую страницу. Как мы узнали выше, нужно один раз пройти по рекурсивной записи, а затем по индексам 4-го, 3-го и 2-го уровней. Для этого мы перемещаем все блоки адресов на один блок вправо и устанавливаем индекс рекурсивной записи на место исходного индекса уровня 4:

Для доступа к таблице уровня 2 этой страницы мы перемещаем все блоки индексов на два блока вправо и устанавливаем рекурсивный индекс на место обоих исходных блоков: уровня 4 и уровня 3:

Для доступа к таблице уровня 3 делаем то же самое, только смещаем вправо уже три блока адресов.

Наконец, для доступа к таблице уровня 4 смещаем всё на четыре блока вправо.

Теперь можно вычислить виртуальные адреса для таблиц страниц всех четырёх уровней. Мы даже можем вычислить адрес, который точно указывает на конкретную запись таблицы страниц, умножив её индекс на 8, размер записи таблицы страниц.

В таблице ниже приведена структура адресов для доступа к различным типам фреймов:

Виртуальный адрес для	Структура адреса (восьмеричная)
Страница	0o_SSSSSS_AAA_BBB_CCC_DDD_EEEE
Запись в таблице уровня 1	0o_SSSSSS_RRR_AAA_BBB_CCC_DDDD
Запись в таблице уровня 2	0o_SSSSSS_RRR_RRR_AAA_BBB_CCCC
Запись в таблице уровня 3	0o_SSSSSS_RRR_RRR_RRR_AAA_BBBB
Запись в таблице уровня 4	0o_SSSSSS_RRR_RRR_RRR_RRR_AAAA

Здесь ААА — индекс уровня 4, ВВВ — уровня 3, ССС — уровня 2, а DDD — индекс уровня 1 для отображённого фрейма, EEEE — его смещение. RRR — индекс рекурсивной записи. Индекс (три цифры) преобразуется в смещение (четыре цифры) путём умножения на 8 (размер записи таблицы страниц). При таком смещении результирующий адрес напрямую указывает на соответствующую запись таблицы страниц.

SSSS — биты расширения знакового разряда, то есть все они копии бита 47. Это специальное требование для допустимых адресов в архитектуре x86_64, что мы обсуждали в предыдущей статье.

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

Код Rust

Cконструировать такие адреса в коде Rust можно с помощью побитовых операций:

// the virtual address whose corresponding page tables you want to access
let addr: usize = […];

let r = 0o777; // recursive index
let sign = 0o177777 << 48; // sign extension

// retrieve the page table indices of the address that we want to translate
let l4_idx = (addr >> 39) & 0o777; // level 4 index
let l3_idx = (addr >> 30) & 0o777; // level 3 index
let l2_idx = (addr >> 21) & 0o777; // level 2 index
let l1_idx = (addr >> 12) & 0o777; // level 1 index
let page_offset = addr & 0o7777;

// calculate the table addresses
let level_4_table_addr =
    sign | (r << 39) | (r << 30) | (r << 21) | (r << 12);
let level_3_table_addr =
    sign | (r << 39) | (r << 30) | (r << 21) | (l4_idx << 12);
let level_2_table_addr =
    sign | (r << 39) | (r << 30) | (l4_idx << 21) | (l3_idx << 12);
let level_1_table_addr =
    sign | (r << 39) | (l4_idx << 30) | (l3_idx << 21) | (l2_idx << 12);

Этот код предполагает рекурсивное отображение последней записи уровня 4 с индексом 0o777 (511) рекурсивно сопоставлена. В настоящее время это не так, поэтому код пока не будет работать. См. ниже о том, как сообщить загрузчику установить рекурсивное отображение.

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

// in src/memory.rs

use x86_64::structures::paging::{Mapper, Page, PageTable, RecursivePageTable};
use x86_64::{VirtAddr, PhysAddr};

/// Creates a RecursivePageTable instance from the level 4 address.
let level_4_table_addr = […];
let level_4_table_ptr = level_4_table_addr as *mut PageTable;
let recursive_page_table = unsafe {
    let level_4_table = &mut *level_4_table_ptr;
    RecursivePageTable::new(level_4_table).unwrap();
}


/// Retrieve the physical address for the given virtual address
let addr: u64 = […]
let addr = VirtAddr::new(addr);
let page: Page = Page::containing_address(addr);

// perform the translation
let frame = recursive_page_table.translate_page(page);
frame.map(|frame| frame.start_address() + u64::from(addr.page_offset()))

Опять же, для этого кода требуется правильное рекурсивное отображение. При таком отображении недостающий level_4_table_addr вычисляется как в первом примере кода.
Рекурсивное отображение — интересный метод, который показывает, насколько мощным может быть сопоставление через единственную таблицу. Его относительно легко реализовать и он требует лишь минимальной настройки (всего одна рекурсивная запись), поэтому это хороший выбор для первых экспериментов.

Но у него есть и некоторые недостатки:

• Большой объём виртуальной памяти (512 ГиБ). Это не проблема в большом 48-битном адресном пространстве, но может привести к неоптимальному поведению кэша.
  
• Он легко даёт доступ только к активному в данный момент адресному пространству. Доступ к другим адресным пространствам по-прежнему возможен путём изменения рекурсивной записи, но для переключения требуется временное сопоставление. Мы описали, как это сделать, в прошлой (устаревшей) статье.
  
• Сильно зависит от формата таблицы страниц x86 и может не работать на других архитектурах.

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

Значит, нужна помощь загрузчика. У него есть доступ к таблицам страниц, поэтому он может создавать любые отображения, которые нам нужны. В своей текущей реализации крейт bootloader поддерживает два вышеупомянутых подхода с помощью функций cargo:

• Функция map_physical_memory отображает полную физическую память где-то в виртуальном адресном пространстве. Таким образом, ядро получает доступ ко всей физической памяти и может применить подход с отображением полной физической памяти.
  
• С помощью функции recursive_page_table загрузчик рекурсивно отображает запись таблицы страниц четвёртого уровня. Это позволяет ядру работать по методу, описанному в разделе «Рекурсивные таблицы страниц».

Для нашего ядра мы выбираем первый вариант, потому что это простой, независимый от платформы и более мощный подход (он также даёт доступ к остальным фреймам, не только к таблицам страниц). Для поддержки со стороны загрузчика добавляем в его зависимости функцию map_physical_memory:

[dependencies]
bootloader = { version = "0.4.0", features = ["map_physical_memory"]}

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

Загрузочная информация

Крейт bootloader определяет структуру BootInfo со всей информацией, передаваемой ядру. Структура ещё дорабатывается, поэтому возможны некоторые сбои при обновлении до будущих версий, несовместимых с semver. В настоящее время в структуре два поля: memory_map и physical_memory_offset:

• Поле memory_map содержит обзор доступной физической памяти. Оно говорит ядру, сколько физической памяти доступно в системе и какие области памяти зарезервированы для устройств, таких как VGA. Карту памяти можно запросить из прошивки BIOS или UEFI, но только в самом начале процесса загрузки. По этой причине её должен предоставлять загрузчик, потому что потом ядро уже не сможет получить эту информацию. Карта памяти пригодится нам позже в этой статье.
  
• physical_memory_offset сообщает виртуальный начальный адрес отображения физической памяти. Добавив это смещение к физическому адресу, мы получаем соответствующий виртуальный адрес. Это даёт доступ из ядра к произвольной физической памяти.

Загрузчик передаёт ядру структуру BootInfo в виде аргумента &'static BootInfo к функции _start. Добавим его:

// in src/main.rs

use bootloader::BootInfo;

#[cfg(not(test))]
#[no_mangle]
pub extern "C" fn _start(boot_info: &'static BootInfo) -> ! { // new argument
    […]
}

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

Макрос точки входа

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

Чтобы убедиться, что у функция точки входа всегда правильная сигнатура, крейт bootloader предоставляет макрос entry_point. Перепишем нашу функцию с использованием этого макроса:

// in src/main.rs

use bootloader::{BootInfo, entry_point};

entry_point!(kernel_main);

#[cfg(not(test))]
fn kernel_main(boot_info: &'static BootInfo) -> ! {
    […]
}

Больше не нужно использовать для точки входа extern "C" или no_mangle, так как макрос определяет для нас реальную точку входа нижнего уровня _start. Функция kernel_main теперь стала полностью нормальной функцией Rust, поэтому мы можем выбрать для неё произвольное имя. Важно то, что он проверяется по типу, так что если использовать неправильную сигнатуру, например, путём добавления аргумента или изменения его типа, то возникнет ошибка компиляции
Теперь у нас есть доступ к физической памяти и можно, наконец, начать реализацию системы. Во-первых, рассмотрим текущие активные таблицы страниц, на которых работает ядро. На втором шаге создадим функцию трансляции, которая возвращает физический адрес, которому сопоставлен данный виртуальный адрес. На последнем шаге попытаемся изменить таблицы страниц, чтобы создать новое сопоставление.

Для начала создадим в коде новый модуль memory:

// in src/lib.rs

pub mod memory;

Для модуля создаем пустой файл src/memory.rs.

Доступ к таблицам страниц

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

// in src/memory.rs

use x86_64::structures::paging::PageTable;

/// Returns a mutable reference to the active level 4 table.
///
/// This function is unsafe because the caller must guarantee that the
/// complete physical memory is mapped to virtual memory at the passed
/// `physical_memory_offset`. Also, this function must be only called once
/// to avoid aliasing `&mut` references (which is undefined behavior).
pub unsafe fn active_level_4_table(physical_memory_offset: u64)
    -> &'static mut PageTable
{
    use x86_64::{registers::control::Cr3, VirtAddr};

    let (level_4_table_frame, _) = Cr3::read();

    let phys = level_4_table_frame.start_address();
    let virt = VirtAddr::new(phys.as_u64() + physical_memory_offset);
    let page_table_ptr: *mut PageTable = virt.as_mut_ptr();

    &mut *page_table_ptr // unsafe
}

Сначала считываем физический фрейм активной таблицы 4-го уровня из регистра CR3. Затем берём его физический начальный адрес и преобразуем в виртуальный адрес, добавив physical_memory_offset. Наконец, преобразуем адрес в сырой указатель *mut PageTable методом as_mut_ptr, а затем небезопасно создаём из него ссылку &mut PageTable. Мы создаём ссылку &mut вместо &, потому что мы позже в статье будем изменять эти таблицы страниц.

Здесь не нужно вставлять блок unsafe, потому что Rust расценивает всё тело unsafe fn как один большой небезопасный блок. Это повышает риски, потому что можно случайно ввести небезопасную операцию в предыдущих строках. Это также значительно затрудняет обнаружение небезопасных операций. Уже создан RFC для изменения такого поведения Rust.

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

// in src/main.rs

#[cfg(not(test))]
fn kernel_main(boot_info: &'static BootInfo) -> ! {
    […] // initialize GDT, IDT, PICS

    use blog_os::memory::active_level_4_table;

    let l4_table = unsafe {
        active_level_4_table(boot_info.physical_memory_offset)
    };
    for (i, entry) in l4_table.iter().enumerate() {
        if !entry.is_unused() {
            println!("L4 Entry {}: {:?}", i, entry);
        }
    }

    println!("It did not crash!");
    blog_os::hlt_loop();
}

В качестве physical_memory_offset передаём соответствующее поле структуры BootInfo. Затем используем функцию iter для итерации по записям таблицы страниц и комбинатор enumerate для добавления индекса i к каждому элементу. Выводим только непустые записи, потому что все 512 записей не поместятся на экране.

Когда мы запускаем код, то видим такой результат:

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

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

// in the for loop in src/main.rs

use x86_64::{structures::paging::PageTable, VirtAddr};

if !entry.is_unused() {
    println!("L4 Entry {}: {:?}", i, entry);

    // get the physical address from the entry and convert it
    let phys = entry.frame().unwrap().start_address();
    let virt = phys.as_u64() + boot_info.physical_memory_offset;
    let ptr = VirtAddr::new(virt).as_mut_ptr();
    let l3_table: &PageTable = unsafe { &*ptr };

    // print non-empty entries of the level 3 table
    for (i, entry) in l3_table.iter().enumerate() {
        if !entry.is_unused() {
            println!("  L3 Entry {}: {:?}", i, entry);
        }
    }
}

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

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

Трансляция адресов

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

// in src/memory.rs

use x86_64::{PhysAddr, VirtAddr};

/// Translates the given virtual address to the mapped physical address, or
/// `None` if the address is not mapped.
///
/// This function is unsafe because the caller must guarantee that the
/// complete physical memory is mapped to virtual memory at the passed
/// `physical_memory_offset`.
pub unsafe fn translate_addr(addr: VirtAddr, physical_memory_offset: u64)
    -> Option
{
    translate_addr_inner(addr, physical_memory_offset)
}

Мы ссылаемся на безопасную функцию translate_addr_inner, чтобы ограничить объёма небезопасного кода. Как отмечалось выше, Rust расценивает всё тело unsafe fn как большой небезопасный блок. Вызывая одну безопасную функцию, мы снова делаем явной каждую операцию unsafe.

У специальной внутренней функции есть реальная функциональность:

// in src/memory.rs

/// Private function that is called by `translate_addr`.
///
/// This function is safe to limit the scope of `unsafe` because Rust treats
/// the whole body of unsafe functions as an unsafe block. This function must
/// only be reachable through `unsafe fn` from outside of this module.
fn translate_addr_inner(addr: VirtAddr, physical_memory_offset: u64)
    -> Option
{
    use x86_64::structures::paging::page_table::FrameError;
    use x86_64::registers::control::Cr3;

    // read the active level 4 frame from the CR3 register
    let (level_4_table_frame, _) = Cr3::read();

    let table_indexes = [
        addr.p4_index(), addr.p3_index(), addr.p2_index(), addr.p1_index()
    ];
    let mut frame = level_4_table_frame;

    // traverse the multi-level page table
    for &index in &table_indexes {
        // convert the frame into a page table reference
        let virt = frame.start_address().as_u64() + physical_memory_offset;
        let table_ptr: *const PageTable = VirtAddr::new(virt).as_ptr();
        let table = unsafe {&*table_ptr};

        // read the page table entry and update `frame`
        let entry = &table[index];
        frame = match entry.frame() {
            Ok(frame) => frame,
            Err(FrameError::FrameNotPresent) => return None,
            Err(FrameError::HugeFrame) => panic!("huge pages not supported"),
        };
    }

    // calculate the physical address by adding the page offset
    Some(frame.start_address() + u64::from(addr.page_offset()))
}

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

Структура VirtAddr уже предоставляет методы для вычисления индексов в таблицах страниц четырёх уровней. Мы храним эти индексы в небольшом массиве, потому что это позволяет проходить по всем таблицам с помощью цикла for. Вне цикла запоминаем последний посещённый фрейм, чтобы позже вычислить физический адрес. frame указывает на фреймы таблицы страниц во время итерации и на сопоставленный фрейм после последней итерации, т. е. после прохождения записи уровня 1.

Внутри цикла мы снова применяем physical_memory_offset для преобразования фрейма в ссылку на таблицу страниц. Затем читаем запись текущей таблицы страниц и используем функцию PageTableEntry::frame для извлечения сопоставленного кадра. Если запись не сопоставлена с кадром, возвращаем None. Если запись отображает огромную страницу 2 МиБ или 1 ГиБ, пока что у нас будет паника.

Итак, проверим функцию трансляции на некоторых адресах:

// in src/main.rs

#[cfg(not(test))]
fn kernel_main(boot_info: &'static BootInfo) -> ! {
    […] // initialize GDT, IDT, PICS

    use blog_os::memory::translate_addr;
    use x86_64::VirtAddr;

    let addresses = [
        // the identity-mapped vga buffer page
        0xb8000,
        // some code page
        0x20010a,
        // some stack page
        0x57ac_001f_fe48,
        // virtual address mapped to physical address 0
        boot_info.physical_memory_offset,
    ];

    for &address in &addresses {
        let virt = VirtAddr::new(address);
        let phys = unsafe {
            translate_addr(virt, boot_info.physical_memory_offset)
        };
        println!("{:?} -> {:?}", virt, phys);
    }

    println!("It did not crash!");
    blog_os::hlt_loop();
}

Когда мы запускаем код, получаем такой результат:

Как и ожидалось, при тождественном отображении адрес 0xb8000 преобразуется в тот же физический адрес. Кодовая страница и страница стека преобразуются в произвольные физические адреса, которые зависят от того, как загрузчик создал начальное сопоставление для нашего ядра. Сопоставление physical_memory_offset должно указывать на физический адрес 0, но терпит неудачу, потому что в трансляции для эффективности используются огромные страницы. Будущая версия загрузчика может применить ту же оптимизацию для страниц ядра и стека.

Использование MappedPageTable

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

Основа абстракции — два трейта, которые определяют различные функции трансляции таблицы страниц:

• Трейт Mapper предоставляет функции, работающие на страницах. Например, translate_page для трансляции данной страницы во фрейм того же размера, а также map_to для создания в таблице нового сопоставления.
  
• Трейт MapperAllSizes подразумевает применение Mapper для всех размеров страниц. Кроме того, он предоставляет функции, которые работают со страницами разного размера, в том числе translate_addr или общий translate.

Трейты определяют только интерфейс, но не обеспечивают никакой реализации. Сейчас крейт x86_64 предоставляет два типа, реализующих трейты: MappedPageTable и RecursivePageTable. Первый требует, чтобы каждый фрейм таблицы страниц куда-то отображался (например, со смещением). Второй тип можно использовать, если таблица четвёртого уровня отображается рекурсивно.

У нас вся физическая память отображается в physical_memory_offset, поэтому можно использовать тип MappedPageTable. Чтобы его инициализировать, создаём новую функцию init в модуле memory:

use x86_64::structures::paging::{PhysFrame, MapperAllSizes, MappedPageTable};
use x86_64::PhysAddr;

/// Initialize a new MappedPageTable.
///
/// This function is unsafe because the caller must guarantee that the
/// complete physical memory is mapped to virtual memory at the passed
/// `physical_memory_offset`. Also, this function must be only called once
/// to avoid aliasing `&mut` references (which is undefined behavior).
pub unsafe fn init(physical_memory_offset: u64) -> impl MapperAllSizes {
    let level_4_table = active_level_4_table(physical_memory_offset);
    let phys_to_virt = move |frame: PhysFrame| -> *mut PageTable {
        let phys = frame.start_address().as_u64();
        let virt = VirtAddr::new(phys + physical_memory_offset);
        virt.as_mut_ptr()
    };
    MappedPageTable::new(level_4_table, phys_to_virt)
}

// make private
unsafe fn active_level_4_table(physical_memory_offset: u64)
    -> &'static mut PageTable
{…}

Мы не можем напрямую вернуть MappedPageTable из функции, потому что он общий для типа замыкания. Мы обойдём эту проблему с помощью синтаксической конструкции impl Trait. Дополнительное преимущество в том, что затем можно переключить ядро на RecursivePageTable без изменения сигнатуры функции.

Функция MappedPageTable::new ожида

© Habrahabr.ru