FAT32 文件恢复

编程实验 (基于 Linux)

截止时间 (Hard Deadline)：2026年1月13日 23:59 (本学期所有 labs 的最终 Hard Deadline)

提交内容：

  1. 代码源文件 fat32.c：注意代码中应有必要的注释。
  2. 实验报告 学号.pdf：简要描述实验中遇到的关键问题及解决方案、印象最深的 bugs、或者额外实现的功能等即可 (1～2 页)。

提交方式： TBD

FAT (File Allocation Table) 是 MS-DOS 和早期 Windows 等操作系统中默认使用的文件系统。目前 FAT 已从 FAT12、FAT16 发展到 FAT32 和 exFAT 等，该文件系统在设计和实现上的简单特点也使其在 USB 存储卡等移动存储介质上得到了广泛应用。 在本次实验中，我们需要编写 C 语言代码来实现对 FAT32 文件系统的访问，以更好地理解文件 (File) 和目录 (Directory) 的概念，并在此基础上实现一个能恢复 FAT32 文件系统中已删除文件的程序。

运行如下命令下载本实验的框架代码：

git clone https://git.nju.edu.cn/oslab/fat32-2025fall.git
cd fat32-2025fall

🗒️ 实验内容

FAT 文件系统的布局 (File System Layout) 由如下四个部分组成：

  • Reserved Region：存储 FAT 文件系统的各项属性信息 (Super Block)，其中第一个扇区 (Sector) 存储了 FAT 文件系统的 BPB (BIOS Parameter Block) 结构；
  • FAT Region：存储 File Allocation Table 数据结构，通常包括两个表，其中一个作为备份；
  • Root Directory Region：存储根目录内容，注意 FAT32 没有 Root Directory Region；
  • Data (File and Directory) Region：存储具体文件数据，以数据块 (Data Block) 来作为逻辑存储单元，其中每个数据块由物理磁盘上的若干连续扇区 (Sector) 构成。FAT 文件系统将每个数据块称为一个簇 (Cluster)，每个簇对应一个 FAT 表项。

我们可以使用 mmap() 来将一个 FAT 文件系统镜像 (例如 fat32.img) 映射到进程虚拟地址空间，随后就可以像操作内存中的某个数据结构一样来读取和分析文件系统中各个部分的内容：只要能计算得到正确的 “指针” (例如，第 K 个 Cluster 或 Sector 的起始地址)，你就能访问文件系统中的特定数据。

为了知道你想访问的数据具体位于什么地方，你需要参考 FAT 文件系统的规格说明。该手册内容并不是很多，是了解真实文件系统具体设计的一个很好的出发点。特别地，你需要注意查看：

  • Sections 3.1 和 3.3：了解 BPB 结构体中包含的内容、以及各项的含义；
  • Section 4：了解 FAT 的结构、以及如何根据簇号计算得到该簇在 FAT 中的位置；
  • Section 6：了解目录项的具体结构及其中各项的含义、以及如何计算得到编号为 K 的簇的第一个 Sector 的起始地址；
  • Section 6.7：了解如何计算得到 Data Region 的起始地址。

框架代码和实现需求

我们提供的框架代码中包括如下文件：

  • fat32.h：该文件提供了 FAT32 的 BPB 结构 Fat32BPB 和目录项结构 DirEntry 等；
  • fat32.c：该文件包含待实现的文件恢复 API 接口；
  • main.c：该文件包含一个调用文件恢复接口的简单测试用例 (对提交代码的测试也会以类似的方式进行)；
  • fat32.img 和 fat32_img：一个大小为 64MB 的 FAT32 文件系统镜像、以及其中未删除时的文件内容，可用于测试。

基于框架代码中已经设计好的结构体，你需要实现 fat32.c 中的如下 API：

int fat_recovery(const char *image_path);

其中，输入参数 image_path 是待扫描 FAT32 文件系统镜像的路径。 运行上述 API 将尝试恢复该文件系统中尽可能多的已删除文件，并最终将所有普通文件的恢复结果按如下格式存储在 fat32-2025fall/output.txt 文件中 (恢复的普通文件数作为 API 的返回值)：

APPLE.TXT 2aae6c35c94fcfb415dbe95f408b9ce91ee846ed
DOS.TXT d98b38a8c6e8a1c6e8a1c6e8a1c6e8a1c6e8a1c6
HELLO.BMP 1234567890abcdef1234567890abcdef12345678

这里的每行代表一个已恢复的普通文件，包括文件名和文件数据的 SHA1 签名 (由命令行工具 sha1sum 计算得到) 两部分，中间使用一个空格隔开；多个普通文件的输出顺序可以任意指定。

上述输出应仅包含文件系统中所有普通文件的恢复结果，而不需要包括目录文件。但是需要注意，如果某个包含普通文件的目录被删除，则这些普通文件也属于应恢复的文件 (即你需要递归处理所有发现的已删除目录，以找到其中可能存在的普通文件)。例如，上述输出示例可能对应如下的 FAT32 文件系统：

  /
  ├── APPLE.TXT (已删除)
  ├── BANANA.BMP (未删除)
  ├── CHERRY.TXT (未删除)
  └── DIR/ (已删除)
      ├── DOS.TXT (已删除)
      └── HELLO.BMP (已删除)

