2021q1 Homework2 (quiz2)

contributed by < DokiDokiPB >

相關資訊

• 課程資訊
• 交作業區
• 測驗題目
• 筆記觀摩

測驗一

選擇題

COND1 && COND2

• ( c ) fast->next == list
• ( b ) fast->next->next == list
• fast 移動距離為 slow 兩倍，因為 queue 採取 circular queue 的方式，透過判斷否走回 head 的方式中斷 list_for_each。
• fast 的起始點為 list->next
  • 如果 queue node 數量為偶數，當 fast->next == list head 時， slow 就會在中間。
  • 如果 queue node 數量為奇數，當 fast->next->next == list head 時， slow 就會在中間。

MMM

• (e) &get_middle(&q->list)->list

TTT

• 這裡要求傳回 middle，依據上面 CONT1 & CONT2 的結果，也就是傳回 slow。

解釋程式碼運作原理

container_of

• container_of
• gcc gnu typeof
• 你所不知道的 C 語言：技巧篇 善用 GNU extension 的 typeof

list_head

struct list_head {
    struct list_head *prev, *next;
};
#define LIST_HEAD(head) struct list_head head = {&(head), &(head)}

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

• 依據測驗題目筆記的說明，只要在自己的 struct 引入 list_head，無須自己維護一套 doubly-linked list
• 當 head 指向自己時候，表示此 head 為空，沒有東西。

在本程式碼實作，會有兩種情況

• queue_t 中的 list，用於記錄 head，不用於記錄資料內容
• list_ele_t 中的 node，用於記錄 node，不用於記錄 linked list.

在 function 中的命名有反應此情況：

• 以 struct list_head *node 表示其為 node，非 head
• 以 struct list_head *head 表示其為 head， head->next 為其 node
• 以 struct list_head *list 表示其為 head 並且很多 node

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;
}

• head->prev 就是取得 list tail，並將新的 node 接上 list tail 之後。

list_del

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

• 刪除 node 的方式就是將 prev 跟 next 相連結
• 如果 node == prev 或是 node == next， list_del 不會有作用
• 只是將目標 node 移除該 list

list_empty

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

• 就是判斷 list_head 是否只有自己(head)

list_is_singular

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

• head->prev == head->next 表示指向 head 或是指向同一個 node，再透過 !list_empty 排除指向 head 的情況，即可獲得 head 中只有一個 node

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, *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;
}

• list_splice_tail 的目的是將 list 整串加入 head 尾端中
• 因為 list_head 為 doubly-linked list，也就是取得頭尾，並且重新串接。

list_cut_position

static inline void list_cut_position(struct list_head *head_to,
                                     struct list_head *head_from,
                                     struct list_head *node)
{
    struct list_head *head_from_first = head_from->next;

    if (list_empty(head_from))
        return;

    if (head_from == node) {
        INIT_LIST_HEAD(head_to);
        return;
    }

    head_from->next = node->next;
    head_from->next->prev = head_from;

    head_to->prev = node;
    node->next = head_to;
    head_to->next = head_from_first;
    head_to->next->prev = head_to;
}

• list_cut_position 的目標是切割成兩串 list
  • head_to 為存放切割過後的左半 list，切割後存放範圍為原本 head_from->next 至 node
  • head_from 為被切割的 list，切割後的存放右半 list，存放範圍為 node->next 至 head_from->prev
  • node 為切割的點

list_entry

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

• list_head 新增至使用者自定義的結構中，原本可以透過自定義的結構體取得 list_head，但是 list_head 不能反查自定義的結構。
• 透過 container_of 的特性，可以反查結構，並取得該結構。

改進部份 第一版本

移除不必要的程式碼

• 在 list_head 中，有明顯的分別 list_head node 跟 list_head head 兩者操作方式不一樣，需要修改名稱以符合定義
  • 修改 list_ele_t 中 list 改為 node
  • queue_t 保持原樣
• queue_t 中不需要去額外新增 head, tail
• queue_t 中 size 沒有使用，也是可以移除。

typedef struct __element {
    char *value;
-   struct list_head list;
+   struct list_head node;
} list_ele_t;

typedef struct {
-    list_ele_t *head; /* Linked list of elements */
-    list_ele_t *tail;
-    size_t size;
    struct list_head list;
} queue_t;

function 名稱錯誤

• delete 一字的意思為刪除，表示會刪除其資料內容，應改為 remove
• 操作的對象為 node，名稱應修正成 list_remove_node 表示這是移除 node

- static inline void list_del(struct list_head *node)
+ static inline void list_remove_node(struct list_head *node)

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

• 請參閱筆記 研讀 Linux 核心的 lib/list_sort.c 原始程式碼

TODO:

• 閱讀程式碼並且回答選擇題
• 回答延伸問題
  • 解釋上述程式碼運作原理，指出改進空間並著手實作
  • 研讀 Linux 核心的 lib/list_sort.c 原始程式碼，學習 sysprog21/linux-list 的手法，將 lib/list_sort.c 的實作抽離為可單獨執行 (standalone) 的使用層級應用程式，並設計效能評比的程式碼，說明 Linux 核心的 lib/list_sort.c 最佳化手法
  • 將你在 quiz1 提出的改進實作，和 Linux 核心的 lib/list_sort.c 進行效能比較，需要提出涵蓋足夠廣泛的 benchmark

測驗二

• 閱讀程式碼並且回答選擇題
• 回答延伸問題
  • 解釋上述程式碼運作原理
  • 在 The Linux Kernel API 頁面搜尋 “power of 2”，可見 is_power_of_2，查閱 Linux 核心原始程式碼，舉例說明其作用和考量，特別是 round up/down power of 2
    • 特別留意 __roundup_pow_of_two 和 __rounddown_pow_of_two 的實作機制
  • 研讀 slab allocator，探索 Linux 核心的 slab 實作，找出運用 power-of-2 的程式碼和解讀

測驗三

• 閱讀程式碼並且回答選擇題
• 回答延伸問題
  • 解釋上述程式碼運作原理，並嘗試重寫為同樣功能但效率更高的實作
  • 在 Linux 核心原始程式碼找出逐 bit 進行資料複製的程式碼，並解說相對應的情境

測驗四

• 閱讀程式碼並且回答選擇題
• 回答延伸問題
  • 上述程式碼使用到 gcc atomics builtins，請透過 POSIX Thread 在 GNU/Linux 驗證多執行緒的環境中，string interning 能否符合預期地運作？若不能，請提出解決方案
  • chriso/intern 是個更好的 string interning 實作，請探討其特性和設計技巧，並透過內建的 benchmark 分析其效能表現