算法旅人

2021年11月12日星期五

?? 本周的MP重點(diǎn)在于學(xué)習(xí)使用GDB進(jìn)行調(diào)試，這里貼一個GDB的官方介紹：

GNU symbolic debugger，簡稱「GDB 調(diào)試器」，是 Linux 平臺下最常用的一款程序調(diào)試器。GDB 編譯器通常以 gdb 命令的形式在終端（Shell）中使用

???學(xué)會使用debugger進(jìn)行逐行調(diào)試是很重要的編程基本功，就像我們在學(xué)習(xí)匯編語言時使用了LC3-tk 一樣，本質(zhì)上gdb也是帶有追蹤標(biāo)記功能的調(diào)試工具，Pavol教授也坦言Lumetta他們實(shí)際上就是基于GDB設(shè)計的可視化的LC3 debugger。

或許有人會覺得使用GCC的編譯就足以發(fā)現(xiàn)程序問題了，但實(shí)際上，我們常常會遇到三種【錯誤】：error, exception 和 bug,以及不一定會影響運(yùn)行的warning（典中典：warning 不影響程序運(yùn)行，不用太care）實(shí)際上，早在CS101偉烈教授就講解了他們?nèi)叩膮^(qū)別：

很顯然我們可以看到，最有危害的是bug , 即邏輯漏洞（錯誤）。邏輯錯誤指的是代碼思路或者設(shè)計上的缺陷，程序出現(xiàn)邏輯錯誤的癥狀是：代碼能夠編譯通過，沒有語法錯誤，但是運(yùn)行結(jié)果不對。對于這類錯誤，只能靠我們自己去發(fā)現(xiàn)和糾正。

C語言中文網(wǎng)就說到：“對于初學(xué)者來說，學(xué)習(xí)調(diào)試可以增加編程的功力，能讓我們更加了解自己的程序，比如變量是什么時候賦值的、內(nèi)存是什么時候分配的，從而彌補(bǔ)學(xué)習(xí)的紕漏。調(diào)試是每個程序員必須掌握的基本技能，沒有選擇的余地！”

那么這里我們就先略過對GDB的概覽介紹，研究一下本次MP的問題吧：

MAKE文件有一個bug導(dǎo)致我們不能編譯使用GDB【√】需要添加 -g Flag

第三個程序只有可執(zhí)行文件，無法看到源碼的條件下進(jìn)行黑盒測試

注：黑盒測試又叫功能測試、數(shù)據(jù)驅(qū)動測試或基于需求規(guī)格說明書的功能測試。. 該類測試注重于測試軟件的功能性需求。采用這種測試方法， 測試工程師把測試對象看作一個黑盒子，完全不考慮程序內(nèi)部的邏輯結(jié)構(gòu)和內(nèi)部特性，只依據(jù)程序的《需求規(guī)格說明書》，檢查程序的功能是否符合它的功能說明。. 測試工程師無需了解程序代碼的內(nèi)部構(gòu)造，完全模擬軟件產(chǎn)品的最終用戶使用該軟件，檢查軟件產(chǎn)品是否達(dá)到了用戶的需求。. 黑盒測試方法能更好、更真實(shí)地從用戶角度來考察被測系統(tǒng)的功能性需求實(shí)現(xiàn)情況。

? ? ? 3，第一個程序涉及到C語言main函數(shù)參數(shù)的概念：

不帶參數(shù)的main 后的括號都是空括號。實(shí)際上，main函數(shù)可以帶參數(shù)，這個參數(shù)可以認(rèn)為是main函數(shù)的形式參數(shù)。C語言規(guī)定main函數(shù)的參數(shù)只能有兩個，習(xí)慣上這兩個參數(shù)寫為argc和argv。因此，main函數(shù)的函數(shù)頭可寫為：
? ? main (argc,argv)
C語言還規(guī)定argc(第一個形參)必須是整型變量，argv(第二個形參)必須是指向字符串的指針數(shù)組。加上形參說明后，main函數(shù)的函數(shù)頭應(yīng)寫為：
? ? main (int argc,char *argv[])

