Try   HackMD

2022q1 Homework1 (labc0)

contributed by < void110916 >

實驗環境

$ gcc --version
gcc (Ubuntu 9.3.0-17ubuntu1~20.04) 9.3.0

$ uname -a
Linux void-pc 5.13.0-28-generic #31~20.04.1-Ubuntu SMP Wed Jan 19 14:08:10 UTC 2022 x86_64 x86_64 x86_64 GNU/Linux

$ 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):                          12
On-line CPU(s) list:             0-11
Thread(s) per core:              2
Core(s) per socket:              6
Socket(s):                       1
NUMA node(s):                    1
Vendor ID:                       GenuineIntel
CPU family:                      6
Model:                           158
Model name:                      Intel(R) Core(TM) i7-8750H CPU @ 2.20GHz
Stepping:                        10
CPU MHz:                         2200.000
CPU max MHz:                     4100.0000
CPU min MHz:                     800.0000
BogoMIPS:                        4399.99
Virtualization:                  VT-x
L1d cache:                       192 KiB
L1i cache:                       192 KiB
L2 cache:                        1.5 MiB
L3 cache:                        9 MiB
NUMA node0 CPU(s):               0-11

作業要求

  • 在 GitHub 上 fork lab0-c
  • 依據上述指示著手修改 queue.[ch] 和連帶的檔案,測試後用 Git 管理各項修改,要能滿足 $ make test 自動評分系統的所有項目。
    queue.c實做
    • q_new: 建立空 (empty) 佇列
    • q_free: 釋放所有被佇列使用的空間
    • q_insert_head: 從佇列開頭插入新節點
    • q_insert_tail: 從佇列結尾插入新節點
    • q_remove_head: 從佇列開頭移除新節點
    • q_remove_tail: 從佇列結尾移除新節點
    • q_size: 回傳佇列個數
    • q_delete_mid: 刪除佇列中間的節點
    • q_delete_dup: 刪除佇列中重複字串的節點
    • q_swap: 交換鄰近的節點
    • q_reverse: 反向排列佇列
    • q_sort: 以升幕排列佇列
    • 詳閱「你所不知道的 C 語言: linked list 和非連續記憶體」並應用裡頭提及的手法,例如 pointer to pointer (指向某個指標的指標,或說 indirect pointer),讓程式碼更精簡且有效
    • 研讀 Linux 核心原始程式碼的 lib/list_sort.c 並嘗試引入到 lab0-c 專案,比較你自己實作的 merge sort 和 Linux 核心程式碼之間效能落差
  • qtest 提供新的命令 shuffle,允許藉由 Fisher–Yates shuffle 演算法,對佇列中所有節點進行洗牌 (shuffle) 操作
  • qtest 提供新的命令 web,提供 web 伺服器功能,注意: web 伺服器運作過程中,qtest 仍可接受其他命令
  • 除了修改程式,也要編輯「作業區」,增添開發紀錄和 GitHub 連結,除了提及你如何逐步達到自動評分程式的要求外,共筆也要涵蓋以下:
    • 開啟 Address Sanitizer,修正 qtest 執行過程中的錯誤
      • 先執行 qtest 再於命令提示列輸入 help 命令,會使 開啟 Address Sanitizer 觸發錯誤,應予以排除
    • 運用 Valgrind 排除 qtest 實作的記憶體錯誤,並透過 Massif 視覺化 "simulation" 過程中的記憶體使用量,需要設計對應的實驗
    • 解釋 select 系統呼叫在本程式的使用方式,並分析 console.c 的實作,說明其中運用 CS:APP RIO 套件 的原理和考量點。可對照參考 CS:APP 第 10 章重點提示
    • 研讀論文〈Dude, is my code constant time?〉,解釋本程式的 "simulation" 模式是如何透過以實驗而非理論分析,達到驗證時間複雜度,需要解釋 Student's t-distribution 及程式實作的原理。注意:現有實作存在若干致命缺陷,請討論並提出解決方案;
  • 指出現有程式的缺陷 (提示: 和 RIO 套件 有關) 或者可改進之處 (例如更全面地使用 Linux 核心風格的鏈結串列 API),嘗試實作並提交 pull request

Knowledge in This Homeworks

Linux 核心原始程式碼巨集: container_of: 如何取得該子結構的父結構

程式開發紀錄

q_new

問題程式

問題連結:記憶體釋放錯誤

struct list_head *q_new()
{
    struct list_head *q_head = malloc(sizeof(struct list_head));
    if (!q_head)
        return NULL;
    INIT_LIST_HEAD(q_head);
    return q_head;
}

