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 嗎？

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

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

解決方法

此處有兩個問題：

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)