由于main函數(shù)不能被其它函數(shù)調(diào)用，因此不可能在程序內(nèi)部取得實(shí)際值。那么，在何處把實(shí)參值賦予main函數(shù)的形參呢？實(shí)際上，main函數(shù)的參數(shù)值是從操作系統(tǒng)命令行上獲得的。當(dāng)我們要運(yùn)行一個可執(zhí)行文件時，在DOS提示符下鍵入文件名，再輸入實(shí)際參數(shù)即可把這些實(shí)參傳送到main的形參中去。
命令行的一般形式為：
? ? C:\>可執(zhí)行文件名? 參數(shù)? 參數(shù) ……;?
但是應(yīng)該特別注意的是，main 的兩個形參和命令行中的參數(shù)在位置上不是一一對應(yīng)的。因?yàn)?#xff0c;main的形參只有二個，而命令行中的參數(shù)個數(shù)原則上未加限制。

argc參數(shù)表示了命令行中參數(shù)的個數(shù)（注意：文件名本身也算一個參數(shù)），argc的值是在輸入命令行時由系統(tǒng)按實(shí)際參數(shù)的個數(shù)自動賦予的。

例如有命令行為：
? ? C:\>E24? BASIC? foxpro? FORTRAN
由于文件名E24本身也算一個參數(shù)，所以共有4個參數(shù)，因此argc取得的值為4。argv參數(shù)是字符串指針數(shù)組，其各元素值為命令行中各字符串(參數(shù)均按字符串處理)的首地址。 指針數(shù)組的長度即為參數(shù)個數(shù)。數(shù)組元素初值由系統(tǒng)自動賦予。其表示如圖所示：

——引用自C語言中文網(wǎng)

這里就能看出，C和Python的顯著不同，一個是指針，一個則是面對對象
當(dāng)然，python也支持__main__這樣的語法，以后會學(xué)到，蠻重要的，類與OOP
4, 素數(shù)問題：

這里看到了一個很好的知乎帖子，講解如何求素數(shù)的數(shù)學(xué)原理

5種你不知道的素數(shù)的判斷方法 - 知乎 (zhihu.com)https://zhuanlan.zhihu.com/p/104314640

5, 堆排序：Heap Sort

堆排序（Heapsort）是指利用堆這種數(shù)據(jù)結(jié)構(gòu)所設(shè)計的一種排序算法。堆積是一個近似完全二叉樹的結(jié)構(gòu)，并同時滿足堆積的性質(zhì)：即子結(jié)點(diǎn)的鍵值或索引總是小于（或者大于）它的父節(jié)點(diǎn)。堆排序可以說是一種利用堆的概念來排序的選擇排序。分為兩種方法：

大頂堆：每個節(jié)點(diǎn)的值都大于或等于其子節(jié)點(diǎn)的值，在堆排序算法中用于升序排列；

小頂堆：每個節(jié)點(diǎn)的值都小于或等于其子節(jié)點(diǎn)的值，在堆排序算法中用于降序排列；

堆排序的平均時間復(fù)雜度為 Ο(nlogn)。

——菜鳥教程

第三個sort程序的黑箱測試：

BUG在：應(yīng)該是arr[n-1]而不是arr[n]！?

array 從 0 開始計算索引！

以下是本次的report：

比較長，因?yàn)閟pecific 里面需要復(fù)制粘貼我的g

