Операционная система в 1 000 строк кода (часть 3)

Перед вами третья часть серии статей, в которой мы пишем собственную небольшую ОС. В этой части мы реализуем аллокатор памяти ^[1], механизм её адресации с использованием таблицы страниц, а также переключение контекста и некоторые другие элементы системы.

▍ Навигация по вышедшим частям

• Часть 1 ^[2]
• Часть 2 ^[3]
• Часть 3 < — вы здесь

Аллокация памяти

В этом разделе мы реализуем простой механизм аллокации памяти.

▍ Вернёмся к скрипту компоновщика

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

kernel.ld

    . = ALIGN(4);
    . += 128 * 1024; /* 128KB */
    __stack_top = .;

    . = ALIGN(4096);
    __free_ram = .;
    . += 64 * 1024 * 1024; /* 64MB */
    __free_ram_end = .;
}

Этот код добавляет два новых символа — __free_ram и __free_ram_end — определяя область памяти после стека. Размер этой области (64 МБ) произволен, и . = ALIGN(4096) обеспечивает выравнивание по границе 4 КБ.

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

Подсказка

Реальные операционные системы под x86-64 определяют доступные области памяти, получая информацию от аппаратных устройств во время загрузки (например, с помощью функции UEFI GetMemoryMap).

▍ Простейший в мире алгоритм аллокации памяти

Далее мы реализуем функцию для динамической аллокации памяти. Вместо её аллокации в байтах, как делает malloc, она будет аллоцировать память в более крупных единицах, называемых «страницы». Одна страница обычно имеет размер 4 КБ (4096 байт).

Подсказка

4 КБ = 4096 = 0x1000 (в шестнадцатеричной форме). Значит, выровненные по размеру страницы адреса будут красиво выглядеть в шестнадцатеричном формате.

Приведённая далее функция alloc_pages динамически аллоцирует n страниц памяти и возвращает стартовый адрес:

kernel.c

extern char __free_ram[], __free_ram_end[];

paddr_t alloc_pages(uint32_t n) {
    static paddr_t next_paddr = (paddr_t) __free_ram;
    paddr_t paddr = next_paddr;
    next_paddr += n * PAGE_SIZE;

    if (next_paddr > (paddr_t) __free_ram_end)
        PANIC("out of memory");

    memset((void *) paddr, 0, n * PAGE_SIZE);
    return paddr;
}

PAGE_SIZE представляет размер одной страницы. Пропишем это в common.h:

common.h

#define PAGE_SIZE 4096

Вот основные части alloc_pages:

• next_paddr определена как переменная static. Это значит, что её значение, в отличие от локальных переменных, между вызовов функции сохраняется. То есть по факту она действует как глобальная переменная.
• next_paddr указывает на стартовый адрес «следующей аллоцируемой области» (свободной области). Во время аллокации next_paddr продвигается на величину, равную этой области.
• next_paddr изначально содержит адрес __free_ram. Это означает, что память аллоцируется последовательно, начиная с __free_ram.
• __free_ram, благодаря ALIGN(4096) в скрипте компоновщика, выравнивается по границе 4 КБ. В связи с этим функция alloc_pages всегда возвращает адрес, выровненный по 4 КБ.
• Если функция пытается произвести аллокацию за пределами __free_ram_end, иначе говоря, исчерпывает доступный объём памяти, возникает паника ядра.
• Функция memset обеспечивает, чтобы аллоцированная памятm всегда заполнялась нулями. Это позволяет избежать трудных для отладки проблем, вызванных неинициализированной памятью.

Согласитесь, вроде ничего сложного? Однако есть в этом алгоритме аллокации одна серьёзная проблема: выделенная память не освобождается. Хотя для нашей простой ОС достаточно и такого решения.

Подсказка

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

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

▍ Проверка аллокации

Предлагаю протестировать реализованную нами функцию аллокации. Добавьте в kernel_main следующий код:

kernel.c

void kernel_main(void) {
    memset(__bss, 0, (size_t) __bss_end - (size_t) __bss);

    paddr_t paddr0 = alloc_pages(2);
    paddr_t paddr1 = alloc_pages(1);
    printf("alloc_pages test: paddr0=%xn", paddr0);
    printf("alloc_pages test: paddr1=%xn", paddr1);

    PANIC("booted!");
}

Убедитесь, что первый адрес (paddr0) соответствует адресу __free_ram, а следующий (paddr1) — адресу, расположенному на 8 КБ позади paddr0:

$ ./run.sh
Hello World!
alloc_pages test: paddr0=80221000
alloc_pages test: paddr1=80223000

$ llvm-nm kernel.elf | grep __free_ram
80221000 R __free_ram
84221000 R __free_ram_end

Процесс

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

Примечание

