Операционные системы с нуля; уровень 3 (младшая половина)23.04.2018 08:48

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

оригинал

Нулевая лаба

Первая лаба: младшая половина и старшая половина

Вторая лаба: младшая половина и старшая половина

Полезности

• Книга по Rust v2. Вся необходимая инфа по Rust, необходимая в рамках этого курса.
• Документация стандартной библиотеки Rust
• Документация BCM2837. Наша модифицированная версия документации BCM2835 с исправлениями для BCM2837.
• ARMv8 Reference Manual. Справочное руководство по архитектуре ARMv8. Это цельное руководство, охватывающее всю архитектуру в целом. Для конкретной реализации архитектуры см. Руководство ARM Cortex A53.
• ARM Cortex-A53 Manual. Руководство для конкретной реализации архитектуры ARMv8 (v8.0-A). Именно это используется в малинке.
• Руководство программиста ARMv8-A. Руководство высокого уровня по программированию процесса ARMv8-A.
• AArch64 Procedural Call Standard
  Стандартная стандартная процедура для архитектуры AArch64.
• ARMv8 ISA Cheat Sheet. Краткое описание инструкций сборки ARMv8, представленных в этой лабе. За авторством Griffin Dietz.

Фаза 0: Начало работы

Как и в прошлых частях, для гарантированной работы требуется:

• Машина с современным Юниксом: Linux, BSD или macOS.
• 64-битная ОС.
• Наличие USB порта.
• Установлено ПО из прошлых выпусков.

Получение кода

В репе 3-spawn нет ничего кроме вопросиков, но стащить никто не мешает:

git clone https://web.stanford.edu/class/cs140e/assignments/3-spawn/skeleton.git 3-spawn

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

cs140e
├── 0-blinky
├── 1-shell
├── 2-fs
├── 3-spawn
└── os

А вот внутри os-репы переключиться на ветку 3-spawn будет таки необходимо:

cd os
git fetch
git checkout 3-spawn
git merge 2-fs

Скорее всего вы опять увидите конфликты слияния. Что-то вроде такого:

Auto-merging kernel/src/kmain.rs
CONFLICT (content): Merge conflict in kernel/src/kmain.rs
Automatic merge failed; fix conflicts and then commit the result.

Конфликты слияния надобно будет разрешить вручную, меняя файл kmain.rs. При этом надо убедиться, что вы сохранили все свои изменения из лабы 2. После устранения конфликтов добавьте файлы git add и закоммитите это всё. Для того, чтоб получить больше инфы по этой теме — смотрите туториал на githowto.com.

Документация ARM

В этом задании мы будем постоянно ссылаться на три оффициальных документа по ARM. Вот эти три:

1. ARMv8 Reference Manual
   Это оффициальное справочное руководство по архитектуре ARMv8. Цельное руководство, которое охватывает всю архитектуру целиком и полностью. Для конкретной реализации этой архитектуры в проце малинки нам потребуется мануал №2. Мы будем ссылаться на разделы этого большого мануала по ARMv8 по средством примечаний вида (ref: C5.2). В данном случае это означает, что надо посмотреть в ARMv8 Reference Manual в разделе C5.2.
2. ARM Cortex-A53 Manual
   Это уже мануал по вполне конкретной реализации ARMv8 (v8.0-A), которая и используется в малинке. На этот мануал мы будем ссылаться примечаниями вида (A53: 4.3.30).
3. ARMv8-A Programmer Guide
   Теперь перед нами достаточно высокоуровневый мануал по программированию ARMv8-А. На него мы будем ссылаться примечаниями вида (guide: 10.1)

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

Как это вообще читать? Нам не требуется читать его целиком и полностью. По этому для начала крайне важно знать, чего мы хотим найти в этом мануале. Оный мануал имеет хорошую годную структуру. Он разбит на несколько частей. Нас интересует AArch64 и не интересует слишком глубокое погружение (мы же не производители процессоров). Значит нам не интересны многие главы от слова совсем. По факту нам достаточно частей A, B и некоторой информации из C и D. В первых двух частях описываются общие понятия применительно к архитектуре и к AArch64 в частности. В части C описывается набор инструкций. Эту часть мы будем использовать как справочную по самым основным инструкциям и регистрам (например SIMD нас не интересует сейчас). В части D описываются некоторые детали AArch64. В частности про прерывания и всё такое.

