2024q1 Homework2 (quiz1+2)

contributed by < nelson0720j >

第 1 周測驗題

測驗一

解析

node_t 結構

typedef struct __node {
    struct __node *left, *right;
    struct __node *next;
    long value;
} node_t;

解題

list_tail

node_t *list_tail(node_t **left)
{
    while ((*left) && (*left)->next)
        left = &(AAAA); // *left->next
    return *left;
}

目標: 找出鏈結串列的最後一個節點，並輸出指向他的指標

*left 不斷指向他的 next 所指向的節點，直到這個節點不存在為止。

list_length

int list_length(node_t **left)
{
    int n = 0;
    while (*left) {
        ++n;
        left = &(BBBB); // (*left)->next
    }
    return n;
}

同上述，不斷更新 *left 所指向的節點，每往下移長度就加一。
3. iterative Quicksort

void quick_sort(node_t **list)
{
    int n = list_length(list);
    int value;
    int i = 0;
    int max_level = 2 * n;
    node_t *begin[max_level], *end[max_level];
    node_t *result = NULL, *left = NULL, *right = NULL;
    
    begin[0] = *list;
    end[0] = list_tail(list);
            
    while (i >= 0) {
        node_t *L = begin[i], *R = end[i];
        if (L != R) {
            node_t *pivot = L;
            value = pivot->value;
            node_t *p = pivot->next;
            pivot->next = NULL;
    
            while (p) {
                node_t *n = p;
                p = CCCC; // p->next
                list_add(n->value > value ? &right : &left, n);
            }

            begin[i] = left;
            end[i] = DDDD; // list_tail(&left)
            begin[i + 1] = pivot;
            end[i + 1] = pivot;
            begin[i + 2] = right;
            end[i + 2] = EEEE; // list_tail(&right)

            left = right = NULL;
            i += 2;
        } else {
            if (L)
                list_add(&result, L);
            i--;
        }
    }
    *list = result;
}

首先， pivot 設為最左邊的點， p 為 pivot 的下一個節點。依序看 p 的 vlaue 是否比 pivot 的 value 還大，若大於則加到 right 的鏈結串列中，反之，則加到 left 的鏈結串列中。

接下來，會分成三個鏈結串列。begin[0] 及 end[0] 紀錄 left 頭及尾端節點， begin[1] 及 end[1] 紀錄當前 pivot 節點，begin[2] 及 end[2] 紀錄 right 頭及尾端節點。

最後，迭代操作，直到分開的三個鏈結串列都只有一個節點，依序將節點加入到 result 。

測驗二

Timsort

解析

解題

merge
merge之實作

static struct list_head *merge(void *priv,
                               list_cmp_func_t cmp,
                               struct list_head *a,
                               struct list_head *b)
{
    struct list_head *head;
    struct list_head **tail = AAAA; // &head
    for (;;) {
        /* if equal, take 'a' -- important for sort stability */
        if (cmp(priv, a, b) <= 0) {
            *tail = a;
            tail = BBBB; // &a->next
            a = a->next;
            if (!a) {
                *tail = b;
                break;
			}
        } else {
            *tail = b;
            tail = CCCC; // &b->next
            b = b->next;
            if (!b) {
                *tail = a;
                break;
            }
		}
	}
    return head;
}

將 tail 指向 head 來達成首尾相接

接著，比較 a 和 b 所指向節點的值，若 a 小於或等於 b ，則將 a 加入 head 所指向的新佇列，反之，則將 b 加入。

build_prev_link
建立雙向循環鏈表的前向和後向鏈接。

static void build_prev_link(struct list_head *head,
                            struct list_head *tail,
                            struct list_head *list)
{
    tail->next = list;
    do {
        list->prev = tail;
        tail = list;
        list = list->next;
    } while (list);

    /* The final links to make a circular doubly-linked list */
    DDDD = head; // tail->next
    EEEE = tail; // head->prev
}

timsort

