2024q1 Homework2 (quiz1+2)

contributed by < YiChiChao >

閱讀 你所不知道的 C 語言：數值系統 文中實作

FreeBSD 案例分析

#define KSIZE 1024
char kbuf[KSIZE];
int copy_from_kernel(void *user_dest, int maxlen) {
    int len = KSIZE < maxlen ? KSIZE : maxlen;
    memcpy(user_dest, kbuf, len);
    return len;
}

文中提問：假設懷有惡意的程式設計師將「負」的數值作為 maxlen 帶入 copy_from_kernel，會有什麼問題？

copy_from_kernel 原本的功能是將至多 KSIZE bytes 的字元複製到 user_dest 。如果傳入的 maxlen 為負值，則在函式的第一行 int len 便會被賦值到負數。

/* Copy N bytes of SRC to DEST.  */
extern void *memcpy (void *__restrict __dest, const void *__restrict __src,
		     size_t __n) 

memcpy 傳入的參數 n 的型別為 size_t , 也就是 unsigned integer 。

所以如果 len 是負數，傳入 memcpy 就會是一個很大的數值，至少可以確定一定超過 1024 。

---

2002 年 External data representation (XDR)

void *copy_elements(void *ele_src[], int ele_cnt, int ele_size) {
    void *result = malloc(ele_cnt * ele_size);
    if (result==NULL) return NULL;
    void *next = result;
    for (int i = 0; i < ele_cnt; i++) {
        memcpy(next, ele_src[i], ele_size);
        next += ele_size;
    }
    return result;
}

文中提問：假設懷有惡意的程式設計師將 ele_cnt =

$2^{52}+1$ , ele_size =

$2^{12}$ 帶入，會有什麼問題？

void *malloc(size_t size);

已知 size_t 為 unsigned integer ，以 word size 為 64 的電腦，實際的數值範圍是

$0$ ~

$2^{64}-1$ 。

透過兩數相乘會得到 integer overflow 的結果，數值為

$2^{12}$ 。

#include <math.h>
#include <stdint.h>
#include <stdio.h>

int main() {
  size_t c = 4096;             // 2^12
  size_t d = 4503599627370497; // 2^52+1

  printf("%ld\n", c * d);
  return 0;
}

/* Output: 4096 */

也就是說，malloc 所回傳的指標所配置到的位置不足夠接續的複製工作。

2024q1 第 1 週測驗題

測驗 1

運作原理

作者將 Quick Sort 以非遞迴的方式，想避免函式呼叫，以及同一數字不必要的移動。

• node_t *right：存放當前迭代所有節點數值比 pivot 大的節點，初始狀態 right = NULL
• node_t *left：存放當前迭代所有節點數值比 pivot 小的節點，初始狀態 left = NULL
• node_t *begin[max_level]: 紀錄每個佇列的頭節點指標的陣列，初始狀態 begin[0] = list_head
• node_t *end[max_level]: 紀錄每個佇列的尾節點指標的陣列，初始狀態 end[0] = list_tail

在 QuickSort 函式的一次迭代中，將佇列的第一個節點數值設為 pivot ，在遍歷整個佇列過程中，將節點數值大於 pivot的節點插入 right 佇列，將節點數值小於 pivot的節點插入 left 佇列。

完成一次迭代後，更新begin 和 after 陣列，將 right 和 left 佇列的頭節點指標以及 pivot 對應的節點紀錄在 begin 陣列，將 right 和 left 佇列的尾節點指標以及 pivot 對應的節點紀錄在end。

其目的在於將原先的佇列分個成三個區塊，且保證左邊的佇列中所有節點數值必大於右邊的佇列中所有節點數值。

before = {2, 4, 7}
after = {1, 4, 5}

接著藉由提取 begin 和 end 紀錄的每個佇列之頭尾，將各個佇列進行迭代。

before = {2, 4, 5, 7, NULL}
after = {1, 4, 5, 7, NULL}

L 和 R 負責在每一次迭代開始分別指向佇列的頭和尾。如果 L == R 代表此佇列只有一個元素或為空佇列，無須再進行排列。

除非 L 現在是指向空指標，否則此時便可將此元素從頭插入 result佇列中。

經過四次迭代後，此時 result 佇列已插入 3 個元素。

接著完成其餘佇列：

// The accessed element are not removed
before = {1, 2, 3, 7, NULL}
after = {1, 2, 3, 7, NULL}

再經過 3 次迭代後，排列完成。

利用 Linux Kernel API 改寫

在觀察題目的程式碼時，發現 node_t 中有 node_t *left 和 node_t *right ，但在原先的程式碼中完全沒有被用到。原本的left 和 right 陣列更新和維護與 list.h 中的 list_head 結構體有相似處。

於是我將 node_t 中有 node_t *left 和 node_t *right 修改成 struct list_head stack

會命名為 stack 是因為 begin 和 end 陣列原本的功能是紀錄各個子佇列的頭尾，如果是遞迴方式來作 quick sort, 此部份的工作會是由 stack 來完成。故此命名。

