跳转至

FAT16 文件系统

定位

本文是实验4：语义文件系统的 Part1 阅读材料，内容包括 FAT16 文件系统简介与实验任务。本实验需要同学们完成的代码中有大量与 FAT16 特点相关的内容，请同学们在进行实验4 Part1 之前认真阅读此文实验背景部分，以对 FAT16 文件系统的元数据、FAT 表、目录项等结构有较深了解。之后按照实验任务的要求完成实验

1. 实验背景

NexOS 原生使用的文件系统将磁盘划分为 superblock、inode 区、bitmap 区和 data block 区。其中，superblock 保存文件系统的整体布局信息，例如磁盘大小、inode 数量、bitmap 起始位置等；inode 区保存每个文件或目录的元数据；bitmap 用于记录数据块是否已经被分配；data block 区则存放文件内容和目录项。inode 结构中包含了指向数据块的地址，这些数据块分为直接块与间接块，直接块中保存的数据即为文件数据，而间接块中保存的数据则是直接块的地址，原生的文件系统通过此方式扩展一个文件能够占用的磁盘空间。

FAT16 文件系统与 NexOS 原生的文件系统无论是从磁盘结构还是从数据存储等方面来看均有较大区别，接下来本文将介绍 FAT16 的具体结构。

FUSE

FUSE（Filesystem in Userspace）是 Linux 系统提供的内核接口，允许非特权用户在不用编写内核模块的情况下实现自己的文件系统，即文件系统的主要逻辑运行在用户态程序中，内核只负责把来自应用程序的文件操作请求转发给用户态文件系统进程。为简化设计，本实验并未提供类似 FUSE 的接口，而是直接让内核运行 FAT16 文件系统。感兴趣的同学可以在课后时间了解 FUSE，在 Linux 虚拟机内实现一个文件系统，依靠 FUSE 挂载到用户态中。

1.1 FAT16 文件系统总览

文件分配表（File Allocation Table）是一种由 Microsoft 发明的文件系统，此文件系统编排的文件以簇链表的形式存储在磁盘中，并将连接信息存入特定位置的 FAT 表中，16 代表着文件系统最多管理 \(2^{16}\) 个簇。以下是 FAT16 文件系统为磁盘划分的功能区：

FAT16 文件系统磁盘结构

下面将分区对 FAT16 如何管理文件做说明。

1.2 引导扇区

Note

这里重点关注引导扇区对文件系统磁盘分区的作用，因此不介绍引导扇区如何引导虚拟机启动操作系统。

运行在内存中的内核并不天然知道某 FAT16 镜像中一个簇有多少扇区（此实验内“扇区”与“块”可以相互替换）、一个扇区有多少字节等信息，同样地，内核也不知道 FAT 表、根目录以及数据区的位置（起始地址），这些数据都被保存到了引导扇区中的基本输入输出参数块（BIOS Parameter Block）中，我们称这些数据为 FAT16 的元数据。

引导扇区固定为镜像文件的第一个扇区，因此我们在初始化文件系统时要从第一个扇区内将此镜像对应的 FAT16 元数据读取到内存中。一个扇区的大小通常为 512 字节，引导扇区里诸多位置（称“偏移”）对应的数据都有其特殊意义，这里只截取出重要的（做实验需要的）条目供大家阅读。

块内偏移地址 长度（字节） 含义
0x000b 2 每扇区字节数
0x000d 1 每簇扇区数
0x000e 2 保留扇区数，引导扇区就是一个保留扇区
0x0010 1 FAT 表个数
0x0011 2 根目录项数
0x0013 2 扇区总数，小于 32MB 的分区记录在这里
0x0016 2 每 FAT 表包含扇区数
0x0020 4 扇区总数，大于 32MB 的分区记录在这里

举一个例子来说明这些数据的作用，假设保留扇区数为 1，FAT 表个数为 1，每 FAT 表包含扇区数为 21，由此可以得到根目录在磁盘上的按块偏移是 1 + 1 * 21 = 22，于是我们就可以使用 bread(dev, 22) 读取到根目录的第一个块存储的数据了。

1.3 目录与 FAT 表

