Прежде чем перейти к статье, хочу вам представить, экономическую онлайн игру Brave Knights, в которой вы можете играть и зарабатывать. Регистируйтесь, играйте и зарабатывайте!
Два года назад я начал работать разработчиком ПО. Иногда я рассказывал своим коллегам о студенческом проекте, которым занимался на третьем курсе университета, и они восприняли его настолько хорошо, что я решил написать этот пост1.
Позвольте задать вам вопрос: вы когда-нибудь проектировали собственную архитектуру набора команд (ISA), создавали на FPGA процессор на основе этой ISA и собирали для него компилятор? Запускали ли вы операционную систему на этом процессоре?
А у нас это получилось.
В этом посте я расскажу о своей учёбе в 2015 году, о четырёх месяцах создания самодельного CPU на самодельной архитектуре набора команд RISC, создании самодельного тулчейна C и портировании на этот процессор Unix-подобной ОС Xv6.
Процессорный эксперимент в Токийском университете
Всё это делалось в рамках студенческого экспериментального проекта под названием CPU Experiment. Давайте начнём с того, что же такое CPU experiment.
CPU experiment — это небольшое популярное упражнение, проводящееся зимой третьего курса моей Кафедры информационных наук Токийского университета. В этом эксперименте студентов разделяют на группы по четыре-пять человек. Каждая группа проектирует собственную процессорную архитектуру, реализует её на FPGA, собирает компилятор подмножества OCaml для этого процессора, а затем запускает на процессоре определённую программу трассировки лучей. Обычно за каждую из задач (CPU, FPU, симулятор CPU и компилятор) отвечает один-два человека. В своей Group 6 я занимался CPU.
Это упражнение хорошо известно тем, что в нём от студентов ждут высокого уровня самообучения. Преподаватель просто даёт студентам задание взять написанную на OCaml программу трассировки лучей и запустить её на CPU, реализованном на FPGA, после чего занятие завершается. Он почти ничего не рассказывает о конкретных шагах по созданию CPU и компиляторов. Студенты сами изучают, как воплотить общие знания о процессорах и компиляторах, полученные на предыдущих лекциях, в реальные цепи и код. Это очень сложное упражнение, зато увлекательное и познавательное.
Запустим на собственном CPU операционную систему
Как вы могли заметить, я ничего не говорил об операционной системе, поэтому требуется объяснение.
Обычно эксперимент проходит следующим образом: во-первых, вы создаёте надёжно работающий CPU, вне зависимости от скорости его работы. Если вы сделаете работающий CPU и успешно запустите программу трассировки лучей, то получите за эксперимент зачёт. После этого вы сможете отдохнуть. Традиционно это время отдыха используется для дальнейшего ускорения своего CPU. В предыдущих экспериментах студенты создавали CPU с внеочередным (out-of-order) исполнением команд, VLIEW CPU, многоядерный CPU и даже суперскалярный CPU, что, по-моему, потрясающе.
Однако некоторые команды вкладывают больше энергии в реализацию развлекательных вещей, например, запуск игр или воспроизведение музыки, подключая к своим CPU динамик. В шестой группе, где находился я, была компания студентов, любивших развлечения, поэтому в качестве цели команды мы выбрали запуск ОС.
В результате к этой идее проявили интерес другие группы, была образована объединённая группа Group X примерно из восьми человек, целью которой стало «Давайте запустим на собственном CPU операционную систему!»
Хотя в Group 6 я отвечал за создание процессора, на этот раз я решил стать руководителем команды разработки ОС в Group X. Поэтому этот пост в основном написан с точки зрения команды разработчиков ОС, хотя я, разумеется, расскажу и про общие результаты группы.
Xv6
В качестве портируемой ОС мы выбрали Xv6 — простую ОС, источником вдохновения для которой стал Unix v6; её создал с образовательными целями MIT. Xv6, в отличие от Unix v6, написана на ANSI C и выполняется на x86. Xv6 — образовательная ОС, поэтому имеет довольно ограниченную функциональность, но в качестве простой Unix-подобной ОС она обладает достаточным набором возможностей. Подробнее о Xv6 можно прочитать на Википедии или в репозитории GitHub.
Сложности
При портировании xv6 было множество сложностей с программной стороны, потому что мы стремились создать всё с нуля.
1. Компилятор C и тулчейн для Xv6
В эксперименте с CPU мы обычно создаём компилятор ML. Естественно, им невозможно компилировать код Xv6, написанный на C.
2. Какие функции процессора необходимы для операционной системы?
Защита привилегий? Виртуальный адрес? Прерывание? Да, по лекциям мы имели общее представление о том, что делает операционная система, но не обладали достаточно полными знаниями, чтобы понять, какие конкретно функции CPU помогут нам реализовать задачу.
3. А что насчёт симулятора?
У нас был симулятор, который являлся одной из основных частей эксперимента с CPU, но он был простым и выполнял одну команду за другой, в нём не существовало ни прерываний, ни преобразования виртуальных адресов.
4. Плохая портируемость xv6
Xv6 не очень хорошо портируется. Например, в ней есть допущение о том, что
char занимает 1 байт, а int — 4 байта, и она выполняет активные манипуляции со стеком. Название Xv6, насколько я понимаю, взято от x86 и Unix «v6», поэтому это в общем-то естественно.У нас было много сомнений, но в декабре мы начали процесс портирования ОС Group X. Далее я буду писать о том, что мы делали, примерно в хронологическом порядке. Пост немного длинноват, поэтому если вы сразу хотите взглянуть на готовый результат, то перейдите к разделу «Март».
Конец ноября — приступаем к работе над компилятором
Первой задачей, ответ на который мы нашли, был компилятор и тулчейн. На удивление, наше решение заключалось в создании с нуля компилятора C89. Честно говоря, я не представлял, что мы выберем такой путь. Помню, как мы сначала обсуждали с Юити, отвечавшим в Group X за CPU, создание порта gcc или llvm.
Однако один из членов команды, Кэйити, внезапно сообщил нам, что написал компилятор C, и показал прототип компилятора с простым парсером и эмиттером. Нам показалось, что интереснее будет написать тулчейн с нуля, поэтому мы решили написать компилятор сами.
Юити и Ватару из Group 3, уже завершивший базовую часть эксперимента, присоединились к Кэйити, и так появилась команда разработки компилятора Group X. Позже мы назвали наш компилятор Ucc.
Середина декабря — появилась команда разработки ОС!
В начале декабря я завершил свой процессор, и Group 6 закончила базовую часть эксперимента с CPU. Поэтому мы перешли к интересной части — задаче по портированию ОС для Group X. В то время я и Сёхэй из Group 6 начали работать в Group X, став командой разработки ОС. Тогда же к нам присоединился Масаеси.
Базовая часть эксперимента: написание CPU
Кстати, я думаю, что немногим разработчикам ПО когда-нибудь доводилось писать CPU, поэтому немного расскажу и о создании CPU.
Сегодня для создания CPU необязательно соединять отдельные перемычки на монтажной плате; можно писать схему на языке описания аппаратуры (Hardware Description Language). Затем при помощи Vivado или Quartus код на HDL синтезируется в реальную схему. Этот процесс называется синтезом логических схем, а не компиляцией.
HDL и языки программирования похожи друг на друга, но и отличаются. Воспринимайте его как написание функции, связывающей состояние сигналов регистров с другим состоянием сигналов, создаваемым синхрогенератором или входящим сигналом. Если вы хотите попробовать настоящее реактивное программирование, то рекомендую писать на HDL. Также стоит не забывать, что при написании HDL следует всегда заботиться о том, чтобы распространение записываемых вами сигналов HDL завершалось за один такт. В противном случае поведение ваших схем будет непостижимым для людей.
Самая сложная часть самой разработки заключалась в том, что синтез логических схем занимал огромное количество времени. Часто бывало так, что после запуска синтеза нам приходилось ждать по 30 минут, поэтому запустив синтез, я играл в Smash Bros. Melee с другими проектировщиками CPU, которые тоже ждали завершения синтеза. Кстати, мой любимый персонаж — Sheik.
Конец декабря-середина января — обучаемся, портируя Xv6 на MIPS
Мы начали искать ответ на вопрос: «Какие функции процессора необходимы для операционной системы?»
После создания команды разработки ОС мы приступили к еженедельным сессиям чтения исходного кода Xv6.
В то же время я начал портировать Xv6 на MIPS. Частично это было нужно для того, чтобы узнать, как работает ОС на уровне реализации, а частично потому, что, как оказалось, порта Xv6 на MIPS не существует. Примерно за неделю я завершил порт до этапа начала планировщика процессов. Во время процесса портирования я активно изучал MIPS и как работает xv6 на x86. Благодаря этому я понял на уровне реализации механизмы прерываний и MMU. На этом этапе я получил глубокое понимание функциональности CPU, требуемой для Xv6.
Кроме того, в середине января мы упорно работали над компиляцией всего кода Xv6, превращая его отдельные части в комментарии. В результате этого Xv6 в симулятора нашей самодельной архитектуры отобразил первое сообщение последовательности загрузки:
xv6...
cpu0: starting...
В то же самое время это означало, что на данном этапе Ucc уже достаточно вырос, чтобы компилировать бóльшую часть xv6, и это было замечательно2.
Февраль — родился наш CPU под названием GAIA!
В порте на MIPS я завершил инициализацию PIC, что представляло огромную проблему, а также завершил реализацию обработчика прерываний. В результате этого портирование Xv6 на MIPS было завершено до этапа запуска первой пользовательской программы.
На основании своего опыта я создал проект спецификации прерываний и преобразования виртуальных адресов нашего самодельного CPU. Чтобы не усложнять его, мы решили не включать в него механизмы аппаратных привилегий, например, кольцевую защиту. Для преобразования виртуальных адресов мы решили, как и в x86, использовать методику аппаратного обхода страниц. Может показаться, что это сложно реализовать аппаратно, но мы посчитали, что так будет менее затратно, если мы пожертвуем скоростью и исключим реализацию TLB. В конечном итоге, позже Юити создал превосходное ядро CPU, в которое с самого начала был установлен TLB.
Юити завершил общую архитектуру набора команд нашего процессора. Он назвал наш CPU GAIA. Обычно в экспериментах с CPU мы не реализуем ни прерываний, ни MMU. Однако Юити начал реализовывать их для Xv6 на основании рефакторизованной версии процессора Group 3.
В дальнейшем я перейду к еженедельным записям, потому что с этого момента процесс начнёт развиваться быстро!
Первая неделя
Вместо того, чтобы просто закомментировать последовательности загрузки, Масаеси начал реализацию настоящей инициализации нашего CPU, а Сёхэй переписал код ассемблера x86 операционной системы Xv6 под нашу самодельную архитектуру. Я добавил в симулятор возможность симуляции прерываний, которую Ватару создал в базовой части экспериментов с CPU, а также завершил поддержку преобразования виртуальных адресов. Мы реализовали в симуляторе функциональность, достаточную для запуска ОС.
Вторая неделя
Я создал примитивный компоновщик для нашей архитектуры, чтобы собирать Xv6 и её двоичные объекты. Сёхэй работал над реализацией обработчика прерываний, и это была сложная задача. Прерывания трудно понять, тяжело разобраться с потоком, тяжело отлаживать, тяжело разрабатывать.
Когда я портировал Xv6 на MIPS, у меня был GDB, поэтому было довольно сносно, но в нашем эмуляторе не было никаких функций отладки, поэтому её выполнять, наверно, было очень трудно. Сёхэй не смог выдержать сложность отладки, поэтому он добавил в симулятор дизассемблер и отладочную функцию дампа. После этого отладочные функции симулятора были быстро усовершенствованы командой разработки ОС, и симулятор, наконец, вырос и стал похожим на это изображение:
Третья неделя
Превозмогая различные трудности, мы продолжали портирование Xv6, но ОС по-прежнему не работала.
В частности, вызывала много проблем спецификация Ucc, в которой
char и int занимали 32 бита. Это была не вина Ucc. На самом деле, спецификация C требует только, чтобы sizeof(char) == 1 и sizeof(char) <= sizeof(int), поэтому в этом не было нарушений.Однако, xv6 написана для x86, поэтому она предполагает, что
sizeof(int) == 4 и добавляет константы к значению указателя, что приводило ко множеству противоречий. Поскольку создаваемый этим баг было так трудно найти, а объём был настолько велик, что в конечном итоге мы решили указать в Ucc, что char равен 8 битам.Делегировав проблему 32-битного char команде разработчиков Ucc, я написал инициализацию страничной адресации этапа начальных вводов, и путём проб и ошибок пытался заставить правильно работать прерывания.
В конечном итоге, мы упорно трудились над решением задачи 4, «Плохой портируемости xv6».
27, 28 февраля
Перечитав Slack, я увидел, что за этот день был сделан большой шаг вперёд. После того, как команда разработчиков Ucc очень быстро завершила изменение, сделав
char 8-битным, мы упорно работали над большим объёмом отладки. Наконец, наша первая пользовательская программа init всё-таки заработала!После этого мы так продвинулись в портировании приложений пользовательских процессов, что я ещё не успел перенести это в порт на MIPS. По ходу дела мы обнаружили и устранили множество трудновоспроизводимых багов и несоответствий в спецификации прерываний; тем не менее, нам как-то удалось всё это преодолеть.
Одна интересная исправленная нами ошибка заключалась в проблеме с алиасом кэша. Процессор GAIA выбирал в качестве индекса кэша виртуальный адрес вместо физического. Так получалось потому, что он позволяет при поиске кэшей пропускать преобразование виртуальных адресов. Однако из-за этого мы обнаружили, что между кэшами возникает противоречие, поскольку несколько кэшей виртуальных адресов могут указывать на один физический адрес. При обновлении кэша одного виртуального адреса кэши других виртуальных адресов, указывающих на тот же физический адрес, не обновлялись.
Этот баг сложно было устранить с низкими затратами на стороне оборудовании, поэтому мы устранили его, добавив в Xv6 «цвет страниц». Для каждой строки кэша добавляется «цвет» и страницы выделяются так, что виртуальные адреса, указывающие на один физический адрес, всегда получают одинаковый цвет. Это означает, что виртуальные адреса, указывающие на один физический адрес, всегда будут иметь только один кэш. Так мы гарантируем, что GAIA никогда не будет иметь нескольких кэшей с общим физическим адресом.
Март — Xv6 запускается!
Первого марта порт xv6 был завершён. Теперь xv6 работала в симуляторе!
Развлечений всегда должно быть с запасом
Изначально порт Xv6 рассматривался как развлечение, и поскольку Xv6 начала работать в симуляторе, мы стали трудиться над тем, чтобы развлечений стало ещё больше.
Во-первых, примерно за 4 часа Масаеси создал команду
sl, запускаемую на нашем Xv6.
Сёхэй захотел написать «Сапёра».
В это время Юити завершил реализацию процессора Group X. Реальный CPU работал гораздо быстрее симулятора, благодаря чему игру стало проще разрабатывать и играть в неё. Тогда же было создано очень качественное приложение 2048.
Эта игра 2048 получилась очень качественной, Юити постоянно в неё играл. Кстати, 2048 использует нелинейный буферизованный ввод, но в xv6 изначально этой функции не было. Для поддержки этой функции в дополнение к
read и write в качестве devsw-действия было добавлено ioctl, а также связанные с termios функции для управления ICANON и echo. То есть единственная Xv6, способная играть в 2048 с подобной степенью полноты, есть только на GAIA.Кстати, чтобы реализовать в Xv6 более близкую к Unix V6 схему, было бы лучше, по моему мнению, добавить системные вызовы
gtty и stty. Однако я использовал ioctl, потому что Xv6 не имеет концепции tty, а также потому что ioctl появилась в следующей версии (V7), которая исторически близка к V6.Есть и более крутые новости: на Xv6-GAIA появился небольшой ассемблер, созданный Кэйити. Также на нём есть миниатюрный vi, созданный Сёхэем. Только представьте, что можно сделать с этими двумя инструментами.
Это интерактивное программирование на FPGA!
Для эксперимента с CPU это довольно впечатляющее демо, ведь на этом процессоре нет никаких интерактивных программ.
Самое лучшее демо
Исходная задача эксперимента с CPU звучала так: «Запустить на самодельном процессоре определённую программу трассировки лучей». Теперь, когда у нас есть работающая на процессоре операционная система, мы все знаем, что нужно сделать, правда? Мы решили запустить программу трассировки лучей «в ОС» нашего собственного CPU. У нас возникло несколько багов, однако нам удалось завершить её за час до финальной презентации.
Итак, мы выполнили то, о чём наверняка хотя бы раз шутил каждый студент нашей кафедры: запустили операционную систему на CPU, а поверх неё — программу трассировки лучей.
Взгляд из 2020 года
По сути, всё написанное выше является переработанным вариантом моего поста, написанного в 2015 году. Перечитывая его сегодня, я вижу свою техническую неопытность того времени, однако сделанное нами определённо заслуживает восхищения.
Кстати, вы можете увидеть, как в то время выглядела Xv6, прямо в браузере, пройдя по ссылке! После эксперимента с CPU я портировал при помощи Emscripten наш симулятор GAIA на JavaScript. Давайте попробуем запустить наши
sl, minesweeper и 2048.xv6...
cpu0: starting
init: starting sh
$
Также стоит сказать, что портирование Xv6 на MIPS, которое не было закончено во время эксперимента с CPU, завершили месяц спустя. Репозиторий GitHub находится здесь.
После того, как мы опубликовали в 2015 году пост о челлендже Group X, следующие поколения студентов продолжили брать новые задания, связанные с ОС.
В 2018 году одни студенты запустили собственную ОС поверх самодельного CPU, а в 2019 году группа других студентов запустила собственную ОС, использовав в ISA самодельного CPU команды RISC-V. Кроме того, группа в 2020 году наконец-то запустила операционную систему Linux поверх самодельного CPU, в качестве ISA которого также использовалась RISC-V3.
Я уверен, что в будущем будет гораздо больше таких историй, поэтому следите за ними. Лично я ожидаю, что когда-нибудь кто-то запустит Linux на собственной ISA, или запустит на ней виртуальную машину.
Обычно говорят, что изобретать велосипеды заново не стоит, но в процессе изобретения можно довольно многому научиться. Он заставил меня осознать, что я не понимал всего этого настолько хорошо, чтобы реализовать всё с нуля. Кроме того, я рекомендую вам это сделать, потому что это чертовски увлекательно!
Это конец истории нашего эксперимента с CPU. Если вы заинтересовались изобретением замечательного велосипеда, то попробуйте создать процессор или портировать на него ОС.
В конце я хочу рассказать об участниках Group X.
- Такая Саэки — это я. Xv6 (Xv6 GAIA и Xv6 MIPS)
- Сёхэй Кобаяси — Xv6
- Масаеси Хаяси — Xv6
- Кэйити Ватанабэ — Ucc
- Ватару Инариба — Ucc, симулятор CPU
- Юити Нисиваки — GAIA, Ucc
- Масаки Вага — FPU
- Рюити Кирио — разные задачи
- Если вы знаете японский, то можете прочитать мой предыдущий пост здесь. Я работаю в Microsoft, и не все мои коллеги понимают японский, поэтому я написал этот пост на английском.
- Кэйити сказал мне, что одной из причин быстрого роста Ucc заключалась в том, что они писали Ucc на OCaml. OCaml позволяет с лёгкостью манипулировать структурой дерева без багов указателей. Кстати, если вас интересует этап препроцессора, то мы использовали Clang CPP. Вы знали, что Clang CPP можно использовать как независимую команду? Кэйити написал на японском свою статью о команде разработчиков компилятора.
- Все статьи написаны на японском. Статьи группы, запускавшей собственную ОС поверх самодельного CPU в 2018 году находятся здесь, статьи группы, запускавшей свою ОС на процессоре RISC-V в 2019 году — здесь, а статьи группы, запустившей Linux на своём процессоре RISC-V в 2020 году — здесь.
