# 2025q1 Homework1 (ideas)
contributed by < `rota1001` >
{%hackmd NrmQUGbRQWemgwPfhzXj6g %}
## [Linux 核心專題: 針對鏈結串列的資料排序改進](https://hackmd.io/@sysprog/BJPBcQ34C) - `fennecJ`
這個專題是要引進 Timsort 以改良 linux 中的 `list_sort`，並以實驗說明其好處。
### Timsort
此演算法的前提是現實世界中的大部分資料都是部份排序的，所以將部份排序良好的陣列合併成一塊一塊（runs），最後將他們合併。
原始的版本是在陣列上，會決定一個 `minrun` ，代表一個 run 最小的長度。從陣列的開頭開始蒐集元素組成 run，選取連續遞增或嚴格遞減的元素連起來，如果他的長度小於 `minrun` 就用插入排序法將後面的元素插到 run 裡面。`minrun` 通常選 64，因為它可以放進 cacheline 中，讓插入排序法效益較高。然後它可以二分搜應該插入的位置，這樣雖然插入還是需要 $n$ 個操作去移動元素，但比較只需要 $\log n$。接下來進行合併，每次將一個 run 加入到堆疊的頂部，持續的檢查頂部的 4 個元素，$A$、$B$、$C$、$D$（長度），滿足底下的性質（若只有 3 個元素只要比較第 2 條，若只有 2 個元素就只比較第 3 條，這是基於看[程式碼](https://github.com/yanjiew1/linux23q1-timsort/blob/main/timsort.c)的理解）：
- $A > B+C$
- $B > C+D$
- $C > D$
這裡如果是只有 3 個的話在符號上就會是 $B$、$C$、$D$
如果不滿足任何一條的話，那 $C$ 就和 $B$ 或 $D$ 中較小的合併，一直做到滿足以上性質。
如果插入一個處理到滿足性質後，就會接著插入另一個 run，直到所有 run 都插入完成。這個時候整條序列會滿足至少以費式的增長速度遞增，再從堆疊頂部開始一路合併到堆疊底部。
這裡使用[Timsort 研究與對 Linux 核心貢獻嘗試](https://hackmd.io/@yanjiew/linux2023q1-timsort#Timsort-%E7%9A%84%E4%BF%AE%E6%AD%A3%E7%89%88)的例子來解釋：
```graphviz
digraph structs {
node [shape=record];
rankdir=LR;
y1 [label="E|D|C|B|A"]
y2 [label="E|DC|B|A"]
y3 [label="EDC|B|A"]
y4 [label="EDCB|A"]
y5 [label="EDCBA"]
x1 [label="30|20|25|80|120"]
x2 [label="30|45|80|120"]
x3 [label="75|80|120"]
x4 [label="155|120"]
x5 [label="275"]
x1->x2->x3->x4->x5;
y1->y2->y3->y4->y5;
}
```
### Adaptive ShiversSort
這是 Timsort 的一種改良，將堆疊的性質檢查做修改，對於每次插入 run 時，頂部的 3 個元素 $A$、$B$、$C$，滿足：
- $\lfloor\log_2A\rfloor>\lfloor\log_2(max(B,C))\rfloor$
- $B > C$
否則將 $A$、$B$ 合併。這樣讓從堆疊頂部開始保證以 2 的羃遞增。
### Powersort
這也是對於 Timsort 合併時的改良。前述的方式可以歸納為保證從堆疊頂部開始的某種指數的增長，然而這會造成一些情況上不平衡的合併（差距很大的 run 互相合併）。Powersort 的概念是去貼近 top-down merge sort 對於陣列的切割。
在 [COMP526 (Fall 2023) 3-6 §3.6 Python's sorting method & Powersort 的 12:47](https://youtu.be/exbuZQpWkQ0?t=767) 可以看到一個圖，這個圖是代表在進行 top-down merge sort 時會去進行的切割，編號為 1 的將陣列切成 2 塊，編號為 2 的將陣列切成 4 塊，編號為 3 的將陣列切成 8 塊。接下來，對於兩個 runs 來說，他們的中點所為成的區間蓋住的編號中最大的數字就是這兩個 runs 中間的那個縫隙的 power。對於每個 run 來說，他的 power 就是它左邊的縫隙的 power，如果是第 0 個 runs 的話，那他的 power 就是 0。合併方式是這樣的，每次新增 run，對於堆疊頂部的 $A$、$B$，滿足：
$power_A<power_B$
這裡想到一種用機率的觀點來直觀的思考 powersort。首先，一個固定長度的區間，蓋住一個編號較大的切割是比蓋住一個編號較小的切割機率更大的，而且由分佈密度來看的話機率相對於編號的遞增是指數遞減的，另外，區間長度越長所能蓋住某個特定的切割的機率更大，而且這個機率是線性遞增的。換句話說，如果某個區間蓋住了某個切割，那相對於這個切割的編號，這個區間的長度的期望是指數遞增的。所以這個縫隙數字為 $k$ 的意思代表期望上這兩個 run 合併後的大小是 $\frac{n}{2^{i-1}}$，帶入 top-down merge sort 的結果也可以發現到它完美的符合。另外，選兩者的中點是因為希望這個切割是靠中間的位置。
### 讀後思考
#### 引入 Timsort 的利弊分析
- 非連續記憶體對切割 runs 的好處喪失
Timsort 原本在 cpython 中是實現在陣列上的，然而它轉而實作在鏈節串列中會有一些好處消失。首先在最開始切 runs 的時候，使用陣列可以利用長度小於 64 的資料可以放進 cacheline 的特性讓它進行插入排序法的效益較高，而且連續記憶體還可以使用二分搜來找到插入位置，讓比較次數變成 $\log n$，只是非連續記憶體無法做到上述兩件事，在不管是 Timsort 還是其變體中建立一個新的 run 的程式碼中，都是只有單純的將遞增或嚴格遞減的連起來。另外，在普通的 Timsort 合併時，陣列的版本可以在一個陣列中二分搜另外一個陣列的第 0 個元素，減少比較的次數，讓兩個陣列在大小上重疊很少的時候不需要每次都比較兩個陣列的頭兩個元素，然而在非連續記憶體的情況下也無法做到這件事。
- 比較次數較多但執行時間較短的可能解釋（Timsort 的主要好處）
Timsort 在一開始選取 runs 時，可以將連續遞增（或嚴格遞減）的元素先合併起來。這樣做，雖然在一開始會經歷相鄰元素的比較，所以在比較次數上未必會優於 merge sort，但是由於在比較時是一直存取剛存取過的元素，對快取有正面影響，這樣當資料有好的分佈的話可以用較低的成本合併一些元素。這也能解釋為何在一些資料上，Timsort 的比較次數比 merge sort 還要多，但是執行時間卻比較短。
- 犧牲 merge sort 最佳化的合併
因為無法確定切出來的 runs 的大小分佈是如何，所以會犧牲 merge sort 原本最佳化的合併方法，只能盡量追求在最後一次合併前從堆疊頂部開始以某種指數方式遞增，或是盡可能貼近 optimized merge tree。
而以實驗結果看來，Timsort 與其變體確實能在特定的資料上有顯著的效率改善。
#### powersort 實作改進
> Commit [527edb2](https://github.com/fennecJ/linux2024-quiz/commit/527edb2c6db8257167e8e44501fac85465257129)
```cpp=
static inline size_t nodePower(struct list_head *h1, struct list_head *h2,
size_t start_A, size_t len)
{
if(!h1 || !h2){
return 0;
}
size_t len_2 = len << 1;
size_t start_B = start_A + run_size(h1);
size_t end_B = start_B + run_size(h2);
size_t l = start_A + start_B;
size_t r = start_B + end_B + 1;
int a = (int)((l << 31) / len_2);
int b = (int)((r << 31) / len_2);
return __builtin_clz(a ^ b);
}
```
第 12 行和第 13 行中 `l` 和 `r` 的型別是 `size_t`，他將它左移了 31 位，然而，我們不能期待 `size_t` 是 64 位元的，尤其是它可能運行在 32 位元架構上。所以，改成 `uint64_t` 會比較適應多平台。而 `__builtin_clz` 傳入的參數是 `unsigned int`，這裡又使用位元運算，所以 12 和 13 行應該轉型為 `unsigned int` 更適合。另外，第 4 到 6 行，`if` 之下只有一行，應該將大括號省略。
#### 在 `queue.c` 中引入 powersort
我發現，powersort 適合運用在 `q_merge` ，於是在 Commit [7c2224a](https://github.com/sysprog21/lab0-c/commit/7c2224a01909ca61f9d46d96994fe062fc058aa8) 將其引入。
## [Linux 核心專題: 亂數產生器研究](https://hackmd.io/@sysprog/BkhlALt8A) - `teresasa0731`
這篇專題大略是在各面向分析各種偽隨機數，並且觀察 Linux 的隨機數生成流程。
### 亂數考量因素
評價一個偽隨機數的考慮因數有以下：
- 週期長度
- 均勻分佈
- 生成速度
- 在現性
- 安全性
### xoroshiro128+
這是一種線性平移的隨機數，在統計學上隨機，但是次數多起來後效率有明顯下降。
### Linux RNG
Linux 的隨機數是蒐集硬體產生的隨機資訊（物理干擾）進行一些處理放進熵池中，並且用熵來評價這個熵池的亂度。`/dev/random` 會等待 I/O 到熵池的熵足後取得亂數，而 `/dev/urandom` 會用安全的加密演算法來補足隨機性資料。
### Raspberry Pi 4 RNG
接下來在 Raspberry Pi 4 上裝 Linux，它是由硬體提供應用層亂數的，以此來觀察 `/dev/random` 在熵池不足的情形。
首先做了 `FIPS 140-2` 的測試，發現表現良好。
後面做了效率測試，發現到一定程度的數量後，出現熵池不足的問題，開始等待，如前面所訴。
### 讀後思考
#### xoroshiro128+ 的安全性思考
前面在評估 xoroshiro128+ 的時候，沒有評估到安全性這一塊，這裡補充一下。
xoroshiro128+ 是一種 LFSR，他的操作並不複雜，在拿到夠多資料的情況是可以將種子計算出來。說起來簡單，這裡使用 [z3-solver](https://github.com/Z3Prover/z3) 去進行預測：
```python
import os
from Crypto.Util.number import bytes_to_long
import z3
def rotl(x, k):
if type(x) == int:
return (x << k) | (x >> (64 - k))
return z3.RotateLeft(x, k)
class xorshift128():
def __init__(self, s0, s1):
self.s = [s0, s1]
def next(self):
s0, s1 = self.s
if type(s0) == int:
result = (s0 + s1) % (2**64)
else:
result = s0 + s1
s1 ^= s0
self.s[0] = rotl(s0, 24) ^ s1 ^ (s1 << z3.BitVecVal(16, 64))
self.s[1] = rotl(s1, 37)
return result
seed = bytes_to_long(os.urandom(8)), bytes_to_long(os.urandom(8))
xor = xorshift128(seed[0], seed[1])
s = z3.Solver()
a, b = z3.BitVec("a", 64), z3.BitVec("b", 64)
xor_bv = xorshift128(a, b)
for i in range(16):
s.add(xor.next() == xor_bv.next())
s.check()
a = int(s.model()[a].as_long())
b = int(s.model()[b].as_long())
print(f"{a = }, {b = }")
print(f"{seed = }")
```
輸出結果是：
```
a = 17033195837716372443, b = 16345491342652664975
seed = (17033195837716372443, 16345491342652664975)
```
可以發現我們將 seed 破解出來了。
z3-solver 是一個可以用指定位數的 `BitVec` 去進行計算產生一些符號化的變數，我們去對這些變數進行約束的話，資訊夠多且計算單純就可以輕易的獲得解。而如果是一些更特殊的條件下，使用更精確的破解工具是更好的選擇，譬如說只有用到 `^`、`&`、`<<`、`>>` 的 LFSR，或者是 MT19937，等同於是在 $GF(2)$ 上做運算，可以使用 [gf2bv](https://github.com/maple3142/gf2bv/tree/master) 這個工具，一樣實現了 `BitVec` 的用代數表示變數，但是可以在 $GF(2)$ 上去解線性方程，所以快很多。
順道一題，python 的 random 是用 MT19937 去實作的，但是 randrange 因為會機率性的丟棄一些東西，造成預測上的困擾，所以我有分享過一篇 [randrange 的預測](https://www.canva.com/design/DAGTjxHYxe8/7oxvxerv4xZvsQLejh-tSg/edit?utm_content=DAGTjxHYxe8&utm_campaign=designshare&utm_medium=link2&utm_source=sharebutton)，只是程式碼還沒開源，如果對慨念有興趣可以參考看看（當時不知道有 gf2bv 可以用，所以用 z3，後來嘗試了有很大的效率提昇）。
> TODO: 列出 Linux 核心在密碼學可貢獻的機會
## [從 CFS, EAS, 到 EEVDF ](https://hackmd.io/@sysprog/rkJd7TFX0#4-Group-scheduling-and-cgroups) - `Kuanch`, `devarajabc`
### CFS
引入 per-CPU runqueue 和紅黑樹。以虛擬執行時間（virtual runtime）來決定下一個任務要執行什麼。對於不同的優先度，其權重會決定單位時間轉換過去的虛擬執行時間有多少，優先集越高權重越低。對排程器（CFS）來說，它只看得到虛擬執行時間，以這個時間決定公平的跑每個任務。
為什麼它會被取代呢？主要是因為公平性並不一定是排程的全部考量，如果有個需求低延遲的卻較低優先級的任務，那它不應該被丟著一段時間不管。
### EEVDF
多考慮了任務的急迫性，引入了 latency-nice，代表此任務有多急，數字越小越急。所以，EEVDF 會比 CFS 有更小的延遲。
### EAS
Linux 考量很多大型電腦，需要去嚴格考量功耗比。這是一個提供 CPU 排程器評判效率和能量的機制。
#### big.LITTLE 問題
有大核和小核，如何考量一個任務要放哪？
- 大核
效率高但功耗大
- 小核
效率低但功耗小
### 使用 QEMU + Buildroot + GDB 分析 Kernel
首先跟著 [linux-kernel-debugging](https://github.com/Rhydon1337/linux-kernel-debugging?tab=readme-ov-file)，使用 buildroot 編譯 linux 核心，並且調一些 kernel debug 的設定。
接下來用 qemu 跑起來，開啟它提供的 gdbserver。
接下來用 gdb 的 remote debug 功能連上 gdbserver 就可以開始動態分析。
### 效能分析
#### schbench
拿來分析 Linux 核心效能，評價的項目包括：
- 閒置 CPU
- context switch 數量
- 排程的延遲
Sign in with Wallet
Connect another wallet