2023q1 Homework1 (quiz1)

contributed by < Welly0902 >

測驗一

延伸問題

解釋程式碼運作原理
針對 Quick sort 提出程式碼的改進方案並實作
引入 hybrid sort 策略並在 Linux 核心風格的 circular doubly-linked list 實作，需要量化性能表現並探討不同資料集 (data set) 的影響
BONUS: 嘗試對 Linux 核心提出排序程式碼改進的貢獻

Circular doubly-linked list 節點 structure 定義如下：

#include <stdint.h>
#include "list.h"

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

再來是節點內含值比較的函式：

static inline int cmpint(const void *p1, const void *p2)
{
    const uint16_t *i1 = (const uint16_t *) p1;
    const uint16_t *i2 = (const uint16_t *) p2;
    return *i1 - *i2;
}

可看到 cmpint 並不是直接 return *p1 - *p2;，故接下來會觀察一下 uint16_t 這個資料型態是否有它必要的意義。

再來看一下 sorting 的程式：

static void list_sort(struct list_head *head)
{
    //1
    if (list_empty(head) || list_is_singular(head))
        return;

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

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

    //4
    struct item *itm = NULL, *is = NULL;
    // CCC
    list_for_each_entry_safe (itm, is, head, list) {
        if (cmpint(&itm->i, &pivot->i) < 0)
            // DDD
            list_move_tail (&itm->list, &list_less);
        else
            // EEE
            list_move_tail (&itm->list, &list_greater);
    }
    
    //5
    list_sort(&list_less);
    list_sort(&list_greater);

    //6
    list_add(&pivot->list, head);
    list_splice(&list_less, head);
    // FFF
    list_splice_tail(&list_greater, head);
}

一段一段拆解來看，首先：

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

參照 list.h 說明，我們可以看到list_empty的程式碼：

static inline int list_empty(const struct list_head *head)
{
    return (head->next == head);
}

return 1 代表 list 是空的，也就是說的 head->next == head 時 list 是空的，這裡我不太確定 circular doubly-linked list 當一開始空的時候長怎樣，所以我們回去看 list.h 中的 INIT_LIST_HEAD：

static inline void INIT_LIST_HEAD(struct list_head *head)
{
    head->next = head;
    head->prev = head;
}

畫成圖為：

所以從上圖我們可看出 head->next == head 確實為只有 head 的初始狀態，為空。

接下來看一下 list_is_singular function，同樣查看 list.h 了解它的目的是為了去檢驗是否剛好只有一個節點在此。看一下下方程式碼:

static inline int list_is_singular(const struct list_head *head)
{
    return (!list_empty(head) && head->prev == head->next);
}

可看條件為非空且 head->prev 與 head->next 指到同一個 node。

所以回到 sorting 原程式，//1 先檢查如果 input list 為空或只有一個節點，那直接回傳即為排列好的 list。再來 //2 的部分 initialize 了兩個 pointer list_less 和 list_greater:

再來 //3 的部分首先先看 list_first_entry macro 的程式碼:

#define list_first_entry(head, type, member) \
    list_entry((head)->next, type, member)

可以看到運用了另一個 macro list_entry:

#define list_entry(node, type, member) container_of(node, type, member)

裡面又連結到另一個 list.h 中的 macro container_of，並根據 ifdef, ifndef 定義加上 indentation 以方便閱讀:

#ifndef container_of
    #ifdef __LIST_HAVE_TYPEOF
        #define container_of(ptr, type, member)                            \
            __extension__({                                                \
                const __typeof__(((type *) 0)->member) *__pmember = (ptr); \
                (type *) ((char *) __pmember - offsetof(type, member));    \
            })
    #else
        #define container_of(ptr, type, member) \
            ((type *) ((char *) (ptr) -offsetof(type, member)))
    #endif
#endif

對於 __LIST_HAVE_TYPEOF 檢查是否允許 GNUC extension 有關條件的說明可參考之前同學的說明。這裡直接看

延伸閱讀: 為何需要 char * casting、macro container_of explained、kobject 基礎介紹

而這裡透過詢問 chatgpt，可快速了解 container_of macro 所代表的意義

Q: container_of in linux kernel
ChatGPT: container_of is a powerful and commonly used macro in the Linux kernel that allows a developer to obtain a pointer to a structure containing a given field.

The container_of macro takes three arguments: a pointer to a field in a structure, the name of the structure containing the field, and the name of the field itself. The macro then computes the offset of the field within the structure and returns a pointer to the containing structure.
:::
所以我們可知 list_entry 可讓我們得到一個 member pointer 用來取用目前 pointer 指向節點內的 member，以取用節點內 member進行操作。而list_first_entry 則可得到指向目前 linked list 中第一個節點的 mpointer 來對其進行操作。

