[Перевод] Xv6: учебная Unix-подобная ОС. Глава 3. Таблицы страниц10.02.2024 15:00

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

Xv6 использует хитрости виртуальной памяти:

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

Глава рассказывает, как xv6 работает с виртуальной памятью и об устройстве виртуальной памяти RISC-V.

Как процессор работает с виртуальной памятью

Инструкции RISC-V — как пользователя, так и ядра — работают с виртуальными адресами. Оперативная память компьютера содержит физические адреса. Процессор RISC-V вычисляет для каждого виртуального адреса физический адрес с помощью таблиц страниц.

Xv6 работает по схеме виртуальной адресации RISC-V Sv39 — использует младшие 39 из 64 бит виртуального адреса, а старшие 25 бит отбрасывает.

Логически таблица страниц в Sv39 — массив из 2^27 записей. Обозначим запись таблицы страниц PTE от англ. Page Table Entry. Каждая запись содержит 44-битный номер физической страницы и набор флагов. Процессор преобразует 39-битный виртуальный адрес в 56-битный физический — использует старшие 27 бит для поиска PTE в таблице страниц, а младшие 12 — как смещение от начала физической страницы.

Логическое представление таблицы страниц RISC-V

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

Таблица страниц верхнего уровня иерархии называется корневой.

Пример: процесс занимает две страницы виртуальной памяти, начиная с адреса 0 — тогда записи корневой таблицы страниц с 1 по 511 не нужны, поэтому и 511 страниц памяти для таблиц следующего уровня не нужны. Следующий уровень иерархии экономит еще 511 * 512 страниц.

Sv39 определяет трехуровневую иерархию таблиц страниц. Каждая таблица страниц в иерархии содержит 512 записей и занимает 4096 байтов — одну страницу памяти. Процессор разбивает старшие 27 бит виртуального адреса на три группы по 9 бит. Каждая группа определяет индекс записи в очередной таблице страниц. Процессор извлекает номер физической страницы из PTE и переходит к следующей таблице страниц в иерархии. PTE из таблицы последнего уровня хранит номер искомой физической страницы. Младшие 12 бит виртуального адреса — смещение от начала физической страницы. Каждая страница занимает 2^12 = 4096 байтов памяти.

Иерархия таблиц страниц RISC-V Sv39

Процессор запоминает результаты поиска PTE в кеше TLB — от англ. Translation Lookahead Buffer — чтобы не повторять поиск по иерархии таблиц страниц.

Разработчики RISC-V зарезервировали старшие 25 бит 64-битного адреса на будущее. Sv39 способна адресовать 512 Гб памяти — достаточно для компьютеров RISC-V. Схема Sv48 адресует 2^48 = 256 Тб памяти.

Каждая PTE содержит битовые флаги — разрешения на действия со страницей:

PTE_V — PTE используется и содержит номер физической страницы. Процессор выбросит исключение при обращении к странице, если флаг PTE_V сброшен.
PTE_R — разрешает читать страницу.
PTE_W — разрешает писать в страницу.
PTE_X — разрешает толковать содержимое страницы как код и выполнять.
PTE_U — разрешает обращаться к странице из режима пользователя. Страница доступна только режиму супервизора, если флаг PTE_U сброшен.

Файл kernel/riscv.h определяет макросы, константы, структуры и процедуры особенные для RISC-V.

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

Ядро отображает физическую память в собственную таблицу страниц, чтобы читать и писать память по любому адресу.

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

Напомним термины:

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

Адресное пространство ядра

Xv6 ведет таблицу страниц виртуальной памяти каждого процесса и одну таблицу страниц виртуальной памяти ядра. Ядро организует виртуальную память так, чтобы обращаться к физической памяти и устройствам ввода-вывода по заранее определенным адресам. Файл kernel/memlayout.h определяет константы, с помощью которых xv6 размечает память.

QEMU эмулирует компьютер с физической памятью, которая начинается с адреса 0x80000000. Xv6 обозначает последний адрес физической памяти константой PHYSTOP = 0x88000000. QEMU отображает управляющие регистры устройств ввода-вывода по физическим адресам ниже 0x80000000. Ядро взаимодействует с устройствами ввода-вывода, когда пишет и читает память по этим адресам. Глава 4 расскажет подробнее, как xv6 работает с устройствами.

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

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

