FAT文件系统学习记录一

这些天在看关于FAT文件系统的一些资料，思路有时混乱，有时又变得清晰起来。我想大抵学习的过程就是这样子吧。

首先在深入的了解FAT的linux源码之前，需要了解一些FAT的原理。

  《FAT文件系统原理》

从这个的简单的介绍中可以了解到FAT文件系统的布局，FAT表的组织，目录的形式，长短文件目录项的关系等等。这些都是FAT文件系统的一些基本思想。

图一：FAT32的组织形式

为了了解FAT的格式，需要仔细而详细的阅读《FAT文件系统原理》的4.3  FAT表和数据的存储原则。后面继续将到了 FAT32 短文件目录和FAT32长文件目录的定义，关于长短文件目录项，可以在后面介绍源码的时候详细的解释。

从《FAT文件系统原理》可以看出FAT表中差不多是采用了一种编程语言中的链表技术来组织FAT表的。

图二：用winhex查看FAT32格式的SD卡的FAT表，该FAT32文件系统的簇大小为0x800,没有保留簇，所以FAT表从第2簇开始。

从上图可以看出，FAT32是以F8 FF FF FF 表示一个FAT表的开始。FAT表中的每一个表项为2个字节，存储的是文件接下来的数据在哪一个簇中。FAT表中以一个FF FF来表示一个文件的结束。从上表中可以看出，其中一个长文件A是从第0x4簇开始的，到第0x45簇结束（图二中红线部分）。接下来的8个0xFF表示存储的是4个小文件。同样其中一个文件B是从第0x48簇开始，到第0x89簇结束。那么有人就会要问，我怎么知道一个文件到底是从哪个簇开始的，总不至于搜索这个FAT表吧。

这个问题分两步来回答，其中一部分涉及到了FAT文件的目录表项。在linux中用结构体struct msdos_dir_entry来描述。另外一个涉及到了所谓的fat表cache的结构体。

有人可能就有疑问了，像上面的文件A，它所占用的簇都是连续的，如果每次都是从第一个簇开始查找，这不是太麻烦了。可不可以将连续的簇合并？

下面就先从struct fat_cache结构体开始吧。

struct fat_cache {

//用于组成链表。

struct list_head cache_list;

//用于记录连续的簇，方便查找

int nr_contig; /* number of contiguous clusters */

//该簇在文件中的标号

int fcluster; /* cluster number in the file. */

//在簇在设备上的实际位置

int dcluster; /* cluster number on disk. */

};

其中成员nr_contig用于描述连续的簇的个数。struct list_head cache_list用于链表的链接。这个链表属于谁呢？答案是这个链表属于inode节点。（再次不多描述，如果对于VFS文件系统有一定了解，那么就很容易理解）。

fat_cache是FAT文件系统中一个使用频率很高的结构体，内核专门为该结构体建立一个slab缓存。

通过fat_cache_init函数来建立一个slab高速缓存。

int __init fat_cache_init(void)

{

fat_cache_cachep = kmem_cache_create("fat_cache",

sizeof(struct fat_cache),

0, SLAB_RECLAIM_ACCOUNT,

init_once, NULL);

if (fat_cache_cachep == NULL)

return -ENOMEM;

return 0;

}

通过fat_cache_destroy函数来销毁掉slab高速缓存。

void fat_cache_destroy(void)

{

if (kmem_cache_destroy(fat_cache_cachep))

printk(KERN_INFO "fat_cache: not all structures were freed\n");

}

这样的话，在需要分配fat_cache结构体的时候，内核通过fat_cache_free来从高速缓存中分配一个fat_slab结构体，通过函数fat_cache_free来将该fat_cache结构体返回给slab高速缓存。

FAT通过fat_cache_lookup从链表中查找一个文件簇在磁盘中的实际位置。

