论坛徽章:: 0

电梯直达

1楼 [收藏(0)] [报告]

发表于 2007-12-16 16:05 |只看该作者 |倒序浏览

最近看了一些FAT和FATX的东西。在这里分享一下。
如果有不对的地方欢迎指出，互相学习。谢谢。
                                                                                       FAT & FATX filesystem
1. 概况：
在讲到具体文件系统之前先看看一个块设备在内核中受到那些模块的影响。这里借用一下《Understanding the Linux Kernel》3rd Ed中第14章中的一个图:
+-----------------------------------------------+
|                                                    VFS                                                                |
+-----------------------------------------------+
                        |                                                    |
                        v                                                    |
+----------------+                                  |
| disk caches                      |                                  |
+----------------+                                  |
                        |                                                    |
                        v                                                    v
+-----------------------------------------------+
|                                        MAPing       Layer                                                    |
+-----------------------------------------------+
                                                            |
                                                         v
+-----------------------------------------------+
|                                           Generic Block Layer                                           |
+-----------------------------------------------+
                                                            |
                                                         v
+-----------------------------------------------+
|                                           I/O scheduler layer                                           |
+-----------------------------------------------+ ·
                        |                                                             |
                     v                                                             v
         +--------------+          +--------------+
         |       Block device    |             |       Block device    |
         |          driver             |             |             driver          |
         +--------------+          +--------------+
                                 |                                                    |
                              v                                                    v
                        hard disk                                  hard disk
图1.overview
  VFS: VirtualFilesystem。大家也知道这个东西，VFS的主要思想就是为Linux创建一个通用的文件系统模型，用户不用管磁盘的具体的文件系统实现，无论磁盘中是NTFS的格式还是ext3的格式，他们看到的都是VFS，命令和操作都是VFS提供的标准接口，这样大大方便了用户和内>核本身，因为他们只要知道VFS就可以对任何Linux支持的文件系统操作。VFS模型是一个传统的UNIX文件系统模型。
Disk Caches: 内核把最近读过的磁盘数据保存在内存中，这样可以方便VFS更快地得到读过的数据，减少实际磁盘操作。
Mapping Layer: 这部分代码根据VFS发起的读写请求计算需要读写的那个block或者多个block在具体磁盘中的位置，因为磁盘使用不同的文件系统，它里面数据的组成结构也不同，所以不同文件系统计算方法一般都不同。
Generic Block Layer: 它也是一个统一的模型，不过它要掩盖的不是不同的文件系统，而是不同的硬件设备，它给我们一个一般性的块设备模型，同样也方便了用户和内核本身。
I/O scheduler layer: 当Generic Block Layer向下层提出读写请求时，内核不会让驱动去马上读些磁盘，因为这样实际的磁盘操作太多了，效率不高。内核会有一定的延迟去响应这些请求，收集多一些请求，通过不同的方法把它们的响应顺序重组，减少访问磁盘的时间。现在内核支持3种方法：CFQ,Deadline,Anticipatory。在编译内核时，内核选项Block layer-->IOschedulers的子选项让我们可以选择要那些方法和我们默认的方法，同时我们还可以通过修改/sys/block/sda/queue/scheduler来改变一个正在运行的系统方法(sda，根据你实际的硬盘会有不>同)。
Block Device Driver: 就是驱动了。
以上内容可以在《Understanding the Linux Kernel》3rd Ed 第14章有更多的解析。
而这里讲的FAT，FATX文件系统实际就是Mapping Layer。它让底层知道各种操作是对磁盘的那个地方进行的。
FAT文件系统就不多介绍了，FATX是XBOX上的文件系统，与传统的FAT文件系统十分类似。

2. FAT 和 FATX的磁盘结构
+-------------+-----------+----------+---------------------------+
| super block          | FAT table          | root dir          | regular data                                              |
+-------------+-----------+----------+---------------------------+
|----->start
图2.FAT disk structure
从图中可见FAT文件系统的主要由4部分组成：
1.super block(超级块):对整个文件系统的描述，包含mount需要的信息。
2.FAT表:FAT文件系统最特别的部分，用表格和静态链表的形式描述后面数据区数据的组成和使用情况。
  3.根目录:文件系统的根目录，FAT12,FAT16的根目录都固定在FAT表之后;而FAT32没这个限制，它的根目录可以在数据区的任意地方，所以可以说FAT32没有这个专门的根目录区域。FATX则无论是FATX16还是FATX32都会有这个区域。
4.数据区:具体文件和目录内容都在这个区域中储存。
下面更详细地讨论这些区域。

