本文为MIT 6.S081课程第八章教材内容翻译加整理。
本课程前置知识主要涉及:
前面两节,我们介绍了xv6 文件系统教材上的相关小节说明,从本节开始,将整理课程所讲内容
文件系统突出的一些特性:
文件系统背后的机制:
为了理解文件系统必须提供什么能力,让我们再看一下一些与文件系统相关的基础系统调用。从这些系统调用接口,我们将可以推断出有关文件系统实现的一些细节,这些系统调用我们在之前的课程已经看过了。首先让我们来看一个简单的场景,假设我们创建了文件“x/y”,或者说在目录x中创建了文件y,同时我们需要提供一些标志位,现在我们还不太关心标志位所以我会忽略它。
fd = open("x/y",-);
上面的系统调用会创建文件,并返回文件描述符给调用者。调用者也就是用户应用程序可以对文件描述符调用write,有关write我们在之前已经看过很多次了,这里我们向文件写入“abc”三个字符。
write(fd,"abc",3);
从这两个调用已经可以看出一些信息了:
除此之外,还有一些我们之前没有看过的有趣的系统调用。例如XV6和所有的Unix文件系统都支持通过系统调用创建链接,给同一个文件指定多个名字。你可以通过调用link系统调用,为之前创建的文件“x/y”创建另一个名字“x/z”。
link("x/y","x/z");
所以文件系统内部需要以某种方式跟踪指向同一个文件的多个文件名。
我们还可能会在文件打开时,删除或者更新文件的命名空间:
unlink("x/y");
write(fd,"def",3);
所以,在文件系统内部,文件描述符必然与某个对象关联,而这个对象不依赖文件名。这样,即使文件名变化了,文件描述符仍然能够指向或者引用相同的文件对象。所以,实际上操作系统内部需要对于文件有内部的表现形式,并且这种表现形式与文件名无关。
文件系统的目的是实现上面描述的API,也即是典型的文件系统API。但是,这并不是唯一构建一个存储系统的方式。如果只是在磁盘上存储数据,你可以想出一个完全不同的API。
所以记住这一点很重要:还存在其他的方式能组织存储系统。我们这节课关注在文件系统,文件系统通常由操作系统提供,而数据库如果没有直接访问磁盘的权限的话,通常是在文件系统之上实现的(注,早期数据库通常直接基于磁盘构建自己的文件系统,因为早期操作系统自带的文件系统在性能上较差,且写入不是同步的,进而导致数据库的ACID不能保证。不过现代操作系统自带的文件系统已经足够好,所以现代的数据库大部分构建在操作系统自带的文件系统之上)
。
接下来我们看一下文件系统的结构。文件系统究竟维护了什么样的结构来实现前面介绍的API呢?
同时基于之前的讨论,我们也知道write和read都没有针对文件的offset参数,所以文件描述符必然自己悄悄维护了对于文件的offset。
文件系统中核心的数据结构就是inode和file descriptor。后者主要与用户进程进行交互。
尽管文件系统的API很相近并且内部实现可能非常不一样。但是很多文件系统都有类似的结构。因为文件系统还挺复杂的,所以最好按照分层的方式进行理解。可以这样看:
不同的文件系统组织方式和每一层可能都略有不同,有的时候分层也没有那么严格,即使在XV6中分层也不是很严格,但是从概念上来说这里的结构对于理解文件系统还是有帮助的。实际上所有的文件系统都有组件对应这里不同的分层,例如buffer cache,logging,inode和路径名。
接下来,我将简单的介绍最底层,也即是存储设备。实际中有非常非常多不同类型的存储设备,这些设备的区别在于性能,容量,数据保存的期限等。其中两种最常见,并且你们应该也挺熟悉的是SSD和HDD。这两类存储虽然有着不同的性能,但是都在合理的成本上提供了大量的存储空间。SSD通常是0.1到1毫秒的访问时间,而HDD通常是在10毫秒量级完成读写一个disk block。
这里有些术语有点让人困惑,它们是sectors和blocks。
有的时候,人们也将磁盘上的sector称为block。所以这里的术语也不是很精确。
这些存储设备连接到了电脑总线之上,总线也连接了CPU和内存。一个文件系统运行在CPU上,将内部的数据存储在内存,同时也会以读写block的形式存储在SSD或者HDD。这里的接口还是挺简单的,包括了read/write,然后以block编号作为参数。虽然我们这里描述的过于简单了,但是实际的接口大概就是这样。
在内部,SSD和HDD工作方式完全不一样,但是对于硬件的抽象屏蔽了这些差异。磁盘驱动通常会使用一些标准的协议,例如PCIE,与磁盘交互。从上向下看磁盘驱动的接口,大部分的磁盘看起来都一样,你可以提供block编号,在驱动中通过写设备的控制寄存器,然后设备就会完成相应的工作。这是从一个文件系统的角度的描述。尽管不同的存储设备有着非常不一样的属性,从驱动的角度来看,你可以以大致相同的方式对它们进行编程。
有关存储设备我们就说这么多:
对于read/write的接口,是不是提供了同步/异步的选项?
从文件系统的角度来看磁盘还是很直观的。因为对于磁盘就是读写block或者sector,我们可以将磁盘看作是一个巨大的block的数组,数组从0开始,一直增长到磁盘的最后。
而文件系统的工作就是将所有的数据结构以一种能够在重启之后重新构建文件系统的方式,存放在磁盘上。虽然有不同的方式,但是XV6使用了一种非常简单,但是还挺常见的布局结构。
通常来说:
通常来说,bitmap block,inode blocks和log blocks被统称为metadata block。它们虽然不存储实际的数据,但是它们存储了能帮助文件系统完成工作的元数据。
boot block是不是包含了操作系统启动的代码?
所以XV6是存储在虚拟磁盘上?
假设inode是64字节,如果你想要读取inode10,那么你应该按照下面的公式去对应的block读取inode。
所以inode0在block32,inode17会在block33。只要有inode的编号,我们总是可以找到inode在磁盘上存储的位置。
接下来我们看一下磁盘上存储的inode究竟是什么?首先我们前面已经看过了,这是一个64字节的数据结构。
以上基本就是XV6中inode的组成部分。
基于上面的内容,XV6中文件最大的长度是多少呢?
一个block大小1024字节,不要忘记了
是的,最大文件尺寸对应的是下面的公式:
可以算出这里就是268KB,这么点大小能存个什么呢?所以这是个很小的文件长度,实际的文件系统,文件最大的长度会大的多得多。那可以做一些什么来让文件系统支持大得多的文件呢?
可以扩展inode中indirect部分吗?
为什么每个block存储256个block编号?
在下一个File system lab,你们需要将inode中的一个block number变成双重indirect block number,这个双重indirect block number将会指向一个包含了256个indirect block number的block,其中的每一个indirect block number再指向一个包含了256个block number的block,这样文件就可以大得多。
接下来,我们想要实现read系统调用。假设我们需要读取文件的第8000个字节,那么你该读取哪个block呢?从inode的数据结构中该如何计算呢?
总结一下,inode中的信息完全足够用来实现read/write系统调用,至少可以找到哪个disk block需要用来执行read/write系统调用。
接下来我们讨论一下目录(directory)。文件系统的酷炫特性就是层次化的命名空间(hierarchical namespace),你可以在文件系统中保存对用户友好的文件名。大部分Unix文件系统有趣的点在于,一个目录本质上是一个文件加上一些文件系统能够理解的结构。在XV6中,这里的结构极其简单。每一个目录包含了directory entries,每一条entry都有固定的格式:
所以每个entry总共是16个字节:
对于实现路径名查找,这里的信息就足够了。假设我们要查找路径名“/y/x”,我们该怎么做呢?
对于路径名查找程序,接下来就是扫描root inode包含的所有block,以找到“y”。该怎么找到root inode所有对应的block呢?根据前一节的内容就是读取所有的direct block number和indirect block number。
结果可能是找到了,也可能是没有找到。如果找到了,那么目录y也会有一个inode编号,假设是251。
我们可以继续从inode 251查找,先读取inode 251的内容,之后再扫描inode所有对应的block,找到“x”并得到文件x对应的inode编号,最后将其作为路径名查找的结果返回。
有没有一些元数据表明当前的inode是目录而不是一个文件?
很明现,这里的结构不是很有效。为了找到一个目录名,你需要线性扫描。实际的文件系统会使用更复杂的数据结构来使得查找更快,当然这又是设计数据结构的问题,而不是设计操作系统的问题。你可以使用你喜欢的数据结构并提升性能。出于简单和更容易解释的目的,XV6使用了这里这种非常简单的数据结构。
接下来我们看一下实际中,XV6的文件系统是如何工作的,这部分内容对于下一个lab是有帮助的。
首先我会启动XV6,这里有件事情我想指出。启动XV6的过程中,调用了makefs指令,来创建一个文件系统。
所以makefs创建了一个全新的磁盘镜像,在这个磁盘镜像中包含了我们在指令中传入的一些文件。makefs为你创建了一个包含这些文件的新的文件系统。
XV6总是会打印文件系统的一些信息,所以从指令的下方可以看出有46个meta block,其中包括了:
之后是954个data block。所以这是一个袖珍级的文件系统,总共就包含了1000个block。在File system lab中,你们会去支持更大的文件系统。
我还稍微修改了一下XV6,使得任何时候写入block都会打印出block的编号。我们从console的输出可以看出,在XV6启动过程中,会有一些对于文件系统的调用,并写入了block 33,45,32。
接下来我们运行一些命令,来看一下特定的命令对哪些block做了写操作,并理解为什么要对这些block写入数据。我们通过echo “hi” > x,来创建一个文件x,并写入字符“hi”。我会将输出拷贝出来,并做分隔以方便我们更好的理解。
这里会有几个阶段:
如果你去看echo的代码实现,基本就是这3个阶段:
int
main(int argc, char *argv[])
{
int i;
for(i = 1; i < argc; i++){
write(1, argv[i], strlen(argv[i]));
if(i + 1 < argc){
write(1, " ", 1);
} else {
write(1, "\n", 1);
}
}
exit(0);
}
上面就是echo的代码,它先检查参数,并将参数写入到文件描述符1,在最后写入一个换行符。
让我们一个阶段一个阶段的看echo的执行过程,并理解对于文件系统发生了什么。相比看代码,这里直接看磁盘的分布图更方便:
你们觉得的write 33代表了什么?我们正在创建文件,所以我们期望文件系统干什么呢?
write 46是向第一个data block写数据,那么这个data block属于谁呢?
为什么它需要被写入数据呢?
接下来的write 32又是什么意思呢?block 32保存的仍然是inode,那么inode中的什么发生了变化使得需要将更新后的inode写入磁盘?是的,根目录的大小变了,因为我们刚刚添加了16个字节的entry来代表文件x的信息。
最后又有一次write 33,我在稍后会介绍这次写入的内容,这里我们再次更新了文件x的inode, 尽管我们又还没有写入任何数据。
以上就是第一阶段创建文件的过程。第二阶段是向文件写入“hi”。
首先是write 45,这是更新bitmap。文件系统首先会扫描bitmap来找到一个还没有使用的data block,未被使用的data block对应bit 0。找到之后,文件系统需要将该bit设置为1,表示对应的data block已经被使用了。所以更新block 45是为了更新bitmap。
接下来的两次write 595表明,文件系统挑选了data block 595。所以在文件x的inode中,第一个direct block number是595。因为写入了两个字符,所以write 595被调用了两次。
第二阶段最后的write 33是更新文件x对应的inode中的size字段,因为现在文件x中有了两个字符。
block 595看起来在磁盘中很靠后了,是因为前面的block已经被系统内核占用了吗?
第二阶段最后的write 33是否会将block 595与文件x的inode关联起来?
以上就是磁盘中文件系统的组织结构的核心,希望你们都能理解背后的原理。
接下来我们通过查看XV6中的代码,更进一步的了解文件系统。因为我们前面已经分配了inode,我们先来看一下这是如何发生的。sysfile.c中包含了所有与文件系统相关的函数,分配inode发生在sys_open函数中,这个函数会负责创建文件:
在sys_open函数中,会调用create函数:
create函数中首先会解析路径名并找到最后一个目录,之后会查看文件是否存在,如果存在的话会返回错误。之后就会调用ialloc(inode allocate),这个函数会为文件x分配inode。ialloc函数位于fs.c文件中。
以上就是ialloc函数,与XV6中的大部分函数一样,它很简单,但是又不是很高效。它会遍历所有可能的inode编号,找到inode所在的block,再看位于block中的inode数据的type字段。如果这是一个空闲的inode,那么将其type字段设置为文件,这会将inode标记为已被分配。函数中的log_write就是我们之前看到在console中有关写block的输出。这里的log_write是我们看到的整个输出的第一个。
以上就是第一次写磁盘涉及到的函数调用。这里有个有趣的问题,如果有多个进程同时调用create函数会发生什么?对于一个多核的计算机,进程可能并行运行,两个进程可能同时会调用到ialloc函数,然后进而调用bread(block read)函数。所以必须要有一些机制确保这两个进程不会互相影响。
让我们看一下位于bio.c的buffer cache代码。首先看一下bread函数:
bread函数首先会调用bget函数,bget会为我们从buffer cache中找到block的缓存。让我们看一下bget函数:
我们这里看一下block 33的cache是否存在,如果存在的话,将block对象的引用计数(refcnt)加1,之后再释放bcache锁,因为现在我们已经完成了对于cache的检查并找到了block cache。之后,代码会尝试获取block cache的锁。
所以,如果有多个进程同时调用bget的话,其中一个可以获取bcache的锁并扫描buffer cache。此时,其他进程是没有办法修改buffer cache的(注,因为buffer cache的锁被占住了)。之后,进程会查找block number是否在cache中,如果在的话将block cache的引用计数加1,表明当前进程对block cache有引用,之后再释放bcache的锁。如果有第二个进程也想扫描buffer cache,那么这时它就可以获取bcache的锁。假设第二个进程也要获取block 33的cache,那么它也会对相应的block cache的引用计数加1。最后这两个进程都会尝试对block 33的block cache调用acquiresleep函数。
acquiresleep是另一种锁,我们称之为sleep lock,本质上来说它获取block 33 cache的锁。其中一个进程获取锁之后函数返回。在ialloc函数中会扫描block 33中是否有一个空闲的inode。而另一个进程会在acquiresleep中等待第一个进程释放锁。
当一个block cache的refcnt不为0时,可以更新block cache吗?因为释放锁之后,可能会修改block cache。
如果buffer cache中有两份block 33的cache将会出现问题。假设一个进程要更新inode19,另一个进程要更新inode20。如果它们都在处理block 33的cache,并且cache有两份,那么第一个进程可能持有一份cache并先将inode19写回到磁盘中,而另一个进程持有另一份cache会将inode20写回到磁盘中,并将inode19的更新覆盖掉。所以一个block只能在buffer cache中出现一次。你们在完成File system lab时,必须要维持buffer cache的这个属性。
如果多个进程都在使用同一个block的cache,然后有一个进程在修改block,并通过强制向磁盘写数据修改了block的cache,那么其他进程会看到什么结果?
这个函数会对refcnt减1,并释放sleep lock。这意味着,如果有任何一个其他进程正在等待使用这个block cache,现在它就能获得这个block cache的sleep lock,并发现刚刚做的改动。
假设两个进程都需要分配一个新的inode,且新的inode都位于block 33。如果第一个进程分配到了inode18并完成了更新,那么它对于inode18的更新是可见的。另一个进程就只能分配到inode19,因为inode18已经被标记为已使用,任何之后的进程都可以看到第一个进程对它的更新。
这正是我们想看到的结果,如果一个进程创建了一个inode或者创建了一个文件,之后的进程执行读就应该看到那个文件。
block cache使用的是sleep lock。sleep lock区别于一个常规的spinlock。我们先看来一下sleep lock:
void
acquiresleep(struct sleeplock *lk)
{
acquire(&lk->lk);
while (lk->locked) {
sleep(lk, &lk->lk);
}
lk->locked = 1;
lk->pid = myproc()->pid;
release(&lk->lk);
}
首先是acquiresleep函数,它用来获取sleep lock。函数里首先获取了一个普通的spinlock,这是与sleep lock关联在一起的一个锁。之后,如果sleep lock被持有,那么就进入sleep状态,并将自己从当前CPU调度开。
既然sleep lock是基于spinlock实现的,为什么对于block cache,我们使用的是sleep lock而不是spinlock?
接下来让我们看一下brelease函数:
brelease函数中首先释放了sleep lock;之后获取了bcache的锁;之后减少了block cache的引用计数,表明一个进程不再对block cache感兴趣;最后如果引用计数为0,那么它会修改buffer cache的linked-list,将block cache移到linked-list的头部,这样表示这个block cache是最近使用过的block cache。这一点很重要,当我们在bget函数中不能找到block cache时,我们需要在buffer cache中腾出空间来存放新的block cache,这时会使用LRU(Least Recent Used)算法找出最不常使用的block cache,并撤回它(注,而将刚刚使用过的block cache放在linked-list的头部就可以直接更新linked-list的tail来完成LRU操作)。为什么这是一个好的策略呢?因为通常系统都遵循temporal locality策略,也就是说如果一个block cache最近被使用过,那么很有可能它很快会再被使用,所以最好不要撤回这样的block cache。
以上就是对于block cache代码的介绍。这里有几件事情需要注意:
sleeplock.c其他函数:
void
initsleeplock(struct sleeplock *lk, char *name)
{
initlock(&lk->lk, "sleep lock");
lk->name = name;
lk->locked = 0;
lk->pid = 0;
}
void
releasesleep(struct sleeplock *lk)
{
acquire(&lk->lk);
lk->locked = 0;
lk->pid = 0;
wakeup(lk);
release(&lk->lk);
}
int
holdingsleep(struct sleeplock *lk)
{
int r;
acquire(&lk->lk);
r = lk->locked && (lk->pid == myproc()->pid);
release(&lk->lk);
return r;
}
最后让我们来总结一下,并把剩下的内容留到下节课。
下节课我将会介绍crash safety,这是文件系统设计中非常棒的一部分。我们将会在crash safety讲两节课。下节课我们会看到基于log实现的crash safety机制,下下节课我们会看到Linux的ext3是如何实现的logging,这种方式要快得多。
我有个关于brelease函数的问题,看起来它先释放了block cache的锁,然后再对引用计数refcnt减一,为什么可以这样呢?