Takaya Saeki作者Panda编译

东京大学版「一生一芯」:自制CPU、C编译器,还成功运行了类Unix系统

前段时间,中国科学院大学的「一生一芯」计划引发热议,五位本科生带着自己设计的处理器芯片正式毕业,被称为「最硬核毕业证」。其实,东京大学信息科学系也有一个自制 CPU 的实践课程。近日,微软软件工程师 Takaya Saeki 刊文回顾了五年前他们小组的 CPU 实验项目:不仅通过自学自制了 CPU、C 编译器,还成功移植了一个类 Unix 操作系统(Xv6)。虽然回顾的是五年前的往事,但这篇文章应该也能为芯片和操作系统人才培养工作带来一些启发。

所有这一切都源自一个学生实验项目:CPU Experiment(CPU 实验)。首先说说这个 CPU 实验是什么。

CPU 实验是东京大学信息科学系一个小有名气的实践课程,通常在大三的冬季进行。在该实验中,学生会被分成小组,每组四、五个人。每一组都要设计一种自己的 CPU 架构,在 FPGA 上实现它,为该 CPU 构建一个 OCaml 子集编译器,然后在该 CPU 上运行一个给定的光线追踪程序。通常来说,CPU、FPU、CPU 模拟器和编译器都各由一两个人负责。我负责第 6 组的 CPU 部分。

这个实践课程的有名之处在于对自学能力的高度期望。导师向学生们下达了任务目标:「把这个用 OCaml 写的光线追踪程序运行在你们用 FPGA 实现的 CPU 上」,然后就下课了。对于编写 CPU 和编译器的具体步骤,他不会多说。学生需要自己学习如何将学过的有关 CPU 和编译器的一般知识转化成实际成品,这将涉及到实际的电路和代码。是的,这个实践课程确实很难,但也很激动人心且极具教育意义。

在我们自己的 CPU 上运行操作系统

你可能已经注意到了,我还没谈到操作系统。我来稍微解释一下。

通常来说,这个实验会这样进行。首先,做出一个能可靠工作的 CPU,不管计算速度如何。如果做出了 CPU 并成功运行了那个光线追踪程序,就能得到这个实践课程的学分。之后,你的团队就自由了。通常来说,这些自由时间会被用于 CPU 提速。在过去的实验中,学生做出过乱序 CPU、VLIEW CPU、多核 CPU 甚至超标量 CPU,确实很了不起。

但是,有些团队则把更多精力放到了一些有趣任务上,比如运行游戏或将 CPU 与扬声器连接来播放音乐。我们第 6 组也是一个热爱娱乐的小组,而我们决定将目标设定为运行一个操作系统

结果,其它一些小组也对这个想法产生了兴趣。于是,一个包含 8 个人的联合小组——Group X 成立了。我们的目标是:「在我们自己的 CPU 上运行 OS!」

尽管我负责第 6 组的 CPU 创建工作,但这一次我选择当 Group X 的领导者。因此,本文主要是从 OS 团队角度写作的,不过我也会介绍 Group X 的整体成果。

Xv6

对于要移植的 OS,我们选择了 Xv6,这是一个由 Unix v6 启发的简单操作系统,是 MIT 为教育目的构建的。不同于 Unix v6,Xv6 是用 ANSI C 编写的,而且运行在 x86 架构上。Xv6 是一款教育用 OS,所以功能有些简陋,但作为一款简单的类 Unix 操作系统,功能已经足够了。有关 Xv6 的更多信息可访问其 GitHub 代码库:https://github.com/mit-pdos/xv6-public

挑战

在移植 Xv6 时,光是软件方面就有一大堆难题,因为我们在尝试从头开始构建一切。

1. 用于 Xv6 的 C 编译器和工具链。

在 CPU 实验中,我们通常会创建一个 ML 编译器。很自然,这样无法编译 Xv6 的 C 代码。

2. 操作系统需要 CPU 具备哪些功能?

