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

作業要求

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_tail 及 q_insert_head 的 return 位置，不知道為何導致 git 無法 commit 成功。

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

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

解決方法

此處有兩個問題：

git commit 首字英文要大寫，且不能超過 50 個字元
因為 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 執行 )，當發生時，便會發生測量時間非常數的錯誤。

2022q1 Homework1 (labc0)

實驗環境

作業要求

Knowledge in This Homeworks

程式開發紀錄

q_new

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: 以升幕排列佇列

問題紀錄

cppcheck

遇到問題

解決方法

記憶體釋放錯誤

遇到問題：

解決方法

trace_17 無法總是通過

遇到問題：

解決方法（未解決）

Read more

2022q1 Homework1 (quiz 1)

Linux 鍵盤按鍵重新定義 (Keyboard Remapping)