用GO重写Linux可行吗？ 第1页

使用高级语言实现POSIX内核的成本和收益

摘要

这篇论文旨在评估用有垃圾回收特性的高级语言去实现一个类POSIX内核的性价比。其目标是研究在实现类POSIX内核的情况下，基于对性能损耗、实现难度、可编程性及安全等方面的考量，分析用高级语言去替代C语言，是否有必要。

在写这篇论文的时候，我们使用golang实现了一个叫做Biscuit的内核，它完全符合POSIX标准（虚拟内存、内存映射、TCP/IP、日志文件系统，poll等），并能执行一些现有的应用。因为在编码时，Biscuit充分利用了golang的一些高级语言特性（闭包、通道、map类型、接口、垃圾回收），所以在主观上我觉得编码不是最棘手的。最棘手的是，如何解决内存不足，内核堆不够分配的问题。得益于golang的开源，我们能够分析golang的源码，最终Biscuit解决了这个问题。

基于一系列CPU密集型的基准测试（包含nginx和redis）分析，Biscuit内核需要占用高达13%的CPU时间在高级语言的特性上（主要是垃圾收集和线程堆栈展开检查）。nginx由于垃圾收集而暂停服务的单次最长时间是115ms，从因为垃圾收集而暂停服务到完成一次客户端请求的总时间，最长是600ms。在实验中，和另一个用C语言编写的相似内核相比，在系统调用，Page Faults以及上下文切换上，golang的实现比C的实现慢5%到15%。

1. 引言

当前主流操作系统的内核都是使用C来编写：Linux、macOS以及Windows。之所以C在这个领域这么流行，是因为C能利用灵活的访问内存技术以及做内存管理技术来获得更好的性能。也正是因为C的这种灵活性，所以就需要有更多经验以及更加谨慎的人来编写C的代码，然而就算你是个经验老到且极度谨慎的人，你依然可能会犯一些很低级的错误。比如说，在2017年，Linux内核中，与内存溢出及忘记释放内存而导致的bug的报告就有50个。

一般来说，高级语言会提供了类型、内存安全以及适当的抽象能力，比如线程。还有些高级语言会提供垃圾回收的特性，垃圾回收使得程序员在编写代码时不需要过多考虑内存问题。众所周知的是，高级语言是可以用来编写内核的：有很多用于探索创意的平台都是使用高级语言编写的内核。而另一方面，当前主流的一些操作系统的设计者一直怀疑，高级语言的内存管理能力和现有的高性能产品级内核是否存在兼容问题。

如果现在再考虑怎么用高级语言去重写当前主流的用C实现的内核，这不太可能，也没有什么意义，但是有意义的，我们可以考虑在编写新的内核时，我们应该使用什么语言。编写内核的难度更大，和普通的应用相比，它有更复杂的约束和需求，研究何种高级语言去编写内核更具性价比，是很有意义的。

我们使用golang实现了一个叫做Biscuit的新内核。golang是一种带有垃圾回收特性的类型安全的语言。Biscuit符合POSIX标准，所以nginx和redis无需修改的源码，就能运行在Biscuit内核中。当前Biscuit已实现的特性包含多核支持、用户线程、futex机制、进程间通信、内存映射、COW、VNode、名称缓存，TCP/IP以及一个日志文件系统。Biscuit还用golang实现了两个重要的驱动器：AHCI SATA硬盘控制器和基于Intel 82599的网卡驱动器。Biscuit的实现有近28000行golang和1546行汇编代码，没有任何C代码。在实现Biscuit的过程中，我还编写了一个关于使用golang的文档，这个文档中包含这个语言对开发内核有帮助的特性，也包含了这个语言对开发内核没有多大帮助的场景。