2.1 super block:
  FAT文件系统的super block占一个sector的大小，那么一个sector有是多大呢？这又在superblock中给出定义。一般的sector大小是512bytes。由于superblock中信息众多，这里只讨论其中一些比较重要的。更完整的描述可以见附件（微软的协议）。
sector是一组连续的byte，cluster是FAT，FATX文件系统中的一个数据单元，一般一个cluster有32个sector。
名字                   偏移量  大小    描述
                              (byte)  (bytes)
byte_per_sector 11    2    这两个byte指明了一个sector占多少个byte
sector_per_clus 13    1    标明一个cluster中有多少个sector
reserved_sector 14    2    指明super block这个区域占多少个sector
FAT_num                16    1    标明有多少个FAT表，一般值为2,互为备份
root_dir_sector 17    2    标明根目录区域占多少个sector，FAT32为0
total_sector_16 19    2    这是一个旧的域，记录这个块设备的总sector数
                                                   因为只有两个byte，最大值为65536。如果实际
                                                   情况超过了这个值。数据就放在新域total_sector_32
                                                   中
FAT_size_16          22    2    对于FAT12和FAT16这两个bytes标明一个FAT表
                                                   占多少个sector
total_sector_32 32    4    这是一个新的域，如果total_sector_16放不下
                                                   设备的sector数，就用这个域来表示。
后面从第36byte到SB的区域完毕，FAT12/16 和FAT32包含的内容不同。
其中FAT32还有一个域比较重要：
FAT_size_32          36    4    只对FAT32有效，标明这个FAT表占的sector数

  XBOX上FATX的SB就简单很多了，一共占4kb，而实际用到的只有18个byte：
名字                   偏移量  大小    描述
                           (byte)  (bytes)
FATX_string          0    4       "FATX" ASCII 字符串
volume_id             4    4       卷号
sector_per_clus 8    4       一个cluster占的sector数
FAT_num                12    2       标明有多少个FAT表
unknown                14    4
Unused                   18    4078
  FATX的SB之所以简单是因为有些参数被固定了，比如每个sector占512个byte，根目录区域占一个cluster等，还有些信息可以由别的地方>得到，比如FAT系统中有total_sector_16和total_sector_32来标明设备有多少个sector，但是这个信息可以由设备相关的内核结构得到，假如这个设备的super block结构是sb，那么这个设备的大小就是sb->s_bdev->bd_inode->i_size。s_bdev是这个块设备本身，bd_inode是这个设备的inode，而i_size又记录了这个文件的大小。
关于更多FAT和FATX系统的差别可以在下面这个地址找到：
http://www.xbox-linux.org/wiki/D ... FATX_and_MS-DOS_FAT

2.2 FAT表:
对于FAT文件系统，FAT表的起始地址为: 第reserved_sector个sector，紧跟在super block后面。
FAT表顾名思义就是一个表，每个项占的字节数由FAT的种类决定，FAT12是1.5个byte，FAT16是2个byte，FAT32是4个byte。而每一项就代表一个FAT表后面数据区的一个cluster。下面举个FAT16的例子：
+----------------+
  3 |    4                                  |-----------+
+----------------+                            |
  4 |    5                                  | <---------+
+----------------+                            |
  5 |  0xFFFF                            | <---------+
+----------------+
  6 |    0                                  |
+----------------+
  7 |    9                                  |-----------+
+----------------+                            |
  8 |  0xFFF7                            |                            |
+----------------+                            |
  9 |    10                                  | <---------+
+----------------+                            |
10|  0xFFFF                            | <---------+
+----------------+
  这段FAT表记录两个文件，第一个占了三个cluster分别为第3,4,5号cluster。另外一个文件也占了三个分别为第7,9,10号cluster。记住FAT表的下标就是对应的cluster号，文件的结尾在FAT表中用0xFFFF表示（因为这是一个FAT16的例子）。第八个cluster是一个坏的cluster，用0xFFF7来表示。表值是0的，像第6个项表示这个cluster还没有被使用。FATX文件系统的FAT表与FAT文件系统的FAT表一致。

2.3 根目录区域
  只有FAT16和FAT12有这个区域，FAT32没有，因为FAT32的根目录在数据区中的任何地方。这个区域的开始地址为:第reserved_sector+FAT_size_16*FAT_num个sector。一个目录也是一个文件，不过只是内容是一些规则的项，每个项占32bytes，标明这个目录的内容。具体每个目录>项的内容为：
名字                         偏移量  大小    描述
                                 (byte)  (bytes)