void timsort(void *priv, struct list_head *head, list_cmp_func_t cmp)
{
    stk_size = 0;

    struct list_head *list = head->next, *tp = NULL;
    if (head == head->prev)
        return;

    /* Convert to a null-terminated singly-linked list. */
    head->prev->next = NULL;

    do {
        /* Find next run */
        struct pair result = find_run(priv, list, cmp);
        result.head->prev = tp;
        tp = result.head;
        list = result.next;
        stk_size++;
        tp = merge_collapse(priv, cmp, tp);
    } while (list);

    /* End of input; merge together all the runs. */
    tp = merge_force_collapse(priv, cmp, tp);

    /* The final merge; rebuild prev links */
    struct list_head *stk0 = tp, *stk1 = stk0->prev;
    while (stk1 && stk1->prev)
        stk0 = stk0->prev, stk1 = stk1->prev;
    if (stk_size <= FFFF) { // 1
        build_prev_link(head, head, stk0);
        return;
    }
    merge_final(priv, cmp, head, stk1, stk0);
}

find_run 找出適合的遞增 run ，再將 tp 指向當前 run 的頭節點。

merge_collapse 執行合併操作，合併最小的兩個 run 。

merge_force_collapse 會持續合併，直到 stk_size < 3 (也就是小於 3 個 run )，如果有 1 個 run ，則 build_prev_link ， 2 個則 merge_final。

第 2 周測驗題

測驗一

結構

struct hlist_node {
    struct hlist_node *next, **pprev;
};

Linux 核心的 hash table 實作

hlist_node 結構為一個雙向鏈結串列， next 指標指向下一個節點本身， pprev 為指向指標的指標，存 &next 指向前一個節點的 next 指標

測驗

static inline void hlist_add_head(struct hlist_node *n, struct hlist_head *h)
{
    if (h->first)
        h->first->pprev = &n->next;
    n->next = AAAA; //h->first
    n->pprev = &h->first;
    h->first = n;
}

目標為: 將新節點 n 加到串列前面。
先檢查 h 的成員 first 是否非空，若為空，將原先 h 的 pprev 所指向的節點( node2 )的 pprev 指向要加入的 n 的 next 。

再將 n 的 next 指向 h 的 first 原先指向的節點，即可完成 n 和原先第一個節點 h->first 的雙向鏈結。

因此 AAAA 為 h->first 。

static int find(int num, int size, const struct hlist_head *heads)
{
    struct hlist_node *p;
    int hash = (num < 0 ? -num : num) % size;
    hlist_for_each (p, BBBB) {
        struct order_node *on = CCCC(p, struct order_node, node);
        if (num == on->val)
            return on->idx;
    }
    return -1;
}

此函式功用為找尋串列中是否有結構的值和參數 num 一樣，若有則回傳此節點的 index 。

hlist_for_each 傳入根據 mod 後的結構位址，因此 BBBB 為 &head[hash]。

接著要取得這個結構的值來比對，這裡用一個結構 order_node 來取得值和索引，透過傳入結構，指標和成員來取得這個結構 order_node 的位址。

因此 CCCC 是 list_entry 。

static inline void node_add(int val,
                            int idx,
                            int size,
                            struct hlist_head *heads)
{
    struct order_node *on = malloc(sizeof(*on));
    on->val = val;
    on->idx = idx;
    int hash = (val < 0 ? -val : val) % size;
    hlist_add_head(&on->node, DDDD);
}

hlist_add_head 他需要的參數為 hlist_head * ，因此根據 hash ，傳入目標位址。

DDDD 為 &heads[hash] 。

延伸問題

Linux 核心的 cgroups 相關原始程式碼

根據 kernel.docs

Control Groups provide a mechanism for aggregating/partitioning sets of tasks, and all their future children, into hierarchical groups with specialized behaviour.

cgroups 作用為限制，控制與隔離 Process 所使用到的系統資源。
cgroup 內可以有多個 subsystems ，各個 subsystem 分別對 cpu, memory, network 等去進行控制。

cgroup 可以以階層結構 ( Hierarchical Organization ) 的方式組織和管理，其子節點預設繼承父節點的屬性，形成一個 forest 的結構。

更多請見 cgroup v1 和 v2 介紹， v2 kernel.docs 。

在此先觀察 cgroup v1 的 pre-order walk 程式碼，

#define css_for_each_descendant_pre(pos, css)				\
	for ((pos) = css_next_descendant_pre(NULL, (css)); (pos);	\
	     (pos) = css_next_descendant_pre((pos), (css)))