Реальные операционные системы предоставляют контекст выполнения в виде отдельного механизма под названием «поток». Для простоты в этом руководстве мы будем рассматривать каждый процесс как имеющий один поток.

▍ Блок управления процессом

Приведённая ниже структура process определяет объект процесса и известна как «Process Control Block (PCB)».

#define PROCS_MAX 8       //Максимальное число процессов.

#define PROC_UNUSED   0   // Неиспользуемый процесс.
#define PROC_RUNNABLE 1   // Готовый к выполнению процесс.

struct process {
    int pid;             // ID процесса.
    int state;           // Состояние процесса: PROC_UNUSED или PROC_RUNNABLE
    vaddr_t sp;          // Указатель стека.
    uint8_t stack[8192]; // Стек ядра.
};

Стек ядра содержит сохранённые значения регистров процессора, адреса возврата (откуда произошёл вызов) и локальные переменные. Подготовив стек ядра для каждого процесса, мы сможем реализовать переключение контекста, сохраняя/восстанавливая значения регистров и переключая указатель стека.

Подсказка

Есть ещё один подход, называемый «единый стек ядра». В нём вместо использования стека ядра для каждого процесса (или потока) есть всего один стек на процессор. Такую модель стека использует seL4 ^[4].

Этот вопрос с тем «где хранить контекст программы» также беспокоит разработчиков асинхронных сред выполнения на языках Go и Rust. Если интересно разобраться в теме, ищите в сети по запросу «stackless async».

▍ Переключение контекста

Смена контекста выполнения процесса называется «переключением контекста». Реализуем мы этот механизм в виде следующей функции switch_context:

kernel.c

__attribute__((naked)) void switch_context(uint32_t *prev_sp,
                                           uint32_t *next_sp) {
    __asm__ __volatile__(
        // Запись сохранённых вызываемым кодом значений регистров в стек текущего процесса.
        "addi sp, sp, -13 * 4n" // Аллокация пространства стека для 13 4-байтовых регистров.
        "sw ra,  0  * 4(sp)n"   // Запись только сохранённых вызываемым кодом значений регистров.
        "sw s0,  1  * 4(sp)n"
        "sw s1,  2  * 4(sp)n"
        "sw s2,  3  * 4(sp)n"
        "sw s3,  4  * 4(sp)n"
        "sw s4,  5  * 4(sp)n"
        "sw s5,  6  * 4(sp)n"
        "sw s6,  7  * 4(sp)n"
        "sw s7,  8  * 4(sp)n"
        "sw s8,  9  * 4(sp)n"
        "sw s9,  10 * 4(sp)n"
        "sw s10, 11 * 4(sp)n"
        "sw s11, 12 * 4(sp)n"

        // Переключение указателя стека.
        "sw sp, (a0)n"         // *prev_sp = sp;
        "lw sp, (a1)n"         // Переключение указателя стека (sp) сюда.

        // Восстановление сохранённых вызываемым кодом значений регистров из стека следующего процесса.
        "lw ra,  0  * 4(sp)n"  // Восстановление только сохранённых вызываемым кодом значений регистров.
        "lw s0,  1  * 4(sp)n"
        "lw s1,  2  * 4(sp)n"
        "lw s2,  3  * 4(sp)n"
        "lw s3,  4  * 4(sp)n"
        "lw s4,  5  * 4(sp)n"
        "lw s5,  6  * 4(sp)n"
        "lw s6,  7  * 4(sp)n"
        "lw s7,  8  * 4(sp)n"
        "lw s8,  9  * 4(sp)n"
        "lw s9,  10 * 4(sp)n"
        "lw s10, 11 * 4(sp)n"
        "lw s11, 12 * 4(sp)n"
        "addi sp, sp, 13 * 4n"  // Извлекли из стека 13 4-байтовых регистров.
        "retn"
    );
}

switch_context записывает содержимое регистров, сохранённое вызываемым кодом, в стек, переключает указатель стека и затем восстанавливает это содержимое из стека. Иными словами, контекст выполнения сохраняется в виде временных локальных переменных в стеке. В качестве альтернативы можно сохранять контекст в struct process, но вы наверняка согласитесь, что подход на основе стека прекрасен в своей простоте.

Регистры, содержимое которых сохраняет вызываемый код — это те регистры, чьи значения вызванная функция должна восстановить, прежде чем возвращать результат. В RISC-V это все регистры от s0 до s11. Содержимое других регистров, таких как a0, сохраняет вызывающий код, и оно уже записано им в стек. Именно поэтому switch_context обрабатывает лишь часть регистров.

Атрибут naked просит компилятор не генерировать никакой другой код, кроме встроенного ассемблера. Всё будет работать и без этого атрибута, но его использование является полезной практикой, позволяющей избежать нежелательного поведения ^[5], особенно при ручном изменении указателя стека.

Подсказка