函数的输入参数为inode结构体，前面提到了，链表属于inode结构。参数fclus是指要查找的文件簇在该文件中的相对位置。但是另外的3个输入参数为指针，对此感到比较奇怪。struct fat_cache_id指针cid用于保持在链表中找到的离fclus最近的一个fat_cache的信息。那么cached_fclus和cached_dclus呢？cached_fclus用于返回查找到离fclus最近的file cluster(cluster  number in file)，cached_dclus用于返回查找到的离disk cluster(cluster number on disk)最近位置。在下面的代码中在细细解释。

static int fat_cache_lookup(struct inode *inode, int fclus,

    struct fat_cache_id *cid,

    int *cached_fclus, int *cached_dclus)

{

static struct fat_cache nohit = { .fcluster = 0, };

struct fat_cache *hit = &nohit, *p;

int offset = -1;

spin_lock(&MSDOS_I(inode)->cache_lru_lock);

//函数遍历与inode对应的msdos_inode_info结构体的cache_lru队列。这就是该inode的fat_cache队列

list_for_each_entry(p, &MSDOS_I(inode)->cache_lru, cache_list) {

/* Find the cache of "fclus" or nearest cache. */

if (p->fcluster <= fclus && hit->fcluster < p->fcluster) {

hit = p;

//查看该hit是否包含了fclus，如果没包含，那么就继续查找该队列的下一个。那么问题出现了，如果该队列后面没有fat_cache了呢?

//这就是问题的关键了，如果没有找到能够包含该fclus，那么就返回离fclus最近的fat_cache。下面就没有办法了，只能从FAT表中一个一个的慢慢查找了。并将查找的结果通过fat_cache_merge或者fat_cache_add添加队列中去。（具体操作请看fat_get_cluster函数）

if ((hit->fcluster + hit->nr_contig) < fclus) {

offset = hit->nr_contig;

} else {

//如果该fclus 包含在其中，那么问题就变得很简单。

offset = fclus - hit->fcluster;

break;

}

}

}

//hit != &nohit，即该链表不为空

if (hit != &nohit) {

fat_cache_update_lru(inode, hit);

//注意CID中保持的是链表中最近的一个

cid->id = MSDOS_I(inode)->cache_valid_id;

cid->nr_contig = hit->nr_contig;

cid->fcluster = hit->fcluster;

cid->dcluster = hit->dcluster;

//返回在fat_cache中包含的离fclus最近的file cluster

*cached_fclus = cid->fcluster + offset;

*cached_dclus = cid->dcluster + offset;

}

spin_unlock(&MSDOS_I(inode)->cache_lru_lock);

return offset;

这样子通过每个inode节点（也就是每个文件）的fat_cache队列，可以快速的获得文件在磁盘上的位置。

上面的函数fat_cache_lookup从名字可以看出，它只是在cache中进行这样的查找过程中，这显然是不够的，因为cache是存在于内存中的，最初是不存在的，只能从FAT表中进行查找。

int fat_get_cluster(struct inode *inode, int cluster, int *fclus, int *dclus)

//该函数输入为inode以及要查找的文件的cluster， 要返回的是该cluster在磁盘上对应的dclus

{

       struct super_block *sb = inode->i_sb;

       const int limit = sb->s_maxbytes >> MSDOS_SB(sb)->cluster_bits;

       struct fat_entry fatent;

       struct fat_cache_id cid;

       int nr;

       BUG_ON(MSDOS_I(inode)->i_start == 0);

       *fclus = 0;

       *dclus = MSDOS_I(inode)->i_start;

       if (cluster == 0)

              return 0;

       //首先尽量从cache中进行查找，这样可以节省很多时间的。

       if (fat_cache_lookup(inode, cluster, &cid, fclus, dclus) < 0) {

              /*

               * dummy, always not contiguous

               * This is reinitialized by cache_init(), later.

               */

              cache_init(&cid, -1, -1);

       }

       //剩下的工作只能从FAT表中一个一个的查找了，确实是一个一个查找，从后面的代码(*fclus)++;也可以看出来。

       fatent_init(&fatent);

//这样可能会出现两种情况

//1. *fclus  =  cluster即需要查找的cluster已经被包含在cache中，那么皆大欢喜，查找结束

//2.*fclus < cluster, cache中包含不完全，其中* dclus中返回的是离cluster最近的cluster在磁盘上位置。然后根据该dclus从FAT表中查找

       while (*fclus < cluster) {

              /* prevent the infinite loop of cluster chain */

              if (*fclus > limit) {

                     fat_fs_error(sb, "%s: detected the cluster chain loop"

                                 " (i_pos %lld)", __func__,

                                 MSDOS_I(inode)->i_pos);

                     nr = -EIO;

                     goto out;

              }

              //根据dclus中FAT表查找出，下一个cluster在磁盘上的位置。

              nr = fat_ent_read(inode, &fatent, *dclus);

              if (nr < 0)

                     goto out;

              else if (nr == FAT_ENT_FREE) {

                     fat_fs_error(sb, "%s: invalid cluster chain"

                                 " (i_pos %lld)", __func__,

                                 MSDOS_I(inode)->i_pos);

                     nr = -EIO;

                     goto out;

              } else if (nr == FAT_ENT_EOF) {

                     fat_cache_add(inode, &cid);

                     goto out;

              }

              (*fclus)++;

              *dclus = nr;

              if (!cache_contiguous(&cid, *dclus))

                     cache_init(&cid, *fclus, *dclus);

       }

       nr = 0;

//查找结束，需要将相应的结果添加到cache中，便于下一次查找

       fat_cache_add(inode, &cid);

out:

       fatent_brelse(&fatent);

       //最终返回文件cluster对应的磁盘cluster号

       return nr;

}

说到fat_ent_read函数就不得不说struct fatent_operations结构体，因为这个函数用到了很多的函数指针，因为不同的FAT类型（FAT12，FAT16，FAT32）而不同。

struct fatent_operations {

       void (*ent_blocknr)(struct super_block *, int, int *, sector_t *);

  //对应的cluster所在的FAT表中的位置

       void (*ent_set_ptr)(struct fat_entry *, int);

       int (*ent_bread)(struct super_block *, struct fat_entry *,

                      int, sector_t);

       //用于读出一个block的内容，显然不管是数据读取还是

       //在获得文件的存储位置(从FAT表中读取)都是需要

       //该函数的

       int (*ent_get)(struct fat_entry *);

//用于获得FAT表中的下一个cluster所在的位置

       void (*ent_put)(struct fat_entry *, int);

       int (*ent_next)(struct fat_entry *);

};

int fat_ent_read(struct inode *inode, struct fat_entry *fatent, int entry)

{

       struct super_block *sb = inode->i_sb;

       struct msdos_sb_info *sbi = MSDOS_SB(inode->i_sb);

       struct fatent_operations *ops = sbi->fatent_ops;

       int err, offset;

       sector_t blocknr;

       if (entry < FAT_START_ENT || sbi->max_cluster <= entry) {

              fatent_brelse(fatent);

              fat_fs_error(sb, "invalid access to FAT (entry 0x%08x)", entry);

              return -EIO;

       }

       fatent_set_entry(fatent, entry);

//要获得一个文件cluster对应的磁盘cluster要分为三步：

1．算出文件cluster在FAT表中对应的位置，ent_blocknr完成

2．读出FAT表中的内容，ent_bread完成

3．获得对应的磁盘cluster，ent_get完成

       ops->ent_blocknr(sb, entry, &offset, &blocknr);

       if (!fat_ent_update_ptr(sb, fatent, offset, blocknr)) {

              fatent_brelse(fatent);

              err = ops->ent_bread(sb, fatent, offset, blocknr);

              if (err)

                     return err;

       }

       return ops->ent_get(fatent);

}