Name                            0    11       一个文件或子目录的名字
Attribution             11    1       一些文件属性，如隐藏，只读等
NT_reserved             12    1       Window NT专用。不知道有什么用。
create_time_ten    13    1       文件创建的时间戳
create_time             14    2       文件创建的时间
date_time                16    2       文件创建的日期
access_time             18    2       最近被访问的时间
high_word                20    2       这个目录项对应文件的第一个cluster的号的高16位
write_time                22    2       写文件的时间
write_date                24    2       写文件的日期
low_word                   26    2       这个目录项对应文件的第一个cluster的号的低16位
file_size                28    4       对应文件的大小
当文件名字的第一个byte等于0xE5或0x00表示这个项是空的，0x00更代表这个项后面的项都是可用的。
对于FATX，每个目录项占64个byte。它的内容和FAT16/32的目录项基本一样，就是多了一项文件名的长度(name_size)，而文件名字占42个byte，名字可以更长。详细目录项的域见http://www.xbox-linux.org/wiki/D ... FATX_and_MS-DOS_FAT
值得注意的是FATX目录项中可用标记值还是0xE5但是它却被记在name_size这个项中了，0xFF用来标明目录的结尾，与FAT中的0x00一样。

2.4 数据区
  数据区包含目录文件和真正的文件内容，它们由前面说的FAT表来组织。目录文件就是上面一节讲的内容。数据区域的开始地址为：第reserved_sector+FAT_size_16*FAT_num+root_dir_sector个sector，紧跟在根目录区域后面。

[ 本帖最后由 pennyliang 于 2007-12-16 16:11 编辑 ]

文库|博客

pennyliang

丰衣足食

论坛徽章:: 0

2楼 [报告]

发表于 2007-12-16 16:08 |只看该作者

3. 内核的数据结构和处理方法(只限于FAT文件系统，这里提到的代码为2.6.20.15版内核)
3.1 super block
  VFS 中有一个叫super_block的struct，它定义在include/linux/fs.h中。就像之前说的那样VFS是一个通用的文件系统模型，所以super_block具有一般性，它所包含的内容是所有文件系统的super_block一般都具有的内容，具体的内容这里就不讨论了，有兴趣的同学可用仔细研究一下。光有一般的信息当然不够，不同的文件系统总会有它独到之处，为了能反应这一点 super_block有一个成员变量void *s_fs_info，它指向>一个特定文件系统定义的superblock数据结构。对FAT文件系统来说，这个结构就是 structmsdos_sb_info它定义在include/linux/msdos_fs.h中，这个数据结构就基本包含了所有磁盘中FAT文件系统的super block的信息。
               (VFS)
  +-------------+
  | super_block          |
  |                                     | s_fs_info                         (FAT)
  |                            ---+---------->+---------------+
  +-------------+                            | msdos_sb_info          |
                                                                     |                                        |
                                                                     +---------------+

那么内核又是怎样组织所有的superblock的呢？所有的SB都串在一个双向链表中，而链表的头是一个叫super_blocks的变量，它定义在 fs/super.c中LIST_HEAD(super_blocks); 而在super_block中的s_list把所有的SB链接起来：

  +------------+          +-----------+          +-----------+          +-----------+
|super_blocks       |<--->|s_list                |<--->|s_list                |<--->|s_list                |
  +------------+          +-----------+          +-----------+          +-----------+
                                                |FAT                      |             |EXT2                   |          |EXT2                   |
                                                |super_block    |             |super_block       |          |super_block    |
                                                +-----------+          +-----------+          +-----------+
相同的文件系统在不同的设备上面有不同的super block。
mount是内核对磁盘super block的第一个操作。mount做了很多事情，而其中一个比较重要的动作就是读磁盘的super block，获得关于这个磁盘的信息。在mount的过程中函数vfs_kern_mount()会读取设备中的super block：

struct vfsmount *
vfs_kern_mount(struct file_system_type *type, int flags, const char *name, void *data)
{
...
error = type->get_sb(type, flags, name, data, mnt);
...
}

复制代码

因为不同的文件系统格式不同，会有不同的方法来读取super blcok，所以type（文件系统的种类）决定了这个方法。对应FAT文件系统get_sb实际上是msdos_get_sb()。

static int msdos_get_sb(struct file_system_type *fs_type,
int flags, const char *dev_name,
void *data, struct vfsmount *mnt)
{
return get_sb_bdev(fs_type, flags, dev_name, data, msdos_fill_super,
mnt);
}

复制代码

