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

Книга об xv6 в формате pdf, html, epub
Исходный текст xv6, что использует страницы виртуальной памяти размера 2Мб вместо 4Кб

Виртуальная память помогает программам работать одновременно и не мешать друг другу. ОС загружает программу в память, чтобы выполнить. Каждая программа требует личного адресного пространства, в которое другие программы не лезут. Программа работает с виртуальными адресами памяти, которые ОС отображает на физические. Так две программы обращаются по одинаковому виртуальному адресу, но ОС выдаст одной программе один физический адрес, а другой программе - другой. Глава 3 расскажет о виртуальной памяти и таблицах страниц подробнее.

ОС делит память на страницы - непрерывные области. Пример: страницы памяти размера 4 Кб занимают диапазоны адресов 0:0xFFF, 0x1000:0x1FFF, а страницы размера 2 Мб - 0:0x1FFFFF, 0x200000:0x3FFFFF.

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

Пример: Пусть программа занимает 4 Мб памяти. Размер страницы - 4 Кб. Программа займет (1024 * 1024 * 4) / (1024 * 4) = 1024 страницы памяти.

ОС избавит процессор от лишней работы, если увеличит размер страницы до 2 Мб - тогда программа займет 2 страницы.

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

Виртуальная память RISC-V

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

Xv6 работает под виртуальной машиной QEMU на 64-битной архитектуре RISC-V. RISC-V предлагает иерархию таблиц страниц. Процессор спускается по иерархии таблиц страниц в поисках физической страницы. Запись таблицы страниц указывает на следующую таблицу, когда биты RWX сброшены, иначе - на страницу физической памяти.

Xv6 использует режим Sv39 виртуальной адресации RISC-V. Процессор разбирает 64-битный виртуальный адрес так, как показывает рисунок.

Отбрасывает старшие биты 63-39.
Использует группы по 9 бит для поиска следующей записи таблицы страниц.
Использует оставшиеся младшие биты как смещение внутри физической страницы.

Пример:

Запись таблицы страниц уровня 0 указывает на страницу размера 2^30 = 1073741824 байтов = 1 Гб, когда биты RWX != 0, то есть хранят разрешения на доступ к физической странице.
Запись таблицы страниц уровня 1 указывает на страницу размера 2^21 = 2097152 байтов = 2 Мб, когда биты RWX != 0.
Запись таблицы страниц уровня 2 указывает на страницу размера 2^12 = 4096 байтов = 4 Кб, когда биты RWX != 0.

Объектный файл, исполняемый файл, образ памяти программы

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

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

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

Сегменты программы, выравнивание секций по размеру страниц. Сценарий компоновщика kernel.ld

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

Сценарий kernel.ld описывает, как устроен образ памяти ядра. Команда SECTIONS определяет, как компоновщик располагает секции из входных файлов в выходном. Команда .text : { *(.text) } говорит компоновщику поместить секции .text из входных файлов в секцию .text выходного. Запись *(...) означает любое имя входного файла.

Команда ENTRY(_entry) определяет точку входа в ядро - процедуру _entry из файла entry.S.

Присваивание . = 0x80000000; означает, что секция .text ядра расположена по виртуальному адресу 0x80000000 - по этому адресу QEMU загружает ядро. Символ . обозначает текущую позицию в выходном файле. Запись . = ALIGN(0x1000); увеличивает позицию до ближайшего адреса, кратного 0x1000 - выравнивает позицию по размеру страницы 4 Кб. ALIGN помогает расположить следующую секцию на новой странице.

Файл trampoline.S объявляет секцию trampsec и содержит код страницы trampoline. Команда ASSERT(. - _trampoline == 0x1000, "error: trampoline larger than one page"); проверяет, что секция trampsec умещается в одну страницу размера 4 Кб.

Примечание: Страница trampoline содержит инструкции, которые переключают процессор из режима пользователя в режим ядра и обратно, когда xv6 обрабатывает прерывания устройств и обслуживает системные вызовы. Глава 4 расскажет о trampoline подробнее.

