# Linux 核心專題: 針對共用程式碼的測試模組
> 執行人: 164253
> [專題解說影片](?)

由於我現在人在中國，拿不到程式碼，底下簡述內容。

## 任務簡介
Linux 核心原始程式碼中，[lib 目錄](https://github.com/torvalds/linux/tree/master/lib)定位於可共用的程式碼，但其品質卻沒有充分被檢驗，更缺乏完整的測試。本任務嘗試針對其中部分程式碼，建立對應的 Linux 核心測試模組。留意量化 (comparison, memory acess, locality) 分析。

## TODO: 改進資料排序的測試
> 改善現有 lib 目錄下，sort 相關程式碼的測試模組，善用 KUnit。

原先的 `test_sort.c` 中沒有測試排序的穩定性，新增一個結構紀錄原本的順序。
並且使用最差情況的資料做排序，原本的 PRNG 並不是最差情況。
為了方便的生成資料，指定 TEST_LEN 是二的冪，且排序後的結果是遞減的。

struct pair{
    int val;
    int order;
}

static void test_sort(struct kunit *test)
{
    //some initial
    //pair a[TEST_LEN];
    for (int i = 0; i < TEST_LEN; ++i) {
        a[i]->val = 0;
        a[i]->order = i;
    }
    sort(a, TEST_LEN, sizeof(*a), cmppair, NULL);
    for (int i = 1; i < TEST_LEN; ++i) { //test stable or not
        KUNIT_ASSERT_GE(test, a[i - 1]->val, a[i]->val);
        KUNIT_ASSERT_LT(test, a[i - 1]->order, a[i]->order);
    }
    
    a[0]->val = TEST_LEN;
    int val = TEST_LEN;
    for (int jump_gap = TEST_LEN; jump_gap; jump_gap>>=1)
        for (int pos = jump_gap>>1; pos < TEST_LEN; pos += jump_gap)
            a[pos]->val = --val;
    //check list is sorted as previous test and caculate time
}

計時相關的程式碼目前手邊沒有，大致是透過 Timer 設定一秒的 timeout ，若超過則代表排序不是 $O(n\log n)$ 的複雜度，或者是常數過大。
每次測試後會輸出不同資料分佈下的實際耗時，以便未來改進 `sort.c` 時能給出更精準的資料，以說明平均、最佳、最差狀況下具體的速度差異。

其中最差情況的資料生成方式有許多種，如同我在 [2024-3-{19,21} 課程問答簡記](https://hackmd.io/3e8LI8_0SLOo_UTDAnPKYQ?view#164253) 給出的，前三種構造法需要已排序的資料或 `next_permutation` 等，第四種則需要遞迴呼叫函式，會有額外的開銷，基於我們只需要資料分佈會是最差狀況就好，直接將內容設定為 $1\sim \text{TEST_LEN}$ 。
可以觀察到每次合併時最大值與次大值在左右兩半，再往下遞迴時也是，當 TEST_LEN 是二的冪時，每次合併的最大值出現的位置即是 $(0,\frac n2),(\frac n4,\frac{3n}4),(\frac n8,\frac{3n}8,\frac{5n}8,\frac{7n}8)$ ，去掉 $0$ 比較特殊要額外處理以外，每次最大值之間的間距減半，起始位置是間距的一半，便可寫出上面的生成方式。

## TODO: 改進紅黑樹的測試
> 引入 threaded rbtree，可以 O(1)。找到前後一個節點，再之後可以視情況加入 morris traversal。

此段程式皆不在手邊，也有部分是還沒寫出來，底下以證明和改進內容之演算法說明為主。

在 linux 的紅黑樹中用了 `__attribute__((aligned(sizeof(long))))` 指定對齊，讓指向親代的最低兩個位元不會被使用到，便可將自身的顏色放在這之中一併儲存。
同理的，指向左右子節點的指標也可利用，在實際用到之前，先介紹[線索化(Threading)](https://en.m.wikipedia.org/wiki/Threaded_binary_tree) 。

在樹上取值時，需要的資料通常是點的值或邊的值，對於邊相關的情況，可以用輕重鏈剖分，或者特化的長鏈剖分，更複雜的情況可以用 link cut tree 。
而點相關分為對點區間跟單個點取答案，後者是前者的特化，但可以有更多的技巧處理問題。

線索化則是建立在同時有單點操作和區間操作上的情況，考慮到一棵樹有 $2n$ 個指向子節點的指標，但一棵樹只有 $n-1$ 條邊，因此會有 $n+1$ 個指標指向空節點的問題，可以利用他們紀錄中序走訪下前後節點的資料。
當左節點或右節點是空的時，改紀錄上一個或下一個節點，並用最低的兩個位元標記，表示這個節點並不是他實際上的孩子。

當加上這些資料後，忽略顏色和親代節點的關係，會發現這時候變成了一個雙向 linked list ，便能做到 $O(1)$ 找到前、後一個節點，對於需要走訪全部 $n$ 個節點的情況能把複雜度從 $O(n\log n)$ 降到 $O(n)$ 。

Morris traversal 指的是 Morris 寫的論文 "Traversing Binary Trees Simply and Cheaply" 給出的遍歷方法，使用遍歷而不是走訪是因為這個演算法是真的走過所有節點，按照前序、中序、後序三種方法有不同的實作， [fennecJ](https://hackmd.io/@fennecJ/Invert_bin_tree) 曾經寫過一次，可以做到不用遞迴呼叫和 stack 就能 $O(n)$ 遍歷，在線索化後可以方便的實現。

## TODO: 研究 `lib/sort.c` 說明近期的改進
> 參照以下:
> * https://www.facebook.com/groups/system.software2024/posts/1617016709076221/
> * https://www.facebook.com/groups/system.software2024/posts/1617008692410356/
> * https://www.facebook.com/groups/system.software2024/posts/1631381294306429/
> 尋找更多改進空間

由於 userspace 下本來就會自動排程，第一筆改進刪除了不必要的重新排程的呼叫。
第二筆則是改進在元素數量極少的狀況下直接插入排序會比分治快的問題，和 c++ std::sort 使用 intro sort 一樣。
第三筆修正了原本的排序會將不需要的資料標記起來，卻造成預期外的錯誤比較，造成結果不正確。