contributed by < komark06 >
yanjiew1
list_for_each_entry_safe (cur, safe, l, list)
q_release_element(cur);
.
後面應該有一個空格,再接下一個句子比較好。shuffle
指令,並分析亂度entropy
dudect
程式改善q_reverseK
)$ gcc --version
gcc (Ubuntu 11.3.0-1ubuntu1~22.04) 11.3.0
$ lscpu
Architecture: x86_64
CPU op-mode(s): 32-bit, 64-bit
Address sizes: 43 bits physical, 48 bits virtual
Byte Order: Little Endian
CPU(s): 12
On-line CPU(s) list: 0-11
Vendor ID: AuthenticAMD
Model name: AMD Ryzen 5 2600 Six-Core Processor
CPU family: 23
Model: 8
Thread(s) per core: 2
Core(s) per socket: 6
Socket(s): 1
Stepping: 2
Frequency boost: disabled
CPU max MHz: 3500.0000
CPU min MHz: 1550.0000
BogoMIPS: 6999.88
在尚未完全實作 queue.c
前,都會在新的分支 beta
下做開發和測試,避免觸發 GitHub Actions 。 在 5fcff8e 更新後, 新分支也會觸發 GitHub Actions 。
由於 lab0 本身有 make test
可以做測試,所以我以 make test
測試的順序作為開發的順序。
struct list_head *q_new()
{
struct list_head *q = malloc(sizeof(*q));
if (!q)
return NULL;
INIT_LIST_HEAD(q);
return q;
}
為新的佇列配置記憶體,並維持 circular linked list 的架構。需要注意的一點, head node 本身並不包含任何資料。
void q_free(struct list_head *l)
{
if (!l)
return;
element_t *cur, *safe;
list_for_each_entry_safe (cur, safe, l, list) {
q_release_element(cur);
}
free(l);
}
釋放佇列的所有節點及佇列本身,用 list_for_each_entry_safe
避免釋放 cur
後,無法往下一個節點前進。
為了避免重複的程式碼,透過 new_element
來新增節點。
static inline element_t *new_element(const char *s)
{
if (!s)
return NULL;
element_t *ne = malloc(sizeof(*ne));
if (!ne)
return NULL;
size_t len = strlen(s);
if (len > len + 1) {
free(ne);
return NULL;
}
ne->value = malloc(len + 1);
if (!ne->value) {
free(ne);
return NULL;
}
memcpy(ne->value, s, len);
ne->value[len] = '\0';
return ne;
}
考慮到 len + 1
可能會觸發 unsigned integer wrapping ,在呼叫 malloc
前作測試。
我覺得用 len > len + 1
來檢查的 overflow 沒有必要。一方面是字串不可能大到會發生 overflow 的狀況,另一方面原本字串結尾應該會有 '\0'
且不會被 strlen
計算。那麼即使一台機器 64-bit address space 被字串用滿,最後一個字元應該會是沒被計入的 '\0'
,故加上 1 不會產生 overflow 。
by yanjiew1
commit 7d9b6f3 修正。
有了 new_element
, q_insert_head
和 q_insert_tail
只需要將節點插入到對應的位置即可。
bool q_insert_head(struct list_head *head, char *s)
{
if (!head)
return false;
element_t *ne = new_element(s);
if (!ne)
return false;
list_add(&ne->list, head);
return true;
}
bool q_insert_tail(struct list_head *head, char *s)
{
if (!head)
return false;
element_t *ne = new_element(s);
if (!ne)
return false;
list_add_tail(&ne->list, head);
return true;
}
如同 new_element
,實作 remove_element
簡化程式碼。
static inline element_t *remove_element(element_t *obj,
char *sp,
size_t bufsize)
{
if (!obj)
return NULL;
if (sp && bufsize != 0) {
size_t len = strlen(obj->value);
if (len > bufsize - 1)
len = bufsize - 1;
memcpy(sp, obj->value, len);
sp[len] = '\0';
}
list_del(&obj->list);
return obj;
}
考量 bufsize
為零, bufsize - 1
會等於 SIZE_MAX
,會誤以為 sp
有很大的空間。所以加入 bufsize != 0
的條件來避免。
因為是 remove ,所以只要將節點移出 queue 即可。
有了 remove_element
, 只要提供相對應的節點,就能實作 q_remove_head
及 q_remove_tail
。
改用 !bufsize
可以更簡潔
by yanjiew1
commit 7d9b6f3 修正。
element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
if (!head || list_empty(head))
return NULL;
return remove_element(list_first_entry(head, element_t, list), sp, bufsize);
}
element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize)
{
if (!head || list_empty(head))
return NULL;
return remove_element(list_last_entry(head, element_t, list), sp, bufsize);
}
commit ea1eb84 修正當佇列為空時,會產生 segmentation fault 。
int q_size(struct list_head *head)
{
if (!head)
return 0;
struct list_head *cur;
int len = 0;
list_for_each (cur, head) {
len++;
}
return len;
}
使用 list_for_each
走訪每一個節點來紀錄節點總數。
bool q_delete_mid(struct list_head *head)
{
if (!head || list_empty(head))
return false;
struct list_head *tail = head->prev, *fast = head->next, *slow = fast;
while (fast != tail && fast->next != tail) {
fast = fast->next->next;
slow = slow->next;
}
list_del(slow);
q_release_element(container_of(slow, element_t, list));
return true;
}
使用前後指標找出中間節點後,將節點移出佇列後,釋放節點記憶體。
如果利用雙向鏈結串列的特性,從頭尾往中間找,可以減少記憶體存取次數。
by yanjiew1
bool q_delete_dup(struct list_head *head)
{
if (!head)
return false;
struct list_head *cur = head->next;
while (cur != head) {
if (cur->next != head) {
struct list_head *safe = cur->next;
element_t *c = container_of(cur, element_t, list),
*n = container_of(cur->next, element_t, list);
if (!strcmp(c->value, n->value)) {
do {
struct list_head *next = n->list.next;
list_del(&n->list);
q_release_element(n);
if (next == head)
break;
n = container_of(next, element_t, list);
} while (!strcmp(c->value, n->value));
safe = cur->next;
list_del(&c->list);
q_release_element(c);
}
cur = safe;
}
}
return true;
}
此函式要求佇列在已排序的情況下,才能正常執行。找出兩個具有相同字串的節點後,先刪除除了第一個節點以外的相同節點,最後再刪除第一個節點。
commit 4db7d66 修正 use after free bug 。
strcmp
會是影響 q_delete_dup
執行速度的關鍵。 考量以 strlen
和 memcmp
取代 strcmp
。先用簡單的實驗測量兩者的 benchmark。
void q_swap(struct list_head *head)
{
if (!head)
return;
struct list_head **cur = &head->next;
for (; *cur != head && (*cur)->next != head; cur = &(*cur)->next->next) {
struct list_head *first = *cur, *second = first->next;
first->next = second->next;
second->next = first;
second->prev = first->prev;
first->prev = second;
*cur = second;
}
}
將兩節點的連結作交換,再透過指標的指標,更新節點。
參考 25077667
chiangkd 的實作更加直觀
void q_reverse(struct list_head *head)
{
if (!head)
return;
struct list_head *cur, *safe;
list_for_each_safe (cur, safe, head) {
list_move(cur, head);
}
}
依序走訪每一個節點,並移動節點到佇列的開頭,就會是一個反轉的佇列。
void q_reverseK(struct list_head *head, int k)
{
if (!head || k <= 1)
return;
struct list_head *cur, *safe, *tmp = head;
LIST_HEAD(dummy);
int count = 0;
list_for_each_safe (cur, safe, head) {
count++;
if (count == k) {
list_cut_position(&dummy, tmp, cur);
q_reverse(&dummy);
list_splice_init(&dummy, tmp);
count = 0;
tmp = safe->prev;
}
}
}
以下的圖,不會畫出最後節點和 head 的連結。
假設有六個節點,要以三個節點為單位反轉 (k=3),當 count == 3
時, cur
會指向 3
。
執行完 list_cut_position(&dummy, tmp, cur)
,會形成兩個佇列。
透過 q_reverse
反轉。
最後,透過 list_splice_init(&dummy, tmp)
將兩個佇列連結成一個佇列,並更新 tmp
。 tmp
作用類似假的 head,紀錄下一次切分佇列和連結佇列的位置。
有用 Graphviz 畫出圖片很棒。
by yanjiew1
void q_sort(struct list_head *head)
{
if (!head || head->next == head->prev)
return;
head->prev->next = NULL;
head->next = merge_sort(head->next);
struct list_head *ptr = head;
for (; ptr->next; ptr = ptr->next)
ptr->next->prev = ptr;
ptr->next = head;
head->prev = ptr;
}
先將 queue 變成 singly-linked list ,這樣排序過程中就不用維持 doubly-linked list 。等到排序完畢後,再重新連結 prev
即可。
struct list_head *merge_two_queue(struct list_head *L1, struct list_head *L2)
{
struct list_head *head = NULL, **ptr = &head;
for (struct list_head **cur = NULL; L1 && L2; *cur = (*cur)->next) {
if (strcmp(container_of(L1, element_t, list)->value,
container_of(L2, element_t, list)->value) >= 0)
cur = &L2;
else
cur = &L1;
*ptr = *cur;
ptr = &(*ptr)->next;
}
*ptr = (struct list_head *) (void *) ((uintptr_t) (void *) L1 |
(uintptr_t) (void *) L2);
return head;
}
static struct list_head *merge_sort(struct list_head *head)
{
if (!head || !head->next)
return head;
struct list_head *slow = head, *fast = head->next;
for (; fast && fast->next; fast = fast->next->next, slow = slow->next)
;
fast = slow->next;
slow->next = NULL;
return merge_two_queue(merge_sort(head), merge_sort(fast));
}
merge_two_queue
只有 queue.c
檔案會用到,應該可在函式宣告前面加上 static
。
by yanjiew1
int q_descend(struct list_head *head)
{
if (!head)
return 0;
int len = 0;
struct list_head *cur = head->prev;
while (cur != head) {
len++;
if (cur->prev == head)
break;
element_t *c = container_of(cur, element_t, list),
*p = container_of(cur->prev, element_t, list);
if (strcmp(c->value, p->value) > 0) {
list_del(&p->list);
q_release_element(p);
len--;
} else {
cur = cur->prev;
}
}
return len;
}
反方向走訪佇列(沿著 prev
),當下一個節點小於當前節點的時候,刪除下一個節點。
雖然註解寫到 remove
,但實際上透過 make test
測試,會出現 ERROR: Freed queue, but 4 blocks are still allocated
。可見節點記憶體應該要被釋放。
int q_merge(struct list_head *head)
{
if (!head || list_empty(head))
return 0;
queue_contex_t *fir = container_of(head->next, queue_contex_t, chain);
if (head->next == head->prev)
return fir->size;
for (struct list_head *cur = head->next->next; cur != head;
cur = cur->next) {
queue_contex_t *que = container_of(cur, queue_contex_t, chain);
list_splice_init(que->q, fir->q);
que->size = 0;
}
q_sort(fir->q);
fir->size = q_size(fir->q);
return fir->size;
}
將所有佇列合併為單一佇列,再用 q_sort
排序。
q_merge
在題目有說明輸入的佇列會是排序好的,故若能利用這個特性,應該能讓效能快一點。
by yanjiew1
時間複雜度無法通過,應研究 論文 後改進 dudect 。
評分 95/100。
lib/list_sort.c
lib/list_sort.c
引入 list_sort
、 merge
和 merge_final
。
// original version
__attribute__((nonnull(2,3,4)))
static struct list_head *merge(void *priv, list_cmp_func_t cmp,
struct list_head *a, struct list_head *b);
__attribute__((nonnull(2,3,4,5)))
static void merge_final(void *priv, list_cmp_func_t cmp, struct list_head *head,
struct list_head *a, struct list_head *b);
__attribute__((nonnull(2,3)))
void list_sort(void *priv, struct list_head *head, list_cmp_func_t cmp);
將不需要的函式參數刪除: priv
、 cmp
移除 gcc function attributes
// modified version
static struct list_head *merge(struct list_head *a, struct list_head *b);
static void merge_final(struct list_head *head,
struct list_head *a,
struct list_head *b);
void list_sort(struct list_head *head);
if (cmp(priv, a, b) <= 0)
由於沒有 cmp
比較兩節點大小,以 strcmp
取代。
if (strcmp(container_of(a, element_t, list)->value,
container_of(b, element_t, list)->value) <= 0)
if (unlikely(!++count))
if (likely(bits))
移除 unlikely 和 likely 。
if (unlikely(!++count))
cmp(priv, b, b);
移除不需要的 callback 。
將更改後的內容加入 queue.c
,並將 list_sort
改名成 k_sort
。最後在 queue.h
加入宣告。
void k_sort(struct list_head *head);
qtest.c
#define ADD_COMMAND(cmd, msg, param) add_cmd(#cmd, do_##cmd, msg, param)
透過 ADD_COMMAND
加入新的命令 ksort
。 當執行 ksort
時,會呼叫 do_ksort
。 do_ksort
的實作和 do_sort
基本一樣,差別在於使用 q_sort
或 k_sort
。
if (current && exception_setup(true))
k_sort(current->q);
$ ./qtest
cmd> new
l = []
cmd> it RAND 1024
l = [dfbhi oanmcmnr izzsag sceioub ixjjsjxq txiyznfex kijdroox xmuwkozn xwbxkdla gdpyvh dowdm jajcua emhav yplcnr vcpmso vohlzpiz eufoh mztvqcejk nkssalg vfxht xgcroxdti nnlls gtkwfnpsq pyjaftapk wmubigy qmljqttm wgpunvu gikflv nrmaq akyeyznh ... ]
cmd> ksort
l = [aajqysvl aazwthv abcjtl abuesz abyhz ackqhst acvtglgo admii aedjfh aeebejmo afjcrke agbmqkj agcad agyhm ahhwvbl aivnzjrkl akjictu aknmc akxyymnjm akyeyznh amibbrkto ammlcie aowovx apmkz appjp apyuntj aqaeiywf aqerl aqweabl arsozaxi ... ]
測試後可正常執行。
可以嘗試透過實作新的 option
來切換排序演算法,可以用來比較不同排序演算法的效能。
by yanjiew1
lib/list_sort.c
和自己實作的 merge sort以 cpu cycles 作為評比的標準。為了讓實驗更加公平,兩方輸入的資料必須相同。故決定先將資料寫入 data.txt
後,再讓測試程式讀取資料運算, 計算 cpu cycles 的工作則由 perf report 執行。
# randstr.py
import random
import string
import subprocess
def set_cursor(choice):
if (choice):
print("\x1b[?25h",end='')
else:
print("\x1b[?25l",end='')
if __name__ == "__main__":
max_string_length = 1024
end = 10000000
set_cursor(False)
with open("data.txt","w") as f:
for i in range(end):
f.write(''.join(random.choices(string.ascii_letters + string.digits, k=max_string_length))+"\n")
print("{:.3f}%".format(i/end*100),end="\r")
set_cursor(True)
randstr.py
寫入隨機字串到 data.txt
,總計 end
行數,每一行字串長度為 max_string_length
。
int run(long count)
{
struct list_head *queue = q_new();
if (!queue) {
fprintf(stderr, "Can't allocate memory.\n");
return -1;
}
char *str = NULL;
long cnt = 0;
size_t len = 0;
errno = 0;
while (cnt < count && (getline(&str, &len, stdin) != -1)) {
char *nl = strchr(str, '\n');
if (nl)
*nl = '\0';
if (!q_insert_head(queue, str)) {
fprintf(stderr, "Can't allocate memory.\n");
q_free(queue);
free(str);
return -2;
}
cnt++;
}
free(str);
if (cnt != count) {
fprintf(stderr, "Stdin only has %ld string. We need %ld.", cnt, count);
q_free(queue);
return -3;
}
#ifdef KSORT
CPU_MEASURE_k_sort(queue);
#else
CPU_MEASURE_q_sort(queue);
#endif
#ifdef KSORT
puts("ksort:");
#else
puts("my sort:");
#endif
q_free(queue);
return 0;
}
從 stdin
讀取 count
數目的字串,並加入到佇列裡,再根據前置處理器決定使用 q_sort
或 k_sort
。並用 perf record 紀錄 cpu cycles 。
假設要輸入10000
個字串:
$ perf record -e cycles:u -F max -- ./my_sort 10000 < data.txt
由於 perf record 會紀錄全部的函式,但我們只對 k_sort
和 q_sort
相關的函式有興趣,所以將要紀錄的函式加上前綴 CPU_MEASURE
,方便 parse.py
作分析。
perf record 所產生的資料,使用 perf script 輸出後的部份結果。
my_sort 44505 72529.546820: 19401 cycles:u: ffffffff91c00b50 [unknown] ([unknown])
my_sort 44505 72529.546852: 19832 cycles:u: 7f53f099d488 [unknown] (/usr/lib/x86_64-linux-gnu/libc.so.6)
my_sort 44505 72529.546871: 20517 cycles:u: 5623dae61493 CPU_MEASURE_merge_sort+0x1e (/home/ko/code/Measure/my_sort)
可見函式名稱在倒數第二個欄位, cpu cycles 則位在第三個欄位。
import sys
total_cycles = 0
for line in sys.stdin:
if 'cycles:u:' in line:
function_name = line.split()[-2]
cycles = int(line.split()[3])
total_cycles += cycles
if 'CPU_MEASURE' in function_name:
total_cycles += cycles
input_size = int(sys.argv[1])
print(f"{input_size}:{total_cycles}")
{input_size}:{total_cycles}")
從 stdin
讀取資料後,作解析,把結果輸出到 stdout
。
CC = gcc
CFLAGS = -O1 -g -Wall
CFILES=queue.c measure.c
TOTAL:= 1000000
START=$(shell expr $(TOTAL) / 100)
all: my_sort ksort
my_sort: $(CFILES)
$(CC) -o $@ $(CFILES) $(CFLAGS)
ksort: $(CFILES)
$(CC) -o $@ $(CFILES) $(CFLAGS) -DKSORT
data.txt: randstr.py
python3 randstr.py
test: data.txt my_sort ksort plot.gp
rm -f my_sort.data kernel_sort.data
for i in $$(seq $(START) $(START) $(TOTAL)) ; do \
perf record -e cycles:u -F max -- ./my_sort $$i < data.txt ; \
perf script | python3 parse.py >> my_sort.data $$i ; \
perf record -e cycles:u -F max -- ./ksort $$i < data.txt ; \
perf script | python3 parse.py >> kernel_sort.data $$i ; \
done
gnuplot plot.gp
.PHONY: clean
clean:
rm -f *.o my_sort ksort
透過 TOTAL
決定最大的資料輸入量,再透過 START
和 seq
。將 TOTAL
拆分成 100 個節點,對每一個節點作測量。等全部實驗都做完後,使用 plot.gp
作圖。
set terminal pngcairo enhanced font 'Verdana,10'
set output "plot.png"
set xlabel "Number of string"
set ylabel "Total CPU cycles"
set datafile separator ":"
plot "my_sort.data" using 1:2 with linespoints title 'My sort', \
"kernel_sort.data" using 1:2 with linespoints title 'Linux sort'
可見當輸入的節點越多,兩者之間的差異越大。
linenoise
套用至 web
命令目前在執行過 web
命令後,會透過 console.c
的 cmd_select
函式來處理使用者輸入和網路伺服器。但 cmd_select
並沒有 linenoise
的諸多功能,例如:自動補齊、命令記憶等。此外,處理使用者輸入時,並沒有逾時機制。導致使用者若遲遲沒有輸入命令,那網路伺服器也無法處理請求。
解決方案:處理使用者輸入時,設置逾時機制,逾時後,轉而處理網頁伺服器請求。
char *linenoise(const char *prompt, int timeout);
新增 timeout
參數。
timeout
大於 0 時,函式會等待 timeout*0.1
秒,如果在這段時間內沒有輸入,則函式會立即返回timeout
等於 0 時,函式會立即返回,不會等待任何輸入timeout
小於 0 時,函式會一直等待使用者輸入 enter
,然後才返回。這樣可以保證函式在使用者確實輸入了一行文字後才返回NULL
並將 errno
設置為 EAGAIN
timeout
主要用在 enable_raw_mode
函式,透過 VMIN
和 VTIME
,來設定阻塞或是逾時模式。
在 enable_raw_mode
加入以下程式碼:
if (timeout < 0) {
/* blocking mode */
raw.c_cc[VMIN] = 1;
raw.c_cc[VTIME] = 0;
} else {
/* timeout mode */
raw.c_cc[VMIN] = 0;
raw.c_cc[VTIME] = timeout;
}
Case C: MIN=0, TIME>0
In case C, since MIN=0, TIME no longer represents an inter-byte timer. It now serves as a read timer that shall be activated as soon as the read() function is processed. A read shall be satisfied as soon as a single byte is received or the read timer expires. Note that in case C if the timer expires, no bytes shall be returned. If the timer does not expire, the only way the read can be satisfied is if a byte is received. If bytes are not received, the read shall not block indefinitely waiting for a byte; if no byte is received within TIME*0.1 seconds after the read is initiated, the read() shall return a value of zero, having read no data. If data is in the buffer at the time of the read(), the timer shall be started as if data has been received immediately after the read().
Case D: MIN=0, TIME=0
The minimum of either the number of bytes requested or the number of bytes currently available shall be returned without waiting for more bytes to be input. If no characters are available, read() shall return a value of zero, having read no data.
由此可知,逾時觸發後, read
會回傳 0 。故要將 linenoise
對於 read
回傳值的處理作相對應的變更。
complete_line
的程式碼原先的版本:
int nread = read(ls->ifd, &c, 1);
if (nread <= 0) {
free_completions(&lc);
return -1;
}
變更後的版本:
int nread = read(ls->ifd, &c, 1);
if (nread < 0) {
free_completions(&lc);
return nread;
} else if (!nread) {
c = 0;
}
當 nread
等於 0 時,將 c
值設定為 0 ,並執行後續操作。
此實作存在問題:
在逾時模式下,兩個 tab 間隔太長進而觸發逾時,將會重複進入 complete_line
。導致自動補完會重複顯示第一個提示,而不是依序顯示。
原因: complete_line
使用區域變數 i
紀錄當前的命令提示次序。
line_edit
的程式碼原先的版本:
nread = read(l.ifd, &c, 1);
if (nread <= 0)
return l.len;
變更後的版本:
nread = read(l.ifd, &c, 1);
if (nread <= 0) {
if (!nread)
errno = EAGAIN;
return l.len;
}
line_edit
在兩個模式下都要立即回傳,唯一的差別在,逾時模式下,要將 errno
值設為 EAGAIN
$ cppcheck --version
Cppcheck 2.7
$ git commit -a
Following files need to be cleaned up:
queue.c
report.c:58:18: style: Variable 'msg_name_text' can be declared with const [constVariable]
static char *msg_name_text[N_MSG] = {
^
Fail to pass static analysis.
在執行 pre-commit-hook
會出現以上錯誤。將 cppcheck
版本更新至 2.10 ,便不會報錯。
利用 Cppcheck 的 --suppress
選項,抑制上述警告,可見 Cppcheck manual。稍後提交 pull request。
jserv
已提交 pull request
如果採用上述 pull request ,在 Cppcheck 2.10 下,因為不會觸發警告,所以會觸發 Unmatched suppression 。
report.c:59:0: information: Unmatched suppression: constVariable [unmatchedSuppression]
static char *msg_name_text[N_MSG] = {
在 pre-commit.hook 加入以下內容,即可抑制 Unmatched suppression 。
--suppress=unmatchedSuppression:report.c
參見 commit 0180045
jserv
如果在原檔案更改,會呈現以下內容:
新增在第 10 行。
#!/usr/bin/env bash
CPPCHECK_suppresses="--inline-suppr harness.c --suppress=unmatchedSuppression:harness.c \
--suppress=missingIncludeSystem \
--suppress=noValidConfiguration \
--suppress=unusedFunction \
--suppress=unmatchedSuppression:qtest.c \
--suppress=identicalInnerCondition:log2_lshift16.h \
--suppress=nullPointerRedundantCheck:report.c \
--suppress=unmatchedSuppression:report.c \
--suppress=nullPointerRedundantCheck:harness.c \
--suppress=nullPointer:queue.c \
--suppress=nullPointer:qtest.c \
--suppress=unmatchedSuppression:queue.c"