你好，我是闪客。

在上一讲中我们说到了进程调度的初始化，让操作系统随时准备迎接时钟中断的到来，进而触发进程调度。

那接下来我们就回到 main 函数，继续看下一个初始化的方法，缓冲区初始化 buffer_init，加油，没剩多少了！

// init/main.c
void main(void) {
    ...
    buffer_init(buffer_memory_end);
    ...
}

首先要注意到，这个函数传了个参数 buffer_memory_end，这个是在老早之前就设置好的，就在 第12讲 | 边界值划分与主内存初始化，可以去回顾下。

同时，且我们在 第12讲，主内存初始化 mem_init 中，用 mem_init 设置好了主内存的管理结构 mam_map。

这是把主内存区管理起来了，所以今天就是把剩下的缓冲区部分，也初始化管理起来。目的就是这么单纯，我们看代码。

我们还是采用之前的方式，就假设内存只有 8M，把一些不相干的分支去掉，方便理解。

// fs/buffer.c
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;
}

虽然很长，但其实就造了两个数据结构而已。

不过别急，我们先从第一行代码开始看起。

// fs/buffer.c
extern int end;
void buffer_init(long buffer_end) {
    struct buffer_head * start_buffer = (struct buffer_head *) &end;
    ...
}

这里有个外部变量 end，而我们的缓冲区开始位置 start_buffer 就等于这个变量的内存地址。

这个外部变量 end 并不是操作系统代码写就的，而是由链接器 ld 在链接整个程序时设置的一个外部变量，帮我们计算好了整个内核代码的末尾地址。

那在这之前的是内核代码区域肯定不能用，在这之后的，就给 buffer 用了。所以我们的内存分布图可以更精确一点了。

你看，之前的疑惑解决了吧？很好理解嘛，内核程序和缓冲区的划分，肯定有个分界线，这个分界线就是 end 变量的值。

这个值定多少合适呢？

像主内存区和缓冲区的分界线，就直接代码里写死了，就是上图中的 2M，这是我们自己规定的，也就是 Linus 定的，没啥好解释的。

可是内核程序占多大内存在写的时候完全不知道，就算知道了如果改动一点代码也会变化，所以就由程序编译链接时由链接器程序帮我们把这个内核代码末端的地址计算出来，作为一个外部变量 end 我们拿来即用，就方便多了。

好，回过头我们再看看，整段代码创造了哪两个管理结构？

我们先看这段结构。

// fs/buffer.c
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_data = (char *) b;
        h->b_prev_free = h-1;
        h->b_next_free = h+1;
        h++;
    }
    ...
}

就俩变量。

一个是 buffer_head 结构的 h，代表缓冲头，其指针值是 start_buffer，刚刚我们计算过了，就是图中的内核代码末端地址 end，也就是缓冲区开头。

一个是 b，代表缓冲块，指针值是 buffer_end，也就是图中的 2M，就是缓冲区结尾。

缓冲区结尾的 b 每次循环 -1024，缓冲区结尾的 h 每次循环 +1（一个 buffer_head 结构体大小的内存），直到碰一块为止。

可以看到，其实这个 b 就代表缓冲块，h 代表缓冲头，一个从上往下，一个从下往上。

简单说，其实就是一块空间，分别给了一对儿一对儿的缓冲头和缓冲块，缓冲头就是用来寻找缓冲块的。

// include/linux/fs.h
struct buffer_head {
  char *b_data;
  ...
  struct buffer_head *b_prev_free;
  struct buffer_head *b_next_free;
};

上面就是缓冲头的数据结构，根据代码看，其中的 b_data 是个指针，指向了与之相配对儿的 1024 字节大小的缓冲块。还有个前后空闲指针 b_prev_free 和 b_next_free，分别前一个缓冲头和后一个缓冲头。

那画成图就是如下这样（图中直接用 prev 和 next 省略表示了）。

当缓冲头 h 的所有 b_prev_free 和 b_next_free 指针都指向彼此时，就构成了一个双向空闲链表。继续看。

// fs/buffer.c
void buffer_init(long buffer_end) {
    ...
    free_list = start_buffer;
    free_list->b_prev_free = h;
    h->b_next_free = free_list;
    ...
}

这三行代码，结合刚刚的双向空闲链表 h，我画出图，你就懂了。

看，free_list 指向了缓冲头双向链表的第一个结构，然后就可以顺着这个结构，从双向链表中遍历到任何一个缓冲头结构了，而通过缓冲头又可以找到这个缓冲头对应的缓冲块。

简单说，缓冲头就是具体缓冲块的管理结构，而 free_list 开头的双向链表又是缓冲头的管理结构，整个管理体系就这样建立起来了。

现在，从 free_list 开始遍历，就可以找到这里的所有内容了。

不过，还有最后一个事，能帮助更好管理，往下看。

// fs/buffer.c
void buffer_init(long buffer_end) {
    ...
    for (i=0;i<307;i++)
        hash_table[i]=NULL;
}

一个 307 大小的 hash_table 数组，这是干嘛的呢？

其实今天的这个代码在 buffer.c 中，而 buffer.c 是在 fs 包下的，也就是文件系统包下的。所以它今后是为文件系统而服务，具体是内核程序如果需要访问块设备中的数据，就都需要经过缓冲区来间接地操作。

也就是说，读取块设备的数据（硬盘中的数据），需要先读到缓冲区中，如果缓冲区已有了，就不用从块设备读取了，直接取走。

那怎么知道缓冲区已经有了要读取的块设备中的数据呢？从双向链表从头遍历当然可以，但是这效率可太低了。所以需要一个哈希表结构以 O(1) 的复杂度快速查找，这就是 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);
    ...
}

一路跟下来发现，就是通过

dev^block % 307

即

(设备号^逻辑块号) Mod 307

找到在 hash_table 里的索引下标，接下来就和 Java 里的 HashMap 类似，如果哈希冲突就形成链表，画成图就是这样。

哈希表 + 双向链表，如果刷算法题多了，很容易想到这可以实现 LRU 算法，没错，之后的缓冲区使用和弃用，正是这个算法发挥了作用。

后面通过文件系统来读取硬盘文件时，都需要使用和弃用这个缓冲区里的内容，缓冲区即是用户进程的内存和硬盘之间的桥梁。

总结时刻

好了好了，再多说几句就把文件系统里读操作的细节讲出来了，怕你压力太大，我们这一讲还是主要来了解这个缓冲区的管理工作是如何初始化的，为后面做铺垫。

还是老规矩，我们再来简单回顾一下这一讲的内容。这一讲我们说到，buffer_init 完成了缓冲区初始化工作，通过双向空闲链表和哈希表的方式，形成了缓冲区管理的方法。

欲知后事如何，且听下回分解。