Фаза 1: ARM and a Leg (Рука и нога)

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

Субфаза A: Обзор ARMv8

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

ARM (Acron RISC Machine) — это архитектура микропроцессоров с более чем 30 летней историей. На текущий момент есть восемь версий этой архитектуры. Последняя ARMv8 была представлена в 2011 году. Чип BCM2837 от Broadcom содержит в себе ядра ARM Cortex-A53, которые являются ядрами, основанными на ARMv8.0. Cortex-A53 (и подобные) — это реализация архитектуры. И это та реализация, которую мы будем изучать во всей этой части.

Микропроцессоры ARM доминируют на мобильном рынке.

ARM это примерно 95% всего мирового рынка смартфонов и 100% флагманских смартфонов. Включая Apple iPhone или Google Pixel.

До сих пор мы старались избегать делатей, относящихся к архитектуре процессора. За нас всё делал Rust. Для того, чтоб у нас работали процессы в юзерспейсе, нам потребуется провести некоторое количество работ на низком уровне. Программирование на проце напрямую потребует ознакомления с ассемблером этой архитектуры и со всеми связанными концепциями вокруг этого. Мы начнём с обзора архитектуры и разберёмся с самымми основными ассемблерными инструкциями.

Регистры

В архитектуре ARMv8 есть следующие регистры (ref: D1.2.1):

• r0…r30 — 64-битные регистры общего назначения. Доступ к регистрам осуществляется по псевдонимам (алиасам). Регистры x0…x30 являются алиасами для 64-битной версии (т.е. полной). Ещё есть алиасы w0…w30. По последним осуществляется доступ к нижним 32 битам регистра.
• lr — 64-битный ссылочный регистр. Алиас для x30. Используется для хранения адреса перехода. Инструкция bl сохраняет текущий счётчик команд (PC) в lr и переходит на адрес addr. Обратную работу будет делать инструкция ret. Она возьмёт адрес из lr и присвоит его PC.
• sp — указатель стека. Нижние 32 бита доступны по алиасу wsp. Указатель стека всегда должен быть выровнен по 16 байт.
• pc — програмный счётчик. В этот регистр нельзя писать напрямую, но можно прочитать. Он обновляется на инструкциях перехода, при вызове прерываний, при возврате.
• v0…v31 — 128-битные SIMD и FP регистры. Эти используются для векторных SIMD операций и для операций с плавающей запятой. Эти регистры доступны по алиасам. q0…q31 — алиасы для всех 128 бит регистра. Регистры d0…d31 это нижние 64 бита. По мимо этого есть алиасы для нижних 32, 16 и 8 бит по префиксам s, h и b соотвесвенно.
• xzr — нулевой регистр. Это псевдорегистр, который может быть или не быть хардварным регистром. Всегда содержит 0. Этот регистр можно только читать.

Есть ещё много регистров специального назначения. О них мы поговорим чуть позже.

PSTATE

В любой момент времени проц ARMv8 даёт возможность получить доступ к состоянию программы через псевдорегистр по имени PSTATE (ref: D1.7). Это не обычный регистр. Его нельзя прочитать или записать в него напрямую. Вместо есть несколько регистров специального назначения, которые можно использовать для того, чтоб оперировать с частями псевдорегистра PSTATE. На ARMv8.0 это:

• NZCV — флаги состояния
• DAIF — битовая маска исключений, которая используется для того, чтоб включать и выключать эти самые исключения
• CurrentEL — текущий уровень исключений (будет описан позже)
• SPSel — селектор указателей стека (их на самом деле несколько)

Подобные регистры принадлежат к классу системных или специальных регистров (ref: C5.2). Обычные регистры можно прочитать из оперативной памяти при помощи ldr или записать в память при помощи str. Системные регистры так использовать не получится. Вместо этого требуется использовать специальные команды mrs и msr (ref: C6.2.162 — C6.2.164). Например для того, чтоб прочитать NZCV в x1 нам следует использовать следующую запись:

mrs x1, NZCV

Состояние выполнения

В любой момент времени проц ARMv8 выполняется с определённым состоянием выполнения (execution state). Всего есть ровно два таких состояния. AArch32 — режим совместимости с 32-битным ARMv7. И AArch64 — 64-битный режим ARMv8 (guide: 3.1). Мы будем работать только с AArch64.

Безопасный режим

В любой момент времени наш проц исполняется с определённым состоянием безопасности (security state) (guide: 3). Эту фигню можно искать ещё и по security mode или по security world. Всего два состояния: secure и non-secure. Т.е. безопасное и обычное. Мы будем работать целиком в обычном режиме.

Уровни исключений

По мимо этого есть ещё и уровни исключений (exception level) (guide: 3). Каждый уровень исключений соответствует определённому уровню привилегий. Чем выше уровень исключений, тем больше привилегий получает программа, запущенная на этом уровне. Всего есть 4 уровня:

• EL0 (user) — Обычно используется для запуска пользовательских прог.
• EL1 (kernel) — Привилегированный режим. Обычно тут запускается ядро операционной системы.
• EL2 (hypervisor) — Обычно используется для запуска гипервизоров виртуальных машин.
• EL3 (monitor) — Обычно используется для низкоуровневой прошивки.

Процессор Raspberry Pi загружается в EL3. На этом этапе запускается прошивка, предоставляемая фондом Raspberry Pi. Прошивка переключает процессор на EL2 и запускает наш файлик kernel8.img. Таким образом наше ядро запускается с уровня EL2. Чуть позже мы займёмся переключением из EL2 на EL1, чтоб наше ядро работало на соответствующем уровне исключений.

Регистры ELx

Некоторое количество системных регистров, таких как ELR, SPSR и SP, дублируются для каждого уровня исключений. При этом к их именам ставится суффикс _ELn, где n — уровень исключений, к которому этот регистр относится. Например ELR_EL1 является регистром ссылок исключений для уровня EL1, а ELR_EL2 — тоже самое, но для уровня EL2.

Мы будем использовать суффикс x (например в ELR_ELx), когда надо сослаться на регистр из целевого уровня исключения x. Целевой уровень исключений — это уровень исключений, на который CPU переключится (если необходимо) при запуске вектора исключения.

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

Переключение между уровнями исключений

Существует ровно один механизм увеличения уровня исключения и ровно один механизм для уменьшения уровня исключения.

Для переключения с более высокого уровня на более низкий уровень (уменьшение привилегий), работающая программа должно выполнить возврат (return) из этого уровня исключения при помощи команды eret (ref: D1.11). При выполнении команды eret для уровня ELx процессор:

• Установит PC на значение из спец-регистра ELR_ELx.
• Установит PSTATE на значение из спец-регистра SPSR_ELx.

Регистр SPSR_ELx (ref: C5.2.18) по мимо прочего содержит в себе тот уровень исключений, на который надо перейти. Кроме того стоит обратить внимание на следующие дополнительные последствия смены уровней исключений:

• При возврате к ELs, sp устанавливается в SP_ELs если SPSR_ELx[0] == 1 или в SP_EL0 если SPSR_ELx[0] == 0.

Переход от более низкого уровня к более высокому происходит только в результате исключения (guide: 10). Если не настроено иначе, то проц будет перехватывать исключения для следующего уровня. Например в случае, если прерывание получено во время работы в EL0, то проц переключится на EL1 для обработки исключения. При переходе на ELx проц будет делать следующее:

• Выключит (замаскирует) все исключения и прерывания: PSTATE.DAIF = 0b1111.
• Сохранит PSTATE и всякое в SPSR_ELx.
• Сохранит адрес возврата в ELR_ELx (ref: D1.10.1).
• Установит sp на SP_ELx если SPSel равен 1.
• Установит синдром исключения (опишем это позже) в ESR_ELx (ref: D1.10.4).
• Установит pc на адрес, соответствующий вектору исключения (опишем чуть позже).

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

Векторы исключений

