[源码笔记] Linux内核内存检测工具Kmemcheck浅读

Linux内核2.6.31版本发布于2009年9月9日(真是个吉利的日子),其中新加入了两个内核内存管理方面的新工具Kmemcheck和Kmemleak。Kmemcheck工作于内核态,用于检测未初始化等内存非法读写访问并发出警告(类似的编程辅助工具Valgrind也可用于内存检测,但其工作于用户态,对内核态进程无能)。但是由于Kmemcheck会大大地影响内核工作的速度,并消耗较近两倍的内存使用,其将只作为Linux内核的一个调试工具,需要手动开启。

这对于内核开发(如设备驱动程序)者而言,是十分有用的。因为编程习惯或者对未初始化内存的不经意使用(C语言甚至允许访问任意的内存地址),非常可能导致一些难以检查的错误,有时还可能导致系统一直处于无响应状态。Kmemcheck能够帮助定位大多数内存错误的上下文,虽然目前它只支持x86平台,且仍在不断改进中。

1. 实现思路

Kmemcheck记录跟踪内存中每一位的内存状态,并于每次访问时检查其状态是否合法,若判断为非法访问,则给出警告信息。

1.1 分配
当Kmemcheck被开启时,每一块动态申请并要求跟踪的核态内存A都将有一块和其大小相同的影子内存B(其地址记录于每个页描述符的shadow字段中),用于记录A中每个字节的内存状态,这是判断内存访问是否合法的依据:

KMEMCHECK_SHADOW_UNALLOCATED 未分配的(在SLAB中,新分配的slab页面中没有被分配object的部分会被设置成此状态)
KMEMCHECK_SHADOW_UNINITIALIZED 未初始化的(一般情况下,新分配的页面都会被设置成此状态)
KMEMCHECK_SHADOW_FREED 释放的(在SLAB中,当object被释放后,其所占用的内存会被设置成此状态)
KMEMCHECK_SHADOW_INITIALIZED 初始化的(对它的访问是正确的)

以上4中状态,前3种均为非法访问,Kmemcheck会给出相应的警告。

Kmemcheck在页表项的页面属性新定义了一个_PAGE_HIDDEN标志位,在slab_cache中添加SLAB_NOTRACK属性,在GFP中添加GFP_NOTRACK属性。
当分配内存时,A对应页表项中的_PAGE_PRESENT标志位被清零(表示该页不存在,引起一次缺页中断),并置位_PAGE_HIDDEN标志位以区别于真正的缺页中断;B则置位了
GFP_NOTRACK使得其自身不被Kmemcheck跟踪,并且B中的每个字节都会被标志位uninitialized。另外,为了系统的正常运行,关键的内核代买也被SLAB_NOTRACK和__GFP_NOTRACK保护起来,不受Kmemcheck跟踪。

1.2 操作
当对内存读写操作发生时,被Kmemcheck跟踪的内存将发生一次缺页中断,调用do_page_fault(),Kmemcheck在其中置入的钩子函数就会起作用。如果是读操作,则检查对应shadow中的状态是否为initialized,若否,则启动报错程序;如果是写操作,则将对应shadow置为initialized。
检查完成之后,将这些页的_PAGE_PRESENT置位为“存在”,使其能够返回完成原来的操作;并置位TF(X86_EFLAGS_TF)标志位,使得CPU在执行下一条指令进入单步调试状态,并在之后调用的do_debug()中将以上访问页的_PAGE_PRESENT重新置为“不存在”。那么,当下次读写访问到来时,又可以进入Kmencheck检查。

1.3 释放
除了释放跟踪内存A和shadow,还需将其标记为“存在”和“不隐藏”。

2. 技术细节

2.1 内存管理 Kmemcheck检测内存的功能主要通过对照与跟踪内存紧密相关的影子内存实现。影子内存随着跟踪内存分配而分配并初始化,也随着跟踪内存的释放而释放。Kmemcheck中与内存管理相关的核心函数主要位于mm/kmemcheck.c中,涉及跟踪内存的初始化、影子内存的分配和初始化等。

