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

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

Введение

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

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

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

Для работы нужна x86_64 версии 0.4.0 или более поздней. Обновим зависимость в нашем Cargo.toml:

[dependencies]
x86_64 = "0.4.0" # or later

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

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



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

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

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

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



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

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

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

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



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

Путём записи в тождественно отображённую таблицу уровня 1 наше ядро может создать до 511 временных сопоставлений (512 минус запись, необходимая для тождественного отображения). В приведённом примере ядро сопоставило нулевую запись таблицы уровня 1 с фреймом по адресу 24 KiB. Это создало временное сопоставление виртуальной страницы по адресу 0 KiB с физическим фреймом таблицы страниц уровня 2, обозначенным пунктирной стрелкой. Теперь ядро может получить доступ к таблице уровня 2 путём записи в страницу, которая начинается по адресу 0 KiB.

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

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

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

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

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

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

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



Единственное отличие от примера в начале статьи — это дополнительная запись с индексом 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-битные индексы таблиц разного уровня. Это невозможно в шестнадцатеричной системе, где каждый символ представляет четыре бита.

Реализация

После всей этой теории мы можем, наконец, приступить к реализации. Удобно, что загрузчик сгенерировал не только таблицы страниц, но и рекурсивное отображение в последней записи таблицы уровня 4. Загрузчик сделал это, потому что в противном случае возникла бы проблема курицы или яйца: нам нужно получить доступ к таблице уровня 4, чтобы создать рекурсивное отображение, но мы не можем получить доступ к нему без какого-либо отображения.

Мы уже использовали это рекурсивное отображение в конце предыдущего статьи для доступа к таблице уровня 4 через жёстко прописанный адрес 0xffff_ffff_ffff_f000. Если преобразовать этот адрес в восьмеричный и сравнить с приведённой выше таблицей, то мы увидим, что он точно соответствует структуре записи таблицы уровня 4 с RRR = 0o777, AAAA = 0 и битами расширения знака 1:

структура: 0o_SSSSSS_RRR_RRR_RRR_RRR_AAAA
адрес:     0o_177777_777_777_777_777_0000

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

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

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

// in src/lib.rs

pub mod memory;

// in src/memory.rs

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

/// Returns the physical address for the given virtual address, or `None` if the
/// virtual address is not mapped.
pub fn translate_addr(addr: usize) -> Option<PhysAddr> {
    // introduce variables for the recursive index and the sign extension bits
    // TODO: Don't hardcode these values
    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);

    // check that level 4 entry is mapped
    let level_4_table = unsafe { &*(level_4_table_addr as *const PageTable) };
    if level_4_table[l4_idx].addr().is_null() {
        return None;
    }

    // check that level 3 entry is mapped
    let level_3_table = unsafe { &*(level_3_table_addr as *const PageTable) };
    if level_3_table[l3_idx].addr().is_null() {
        return None;
    }

    // check that level 2 entry is mapped
    let level_2_table = unsafe { &*(level_2_table_addr as *const PageTable) };
    if level_2_table[l2_idx].addr().is_null() {
        return None;
    }

    // check that level 1 entry is mapped and retrieve physical address from it
    let level_1_table = unsafe { &*(level_1_table_addr as *const PageTable) };
    let phys_addr = level_1_table[l1_idx].addr();
    if phys_addr.is_null() {
        return None;
    }

    Some(phys_addr + page_offset)
}

Во-первых, мы вводим переменные для рекурсивного индекса (511 = 0o777) и битов расширения знака (каждый равен 1). Затем вычисляем индексы таблиц страниц и смещение через побитовые операции, как указано на иллюстрации:



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

После вычисления адреса используем оператор индексирования для просмотра записи в таблице уровня 4. Если эта запись равна нулю, то нет таблицы уровня 3 для этой записи уровня 4. Это означает, что addr не сопоставлен ни с какой физической памятью. Таким образом, мы возвращаем None. В противном случае мы знаем, что таблица уровня 3 существует. Тогда мы повторяем процедуру, как на предыдущем уровне.

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

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

Пробуем

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

// in src/main.rs

#[cfg(not(test))]
#[no_mangle]
pub extern "C" fn _start() -> ! {
    […] // initialize GDT, IDT, PICS

    use blog_os::memory::translate_addr;

    // the identity-mapped vga buffer page
    println!("0xb8000 -> {:?}", translate_addr(0xb8000));
    // some code page
    println!("0x20010a -> {:?}", translate_addr(0x20010a));
    // some stack page
    println!("0x57ac001ffe48 -> {:?}", translate_addr(0x57ac001ffe48));


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

После запуска видим такой результат:



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

Тип RecursivePageTable

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

// 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.
///
/// This function is unsafe because it can break memory safety if an invalid
/// address is passed.
pub unsafe fn init(level_4_table_addr: usize) -> RecursivePageTable<'static> {
    let level_4_table_ptr = level_4_table_addr as *mut PageTable;
    let level_4_table = &mut *level_4_table_ptr;
    RecursivePageTable::new(level_4_table).unwrap()
}

