2021q1 Homework1 (lab0)

contributed by < Julan-Chu >

tags: linux2021

注意共筆書寫規範：中英文之間用一個半形空白字元區隔。 jserv

感謝老師提醒 已修正排版

Environment

使用 WSL2, 目前 perf 工具無法安裝，gnuplot 需要使用 xserver，之後會安裝雙系統

Linux MSI 4.19.104-microsoft-standard 
gcc (Ubuntu 9.3.0-17ubuntu1~20.04) 9.3.0

How to test code

make test make check ./qtest

Requirement

• q_new: 建立新的「空」佇列;
• q_free: 釋放佇列所佔用的記憶體;
• q_insert_head: 在佇列開頭 (head) 加入 (insert) 給定的新元素 (以 LIFO 準則);
• q_insert_tail: 在佇列尾端 (tail) 加入 (insert) 給定的新元素 (以 FIFO 準則);
• q_remove_head: 在佇列開頭 (head) 移去 (remove) 給定的元素。
• q_size: 計算佇列中的元素數量。
• q_reverse: 以反向順序重新排列鏈結串列，該函式不該配置或釋放任何鏈結串列元素，換言之，它只能重排已經存在的元素;
• q_sort: 「Linux 核心設計」課程所新增，以遞增順序來排序鏈結串列的元素，可參閱 Linked List Sort 得知實作手法;

Implementation

O(1) insert_tail and size

queue.h

/* Queue structure */
typedef struct {
    list_ele_t *head; /* Linked list of elements */
    list_ele_t *tail;
    int size;
} queue_t;

q_new 與 q_free 的過程與 alloc 和 free 的過程有雷同之處， block 相當於 list_ele_t

q_new

queue_t *q_new()
{
    queue_t *q = malloc(sizeof(queue_t));
    if (!q)
        return NULL;
    q->head = NULL;
    q->tail = NULL;
    q->size = 0;
    return q;
}

q_free

/* Free all storage used by queue */
void q_free(queue_t *q)
{
    if (!q)
        return;
    /* Free queue structure */
    list_ele_t *node = q->head;
    while (node) {
        free(node->value);
        list_ele_t *tmp = node;
        node = node->next;
        free(tmp);
    }

    free(q);
}

q_insert_head q_insert_tail

兩者皆相似，需注意的議題

• strlen 與 '\0' termination
• strcpy
• 起始為 NULL 的問題 ps: 建議可以增加對 insert_tail to empty queue 的測試

bool q_insert_head(queue_t *q, char *s)
{
    list_ele_t *newh;
    if (!q)
        return false;

    newh = malloc(sizeof(list_ele_t));
    if (!newh)
        return false;

    newh->value = malloc(sizeof(char) * (strlen(s) + 1));
    if (!newh->value) {
        free(newh);
        return false;
    }
    newh->next = NULL;

    strlcpy(newh->value, s, strlen(s) + 1);
    newh->next = q->head;
    if (!q->head) {
        q->tail = newh;
    }
    q->head = newh;
    q->size++;
    return true;
}

q_remove_head

第一版實作有問題

bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
    if (!q || !q->head)
        return false;

    list_ele_t *node = q->head;
    if (sp) {
        strncpy(sp, node->value, bufsize - 1);
        sp[bufsize - 1] = '\0';
    }

    q->head = q->head->next;
    free(node->value);
    free(node);
    q->size--;
    return true;
}

以上通過17個 testcase，但在手動測試發現錯誤

Steps to reproduce bug

valgrind --leak-check=full ./qtest
 