大部分文件系统都是通过get_sb_bdev()来获取superblcok内容的，不同的是调用它时的第五个参数msdos_fill_super一个函数指针，它才是真正读磁盘，解析superblock的地方。而msdos_fill_super实际上又是调用fat_fill_super来完成工作的，下面简要分析一下fat_fill_super所做的事：

int fat_fill_super(struct super_block *sb, void *data, int silent,
struct inode_operations *fs_dir_inode_ops, int isvfat)
{
...
//在进这个函数之前VFS的super_block已经分配好并挂在super_blocks链
//上。msdos_sb_info在这里分配。
sbi = kzalloc(sizeof(struct msdos_sb_info), GFP_KERNEL);
if (!sbi)
return -ENOMEM;
//把这个msdos_sb_info挂在VFS的super_block的s_fs_info上
sb->s_fs_info = sbi;
...
//解析和处理用户挂载一个磁盘时mount的参数
error = parse_options(data, isvfat, silent, &debug, &sbi->options);
...
//进行一次实际的读磁盘操作，目的是把super block读到内存中，sb_bread的第二个
//参数是指出要读的block在那个位置，super block当然是第0个了。
bh = sb_bread(sb, 0);
if (bh == NULL) {
printk(KERN_ERR "FAT: unable to read boot sector\n");
goto out_fail;
}
//bh->b_data就是从磁盘中读上来的内容。
//fat_boot_sector是一个定义在include/linux/msdos_fs.h中的结构体。
//它的内容结构和磁盘中的super block完全一样。所有可用直接赋值，这样变量b
//就有了这个设备的SB信息。
b = (struct fat_boot_sector *) bh->b_data;
...
//接着就是根据b内容给msdos_sb_info的成员赋值
sbi->sec_per_clus = b->sec_per_clus;//每个cluster占多少个sector
...
sbi->cluster_size = sb->s_blocksize * sbi->sec_per_clus;
sbi->cluster_bits = ffs(sbi->cluster_size) - 1;
sbi->fats = b->fats;//FAT表的个数
sbi->fat_bits = 0; /* Don't know yet */
sbi->fat_start = le16_to_cpu(b->reserved);//FAT表的开始位置
sbi->fat_length = le16_to_cpu(b->fat_length);//FAT表占的sector数
sbi->root_cluster = 0;
sbi->free_clusters = -1; /* Don't know yet */
sbi->prev_free = FAT_START_ENT;
...
//每个block占多少个目录文件
sbi->dir_per_block = sb->s_blocksize / sizeof(struct msdos_dir_entry);
sbi->dir_per_block_bits = ffs(sbi->dir_per_block) - 1;
//根目录区域的起始地址
sbi->dir_start = sbi->fat_start + sbi->fats * sbi->fat_length;
//每个目录文件有多少个目录项
sbi->dir_entries =
le16_to_cpu(get_unaligned((__le16 *)&b->dir_entries));
...
//给根目建一个inode
root_inode = new_inode(sb);
...
}

复制代码

这些super block的信息会一直留在内存中到设备被umount。当然super block的信息也会在用户使用过程中被修改

3.2 inode
与super block一样,inode也是由VFS的inode和FAT本身的inode组成:
      (FAT)
+------------------+
| msdos_inode_info             |
|                                                 |
|                                                 | vfs_inode (VFS)
|                                           --+---------->+-------+
+------------------+                            | inode       |
                                                                                    |                   |
                                                                                    +-------+

不过这次是FAT的inode数据结构包着VFS的inode数据结构。至于inode是怎样在内核中联系起来，由于与FAT关系不太大，这里就不讨论了，同学可以通过阅读关于VFS的资料来获取更多信息。(msdos_sb_info 定义在include/linux/msdos_fs.h中)
但是FAT文件系统不像EXT2/3文件系统，自己本身是没有inode这个概念的，为了与VFS这个通用的模型接合起来，内核是怎样做的呢？
先看一下目录文件的目录项在内核中用struct msdos_dir_entry(定义在 include/linux/msdos_fs.h中)来表示，它也是通过sb_bread函数>读取磁盘信息然后给msdos_sb_info赋值：

struct msdos_dir_entry {
__u8 name[8],ext[3]; /* name and extension */
__u8 attr; /* attribute bits */
__u8 lcase; /* Case for base and extension */
__u8 ctime_cs; /* Creation time, centiseconds (0-199) */
__le16 ctime; /* Creation time */
__le16 cdate; /* Creation date */
__le16 adate; /* Last access date */
__le16 starthi; /* High 16 bits of cluster in FAT32 */
__le16 time,date,start;/* time, date and first cluster */
__le32 size; /* file size (in bytes) */
};