对于实现Biscuit这种类POSIX内核而言，大多数情况下，golang是一个不错的选择。在内核设计上，Biscuit有全新的机制以应对内存不足的问题。Biscuit对源码做静态分析以确定每个系统调用（以及内核活动）可能需要耗费多少内存，以及系统调用由启动到被保留的这个等待阶段（如果需要等待）需要多少堆。一旦一个等待阶段的系统调用的被激活，Biscuit将保证成功分配系统调用需要的内存，且不会发生阻塞。这避免了分配器在为故障恢复及有死锁可能的系统调用分配内存时需要等待空闲内存的问题。高级语言更容易做静态分析使得此种内存分配机制成为可能。

我们在Biscuit内核中运行几个CPU密集型的应用，并测量了golang的类型安全和垃圾回收对性能的影响。我们发现，垃圾回收的CPU占用高达3%。nginx由于垃圾收集而暂停服务的单次最长时间是115ms，从因为垃圾收集而暂停服务到完成一次客户端请求的总时间，最长是600ms。其他的高级语言特性将会占用10%的CPU。

为了更好的对比C和golang实现的内核的性能，我们修改了C实现的内核以保证两者的代码处理使用相同逻辑结构，这种逻辑结构能更为方便的在系统调用，Page Faults以及上下文切换上做基准测试。通过基准测试，我们发现，C的实现比golang的实现快5%到15%。

最后，我们在内核密集型应用程序基准测试上还比较了Biscuit和Linux的性能，发现Linux比Biscuit快10%。这个结果对于语言的选择并不是很有启发性，因为性能还受到Biscuit和Linux的特性、设计和实现差异的影响。但是，这些结果也能从另一个层面回答了一个我们的问题，即使用golang实现Biscuit的绝对性能能否与C实现的内核处于同一级别。

综上所述，这篇论文最终的贡献有：

1. 用golang实现的性能良好的Biscuit内核
2. 全新的应对内核堆耗尽的问题的方法
3. 讨论内核中使用高级语言是否有帮助或者没有帮助
4. 测量在使用高级语言实现内核时需要的额外耗费
5. 直接对比了在相同逻辑结构下golang与C实现的内核的性能

本文没有对C语言和高级语言作为内核实现语言进行任何顶层总结。相反，它提供了经验和度量，这些经验和度量可能有助于其他人做出此决策，这些人在可编程性、安全性和性能方面有特定的目标和需求。我们在第9节总结了这些关键因素。

2. 相关工作

Biscuit并不是从零开始，它基于前人在多个领域的研究结果，这些领域对应的问题有：如何使用高级语言编写内核、如何选用高级系统编程语言以及内核中的如何分配内存。但是针对选择什么语言会对内核性能有多大的影响，据我们所知，在其他条件相同的情况下，这个问题还没有其他人研究过。

如何使用高级语言编写内核？ 最早使用高级语言编写的内核有Pilot内核和Lisp machine，他们分别使用mesa和Lisp。mesa没有垃圾回收特性，但是它的继任者Cedar是支持的。Lisp machine支持实时垃圾回收。

还有大量的使用高级语言编写的内核，比如Taos、Spin、Singularity、Jkernel、KaffeOS、House、the Mirage unikernel和Tock。这些内核项目主要是为了探索一些新的思路，通常他们使用有类型安全的高级语言来编写。虽然性能问题经常被提及，但是通常性能好坏往往与思路更相关，与选择什么语言关联不大。比如Singularity，它量化了软硬件隔离的消耗，这个确实和高级语言有关，但是Singularity却没有量化高级语言类型安全特性带来的性能损耗，但是我们针对这个点在8.4节中却做了一系列的基准测试。

如何选用高级系统编程语言？ 市面上有大量的系统级编程语言都具有类型安全以及垃圾回收的特性，比如golang、Java、C#和Cyclone（最近的，还有Cedar和Modula-3）。其他的一些高级语言和现在的内核设计是不兼容的。比如Erlang，Erlang使用不可变类型所以无法共享任何数据，这导致和传统的使用C实现的共享内存内核有很大的不同。

Frampton等人为Java编写了一个框架，它添加了一些必要的特性，以能够更方便的编写底层代码，并且这些特性支持垃圾回收。不过，Biscuit的目标是在不修改golang源码的基础上提高内核的效率，还要解决其他一系列的问题，比如实现用户/内核空间、页表，中断以及系统调用。