При возникновении исключений CPU передаёт управление в то место, где располагается вектор исключений (ref: D1.10.2). Существует 4 типа исключений, каждый из которых содержит 4 возможных источника исключений. Т.е. всего 16 векторов исключений. Вот четыре типа исключений:

• Synchronous — исключения, вызванные инструкциями типа svc или brk. Ну и вообще для всяких событий, в которых повинен программер.
• IRQ — асинхронные прерывания из внешних источников.
• FIQ — асинхронные прерывания из внешних источников. Версия для быстрой обработки.
• SError — прерывания типа «system error».

А вот четыре источника прерываний:

• Текущий уровень исключений при SP = SP_EL0
• Текущий уровень исключений при SP = SP_ELx
• Более низкий уровень исключений, на котором выполняется AArch64
• Более низкий уровень исключений, на котором выполняется AArch32

Из описания руководства (guide: 10.4):

Когда возникает исключение, процессор должен выполнить код обработчика, который соответствует исключению. Место в памяти, где хранится обработчик [исключения], называется вектором исключения. В архитектуре ARM векторы исключений хранятся в таблице, называемой таблицей векторов исключений. Каждый уровень исключений имеет свою собственную таблицу векторов, то есть для каждого из EL3, EL2 и EL1. Таблица содержит инструкции для выполнения, а не набор адресов [как в x86]. Каждая запись в векторной таблице имеет размер в 16 инструкций. Векторы для отдельных исключений расположены с фиксированными смещениями с начала таблицы. Виртуальный адрес каждой таблицы основывается на [специальных] векторных адресных регистрах VBAR_EL3, VBAR_EL2 и VBAR_EL1.

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

Текущий уровень исключений при SP = SP_EL0

Текущий уровень исключений при SP = SP_ELx

Более низкий уровень исключений, на котором выполняется AArch64

Более низкий уровень исключений, на котором выполняется AArch32

Резюме

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

Какие есть псевдонимы у регистра x30? [arm-x30]

Если мы запишем 0xFFFF в регистр x30, то какие два других имени этого регистра мы можем использовать для извлечения этого значения?

Как можно поменять значение PC на определённый адрес? [arm-pc]

Как можно установить PC на адрес A при помощи инструкции ret? Как установить PC на адрес A при помощи инструкции eret? Укажите, какие регистры вы будете изменять для того, чтоб этого достичь.

Каким образом можно определить текущий уровень исключений? [arm-el]

Какие именно инструкции вы бы выполнили для определения текущего уровня исключения?

Как бы вы изменили указатель стека на возврат исключения? [arm-sp-el]

Указатель стека запущенной программы равен A в момент возникновения исключения. После обработки исключения вы хотите вернуться обратно туда, где выполнялась программа, но хотите изменить указатель стека на B. Как вы это сделаете?

Какой вектор используется для системных вызовов из более низкого EL? [arm-svc]

Пользовательский процесс выполняется на EL0. Этот процесс вызывает svc. По какому адресу будет передано управление?

Какой вектор используется для прерываний из более низкого EL? [arm-int]

Пользовательский процесс выполняется на EL0. В этот момент возникает прерывание таймера. По какому адресу будет передано управление?

Каким образом можно включить обработку IRQ исключений? [arm-mask]

В какой регистр какие значения надо записать для того, чтоб разблокировать прерывания IRQ?

Каким образом вы бы использовали eret для включения режима AArch32? [arm-aarch32]

Источником исключения является AArch64. Обработчик этого исключения тоже на AArch64. Какие значения в каких регистрах вы бы изменили для того, чтоб при возврате из исключения через eret проц переключился в режим выполнения AArch32?
Подсказка: смотреть (guide: 10.1)

Субфаза B: Инструкции ассемблера

В этой подфазе мы изучим самые базовые команды из набора команд ARMv8. Писать код прямо сейчас не будем, но тут есть парочка вопросов для самопроверки.

Доступ к памяти

ARMv8 — это набор инструкций загрузки/хранения RISC (компьютер с сокращённым набором команд). Определяющей особенностью такого набора команд можно назвать тот маленький факт, что доступ к памяти может осуществляться только через чётко определённые инструкции. В частности память можно читать только путём считывания в регистр инструкцией загрузки, а записывать только инструкцией сохранения.