上文提到文件系统通过 FAT 表来编排文件，这其中到底是如何工作的呢？请同学们仔细阅读本章节的相关内容，确保对目录项、簇链、目录等这些名词有更深入的认识。

1.3.1 目录项

上文说引导扇区存储了文件系统的元数据，告诉操作系统文件系统的各个功能区在哪里，本节所说的目录项相对于文件的作用就类似于引导扇区相对于文件系统结构的作用。

首先明确一个事实，目录项与数据是分开（没有在磁盘上连续）存储的，顾名思义，目录项就是一个目录下面的条目，它告诉调用者这个文件的信息，如名字、类型、存放位置等，唯独不直接给出文件数据的字节流，真正给出数据的是簇链。FAT16 的标准目录项固定为 32 字节，下面看目录项内的各个字段代表着什么信息。

目录项内偏移地址 长度（字节） 含义
0x00 8 文件名
0x08 3 扩展名
0x0b 1 文件属性，表示文件只读、隐藏、是否是目录等信息
0x0c 1 保留字段
0x0d 1 创建时间的毫秒部分，以 10ms 计
0x0e 2 文件的创建时间
0x10 2 文件的创建日期
0x12 2 最后访问日期
0x14 2 文件起始簇号高 16 位
0x16 2 最后修改时间
0x18 2 最后修改日期
0x1a 2 文件起始簇号低 16 位
0x1c 4 文件大小

表格中除了两个与簇号相关的字段都易理解，不再赘述，下面介绍什么是簇、簇号怎么转化成磁盘上的位置、簇链在磁盘上是如何连接的、簇链如何终止。

簇是连续扇区的组合，是 FAT16 文件系统分配磁盘空间的最小单位，也就是说，不管文件实际有效字节数有多少，都至少会给该文件分配一个簇的磁盘空间。

簇在磁盘上的编排

文件系统将磁盘的数据区（见FAT16 文件系统磁盘结构）划分为一个个簇，簇号从 2 开始编排，原因在于 0 号和 1 号已经被 FAT 表用来记录媒体介质描述符和脏标记与错误历史记录了，这与本次实验无关，同学们只需要了解数据区的簇号是从 2 开始的就可以了。需要特别说明的是，0 号簇和 1 号簇是不存在于磁盘上的。

假设我们现在已经知道某文件的簇号，接下来要如何读这个文件的数据呢？虽然文件系统是以簇为分配磁盘空间的单位，但是内核读磁盘数据却是按照扇区（块）读的（bread() 即 Block Read），所以文件系统要将簇号转化为磁盘上的块偏移才能使用。FAT16 的元数据已经告诉我们保留扇区的个数、FAT 表的个数、每 FAT 表的扇区数、根目录项数，依据这些数据可以得到数据区的起始扇区号 data_sector，再结合每簇的扇区数 sector_per_cluster，则可以按照下面的公式计算簇号为 cluster 的簇的首扇区号：

\[ \rm{first\_sector = data\_sector + (cluster - 2) * sector\_per\_cluster} \]

1.3.2 簇链

如果所有的文件都只占用少于一个簇的空间，那现在拥有目录项与簇编排的文件系统已经能满足需要了。但显然，这是不够的，对于更大的文件，文件系统需要分配更多簇给它。

如何存储一个文件用了哪些簇呢？先看一个容易想到的方法：让文件从起始簇号连续地占用多个簇并在文件目录项内使用一个字段用来填充文件连续占用簇数。这种方法实现简单，文件系统的结构也简单。我们关注它的缺点，当考虑需要修改文件内容时，如果追加了一定的内容使得文件系统必须分配一个新的簇给该文件而恰好该文件簇尾之后的一个簇已经被占用，那么文件系统就需要重新找一块能存储这个文件的空间并写入，带来文件增长的繁琐操作与低效的空间利用。

因此，FAT16 采用了链表的形式来为文件分配簇，存储簇链连接信息的结构就是 FAT 表。见下图：

FAT 表示例

如图所示，表的前 2 项为保留项，不用来填下一个簇号，因此 0 号簇和 1 号簇实际上不存在；2 号项的值为 0x0000，代表这个簇是空闲的；3 号项的值为 5，5 号项的值为 7，7 号项的值为 0xFFFF，这是 EOC（End Of Chain） 标志，说明文件结束，假设 3 号簇是某文件的首簇，则这个文件所分配的簇就是 3、5、7，同理以 4 号簇为首簇的文件所分配的簇就是 4、6。FAT 表项不同值有不同含义，具体映射如下：

