Try   HackMD

2023q1 Homework1 (lab0)

contributed by < SPFishcool >

開發環境

$ neofetch --stdout
OS: Ubuntu 22.04.1 LTS x86_64 
Host: GL552VW 1.0 
Kernel: 5.15.0-60-generic 
Uptime: 13 hours, 20 mins 
Packages: 1877 (dpkg), 9 (snap) 
Shell: bash 5.1.16 
Resolution: 1920x1080 
DE: GNOME 42.5 
WM: Mutter 
WM Theme: Adwaita 
Theme: Yaru [GTK2/3] 
Icons: Yaru [GTK2/3] 
Terminal: gnome-terminal 
CPU: Intel i5-6300HQ (4) @ 3.200GHz 
GPU: Intel HD Graphics 530 
GPU: NVIDIA GeForce GTX 960M 
Memory: 3626MiB / 11868MiB

$ gcc -v
Thread model: posix
Supported LTO compression algorithms: zlib zstd
gcc version 11.3.0 (Ubuntu 11.3.0-1ubuntu1~22.04)

lab0 資料架構認識

list_head

  • list_head 負責作為鏈結串列將其 entry 串連在一起，其為 Circular Doubly-linked list 類型

注意書寫: doubly-linked list，連字號的位置在 doubly 和 linked 之間。
:notes: jserv







list


cluster_0

list_head



head

prev

next
  • list_head架構圖

使用 Graphviz 製圖並嵌入到 HackMD 頁面。
:notes: jserv
收到！正在改進中！

  • list_head的struct為：
struct list_head {
    struct list_head *prev;
    struct list_head *next;
};

element_t

  • element_t 為佇列儲存 value，內部有 list_head 架構的 list 能夠將所有 element_t 串接起來






list


cluster_0

element_t



value

*value



list
list



head

prev

next
  • element_t 架構圖
  • element_t 的 struct 為：
typedef struct {
    char *value;
    struct list_head list;
} element_t;
  • 因此 lab0 實做的佇列結構會是

queue_chain_t

  • 在執行 qtest.c 時，會先 create 一個 queue_chain_t 結構的物件，其功用類似上述佇列結構的 head，目的是每當 q_new 一個新的佇列時會將新的佇列利用 list_add_tail 加入到 queue_chain_t 鏈結串列的最後面。


queue_chain_t 架構圖，size 為佇列的數量

typedef struct {
    struct list_head head;
    int size;
} queue_chain_t;

queue_contex_t

  • queue_contex_t 在紀錄每一條佇列的資訊，*q 為 pointer of queue head，size 是佇列裡面 element_t 的數量，chain 為與其他 queue_contex_t 串連的 list_head。


queue_contex_t架構圖

typedef struct {
    struct list_head *q;
    struct list_head chain;
    int size;
    int id;
} queue_contex_t;
  • 再加入 queue_chain_t 其完整佇列架構就完成了！


queue 為上圖的紅色虛線部份

lab0 開發過程

q_new

q_new() 會先配置 list_head 大小的記憶體位置，接下來判斷是否配置成功，最後 INIT_LIST_HEAD(new) 會將這個 node 接回自己（成為 Doubly-linked list 型態）。

struct list_head *q_new()
{
    struct list_head *new = malloc(sizeof(struct list_head));
    // check if space allowed
    if (!new)
        return NULL;
    
    INIT_LIST_HEAD(new);
    return new;
}

q_free

q_free() 從 head->next (第一個有entry的節點)開始釋放，直到回到 head 最後釋放 head 節點。

void q_free(struct list_head *l)
{
    if (!l)
        return;
    struct list_head *indirect = l->next;
    struct list_head *tmp = NULL;
    while (indirect != l) {
        tmp = indirect;
        indirect = indirect->next;
        q_release_element(list_entry(tmp, element_t, list));
    }
    free(l);
}

q_insert_head / q_insert_tail

兩者可以使用 list.h 中的 list_add 與 list_add_tail 將 element_t 內的list加入鏈結串列中。

