- 论坛徽章:
- 0
|
在【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结构体里的:
- ___________________________________________________________________4.4BSD-Lite2
- 099 struct vm_page {
- 100 TAILQ_ENTRY(vm_page) pageq; /* queue info for FIFO
- 101 * queue or free list (P) */
- 102 TAILQ_ENTRY(vm_page) hashq; /* hash table links (O)*/
- 103 TAILQ_ENTRY(vm_page) listq; /* pages in same object (O)*/
- 104
- 105 vm_object_t object; /* which object am I in (O,P)*/
- 106 vm_offset_t offset; /* offset into object (O,P) */
- 107
- 108 u_short wire_count; /* wired down maps refs (P) */
- 109 u_short flags; /* see below */
- 110
- 111 vm_offset_t phys_addr; /* physical address of page */
- 112 };
- ______________________________________________________/usr/src/sys/vm/vm_page.h
复制代码
而现在的vm_page结构体的定义如下,已经没有hashq了:
- _____________________________________________________________________FreeBSD6.0
- 107 struct vm_page {
- 108 TAILQ_ENTRY(vm_page) pageq; /* queue info for FIFO queue or free list (P) */
- 109 TAILQ_ENTRY(vm_page) listq; /* pages in same object (O) */
- 110 struct vm_page *left; /* splay tree link (O) */
- 111 struct vm_page *right; /* splay tree link (O) */
- 112
- 113 vm_object_t object; /* which object am I in (O,P)*/
- 114 vm_pindex_t pindex; /* offset into object (O,P) */
- 115 vm_paddr_t phys_addr; /* physical address of page */
- 116 struct md_page md; /* machine dependant stuff */
- 117 u_short queue; /* page queue index */
- 118 u_short flags, /* see below */
- 119 pc; /* page color */
- 120 u_short wire_count; /* wired down maps refs (P) */
- 121 u_int cow; /* page cow mapping count */
- 122 short hold_count; /* page hold count */
- 123 u_char act_count; /* page usage count */
- 124 u_char busy; /* page busy count (O) */
- 125 /* NOTE that these must support one bit per DEV_BSIZE in a page!!! */
- 126 /* so, on normal X86 kernels, they must be at least 8 bits wide */
- 127 #if PAGE_SIZE == 4096
- 128 u_char valid; /* map of valid DEV_BSIZE chunks (O) */
- 129 u_char dirty; /* map of dirty DEV_BSIZE chunks */
- 130 #elif PAGE_SIZE == 8192
- 131 u_short valid; /* map of valid DEV_BSIZE chunks (O) */
- 132 u_short dirty; /* map of dirty DEV_BSIZE chunks */
- 133 #elif PAGE_SIZE == 16384
- 134 u_int valid; /* map of valid DEV_BSIZE chunks (O) */
- 135 u_int dirty; /* map of dirty DEV_BSIZE chunks */
- 136 #elif PAGE_SIZE == 32768
- 137 u_long valid; /* map of valid DEV_BSIZE chunks (O) */
- 138 u_long dirty; /* map of dirty DEV_BSIZE chunks */
- 139 #endif
- 140 };
- ______________________________________________________/usr/src/sys/vm/vm_page.h
复制代码
这就怪了,原来代码里有的时候书上没说这句话,现在代码里已经没有了,书上却又加进去了这句话,
此外,在【FreeBSD操作系统设计与实现】这本书中也没有提到vm_map_entry已经引入了splay树,在它的114页上也只提到了链表结构。这两点都是原书未能及时更新的地方。
[ 本帖最后由 雨丝风片 于 2006-3-22 07:48 编辑 ] |
|