cmd> new
q = []
cmd> ih aa
q = [aa]
cmd> ih bb
q = [bb aa]
cmd> rh
Removed bb from queue
q = [aa]
cmd> rh
Removed aa from queue
q = []
cmd> rh
Warning: Calling remove head on empty queue
Removal from queue failed
q = []
cmd> it cc
==1937== Invalid write of size 8
==1937==    at 0x10E3E1: q_insert_tail (queue.c:107)
==1937==    by 0x10B9BC: do_insert_tail (qtest.c:299)
==1937==    by 0x10CE09: interpret_cmda (console.c:221)
==1937==    by 0x10D2A0: interpret_cmd (console.c:244)
==1937==    by 0x10DD4D: run_console (console.c:660)
==1937==    by 0x10C263: main (qtest.c:780)
==1937==  Address 0x4ba4e98 is 40 bytes inside a block of size 56 free'd
==1937==    at 0x483CA3F: free (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==1937==    by 0x10DFDA: test_free (harness.c:209)
==1937==    by 0x10E471: q_remove_head (queue.c:135)
==1937==    by 0x10B57A: do_remove_head (qtest.c:366)
==1937==    by 0x10CE09: interpret_cmda (console.c:221)
==1937==    by 0x10D2A0: interpret_cmd (console.c:244)
==1937==    by 0x10DD4D: run_console (console.c:660)
==1937==    by 0x10C263: main (qtest.c:780)
==1937==  Block was alloc'd at
==1937==    at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==1937==    by 0x10DE22: test_malloc (harness.c:138)
==1937==    by 0x10E2BB: q_insert_head (queue.c:57)
==1937==    by 0x10BC57: do_insert_head (qtest.c:214)
==1937==    by 0x10CE09: interpret_cmda (console.c:221)
==1937==    by 0x10D2A0: interpret_cmd (console.c:244)
==1937==    by 0x10DD4D: run_console (console.c:660)
==1937==    by 0x10C263: main (qtest.c:780)
==1937== Invalid read of size 8
==1937==    at 0x10E3E9: q_insert_tail (queue.c:108)
==1937==    by 0x10B9BC: do_insert_tail (qtest.c:299)
==1937==    by 0x10CE09: interpret_cmda (console.c:221)
==1937==    by 0x10D2A0: interpret_cmd (console.c:244)
==1937==    by 0x10DD4D: run_console (console.c:660)
==1937==    by 0x10C263: main (qtest.c:780)
==1937==
Segmentation fault occurred.  You dereferenced a NULL or invalid pointer

原因為當移除最後一個 node 時，沒有將 tail 指向 NULL

//修改後
bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
    if (!q || !q->head)
        return false;

    list_ele_t *node = q->head;
    if (sp) {
        strncpy(sp, node->value, bufsize - 1);
        sp[bufsize - 1] = '\0';
    }

    q->head = q->head->next;
    // 新增檢查
    if (!q->head) {
        q->tail = NULL;
    }
    free(node->value);
    free(node);
    q->size--;
    return true;
}

ps: 建議可以增加 test case

q_size

int q_size(queue_t *q)
{
    if (!q)
        return 0;
    return q->size;
}

q_reverse

void q_reverse(queue_t *q)
{
    if (!q || q->size <= 1)
        return;

    list_ele_t *curr, *next;
    curr = q->head;

    while (curr->next) {
        next = curr->next;
        curr->next = next->next;
        next->next = q->head;
        q->head = next;
    }
    q->tail = curr;
}

q_sort

應用 merge sort + fast slow pointers 實作

void q_sort(queue_t *q)
{
    if (!q || !q->head)
        return;
    q->head = merge_sort(q->head);
    while (q->tail->next) {
        q->tail = q->tail->next;
    }
}

list_ele_t *merge_sort(list_ele_t *node)
{
    if (!node)
        return NULL;
    if (!node->next)
        return node;
    list_ele_t *slow = node, *fast = node->next;
    while (fast->next && fast->next->next) {
        slow = slow->next;
        fast = fast->next->next;
    }
    list_ele_t *mid = slow->next;
    slow->next = NULL;

    list_ele_t *left, *right;
    left = merge_sort(node);
    right = merge_sort(mid);

    return merge_sort_two_nodes(left, right);
}