kmemcheck_alloc_shadow(page, order, flags, node) 调用alloc_pages_node()分配相同大小的影子内存,其“不被跟踪”(__GFP_NOTRACK);
将影子页的地址赋予每个对应跟踪页描述符中的shadow字段;
将每个跟踪页置位“不存在”(~_PAGE_PRESENT)和“隐藏”(_PAGE_HIDDEN)。
kmemcheck_free_shadow(page, order) 将每个跟踪页置位“存在”(_PAGE_PRESENT)和“不隐藏”(~_PAGE_HIDDEN);
将每个跟踪页的shadow字段置为NULL;
调用__free_pages()释放对应的影子内存。
kmemcheck_slab_alloc(kmem_cache, gfpflags, object, size) 调用kmemcheck_mark_uninitialized()将跟踪对象所对应的影子内存置位“未初始化”。
(Kmemcheck允许被跟踪页中的部分对象为不被跟踪的,这通过将其影子置位为“初始化”来实现)
kmemcheck_slab_free(kmem_cache, object, size) 调用kmemcheck_mark_freed()将跟踪对象所对应的影子内存置位为“已释放”。
kmemcheck_pagealloc_alloc(*page, order, gfpflags) 调用kmemcheck_alloc_shadow()分配影子内存并标记跟踪内存;
若此内存需被跟踪,则置位其影子为“未初始化”;否则为“初始化”。

在SLAB/SLUB等通用或专用对象分配机制中:
1) kmemcheck_alloc_shadow()被插入到allocate_slab()的新页成功分配之后,分配影子并标识跟踪页(allocate_slab()负责在slab不够用时添加新页并构造新slab)。此后,若slab已被构造函数 初始化则将影子置为“未初始化”,否则置为“未分配”;
2) kmemcheck_slab_alloc()被插入到slab_alloc()的新object成功分配之后,将对应影子置为“未初始化”(slab_alloc()负责为申请的通用或专用对象申请空间);
3) kmemcheck_slab_free()被插入到slab_free()的object释放之后,将对应影子置为“已释放”(slab_free()负责释放已申请的通过或专用对象);
4) kmemcheck_free_shadow()被插入到free_slab()的slab被释放后,将对应影子释放(free_slab()负责释放多余空闲的slab)。

在连续页框分配机制中:
1) kmemcheck_pagealloc_alloc()被插入到alloc_pages_slowpath()连续页分配成功后,分配影子、标识跟踪页并置位影子状态(alloc_pages_slowpath()负责从全局内存池中分配新页);
2) kmemcheck_free_shadow()被插入到__free_pages_ok()和free_hot_cold_page()等页被释放后,将对应影子释放。

在非连续内存区分配机制中(如vmalloc),由于其页框也是通过调用alloc_page()来分配的,因此也可受到Kmemcheck的监控。

那么,通过这些置入内存管理函数中的钩子函数,当一个动态内存申请函数(如kmalloc)被调用时(分配标志中不包含GFP_NOTRACK,GFP_HIGHMEM,对于SLAB内存,cache创建时标志中不包含SLAB_NOTRACK),影子页面就被创建、初始化,而跟踪页面被置位“不存在”和“隐藏”。这样,Kmemcheck就能够结合缺页中断、单步调试等技术跟踪和检查这些内存访问的合法性。当其对应的释放函数(如kfree)被调用时,相应的影子页面被释放,而跟踪页面被置位“存在”和“不隐藏”,使得Kmemcheck停止工作。

2.2 跟踪机制实现
前文提到Kmemcheck通过不断交替标志跟踪页“存在”(kmemcheck_show())和“不存在”(kmemcheck_hide()),使得其对页面的跟踪能始终持续到其被释放。出于进程的并发性、安全性等考虑,Kmemcheck通过kmemcheck_context中的balance字段来同步kmemcheck_show和kmemcheck_hide这一对操作,这是使得Kmemcheck跟踪机制得以顺利工作的关键。核心代码位于/arch/x86/mm/kmemcheck/kmemcheck.c中。

kmemcheck_show_all() 将每个地址对应的页置为“存在”,并刷新TLB
kmemcheck_hide_all() 将每个地址对应的页置为“不存在”,并刷新TLB
kmemcheck_show(regs) 调用kmemcheck_show_all();
balance+1;
置位TF(X86_EFLAGS_TF)标志位,开启单步调试。
kmemcheck_hide(regs) 调用kmemcheck_hide_all();
balance-1,并清空当前跟踪地址;
复位TF标志位,关闭单步调试。

缺页异常处理函数do_page_fault()在大多数情况下只对用户态内存和核态非连续内存区调用,负责为属于进程地址空间但还尚未分配物理页框的页分配物理页框,并交换至物理内存中使得进程可以正常访问(有编程错误而导致的缺页异常不在讨论范围内)。在核态分支中,kmemcheck_fault()调用被插入到正常缺页处理函数vmalloc_fault()之后,包括访问合法性的检查和kmemcheck_show()的调用。之所以选择这个位置,是因为高地址的跟踪页可能被置换出物理内存,插在正常缺页处理之前会引起页面交换的混乱,访问到不相称的内存。