typedef struct __node {
  struct list_head stack;
  struct __node *next;
  long value;
} node_t;

在作者提出的非遞迴式遞迴中，最明顯的問題就是陣列 begin 和 end 的大小問題，測驗中的程式碼將其設定為初始佇列的兩倍大。

雖然這個設定本身就過大（因為在作者的 quick sort 方法中，最差情況只會用到初始佇列本身的大小），但即使將陣列的大小縮小，其中的空間大部分時間都是閒置的。如果可以透過其他資料結構來替換大小固定的陣列，就能提高空間之利用度。

以上的評估，將陣列 begin 和 end 換成以鏈結串列紀錄確實能夠改善此問題。

原本的一次迭代中，在判別佇列是否不為空佇列或一個元素的佇列，是透過 if (L != R) 判別。但在程式碼修改後，已經保證不會有空佇列的存在，所以我直接將此條件判別改成 if(p->next), 並且直接刪去 L 和 R 變數。

 while (i >= 0) {
    pivot = list_entry(pivot_ptr, node_t, stack);
    if (pivot->next) {

---

在原先更新陣列 begin 和 end 部份，因為已將 L 和 R 變數刪除，所以 end 陣列也失去其功能，只須紀錄所有佇列之頭節點即可。透過 list.h 中的 list_add 和 list_add_tail 分別將 right 和 left 佇列的頭節點之 stack 和 pivot 作鏈結。

while (p) {
  node_t *n = p;
  p = p->next;
  linkedlist_add(n->value > value ? &right : &left, n);
}
if (left) {
  list_add_tail(&(left->stack), &(pivot->stack));
  i++;
}
if (right) {
  list_add(&(right->stack), &(pivot->stack));
  i++;
  pivot_ptr = pivot_ptr->next;
}

值得注意的是，我將更新下一次迭代所要使用到的 pivot 放在 if(right) 判別裡面，

用運用原理的例子中，第二次迭代的狀態觀察：

before = {2, 4, 5, 7, NULL}
after = {1, 4, 5, 7, NULL}

pivot 為 7 ，且比大小後 right 並沒有元素，如果在原本使用陣列紀錄各佇列之頭尾時，下次迭代的 L 和 R 皆為 NULL 。然而，在利用 list_head 結構中，不存在 NULL 元素，如果 right 本身為空佇列，則下次迭代的 pivot 就會是此次的 pivot , 也就是維持在 7。
commit: 860c91a

---

當 pivot 為單元素佇列，則移除 pivot 與其他佇列頭節點的鏈結，並將 pivot 插入 result 鏈結串列中。

pivot_ptr = pivot_ptr->prev;
list_del_init(&(pivot->stack));
linkedlist_add(&result, pivot);

測驗2

運作原理

Timsort 旨在從串列中尋找部份已排序好之連續單調遞增子串列，將各個已排序子串列合併，來加速串列之排序。

在 find_run 函式中，尋找串列中連續單調遞增的子串列（如果是單調遞減的子串列，則會在在遍歷過程中反轉整個串列，使其成為單調遞增串列），將其串列頭存在 receive.head 中，其餘串列的頭存在 receive.next ，並且於 head->next->prev 中存放此連續單調遞增子串列之節點總數。

merge_collapse 檢查tp 頂端的 3 個 run 是否符合條件，

• tp->prev->prev 長度大於 tp->prev 長度+ tp 長度
• tp->prev 長度 大於 tp 長度

如果不符合，就需要選擇執行 tp->prev->prev +tp->prev 或是 tp->prev + tp ，以維持 stack 中子串列長度的平衡。

直到串列所有的節點都被分段放入 stack 後，透過 merge_force_collapse 將所有 run 合併成為兩個以下的子串列。

/* 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 <= ????) {
  build_prev_link(head, head, stk0);
  return;
}
merge_final(priv, cmp, head, stk1, stk0);

此程式碼中的 ???? 空缺答案為 1 ，此條件判別的目的是如果 stack 中已經合併到只剩下一個串列，則不需要再呼叫合併函式，只須將 singular linked list 轉換回 doubled linked list 。否則，就會進到最後一次合併，並且在 merge_final 中完成linked list 轉換。

疑問：為什麼要將 len 強制轉型成 struct list_head* 並且儲存在 head->next->prev ?

size_t len = 1;
head->next->prev = (struct list_head *) len;

2024q1 第 2 週測驗題

測驗 1

運作原理

撰寫測試程式

在測驗中的程式碼只給定實作 preorder 和 inorder 轉換成一棵二元樹的相關函式。我將測驗中的程式碼放在 preorder_inorder.c 和 preorder_inorder.h 中，並新增 main.c 作為測試程式。

驗證產生的二元樹是否正確的方式為以 inorder 和 preorder traverse 的方式遍歷二元樹中的節點，將每個節點與傳入的 inorder / preorder array 中的元素順序作比較。

check_preorder 依照 preorder 的遍歷順序，透過遞迴依序從目標節點，左子點，右子點確認其順序是否和陣列中數列的順序相同。值得提起的是，因為是遞迴式，一方面要兼顧回傳順序是否錯誤的訊息，也要隨著訪問子節點去更新 index 。所以當函式回傳為自然數，不僅表示此分支的節點順序正確，此數值也代表目前比對到陣列中的那一個數的 index 。

int check_preorder(struct TreeNode *test, int *preorder, int idx,
                   int pre_size) {
  if (!test)
    return idx - 1;
  int newidx = idx;
  if (test->val == preorder[idx]) {
    if ((newidx = check_preorder(test->left, preorder, idx + 1, pre_size)) >=
        0) {
      if ((newidx = check_preorder(test->right, preorder, newidx + 1,
                                   pre_size)) >= 0) {
        return (newidx < pre_size) ? newidx : -1;
      } else {
        return -1;
      }
    } else {
      return -1;
    }
  } else {
    return -1;
  }
}

check_inorder 也是類似的概念，透過遞迴依序從左子點，目標節點，右子點確認其順序是否和陣列中數列的順序相同。

if (!test)
    return idx;
  if ((idx = check_inorder(test->left, inorder, idx, in_size)) >= 0) {
    if (test->val == inorder[idx]) {
      if ((idx = check_inorder(test->right, inorder, idx + 1, in_size)) >= 0) {
        return (idx <= in_size) ? idx : -1;
...

測驗 2

運作原理

在原本的 LRU 運作機制上增加 hash table 來減少搜尋資料的時間。在沒有引入 hlist 時，資料只儲存在 dhead 的佇列之中，這導致每一次搜尋資料是否存在於快取中的時間複雜度為

$O(n)$。如果建立一個 hash table 將節點存放其中，並且搭配一個適當的 hash function 使每一個節點對應到的 index 分佈足夠分散，最理想情況可以將搜尋資料時間複雜度降為

$O(1)$ 。

LRUCache 結構體
包含紀錄節點最大存放數量 capacity 、快取目前存放節點數量 count 、資料結構體存放之佇列 struct list_head dhead 、資料結構體存放之哈希表 struct hlist_head hhead[] 。

快取寫入 (lRUCachePut)
函式的參數為快取之指標 LRUCache* obj 、欲寫入之資料的鍵值 int key 、欲寫入之資料 int value 。

首先搜尋檢查資料之鍵值是否已經在快取中，將 key 計算出對應的哈西表索引值。從哈希表陣列對應索引值之佇列（例如：hhead[0] ) 線性搜尋，看資料之鍵值是否已經存在。

如果此鍵值已存在快取中，將其節點從 dhead 佇列中移到最前面，以更新此節點在快取中被讀寫的新舊程度。

如果此鍵值未存在快取中，須新增新節點於快取中。由於快取有最大存量之限制，如快取已達最大量，須先刪除當前最久未被讀寫之節點。再將欲新增之鍵值節點新增到對應的 hlist 以及 dhead 的頭。

最後確定鍵值對應的節點位於 dhead 的最前頭，再更新其節點中的數值 value 。

快取讀取（lRUCacheGet)
函式的參數為快取之指標 LRUCache* obj 、欲讀取之資料的鍵值 int key。

搜尋檢查資料之鍵值是否已經在快取中，將 key 計算出對應的哈西表索引值。從哈希表陣列對應索引值之佇列（例如：hhead[0] ) 線性搜尋，如果資料之鍵值存在，則回傳此節點中的數值 value ，否則傳 -1 。

觀察實作

測驗 3

運作原理

#define GENMASK(h, l) \
    (((~0UL) - (1UL << (l)) + 1) & (~0UL >> (BITS_PER_LONG - 1 - (h))))

GENMASK 是一個將 h 和 l 設為 1 的位元遮罩。
-0UL 是將一個 long 型別長度的 0 取反，在此情況就是表示一個全 1 的 64 位元的二進位數字。1UL << (l) 是將 1 左移 l 位的二進位數字。(~0UL) - (1UL << (l)) + 1) 是一個從 l 到最高位皆為 1 的二進位數字。
(~0UL >> (BITS_PER_LONG - 1 - (h))) 則是將一個全 1 的 64 位元的二進位數字右移 (BITS_PER_LONG - 1 - (h) 位，產生一個從最低位到 h+1 位皆為 1 的二進位數字。

將這兩個遮罩 & 在一起， GENMASK（h, l) 是一個 第 h ~ l 為 1 的位元遮罩。

#define __const_hweight8(w) \
    ((unsigned int) ((!!((w) & (1ULL << 0))) + (!!((w) & (1ULL << 1))) + \
                     (!!((w) & (1ULL << 2))) + (!!((w) & (1ULL << 3))) + \
                     (!!((w) & (1ULL << 4))) + (!!((w) & (1ULL << 5))) + \
                     (!!((w) & (1ULL << 6))) + (!!((w) & (1ULL << 7)))))

__const_hweight8(w) 的功能為計算 8 位元整數 w 中被設置為 1 的位元數。
!!(w) & (1ULL << 0) 為判定 w 中的第 0 位是否為 1 。!! 確保結果是 0 或 1 。
再將 8 位的所有判定結果相加，得出最終結果。