android fsck_msdos分析（一）

 FAT32.pdf 

  The UNIX File System Check Program .pdf  

  文件系统检查工具fsck研究以及dosfsck代码分析.pdf         

   最近准备重写android/external中自带的fsck工具，因为这个工具对于内存的占用太厉害了，在一些极端的大容量小簇的情况下会导致系统奔溃，所以准备重写一个。

       Android自带的fsck在检查的时候会为每一个簇分配一个struct fatentry结构体，在后面的检查中构成簇链（cluster chain）。这种方法虽然内存占用比较多，但是处理比较快速，而且适应性较强，可以处理任何情况，也算是一方面的优点吧。

（1）fat表的检查

         Fsck基本分为下面四个阶段：

1.       读FAT，并进行fat表的对比（为了保证fat表的完整性，会保持多份fat表）

2.       处理cluster chain。对于错误情况进行交互式的处理。

3.       处理文件目录项和文件

4.       处理一些无主（没有相应目录项）的数据，写入到LOST.DIR中

5.       写入fat表

我本来不想罗列代码，但是对于一个码农来说，无代码的泛泛而论都显得十分空洞。我是一懒的人，就用下面的表格来代表图。

Boot sector(MBR)

Reserved

FAT表

Root directory

Data区

很多时候大家都将前两个统称为reserved区。关于fat表的描述网络上都有很多的讲解，在此不再赘述。

 

for (cl = CLUST_FIRST; cl < boot->NumClusters;)

                   switch (boot->ClustMask) {

                   case CLUST32_MASK:

                            fat[cl].next = p[0] + (p[1] << 8)

                                            + (p[2] << 16) + (p[3] << 24);

                            fat[cl].next &= boot->ClustMask;

                            ret |= checkclnum(boot, no, cl, &fat[cl].next);

                            cl++;

                            p += 4;

                            break;

                   case CLUST16_MASK:

                            fat[cl].next = p[0] + (p[1] << 8);

                            ret |= checkclnum(boot, no, cl, &fat[cl].next);

                            cl++;

                            p += 2;

                            break;

                   default:

                            fat[cl].next = (p[0] + (p[1] << 8)) & 0x0fff;

                            ret |= checkclnum(boot, no, cl, &fat[cl].next);

                            cl++;

                            if (cl >= boot->NumClusters)

                                     break;

                            fat[cl].next = ((p[1] >> 4) + (p[2] << 4)) & 0x0fff;

                            ret |= checkclnum(boot, no, cl, &fat[cl].next);

                            cl++;

                            p += 3;

                            break;

                   }

上面的代码摘自external/fsck_msdos/fat.c文件。上面的代码根据fat表中的信息来初始化fatentry链表。可以说是fat表的一个更加直观的表现。需要注意的是FAT32中每一个表项占4个字节（也是32bit），FAT16占2个字节（16bit），FAT12占1.5个字节（12bit）.对于前两种的处理稍微简单。对于FAT12处理则稍微复杂一点，因为FAT表中的表项是按1.5字节对齐的。上面的宏CLUST_FIRST等于2.为什么等于2呢？因为0和1在fat表都有特殊的意义。comparefat函数比较简单。

在checkfat的过程中要处理的集中情况，下面是我先罗列的几种正常的情况（关于FAT的组织形式，可以去看我的博客）。

（1）

CLUST_FREE

（2）

CLUST_BAD

（3）

CLUST_EOF

（4）

A

B

C

CLUST_EOF

下面我在举几个不正常的错误。

（1）

A

B

C

CLUST_FREE

（2）

A

B

C

CLUST_RSRVD

（3）第三种不好用表格表示，我就直接用文字描述了，即两个或者多个cluster chain发生交汇。即linked。

这段代码比较难懂，这儿我贴出相关代码。

 

for (head = CLUST_FIRST; head < boot->NumClusters; head++) {

                   /* find next untravelled chain */

//如果fat[head].head == head，就表示这个簇的头是其本身，也就是这个簇是一个簇链的头部

                   if (fat[head].head != head)

                            continue;

 

//沿着簇链往下检查，按道理来讲，这个簇链中所有簇的head是一样的，如果发现其中某一个簇的head不一样，那么就表示有簇发生了交叠。为什么呢

/* for (len = 0, p = head;

* p >= CLUST_FIRST && p < boot->NumClusters;

* p = fat[p].next) {

* /* we have to check the len, to avoid infinite loop */

* if (len > boot->NumClusters) {

* printf("detect cluster chain loop: head %u for p %u\n", head, p);

* break;

* }

*

* fat[p].head = head;

* len++;}

*/