在以上的操作中,为了完成缺页中断使得正常访问得以进行,跟踪页被置为“存在”,那么在后续的操作中,其必须被再次置为“不存在”,才能让Kmemcheck的内存检查得以重复实现。在x86体系结构中,正常情况下指令是乱序执行的。为了避免在重置标志位前跟踪页中的其他地址被再次访问,Kmemcheck在置位“存在”之时开启了CPU的单步调试。这样,CPU就陷入了调试陷阱(Debug Trap),在处理函数do_debug()中,kmemcheck_trap()被调用,其在检查balance值的合法性后,调用kmemcheck_hide()完成单次检测操作标识符的复位。

2.3 读写合法检查
Kmemcheck中的读写合法检查通过对照影子页中对应地址的内存状态值来实现,其核心函数为kmemcheck_access(),位于/arch/x86/mm/kmemcheck/kmemcheck.c中。其流程大致如下:
       a. 检查本次kmemcheck_access的调用合法性(是否与另一kmemcheck_access调用冲突);
       b. 调用kmemcheck_opcode_decode解码指令;
       c. 根据操作码执行不同的合法性检查:读指令执行kmemcheck_read,写指令执行kmemcheck_write,其余还包括一些特殊指令如movs、cmps等,这些特殊指令目前还不甚完善,故不作讨论。

kmemcheck_read_strict(reg, addr, size) 此函数检查不超过页边界的读操作。
检查对应影子中记录的内存状态是否合法;
如有错,则记录错误信息、出错上下文等;
标记本次检查过的内存影子为“初始化”,避免二次报错。
kmemcheck_read(reg, addr, size) 此函数通过将需要检查的地址段按页切割,并调用kmemcheck_read_strict()检查其合法性
kmemcheck_write_strict(reg, addr, size) 此函数处理不超过页边界的写操作,将其对应影子标识为“初始化”。
kmemcheck_write(reg, addr, size) 此函数通过将需要检查的地址段按页切割,并调用kmemcheck_write_strict()处理。

2.4 错误处理报告 对于捕获到的内存非法读写,Kmemcheck调用kmemcheck_error_save()将其存储在结构体kmemcheck_error的形式存放在一个循环缓冲区error_fifo中,包括警告类型、引发警告的内存地址及其访问长度、各寄存器的值和stack trace,同时还将访问地址附近的跟踪页和其对应影子页拷贝保存在记录中。此后,将预先设置好的一个tasklet(负责错误处理)插入到当前CPU的tasklet队列中,然后去触发一个软中断。这样,当注册的tasklet被调度执行时,会将循环缓冲区中所有的记录都打印出来。其代码位于/arch/x86/mm/kmemcheck/error.c中。

作为一个新加入内核的补丁工具,Kmemcheck存在很多不完善的地方,比如movs指令所触发的kmemcheck_copy()操作虽然包含源地址和目标地址两个操作却只能给出一次警告等等。因此,Kmemcheck的代码中还嵌有很多自身bug的发现和记录代码,与捕获错误共用同一套报告方法和数据结构。

2.5 内核选项配置
由于Kmemcheck启用的代价很高(需要近2倍的内存并降低运行速度),它被严格地限定为linux内核的debug工具,在普通模式下是默认不被开启的。只有当程序员需要调试内核代码时,才可手动开启。
下面例举了重新编译内核时选项中针对 Kmemcheck 的配置选项,以及它们应该被设置的值(或推荐值):

CONFIG_CC_OPTIMIZE_FOR_SIZE=n 禁止gcc对数据长度进行优化。
例如在32位的机器中,为了提高内存访问速度,gcc 可能会将一些16位的数据访问提升至32位(真正使用时会舍弃高16位),这样kmemcheck 可能就会对高16位中数据内容访问发出警告(这种警告成为伪警告)。这个选项是配置kmemcheck的前提,否则kmemcheck不会出现在配置选项中。
默认是y,在选项”General setup”中。
CONFIG_SLAB=y or CONFIG_SLUB=y 使用slab 或者slub 机制。
默认是CONFIG_SLUB=y,在选项”General setup” 中。
CONFIG_FUNCTION_TRACER=n 防止嵌套的页面异常。
默认是n,在选项”General setup”中。
CONFIG_DEBUG_PAGEALLOC=n 关闭页面分配调试功能。
默认是 n,在选项”Kernel hacking”中。
CONFIG_DEBUG_INFO=y (**推荐值**) 打开内核调试信息,方便内核调试。
在选项”Kernel hacking” 中。
CONFIG_KMEMCHECK=y (必然**推荐值**) 决定内核是否包含kmemcheck 功能。
在选项”Kernel hacking” 中。
CONFIGKMEMCHECK[DISABLED|ENABLED| ONESHOT]_BY_DEFAULT 定义Kmemcheck 在机器启动时的状态。
DISABLED为不启动,ENABLED为启动但它会降低启动的速度,ONESHOT 将在第一次警告之后关闭Kmemcheck功能。Kmemcheck的状态是可以在系统启动后通过修改/proc/sys/kernel/kmemcheck的值来进行动态调整的。
默认是ENABLED,在选项”Kernel hacking” 中。
CONFIG_KMEMCHECK_QUEUE_SIZE 出错循环缓冲区大小,默认是64,即最多一次可以保存64条警告记录,推荐保留默认值。
CONFIG_KMEMCHECK_SHADOW_COPY_SHIFT 当发生警告时,保存下来的内存数据大小,默认是5,即可以保存32字节的数据,推荐保留默认值。
CONFIG_KMEMCHECK_PARTIAL_OK 为了解决gcc对数据长度的优化,默认是y,推荐保留默认值。
CONFIG_KMEMCHECK_BITOPS_OK 针对位域的访问,默认是n,推荐保留默认值(如果需要用到Kmemcheck来对位域的访问进行跟踪,推荐使用其提供的Bitfield annotations)。

 