list_ele_t *merge_sort_two_nodes(list_ele_t *a, list_ele_t *b)
{
    if (!b)
        return a;
    if (!a)
        return b;

    list_ele_t *head = NULL;
    list_ele_t **indirect = &head;

    while (a && b) {
        if (strcmp(a->value, b->value) < 0) {
            *indirect = a;
            a = a->next;
        } else {
            *indirect = b;
            b = b->next;
        }
        indirect = &(*indirect)->next;
    }

    if (a) {
        *indirect = a;
    }

    if (b) {
        *indirect = b;
    }
    return head;
}

Learn from implementation

string 的實際長度需要考慮 ’\0’ termination

The strlen() function calculates the length of the string pointed to by s, excluding the terminating null byte ('\0').

strcpy is unsafe

strcpy本身不會檢查目的地記憶體空間大小，可能會導致資料寫到目的地以外的空間

Dangerous function detected in /home/julian/repos/lab0-c/queue.c
64:   strcpy(newh->value, s);
91:   strcpy(nrwt->value, s);

Read 'Common vulnerabilities giude for C programmers' carefuly.
    https://security.web.cern.ch/recommendations/en/codetools/c.shtml

文字訊息不要用圖片展現，不僅不利於排版，日後也不易檢索文字，更對視覺障礙的朋友不友善。 jserv

感謝老師提醒 已替換

cern 建議使用 strlcpy ( BSD 內建)，自行撰寫也很簡單 ps: strlcpy 同時也保證 '\0' termination

#ifndef strlcpy
#define strlcpy(dst,src,sz) snprintf((dst), (sz), "%s", (src))
#endif

malloc 不等於 initialize，只會 allocate space，回傳的 space還是有 garbage values

• malloc 後沒有將 next 指向 NULL

cmd> new
q = []
cmd> ih a
a
q = [a ... ]
ERROR:  Either list has cycle, or queue has more than 1 elements

malloc 後 newh.next 不為 NULL

c99:

The malloc function allocates space for an object whose size is specified by size and whose value is indeterminate.

man malloc:

The malloc() function allocates size bytes and returns a pointer to the allocated memory. The memory is not initialized. If size is 0, then malloc() returns either NULL, or a unique pointer value that can later be successfully passed to free().

嘗試更有品味一點

• 修改 q_reverse

// 修改前
void q_reverse(queue_t *q)
{
    if (!q || q->size <= 1)
        return;

    list_ele_t *prev, *curr, *tmp;
    prev = NULL;
    curr = q->head;

    while (curr) {
        tmp = curr->next;
        if (!tmp) {
            curr->next = prev;
            prev = curr;
            break;
        }
        curr->next = prev;
        prev = curr;
        curr = tmp;
    }
    q->tail = q->head;
    q->head = prev;
}

// 修改後
void q_reverse(queue_t *q)
{
    if (!q || q->size <= 1)
        return;

    list_ele_t *curr, *next;
    curr = q->head;

    while (curr->next) {
        next = curr->next;
        curr->next = next->next;                                                                                                                                                                                         next->next = q->head;
        q->head = next;
    }
    q->tail = curr;
}

• 利用 NULL evalutes as false 簡化 Null check

newt = malloc(sizeof(list_ele_t));
if (newt == NULL)
    return false;
// 修改後
if (!(newt = malloc(sizeof(list_ele_t))))
    return false;

NULL as false 相關

c99

An integer constant expression with the value 0, or such an expression cast to type void *, is called a null pointer constant.⁽⁶⁶ If a null pointer constant is converted to a pointer type, the resulting pointer, called a null pointer, is guaranteed to compare unequal to a pointer to any object or function.

66) The macro ++NULL+= is defined in <stddef.h> (and other headers) as a null pointer constant; see 7.19.

The result of the logical negation operator ! is 0 if the value of its operand compares unequal to 0, 1 if the value of its operand compares equal to 0. The result has type int. The expression !E is equivalent to (0==E).

所以NULL可以視為0，而 if(!NULL) 等同於if(0==NULL)

source: stackoverflow

額外思考: 採用這種語法可以讓code更為簡潔，但golang/C#/java不能將null當成bool判斷使用, 而python/javascript可以，背後的設計概念是什麼或是實作上是否有難度?