Существует множество инструкций для загрузки/выгрузки (load/store) в различных вариациях (по большей части они однотипны). Начнём с самой простой формы:

• ldr , []: загружает значение из адреса в .
• str , []: сохраняет значение по адресу из .

Регистр называется базовым регистром. Например если r3 = 0x1234, то:

ldr r0, [r3]      // r0 = *r3 (то есть, r0 = *(0x1234))
str r0, [r3]      // *r3 = r0 (то есть, *(0x1234) = r0)

Кроме этого можно добавить смещение из промежутка [-256, 255]:

ldr r0, [r3, #64]      // r0 = *(r3 + 64)
str r0, [r3, #-12]     // *(r3 - 12) = r0

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

ldr r0, [r3], #30      // r0 = *r3; r3 += 30
str r0, [r3], #-12     // *r3 = r0; r3 -= 12

Или пре-индекс, который изменит значение в базовом регистре перед применения загрузки или сохранения:

ldr r0, [r3, #30]!     // r3 += 30; r0 = *r3
str r0, [r3, #-12]!    // r3 -= 12; *r3 = r0

Смещение, пост-индекс и пре-индекс, они известны как режимы адресации.

Помимо этого есть ещё команда, которая может загружать/выгружать сразу два регистра. Инструкции ldp и stp (load pair, store pair). Эти инструкции можно использовать с теми же режимами адресации, что и ldr и str.

// кладём `x0` и `x1` на стек. после этой операции стек будет:
//
//   |------| 

mov   x0, #0xABCD, LSL #32  // x0 = 0xABCD00000000
mov   x0, #0x1234, LSL #16  // x0 = 0x12340000

mov   x1, #0xBEEF           // x1 = 0xBEEF
movk  x1, #0xDEAD, LSL #16  // x1 = 0xDEADBEEF
movk  x1, #0xF00D, LSL #32  // x1 = 0xF00DDEADBEEF
movk  x1, #0xFEED, LSL #48  // x1 = 0xFEEDF00DDEADBEEF

add_30:
    add x1, x1, #10
    add x1, x1, #20

adr x0, add_30    // x0 = адрес первой инструкции после add_30
ldr x0, =add_30   // x0 = адрес первой инструкции после add_30

mov  x13, #23    //          x13 = 23
mov  sp, x13     // sp = 23, x13 = 23

msr ELR_EL1, x1  // ELR_EL1 = x1

mrs x0, CurrentEL // x0 = CurrentEL

add    // dest = a + b
sub    // dest = a - b

mov x2, #24
mov x3, #36
add x1, x2, x3  // x1 = 24 + 36 = 60
sub x4, x3, x2  // x4 = 36 - 24 = 12

sub sp, sp, #120 // sp -= 120
add x3, x1, #120 // x3 = x1 + 120
add x3, x3, #88  // x3 += 88

mov x1, 0b11001
mov x2, 0b10101

and x3, x1, x2  // x3 = x1 & x2 = 0b10001
orr x3, x1, x2  // x3 = x1 | x2 = 0b11101
orr x1, x1, x2  // x1 |= x2
and x2, x2, x1  // x2 &= x1

and x1, x1, #0b110  // x1 &= 0b110
orr x1, x1, #0b101  // x1 |= 0b101

b label // jump to label

my_function:
    add x0, x0, x1
    ret

mov  x0, #4
mov  x1, #30
bl   my_function  // lr = адрес инструкции `mov x3, x0`
mov  x3, x0       // x3 = x0 = 4 + 30 = 34

ldr  x0, =label
blr  x0          // идентично bl label
br   x0          // идентично b  label

// добавлять 1 к x0 до тех пор, пока он не станет равным x1,
// затем вызвать `function_when_eq`, и выйти
not_equal:
    add  x0, x0, #1
    cmp  x0, x1
    bne  not_equal
    bl   function_when_eq

exit:
    ...

// вызывается когда x0 == x1
function_when_eq:
    ret

cmp  x1, #0
beq  x1_is_eq_to_zero

// FIXME: Return to EL1 at `set_stack`.

mov     x2, #0x3c5
msr     SPSR_EL2, x2