FAT16 表项值 含义
0x0000 空闲簇
0x0001 保留簇
0x0002 - 0xffef 被占用的簇；指向下一个簇
0xfff0 - 0xfff6 保留值
0xfff7 坏簇
0xfff8 - 0xffff 被占用的簇；文件最后一个簇

关于 FAT 表的个数

FAT 表可以有多个，除一个主表外，其他用于备份或其他事宜。

1.3.3 目录

文件系统根据元数据将磁盘分区固定下来，根目录下的文件的目录项存放在位于 FAT 表之后、数据区之前的根目录区，这是很好理解的。然而一方面根目录区的大小是固定的，即根目录只能存放 512（通常是）个文件，另一方面如何在根目录里归类文件呢，通过创建子目录可以解决这个问题。

我们先看根目录下普通文件的创建：为文件分配一个新的簇（即在磁盘上找到一个空闲的簇号），然后编写这个文件的目录项，将这个目录项追加到根目录区中，目录项用来存文件的元数据，簇用来存文件的数据流。类似于根目录，子目录也要能存目录项，于是我们可以得到这样的结构：父目录创建一个目录项指向一个子目录（标记该目录项属性为目录），子目录的簇只用来存其下的目录项数据，由于簇是可以增长的，因此子目录的簇可以存放的目录项数也是可以扩张的，这与根目录不同。

总而言之，子目录就是(用一块数据区的簇来存放(其下文件的)目录项的)文件（这话有点绕，同学们结合上文和本节末的图理解下^_^）。

1.3.4 FAT16 文件系统访问文件流程示例

下图是对 data/file.txt 文件的访问示例图：

文件访问示例图

如图，文件系统先从根目录区匹配到 data 的目录项，然后读出它的首簇，簇中存放了 data 下文件的目录项，然而在首簇中没有匹配到 file.txt 文件，因此需要读 FAT 表继续读下一个簇，在第 2 个簇中，找到了 file.txt 的目录项，并读出其簇。

2. 实验任务

本节说明本次实验 Part1 需要补全的函数。同学们可以参考以下顺序完成实验4 Part1。如果对某个辅助函数的参数含义不清楚，可以参考 实验4补充材料：辅助函数与宏定义速查。

Part 1 的目标是让 FAT16 文件系统能够正常挂载，并支持根目录和普通子目录中的文件读写。完成这一部分后，文件系统应当能够读取根目录、读取文件内容、创建和删除文件、创建和删除目录，并处理跨簇文件读写。

实现注意

注意：待实现函数中存在为通过编译器检查的 return -1 和 return 0 等命令以及提示未实现的 panic 命令，请同学们在实现后记得注释掉这些代码，以免测试失败。

2.1 挂载文件系统并初始化 FAT16 元数据

void fat16fs_fsinit(int dev);
static uint fat16_cluster_first_sector(uint cluster);
static uint fat16_read_fat(uint cluster);

实现流程如下：

  1. 在 fat16fs_fsinit() 中，代码已经通过 bread() 读入第 0 号扇区，并把扇区数据指针保存在 d 中。你需要使用 get16() 和 get32() 从 BPB 中取出 FAT16 元数据，写入 meta 中对应的成员。

  2. 继续在 fat16fs_fsinit() 中，根据已经读取出的 BPB 字段推导 FAT 区、根目录区和数据区的位置。这里需要得到 FAT 表起始扇区、根目录起始扇区、数据区起始扇区、数据簇数量和每簇字节数等信息。

  3. 在 fat16_cluster_first_sector() 中，根据数据簇号返回该簇在磁盘上的第一个扇区。后续读普通文件、读子目录、扩展目录时都会依赖这个函数。

  4. 在 fat16_read_fat() 中，根据簇号定位到 FAT 表项所在扇区，用 bread() 读取该扇区，用 get16() 解析 FAT16 表项，再用 brelse() 释放 buffer。返回值是 FAT 表项值，可能是下一个簇号，也可能是表示簇链结束的 EOC 值。