• 利用 pointer to pointer 簡化 merge_sort_two_nodes

// 修改前
list_ele_t *merge_sort_two_nodes(list_ele_t *a, list_ele_t *b)
{
    if (!b)
        return a;
    if (!a)
        return b;

    list_ele_t *head, *curr;

    if (strcmp(a->value, b->value) < 0) {
        head = a;
        curr = a;
        a = a->next;
    } else {
        head = b;
        curr = b;
        b = b->next;
    }

    while (a && b) {
        if (strcmp(a->value, b->value) < 0) {
            curr->next = a;
            a = a->next;
        } else {
            curr->next = b;
            b = b->next;
        }
        curr = curr->next;
    }

    if (a) {
        curr->next = a;
    }

    if (b) {
        curr->next = b;
    }
    return head;
}  

// 應用 pointer to pointer 修改後
list_ele_t *merge_sort_two_nodes(list_ele_t *a, list_ele_t *b)
{
    if (!b)
        return a;
    if (!a)
        return b;

    list_ele_t *head = NULL;
    list_ele_t **indirect = &head;
    
    while (a && b) {
        if (strcmp(a->value, b->value) < 0) {
            *indirect = a;
            a = a->next;
        } else {
            *indirect = b;
            b = b->next;
        }
        indirect = &(*indirect)->next;
    }

    if (a) {
        *indirect = a;
    }

    if (b) {
        *indirect = b;
    }
    return head;
}

修正 qtest 的錯誤

Tasks

• 開啟 Address Sanitizer，修正 qtest 執行過程中的錯誤，先執行 qtest 再於命令提示列輸入 help 命令，會使 開啟 Address Sanitizer 觸發錯誤，應予以排除
• 運用 Valgrind 排除 qtest 實作的記憶體錯誤，並透過 Massif 視覺化 “simulation” 過程中的記憶體使用量，需要設計對應的實驗

額外參考資料 Sanitize your C++ PDF Video

global buffer overflow

Steps

make clean
make SANITIZER=1
./qtest
cmd> help
...
=================================================================
==4700==ERROR: AddressSanitizer: global-buffer-overflow on address 0x55e9e0da8400 at pc 0x55e9e0d917bd bp 0x7fff621ce820 sp 0x7fff621ce810
READ of size 4 at 0x55e9e0da8400 thread T0
    #0 0x55e9e0d917bc in do_help_cmd /home/julian/repos/lab0-c/console.c:307
    #1 0x55e9e0d918d0 in interpret_cmda /home/julian/repos/lab0-c/console.c:221
    #2 0x55e9e0d920b5 in interpret_cmd /home/julian/repos/lab0-c/console.c:244
    #3 0x55e9e0d937f8 in run_console /home/julian/repos/lab0-c/console.c:660
    #4 0x55e9e0d903e5 in main /home/julian/repos/lab0-c/qtest.c:780
    #5 0x7f82536770b2 in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x270b2)
    #6 0x55e9e0d8db8d in _start (/home/julian/repos/lab0-c/qtest+0x8b8d)

0x55e9e0da8401 is located 0 bytes to the right of global variable 'echo' defined in 'console.c:59:13' (0x55e9e0da8400) of size 1
SUMMARY: AddressSanitizer: global-buffer-overflow /home/julian/repos/lab0-c/console.c:307 in do_help_cmd
Shadow bytes around the buggy address:

先查看 error message 提示程式碼有問題的部分 0x55e9e0da8401 is located 0 bytes to the right of global variable 'echo' defined in 'console.c:59:13' (0x55e9e0da8400) of size 1

SUMMARY: AddressSanitizer: global-buffer-overflow /home/julian/repos/lab0-c/console.c:307 in do_help_cmd Shadow bytes around the buggy address:

59 static bool echo = 0;
.....
296 static bool do_help_cmd(int argc, char *argv[])
297 {
298     cmd_ptr clist = cmd_list;
299     report(1, "Commands:", argv[0]);
300     while (clist) {
301         report(1, "\t%s\t%s", clist->name, clist->documentation);
302         clist = clist->next;
303     }
304     param_ptr plist = param_list;
305     report(1, "Options:");
306     while (plist) {
307         report(1, "\t%s\t%d\t%s", plist->name, *plist->valp,
308                plist->documentation);
309         plist = plist->next;
310     }
311     return true;
312 }

先閱讀相關的 param_ptr struct, report function, 以及調用 echo的地方

 31 /* Integer-valued parameters */
 32 typedef struct PELE param_ele, *param_ptr;
 33 struct PELE {
 34     char *name;
 35     int *valp;
 36     char *documentation;
 37     /* Function that gets called whenever parameter changes */
 38     setter_function setter;
 39     param_ptr next;
 40 };

 91 void report(int level, char *fmt, ...)
 92 {
 93     if (!verbfile)
 94         init_files(stdout, stdout);
 95
 96     if (level <= verblevel) {
 97         va_list ap;
 98         va_start(ap, fmt);
 99         vfprintf(verbfile, fmt, ap);
100         fprintf(verbfile, "\n");
101         fflush(verbfile);
102         va_end(ap);
103
104         if (logfile) {
105             va_start(ap, fmt);
106             vfprintf(logfile, fmt, ap);
107             fprintf(logfile, "\n");
108             fflush(logfile);
109             va_end(ap);
110         }
111     }
112 }

110     add_param("echo", (int *) &echo, "Do/don't echo commands", NULL); 

可以看到這邊為了符合 add_param 的方法簽章利用 pointer to int 去操作 bool 型別的 echo 變數， 重看錯誤訊息，由 0x55e9e0da8400(echo, bool 1 byte) 開始讀取 4 bytes(int type)，在 0x55e9e0da8401(next address to echo) 發生錯誤，將 echo 改為 int 就可以修正這個問題

/* static bool echo = 0; */
static int echo = 0;

simulation 變數也有一樣的問題

/* bool simulation = false; */
int simulation = 0;

• 思考: 是否有其他方式設計可以相容不同 data type? 例如 struct 含有 型別資訊跟 void* 或 char*(string) 之一
• 查詢資料才發現 C99 之前是沒有 bool type的

錯誤? valgrind: blocks are still reachable

Steps

valgrind ./qtest  -f traces/trace-12-malloc.cmd
 
...
cmd>
Freeing queue
==597== 4 bytes in 1 blocks are still reachable in loss record 1 of 3
==597==    at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==597==    by 0x4A4E50E: strdup (strdup.c:42)
==597==    by 0x1100AF: linenoiseHistoryAdd (linenoise.c:1236)
==597==    by 0x110C42: linenoiseHistoryLoad (linenoise.c:1325)
==597==    by 0x10C22C: main (qtest.c:769)
==597==
==597== 110 bytes in 19 blocks are still reachable in loss record 2 of 3
==597==    at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==597==    by 0x4A4E50E: strdup (strdup.c:42)
==597==    by 0x110023: linenoiseHistoryAdd (linenoise.c:1236)
==597==    by 0x110C42: linenoiseHistoryLoad (linenoise.c:1325)
==597==    by 0x10C22C: main (qtest.c:769)
==597==
==597== 160 bytes in 1 blocks are still reachable in loss record 3 of 3
==597==    at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==597==    by 0x11006F: linenoiseHistoryAdd (linenoise.c:1224)
==597==    by 0x110C42: linenoiseHistoryLoad (linenoise.c:1325)
==597==    by 0x10C22C: main (qtest.c:769)
==597== 

看起來都是 linenoiseHistory 相關的問題，前兩個警告都是針對 strdup ， strdup 會在函數內部做 malloc ，等仍然需要對回傳的 char* 做 free

檢查 linenoise.c以下程式碼，可以看到 strdup 到 return 之間都沒有針對 linecopy 做 free

