ucore⽂件系统详解
最近⼀直在mooc上学习清华⼤学的操作系统课程，也算是复习下基本概念和原理，为接下来的⼯作做准备。
每次深⼊底层源码都让我深感操作系统实现的琐碎，即使像ucore这样简单的kernel也让我烦躁不已，⽂件系统相⽐于中断⼦系统、调度⼦系统、进程管理⼦系统等等，要复杂很多，因此被称为⽂件系统⽽不是⽂件⼦系统。参看⽹络上的资料有时会增加我的困惑，很多⼈只是简单转载，很多细节描述的很模糊，实验环境也各不相同，最终很难深⼊理解⽂件系统的本质，参考源码我觉得有点像从三维世界进⼊到⼆维世界，⼀切变得清晰但是却需要消耗更多精⼒，我觉得这样做是值得的，因为如果不能深⼊⽽只是泛泛的理解，对于操作系统这样偏向于⼯程学的东西来说意义不⼤，本⽂的研究内容主要是根据清华⼤学陈渝副教授、向勇副教授在mooc上所讲，以及实验参考书的内容和我⾃⼰在系统上打的log验证过的，如果有读者发现错误还请批评指正。
本篇博客希望尽可能照顾到初学者，但是有些简单原理默认读者已经掌握，很多细节不会展开叙述，读者请⾃⾏Google或者参看Intel Development Manual，实验⽤的源码来⾃于清华⼤学教学操作系统，读者可在github上搜索ucore_os_lab。
附上ucore的实验参考书.
unix文件系统综述
最初实现⽂件系统是为了实现对磁盘数据的⾼效管理，使得⽤户可以⾼效、快速的读取磁盘上的数据内容。其实我个⼈觉得⽂件系统就是操作系统内核和外设之间的⼀套输⼊输出协议，我们所采⽤的算法和索引结点的建⽴⽅式都是为了根据实际应⽤情况所设计的⼀套⾼效的协议。在实现的过程中，我们还要将⽂件系统进⾏分层抽象，也就是实现我们的虚拟⽂件系统，虚拟⽂件系统有对上和对下两个⽅⾯，对上是为了向上层应⽤提供⼀套通⽤的访问接⼝，可以⽤相同的⽅式去访问磁盘上的⽂件（包括⽬录，后⾯会介绍）和外设；对下兼容不同的⽂件系统和外设。虚拟⽂件系统的层次和依赖关系如下图所⽰：
对照上⾯的层次我们再⼤致介绍⼀下⽂件系统的访问处理过程，加深对⽂件系统的总体理解。假如应⽤程序操作⽂件（打开/创建/删除/读写），⾸先需要通过⽂件系统的通⽤⽂件系统访问接⼝层给⽤户空间提供的访问接⼝进⼊⽂件系统内部，接着由⽂件系统抽象层把访问请求转发给某⼀具体⽂件系统（⽐如SFS⽂件系统），具体⽂件系统（Simple FS⽂件系统层）把应⽤程序的访问请求转化为对磁盘上的block的处理请求，并通过外设接⼝层交给磁盘驱动例程来完成具体的磁盘操作。结合⽤户态写⽂件函数write的整个执⾏过程，我们可以⽐较清楚地看出ucore⽂件系统架构的层次和依赖关系。
总体设计
ucore的⽂件系统模型源于Havard的OS161⽂件系统和Linux⽂件系统。但其实这两者都源于UNIX⽂件
系统设计。UNIX提出了四个⽂件系统抽象概念：⽂件（file）、⽬录项（descriptor entry，简写为dentry）、索引节点（inode）和安装点（mount point）。
⽂件：UNIX⽂件中的内容可理解为是⼀有序字节buffer，⽂件都有⼀个⽅便应⽤程序识别的⽂件名称（也称⽂件路径名）。典型的⽂件操作有读、写、创建和删除等。
⽬录项：⽬录项不是⽬录，⽽是⽬录的组成部分。在UNIX中⽬录被看作⼀种特定的⽂件，⽽⽬录项是⽂件路径中的⼀部分。如⼀个⽂件路径名是“/test/testfile”，则包含的⽬录项为：根⽬录“/”，⽬录“test”和⽂件“testfile”，这三个都是⽬录项。⼀般⽽⾔，⽬录项包含⽬录项的名字（⽂件名或⽬录名）和⽬录项的索引节点（见下⾯的描述）位置。
索引节点：UNIX将⽂件的相关元数据信息（如访问控制权限、⼤⼩、拥有者、创建时间、数据内容等等信息）存储在⼀个单独的数据结构中，该结构被称为索引节点。
安装点：在UNIX中，⽂件系统被安装在⼀个特定的⽂件路径位置，这个位置就是安装点。所有的已安装⽂件系统都作为根⽂件系统树中的叶⼦出现在系统中。
上述抽象概念形成了UNIX⽂件系统的逻辑数据结构，并需要通过⼀个具体⽂件系统的架构设计与实现把上述信息映射并储存到磁盘介质上。⼀个具体的⽂件系统需要在磁盘布局也实现上述抽象概念。⽐如⽂
件元数据信息存储在磁盘块中的索引节点上。当⽂件被载如内存时，内核需要使⽤磁盘块中的索引点来构造内存中的索引节点。
ucore模仿了UNIX的⽂件系统设计，ucore的⽂件系统架构主要由四部分组成：
通⽤⽂件系统访问接⼝层：该层提供了⼀个从⽤户空间到⽂件系统的标准访问接⼝。这⼀层访问接⼝让应⽤程序能够通过⼀个简单的接⼝获得ucore内核的⽂件系统服务。
⽂件系统抽象层：向上提供⼀个⼀致的接⼝给内核其他部分（⽂件系统相关的系统调⽤实现模块和其他内核功能模块）访问。向下提供⼀个同样的抽象函数指针列表和数据结构屏蔽不同⽂件系统的实现细节。
Simple FS⽂件系统层：⼀个基于索引⽅式的简单⽂件系统实例。向上通过各种具体函数实现以对应⽂件系统抽象层提出的抽象函数。
向下访问外设接⼝
外设接⼝层：向上提供device访问接⼝屏蔽不同硬件细节。向下实现访问各种具体设备驱动的接⼝，⽐如disk设备接⼝/串⼝设备接⼝/键盘设备接⼝等。
相关数据结构
在⽂件系统初始化时，主要完成三个函数：
void fs_init(void) {
vfs_init();
dev_init();
sfs_init();
}
它们的具体实现如下：
void vfs_init(void) {
sem_init(&bootfs_sem, 1);
vfs_devlist_init();
}
void dev_init(void) {
init_device(stdin);
init_device(stdout);
init_device(disk0);
}
void sfs_init(void) {
int ret;
if ((ret = sfs_mount("disk0")) != 0) {
panic("failed: sfs: sfs_mount: %e.\n", ret);
}
}
对于vfs_init，它只是完成了对vfs访问的信号量和devlist的初始化。dev_init则完成了对设备的初始化，这⾥的stdin代表输⼊设备，即键
盘，stdout代表输出设备，包括UART串⼝和显⽰器，disk0代表磁盘，我们以外设stdin作为例⼦进⾏讲述，stdout和stdin类似，disk0和stdin有⼀些不同，会在下⽂进⾏对⽐。⾸先，这⾥调⽤了init_device（stdin），它是⼀个宏，如下所⽰：
#define init_device(x) \
do { \
extern void dev_init_##x(void); \
dev_init_##x(); \
} while (0)
最后会调⽤到dev_init_stdin()
void dev_init_stdin(void) {
struct inode *node;
if ((node = dev_create_inode()) == NULL) {
panic("stdin: dev_create_node.\n");
}
cprintf("dev_init_stdin is called\n");
stdin_device_init(vop_info(node, device));
int ret;
if ((ret = vfs_add_dev("stdin", node, 0)) != 0) {
panic("stdin: vfs_add_dev: %e.\n", ret);
}
}
在dev_init_stdin中主要涉及两个数据结构，分别是struct inode和device，它们的数据结构如下所⽰：
struct inode {
union {
struct device __device_info;
struct sfs_inode __sfs_inode_info;
} in_info;
enum {
inode_type_device_info = 0x1234,
inode_type_sfs_inode_info,
} in_type;
int ref_count;
int open_count;
struct fs *in_fs;
const struct inode_ops *in_ops;
};
struct device {
size_t d_blocks;
size_t d_blocksize;
int (*d_open)(struct device *dev, uint32_t open_flags);
int (*d_close)(struct device *dev);
int (*d_io)(struct device *dev, struct iobuf *iob, bool write);
int (*d_ioctl)(struct device *dev, int op, void *data);
};
这⾥的关键函数是stdin_device_init（vop_info(node, device))，它完成设置inode为设备⽂件，初始化设备⽂件。其中vop_info是⼀个宏，实现如下：
#define vop_info(node, type) __vop_info(node, type)
#define __vop_info(node, type) \
({ \
struct inode *__node = (node); \
assert(__node != NULL && check_inode_type(__node, type)); \
&(__node->in_info.__##type##_info); \
})
它完成返回in_info这个联合体⾥device的地址，然后交个stdin_device_init处理，实现如下：
static void
stdin_device_init(struct device *dev) {
dev->d_blocks = 0;
dev->d_blocksize = 1;
dev->d_open = stdin_open;
dev->d_close = stdin_close;
dev->d_io = stdin_io;
dev->d_ioctl = stdin_ioctl;
p_rpos = p_wpos = 0;
wait_queue_init(wait_queue);
}
inode代表的是⼀个抽象意义的⽂件，根据in_info和in_type的值的不同，它既可以表⽰⽂件也可以表⽰
外设，open_count表⽰⼀个⽂件被进程打开的次数，当open_count=0时我们可以在kernel移除这个inode结点。这个inode是系统管理⽂件⽤的，因此⽤户层的程序不需要关⼼这个数据结构。device这个数据结构只有当inode表⽰设备时才会有⽤，其中d_blocks表⽰设备占据的数据块个数，d_blocksize表⽰数据占据的数据块⼤⼩，相应的四个操作也很简单，直接翻译过来就能理解，这⾥不再详述。需要注意的是，stdin相对于stdout多了⼀个输⼊缓冲区，需要额外的两个指针p_rpos,p_wpos分别记录当前读的位置和写的位置，当p_rpos < p_wpos时，说明当前有从键盘输⼊到缓冲区的数据但是还没有读到进程⾥，需要唤醒进程从缓冲区进⾏读操作，当p_rpos=p_wpos⽽进程发起读的系统调⽤时（如调⽤c库的scanf），这时需要阻塞进程，等待键盘输⼊时产⽣中断唤醒对应进程。
disk0的初始化过程其实和stdin和stdout⼏乎⼀样，只是在第三步sfs_init的过程中需要执⾏mount操作。sys_mount的调⽤过程如下：
int sfs_mount(const char *devname) {
return vfs_mount(devname, sfs_do_mount);
}
int
vfs_mount(const char *devname, int (*mountfunc)(struct device *dev, struct fs **fs_store)) {
int ret;
lock_vdev_list();
vfs_dev_t *vdev;
if ((ret = find_mount(devname, &vdev)) != 0) {
goto out;
}
if (vdev->fs != NULL) {
ret = -E_BUSY;
goto out;
}
assert(vdev->devname != NULL && vdev->mountable);
struct device *dev = vop_info(vdev->devnode, device);
if ((ret = mountfunc(dev, &(vdev->fs))) == 0) {
assert(vdev->fs != NULL);
cprintf("vfs: mount %s.\n", vdev->devname);
}
out:
unlock_vdev_list();
return ret;
}
其中这⾥⾯最重要的就是对回调函数sfs_do_mount的调⽤，sfs_do_mount主要完成对struct sfs数据结
构的初始化，这⾥的sfs是simple file system的缩写，本⽂讨论的ucore⽬前只⽀持这⼀种⽂件系统，该数据结构的实现如下：
struct sfs_fs {
struct sfs_super super; /* on-disk superblock */
struct device *dev; /* device mounted on */
struct bitmap *freemap; /* blocks in use are mared 0 */
bool super_dirty; /* true if super/freemap modified */
void *sfs_buffer; /* buffer for non-block aligned io */
semaphore_t fs_sem; /* semaphore for fs */
semaphore_t io_sem; /* semaphore for io */
semaphore_t mutex_sem; /* semaphore for link/unlink and rename */
list_entry_t inode_list; /* inode linked-list */
list_entry_t *hash_list; /* inode hash linked-list */
};
其中最主要的是从磁盘中读取该⽂件系统的superblock（上⽂提到过，每个⽂件系统⼀个，记录该⽂件系统的信息），⾄此整个初始化过程讨论完毕。
Simple FS⽂件系统
ucore内核把所有⽂件都看作是字节流，任何内部逻辑结构都是专⽤的，由应⽤程序负责解释。ucore区分⽂件的物理结构，⽬前ucore⽀持如下⼏种类型的⽂件：
常规⽂件：⽂件中包括的内容信息是由应⽤程序输⼊。SFS⽂件系统在普通⽂件上不强加任何内部结构，把其⽂件内容信息看作为字节。
⽬录：包含⼀系列的entry，每个entry包含⽂件名和指向与之相关联的索引节点（index node）的指针。⽬录是按层次结构组织的。
链接⽂件：实际上⼀个链接⽂件是⼀个已经存在的⽂件的另⼀个可选择的⽂件名。
设备⽂件：不包含数据，但是提供了⼀个映射物理设备（如串⼝、键盘等）到⼀个⽂件名的机制。可通过设备⽂件访问外围设备。
管道：管道是进程间通讯的⼀个基础设施。管道缓存了其输⼊端所接受的数据，以便在管道输出端读的进程能⼀个先进先出的⽅式来接受数据。
在github上的ucore教学操作系统中，主要关注的是常规⽂件、⽬录和链接中的hardlink的设计实现。SFS⽂件系统中⽬录和常规⽂件具有共同的属性，⽽这些属性保存在索引节点中。SFS通过索引节点来管理⽬录和常规⽂件，索引节点包含操作系统所需要的关于某个⽂件的关键信息，⽐如⽂件的属性、访问许可权以及其他控制信息都保存在索引节点中。可以有多个⽂件名指向⼀个索引节点。
⽂件系统的布局
⽂件系统通常保存在磁盘上，disk0代表磁盘，⽤来存放⼀个SFS⽂件系统。磁盘的使⽤是以扇区为单位的，但是在⽂件系统中，⼀般按数据块来使⽤磁盘，在sfs中，我们以4k（8个sector，和page⼤⼩相等）为⼀个数据块。sfs⽂件系统的布局如下图所⽰。
第0个块（4K）是超级块（superblock），它包含了关于⽂件系统的所有关键参数，当计算机被启动或⽂件系统被⾸次接触时，超级块的内容就会被装⼊内存。其定义如下：
struct sfs_super {
uint32_t magic; /* magic number, should be SFS_MAGIC */
uint32_t blocks; /* # of blocks in fs */
uint32_t unused_blocks; /* # of unused blocks in fs */
char info[SFS_MAX_INFO_LEN + 1]; /* infomation for sfs */
};
其中成员变量magic代表⼀个魔数，其值为0x2f8dbe2a，内核⽤它来检查磁盘镜像是否合法，blocks记录了sfs中block的数
量，unused_block记录了sfs中还没有被使⽤的block数量，其中关于物理磁盘的管理与虚拟内存的管理⼗分类似，每次使⽤物理磁盘也会有⼀个类似于物理内存管理的分配算法。最后info是记录⼀个字符串"simple file system"。
第1个块放了⼀个root-dir的inode，⽤来记录根⽬录的相关信息。有关inode还将在后续部分介绍。这⾥
只要理解root-dir是SFS⽂件系统的根结点，通过这个root-dir的inode信息就可以定位并查到根⽬录下的所有⽂件信息。
从第2个块开始，根据SFS中所有块的数量，⽤1个bit来表⽰⼀个块的占⽤和未被占⽤的情况。这个区域称为SFS的freemap区域，这将占⽤若⼲个块空间。为了更好地记录和管理freemap区域，专门提供了两个⽂件kern/fs/sfs/bitmap.[ch]来完成根据⼀个块号查或设置对应的bit位的值。
最后在剩余的磁盘空间中，存放了所有其他⽬录和⽂件的inode信息和内容数据信息。需要注意的是虽然inode的⼤⼩⼩于⼀个块的⼤⼩（4096B），但为了实现简单，每个 inode 都占⽤⼀个完整的 block。
在sfs_fs.c⽂件中的sfs_do_mount函数中，完成了加载位于硬盘上的SFS⽂件系统的超级块superblock和freemap的⼯作。这样，在内存中就有了SFS⽂件系统的全局信息。
索引节点
磁盘索引节点
之前在初始化过程中讨论过vfs对应的索引节点，其实索引节点主要是指存在磁盘中的索引节点，当把磁盘中的索引节点load到内存中之后，在内存中也会存在⼀个索引节点，下⾯先讨论磁盘中的索引节点，数据结构如下所⽰。
struct sfs_disk_inode {
uint32_t size; 如果inode表⽰常规⽂件，则size是⽂件⼤⼩
uint16_t type; inode的⽂件类型
uint16_t nlinks; 此inode的硬链接数
uint32_t blocks; 此inode的数据块数的个数
uint32_t direct[SFS_NDIRECT]; 此inode的直接数据块索引值（有SFS_NDIRECT个）
uint32_t indirect; 此inode的⼀级间接数据块索引值
};
对于磁盘索引节点，这⾥只解释最后的两个成员变量，direct指的是这个inode的直接索引块的索引值，它的⼤⼩是12，所以最多能够通过direct的⽅式⽀持最⼤12*4096B的⽂件⼤⼩。之所以这样设计是因为我们实际的⽂件系统中，绝⼤多数⽂件都是⼩⽂件，因此直接索引的⽅式能够提⾼⼩⽂件的存取速度，⽽且通过间接索引的⽅式还能⽀持⼤⽂件。当使⽤⼀级间接数据块索引时，ucore ⽀持最⼤的⽂件⼤⼩为 12 * 4k + 1024 * 4k = 48k + 4m。
对于普通⽂件，索引值指向的 block 中保存的是⽂件中的数据。⽽对于⽬录，索引值指向的数据保存的是⽬录下所有的⽂件名以及对应的索引节点所在的索引块（磁盘块）所形成的数组。数据结构如下：
/* file entry (on disk) */
struct sfs_disk_entry {
uint32_t ino; 索引节点所占数据块索引值
char name[SFS_MAX_FNAME_LEN + 1]; ⽂件名
};
操作系统中，每个⽂件系统下的 inode 都应该分配唯⼀的 inode 编号。SFS 下，为了实现的简便（偷懒），每个 inode 直接⽤他所在的磁盘block 的编号作为 inode 编号。⽐如，root block 的 inode 编号为 1；每个 sfs_disk_entry 数据结构中，name 表⽰⽬录下⽂件或⽂件夹的名称，ino 表⽰磁盘 block 编号，通过读取该 block 的数据，能够得到相应的⽂件或⽂件夹的 inode。ino 为0时，表⽰⼀个⽆效的 entry。（因为 block 0 ⽤来保存 super block，它不可能被其他任何⽂件或⽬录使⽤，所以这么设计也是合理的）。
此外，和 inode 相似，每个 sfs_dirent_entry 也占⽤⼀个 block。
内存索引节点
内存索引节点的数据结构如下图所⽰。
/* inode for sfs */
struct sfs_inode {
struct sfs_disk_inode *din; /* on-disk inode */
uint32_t ino; /* inode number */
uint32_t flags; /* inode flags */
bool dirty; /* true if inode modified */
int reclaim_count; /* kill inode if it hits zero */
semaphore_t sem; /* semaphore for din */
list_entry_t inode_link; /* entry for linked-list in sfs_fs */
list_entry_t hash_link; /* entry for hash linked-list in sfs_fs */
};
内存inode只有在打开⼀个⽂件后才会创建，如果关机则相关信息都会消失。可以看到，内存inode包含了硬盘inode的信息，⽽且还增加了其他⼀些信息，这是为了实现判断是否改写（dirty），互斥操作（sem），回收（reclaim——count）和快速定位（hash_link）等作⽤。为了便于实现上⾯提到的多级数据访问以及⽬录中entry的操作，对inode SFS实现了⼀些辅助函数：
1. sfs_bmap_load_nolock：将对应 sfs_inode 的第 index 个索引指向的 block 的索引值取出存到相应的指针指向的单元（ino_store）。
该函数只接受 index <= inode-<blocks 的参数。当 index == inode-<blocks 时，该函数理解为需要为 inode 增长⼀个 block。并标记inode 为 dirty（所有对 inode 数据的修改都要做这样的操作，这样，当 inode 不再使⽤的时候，sfs 能够保证 inode 数据能够被写回到磁盘）。sfs_bmap_load_nolock 调⽤的 sfs_bmap_get_nolock 来完成相应的操作。（sfs_bmap_get_nolock 只由
sfs_bmap_load_nolock 调⽤）
2. sfs_bmap_truncate_nolock：将多级数据索引表的最后⼀个 entry 释放掉。他可以认为是 sfs_bmap_l
oad_nolock 中，index == inode-
>blocks 的逆操作。当⼀个⽂件或⽬录被删除时，sfs 会循环调⽤该函数直到 inode->blocks 减为 0，释放所有的数据页。函数通过sfs_bmap_free_nolock 来实现，他应该是 sfs_bmap_get_nolock 的逆操作。和 sfs_bmap_get_nolock ⼀样，调⽤
sfs_bmap_free_nolock 也要格外⼩⼼。
3. sfs_dirent_read_nolock：将⽬录的第 slot 个 entry 读取到指定的内存空间。他通过上⾯提到的函数来完成。
4. sfs_dirent_write_nolock：⽤指定的 entry 来替换某个⽬录下的第 slot 个entry。他通过调⽤ sfs_bmap_load_nolock保证，当第 slot 个
entry 不存在时（slot == inode->blocks），SFS 会分配⼀个新的entry，即在⽬录尾添加了⼀个 entry。
5. sfs_dirent_search_nolock：是常⽤的查函数。他在⽬录下查 name，并且返回相应的搜索结果（⽂件或⽂件夹）的 inode 的编号
（也是磁盘编号），和相应的 entry 在该⽬录的 index 编号以及⽬录下的数据页是否有空闲的 entry。（
SFS 实现⾥⽂件的数据页是连续的，不存在任何空洞；⽽对于⽬录，数据页不是连续的，当某个 entry 删除的时候，SFS 通过设置 entry->ino 为0将该 entry 所在的block 标记为 free，在需要添加新 entry 的时候，SFS 优先使⽤这些 free 的 entry，其次才会去在数据页尾追加新的 entry。
这部分⽐较复杂，关于这部分以后会单独开⼀篇博客来叙述。
⽂件系统抽象层-VFS
⽂件系统抽象层是把不同⽂件系统的对外共性借⼝提取出来，形成⼀个数据结构（包含多个函数指针），这样，通⽤⽂件系统访问接⼝层只需要访问⽂件系统抽象层，⽽不需要关⼼具体⽂件系统的实现细节和接⼝。
file&dir接⼝
file&dir接⼝层定义了进程在内核中直接访问的⽂件相关信息，这定义在file数据结构中，具体描述如下：
struct file {
enum {
FD_NONE, FD_INIT, FD_OPENED, FD_CLOSED,
} status; //访问⽂件的执⾏状态
bool readable; //⽂件是否可读
bool writable; //⽂件是否可写
int fd; //⽂件在filemap中的索引值
off_t pos; //访问⽂件的当前位置
struct inode *node; //该⽂件对应的内存inode指针
atomic_t open_count; //打开此⽂件的次数
};
⽽在kern/process/proc.h中的proc_struct结构中描述了进程访问⽂件的数据接⼝fs_struct，其数据结构定义如下：
struct fs_struct {
struct inode *pwd; //进程当前执⾏⽬录的内存inode指针
struct file *filemap; //进程打开⽂件的数组
atomic_t fs_count; //访问此⽂件的线程个数？？
semaphore_t fs_sem; //确保对进程控制块中fs_struct的互斥访问
};
当创建⼀个进程后，该进程的fs_struct将会被初始化或复制⽗进程的fs_struct。当⽤户进程打开⼀个⽂件时，将从filemap数组中取得⼀个空闲file项，然后会把此file的成员变量node指针指向⼀个代表此⽂件的inode的起始地址。
inode接⼝
index node是位于内存的索引节点，它是VFS结构中的重要数据结构，因为它实际负责把不同⽂件系统的特定索引节点信息（甚⾄不能算是⼀个索引节点）统⼀封装起来，避免了进程直接访问具体⽂件系统。它的数据结构在上⽂已经介绍过，在inode中，有⼀个成员变量
in_ops，这是对此inode的操作函数指针列表，其数据结构定义如下：
版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。
发表评论