特权保护?虚拟地址?中断?是的,我们在课堂上已经获得了对操作系统的整体理解,但那时候我们对各个 CPU 功能的具体作用还没有真正的切身体会。

3. 模拟器呢?

我们已经在 CPU 实验的核心任务部分做了一个模拟器,但那个模拟器很简单,只能逐一执行指令,而且没有中断和虚拟地址转换。

4.Xv6 的可移植性差

Xv6 很难移植。举个例子,它假设 char 是 1 个字节,而 int 是 4 个字节,并会大量操作堆栈。好吧,我猜 Xv6 这个名字实际上来自 x86 和 Unix v6,所以这种设计当然很自然。

我们有过很多担忧,但还是在 12 月份开始了 Group X 的 OS 移植项目。

接下来,我将大致按时间顺序编写我们的工作经历。这个过程会有一点长,所以如果你想快些看到结果,请跳转至「三月」部分。

十一月下旬:开始开发编译器

我们找到答案的第一个问题是编译器和工具链。有点意外的是,我们决定从头开始写 C89 编译器。说老实话,我之前没想到我们会选这条路。我记得我和 Yuichi(后来负责 Group X 的 CPU)一开始讨论过移植 gcc 或 llvm。

但是,一位团队成员 Keiichi 突然说他已经写好了一个 C 编译器并向我们展示了一个编译器原型,其带有一个简单的解释器和发射器。从头开始写工具链似乎更有意思,因此我们决定自己写一个编译器。

来自第 3 组的 Yuichi 和 Wataru 已经结束了那一年 CPU 实验的核心任务,于是他们加入了 Keiichi,组成了 Group X 的编译器团队。后来我们将我们的编译器命名为 Ucc。

十二月中旬:OS 团队上线!

十二月初,我完成了自己的 CPU,第 6 组完成了 CPU 实验的核心部分。于是我们开始做有趣的部分:Group X 的 OS 移植任务。这时候,第 6 组的我和 Shohei 开始了 Group X 的工作并组成了 OS 团队。Masayoshi 也在那时候加入了进来。

实验的核心任务:编写一个 CPU

顺便一提,我猜没多少软件工程师亲自写过 CPU,所以我也谈谈如何写 CPU。

现如今,制作 CPU 并不意味着要在面包板上连接各种跳线,你可以完全使用硬件描述语言(HDL)编写电路。然后你可以使用 Vivado 或 Quartus 将 HDL 合成到真实电路中。这个过程叫做逻辑综合(logic synthesis),而不是编译。

HDL 与编程语言既有相似之处,也有一些差异。你可以将其视为一个将寄存器的信号状态映射成另一个信号状态的函数,其可由时钟或输入信号触发。如果你想体验真正的反应式编程,我建议你试试 HDL。同时请务必记住,在写 HDL 时要一直注意你写的 HDL 的信号传播会在某个时钟切实地终止。否则,人类将难以理解你的电路的行为。

实际开发过程中最艰难的部分就是逻辑综合,其所需的时间多得离谱。在开始执行综合之后,我们往往需要等上多达 30 分钟时间。所以开始综合之后,我常常与其他也在等着综合结束的 CPU 团队成员玩《任天堂明星大乱斗 DX》。随便说一下,我的角色是 Sheik。

十二月下旬到一月中旬:通过将 Xv6 移植到 MIPS 来学习

我们开始找到「操作系统需要 CPU 具备哪些功能?」这个问题的答案。

OS 团队诞生之后,我们开始每周聚会,阅读 Xv6 源代码。

与此同时,我开始将 Xv6 移植到 MIPS。这样做的部分原因是学习 OS 在实现层的工作方式,部分原因是似乎还没人将 Xv6 移植到 MIPS 过。我在大约一周内完成了移植工作,直到调度器过程开始。在这个移植过程中,我花了大量精力研究 MIPS,并且为了了解 Xv6 的工作方式还大量研究了 x86。得益于此,我理解了中断的相关机制以及实现层的内存管理单元(MMU)。这时候,对于 Xv6 所需的 CPU 功能,我已经有了扎实的理解。

