# **2024q1 Homework2 (quiz1+2)**

contributed by [<YeeeLiang](https://github.com/YeeeLiang/2024HW2)>

## **第一周 測驗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。