修正後程式:

struct list_head *q_new()
{
    struct list_head *q_head = malloc(sizeof(struct list_head));
    INIT_LIST_HEAD(q_head);
    return q_head;
}

q_free

問題程式

問題連結:記憶體釋放錯誤

void q_free(struct list_head *l)
{
    struct list_head *node = l->next;
    while (!list_empty(l)) {
        list_del(node);
        element_t *e=container_of(node,element_t,list);
        free(e->value);
        free(node);
        node = l->next;
    }
    free(l);
}

修正後程式:

void q_free(struct list_head *l)
{
    if (!l)
        return;
    while (!list_empty(l)) {
        element_t *e = list_entry(l->next, element_t, list);
        list_del(&e->list);
        free(e->value);
        free(e);
    }
    free(l);
}

q_insert_head

問題程式

問題連結:記憶體釋放錯誤

bool q_insert_head(struct list_head *head, char *s)
{
    if (head == NULL)
        return false;
    element_t *e = malloc(sizeof(element_t));
    list_add(&(e->list), head);
    int len = strlen(s);
    e->value = malloc(sizeof(char) * ++len);
    strncpy(e->value, s, len);
    return true;
}

man strlen的敘述:

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

strlen 回傳的值不包含'\0',因此要先將長度值加一再動作。

修正後程式:

bool q_insert_head(struct list_head *head, char *s)
{
    if (!head)
        return false;
    element_t *e = malloc(sizeof(element_t));
    if (!e) 
        return false;
    e->value = strdup(s);
    if (!e->value) {
        free(e);
        return false;
    }
    list_add(&e->list, head);
    return true;
}

q_insert_tail

問題程式

問題連結:記憶體釋放錯誤

bool q_insert_tail(struct list_head *head, char *s)
{
    if (head == NULL)
        return false;
    element_t *e = malloc(sizeof(element_t));
    list_add_tail(&(e->list), head);
    int len = strlen(s);
    e->value = malloc(sizeof(char) * ++len);
    strncpy(e->value, s, len);
    return true;
}

修正後程式:

bool q_insert_tail(struct list_head *head, char *s)
{
    if (!head)
        return false;
    element_t *e = malloc(sizeof(element_t));
    if (!e)
        return false;
    e->value = strdup(s);
    if (!e->value) {
        free(e);
        return false;
    }
    list_add_tail(&e->list, head);

    return true;
}

q_insert_head

q_remove_head

element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
    element_t *e = NULL;
    if (!head) 
        return NULL;
    if (!list_empty(head)) {
        e = container_of(head->next, element_t, list);
        list_del(&e->list);
        if (sp) {
            strncpy(sp, e->value, bufsize - 1);
            sp[bufsize - 1] = '\0';
        }
    }
    return e;
}

q_remove_tail

trace-17 無法總是通過

element_t *q_remove_tail(struct list_head *head, char *sp, size_t bufsize)
{
    element_t *e = NULL;
    if (!head)
        return NULL;
    if (!list_empty(head)) {
        e = container_of(head->prev, element_t, list);
        list_del(&e->list);
        if (sp) {
            strncpy(sp, e->value, bufsize - 1);
            sp[bufsize - 1] = '\0';
        }
    }
    return e;
}

q_size: 回傳佇列個數

int q_size(struct list_head *head)
{
    if (!head)
        return 0;
    int num = 0;
    struct list_head *node = head;
    while (node->next != head) {
        node = node->next;
        num++;
    }
    return num;
}

q_delete_mid: 刪除佇列中間的節點

bool q_delete_mid(struct list_head *head)
{
    struct list_head *front, *tail;
    int i = 0;
    if (!head)
        return false;
    if (list_empty(head))
        return false;
    for (front = head->next, tail = head->prev;
         front != tail && front->next != tail;
         front = front->next, tail = tail->prev, i++) {
    }
    list_del(tail);
    q_release_element(list_entry(tail, element_t, list));
    return true;
}

q_delete_dup: 刪除佇列中重複字串的節點

bool q_delete_dup(struct list_head *head)
{
    if (!head)
        return false;
    element_t *e, *safe, *tmp = NULL;
    for (e = list_entry((head)->next, element_t, list),
        safe = list_entry(e->list.next, element_t, list);
         &safe->list != (head);
         e = safe, safe = list_entry(safe->list.next, element_t, list)) {
        if (!(strcmp(e->value, safe->value) & 0x7fffffff) ||
            !(strcmp(e->value, safe->value))) {
            list_del(&e->list);
            q_release_element(e);
            tmp = safe;
        } else if (tmp) {
            list_del(&tmp->list);
            q_release_element(tmp);
            tmp = NULL;
        }
    }
    if (tmp) {
        list_del(&tmp->list);
        q_release_element(tmp);
        tmp = NULL;
    }
    return true;
}

