2023q1 Homework1 (quiz1)

contributed by < linhoward0522 >

2023q1 第 1 週測驗題
參考 list.h 與 The Linux Kernel API

測驗 `1`

if (list_empty(head) || list_is_singular(head))
    return;

struct list_head list_less, list_greater;
INIT_LIST_HEAD(&list_less);
INIT_LIST_HEAD(&list_greater);

先確認 list 有無排序的必要後再往下執行，判斷 list 是否沒有節點或是只有一個節點
先宣告 list_less, list_greater ， INIT_LIST_HEAD 後， list_less, list_greater 分別用來當比 pivot 小以及比 pivot 大 list 的 head

struct item {                         
    uint16_t i;
    struct list_head list;
};

struct item *pivot = list_first_entry(head, AAA, BBB);
list_del(&pivot->list);

根據結構體的定義，以及 list_first_entry 的定義
把 list 中的第一個元素當作 pivot ，用 list_first_entry 來取出元素，所以 AAA 為 struct item , BBB 為 list
接著再把 pivot 先從 list 中移除，因為 pivot 並不用跟著遞迴

CCC (itm, is, head, list) {
    if (cmpint(&itm->i, &pivot->i) < 0)
        DDD (&itm->list, &list_less);
    else
        EEE (&itm->list, &list_greater);
}

CCC 為 list_for_each_entry_safe 用來走訪整個 list
接著已經給定用以對節點內含值比較的函式 cmpint 來判斷節點數值跟 pivot 的大小
- 若是節點的數值小於 pivot ，則會將該節點移動到 list_less 的尾端
- 若是節點的數值大於等於 pivot ，則會將該節點移動到 list_greater 的尾端
- 所以 DDD 與 EEE 應皆為 list_move_tail

list_sort(&list_less);
list_sort(&list_greater);

接著需要透過遞迴不斷將直到分割不出串列為止

list_add(&pivot->list, head);
list_splice(&list_less, head);
FFF(&list_greater, head);

最後我們要將串列合併回來
- 比 pivot 數值小的節點都放在 pivot 前面，數值大的節點都放在 pivot 後面
- 首先先用 list_add 將 pivot 節點加入 head
- list_splice 從定義可以看出是用來將節點加到開頭，所以將 list_less 串接到 head
- 最後應該要把 list_greater 串接到尾端，所以 FFF 應為 list_splice_tail ，即可得到一個排序過後的 list

避免張貼完整程式碼，善用 GitHub 來保存及管理。

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

測驗 `2`

