System Programming
Rust
27 March

Пишем операционную систему на Rust. Реализация страничной памяти (новый вариант)

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

Этот цикл статей опубликован выложен на 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<PhysAddr>
{
    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<PhysAddr>
{
    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 ожидает два параметра: изменяемую ссылку на таблицу страниц уровня 4 и замыкание phys_to_virt, которое преобразует физический фрейм в указатель таблицы страниц *mut PageTable. Для первого параметра мы можем повторно использовать функцию active_level_4_table. Для второго создаём замыкание, которое использует physical_memory_offset для выполнения преобразования.

Мы также делаем active_level_4_table частной функцией, потому что отныне она будет вызываться только из init.

Чтобы использовать метод MapperAllSizes::translate_addr вместо нашей собственной функции memory::translate_addr, нужно изменить всего несколько строк в kernel_main:

// in src/main.rs

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

    // new: different imports
    use blog_os::memory;
    use x86_64::{structures::paging::MapperAllSizes, VirtAddr};

    // new: initialize a mapper
    let mapper = unsafe { memory::init(boot_info.physical_memory_offset) };

    let addresses = […]; // same as before

    for &address in &addresses {
        let virt = VirtAddr::new(address);
        // new: use the `mapper.translate_addr` method
        let phys = mapper.translate_addr(virt);
        println!("{:?} -> {:?}", virt, phys);
    }

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

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



Как и ожидалось, виртуальный адрес physical_memory_offset преобразуется в физический адрес 0x0. Используя функцию трансляции для типа MappedPageTable, мы избавляем себя от необходимости реализовать поддержку огромных страниц. У нас также есть доступ к другим страничным функциям, таким как map_to, которые мы будем использовать в следующем разделе. На этом этапе нам больше не нужна функция memory::translate_addr, можете удалить её, если хотите.

Создание нового сопоставления


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

Будем использовать функцию map_to из трейта Mapper, поэтому сначала рассмотрим эту функцию. Документация говорит, что она требует четыре аргумента: страница, которую мы хотим отобразить; фрейм, которому должна быть сопоставлена страница; набор флагов для записи таблицы страниц и распределитель фреймов frame_allocator. Аллокатор фреймов необходим, так как сопоставление данной страницы может потребовать создания дополнительных таблиц, которым нужны неиспользуемые фреймы в качестве резервного хранилища.

Функция create_example_mapping


Первый шаг нашей реализации — создание новой функции create_example_mapping, которая сопоставляет данную страницу с 0xb8000, физическим фреймом текстового буфера VGA. Мы выбираем этот фрейм, потому что он позволяет легко проверить, правильно ли было создано отображение: нам просто нужно выполнить запись в недавно отображённую страницу и посмотреть, появится ли она на экране.

Функция create_example_mapping выглядит так:

// in src/memory.rs

use x86_64::structures::paging::{Page, Size4KiB, Mapper, FrameAllocator};

/// Creates an example mapping for the given page to frame `0xb8000`.
pub fn create_example_mapping(
    page: Page,
    mapper: &mut impl Mapper<Size4KiB>,
    frame_allocator: &mut impl FrameAllocator<Size4KiB>,
) {
    use x86_64::structures::paging::PageTableFlags as Flags;

    let frame = PhysFrame::containing_address(PhysAddr::new(0xb8000));
    let flags = Flags::PRESENT | Flags::WRITABLE;

    let map_to_result = unsafe {
        mapper.map_to(page, frame, flags, frame_allocator)
    };
    map_to_result.expect("map_to failed").flush();
}

В дополнение к странице page, которую нужно сопоставить, функция ожидает экземпляр mapper и frame_allocator. Тип mapper реализует трейт Mapper<Size4KiB>, который предоставляет метод map_to. Общий параметр Size4KiB необходим, поскольку трейт Mapper является общим для трейта PageSize, работая как со стандартными страницами 4 КиБ, так и с огромными страницами по 2 МиБ и 1 ГиБ. Мы хотим создать только страницы 4 КиБ, поэтому можем использовать Mapper<Size4KiB> вместо требования MapperAllSizes.

Для сопоставления устанавливаем флаг PRESENT, поскольку он необходим для всех допустимых записей, и флаг WRITABLE, чтобы сделать отображаемую страницу доступной для записи. Вызов map_to небезопасен: можно нарушить безопасность памяти недопустимыми аргументами, поэтому придётся использовать блок unsafe. Список всех возможных флагов см. в разделе «Формат таблицы страниц» предыдущей статьи.

Функция map_to может завершиться ошибкой, поэтому она возвращает Result. Поскольку это всего лишь пример кода, который не должен быть надёжным, мы просто используем expect для паники в случае возникновении ошибки. При успешном выполнении функция возвращает тип MapperFlush, который обеспечивает простой способ очистки недавно отображённой страницы из буфера динамической трансляции (TLB) с помощью метода flush. Как и Result, этот тип применяет атрибут [#[must_use]] для выдачи предупреждения, если мы случайно забудем его использовать.

Фиктивный FrameAllocator


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

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

// in src/memory.rs

/// A FrameAllocator that always returns `None`.
pub struct EmptyFrameAllocator;

impl FrameAllocator<Size4KiB> for EmptyFrameAllocator {
    fn allocate_frame(&mut self) -> Option<PhysFrame> {
        None
    }
}

Теперь нужно найти страницу, которую можно отобразить без создания новых таблиц страниц. Загрузчик загружается в первый мегабайт виртуального адресного пространства, поэтому мы знаем, что для этого региона существует допустимая таблица уровня 1. Для нашего примера можем выбрать любую неиспользуемую страницу в этой области памяти, например, страницу по адресу 0x1000.

Чтобы проверить функцию, мы сначала отображаем страницу 0x1000, а затем вывести на экран содержимое памяти:

// in src/main.rs

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

    use blog_os::memory;
    use x86_64::{structures::paging::Page, VirtAddr};

    let mut mapper = unsafe { memory::init(boot_info.physical_memory_offset) };
    let mut frame_allocator = memory::EmptyFrameAllocator;

    // map a previously unmapped page
    let page = Page::containing_address(VirtAddr::new(0x1000));
    memory::create_example_mapping(page, &mut mapper, &mut frame_allocator);

    // write the string `New!` to the screen through the new mapping
    let page_ptr: *mut u64 = page.start_address().as_mut_ptr();
    unsafe { page_ptr.offset(400).write_volatile(0x_f021_f077_f065_f04e)};

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

Сначала создаём сопоставление для страницы в 0x1000, вызывая функцию create_example_mapping с изменяемой ссылкой на инстансы mapper и frame_allocator. Это сопоставляет страницу 0x1000 с фреймом текстового буфера VGA, поэтому мы должны увидеть на экране то, что там записано.

Затем преобразуем страницу в сырой указатель и записываем значение в смещение 400. Мы не пишем в начало страницы, потому что верхняя строка буфера VGA непосредственно смещается с экрана следующим println. Записываем значение 0x_f021_f077_f065_f04e, которое соответствует строке “New!” на белом фоне. Как мы узнали в статье «Текстовый режим VGA», запись в буфер VGA должна быть волатильной, поэтому используем метод write_volatile.

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



После записи на страницу 0x1000 на экране появилась надпись “New!”. Значит, мы успешно создали новое сопоставление в таблицах страниц.

Это сопоставление сработало, потому что уже была таблица уровня 1 для сопоставления 0x1000. Когда мы пытаемся сопоставить страницу, для которой ещё не существует таблицы уровня 1, функция map_to терпит неудачу, поскольку пытается выделить фреймы из EmptyFrameAllocator для создания новых таблиц. Мы видим, что это происходит, когда пытаемся отобразить страницу 0xdeadbeaf000 вместо 0x1000:

// in src/main.rs

#[cfg(not(test))]
fn kernel_main(boot_info: &'static BootInfo) -> ! {
    […]
    let page = Page::containing_address(VirtAddr::new(0xdeadbeaf000));
    […]
}

Если это запустить, возникает паника со следующим сообщением об ошибке:

panicked at 'map_to failed: FrameAllocationFailed', /…/result.rs:999:5

Чтобы отобразить страницы, у которых ещё нет таблицы страниц уровня 1, нужно создать правильный FrameAllocator. Но как узнать, какие фреймы свободны и сколько доступно физической памяти?

Выделение фреймов


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

// in src/memory.rs

pub struct BootInfoFrameAllocator<I> where I: Iterator<Item = PhysFrame> {
    frames: I,
}

impl<I> FrameAllocator<Size4KiB> for BootInfoFrameAllocator<I>
    where I: Iterator<Item = PhysFrame>
{
    fn allocate_frame(&mut self) -> Option<PhysFrame> {
        self.frames.next()
    }
}

Поле frames может быть инициализировано произвольным итератором кадров. Это позволяет просто делегировать вызовы alloc методу Iterator::next.

Для инициализации BootInfoFrameAllocator используем карту памяти memory_map, которую передаёт загрузчик как часть структуры BootInfo. Как объяснилось в разделе «Загрузочная информация», карта памяти предоставляется прошивкой BIOS/UEFI. Её можно запросить только в самом начале процесса загрузки, поэтому загрузчик уже вызвал нужные функции.

Карта памяти состоит из списка структур MemoryRegion, которые содержат начальный адрес, длину и тип (например, неиспользуемый, зарезервированный и т. д.) каждой области памяти. Создав итератор, который выдаёт кадры из неиспользуемых областей, мы можем создать валидный BootInfoFrameAllocator.

Инициализация BootInfoFrameAllocator происходит в новой функции init_frame_allocator:

// in src/memory.rs

use bootloader::bootinfo::{MemoryMap, MemoryRegionType};

/// Create a FrameAllocator from the passed memory map
pub fn init_frame_allocator(
    memory_map: &'static MemoryMap,
) -> BootInfoFrameAllocator<impl Iterator<Item = PhysFrame>> {
    // get usable regions from memory map
    let regions = memory_map
        .iter()
        .filter(|r| r.region_type == MemoryRegionType::Usable);
    // map each region to its address range
    let addr_ranges = regions.map(|r| r.range.start_addr()..r.range.end_addr());
    // transform to an iterator of frame start addresses
    let frame_addresses = addr_ranges.flat_map(|r| r.step_by(4096));
    // create `PhysFrame` types from the start addresses
    let frames = frame_addresses.map(|addr| {
        PhysFrame::containing_address(PhysAddr::new(addr))
    });

    BootInfoFrameAllocator { frames }
}

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

  • Во-первых, вызываем метод iter для преобразования карты памяти в итератор MemoryRegion. Затем используем метод filter для пропуска зарезервированных или недоступных регионов. Загрузчик обновляет карту памяти для всех сопоставлений, которые создаёт, поэтому фреймы, используемые ядром (код, данные или стек) или для хранения информации о загрузке, уже помечены как InUse или аналогично. Таким образом, мы можем быть уверены, что фреймы Usable не используются где-то ещё.
  • На втором этапе запускаем комбинатор map и синтаксисическую конструкцию range из Rust для преобразования итератора областей памяти в итератор диапазонов адресов.
  • Третий шаг самый сложный: преобразуем каждый диапазон в итератор с помощью метода into_iter, а затем выбираем каждый 4096-й адрес с помощью step_by. Поскольку 4096 байт (= 4 КиБ) — это размер страницы, мы получаем начальный адрес каждого фрейма. Страница загрузчика выравнивает все области памяти, так что нам не нужен код выравнивания или округления. Используя flat_map вместо map, мы получаем Iterator<Item = u64> вместо Iterator<Item = Iterator<Item = u64>>.
  • На последнем шаге преобразуем начальные адреса в типы PhysFrame, чтобы построить требуемый Iterator<Item = PhysFrame>. Затем применяем этот итератор для создания и возврата нового BootInfoFrameAllocator.

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

// in src/main.rs

#[cfg(not(test))]
fn kernel_main(boot_info: &'static BootInfo) -> ! {
    […]
    let mut frame_allocator = memory::init_frame_allocator(&boot_info.memory_map);
    […]
}

На этот раз сопоставление адресов прошло успешно и мы снова видим на экране чёрно-белую надпись “New!”. За кулисами метод map_to создаёт отсутствующие таблицы страниц следующим образом:

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

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

Резюме


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

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

Для нашей реализации мы сначала вручную прошли через таблицы страниц, сделав функцию трансляции, а затем использовали тип MappedPageTable крейта x86_64. Мы также узнали, как создавать новые сопоставления в таблице страниц и как сделать FrameAllocator на карте памяти, переданной загрузчиком.

Что дальше?


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

+39
4.9k 83
Support the author
Comments 1