2.2 按目录项序号定位目录项

static int fat16_slot_by_index(struct inode *dp, uint index,
                               struct fat16_slot *slot);

这个函数的作用是：给定一个目录 inode 和目录项序号 index，找到该目录中的第 index 个 FAT16 32B 目录项，并把目录项内容以及它所在的扇区、扇区内偏移记录到 slot 中。

你只需要实现根目录下的查询，实现流程如下：

先检查 index 是否超过根目录项数量，如果没有越界，就根据根目录起始扇区和目录项序号定位扇区与偏移，再调用 fat16_read_entry() 读出目录项，最后填写 slot->sector、slot->offset 和 slot->index。

2.3 根据文件偏移定位或扩展簇链

static int fat16_cluster_for_offset(struct inode *ip, uint off,
                                    int alloc, uint *cluster_out);

这个函数接收文件 inode、文件内偏移 off 和 alloc 标志，输出 off 对应的簇号 cluster_out。读文件时 alloc == 0，不能分配新簇；写文件时 alloc != 0，如果偏移超过当前簇链范围，就需要扩展簇链。

实现流程如下：

  1. 先根据文件偏移判断目标在簇链中的第几个簇。

  2. 如果文件还没有首簇，读路径应该直接失败；写路径则需要调用 fat16_alloc_cluster() 分配第一个簇，并记录到 inode 中。

  3. 从首簇开始沿 FAT 链向后走。每走一步，先用 fat16_read_fat() 读出当前簇的 FAT 表项。

  4. 如果读路径提前遇到 EOC，说明目标偏移没有对应数据，应返回 -1。如果写路径遇到 EOC，则调用 fat16_alloc_cluster() 分配新簇，并用 fat16_write_fat() 把新簇接到当前簇后面。

  5. 成功走到目标簇时，把簇号写入 cluster_out 并返回 0。

2.4 读取普通文件内容

int fat16fs_readi(struct inode *ip, uint64 off, void *dst, uint n);

文件的读取

大家在使用文件指针的时候是否思考过它读取文件的流程？实际上它提供了一个在文件内的偏移量和要读的字节数，就是此函数的 off 和 n 变量，然后通过磁盘或者内存操作进行流式的读取，将数据拷贝到缓冲区中，此函数帮助大家更好地理解文件读取。

函数前面的检查已经处理了空指针、目录读取、文件类型检查以及越过文件末尾的情况。

实现流程如下：

  1. 从 copied = 0 开始循环。

  2. 每次循环先调用 fat16_cluster_for_offset()，以 alloc == 0 找到当前偏移对应的簇；如果找不到，说明簇链异常或数据不足，应停止读取。

  3. 找到簇后，用 fat16_cluster_first_sector() 定位到簇的起始扇区，再根据当前文件偏移确定本次要读的扇区和扇区内偏移。

  4. 调用 bread() 读取扇区，把需要的字节用 memmove() 拷贝到 dst，再调用 brelse() 释放 buffer。

  5. 每次最多读到当前扇区末尾，读完后更新 copied，直到读够 n 字节或遇到错误。

提示

正常情况下，只有实现了上述功能，Nexos 才能正确进入 shell。

2.5 写入普通文件内容并更新文件大小

int fat16fs_writei(struct inode *ip, uint64 off, const void *src, uint n);

实现流程如下：

  1. 普通文件写入循环的整体结构和读取循环类似：从当前写入偏移出发，调用 fat16_cluster_for_offset() 定位目标簇。这里必须使用 alloc = 1，因为写入可能超过当前簇链长度，需要在必要时分配新簇。

  2. 找到目标簇后，用 fat16_cluster_first_sector() 定位扇区，调用 bread() 把扇区读入内存，把用户数据用 memmove() 覆盖到 buffer 中，再调用 bwrite() 写回磁盘，最后调用 brelse() 释放 buffer。

  3. 每次最多写到当前扇区末尾，直到写完 n 字节或遇到错误。

  4. 写入结束后，根据本次写入的结束位置决定是否需要扩大 ip->size。

  5. 更新 ip->size 后调用 fat16fs_iupdate()，把新的文件大小和首簇号写回 FAT16 标准目录项。

思考题

ip->size（即 file_size）应该在何时更新？