bool q_insert_head(struct list_head *head, char *s)
{
    if (!(head && s))
        return false;

    element_t *new_ele = malloc(sizeof(element_t));

    if (!new_ele)
        return false;

    new_ele->value = (char *) malloc(strlen(s) * sizeof(char) + 1);

    if (!new_ele->value) {
        free(new_ele);
        return false;
    }

    strncpy(new_ele->value, s, strlen(s) + 1);

    // struct list_head *new_node = (new_ele -> list);

    list_add(&new_ele->list, head);
    return true;
}

q_remove_head/q_remove_tail

remove 只有將 element_t 的串列節點從佇列中移除並沒有釋放其空間，因此只需要將其 next 與 prev 連接起來即可移除。

element_t *q_remove_head(struct list_head *head, char *sp, size_t bufsize)
{
    if (!head || list_empty(head))
        return NULL;

    struct list_head *indirect = head->next; //or head->prev (q_remove_tail)
    list_del(indirect);

    element_t *ele = list_entry(indirect, element_t, list);
    if (sp)
    {
        strncpy(sp, ele->value, bufsize-1);
        *(sp+bufsize-1) = '\0';
    }
        
    return ele;
}

q_size

q_size 則從 head->next 開始計算這條佇列的 element_t 數量，並且回傳 i (count 後的結果)

int q_size(struct list_head *head)
{
    if (!head)
        return -1;

    struct list_head *indirect = head->next;
    int i = 0;
    while (indirect != head) {
        i++;
        indirect = indirect->next;
    }
    return i;
}

q_delete_mid

因為佇列是 doubly-linked list 結構，因此可以使用左右指標（最左和最右可以快速找到），其原理是每一迴圈 left_node 往右走一步，right_node 往左走一步，直到兩指標相遇（奇數 element）或相鄰（偶數 element）時 right_node 就是我們要找的節點。

優點：跟快慢指標相比，迴圈節省了一半的次數（僅限 Circular Doubly-linked list）。

bool q_delete_mid(struct list_head *head)
{
    while(!head || list_empty(head))
        return false;

    struct list_head *left_node = head->next;
    struct list_head *right_node = head->prev;
    while ((left_node->next != right_node) && (left_node != right_node)) {
        left_node = left_node->next;
        right_node = right_node->prev;
    }
    list_del(right_node);
    q_release_element(list_entry(right_node, element_t, list));
    return true;
}

q_delete_dup

q_delete_dup 這個 question 我紀錄此次和前次的比較紀錄，而受到「判決」的節點為
indirect->prev(目前指到的節點的前一個節點)

  • cmp：indirect 與 indirect->prev 的比較結果
  • prev_cmp：indirect->prev 與 indirect->prev->prev 的比較結果

    不管是 cmp 還是 prev_cmp 只要為 0 都代表著中間這個節點的 value 與前後節點重複，必刪除！
bool q_delete_dup(struct list_head *head)
{
    if (!head || list_empty(head))
        return false;

    struct list_head *indirect = (head->next)->next;
    element_t *prev_ele = NULL;
    element_t *current_ele = NULL;
    int cmp = -1, prev_cmp = -1;
    while (indirect != head) {
        prev_ele = list_entry(indirect->prev, element_t, list);
        current_ele = list_entry(indirect, element_t, list);
        cmp = strcmp(prev_ele->value, current_ele->value);
        if (cmp == 0 || prev_cmp == 0) {
            list_del(indirect->prev);
            q_release_element(prev_ele);
        }
        prev_cmp = cmp;
        indirect = indirect->next;
    }
    if (cmp == 0) {
        list_del(indirect->prev);
        q_release_element(current_ele);
    }
    return true;
}

q_swap

q_swap 只要將佇列內的 element 兩兩交換即可，因此只需要使用 list.h 中的 list_move 把自己搬到 next 後面即可

void q_swap(struct list_head *head)
{
    if (!head || list_empty(head))
        return;

    struct list_head *indirect = head->next;
    while (indirect != head && indirect->next != head) {
        list_move(indirect, indirect->next);
        indirect = indirect->next;
    }
}

q_reverse

這裡則是使用 pointer to pointer 紀錄第一個 element 節點內的 next 位址（&head->next->next），在每次迴圈中將 next 指到的節點利用 list_move 移到 head 前面直到 next 指向的位置為 head 為止。