1236     linecopy = strdup(line);
1237     if (!linecopy)
1238         return 0;
1239     if (history_len == history_max_len) {
1240         free(history[0]);
1241         memmove(history, history + 1, sizeof(char *) * (history_max_len - 1));
1242         history_len--;
1243     }
1244     history[history_len] = linecopy;
1245     history_len++;
1246     return 1;

新增對 free(linecopy)

1244     history[history_len] = linecopy;
1245     if (linecopy) 
1246          free(linecopy); 
1247     history_len++;
1248     return 1;

再次執行 valgrind ./qtest -f traces/trace-12-malloc.cmd ，可以看到針對strdup的警告已經消失

cmd>
Freeing queue
==1512== 160 bytes in 1 blocks are still reachable in loss record 1 of 1
==1512==    at 0x483B7F3: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==1512==    by 0x11006F: linenoiseHistoryAdd (linenoise.c:1224)
==1512==    by 0x110C4A: linenoiseHistoryLoad (linenoise.c:1327)
==1512==    by 0x10C22C: main (qtest.c:769)
==1512==

剩下一個問題，研究中

更新想法，以上述修正 strdup 後，在其他測試出現了寫入 free'd 的錯誤， 目前最新猜測是 history 沒有被 free ，

valgrind --leak-check=full --show-leak-kinds=all -v ./qtest -f ./traces/trace-12-malloc.cmd

==2003==
==2003== HEAP SUMMARY:
==2003==     in use at exit: 170 bytes in 3 blocks
==2003==   total heap usage: 141 allocs, 138 frees, 18,787 bytes allocated
==2003==
==2003== 5 bytes in 1 blocks are still reachable in loss record 1 of 3
==2003==    at 0x4C31B0F: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==2003==    by 0x5279AF9: strdup (strdup.c:42)
==2003==    by 0x10F1C9: linenoiseHistoryAdd (linenoise.c:1236)
==2003==    by 0x10FD7F: linenoiseHistoryLoad (linenoise.c:1325)
==2003==    by 0x10B48B: main (qtest.c:769)
==2003==
==2003== 5 bytes in 1 blocks are still reachable in loss record 2 of 3
==2003==    at 0x4C31B0F: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==2003==    by 0x5279AF9: strdup (strdup.c:42)
==2003==    by 0x10F142: linenoiseHistoryAdd (linenoise.c:1236)
==2003==    by 0x10FD7F: linenoiseHistoryLoad (linenoise.c:1325)
==2003==    by 0x10B48B: main (qtest.c:769)
==2003==
==2003== 160 bytes in 1 blocks are still reachable in loss record 3 of 3
==2003==    at 0x4C31B0F: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==2003==    by 0x10F18E: linenoiseHistoryAdd (linenoise.c:1224)
==2003==    by 0x10FD7F: linenoiseHistoryLoad (linenoise.c:1325)
==2003==    by 0x10B48B: main (qtest.c:769)
==2003==
==2003== LEAK SUMMARY:
==2003==    definitely lost: 0 bytes in 0 blocks
==2003==    indirectly lost: 0 bytes in 0 blocks
==2003==      possibly lost: 0 bytes in 0 blocks
==2003==    still reachable: 170 bytes in 3 blocks
==2003==         suppressed: 0 bytes in 0 blocks
==2003==
==2003== For counts of detected and suppressed errors, rerun with: -v
==2003== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)

根據 valgrind faq 5.2

"still reachable" means your program is probably ok – it didn't free some memory it could have. This is quite common and often reasonable. Don't use –show-reachable=yes if you don't want to see these reports.

在 qtest.main 中 嘗試呼叫 freeHistory 後產生新的錯誤

