Stanford CS140e 学习笔记 (3)：文件系统

Assignment 2 实现了一个 FAT32 文件系统，以及其所依赖的内存申请释放程序、SD 卡驱动。同时，也需要实现 ls, pwd, cd, cat 等命令行工具，方便进行文件系统操作，验证文件系统是否可用。

文章目录：

• Stanford CS140e 学习笔记 (1)：Rust 基础、LED 闪烁
• Stanford CS140e 学习笔记 (2)：驱动、bootloader、shell
• Stanford CS140e 学习笔记 (3)：文件系统
• Stanford CS140e 学习笔记 (4)：用户态程序的运行

内存分配与释放

Rust 中的 Vec, Box, String 等数据类型，其数据保存在堆上，需要使用操作系统提供的内存申请、释放接口，才能正常工作。在没有操作系统的情况下，就需要自己实现相关的函数了。

Panic 信息输出

在实现内存分配函数之前，需要先实现 panic 信息输出函数，如果程序遇到异常，可通过此函数输出异常的文件、行号，以及异常原因，方便进行问题定位。

在没有操作系统的情况下，可实现 panic_fmt 函数，并添加 #[lang_item] 标记。遇到异常时函数即可自动被调用。

读取 ATAGS

在 ARM CPU 中，有部分内存地址区域中，保存有关于该 CPU 的一些信息，例如内存大小等。这些信息以类似 TLV 的形式进行保存，可通过程序进行遍历，获取必要的信息。

如下文章介绍了 ARM Linux 启动的过程中，ATAGS 的作用：

• Booting ARM Linux

在本课程中，需要实现 memory_map() 函数，通过读取 ATAGS，获取内存的大小和起始位置，并返回可用内存地址范围。

内存对齐的计算

Rust 的 alloc() 和 dealloc() 函数，与 C 中的 malloc() 和 free() 不同，在申请和释放内存的时候，都需要传入待申请内存的大小，以及对齐方式。

首先要实现 align_up() 和 align_down() 函数，传入内存大小和对齐字节数后，能够计算出与传入内存大小最接近、且大小为对齐字节数整数倍的内存数量。这两个函数，用于在后面即将实现的内存分配程序中使用。

Bump 内存分配程序

在前面的步骤中，实现了基础函数后，首先实现一个简单的 Bump 内存分配程序来练手。该内存分配程序只申请内存，不进行释放，内存占满后直接返回错误😂。

一般来说，内存分配和释放的函数，需要保证多线程访问不出问题。在本课程中，没有采用复杂的方法，而是申请释放内存时直接加锁。

Bin 内存分配程序

Bump 内存分配程序完成后，接下来就要实现一个完整的内存分配程序了。主要思路是将内存分成不同块，空闲内存通过链表相连。另外，随着内存的频繁分配释放，还需要考虑内存碎片问题，在实现的过程中，尽可能考虑减少内存碎片。

这部分难度进一步加大，除了链表已经实现好，大部分代码都需要独立完成。

目前的实现采用了长度为 32 的数组，数组中每一个元素均为一个链表头，下挂着空闲内存链表。同一个链表中的各块空闲内存大小相等，为 2 的数组下标次方数。（也就是说，数组中越往后的元素，其对应的空闲内存越大）

申请内存时，如果对应大小的内存块全部用完，则将后面更大的内存块取出，分为两半，一半用于刚刚申请的内存，另一半挂在对应大小的链表中，共以后使用。

释放内存时，如果发现释放的是之前拆开的内存，且内存另一半还在链表中，未被使用，则再将两块内存合并，以减少内存碎片。

参考文章：

• A Memory Allocator
• SHMALL简单堆内存分配器(Simple Heap Memory ALLocator)
• The SLAB Memory Allocator
• Implementing Malloc: Students and Systems Programming

在程序完成，执行测试的时候，遇到了多个 segmentation fault 问题。为了定位这些问题，学会了将 cargo test 命令与 GDB/LLDB 结合，进行程序调试。具体方法参考如下回答：

• How do I debug a failing cargo test in gdb?

文件系统

之前尝试过将 FatFs 移植到单片机。这次需要自己从头实现 FAT32 文件系统。

参考资料：

• MBR 分区表和 FAT 文件系统结构
• Design of the FAT file system – Wikipedia
• MBR与系统引导
• Master boot record – Wikipedia
• SD卡中FAT32文件格式快速入门
• FAT32文件系统详解

MBR 与 EBPB 读取

对于采用 MBR (Master Boot Record) 分区表的磁盘，首先需要读取 MBR，确定各个分区的位于磁盘中的什么部分。

MBR 位于磁盘的前 512 个字节，能够保存四条分区记录，对应四个分区。每条分区记录中，保存有分区的类型 (0xb 或 0xc 代表 FAT32)，以及起始位置和大小 (单位为 sector, 中文一般翻译为「扇区」)。MBR 的最后两个字节为 0x55, 0xaa，用于检查磁盘是否使用了 MBR.

在代码中，需要完成 MBR 的结构体，读取 MBR 后，填充到结构体，并检查其中内容无误。

EBPB (Extended Bios Parameter Block) 位于每个分区起始位置，包含关于磁盘和分区的重要信息。读取方式与 MBR 基本相同。

这部分实际编程中最可能出错的地方，主要就是相关结构体中的数据了。需要严格按照文档中的格式来完成结构体，否则就会遇到读取到的数据，相关字段对应不上的情况。

缓存

硬盘、SD 卡等设备的读写速度较慢，可通过将这些设备中的数据缓存在内存中，提高读写速度。本课程通过 HASH 实现缓存，将数据的所在的逻辑扇区位置，做为 HASH 的 Key，来查找 HASH 中是否存在对应扇区的缓存。如果命中缓存，则直接返回缓存的数据，否则将设备中的数据存入缓存后再返回。

FAT 文件系统的具体实现

接下来就是 FAT 文件系统的具体实现，最主要的是文件属性的读取，以及文件的读取。对于文件读取时可能出现的环路，使用了 Floyd 判圈算法，即使用两个变量保存 cluster，两个变量初始时均保存为待读取的 cluster，其中一个变量每次读取后，指向下一个要读取的 cluster，另一个变量则指向下下个 cluster. 如果经过了一定次的读取，两个变量保存的值相等，则说明读取文件时遇到环路。

SD 卡驱动

在我印象中，Raspberry Pi 的 SD 卡驱动使用 C lib 的形式提供，无需手动编写。

在 Rust 中，为了使用 SD 卡驱动 lib 中的函数，需要使用 Rust 的 FFI，将 lib 中的 C 函数转换为 Rust 中直接可用的函数。

在操作系统中使用文件系统和 SD 卡驱动

文件系统和 SD 卡驱动完成后，接下来，就需要在操作系统的代码中，调用初始化 SD 卡驱动和文件系统的函数。

之后，通过实现 ls, pwd, cd, cat 等命令行工具，进一步熟悉了文件系统相关接口的使用。

目前在真机调试的过程中，还不能完全正常工作，有待进一步调试。可能与内存分配有关，参考如下两篇文章：

• CS140e: (3) 文件系统
• CS140e (2) 分配内存读取文件