内存越界检测方案讨论

chenyu105

自己写的网卡驱动代码里，总有一些skb越界操作的问题。
skb是slab分配出来的，所以给内核配置了CONFIG_DEBUG_SLAB，
但是这个选项只是给slab对象的前后加了红区(red zone)，以及在刚分配slab对象前，将其poison，
这两个方案都只能检查事后内存被改的情况。

为了抓到第一现场，封装了string.c里的类C库接口。
以memcpy为例，假设驱动代码里有一句memcpy(dest,src,len)， 那么就会检测区间
[dest,dest+len] 是否覆盖掉了别人的slab对象区间。  

场景：假设系统中此时通过slab分配出来的对象集合有：

[a1,b1]  [a2,b2]  ... [an,bn]

检测越界时，如果发现[dest,dest+len]  与 [ai,bi]有重叠，并且不是[ai,bi]的子区间，那说明[dest,dest+len]这次memcpy是一次非法的越界拷贝。

即满足(dest <ai )&& (dest+len >ai) && (dest+len <bi]  （前重叠）
            
   (dest >ai) && (dest <bi ) && (dest +len >bi)  （后重叠）
就是一次越界memcpy。

                             |ai----------------------------------bi|                                     //某个slab对象区间

                  |dest-----------dest+len|                                                                 //前重叠

                                                         |dest-------------------------dest+len|    //后重叠


slab对象区间，以ai（对象虚拟地址）为主key、bi为辅助信息，保存在红黑树中；
每次memcpy时，以dest为key去查找红黑树里大于dest的第一个节点，再判断dest_len是否小于bi，有的话就是前覆盖；
如果没有，则再以dest为key去查找红黑树里小于dest的第一个节点，再判断dest_len是否大于bi，有的话就是后覆盖。
因此最坏情况下，可能要遍历两次红黑树才能判断是否存在越界。
当系统处于高负载时，有大量slab对象的分配和释放，这个检测机制运行起来后系统非常慢。
再加上红黑树可能有许多的树旋转操作，导致比较耗时。


从上面的流程可以看出，如果通过一次搜索，能找到大于dest和小于dest的两个节点，那么效率就会提升一倍。
不知道哪种结构可以满足不？ 大家有没有其他的方案和思路可以逮到越界第一现场？

mordorwww

木有什么好办法，只能老老实实调试，检查代码

humjb_1983

chenyu105 发表于 2013-11-30 15:09
自己写的网卡驱动代码里，总有一些skb越界操作的问题。
skb是slab分配出来的，所以给内核配置了CONFIG_DEB ...

印象中有一种内存越界检测思路是，将红黑区内存属性设置为只读，但有越界写的时候，就会触发GP异常，通过捕获异常应该就能捕捉到了~

openspace

不知道用 B tree 之类的会不会操作损耗少一些

hejianet

楼主看看线段树 interval tree

chenyu105

回复 3# humjb_1983

恩 是个好方法，这一块跟架构相关吧，开源内核有吗？

   

chenyu105

回复 4# openspace

    消耗应该不是在树结构上

humjb_1983

chenyu105 发表于 2013-12-02 18:13
回复 3# humjb_1983

恩 是个好方法，这一块跟架构相关吧，开源内核有吗？

跟架构无关，查了一下，有个开源的工具mudflap，可以进行内存越界的实时检测，基本原理是：封装内存操作函数，如malloc，在封装函数中注册对象，并在编译时插入指令监控内存的读写操作，在操作内存时，实时检查相应的地址是否已有对象，以确认是否有越界操作。该工具依赖于编译器提供的插入监控指令的机制，由于每次内存操作都要进行检查，效率也会比较低。

chenyu105

回复 9# humjb_1983

内核态的越界，我刚才查了一个kmemcheck，正在看他的使用方法。
   

chenyu105

回复 5# hejianet


    我在水木社区也问了一下，http://www.newsmth.net/nForum/#!article/Algorithm/57822