原文转自：http://blog.chinaunix.net/uid-7471615-id-83767.html
UNIX内核系列已经写了5篇了。按照“The Design of The UNIX Operation System”给出的系统原型来看，file sub-system基本上已经覆盖到了——当然要除去设备驱动相关的部分，如下图所示：
——注意，file sub-system与常说的ext2、ext3文件系统不是一个概念。ext2、ext3是指文件系统类型，file sub-system是指内核中管理各种类型文件系统、执行特定文件系统操作的一个子系统。如下图所示：
其实在Linux系统中，file subsystem还作为各文件系统的抽象——主要是抽象出操作，因此可以视为各文件系统类型的接口（熟悉java和C#的同学都知道）。扯远了……
到目前为止，已经描述了磁盘缓冲的管理、inode及磁盘块的一些操作，那么由谁来管理inode及磁盘块呢？UNIX实用了super block。今天就来说说它。
super block保存在磁盘上，通常，使用mkfs能够创建super block，这也是一个磁盘能够mount/unmount的一个重要对象。挂接上之后，super block将被加载到内存中，成为in-core的super block，内核会定期将其写到磁盘上，以保证其正确性。这就是为什么不unmount一个fs就断开其与系统的连接会导致数据丢失的原因。
super block对inode及磁盘块的管理主要的操作只有几个：分配/回收inode，分配/回收磁盘块。为了完成管理功能，super block类包含如下属性：
fs的大小
该fs空闲磁盘快数量
fs上可用空闲磁盘块链表
空闲磁盘块链表上下一个空闲块的索引
inode列表大小
空闲inode数
空闲inode表
空闲inode表中下一个空闲inode的索引
inode表和磁盘块表的锁
修改标志
Linux 0.99.15的inode类型与该原型差别较大，因此不列出其代码。
为新文件分配inode
fs中有一个线性的inode列表，inode的type字段为0时表示该inode空闲。当进程需要一个新的inode，理论上系统可以扫描整个inode列表来查找空闲的inode。但这样做开销太大，因为对于每个inode都要做一次读取操作（有可能是从磁盘上读）。因此，为了提高性能，fs的super block包含了一个数组来缓存系统中的空闲inode数。关于这点后面会讲到。先来看看ialloc()，看看如何分配新的inode。ialloc主要的思路很简单，就是先获取inode号，然后申请一个in-core的inode，最后将磁盘上的inode读取到in-core的inode中。伪代码如下：
INode ialloc(fs)
{
while (未完成)
{
if (super block被锁住)
{
sleep (super block解锁事件);
continue;
}
if (super block里的inode列表为空)
{
锁住super block;
获取空闲inode查找所记下的inode;
在磁盘上查找空闲inode，直到super block满，或者没有空闲inode（bread()和brelse()）;
解锁super block;
wakeup(super block解锁事件);
if (磁盘上没有找到空闲inode)
return 无inode;
设置下次空闲inode查找的起始inode;
}
/* 在super block的inode列表中有inode */
从super block的inode列表中获取inode号;
iget(); // 获取in-core的inode
if (inode未释放) // ！！！
{
将inode写到磁盘;
iput();
continue;
}
// inode空闲
初始化该inode;
写inode到磁盘; // 主要是将type字段置为非零表示被占用
减小fs的inode计数;
return inode;
}
}
现在让我们来稍微仔细地看看这个函数，前面已经说了最正常的情况。如果super block的空闲inode列表为空，内核将搜索磁盘，将尽量多的inode号置入super block中，内核一块一块的读取磁盘块，并记住最大的读取到的inode号，作为下次读取的起始。分配空闲的inode号如下图所示：
Super Block Free Inode List
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
｜ Ｆｒｅｅ ｉｎｏｄｅｓ ｜ ｜ ｜ Ｅｍｐｔｙ ｜
｜＜－－－－－－－－－－－＞｜８３｜４８｜＜－－－－－－－－－－－－－＞｜
｜ ｜ ｜ ｜ ｜
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
０ １８ １９ ２０
︿
｜ ｉｎｄｅｘ
当分配空闲inode号时，从空闲inode列表中获取，上图中的下一可用inode号的索引为20-1，因此取走 inode号48，并设置inode号的索引为19（下一可用inode索引为19-1），如下图：
Super Block Free Inode List
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
｜ Ｆｒｅｅ ｉｎｏｄｅｓ ｜ ｜ Ｅｍｐｔｙ ｜
｜＜－－－－－－－－－－－＞｜８３｜＜－－－－－－－－－－－－－－－－＞｜
｜ ｜ ｜ ｜
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
０ １８ １９ ２０
︿
｜ ｉｎｄｅｘ
当空闲inode列表为空时，根据存放在数组0号位置的inode号来搜索inode号，如下图所示：
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
｜４７０｜ Ｅｍｐｔｙ ｜
｜＜－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－＞｜
｜ ｜ ｜
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
０
︿
｜ ｉｎｄｅｘ
搜索到之后，填满该数组：
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
｜５３５｜ Ｆｒｅｅ ｉｎｏｄｅｓ ｜４７１｜
｜＜－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－＞｜
｜ ｜ ｜ ｜
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
０ ︿
｜ ｉｎｄｅｘ
释放inode
相对就要简单很多。伪代码如下所示：
void ifree (INode_No iNode_No)
{
++fs的可用inode计数;
if (super block被锁住)
return;
if (inode列表已满)
{
if (iNode_No < 记住的inode号)
记住的inode号 = iNode_No;
}
else
将iNode_No存到可用inode列表中;
return;
}
注意这里，一旦发现super block被锁住就返回，此时该inode号没有被放到super block中，但它能够在磁盘上找到。另外就是“if (iNode_No < 记住的inode号)”，这个处理是因为如果用给小的inode号去搜索磁盘，那么大的那个inode号肯定会被搜索到。
竞态条件
在ialloc()中仅仅在操作super block空闲inode列表时锁住了super block，而不是在整个操作中都锁住它，也许此处会带来竞态条件。分析一下：
当内核为进程A分配了最后一个空闲的inode号n，然后在读取该inode时睡眠。然后有个进程B试图从super block获取一个inode号时发现空闲inode列表为空，因此它将读取inode，并填满super block的空闲inode列表。此时由于进程A还在读取磁盘的inode，并未执行到更新磁盘上inode的type字段的代码，因此，B有可能将n作为free的inode读到列表中。此后进程B执行相应的操作，唤醒A。A进程完成分配操作。此时第三个进程C请求一个inode，并且恰好分配的是n号inode。当C要获取n的核内inode时发现inode被占用，因此再次循环（ialloc()伪码中“！！！”部分）。因此将更新后的inode立刻写回到磁盘就能够使得产生竞态条件的几率小些。
锁住super block的空闲列表防止了其他的竞态条件的发生。因为可能同时会有两个进程发现该列表是空的，其中第一个进程在读取磁盘inode号时睡眠，另一个进程获得执行机会，它也将从磁盘读取inode号，这要就导致了数据的不一致性。同样，当一个进程释放一个inode号时，可能有某个进程因为从磁盘读取inode号而睡眠，此时不加锁保护列表，将导致该释放的inode号覆盖掉读取到的inode号，造成数据的不一致性。
分配/释放磁盘块
当一个进程要向磁盘上写数据时，内核必须为其分配磁盘块。fs的super block中含有一个空闲磁盘块号码数组链表。mkfs程序完成的功能之一就是建立这样的链表，如下图所示：
Super block list of free disk block numbers
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
｜１０９｜１０６｜１０３｜１００｜．．．．．．．．．．．．．．．．．．．．．．．．．．｜
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
｜｜
＼／ 磁盘块NO：109
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
｜２１１｜２０８｜２０５｜２０２｜．．．．．．．．．．．．．．．．．．．．．．｜１１２｜
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
｜｜
＼／ 磁盘块NO：211
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
｜３１０｜３０７｜３０４｜３０１｜．．．．．．．．．．．．．．．．．．．．．．｜２１４｜
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
｜｜
＼／
在这个数组链表中每个磁盘块存放的都是空闲磁盘块号——除第一个之外。这个数组链表中每个磁盘块的第一个slot（array[0]）存放的是存放空闲磁盘块号的磁盘块的号码（有点绕口，我改了好几遍表述方法都不满意，只好这样了，结合上图来理解。^_^!）。
磁盘块号一旦被分配出去就不再可用，除非被释放了。如果申请磁盘块时只剩下slot 0，这样的话，内核会读取该磁盘块号指向的磁盘块数据，并存放到super block中，然后将slot 0中存放的磁盘块号分配给请求者，（并将该磁盘块清空？），因为磁盘块号的分配是从super block的空闲列表的最后一个元素开始的。
释放磁盘块的操作与之相反。将磁盘块号置入super block的空闲列表尾，然后将下一个空闲磁盘块号索引指向该slot。如果该空闲列表已满，内核就会将super block列表中的内容写到这个释放的磁盘块中，然后清空super block的列表，将这个释放的磁盘块号写到列表的slot 0中。
分配和释放磁盘块如下图所示：
super block list
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
｜１０９｜ ｜
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
｜｜
＼／ 磁盘块NO：109
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
｜２１１｜２０８｜２０５｜２０２｜．．．．．．．．．．．．．．．．．．．．．．｜１１２｜
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
初始状态
super block list
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
｜１０９｜９４９｜ ｜
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
｜｜
＼／ 磁盘块NO：109
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
｜２１１｜２０８｜２０５｜２０２｜．．．．．．．．．．．．．．．．．．．．．．｜１１２｜
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
释放949号磁盘块
super block list
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
｜１０９｜ ｜
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
｜｜
＼／ 磁盘块NO：109
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
｜２１１｜２０８｜２０５｜２０２｜．．．．．．．．．．．．．．．．．．．．．．｜１１２｜
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
分配949号磁盘块
super block list
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
｜２１１｜２０８｜２０５｜２０２｜．．．．．．．．．．．．．．．．．．．．．．｜１１２｜
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
｜｜
＼／ 磁盘块NO：211
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
｜３１０｜３０７｜３０４｜３０１｜．．．．．．．．．．．．．．．．．．．．．．｜２１４｜
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
分配109号磁盘块
super block list
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
｜３４４｜ ｜
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
｜｜
＼／ 磁盘块NO：344
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
｜２１１｜２０８｜２０５｜２０２｜．．．．．．．．．．．．．．．．．．．．．．｜１１２｜
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
｜｜
＼／ 磁盘块NO：211
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
｜３１０｜３０７｜３０４｜３０１｜．．．．．．．．．．．．．．．．．．．．．．｜２１４｜
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
释放344号磁盘块
简单看看磁盘块的分配和释放：
DiskBlockBuffer alloc (FileSystemNo fsNo)
{
while (super block被锁住)
sleep (super block解锁事件);
从super block空闲列表中移出一个块;
if (该块是最后一个块)
{
lock (super block);
读取刚刚分配的磁盘块bread();
将该磁盘块中的数据拷贝到super block的列表中;
brelse()释放该块;
unlock (super block);
唤醒所有等待super block解锁的进程;
}
}
为刚刚从super block中移出的磁盘块分配buffer（getblk()）;
清空buffer;
--可用磁盘块数;
将super block标记为已修改;
return 该buffer;
}
void free(BlkNo blkNo)
{
while (super block被锁住)
sleep (super block解锁事件);
lock (super block);
if (super block的列表未满)
{
将blkNo放到super block列表中;
++下一个可用块号的索引;
}
else
{
将super block列表的内容写到该磁盘块bwrite();
清空super block列表;
将blkNo写到super block列表的slot 0;
}
unlock (super block);
唤醒所有等待super block解锁的进程;
brelse()释放该buffer;
}
PS：本文其实在10月30日就应该写完，不过从那天一直忙到现在，好不容易有时间，总算完成了。
PS：周六去了趟霍营，从城铁霍营站坐公交车走，发现每个坐车的人态度都很好，挤挤碰碰了也就一笑了之，售票员态度也很好；不像城里，挤着碰着肯定要吵架，甚至要打架，售票员态度也很差劲。——唉：城里人的火气真大，还是乡下好啊……
参考：
The Design of The UNIX Operation System, by Maurice J. Bach
Linux Kernel Source Code v0.99.15, by Linus Torvalds
Linux Kernel Source Code v2.6.22, by Linus Torvalds and Linux community.
Understanding The Linux Kernel, 3rd edition, by Daniel P. Bovet, Marco Cesati
Copyleft (C) 2007 raof01. 本文可以用于除商业用途外的所有用途。若要用于商业用途，请与作者联系