为了简化 fat_recovery() 的实现：

  • 你可以仅考虑 FAT32 而不需要对其它 FAT 文件系统格式进行兼容；
  • 仅需要支持短文件名，即可以假设文件系统中所有文件都采用 8.3 格式来命名 (最长 8 个字符文件名 + 3 个字符扩展名)，且不区分大小写；
  • 可以假设文件系统中仅包含 .txt 和 .bmp 两类普通文件；
  • 可以假设每个目录中都仅包含少量文件；
  • 不需要考虑多个线程/进程同时执行文件恢复的情况。

🛠️ Tips

基础实现思路

在 FAT32 文件系统中，删除文件操作并不会立即从磁盘移除文件数据，而是仅将目录项中文件名的第一个字节修改为 0xE5，同时将文件占用的 Data Blocks 在 File Allocation Table 中标记为空闲状态 (在恢复时，你可以将文件名的第一个字节替换为任意可打印字符)。此时，文件数据仍然保留在磁盘上，直到这些 Data Blocks 被新的文件覆盖，这使得恢复已删除的文件成为可能。

为了实现文件恢复，你需要能首先获取 FAT32 文件系统的布局信息 (File System Layout)，然后还需要能打开目录文件和普通文件 (Resolve File Name)，并读取其中的内容。其中涉及的一些关键基础操作包括：

  1. 挂载磁盘镜像：读取 FAT32 文件系统的 Super Block。框架代码中提供的 int fat_mount(const char *path) 已经实现了对 Fat32BPB 结构体的读取，你可以对照 FAT 规格说明手册了解其中各项的具体含义，然后进一步进行修改和定制 (例如，计算得到 Data Region 的起始地址)。

  2. 打开和读取文件：解析文件名以获取文件的属性信息，然后基于该信息顺序读取文件的全部内容。

  3. 读取目录项：读取目录中每个文件 (包括普通文件和目录文件) 的目录项，并从中解析文件名、文件第一个 Data Block、以及文件大小等属性信息。

你可以基于框架代码中的结构体先设计和实现上述基础 API，然后再基于这些 API 实现文件的扫描和恢复。

这里需要注意，当单个文件大小超过一个 Data Block 大小时，文件数据会被存储在多个 Data Blocks 中。此时，由于文件删除时已将 File Allocation Table 中的对应表项设置为空闲状态，我们就需要去 “猜测” 哪些 Data Blocks 属于这个被删除的文件。

针对上述问题，一种直观的思路是从文件系统的 Data Blocks 分配方式入手，即在存储空间充足的情况下，文件系统往往会按顺序分配方式存储大文件。基于此，我们就可以利用文件大小信息来辅助判断哪些 Data Blocks 属于该文件。当然，对于碎片化的存储方式，就需要应用更复杂的恢复策略 (例如，利用文件格式特征等)。

计算 SHA1 签名

为了计算文件数据 data 的 SHA1 签名，可以参考和利用框架代码中的如下函数：

int calculate_sha1(const uint8_t *data, uint32_t size, char *buf);

该函数会首先将长度为 size 的 data 写入一个临时文件 temp_path，然后调用命令行工具 sha1sum 来计算文件内容的 SHA1 签名。sha1sum 执行时会从该临时文件中读取数据，然后把计算得到的 SHA1 checksums (160-bit) 输出到标准输出，并最终被 fscanf 读取到 buf。

构建测试对象

为了创建一个FAT32 文件系统用于实验，你可以先使用 Linux 中的 dd (data duplicator) 命令来创建一个特定大小的空文件 (这里利用了 /dev/zero 这个 “零” 设备来作为数据复制的原始地址)：

dd if=/dev/zero of=fs.img bs=1M count=64

然后使用 mkfs.fat 来将其快速格式化为一个 FAT32 文件系统镜像 (其中，-F 指明 FAT 类型，-S 指明 Sector 大小，-s 指明每个 Cluster 由多少个 Sectors 组成)：

mkfs.fat -F 32 -S 512 -s 8 fs.img

在此之后你可以使用 mount 命令来将 fs.img 挂载到你当前的文件系统中：

mount fs.img /mnt/

然后你就可以在/mnt/中按需创建或删除各类文件/目录。本次实验框架代码所提供的fat32.img示例文件系统就是使用上述的方式制作的。

此外，在你每次对文件系统进行创建或删除文件/目录操作后，还可以使用 hexdump 命令直接查看 FAT32 镜像的十六进制结构并进行比对，这对于理解文件系统如何实现文件和目录的创建和删除非常有帮助。例如：

hexdump -C -s 147456 -n 4096 fat32.img
  • -C: 规范格式显示 (Canonical Format)。显示三列：
    • 左边：偏移地址 (十六进制)
    • 中间：十六进制字节值 (16 个字节一组)
    • 右边：对应的ASCII字符（不可打印字符显示为 .）
  • -s 147456: 跳过前 147456 字节 (s = skip)，即从第 147457 个字节开始显示
  • -n 4096: 只显示 4096 字节 (n = number)

📊 结果评估

我们将使用若干不同的 FAT32 文件系统镜像来对你实现的 fat_recovery() 的正确性进行测试，主要包括：

  • 对不同数量、以及不同类型文件的恢复；
  • 对已删除目录中普通文件的恢复；
  • 对存储于单个 Data Block 的 “小” 文件、以及存储于多个连续 Data Blocks 的 “大” 文件的恢复。

注意提交的代码不能对框架代码 fat32.c 中的头文件进行修改，否则会直接返回错误信息。