Try   HackMD

2024q1 Homework2 (quiz1+2)

contributed by <YeeeLiang>

第一周 測驗1

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

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

延伸問題

1. 原始程式碼的解釋:

  • 節點結構 (node_t): 代表鏈結串列中的一個節點。 包含指向左右子節點,以及一個指向下一個節點的指標。
  • 串列操作函數: list_add: 在串列的開頭添加一個節點。 list_tail: 返回串列的尾部。 list_length: 返回串列的長度。 list_construct: 建構一個新節點並將其添加到串列的開頭。 list_free: 釋放串列佔用的記憶體。
  • quick_sort: 使用輔助堆疊(begin 和 end)實現快速排序的非遞迴,來跟蹤子串列。
  • main: 創建一個整數陣列,對其進行洗牌,構建一個鏈結串列,使用快速排序進行排序。

2. 改寫的程式碼:

#include <linux/list.h>
#include <linux/kernel.h>

typedef struct __node {
    struct list_head list;
    long value;
} node_t;

void quick_sort(struct list_head *list);
void print_list(struct list_head *list);

int main(void) {
    LIST_HEAD(my_list);
    quick_sort(&my_list);
    print_list(&my_list);

    return 0;
}

void quick_sort(struct list_head *list) {
}

void print_list(struct list_head *list) {
}

第一周 測驗2

    struct list_head *head;
-    struct list_head **tail = AAAA;
+    struct list_head **tail = &(head->next);

    for (;;) {
        
        if (cmp(priv, a, b) <= 0) {
            *tail = a;
-           tail = BBBB;
+           tail = &((*tail)->next);
            a = a->next;
            if (!a) {
                *tail = b;
                break;
            }
        } else {
            *tail = b;
-           tail = CCCC;
+           tail = &((*tail)->next);
            b = b->next;
            if (!b) {
                *tail = a;
                break;
            }
        }
    }
    return head;
}
-    DDDD = head;
-    EEEE = tail;
+    (stk1->prev) = head
+    (stk0->prev) = tail;

延伸問題

  • run_size 函數:計算當前非遞減順序的元素序列(run)的大小。
  • merge 函數:將兩個run合併為一個。
  • build_prev_link 函數:為合併後的run建立前一個連結。
  • merge_final 函數:在合併主run後,合併剩餘的runs。
  • find_run 函數:在輸入列表中找到下一個run。
  • merge_at 函數:在指定位置合併兩個相鄰的runs。
  • merge_force_collapse 函數:強制折疊,不斷合併相鄰的runs。
  • merge_collapse 函數:根據設定條件合併runs。
  • timsort 函數:協調整個Timsort演算法,查找並合併runs,直到堆疊被折疊。
  • 改進後程式碼:
static struct list_head *merge(void *priv,
                               list_cmp_func_t cmp,
                               struct list_head *a,
                               struct list_head *b)
{
    struct list_head *head = malloc(sizeof(struct list_head));
    struct list_head **tail = &(head->next);
    return head;
}

第二周 測驗1

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;
+   n->next = h->first;
    n->pprev = &h->first;
    h->first = n;
}
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) {
+   hlist_for_each (p, head) {
-       struct order_node *on = CCCC(p, struct order_node, node);
+       struct order_node *on = container_of(p, struct order_node, node);
        if (num == on->val)
            return on->idx;
    }
    return -1;
}
{
    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(&on->node, heads[hash]);
}

延伸問題

1.

這段程式碼主要是用在構建二叉樹,基於給定的先序遍歷(preorder)和中序遍歷(inorder)序列,通過深度優先搜索(DFS)的方式構建對應的二叉樹。其中,使用了哈希表(Hash table)和鍊錶(linked lists)的概念,來實現尋找元素在中序序列中的索引功能。

程式碼中的主要結構和功能包括:

  • 定義一個單向鏈錶的節點結構 struct hlist_node 和一個哈希鏈錶的頭結構 struct hlist_head
  • 定義一個二叉樹節點的結構 struct TreeNode
  • 使用了一個哈希鏈錶結構 struct order_node 來保存中序序列中元素的值、索引,並連接到哈希鏈錶中。
  • 構建二叉樹的主函數 buildTree,可初始化哈希鏈錶,並調用 dfs 開始構建二叉樹。dfs 為使用 DFS 遞迴構建二叉樹的函數 。
#include <stdio.h>

int main() {
    int preorder[] = {3, 9, 20, 15, 7};
    int inorder[] = {9, 3, 15, 20, 7};
    int preorderSize = sizeof(preorder) / sizeof(preorder[0]);
    int inorderSize = sizeof(inorder) / sizeof(inorder[0]);
    
    struct TreeNode *root = buildTree(preorder, preorderSize, inorder, inorderSize);

    return 0;
}
  • 可改進之處:
  1. 程式碼中使用了哈希值計算索引的方式,可以考慮使用現有的哈希函數,而非簡單的 (num < 0 ? -num : num) % size。
  2. 記憶體管理:在程式中使用了 malloc 分配內存,但缺乏相應的 free 釋放內存的操作。
  3. 沒有處理例外情況:程式碼沒有處理 malloc 失敗的情況,應該在分配內存後,設置檢查是否成功。