Регистры, содержимое которых сохраняют вызываемый/вызывающий код, определены в соглашении о вызовах ^[6], и компиляторы генерируют код на основе этого соглашения.

Далее мы реализуем функцию инициализации процесса, create_process. Она будет получать в качестве параметра точку входа и возвращать указатель на созданную структуру process:

struct process procs[PROCS_MAX]; // Все блоки управления процессами.

struct process *create_process(uint32_t pc) {
    // Поиск блока управления неиспользуемого процесса. 
    struct process *proc = NULL;
    int i;
    for (i = 0; i < PROCS_MAX; i++) {
        if (procs[i].state == PROC_UNUSED) {
            proc = &procs[i];
            break;
        }
    }

    if (!proc)
        PANIC("no free process slots");

    // Запись в стек значений регистров, сохранённых вызываемым кодом. Эти значения будут восстановлены при первом переключении контекста функцией switch_context.
    uint32_t *sp = (uint32_t *) &proc->stack[sizeof(proc->stack)];
    *--sp = 0;                      // s11
    *--sp = 0;                      // s10
    *--sp = 0;                      // s9
    *--sp = 0;                      // s8
    *--sp = 0;                      // s7
    *--sp = 0;                      // s6
    *--sp = 0;                      // s5
    *--sp = 0;                      // s4
    *--sp = 0;                      // s3
    *--sp = 0;                      // s2
    *--sp = 0;                      // s1
    *--sp = 0;                      // s0
    *--sp = (uint32_t) pc;          // ra

    // Инициализация полей.
    proc->pid = i + 1;
    proc->state = PROC_RUNNABLE;
    proc->sp = (uint32_t) sp;
    return proc;
}

▍ Проверка переключения контекста

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

kernel.c

void delay(void) {
    for (int i = 0; i < 30000000; i++)
        __asm__ __volatile__("nop"); // do nothing
}

struct process *proc_a;
struct process *proc_b;

void proc_a_entry(void) {
    printf("starting process An");
    while (1) {
        putchar('A');
        switch_context(&proc_a->sp, &proc_b->sp);
        delay();
    }
}

void proc_b_entry(void) {
    printf("starting process Bn");
    while (1) {
        putchar('B');
        switch_context(&proc_b->sp, &proc_a->sp);
        delay();
    }
}

void kernel_main(void) {
    memset(__bss, 0, (size_t) __bss_end - (size_t) __bss);

    WRITE_CSR(stvec, (uint32_t) kernel_entry);

    proc_a = create_process((uint32_t) proc_a_entry);
    proc_b = create_process((uint32_t) proc_b_entry);
    proc_a_entry();

    PANIC("unreachable here!");
}

Функции proc_a_entry и proc_b_entry являются точками входа для процесса A и процесса B соответственно. После вывода одного символа с помощью функции putchar они переключают контекст на другие процессы, используя функцию switch_context.

Функция delay реализует холостой цикл, чтобы исключить слишком быстрый вывод символов, из-за которого терминал бы просто перестал отвечать. Инструкция nop означает «ничего не делать». Она добавляется, чтобы компилятор в рамках оптимизации не удалил этот холостой цикл.

Проверим, что получилось. Сначала поочерёдно будут выведены сообщения о запуске, за которыми последует бесконечная череда «ABABAB...»:

$ ./run.sh

starting process A
Astarting process B
BABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABAQE

▍ Планировщик

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

Реализуем мы этот механизм в виде приведённой ниже функции yield.

Подсказка

Слово «yield» часто используется в качестве имени API, позволяющего добровольно уступать процессор другому процессу.

kernel.c

struct process *current_proc; // Выполняющийся в текущий момент процесс.
struct process *idle_proc;    // Бездействующий процесс.

void yield(void) {
    // Поиск готового к выполнению процесса.
    struct process *next = idle_proc;
    for (int i = 0; i < PROCS_MAX; i++) {
        struct process *proc = &procs[(current_proc->pid + i) % PROCS_MAX];
        if (proc->state == PROC_RUNNABLE && proc->pid > 0) {
            next = proc;
            break;
        }
    }

    // Если за исключением текущего процесса других готовых к выполнению процессов нет, произвести возврат и продолжить обработку.
    if (next == current_proc)
        return;

    // Переключение контекста.
    struct process *prev = current_proc;
    current_proc = next;
    switch_context(&prev->sp, &next->sp);
}

Здесь мы вводим две глобальные переменные: current_proc указывает на текущий выполняемый процесс, а idle_proc — на бездействующий, который «нужно выполнить, когда готовых к выполнению процессов не будет». Переменная idle_proc создаётся при запуске в виде процесса с ID -1 так:

kernel.c