void q_reverse(struct list_head *head)
{
    if (!head || list_empty(head))
        return;
    struct list_head **indirect = &((head->next)->next);
    while (*indirect != head)
        list_move(*indirect, head);
}

q_reverseK

q_reverseK 其原理與 q_reverse 相似，但因為如果後面個數不足 k 個則不做 reverse，因此我的作法是先讓一個指標邊走邊數，數到第 k 個後，再將後面的節點一一搬到前面來，因此如果走完一圈沒有數到 k 個，剩下的節點就不會動到。

void q_reverseK(struct list_head *head, int k)
{
    if (!head || list_empty(head))
        return;

    struct list_head **indirect = &(head->next);
    struct list_head *current = head->next;
    struct list_head *tmp = NULL;

    int i = 1;
    while (current != head) {
        if (i % k == 0) {
            tmp = current;
            while (*indirect != tmp) {
                list_move(tmp->prev, current);
                current = current->next;
            }
            indirect = &((current)->next);
        }
        current = current->next;
        i++;
    }
}

q_sort

參考你所不知道的 C 語言: linked list 和非連續記憶體merge_sort寫法。
原先想法是要維持 doubly-linked list 的結構去設計，但當我要 malloc 新的 head 來接分割後的子串列時遇到ERROR:Calls to malloc disallowed，因此決定將 circular 斷開將最後一個 node 的prev指向NULL才進行mergesort並且在排序後將排序過後的串列重新接上 head。

void q_sort(struct list_head *head)
{
    if (!head || list_empty(head))
        return;

    struct list_head *start = head->next;
    struct list_head *tail = head->prev;
    tail->next = NULL;

    struct list_head *sorted_list = merge_sort(start);

    head->next = sorted_list;
    struct list_head *cur = head;
    while (cur->next) {
        cur->next->prev = cur;
        cur = cur->next;
    }
    cur->next = head;
    head->prev = cur;
}

struct list_head *mergeList(struct list_head *l1, struct list_head *l2)
{
    struct list_head *head = NULL;
    struct list_head **current = &head;
    while (l1 && l2) {
        if (strcmp(list_entry(l1, element_t, list)->value,
                   list_entry(l2, element_t, list)->value) >= 0) {
            *current = l2;
            l2 = l2->next;
        } else {
            *current = l1;
            l1 = l1->next;
        }
        current = &((*current)->next);
    }
    *current = (struct list_head *) ((__intptr_t) l1 | (__intptr_t) l2);
    return head;
}

struct list_head *merge_sort(struct list_head *head)
{
    if (!head || head->next == NULL)
        return head;

    struct list_head *slow = head;


    for (struct list_head *fast = head->next; fast && fast->next;
         fast = fast->next->next) {
        slow = slow->next;
    }

    struct list_head *list2 = slow->next;

    slow->next = NULL;
    return mergeList(merge_sort(head), merge_sort(list2));
}

q_descend

q_descend 若是 prev 方向有比自己小的節點則這些小的節點都要 delete 掉，直到遇到下一個比自己大的節點，則移動到下一個節點(prev)

int q_descend(struct list_head *head)
{
    if (!head || list_empty(head))
        return 0;
    struct list_head *current = head->prev;
    struct list_head *cur_prev = current->prev;
    while (cur_prev != head) {
        if (strcmp(list_entry(current, element_t, list)->value,
                   list_entry(cur_prev, element_t, list)->value) > 0) {
            list_del(cur_prev);
            q_release_element(list_entry(cur_prev, element_t, list));
        } else {
            current = current->prev;
        }
        cur_prev = current->prev;
    }
    int len = q_size(head);
    return len;
}

q_merge

在 qtest.c 裡執行q_merge其程式碼為

    len = q_merge(&chain.head);

這個 chain 其實就是 queue_chain_t 結構，所以得知輸入的資料為 queue_chain_t 內的 head 元素因此我們可以很簡單的拜訪所有佇列再使用list.h中的 list_splice_init 從第二個佇列到最後一個一一串在 id=0 目前第一個 queue_contex_t->q 的串列內。