Страница trampoline. Ядро отображает физическую страницу trampoline на последнюю виртуальную страницу памяти каждого процесса. Ядро дважды отображает физическую страницу trampoline на виртуальную память ядра: на последнюю виртуальную страницу и на страницу, чей адрес совпадает с физическим.
Страницы под стек ядра каждого процесса. Ядро располагает виртуальные страницы стеков ядра процессов в верхних адресах виртуальной памяти так, чтобы под каждой страницей стека расположить защитную страницу, которая не отображена на физическую память. Флаг PTE_V сброшен для защитной страницы, поэтому переполнение стека ядра выдаст ошибку доступа к странице. Без защитной страницы переполнение стека затрет другую память и нарушит работу ОС. Ядро остановит работу и сообщит об ошибке при переполнении стека, благодаря защитной странице.

Адресное пространство ядра

Код: создание адресного пространства

Файл kernel/vm.c содержит код управления виртуальной памятью и таблицами страниц. Тип pagetable_t определяет указатель на корневую таблицу страниц RISC-V — таблицу страниц ядра или процесса. Функция walk ищет запись таблицы страниц для указанного виртуального адреса. Функция mappages отображает виртуальные страницы на физические — вносит записи в таблицу страниц. Функции kvm* работают с таблицей страниц ядра, uvm* — с таблицей страниц процесса, остальные функции универсальны. Функция copyin копирует байты из адресного пространства пользователя в пространство ядра, а copyout — в обратном направлении. Процесс пользователя передает виртуальные адреса системным вызовам как аргументы.

Процедура main вызывает kvminit при загрузке ОС, чтобы создать таблицу страниц ядра с помощью kvmmake. Процессор еще работает с физической памятью на этом этапе — виртуальная память отключена, когда процессор начинает работу. Функция kvmmake запрашивает у аллокатора страницу памяти под корневую таблицу страниц ядра, затем добавляет в таблицу виртуальные страницы для устройств ввода-вывода, кода ядра, данных ядра и свободного пространства физической памяти вплоть до PHYSTOP. Процедура proc_mapstacks запрашивает у аллокатора память под стек ядра каждого процесса. Макрос KSTACK возвращает адрес вершины стека ядра i-го процесса так, чтобы оставить место для защитных страниц. Процедура kvmmap добавляет страницы в таблицу страниц ядра.

Процедура kvmmap вызывает mappages, чтобы добавить записи в таблицу страниц для диапазона виртуальных адресов. Функция mappages разбивает диапазон на страницы и отображает каждую виртуальную страницу на физическую. Функция mappages вызывает walk для виртуального адреса каждой страницы, чтобы найти запись таблицы страниц и заполнить — записать номер физической страницы, разрешения и установить флаг PTE_V.

Функция walk ищет для виртуального адреса запись в таблице страниц — walk проходит по трехуровневой иерархии таблиц страниц, на каждом шаге извлекает из виртуального адреса по 9 бит и использует как индекс в таблице страниц очередного уровня. Функция walk создаст таблицу страниц, когда встретит пустую запись таблицы страниц, если аргумент alloc = 1. Функция walk возвращает адрес записи таблицы страниц последнего уровня иерархии.

Код kernel/vm.c полагается на прямое отображение ядром виртуальных адресов на физические — извлекает физические адреса из таблиц страниц и использует как виртуальные.

Процедура main вызывает kvminithart, чтобы записать адрес таблицы страниц ядра в регистр satp процессора — с этих пор процессор работает с виртуальной памятью. Адрес следующей инструкции в регистре pc процессора остался верным, так как адреса виртуальной памяти ядра идентичны физическим.

Каждый процессор кеширует записи таблиц страниц в TLB, поэтому xv6 сообщает процессору об изменении таблиц страниц, чтобы процессор сбросил кеш. Устаревшая запись TLB заставит процессор обратиться по неверному физическому адресу и нарушить работу программ. Инструкция sfence.vma очищает TLB текущего процессора. Xv6 выполняет sfence.vma в kvminithart после записи регистра satp и в коде со страницы trampoline, что переключается на таблицу страниц процесса.

Xv6 выполняет sfence.vma и до записи в регистр satp, чтобы дождаться завершения операция чтения и записи, которые используют старую таблицу страниц.

RISC-V умеет помечать блоки памяти идентификаторами и сбрасывать не весь TLB, а конкретные записи. Xv6 не пользуется этой возможностью.

Физическая память

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

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

Код: аллокатор физической памяти

Файл kernel/kalloc.c содержит аллокатор страниц физической памяти. Ядро ведет список свободных страниц. Элемент списка — структура run. Аллокатор хранит каждую структуру в соответствующей свободной странице.

Спин-блокировка защищает список, когда два процесса изменяют список одновременно. Структура kmem объединяет список и блокировку, чтобы подчеркнуть взаимосвязь. Глава 6 расскажет о блокировках подробнее.

