contributed by < zodf0055980
>
Linux 核心設計
主要是去實作 FIFO & LIFO queue,需滿足以下功能:
2/26 簡化程式碼
為了實現 q_insert_tail 和 q_size 的時間複雜度為 ,所以加入指向 Queue 尾端的 pointer 以及儲存 size 大小。
這邊需要注意 malloc() 如果請求失敗,會回傳 NULL ,因此需要注意 malloc() 請求失敗的狀況。
這邊需注意 list_ele_t malloc() 成功,但 value malloc() 失敗,需要把 list_ele_t 給 free(),避免多餘的資料占用記憶體。
這邊也注意到自己的不足,居然把 sizeof(s) 當作整個 string 的長度,因為 s 是指標,所以得到的會是指標的大小,而非字串的長度。想起上課講到的,這是愚蠢的程式碼。
此段時間複雜度為
q_insert_tail 和 q_insert_head 相似,時間複雜度為 。
這邊需要注意 sp 需要判斷是否為 NULL,時間複雜度為 。
這邊需要注意要先 free value,再free list_ele_t,時間複雜度為 。
這邊一開始沒有考慮 q 為 NULL 的狀況,時間複雜度為 。
這裡特地把以前資料結構的書給拿出來看,利用3個 pointer 去實現 Queue 的反轉。
這邊一開始測試檔一直過不了。
參考學長的共筆紀錄
並至 trace-06-string.cmd 中依序測試一遍,發現如果 Queue 未建立,會出現 Null Dereferencing。因此需判斷 Queue 中是否有多於兩個 element,而此 reverse 時間複雜度為 。
在 harness.h 中有這段
他把 malloc 和 free 都對應到 harness.c 中的程式碼,去做相關的檢查,這也是為什麼 segment fault 不會結束程式的原因。
第一次看到宣告矩陣大小為0的,一查發現原來是 Arrays of Length Zero。透過去 malloc(sizeof(block_ele_t) + 額外的記憶體空間) 便可以利用 unsigned char payload[] 去對額外空間作存取。因此去利用 block_ele_t 去儲存有關分配記憶體的各項資料,去判斷是否有不正當得使用。
列出第一手資料,規格書或者編譯器使用手冊
以更正
利用 Arrays of Length Zero 的技巧把 new_block 指派我們想要 malloc() 的大小。並儲存分派記憶體大小和把 magic_header 設為 0xdeadbeef。以及利用 find_footer 去把 block_ele_t 最尾端指向 0xbeefdead。最後利用 double linked list 把分配的記憶體給串聯起來,並回傳實際可用空間的記憶體位址。
如果 test_malloc 成功執行,記憶體的內容會如下圖所示:
這樣便可以透過 magic_header 和 MAGICFOOTER 去判斷對記憶體的操作是否正確。而 magic_header 和 MAGICFOOTER 可為任意的值,主要是拿來判斷正確性。
因為 test_malloc 所回傳的值是實際可用空間的記憶體位址,因此需要透過 find_header 找 block_ele_t 所在的記憶體位址。
並把 magic_header 和 MAGICFOOTER 指向 0xffffffff 來代表該記憶體區塊已經釋放,並用 FILLCHAR 去填滿。且從 double linked list 移除。
在 qtest 中的 queue_init() 中,透過
透過設置信號和 function,只要有 SIGSEGV 和 SIGALRM 的信號,便會執行 sigsegvhandler 和 sigalrmhandler 的 function。
而 SIGSEGV 負責處理的是 Invalid memory reference,一般我們程式如果發生 segmentation fault,便會產生 exception 通知 OS,由 OS 做處理。這也是為甚麼我們平常只要有 segmentation fault 程式就會中斷。而透過 signal() 去設定發生 segmentation fault 的處理 function,這也就是為什麼程式出錯而不會結束的原因。
而 SIGALRM 負責處理的是 Alarm clock。透過 alarm(time_limit) 去設定 timer 幾秒後產生 SIGALRM 的信號,alarm(0) 去取消停止當前的 timer 處理。
在 qtest.c 中對 Queue 的操作都有類似下面的 code:
如果一段時間內(此程式為1秒)沒有執行 exception_cancel 去取消 timer 的處理,timer 會產生 Alarm clock 的信號,以確保程式不會有無窮迴圈的情況。