免费注册 查看新帖 |

Chinaunix

  平台 论坛 博客 文库
最近访问板块 发新帖
查看: 4592 | 回复: 3

vm_page的hash链表已经被splay树取代了 [复制链接]

论坛徽章:
0
发表于 2006-03-21 13:30 |显示全部楼层
在【FreeBSD操作系统设计与实现】的第5.2节“FreeBSD虚拟内存系统概述”的末尾,提到了vm_page结构体通常是用一个全局的hash链表进行快速查找的。求诸代码,结果看了很久都没有在源码中发现所谓hash链表的影子,但【FreeBSD操作系统设计与实现】、man手册页以及源代码中的一些注释都提及了这个hash链表的存在,百思不得其解。于是决定进一步考证,去FreeBSD的网站上查历史记录。就在vm_object.c文件的历史中翻出了这么一条:

Revision 1.215 / (download) - annotate - [select for diffs], Fri Oct 18 17:24:30 2002 UTC (3 years, 5 months ago) by dillon
Branch: MAIN
Changes since 1.214: +92 -58 lines
Diff to previous 1.214 (colored)

Replace the vm_page hash table with a per-vmobject splay tree. There should
be no major change in performance from this change at this time but this
will allow other work to progress:  Giant lock removal around VM system
in favor of per-object mutexes, ranged fsyncs, more optimal COMMIT rpc's for
NFS, partial filesystem syncs by the syncer, more optimal object flushing,
etc.  Note that the buffer cache is already using a similar splay tree
mechanism.

Note that a good chunk of the old hash table code is still in the tree.
Alan or I will remove it prior to the release if the new code does not
introduce unsolvable bugs, else we can revert more easily.