2.

cgroups(Control Groups)是 Linux 內核中的一個機制,用於限制、分類和監控進程及其資源的使用。cgroup 組成一個樹狀結構,而其中每個節點代表一個 cgroup。Pre-order walk是一種樹狀結構中的走訪方式,它會先訪問父節點,然後再訪問子節點。

pre-order walk 程式碼:

// kernel/cgroup/cgroup.c
#include <linux/cgroup.h>

static void cgroup_pre_order(struct cgroup_root *root,void (*proc)(struct cgroup *, void *),void *data)
{struct cgroup *cgrp, *child;rcu_read_lock();proc(&root->top_cgroup, data);list_for_each_entry(cgrp, &root->top_cgroup.children, sibling) {proc(cgrp, data);list_for_each_entry(child, &cgrp->children, sibling)proc(child, data);}rcu_read_unlock();
}
EXPORT_SYMBOL_GPL(cgroup_pre_order);

第二周 測驗2

    struct hlist_node *next = n->next, **pprev = n->pprev;
    *pprev = next;
    if (next)
-       EEEE = pprev;
+       pprev = 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);
+      LRUNode *cache = list_entry(pos, LRUNode, link);
-       list_del(GGGG);
+       list_del(link);
        free(cache);
    }
    free(obj);
}

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);
+       LRUNode *cache = list_entry(pos, LRUNode, node);
        if (cache->key == key) {
-           list_move(IIII, &obj->dhead);
+           list_move(&cache->link, &obj->dhead);
            return cache->value;
        }
    }
    return -1;
}

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);
+       LRUNode *c = list_entry(pos, LRUNode, node);
        if (c->key == key) {
-           list_move(KKKK, &obj->dhead);
+           list_move(&cache->link, &obj->dhead);
            cache = c;
        }
    }

延伸問題

1.

雙向鏈表(struct list_head):

  • 用於根據元素的使用情況維護緩存中元素的順序。
  • INIT_LIST_HEAD:初始化一個空的雙向鏈表。
  • __list_add:在指定的元素之後將新元素添加到鏈表中。
  • __list_del:從鏈表中刪除元素。

哈希表(struct hlist_head):

  • 用於根據鍵快速訪問緩存中的元素。
  • INIT_HLIST_HEAD:初始化一個空的哈希表。
  • hlist_add_head:將新元素添加到哈希表中。
  • hlist_del:從哈希表中刪除元素。

LRUCache 結構:

  • 維護一個雙向鏈表(dhead)來跟蹤元素的使用順序。
  • 使用哈希表數組(hhead)以便高效地根據鍵訪問緩存元素。
  • LRUNode 結構表示緩存中的鍵值對,具有雙向鏈表節點和哈希表節點。

LRUCache 操作:

  • lRUCacheCreate:初始化並分配 LRUCache 結構的內存。
  • lRUCacheFree:釋放 LRUCache 結構及其元素使用的內存。
  • lRUCacheGet:從緩存中檢索與給定鍵相關聯的值。
  • lRUCachePut:在緩存中插入或更新鍵值對。

改進的地方:

  • lRUCachePut 中的 list_move 函數存在潛在問題:因為在為 cache 分配值之前,它就已被移動。這可能導致未定義的行為。應該在分配值之前移動項目(&c->link)而不是 &cache->link。
  • lRUCacheFree函數使用list_entry 從列表中訪問 LRUNode,但雙向鏈表的用法為 list_entry。故應該更改為list_entry
#include <stdio.h>

int main() {
    LRUCache *cache = lRUCacheCreate(3);

    lRUCachePut(cache, 1, 1);
    lRUCachePut(cache, 2, 2);
    lRUCachePut(cache, 3, 3);

    printf("Get key 2: %d\n", lRUCacheGet(cache, 2)); 
    lRUCachePut(cache, 4, 4);

    printf("Get key 1: %d\n", lRUCacheGet(cache, 1)); 
    lRUCacheFree(cache);

    return 0;
}

2.

在 Linux 核心的虛擬記憶體管理和緩存中,LRU 策略的實現是系統性能的關鍵部分。這些代碼確保了對於使用頻率較低的頁面進行有效管理,以最大程度地減少對物理內存和磁盤 I/O 的需求。

LRU相關程式碼:

#include <stdio.h>
#include <stdlib.h>

#define CACHE_SIZE 3

typedef struct {
    int key;
    int value;
} CacheItem;

typedef struct {
    CacheItem *cacheArray; 
    int *order;           
    int size;            
    int count;           
} LRUCache;

LRUCache *initCache(int size) {
    LRUCache *cache = (LRUCache *)malloc(sizeof(LRUCache));
    cache->cacheArray = (CacheItem *)malloc(size * sizeof(CacheItem));
    cache->order = (int *)malloc(size * sizeof(int));
    cache->size = size;
    cache->count = 0;

    for (int i = 0; i < size; i++) {
        cache->order[i] = -1;
    }

    return cache;
}