void kernel_main(void) {
    memset(__bss, 0, (size_t) __bss_end - (size_t) __bss);

    printf("nn");

    WRITE_CSR(stvec, (uint32_t) kernel_entry);

    idle_proc = create_process((uint32_t) NULL);
    idle_proc->pid = -1; // Бездействует.
    current_proc = idle_proc;

    proc_a = create_process((uint32_t) proc_a_entry);
    proc_b = create_process((uint32_t) proc_b_entry);

    yield();
    PANIC("switched to idle process");
}

Ключевым элементом в этой инициализации процесса выступает current_proc = idle_proc. Он обеспечивает, чтобы контекст выполнения процесса загрузки сохранялся и восстанавливался как в случае бездействующего процесса. Во время первого вызова функции yield происходит переключение с бездействующего процесса на процесс A, а при обратном переключении происходит как бы возврат из этого вызова yield.

Наконец, измените proc_a_entry и proc_b_entry, как показано ниже, чтобы вместо прямого вызова функции switch_context вызывать функцию yield:

kernel.c

void proc_a_entry(void) {
    printf("starting process An");
    while (1) {
        putchar('A');
        yield();
    }
}

void proc_b_entry(void) {
    printf("starting process Bn");
    while (1) {
        putchar('B');
        yield();
    }
}

Если «A» и «B» выводятся как и прежде, значит, всё прекрасно работает!

▍ Изменения в обработчике прерываний

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

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

kernel.c

void yield(void) {
    /* код опущен */

    __asm__ __volatile__(
        "csrw sscratch, %[sscratch]n"
        :
        : [sscratch] "r" ((uint32_t) &next->stack[sizeof(next->stack)])
    );

    // Переключение контекста.
    struct process *prev = current_proc;
    current_proc = next;
    switch_context(&prev->sp, &next->sp);
}

Поскольку указатель стека движется в сторону уменьшения адресов, в качестве базового значения стека ядра мы устанавливаем адрес sizeof(next->stack)-го байта.

В обработчик исключений при этом нужно внести следующие изменения:

kernel.c