Submitted by:        alc        (this is Alan's code)
Approved by:        re


也就是说,vm_page的hash链表已经在2002年的10月份被替换成了splay树!联想到我前两天写的关于vm_map_entry的splay树的文章,又去查vm_map.c文件的历史记录,发现那边是在2002年的5月份引入splay树的,前后差了5个月。

通过和这本书的前身【4.4BSD操作系统设计与实现】的对比,发现关于vm_page用hash链表查找的那句话是在新版本中添加进去的。继续考证4.4BSD-Lite2的代码,原来的hash链表就是放在vm_page结构体里的:

  1. ___________________________________________________________________4.4BSD-Lite2
  2. 099  struct vm_page {
  3. 100      TAILQ_ENTRY(vm_page)    pageq;        /* queue info for FIFO
  4. 101                           * queue or free list (P) */
  5. 102      TAILQ_ENTRY(vm_page)    hashq;        /* hash table links (O)*/
  6. 103      TAILQ_ENTRY(vm_page)    listq;        /* pages in same object (O)*/
  7. 104  
  8. 105      vm_object_t        object;        /* which object am I in (O,P)*/
  9. 106      vm_offset_t        offset;        /* offset into object (O,P) */
  10. 107  
  11. 108      u_short            wire_count;    /* wired down maps refs (P) */
  12. 109      u_short            flags;        /* see below */
  13. 110  
  14. 111      vm_offset_t        phys_addr;    /* physical address of page */
  15. 112  };
  16. ______________________________________________________/usr/src/sys/vm/vm_page.h
复制代码


而现在的vm_page结构体的定义如下,已经没有hashq了:
  1. _____________________________________________________________________FreeBSD6.0
  2. 107  struct vm_page {
  3. 108      TAILQ_ENTRY(vm_page) pageq;    /* queue info for FIFO queue or free list (P) */
  4. 109      TAILQ_ENTRY(vm_page) listq;    /* pages in same object (O)     */
  5. 110      struct vm_page *left;        /* splay tree link (O)        */
  6. 111      struct vm_page *right;        /* splay tree link (O)        */
  7. 112  
  8. 113      vm_object_t object;        /* which object am I in (O,P)*/
  9. 114      vm_pindex_t pindex;        /* offset into object (O,P) */
  10. 115      vm_paddr_t phys_addr;        /* physical address of page */
  11. 116      struct md_page md;        /* machine dependant stuff */
  12. 117      u_short    queue;            /* page queue index */
  13. 118      u_short    flags,            /* see below */
  14. 119          pc;            /* page color */
  15. 120      u_short wire_count;        /* wired down maps refs (P) */
  16. 121      u_int cow;            /* page cow mapping count */
  17. 122      short hold_count;        /* page hold count */
  18. 123      u_char    act_count;        /* page usage count */
  19. 124      u_char    busy;            /* page busy count (O) */
  20. 125      /* NOTE that these must support one bit per DEV_BSIZE in a page!!! */
  21. 126      /* so, on normal X86 kernels, they must be at least 8 bits wide */
  22. 127  #if PAGE_SIZE == 4096
  23. 128      u_char    valid;            /* map of valid DEV_BSIZE chunks (O) */
  24. 129      u_char    dirty;            /* map of dirty DEV_BSIZE chunks */
  25. 130  #elif PAGE_SIZE == 8192
  26. 131      u_short    valid;            /* map of valid DEV_BSIZE chunks (O) */
  27. 132      u_short    dirty;            /* map of dirty DEV_BSIZE chunks */
  28. 133  #elif PAGE_SIZE == 16384
  29. 134      u_int valid;            /* map of valid DEV_BSIZE chunks (O) */
  30. 135      u_int dirty;            /* map of dirty DEV_BSIZE chunks */
  31. 136  #elif PAGE_SIZE == 32768
  32. 137      u_long valid;            /* map of valid DEV_BSIZE chunks (O) */
  33. 138      u_long dirty;            /* map of dirty DEV_BSIZE chunks */
  34. 139  #endif
  35. 140  };
  36. ______________________________________________________/usr/src/sys/vm/vm_page.h
复制代码


这就怪了,原来代码里有的时候书上没说这句话,现在代码里已经没有了,书上却又加进去了这句话,

此外,在【FreeBSD操作系统设计与实现】这本书中也没有提到vm_map_entry已经引入了splay树,在它的114页上也只提到了链表结构。这两点都是原书未能及时更新的地方。

[ 本帖最后由 雨丝风片 于 2006-3-22 07:48 编辑 ]

论坛徽章:
2
亥猪
日期:2014-03-19 16:36:35午马
日期:2014-11-23 23:48:46
发表于 2006-03-21 15:47 |显示全部楼层
先收藏,等看到这个地方的时候再来研读。

论坛徽章:
0
发表于 2006-03-21 16:33 |显示全部楼层
原帖由 gvim 于 2006-3-21 15:47 发表
先收藏,等看到这个地方的时候再来研读。


书没有跟上时代发展还情有可原,最让我郁闷的是man手册页和代码里的一些注释都没有对此进行更新,浪费了我0.5小时的时间!:em12:

论坛徽章:
0
发表于 2006-03-24 09:20 |显示全部楼层
这么多啊
您需要登录后才可以回帖 登录 | 注册

本版积分规则 发表回复

SACC2019中国系统架构师大会

【数字转型 架构演进】SACC2019中国系统架构师大会,8.5折限时优惠重磅来袭!
2019年10月31日~11月2日第11届中国系统架构师大会(SACC2019)将在北京隆重召开。四大主线并行的演讲模式,1个主会场、20个技术专场、超千人参与的会议规模,100+来自互联网、金融、制造业、电商等领域的嘉宾阵容,将为广大参会者提供一场最具价值的技术交流盛会。

限时8.5折扣期:2019年9月30日前


----------------------------------------

大会官网>>
  

北京盛拓优讯信息技术有限公司. 版权所有 16024965号-6 北京市公安局海淀分局网监中心备案编号:11010802020122
中国互联网协会会员  联系我们:huangweiwei@it168.com
感谢所有关心和支持过ChinaUnix的朋友们 转载本站内容请注明原作者名及出处

清除 Cookies - ChinaUnix - Archiver - WAP - TOP