另外,在一月中旬,我们也开始努力通过注释掉各个部分来编译 Xv6 的整体代码。结果是在我们自制架构的模拟器上,Xv6 在引导顺序中显示出了第一条消息:

xv6...cpu0: starting...

与此同时,这意味着这时候 Ucc 已经成长到足以编译大部分 Xv6 代码了。真是太棒了!

二月:我们的 CPU GAIA 诞生!

在 MIPS 移植过程中,我完成了 PIC 的初始化,这个过程很痛苦。另外,我还完成了实现中断处理程序的任务。结果,Xv6 向 MIPS 的移植工作刚完成,第一个用户程序就开始开发了。

在这一经历的基础上,我为我们的自制 CPU 编写了中断和虚拟地址转译的规范草稿。为了简单,我们决定忽略 Ring 保护等硬件特权机制。至于虚拟地址转译,我们决定使用 x86 那样的硬件页面游走法(hardware page-walking method)。看起来可能很难在硬件中实现这个功能,但我们认为如果我们牺牲掉速度并忽视 TLB 实现,可能就不会那么难。毕竟 Yuichi 后来做了一个很棒的 CPU 内核,不过它一开始就安装了 TLB。

Yuichi 完成了我们的 CPU 的 ISA(指令集架构)的整体设计。他将我们的 CPU 命名为 GAIA。在典型的 CPU 实验项目中,我们既不会实现中断,也不会实现 MMU。但是,Yuichi 开始为 Xv6 实现它们,他是基于第 3 组的 CPU 的重构版本开发的。

接下来,进度加快了,所以我将开始按周进行说明。

第一周

Masayoshi 开始为我们的 CPU 实现真正的初始化,而不只是将引导顺序注释掉;而 Shohei 将 Xv6 的 x86 汇编重写进了我们自制的架构中。我为我们的模拟器添加了中断模拟,而这个模拟器是 Wataru 在 CPU 实验的核心任务部分开发的;另外我还完成了对虚拟地址转译的支持。这能让模拟器有足够的功能来运行 OS。

第二周

我为我们的架构构建了一个原语链接器,以集成 Xv6 及其 binary blobs。Shohei 正在实现中断处理程序,这部分很难。中断很难理解,难以弄清流程、难以调试、难以开发。

当我将 Xv6 移植到 MIPS 时,我有 GDB,所以还能应付,但我们自己的模拟器没有任何调试功能,所以调试起来肯定非常难。

Shohei 也顶不住这样的难度,所以他为模拟器添加了一个反汇编器和调试 dump 函数。之后,OS 团队又对这个模拟器的调试功能进行了快速升级,最后得到的模拟器看起来是这样:

第三周

克服了许多困难之后,Xv6 的移植工作有所进展,但 Xv6 还是无法工作。

尤其是 Ucc 的规范为 char 和 int 都是 32 位,这带来了许多问题。这不是 Ucc 的错。事实上,C 规范仅要求 sizeof(char) == 1 且 sizeof(char) <= sizeof(int),因此这是符合规范的。

但是,Xv6 是为 x86 编写的,所以它假设 sizeof(int) == 4 并会将常量添加到指针的值,这会导致大量不一致。由这个问题带来的漏洞很难查找,而且数量也很多,所以最后我们决定将 Ucc 的 char 规范改为 8 位。

在将 char 32 位问题委托给 Ucc 团队之后,我为首次进入阶段写了初始化页面,并尝试通过试错方法让中断能够有效工作。

最重要的是,我们努力解决了第 4 个难题:Xv6 的可移植性差。

2 月 27-28 日

当我回头看 Slack 时,我发现这一天我们进展颇丰。在 Ucc 团队很快完成将 char 改为 8 位的工作之后,我们进行了大量调试。最后,我们的第一个用户程序 init 可以工作了!