void kernel_entry(void) {
    __asm__ __volatile__(
        // Извлечение стека ядра выполняющегося процесса из sscratch .
        "csrrw sp, sscratch, spn"

        "addi sp, sp, -4 * 31n"
        "sw ra,  4 * 0(sp)n"
        "sw gp,  4 * 1(sp)n"
        "sw tp,  4 * 2(sp)n"
        "sw t0,  4 * 3(sp)n"
        "sw t1,  4 * 4(sp)n"
        "sw t2,  4 * 5(sp)n"
        "sw t3,  4 * 6(sp)n"
        "sw t4,  4 * 7(sp)n"
        "sw t5,  4 * 8(sp)n"
        "sw t6,  4 * 9(sp)n"
        "sw a0,  4 * 10(sp)n"
        "sw a1,  4 * 11(sp)n"
        "sw a2,  4 * 12(sp)n"
        "sw a3,  4 * 13(sp)n"
        "sw a4,  4 * 14(sp)n"
        "sw a5,  4 * 15(sp)n"
        "sw a6,  4 * 16(sp)n"
        "sw a7,  4 * 17(sp)n"
        "sw s0,  4 * 18(sp)n"
        "sw s1,  4 * 19(sp)n"
        "sw s2,  4 * 20(sp)n"
        "sw s3,  4 * 21(sp)n"
        "sw s4,  4 * 22(sp)n"
        "sw s5,  4 * 23(sp)n"
        "sw s6,  4 * 24(sp)n"
        "sw s7,  4 * 25(sp)n"
        "sw s8,  4 * 26(sp)n"
        "sw s9,  4 * 27(sp)n"
        "sw s10, 4 * 28(sp)n"
        "sw s11, 4 * 29(sp)n"

        // Извлечение и сохранение sp в момент исключения.
        "csrr a0, sscratchn"
        "sw a0,  4 * 30(sp)n"

        // Сброс стека ядра.
        "addi a0, sp, 4 * 31n"
        "csrw sscratch, a0n"

        "mv a0, spn"
        "call handle_trapn"

Первая инструкция csrrw представляет операцию перестановки:

tmp = sp;
sp = sscratch;
sscratch = tmp;

Таким образом, теперь sp указывает на стек ядра (не пользователя) текущего выполняющегося процесса. Кроме того, теперь sscratch содержит исходное значение sp (стека пользователя) на момент исключения.

После сохранения в стек ядра значений и других регистров, мы восстанавливаем исходное значение sp из sscratch и сохраняем его в этот же стек. Затем мы вычисляем изначальное значение sscratch и также восстанавливаем его.

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

Подсказка

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

▍ Дополнение: «Зачем сбрасывать указатель стека?»

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

Дело в том, что нельзя доверять указателю стека на момент исключения. И здесь нужно иметь ввиду, что в обработчике исключений возможно три случая:

1. Исключение произошло в режиме ядра.
2. Исключение произошло в режиме ядра в момент обработки другого исключения (вложенное исключение).
3. Исключение произошло в режиме пользователя.

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

Возникает же проблема в третьем случае, когда sp указывает на область стека пространства пользователя. Если мы реализуем этот стек так, чтобы он использовал (доверял) sp как есть, может возникнуть уязвимость, ведущая к сбою ядра.

Давайте проведём эксперимент, запустив следующее приложение, когда реализуем все компоненты, вплоть до последней главы руководства:

// Пример приложений.
#include "user.h"

void main(void) {
    __asm__ __volatile__(
        "li sp, 0xdeadbeefn"  // Установка в sp недопустимого адреса.
        "unimp"                // Возникновение исключения.
    );
}

Если запустить этот код, не внося изменения из текущей главы (то есть без восстановления стека ядра из sscratch), то ядро просто молча зависнет. При этом в журнале QEMU вы увидите следующее:

epc:0x0100004e, tval:0x00000000, desc=illegal_instruction <- unimp активирует обработчик исключений.
epc:0x802009dc, tval:0xdeadbe73, desc=store_page_fault <- отменённая операция записи в стек (0xdeadbeef)
epc:0x802009dc, tval:0xdeadbdf7, desc=store_page_fault <- отменённая операция записи в стек (0xdeadbeef) (2)
epc:0x802009dc, tval:0xdeadbd7b, desc=store_page_fault <- отменённая операция записи в стек (0xdeadbeef) (3)
epc:0x802009dc, tval:0xdeadbcff, desc=store_page_fault <- отменённая операция записи в стек (0xdeadbeef) (4)
...

Сначала происходит исключение из-за недопустимой псевдо-инструкции unimp, и выполнение переходит к обработчику прерываний ядра. Тем не менее, так как указатель стека ведёт к неотображённому адресу (0xdeadbeef), при попытке сохранить значения регистров происходит исключение, ведущее обратно к началу обработчика прерываний. В итоге возникает бесконечный цикл, вызывающий зависание ядра. Чтобы этого не допустить, нужно извлечь проверенную область стека из sscratch.

Ещё одним решением будет создание нескольких обработчиков исключений. В версии xv6 для RISC-V (известная образовательная UNIX-подобная ОС) есть свой обработчик исключений для случая 1 и 2 (kernelvec [7]) и свой для случая 3 (uservec [8]). Первый наследует указатель стека в момент исключения, а второй получает отдельный стек ядра. Обработчик прерываний переключается ^[9] при входе/выходе из режима ядра.

Подсказка

В разработанной Google операционной системе Fuchsia был случай, когда API, допускающий установку из режима пользователя произвольных значений счётчика команд, стал уязвимостью ^[10]. В разработке ядра крайне важно с недоверием относиться к вводу пользователей (приложений).

▍ Дальнейшие шаги

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

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

Таблица страниц

▍ Управление памятью и виртуальная адресация

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

В текущем разделе мы реализуем аппаратный механизм изоляции памяти.

▍ Структура виртуального адреса

В этом руководстве мы используем механизм страничной организации памяти Sv32, основанный на двухуровневой таблице страниц. В ней 32-битные виртуальные адреса разделяются на индекс страницы первого уровня (VPN[1]), индекс страницы второго уровня (VPN[0]) и смещение на странице.

Попробуйте интерактивное приложение RISC-V Sv-32 Virtual Address Breakdown ^[11], чтобы понять, как виртуальные адреса разбиваются на индексы страниц таблицы и смещения.

Вот несколько примеров:

Подсказка

Из примеров выше мы видим, что индексы обладают следующими характеристиками:

• Изменение средних битов (VPN[0]) не влияет на индекс первого уровня. Это означает, что записи таблицы страниц для близлежащих адресов сконцентрированы в одной таблице первого уровня.
• Изменение младших битов не влияет ни на VPN[1], ни на VPN[0]. Это означает, что адреса на одной странице 4 КБ находятся в одной записи таблицы страниц.

Эта структура построена по принципу локальности ^[12], позволяя использовать таблицы страниц меньшего размера и более эффективно использовать буфер ассоциативной ^[13] трансляции (Translation Lookaside Buffer, TLB).

Обращаясь к памяти, процессор вычисляет VPN[1] и VPN[0], чтобы определить соответствующую запись таблицы страниц, считывает связанный с ней базовый физический адрес и добавляет offset для получения итогового адреса.

▍ Построение таблицы страниц

Теперь построим таблицу страниц по принципу Sv32. Для начала определим макрос. SATP_SV32 — это бит в регистре satp, указывающий на «активацию страничной организации памяти в режиме Sv32», а PAGE_* — это флаги, устанавливаемые в записях таблицы.

kernel.h

#define SATP_SV32 (1u << 31)
#define PAGE_V    (1 << 0)   // бит "Valid" (запись активна)
#define PAGE_R    (1 << 1)   // Доступна для чтения
#define PAGE_W    (1 << 2)   // Доступна для записи
#define PAGE_X    (1 << 3)   // Исполняемая
#define PAGE_U    (1 << 4)   // Пользователь (доступна в режиме пользователя)

▍ Отображение страниц

Приведённая далее функция map_page получает таблицу страниц первого уровня (table1), виртуальный адрес (vaddr), физический адрес (paddr) и флаги записей таблицы (flags):

kernel.c

void map_page(uint32_t *table1, uint32_t vaddr, paddr_t paddr, uint32_t flags) {
    if (!is_aligned(vaddr, PAGE_SIZE))
        PANIC("unaligned vaddr %x", vaddr);

    if (!is_aligned(paddr, PAGE_SIZE))
        PANIC("unaligned paddr %x", paddr);

    uint32_t vpn1 = (vaddr >> 22) & 0x3ff;
    if ((table1[vpn1] & PAGE_V) == 0) {
        // Создаём 2-х уровневую таблицу страниц.
        uint32_t pt_paddr = alloc_pages(1);
        table1[vpn1] = ((pt_paddr / PAGE_SIZE) << 10) | PAGE_V;
    }

    // Прописываем запись таблицы страниц 2-го уровня как отображающую физическую страницу.
    uint32_t vpn0 = (vaddr >> 12) & 0x3ff;
    uint32_t *table0 = (uint32_t *) ((table1[vpn1] >> 10) * PAGE_SIZE);
    table0[vpn0] = ((paddr / PAGE_SIZE) << 10) | flags | PAGE_V;
}

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

▍ Отображение в область памяти ядра

Таблица страниц должна быть настроена не только для приложений (пространство пользователя), но и для ядра.

В этом руководстве отображение в память ядра настроено так, чтобы его виртуальные адреса сопоставлялись с физическими (то есть vaddr == paddr). Это позволяет одному и тому же коду продолжать выполнение, даже после активации страничного режима памяти.

Для начала мы изменим скрипт компоновщика, определив в нём стартовый адрес, используемый ядром (__kernel_base):

kernel.ld

ENTRY(boot)

SECTIONS {
    . = 0x80200000;
    __kernel_base = .;

Предупреждение

Определите __kernel_base после строки . = 0x80200000. Если сделать наоборот, значение __kernel_base окажется нулевым.

Далее добавьте в структуру процесса таблицу страниц. Это будет указатель на таблицу первого уровня.

kernel.h

struct process {
    int pid;
    int state;
    vaddr_t sp;
    uint32_t *page_table;
    uint8_t stack[8192];
};

Наконец, отобразите страницы памяти ядра в функцию create_process. Страницы ядра охватывают область от __kernel_base до __free_ram_end. Такой подход позволит ядру обращаться как к статически аллоцированным областям (вроде .text), так и к динамически аллоцированным, которыми управляет alloc_pages:

kernel.c

extern char __kernel_base[];

struct process *create_process(uint32_t pc) {
    /* код опущен */

    // Отображение в страницы памяти ядра.
    uint32_t *page_table = (uint32_t *) alloc_pages(1);
    for (paddr_t paddr = (paddr_t) __kernel_base;
         paddr < (paddr_t) __free_ram_end; paddr += PAGE_SIZE)
        map_page(page_table, paddr, paddr, PAGE_R | PAGE_W | PAGE_X);

    proc->pid = i + 1;
    proc->state = PROC_RUNNABLE;
    proc->sp = (uint32_t) sp;
    proc->page_table = page_table;
    return proc;
}

▍ Переключение таблиц страниц

Теперь реализуем переключение таблиц страниц при смене контекста:

kernel.c

void yield(void) {
    /* код опущен */

    __asm__ __volatile__(
        "sfence.vman"
        "csrw satp, %[satp]n"
        "sfence.vman"
        "csrw sscratch, %[sscratch]n"
        :
        // Не забудьте запятую в конце!
        : [satp] "r" (SATP_SV32 | ((uint32_t) next->page_table / PAGE_SIZE)),
          [sscratch] "r" ((uint32_t) &next->stack[sizeof(next->stack)])
    );

    switch_context(&prev->sp, &next->sp);
}

Мы можем переключать таблицы страниц, указывая таблицу первого уровня в satp. Обратите внимание ^[14], что мы делим на PAGE_SIZE, так как это количество физических страниц.

Добавленные до и после установки таблицы страниц инструкции sfence.vma служат двум целям:

1. Обеспечить, чтобы изменения в таблице страниц были завершёнными (аналог барьера памяти).
2. Для очистки кэша записей таблиц страниц (TLB).

Подсказка

При запуске ядра по умолчанию страничная память отключена (регистр satp не установлен), и виртуальные адреса выступают в роли физических.

▍ Тестирование страничной памяти

Теперь проверим, что у нас получилось.

$ ./run.sh

starting process A
Astarting process B
BABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABAB

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

▍ Проверка содержимого таблиц страниц

Посмотрим, как отображаются виртуальные адреса рядом с 0x80000000. При правильной установке они должны отображаться так, чтобы (virtual address) == (physical address).

QEMU 8.0.2 monitor - type 'help' for more information
(qemu) stop
(qemu) info registers
 ...
 satp     80080253
 ...

Здесь мы видим, что satp соответствует 0x80080253. Согласно спецификации (режим Sv32 в RISC-V), интерпретация этого значения даёт нам стартовый физический адрес таблицы страниц первого уровня: (0x80080253 & 0x3fffff) * 4096 = 0x80253000.

Теперь взглянем на содержимое таблицы первого уровня. Мы хотим узнать таблицу страниц второго уровня, соответствующую виртуальному адресу 0x80000000. QEMU предоставляет команды для вывода содержимого памяти (дампа памяти). В частности, команда xp выводит содержимое по указанному физическому адресу. Мы сделаем дамп 512-й записи, так как 0x80000000 >> 22 = 512. И поскольку каждая запись имеет размер 4 байта, мы умножаем на 4:

(qemu) xp /x 0x80253000+512*4
0000000080253800: 0x20095001

В первом столбце отображается физический адрес, а в следующих — значения памяти. Мы видим, что установлены ненулевые значения. Опция /x определяет вывод в шестнадцатеричном формате. Добавление числа перед x (например, /1024x) позволяет указать количество выводимых записей.

Подсказка

Использование команды x вместо xp позволит просмотреть дамп памяти для указанного виртуального адреса. Это пригождается при изучении области памяти пространства пользователя (приложений), где, в отличие от пространства ядра, виртуальные адреса не соответствуют физическим.

Согласно спецификации, таблица записей второго уровня расположена по адресу (0x20095000 >> 10) * 4096 = 0x80254000. Давайте выведем всю её выведем (1024 записи):

(qemu) xp /1024x 0x80254000
0000000080254000: 0x00000000 0x00000000 0x00000000 0x00000000
0000000080254010: 0x00000000 0x00000000 0x00000000 0x00000000
0000000080254020: 0x00000000 0x00000000 0x00000000 0x00000000
0000000080254030: 0x00000000 0x00000000 0x00000000 0x00000000
...
00000000802547f0: 0x00000000 0x00000000 0x00000000 0x00000000
0000000080254800: 0x2008004f 0x2008040f 0x2008080f 0x20080c0f
0000000080254810: 0x2008100f 0x2008140f 0x2008180f 0x20081c0f
0000000080254820: 0x2008200f 0x2008240f 0x2008280f 0x20082c0f
0000000080254830: 0x2008300f 0x2008340f 0x2008380f 0x20083c0f
0000000080254840: 0x200840cf 0x2008440f 0x2008484f 0x20084c0f
0000000080254850: 0x200850cf 0x2008540f 0x200858cf 0x20085c0f
0000000080254860: 0x2008600f 0x2008640f 0x2008680f 0x20086c0f
0000000080254870: 0x2008700f 0x2008740f 0x2008780f 0x20087c0f
0000000080254880: 0x200880cf 0x2008840f 0x2008880f 0x20088c0f
...

Первые записи заполнены нулями, но с 512-й записи (254800) начинают появляться значения. Причина в том, что __kernel_base соответствует адресу 0x80200000, а VPN[1] — 0x200.

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

(qemu) info mem
vaddr    paddr            size     attr
-------- ---------------- -------- -------
80200000 0000000080200000 00001000 rwx--a-
80201000 0000000080201000 0000f000 rwx----
80210000 0000000080210000 00001000 rwx--ad
80211000 0000000080211000 00001000 rwx----
80212000 0000000080212000 00001000 rwx--a-
80213000 0000000080213000 00001000 rwx----
80214000 0000000080214000 00001000 rwx--ad
80215000 0000000080215000 00001000 rwx----
80216000 0000000080216000 00001000 rwx--ad
80217000 0000000080217000 00009000 rwx----
80220000 0000000080220000 00001000 rwx--ad
80221000 0000000080221000 0001f000 rwx----
80240000 0000000080240000 00001000 rwx--ad
80241000 0000000080241000 001bf000 rwx----
80400000 0000000080400000 00400000 rwx----
80800000 0000000080800000 00400000 rwx----
80c00000 0000000080c00000 00400000 rwx----
81000000 0000000081000000 00400000 rwx----
81400000 0000000081400000 00400000 rwx----
81800000 0000000081800000 00400000 rwx----
81c00000 0000000081c00000 00400000 rwx----
82000000 0000000082000000 00400000 rwx----
82400000 0000000082400000 00400000 rwx----
82800000 0000000082800000 00400000 rwx----
82c00000 0000000082c00000 00400000 rwx----
83000000 0000000083000000 00400000 rwx----
83400000 0000000083400000 00400000 rwx----
83800000 0000000083800000 00400000 rwx----
83c00000 0000000083c00000 00400000 rwx----
84000000 0000000084000000 00241000 rwx----

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

Атрибуты представлены сочетанием r (доступен для чтения), w (доступен для записи), x (исполняемый), a (вызванный) и d (записанный). Здесь a и d указывают, что процессор «обратился к странице» и «записал страницу» соответственно. Всё это является вспомогательной информацией для ОС для отслеживания, какие страницы используются/изменяются.

Подсказка

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

▍ Дополнение: отладка страничной памяти

Наладить работу таблиц страниц бывает нелегко, и ошибки ^[15] при этом порой сложно обнаружить. Так что здесь мы разберём некоторые распространённые ошибки и способы их исправления.

▍ Забыл установить режим страничной организации памяти

Предположим, мы забыли установить этот режим в регистре satp:

kernel.c

    __asm__ __volatile__(
        "sfence.vman"
        "csrw satp, %[satp]n"
        "sfence.vman"
        :
        : [satp] "r" (((uint32_t) next->page_table / PAGE_SIZE)) // Missing SATP_SV32!
    );

В этом случае вы заметите, что работа ОС никак не изменится. Дело в том, что режим страничной памяти остаётся отключен, и адреса памяти по-прежнему рассматриваются как физические.

Чтобы это исправить, выполните в мониторе QEMU команду info mem. Отобразится что-то вроде:

(qemu) info mem
No translation or protection

▍ Указал физический адрес вместо количества физических страниц

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

kernel.c

    __asm__ __volatile__(
        "sfence.vman"
        "csrw satp, %[satp]n"
        "sfence.vman"
        :
        : [satp] "r" (SATP_SV32 | ((uint32_t) next->page_table)) // Забыли сместиться!
    );

В этом случае info mem не покажет никаких отображённых страниц:

$ ./run.sh

QEMU 8.0.2 monitor - type 'help' for more information
(qemu) stop
(qemu) info mem
vaddr    paddr            size     attr
-------- ---------------- -------- -------

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

(qemu) info registers

CPU#0
 V      =   0
 pc       80200188
 ...
 scause   0000000c
 ...

Согласно llvm-addr2line, 80200188 — это стартовый адрес обработчика исключений. Причина исключения в scause соответствует «отказу страницы».

Попробуем вникнуть в происходящее, открыв логи QEMU:

run.sh
bash
$QEMU -machine virt -bios default -nographic -serial mon:stdio --no-reboot 
    -d unimp,guest_errors,int,cpu_reset -D qemu.log   # new!
    -kernel kernel.elf
Invalid read at addr 0x253000800, size 4, region '(null)', reason: rejected
riscv_cpu_do_interrupt: hart:0, async:0, cause:0000000c, epc:0x80200580, tval:0x80200580, desc=exec_page_fault
Invalid read at addr 0x253000800, size 4, region '(null)', reason: rejected
riscv_cpu_do_interrupt: hart:0, async:0, cause:0000000c, epc:0x80200188, tval:0x80200188, desc=exec_page_fault
Invalid read at addr 0x253000800, size 4, region '(null)', reason: rejected
riscv_cpu_do_interrupt: hart:0, async:0, cause:0000000c, epc:0x80200188, tval:0x80200188, desc=exec_page_fault

Что можно понять из этих логов:

• epc, указывающий расположение исключения из-за отказа страницы, соответствует адресу 0x80200580. llvm-objdump показывает, что он указывает на инструкцию, идущую сразу за установкой регистра satp. Это означает, что отказ страницы происходит сразу после активации режима страничной памяти.
• Все последующие отказы страниц показывают то же значение. Исключения произошли по адресу 0x80200188, который соответствует стартовому адресу обработчика исключений. Так как записи этого журнала продолжают повторяться, это говорит о том, что исключения (отказ страниц) происходят при попытке запустить обработчик исключений.
• Вывод info registers в мониторе QEMU показывает, что satp соответствует 0x80253000. Вычисление физического адреса в соответствии со спецификацией даёт (0x80253000 & 0x3fffff) * 4096 = 0x253000000, который не вписывается в 32-битное адресное пространство. Это указывает на то, что было установлено недопустимое значение.

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

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

До скорой встречи!

Telegram-канал со скидками, розыгрышами призов и новостями IT 💻 ^[16]

^[17]