Главная » Хабрахабр » [Перевод] Операционные системы с нуля; уровень 3 (старшая половина)

[Перевод] Операционные системы с нуля; уровень 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

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

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

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

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

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

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

Trap Frame

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

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

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

  • x0x30 — т.е. все 64-битные регистры, коих целых 31 штука.
  • q0q31 — все 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. После того, как мы положим всё необходимое на стек, его содержимое должно выглядеть примерно таким вот образом: После того, как обработчик отдаст управление обратно ассемблерному коду, нам потребуется это состояние вернуть, каким оно там было.

trap frame

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

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

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

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

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

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

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

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

Реализация

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

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

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

// кладём на стек значения регистров `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

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

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

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

Содержимое вашего 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]

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

Как мы могли бы использовать эту возможность для того, чтоб лениво подгружать эти регистры только в тех случаях, когда они реально используются? Архитектура 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]

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

Реализация

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

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

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

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

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

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

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

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

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

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

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

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

  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.

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

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

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

Реализация

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

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

  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");
}

Теперь kmain должна содержать три инициализирующих вызова. Как только вы реализуете всё необходимое — добавьте вызов SCHEDULER.start() в 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 прерывания — это не что иное, как исключения определённого класса. Они генерируются внешним источником в ответ на внешние события.

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

int-chain

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

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

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

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

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

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

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

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

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

Процессор

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

В прошлой подфазе мы настроили получение исключений из 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 будет заниматься подтверждением и обработкой прерываний.

Реализация

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

round-robin

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

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

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

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

Прерывания таймера, установленные и настроенные в предыдущей подфазе станут одним из основных источников изменения состояния планировщика. В конце планировщик должен вызываться каждые 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

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

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

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

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

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

Наша операционная система будет использовать модифицированную версию соглашений, которую используют некоторые 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

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

(1) sleep(u32) -> u32

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

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

Реализация

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

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

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

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

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

Подсказки:

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

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

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

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


Оставить комментарий

Ваш email нигде не будет показан
Обязательные для заполнения поля помечены *

*

x

Ещё Hi-Tech Интересное!

«ПК», но не «персональный компьютер»: интервью с программным комитетом Joker

Кнопочки на сайте видны всем — но при взгляде со стороны можно никогда не задуматься о бэкенде, без которого эти кнопочки не работали бы. Любому Java-разработчику понятно, сколько важного остаётся незаметным для конечного пользователя. «Фронтендом» можно считать спикеров: они видны ...

Мастер осанки: остаться в живых

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