最近出现的很多用于系统编程的新语言，比如：D、Nim、Go以及Rust。有大量的使用Rust实现的内核，但是没有一个实现是为了和C的实现做对比的。Gopher OS是一个用golang写的内核，它的目标和Biscuit类似，但是这个项目还处于早期阶段。也存在其他的使用golang实现的内核，但是他们的目标和Biscuit是不相同的。例如，Clive是一个unikernel，而且不能运行在裸设备上。Ethos OS使用C实现的内核，使用golang实现用户空间应用，他的设计重点是安全性。gVisor是一个用Go编写的用户空间内核，它实现了Linux系统API到沙箱容器的大部分功能。

内核中的如何分配内存？ 业界对于系统编程语言是否应该具有垃圾收集特性还没有达成共识。例如，Rust认为全自动的垃圾回收不一定有效，所以Rust编译器是分析程序然后半自动的去释放内存。这种方法可能会使多个线程或闭包之间的数据共享变得困难。

并行垃圾回收器通过在应用程序运行时回收垃圾来减少暂停时间。Go 1.10中实现了这样一个垃圾回收器，Biscuit使用的就是这个垃圾回收器。

有几篇论文比较了手工内存分配与自动垃圾收集的性能，主要关注点在于研究在用户级程序中使用了垃圾回收，对堆空间的余量的影响。对Biscuit而言，堆空间的余量也很重要(§5和§8.6)。

Rafkind等人通过自动转译C源码的方式为Linux的部分模块添加了垃圾回收特性。之所以不是全部的Linux模块，是因为作者发现复杂的内核环境让这个任务变得无比复杂，所以最终选用了一部分模块使其能够兼容垃圾回收的特性。Biscuit使用golang重头开始，得益于golang的垃圾回收器，所以在内存分配处理上，不需要程序员花费太多的时间。

Linux的slab回收器是专门针对内核进行调优的，它按类型隔离空闲对象，以避免重新初始化和内存碎片。在设计Biscuit时，我们假设golang的垃圾收集器可以适用于各种不同的内核对象，所以不需要再做调优。

如何解决内核堆不够分配的问题？ 所有内核都需要考虑在内存耗尽，如何解决内核堆不够分配的问题。Linux的策略是乐观地允许系统调用一直进行直到分配失败为止。在某些情况下，代码会等待并重新尝试分配几次，以给处理“内存不足”的线程时间来查找并销毁滥用内存的进程。然而，分配内存线程通常不能无限期地等待:它可能持有一个锁，而如果这个锁等待的是另一个要被垃圾回收的线程，这样就存在死锁的风险（你不分配我不回收，你不回收我不分配）。因此，Linux系统调用必须能够还原垃圾回收失败时的内存状态，这就需要撤销到当前为止所有的修改，这或许可以通过函数来实现。但麻烦的是，在发生内存不足的情况下，系统调用的最终返回结果是内存不足错误。一旦内存不足，任何系统调用在分配内存时都可能失败。如果一个应用拿到系统调用返回的结果是内存不足错误，基本上大部分应用都不会继续运行。所以纵使内核已经正确的处理了内存不足的问题，应用还是可能会出现故障。

3. 动机

本节概述了在实现内核时，选择C和高级语言时需要考虑的主要问题。

3.1 为什么选C？

之所以C在内核这个领域这么流行，主要是它支持用一些很底层的技术来提升性能，特别是指针、无类型限制、强大的内存分配方式。当然还有其他原因，比如C可以操作硬件寄存器并且不依赖于复杂的运行时，但是性能应该是最重要的。

3.2 为什么选择一个高级语言？

众所周知高级语言有很多好处。自动内存管理减少了程序员的工作以及由于使用之后忘记释放内存导致的bug、类型安全可以更方便的检测错误、运行时类型和方法分发有助于设计抽象、还有语言层面支持线程和同步简化了并发编程。