/// Returns the physical address for the given virtual address, or `None` if
/// the virtual address is not mapped.
pub fn translate_addr(addr: u64, recursive_page_table: &RecursivePageTable)
    -> Option<PhysAddr>
{
    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()))
}

Тип RecursivePageTable полностью инкапсулирует небезопасный обход таблиц страниц, так что больше не нужен код unsafe в функции translate_addr. Функция init остаётся небезопасной из-за необходимости гарантировать корректность переданного level_4_table_addr.

Наша функция _start должна быть обновлена для новой подписи функции следующим образом:

// in src/main.rs

#[cfg(not(test))]
#[no_mangle]
pub extern "C" fn _start() -> ! {
    […] // initialize GDT, IDT, PICS

    use blog_os::memory::{self, translate_addr};

    const LEVEL_4_TABLE_ADDR: usize = 0o_177777_777_777_777_777_0000;
    let recursive_page_table = unsafe { memory::init(LEVEL_4_TABLE_ADDR) };

    // the identity-mapped vga buffer page
    println!("0xb8000 -> {:?}", translate_addr(0xb8000, &recursive_page_table));
    // some code page
    println!("0x20010a -> {:?}", translate_addr(0x20010a, &recursive_page_table));
    // some stack page
    println!("0x57ac001ffe48 -> {:?}", translate_addr(0x57ac001ffe48,
        &recursive_page_table));

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

Теперь вместо передачи LEVEL_4_TABLE_ADDR в translate_addr и доступа к таблицам страниц через небезопасные необработанные указатели мы передаём ссылки на тип RecursivePageTable. Таким образом, теперь у нас есть безопасная абстракция и чёткая семантика владения. Это гарантирует, что мы не сможем случайно изменить таблицу страниц в совместном доступе, потому что для её изменения требуется монопольно завладеть RecursivePageTable.

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

Делаем небезопасные функции безопаснее

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

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

pub unsafe fn init(level_4_table_addr: usize) -> RecursivePageTable<'static> {
    let level_4_table_ptr = level_4_table_addr as *mut PageTable;
    let level_4_table = &mut *level_4_table_ptr; // <- this operation is unsafe
    RecursivePageTable::new(level_4_table).unwrap()
}

Проблема в том, что мы не сразу видим, какие части небезопасны. Например, не глядя на определение функции RecursivePageTable::new мы не можем сказать, является она безопасной или нет. Так очень легко случайно пропустить какой-то небезопасный код.

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

// in src/memory.rs

pub unsafe fn init(level_4_table_addr: usize) -> RecursivePageTable<'static> {
    /// Rust currently treats the whole body of unsafe functions as an unsafe
    /// block, which makes it difficult to see which operations are unsafe. To
    /// limit the scope of unsafe we use a safe inner function.
    fn init_inner(level_4_table_addr: usize) -> RecursivePageTable<'static> {
        let level_4_table_ptr = level_4_table_addr as *mut PageTable;
        let level_4_table = unsafe { &mut *level_4_table_ptr };
        RecursivePageTable::new(level_4_table).unwrap()
    }

    init_inner(level_4_table_addr)
}

Теперь блок unsafe опять требуется для разыменования level_4_table_ptr, а мы сразу видим, что это единственные небезопасные операции. В данный момент в Rust открыт RFC по изменению этого неудачного свойства небезопасных функций.

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

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

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

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

Реализуем её в новой функции create_maping в модуле memory:

// in src/memory.rs

use x86_64::structures::paging::{FrameAllocator, PhysFrame, Size4KiB};

pub fn create_example_mapping(
    recursive_page_table: &mut RecursivePageTable,
    frame_allocator: &mut impl FrameAllocator<Size4KiB>,
) {
    use x86_64::structures::paging::PageTableFlags as Flags;

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

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

Функция принимает изменяемую ссылку на RecursivePageTable (она будет изменять её) и FrameAllocator, который объясняется ниже. Затем применяет функцию map_to в трейте Mapper для сопоставления страницы по адресу 0x1000 с физическим фреймом по адресу 0xb8000. Функция небезопасна, так как можно нарушить безопасность памяти недопустимыми аргументами.

Кроме аргументов page и frame, функция map_to принимает ещё два аргумента. Третий аргумент — это набор флагов для таблицы страниц. Мы ставим флаг PRESENT, необходимый для всех действительных записей, и флаг WRITABLE для возможности записи.

Четвёртый аргумент должен быть некоторой структурой, реализующей трейт FrameAllocator. Этот аргумент нужен методу map_to, поскольку для создания новых таблиц страниц могут потребоваться неиспользуемые фреймы. В реализации трейта необходим аргумент Size4KiB, поскольку типы Page и PhysFrame являются универсальными для трейта PageSize, работая как со стандартными страницами 4 КиБ, так и с огромными страницами на 2 MиБ / 1 ГиБ.

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

Поскольку мы знаем, что для адреса 0x1000 не требуются новые таблицы страниц, то FrameAllocator может всегда возвращать 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
    }
}

(Если появляется ошибка 'method allocate_frame is not a member of trait FrameAllocator', необходимо обновить x86_64 до версии 0.4.0.)

