早期的文件系统是以FAT(File Allocate Table)文件分配表形式组织形成的，由于操作系统作业需要实现一个FAT32文件系统，所以这里简单介绍了解一下FAT文件系统的组织结构及具体实现。

Pre-knowledge

MBR（Main Boot Record）

主引导记录，占446字节, 为计算机启动后从可启动介质上首先装入内存并且执行的代码，通常用来解释分区结构。

DBR（DOS Boot Record）

DOS引导记录，为操作系统进入文件系统以后可以访问的第一个扇区，通常用来解释文件系统，DBR是由硬盘的MBR装载的程序段。DBR装入内存后，即开始执行该引导程序段，其主要功能是完成操作系统的自举并将控制权交给操作系统。每个分区都有引导扇区，但只有被设为活动分区才会被MBR装的DBR入内存运行。

EBR（Extended Boot Record）

扩展分区引导记录，类似于主引导记录MBR.因为MBR四条分区信息的限制,可以使用EBR方便扩展.它的结构与MBR类似,但是没有引导程序和磁盘签名,仅仅保留了分区表和结束标志。

FAT32 File System

Introduction to FAT32

  • FAT（File Allocation Table，文件分配表）文件系统是windows操作系统所使用的一种文件系统，它的发展过程经历了FAT12、FAT16、FAT32三个阶段。FAT文件系统用“簇”作为数据单元。一个“簇”由一组连续的扇区组成，簇所含的扇区数必须是2的整数次幂。簇的最大值为64个扇区，即32KB（一个扇区512Bytes）。所有簇从2开始进行编号，每个簇都有一个自己的地址编号。用户文件和目录都存储在簇中。
  • FAT文件系统的数据结构中有两个重要的结构：文件分配表和目录项：
    • 文件分配表：文件和文件夹内容储存在簇中，如果一个文件或文件夹需要多于一个簇的空间，则用FAT表来描述，如何找到另外的簇。FAT结构用于指出文件的下一个簇，同时也说明了簇的分配状态。FAT12、FAT16、FAT32这三种文件系统之间的主要区别在于FAT项的大小不同。
    • 目录项：FAT文件系统的每一个文件和文件夹都被分配到一个目录项，目录项中记录着文件名、大小、文件内容起始地址以及其他一些元数据。
  • 在FAT文件系统中，文件系统的数据记录在“引导扇区中（DBR）”中。引导扇区位于整个文件系统的0号扇区，是文件系统隐藏区域（也称为保留区）的一部分，我们称其为DBR扇区，DBR中记录着文件系统的起始位置、大小、FAT表个数及大小等相关信息。在FAT文件系统中，同时使用“扇区地址”和“簇地址”两种地址管理方式。这是因为只有存储用户数据的数据区使用簇进行管理（FAT12和FAT16的根目录除外），所有簇都位于数据区。其他文件系统管理数据区域是不以簇进行管理的，这部分区域使用扇区地址进行管理。文件系统的起始扇区为0号扇区(逻辑0扇区)。

    FAT32 file structure

  • 保留区：DOS引导扇区，FAT12、FAT16一般只有一个引导扇区，FAT32多一些。
  • FAT表：FAT区由两个大小相等的FAT文件分配表组成，FAT1、FAT2挨着
  • 数据区：FAT32根目录通常位于2号簇。FAT12、FAT16的根目录虽然也属于数据区，但是他们并不由簇进行管理。也就是说FAT12、FAT16的根目录是没有簇号的，他们的2号簇从根目录之后开始。

    Reserved Partition

    保留区由若干个扇区组成，保留区大小记录在DBR扇区中，常见为32、34、38个扇区。由DBR中0x0e和0x0f两个地址的数值决定，小端字节序，即N的值。

    DBR

  • 0x00~0x02：3字节，跳转指令。
  • 0x03~0x0A：8字节，文件系统标志和版本号，这里为MSDOS5.0。
  • 0x0B~0x0C：2字节，每扇区字节数，0x0200=512
  • 0x0D~0x0D：1字节，每簇扇区数，0x08
  • 0x0E~0x0F：2字节，保留扇区数，0x0C22=3106
  • 0x10~0x10：1字节，FAT表个数，0x02
  • 0x11~0x12：2字节，FAT32必须等于0，FAT12/FAT16为根目录中目录的个数
  • 0x13~0x14：2字节，FAT32必须等于0，FAT12/FAT16为扇区总数。
  • 0x15~0x15：1字节，哪种存储介质，0xF8标准值，可移动存储介质。
  • 0x16~0x17：2字节，FAT32必须为0，FAT12/FAT16为一个FAT 表所占的扇区数。
  • 0x18~0x19：2字节，每磁道扇区数，只对于“特殊形状”（由磁头和柱面分割为若干磁道）的存储介质有效，0x003F=63。
  • 0x1A~0x1B：2字节，磁头数，只对特殊的介质才有效，0x00FF=255。
  • 0x1C~0x1F：4字节，EBR分区之前所隐藏的扇区数，0x0004A800=305152又出现了呢，与MBR中地址0x1C6开始的4个字节数值相等。
  • 0x20~0x23：4字节，文件系统总扇区数，0x00E83800=15218688
  • 0x24~0x27：4字节，每个FAT表占用扇区数，0x000039EF=14831
  • 0x28~0x29：2字节，标记，此域FAT32 特有。
  • 0x2A~0x2B：2字节，FAT32版本号0.0，FAT32特有。
  • 0x2C~0x2F：4字节，根目录所在第一个簇的簇号，0x02。（虽然在FAT32文件系统下，根目录可以存放在数据区的任何位置，但是通常情况下还是起始于2号簇）
  • 0x30~0x31：2字节，FSINFO（文件系统信息扇区）扇区号0x01，该扇区为操作系统提供关于空簇总数及下一可用簇的信息。
  • 0x32~0x33：2字节，备份引导扇区的位置。备份引导扇区总是位于文件系统的6号扇区。
  • 0x34~0x3F：12字节，用于以后FAT 扩展使用。
  • 0x40~0x40：1字节，与FAT12/16 的定义相同，只不过两者位于启动扇区不同的位置而已。
  • 0x41~0x41：1字节，与FAT12/16 的定义相同，只不过两者位于启动扇区不同的位置而已 。
  • 0x42~0x42：1字节，扩展引导标志，0x29。与FAT12/16 的定义相同，只不过两者位于启动扇区不同的位置而已
  • 0x43~0x46：4字节，卷序列号。通常为一个随机值。
  • 0x47~0x51：11字节，卷标（ASCII码），如果建立文件系统的时候指定了卷标，会保存在此。
  • 0x52~0x59：8字节，文件系统格式的ASCII码，FAT32。
  • 0x5A~0x1FD：共410字节，引导代码。
  • 0x1FE~0x1FF：签名标志“55 AA”。
    FAT文件系统将引导代码与文件形同数据结构融合在FAT32文件系统引导扇区的512字节中，90~509字节为引导代码，而FAT12/16则是62~509字节为引导代码。同时，FAT32还可以利用引导扇区后的扇区空间存放附加的引导代码。一个FAT卷即使不是可引导文件系统，也会存在引导代码。

    FSINFO扇区

    FAT32在保留区中增加了一个FSINFO扇区，用以记录文件系统中空闲簇的数量以及下一可用簇的簇号等信息，以供操作系统作为参考。FSINFO信息扇区一般位于文件系统的1号扇区，结构非常简单。
  • 0x200~0x203：4个字节，扩展引导标志“0x52526141”。
  • 0x204~0x3E3：480个字节，未使用，全部置0。
  • 0x3E4~0x3E7：4个字节，FSINFO签名“0x72724161”。
  • 0x3E8~0x3EB：4个字节，文件系统的空簇数，0xFFFFFFFF,这个值感觉有问题，格式化SD卡新建一个小于4K的文件，此处的值变成0x1CF6FE，所以上面的值应该为0x1FF6FF，猜测可能是由于格式化之后就会将此处置FF，新建文件后才会恢复
  • 0x3EC~0x3EF：4个字节，下一可用簇号（0x00000002）。
  • 0x3F0~0x3FD：14个字节，未使用。
  • 0x3FE~0x3FF：2个字节，“55 AA”标志。
  • 温馨提示：通常情况下，文件系统的2号扇区结尾也会被设置“55 AA”标志。6号扇区也会有一个引导扇区的备份，相应的7号扇区应该是一个备份FSINFO信息扇区，8号扇区可以看做是2号扇区的备份。