某些类型的bug在高级语言中出现的可能性似乎比在C中要小得多，比如由于缓冲区溢出、使用之后忘记释放内存导致的bug，以及由于依赖于C的松散类型而导致的bug。即使是由专业程序员小心翼翼编写的C代码也会出现bug。Linux内核的CVE数据库列出了2017年的40个代码漏洞，使用高级语言可以完全或部分地改善这些漏洞(参见§8.2)。

众所周知，使用之后忘记释放内存导致的bug非常难以调试。但是这种bug经常发生，所以Linux内核中包含一个内存检查器，用于检测运行时忘记释放的内存而导致bug。不过，Linux的开发人员还是经常发现此类型的bug。2018年1月到4月，Linux至少有36个提交都是为了修复这种bug。

另外一个高级语言的特性也是对编写内核很有帮助的，就是语言层面的并发支持。在C语言里面，临时工作线程的清理工作就很麻烦，你必须释放在最后一个线程停止时线程使用到的全部共享对象。这在支持垃圾收集语言中很容易实现。

但是并不是使用高级语言就没有代价，垃圾回收和安全检查会更多消耗CPU时间，并可能导致应用延迟；高级特性的开销可能会阻碍它们的使用；语言的运行时层隐藏了重要的机制，比如内存分配；强制的抽象和安全性可能会减少开发人员的代码实现时的选择。

4. 概述

Biscuit的主要目的是评估用高级语言编写内核的实用性。为了便于比较，它使用类UNIX内核的设计。Biscuit可以运行在64位x86硬件上，它基于 Go 1.10运行时，使用golang和一小部分汇编编写，汇编代码是用来处理启动，进入和退出系统调用以及中断。没有C代码。本节会简要介绍Biscuit的组件，重点介绍golang的使用对设计和实现的影响。

引导块以及golang运行时。引导块会加载Biscuit、golang运行时以及一个叫做“slim”的层（如上图所示）。对于golang运行时我们没有做大的修改，我们修改的地方是希望能够为某些服务调用底层内核，特别是内存分配和执行上下文的控制。shim层提供了这些功能，因为我们没有更底层的内核。shim层的大部分活动发生在系统初始化期间，例如为Go内核堆预分配内存。

进程和线程。Biscuit提供用户进程是使用POSIX标准，比如fork, exec等函数，这个标准还包含了内核级线程支持以及futex机制的实现。一个用户进程包含一个地址空间和一个或多个线程。Biscuit基于硬件页面保护来隔离用户进程。最终用户的应用可以使用任何语言实现；但是我们只用过C和c++的实现（不是golang）。Biscuit维护与每个用户线程对应的内核级goroutine；goroutine为用户线程执行系统调用以及处理Page Fault和线程异常。虽然“goroutine”是Go对线程的名称，但在在本文中仅指运行在内核中的线程。

Biscuit运行时用来调度用户进程中的线程，每个进程在必要时以用户模式执行自己的用户线程。Biscuit使用计时器去中断先运行的用户线程然后做线程切换，这依赖于golang编译器为goroutine生成的优先级。

中断。和之前内核的处理方式一样，设备请求中断时，Biscuit将关联的设备驱动线程标记为可运行，然后就返回。就算没有发生死锁的风险中断也不需要做更多的操作，因为golang运行时不会在上下文切换这样敏感的操作中关闭中断。

用户空间的系统调用和故障处理程序可以执行任何golang代码。Biscuit在与当前用户线程关联的goroutine上下文中执行这些代码。

多核和同步。Biscuit可以在多核硬件上并行运行。它使用golang的互斥锁保护其数据结构，并使用golang的通道和条件变量进行同步。锁的粒度足够细，因此来自不同内核上的线程的系统调用在大多数情况下可以并行执行，例如在不同的文件、管道、套接字上操作时，或者在不同的进程中fock或exec时。在一些性能关键的代码中，Biscuit使用只读锁(参见下面)。

