『壹』 調試驅動程序的高效方法
驅動程序開發的一個重大難點就是不易調試。本文目的就是介紹驅動開發中常用的幾種直接和間接的調試手段，它們是：
1、利用printk
2、查看OOP消息
3、利用strace
4、利用內核內置的hacking選項
5、利用ioctl方法
6、利用/proc 文件系統
7、使用kgdb
前兩種如下：
一、利用printk
這是驅動開發中最朴實無華，同時也是最常用和有效的手段。scull驅動的main.c第338行如下，就是使用printk進行調試的例子，這樣的例子相信大家在閱讀驅動源碼時隨處可見。
338 // printk(KERN_ALERT "wakeup by signal in process %d\n", current->pid);
printk的功能與我們經常在應用程序中使用的printf是一樣的，不同之處在於printk可以在列印字元串前面加上內核定義的宏，例如上面例子中的KERN_ALERT（注意：宏與字元串之間沒有逗號）。
#define KERN_EMERG "<0>"
#define KERN_ALERT "<1>"
#define KERN_CRIT "<2>"
#define KERN_ERR "<3>"
#define KERN_WARNING "<4>"
#define KERN_NOTICE "<5>"
#define KERN_INFO "<6>"
#define KERN_DEBUG "<7>"
#define DEFAULT_CONSOLE_LOGLEVEL 7
這個宏是用來定義需要列印的字元串的級別。值越小，級別越高。內核中有個參數用來控制是否將printk列印的字元串輸出到控制台（屏幕或者/sys/log/syslog日誌文件）
# cat /proc/sys/kernel/printk
6 4 1 7
第一個6表示級別高於（小於）6的消息才會被輸出到控制台，第二個4表示如果調用printk時沒有指定消息級別（宏）則消息的級別為4，第三個1表示接受的最高（最小）級別是1，第四個7表示系統啟動時第一個6原來的初值是7。
因此，如果你發現在控制台上看不到你程序中某些printk的輸出，請使用echo 8 > /proc/sys/kernel/printk來解決。
在復雜驅動的開發過程中，為了調試會在源碼中加入成百上千的printk語句。而當調試完畢形成最終產品的時候必然會將這些printk語句刪除想想驅動的使用者而不是開發者吧。記住：己所不欲，勿施於人），這個工作量是不小的。最要命的是，如果我們將調試用的printk語句刪除後，用戶又報告驅動有bug，所以我們又不得不手工將這些上千條的printk語句再重新加上。oh，my god，殺了我吧。所以，我們需要一種能方便地打開和關閉調試信息的手段。哪裡能找到這種手段呢？哈哈，遠在天邊，近在眼前。看看scull驅動或者leds驅動的源代碼吧！
#define LEDS_DEBUG
#undef PDEBUG
#ifdef LEDS_DEBUG
#ifdef __KERNEL__
#define PDEBUG(fmt, args…) printk( KERN_EMERG "leds: " fmt, ## args)
#else
#define PDEBUG(fmt, args…) fprintf(stderr, fmt, ## args)
#endif
#else
#define PDEBUG(fmt, args…)
#endif
#undef PDEBUGG
#define PDEBUGG(fmt, args…)
這樣一來，在開發驅動的過程中，如果想列印調試消息，我們就可以用PDEBUG("address of i_cdev is %p\n", inode->i_cdev);，如果不想看到該調試消息，就只需要簡單的將PDEBUG改為PDEBUGG即可。而當我們調試完畢形成最終產品時，只需要簡單地將第1行注釋掉即可。
上邊那一段代碼中的__KERNEL__是內核中定義的宏，當我們編譯內核（包括模塊）時，它會被定義。當然如果你不明白代碼中的…和##是什麼意思的話，就請認真查閱一下gcc關於預處理部分的資料吧！如果你實在太懶不願意去查閱的話，那就充當VC工程師把上面的代碼到你的代碼中去吧。
二、查看OOP消息
OOP意為驚訝。當你的驅動有問題，內核不驚訝才怪：嘿！小子，你干嗎亂來！好吧，就讓我們來看看內核是如何驚訝的。
根據faulty.c（單擊下載）編譯出faulty.ko，並 insmod faulty.ko。執行echo yang >/dev/faulty，結果內核就驚訝了。內核為什麼會驚訝呢？因為faulty驅動的write函數執行了*(int *)0 = 0，向內存0地址寫入，這是內核絕對不會容許的。
52 ssize_t faulty_write (struct file *filp, const char __user *buf, size_t count,
53 loff_t *pos)
54 {
55
56 *(int *)0 = 0;
57 return 0;
58 }
1 Unable to handle kernel NULL pointer dereference at virtual address 00000000
2 pgd = c3894000
3 [00000000] *pgd=33830031, *pte=00000000, *ppte=00000000
4 Internal error: Oops: 817 [#1] PREEMPT
5 Moles linked in: faulty scull
6 CPU: 0 Not tainted (2.6.22.6 #4)
7 PC is at faulty_write+0×10/0×18 [faulty]
8 LR is at vfs_write+0xc4/0×148
9 pc : [] lr : [] psr: a0000013
10 sp : c3871f44 ip : c3871f54 fp : c3871f50
11 r10: 4021765c r9 : c3870000 r8 : 00000000
12 r7 : 00000004 r6 : c3871f78 r5 : 40016000 r4 : c38e5160
13 r3 : c3871f78 r2 : 00000004 r1 : 40016000 r0 : 00000000
14 Flags: NzCv IRQs on FIQs on Mode SVC_32 Segment user
15 Control: c000717f Table: 33894000 DAC: 00000015
16 Process sh (pid: 745, stack limit = 0xc3870258)
17 Stack: (0xc3871f44 to 0xc3872000)
18 1f40: c3871f74 c3871f54 c0088eb8 bf00608c 00000004 c38e5180 c38e5160
19 1f60: c3871f78 00000000 c3871fa4 c3871f78 c0088ffc c0088e04 00000000 00000000
20 1f80: 00000000 00000004 40016000 40215730 00000004 c002c0e4 00000000 c3871fa8
21 1fa0: c002bf40 c0088fc0 00000004 40016000 00000001 40016000 00000004 00000000
22 1fc0: 00000004 40016000 40215730 00000004 00000001 00000000 4021765c 00000000
23 1fe0: 00000000 bea60964 0000266c 401adb40 60000010 00000001 00000000 00000000
24 Backtrace:
25 [] (faulty_write+0×0/0×18 [faulty]) from [] (vfs_write+0xc4/0×148)
26 [] (vfs_write+0×0/0×148) from [] (sys_write+0x4c/0×74)
27 r7:00000000 r6:c3871f78 r5:c38e5160 r4:c38e5180
28 [] (sys_write+0×0/0×74) from [] (ret_fast_syscall+0×0/0x2c)
29 r8:c002c0e4 r7:00000004 r6:40215730 r5:40016000 r4:00000004
30 Code: e1a0c00d e92dd800 e24cb004 e3a00000 (e5800000)
1行驚訝的原因，也就是報告出錯的原因；
2-4行是OOP信息序號；
5行是出錯時內核已載入模塊；
6行是發生錯誤的CPU序號；
7-15行是發生錯誤的位置，以及當時CPU各個寄存器的值，這最有利於我們找出問題所在地；
16行是當前進程的名字及進程ID
17-23行是出錯時，棧內的內容
24-29行是棧回溯信息，可看出直到出錯時的函數遞進調用關系（確保CONFIG_FRAME_POINTER被定義）
30行是出錯指令及其附近指令的機器碼，出錯指令本身在小括弧中
反匯編faulty.ko（ arm-linux-objmp -D faulty.ko > faulty.dis ；cat faulty.dis）可以看到如下的語句如下：
0000007c :
7c: e1a0c00d mov ip, sp
80: e92dd800 stmdb sp!, {fp, ip, lr, pc}
84: e24cb004 sub fp, ip, #4 ; 0×4
88: e3a00000 mov r0, #0 ; 0×0
8c: e5800000 str r0, [r0]
90: e89da800 ldmia sp, {fp, sp, pc}
定位出錯位置以及獲取相關信息的過程：
9 pc : [] lr : [] psr: a0000013
25 [] (faulty_write+0×0/0×18 [faulty]) from [] (vfs_write+0xc4/0×148)
26 [] (vfs_write+0×0/0×148) from [] (sys_write+0x4c/0×74)
出錯代碼是faulty_write函數中的第5條指令（(0xbf00608c-0xbf00607c)/4+1=5），該函數的首地址是0xbf00607c，該函數總共6條指令（0×18），該函數是被0xc0088eb8的前一條指令調用的（即：函數返回地址是0xc0088eb8。這一點可以從出錯時lr的值正好等於0xc0088eb8得到印證）。調用該函數的指令是vfs_write的第49條（0xc4/4=49）指令。
達到出錯處的函數調用流程是：write(用戶空間的系統調用)–>sys_write–>vfs_write–>faulty_write
OOP消息不僅讓我定位了出錯的地方，更讓我驚喜的是，它讓我知道了一些秘密：1、gcc中fp到底有何用處？2、為什麼gcc編譯任何函數的時候，總是要把3條看上去傻傻的指令放在整個函數的最開始？3、內核和gdb是如何知道函數調用棧順序，並使用函數的名字而不是地址？ 4、我如何才能知道各個函數入棧的內容？哈哈，我漸漸喜歡上了讓內核驚訝，那就再看一次內核驚訝吧。
執行 cat /dev/faulty，內核又再一次驚訝！
1 Unable to handle kernel NULL pointer dereference at virtual address 0000000b
2 pgd = c3a88000
3 [0000000b] *pgd=33a79031, *pte=00000000, *ppte=00000000
4 Internal error: Oops: 13 [#2] PREEMPT
5 Moles linked in: faulty
6 CPU: 0 Not tainted (2.6.22.6 #4)
7 PC is at vfs_read+0xe0/0×140
8 LR is at 0xffffffff
9 pc : [] lr : [] psr: 20000013
10 sp : c38d9f54 ip : 0000001c fp : ffffffff
11 r10: 00000001 r9 : c38d8000 r8 : 00000000
12 r7 : 00000004 r6 : ffffffff r5 : ffffffff r4 : ffffffff
13 r3 : ffffffff r2 : 00000000 r1 : c38d9f38 r0 : 00000004
14 Flags: nzCv IRQs on FIQs on Mode SVC_32 Segment user
15 Control: c000717f Table: 33a88000 DAC: 00000015
16 Process cat (pid: 767, stack limit = 0xc38d8258)
17 Stack: (0xc38d9f54 to 0xc38da000)
18 9f40: 00002000 c3c105a0 c3c10580
19 9f60: c38d9f78 00000000 c38d9fa4 c38d9f78 c0088f88 c0088bb4 00000000 00000000
20 9f80: 00000000 00002000 bef07c80 00000003 00000003 c002c0e4 00000000 c38d9fa8
21 9fa0: c002bf40 c0088f4c 00002000 bef07c80 00000003 bef07c80 00002000 00000000
22 9fc0: 00002000 bef07c80 00000003 00000000 00000000 00000001 00000001 00000003
23 9fe0: 00000000 bef07c6c 0000266c 401adab0 60000010 00000003 00000000 00000000
24 Backtrace: invalid frame pointer 0xffffffff
25 Code: ebffff86 e3500000 e1a07000 da000015 (e594500c)
26 Segmentation fault
不過這次驚訝卻令人大為不解。OOP竟然說出錯的地方在vfs_read（要知道它可是大拿們千錘百煉的內核代碼），這怎麼可能？哈哈，萬能的內核也不能追蹤函數調用棧了，這是為什麼？其實問題出在faulty_read的43行，它導致入棧的r4、r5、r6、fp全部變為了0xffffffff，ip、lr的值未變，這樣一來faulty_read函數能夠成功返回到它的調用者——vfs_read。但是可憐的vfs_read（忠實的APTCS規則遵守者）並不知道它的r4、r5、r6已經被萬惡的faulty_read改變，這樣下去vfs_read命運就可想而知了——必死無疑！雖然內核很有能力，但缺少了正確的fp的幫助，它也無法追蹤函數調用棧。
36 ssize_t faulty_read(struct file *filp, char __user *buf,
37 size_t count, loff_t *pos)
38 {
39 int ret;
40 char stack_buf[4];
41
42
43 memset(stack_buf, 0xff, 20);
44 if (count > 4)
45 count = 4;
46 ret = _to_user(buf, stack_buf, count);
47 if (!ret)
48 return count;
49 return ret;
50 }
00000000 :
0: e1a0c00d mov ip, sp
4: e92dd870 stmdb sp!, {r4, r5, r6, fp, ip, lr, pc}
8: e24cb004 sub fp, ip, #4 ; 0×4
c: e24dd004 sub sp, sp, #4 ; 0×4，這里為stack_buf[]在棧上分配1個字的空間，局部變數ret使用寄存器存儲，因此就不在棧上分配空間了
10: e24b501c sub r5, fp, #28 ; 0x1c
14: e1a04001 mov r4, r1
18: e1a06002 mov r6, r2
1c: e3a010ff mov r1, #255 ; 0xff
20: e3a02014 mov r2, #20 ; 0×14
24: e1a00005 mov r0, r5
28: ebfffffe bl 28 //這里在調用memset
78: e89da878 ldmia sp, {r3, r4, r5, r6, fp, sp, pc}
這次OOP，深刻地認識到：
內核能力超強，但它不是，也不可能是萬能的。所以即使你能力再強，也要和你的team member搞好關系，否則在關鍵時候你會倒霉的；
出錯的是faulty_read，vfs_read卻做了替罪羊。所以人不要被表面現象所迷惑，要深入看本質；
內核本來超級健壯，可是你寫的驅動是內核的組成部分，由於它出錯，結果整體崩盤。所以當你加入一個團隊的時候一定要告誡自己，雖然你的角色也許並不重要，但你的疏忽大意將足以令整個非常牛X的團隊崩盤。反過來說，當你是team leader的時候，在選團隊成員的時候一定要慎重、慎重、再慎重，即使他只是一個小角色。
千萬別惹堆棧，它一旦出問題，定位錯誤將會是一件非常困難的事情。所以，千萬別惹你的領導，否則將死得很難看。
『貳』 什麼是棧回溯
一、棧回溯的概念：
棧回溯就是回溯法，是一個既帶有系統性又帶有跳躍性的的搜索演算法。它在包含問題的所有解的解空間樹中，按照深度優先的策略，從根結點出發搜索解空間樹。演算法搜索至解空間樹的任一結點時，總是先判斷該結點是否肯定不包含問題的解。如果肯定不包含，則跳過對以該結點為根的子樹的系統搜索，逐層向其祖先結點回溯。否則，進入該子樹，繼續按深度優先的策略進行搜索。回溯法在用來求問題的所有解時，要回溯到根，且根結點的所有子樹都已被搜索遍才結束。而回溯法在用來求問題的任一解時，只要搜索到問題的一個解就可以結束。這種以深度優先的方式系統地搜索問題的解的演算法稱為回溯法，它適用於解一些組合數較大的問題。
二、演算法框架：
1、問題的解空間：應用回溯法解問題時，首先應明確定義問題的解空間。問題的解空間應到少包含問題的一個（最優）解。
2、回溯法的基本思想：確定了解空間的組織結構後，回溯法就從開始結點（根結點）出發，以深度優先的方式搜索整個解空間。這個開始結點就成為一個活結點，同時也成為當前的擴展結點。在當前的擴展結點處，搜索向縱深方向移至一個新結點。這個新結點就成為一個新的活結點，並成為當前擴展結點。如果在當前的擴展結點處不能再向縱深方向移動，則當前擴展結點就成為死結點。換句話說，這個結點不再是一個活結點。此時，應往回移動（回溯）至最近的一個活結點處，並使這個活結點成為當前的擴展結點。回溯法即以這種工作方式遞歸地在解空間中搜索，直至找到所要求的解或解空間中已沒有活結點時為止。
運用回溯法解題通常包含以下三個步驟：
（1）針對所給問題，定義問題的解空間；
（2）確定易於搜索的解空間結構；
（3）以深度優先的方式搜索解空間，並且在搜索過程中用剪枝函數避免無效搜索。