文件系统检查工具—fsck研究

文件系统检查工具—fsck研究

 

第一部分 理论

导致一个文件系统corrupt的原因有可能有几种，而最经常的就是非正常关机流程和硬件的错误造成的。

 

造成corrupt的主要原因就是在停止CPU之前没有同步系统数据。如果非正常的启动没有被检测到，比如没有检查文件系统的一致性，没有修复不一致的数据，允许使用一个corrupt的文件系统将是一种灾难。另外，一部分硬件有可能在任何时间出错，如在磁盘上的一个坏的块，或者是磁盘控制器没有响应等。

 

一般情况下fsck会在非交互的方式下运行。这种方式只会修正由unclean halt所引起的corrupt。这些操作一般是在交互方式下运行操作的子集。这份文档中我们默认fsck是在交互方式下运行的，所有可能的错误都会遇到。在这种方式下发现不一致的情况，则会将其汇报给操作者选择修正的方式。

在执行fsck时，文件系统必须处于一种quiescent state，因为fsck是一个multi-pass的程序。

以下部分分别讨论发现数据不一致的方法，修正cylinder group blocks，inodes, indirect blocks 和包含有目录项的data blocks的方法。

 

1.       Super block checking

在一个文件系统中最经常corrupt掉的是super block中的汇总信息。原因是这些信息在文件系统的block或者inode的每项改动，都需要在汇总信息中做相应的修改。因此，经常会corrupt（汇总信息与实际的文件系统信息不一致）。

Super block的一致性检查包括文件系统大小，inode数量，空闲的block块，空闲的inode数量等。文件系统的大小必须大于super block和inode使用的block数的和。文件系统的大小和布局信息是对fsck而言至关重要的信息。但并没有一种可以实际检查这些大小，因为他们是由newfs静态决定的，fsck可以检查这些大小在一个合理的范围之内。如果fsck在默认的super block中的静态的参数中检查到corrupt，它就会要求提供备用的super block所存放的地址。

 

2.       Free block checking

Fsck会检查所有在cylinder group block maps （注：cylinder group即对应于fs的partions。）中标记为free的块，即没有被文件占用的块。Fsck会检查free的块的数量与inode中声明使用的块的数量的和是否与整个文件系统的所有块数相等。

如果在block allocation maps中有任何错误，fsck将根据其计算的allocated blocks进行重新组建block allocation maps。

Super block中也存有所有free块的数量信息，fsck会把自己检查的结果与super block中的信息进行比较。如果这两个数不等，则fsck会将检查得到的结果更新到super block中。对文件系统中的free inode的数量，也会进行类似的处理。

 

3.       Checking the inode state

当文件系统中有很多inode存在的时候（即很多文件），有可能会有几个inode corrupt。文件系统中的inode链表是从inode2开始顺序被检查的（inode0标记没有用过的inode，inode1用来将来的扩展），直到文件系统中的最后一个inode。Inode的状态检查包括：format and type, link count, duplicated blocks, bad blocks, and inode size。

每个inode都有一个mode word，它描述了inode的type和state。Inode必须处于六种类型之一：普通inode，目录inode，symbolink inode，special block inode，special character inode，或者是socket inode。

Indoe有三种allocation状态：unallocated，allocated 和不属于前两种情况的情况。在第三种状态的inode就是不正确的inode，当inodes链表被写入坏的数据的时候，inode有可能进入这种状态。唯一可能修复的方法是fsck清空这个inode（在链表中删除之）。

4.       inode links

连接数是计算每一个inode与其相连的目录项的数目。fsck从文件系统的root目录开始检查每一个inode的连接数，并沿着目录树依次查找。每个inode的实际link count在遍历的时候计算得到。

如果存储的link count非0，而计算的link count为0，则此inode没有对应的目录项。这种情况下，fsck将把这个对应的文件放入lost+fount目录中。如果存储的link count与实际计算所得的值非0且不相等，那么可能是inode的link count在有一个目录加入或删除的时候没有被相应更新。这种情况下，fsck会用计算得到的值更新存储的值。

每个inode都包含一个列表或者是列表的指针，上面记录着这个inode所使用的数据块。因为inode是这些列表的拥有者，因此，当这些列表存在不一致的情况时，就直接影响到拥有它的inode。

Fsck会将一个inode声明的block number与列表中已经分配的block number比较。如果另一个inode已经声明了一个block number，那么这个block number就被加入到一个duplicate block 链表中。否则，已分配的block list中会将这个block number加入。

对任何duplicate blocks，fsck将会遍历inode list找到拥有duplicated block的inode。一般而言，拥有最早修改时间的inode 坏掉的可能性比较大，需要被clear。如果是这种情况，fsck将执行操作，clear这两个inodes。操作必须决定，哪个该留，哪个该clear。

