Перед вами третья часть серии статей, в которой мы пишем собственную небольшую ОС. В этой части мы реализуем аллокатор памяти, механизм её адресации с использованием таблицы страниц, а также переключение контекста и некоторые другие элементы системы.
▍ Навигация по вышедшим частям
Аллокация памяти
В этом разделе мы реализуем простой механизм аллокации памяти.
▍ Вернёмся к скрипту компоновщика
Прежде, чем заняться аллокатором памяти, мы определим области, которыми он будет управлять:
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 определяют доступные области памяти, получая информацию от аппаратных устройств во время загрузки (например, с помощью функции UEFIGetMemoryMap
).
▍ Простейший в мире алгоритм аллокации памяти
Далее мы реализуем функцию для динамической аллокации памяти. Вместо её аллокации в байтах, как делает
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=%x\n", paddr0);
printf("alloc_pages test: paddr1=%x\n", 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.
Этот вопрос с тем «где хранить контекст программы» также беспокоит разработчиков асинхронных сред выполнения на языках 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 * 4\n" // Аллокация пространства стека для 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 * 4\n" // Извлекли из стека 13 4-байтовых регистров.
"ret\n"
);
}
switch_context
записывает содержимое регистров, сохранённое вызываемым кодом, в стек, переключает указатель стека и затем восстанавливает это содержимое из стека. Иными словами, контекст выполнения сохраняется в виде временных локальных переменных в стеке. В качестве альтернативы можно сохранять контекст в struct process
, но вы наверняка согласитесь, что подход на основе стека прекрасен в своей простоте.Регистры, содержимое которых сохраняет вызываемый код — это те регистры, чьи значения вызванная функция должна восстановить, прежде чем возвращать результат. В RISC-V это все регистры от
s0
до s11
. Содержимое других регистров, таких как a0
, сохраняет вызывающий код, и оно уже записано им в стек. Именно поэтому switch_context
обрабатывает лишь часть регистров.Атрибут
naked
просит компилятор не генерировать никакой другой код, кроме встроенного ассемблера. Всё будет работать и без этого атрибута, но его использование является полезной практикой, позволяющей избежать нежелательного поведения, особенно при ручном изменении указателя стека.Подсказка
Регистры, содержимое которых сохраняют вызываемый/вызывающий код, определены в соглашении о вызовах, и компиляторы генерируют код на основе этого соглашения.
Далее мы реализуем функцию инициализации процесса,
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 A\n");
while (1) {
putchar('A');
switch_context(&proc_a->sp, &proc_b->sp);
delay();
}
}
void proc_b_entry(void) {
printf("starting process B\n");
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("\n\n");
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 A\n");
while (1) {
putchar('A');
yield();
}
}
void proc_b_entry(void) {
printf("starting process B\n");
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, sp\n"
"addi sp, sp, -4 * 31\n"
"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, sscratch\n"
"sw a0, 4 * 30(sp)\n"
// Сброс стека ядра.
"addi a0, sp, 4 * 31\n"
"csrw sscratch, a0\n"
"mv a0, sp\n"
"call handle_trap\n"
Первая инструкция
csrrw
представляет операцию перестановки:tmp = sp;
sp = sscratch;
sscratch = tmp;
Таким образом, теперь
sp
указывает на стек ядра (не пользователя) текущего выполняющегося процесса. Кроме того, теперь sscratch
содержит исходное значение sp
(стека пользователя) на момент исключения.После сохранения в стек ядра значений и других регистров, мы восстанавливаем исходное значение
sp
из sscratch
и сохраняем его в этот же стек. Затем мы вычисляем изначальное значение sscratch
и также восстанавливаем его.Суть здесь в том, что у каждого процесса есть собственный независимый стек ядра. Манипулируя содержимым
sscratch
во время переключения контекста, мы можем возобновлять выполнение процесса с точки, где оно было остановлено, будто ничего и не происходило.Подсказка
Выше мы реализовали механизм переключения контекста для стека «ядра». Стек, используемый приложениями (так называемый «стек пользователя») будет аллоцироваться отдельно, и его мы реализуем чуть позже.
▍ Дополнение: «Зачем сбрасывать указатель стека?»
В предыдущем разделе вы могли задаться вопросом, зачем нам переключаться на стек ядра, меняя содержимое
sscratch
.Дело в том, что нельзя доверять указателю стека на момент исключения. И здесь нужно иметь ввиду, что в обработчике исключений возможно три случая:
- Исключение произошло в режиме ядра.
- Исключение произошло в режиме ядра в момент обработки другого исключения (вложенное исключение).
- Исключение произошло в режиме пользователя.
Если не сбросить указатель стека в первом случае, то обычно проблем не возникнет. Во втором случае мы таким образом перепишем сохранённые данные, но в нашей реализации при вложенных исключениях возникает паника, так что тоже никаких проблем.
Возникает же проблема в третьем случае, когда
sp
указывает на область стека пространства пользователя. Если мы реализуем этот стек так, чтобы он использовал (доверял) sp
как есть, может возникнуть уязвимость, ведущая к сбою ядра.Давайте проведём эксперимент, запустив следующее приложение, когда реализуем все компоненты, вплоть до последней главы руководства:
// Пример приложений.
#include "user.h"
void main(void) {
__asm__ __volatile__(
"li sp, 0xdeadbeef\n" // Установка в 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
) и свой для случая 3 (uservec
). Первый наследует указатель стека в момент исключения, а второй получает отдельный стек ядра. Обработчик прерываний переключается при входе/выходе из режима ядра. Подсказка
В разработанной Google операционной системе Fuchsia был случай, когда API, допускающий установку из режима пользователя произвольных значений счётчика команд, стал уязвимостью. В разработке ядра крайне важно с недоверием относиться к вводу пользователей (приложений).
▍ Дальнейшие шаги
Вот мы и реализовали многозадачную ОС, получив возможность одновременно выполнять несколько процессов.
Как бы то ни было, пока что процессы могут свободно считывать/записывать данные в память ядра, что очень опасно. В следующих главах в целях безопасного выполнения приложений мы научимся изолировать их от ядра.
Таблица страниц
▍ Управление памятью и виртуальная адресация
Когда программа обращается к памяти, процессор переводит конкретный адрес обращения (виртуальный адрес) в физический адрес. Таблица, в которой виртуальные адреса сопоставляются с физическими, называется таблицей страниц. При переключении таких таблиц один и тот же виртуальный адрес может указывать на разные физические адреса. Это позволяет изолировать области виртуальной памяти и отделять области ядра от областей приложений, повышая безопасность системы.
В текущем разделе мы реализуем аппаратный механизм изоляции памяти.
▍ Структура виртуального адреса
В этом руководстве мы используем механизм страничной организации памяти Sv32, основанный на двухуровневой таблице страниц. В ней 32-битные виртуальные адреса разделяются на индекс страницы первого уровня (
VPN[1]
), индекс страницы второго уровня (VPN[0]
) и смещение на странице.Попробуйте интерактивное приложение RISC-V Sv-32 Virtual Address Breakdown, чтобы понять, как виртуальные адреса разбиваются на индексы страниц таблицы и смещения.
Вот несколько примеров:
Виртуальный адрес | VPN[1] (10 бит) | VPN[0] (10 бит) | Смещение (12 бит) |
0x1000_0000 | 0x040 | 0x000 | 0x000 |
0x1000_0000 | 0x040 | 0x000 | 0x000 |
0x1000_1000 | 0x040 | 0x001 | 0x000 |
0x1000_f000 | 0x040 | 0x00f | 0x000 |
0x2000_f0ab | 0x080 | 0x00f | 0x0ab |
0x2000_f012 | 0x080 | 0x00f | 0x012 |
0x2000_f034 | 0x080 | 0x00f | 0x045 |
Подсказка
Из примеров выше мы видим, что индексы обладают следующими характеристиками:
- Изменение средних битов (
VPN[0]
) не влияет на индекс первого уровня. Это означает, что записи таблицы страниц для близлежащих адресов сконцентрированы в одной таблице первого уровня.- Изменение младших битов не влияет ни на
VPN[1]
, ни наVPN[0]
. Это означает, что адреса на одной странице 4 КБ находятся в одной записи таблицы страниц.
Эта структура построена по принципу локальности, позволяя использовать таблицы страниц меньшего размера и более эффективно использовать буфер ассоциативной трансляции (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.vma\n"
"csrw satp, %[satp]\n"
"sfence.vma\n"
"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
. Обратите внимание, что мы делим на PAGE_SIZE
, так как это количество физических страниц.Добавленные до и после установки таблицы страниц инструкции
sfence.vma
служат двум целям:- Обеспечить, чтобы изменения в таблице страниц были завершёнными (аналог барьера памяти).
- Для очистки кэша записей таблиц страниц (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
указывают, что процессор «обратился к странице» и «записал страницу» соответственно. Всё это является вспомогательной информацией для ОС для отслеживания, какие страницы используются/изменяются.Подсказка
Для начинающих отладка таблицы страниц может показаться трудной. Если вам не удаётся всё как следует наладить, почитайте следующий раздел «Дополнение: отладка страничной памяти».
▍ Дополнение: отладка страничной памяти
Наладить работу таблиц страниц бывает нелегко, и ошибки при этом порой сложно обнаружить. Так что здесь мы разберём некоторые распространённые ошибки и способы их исправления.
▍ Забыл установить режим страничной организации памяти
Предположим, мы забыли установить этот режим в регистре
satp
:kernel.c
__asm__ __volatile__(
"sfence.vma\n"
"csrw satp, %[satp]\n"
"sfence.vma\n"
:
: [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.vma\n"
"csrw satp, %[satp]\n"
"sfence.vma\n"
:
: [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 ?
checkpoint
Если сделать вызов yeild() неявным, т.е. по таймеру, то получим вытесняющую многозадачность, вместо кооперативной. Правда в фунции switch_context() придется сохранить/восстановить все регистры, а не только сохраняемые по конвенции. И функцию yeild() придется подшаманить.