# 2025q1 Homework1 (ideas)
contributed by < [`charliechiou`](https://github.com/charliechiou?tab=repositories) >

## [針對鏈結串列的資料排序改進](https://hackmd.io/@sysprog/BJPBcQ34C)

目標 : 嘗試引入 Timsort 及其延伸的演算法並與 listsort 比較。

初步閱讀這份期末專題，以下是目前的疑惑
- Timsort 實做方法及延伸演算法
- 龐大的 linux kernel程式碼應該如何去找出改動程式碼時候會影響到的內容
- 如何編譯及測試 linux kernel 中的程式碼並改良內部的程式
- 比較排序演算法時需要分析的參數

### Timsort 演算法

先將需要排序的資料整個掃過一遍，並將單調遞增/遞減的資料視為一個 run 並依照需求先把每個 run 排序好再合併，而每個 run 之間的資料透過 stack 維持。

> 疑惑 :
> - 若需要排序的資料極大，先掃描過一次不會降低效率嗎 ?
> - 為何使用 stack ?
>
> 想法 :
> - Timsort 演算法的時間複雜度為 O(nlogn) ，這樣的掃描僅花費 O(n) 因此不會特別降低效率，且這部份的掃描能夠大幅減少後面所需要的時間。
> - stack 有後進先出的特性(LIFO)，合併需要存取最上面的幾個數值因此可以有效減少需要的時間

每次合併時會合併兩個 run ，因此 run 總數略大於 2 的冪時效率會特別低 (資料不平衡)，為了改善平衡問題，因此長度不足於 minrun 的兩個 runs 會做兩兩合併，常見的 minrun 會設定為 64。

前述的 minrun 設定作者解釋為是由於 64 可以一次放入 cache line，但這邊是針對鍊結串列 (Linked-list) 所作的操作，因此不一定是設定為 64，是可以在探討及測試的部份。

### adaptive_shiversSort

這部份是針對合併 minrun 所作的改良，若目前 stack 上的 run 為 X,Y,Z 且 Z 為 top ，如果
$$
\left\lfloor \log_2 X \right\rfloor \leq \left\lfloor \log_2 (\max(Y, Z)) \right\rfloor
$$
則合併 X,Y。可以很簡單的透過 clz 來實做 $log_2$ 的計算。

> 疑問：
> - clz 如何很簡單的計算 $log_2$ ?
>
> 解答：
> - 二進位中一個數字可以表示為
> $$
> N = b_k 2^k + b_{k-1} 2^{k-1} + \dots + b_1 2^1 +
> $$
> 因此 $2^k$ 的 $log_2$ 會直接和最高位1的索引值對應

### Powersort
(To be done)

### 資料蒐集
作者先透過搜尋找出 linux_kernel 中有使用到 list_sort 的部份，再查看那些 function 後找到可以在使用者層級使用的命令，因此從這部份著手比較方便查看結果。

> 可以將這種方法作為改善 linux kernel 程式碼的切入點

接著使用 [virtme-ng](https://github.com/arighi/virtme-ng) 的虛擬環境來進行實驗。透過修改 list_sort 使他在被呼叫時會留下對應的紀錄，並透過 list_sort 的 kernel 版本編譯出對應的 perf tools。

> 是否這邊可以有類似 gdb 的方式來查看修改結果或呼叫結果而不用在程式碼安插一個 print ?

並透過自己撰寫的 kernel module 呼叫 list_sort 並檢視輸出
> 什麼是 kernel module 又是如何撰寫的 ?
> 參考 [Linux 核心模組運作原理](/pfRzP9sxRYqYbXS6Tm0Ynw)，kernel module 是一個可以載入 (load) 及卸除 (unload) 到核心的模組，詳細的使用辦法參考前述的連結。

[    0.672210] virtme-ng-init: initialization done
[   30.108569] list_sort_module: loading out-of-tree module taints kernel.
[   30.108752] List before sorting:
[   30.108754] Value: 9
[   30.108755] Value: 8
[   30.108755] Value: 7
[   30.108756] Value: 6
[   30.108757] Value: 5
[   30.108757] Value: 4
[   30.108758] Value: 3
[   30.108758] Value: 2
[   30.108759] Value: 1
[   30.108759] Value: 0
[   30.108760] Hello from list_sort
[   30.108761] List after sorting:
[   30.108762] Value: 0
[   30.108762] Value: 1
[   30.108763] Value: 2
[   30.108763] Value: 3
[   30.108764] Value: 4
[   30.108764] Value: 5
[   30.108765] Value: 6
[   30.108766] Value: 7
[   30.108766] Value: 8
[   30.108767] Value: 9

接著便嘗試使用 perf 呼叫 list_sort ， 這部份會需要重新編譯 `libtraceevent` 因此在 vng 為系統安裝 `libtraceevent`

> libtraceevent 是 perf 依賴的 library

隨後找到正確會調用到 list_sort 的部份再參考 `metric_list_cmp` 如何將 metric_list 中要排序的資料解析出來撰寫 `dump_metric_list_ele` 將資料解析出來。

> 和先前有一樣的疑惑，是否可以透過類似 gdb 的方法省去這步驟

再接著透過 [stress-ng](https://github.com/ColinIanKing/stress-ng) 來進行壓力測試，可以測試 GPU 滿載情況的效能。但 perf 在呼叫到 list_sort 時候只依照輸入的 matric list 順序進行排序，和最後的結果，因此會是固定的資料分佈無法用作測試。

接著測試檔案系統為 ext4 的隨身碟，再透過自己撰寫的程式讓使用者輸入 ext4 裝置路徑並回傳 fsmap 內容。

> 疑問:
> - ext4檔案是怎樣的檔案類型？
>
> 解答：
> - ext4(fourth extended filesystem)：[wiki](https://en.wikipedia.org/wiki/Ext4)

並透過編譯好的程式來查看目錄，但為了取得資料分佈，必須修改kernel。由於虛擬機器的檔案系統會變為 tmpfs 因此需要直接編譯完整的 kernel 直接執行。

### 編譯 linux kernel

先下載需要的套件後，將原先電腦的 config 那來使用做為驅動的設定，再透過 make 安裝所需的 modules。重新啟動後在 grub 中選擇剛剛的 kernel 即可。

> 從這邊可以更深刻的了解到 linux 作為作業系統的存在

用類似的方式取得 XFS 的資料後便可以開始進行 sorting 的實驗。

### 整合 Timsort及改進至 Linux 核心

作者透過 linux 中的 module 來方便的完成實做，將 list_sort 等相關算法寫成 module 後再透過 `EXPORT_SYMBOL` 來導出。

> 這部份我的理解是透過 linux 中的 module 可以把寫在不同區域的 function 打包，只要打包的 function 是在核心中運作便可以方便的使用它。

接著透過 `insmod` 將編譯好的 module 載入。

### 實驗

實驗紀錄對同一筆資料集排序數次後的時間加總，透過 ktime_get 取得經過的時間。且為了避免 `interrupt` 以及 `preemption` 對實驗造成影響，因此作者也透過以下指令關閉

local_irq_disable(); // disable local interrupt
get_cpu();           // disable preemption
// Experiments
local_irq_enable();  // enable local interrupt
put_cpu();           // enable preemption

主要測試以下幾項

- ext4 檔案系統的 ext4_getfsmap
- btrfs 檔案系統的 extent_list
- 透過 perf stat -M 照順序輸入所有 metric 的 perf_metric_list
- xfs 檔案系統的 `xfs_buf_delwri_submit_buffers`, `xlog_cil_push_work`, `xfs_trans_run_precommits` 以及 `xfs_extent_busy_sort`

在 ex4 及 btrfs 的測試中可以了解到 Timsort 對於 ex4 的表現並不會比原先的 list_sort 較為優異，但在 btrfs 則會有更好的結果。

> 過去在做其他實驗測量程式執行時間時，常會受到環境中其他因素影響，是否有可以像是 dudect 類似的方法可以更公正的測量程式碼執行時間?

而在 perf stat -M 的實驗測試中雖然 Timsort 比較次數較多，但執行時間則較少。

> 是否可能就是上述的所說環境中其他因素影響？

而最後也用同樣方法測量 xfs 檔案系統，在部份的結果中 Timsort 也都取得優異的表現。

> 思考可以改善的方式，是否可以讓 Timsort 在第一次掃描全部資料時若分佈不如預期，就使用原先的 list_sort 來排序？

## [位元運算的應用](https://hackmd.io/@sysprog/rkt-cdRrC)

目標 : 解析[第七週測驗題](https://hackmd.io/@sysprog/linux2024-quiz7) 測驗 1, 2 及[第九週測驗題](https://hackmd.io/@sysprog/linux2024-quiz9) 測驗 3

### 第七週測驗題 測驗 1

:::success
#### 延伸問題1.
解釋上述程式碼運作原理
:::

首先先介紹如何判斷一個數是否為奇術，`bool odd(uint32_t x){return x & 1}`，為減少運算量，我們可以將兩個 32 位元合併為 64 位元並用特殊的位元遮罩做計算，此時可以寫成

static inline uint64_t bit_compound(uint32_t x, uint32_t y)
{
    return ((0L + x) << 32) | ((y + 0L) & (-1L >> 32));
}

作者這邊提出 `& (-1L >> 32))` 應該是不必要的操作。

>在規格書中 6.1.3.8 Usual arithmetic conversions 有提到型別在位移時會自動轉換，因此我認為這邊應該也可以不需要額外的 0L 操作
>> Many operators that expect operands of arithmetic type cause conversions and yield result types in a similar way. The purpose is to determine a common real type for the operands and result. For the specified operands, each operand is converted, without change of type domain, to a type whose corresponding real type is the common real type.

接著查看 Linux 核心中的 [lib/string.c](https://github.com/torvalds/linux/blob/master/lib/string.c) 中 [memchr](https://man7.org/linux/man-pages/man3/memchr.3.html) 實作用來在記憶體區塊 str 中搜尋字元 c：

/**
 * memchr - Find a character in an area of memory.
 * @s: The memory area
 * @c: The byte to search for
 * @n: The size of the area.
 *
 * returns the address of the first occurrence of @c, or %NULL
 * if @c is not found
 */
void *memchr(const void *s, int c, size_t n)
{
    const unsigned char *p = s;
    while (n-- != 0) {
        if ((unsigned char)c == *p++) {
            return (void *)(p - 1);
        }
    }
    return NULL;
}

而透過 [SIMD within a register (SWAR)](https://en.wikipedia.org/wiki/SWAR) 的技巧，我們可改寫為以下 memchr_opt 函式:

#include <limits.h>
#include <stddef.h>
#include <stdint.h>
#include <string.h>

/* Nonzero if X is not aligned on a "long" boundary */
#define UNALIGNED(X) ((long) X & (sizeof(long) - 1))

/* How many bytes are loaded each iteration of the word copy loop */
#define LBLOCKSIZE (sizeof(long))

/* Threshhold for punting to the bytewise iterator */
#define TOO_SMALL(LEN) ((LEN) < LBLOCKSIZE)

#if LONG_MAX == 2147483647L
#define DETECT_NULL(X) (((X) - (0x01010101)) & ~(X) & (0x80808080))
#else
#if LONG_MAX == 9223372036854775807L
/* Nonzero if X (a long int) contains a NULL byte. */
#define DETECT_NULL(X) \
    (((X) - (0x0101010101010101)) & ~(X) & (0x8080808080808080))
#else
#error long int is not a 32bit or 64bit type.
#endif
#endif

/* @return nonzero if (long)X contains the byte used to fill MASK. */
#define DETECT_CHAR(X, mask) DETECT_NULL(AAAA)

void *memchr_opt(const void *str, int c, size_t len)
{
    const unsigned char *src = (const unsigned char *) str;
    unsigned char d = c;

    while (UNALIGNED(src)) {
        if (!len--)
            return NULL;
        if (*src == d)
            return (void *) src;
        src++;
    }

    if (!TOO_SMALL(len)) {
        /* If we get this far, len is large and src is word-aligned. */

        /* The fast code reads the source one word at a time and only performs
         * a bytewise search on word-sized segments if they contain the search
         * character. This is detected by XORing the word-sized segment with a
         * word-sized block of the search character, and then checking for the
         * presence of NULL in the result.
         */
        unsigned long *asrc = (unsigned long *) src;
        unsigned long mask = d << 8 | d;
        mask |= mask << 16;
        for (unsigned int i = 32; i < LBLOCKSIZE * 8; i <<= 1)
            mask |= mask << i;

        while (len >= LBLOCKSIZE) {
            if (DETECT_CHAR(CCCC, mask))
                break;
            asrc++;
            len -= LBLOCKSIZE;
        }

        /* If there are fewer than LBLOCKSIZE characters left, then we resort to
         * the bytewise loop.
         */
        src = (unsigned char *) asrc;
    }

    while (len--) {
        if (*src == d)
            return (void *) src;
        src++;
    }

    return NULL;
}

接著照作者的寫法逐步分析程式碼的原理

首先第一個迴圈使用到 UNALIGNED(src) 來確定是否有對齊記憶體

/* Nonzero if X is not aligned on a "long" boundary */
#define UNALIGNED(X) ((long) X & (sizeof(long) - 1))

> 這部份不太能理解作者的解釋，因此又自己查閱其原理。
> long 所佔據的大小為 8 因此這行表示只要 x 和 7 (i.e., 0b0111) 去做 AND 運算便可確定是否未對齊。以 x = 0x1002 為例，0x1002 & 0x7 == 2 未對齊，相當於確認 x 是否為 8 的倍數(i.e., 第三位底下是否都是 0)

進到迴圈後判斷

- 第一個判別式用以判斷 len 是否為 0，若為 0 則表所有字元已經掃描過一輪，而隨著每次檢查會將其值遞減，直至迴圈條件不成立。
- 第二個判別式用以判斷當前 src 所指向字元與欲搜尋之字元 d 是否匹配。
- 最後將 src 改指向下一個字元所在位址，直到位址值符合對齊條件。

接著進到第二個條件判斷，首先判斷 `if (!TOO_SMALL(len))` 當輸入字串長度 ≥ 8 時，判別式條件成立，並強制轉型 `unsigned long *asrc = (unsigned long *) src;`。

接著透過 `or` 及左移運算，使變數 mask 為欲搜尋字元 d 的重覆擴展（擴展次數會因不同機器上的 `long` 型別位元數而有所不同）。

unsigned long mask = d << 8 | d;
mask |= mask << 16;
for (unsigned int i = 32; i < LBLOCKSIZE * 8; i <<= 1)
    mask |= mask << i;

接著使用 DETECT_CHAR 及 DETECT_NULL 來檢測 c 是否出現在字串中

#define DETECT_CHAR(X, mask) DETECT_NULL((X) ^ (mask))

由於 mask 是由 c 重複擴展的 mask 因此可以先用 `^` 來確認是否有出現 c 這個字元，相同的部份則設成 0x00 再由 DETECT_NULL 來確認是否有 0x00 的存在。

接著查看 DETECT_NULL 的使用

#if LONG_MAX == 2147483647L
#define DETECT_NULL(X) (((X) - (0x01010101)) & ~(X) & (0x80808080))
#else
#if LONG_MAX == 9223372036854775807L
/* Nonzero if X (a long int) contains a NULL byte. */
#define DETECT_NULL(X) \
    (((X) - (0x0101010101010101)) & ~(X) & (0x8080808080808080))
#else
#error long int is not a 32bit or 64bit type.
#endif
#endif

若系統為 32 位元則使用第二行來偵測是否有出現 NULL，若 64 位元則使用第七行，若接非則用第 9 行跳出。

以 32 位元為例，首先 x 與 0x01010101 相減，若其中某個段落為 0x00 則會變為 0xFF。接著再和 x 的取反便可留下 0x00 出現的位置 (其他不是 0x00 的部份和自己的 not 做運算會變成 0x00)， 最後再和 0x80808080 做 AND 便可識別出出現 NULL 的位置。

:::success
#### 延伸問題2.
比較 Linux 核心原本 (與平台無關) 的實作和 memchr_opt，設計實驗來觀察隨著字串長度和特定 pattern 變化的效能影響
:::

這部份作者僅討論要如何選定資料長度來當作樣本，並列舉出實驗所需要的數據大小，並未進行實驗，因此是可以做改進的地方。

:::success
#### 延伸問題 3.
研讀 [2022 年學生報告](https://hackmd.io/@arthur-chang/linux2022-quiz8)，在 Linux 核心原始程式碼找出 x86_64 或 arm64 對應的最佳化實作，跟上述程式碼比較，並嘗試舉出其中的策略和分析
> 下一步：貢獻程式碼到 Linux 核心
> [Phoronix 報導](https://www.phoronix.com/news/Linux-Kernel-Faster-memchr)
:::

同樣這個延伸問題並未完成，但也讓我好奇 linux 對於不同的硬體設備是否皆會做相對應的優化，又或者 linux 核心如何適應各種不同的硬體設備的?

### 第七週測驗題 測驗 2
### 第九週測驗題 測驗 3

## [虛擬攝影機裝置](https://hackmd.io/@sysprog/HJBxRsRr0)

## [重做 lab0](https://hackmd.io/@sysprog/Syc7ROemA)

## [CPU 排程器](https://hackmd.io/@sysprog/BJdyxvxX0)

## [vcam 研究](https://hackmd.io/@sysprog/ByzkF6xDA)

## [虛擬攝影機裝置驅動程式](https://hackmd.io/@sysprog/S1l3ZlcLA)