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

В этой части мы допишем обработку прерываний и возьмёмся за планировщик. Наконец-то у нас появятся элементы многозадачной операционной системы! Разумеется это только начало темы. Одно прерывание таймера, один системный вызов, базовая часть простого планировщика потоков. Ничего сложного. Однако этим мы подготовим плацдарм для создания полноценной системы, которая будет заниматься самыми настоящими процессами безо всяких "но". Прямо как в этих ваших линупсах и прочих. До конца этого курса осталось уже чуть менее половины.

Нулевая лаба

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

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

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

Субфаза E: Возврат из исключений

В этой субфазе мы будем писать код для возврата из обработчика исключений любых видов, форм и расцветок. Основная работа будет проводиться в файлике kernel/ext/init.S и папке kernel/src/traps.

Обзор

Если вы попытаетесь удалить бесконечный цикл из handle_exception, то скорее всего Raspberry Pi войдёт в цикл исключений. Т.е. неправильно обработанные исключения будут возникать снова и снова, а в некоторых случаях будет крешиться наша debug-оболочка. Это всё связано с тем, что когда обработчик исключений пытается вернуться в точку, где код выполнялся, состояние процессора (особенно данные в регистрах) изменилось без учёта того, что в этом самом коде происходило.

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

1: mov x3, #127
2: mov x4, #127
3: brk 10
4: cmp x3, x4
5: beq safety
6: b   oh_no

Когда возникает исключение brk, вызовется наш вектор исключения, который в конечном счёте вызовет handle_exception. Эта самая функция handle_exception, которая скомпилирована Rust-ом, будет помимо прочего использовать регистры x3 и x4 для своих грязных делишек. Когда наш обработчик исключений будет возвращаться в место вызова brk, состояние x3 и x4 будет совсем не то, каким мы его ожидаем. Соответственно и для инструкции beq в строке 5 не гарантируется правильное состояние. Может быть код прыгнет до safety, а может и нет.

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

Почему именно переключение контекста?

Кажется, что слово переключение здесь не слишком уместно. Мы же вроде как просто возвращаемся к тому же самому контексту, верно же?

В некоторых случаях это так. Однако на самом деле мы редко хотим возвращаться к тому же самому контексту выполнения. Чаще мы хотим изменить этот самый контекст для того, чтоб процессор делал всякие разные полезные штуки. Например когда нам понадобится реализовать переключение между разными процессами, мы будем подменять один контекст, на другой. Таким образом мы достигнем многозадачности. Когда мы будем реализовывать системные вызовы нам потребуется изменять значение регистров для того, чтоб реализовать возвращаемые значения. Даже в случае точек останова нам потребуется изменить регистр ELR для того, чтоб выполнялась следующая команда (иначе будет вызываться обработчик brk снова и снова).

В этой подфазе мы и будем заниматься сохранением/восстановлением контекста. Структура, которая будет содержать наш сохранённый контекст, будет называться фреймовой ловушкой (trap frame). Недописанную структуру TrapFrame можно найти в файлике kernel/src/traps/trap_frame.rs. Эту структуру мы будем использовать для того, чтоб получать доступ к сохранённым регистрам из Rust. С другой стороны заполнять эту структуру мы будем в ассемблерном коде. Останется только передать указатель на эту структуру через параметр tf в функцию handle_exception.

Trap Frame

Trap Frame — это имя, которое мы даём структуре, которая содержит весь контекст процессора. Имя "trap frame" происходит от термина "trap" (ловушка), который является общим термином для описания механизма, с помощью которого процессор вызывает более высокий уровень привилегий при возникновении некоторого события. Не знаю на счёт хорошего годного термина для обозначения этого всего на русском. Думаю в данном случае удобнее будет пользоваться только англоязычным термином.

Существуют различные способы создания trap frame, но суть их одна. Нам требуется сохранить всё состояние, которое необходимо для выполнения, в оперативную память. Большинство реализаций кладут всё состояние на стек. После того, как мы заполним стек содержимым регистров, указатель на верхушку стека станет нашим указателем на ловушку. Именно такую вариацию мы и будем в дальнейшем использовать.

На данный момент нам надо сохранить следующие части состояния ядра Cortex-A53:

• x0… x30 — т.е. все 64-битные регистры, коих целых 31 штука.
• q0… q31 — все 128-битные регистры SIMD/FP.
• pc — программный счётчик.
  За это отвечает регистр ELR_ELx. Он может быть, а может и не быть PC. Так или иначе, но это тот адрес, куда нам следует вернуться после выполнения обработчика исключения. Обычно в ELR_ELx содержится либо PC непосредственно, либо PC + 4, т.е. адрес следующей команды.
• PSTATE — флаги состояния процессора.
  Напомним, что состояние проца передаётся нам через регистр SPSR_ELx при предыдущем уровне ELx.
• sp — указатель на границу стека.
  К его содержимому можно получить доступ через SP_ELs для уровня исключений s.