程式內使用到的遞迴幾乎等效於 list_for_each_entry_safe ,但是因為 list_for_each_entry_safe 的條件判斷是判斷 entry 而非 safe ,以至於最後會對 head 取 entry 並造成 segement fault。

q_swap: 交換鄰近的節點

void q_swap(struct list_head *head)
{
    struct list_head *next, *nnext;
    for (next = head->next, nnext = next->next;
         (next != head) && (nnext != head);
         next = next->next, nnext = next->next) {
        list_move(next, nnext);
    }
}

q_reverse: 反向排列佇列

void q_reverse(struct list_head *head)
{
    if (!head)
        return;
    struct list_head *iter = head;
    do {
        struct list_head *tmp = iter->next;
        iter->next = iter->prev;
        iter->prev = tmp;
        iter = iter->next;
    } while (iter != head);
}

q_sort: 以升幕排列佇列

void q_sort(struct list_head *head)
{
    if (!head)
        return;
    int count = 0;
    // insertion sort
    struct list_head *i, *j, *isafe, *jsafe;
    for (i = (head->next)->next, isafe = i->next; i != head;
         i = isafe, isafe = i->next) {
        for (j = head->next, jsafe = j->next; j != i;
             j = jsafe, jsafe = j->next) {
            char *s1, *s2;
            s1 = list_entry(i, element_t, list)->value;
            s2 = list_entry(j, element_t, list)->value;
            int cmp = strcmp(s1, s2);
            count++;
            if (cmp < 0) {
                list_move(i, j->prev);
                break;
            }
        }
    }
}

問題紀錄

cppcheck

遇到問題

$ git commit -m "edit function q_new, q_insert_head/tail, q_remove_head/tail"
Following files need to be cleaned up:
queue.c
queue.c:50:5: error: Memory leak: e [memleak]
    return true;
    ^
queue.c:69:5: error: Memory leak: e [memleak]
    return true;
    ^
queue.c:50:5: error: Memory leak: e.value [memleak]
    return true;
    ^
queue.c:69:5: error: Memory leak: e.value [memleak]
    return true;
    ^

Fail to pass static analysis.

該位置為 q_insert_tailq_insert_head 的 return 位置,不知道為何導致 git 無法 commit 成功。

這裡指的 memory leak 是記憶體洩漏那個 memory leak 嗎?

是的,你應該追蹤「完整」的程式碼,而非只注視單一函式。

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →
jserv

解決方法

此處有兩個問題:

  1. git commit 首字英文要大寫,且不能超過 50 個字元
  2. 因為 cppcheck 有檢查,所以 list 需要用 INIT_LIST_HEAD 做初使化: value 要用 strdup 配置動態記憶體,不能使用 calloc 或 malloc 。

記憶體釋放錯誤

遇到問題:

ERROR: Attempted to free unallocated block.  Address = 0x55b5876a7e50
ERROR: Attempted to free unallocated or corrupted block.  Address = 0x55b5876a7e50
ERROR: Corruption detected in block with address 0x55b5876a7e50 when attempting to free it
Segmentation fault occurred.  You dereferenced a NULL or invalid pointer
[1]    73359 abort (core dumped)  ./qtest

確定能從該位置取得字串,但不確定為何無法釋放。

解決方法

測試後得知,在 harness.h 中, malloc 、 free 、 strdup 被重新撰寫以追蹤記憶體配置,因此此作業在動態記憶體配置上只能用此三個函式,無法使用像 calloc 、 strndup 等函式。

trace_17 無法總是通過

遇到問題:

q_remove_head 及 q_remove_tail函式幾乎一樣,差別只在移除 head 前面的還是後面的 list ,但是在跑 trace-17 的測試時 q_remove_tail 有機率無法通過。