虚拟内存。Biscuit使用页表硬件实现按需零填的内存分配、写时复制的和文件延迟映射(例如，对于exec)，其中PTEs仅在进程Page Faults和内存映射时填充。

Biscuit记录相邻的且紧凑的连续内存区域，因此通常情况下，不需要大量的映射对象。一个物理页面可以有多个引用；Biscuit使用引用计数跟踪这些页面。

文件系统。Biscuit实现了一个支持POSIX文件系统调用的文件系统。文件系统有一个文件名查找缓存、一个VNode缓存和一个块缓存。Biscuit使用互斥锁保护每个VNode，并解析路径名，具体的做法是，先尝试在一个只读锁的目录换成中逐个查找，然后再锁定路径中命名的每个目录。Biscuit将每个文件系统调用作为事务运行，并有一个日志以原子方式将更新提交到磁盘。日志通过延迟组提交对事务进行批处理，并允许文件内容写绕过日志。Biscuit有一个AHCI磁盘驱动程序，它使用DMA、命令合并、本机命令队列和MSI中断。

网络协议栈。Biscuit实现了TCP/IP协议栈，并且使用golang为英特尔PCI-Express以太网NIC编写了驱动程序。这个驱动程序使用DMA和MSI中断。系统调用API提供POSIX套接字接口。

缺陷。尽管Biscuit可以在无需修改源码的情况下运行很多Linux的C程序，但它终究只是一个研究原型，还是缺乏很多功能。Biscuit不支持调度优先级，因为它依赖于golang运行时调度程序。Biscuit针对少量内核进行了优化，但不适用于大型多核机器或NUMA。Biscuit不支持交换或分页到磁盘，也不支持映射页面所需的反向映射。Biscuit缺乏许多安全特性，比如用户、访问控制列表或随机化的随机化地址空间。

5. 垃圾回收

Biscuit中垃圾回收对性能有明显的影响。本节概述了golang垃圾回收器的设计，并描述了Biscuit如何配置垃圾回收器;§8评估性能成本

5.1 golang垃圾回收器

golang1.10中有一个并行的标记-清除垃圾回收器。垃圾回收器的并发特性对Biscuit非常重要，因为它会降低内核的停机时间。

在垃圾回收器空闲状态时的时候，运行时使用最后一次垃圾回收所创建的空闲列表分配内存。当空闲内存低于阈值时，运行时启用并发回收。当并发回收被启动时，分配内存与追踪指针以标记可达对象会同时进行：内存分配器每次分配内存的操作都执行少量的跟踪和标记。编译时生成的“write barriers”，可以保证创建的任何新对象其指针都是可以被追踪的，对任何一个已经被追踪的对象进行写入操作也是可以被检测。一旦所有指针都已经被跟踪，垃圾回收器就会关掉“write barriers”开始执行回收操作。在回收期间会有两次“停机”操作：第一次发生在启用“write barriers”时，第二次发生在对所有对象被标记完成时。这些“停机”操作通常持续几十微秒。在Biscuit执行内核操作的同时，垃圾回收器从未标记的内存部分(“清除”)重新构建空闲列表，然后释放所有空闲堆内存，最后再将垃圾回收器标记为空闲状态。垃圾回收器在回收的过程中不会移动对象，因此不会减少内存碎片。

消耗在垃圾回收上的CPU时间与活动对象的数量大致成正比，与回收之间的间隔成反比。通过加大内存，可使得每次回收能够释放更多空间，这样就能加大回收之间的间隔，以降低CPU时间。

golang垃圾回收器在内存分配期间就完成大部分工作，不在内存分配期间的工作基本会平摊到每次调用垃圾回收的时候。因此goroutine的延迟与内存分配的对象数量成正比;§8.5给出了对Biscuit延迟的测量。

5.2 Biscuit的堆大小

系统启动时，Biscuit为golang分配一个固定大小的堆，这个数值为总内存大小的1/32。当分配的内存数超过当前堆大小的一半时，golang的垃圾回收器会请求分配更多内存。Biscuit不会接受这个请求，所以不会给应用分配更多内存。下一节(§6)中，我们将解释Biscuit如何处理堆内存几乎没有可用空间的问题。

