Chinaunix首页 | 论坛 | 博客
  • 博客访问: 115814
  • 博文数量: 28
  • 博客积分: 28
  • 博客等级: 民兵
  • 技术积分: 62
  • 用 户 组: 普通用户
  • 注册时间: 2011-10-08 16:15
个人简介

study,record,share

文章分类
文章存档

2015年(2)

2014年(12)

2013年(12)

2012年(2)

我的朋友

分类: LINUX

2015-08-20 11:47:24

 FAT32.pdf 

  The UNIX File System Check Program .pdf  

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

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

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

1fat表的检查

         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表的描述网络上都有很多的讲解,在此不再赘述。

 

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

  2.                    switch (boot->ClustMask) {

  3.                    case CLUST32_MASK:

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

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

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

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

  8.                             cl++;

  9.                             p += 4;

  10.                             break;

  11.                    case CLUST16_MASK:

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

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

  14.                             cl++;

  15.                             p += 2;

  16.                             break;

  17.                    default:

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

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

  20.                             cl++;

  21.                             if (cl >= boot->NumClusters)

  22.                                      break;

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

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

  25.                             cl++;

  26.                             p += 3;

  27.                             break;

  28.                    }

上面的代码摘自external/fsck_msdos/fat.c文件。上面的代码根据fat表中的信息来初始化fatentry链表。可以说是fat表的一个更加直观的表现。需要注意的是FAT32中每一个表项占4个字节(也是32bit),FAT162个字节(16bit),FAT121.5个字节(12bit.对于前两种的处理稍微简单。对于FAT12处理则稍微复杂一点,因为FAT表中的表项是按1.5字节对齐的。上面的宏CLUST_FIRST等于2.为什么等于2呢?因为01fat表都有特殊的意义。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

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

 

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

  2.                    /* find next untravelled chain */

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

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

  5.                             continue;

 

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

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

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

  4. * p = fat[p].next) {

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

  6. * if (len > boot->NumClusters) {

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

  8. * break;

  9. * }

  10. *

  11. * fat[p].head = head;

  12. * len++;}

  13. */

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

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

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

  17.                                       p = n,wdk--) {

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

  19.                                      break;

  20.                    }

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

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

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

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

  25.                             if (conf == FSERROR) {

  26.                                      /*

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

  28.                                       */

  29.                                      for (p = n;

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

  31.                                           p = fat[p].next) {

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

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

  34.                                                         /*

  35.                                                          * Have to reexamine this chain.

  36.                                                          */

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

  38.                                                         head--;

  39.                                                         break;

  40.                                                }

  41.                                                fat[p].head = head;

  42.                                      }

  43.                             }

  44.                             clearchain(boot, fat, h);

  45.                             conf |= FSFATMOD;

  46.                    }

  47.                    ret |= conf;

  48.          }

我个人认为上面这段代码是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可以指定根目录的位置之外,FAT12FAT16都不能,根目录必须跟在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

该文件首簇的高16bitFAT12FAT16中设置为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字节全部清零,只需要在目录项的第一个字节写入相关信息即可。

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

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

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

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

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

3)处理无主的文件

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

  1. if (!lostDir) {

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

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

  4.                                      break;

  5.                    }

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

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

  8.                             return FSERROR;

  9.                    }

  10.          }

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

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

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

checklost中海油一段代码为:

                            mod |= writefsinfo(dosfs, boot);

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

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

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

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

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

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

阅读(1968) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~