int q_merge(struct list_head *head)
{
    if(!head || list_empty(head))
        return 0;
    else if(list_is_singular(head))
        return list_entry(head->next, queue_contex_t, chain)->size;
    queue_contex_t *target = list_entry(head->next, queue_contex_t, chain);
    queue_contex_t *que = NULL;
    list_for_each_entry (que, head, chain) {
        if (que == target)
            continue;
        list_splice_init(que->q, target->q);
        target->size = target->size + que->size;
        que->size = 0;
    }
    q_sort(target->q);
    return target->size;
}

目前 queue.c 靜態與動態評分

make test

  • score: 95/100
  • problem: q_insert 系列程式時間複雜度非 constant time

make valgrind

  • score: 94/100
  • problem: Test of malloc failure on new 測試未通過
  • reason：在 qtest 執行結束未妥善釋放其程式所配置的記憶體所導致
  • solved: 在研讀Valgrind + 自動測試程式後發現大部分的test其實都在記憶體配置上出現問題，例如：
==104151== 128,000 bytes in 2,000 blocks are still reachable in loss record 4 of 6
==104151==    at 0x4848899: malloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==104151==    by 0x10F110: test_malloc (harness.c:133)
==104151==    by 0x10F645: q_insert_tail (queue.c:72)
==104151==    by 0x10C62B: do_it (qtest.c:312)
==104151==    by 0x10DDFA: interpret_cmda (console.c:181)
==104151==    by 0x10E3AF: interpret_cmd (console.c:201)
==104151==    by 0x10E7B0: cmd_select (console.c:610)
==104151==    by 0x10F09C: run_console (console.c:705)
==104151==    by 0x10D1EC: main (qtest.c:1223)

而上述 problem 的錯誤為：

==104070== 160 bytes in 5 blocks are possibly lost in loss record 3 of 3
==104070==    at 0x4848899: malloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==104070==    by 0x10CBCE: do_new (qtest.c:145)
==104070==    by 0x10DDFA: interpret_cmda (console.c:181)
==104070==    by 0x10E3AF: interpret_cmd (console.c:201)
==104070==    by 0x10E7B0: cmd_select (console.c:610)
==104070==    by 0x10F09C: run_console (console.c:705)
==104070==    by 0x10D1EC: main (qtest.c:1223)

在這情況下我決定先嘗試解決比較輕的問題，解決過程如下：

  • 檢查 queue.c 是否有哪一個功能沒有完全 free 空間
  • 檢查 script 資料夾內的 cmd 檔案，發現沒有此問題的腳本都有執行 free。
  • 開始檢查 qtest.c 的退出程式發現：
