Try   HackMD

2022q1 Homework1 (lab0)

contributed by < HScallop >

作業說明與要求

K01: lab0

實驗環境

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

$ 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:                         800.218
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

開發過程

q_new

  • Create empty queue.
  • Return NULL if could not allocate space.
struct list_head *q_new()
{
    struct list_head *q = malloc(sizeof(struct list_head));
    if (q) {
        INIT_LIST_HEAD(q);
    }
    return q;
}

一開始用 LIST_HEAD 宣告一個 list_head 後，用pointer指向他，但發現會有 scope 的問題，所以後來改成使用 malloc 配置記憶體。

q_free

  • Free all storage used by queue.
void q_free(struct list_head *l)
{
    if (!l) {
        return;
    }
    element_t *entry = NULL, *next = NULL;
    list_for_each_entry_safe (entry, next, l, list) {
        free(entry->value);
        free(entry);
    }
    free(l);
}

用 list_for_each_entry_safe 一個一個找到記憶體位址後，釋放記憶體。

q_insert_head

  • Attempt to insert element at head of queue.
  • Return true if successful.
  • Return false if q is NULL or could not allocate space.
  • Argument s points to the string to be stored.
  • The function must explicitly allocate space and copy the string into it.
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;
}

照著註解的要求寫。查如何複製字串時，找到 strdup 。因為實作有使用 malloc ，使用上要手動 free ，避免 memory leak 。

q_insert_tail

  • Attempt to insert element at tail of queue.
  • Return true if successful.
  • Return false if q is NULL or could not allocate space.
  • Argument s points to the string to be stored.
  • The function must explicitly allocate space and copy the string into it.
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 極其類似，只需要把後面改成 list_add_tail 。

q_remove_head

  • Attempt to remove element from head of queue.
  • Return target element.
  • Return NULL if queue is NULL or empty.
  • If sp is non-NULL and an element is removed, copy the removed string to *sp
element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
    if (!head || list_empty(head)) {
        return NULL;
    }
    element_t *e = list_first_entry(head, element_t, list);
    if (sp) {
        strncpy(sp, e->value, bufsize - 1);
        sp[bufsize - 1] = '\0';
    }
    list_del(&e->list);
    return e;
}

判斷是否為空後，使用 list_first_entry 找到第一個 element 的位址，照著註解的要求複製給 *sp ，最後 list_del remove list node 。

q_remove_tail

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

基本上跟 q_remove_head 一樣，頭改尾。

q_size

  • Return number of elements in queue.
  • Return 0 if q is NULL or empty.
int q_size(struct list_head *head)
{
    if (!head || list_empty(head)) {
        return 0;
    }
    struct list_head *node;
    int count = 0;
    list_for_each (node, head) {
        count++;
    }
    return count;
}

用 list_for_each 一個一個去數，看有幾個。

q_delete_mid

  • Delete the middle node in list.
  • The middle node of a linked list of size n is the
  • ⌊n / 2⌋th node from the start using 0-based indexing.
  • If there're six element, the third member should be return.
  • Return true if successful.
  • Return false if list is NULL or empty.
bool q_delete_mid(struct list_head *head)
{
    if (!head || list_empty(head)) {
        return false;
    }
    struct list_head *fast, *slow;
    fast = slow = head->next;
    while (fast != head && fast->next != head) {
        fast = fast->next->next;
        slow = slow->next;
    }
    list_del(slow);
    q_release_element(list_entry(slow, element_t, list));
    return true;
}

參考 leetcode discussion 作法，使用兩個 pointer 用兩倍速差去跑，快的跑到底時，慢的就是中間。

q_delete_dup

  • Delete all nodes that have duplicate string, leaving only distinct strings from the original list.
  • Return true if successful.
  • Return false if list is NULL.
{
    if (!head) {
        return false;
    }
    if (list_empty(head) || list_is_singular(head)) {
        return true;
    }
    element_t *node, *safe;
    bool dup = false;
    list_for_each_entry_safe (node, safe, head, list) {
        if ((node->list.next != head) &&
            (strcmp(node->value,
                    list_entry(node->list.next, element_t, list)->value) ==
             0)) {
            list_del(&node->list);
            q_release_element(node);
            dup = true;
        } else if (dup) {
            list_del(&node->list);
            q_release_element(node);
            dup = false;
        }
    }
    return true;
}

一直做不出來，後來參考 laneser 的作法。
改進方向：應該可以先找出所有重複的相同 element 一起拿掉。

q_swap

  • Attempt to swap every two adjacent nodes.
void q_swap(struct list_head *head)
{
    if (!head || list_empty(head) || list_is_singular(head)) {
        return;
    }
    struct list_head *node;
    for (node = head->next; node != head && node->next != head;
         node = node->next) {
        struct list_head *tmp = node->next;
        list_del(tmp);
        list_add_tail(tmp, node);
    }
}

先排除空、只有一個的情況，接著兩個兩個交換。

q_reverse

  • Reverse elements in queue.
  • No effect if q is NULL or empty.
  • This function should not allocate or free any list elements.
void q_reverse(struct list_head *head)
{
    if (!head || list_empty(head) || list_is_singular(head)) {
        return;
    }
    struct list_head *node, *safe;
    list_for_each_safe (node, safe, head) {
        list_move(node, head);
    }
}

