Chinaunix首页 | 论坛 | 博客

wangcong02345wangcong02345.blog.chinaunix.net

首页　| 　博文目录　| 　关于我

wangcong02345

  • 博客访问： 2118629
  • 博文数量： 438
  • 博客积分： 3871
  • 博客等级： 中校
  • 技术积分： 6075
  • 用 户 组： 普通用户
  • 注册时间： 2011-09-10 00:11
个人简介

邮箱: wangcong02345@163.com

文章分类

全部博文（438）

文章存档

2017年（15）

2016年（119）

2015年（91）

2014年（62）

2013年（56）

2012年（79）

2011年（16）

我的朋友
最近访客
推荐博文
相关博文
linux0.12--9.高速缓冲区分析

分类： LINUX

2016-10-03 22:02:11

buffer的内存分布如下图:

上图出自《Linux内核完全注释V3.0.pdf》P532
一. 高速缓冲区的初始化
1. buffer的初始化-->在fs/buffer.c中
  1. void buffer_init(long buffer_end)     //在main.c中设置buffer_end=4M
  2. {
  3.     struct buffer_head * h = start_buffer;   //start_buffer=0x41c0c=大约在263K
  4.     void * b;                   //同时在buffer.c中struct buffer_head * start_buffer = (struct buffer_head *) &end;              
  5.     int i;                      //这个end是在链接时确定的，内核代码段的末端

  7.     if (buffer_end == 1<<20)
  8.         b = (void *) (640*1024);
  9.     else
  10.         b = (void *) buffer_end;
  11.     while ( (b -= BLOCK_SIZE) >= ((void *) (h+1)) ) {
  12.         h->b_dev = 0;
  13.         h->b_dirt = 0;
  14.         h->b_count = 0;
  15.         h->b_lock = 0;
  16.         h->b_uptodate = 0;
  17.         h->b_wait = NULL;
  18.         h->b_next = NULL;
  19.         h->b_prev = NULL;
  20.         h->b_data = (char *) b;     //b_data指向一个个划分好的1K block
  21.         h->b_prev_free = h-1;
  22.         h->b_next_free = h+1;
  23.         h++;
  24.         NR_BUFFERS++;
  25.         if (b == (void *) 0x100000)  //跳过[640-1M]
  26.             b = (void *) 0xA0000;    //buffer的划分是从高到低进行划分的，
  27.     }                                //当遇到1M时直接跳到640K处再进行划分
  28.     h--;
  29.     free_list = start_buffer;        //链表的头是在start_buffer处
  30.     free_list->b_prev_free = h;
  31.     h->b_next_free = free_list;
  32.     for (i=0;i<NR_HASH;i++)
  33.         hash_table[i]=NULL;
  34. }
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 调试结果
  1. Breakpoint 1, buffer_init (buffer_end=4194304) at buffer.c:349
  2. 349    {
  3. (gdb) p /x b
  4. $1 = 0x400000=4M
  5. (gdb) p /x h
  6. $2 = 0x41c0c=263.011K
  7. 后
  8. (gdb) p /x b
  9. $7 = 0x5f000=380K
  10. (gdb) p /x h
  11. $8 = 0x5f054=380.082K
  12. (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}
  13. (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}
  14. (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 
  15. $12 = 3331
  16. }
二.高速缓冲区分配与释放的流程
以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的情况
  1. #define BADNESS(bh) (((bh)->b_dirt<<1)+(bh)->b_lock)
  2. struct buffer_head * getblk(int dev,int block)
  3. {
  4.     struct buffer_head * tmp, * bh;

  6. repeat:
  7. //查找hash表中有没有己分配的bh，如果有则直接返回
  8. //现在是第1次使用buffer，所以这儿的bh=NULL
  9.     if (bh = get_hash_table(dev,block))
  10.         return bh;
  11. //在buffer_init中free_list=start_buffer,
  12. //现在是第1次使用所以free_list还是start_buffer，即高速缓冲区的第0个管理bh
  13.     tmp = free_list;
  14.     do {
  15.         if (tmp->b_count)
  16.             continue;
  17.         if (!bh || BADNESS(tmp)<BADNESS(bh)) {
  18.             bh = tmp;
  19.             if (!BADNESS(tmp))
  20.                 break;
  21.         }
  22. /* and repeat until we find something good */
  23.     } while ((tmp = tmp->b_next_free) != free_list);
  24.     if (!bh) {
  25.         sleep_on(&buffer_wait);
  26.         goto repeat;
  27.     }
  28.     wait_on_buffer(bh);              //查看是否被占用，占用就跳到repeat
  29.     if (bh->b_count)
  30.         goto repeat;
  31.     while (bh->b_dirt) {
  32.         sync_dev(bh->b_dev);
  33.         wait_on_buffer(bh);         //查看是否被占用，占用就跳到repeat
  34.         if (bh->b_count)
  35.             goto repeat;
  36.     }
  37. /* While we slept waiting for this block, somebody else might */
  38. /* already have added "this" block to the cache. check it */
  39.     if (find_buffer(dev,block))     //查看是否又被占用，占用就跳到repeat
  40.         goto repeat;
  41. /* OK, FINALLY we know that this buffer is the only one of it's kind, */
  42. /* and that it's unused (b_count=0), unlocked (b_lock=0), and clean */
  43.     bh->b_count=1;
  44.     bh->b_dirt=0;
  45.     bh->b_uptodate=0;
  46.     remove_from_queues(bh);
  47.     bh->b_dev=dev;
  48.     bh->b_blocknr=block;
  49.     insert_into_queues(bh);
  50.     return bh;
  51. }
在fs/buffer.c中 L183
  1. struct buffer_head * get_hash_table(int dev, int block)
  2. {
  3.     struct buffer_head * bh;

  5.     for (;;) {
  6.         if (!(bh=find_buffer(dev,block)))
  7.             return NULL;
  8.         bh->b_count++;
  9.         wait_on_buffer(bh);
  10.         if (bh->b_dev == dev && bh->b_blocknr == block)
  11.             return bh;
  12.         bh->b_count--;
  13.     }
  14. }
在fs/buffer.c中-->L166
  1. static struct buffer_head * find_buffer(int dev, int block)
  2. {        
  3.     struct buffer_head * tmp;

  5.     for (tmp = hash(dev,block) ; tmp != NULL ; tmp = tmp->b_next)
  6.         if (tmp->b_dev==dev && tmp->b_blocknr==block)
  7.             return tmp;
  8.     return NULL;
  9. }
在fs/buffer.c中-->L129
  1. #define _hashfn(dev,block) (((unsigned)(dev^block))%NR_HASH)
  2. #define hash(dev,block) hash_table[_hashfn(dev,block)]
  3. 即:
  4. #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
  1. static inline void remove_from_queues(struct buffer_head * bh)
  2. {
  3. /* remove from hash-queue */
  4.     if (bh->b_next)
  5.         bh->b_next->b_prev = bh->b_prev;
  6.     if (bh->b_prev)
  7.         bh->b_prev->b_next = bh->b_next;
  8.     if (hash(bh->b_dev,bh->b_blocknr) == bh)
  9.         hash(bh->b_dev,bh->b_blocknr) = bh->b_next;
  10. /* remove from free list */
  11. //free_list: 先把刚申请到的hb从free_list中删除
  12.     if (!(bh->b_prev_free) || !(bh->b_next_free))
  13.         panic("Free block list corrupted");
  14.     bh->b_prev_free->b_next_free = bh->b_next_free;
  15.     bh->b_next_free->b_prev_free = bh->b_prev_free;
  16.     if (free_list == bh)
  17.         free_list = bh->b_next_free;
  18. }

  20. static inline void insert_into_queues(struct buffer_head * bh)
  21. {
  22. /* put at end of free list */
  23. //free_list: 再把刚申请到的hb添加到free_list的末尾
  24.     bh->b_next_free = free_list;
  25.     bh->b_prev_free = free_list->b_prev_free;
  26.     free_list->b_prev_free->b_next_free = bh;
  27.     free_list->b_prev_free = bh;
  28. /* put the buffer in new hash-queue if it has a device */
  29.     bh->b_prev = NULL;
  30.     bh->b_next = NULL;
  31.     if (!bh->b_dev)
  32.         return;
  33.     bh->b_next = hash(bh->b_dev,bh->b_blocknr);
  34.     hash(bh->b_dev,bh->b_blocknr) = bh;
  35.     bh->b_next->b_prev = bh;
  36. }
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
  1. struct buffer_head {
  2.     char * b_data;                /* pointer to data block (1024 bytes) */
  3.     unsigned long b_blocknr;      /* block number */
  4.     unsigned short b_dev;         /* device (0 = free) */
  5.     unsigned char b_uptodate;
  6.     unsigned char b_dirt;         /* 0-clean,1-dirty */
  7.     unsigned char b_count;        /* users using this block */
  8.     unsigned char b_lock;         /* 0 - ok, 1 -locked */
  9.     struct task_struct * b_wait;
  10.     struct buffer_head * b_prev;       -->b_prev跟hash表有关
  11.     struct buffer_head * b_next;       -->b_next跟hash表有关
  12.     struct buffer_head * b_prev_free;
  13.     struct buffer_head * b_next_free;
  14. };
3.1 b_data
无论某一个bh在free_list或hash表的位置如何变化，b_data的值一直不变,一直指向固定的1K缓冲块。



阅读(1041) | 评论(0) | 转发(0) |
0

上一篇：linux0.12--8.磁盘读写流程

下一篇：linux0.12--10.minix文件系统分析

给主人留下些什么吧！~~
关于我们 | 关于IT168 | 联系方式 | 广告合作 | 法律声明 | 免费注册

Copyright 2001-2010 ChinaUnix.net All Rights Reserved 北京皓辰网域网络信息技术有限公司. 版权所有

感谢所有关心和支持过ChinaUnix的朋友们

16024965号-6