操作系统(Linux Kernel 0.11Linux Kernel 0.12)解读整理——内核初始化(main init)之缓冲区的管理
前言
当一个程序需要读取硬盘上的一个逻辑块时，就会向缓冲区管理程序提出申请。而请求读写的程序进程则进入睡眠等待状态。缓冲区管理程序首先在缓冲区中寻找以前是否已经读取过这块数据。如果缓冲区中已经有了，就直接将对应的缓冲区块头指针返回给程序并唤醒等待的进程。若缓冲区中还不存在所要求的数据块，则缓冲管理程序就会调用低级块读写函数 ll_rw_block()，向相应的块设备驱动程序发出一个读数据块的操作请求。该函数会为此创建一个请求结构项，并插入请求队列中。为了提高读写磁盘的效率，减小磁头移动的距离，内核代码在把请求项插入请求队列时，会使用电梯算法将请求项插入到磁头移动距离最小的请求队列位置处。
若此时对应块设备的请求项队列为空，则表明此刻该块设备不忙。于是内核就会立刻向该块设备的控制器发出读数据命令。当块设备的控制器将数据读入到指定的缓冲块后，就会发出中断请求信号，并调用相应的读命令后处理函数，处理继续读扇区操作或者结束本次请求项的过程。例如对相应块设备进行关闭操作和设置该缓冲块数据已经更新标志，最后唤醒等待该块数据的进程。
(总而言之，缓冲区是程序操作块设备的数据的载体)
缓冲区也属于内存的一部分，并且作为后续与块设备打交道的重要结构(主内存与块设备的桥梁)，而且像缓冲的概念在其他地方也是有使用的，如在最近访问的页目录和页表会被存放在处理器的页高速缓冲器件中。
于buffer.c程序中用于对高速缓冲区(池)进行操作和管理。高速缓冲区位于内核代码块和主内存区之间。高速缓冲区在块设备与内核其他程序之间起着一个桥梁作用。除了块设备驱动程序以外，内核程序如果需要访问块设备中的数据，就都需要经过高速缓冲区来间接地操作。
如之前的文章所总结，任何程序的运行，都是在对所设计的数据结构的灵活运用，接下来简单地介绍下缓冲区管理的两种关键数据结构。
两组重要结构
作为需要传入参数的初始化方法 缓冲区初始化 buffer_init ，其中的 buffer_memory_end 是内存划分时的边界设置
void main(void) {
...
buffer_init(buffer_memory_end);
...
}假设内存只有 8M，核心的代码如下：
extern int end;
struct buffer_head * start_buffer = (struct buffer_head *) &end;
void buffer_init(long buffer_end) {
struct buffer_head * h = start_buffer;
void * b = (void *) buffer_end;
while ( (b -= 1024) >= ((void *) (h+1)) ) {
h->b_dev = 0;
h->b_dirt = 0;
h->b_count = 0;
h->b_lock = 0;
h->b_uptodate = 0;
h->b_wait = NULL;
h->b_next = NULL;
h->b_prev = NULL;
h->b_data = (char *) b;
h->b_prev_free = h-1;
h->b_next_free = h+1;
h++;
}
h--;
free_list = start_buffer;
free_list->b_prev_free = h;
h->b_next_free = free_list;
for (int i=0;i<307;i++)
hash_table[i]=NULL;
}其中外部变量 end，而缓冲区开始位置 start_buffer 就等于这个变量的内存地址。
这个外部变量 end 并不是操作系统代码写就的，而是由链接器 ld 在链接整个程序时设置的一个外部变量，帮助计算好了整个内核代码的末尾地址。内存分布图可以精确为如下：
像主内存和缓冲区的分界线，就直接代码里写死了，就是上图中的 2M。可是内核程序占多大内存在写的时候完全不知道，就算知道了如果改动一点代码也会变化，所以就由程序编译链接时由链接器程序帮我们把这个内核代码末端的地址计算出来，作为一个外部变量 end 拿来即用。
两个重要结构变量，一个是 buffer_head 结构的 h，代表缓冲头，其指针值是 start_buffer，就是图中的内核代码末端地址 end，也就是缓冲区开头。 一个是 b，代表缓冲块，指针值是 buffer_end，也就是图中的 2M，就是缓冲区结尾。 缓冲区结尾的 b 每次循环 -1024，也就是一页的值，缓冲区结尾的 h 每次循环 +1（一个 buffer_head 大小的内存），直到碰一块为止。
所有缓冲块的 buffer_head 被链接成一个双向链表结构,称为空闲链表。图中 free_list 指针是该链表的头指针，指向空闲块链表中第一个“最为空闲的”缓冲块，即近期最少使用的缓冲块。而该缓冲块的反向指针b_prev_free 则指向缓冲块链表中最后一个缓冲块，即最近刚使用的缓冲块。缓冲块的缓冲头数据结构如下
(一个从上往下，一个从下往上。)
这个过程中，h 被附上了属性值，其中比较关键的是这个 buffer 所表示的数据部分 b_data，也就是指向了上面的缓冲块 b。这个 buffer 的前后空闲 buffer 的指针 b_prev_free 和 b_next_free。当缓冲头 h 的所有 next 和 prev 指针都指向彼此时，就构成了一个双向链表
free_list = start_buffer;
free_list->b_prev_free = h;
h->b_next_free = free_list;free_list 指向了缓冲头双向链表的第一个结构，然后就可以顺着这个结构，从双向链表中遍历到任何一个缓冲头结构了，而通过缓冲头又可以找到这个缓冲头对应的缓冲块。 (缓冲头就是具体缓冲块的管理结构，而 free_list 开头的双向链表又是缓冲头的管理结构，整个管理体系就这样建立起来了。)从 free_list 开始遍历，就可以找到这里的所有内容了。但是，还有一步，能帮助更高效地管理。
for (i=0;i<307;i++)
hash_table[i]=NULL;总而言之，一个 307 大小的 hash_table 数组，这个代码在 buffer.c 中，而 buffer.c 是在 fs 包下的，也即文件系统包下的。并且它后续是为文件系统而服务，具体是内核程序如果需要访问块设备中的数据，就都需要经过缓冲区来间接地操作。 (也即，读取块设备的数据（硬盘中的数据），需要先读到缓冲区中，如果缓冲区已有了，就不用从块设备读取了，直接取走。)
在双向链表从头遍历即可知道缓冲区是否已经有了要读取的块设备中的数据，但是效率太低。所以需要一个 hashmap 的结构方便快速查找(结合链表和数组的优点形成的数据结构)，即 hash_table 这个数组的作用。 现在只是初始化这个 hash_table。之后当要读取某个块设备上的数据时，首先要搜索相应的缓冲块。
如下函数：
#define _hashfn(dev,block) (((unsigned)(dev^block))%307)
#define hash(dev,block) hash_table[_hashfn(dev,block)]
// 搜索合适的缓冲块
struct buffer_head * getblk(int dev,int block) {
...
struct buffer_head bh = get_hash_table(dev,block)；
...
}
struct buffer_head * get_hash_table(int dev, int block) {
...
find_buffer(dev,block);
...
}
static struct buffer_head * find_buffer(int dev, int block) {
...
hash(dev,block);
...
}(即通过 (设备号^逻辑块号) % 307 找到在 hash_table 里的索引下标)
与C++中的 哈希表(散列表) 类似，如果哈希冲突就形成链表。
其中的缓冲块搜索函数 getblk()，
获取适合的空闲缓冲块。该函数会首先调用get_hash_table()函数，在 hash 表队列中搜索指定设备号和逻辑块号的缓冲块是否已经存在。如果指定的缓冲块存在就立刻返回对应缓冲头结构的指针;如果不存在，则从空闲链表头开始，对空闲链表进行扫描，寻找一个空闲缓冲块。在寻找过程中还要对找到的空闲缓冲块作比较，根据赋予修改标志和锁定标志组合而成的权值，比较哪个空闲块最适合。若找到的空闲块既没有被修改也没有被锁定，就不用继续寻找了。
若此时没有找到空闲块，则让当前进程进入睡眠状态，待继续执行时再次寻找。若该空闲块被锁定，则进程也需进入睡眠，等待驱动程序对其解锁。若在睡眠等待的过程中，该缓冲块又被其他进程占用，那么只要再重头开始搜索缓冲块。否则判断该缓冲块是否已被修改过，若是，则将该块写盘，并等待该块解锁。此时如果该缓冲块又被别的进程占用,那么又一次全功尽弃,只好再重头开始执行 getblk()
此时有可能出现另外一个意外情况，也就是在我们睡眠时，可能其他进程已经将我们所需要的缓冲块加进了 hash 队列中，因此这里需要最后一次搜索一下 hash 队列。如果真的在 hash 队列中找到了我们所需要的缓冲块，那么我们又得对找到的缓冲块进行以上判断处理，因此，又一次地我们需要重头开始执行 getblk()
最后，才算找到了一块没有被进程使用、没有被上锁，而且是干净(修改标志未置位)的空闲缓冲块。于是我们就将该块的引用次数置 1，并复位其他几个标志，然后从空闲表中移出该块的缓冲头结构。在设置了该缓冲块所属的设备号和相应的逻辑号后，再将其插入 hash 表对应表项首部并链接到空闲队列的末尾处。由于搜索空闲块是从空闲队列头开始的，因此这种先从空闲队列中移出并使用最近不常用的缓冲块，然后再重新插入到空闲队列尾部的操作也就实现了最近最少使用LRU 算法。最终，返回该缓冲块头的指针。
哈希表 + 双向链表，这可以实现著名的 LRU 算法，之后的缓冲区使用和弃用，正是这个算法发挥了作用。之后通过文件系统来读取硬盘文件时，都需要使用和弃用这个缓冲区里的内容，缓冲区即是用户进程的内存和硬盘之间的桥梁，也可以说是page_cache的雏形。
搜索函数在每次获取新的空闲缓冲块时，就会把它移到 free_list 头指针所指链表的最后面，即越靠近链表末端的缓冲块被使用的时间就越近。因此如果 hash 表中没有找到对应缓冲块,就会在搜索新空闲缓冲块时从 free_list 链表头处开始搜索。内核取得缓冲块的算法使用了以下策略:
如果指定的缓冲块存在于 hash 表中，则说明已经得到可用缓冲块，于是直接返回:否则就需要在链表中从 free_list 头指针处开始搜索，即从最近最少使用的缓冲块处开始。
因此最理想的情况是找到一个完全空闲的缓冲块，即b_dirt 和b_lock 标志均为0的缓冲块;但是如果不能满足这两个条件,那么就需要根据b_dirt和b_lock标志计算出一个值。因为设备操作通常很耗时，所以在计算时需加大b_dirt 的权重。然后我们在计算结果值最小的缓冲块上等待(如果缓冲块已经上锁)。最后当标志b_lock 为0时，表示所等待的缓冲块原内容已经写到块设备上。因此getblk() 就获得了一块空闲缓冲块。
对于更新和同步(Synchronization)操作，其主要作用是让内存中的一些缓冲块内容与磁盘等块设备上的信息一致。sync_inodes()的主要作用是把i节点表 inode_table 中的i节点信息与磁盘上的一致起来。但需要经过系统高速缓冲区这一中间环节。实际上，任何同步操作都被分成了两个阶段
1.数据结构信息与高速缓冲区中的缓冲块同步问题，由驱动程序独立负责;
2.高速缓冲区中数据块与磁盘对应块的同步问题，由这里的缓冲管理程序负责;
sync_inodes() 函数不会直接与磁盘打交道，它只能前进到缓冲区这一步，即只负责与缓冲区中的信息同步。剩下的操作需要缓冲管理程序负责。为了让 sync_inodes()知道哪些i节点与磁盘上的不同，就必须首先让缓冲区中内容与磁盘上的内容一致。这样 sync_indes()通过与当前磁盘在缓冲区中的最新数据比较才能知道哪些磁盘 inode 需要修改和更新。最后再进行高速缓冲区与磁盘设备的第二次同步操作,做到内存中的数据与块设备中的数据真正的同步。
高速缓冲区在提高对块设备的访问效率和增加数据共享方面起着重要的作用。除驱动程序以外，内核其他上层程序对块设备的读写操作都需要经过高速缓冲区管理程序来间接地实现。它们之间的主要联系是通过高速缓冲区管理程序中的 bread()函数和块设备低层接口函数ll_rw_block()来实现。上层程序若要访问块设备数据就通过 bread()向缓冲区管理程序申请。如果所需的数据已经在高速缓冲区中，管理程序就会将数据直接返回给程序。如果所需的数据暂时还不在缓冲区中，则管理程序会通过 ll_rw block() 向块设备驱动程序申请,同时让程序对应的进程睡眠等待。等到块设备驱动程序把指定的数据放入高速缓冲区后，管理程序才会返回给上层程序。