int findItem(LRUCache *cache, int key) {
    for (int i = 0; i < cache->size; i++) {
        if (cache->cacheArray[i].key == key) {
            return i; 
        }
    }
    return -1; 
}

void updateOrder(LRUCache *cache, int index) {
 
    for (int i = 0; i < cache->size; i++) {
        if (cache->order[i] >= 0) {
            cache->order[i]++;
        }
    }
    cache->order[index] = 0;
}

void addItem(LRUCache *cache, int key, int value) {
    if (cache->count >= cache->size) {
        int maxOrderIndex = 0;
        for (int i = 1; i < cache->size; i++) {
            if (cache->order[i] > cache->order[maxOrderIndex]) {
                maxOrderIndex = i;
            }
        }
        cache->cacheArray[maxOrderIndex].key = key;
        cache->cacheArray[maxOrderIndex].value = value;
        updateOrder(cache, maxOrderIndex);
    } else {
        int index = cache->count;
        cache->cacheArray[index].key = key;
        cache->cacheArray[index].value = value;
        updateOrder(cache, index);
        cache->count++;
    }
}

int get(LRUCache *cache, int key) {
    int index = findItem(cache, key);
    if (index >= 0) {
        updateOrder(cache, index);
        return cache->cacheArray[index].value;
    } else {
        return -1; 
    }
}

int main() {
    LRUCache *cache = initCache(CACHE_SIZE);

    addItem(cache, 1, 10);
    addItem(cache, 2, 20);
    addItem(cache, 3, 30);

    printf("Item with key 2: %d\n", get(cache, 2)); 
    addItem(cache, 4, 40);

    printf("Item with key 1: %d\n", get(cache, 1)); 
    printf("Item with key 2: %d\n", get(cache, 2)); 

    free(cache->cacheArray);
    free(cache->order);
    free(cache);

    return 0;
}

第二周 測驗3

#if BITS_PER_LONG == 64
-   if ((word & AAAA) == 0) {
+   if ((word & 0xFFFFFFFF00000000UL) == 0) {
        num += 32;
        word >>= 32;
    }
static inline void __clear_bit(unsigned long nr, volatile unsigned long *addr)
{
    unsigned long mask = BIT_MASK(nr);
    unsigned long *p = ((unsigned long *) addr) + BIT_WORD(nr);
    
-   *p &= BBBB;
+   *p &= ~BIT_MASK(nr);
}

延伸問題

1.

這是一組用於操作和搜尋位元,在由無號長整數陣列表示的位圖巨集和內嵌函數。旨在以高效的方式進行位元操作和搜尋,1並考慮到不同的字大小(8、16、32 和 64 位元)。find_nth_bit 函數是核心部分,提供了在位圖中查找第 n 個設置位元位置的通用方法。

位元操作巨集:

  • BITS_PER_LONG:定義了無號長整數中的位元數(假定為 64 位元)。
  • BIT_MASK(nr):創建具有第 n 位元設置的位遮罩。
  • BIT_WORD(nr):確定包含第 n 位元的無號長整數的索引。
  • BITMAP_LAST_WORD_MASK(nbits):為位圖中的最後一個單詞創建一個位遮罩。

向上取整的除法巨集:

  • DIV_ROUND_UP(n, d):將 n 除以 d 並向上取整。

位元計數巨集:

  • __const_hweight8(w):計算 8 位元字中設置位元的數量。
  • __const_hweight16(w)、__const_hweight32(w)、__const_hweight64(w):將位元計數擴展到 16、32 和 64 位元。
  • hweight_long(w):使用 64 位元計數的包裝函數,對無號長整數進行計數。

最小值巨集:

  • min(x, y):返回兩個值的最小值。

查找第 n 個設置位元:

  • FIND_NTH_BIT(FETCH, size, num):查找在由 FETCH 定義的位圖中的第 n 個設置位元的位置。它使用輔助函數 hweight_long 和 fns 來實現。

查找第一個設置位元的函數:

  • __ffs(word):查找字中第一個設置位元的位置。

清除位元的函數:

  • __clear_bit(nr, addr):在給定地址上清除第 n 位元。

查找第 n 個設置位元的函數:

  • find_nth_bit(addr, size, n):查找由 addr 和 size 指定的位圖中的第 n 個設置位元的位置。

其他巨集:

  • small_const_nbits(nbits):檢查位元數是否是常數且在單個無號長整數的範圍內。
  • GENMASK(h, l):生成具有第 l 到第 h 位元設置的遮罩。

2.

find_nth_bit函數通常用於在位元運算中找到某個位元序列的第 n 個設定(或清除)的位元,可應用在 CPU affinity 設定中。而在 Linux 核心中,CPU affinity 相關的原始碼通常與進程排程和任務管理有關。

一個常見的使用案例是在 sched.h中,可能會涉及到 cpumask_t 類型的位元遮罩,而 find_nth_bit 可能用於在這些位元遮罩中找到特定的 CPU。