Try   HackMD

2023q1 Homework1 (lab0)

contributed by < komark06 >

Reviewed by yanjiew1

  • 程式碼風格大致上符合要求,但向下方迴圈內只有一個敘述時,應可省略大括號:
list_for_each_entry_safe (cur, safe, l, list)
    q_release_element(cur);
  • Git 分支 master 只有存放原本 fork 進來的程式碼,而你的實作是放在 beta 分支。建議把預設分支改為 beta
  • Commit message 中(例如: e7b9d4f),英文的句號 . 後面應該有一個空格,再接下一個句子比較好。
  • 仍然有些作業要求沒有達到:
    • 提供 shuffle 指令,並分析亂度
    • 觀察 entropy
    • 實作不同的亂數產生器
    • 研讀論文〈Dude, is my code constant time?
    • dudect 程式改善
  • 使用 Graphviz 圖片來解說程式很棒 (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 測試的順序作為開發的順序。

q_new 和 q_free 實作

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 後,無法往下一個節點前進。

q_insert_head 和 q_insert_tail 實作

為了避免重複的程式碼,透過 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_elementq_insert_headq_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;
}

q_remove_head 和 q_remove_tail 實作

如同 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_headq_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 。

q_size 實作

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 走訪每一個節點來紀錄節點總數。

q_delete_mid 實作

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

q_delete_dup 實作

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 執行速度的關鍵。 考量以 strlenmemcmp 取代 strcmp 。先用簡單的實驗測量兩者的 benchmark。

q_swap 實作

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 的實作更加直觀

q_reverse 實作

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);
    }
}

依序走訪每一個節點,並移動節點到佇列的開頭,就會是一個反轉的佇列。

q_reverseK 實作

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







%0



h

head



1

1



h->1





1->h





2

2



1->2





2->1





3

3



2->3





3->2





4

4



3->4





4->3





5

5



4->5





5->4





6

6



5->6





6->5





cur

cur



cur->3





執行完 list_cut_position(&dummy, tmp, cur) ,會形成兩個佇列。







%0



d

dummy



1

1



d->1





1->d





2

2



1->2





2->1





3

3



2->3





3->2





h

head



4

4



h->4





4->h





5

5



4->5





5->4





6

6



5->6





6->5





透過 q_reverse 反轉。







%0



d

dummy



3

3



d->3





3->d





2

2



3->2





2->3





1

1



2->1





1->2





h

head



4

4



h->4





4->h





5

5



4->5





5->4





6

6



5->6





6->5





最後,透過 list_splice_init(&dummy, tmp) 將兩個佇列連結成一個佇列,並更新 tmptmp 作用類似假的 head,紀錄下一次切分佇列和連結佇列的位置。







%0



h

head



3

3



h->3





3->h





2

2



3->2





2->3





1

1



2->1





1->2





4

4



1->4





4->1





5

5



4->5





5->4





6

6



5->6





6->5





tmp

tmp



tmp->1





有用 Graphviz 畫出圖片很棒。

by yanjiew1

q_sort 實作

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

q_descend 實作

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 。可見節點記憶體應該要被釋放。

q_merge 實作

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_sortmergemerge_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);

將不需要的函式參數刪除: privcmp
移除 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 。

參考資料:likely and unlikely macro

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_ksortdo_ksort 的實作和 do_sort 基本一樣,差別在於使用 q_sortk_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_sortk_sort 。並用 perf record 紀錄 cpu cycles 。
假設要輸入10000 個字串:

$ perf record -e cycles:u -F max -- ./my_sort 10000 < data.txt

由於 perf record 會紀錄全部的函式,但我們只對 k_sortq_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

Makefile 和 gnuplot script

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 決定最大的資料輸入量,再透過 STARTseq 。將 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.ccmd_select 函式來處理使用者輸入和網路伺服器。但 cmd_select 並沒有 linenoise 的諸多功能,例如:自動補齊、命令記憶等。此外,處理使用者輸入時,並沒有逾時機制。導致使用者若遲遲沒有輸入命令,那網路伺服器也無法處理請求。

解決方案:處理使用者輸入時,設置逾時機制,逾時後,轉而處理網頁伺服器請求。

Loop
timeout
no timeout
linenoise
user's input
web request
Start

新增逾時機制

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 函式,透過 VMINVTIME ,來設定阻塞或是逾時模式。

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;
}

General Terminal Interface

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 回報錯誤

$ 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。
:notes: 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
:notes: 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"