第三次的作业主要内容有：分配内存、读取FAT32文件系统。这次作业拖了好久，期间各种浪，一拖再拖。

大战编译器

前面挖了 rustc 1.28.0-nightly (cd494c1f0 2018-06-27) 的坑，现在又得继续填了。这次 std 里面加了好多东西，一开始改起来也是摸不着头脑，尤其是原先的 Heap traits 基本上全都变了，跑到了 alloc crate 里面去，感觉要改非常多的东西。

这里先要称赞一下 Rust 的 alloc crate，这个抽象真的非常实用。按照 RFC 的说法：

The core crate does not assume even the presence of heap memory, and so it excludes standard library types like Vec<T>. However some environments do have a heap memory allocator (possibly as malloc and free C functions), even if they don’t have files or threads or something that could be called an operating system or kernel. Or one could be defined in a Rust library ultimately backed by fixed-size static byte array.

An intermediate subset of the standard library smaller than “all of std” but larger than “only core” can serve such environments.

alloc crate 介于只有 core 和完整 std 中间。有了它，只要实现了内存分配，no_std 就可以享受到 std 中非常多的福利，比如说 Vec<T>。

说回适配新版本的编译器。因为这次需要修改的东西比较多，像上次那样一点点改怕是不太现实。@codeworm96 大神一句“哪里报错就把最新std拖过来”拯救了我。这个作业里面的 std 肯定也是从当时编译器版本的 std 里面复制过来然后裁剪的，确实只要把我编译器中的 std 粘过去就行了。而且我发现了作者在裁剪的时候非常明显地用 //- 标了出来，所以在报错的文件里面只需要搜索一下有没有这个特殊的注释符号，没有的话就大胆地把整个文件替换掉，有的话就在次基础上局部做相应的微调。至于当前版本的 std 源码嘛，也不必特地去找，先 rustup doc 调出本地的 API 文档，然后点 src 看源码，地址栏里面把文件名去掉就可以列目录了。

整体上来说这个复制粘贴还是非常轻松愉快的，进度也非常快。我遇到的两个问题，一个是 panic! 找不到了。对比了上一次的作业，我发现 CS140e 的 panic! 直接在 std/src/lib.rs 里面 re-export 了 core::panic，而不是用的 std 定义的那个。照样 re-export 就行了。