上述程式碼會用 pre-order 的方式走過 css ( cgroup subsystem ) 的後代，並且提到會在依序走過樹的時候使用 cu_read_lock() 的函式作同步控制，確保狀態更新的一致。
另外，在 cgroup-defs.h 中的 struct cgroup_subsys_state 有提到保存 css 狀態的結構，方便管理整個樹狀的結構。

測驗二

LRU可能的合法 C 程式實作

void hlist_del(struct hlist_node *n)
{
    struct hlist_node *next = n->next, **pprev = n->pprev;
    *pprev = next;
    if (next)
        EEEE = pprev;
}

解釋:
**pprev = n->pprev 為將 pprev 指標指向 n 的 pprev 指標所指向的 next 指標，即 pprev 存 &(n->pprev) 。

解題:
先將 n 節點的前一個節點的 next 指向 n 的下一個節點(即 n->next ) 。
接著將 n 的下一個節點的 pprev 指向 n 的前一個節點的 next ，即可跳過節點 n ，達成類似刪除節點 n 的效果(實際上 n 節點仍存在)。
EEEE 為 next->pprev 。

void lRUCacheFree(LRUCache *obj)
{
    struct list_head *pos, *n;
    list_for_each_safe (pos, n, &obj->dhead) {
        LRUNode *cache = list_entry(pos, LRUNode, FFFF);
        list_del(GGGG);
        free(cache);
    }
    free(obj);
}

list_entry 的第三個參數是第二個參數型態的成員，因此根據以下 LRUNode 結構，可能成員為 node 或 link

typedef struct {
    int key;
    int value;
    struct hlist_node node;
    struct list_head link;
} LRUNode;

且根據 struct list_head *pos pos指標需要存一個 list_head 型別，
因此 FFFF 為 link。
找到結構位址後，用 list_del() 刪除結構，參數為 struct list_head *entry ，因此 GGGG 為 &cache->link 。
最後再釋放 cache 所指向的整個結構。

int lRUCacheGet(LRUCache *obj, int key)
{
    int hash = key % obj->capacity;
    struct hlist_node *pos;
    hlist_for_each (pos, &obj->hhead[hash]) {
        LRUNode *cache = list_entry(pos, LRUNode, HHHH);
        if (cache->key == key) {
            list_move(IIII, &obj->dhead);
            return cache->value;
        }
    }
    return -1;
}

解釋:
函式功能為獲取指定 key 的 value，並將最近使用過的節點，也就是符合 key 值的點，透過 list_move 移動到串列頭，以此代表最近使用過，來實現 LRU 。

解題:
pos 為 hlist_node * 型別，因此 HHHH 為 node 。
void list_move(struct list_head *entry, struct list_head *head) 需傳入 list_head 型別，因此 IIII 為 &cache->link。

void lRUCachePut(LRUCache *obj, int key, int value)
{
    LRUNode *cache = NULL;
    int hash = key % obj->capacity;
    struct hlist_node *pos;
    hlist_for_each (pos, &obj->hhead[hash]) {
        LRUNode *c = list_entry(pos, LRUNode, JJJJ);
        if (c->key == key) {
            list_move(KKKK, &obj->dhead);
            cache = c;
        }
    }
#以下省略
}

這個函式用於將一個鍵值對放入LRU快取中。根據LRU快取的特性，如果快取已滿且新的鍵值對要放入，則應該淘汰最近最少使用的鍵值對。
JJJJ 為 node ，KKKK 為 &c->link 。

延伸問題

解釋程式碼
結構:

在 Linux 核心找出 LRU 相關程式碼並探討
lru_cache
struct lc_element: 代表快取中的一個元素。
struct lru_cache: 代表整個 LRU 快取。
lc_create: 用於初始化 LRU 快取。
lc_get: 通過標籤獲取元素，並可能改變活動集。
lc_put: 減少元素的引用計數，並在引用計數為零時將其移到 LRU 列表中。

測驗三

參考資料

作業要求

2024q1 Homework2 (quiz1+2)

第 1 周測驗題

測驗一

解析

解題

測驗二

解析

解題

第 2 周測驗題

測驗一

結構

測驗

延伸問題

測驗二

延伸問題

測驗三

參考資料

Read more

2024q1 Homework5 (assessment)

2024q1 Homework6 (integration)

2024q1 Homework4 (quiz3+4)

linux2024-homework1