之后,我们在移植用户过程应用方面的成果越来越多,这是我在移植到 MIPS 时没有做过的事情。在这个过程中,很多漏洞都很难重现,中断规范之中的不足之处也显现了出来,但我们最终克服了困难,找到并修复了这些漏洞。

我们修复的一个有趣问题是缓存别名问题。GAIA CPU 选择了虚拟地址作为缓存索引,而非物理地址。这让 CPU 在查找缓存时能够跳过虚拟地址转译。但是,由于这样的设计,我们发现缓存之间会出现不一致问题,因为虚拟地址的多个缓存可以指向同一个物理地址。当一个虚拟地址的缓存更新之后,其它指向同一物理地址的虚拟地址的缓存却没有更新。

这个漏洞很难在硬件层面上低成本地修复,所以为了解决它,我们为我们的 Xv6 引入了 Page Coloring。这会为每个缓存行引入「颜色」并重新分配页面,使得指向同一物理地址的虚拟地址总会有一样的颜色。这意味着指向同一物理地址的虚拟地址总是仅有一个缓存。这能让 Xv6 确保 GAIA 永远不会让多个缓存共用同一个物理地址。


三月:Xv6 跑起来!

3 月 1 日,Xv6 移植工作完成。现在 Xv6 已经运行在模拟器上了!

娱乐少不了

一开始,移植 Xv6 是因为这很有趣,现在 Xv6 已经成功运行在模拟器上,那我们就要加把劲让它更有趣。

首先,Masayoshi 用大约 4 个小时做了一个小火车以及运行在 Xv6 上的 sl 命令。
Shohei 则想做一个扫雷游戏。

在这期间,Yuichi 完成了 Group X 的 CPU 实现工作。真正的 CPU 的运行速度比模拟器快多了,这能让我们更轻松地玩耍和开发游戏。这时候,我们创建了一个非常高质量的应用:2048。

这个 2048 的质量很高。Yuichi 老是在玩。顺便提一句,这个 2048 使用的是 non-line buffering 输入,这是 Xv6 原本没有的功能。为了支持这一功能,ioctl 被添加进来作为 read 和 write 之外的另一个 devsw 动作,另外还添加了用来控制 ICANON 和 echo 的与 termios 相关的新功能。因此,唯一能以如此高的完成度玩 2048 的 Xv6 就运行在 GAIA 上。

另外,毕竟 Xv6 是由 Unix v6 启发的,因此我猜想,添加 gtty 和 stty 系统调用是更像 Unix v6 的方法。不过,因为 Xv6 没有 tty 的概念,所以我采用了 ioctl;而且事实上 Unix v7 就引入了 ioctl,所以这与历史情况也接近。

现在,更酷的是,Keiichi 又为 Xv6-GAIA 做了一个小型汇编器,Shohei 还做了一个 mini vi。想想看你能用这两个工具做什么。

这就是基于 FPGA 的交互式编程!这是 CPU 实验的一个出色演示,因为其中一般不包括任何交互式程序。

最棒的演示

CPU 实验实践课程的原始任务是「在自制 CPU 上运行给定的光线追踪程序」。现在我们的 CPU 上有操作系统了,你知道该怎么做了吗?我们决定在我们的 CPU 的 OS 上运行这个光线追踪程序。我们遇到了一些问题,但我们在最终展示前一个小时里成功解决了它们。

因此,我们做了我们这个系的学生开玩笑时说的话:在一个 CPU 上运行一个操作系统,然后再在上面运行光线追踪程序。

来自 2020 年的回顾

这段故事发生在 2015 年,本文也是我自己的博文的翻新稿。尽管现在读来,我看到了当时自身技术经验的不足,但我们当时做的事情实在很激动人心。

另外,你现在也可以在你的浏览器中体验我们的 Xv6:https://nullpo-head.github.io/emcc-gaia-simu/xv6.html