Процедура main вызывает kinit, которая инициализирует аллокатор — разбивает область свободной памяти на страницы и заполняет список свободных страниц. Xv6 полагает, что на компьютере доступно 128 Мб памяти, хотя размер памяти хранится в конфигурации компьютера. Процедура kinit вызывает freerange, чтобы разбить область памяти на страницы и освободить каждую вызовом kfree. Записи таблицы страниц ссылаются на физическое адреса, выровненные по размеру страницы, поэтому freerange выравнивает адрес макросом PGROUNDUP. Аллокатор не владеет свободной памятью как только создан, поэтому ОС наполняет его свободными страницами при запуске.

Аллокатор работает с адресами как с целыми числами, когда обходит страницы, но как с указателями, когда обращается к структурам run, поэтому код аллокатора кишит операторами приведения типов языка Си.

Процедура kfree стирает содержимое страницы — устанавливает значение каждого байта в 1 — так код, что по ошибке продолжает работать с освобожденной памятью, рухнет скорее. Процедура kfree помещает страницу в начало списка свободных страниц — приводит адрес pa к указателю на struct run, пишет адрес головы списка в r->next, а затем назначает новой головой списка r. Функция kalloc возвращает первую страницу списка и убирает страницу из списка.

The Art Of Unix Programming. Rule of Repair: Repair what you can — but when you must fail, fail noisily and as soon as possible.

Адресное пространство процесса

Xv6 ведет таблицу страниц каждого процесса и переключает таблицы, когда переключает процессы. Виртуальная память процесса простирается от 0 до MAXVA, то есть процесс способен адресовать 256 Гб памяти.

Адресное пространство процесса и стек процесса

Виртуальная память процесса содержит страницы кода, данных, стека и кучи. Xv6 назначает страницам следующие разрешения:

Код — чтение и выполнение, доступ из режима пользователя — PTE_R | PTE_X | PTE_U
Данные, стек и куча — чтение и запись, доступ из режима пользователя = PTE_R | PTE_W | PTE_U

Страницы кода запрещают запись, чтобы процесс не изменил код — случайно или злонамеренно.

Страницы с данными запрещают выполнение, чтобы процесс не передал управление случайному массиву байтов.

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

Aleph One. Smashing the stack for fun and profit

Стек умещается в одну страницу. Вызов exec копирует на стек аргументы программы так, словно программу вызвали как main(argc, argv).

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

Xv6 расширяет кучу процесса по требованию — запрашивает физическую страницу памяти у kalloc, вносит запись в таблицу страниц процесса, устанавливает флаги PTE_R | PTE_W | PTE_U | PTE_V для этой страницы. Записи таблицы страниц процесса пусты и не используются, пока процесс не запросит больше памяти. Флаг PTE_V сброшен у неиспользуемых записей.

Код: sbrk

Процесс вызывает sbrk, чтобы сократить или расширить память. Системный вызов sbrk вызывает growproc, которая вызывает uvmalloc, если получает положительный аргумент, и uvmdealloc, если аргумент отрицательный. Процедура uvmalloc запрашивает физическую память у kalloc, вносит записи в таблицу страниц процесса с помощью mappages. Процедура uvmdealloc вызывает uvmunmap, которая ищет записи в таблице страниц с помощью walk и освобождает страницы вызовом kfree.

Таблица страниц процесса — единственное место, что хранит знание о физических страницах процесса, поэтому освобождение памяти требует поиска по таблице страниц.

Код: exec

Системный вызов exec заменяет виртуальную память процесса образом программы из исполняемого файла. Компилятор создает исполняемый файл из файла с исходным текстом программы. Исполняемый файл содержит машинные инструкции и данные программы. Вызов exec находит файл по имени с помощью namei, затем читает ELF-заголовок файла. Файл kernel/elf.h описывает формат исполняемого файла ELF. Исполняемый файл состоит из заголовка elfhdr, за которым следуют заголовки секций программы proghdr. Программы xv6 содержат по две секции — одна для кода, другая для данных.

О namei подробно расскажет глава 8.

Первые 4 байта ELF-файла — волшебные: 0x7F, E, L, F. По этим байтам ОС узнает исполняемый файл. Вызов exec считает ELF-файл корректным, проверив волшебные байты.

Вызов exec создает пустую таблицу страниц процесса вызовом proc_pagetable, запрашивает память под каждую секцию программы вызовом uvmalloc и загружает каждую секцию в память вызовом loadseg. Функция loadseg вызывает walkaddr, чтобы узнать физический адрес страницы памяти, и вызывает readi, чтобы заполнить очередную страницу памяти блоком данных из файла.