;=======================================; | Machine Problem Seven | Worked By Wang Jie(Tony) | Netid: jiew5, ZJUid: 3200112404 | Date: 2021.11.12 ;=======================================;TASK DESCRTIPTION:In this MP, I need to write down the possible reason of 3 buggy C function. To do so, I need GDB debugger to do the black box test. ============================================================================== [FIRST: PrintRev.c] 0, Report student@ece220-VM:~/jiew5/mp/mp7/printRev$ make gcc -c -g -Wall -o pr_buggy.o pr_buggy.c 2> /dev/null #Here I add a -g flag in the Makefile gcc -c -g -Wall -o prmain.o prmain.c gcc pr_buggy.o prmain.o -o prev -gstudent@ece220-VM:~/jiew5/mp/mp7/printRev$ gdb prev -q #Here I add a -q flag to skip the declearation of GDB Reading symbols from prev... -----------------------------------------| 1, Function Description:The function, consist of pr_buggy.c and prmain.c, is used to reverse the input string sentence.After 10 numbers counting down, the program asked "What's on the stack now?" then print the reversed version and the length of string.Meanwhile, the main function use blank [ ] to seperate the input arguments and it support multiple input.-----------------------------------------| 2, input case:<a> YZZ,YWW #Chinese short name for "The story of Brave is never finished."(gdb) r YZZ,YWW Starting program: /home/student/jiew5/mp/mp7/printRev/prev YZZ,YWW 9 8 7 6 5 4 3 2 1 0 What's on the stack now?"YZZ,YWW" reversed is "WWY,ZZY" (length 7) #Correct1 [Inferior 1 (process 4007) exited normally]<b> ECE220 is so hard! (gdb) r ECE220 is soo hard! Starting program: /home/student/jiew5/mp/mp7/printRev/prev ECE220 is so hard! 9 8 7 6 5 4 3 2 1 0 What's on the stack now?"ECE220" reversed is "022ECE" (length 32773) #BUG1 9 8 7 6 5 4 3 2 1 0 What's on the stack now?"is" reversed is "si" (length 2) #Correct2 9 8 7 6 5 4 3 2 1 0 What's on the stack now?"soo" reversed is "oos" (length 3) #Correct3 9 8 7 6 5 4 3 2 1 0 What's on the stack now?"hard!" reversed is "!drah" (length 32772) #BUG2 [Inferior 1 (process 4049) exited normally]<c> 12345 #Used to test 5 length str (gdb) r 12345 Starting program: /home/student/jiew5/mp/mp7/printRev/prev 12345 9 8 7 6 5 4 3 2 1 0 What's on the stack now?"12345" reversed is "54321" (length 32772) #BUG3 [Inferior 1 (process 4293) exited normally]2, Reason of BUG:After examing the code, I find that in pr_buggy.c, there are an innitial error of int32_t rest. It should be set as 0 at the beginning of code, otherwise when the recursive process ends, we can't know what will be the starting rest, so the ending rest will be very large.3, How to solve it:Just simply change line #36 in pr_buggy.c from int32_t rest; into int32_t rest = 0; Then every BUG input above works. ============================================================================== [SECOND: primeNumber.c] //The source code of is_prime.c is hidden. //Doing Black box test can help us find the bug 1, Bug report: gdb primeNumber GNU gdb (Ubuntu 9.2-0ubuntu1~20.04) 9.2 Copyright (C) 2020 Free Software Foundation, Inc. License GPLv3+: GNU GPL version 3 or later <http://gnu.org/licenses/gpl.html> This is free software: you are free to change and redistribute it. There is NO WARRANTY, to the extent permitted by law. Type "show copying" and "show warranty" for details. This GDB was configured as "x86_64-linux-gnu". Type "show configuration" for configuration details. For bug reporting instructions, please see: <http://www.gnu.org/software/gdb/bugs/>. Find the GDB manual and other documentation resources online at:<http://www.gnu.org/software/gdb/documentation/>.For help, type "help". Type "apropos word" to search for commands related to "word"... Reading symbols from primeNumber... (gdb) r Starting program: /home/student/jiew5/mp/mp7/primeNumber/primeNumber 2 is prime. 3 is prime. 4 is prime. #not a prime 5 is prime. 7 is prime. 9 is prime. #not a prime 11 is prime. 13 is prime. 17 is prime. 19 is prime. 23 is prime. 25 is prime. #not a prime 29 is prime. 31 is prime. 37 is prime. 41 is prime. 43 is prime. 47 is prime. 49 is prime. #not a prime 53 is prime. 59 is prime. 61 is prime. 67 is prime. 71 is prime. 73 is prime. 79 is prime. 83 is prime. 89 is prime. 97 is prime. 101 is prime. 103 is prime. 107 is prime. 109 is prime. 113 is prime. 121 is prime. #not a prime 127 is prime. 131 is prime. 137 is prime. 139 is prime. 149 is prime. 151 is prime. 157 is prime. 163 is prime. 167 is prime. 169 is prime. #not a prime 173 is prime. 179 is prime. 181 is prime. 191 is prime. 193 is prime. 197 is prime. 199 is prime. 211 is prime. 223 is prime. 227 is prime. 229 is prime. 233 is prime. 239 is prime. 241 is prime. 251 is prime. 257 is prime. 263 is prime. 269 is prime. 271 is prime. 277 is prime. 281 is prime. 283 is prime. 289 is prime. 293 is prime. 307 is prime. 311 is prime. 313 is prime. 317 is prime. 331 is prime. 337 is prime. 347 is prime. 349 is prime. 353 is prime. 359 is prime. 361 is prime. #not a prime 367 is prime. 373 is prime. 379 is prime. 383 is prime. 389 is prime. 397 is prime. 401 is prime. 409 is prime. 419 is prime. 421 is prime. 431 is prime. 433 is prime. 439 is prime. 443 is prime. 449 is prime. 457 is prime. 461 is prime. 463 is prime. 467 is prime. 479 is prime. 487 is prime. 491 is prime. 499 is prime. 503 is prime. 509 is prime. 521 is prime. 523 is prime. 529 is prime. #not a prime 541 is prime. 547 is prime. 557 is prime. 563 is prime. 569 is prime. 571 is prime. 577 is prime. 587 is prime. 593 is prime. 599 is prime. 601 is prime. 607 is prime. 613 is prime. 617 is prime. 619 is prime. 631 is prime. 641 is prime. 643 is prime. 647 is prime. 653 is prime. 659 is prime. 661 is prime. 673 is prime. 677 is prime. 683 is prime. 691 is prime. 701 is prime. 709 is prime. 719 is prime. 727 is prime. 733 is prime. 739 is prime. 743 is prime. 751 is prime. 757 is prime. 761 is prime. 769 is prime. 773 is prime. 787 is prime. 797 is prime. 809 is prime. 811 is prime. 821 is prime. 823 is prime. 827 is prime. 829 is prime. 839 is prime. 841 is prime. 853 is prime. 857 is prime. 859 is prime. 863 is prime. 877 is prime. 881 is prime. 883 is prime. 887 is prime. 907 is prime. 911 is prime. 919 is prime. 929 is prime. 937 is prime. 941 is prime. 947 is prime. 953 is prime. 961 is prime. 967 is prime. 971 is prime. 977 is prime. 983 is prime. 991 is prime. 997 is prime. [Inferior 1 (process 2575) exited normally]BUG: some of check is wrongly output, there are not prime. BUG Case: [4,9,25,49,121,169,361,529,...] From mathmatical anlaysis, we know all of these cases are the square of prime. And for efficiently checking whether a given number N is prime, we divide it between 2 to sqrt(N), seeing if it can be divide excatly. Here we set breakpoints and display check to see whether it works like my assumption: (gdb) b main Breakpoint 1 at 0x1139: file primeNumber.c, line 38. (gdb) r Starting program: /home/student/jiew5/mp/mp7/primeNumber/primeNumber Breakpoint 1, main () at primeNumber.c:38 38 { (gdb) display check 1: check = 0 (gdb) watch check == 4 Hardware watchpoint 2: check == 4 (gdb) watch check == 9 Hardware watchpoint 3: check == 9 (gdb) watch check == 25 Hardware watchpoint 4: check == 25 (gdb) c Continuing. 2 is prime. 3 is prime.Hardware watchpoint 2: check == 4Old value = 0 New value = 1 (gdb) n 4 is prime. (gdb) c Continuing. 5 is prime. 7 is prime.Hardware watchpoint 3: check == 9Old value = 0 New value = 1 0x0000555555555176 in main () at primeNumber.c:42 42 for (check = 2; 1000 > check; check++) { 1: check = 9 (gdb) c Continuing. 9 is prime.Hardware watchpoint 3: check == 9Old value = 1 New value = 0 #... Repeating process2, Reason of BUG:By checking all of the check, we found that is_prime cannot know if [check] can be divided by [sqrt(check)] exactly. Therefore, we can guess the children function is_prime contains a comparison symbol error. It should be <= sqrt(N) instead of < 3, How to solve it:Just simply change comparison symbol in is_prime.c from < sqrt(N) into <= sqrt(N) Then every BUG input above works. ============================================================================== [THIRD: sort] //The source code of sortMain.c is hidden. // It is astonishing that we don't have a main program... and there is a bug in it... 0, Function description:Seeing test1.txt and sort.c, we know the program first detect whether do we input a txt file, if not it prints:"Usage: ./sort <input_file>"The main program first test the 1st line of input file, which is number N receiving the length of array to be sorted. Then it calls heapify N times, sort the array and calls printArray to print sorted array.----------------------------| 1, TEST case: student@ece220-VM:~/jiew5/mp/mp7/sort$ gdb sort -q Reading symbols from sort... (gdb) r test1.txt Starting program: /home/student/jiew5/mp/mp7/sort/sort test1.txt 1 3 9 12 13 15 18 19 22 23 29 41 45 51 58 96 97 99 100 117 #Seems it is correct output. [Inferior 1 (process 2928) exited normally] After running program many times.. 1 3 9 12 13 13 15 18 19 22 23 29 41 45 51 58 96 97 99 100 # The biggest Number is lost, and we get another 13 Repeating test the program, we see the output of sort is totally random.Therefore, we can assume that there is a bug in the index method of main program, which will cauase such a random case. Then we can track arr[0], arr[19] and arr[20] to know whether my hypothesis is true. 2, Discription of deBUG: I set 3 break points: Num Type Disp Enb Address What 1 breakpoint keep y 0x0000555555555477 <main+4>2 breakpoint keep y 0x00005555555551c9 in swap at sort.c:33 breakpoint keep y 0x0000555555555258 in heapify at sort.c:19 And after I run to heapify, I trace arr[0],arr[19] and arr[20]: (gdb) display arr[0] 1: arr[0] = 97 (gdb) display arr[20] 2: arr[20] = 0 (gdb) display arr[19] 3: arr[19] = 0 However, since the total number of to be sorted number is 20, and the C language starts from zero 0, the arr[20] should always not be used( Otherwise there will be strange value stored in its memory. And we continue: Breakpoint 3, heapify (arr=0x55555555a490, n=20, i=5) at sort.c:19 19 { 1: arr[0] = 1 2: arr[20] = 117 #We can see, arr[20] is used by main program! 3: arr[19] = 13 We can almost sure what is wrong, but we contine:Since the testing process is long, I continuely enter c to watch how the bottom of array changes: Until: Breakpoint 3, heapify (arr=0x55555555a49c, n=21845, i=1431676076) at sort.c:19 19 { 1: arr[0] = 99 2: arr[20] = 0 3: arr[19] = 129825 we can see there is a strange number in arr[19], while 20 is zero, then we can conclude that it must a bug in the sortMain.o that uses a place of arr which should not be used.3, How to solve it:Not quite sure, it depends on the main prgram's writing styleMaybe we just need to simply change arr[n] to arr[n-1]?============================================================================== Ps. In this MP, I always unconsciously used the annotation writing style and syntax similar to LC3, so I couldn't help using ; or //. It's very trance

不過嘛，我發(fā)現(xiàn)了教授的小尾巴，很顯然，他們是偽造出了bug，好方便我們查找

太陰險了！ ：-（?

總結(jié)

以上是生活随笔為你收集整理的ECE220生存指南[02] MP7: GDB 调试Debug的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。