实验之后,我将我们的 GAIA 模拟器通过 Emscripten 移植到了 JavaScript。去试试看我们的 sl、扫雷和 2048 吧。

xv6...cpu0: startinginit: starting sh$

还要说一下,Xv6 向 MIPS 的移植工作在 CPU 实验期间并没有完成,而是在实验之后一个月完成的。GitHub 代码库在这里:https://github.com/nullpo-head/xv6-mips

在我们 2015 年写文介绍了 Group X 的工作之后,后来的学生继续攻坚有关 OS 的新挑战。

2018 年,一些学生在自制的 CPU 上运行了他们自己开发的 OS;2019 年,一组学生运行了他们开发的 OS,同时采用了 RISC-V 作为他们自制 CPU 的 ISA。此外,2020 年的一个小组终于在自制 CPU 上成功运行 Linux,同时 ISA 也采用了 RISC-V。

我相信未来还会有更多故事,也让我们保持期待。从个人角度看,我很期待某天能看到某人在自己的 ISA 上运行 Linux,或在上面运行虚拟机。

人们常说要避免重新造轮子,但这个过程确实能让人学到很多东西。这让我认识到,我对它的理解其实没有那么深,无法从头开始实现它。而且,我推荐这个故事的另一个原因是这真的非常有趣!

我们的 CPU 实验故事就到此为止了。如果你也有兴趣重新发明轮子,可以试试自制 CPU 并移植 OS。

原文链接:https://fuel.edby.coffee/posts/how-we-ported-xv6-os-to-a-home-built-cpu-with-a-home-built-c-compiler/


工程东京大学编译器CPU硬件芯片
相关数据
调度技术

调度在计算机中是分配工作所需资源的方法。资源可以指虚拟的计算资源,如线程、进程或数据流;也可以指硬件资源,如处理器、网络连接或扩展卡。 进行调度工作的程序叫做调度器。调度器通常的实现使得所有计算资源都处于忙碌状态,允许多位用户有效地同时共享系统资源,或达到指定的服务质量。 see planning for more details

重构技术

代码重构(英语:Code refactoring)指对软件代码做任何更动以增加可读性或者简化结构而不影响输出结果。 软件重构需要借助工具完成,重构工具能够修改代码同时修改所有引用该代码的地方。在极限编程的方法学中,重构需要单元测试来支持。

光线追踪技术

在计算机图形学中,光线跟踪是一种渲染技术,用于通过将光的路径跟踪为图像平面中的像素并模拟虚拟对象对光线的接收效果来生成图像。 该技术能够产生非常高的视觉真实感,通常高于典型扫描线渲染方法,但计算成本更高。

映射技术

映射指的是具有某种特殊结构的函数,或泛指类函数思想的范畴论中的态射。 逻辑和图论中也有一些不太常规的用法。其数学定义为:两个非空集合A与B间存在着对应关系f,而且对于A中的每一个元素x,B中总有有唯一的一个元素y与它对应,就这种对应为从A到B的映射,记作f:A→B。其中,y称为元素x在映射f下的象,记作:y=f(x)。x称为y关于映射f的原象*。*集合A中所有元素的象的集合称为映射f的值域,记作f(A)。同样的,在机器学习中,映射就是输入与输出之间的对应关系。

逻辑技术

人工智能领域用逻辑来理解智能推理问题;它可以提供用于分析编程语言的技术,也可用作分析、表征知识或编程的工具。目前人们常用的逻辑分支有命题逻辑(Propositional Logic )以及一阶逻辑(FOL)等谓词逻辑。

操作系统技术

操作系统(英语:operating system,缩写作 OS)是管理计算机硬件与软件资源的计算机程序,同时也是计算机系统的内核与基石。操作系统需要处理如管理与配置内存、决定系统资源供需的优先次序、控制输入与输出设备、操作网络与管理文件系统等基本事务。操作系统也提供一个让用户与系统交互的操作界面。

暂无评论
暂无评论~