static bool q_quit(int argc, char *argv[])
{
    return true;
    report(3, "Freeing queue");
    if (current && current->size > BIG_LIST_SIZE)
        set_cautious_mode(false);

    if (exception_setup(true)) {
        struct list_head *cur = chain.head.next;
        while (chain.size > 0) {
            queue_contex_t *qctx, *tmp;
            tmp = qctx = list_entry(cur, queue_contex_t, chain);
            cur = cur->next;
            q_free(qctx->q);
            free(tmp);
            chain.size--;
        }
    }

發現 do_quit 第一行程式碼即 return true 表示下方程式完全沒有走過，註解掉後重新 make valgrind 所有問題都解決了。

研讀 Linux 核心原始程式碼的 lib/list_sort.c

在 linux 核心原始程式碼內的 lib/list_sort.c 所作的 sort 為 Merge Sort ，但這裡面的 Merge Sort 跟我們以前認識的 Merge Sort 不同。
在 list_sort 內有 3 個 Function

  • merge
  • merge_final
  • list_sort

而走訪 linked list 時會使用 count 會計算目前走訪到的節點數量，一旦走訪數量走到

2k 數量時不執行 merge，反之就會執行 merge。其流程如下

  1. 一開始 list 從 head->next 開始，而 pending 起始為 NULL，count 起始為 0，linked list 最後指向 NULL。
  2. 迴圈開始，宣告 **tail指向 pending 的位址。
  3. 會先計算 count 是否為
    2k−1     ，如果是，跳到 "7."。
  4. 準備 merge ，將 a = *tail、b = a->prev，執行 merge(priv, cmp, b, a);
  5. merge 會有一個 **tail 紀錄前一次比較最小的節點的 next 位址，每一次比較會把 *tail 指向較小的節點，其實就是一般的merge，這裡就把 next 拿來做 merge 的主要 link。
  6. merge return 為 merge 後的第一個節點（最小）存入 a ，將目前的 a->prev 重指成 b->prev，藉由 *tail 把 pending 指向 a（merge 起始節點）。
  7. 將 list->prev 指向 pending，list 往前一步， panding = list->prev， 把 pending->next 指向 NULL。
  8. 若 list 還沒走完，回到 "2."
  9. merge 剩下還沒 merge 起來的 pending list。
  10. 最後 merge_final 把 merge 完的 list 將其 prev 連接起來。

看完 lib/list_sort.c 發現他並沒有特別做 divide 而是走訪過程一一將 next 斷開並且把 next 當成執行 merge 動作時走訪的 link，比較「你所不知道的 C 語言: linked list 和非連續記憶體」所提及的遞迴與非遞迴，此做法省去 divide 這一部份，也沒有使用 stack 有 Max Depth 的限制。

引入 lib/list_sort.c 到 lab0-c 專案

ADD_COMMAND(list_sort, "Sort queue in ascending order by list_sort", "");
  • 製作分析準備

利用 perf 分析 list_sort 與自己做的 q_sort 效能比較

參考 linhoward0522 開發紀錄 (lab0) 使用 perf 分析其效能，在 traces/trace-15-perf.cmd 有三筆資料來測試排序，因此我們可以依照這個檔案自製用來測試的 cmd 檔。

.
├── RAND-1000000-list.cmd
├── RAND-1000000-q.cmd
├── RAND-100000-list.cmd
├── RAND-100000-q.cmd
├── RAND-10000-list.cmd
├── RAND-10000-q.cmd
├── RAND-1000-list.cmd
└── RAND-1000-q.cmd

q : q_sort
list : list_sort

接下來是試做 shell scripts

#!/bin/bash
# q_sort
for i in ./traces/perf_traces/RAND-*-q.cmd
do
    perf stat --repeat 5 -o "${i%.cmd}"-report -e cache-misses,branches,instructions,context-switches ./qtest -v 0 -f "$i"
done

#list_sort
for i in ./traces/perf_traces/RAND-*-list.cmd
do
    perf stat --repeat 5 -o "${i%.cmd}"-report -e cache-misses,branches,instructions,context-switches ./qtest -v 0 -f "$i"
done

  • q_sort

    #node cache-misses branches instructions context-switch
    1000 3469 77,9884 516,0401 0
    10000 3,3403 621,9374 4305,8950 0
    100000 543,0532 6326,2119 4,3295,3471 0
    1000000 7491,5547 4,6974,1917 31,6153,3055 10

  • list_sort

    #node cache-misses branches instructions context-switch
    1000 2489 77,7798 519,9240 0
    10000 4,1257 614,2028 4329,3845 0
    100000 439,1922 6258,0696 4,3642,0292 3
    1000000 5824,6891 4,6028,3507 31,6579,3448 9

可以看到節點數增多，效能差異越大，雖然 RAND 會導致偶爾會讓 list_sort 效能看起來跟 q_sort 差不多甚至更差，但時間上還是 list_sort 略勝一籌。

在 qtest.c 新增 shuffle 命令

作業要求為使用「Fisher–Yates shuffle」完成 shuffle，其原理就是從最後一個節點開始，隨機選取前面的節點與其交換，交換完後再往前一格完成前面敘述的事情直到第二張牌為止。

    for (int i = len-1;i > 0;i--)
    {
        //random 1~i
        int count = rand() % i;
        struct list_head *node = head->next;
        
        for (int j=1; j < count;j++)
            node = node->next;
        swap(tail, node);
        tail = node->prev;
    }

跟設定 list_sort 一樣，新增 do_shuffle 與 ADD_COMMAND

ADD_COMMAND(shuffle, "shuffle queue.", "");

接下來統計剛設計出來的 shuffle 亂度
參考 L01: lab0 亂數+論文閱讀 中的測試程式並載入 Makefile 執行指令

shuffle_check: qtest scripts/shuffle_test.py
	scripts/shuffle_test.py

執行結果：


依照 4 個數字的亂數來看，分佈差距大約在
±1.2% ，學生突然想到如果數字在多一點的話分佈會不會變化比較大，因此我將數字加到 6 個，而 6 個數字的排列組合比 4 個數字多出 30 倍，因此也將次數增加到 30000000 次。

執行結果：

在這張圖最少次為 41081，最多次為 42281，幅度有稍微增加，但沒有特別明顯。

使用 entropy 觀察亂數

在認識 entropy 之前，對 entropy 的唯一認知就是機器學習中計算 loss 值的方式 cross entropy，發現其中的含意與 entropy 也有一些關係，但知道了「entropy 與亂數產生的資訊量成反比」還是覺得對 entropy 有點抽象，因此我打算從 qtest.c 裡的指令 option entropy 1 與 ih RAND 10 找出關於 entropy 的蛛絲馬跡，最後發現 shannon_entropy.c 裡的 shannon_entropy 實作了以下 entropy 公式。

−∑i=1np(xi)log2⁡p(xi)

    for (uint32_t i = 0; i < BUCKET_SIZE; i++) {
        if (bucket[i]) {
            uint64_t p = bucket[i];
            p *= LOG2_ARG_SHIFT / count;
            entropy_sum += -p * log2_lshift16(p);
        }
    }

    entropy_sum /= LOG2_ARG_SHIFT;
    return entropy_sum * 100.0 / entropy_max;

這裡除了使用 bucket 計算每一個字元的熵值，而且使用 LOG_ARG_SHIFT 預計算的常數來避免使用浮點數增加計算時間。

Last changed by 
 
SPFishcool
0
806

Read more

4/16 一對一問題回復

linux 核心的 list_sort 實作考量 在 linux 核心的 list_sort 使用 buttom-up merge sort 實作排序，buttom-up 與 top-down 的差異在於 buttom-up 少了 partition 這一步驟。 此作法可以省去 recursive 和 stack 的使用（會佔用大量記憶體的寫法，並且會較常去 catch 記憶體更新 cache 內容） 其效能比較根據如下（q_sort 為 lab0-c 實作之排序）： q_sort#nodecache-missesbranchesinstructionscontext-switch1000346977,9884516,04010100003,3403621,93744305,89500100000543,05326326,21194,3295,3471010000007491,55474,6974,191731,6153,305510 list_sort#nodecache-missesbranchesinstructionscontext-switch1000248977,7798519,92400100004,1257614,20284329,38450100000439,19226258,06964,3642,0292310000005824,68914,6028,350731,6579,34489

May 8, 2023
2023q1 Homework6 (quiz6)

contributed by < SPFishcool > 開發環境 $ neofetch --stdout fico@fico-mac ------------- OS: Arch Linux ARM aarch64 Host: Apple MacBook Air (13-inch, M2, 2022) Kernel: 6.2.0-asahi-11-1-edge-ARCH Uptime: 16 hours, 7 mins

Apr 27, 2023
2023q1 Homework3 (fibdrv)

contributed by < SPFishcool > 開發環境 $ neofetch --stdout fico@fico-mac ------------- OS: Arch Linux ARM aarch64 Host: Apple MacBook Air (13-inch, M2, 2022) Kernel: 6.1.0-asahi-2-2-ARCH Uptime: 12 mins

Mar 20, 2023
2023q1 Homework2 (quiz2)

contributed by < SPFishcool > 測驗一 運作原理 程式裡 next_pow2(x) 要找出最接近且大於等於 x 的 2 的冪次方的值。 在改寫程式裡，有著幾行類似下方的程式碼。 x |= x >> 1; 這會讓 x 右移一位並將 1 set 到原本的 x 上，例如： 00100000 變成 00110000、 00100110 變成 00110111。

Mar 13, 2023
Read more from SPFishcool
Published on HackMD