linux0.12--9.高速缓冲区分析

buffer的内存分布如下图:

上图出自《Linux内核完全注释V3.0.pdf》P532
一. 高速缓冲区的初始化
1. buffer的初始化-->在fs/buffer.c中

void buffer_init(long buffer_end)     //在main.c中设置buffer_end=4M
{
    struct buffer_head * h = start_buffer;   //start_buffer=0x41c0c=大约在263K
    void * b;                   //同时在buffer.c中struct buffer_head * start_buffer = (struct buffer_head *) &end;
    int i;                      //这个end是在链接时确定的，内核代码段的末端

    if (buffer_end == 1<<20)
        b = (void *) (640*1024);
    else
        b = (void *) buffer_end;
    while ( (b -= BLOCK_SIZE) >= ((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;     //b_data指向一个个划分好的1K block
        h->b_prev_free = h-1;
        h->b_next_free = h+1;
        h++;
        NR_BUFFERS++;
        if (b == (void *) 0x100000)  //跳过[640-1M]
            b = (void *) 0xA0000;    //buffer的划分是从高到低进行划分的，
    }                                //当遇到1M时直接跳到640K处再进行划分
    h--;
    free_list = start_buffer;        //链表的头是在start_buffer处
    free_list->b_prev_free = h;
    h->b_next_free = free_list;
    for (i=0;i<NR_HASH;i++)
        hash_table[i]=NULL;
}

1.1 初始化完成之后的高速缓冲区如下图所示:
其中缓冲区低端都是一个个的结构体struct buffer_head (紫色表示)
缓冲块的大小都是固定1K
注意:下图没有标出640K-1M的空间,图中的“己划分不出缓冲块 弃之不用"是指缓冲与管理结构体bh之间的内存地址相差不到1K时的情况。

上图出自《Linux内核完全注释V3.0.pdf》P533
1.2 管理结构体bh的内部结构如下图所示:

上图出自《Linux内核完全注释V3.0.pdf》P534
1.3 从buffer_init可以看出:
a.  从start_buffer 一直到  start_buffer+nr_blocks*(sizeof(struct buffer_head))
即[0x41c0c--0x5f054] 处存着buffer的管理结构体struct buffer_head
(gdb) p sizeof(struct buffer_head)
$7 = 36
b. 从[4M-1M] 从[640K-0x5f400=381K]被划分成了一个个1K大小的block，h->b_data = (char *) b;

1.4 调试结果

Breakpoint 1, buffer_init (buffer_end=4194304) at buffer.c:349
349    {
(gdb) p /x b
$1 = 0x400000=4M
(gdb) p /x h
$2 = 0x41c0c=263.011K
后
(gdb) p /x b
$7 = 0x5f000=380K
(gdb) p /x h
$8 = 0x5f054=380.082K
(gdb) p /x *h
$9 = {b_data = 0x5f400, b_blocknr = 0x0, b_dev = 0x0, b_uptodate = 0x0, b_dirt = 0x0, b_count = 0x0, b_lock = 0x0, b_wait = 0x0, b_prev = 0x0, b_next = 0x0,  b_prev_free = 0x5f030, b_next_free = 0x5f078}
(gdb) p /x *h->b_prev_free 
$10 = {b_data = 0x5f800, b_blocknr = 0x0, b_dev = 0x0, b_uptodate = 0x0, b_dirt = 0x0, b_count = 0x0, b_lock = 0x0, b_wait = 0x0, b_prev = 0x0, b_next = 0x0, b_prev_free = 0x5f00c, b_next_free = 0x5f054}
(gdb) p /x *h->b_prev_free->b_prev_free 
$11 = {b_data = 0x5fc00, b_blocknr = 0x0, b_dev = 0x0, b_uptodate = 0x0, b_dirt = 0x0, b_count = 0x0, b_lock = 0x0, b_wait = 0x0, b_prev = 0x0, b_next = 0x0, b_prev_free = 0x5efe8, b_next_free = 0x5f030}
(gdb) p /x free_list 
$12 = 0x41c0c    -->就是buffer的开始处
(gdb) p /x *free_list 
$13 = {b_data = 0x3ffc00, b_blocknr = 0x0, b_dev = 0x0, b_uptodate = 0x0, b_dirt = 0x0, b_count = 0x0, b_lock = 0x0, b_wait = 0x0, b_prev = 0x0, b_next = 0x0, b_prev_free = 0x41be8, b_next_free = 0x41c30}
			
				即free_list的第1项指向buffer的最后一个block 0x3ffc00=4095K 
			

			
				(gdb) p nr_buffers
$12 = 3331
}

---

二.高速缓冲区分配与释放的流程
以getblk为例说明:
sys_setup
--> bh = bread(0x300 + drive*5,0)
     struct buffer_head * bread(int dev,int block)
  -->bh=getblk(dev,block);
2.1 getblk --> 在fs/buffer.c中 L205 -->下面是第1次进getblk的情况

#define BADNESS(bh) (((bh)->b_dirt<<1)+(bh)->b_lock)
struct buffer_head * getblk(int dev,int block)
{
    struct buffer_head * tmp, * bh;

repeat:
//查找hash表中有没有己分配的bh，如果有则直接返回
//现在是第1次使用buffer，所以这儿的bh=NULL
    if (bh = get_hash_table(dev,block))
        return bh;
//在buffer_init中free_list=start_buffer,
//现在是第1次使用所以free_list还是start_buffer，即高速缓冲区的第0个管理bh
    tmp = free_list;
    do {
        if (tmp->b_count)
            continue;
        if (!bh || BADNESS(tmp)<BADNESS(bh)) {
            bh = tmp;
            if (!BADNESS(tmp))
                break;
        }
/* and repeat until we find something good */
    } while ((tmp = tmp->b_next_free) != free_list);
    if (!bh) {
        sleep_on(&buffer_wait);
        goto repeat;
    }
    wait_on_buffer(bh);              //查看是否被占用，占用就跳到repeat
    if (bh->b_count)
        goto repeat;
    while (bh->b_dirt) {
        sync_dev(bh->b_dev);
        wait_on_buffer(bh);         //查看是否被占用，占用就跳到repeat
        if (bh->b_count)
            goto repeat;
    }
/* While we slept waiting for this block, somebody else might */
/* already have added "this" block to the cache. check it */
    if (find_buffer(dev,block))     //查看是否又被占用，占用就跳到repeat
        goto repeat;
/* OK, FINALLY we know that this buffer is the only one of it's kind, */
/* and that it's unused (b_count=0), unlocked (b_lock=0), and clean */
    bh->b_count=1;
    bh->b_dirt=0;
    bh->b_uptodate=0;
    remove_from_queues(bh);
    bh->b_dev=dev;
    bh->b_blocknr=block;
    insert_into_queues(bh);
    return bh;
}

在fs/buffer.c中 L183

struct buffer_head * get_hash_table(int dev, int block)
{
    struct buffer_head * bh;

    for (;;) {
        if (!(bh=find_buffer(dev,block)))
            return NULL;
        bh->b_count++;
        wait_on_buffer(bh);
        if (bh->b_dev == dev && bh->b_blocknr == block)
            return bh;
        bh->b_count--;
    }
}

在fs/buffer.c中-->L166

static struct buffer_head * find_buffer(int dev, int block)
{
    struct buffer_head * tmp;

    for (tmp = hash(dev,block) ; tmp != NULL ; tmp = tmp->b_next)
        if (tmp->b_dev==dev && tmp->b_blocknr==block)
            return tmp;
    return NULL;
}

在fs/buffer.c中-->L129

#define _hashfn(dev,block) (((unsigned)(dev^block))%NR_HASH)
#define hash(dev,block) hash_table[_hashfn(dev,block)]
即:
#define hash(dev,block) hash_table[((unsigned)(dev^block))%NR_HASH]

fs/buffer.c中定义了-->struct buffer_head * hash_table[NR_HASH];

include/linux/fs.h中定义了-->#define NR_HASH 307

对哈希表的操作-->在fs/buffer.c中-->L131

static inline void remove_from_queues(struct buffer_head * bh)
{
/* remove from hash-queue */
    if (bh->b_next)
        bh->b_next->b_prev = bh->b_prev;
    if (bh->b_prev)
        bh->b_prev->b_next = bh->b_next;
    if (hash(bh->b_dev,bh->b_blocknr) == bh)
        hash(bh->b_dev,bh->b_blocknr) = bh->b_next;
/* remove from free list */
//free_list: 先把刚申请到的hb从free_list中删除
    if (!(bh->b_prev_free) || !(bh->b_next_free))
        panic("Free block list corrupted");
    bh->b_prev_free->b_next_free = bh->b_next_free;
    bh->b_next_free->b_prev_free = bh->b_prev_free;
    if (free_list == bh)
        free_list = bh->b_next_free;
}

static inline void insert_into_queues(struct buffer_head * bh)
{
/* put at end of free list */
//free_list: 再把刚申请到的hb添加到free_list的末尾
    bh->b_next_free = free_list;
    bh->b_prev_free = free_list->b_prev_free;
    free_list->b_prev_free->b_next_free = bh;
    free_list->b_prev_free = bh;
/* put the buffer in new hash-queue if it has a device */
    bh->b_prev = NULL;
    bh->b_next = NULL;
    if (!bh->b_dev)
        return;
    bh->b_next = hash(bh->b_dev,bh->b_blocknr);
    hash(bh->b_dev,bh->b_blocknr) = bh;
    bh->b_next->b_prev = bh;
}

a. 对于刚申请的bh
   remove_from_queues-->从free_list的双向链表中删掉
   insert_into_queues   --> 把bh放在free_list双向链表的最后
   即这个刚申请到的bh一直存在于free_list中，但是一申请就被放在了最后，以实现LRU(Least Recently Used)表
所以free_list中的元素并不是全部的free,而是有的free有的不free,在buffer_init中初始化的所有bh都在free_list中,
从始至终都在free_list中,甭管分配了还是没有分配全都放在free_list中。
b. 正在被使用的bh放在哪？
放在hash_table中

3.加入hash表的目的是什么?
是为了快速查找bh:
”hash表的主要作用就是减少查找比较元素所花费的时间。通过在元素的存储位置与关键字之间建立一个对应关系（hash函数），
我们就可以直接通过函数计算立刻查询到指定的元素。建立hash函数的指导条件主要是尽量确保散列到任何数组项的概率基本相等。
建立函数的方法有多种，这里Linux 0.11主要采用了关键字除留余数法。因为我们寻找的缓冲块有两个条件，即设备号dev和缓冲块号block，
因此设计的hash函数肯定需要包含这两个关键值。这里两个关键字的异或操作只是计算关键值的一种方法。
再进行MOD运算就可以保证函数所计算得到的值都处于函数数组项范围内。“
上述引自
getblk-->get_hash_table-->find_buffer

struct buffer_head {
    char * b_data;                /* pointer to data block (1024 bytes) */
    unsigned long b_blocknr;      /* block number */
    unsigned short b_dev;         /* device (0 = free) */
    unsigned char b_uptodate;
    unsigned char b_dirt;         /* 0-clean,1-dirty */
    unsigned char b_count;        /* users using this block */
    unsigned char b_lock;         /* 0 - ok, 1 -locked */
    struct task_struct * b_wait;
    struct buffer_head * b_prev;       -->b_prev跟hash表有关
    struct buffer_head * b_next;       -->b_next跟hash表有关
    struct buffer_head * b_prev_free;
    struct buffer_head * b_next_free;
};

3.1 b_data
无论某一个bh在free_list或hash表的位置如何变化，b_data的值一直不变,一直指向固定的1K缓冲块。