复制代码

可见这个数据结构与磁盘中的目录项基本一致，在的到了一个目录项之后，内核调用fat_fill_inode来给FAT的inode赋值：

static int fat_fill_inode(struct inode *inode, struct msdos_dir_entry *de)
{
...
//在这个函数之前，VFS和FAT的inode数据结构都已经分配好了。
//一方面一些inode信息可用通过SB里的信息得到，如下：
MSDOS_I(inode)->i_pos = 0;
inode->i_uid = sbi->options.fs_uid;
inode->i_gid = sbi->options.fs_gid;
inode->i_version++;
...
//而其他的信息就通过这个文件的目录项来得到
//这是个目录
if ((de->attr & ATTR_DIR) && !IS_FREE(de->name)) {
...
//目录的属性
inode->i_mode = MSDOS_MKMODE(de->attr,
S_IRWXUGO & ~sbi->options.fs_dmask) | S_IFDIR;
...
//真正的数据在数据区的那个cluster中保存
MSDOS_I(inode)->i_start = le16_to_cpu(de->start);
if (sbi->fat_bits == 32)
MSDOS_I(inode)->i_start |= (le16_to_cpu(de->starthi) << 16);
...
//这是个文件
} else {
inode->i_mode = MSDOS_MKMODE(de->attr,
((sbi->options.showexec &&
!is_exec(de->ext))
? S_IRUGO|S_IWUGO : S_IRWXUGO)
& ~sbi->options.fs_fmask) | S_IFREG;
MSDOS_I(inode)->i_start = le16_to_cpu(de->start);
if (sbi->fat_bits == 32)
MSDOS_I(inode)->i_start |= (le16_to_cpu(de->starthi) << 16);
...
}
...
//关于时间的信息
if (sbi->options.isvfat) {
int secs = de->ctime_cs / 100;
int csecs = de->ctime_cs % 100;
inode->i_ctime.tv_sec =
date_dos2unix(le16_to_cpu(de->ctime),
le16_to_cpu(de->cdate)) + secs;
inode->i_ctime.tv_nsec = csecs * 10000000;
inode->i_atime.tv_sec =
date_dos2unix(0, le16_to_cpu(de->adate));
inode->i_atime.tv_nsec = 0;
} else
inode->i_ctime = inode->i_atime = inode->i_mtime;
...
}

复制代码

FAT文件系统中没有inode，而最能反应文件各种属性的就是SB和目录项，当然还有FAT表，内核就是通过它们来建立一个虚构的inode。
inode被修改了，当然要向磁盘写了，fat_write_inode（定义在fs/fat/inode.c中）完成了这个工作。从构建inode的过程可用想到，写inode其实主要也是写inode对应的文件在父目录中的目录项。这里就不多说了。

3.3 FAT表
大家也应该想到，VFS中不可能有FAT表，因为它并不是传统的UNIX文件系统应有的东西。但是从FAT表的结构可用看到，如果要访问一个文>件的某部分内容，举个例子，要访问一个文件的第3个cluster的内容，那么我们还是要从FAT表中文件对应的第一个cluster的表项找到第二个 >，再从第二个表项的内容得知第三个表项的下表从而判断出第三个cluster的具体位置。
+----------------+
  3|    4                                  |-----------+
+----------------+                            |
  4|    5                                  | <---------+
+----------------+                            |
  5|  0xFFFF                            | <---------+
+----------------+
  6|    0                                  |
+----------------+
内核并没有把整个FAT表读到内存中，为了避免频繁读磁盘，它通过一个链表cache_lru来加快查找速度。cache_lru是 msdos_inode_info的>一个成员变量，它记录最近访问过的FAT表表项，每个inode有一个这样的链表。每个链表元素为 fat_cache（定义在fs/fat/cache.c）：

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. */
};

复制代码

这样一个结构就记录了相对于文件开头第fcluster个cluster对应于磁盘中的位置为第dcluster个cluster。有了这个链表，如果要访问文件的第3个cluster，而我们又曾经访问过第二个cluster，那么我们就可用从第二个开始去读FAT表，从而知道第三个cluster的磁盘位置，同时这个新的cluster的信息又会被加到这个链表中。nr_contig这个变量是标明这个文件从fcluster这个cluster开始，后面有nr_contig个cluster在磁盘中是连续的，这种结构更有利于节省空间。当一个文件不再被使用，inode被删除时，这个链表也会被删除。