• TPIDR — 64-битное значение текущего "ID процесса".
  Значение можно получить из TPIDR_ELs для уровня исключений s.

Вот это всё нам и нужно сохранить в нашем trap frame. Сохранять будем на стеке до того, как вызовем обработчик исключений. После того, как обработчик отдаст управление обратно ассемблерному коду, нам потребуется это состояние вернуть, каким оно там было. После того, как мы положим всё необходимое на стек, его содержимое должно выглядеть примерно таким вот образом:

Обратите внимание на SP и TPIDR в этой структуре. Они должны быть именно указателями стека и ID потока источника, а не частью состояния прерывания. Поскольку единственным возможным источником у нас будет EL0, их можно будет получить через чтение SP_EL0 и TPIDR_EL0. При этом текущий SP (который используется вектором исключения) будет указывать на начало trap frame. Сразу после того, как мы на этот самый стек положим необходимые значения разумеется.

После того, как мы заполним стек необходимыми значениями, мы передадим указатель на верх стека в качестве третьего аргумента handle_exception. Тип этого аргумента: &mut TrapFrame. Как уже говорилось, этот самый TrapFrame можно найти в файлике kernel/src/traps/trap_frame.rs. Вам необходимо дописать эту структуру.

Что за идентификатор треда?

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

Предпочтительный адрес возврата из исключения

Когда случается исключительная ситуация на уровне ELx, требующая обработки, CPU сохраняет предпочтительный адрес возврата в ELR_ELx. Подробности можно найти в документации (ref: D1.10.1). Вот кой чего оттуда:

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

Инструкция brk принадлежит ко второй категории. Таким образом ежели мы хотим продолжить выполнение после команды brk, нам потребуется убедиться, что в ELR_ELx содержится адрес следующей инструкции. Поскольку все инструкции в AArch64 имеют размер в 32 бита, то нам будет достаточно перезаписать это значение на ELR_ELx + 4.

Реализация

Начните с реализации context_save и context_restore из файлика os/kernel/ext/init.S. Подпрограмма context_save должна класть на стек все необходимые регистры, а затем вызывать handle_exception, передав этой функции все необходимые аргументы, включая и trap frame в качестве третьего аргумента. После того, как разберётесь с этим, займитесь подпрограммой context_restore. Эта подпрограмма должна восстанавливать контекст обратно.

Обратите внимание на инструкции, которые созданы макросом HANDLER. Там уже выполняется сохранение и восстановление x0 и x30. Вы не должны трогать эти регистры при сохранении/восстановлении в процедурах context_{save, restore}. Однако эти регистры должны лежать в trap frame.

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