Теперь можем протестировать новую функцию трансляции:

// in src/main.rs

#[cfg(not(test))]
#[no_mangle]
pub extern "C" fn _start() -> ! {
    […] // initialize GDT, IDT, PICS

    use blog_os::memory::{create_example_mapping, EmptyFrameAllocator};

    const LEVEL_4_TABLE_ADDR: usize = 0o_177777_777_777_777_777_0000;
    let mut recursive_page_table = unsafe { memory::init(LEVEL_4_TABLE_ADDR) };

    create_example_mapping(&mut recursive_page_table, &mut EmptyFrameAllocator);
    unsafe { (0x1900 as *mut u64).write_volatile(0xf021f077f065f04e)};

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

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

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

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



Надпись на экране.

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

// in src/memory.rs

pub fn create_example_mapping(…) {
    […]
    let page: Page = Page::containing_address(VirtAddr::new(0xdeadbeaf000));
    […]
}

// in src/main.rs

#[no_mangle]
pub extern "C" fn _start() -> ! {
    […]
    unsafe { (0xdeadbeaf900 as *mut u64).write_volatile(0xf021f077f065f04e)};
    […]
}

При запуске начинается паника с таким сообщением об ошибке:

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

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

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

На разных компьютерах разный объём физической памяти и отличаются области, зарезервированные устройствами, такими как VGA. Только прошивка BIOS или UEFI точно знает, какие области памяти можно использовать, а какие зарезервированы. Оба стандарта микропрограммного обеспечения предоставляют функции для получения карты распределения памяти, но их можно вызвать только в самом начале загрузки. Поэтому наш загрузчик уже запросил эту (и другую) информацию у BIOS.

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

// in src/main.rs

use bootloader::bootinfo::BootInfo;

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

Структура BootInfo ещё дорабатывается, так что не удивляйтесь сбоям при обновлении до будущих версий загрузчика, не совместимых с semver. В настоящее время у него три поля p4_table_addr, memory_map и package:

• Поле p4_table_addr содержит рекурсивный виртуальный адрес таблицы страниц уровня 4. Благодаря этому не нужно жёстко прописывать адрес 0o_177777_777_777_777_777_0000.
  
• Поле memory_map представляет наибольший интерес, так как содержит список всех областей памяти и их тип (неиспользуемые, зарезервированные или другие).
  
• Поле package является текущей функцией для связывания дополнительных данных с загрузчиком. Реализация не завершена, поэтому можем пока его игнорировать.

Прежде чем использовать поле memory_map для создания правильного FrameAllocator, мы хотим гарантировать правильный тип аргумента boot_info.

Макрос entry_point

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

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

// in src/main.rs

use bootloader::{bootinfo::BootInfo, entry_point};

entry_point!(kernel_main);

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

    let mut recursive_page_table = unsafe {
        memory::init(boot_info.p4_table_addr as usize)
    };

    […] // create and test example mapping

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

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

Заметьте, что сейчас мы передаём в memory::init не жёстко закодированный адрес, а boot_info.p4_table_addr. Таким образом, код будет работать, даже если будущая версия загрузчика выберет для рекурсивного отображения другую запись таблицы страниц уровня 4.

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

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

// 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 происходит в новой функции 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.into_iter().step_by(4096));
    // create `PhysFrame` types from the start addresses
    let frames = frame_addresses.map(|addr| {
        PhysFrame::containing_address(PhysAddr::new(addr))
    });

    BootInfoFrameAllocator { frames }
}

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

• Сначала вызываем метод iter для преобразования карты распределения памяти в итератор MemoryRegion. Затем используем метод filter, чтобы пропустить зарезервированные или недоступные регионы. Загрузчик обновляет карту распределения памяти для всех созданных им сопоставлений, поэтому фреймы, используемые нашим ядром (код, данные или стек) или для хранения загрузочной информации, уже помечены как InUse или аналогично. Таким образом, мы можем быть уверены, что используемые фреймы не используются где-то ещё.
  
• На втором этапе используем комбинатор map и синтаксис range Rust для преобразования нашего итератора областей памяти в итератор диапазонов адресов.
  
• Третий шаг является самым сложным: мы преобразуем каждый диапазон в итератор с помощью метода into_iter, а затем выбираем каждый 4096-й адрес с помощью step_by. Поскольку размер страницы 4096 байт (4 КиБ), мы получим адрес начала каждого фрейма. Страница загрузчика выравнивает все используемые области памяти, так что нам не нужен код выравнивания или округления. Заменив map на flat_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) -> ! {
    […] // initialize GDT, IDT, PICS

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

    let mut recursive_page_table = unsafe {
        memory::init(boot_info.p4_table_addr as usize)
    };
    // new
    let mut frame_allocator = memory::init_frame_allocator(&boot_info.memory_map);

    blog_os::memory::create_mapping(&mut recursive_page_table, &mut frame_allocator);
    unsafe { (0xdeadbeaf900 as *mut u64).write_volatile(0xf021f077f065f04e)};

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

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

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

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

Резюме

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

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

Что дальше

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