上面我插入了一段代码，也是在checkfat中，这段代码是沿着簇链，设置每一个簇的head，如果簇链交接的话，那么这段交接的簇的head必然会被检查出来。

                   for (p = head,wdk=boot->NumClusters;

                        (n = fat[p].next) >= CLUST_FIRST && n < boot->NumClusters && wdk;

                                      p = n,wdk--) {

                            if (fat[n].head != head)

                                     break;

                   }

                   pwarn("Cluster chains starting at %u and %u are linked at cluster %u\n",

                         head, fat[n].head, n);

                   conf = tryclear(boot, fat, head, &fat[p].next);

                   if (ask(1, "Clear chain starting at %u", h = fat[n].head)) {

                            if (conf == FSERROR) {

                                     /*

                                      * Transfer the common chain to the one not cleared above.

                                      */

                                     for (p = n;

                                          p >= CLUST_FIRST && p < boot->NumClusters;

                                          p = fat[p].next) {

//为什么这儿还要检查呢？可能会发生三个好，四个或者更多的链交错的情况。

                                               if (h != fat[p].head) {

                                                        /*

                                                         * Have to reexamine this chain.

                                                         */

//我们注意到了for循环中的head++，但是每一次只能处理clear掉一个簇链，如果发生超过两个簇链交叠的情况，就需要将head--，将该簇再处理一遍。

                                                        head--;

                                                        break;

                                               }

                                               fat[p].head = head;

                                     }

                            }

                            clearchain(boot, fat, h);

                            conf |= FSFATMOD;

                   }

                   ret |= conf;

         }

我个人认为上面这段代码是fsck中最纠结的部分，需要反复的解读才能明白其中的意思。

(4)第四种就是发生cluster circuit，即成环了，所以在检测的过程中会检查cluster chain的长度，避免发生circuit.当然计算cluster chain不仅仅是为了发生circuit的情况，后面还会用到cluster长度来校验文件的大小。

在校验的过程中，如果发生错误，会通过ask向用户寻求意见，如果用户不采取措施的话，fsck_check仍然采取一些行为来纠正这些错误。

在整个cluster chain的检查过程中一般会有两种纠正方法:

1.       tryclear，即在cluster chain中发生错误，即将整个cluster chain清除掉

2.       第二种即阶段操作，在发生错误的位置写入EOF，将后面的全部截断掉。这种截断操作会造成一些无主的数据，后面在LOST.DIR检查中会详细的讲到。

（2）文件及目录项的检查

说到文件及目录项，在我的脑子人第一个想到的就是文件或者目录是如何组织的。Linux中读取每一个文件的时候，都会读出或者构造一个superblock的信息，这里面除了文件系统的全局统计信息之外，另外一个极其重要的内容就是文件或者目录树的根目录所在位置。FAT文件系统也不例外，除了FAT32可以指定根目录的位置之外，FAT12和FAT16都不能，根目录必须跟在FAT表之后。

         在FAT中每一个文件或者文件夹都以目录项的形式，只不过文件夹的属性为ATTR_DIRECTORY属性，并且文件的大小为0。每一个目录项的大小为32字节。

         FAT32 byte directory entry struct

Name	Offset(byte)	Size(byte)	description
DIR_NAME	0	11	这11个字节又分为两段，其中前8个字节为文件名，后三个字节为文件的扩展属性，比如sample.txt，文件名为sample，扩展文件名为txt
DIR_Attr	11	1	文件属性： ATTR_READ_ONLY   0x1 ATTR_HIDDEN      0X2 ATTR_SYSTEM      0X4 ATTR_VOLUME_ID  0X8 ATTR_DIRECTORY   0X10 ATTR_ARCHIVE     0X20 ATTR_LONG_NAME  =ATTR_READ_ONLY|ATTR_HIDDEN|ATTR_SYSTEM |ATTR_VOLUME_ID
DIR_NTRes	12	1	Windows NT用，现在设置为0
DIR_CrtTimeTenth	13	1	文件创建时间，微秒段
DIR_CrtTime	14	2	文件创建时间
DIR_CrtDate	16	2	文件创建日期
DIR_LstAccDate	18	2	文件的最后访问时间
DIR_FstClusHI	20	2	该文件首簇的高16bit（FAT12和FAT16中设置为0）
DIR_WrtTime	22	2	文件的最后写的时间
DIR_WrtDate	24	2	文件最后写的日期
DIR_FstClustLO	26	2	文件首簇的低16bit
DIR_FileSize	28	4	文件的大小

在每一个目录项中都有属于该目录项的首簇，有人会问，既然文件夹的大小为0，那么文件夹有属于它的簇吗，当然有，这些簇中保持的不是数据，而是一些目录项。

我们可以先整理一下思路。FAT文件系统的super block中指定了根目录所在的簇，然后根据fat表，可以找到一个簇链，该簇链中都是上面描述的32字节的directory entry struct。

每一个目录项要么描述的是一个文件夹，要么是一个文件。文件夹又可以根据首簇找到一个簇链，这个首簇必然是这个簇链的头（如果不是，那么就是发生错误了），这些簇中包含的又是这些32字节的directory entry struct数组。如果是文件，那么这些簇中是这个文件的数据。这样可以在脑海中浮现出这样的一个文件树的组织形式。当然fat中没有所谓的super block，而是boot sector。但是其根本的目的是一样的。

         说到这儿，可能有人又有问题，这么文件的文件名只有8个字节，那么我们磁盘中文件的长名字是如何组织的呢？

         其实FAT的设计者早就想好了，如果长名字没什么的，不过是一分为几而已，下面是长目录项定义。

FAT long directory entry