6. 解决内存不足的问题

Biscuit需要解决内存可能耗尽，内核堆可能不够分配的问题。这也是现有内核难以解决的一个难题(§2)。

6.1 解决方法：预留内存

设计Biscuit是为了避免在内存耗尽的情况下系统出错的问题。除此以外，当Biscuit发现某些“坏”进程要求分配过多的内存资源时，Biscuit将终结掉这些“坏”进程，释放内存空间，以此让“好”进程的更好的执行，比如某些进程一次性打开非常多的文件，这种Biscuit将会识别为“坏”进程，然后终结掉。

Biscuit解决内存耗尽的方法有三个。第一，当堆内存接近耗尽时，它清除缓存和软状态。第二，每次系统调用在正式执行之前需要等待内核为它预留足够多的内存空间；一旦内核预留到了足够多的空间，这个等待就会结束，系统调用才会被正式执行。第三，内核中的销毁线程会监视那些消耗大量内存以致于可能造成内存不足问题的进程，并销毁这些进程。

这种方法有很多好处。应用程序不需要处理由于内存耗尽而导致的系统调用失败的问题。内核代码不会看到堆分配失败(除了少数例外)，所以不需要处理从系统调用中发生内存不足而导致失败之后的内存状态还原问题。系统调用可能必须等待预留内存完成，以致与获得足够多的内存，但是它们只是在执行前等待，而不持有锁，因此避免了死锁。

销毁线程必须能够区分“好”进程和“坏”进程，因为杀死一个关键进程(例如init)会使系统不可用。如果没有显而易见的“坏”进程，销毁线程可能会阻塞和/或杀死“好”进程。在类POSIX内核中，无法优雅地撤销资源，这导致在一些内存不足的情况下没有好的解决方案。

本节中的预留内存的机制不适用与非堆内存的分配。特别是我们使用一个独立的内存分配器为Biscuit分配内存，而不是从golang堆中：内存页分配可能失败，但是内核必须能够检测失败然后做还原操作（通常是返回一个错误给系统调用）。

6.1 Biscuit如何预留

Biscuit为内核分配一个固定的内存大小，我们称之为M。综前文所述，一个系统调用只能在内核为其分配足够多的内存的情况下才能真正执行，这个系统调用执行的过程中所需的全部活动对象的总内存的峰值我们称之为 s。一次系统调用中我们可能会从堆中为其分配超过s量的内存，但是大于s的这部分内存一定会被标记为可被垃圾回收器回收。这意味着，即使内存仅剩s大小的空间可用，其他的部分都已经被占用或被其他系统调用预留，当前已分配完成的系统调用依然可用顺利执行，并且垃圾回收器也能在已分配的内存查找到可以被回收的内存来释放空间。

理想情况下，预留的过程应该要检查是M减去堆中已预留的内存数和活动堆内存堆的内存数总和，这个数要大于或等于s。但是，除非在垃圾回收之后立即执行，否则不知道活动堆数据的数量。Biscuit使用三个计数器对活动堆数据进行保守的高估:g、c和n。g是由前面的垃圾收集标记的活动数据量。c是为已预留的内存数。n是正在执行但尚未完成的系统调用的预留的内存总数。设L是g，c，n的和。

       reserve(s):     g := last GC live bytes     c := used bytes     n := reserved bytes     L := g + c + n     M := heap RAM bytes     if L + s < M:         reserved bytes += s     else:         wake killer thread         wait for OK from killer thread release(s):     a := bytes allocated by syscall     if a < s:         used bytes += a     else:         used bytes += s     reserved bytes -= s      

以上是Biscuit进行预留及释放内存的伪代码。在系统调用真正执行之前，内核检查线程检查L + s < M。如果L + s < M，内核会给n加s然后预留内存空间给系统调用，否则内核将启动销毁线程，直到销毁线程返回OK。