分类： LINUX
2009-01-06 20:31:14
知其然也知其所以然，是我们《大内高手》系列一贯做法，本文亦是如此。这里我不打算讲解如何使用boundschecker、purify、valgrind或者gdb，使用这些工具非常简单，讲解它们只是多此一举。相反，我们要研究一下这些工具的实现原理。
本文将从应用程序、编译器和调试器三个层次来讲解，在不同的层次，有不同的方法，这些方法有各自己的长处和局限。了解这些知识，一方面满足一下新手的好奇心，另一方面也可能有用得着的时候。
从应用程序的角度
最好的情况是从设计到编码都扎扎实实的，避免把错误引入到程序中来，这才是解决问题的根本之道。问题在于，理想情况并不存在，现实中存在着大量有内存错误的程序，如果内存错误很容易避免，JAVA/C#的优势将不会那么突出了。
对于内存错误，应用程序自己能做的非常有限。但由于这类内存错误非常典型，所占比例非常大，所付出的努力与所得的回报相比是非常划算的，仍然值得研究。
前面我们讲了，堆里面的内存是由内存管理器管理的。从应用程序的角度来看，我们能做到的就是打内存管理器的主意。其实原理很简单：
对付内存泄露。重载内存管理函数，在分配时，把这块内存的记录到一个链表中，在释放时，从链表中删除吧，在程序退出时，检查链表是否为空，如果不为空，则说明有内存泄露，否则说明没有泄露。当然，为了查出是哪里的泄露，在链表还要记录是谁分配的，通常记录文件名和行号就行了。
对付内存越界/野指针。对这两者，我们只能检查一些典型的情况，对其它一些情况无能为力，但效果仍然不错。其方法如下(源于《Comparing and contrasting the runtime error detection technologies》)：
l 首尾在加保护边界值
|
Header |
Leading guard(0xFC) |
User data(0xEB) |
Tailing guard(0xFC) |
在内存分配时，内存管理器按如上结构填充分配出来的内存。其中Header是管理器自己用的，前后各有几个字节的guard数据，它们的值是固定的。当内存释放时，内存管理器检查这些guard数据是否被修改，如果被修改，说明有写越界。
它的工作机制注定了有它的局限性: 只能检查写越界，不能检查读越界，而且只能检查连续性的写越界，对于跳跃性的写越界无能为力。
l 填充空闲内存
|
空闲内存(0xDD) |
内存被释放之后，它的内容填充成固定的值。这样，从指针指向的内存的数据，可以大致判断这个指针是否是野指针。
它同样有它的局限：程序要主动判断才行。如果野指针指向的内存立即被重新分配了，它又被填充成前面那个结构，这时也无法检查出来。
从编译器的角度
boundschecker和purify的实现都可以归于编译器一级。前者采用一种称为CTI(compile-time instrumentation)的技术。VC的编译不是要分几个阶段吗？boundschecker在预处理和编译两个阶段之间，对源文件进行修改。它对所有内存分配释放、内存读写、指针赋值和指针计算等所有内存相关的操作进行分析，并插入自己的代码。比如：
|
Before if (m_hsession) gblHandles->ReleaseUserHandle( m_hsession ); if (m_dberr) delete m_dberr; After if (m_hsession) { _Insight_stack_call(0); gblHandles->ReleaseUserHandle(m_hsession); _Insight_after_call(); } _Insight_ptra_check(1994, (void **) &m_dberr, (void *) m_dberr); if (m_dberr) { _Insight_deletea(1994, (void **) &m_dberr, (void *) m_dberr, 0); delete m_dberr; } |
Purify则采用一种称为OCI(object code insertion)的技术。不同的是，它对可执行文件的每条指令进行分析，找出所有内存分配释放、内存读写、指针赋值和指针计算等所有内存相关的操作，用自己的指令代替原始的指令。
boundschecker和purify是商业软件，它们的实现是保密的，甚至拥有专利的，无法对其研究，只能找一些皮毛性的介绍。无论是CTI还是OCI这样的名称，多少有些神秘感。其实它们的实现原理并不复杂，通过对valgrind和gcc的bounds checker扩展进行一些粗浅的研究，我们可以知道它们的大致原理。
gcc的bounds checker基本上可以与boundschecker对应起来，都是对源代码进行修改，以达到控制内存操作功能，如malloc/free等内存管理函数、memcpy/strcpy/memset等内存读取函数和指针运算等。Valgrind则与Purify类似，都是通过对目标代码进行修改，来达到同样的目的。
Valgrind对可执行文件进行修改，所以不需要重新编译程序。但它并不是在执行前对可执行文件和所有相关的共享库进行一次性修改，而是和应用程序在同一个进程中运行，动态的修改即将执行的下一段代码。
Valgrind是插件式设计的。Core部分负责对应用程序的整体控制，并把即将修改的代码，转换成一种中间格式，这种格式类似于RISC指令，然后把中间代码传给插件。插件根据要求对中间代码修改，然后把修改后的结果交给core。core接下来把修改后的中间代码转换成原始的x86指令，并执行它。
由此可见，无论是boundschecker、purify、gcc的bounds checker，还是Valgrind，修改源代码也罢，修改二进制也罢，都是代码进行修改。究竟要修改什么，修改成什么样子呢？别急，下面我们就要来介绍：
管理所有内存块。无论是堆、栈还是全局变量，只要有指针引用它，它就被记录到一个全局表中。记录的信息包括内存块的起始地址和大小等。要做到这一点并不难：对于在堆里分配的动态内存，可以通过重载内存管理函数来实现。对于全局变量等静态内存，可以从符号表中得到这些信息。
拦截所有的指针计算。对于指针进行乘除等运算通常意义不大，最常见运算是对指针加减一个偏移量，如++p、p=p+n、p=a[n]等。所有这些有意义的指针操作，都要受到检查。不再是由一条简单的汇编指令来完成，而是由一个函数来完成。
有了以上两点保证，要检查内存错误就非常容易了：比如要检查++p是否有效，首先在全局表中查找p指向的内存块，如果没有找到，说明p是野指针。如果找到了，再检查p+1是否在这块内存范围内，如果不是，那就是越界访问，否则是正常的了。怎么样，简单吧，无论是全局内存、堆还是栈，无论是读还是写，无一能够逃过出工具的法眼。
代码赏析(源于tcc)：
对指针运算进行检查：
|
void *__bound_ptr_add(void *p, int offset) { unsigned long addr = (unsigned long)p; BoundEntry *e; #if defined(BOUND_DEBUG) printf("add: 0x%x %d\n", (int)p, offset); #endif e = __bound_t1[addr >> (BOUND_T2_BITS + BOUND_T3_BITS)]; e = (BoundEntry *)((char *)e + ((addr >> (BOUND_T3_BITS - BOUND_E_BITS)) & ((BOUND_T2_SIZE - 1) << BOUND_E_BITS))); addr -= e->start; if (addr > e->size) { e = __bound_find_region(e, p); addr = (unsigned long)p - e->start; } addr += offset; if (addr > e->size) return INVALID_POINTER; /* return an invalid pointer */ return p + offset; } static void __bound_check(const void *p, size_t size) { if (size == 0) return; p = __bound_ptr_add((void *)p, size); if (p == INVALID_POINTER) bound_error("invalid pointer"); } |
重载内存管理函数：
|
void *__bound_malloc(size_t size, const void *caller) { void *ptr; /* we allocate one more byte to ensure the regions will be separated by at least one byte. With the glibc malloc, it may be in fact not necessary */ ptr = libc_malloc(size + 1); if (!ptr) return NULL; __bound_new_region(ptr, size); return ptr; } void __bound_free(void *ptr, const void *caller) { if (ptr == NULL) return; if (__bound_delete_region(ptr) != 0) bound_error("freeing invalid region"); libc_free(ptr); } |
重载内存操作函数：
|
void *__bound_memcpy(void *dst, const void *src, size_t size) { __bound_check(dst, size); __bound_check(src, size); /* check also region overlap */ if (src >= dst && src < dst + size) bound_error("overlapping regions in memcpy()"); return memcpy(dst, src, size); } |
从调试器的角度
现在有OS的支持，实现一个调试器变得非常简单，至少原理不再神秘。这里我们简要介绍一下win32和linux中的调试器实现原理。
在Win32下，实现调试器主要通过两个函数：WaitForDebugEvent和ContinueDebugEvent。下面是一个调试器的基本模型(源于: 《Debugging Applications for Microsoft .NET and Microsoft Windows》)
|
void main ( void ) { CreateProcess ( ..., DEBUG_ONLY_THIS_PROCESS ,... ) ; while ( 1 == WaitForDebugEvent ( ... ) ) { if ( EXIT_PROCESS ) { break ; } ContinueDebugEvent ( ... ) ; } } |
由调试器起动被调试的进程，并指定DEBUG_ONLY_THIS_PROCESS标志。按Win32下事件驱动的一贯原则，由被调试的进程主动上报调试事件，调试器然后做相应的处理。
在linux下，实现调试器只要一个函数就行了：ptrace。下面是个简单示例：(源于《Playing with ptrace》)。
|
#include #include #include #include #include etc. */ int main(int argc, char *argv[]) { pid_t traced_process; struct user_regs_struct regs; long ins; if(argc != 2) { printf("Usage: %s argv[0], argv[1]); exit(1); } traced_process = atoi(argv[1]); ptrace(PTRACE_ATTACH, traced_process, NULL, NULL); wait(NULL); ptrace(PTRACE_GETREGS, traced_process, NULL, ®s); ins = ptrace(PTRACE_PEEKTEXT, traced_process, regs.eip, NULL); printf("EIP: %lx Instruction executed: %lx\n", regs.eip, ins); ptrace(PTRACE_DETACH, traced_process, NULL, NULL); return 0; } |
由于篇幅有限，这里对于调试器的实现不作深入讨论，主要是给新手指一个方向。以后若有时间，再写个专题来介绍linux下的调试器和ptrace本身的实现方法。