==2917== Invalid read of size 8
==2917==    at 0x10E073: freeHistory (linenoise.c:1196)
==2917==    by 0x10E164: linenoiseAtExit (linenoise.c:1205)
==2917==    by 0x521F160: __run_exit_handlers (exit.c:108)
==2917==    by 0x521F259: exit (exit.c:139)
==2917==    by 0x51FDBFD: (below main) (libc-start.c:344)
==2917==  Address 0x55cec60 is 0 bytes inside a block of size 160 free'd
==2917==    at 0x4C32D3B: free (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==2917==    by 0x10E08B: freeHistory (linenoise.c:1197)
==2917==    by 0x10FDFD: linenoiseClose (linenoise.c:1332)
==2917==    by 0x10B4C8: main (qtest.c:783)
==2917==  Block was alloc'd at
==2917==    at 0x4C31B0F: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==2917==    by 0x10F1A1: linenoiseHistoryAdd (linenoise.c:1224)
==2917==    by 0x10FD92: linenoiseHistoryLoad (linenoise.c:1325)
==2917==    by 0x10B48B: main (qtest.c:769)
==2917==
==2917== Invalid free() / delete / delete[] / realloc()
==2917==    at 0x4C32D3B: free (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==2917==    by 0x10E07A: freeHistory (linenoise.c:1196)
==2917==    by 0x10E164: linenoiseAtExit (linenoise.c:1205)
==2917==    by 0x521F160: __run_exit_handlers (exit.c:108)
==2917==    by 0x521F259: exit (exit.c:139)
==2917==    by 0x51FDBFD: (below main) (libc-start.c:344)
==2917==  Address 0x55ced40 is 0 bytes inside a block of size 5 free'd
==2917==    at 0x4C32D3B: free (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==2917==    by 0x10E07A: freeHistory (linenoise.c:1196)
==2917==    by 0x10FDFD: linenoiseClose (linenoise.c:1332)
==2917==    by 0x10B4C8: main (qtest.c:783)
==2917==  Block was alloc'd at
==2917==    at 0x4C31B0F: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==2917==    by 0x5279AF9: strdup (strdup.c:42)
==2917==    by 0x10F1DC: linenoiseHistoryAdd (linenoise.c:1236)
==2917==    by 0x10FD92: linenoiseHistoryLoad (linenoise.c:1325)
==2917==    by 0x10B48B: main (qtest.c:769)

目前排除失敗。 思考: history 是該手動 free 的對象嗎， still reachable 是該處理的錯誤嗎?

Massif for simulation mode

valgrind --tool=massif ./qtest
cmd> option simulation 1
cmd> it
Probably constant time
cmd> quit
Freeing queue

Coroutine

jump

從 c11 有提到 jump 的部分有 goto 跟 setjmp

C11 6.8.6.1 The goto statment A goto statement causes an unconditional jump to the statement prefixed by the named label in the enclosing function.

C11 7.13 Nonlocal jumps<setjmp.h>

兩者的區別為 :

• goto 利用 label， 只可以在 function 內切換
• setjmp 利用 jmp_buf 記錄當下 function 的狀態，利用 longjmp 切換到目標 function 的 jmp_buf

主要的兩個方法

int setjmp(jmp_buf env); jmp_buf 當前 function 的資訊 void longjmp(jmp_buf env, int val); jmp_buf 目標 function 的資訊

longjmp 會傳遞 val 給 setjmp ， 可以利用回傳值作判斷， 另外要注意的是， longjmp 無法讓 setjmp 回傳 0 ，需要特別注意

If the return is from a direct invocation, the setjmp macro returns the value zero. If the return is from a call to the longjmp function, the setjmp macro returns a nonzero value.

After longjmp is completed, thread execution continues as if the corresponding invocation of the setjmp macro had just returned the value specified by val. The longjmp function cannot cause the setjmp macro to return the value 0; if val is 0, the setjmp macro returns the value 1.

利用setjmp回傳值做判斷:

#include <setjmp.h>
#include <stdio.h> 

int main() {
  jmp_buf env;
  int val;

  val = setjmp(env);

  printf("val is %d\n", val);

  switch (val) {
  case 0:
    printf("init\n");
    longjmp(env, 1);
    break;
  case 1:
    printf("do more\n");
    longjmp(env, 2);
    break;
  default:
    printf("end\n");
  }

  return 0;
}

嘗試使用 setjmp 和 longjmp 整合 web 指令: 失敗

先用 for(;;) 模擬 long running web server， server_jmp_buf 與 console_jmp_buf 分別為 web server 跟 console 的 jmp_buf， 在 forloop 內設置 setjmp 以及 longjmp， 同時新增 web command

#define SERVER_FINISHED -1

jmp_buf server_jmp_buf, console_jmp_buf;

static void start_web_srv()
{
    for (;;) {
        switch (setjmp(server_jmp_buf)) {
        case 0:
            printf("server is starting...");
            break;
        case -1:
            printf("server is finishing");
            break;
        default:
            printf("server is running");
        }
        longjmp(console_jmp_buf, 1);
        printf("after longjmp");
    }
}

static bool do_web_cmd(int argc, char *argv[])
{
    printf("jmp_count:%d\n", jmp_count);

    if (webserver_state != 1) {
        webserver_state = 1;
        start_web_srv();
    }
    return true;
}

改寫 run_console 利用全局的 webserver_state 變數，決定是否進行console 跟 server 之間的切換

bool run_console(char *infile_name)
{
    if (!push_file(infile_name)) {
        report(1, "ERROR: Could not open source file '%s'", infile_name);
        return false;
    }

    if (!has_infile) {
        setjmp(console_jmp_buf)
        char *cmdline;
        if (webserver_state != 1) {
            while ((cmdline = linenoise(prompt)) != NULL) {
                interpret_cmd(cmdline);
                linenoiseHistoryAdd(cmdline); /* Add to the history. */
                linenoiseHistorySave(
                    HISTORY_FILE); /* Save the history on disk. */
                linenoiseFree(cmdline);
                if (webserver_state == 1) {
                    longjmp(server_jmp_buf, 1);
                }
            }
        } else {            
            if ((cmdline = linenoise(prompt)) != NULL) {
                interpret_cmd(cmdline);
                linenoiseHistoryAdd(cmdline); /* Add to the history. */
                linenoiseHistorySave(
                    HISTORY_FILE); /* Save the history on disk. */
                linenoiseFree(cmdline);
                printf("cmd: %s\n", cmdline);
            }            
            longjmp(server_jmp_buf, 1);
        }
    } else {
        while (!cmd_done())
            cmd_select(0, NULL, NULL, NULL, NULL);
    }

    return err_cnt == 0;
}

嘗試失敗

cmd> web
server is starting..
cmd> web

*** longjmp causes uninitialized stack frame ***: terminated
Aborted

出現 longjmp causes uninitialized stack frame 警告， 查詢資料後發現 longjmp 與 setjmp 記憶的是 stack pointer 並非整個 stack ，所以 longjmp to returned function 會出現上述錯誤，因為stack pointer 指向的 stack 已經消失

在 longjmp 跳回 run_consle 後 start_web_srv 的 stack 被釋放

The stack pointer value stored at any point of the programs execution should not be used any further after the current stack pointer has pointed or still points to a lower stack element than the marked one. At such a point the procedure that contained the setjmp call has already returned. The stack pointer was or is set to a lower level and any intermediate subsequent procedure call might have overwritten the element the saved pointer value originally pointed to. Therefore undetermined behaviour or crashes are likely to occur. http://www.fmc-modeling.org/category/projects/apache/amp/A_5_Longjmp.html

另外查詢資料過程， 發現 gcc 文件有提示，沒有宣告volatile的 automatic variable 在longjmp的行為是未定義的， 可能會有 data corruption 的問題

If you use longjmp, beware of automatic variables. ISO C says that automatic variables that are not declared volatile have undefined values after a longjmp. And this is all GCC promises to do, because it is very difficult to restore register variables correctly, and one of GCC’s features is that it can put variables in registers without your asking it to. https://gcc.gnu.org/onlinedocs/gccint/Interface.html

todo:

• 採用 Coroutines in less than 20 lines of standard C 實作 coroutine 的方式避免 stack 釋放
• 參考其他利用 setjmp / longjmp 實作 scheduler/task/thread 的方式