先排除不用移動的情況後，一個一個慢慢移動。

q_sort

  • Sort elements of queue in ascending order
  • No effect if q is NULL or empty. In addition, if q has only one
  • element, do nothing

mergeTwoLists

struct list_head *mergeTwoLists(struct list_head *l1, struct list_head *l2)
{
    struct list_head *head = NULL, **ptr = &head, **node;

    for (node = NULL; l1 && l2; *node = (*node)->next) {
        node = (strcmp(list_entry(l1, element_t, list)->value,
                       list_entry(l2, element_t, list)->value) < 0)
                   ? &l1
                   : &l2;
        *ptr = *node;
        ptr = &(*ptr)->next;
    }

    *ptr = (struct list_head *) ((u_int64_t) l1 | (u_int64_t) l2);

    return head;
}

使用 indirect pointer.

mergesort

struct list_head *mergesort(struct list_head *head)
{
    if (!head->next) {
        return head;
    }
    struct list_head *fast = head, *slow = head, *mid;
    while (true) {
        if (!fast || !fast->next) {
            break;
        }
        fast = fast->next->next;
        slow = slow->next;
    }

    mid = slow;
    slow->prev->next = NULL;

    struct list_head *l1 = mergesort(head), *l2 = mergesort(mid);
    return mergeTwoLists(l1, l2);
}

q_sort

void q_sort(struct list_head *head)
{
    if (!head || list_empty(head) || list_is_singular(head)) {
        return;
    }
    struct list_head *node = head->next, *tmp;
    head->prev->next = NULL;
    head->next = NULL;

    node = mergesort(node);

    tmp = head;
    tmp->next = node;
    while (tmp->next) {
        tmp->next->prev = tmp;
        tmp = tmp->next;
    }
    tmp->next = head;
    head->prev = tmp;
}

參考 你所不知道的 C 語言: linked list 和非連續記憶體 實作 (recursion method)。
可以實作 iteration 部份

valgrind

用 MakeFile 裡面寫好的指令來測試

$ make valgrind

結果：

---	trace-17-complexity	0/5
---	TOTAL		95/100
make: *** [Makefile:68: valgrind] Error 1

回頭找 trace-17

+++ TESTING trace trace-17-complexity:
# Test if time complexity of q_insert_tail, q_insert_head, q_remove_tail, and q_remove_head is constant
Probably constant time
ERROR: Probably not constant time
Probably constant time
ERROR: Probably not constant time

q_insert_head, q_remove_head 被 valgrind 認為可能不是 O(1)

目前還沒想出原因

valgrind 沒有發現 memory leak
所有輸出皆為：

160 bytes in 1 blocks are still reachable in loss record 30 of 30

記憶體分析

valgrind tool Massif: a heap profiler

Massif is a heap profiler. It measures how much heap memory your program uses. This includes both the useful space, and the extra bytes allocated for book-keeping and alignment purposes. It can also measure the size of your program's stack(s), although it does not do so by default.

The topic of valgrind user manual says it's a heap profiler, but the manual itself shows it can also measure the size of stack actually.

A memory test trace is added. To observe heap, use the ih command. And use sort command to observe stack (currently implemented w/ recurrsive merge sort).

trace-massif.cmd

new
ih RAND 1000
sort
free
quit

$ valgrind --tool=massif --stacks=yes ./qtest -f traces/trace-massif.cmd
$ massif-visualizer massif.out.<pid>

signal

signal description default action
SIGABRT Process abort signal.
SIGFPE
SIGILL
SIGINT
SIGSEGV
SIGTERM

Why merge sort?

在 linux kernel 中， list_sort.c 為何使用 merge sort 實作，而不使用 quick sort ？

跟在教科書上用 array 的討論不同，在 list 不是連續記憶體，如果使用 merge sort 我們可以良好的運用 locality of reference 的特性。

實驗

閱讀 linux/lib/list_sort.c

Dude, is my code constant time?

運作方式

以下敘述論文中提供的實作步驟
step1 measure execution time
用 t-test 來偵測是否在運行時是 constant time 的行為，造成可能的 leakage 。

TODO LIST

  • valgrind 測試
  • valgrind 視覺化 (massif)
  • 開發歷程說明
  • tiny-web
  • 分析 console.c 研究 CS:APP RIO 套件
  • 研究 Dude, is my code constant time?
  • 解決 vscode git push 卡住問題
Last changed by 
 
HScallop
1
542

Read more

2022-04-04 [HScallop](https://github.com/HScallop/linux2022-quiz8)

quiz8 &#x6E2C;&#x9A57; 1 #include &lt;stddef.h&gt; #include &lt;stdint.h&gt; #include &lt;limits.h&gt; #include &lt;string.h&gt; /* Nonzero if either X or Y is not aligned on a &quot;long&quot; boundary */ #define UNALIGNED(X) ((long) X &amp; (sizeof(long) - 1))

Jun 30, 2022
2022q1 Homework2 (quiz2)

contributed by &lt;HScallop&gt; 2022q1 quiz2 &#x6E2C;&#x9A57; 1 #include &lt;stdint.h&gt; uint32_t average(uint32_t a, uint32_t b) { return (a &gt;&gt; 1) + (b &gt;&gt; 1) + (EXP1); }

Apr 26, 2022
Read more from HScallop
Published on HackMD