// кладём на стек значения регистров `x1`, `x5`, `x12` и `x13`
sub  SP, SP, #32
stp  x1, x5, [SP]
stp  x12, x13, [SP, #16]

// вынимаем из стека значения регистров `x1`, `x5`, `x12` и `x13`
ldp  x1, x5, [SP]
ldp  x12, x13, [SP, #16]
add  SP, SP, #32

Убедитесь, что SP всегда выровнен по 16 байт. Вы обнаружите, что при таком подходе будет создаваться reserved в нашем trap frame. Этот самый reserved следует заполнять нулями.

Как только вы закончите с этими двумя подпрограммами, займитесь структурой TrapFrame из kernel/src/traps/trap_frame.rs. Убедитесь, что порядок и размер полей в точности соответствует с тем, что вы сохраняете в context_save и передаёте в качестве параметра tf.

В конце концов добавьте в handle_exception увеличение ELR на 4 перед тем, как возвращаться из обработчика исключения brk. Как только вы успешно реализуете переключение контекста, ваше ядро должно работать нормально после выхода из debug-оболочки. Когда всё будет готово — переходите к следующему этапу.

Содержимое вашего trap frame не обязано в точности соответствовать диаграмме, однако обязательно должно содержать все те же самые данные.

И не забудьте, что регистры qn имеют размер в 128 бит!

Подсказки:

Для того, чтоб вызвать handle_exception вам надо будет заняться сохранением/восстановлением регистров, которые не являются частью trap frame.

У Rust есть типы u128 и i128 для значений размером 128 бит.

Используйте инструкции mrs и msr для чтения/записи специальных регистров.

Наша версия context_save занимает около 45 инструкций.

Наша версия context_restore занимает около 41 инструкции.

А наша TrapFrame состоит из 68 полей с общим размером в 800 байт.

---

Каким образом можно лениво обрабатывать регистры для чисел с плавающей запятой? [lazy-float]

Сохранение и восстановление всех 128-битных SIMD/FP регистров достаточно дорогое удовольствие. Они занимают целых 512 байт из 800 в структуре TrapFrame! Было бы идеально обрабатывать эти регистры только в том случае, если они реально использовались источником исключения или целью переключения контекста.

Архитектура AArch64 позволяет нам выборочно включать/выключать использование этих регистров. Как мы могли бы использовать эту возможность для того, чтоб лениво подгружать эти регистры только в тех случаях, когда они реально используются? Но при этом иметь возможность эти регистры использовать свободно в своём коде. Какой код вы напишите для обработчика исключений? Нужно ли как либо модифицировать структуру TrapFrame для того, чтоб добавить какое либо дополнительное состояние и как это доп. состояние следует поддерживать?

Фаза 2: Это процесс

В этой части мы перейдём к самому вкусному. Мы будем реализовывать пользовательские процессы. Начнём с реализации структуры Process, которая будет работать с состоянием нашего процесса. Затем мы запустим первый процесс. После этого мы реализуем планировщик процессов типа round-robin. Для этого нам надо будет реализовать драйвер контроллера прерываний и включить прерывание таймера. Следом мы будем запускать наш планировщик при возникновении прерывания таймера и займёмся переключением контекста дабы осуществить переход к следующему процессу. И наконец мы реализуем первый системный вызов: sleep.

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

Субфаза A: Процесс

В этой подфазе мы будем реализовывать всё необходимое для функционирования типа Process из файла kernel/src/process/process.rs. Весь этот код нам пригодится уже в следующей подфазе.

Чем является Процесс?

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

В большинстве случаев процессы выполняются с ограниченным набором привилегий (в нашем случае это EL0). Всё во имя того, чтоб ядро могло обеспечить необходимый уровень стабильности и безопасности всей системы в целом. Если один из процессов ломается, то мы не хотим чтоб такая же участь постигла остальные процессы. Тем более мы не хотим, чтоб результатом этого был полный крах всей системы. Помимо этого мы не хотим, чтоб процессы мешали друг другу. Если один процесс завис, то мы хотим, чтоб остальные процессы всё ещё выполнялись. Таким образом процессы подразумевают изоляцию. Они работают до некоторой степени независимо друг от друга. Вероятно вы видите все эти свойства каждый день: когда у вас завис браузер, то остальная часть продолжает работу или тоже зависает?

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

Что внутри Процесса?

Для реализации процессов нам потребуется отслеживать код и данные процесса и всяческую вспомогательную информацию. Всё ради того, чтоб мы могли легко и свободно управлять состоянием процессов и изолировать процессы друг от друга. Это всё означает, что нам надо отслеживать:

• Стек
  Для каждого процесса требуется свой собственный уникальный стек. При реализации процессов нам необходимо выделить раздел памяти, который подойдёт для использования в качестве стека процесса. И разумеется нам нужно будет изменять указатель стека процесса таким образом, чтоб он указывал на эту область памяти.
• Куча (heap)
  Для того, чтоб работать с динамической памятью, каждому процессу потребуется выделить свою кучу. В самом начале куча будет совершенно пустой, но её можно будет расширить при помощи специальных системных вызовов. Мы пока оставим эту тему и вернёмся к ней в будущем.
• Код
  Процесс практически бесполезен, если он не выполняет какой либо код. Следовательно нашему ядру нужно будет каким-то образом загружать код процесса в память и передавать этому коду управление тогда, когда это необходимо.
• Виртуальное адресное пространство
  Поскольку мы не хотим давать процессам возможность доступа к памяти ядра и памяти других процессов, каждый процесс будет ограничен своим собственным адресным пространством при помощи такой штуки, как виртуальная память.
• Состояние планировщика
  В большинстве случаев мы предполагаем, что процессов может быть больше, чем ядер процессора. Ядро может выполнять только один поток команд за раз. Следовательно нам нужны механизмы мультиплексирования времени CPU (и следовательно у нас будет несколько потоков команд) для одновременного выполнения процессов. Задача планировщика состоит в определении того, какой процесс запускается и в какой момент это всё будет происходить. Для того, чтоб сделать это правильно, планировщик должен знать, готов ли какой либо процесс к планированию, либо нет. Состояние планировщика, которое хранится в каждом процессе — это именно то самое.
• Состояние выполнения
  Для того, чтоб правильно мультиплексировать время проца между несколькими процессами, нам нужно будет убедиться, что мы сохраняем состояние выполнения процесса, когда мы прекращаем выполнение этого процесса. Ну и не забываем о корректном восстановлении состояния в тот момент, когда мы включаем этот процесс обратно. По сути мы уже сделали всё необходимое для обработки этого состояния. Для этого нам и требовалось создать TrapFrame. Каждый процесс должен правильным способом хранить это состояние.

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

Структура Process из файла kernel/src/process/process.rs будет содержать всю эту информацию. На текущий момент (в этой фазе) все процессы будут использовать общую память и там не будет полей для кода, кучи или виртуального адресного пространства. Но мы добавим их чуть позже.

Должен ли процесс доверять ядру? [kernel-distrust]

В целом очевидно, что ядро должно с явным недоверием относиться к процессам. Но должны ли процессы доверять ядру? Если да, то чего должны ожидать процессы от ядра?

---

Что может пойти не так, если два процесса разделяют стеки? [isolated-stacks]

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

Реализация

Настало время реализовать всё необходимое для Process из файла kernel/src/process/process.rs. Перед тем, как начать, прочитайте реализацию типа Stack, которую можно найти в файлике kernel/src/process/stack.rs. Убедитесь, что вы знаете, как использовать эту структуру для создания нового стека и получения указателя стека для только что созданного процесса. Затем прочитайте реализацию типа State, которая будет использоваться для отслеживания состояния, относящегося к планировщику. Этот тип можно найти в файлике kernel/src/process/state.rs. Попробуйте порассуждать о том, как интерпретировать различные варианты состояния в контексте планирования жизненного пути процессов.

В конце концов реализуйте метод Process::new(). Реализация будет весьма простой. На самом деле нет ничего особо сложного в реализации отслеживания состояния процесса! Когда будете готовы — переходите к следующей подфазе.

Как восстанавливается память стека? [stack-drop]

Структура Stack выделяет 1MiB памяти под стек. При этом память выровнена по 16 байт. Откуда берутся гарантии освобождения этой памяти в тот момент, когда процесс, которому эта память принадлежит, героически заканчивает свою жизнь?

---

Каким образом можно лениво выделять память под стек? [lazy-stacks]

Структура Stack выделяет 1MiB памяти вне зависимости от реальных потребностей программы. Поразмышляйте на тему виртуальной памяти. Можно ли использовать виртуальную память для того, чтоб выделять настоящую физическую память под стек ровно в том объёме, который реально используется программой?

---

Каким образом процесс может увеличить размер стека? [stack-size]

Для некоторых процессов может потребоваться значительно большее пространство под стек. Но наша простая система выделяет жестко 1MiB. Предполагая, что процессы имеют доступ к распределению динамической памяти, каким образом процесс сможет увеличить размер стека? Конкретно, какие инструкции потребуются для того, чтоб реализовать это всё?

Субфаза B: Первый процесс

В этой подфазе мы выпустим наш первый процесс гулять по просторам пользовательского пространства (EL0). Основная работа будет вестись в файлах kernel/src/process/scheduler.rs и kernel/src/kmain.rs.

Переключение контекстов процессов

Большая часть работы, связанной с переключением контекстов уже выполнена. Для того чтоб собсна переключить контекст при возникновении соответствующего исключения нам надо:

1. Сохранить trap frame текущего процесса в поле trap_frame.
2. Восстановить trap frame из состояния следующего процесса из его поля trap_frame.
3. Изменить состояние планировщика, чтоб понимать, какой процесс выполняется.

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

Посмотрим, что произойдёт, ежели мы выполним все эти шаги для первого процесса. Начинается всё с возникновения исключения, которое вызывает переключение контекста. Например прерывание таймера. Затем происходит следующее. В ответ на исключительную ситуацию мы сохраняем всё состояние в поле trap_frame. Вот только что там содержится в trap frame? Оно ведь не имеет никакого отношения к процессу! Чуть позже как часть шага 2 мы восстановим trap_frame процесса, но там будет по сути мусор.

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

Для того, чтоб обойти это всё, мы собираемся перенастроить переключение контекстов с нуля. Вместо trap frame, пришедшего из context_save мы будем использовать вручную созданный контекст, а затем вызовем context_restore самостоятельно. Таким образом мы обойдём шаг 1 целиком. После того, как мы запустим первый процесс, все остальные переключения контекстов будут работать нормально.

Потоки ядра

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

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

Чуть позже мы запустим наш первый процесс. Поскольку этот процесс будет иметь общие ресурсы с ядром, то его можно назвать потоком ядра. Таким образом объём работы, необходимой для запуска первого процесса минимален ибо всё необходимое уже находится в памяти:

1. Создаём "поддельный" trap frame для переключения контекста.
2. Вызываем context_restore.
3. Переключаемся на уровень EL0.

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

Термин поток ядра перегружен.

Термин поток ядра используется для ссылки на потоки, реализованные ядром (в отличии от потоков, реализованных целиком в пользовательском пространстве) и для ссылки на потоки, которые выполняются в контексте ядра. Немного неудачная коллизия, но обычно понятно из контекста, какой именно вариант подразумевается. Если обсуждение не касается разработки ОС, то следует в первую очередь предполагать, что речь идёт о потоках, которые реализуются ядром.

Реализация

Существует ещё одна новенькая глобальная переменная в kmain.rs по имени SCHEDULER с типом GlobalScheduler, которая попросту оборачивает тип Scheduler. Оба типа можно найти в файлике kernel/src/process/scheduler.rs. Переменная SCHEDULER будет служить дескриптором планировщика для всея системы.

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

1. Написать extern-функцию без параметров, которая запускает командную оболочку.
   Эта функция будет точкой входа для нашего первого процесса. Вы можете поместить эту функцию в любое место, какое захотите. Мы удалим эту функцию, как только сможем загружать двоичные файлы с диска.
2. Создать экземпляр Process и настроить ему чистый trap frame.
   Нам нужно будет настроить trap frame, который будет потом восстанавливаться через context_restore позже. Прямо перед тем, как будет выполняться extern-функция. Для которой нам ещё надо настроить указатель на вершину стека. И только после этого переключить режим процессора в EL0.
3. Настроить необходимые регистры и вызвать context_restore, а затем eret для перехода в EL0.
   После настройки trap frame нам надо провести переключение контекста на этот процесс. Примерно таким образом:
   
   • Выполнить context_restore с соответствующим набором регистров.
     Примечание: тут немного расплывчатая информация. И это сделано специально. Если это кажется совсем мутной информацией, то подумайте о том, что должна делать context_restore, о том, что вы хотите сделать и каким образом это осуществить.
   • Установить текущий указатель стека (sp) на его изначальное значение (адрес _start). Это необходимо для того, чтоб мы могли использовать весь стек уровня EL1 при обработке исключений. Примечание: вы не можете напрямую использовать ldr или adr в sp. Для начала загрузите значение в какой либо регистр, а уже затем переместите это значение в sp.
   • Сбросить все регистры в 0. Вы не должны позволять любой информации утекать на пользовательский уровень.
   • Перейти на уровень EL0 при помощи инструкции eret.

Для реализации всего этого нам пригодится функционал ассемблерных вставок. В качестве примера, если переменная tf является указателем на trap frame, то следующий код будет устанавливать значение из этой переменной в x0, а затем скопирует это значение в x1:

unsafe {
    asm!("mov x0, $0
          mov x1, x0"
         :: "r"(tf)
         :: "volatile");
}

Как только вы реализуете всё необходимое — добавьте вызов SCHEDULER.start() в kmain и удалите любые вызовы оболочки или точек останова. Теперь kmain должна содержать три инициализирующих вызова. При чём планировщик в этой цепочке вызовов должен быть последним. Если всё работает правильно, то будет вызвана наша extern-функция на уровне EL0 и запустит командную оболочку.

Прежде чем продолжать, убедитесь, что переключение контекста на один и тот же процесс работает правильно. Попробуйте добавить несколько вызовов brk в свою extern-функцию до и после запуска оболочки:

extern fn run_shell() {
    unsafe { asm!("brk 1" :::: "volatile"); }
    unsafe { asm!("brk 2" :::: "volatile"); }
    shell::shell("user0> ");
    unsafe { asm!("brk 3" :::: "volatile"); }
    loop { shell::shell("user1> "); }
}

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

Подсказки:

Наша ассемблерная вставка состоит из 6 инструкций.

Для того, чтоб получить указатель типа T из Box<T> используйте &*box.

Помимо ассемблерной ставки, там не должно быть unsafe-блоков.

Субфаза C: Прерывание таймера

В этой подфазе мы будем реализовывать драйвер контроллера прерываний BCM2837. Помимо этого допилим существующий драйвер системного таймера, дабы включить туда настройку прерываний этого самого таймера. В итоге мы настроим прерывания таймера, которые нам потребуются для переключения контекста в планировщике. Основная работа будет вестись в файликах os/pi/src/interrupt.rs, os/pi/src/timer.rs и папке os/kernel/src/traps.

Обработка прерываний

В архитектуре AArch64 прерывания — это не что иное, как исключения определённого класса. Ключевым отличием является их асинхронная природа. Они генерируются внешним источником в ответ на внешние события.

На приведенной ниже диаграмме показан путь, по которому прерывания передаются от внешнего источника до вектора исключения:

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

Что такое контроллер прерываний?

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

Этот дополнительный слой позволяет выборочно включать/выключать прерывания. Помимо этого он позволяет производителям процессоров выбирать, какие контроллеры прерываний они хотят связать в со своим процессором.

Внешнее устройство

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

Контроллер прерываний

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

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

Процессор

Прерывания должны быть разблокированы (unmasked) процессором для того, чтоб доставлять их векторам прерываний. По умолчанию прерывания заблокированны (masked) процессором. Следовательно доставлены не будут. Проц может доставлять прерывания, которые были получены, когда прерывания были заблокированны, в тот момент, когда они разблокируются. Когда проц вызывает вектор исключения, он автоматически блокирует все прерывания. Благодаря такому подходу прерывания не будут сразу приводить к циклу исключений.

В прошлой подфазе мы настроили получение исключений из EL0, так что тут не должно быть особой дополнительной работы.

Когда следует разблокировать IRQ во время обработки IRQ? [reentrant-irq]

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

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

Сами векторы исключений вы уже настроили. Осталось только правильно обрабатывать IRQ (прерывания). Потребуется дописать некоторое количество кода в функции handle_exception из kernel/src/traps/mod.rs для того, чтоб пересылать все прерывания функции handle_irq из kernel/src/traps/irq.rs. Для того, чтоб определить, какое именно прерывание произошло, вам потребуется проверить, какие прерывания активны в контроллере прерываний. Функция handle_irq будет заниматься подтверждением и обработкой прерываний.

Реализация

Начните с реализации драйвера контроллера прерываний в файлике pi/src/interrupt.rs. Документацию по контроллеру прерываний можно найти в главе 7 руководства по периферийным устройствам BCM2873. Вам надо будет заняться включением/выключением и проверкой состояния обычных IRQ, из типа Interrupt. На FIQ или BasicIRQ можно не обращать внимания.

Затем надо будет реализовать метод tick_in() у системного таймера из pi/src/timer.rs. Документацию по таймеру можно найти в главе 12 руководства по периферийным устройствам BCM2873. Для реализации tick_in() вам нужно корректно записать определённые значения в два регистра.

Следующим шагом будет включение прерываний таймера и установка значения в микросекундах в соответствии с константы TICK. Это стоит выполнить прямо перед вызовом GlobalScheduler::start() из kernel/src/process/scheduler.rs. Константа TICK объявлена в этом же файле.

И наконец изменяем функцию handle_exception из kernel/src/traps/mod.rs таким образом, чтоб она передавала обработку прерываний функции handle_irq из kernel/src/traps/irq.rs. Эта самая handle_irq должна подтвердить обработку прерывания таймера и установить следующее прерывание таймера на количество микросекунд из TICK, гарантируя, что каждое прерывание таймера будет происходить каждые TICK микросекунд.

По окончанию всего этого вы должны увидеть, что происходит прерывание таймера каждые TICK микросекунд. Источником этих прерываний должно быть LowerAArch64, а тип (kind) должен быть Irq. Вы должны иметь возможность нормально взаимодействовать с процессом между прерываниями таймера. Как только всё заработает — переходите к следующей подфазе.

Мы изменим значение TICK позже!

В настоящее время используется абсурдно медленная настройка TICK. Прерывание будет происходить с интервалом в 2 секунды. Это в большей степени для того, чтоб было удобнее определить, что всё работает так, как ожидается. Как правило реалистичное значение для этой константы составляет от 1 до 10 миллисекунд. Мы уменьшим значение TICK до разумных 10 мс позже.

Субфаза D: Планировщик

В этой подфазе мы реализуем простенький round-robin планировщик. Основная работа ведётся в файлах kernel/src/process/scheduler.rs, kernel/src/process/process.rs и kernel/src/traps/irq.rs.

Планирование

Основная зона ответственности планировщика включает в себя определение того, какую задачу выполнять после текущей. При этом под задачей подразумевается что-то, что требует выполнения на CPU. Наша операционная система относительно проста. По этому концепция планировщика будет связанна в основном с процессами. Таким образом наш планировщик будет отвечать за определение того, какой процесс будет выполняться дальше. Если таковой имеется.

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

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

• Ready
  Задача, которая готова к выполнению. Планировщик выполнит задачу, когда подойдёт её очередь.
• Running
  Задача, которая выполняется прямо сейчас.
• Waiting
  Задача, которая ожидает какого либо события и не готова к выполнению до тех пор, пока это событие не произойдёт. Планировщик проверяет, произошло ли событие, когда подходит очередь такой задачи. Если к этому времени событие не произошло, то процесс теряет свою очередь на выполнение и будет проверен в будущем. Т.е. такую задачу планировщик отправит в конец очереди.

Перечисление State из kernel/src/process/state.rs представляет эти состояния. Каждая структура процесса связана с этим State, которым в свою очередь управляет планировщик. Обратите внимание, что состояние Waiting содержит функцию, которую планировщик может использовать для того, чтоб определить, произошло ли ожидаемое событие.

На приведённой ниже диаграмме показаны шесть циклов round-robin планировщика. Задача C ожидает появления события, которое происходит где-то между 3 и 5 раундами.

Немного об этих раундах:

1. В первом раунде в очереди есть три задачи: B, C, D и задача, которая выполняется в данный момент: A. При этом C находится в состоянии ожидания, а остальные работают, либо готовы к работе. Как только квант A исчерпан, он перемещается в конец очереди.
2. Теперь подходит очередь на выполнение для задачи B. По исчерпанию кванта эта задача также перемещается в конец очереди.
3. Поскольку C ожидает события, планировщик проверяет, произошло ли уже это событие. На данный момент это не так. Значит задача C пропускает свой квант времени и право занять время процессора переходит к задаче D. Как только квант D исчерпывает себя, эта задача переводится в конец очереди.
4. Этот раунд на диаграмме не показан. Для A выделяется квант времени и как только оный заканчивается, задача A опять перемещается в конец очереди.
5. B захватывает время процессора и перемещается в конец очереди.
6. C всё ещё ожидает события. Планировщик проверяет, произошло ли это событие. На этот раз событие таки произошло. А значит задаче C выделяется её заслуженный квант времени.

Было бы выгоднее разделять готовые и ожидающие задачи? [wait-queue]

Альтернативная реализация round-robin планировщика содержит в себе две очереди: очередь готовых к выполнению задач и очередь задач, ожидающих события. Как бы вы могли бы использовать очереди в round-robin планировщике? Ожидаете ли вы, что производительность (средняя задержка/производительность задачи) будет лучше/хуже?

Структура кода

Структура Scheduler из kernel/src/process/scheduler.rs содержит в себе очередь процессов, ожидающих своей очереди. Процессы добавляются в очередь через метод Scheduler::add(). Этот метод помимо прочего отвечает за назначение уникальных идентификаторов процессам. Эти идентификаторы хранятся в регистре TPIDR.

Когда требуется вмешательство в состояние планирования, вызывается метод Scheduler::switch(). Этот метод изменяет состояние текущего процесса на new_state, сохраняет текущий trap frame в текущем процессе, находит следующий процесс для выполнения и восстанавливает его trap frame. Если нет процесса, готового к выполнению, то планировщик ждёт, пока такой процесс не появится.

Для того, чтоб определить, готов ли процесс к выполнению, должен быть вызван метод process.is_ready(), определённый в файлике kernel/src/process/process.rs. Этот метод возвращает true, если состояние равно Ready, либо произошло ожидаемое процессом событие.

В конце планировщик должен вызываться каждые TICK микросекунд. Прерывания таймера, установленные и настроенные в предыдущей подфазе станут одним из основных источников изменения состояния планировщика. Обратите внимание на обеспечение типом GlobalScheduler потокобезопастной обёртки вокруг методов add() и switch() типа Scheduler.

Почему планировщик не знает нового состояния? [new-state]

Метод scheduler.switch() требует, чтоб вызывающий передал новое состояние текущего процесса. Это означает, что планировщик не знает, каким будет следующее состояние процесса. Почему это сделано таким образом?

Реализация

Теперь у нас всё готово для реализации round-robin планировщика. Рекомендуемый путь реализации таков:

1. Реализовать метод Process::is_ready() из kernel/src/process/process.rs
   Функция mem::replace() должна оказаться весьма полезной тут.
2. Реализовать всё необходимое для структуры Scheduler из kernel/src/process/scheduler.rs.
   При этом метод switch() требует, чтоб вы блокировали выполнение до тех пор, пока не найдётся процесс, к которому можно переключиться. До тех пор следует стараться сохранять энергию в максимально возможной степени. Для того, чтоб перевести процессор в режим сохранения энергии, следует использовать инструкцию wfi (wait for interrupt). Выполнение этой инструкции приводит к тому, что проц переходит в состояние с малым потреблением энергии и ждёт, пока не произойдёт какое либо прерывание от выполнения чего либо. Вы должны добавить необходимые обёртки для этого в файл aarch64.rs.
3. **Настроить планировщик в методе GlobalScheduler::start().
   Глобальная версия планировщика должна быть создана и инициализирована до того, как выполнится первый процесс. Первый процесс должен присутствовать в очереди планировщика перед тем, как он начнёт выполняться.
4. Вызывать планировщик при прерываниях таймера.
   Вызовите SCHEDULER.switch() в обработчике прерывания таймера для того, чтоб переключить контекст между текущим и следующим процессами.

Проверьте работу планировщика, запустив несколько процессов в GlobalScheduler::start(). Для этого вам нужно будет выделить новые процессы и настроить их соответствующим образом. Вероятно вы захотите создать другую точку входа (extern-функцию) для каждого нового процесса, для того, чтоб эти процессы можно было различать между собой. Убедитесь, что вы добавляете процессы в очередь планировщика в правильном порядке.

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

Не допускайте переполнения при генерации идентификатора процесса!

Вы не должны использовать unsafe при реализации всех этих методов и процедур!

Используйте mem::replace() для получения владения над state процесса.

Почему правильно ожидать прерываний, когда нет готовых процессов? [wfi]

Использование команды wfi для ожидания готовности процесса означает, что процессор останавливается до тех пор, пока не поступит прерывание. Если прерывание не выполняется после выполнения wfi, то процесс планирования не запустится никогда. И тем не менее, почему это правильное поведение?

Подсказка: Подумайте о сценариях, в которых процесс находится в состоянии ожидания.

Субфаза E: Sleep

В этой подфазе вы реализуете системный вызов sleep и вызов команд оболочки. Основная работа ведётся в файле kernel/src/shell.rs и в папке kernel/src/traps.

Системные вызовы

Системный вызов — это не что иное, как особый вид исключения процессора. Когда выполняется команда svc #n, генерируется синхронное исключение с синдромом Svc(n), где n — число, соответствующее данному системному вызову. Это похоже на то, как brk #n генерирует исключение Brk(n), за исключением того, что предпочтительным адресом возврата является инструкция после вызова команды svc вместо адреса самой инструкции. Системные вызовы — это механизм, который используют пользовательские процессы для взаимодействия с различными частями операционной системы, для использования которых у процессов нет достаточных привилегий.

В типичной операционной системе может предоставляться около 100 системных вызовов для получения информации об оборудовании и других нужд. В этой подфазе мы будем реализовывать системный вызов sleep. Данный системный вызов заставляет планировщик убрать процесс из очереди на планирование на некоторое время. Другими словами он просит усыпить процесс.

Соглашение о системных вызовах

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

• Системный вызов n вызывается при помощи svc #n.
• До 7 параметров можно передать через регистры x0...x6.
• До 7 параметров можно возвратить через регистры x0...x6.
• Регистр x7 используется для обозначения возникших ошибок.
  
  • Если регистр x7 содержит 0 — ошибок нет.
  • Если регистр x7 содержит 1 — такого системного вызова не существует.
  • Если регистр x7 содержит что-то ещё — это число используется для обозначения какой либо ошибки данного системного вызова.
• Все остальные регистры и состояние программы сохраняются ядром в первозданном виде.

Таким образом для того, чтоб вызвать придуманный мной только что системный вызов 7, который принимает два параметра с типами u32 и u64, а потом возвращает два значение с типами u64, мы можем написать следующий код, который использует ассемблерные вставки:

fn syscall_7(a: u32, b: u64) -> Result<(u64, u64), Error> {
    let error: u64;
    let result_one: u64;
    let result_two: u64;
    unsafe {
        asm!("mov w0, $3
              mov x1, $4
              svc 7
              mov $0, x0
              mov $1, x1
              mov $2, x7"
              : "=r"(result_one), "=r"(result_two), "=r"(error)
              : "r"(a), "r"(b)
              : "x0", "x1", "x7")
    }

    if error != 0 {
        Err(Error::from(error))
    } else {
        Ok((result_one, result_two))
    }
}

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

Почему мы используем отдельный регистр для передачи значения ошибки? [syscall-error]

Большинство unix-подобных операционных систем, включая Linux, перегружают первый регистр результата (x0 в нашем случае) в качестве регистра ошибок. В этих соглашениях отрицательные значения с определённым диапазоном представляют коды ошибок. Все остальные значения интерпретируются как успешные возвращаемые значения. В чём преимущество того, подхода который используем мы? Каков недостаток этого подхода?

Системный вызов Sleep

Системный вызов sleep будет иметь номер 1 в нашей операционной системе. Данный сисколл будет иметь один единственный параметр с типом u32. Количество миллисекунд, на которые процесс должен быть приостановлен. Помимо значения ошибки он возвращает один параметр с типом u32. Количество миллисекунд, прошедшие между первоначальным запросом процесса и моментом пробуждения этого процесса. В псевдокоде его сигнатура будет такой:

(1) sleep(u32) -> u32

В каких случаях разница во времени будет отличаться от запрошенного? [sleep-elapsed]

В каких ситуациях (если такие вообще есть) будет возвращаться значение, которое будет отличаться от входного значения? В каких ситуациях, если они есть, это значения будут идентичны? Как вы думаете, какова относительная вероятность каждого из этих случаев?

Реализация

Сейчас мы реализуем системный вызов sleep. Начните с модификации функции handle_exception из kernel/src/traps/mod.rs. Надо, чтоб она распознавала исключения системных вызовов и передавала управление в функцию handle_syscall из kernel/src/traps/syscalls.rs. Затем реализуйте эту самую handle_syscall. Эта функция должна выделять вызов sleep среди прочих и изменять состояние требуемого процесса. Вероятно придётся создать Box<FnMut>, который будет содержать замыкание. Это будет выглядеть примерно следующим образом:

let boxed_fnmut = Box::new(move |p| {
    // используем `p`
});

Про замыкания можно почитать книжечку по Rust.

После всего этого добавьте команду sleep <ms> к командной оболочке. Эта команда должна парсить ms и вызывать очевидно какой системный вызов (он у нас один пока).

Проверьте свою реализацию, вызвав sleep из оболочки пользовательского пространства. Убедитесь, что процесс не будет планироваться на выполнение до тех пор, пока не проспит достаточное время. Все остальные процесс при этом всём должны по прежнему правильно планироваться. Затем убедитесь, что никакой процесс не запланирован, если все процессы спят. Как только ваша реализация будет готова — наслаждайтесь и ожидайте выхода следующей серии.

Подсказки:

Обработчик системного вызова sleep должен взаимодействовать с планировщиком.

Напомним, что замыкания могут захватывать значения из своего окружения.

Тип u32 реализует FromStr.

---

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