FAT表

保留分区后面的是FAT区，由两个完全相同的FAT（File Allocation Table，分区表）构成。FAT表是一组与数据簇号对应的列表。FAT2紧跟在FAT1之后，可以由 FAT表扇区数+FAT1 计算出来。

FAT表作用

  • 文件系统分配磁盘空间按簇来分配。因此，文件占有磁盘空间时，基本单位不是字节而是簇，即使某个文件只有一个字节，操作系统也会给它分配一个最小单元：即一个簇。对于大文件，需要分配多个簇。同一个文件的数据并不一定完整地存放在磁盘中一个连续地区域内，而往往会分若干段，像链子一样存放。这种存储方式称为文件的链式存储。为了实现文件的链式存储，文件系统必须准确地记录哪些簇已经被文件占用，还必须为每个已经占用的簇指明存储后继的下一个簇的簇号，对于文件的最后一簇，则要指明本簇无后继簇。这些都是由FAT表来保存的，FAT 表对应表项中记录着它所代表的簇的有关信息：诸如是空，是不是坏簇，是否是已经是某个文件的尾簇等。
  • 对于文件系统来说，FAT表有两个重要作用：描述簇的分配状态以及标明文件或目录的下一簇的簇号。
  • 通常情况下，一个FAT文件系统会有两个FAT表，但有时也允许只有一个FAT表，FAT表的具体个数记录在引导扇区的偏移0x10字节处。
  • 由于FAT区紧跟在文件系统保留区后，所以FAT1在文件系统中的位置可以通过引导记录中偏移0x0E~0x0F字节处的“保留扇区数”得到，即M值。

    FAT表分析

    FAT32中每个簇地址都有$32bit$，则FAT表中所有地址位置以4字节（Bytes）为单位进行划分，并且对划分后位置为0的地址进行编号，0号地址与1号地址系统保留，从2号地址开始，每个地址对应于数据区的簇号。