#define MAX_DEPTH 512
static void list_sort_nr(struct list_head *head)
{
    if (list_empty(head) || list_is_singular(head))
        return;

    struct list_head stack[MAX_DEPTH];
    for (int i = 0; i < MAX_DEPTH; i++)
        INIT_LIST_HEAD(&stack[i]);
    int top = -1;
    list_splice_init(head, &stack[++top]);

先確認 list 有無排序的必要後再往下執行，判斷 list 是否沒有節點或是只有一個節點
由上方的 define 可知，先宣告一個大小為 512 的 stack ，接著用 INIT_LIST_HEAD 做初始化

list_splice_init(head, &stack[++top]) 會把 head 節點的資料移動到 stack[0] ，然後初始化 head

struct list_head partition;
INIT_LIST_HEAD(&partition);

宣告 partition 並將它初始化

INIT_LIST_HEAD(&partition);
list_splice_init(&stack[top--], &partition);

進入迴圈後先將 partition 初始化，再把 stack[top] 的資料移動到 partition ，然後初始化 stack[top] ，最後因為從 stack[top] 拿出資料，所以 TOP 減一

if (!list_empty(&partition) && !list_is_singular(&partition)) {
    struct list_head list_less, list_greater;
    INIT_LIST_HEAD(&list_less);
    INIT_LIST_HEAD(&list_greater);

首先判斷 partition 所指向的 list 有節點且不只有一個節點
接著宣告 list_less, list_greater ， INIT_LIST_HEAD 後， list_less, list_greater 分別用來當比 pivot 小以及比 pivot 大 list 的 head

struct item *pivot =
    list_first_entry(&partition, struct item, list);
list_del(&pivot->list);
INIT_LIST_HEAD(&pivot->list);

把 list 中的第一個元素當作 pivot ，用 list_first_entry 來取出元素
接著再把 pivot 先從 list 中移除，因為 pivot 並不用跟著遞迴
最後再初始化 pivot 節點

struct item *itm = NULL, *is = NULL;
GGGG (itm, is, &partition, list) {
    list_del(&itm->list);
    if (cmpint(&itm->i, &pivot->i) < 0)
        list_move(&itm->list, &list_less);
    else
        list_move(&itm->list, &list_greater);
}

GGGG 為 list_for_each_entry_safe 用來走訪整個 list
接著已經給定用以對節點內含值比較的函式 cmpint 來判斷節點數值跟 pivot 的大小
- 若是節點的數值小於 pivot ，則會將該節點移動到 list_less
- 若是節點的數值大於等於 pivot ，則會將該節點移動到 list_greater

其中 list_del(&itm->list) 應該可以不用，根據 list_move 的定義，會先做 list_del 來將節點刪除

HHHH (&pivot->list, &list_less);
if (!list_empty(&list_greater))
    list_splice_tail(&list_greater, IIII);
if (!list_empty(&list_less))
    list_splice_tail(&list_less, JJJJ);

應要將 pivot 移動到 list_less 的尾端，所以 HHHH 為 list_move_tail
接著判斷如果 list_greater , list_less 不為空，就把它們串接到 stack[++top] 尾端
所以 IIII,JJJJ 皆為 stack[++top]

else {
    top++;
    list_splice_tail(&partition, &stack[top]);
    while (top >= 0 && list_is_singular(&stack[top])) {
        struct item *tmp =
            list_first_entry(&stack[top], struct item, list);
        list_del(&tmp->list);
        INIT_LIST_HEAD(KKKK);
        list_add_tail(&tmp->list, head);
    }
}

若判斷 partition 所指向的 list 沒有節點或是只有一個節點，則會進入 else
把 partition 串接到 stack[top] 尾端
進入迴圈後則是當 stack[top] 裡面只有一個節點時，就把 stack[top] 的節點加到 head 的尾端並初始化
所以 KKKK 應為 &stack[top--]

其中 list_del(&tmp->list) 與 list_add_tail(&tmp->list, head) 可以根據 list_move_tail 的定義改成 list_move_tail(&tmp->list, head);

根據 38 到 41 行，可以得知 stack 是從數值大放到數值小的，也就是 TOP 會放最小值
所以當 stack 中只有一個節點，就表示為當前的最小值，並會進入 else 把該節點加到 head 的尾巴

實驗結果

根據自己 lab0-c 量測 merge_sort 的 Perf 實驗，來實驗 recursive , non-recursive 版本 qucik sort 的效能

recursive

# node	cache-misses	branches	instructions	context-switches	time
1000	1941	77,9096	527,1670	0	0.0009604
10000	5036	613,9708	4443,3334	1	0.0056116
100000	115,6576	6397,8997	4,6220,5173	0	0.070447
1000000	7964,9292	6,7530,3741	48,1683,4390	4	1.23062

non-recursive

# node	cache-misses	branches	instructions	time
1000	1361	85,0934	575,9383	0.0009421
10000	3604	696,6615	5004,3747	0.006474
100000	120,2711	7312,8727	5,2320,1918	0.078943
1000000	8768,6011	7,6389,7122	54,3217,4602	1.4274

測驗 `3`

xor_node_t

xor_list_t

test_node

參考 XOR linked list
uintptr_t 可以將指標儲存為整數
- C99 [7.18.1.4] Integer types capable of holding object pointers
  
  The following type designates an unsigned integer type with the property that any valid pointer to void can be converted to this type, then converted back to pointer to void, and the result will compare equal to the original pointer

從 stdint.h 中可以發現對 uintptr_t 的定義

在 64 位元機器上， intptr_t 為 long int ， uintptr_t 為 unsigned long int
非 64 位元機器上， intptr_t 為 int ， uintptr_t 為 unsigned int

stdint.h

/* Types for `void *' pointers.  */
#if __WORDSIZE == 64
# ifndef __intptr_t_defined
typedef long int                intptr_t;
#  define __intptr_t_defined
# endif
typedef unsigned long int        uintptr_t;
#else
# ifndef __intptr_t_defined
typedef int                        intptr_t;
#  define __intptr_t_defined
# endif
typedef unsigned int                uintptr_t;
#endif

列出 C 語言規格書相關的描述。

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

#define XOR_COMP(a, b) ((xor_node_t *) (LLLL))

可以得知這是一個要做 XOR 運算的函式，但我們必須要將 a , b 做 casting
所以 LLL 應為 (uintptr_t) a ^ (uintptr_t) b

int main(void)
{
    xor_list_t list;
    xor_node_t *p1, *p2;

    XORLIST_INIT(list);
    for (int i = 0; i < 1000; i++) {
        struct test_node *new = malloc(sizeof(struct test_node));
        xornode_init(&new->xornode);
        new->value = i;
        xorlist_add(&list, &new->xornode);
        if (i == 5)
            p1 = &new->xornode;
        if (i == 6)
            p2 = &new->xornode;
    }

我們先看到 main

首先會先初始化 list ，以及 malloc 一個 test_node ，接著將他們傳入 xorlist_add

int xorlist_add(xor_list_t *list, xor_node_t *n)
{
    xor_node_t *real_next;

    if (!n)
        return ENOMEM;

    xor_node_t *real_prev = &list->head;
    xor_node_t *node = real_prev->cmp;

接著看到 xorlist_add 來插入節點

real_prev 指向 list 的 head
node 指向 real_prev 所指向 head 的 cmp 所指向的地方，也就是指向 tail

if (node == &list->tail)
        real_next = MMMM;
    else
        real_next = node;

node 在初始狀態的話 real_next 就應是 &list->tail

所以 MMMM 為 &list->tail

    real_prev->cmp = n;

首先將 real_prev 的 cmp 指向 n ，其中

n 指向要加入的新節點
real_prev 就是 list 的 head

    n->cmp = XOR_COMP(real_prev, real_next);

接著要計算 n 所指向節點的記憶體位址，存放到 cmp

將前面一個節點的位址與後面一個節點的位址做 XOR
- 假設 head 的位址為 A , tail 的位址為 B ，新節點的位址為 C

    real_next->cmp = XOR_COMP(n, XOR_COMP(real_prev, PPPP));
    list->count++;

    return 0;
}

接著要計算下一個節點 cmp 要存放的位址，其中 real_prev 要先和 PPPP 做 XOR 是為了要將 head 的位址消除掉，所以 PPPP 應為 real_next->cmp
- $C \oplus (A \oplus A) = (A \oplus B) \oplus (A \oplus A) = (A \oplus B) = C$

最後 count++

程式碼

2023q1 Homework1 (quiz1)

測驗 1

測驗 2

實驗結果

測驗 3

Read more

2023q1 Homework1 (lab0)

Demystifying the Linux CPU Scheduler 閱讀筆記

關於 BORE 及 schedgraph 的描述

2023q1 Homework7 (ktcp)

測驗 `1`

測驗 `2`

測驗 `3`