NetBSD 内存管理系统 UVM 浅析

核心提示： uvm_map_entry 使用双向链表, 按地址顺序链接在 uvm_map 中. 它还使用了红黑树的方法加快查找和地址分配速度. 这是一个相对简单的函数, 函数首先载入 hint, 即上一次查找到的位置, 由于我们对地址空间的查找往往是从小到大按序进行的, 因此这是一个很大的优化. 如果

uvm_map_entry 使用双向链表, 按地址顺序链接在 uvm_map 中. 它还使用了红黑树的方法加快查找和地址分配速度.

这是一个相对简单的函数, 函数首先载入 hint, 即上一次查找到的位置, 由于我们对地址空间的查找往往是从小到大按序进行的, 因此这是一个很大的优化.

如果我们所需的地址在 hint 之前或 uvm_map 所含有的 entry 数大于 30, 我们将使用红黑树的搜索而非线性搜索.

红黑树是一种二叉查找树, 其特别之处在于能够保证树的大致平衡而保证搜索效率. 红黑树的基本知识参见 http://en.wikipedia.org/wiki/Red-black_tree, NetBSD 在 sys/tree.h 实现了它. 而线性搜索的分析从略.

uvm_map() 和 uvm_unmap()

uvm_map() 显然是 uvm_map.c 的核心函数, 它将一个 uvm_obj 映射进地址空间 . 它使用了众多的底层函数帮助它完成功能.

uvm_map() 的工作分成以下几步:

调整参数, 调整 rbtree, 加锁等准备工作.

XXX

在地址空间中找到合适的地方做映射

这里的主要工作是由 uvm_map_findspace() 完成的, 它返回了符合长度要求的空闲空间前面的一个 entry (而不是直接返回空闲空间的偏移量, 后面会看到这样做的原因).

XXX: uvm_map_findspace() 的分析

调整 object 相关参数

懒了, 直接抄

if uobj is null, then uoffset is either a VAC hint for PMAP_PREFER
[typically from uvm_map_reserve] or it is UVM_UNKNOWN_OFFSET.　 in
either case we want to zero it　before storing it in the map entry
(because it looks strange and confusing when debugging...)
　　
if uobj is not null
　　if uoffset is not UVM_UNKNOWN_OFFSET then we have a normal mapping
　　and we do not need to change uoffset.
　　if uoffset is UVM_UNKNOWN_OFFSET then we need to find the offset
　　　　now (based on the starting address of the map).　 this case is
　　　　for kernel object mappings where we don't know the offset until
　　the virtual address is found (with uvm_map_findspace).　 the
　　offset is the distance we are from the start of the map.


加入 uvm_map

程序首先试图与其临近的表项合并, 如果它们属性相同, 地址能接得上, 指向同一个 uvm_obj, offset也接得上, 没用 amap 或 amap 也是能够接得上且不与其他地址空间共享 (共享的东西千万不要乱动), 那么它们就是可以合并的, 减少表项能够加快频繁使用的表项查找的效率. 应该指出的是, 这是很常见的现象, 因为内存空间中绝大多数都是内存对象而非文件的映射, 分配算法又使它们尽量紧靠在一起, 合并可以常常进行 (XXX: 果真如此?)