Вот заголовки программных секций из файла /init:

$ objdump -p user/_init

user/_init:     file format elf64-little

Program Header:
0x70000003 off    0x0000000000006bb5 vaddr 0x0000000000000000 paddr 0x0000000000000000 align 2**0
filesz 0x0000000000000053 memsz 0x0000000000000000 flags r--
LOAD off    0x0000000000001000 vaddr 0x0000000000000000 paddr 0x0000000000000000 align 2**12
filesz 0x0000000000001000 memsz 0x0000000000001000 flags r-x
LOAD off    0x0000000000002000 vaddr 0x0000000000001000 paddr 0x0000000000001000 align 2**12
filesz 0x0000000000000010 memsz 0x0000000000000030 flags rw-
STACK off    0x0000000000000000 vaddr 0x0000000000000000 paddr 0x0000000000000000 align 2**4
filesz 0x0000000000000000 memsz 0x0000000000000000 flags rw-

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

Xv6 расширит секцию в памяти до размера memsz, если размер секции в файле filesz меньше, чем memsz. Секция данных программы /init занимает 0x10 байтов в файле и 0x30 в памяти, поэтому exec запрашивает у uvmalloc 0x30 байтов, но читает из файла 0x10 байтов.

Затем exec запрашивает одну страницу памяти под стек, копирует аргументы программы на вершину стека и запоминает адреса аргументов в массиве ustack. Код завершает список аргументов на стеке нулевым указателем — так принято обозначать конец массива argv для main. Первые три элемента ustack — фальшивый адрес возврата, число аргументов argc и указатель на массив аргументов argv.

Код exec помещает под стек защитную страницу, которая страхует программу от переполнения стека. Защитная страница помогает exec обнаружить переполнение стека еще до запуска программы — copyout вернет -1, если при копировании аргументов переполнит стек и получит ошибку обращения к странице.

Код exec переходит к метке bad, когда обнаруживает ошибку, освобождает временную память и возвращает -1. Код exec не уничтожает старую таблицу страниц процесса, пока не загрузит новую программу в память — иначе exec не вернет управление старой программе, если загрузить новую не удалось.

ELF-файл содержит непредсказуемые адреса, поэтому exec проверяет, чтобы сумма ph.addr + ph.memsz умещалась в 64 бита — иначе хакер заставит ОС загрузить код по запрещенному адресу, используя переполнение суммы. Старая версия xv6 отображала код ядра на виртуальную память процесса — хакер изменил бы код ядра, если бы exec не проверял адреса. Версия xv6 для RISC-V ведет отдельную таблицу страниц ядра и подменить код ядра таким способом не получится.

Хакеры постоянно находят новые уязвимости ядер ОС, чтобы повышать привилегии программы до уровня ядра. Xv6 — не исключение.

Реальность

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

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

RISC-V позволяет назначить привилегии доступа к областям физической памяти, но xv6 этим не пользуется.

RISC-V поддерживает страницы большего размера. Маленькие страницы хороши, когда физической памяти мало и ОС сбрасывает страницы на диск. Большие страницы хороши, когда физической памяти много и каждая программа занимает больше памяти. Большие страницы сократят число операций с таблицами страниц в таких условиях.

Xv6 не предоставляет аллокатора памяти для небольших объектов как это делает функция malloc языка Си — это мешает использовать структуры, что конструируют поля динамически. Функция malloc требует, чтобы ядро вело список блоков свободной памяти различных размеров, а не только страниц по 4096 байтов — так ядро обслужит как большие запросы на память, так и маленькие.

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

Дональд Кнут. «Искусство программирования, том 1: Основные алгоритмы»

Упражнения

Разберите дерево устройств RISC-V и узнайте объем физической памяти компьютера
Напишите программу, которая увеличивает память процесса на один байт вызовом sbrk(1). Запустите программу и загляните в таблицу страниц до и после вызова sbrk. Сколько памяти ядро выдало процессу? Что содержит новая запись таблицы страниц?
Измените код xv6 так, чтобы ядро использовало большие страницы памяти.
Вызов exec в Unix обрабатывает shell-сценарии — когда первая строка файла начинается символами #!, exec извлекает имя программы-интерпретатора из строки, запускает и передает имя этого файла программе вместе с аргументами. Пример: exec выполняет myprog arg1 и первая строка файла myprog — #!/interp. Тогда exec выполняет /interp с аргументами командной строки interp myprog arg1 . Реализуйте это в xv6.
Реализуйте непредсказуемое расположение адресного пространства процесса.