Fsck检查每个inode声明的block number的范围，如果block number比文件系统中第一个数据块的块号低，或者比文件系统中的最后一个数据块的块号大，则称为bad block number。一个inode中许多的bad blocks经常是由于一个indirect block没有被写入到文件系统中，发生这种情况的前提是由于有硬件异常的产生。如果一个inode含有bad block numbers，fsck会将其clear。

5.       inode data size

每个inode包含一定数量的data blocks。实际data block的数量是所有allocated data blocks和indirect blocks的总和。Fsck计算实际的data blocks的数量，并与inode所记录的数值进行比较。如果两者不一致，fsck会进行修正。

每个inode包含了一个32位的size域。这个数是inode对应的文件所含有的字节数。这个size域的一致性检查是通过计算与inode对应的最大数量的blocks数，与实际inode保存的数值比较。

 

6.        checking the data with an inode

一个inode可以直接或间接的reference三种类型的data blocks。所有的referenced blocks必须是同种类型。这三种类型是：plain data blocks， symbolic link data blocks和directory data blocks。Plain data blocks包含文件中保存的信息。symbolic link data blocks包含一个link中包含的路径名。Directory data blocks包含目录项。Fsck只能检查directory data blocks的有效性。

Fsck 会检查每个directory data block的几种一致性：directory inode指向unallocated inodes，directory inodes的数量比文件系统中的inode数量大，不正确的“.”“..”directory inode numbers，没有结合在文件系统中的directories。如果一个directory data block中的inode number references 一个unallocated inode， fsck将移除这个directory entry（目录项）。这种情况只发生在存在硬件异常的情况下。

Fsck检查与unallocated blocks（holes）对应的directories。这些directories应当从不被创建。当发现这些directory存在时，fsck将通过缩短这些directory大小到上一个allocated block结尾的hole来提示用户去调整这些directory。但同时这又意味着另一轮的第一部分检查需要执行---super blockchecking。Fsck将提示用户在修改一个含有unlocated block的directory 后重新执行fsck。（Whenfound, fsck will prompt the user to adjust the length of the offending directory which is done by shortening the size of the directory to the end of the last allocated block preceeding the hole. Unfortunately, this means that another Phase 1 run has to be done. Fsck will remind the user to rerun fsck after repairing a directory containing an unallocated block.）

如果一个directory entry的inode number reference不在inode list中，fsck会移除这个directory entry。这一般发生在bad data被写入到a directory data block的情况下。

“.”的directory inode number entry必须是directory data block的第一个entry。“.”的inode number必须reference 它自己。比如，它必须等于directory data block 的inode number。“..”的directory inode number entry必须是directory data block的第二个entry，它的值必须与这个directory entry的父目录的inode number 相等（如果是root directory的“..”，则与其directory data block的inode number相等）。如果directory inode numbers不正确，fsck将用正确的值取代它。如果目录有许多hard links，第一个被认为是“..”指向的真正的父目录，fsck 会倾向于删除其后出现的名称。（recommends deletion for the subsequently discovered names.（不懂这句话）

7.       File system connectivity

Fsck检查文件系统的general connectivity。如果目录不被link到文件系统中，fsck 会link directory 到文件系统中的 lost+found directory。这个条件只有在发生硬件异常的时候成立。

 

翻译文献：Fsck - The UNIX File System Check Program Marshall Kirk McKusick

 

 

 

第二部分 dosfsck实现分析

 

1.       Main 函数：

Main()

{

解析输入参数；

fs_open();//打开设备文件，并取得其fd以全局使用

read_boot();//读取并检查boot_sector内容

while (read_fat(&fs), scan_root(&fs)) qfree(&mem_queue);//检查分区表, 根目录以及所有子目录文件

if (test) fix_bad(&fs); //扫描所有的cluster，如果一个cluster没有owener，且在fat表中记录的值不合法，则进一步判断不可读，在fat表中将其标示为“bad”。

if (salvage_files) reclaim_file(&fs); //-f位设定的话，将cluster chain中的free cluster归为文件所有，

else reclaim_free(&fs);// 否则归free disk所有。

free_clusters = update_free(&fs); // 读取磁盘上的free cluster数目，并更新到fs结构中。

file_unused();//??????

qfree(&mem_queue);//问题：memory是怎样使用的？

if (verify) {

printf("Starting verification pass.\n");

read_fat(&fs);

scan_root(&fs);

reclaim_free(&fs); //reclaim unused cluster

qfree(&mem_queue);

}

 

if (fs_changed()) {

if (rw) {

           if (interactive)

              rw = get_key("yn","Perform changes ? (y/n)") == 'y';

           else printf("Performing changes.\n");

       }

       else

           printf("Leaving file system unchanged.\n");

    }

 

    printf( "%s: %u files, %lu/%lu clusters\n", argv[optind],

           n_files, fs.clusters - free_clusters, fs.clusters );

 

    return fs_close(rw) ? 1 : 0;

 

}

 