Name	Offset(byte)	Size (bytes)	description
LDIR_Ord	0	1	长目录项的index 如果0x40，那么就是长目录项的最后一个
LDIR_Name1	1	10	长名字的第1-5个字符
LDIR_Attr	11	1	属性
LDIR_Type	12	1	如果是0，表示该长目录项是长文件名的一部分
LDIR_Chksum	13	1	校验和，用于检验长文件名的完整性
LDIR_Name2	14	12	长文件名的第6-11个字符
LDIR-FstClustLO	26	2	必须为0
LDIR_Name3	28	4	长文件名的第12-13个字符

有人会问，为什么讲这13个字符一份为3呢，这是为了保持与短目录项的一致。长目录项中的文件首簇为0，即没有指定文件的数据所在的位置。这些信息是在短目录项中指定的。所以说，每一个文件或者文件夹必然有一个短目录项，但是不一定有长目录项。

上图是一个长目录项的sample。其中长目录项是以倒序的形式组织的。有人会问为什么要倒序呢？其实倒序的好处就是可以一下子知道长目录项的个数。如果是以顺序的形式组织的话，必然需要一个字段用来存储长目录项的总长度，这显然太浪费了。

既然长目录项中存储的是文件的长文件名，那么短目录项的文件名字段是空着的吗？不是，fat以一种算法将长文件名压缩到8个字符，然后存储在短目录项中，段目录项中存储了文件（夹）的基本信息，比如首簇位置，文件长度等等。

前面在cluster chain的校验过程中已经讲到了，通过读取fat表来构建簇链，那么在文件检查中，会读出相应文件的信息，比如首簇。然后根据首簇找到其相应的簇链。这个检查会有两种结果：

（1）       没有找到与该文件相应的簇链。

（2）       簇链中仍然多余的链没有找到相应的文件目录项

如果出现第一种情况，那么fsck就会将这个目录项清除掉，这个清除并不是将每一个目录项的32字节全部清零，只需要在目录项的第一个字节写入相关信息即可。

#define SLOT_EMPTY 0x00 /* slot has never been used */

#define SLOT_E5 0x05 /* the real value is 0xe5 */

#define SLOT_DELETED 0xe5 /* file in this slot deleted */

其中SLOT_DELETED表示这个目录项被删除了，可以在下次入新文件的时候被使用。SLOT_EMPTY表示从该目录项开始，后面再也没有有效的目录项了，即后面的目录项都是空白的。这样在查找空闲目录项的时候省了进一步查找的时间。

如果出现第二种情况，在android的SD卡中，如果注意的话，会在根目录下发现一个叫LOST.DIR的文件夹，fsck会将一些无主的数据写入到LOST.DIR目录中。其中名字是以这段无主数据的首簇命名的。网上很多网友说SD时间长了，剩余空间会不足，可以直接将LOST.DIR目录删除掉。但是千万别将LOST.DIR目录删除掉，至少我在当前的代码中还没有见到重建LOST.DIR目录的相关代码。如果你删除了，说不定系统会检查失败，然后将你的SD卡格式化掉。。。

（3）处理无主的文件

在这儿我们统称为无主的文件，因为其实不单单是文件数据，也有可能是目录项是数据。但是不管是那种数据。Fsck都会将其当做原始数据写入LOST.DIR中。

if (!lostDir) {

                   for (lostDir = rootDir->child; lostDir; lostDir = lostDir->next) {

                            if (!strcmp(lostDir->name, LOSTDIR))

                                     break;

                   }

                   if (!lostDir) { /* Create LOSTDIR? XXX */

                            pwarn("No %s directory\n", LOSTDIR);

                            return FSERROR;

                   }

         }

从上面这段代码可以看出两点：1.LOST.DIR是在根目录下面。2.如果没有LOST.DIR目录，fsck不会去主动的重建，看来只能留给格式化程序了。

(void)snprintf(d.name, sizeof(d.name), "%u", head);

从上面这段可以看出，LOST.DIR中的文件是以首簇作为文件名的

在checklost中海油一段代码为：

                            mod |= writefsinfo(dosfs, boot);

有人就会问，既然有了bootsector，为什么还要写入一些所谓的fsinfo（file system information）呢。其实仔细看看bootsector中的字段就会发现：boot sector只描述了fat文件系统的一些静态信息，比如每个簇的大小，文件系统的类型（12,16,32）等等。但是缺失一些动态信息，而这些动态信息关系到了文件系统的性能，比如文件系统中的可供分配的下一个空闲簇，这是极其关键的。因为不可能等到分配空闲簇的时候才去查找，为时已晚，严重影响到了文件系统的性能。所以在检查的过程中顺便统计一下这些动态信息，并与文件系统保持的动态信息比较矫正。

最后一步当然更新fat表了，当然有人可能会说，你好好检查就行了，为什么还要重写fat表，答案是因为fat信息可能是错误的。

Fat的更新是建立两个基础之上的：

1.       由于一些错误，导致fat表中的簇信息被clear或者truncate

2.       Fsck通过ask询问用户是否需要修改fat表。

如果同时满足上面两个条件，fsck才会去重写fat表。Fat表的写入比较简单。