3. 验证实验

为了验证Kmemcheck的性能,我们编写了几种核态下非法访问内存的例子,并在linux2.6.31版本下开启Kmemcheck功能调试。

系统环境:
WindowXP sp3 + VMware® Workstation 7.0 + Fedora 12 (v2.6.31) + gcc 4.4.2

3.1 alloc_page 先用alloc_pages分配了两个页面大小的内存,然后在未初始化的情况下对其中的内容进行访问。Kmemcheck给出内存未初始化警告信息(即KMEMCHECK_SHADOW_UNINITIALIZED类型的错误信息)。

部分代码示意:
  code01_thumb16

Kmemcheck给出的警告信息:
 ![re01[5]](http://lh5.ggpht.com/_NFbnZk4IksM/TKQ80LssPUI/AAAAAAAAAFs/zn2ftUFpkKQ/s1600-h/re01%5B5%5D%5B2%5D.jpg)
其中,A行给出非法访问的内存地址和错误类型;
B行给出了跟踪页中访问地址附近的32个字节;
C行给出了对应影子页上这32个字节的内存状态,u表示KMEMCHECK_SHADOW_UNINITIALIZED,a表示KMEMCHECK_SHADOW_UNALLOCATED,f表示KMEMCHECK_SHADOW_FREED;
D行指向非法访问内存所在的位置;
E行以下记录的是当时stack trace和寄存器信息,其中EIP记录引发警告的指令地址。

3.2 slab
先创建了一个slab cache,然后对slab中未分配的对象进行访问。Kmemcheck会发出内存未分配警告信息(即KMEMCHECK_SHADOW_UNALLOCATED类型的错误信息)。

部分代码示意:
 code02_thumb2

Kmemcheck给出的警告信息:
 re02_thumb2

3.3 kmalloc 先用kmalloc分配内存,完毕后释放该内存,然后再去访问被释放了的内存空间。Kmemcheck给出访问内存已释放警告信息(即 KMEMCHECK_SHADOW_FREED 类型的错误信息)。

部分代码示意:
 code03_thumb2

Kmemcheck给出的警告信息:
 ![re03[4]](http://lh5.ggpht.com/_NFbnZk4IksM/TKQ86P1884I/AAAAAAAAAGM/BtWd_bmtDQ4/s1600-h/re03%5B4%5D%5B2%5D.jpg)

4. 总结

Kmemcheck作为开源的测试工具,其性能是完全可以接受的。它能够检测出对动态分配的核态的未初始化、未分配和已释放内存的非法访问,但偶尔也会给出伪警告信息。虽然目前,Kmemcheck还在不断完善中,相关指令的检测处理还不全面,对其他体系平台的支撑还有待探究。并且由于其与内存、调度、进程管理、中断处理等其他子系统的关系非常紧密,Kmemcheck的稳定性受到很多外来因素的影响。但是无疑,它的检测过程显得十分大胆、有趣,而且有效。

最后,引用一名知名的linux内核开发者Ingo Molnár对Kmemcheck的评价:
it should also be made clear that not only does kmemcheck consume half of the RAM to do byte granular tracking of the other half of RAM, it’s also slow, very slow, because almost every kernel-space instruction will generate a pagefault and then it will be single-stepped and it takes a debug fault as well. That’s of course totally crazy, but that’s also OK and it’s what makes the feature so interesting and powerful.

5. 参考资料

来自IBM Linux技术文档库的文章《Linux 内核内存检测工具 - Kmemcheck》及相关
源码来源:http://lxr.linux.no/ (2.6.31)
深入理解LINUX内核》一书