2.       read_boot()

主要完成的工作是检查boot sector中的内容。取得相应的文件系统信息。

Read_boot(){

读取分区的boot sector;

If(扇区字节数为0，或者cluster大小为0)

{

退出

}

If(分区表的数目>2 或者<1)

{

     退出： 不支持分区表数目

}

检查root_cluster和root_entries;

如果是FAT32，则检查check_backup_boot().

检查总cluster数与fat表能表示的最大数是否冲突；

检查root directory的大小是否为0；

检查root entry是否占据整数个扇区；

检查逻辑扇区是否是物理扇区的整数倍。

检查boot sector记录的是否非法磁盘格式；

If(verbose)

Dump_boot();//把boot sector信息输出到内存中。

}

 

3.       read_fat

主要完成的工作是检查FAT的有效性。一般fat文件系统会有2个fat，因此可以检查哪个可用，或者采用交互的方式由用户决定采用哪个fat。

Read_fat()

{

将fat表拷贝到内存中。

如果含有2个分区表，则比较这2个表是否一致。

If(2个分区表不同)

{

判断2个分区表的有效性（判断依据需要进一步探讨）；

只有一个有效则用有效的一个覆盖无效的一个；

两个都有效

If(用户交互模式)

{根据用户的选择}

Else{选择第二个有效}

}

Else 选择第一个。

如果2个分区表都无效，则文件系统崩溃，退出检查。（无法修复）

检查fat表的内容，如果出现越界（超过能标示cluster号的最大值），则设置为eof。

 

4.       scan_root

主要完成

函数逻辑：

Scan_root(){

Check_dir();  //root

Check_files() //root

Subdirs(); //sub directories and files

}

(1)    check_dir

check_dir()

{

检查目录下的所有文件(包括文件夹)的文件名。

如果一个文件夹下的文件包含太多的坏文件名，则对其进行截断操作。

遍历所有文件{

If(是 . 或者 ..)

{

         Handle_dot();

}

If(文件夹属性非ATTR_VOLUME，而且文件名不合法)

{

     If(用户交互模式)

     {

          1) Drop file\n2) Rename file\n3) Auto-rename\n 4) Keep it

}

}

 

}

检查是否含有相同名字的文件，有则"1) Drop first\n2) Drop second\n3) Rename first\n"

                            "4) Rename second\n5) Auto-rename first\n"

                            "6) Auto-rename second\n");。

}遍历结束

检查是否含有. 和..

}

 

(2)    check_files

static int check_files(DOS_FS *fs,DOS_FILE *start)

{

    while (start) {

       if (check_file(fs,start)) return 1;

       start = start->next;

    }

    return 0;

}

 

(3)    check_file()

if(文件是目录)

{

if(文件的dentry大小不为0)

{

    设置文件的dentry大小为0；

}

if(是”.”)

{

    开始的cluster号是否与parent相同。如果不同则将“.”的cluster号改为parent目录的cluster号；

}

if(是”..”)

{

    开始的cluster号是否与parent的parent目录相同。如果不同则将“.”的cluster号改为parent的parent目录的cluster号；

}

if(FSTART(file,fs)==0)

{

    删除此指向root的目录。

}

if(FSTART(file,fs) >= fs->clusters+2)

{

    超出文件系统的cluster界限，则改为EOF？？？？MODIFY_START(file,0,fs);

}

}

遍历所有的cluster

{

    遇到“bad”cluster则改为EOF；MODIFY_START(file,0,fs);

    如果root 含有bad cluster，则退出；

 

    If(文件非目录 且文件记录的大小小于实际cluster大小“遍历cluster得到的数值”)

    {

        则对文件进行截短处理。修改文件的大小值，并修改cluster chain，全部标记为free，即只存在entry记录，无对应实体数据？

}

If(current cluster 有拥有者)

{

     有错误；

     需要选择保留哪个？

}

设置current cluster的owner。

}（遍历结束）

If(文件的实际大小大于entry记录中的文件大小)

{

    修改entry记录文件大小的值为实际的大小。

}

 

}

(4)    subdirs()

static int subdirs(DOS_FS *fs,DOS_FILE *parent,FDSC **cp)

{

    DOS_FILE *walk;

 

    for (walk = parent ? parent->first : root; walk; walk = walk->next)

       if (walk->dir_ent.attr & ATTR_DIR)

           if (strncmp(walk->dir_ent.name,MSDOS_DOT,MSDOS_NAME) &&

             strncmp(walk->dir_ent.name,MSDOS_DOTDOT,MSDOS_NAME))

              if (scan_dir(fs,walk,file_cd(cp,walk->dir_ent.name))) return 1;

    return 0;

}

 

(5)    scan_dir

scan_dir()

{

 

Check_dir()

Check_files()

 

}