回到 //3 的程式碼，從說明可以快速推出 AAA 與 BBB 為 item 和 list。

 * @type: type of the entry containing the list node
 * @member: name of the list_head member variable in struct @type

再來看程式碼:

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

首先第一行:

再來第二行的 list_del 程式碼如下:

static inline void list_del(struct list_head *node)
{
    struct list_head *next = node->next;
    struct list_head *prev = node->prev;

    next->prev = prev;
    prev->next = next;

#ifdef LIST_POISONING
    node->prev = (struct list_head *) (0x00100100);
    node->next = (struct list_head *) (0x00200200);
#endif
}

LIST_POISONING can be enabled during build-time to provoke an invalid memory
access when the memory behind the next/prev pointer is used after a list_del.
This only works on systems which prohibit access to the predefined memory addresses.

這裡做 deletion 是為了先將選中的 pivot (此程式是選 list 的第一個元素當作 pivot) 當作分隔 list 中 node 的 i 值大小的依據。Deletion 過程如下圖:

由上圖可以看出 n2 及 n3 經過 pivot 指向的 node n1 deletion 後已經成為
一個 circular doubly-linked list，不過從此處程式碼看不出:

n1 節點剩餘 link 的處理
list head 也沒有重新指到新的頭尾
這兩個問題暫時還沒找到解答。

再來先繼續往下看主程式:

    //4
    struct item *itm = NULL, *is = NULL;
    // CCC
    list_for_each_entry_safe (itm, is, head, list) {
        if (cmpint(&itm->i, &pivot->i) < 0)
            // DDD
            list_move_tail (&itm->list, &list_less);
        else
            // EEE
            list_move_tail (&itm->list, &list_greater);
    }

首先先建立等等 for each 會用到的 member pointer:

接下來先看一下 list_move_tail 的程式:

static inline void list_move_tail(struct list_head *node,
                                  struct list_head *head)
{
    list_del(node);
    list_add_tail(node, head);
}

以及 list_add_tail 的程式:

static inline void list_add_tail(struct list_head *node, struct list_head *head)
{
    struct list_head *prev = head->prev;

    prev->next = node;
    node->next = head;
    node->prev = prev;
    head->prev = node;
}

那我們假設目前的 list 如下圖:

則當我們利用 cmpint 與 pivot相減後，以上圖例子來看，首先3-6<0，故會執行list_move_tail (&itm->list, &list_less);:

先執行 list_del(&itm->list)(當下節點為 3):

接著 list_add_tail(&itm->list, &list_less):

當執行完主程式的 //4，可得下圖:

接著進行到 //5 時，會將 list_less 和 list_greater 中的值遞迴排序好。
排序好後會剩下 list_less 和 list_greater 的 list 和 pivot node 並執行 //6。
在執行前先看一下 list_splice 的程式碼:

static inline void list_splice(struct list_head *list, struct list_head *head)
{
    struct list_head *head_first = head->next;
    struct list_head *list_first = list->next;
    struct list_head *list_last = list->prev;

    if (list_empty(list))
        return;

    head->next = list_first;
    list_first->prev = head;

    list_last->next = head_first;
    head_first->prev = list_last;
}

以及 list_splice_tail 的程式碼:

static inline void list_splice_tail(struct list_head *list,
                                    struct list_head *head)
{
    struct list_head *head_last = head->prev;
    struct list_head *list_first = list->next;
    struct list_head *list_last = list->prev;

    if (list_empty(list))
        return;

    head->prev = list_last;
    list_last->next = head;

    list_first->prev = head_last;
    head_last->next = list_first;
}

在 //6 中先執行 list_add(&pivot->list, head) 將 pivot 加到 head pointer 最前面:

list_splice_tail 時從 head->prev 也就是 head 這個 linked list的最後一個節點(6)進行操作:

測驗二

延伸問題

解釋程式碼運作原理
針對 Quick sort 提出程式碼的改進方案並實作
引入 hybrid sort 策略並在 Linux 核心風格的 circular doubly-linked list 實作，需要量化性能表現並探討不同資料集 (data set) 的影響
BONUS: 嘗試對 Linux 核心提出排序程式碼改進的貢獻

測驗三

延伸問題

解釋上述程式碼運作原理，指出其實作缺陷並改進
在上述 XOR linked list 的基礎，實作測驗 1 和 2 提及的快速排序演算法，注意要引入你改進效能的版本
修改 xorlist_destroy，使其不急著釋放記憶體，而搭配 atexit(3) 並在程式即將結束執行時，才批次處理資源釋放

2023q1 Homework1 (quiz1)

測驗一

測驗二

測驗三

Read more

2023q1 Homework1 (lab0)

Build RAID0 in Ubuntu