q_remove_head disassemble
0000000000000158 <q_remove_head>:
 158:	f3 0f 1e fa          	endbr64 
 15c:	41 54                	push   r12
 15e:	55                   	push   rbp
 15f:	53                   	push   rbx
 160:	48 85 ff             	test   rdi,rdi
 163:	74 45                	je     1aa <q_remove_head+0x52>
 165:	48 89 f5             	mov    rbp,rsi
 168:	49 89 d4             	mov    r12,rdx
 16b:	48 8b 47 08          	mov    rax,QWORD PTR [rdi+0x8]
 16f:	48 39 c7             	cmp    rdi,rax
 172:	74 3b                	je     1af <q_remove_head+0x57>
 174:	48 8d 58 f8          	lea    rbx,[rax-0x8]
 178:	48 8b 48 08          	mov    rcx,QWORD PTR [rax+0x8]
 17c:	48 8b 10             	mov    rdx,QWORD PTR [rax]
 17f:	48 89 11             	mov    QWORD PTR [rcx],rdx
 182:	48 89 4a 08          	mov    QWORD PTR [rdx+0x8],rcx
 186:	48 85 f6             	test   rsi,rsi
 189:	74 17                	je     1a2 <q_remove_head+0x4a>
 18b:	49 8d 54 24 ff       	lea    rdx,[r12-0x1]
 190:	48 8b 70 f8          	mov    rsi,QWORD PTR [rax-0x8]
 194:	48 89 ef             	mov    rdi,rbp
 197:	e8 00 00 00 00       	call   19c <q_remove_head+0x44>
 19c:	42 c6 44 25 ff 00    	mov    BYTE PTR [rbp+r12*1-0x1],0x0
 1a2:	48 89 d8             	mov    rax,rbx
 1a5:	5b                   	pop    rbx
 1a6:	5d                   	pop    rbp
 1a7:	41 5c                	pop    r12
 1a9:	c3                   	ret    
 1aa:	48 89 fb             	mov    rbx,rdi
 1ad:	eb f3                	jmp    1a2 <q_remove_head+0x4a>
 1af:	bb 00 00 00 00       	mov    ebx,0x0
 1b4:	eb ec                	jmp    1a2 <q_remove_head+0x4a>
q_remove_tail disassemble
00000000000001b6 <q_remove_tail>:
 1b6:	f3 0f 1e fa          	endbr64 
 1ba:	41 54                	push   r12
 1bc:	55                   	push   rbp
 1bd:	53                   	push   rbx
 1be:	48 85 ff             	test   rdi,rdi
 1c1:	74 45                	je     208 <q_remove_tail+0x52>
 1c3:	48 89 f5             	mov    rbp,rsi
 1c6:	49 89 d4             	mov    r12,rdx
 1c9:	48 3b 7f 08          	cmp    rdi,QWORD PTR [rdi+0x8]
 1cd:	74 3e                	je     20d <q_remove_tail+0x57>
 1cf:	48 8b 07             	mov    rax,QWORD PTR [rdi]
 1d2:	48 8d 58 f8          	lea    rbx,[rax-0x8]
 1d6:	48 8b 48 08          	mov    rcx,QWORD PTR [rax+0x8]
 1da:	48 8b 10             	mov    rdx,QWORD PTR [rax]
 1dd:	48 89 11             	mov    QWORD PTR [rcx],rdx
 1e0:	48 89 4a 08          	mov    QWORD PTR [rdx+0x8],rcx
 1e4:	48 85 f6             	test   rsi,rsi
 1e7:	74 17                	je     200 <q_remove_tail+0x4a>
 1e9:	49 8d 54 24 ff       	lea    rdx,[r12-0x1]
 1ee:	48 8b 70 f8          	mov    rsi,QWORD PTR [rax-0x8]
 1f2:	48 89 ef             	mov    rdi,rbp
 1f5:	e8 00 00 00 00       	call   1fa <q_remove_tail+0x44>
 1fa:	42 c6 44 25 ff 00    	mov    BYTE PTR [rbp+r12*1-0x1],0x0
 200:	48 89 d8             	mov    rax,rbx
 203:	5b                   	pop    rbx
 204:	5d                   	pop    rbp
 205:	41 5c                	pop    r12
 207:	c3                   	ret    
 208:	48 89 fb             	mov    rbx,rdi
 20b:	eb f3                	jmp    200 <q_remove_tail+0x4a>
 20d:	bb 00 00 00 00       	mov    ebx,0x0
 212:	eb ec                	jmp    200 <q_remove_tail+0x4a>

並且,不管字串複製是使用 memcpy 還是 strncpy ,在轉譯後的組語是完全一樣的。

解決方法(未解決)

目前觀測到在測量 q_remove_tail 時會發生執行核心交換的情況( ex. 原本在 cpu0 執行,但是跑到一半變成 cpu12 執行 ),當發生時,便會發生測量時間非常數的錯誤。