知其然也知其所以然，是我們《大內高手》系列一貫做法，本文亦是如此。這裡我不打算講解如何使用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 <sys/ptrace.h>
#include <sys/types.h>
#include <sys/wait.h>
#include <unistd.h>
#include <linux/user.h> /* For user_regs_struct
etc. */
int main(int argc, char *argv[])
{ pid_t traced_process;
struct user_regs_struct regs;
long ins;
if(argc != 2) {
printf("Usage: %s <pid to be traced>\n",
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本身的實現方法。
~~~end~~