另一个问题是，2-fs 分支把 lang_items.rs 里面的 memcpy 和 memmove 删掉了，于是我就在链接的时候出现了 undefined reference to `memcpy'。找了半天，似乎也没找到 memcpy 在哪里导进来，最后还是把上一次 lang_items.rs 中的 memcpy 粘了回去，总算解决了问题。

我把修改好的版本传到了 GitHub Gist 上，有需要的读者可以自行下载。

Panic 和 ARM Tags

panic! 在前几次作业的时候就解决了，就不说了。

ARM Tags 教大家怎么用 union。感觉 Rust 把 union 设计成 unsafe 还是很合理的，毕竟这相当于是一种 reinterpret_cast。所以说呢，CS140e 教大家，还是要封装一下的。

说一下我在实现的过程中遇到的一个小 bug，我发现我无法解析 command line。CMDLINE ATAG 是这么定义的：

pub struct Cmd {
    /// The first byte of the command line string.
    pub cmd: u8
}

let base = cmd.cmd as *const u8;     // (1)
let base = &cmd.cmd as *const u8;    // (2)
let base = (&cmd.cmd) as *const u8;  // (3)

cmd.cmd 是 command line 字符串的头一个字节，要把整个字符串读出来，自然是沿着这个地址继续往下读。要获取这个基地址，我一开始写成了 (1) 的形式，后面发现了问题之后改成了 (2) 的形式，bug 就解决了。这是因为 (1) 的语义是把 cmd.cmd 里面的值作为一个地址，而 (2) 的语义同 (3)，意思是把 cmd.cmd 的地址取出来。这一字之差语义完全不同，但是都可以通过编译。果真 unsafe 非常的危险啊。

内存分配

之前我因为见识少，以为内存分配 API 应该都长 C 的这个样就行了：

void* malloc(size_t size);
void free(void* ptr);

而 Rust 却不太一样：

pub unsafe trait Alloc {
    unsafe fn alloc(&mut self, layout: Layout) -> Result<NonNull<u8>, AllocErr>;
    unsafe fn dealloc(&mut self, ptr: NonNull<u8>, layout: Layout);
    // other trait methods with default implementations...
}

Rust 多了一个 Layout，显式地传递了大小和对齐信息。如 RFC 1398 所说，这样的好处是，不用像 malloc 那样把这些额外的信息存下来，因为 Rust 在编译期间就能够根据类型算出来了：

Another problem with the malloc interface is that it burdens the allocator with tracking the sizes of allocated data and re-extracting the allocated size from the ptr in free and realloc calls (the latter can be very cheap, but there is still no reason to pay that cost in a language like Rust where the relevant size is often already immediately available as a compile-time constant).

确实是免除了簿记的负担，但是同时，因为对齐可以任意指定，所以在实现的时候要额外处理不同的对齐大小的情况。反过来的话 man malloc 说 malloc 会有一个全局的通用的对齐：

The allocated memory is aligned such that it can be used for any data type, including AltiVec- and SSE-related types.

总体上来说，Rust 的这套内存分配 API 设计感觉还是更先进一点，支持更灵活的对齐选项，又去除了额外的簿记开销。

在实现的时候，我发现 Rust 语言自带了好多实用的工具，比方说：

在实现 Bin Allocator 的时候，又一次看到了所谓的 intrusive linked list，又一次感觉到非常巧妙。巧妙的倒不是 intrusive，毕竟以前用 C 写链表的话，入侵式的写法是家常便饭。我觉得巧妙的地方在于，这个链表的值和地址是耦合的，直接把链表放在了裸的内存空间上，或者说直接把裸的内存空间当作了链表，以至于可以在没有内存分配器的时候就能动态地修改链表。

这让我想起了以前搞 MIT 6.828 的时候，xv6 也有这样的“骚操作”。xv6 中对应的链表是 kalloc.c 里面的 struct run，代码见 Github：

struct run {
  struct run *next;
};

struct {
  struct spinlock lock;
  int use_lock;
  struct run *freelist;
} kmem;

对应的说明见书的第32页最底下 Physical memory allocation 章节。

It keeps track of which pages are free by threading a linked list through the pages themselves. Allocation consists of removing a page from the linked list; freeing consists of adding the freed page to the list.

至于 6.828 的作业 JOS 倒不是这么实现的，JOS 是先用一个 bump allocator 来乱分配一通，然后再建立页表。

说回 CS140e，这里用了一个 #[path] attribute 来切换实现。说实在的，我觉得好像比较 tricky，我的编译器会警告我 bin allocator 里面的函数全都 unused。我后面改成了

use self::bin as imp;

警告就消失了，而且也能正常运作。我觉得这样的黑科技能少用一点就少用一点吧，而且 std 也是这么用的，见 std/fs.rs：

use sys::fs as fs_imp;

读取 FAT32 文件系统

这个部分折腾了很久……总结一下经验就是要把这个 FAT32 从头到尾的流程搞清楚，然后要把协议看仔细了。在实现 FAT32 的时候就感觉到了良心微软果然是千方百计地想着兼容性，这个 LFN 这么蛋疼的写法都能想得出来。顺带吐槽一下 FAT32 的时间戳，ctime/mtime/atime 的精度真是天差地别，分别是 10ms/2s/1day。

说一下我实现的时候几个比较大的 bug 吧。

第一个是目录的内容乱了。这个查来查去，最后发现 cluster 竟然是从 2 开始编号的，而不是 0……

第二个是一部分文件的文件名乱了，比如 /NOTES/LEC3/dfcheat-sheet.p，原因是忘记把 LFN 文件按照 LFN entry 的 sequence number 排序。

第三个是 test_mock1_files_recursive 测试莫名其妙多出来了好多文件，但是我试着把 mock1.fat32.img 挂到我的操作系统上，发现里面确实有我列出来的文件。后来看了看 fat32/src/test.rs，发现 hash_files_recursive 函数里面把大于1MB的文件全都过滤掉了，而碰巧我的 size() 又实现错了，全都返回0……

真机调试

在实现几个 shell 命令之前，我先调试输出了根目录，结果列了两个文件之后就卡死了，也没有报 panic，突然就一动不动了。这真机也没有 GDB，fat32 crate 也没有 kprintln!，一时不知道怎么办。

后来灵机一动，翻了翻前面作业是怎么实现 kprintln! 的，发现其实是用了 pi crate 的 MiniUart。那就很简单了，把 pi crate 加到 fat32 crate 的 Cargo.toml 的 [dependencies] 和 [dev-dependencies] 里面。然后加一个 MiniUart::debug_new() -> MiniUart 来创建一个 MiniUart 但是不修改寄存器。至于 kprintln! 嘛，手动展开就行了。于是乎就可以在 fat32 crate 里面这么输出调试信息：

MiniUart::debug_new().write_fmt(format_args!("ptr: {:?}\n", ptr));

加了一堆调试信息之后，发现卡在了我 bump allocator 的 dealloc 上面

pub fn dealloc(&mut self, ptr: NonNull<u8>, layout: Layout) {
    MiniUart::debug_new().write_fmt(format_args!("BinAllocator::dealloc enter\n"));
    MiniUart::debug_new().write_fmt(format_args!("====== BinAllocator ======\n{:#?}\n", self));
    let addr = ptr.as_ptr() as *mut usize;
    MiniUart::debug_new().write_fmt(format_args!("BinAllocator::dealloc 1\n"));
    let fragment = self.get_fragment(layout);
    MiniUart::debug_new().write_fmt(format_args!("BinAllocator::dealloc 2\n"));
    unsafe { fragment.push(addr); }
    MiniUart::debug_new().write_fmt(format_args!("BinAllocator::dealloc exit\n"));
}

在输出了 BinAllocator::dealloc 2 之后就不动了，也就是那句 unsafe 挂掉了。这个时候我默默惊叹 Rust 果然厉害，以后出错首先查 unsafe。

但是呢，这个链表又是课程给的，而且我也能保证丢给链表的值是唯一的，怎么还会卡住呢？然后突然想起来 @codeworm96 的笔记中提到了这个问题。

用 panic/kprintln 调了一天，终于把出错范围缩小到 memory allocator 里 intrusive linked list 的某处 unsafe 里的一个内存写。原来 arm 对非对齐的内存访问是会 fault 的。那么测试时又为何不会出现这个问题呢？因为 x86 不对齐也可以访问。因为 intrusive linked list 会在分配的地址空间写入一个 usize, 因此每块分配的内存都至少需要满足 usize 的大小和对齐。修复后便可以正常工作了。

果真修复后便可以正常工作了……

但是我觉得很奇怪，为什么明明给了 Layout 但是还会出现不对齐的情况呢。仔细一想，原因是在申请内存的时候的 Layout 是对申请的类型 T 而言的，比方说申请 u8 是32位对齐的，而在这里强行把这个地址用作了 *mut usize，而 usize 要求64位对齐，所以这里就卡住了。

那不同平台的对齐是怎么指定的呢？RFC 131 说有一个选项会传递给 LLVM。 不过我试图修改 aarch64-none-elf.json 的 data-layout 字段，均不太成功。

  • 原先是这样的：e-m:e-i8:8:32-i16:16:32-i64:64-i128:128-n32:64-S128
  • 改成这样依旧不行：e-m:e-i8:8:64-i16:16:64-i32:32:64-i64:64:64-i128:128-n32:64-S128-p:64:64:64
  • 改成这样无法编译 core：e-m:e-i8:64:64-i16:64:64-i32:64:64-i64:64:64-i128:128-n32:64-S128-p:64:64:64

最后只好先 hack 一下 bump allocator，在分配的时候

let align = max(layout.align(), mem::size_of::<usize>());

后面实现了几个 shell 命令之后，在某些目录 ls 的时候又遇到了这样的情况，应该就是 @codeworm96 的笔记的后半段：

但是回顾 FAT32 的实现，对齐问题并没有根本上解决：实现中 block 在内存中是以 [u8] 存储，其对齐为 1, 这样转换为 FAT32 的一些 struct 后，对某些 field 的读取可能是非对齐的。不过由于这些 field 的对齐要求都没有 usize 严，所以并不会暴露出来。由于我不知道怎么限制 [u8] 的对齐，所以这个修复还处于坑掉的状态。希望知道怎么解决的朋友教我一下。

至于怎么解决……我也不懂……

总结及弃坑

感觉做了 CS140e 的三次作业之后，我对 Rust 有了基本的认识，感觉可以开始磕磕绊绊地写一些 Rust 程序了。至于课程的最后一次作业 3-spawn，我觉得我就不做了，弃坑了。原因有三点：

  1. 最后一次作业也不完整，最后两个小结也没有放出来，官方都弃坑了……
  2. 感觉 CS140e 毕竟还是实验性的性质，里面大大小小的坑还是很多。
  3. 我做这个课的目的是学习 Rust 而不是学习操作系统，前一个目的基本上达到了，而后者这个课程也不能很好地支撑。

如果读者对操作系统感兴趣的话，我强烈建议学习 MIT 6.828。我之前做过一次，感觉课程设计得非常好，相关 Lab 的笔记如果读者有需要的话也可以参考：

最后，非常感谢 Sergio Benitez 为大家提供 CS140e 了这么一个优秀的课程。