主要参考了这篇博客.
1. 文件系统
维基百科对于文件系统给出了如下的定义和解释:
计算机的文件系统是一种存储和组织计算机数据的方法，它使得对其访问和查找变得容易，文件系统使用文件和树形目录的抽象逻辑概念代替了硬盘和光盘等物理设备使用数据块的概念，用户使用文件系统来保存数据不必关心数据实际保存在硬盘（或者光盘）的地址为多少的数据块上，只需要记住这个文件的所属目录和文件名。在写入新数据之前，用户不必关心硬盘上的那个块地址没有被使用，硬盘上的存储空间管理（分配和释放）功能由文件系统自动完成，用户只需要记住数据被写入到了哪个文件中。
文件系统通常使用硬盘和光盘这样的存储设备，并维护文件在设备中的物理位置。但是，实际上文件系统也可能仅仅是一种访问资料的界面而已，实际的数据可能是通过网络协议（如NFS、SMB、9P等）提供的或者暂存于内存上，甚至可能根本没有对应的文件（如proc文件系统）。
严格地说，文件系统是一套实现了数据的存储、分级组织、访问和获取等操作的抽象数据类型（Abstract data type）。
2. FAT
FAT (File Allocation Table, 文件分配表) 是一种由微软发明并拥有部分专利的文件系统，供MS-DOS使用，也是所有非NT核心的Windows系统使用的文件系统。
FAT文件系统考虑当时电脑性能有限，所以未被复杂化，因此几乎所有个人电脑的操作系统都支持。这特性使它成为理想的软盘和存储卡文件系统，也适合用作不同操作系统中的资料交流。
但FAT有一个严重的缺点：当文件删除后写入新资料，FAT不会将文件整理成完整片段再写入，长期使用后会使文件资料变得逐渐分散，而减慢了读写速度。碎片整理是一种解决方法，但必须经常磁盘碎片整理来保持FAT文件系统的效率。
3. FAT12
初期的FAT就是现在俗称的FAT12。作为软盘的文件系统，它有几项限制：
- 不支持分层性结构
- 簇寻址只有12位（这使得控制FAT有些棘手）
- 而且只支持最多32M的分区.
当时入门级的磁盘是5.25"、单面、40磁道、每个磁道8个扇区、容量略少于160KB。上面的限制超过了这个容量一个或几个数量级，同时允许将所有的控制结构放在第一个磁道，这样在读写操作时移动磁头。这些限制在随后的几年时间里被逐步增大。
由于唯一的根目录也必须放在第一个磁道，能够存放的文件个数就限制在几十个。
FAT12的基本组织单位
- byte: 基本数据单位——在FAT12中, 没有比byte更小单位的数据
- sector: 磁盘中的最小数据单元——磁盘的读写最小只能以一个sector为一个单位
- cluster: 一个cluster是一个或多个扇区
FAT12 文件系统的组成
| 起始扇区位置 | 长度 (单位: 扇区) | 内容 |
|---|---|---|
| 0 | 1 | 引导扇区 (Boot Sector): 负责启动计算机并加载操作系统，同时它也包含了有关磁盘和文件系统的相关信息. |
| 1 | 9 | FAT1 (File Allocation Table1): 存储了文件在磁盘上的位置信息，以及每个文件或目录的属性等. |
| 10 | 9 | FAT2 (File Allocation Table2): 同上. |
| 19 | 14 | 根目录区 (Root Directory Region): 存储了文件系统中所有根目录下的文件和子目录的相关信息，这些信息通常包括文件名、扩展名、文件大小、创建时间、修改时间、访问时间等. |
| 33 | — | 文件数据 |
FAT12 Boot Sector
主引导区的大小为512个字节, 主引导区的构成如下表
| identifier | offset (byte) | type | size | default value | description |
|---|---|---|---|---|---|
| BS_JmpBoot | 0 | db | 3 | 跳转指令 | |
| BS_OEMName | 3 | db | 8 | MSWIN4.1 | OEM字符串, 必须为8个字符, 不足的话以空格补上 |
| BPB_BytesPerSec | 11 | dw | 2 | 0x0200 | 每个扇区的字节数 |
| BPB_SecPerClus | 13 | db | 1 | 1 | 每个簇的扇区数 (注意 FAT12中每个簇默认只有一个扇区) |
| BPB_RsvdSecCnt | 14 | dw | 2 | 1 | Boot占用的扇区数 |
| BPB_NumFATs | 16 | db | 1 | 2 | FAT表的记录数 |
| BPB_RootEntCnt | 17 | dw | 2 | 0xE0 | 最大根目录文件数 |
| BPB_TotSec16 | 19 | dw | 2 | 0xB40 | 逻辑扇区总数 |
| BPB_Media | 21 | db | 1 | 0xF0 | 媒体描述符 |
| BPB_FATSz16 | 22 | dw | 2 | 9 | 每个FAT占用的扇区数 |
| BPB_SecPerTrk | 24 | dw | 2 | 0x12 | 每个磁道的扇区数 |
| BPB_NumHeads | 26 | dw | 2 | 2 | 磁头数 |
| BPB_HiddSec | 28 | dd | 4 | 0 | 隐藏扇区数 |
| BPB_TotSec32 | 32 | dd | 4 | 0 | 如果BPB_TotSec16为0, 那么在这里记录扇区总数 |
| BS_DrvNum | 36 | db | 1 | 0 | 中断13的驱动器号 |
| BS_Reserved1 | 37 | db | 1 | 0 | 未使用 |
| BS_BootSig | 38 | db | 1 | 0x29 | 扩展引导标志 |
| BS_VolID | 39 | dd | 4 | 0 | 卷序列号 |
| BS_VolLab | 43 | db | 11 | 卷标, 必须为11个字符, 不足的话以空格补上 | |
| BS_FileSysType | 54 | db | 8 | FAT12 | 文件系统类型, 必须为8个字符, 不足的话以空格补上 |
| BOOT_Code | 62 | db | 448 | FAT12 | 引导代码, 由offset=0处短跳转来 |
| END | 510 | db | 2 | 0x55, 0xAA | 系统引导标识 |
根目录区的目录项
根目录区由若干个目录项构成, 每个目录项的大小是32个byte
| member | offset (byte) | size (byte) | description |
|---|---|---|---|
| DIR_Name | 0 | 11 | 文件名8字节, 扩展名3字节 |
| DIR_Attr | 11 | 1 | 文件属性 |
| Reserve | 12 | 10 | 保留位 |
| DIR_WrtTime | 22 | 2 | 最后一次写入时间 |
| DIR_WrtDate | 24 | 2 | 最后一次写入日期 |
| DIR_FstClus | 26 | 2 | 文件开始的簇号 |
| DIR_FileSize | 28 | 4 | 文件大小 |
我真的很讨厌 markdown 的表格
FAT
FAT是FAT12的数据组织核心
在 FAT12 文件系统中, 包括两个 FAT (File Allocation Table): FAT1 和 FAT2, 两者是相互备份的关系 ，数据内容完全一致.
从数据结构的角度看, FAT表是一个有向关系图, 这个图记录了文件先后关系.
FAT表包括若干个紧密分布的表项 (FATEntry), 每个表项占用12bit (也就是说3个表项占用2个字节), 每个表项都与数据区中的一个簇相对应，而且表项的序号也是与簇号一一对应的. 当然, 也有一些特例
- FATEntry的值 $\geq$ 0xFF8，表示当前簇已经是本文件的最后一个簇
- FATEntry的值为 0xFF7, 表示它是一个坏簇
在1.44M软盘上，FAT前三个字节 (即前两个FATEntry) 的值是固定的: 0xF0、0xFF、0xFF, 用于表示这是一个应用在1.44M 软盘上的FAT12 文件系统。本来序号为 0和1的FAT表项应该对应于簇0和簇1，但是由于这两个表项被设置成了固定值，Cluster0 和 Cluster1就没有存在的意义了，所以数据区就起始于 Cluster2.
FAT 表以一种非常优雅的方式规范了文件数据的先后关系. 假设 $DIR\_FstClus$ 表示文件第 $0$ 簇 (扇区) 的位置, 第 $i$ 个表项 $vec[i]$ 表示文件数据的实际位置, 则文件第一扇区的位置为 $vec[DIR\_FstClus]$ , 且迭代地有, 第 $i+ 1$ 个表项的实际位置为