contributed by < ollieni >
詳閱作業說明,指定的格式中有空白字元,留意各式細節,唯有重視小處並步步為營,方可挑戰原始程式碼規模超越三千七百萬行的 Linux 核心
$ gcc --version
gcc (Ubuntu 9.4.0-1ubuntu1~20.04.2) 9.4.0
Copyright (C) 2019 Free Software Foundation, Inc.
This is free software; see the source for copying conditions. There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
$ lscpu
Architecture: x86_64
CPU op-mode(s): 32-bit, 64-bit
Byte Order: Little Endian
Address sizes: 39 bits physical, 48 bits virtual
CPU(s): 4
On-line CPU(s) list: 0-3
Thread(s) per core: 1
Core(s) per socket: 4
Socket(s): 1
NUMA node(s): 1
Vendor ID: GenuineIntel
CPU family: 6
Model: 154
Model name: 12th Gen Intel(R) Core(TM) i7-12700H
Stepping: 3
CPU MHz: 2688.004
BogoMIPS: 5376.00
Hypervisor vendor: KVM
Virtualization type: full
L1d cache: 192 KiB
L1i cache: 128 KiB
L2 cache: 5 MiB
L3 cache: 96 MiB
NUMA node0 CPU(s): 0-3
修改 queue.c ,使其滿足
$ make test
自動評分系統的所有項目
建立一個空的佇列,並將其下一個和上一個的指標都指向自己。
避免非必要的項目縮排 (即 *
),用清晰、明確,且流暢的漢語書寫。
宣告一個 list_head
型別的指標並使用 malloc
分配 配置記憶體空間再2. 用 list.h
中的 INIT_LIST_HEAD
將其指向下一個和上一個的指標都指向自己。
allocate 的翻譯是「配置」,以區隔 dispatch (分配/分發) 的翻譯。
將佇列所使用的全部記憶體釋放,若是佇列是空的則不動作。
留意資訊科技詞彙翻譯
使用 list.h
中的 list_for_each_safe
去遍歷 走訪整個佇列
將走過的節點用 list_del
從佇列中移去
使用 list_entry
去取得該節點 container (也就是 element_t)位置,把 value 和該節點之記憶體釋放。
避免非必要的項目縮排 (即 *
和 -
),以清晰、明確,且流暢的漢語書寫。
q_insert_head
, q_insert_tail
插入一個節點到佇列的頭(尾)。
分配 記憶體空間給新結點
將要插入的字串存到 value
使用 list.h
中的 list_add
/ list_add_tail
將節點插入佇列中。
避免非必要的項目縮排 (即 *
和 -
),以清晰、明確,且流暢的漢語書寫。
一開始在寫完後執行 make check
產生以下錯誤訊息。
# Fill it with some values. First at the head
ERROR: Need to allocate and copy string for new queue element
l = [dolphin]
根據錯誤訊息可得知,需要先使用 malloc
配置空間給新的元素,並複製要插入的字串。
bool q_insert_head(struct list_head *head, char *s)
{
element_t *new = malloc(sizeof(element_t *));
+ new->value = malloc(sizeof(s)+1);
+ strcpy(new->value, s);
- new->value = s;
list_add(&new->list, head);
return true;
}
修改程式後可以順利執行,但是當 commit 的時候被偵測到有危險的函式。
Dangerous function detected in /home/ollieni/linux2024/lab0-c/queue.c
31: strcpy(new->value, s);
41: strcpy(new->value, s);
Read 'Common vulnerabilities guide for C programmers' carefully.
https://security.web.cern.ch/security/recommendations/en/codetools/c.shtml
在查看錯誤訊息提供的 Common vulnerabilities guide for C programmers之後,得到了以下的資訊 :
"The strcpy built-in function does not check buffer lengths and may very well overwrite memory zone contiguous to the intended destination. In fact, the whole family of functions is similarly vulnerable: strcpy, strcat and strcmp."
這些文字的大意是 :
strcpy 內建函式並未檢查緩衝區的長度,可能會覆寫意圖目的地相鄰的記憶體區域。事實上,整個函式家族都存在相似的風險:strcpy、strcat 和 strcmp。
我根據網頁中的推薦使用 strncpy
。
bool q_insert_head(struct list_head *head, char *s)
{
+ int len = strlen(s);
+ strncpy(new->value, s, len + 1);
- strcpy(new->value, s);
}
q_remove_head
, q_remove_tail
將佇列中第一個(最後一個)節點移去。
使用 list_entry
將第一個(最後一個)節點之 container 找出。
將節點之 value 複製存於 sp ,使用 list_del
將節點移去。
避免非必要的項目縮排 (即 *
和 -
),以清晰、明確,且流暢的漢語書寫。
計算佇列的長度。
用教材中之程式。
刪除佇列中間的節點。
使用 q_size
得到佇列之長度後。
用 while 迴圈找到中間的節點,再將其刪除。
避免非必要的項目縮排 (即 *
和 -
),以清晰、明確,且流暢的漢語書寫。
將佇列中重複的元素全部刪除。
將節點和下一個節點之 value 進行比較,若是相同就刪除當下節點,並用 count++ 記錄此 value 有重複 (在 C 語言中除了 0 都是 True)。
在不相等時,去查看 count 來判斷是否刪除當下節點。
在最後一個節點時,也需查看 count 來判斷是否刪除當下節點。
避免非必要的項目縮排 (即 *
和 -
),以清晰、明確,且流暢的漢語書寫。
一開始的實作會如同這題 leetcode,無法將重複的全部刪除。
ERROR: Duplicate strings are in queue or distinct strings are not in queue
後來使用 count 記錄當下節點之前是否重複,在我自己的測試中能得到正確的結果。
但是在 make test 中出現問題,在自己排查後,發現是最後一個節點永遠不會被刪除。
再多加上一個判斷就解決了。
將佇列中每兩個相鄰元素的值進行交換。
善用 List API,撰寫出更精簡的程式碼。
反轉整個佇列。
按照指定的 k 大小,先將整個串列分成 k 組,再對其反轉。
將 current 指標向前移動 k 次,切斷 head 和 current->prev 之間的元素,存在 temp 中。
呼叫先前定義的 q_reverse 函數對 temp 進行反轉。
使用 list_splice_tail_init 將反轉後的 temp 串列添加到 result 串列的尾部。
使用 list_splice_init 將最終結果 result 串列合併到原始 head 串列。
改進你的漢語表達。
使用 merge sort 實作,將佇列中元素依照輸入的 descend 參數決定要輸出升序或降序的結果。
我分成 4 個函式實作 :
merge 函式:
此函式用於合併兩個已經排序的佇列 l1 和 l2。
創建三個指標 cur1、cur2 和 swap 以遍歷 ??? l1 和 l2,以及存儲合併結果的 result 佇列。
在迴圈中,比較 cur1 和 cur2 指向的元素,將較小的元素添加到 result 佇列中。
最後,處理剩餘的元素,並將 result 佇列接合到原始 l1 或 l2 中。
返回合併後的佇列。
split_two 函式:
此函式用於將佇列分成兩半,返回分割點的位置。
sort 函式:
此函式實現合併排序,接受一個指向佇列 head 和一個布林值 descend(用於指定升序或降序排列)作為參數。
使用 split_two 函式將佇列分為兩半,然後分別對兩半進行遞迴排序。
使用 merge 函式將兩半合併為一個排序好的佇列。
返回排序後的佇列。
q_sort 函式:
call 的翻譯是「呼叫」,這個函式的權限沒大到可以「調用」你。
此函式用於調用呼叫 sort 函式進行合併排序。
先檢查連結串列的大小,如果為空或只有一個元素,則直接返回。
將連結串列的頭節點刪除,將剩餘部分進行排序,最後將排序後的結果重新連結到原始的 head。
刪除具有較小值在右側的節點。
刪除具有較大值在右側的節點。
實作和ascend一樣,只要將判斷式中的 >=
改成 <=
即可。
合併多個排好序的佇列,並將結果放到第一個佇列裡。
以下方兩個函式實作:
對應到數學公式,function 應翻譯為「函數」,後者就像是台「機器」,它能夠將集合 A 裡面的每個元素「唯一地」對應到集合 B 裡的一個元素。但在 C 語言一類的通用程式語言中,function 未必具備數學函數的意涵,也就是缺乏「唯一對應」的特性,例如對於 time 來說,給定同樣的輸入,卻會在不同時間點得到不同的結果,在 C 語言一類的通用程式語言中,甚至可省略傳回值,後者就不符合「函數」的行為。因此,當在通用的程式設計中,function 應翻譯為「函式」,表示「衍生自數學函數的常式 (routine)」。另外,對於更一般的描述,function 會指「功能」一類的意涵,應合適挑選譯詞。
\(\to\) 資訊科技詞彙翻譯
merge_two_list 函式:
此函式用於合併兩個已經排序的連結串列 l1 和 l2。
創建三個指標 cur1、cur2 和 swap 以遍歷 l1 和 l2,以及儲存合併結果的 result 串列。
在迴圈中,比較 cur1 和 cur2 指向的元素,將較小(或相等)的元素添加到 result 串列中。
將剩餘的元素依次添加到 result 串列中。
最後,將 result 串列接合到原始 l1 中。
q_merge 函式:
此函式的目的是合併多個已排序佇列,形成一個新的排序佇列。
使用 merge_two_list 函數將每個佇列逐一合併到第一個串列 context1->q 中。
如果指定的排序方式為降序,則呼叫 q_reverse 函數對最終合併的佇列進行反轉。
返回最終合併的佇列的大小,即呼叫 q_size 函數。
做完所有項目後,我 make test 有時候會得到100分,有時候不會。
文字訊息避免用圖片來表示,否則不好搜尋和分類
--- trace-14-perf 6/6
+++ TESTING trace trace-15-perf:
# Test performance of sort with random and descending orders
# 10000: all correct sorting algorithms are expected pass
# 50000: sorting algorithms with O(n^2) time complexity are expected failed
# 100000: sorting algorithms with O(nlogn) time complexity are expected pass
--- trace-15-perf 6/6
+++ TESTING trace trace-16-perf:
# Test performance of insert_tail
--- trace-16-perf 6/6
+++ TESTING trace trace-17-complexity:
# Test if time complexity of q_insert_tail, q_insert_head, q_remove_tail, and q_remove_head is constant
Probably constant time
Probably constant time
Probably constant time
Probably constant time
--- trace-17-complexity 5/5
--- TOTAL 100/100
ollieni@ollie-CA:~/linux2024/lab0-c$
但 push 上 github ,無法通過 CI/CD的測試。
經過推測,發現有可能是老師在作業文件中提到的問題。
注意:現有實作存在若干致命缺陷,請討論並提出解決方案
嘗試使用 web
去確認我實作的程式是否能搭配,
測試指令 :
$ curl http://localhost:9999/new
$ curl http://localhost:9999/ih/1
$ curl http://localhost:9999/ih/2
$ curl http://localhost:9999/ih/3
$ curl http://localhost:9999/sort
$ curl http://localhost:9999/quit
以下是測試結果 :
$ ./qtest
cmd> web
listen on port 9999, fd is 3
cmd> l = []
cmd> l = [1]
cmd> l = [2 1]
cmd> l = [3 2 1]
cmd> l = [1 2 3]
cmd> Freeing queue
指令
command 是「命令」,而非「指令」(instruction)
根據教學文件 qtest 命令直譯器的實作,在 console_init() 中加上 ADD_COMMAND(shuffle, "Shuffle the nodes of the queue", "");
,並寫一個 do_shuffle 去呼叫我們實作的q_shuffle。
雖然教材中有,但我還是嘗試寫了一個版本。
algorithm 是「演算法」,而「算法」是 the way to calculate,一如你以前國小考試作答的計算過程。
以下為執行測試程式後的結果 :
$ python3 scripts/shuffle.py
Expectation: 41666
Observation: {'1234': 41656, '1243': 41850, '1324': 41965, '1342': 41372, '1423': 41682, '1432': 41783, '2134': 41375, '2143': 41391, '2314': 41578, '2341': 41945, '2413': 41157, '2431': 41731, '3124': 41651, '3142': 41445, '3214': 41810, '3241': 41649, '3412': 41421, '3421': 41752, '4123': 42126, '4132': 41662, '4213': 41641, '4231': 42100, '4312': 41487, '4321': 41771}
chi square sum: 31.539144626314016
整個專案的程式風格統一,才能有利於協做並更好的維護程式。
Clang Format 這個工具,可以很有效率的幫助我們輕鬆統一程式風格。
我們只要在專案的根目錄下,寫一個 .clang-format
檔案,裡面可以詳細定義要遵循的程式風格,比如說 : 不能使用 tab
、使用 4 個空白代替,我們在下指令的時候,沒有指定 -style
,clang format 預設會去抓我們定義的 .clang-format
檔案。
你查詢哪些材料?該列出來,並以第一手材料為主。
根據我查詢的資料 根據 Git 官方手冊 Git Hooks , Git Hook 這個功能的是將一些簡單的 CI 從 server 端,移到開發人員端做,我們在 commit 前就能確保我們程式符合規範。
這些規範的腳本會在 .git/hooks/
這個目錄下,有些腳本有 .sample
這個副檔名,代表沒啟用,如果要啟用只需將 .sample
刪掉即可。
在 Git 官方手冊中,有提到我們使用的 pre-commit 是 client-side hook,這種 hook 不會隨著 git clone 被複製,我就有疑問我們沒有特別設定,怎麼有這個功能。
在仔細重看了一次 lab0 文件後,找到在 Git Hooks 進行自動程式碼排版檢查,有寫到 "首次執行 make 後,Git pre-commit / pre-push hook 將自動安裝到現行的工作區 (workspace)",於是我去看 Makefile,注意到有執行一個腳本 $(GIT_HOOKS): @scripts/install-git-hooks
,再去查看 scripts/install-git-hooks
腳本中的內容,以下我覺得是重點
mkdir -p .git/hooks
ln -sf ../../scripts/pre-commit.hook .git/hooks/pre-commit || exit 1
chmod +x .git/hooks/pre-commit
ln -sf ../../scripts/commit-msg.hook .git/hooks/commit-msg || exit 1
chmod +x .git/hooks/commit-msg
ln -sf ../../scripts/pre-push.hook .git/hooks/pre-push || exit 1
chmod +x .git/hooks/pre-push
touch .git/hooks/applied || exit 1
我可以看出,在這個專案中,將我們所需的腳本先放在 scripts
目錄下,這樣我們 clone 時,就能複製到這些腳本。然後在執行 make
的時候,會去執行 install-git-hooks
, 將 pre-commit
、commit-msg
、pre-push
用 ln
建立連結檔到 .git/hooks/
目錄下並改變權限讓其可以執行,如此我們就可以使用這些 client-side hook。
參考資料 : 探索藏在Git當中的Git Hook
為何不閱讀 Git 官方的手冊呢?
工程人員說話要精準,避免說「感覺」
Indirect pointer 使用時機
Rust key concept
你閱讀教材都沒遇到問題嗎?
lib/list_sort.c
這是 Linux 核心使用的 sort ,是 merge sort ,主要由三個函式 list_sort()
、 merge()
及 merge_final()
組成,這個實作有幾個特別的地方:
在 sort 的時候會先將鏈結串列轉換成 null-terminated 的。
有兩個 merge 的函式,merge_final
,會在合併完最後兩個鏈結串列後將結果恢復為標準的 circular doubly linked-list。
merge ()
函式 :
merge()
的實作方法是用一個無線迴圈,使用 cmp
來決定要將 a
還是 b
放到 tail
.
這裡有個重點,註解有提到如果有等於的情況,為了排序的 stability 要取 a
。
值得一提的是 cmp
以 function pointer 的型別傳入,定義在 include/linux/list_sort.h
裡面:
typedef int __attribute__((nonnull(2,3))) (*list_cmp_func_t)(void *, const struct list_head *, const struct list_head *);
在 linux/lib /test_list_sort.c
中可以找到cmp
函式,以下是 cmp()
的行為 :
當 cmp
回傳大於 0 時,表示 a > b 。
當 cmp
回傳小於等於 0 時,表示 b < a 。
補充 :
__attribute__
能讓你向編譯器提供關於函式的額外訊息,比如說 list_sort.c
中的 __attribute__((nonnull(2,3,4)))
,代表告訴編譯器,這個函式的第 2、3、4個參數不能是 null
。
likely
被定義在 /include/linux/compiler.h
裡,這個宏定義可以告訴編譯器,你覺得哪個分支更有可能被執行,可以讓編譯器在編譯時,做最佳化,舉例來說,如果在判斷式中使用 unlikely
,編譯器會調整其編譯出的組語或機器碼,讓 false
分支接在後面,使其只有在 true
的時候 jump
。
參考資料 :
Declaring Attributes of Functions
The Linux Kernel Module Programming Guide
在我測試完功能要 commit 時,遇到以下問題:
Following files need to be cleaned up:
qtest.c
queue.c
list_sort.c:21:20: style: Variable 'head' is not assigned a value. [unassignedVariable]
struct list_head *head, **tail = &head;
^
list_sort.c:11:7: error: Null pointer dereference: (struct element_t*)0 [nullPointer]
la = list_entry(a, element_t, list);
^
list_sort.c:12:7: error: Null pointer dereference: (struct element_t*)0 [nullPointer]
lb = list_entry(b, element_t, list);
^
Fail to pass static analysis.
第一個 style 的錯誤訊息是因為沒有賦值給 head
,所以我改成 struct list_head *head = NULL
,就符合 style 了。
接下來兩個錯誤訊息是 cppcheck 檢查的東西,根據 david965154 的筆記,我了解到可以去 script/pre-commit.hook
中設定,--suppress=nullPointer:list_sort.c"
,我加了這行讓 pre-commit 對我的 list_sort.c 不檢查 nullPointer 的問題,即可 commit 成功。
使用第一周測驗2的 tim_sort(待辦事項:了解程式碼有沒有問題),引入過程和 list_sort 引入過程一樣。