PROVIDE(etext = .) добавит в таблицу символов программы символ etext с адресом конца секции .text. Функция kvmmake использует этот адрес, когда создает таблицу страниц ядра.

Код секции .rodata начинается с новой страницы, потому что команды ALIGN(0x1000) обрамляют страницу trampoline.

Секции .data и .bss требуют прав на запись, поэтому располагаются на новой странице - отдельно от секций .text и .rodata.

Опция командной строки компоновщика ld -z max-page-size= задает размер страницы памяти. Команда CONSTANT(MAXPAGESIZE) вернет размер страницы памяти - используем . = ALIGN(CONSTANT(MAXPAGESIZE)); вместо ALIGN(0x1000), чтобы выравнивать секции.

Сценарий компоновщика user.ld

Сценарий user.ld говорит компоновщику, как собирать программы пользователя - init, sh, cat, ls и т.д.

Команда ENTRY(_main) задает точку входа - функцию main. Компилятор предваряет имена символов - функций, переменных - подчеркиванием _.

Команда . = 0x0; располагает секцию кода по виртуальному адресу 0.

Секция .rodata следует за .text без переноса на новую страницу. Секция .rodata не требует разрешения на запись, поэтому располагается на страницах кода.

Примечание: компоновщик расширит секцию до начала следующей страницы, если поместить ALIGN внутри описания секции. Это замедлит запуск программы - ОС потратит больше времени на чтение секции из файла.
Размер секции останется прежним, если ALIGN расположить после описания секции. Следующая секция начнется с новой страницы, компоновщик добавит выравнивающие байты в файл, но байты не попадут в секцию и ОС не станет загружать эти байты из файла.

Код: увеличим размер страниц xv6

Файл kernel/risc.v определяет константу PGSIZE - размер виртуальной страницы - установим PGSIZE = (1024 * 1024 * 2) = 2 Мб.

Константа PGSHIFT определяет число бит в адресе, что задают смещение от начала страницы. Размер страницы увеличился с 2^12 = 4096 до 2^21 = 2097152 - теперь 21 бит определяет смещение.

Функция kvmmake создает таблицу страниц ядра - отображает в память регистры устройств, код и данные ядра, страницу trampoline и готовит страницы для стеков процессов. Файл kernel/memlayout.h определяет константы UART0, VIRTIO0, PLIC0, KERNBASE - убедимся, что адреса кратны новому размеру страницы.

#include <stdio.h>

#define MAXVA (1L << (9 + 9 + 9 + 12 - 1))
#define PGSIZE 1024 * 1024 * 2

#define UART0 0x10000000L
#define VIRTIO0 0x10001000
#define PLIC 0x0c000000L
#define KERNBASE 0x80000000L
#define TRAMPOLINE (MAXVA - PGSIZE)

#define PHYSTOP (KERNBASE + 128*1024*1024)

