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

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

文章目录:

内存分配与释放

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

Panic 信息输出

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

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

读取 ATAGS

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

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

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

内存对齐的计算

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

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

Bump 内存分配程序

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

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

Bin 内存分配程序

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

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

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

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

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

参考文章:

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

文件系统

之前尝试过将 FatFs 移植到单片机。这次需要自己从头实现 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 等命令行工具,进一步熟悉了文件系统相关接口的使用。

目前可能是因为我的 Raspberry Pi 硬件问题,初始化 SD 卡驱动时,会返回错误。使用了网上其他人的程序,也是同样的现象。所以 Assignment 2 仅仅完成了代码,还没正式调通。

“Stanford CS140e 学习笔记 (3):文件系统”的2个回复

发表评论

电子邮件地址不会被公开。 必填项已用*标注