消息引用于此。
http://bbs.520dn.com/thread-70441-1-1.html
综述
UVM 是 NetBSD 使用的虚拟内存系统. 与其他基于 4.4BSD 的系统如 FreeBSD 等不同, 它完全重写了 4.4BSD 的 VM. 相对于 4.4BSD VM, 它有很多显著的改进. 简化了设计, 提高了效率, 特别是引入了 amap, 很好地解决了 COW 问题.
uvm 系统与系统 kernel 相对独立 (4.4BSD VM 基于 Mach VM, 与 Mach 微内核分离, 4.4BSD 和 NetBSD 虽然没采用微内核架构, 却也集成了这样的功能模块结构). 全部代码在代码树 src/sys/uvm 处, 下文提到的文件路径若非绝对路径 , 都是从该目录开始的路径.
核心数据结构
在 NetBSD 中, 每个进程拥有一个独立的进程空间. 这由 vmspace 结构表示, 每个 proc 接口都包含着一个执行 vmspace 的项p_vmsapce, 这个 uvm 系统与进程管理系统的接口.
vmspace 结构的声明在 uvm_extern.h, 我们看到, 除了一些审计信息之外, 它直接指向 uvm_map.h 中的 uvm_map 结构. 因此 uvm_map 结构才是代表一个地址空间, 顾名思义, 用于完成地址的映射 (mapping 功能). uvm_map 中最为重要的两项是指向硬件相关的地址空间描述结构 pmap 和 uvm_map_entry 的双向链表.
我们在下一节认真查看 uvm_map_entry 结构, 以后要经常跟它打交道. 在这里, 我们看到, 它的 start 和 end 项说明了这个 entry 映射到地址空间中的地址范围, 接下来是一个联合的指向 uvm_obj 或 sub_map 的 object 项, sub_map 是提供给内核地址空间的特殊机制, 我们很少讨论它. 可以这么说, uvm_map_entry 指向一个 uvm_obj 结构, 是该对象的映射. offset 项说明了它在 uvm_obj 中的偏移量. ps. 这都是注释写得很清楚的, 我在这里说干嘛...
我们还可以看到 aref 项, vm_aref 结构指向了一个 amap (匿名对象映射 XXX. 这个翻译准确么?), 是一种代替 4.4BSD 中多层 shadow 对象的机制.
uvm_obj, vm_amap 及一下的结构我们称为底层结构, 内存的实际分配和操作都在这以下的层面完成, 它们最终指向内存分配管理的最小单位 vm_page.
整个 uvm 的核心数据可以表示如下, vm_amap 和 uvm_obj 之间的虚线我们会在下面的章节解释. 并非真正表示指针引用关系.
vmspace
|
v
uvm_map_entry <--> vm_map_entry ...
| |
| v
| vm_pmap
|
+-----------------+
| |
v |
vm_aref |
| |
v v
vm_amap < - - - > uvm_obj
| |
v v
vm_anon ... vm_page <-> vm_page ...
|
v
vm_page
另外, 我们注意到 uvm.h 中有个 uvm 结构, 这是各种 uvm 资源和参数的集合, 系统中只存在一个 uvm 对象.
顶层映射机构 (vmspace, uvm_map, uvm_map_entry)
顶层映射机构所要负责的事务包括
将一个对象映射进地址空间.
对一个虚地址 (VA), 定位到所属 uvm_map_entry (因为在此之下的地址是连 续的, 不用什么定位).
提取地址空间的某一断以供其他地址空间使用.
COW (Copy-On-Write) 的顶层处理.
其主要代码在 uvm_map.c, 这个一个有 4000 多行代码的大文件, 我们从顶层接口到底层实现逐一分析.
uvm_map_lookup_entry()
该函数能得到一个 VA 所指向, 或正好在此之前的一个 uvm_map_entry. 该函数不但用于地址映射, 还帮助地址空间分配机构找到合适的地址范围.
uvm_map_entry 使用双向链表, 按地址顺序链接在 uvm_map 中. 它还使用了红黑树的方法加快查找和地址分配速度.
这是一个相对简单的函数, 函数首先载入 hint, 即上一次查找到的位置, 由于我们对地址空间的查找往往是从小到大按序进行的, 因此这是一个很大的优化.
如果我们所需的地址在 hint 之前或 uvm_map 所含有的 entry 数大于 30, 我们将使用红黑树的搜索而非线性搜索.
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: 果真如此?)
如果合并不成, 我们就要创建新的表项, 代码在 nomerge 标记之后. 需要注意的是对 UVM_FLAG_COPYONW (COW) 的处理, 如果没有要求 UVM_FLAG_OVERLAY ( 创建一个映射覆盖 uobj 的 amap) 的话, 就会设其 etype 为 NEEDSCOPY, 这样 , 就是在第一次试图写的时候引起 fault, 由 vm_fault 处理这个 COW 的情况, 这是 uvm_map 对 COW 的支持, 而详细的处理过程将在下面的章节介绍.
--------------------------------------------------------------------------------
uvm_unmap 的代码在 uvm_map_i.h, 它的主要工作是由 uvm_map.c 中的 uvm_map_remove 和 uvm_map_detach 完成.
uvm_map_remove()
这函数将解除参数 start 到 end 的映射. 这本是一个简单的任务, 只要将 start 到 end 之间的 vm_map_entry 清理出去就可以了. 但是如果 start 和 end 不是正好跟一个 vm_map_entry 对齐的时候, 我们就只好先把这个 vm_map_entry 分成两半, 在把其中的一半清理出去, 这由 UVM_MAP_CLIP_START 和 UVM_MAP_CLIP_END 完成, 它们包裹位于 uvm_map.c 中的 uvm_map_clip_start 和 uvm_map_clip_end, 有兴趣的读者可以自行阅读相关代码.
除此以外, 我们可以依次把范围内的 vm_map_entry 清出, 我们来看具体的处理过程.
XXX
uvm_map_detach()
uvm_unmap_remove 将清出 uvm_map 的表项做成链表返回, 再由 uvm_unmap_detach 解除引用关系. 这样做的原因是解除引用关系往往会引起写回文件等 I/O 操作, 花费很多时间, 而 uvm_umap_remove 工作时时要把整个 uvm_map 锁住的, 如果是在 remove 的同时做 detach 操作, 锁住 uvm_map 的时间就会很长, 影响效率.
函数本身很简单, 就是依次取消每个表项的 amap 和 uvm_obj 引用.
底层管理机构 (amap, anon, uobj, pager)
传统管理机构: uvm_obj
我们先来叙述经典的 4.4BSD vm_object 机制. vm_object 内存系统中的资源代表, 可以映射进地址空间使用. vm_object 向下连接着 pager --- 资源操作的接口, pager 又连接着真正的资源. 当访问内存产生 fault 的时候, 系统会通过 vm_object, 再通过 pager 到指定的资源处取得相关的数据来填充页面, 从用户的观点看就象是这个资源已经完全映射到内存中一样.
这种两层 (三层) 指向的机制是复杂的, 一个更严重的问题是, vm_object 在使用时有一个 cache, 而系统被设计成资源对象与内存系统完全分离, 像 vnode 对象它又由另一个 cache 系统缓存, 这样不但降低了内存的使用率, 还会产生一致性问题. (XXX: Really?)
所以 UVM 决定把 uvm_obj 直接嵌入可映射入内存的资源对象中, 如 vnode 结构中就有 uvm_obj 项, 来解决这种复杂性和不一致. 大大简化了对象操作.
Anonymous Memory Object
Anonymous Memory Object 是指没有文件与之相联系的内存对象, 因此是无名 (anonymous) 的, 它在初次使用时为空(填为 0), 用完后被自动抛弃. (XXX: 我们是否可以在概念上把它看成 /dev/zero 的映射?)
XXX: 管理算法, uao_get(), uao_put() 解析.
[ 本帖最后由 denny216 于 2008-10-13 19:13 编辑 ]
TOP
denny216
* 发短消息
* 加为好友
denny216 当前离线
最后登录
2010-2-4
注册时间
2008-8-22
阅读权限
80
精华
18
积分
35151
帖子
7083
QQ查看详细资料
论坛元老
Rank: 21Rank: 21Rank: 21
威望
3825
金钱
30542 D币
宣传币
2512 X币
主题
0
幽默大师勋章 优秀版主勋章 一等功勋章 精品文章勋章 超级灌水员勋章 社区建设勋章 三等功勋章 论坛原创勋章 解答高手勋章 热心会员勋章 爱心勋章 爱国勋章 绿色软件勋章 宣传小组勋章 灌水大仙勋章 活动勋章 两周年勋章
2楼
发表于 2008-10-13 19:12 | 只看该作者
解决 COW: UVM 方法
COW (Copy-On-Write) 是一个重要的系统特性, 为 fork(2), mmap(2) 等重要的系统调用提供了强力支持.
4.4BSD 使用影子(shadow)对象的方法解决 COW 的问题. 当拷贝内存的时候, 目标地址所对应的是一个影子对象, 它指向原对象作为后援对象, 当由于写操作产生一个 fault 的时候, 就从后援对象那里获取数据, 完成 COW. 注意影子对象也可以被复制, 成为另一个影子对象的后援对象, 这样就成为了一个影子对象链 .
使用这样的方法, 当影子对象链太长的时候, 处理 fault 的时间就会很长, 因为要整条影子对象链都 fault 一次. 偏偏使用 COW 肯定会产生很多 fault, 因此会产生严重的效率问题. 一种解决方法是在可能的时候尽量压缩影子对象链 (FreeBSD 方法), 这增加了复杂性却又没有真正解决问题.
UVM 使用了 amap 来解决 COW. amap 管理一组 anon, 每个 anon 指向一个 vm_page, 每个 anon 都有一个引用数, 引用数大于 1 时会使之不可写. 当我们要 COW copy 一个没有 amap 的 entry 时, 我们将两者都标为 UVM_ET_NEEDSCOPY, 这时候, 只要对其作写操作就会 fault, 而 fault 处理发 现它们时 NEEDSCOPY 的时候, 就会为其简历 amap, 以后的写操作都写在 amap 上, 达到了 COW 的目的; 而要 COW copy 一个带 amap 的entry 时, 我们还要复制 amap, 新 entry 就能访问与旧 entry 一样的数据, 这样以来, 原 amap 所管理的 anon 的引用数就变成 2, 而变成只读. 因此, 对其写操作也会引起 fault, 这是系统将申请一个 anon 和新页, 复制页面数据, 将 anon 连入被写的 amap, 也就完成了 COW. 这样看来, 无论是首次 COW, 还是 COW 对象上的 COW 我们都可以用上述机制处理. 而只要访问两层的接口, 避免了长影子对象链的问题, 又简化了设计. 其关键就在于 COW 时我们能够 复制 而不是 引用 amap, 相对于 COW 对象的 fault, 复制 amap 出现的概率小得多, 因此复制整个 amap 是有价值的.
观察 uvm_map 中的 vmspace_fork() 中对 MAP_INHERIT_COPY 情况的处理, 能够了解 amap 是怎么被创建和使用的, 而 fault 的处理, 即真正的 COW 过程, 我们将在 uvm_fault() 处解析.
我们来看 amap 和 anon 的具体管理实现.
anon 结构的声明在 uvm_anon.h 中, 有一个引用数, 一个 lock, 一个在未使用时指向下一未使用 anon 或在使用时指向 page 的指针. (anon 使用一个预分配的 anon 池完成 anon 的分配和释放), 以及标识该 anon 所管理的页在 swap 中的位置的 index, 非常易懂.
anon 的操作在 uvm_anon.c. 主要时 anon 的分配和释放, 以及一些 swap 系统的支持, 忽略之.
我们现在来看 amap 的数据接口, 主要是要注意 am_anon, am_bckptr, 和 am_slots 的关系, 在 uvm_amap.h:181 处的注释中有比较详细的解释. 它们结合起来实现对 anon 高效的查找和管理. 最后总结成一句最重要的话: "if am_anon[X] is non-NULL, then the following must be true: am_slots[am_bckptr[X]] == X".
下面来分析 uvm_amap.c, amap 本身的分配和释放过去简单, 忽略之, 我们主要观察:
amap 对 anon 的管理.
amap_add() 和 amap_unadd() 能加入/撤消一个 amap 对 anon 的链接, 代码在 uvm_amap_i.h 并不复杂, 主要是要在这里熟悉其数据结构的操作, 注意 amp_unadd() 保证删除一项后仍保持 am_slots 连续且有效的方法.
amap 对 COW 的支持.
amap_copy() 用于在 COW 的 write fault 发生的时候拷贝整个 amap 的表项, 以达到 COW 的效果 (想想 fork(2) 的传统处理过程). 这是 COW 的关键步骤.
首先, 如果要求处理的 entry 根本没有 amap --- 直接在 obj 上的 COW, 我们就先得创建一个. 然后, 我们得检查是否只有我们引用了这个 amap, 如果是刚刚新创建的 amap 就处于这种状态, 既然只有我们引用它, 那么 COW 的前提就不存在了, 直接忽略之. 之后, 我们就真要拷贝 amap 了, 我们拷贝的是对 amap 对 anon 的引用. 这时候, 我们就有了两个完全一样的 amap, 指向一样的 anon, 也就指向了同样的内存资源, 这样从我们看来就像是真正拷贝了内存资源一样, 但它们是只读的, 在第一次写 --- 也即要使它们不一样的时候, 我们才去做数据的拷贝和写操作, 这就是 COW 了.
uvm_fault() 作为内存管理的核心
uvm_fault() 是一个 1200 多行的大函数, 它在读或写的 fault 的时候, 实际完成了内存分配, COW 等核心功能. 我们可以这么看, 前面介绍的函数只是设置好了数据结构, 而真正的功能是由 uvm_fault() 完成的. 我们现在来分析这个函数, 也作为前面章节介绍内容的综合分析.
注意 uvm_fault.c 头部的注释, 解释了产生 fault 的几种情况, 这也能加深对前面章节 COW 机制的理解.
uvm_fault() 的主体脉络如下:
begin
loop up for fault page;
check protection -> cow_now;
handle need_copy case, copy amap if we need;
check case0(no amp, no uobj, errr);
A: statbish intrest range, pre-fault, get fault level;
if shadowed (uper level fault)
uvm_anonget();
B: handle loan case (break if we need);
C: handle COW case;
pmap_enter();
update page queue;
else
ask the backing obj to handle it;
D: handle it in a general way if backing obj
do not know how to do;
get uobjpage, ensure it's not PG_RELEASED;
if not promote (case 2A)
fault it directlly
else (case 2B)
get a anon and fill it with data;
add it into amap;
pmap_enter();
update page queue;
A: line 698
一个 fault 的页面周围的页面也很可能在近期 fault, 为了防止过多的内存访问异常拖慢速度, 我们有根据 advise 的设置的范围进行 pre-fault.
首先一大堆代码已确定 pre-fault 的范围, 如果是 wired 的地方, 我们不应该做 pre-fault (narrow == TRUE). 从 788 行开始的代码, 开始了真正的 pre-fault 操作. 其主要方法就是将可以 active 的页面 active 掉, 并填充 pages 数组. 注意 821 行, 如果一个中心页面 (真正 fault 的地方) 能够来到这里, 说明在 amap 中有其相应的表项, 那它肯定是因为基于 amap 的 COW 而 fault 掉的, 因此 shadow = TRUE, fault 在上层 (amap 层).
接着, 根据 fault 的层次, 有 Case1 和 Case 2 两分支. 我们先来看 Case 1 分支, 其代码真正开始在 1028 行.
B: line 1076, handling loan
XXX
C: line 1163, handling COW (case 1B)
如果是 COW 且 anon 的引用数大于 1, 我们就需要创建一个新 anon 以及页面, 复制数据 (uvm_pagecopy()), 把新结点替换进 amap (amap_add). 否则, 我们只需将 fault 位复原而继续使用. XXX. why?
D: line 901
这是属于 Case B 的代码. 我们来到这里, 说明其 obj 的 pager 中没有 pgo_fault 函数自主处理 fault 情况, 我们要使用它的 pgo_get 函数来处理 fault 情况.
我们首先调用 obj 的 pgo_get 函数读取所需的页面数据 (不要忘了我们有做 pre-fault, 所以要取出的不是仅一个页面的数据), pgo_get 会填充 pages 里需要处理 (== NULL) 且能够处理的表项, 激活有效的项 (否则又被换出了), 我们在这里还得到 uobjpage, 即真正 fault 的地方的 page. 注意 uobjpage 不在这里进行写入 pmap 等的处理, 因为在后面, 我们还要再去处理这个页面, 可能还要将它倒回 anon (Case 2B).
底层页面分配
vm_page 是 UVM 硬件无关部分所管理的最小单位和最底层对象. 其声明在 vm_page.h, 除了一些链接属性外 (前面的注释有解释). 还有指向所属的 anon 或 object 的反向指针, 显然, 它们之中只能有一个非 NULL, 还有其对应的物理地址, 以及机器相关的部分.
观察 uvm 结构中与页面分配相关的表项, 我们可以知道其基本原理: page_free 指向若干个 (1 - 2 个, i386 的取值是 2) 个 hash pool, 用于管理空闲的页面, page_active 和 page_inactive 双向列表管理在用的 page.
细看 pgfreelist, 它包含若干的 bucket 用于hash, 而每个 bucket 里有两条链表而不是通常的一条. 一条用于存放未知状态页面, 一条用于组织些空白的页面, 这样能显著加快 zero fill page 的分配速度, 而我们知道, 这样的 zero fill page 在系统中大量存在 (程序的 BSS 段), 因此这是个很大的优化.
我们接着分析最常用的接口 uvm_pagealloc() 和 uvm_pagefree(), uvm_pagealloc() 是 uvm_pagealloc_strat() 的包装宏, 我们直接分析 uvm_pagealloc_strat().
uvm_pagealloc_strat()
函数确定本次分配所用的 bucket 号 (所谓 color). 调用 UVM_KICK_PDAEMON, 该宏在内存紧张的时候唤醒 pagedeamon (真形象) 试图增加空闲内存. 然后确定使用真正的分配函数 uvm_pagealloc_pgfl() 的行为, 然后调用 uvm_pagealloc_pgfl() 获取页面.
uvm_pagealloc_pgfl() 相当简单, 根据当前 color (bucket 号) 试图分配, 不行的话找下一个 bucket, 找到后更新一下审计数据. 完毕.
如果 uvm_pagealloc_strat() 顺利获得页面, 就填写下一次分配时使用的 color, 就将参数提供的信息填入之, 之后反向处理 anon 或 obj 的情况, obj 需要将页面链接进 obj 的页面链表, 最后处理空白页面情况即可完成.
uvm_pagefree()
该函数操作更为简单, (XXX: 先忽略掉 loan 的情况先). 需要注意的是 1412 行, 这里是真正用到 hash 函数的地方, 这是一个根据页面的物理地址做的 hash.
swap 管理
swap 设备管理
XXX: 讲清楚基本原理即可, 翻译 comment
页面换出
页面换出工作由内核守护进程 pagedaemon 完成. (注: 另一个貌似处理页面换出的守护进程是 swapper, 它的任务是在系统资源紧张而某进程睡眠时间很长的时候, 将整个进程换出去, 我们在这里不讨论这个, 这可以算是最古老的 UNIX 系统的遗留). 代码在 uvm_pdaemon.c 中.
我们在看到, uvm_pagealloc_strat() 在遇到系统内存不足 (不一定是不足到分配不出页面) 的时候, 就会唤醒 pagedaemon 进程, 进行页面回收和换出操作.
pagedaemon 的主程序在 197 行 uvm_pageout(). 在 main loop 中, 首先判断 npages 和真正的系统 npages 有什么不同, 它有可能在 pagedaemon sleep 的时候发生改变, 运行 uvmpd_tune() 来调整参数, 在这里我们可以看到 pagedaemon 的目标 (line 182): 另 free 的页面至少在保留页面容量的 4/3.
若未达到目标, 我们就需要运行真正的换出程序 uvmpd_scan() 解决. 函数将先调用主要的 uvmpd_scan_inactive() 来完成, 我们说过 incative page list 里存放的是最近没有操作的页面, 将它们换出去是适当的. 函数首先统计更详细的需求数据, 然后遍历整个链表.
对于每个页面, 系统首先判断它是否适合换出, 如果适合 (line 488) 首先尝试所住所属的 obj 或 anon (这里不能 wait, 否则会死锁). 下面, 若这个不是由 swap 管理的页面 (不是 anon 也不是 aobj), 交给 obj 去释放这个. 否则, 函数首先采取各种办法尽量避免真正 pageout 而空出内存, 比如它是 CLEAN 的, 说明它在内存期间没做过任何操作, 无论是一个 zero fill 新页面还是从 swap 换掉内存的, 我们都可以直接释放它, 在再次需要它的时候正确提供数据. 否则 , 我们先释放其原来在 swap 中的数据, 因为已经不再适用, 然后记录新的 slot 的位置, 如果有需要, 我们继续查找可释放的页面, 而将真正的 I/O 操作推后. 最后, 我们在 719 行做真正的换出 I/O 操作.
回到 uvmpd_scan(), 如果我们的 inactive 页面不够, 就需要遍历 active 链表, 如果 swap 不够而它在 swap 中有映象, 清出在 swap 中的数据, 因为既然它都在 active 里了, swap 的数据显然是没用的. 然后我们让它 inactive, 去迎合系统要求.
页面换入
obj 页面换入
回忆 vm_fault, 如果 fault 是因为缺页, 我们就应该向其 obj 请求数据 --- 这就是页面换入的地方. 我们在上面说过, 如果一个 inactive 的页面属于非 anon 和非 aobj, 就请求其 obj 写入, 然后释放页面, 那么如果我们再访问这个页面, 就会产生一个缺页, 结果是调用该 obj 重新读出该页 --- 这其实就是对非匿名内存的页面换入和换出全过程. 而我们最常见的匿名内存的换入/换出, 基本原理是一样的, 只是稍微复杂罢了. 它的换出有特别的处理(因为还涉及 COW 的 amap 换出的问题), 而它的换入, 也是由一个 obj --- aobj 通过同样的接口进行的, 联系上面的章节就能清楚了解其原理.
amap 页面换入
vm_fault() 主函数的运行是不处理 amap 中的 anon 不在内存的情况的, 观察 vm_fault.c:1038, 它说明, 判断 amap 层的 fault 的前提是 fault 的 anon 在内存内, 函数调用 uvmfault_anonget() 来保证这一点. 该函数检查 anon 的 page, 若它没有 page (line 370), 就要先申请一个页面, 然后用底层的 uvm_swap_get() 在 swap 设备中取得数据.
NetBSD 内存管理系统 UVM 浅析
在线用户
正浏览此版面之用户: 没有注册用户 和 0 访客