#define CHECK_ALIGNMENT(addr, name) \
    printf("Address %s is %saligned to page size\n", #name, 0 == ((addr) % PGSIZE) ? "" : "NOT ");

int main() {
    CHECK_ALIGNMENT(UART0, UART0);
    CHECK_ALIGNMENT(VIRTIO0, VIRTIO0);
    CHECK_ALIGNMENT(PLIC, PLIC);
    CHECK_ALIGNMENT(KERNBASE, KERNBASE);
    CHECK_ALIGNMENT(TRAMPOLINE, TRAMPOLINE);
}

Теперь VIRTIO0 - UART0 = 0x1000 < PGSIZE, поэтому VIRTIO0 попадает на ту же страницу, что и UART0 - убираем вызов kvmmap(kpgtbl, VIRTIO0, VIRTIO0, PGSIZE, PTE_R | PTE_W);, иначе получим ошибку panic: mappages: remap.

Функция walk(pagetable, va, alloc) ищет запись таблицы страниц pagetable для виртуального адреса va. Функция добавит страницу в таблицу, если не найдет и флаг alloc равен 1. Теперь ОС работает со страницами размера 2 Мб, поэтому walk не спускается ниже второго уровня иерархии таблиц страниц.

Теперь walk работает с 2-мя уровнями иерархии таблиц страниц

В Makefile сменим размер страницы для компоновщика в LDFLAGS.

Теперь размер виртуальной страницы равен 2 Мб

Xv6 работает на виртуальной машине QEMU со 128 Мб памяти.

QEMUOPTS = -machine virt -bios none -kernel $K/kernel -m 128M -smp $(CPUS) -nographic

Функция proc_mapstacks занимает память под стеки процессов. Функция требует по 2 страницы на процесс - страница стека и защитная страница - а для NPROC = 64 процессов - 64 * 2 = 128 страниц. Процессы требовали 128 * 4 = 512 Кб памяти, теперь же требуют 128 * 2 = 256 Мб. Уменьшим число процессов NPROC или увеличим объем памяти машины.

"И того, и другого, и можно без хлеба" - сказал Винни Пух.

Константа MAXFILE ограничивает наибольший размер файла. Константа MAXFILE равна наибольшему числу блоков файловой системы, которые файл занимает - MAXFILE = NDIRECT + NINDIRECT. Структура dinode описывает, как файл хранится на диске. Структура dinode содержит NDIRECT блоков содержимого файла и один косвенный блок, который содержит номера блоков диска с остальным содержимым файла.

kernel/fs.h

#define BSIZE 1024 // block size
#define NDIRECT 12
#define NINDIRECT (BSIZE / sizeof(uint)) // 1024 / 4 = 256
#define MAXFILE (NDIRECT + NINDIRECT) // 268

Файловая система ограничивает размер файла 268 блоками по 1024 байта - размер файла не превышает 268 Кб. Файлы программ занимают больше места после увеличения размера страниц, поэтому команда mkfs завершится ошибкой:

make qemu // или make fs.img
...
Assertion failed: fbn < MAXFILE

Программа содержит не менее двух страниц памяти - кода и данных - поэтому ориентируемся на размер файла не менее 4 Мб.

Размер блока кратен размеру структуры dinode, чтобы один блок умещал целое число структур dinode - так файловой системе легче найти dinode по номеру. Увеличим число блоков файла так, чтобы структура dinode занимала 1024 байта:

NDIRECT = (1024 - 4 * sizeof(short) - sizeof(uint)) / 4 - 1 = (1024 - 12) / 4 - 1 = 252

Это увеличит наибольший размер файла до 252 + 256 = 508 Кб. Увеличим размер блока до 4096 байтов - получим наибольший размер файла ~4.98 Мб.

MAXFILE = 252 + 4096 / 4 = 252 + 1024 = 1276
max_size = 1276 * 4096 = 5226496

Глава 8 расскажет о файловой системе подробнее.

Запускаем usertests

Программисты пишут тесты, чтоб тесты запускали - запускайте тесты до того, как изменили код, запускайте тесты после.

Программа usertests проверяет ядро на прочность - передает системным вызовам неверные адреса памяти, пишет в файл по неверному смещению, одновременно вызывает fork, exit, wait, чтобы провоцировать взаимную блокировку процессов и т.д.

Программа usertests работает медленнее после увеличения размера страниц, потому что fork дольше копирует память. Теперь программа usertests требует больше памяти, поэтому увеличим объем памяти машины до 1024 Мб и константу PHYSTOP, чтобы xv6 использовала эту память.

# Makefile
QEMUOPTS = -machine virt -bios none -kernel $K/kernel -m 1024M -smp $(CPUS) -nographic

// kernel/memlayout.h
#define PHYSTOP (KERNBASE + 1024*1024*1024)

Заключение

Поупражнялись и хватит :) Xv6 стала работать медленнее, когда размер страниц увеличился - программа usertests работает в 10-15 раз дольше. Системный вызов fork работает дольше, потому что копирует больше памяти.

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

Ссылки

Xv6: увеличим размер страниц виртуальной памяти с 4Кб до 2Мб

zproxy.org