## 2024q1 Homework5 (assessment)
contributed by < [yc199911](https://github.com/yc199911) >

[專題解說錄影](https://www.youtube.com/watch?v=1tolOWeVmCo)

### 閱讀〈因為自動飲料機而延畢的那一年〉

在閱讀完〈因為自動飲料機而延畢的那一年〉後我對作者為了達成一件事情的毅力感到佩服，文中作者朋友說：明明知道創投不會投，代表他們覺得這東西回報率很低，那你為什麼還要做 ？ 他沒有被這句話打敗而是持續尋找方法最後的成品雖然一樣沒有被大家運用，但我認為能將自己想做的東西透過努力，最後達成目標，這才是最令人尊敬的精神。

目前也持續在補前幾週的作業，在看完〈因為自動飲料機而延畢的那一年〉後，讓我也想全心全意的投入一個有興趣的專案，體驗那種為了達成目標奮不顧身的精神。

### 研讀課程教材中的問題

#### 你所不知道的 C 語言：數值系統篇

#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;
}

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

因爲 KSIZE 是正整數 1024 ，所以 KSIZE < maxlen ，而 memcpy 第三個參數是 size_t 型別，如果 len 是負數，會被隱式轉換為一個非常大的無號整數會導致 undefine behavior。
當 memcpy 拷貝的位元組數遠超過預期範圍時，它可能會覆蓋記憶體中其他關鍵資料，包括函數返回地址、函數指針、或其他控制結構。覆蓋返回地址可以使程序在函數返回時跳轉到由攻擊者指定的地址，通常是惡意代碼的位置，即完成攻擊。

疑問：這樣電腦是不是很容易就被攻擊成功？因為只需要讓一個參數變成負數就能攻擊成功了。
:::

### 簡述你想投入的專案

#### 1.透過 Netfilter 自動過濾廣告
儘管我們可在網頁瀏覽器中透過像是 AdBlock 這類的 extension 來過濾廣告，但需要額外的設定和佔用更多系統資源，倘若我們能透過 netfilter，直接在核心層級過濾網路廣告，那所有應用程式都有機會受益。

:::info
疑問 :
* 為什麼使用 netfilter 需要使用 NAT(network adresses translation) 偽裝互聯網<s>訪問</s>?
* 那我如果在使用 netfilter 時須要小心電腦遭到入侵嗎?
:::

:::danger
訪問 = visit
存取 = access
https://hackmd.io/@sysprog/it-vocabulary
:::

#### 2.以 Linux XDP 為基礎的防火牆
XDP (eXpress Data Path) 自 Linux 核心 4.8 版本起作為以 eBPF 為基礎的高效資料處理路徑，一旦網路中斷觸發後，XDP 允許將特定的操作提前在 TCP/IP 堆疊之前就處理，不僅反應更快而且省下寶貴的記憶體分配的成本。本議程以 XDP 作為切入，探討如何在這之上發展高效網路負載平衡器，並針對典型的 High Availability (HA) 叢集和非典型的情境去調整。

#### 3.將之前的作業的完成度提高

---

TCP 3-way handshake?
SYN
https://hackmd.io/@sysprog/SyrtOTNb0

TODO: https://hackmd.io/@sysprog/linux2024-integration (回答「自我檢查清單」 + 進行「並行的混合排序」) + 彙整其他同學的成果 (重現實驗，指出他人的錯誤和缺失) + extra

## 自我檢查清單
- [X] 研讀前述 ==Linux 效能分析== 描述，在自己的實體電腦運作 GNU/Linux，做好必要的設定和準備工作 $\to$ 從中也該理解為何不希望在虛擬機器中進行實驗;

* 已在自己的實體電腦運作 GNU/Linux
* 為何不希望在虛擬機中進行實驗？
>1. 虛擬機器運行在一個虛擬層上，這個層會引入額外的開銷。這些開銷包括虛擬化技術所需的資源管理、虛擬硬件抽象等，這些都會影響測試結果，使得無法反映實際硬體環境中的效能。
>2. 在虛擬機器環境中，多個虛擬機器通常會共享同一套物理硬體資源（例如CPU、內存和I/O）。這會導致資源競爭，進而影響到應用程式和核心的效能表現，使得測試結果不穩定或不一致。
>3. 時間精準度問題

- [X] 閱讀〈[Linux 核心模組運作原理](https://hackmd.io/@sysprog/linux-kernel-module)〉並對照 Linux 核心原始程式碼 (v6.1+)，解釋 `insmod` 後，Linux 核心模組的符號 (symbol) 如何被 Linux 核心找到 (使用 List API)、`MODULE_LICENSE` 巨集指定的授權條款又對核心有什麼影響 (GPL 與否對於可用的符號列表有關)，以及藉由 [strace](https://man7.org/linux/man-pages/man1/strace.1.html) 追蹤 Linux 核心的掛載，涉及哪些系統呼叫和子系統？
> 〈[Linux 核心模組運作原理](https://hackmd.io/@sysprog/linux-kernel-module)〉列出的程式碼較舊，歡迎編輯頁面，更新到 Linux v6.1 以上。

>1. `insmod` : The use of module_init is mandatory. This macro adds a special section to the module’s object code stating where the module’s initialization function is to be found. Without this definition, your initialization function is never called.
>2. `MODULE_LICENSE` : is used to tell the kernel that this module bears a free license; without such a declaration, the kernel complains when the module is loaded.

閱讀完 [Linux 核心模組運作原理](https://hackmd.io/@sysprog/linux-kernel-module) 後，學習同學 [vax-r](https://hackmd.io/@vax-r/linux2024-homework6) 的追蹤方法透過 `strace` 命令觀察呼叫的系統呼叫，注意到會進行 `finit_module` 系統呼叫，並在 `idempotent_init_module` 當中的 `init_module_from_file` 呼叫 `load_module` ，值得注意的是 `load_module` 當中的 `simplify_symbols` 會透過一系列操作與函式呼叫將核心模組的 `symbols` 給載入，當中呼叫 `resolve_symbol_wait` 再呼叫 `resolve_symbol` 再呼叫 `find_symbol` ，特別注意到在 `find_symbol` 當中有用到 `List API list_for_each_entry_rcu` 來設定 `module` 當中的為雙向鍵結串列，也可以注意到搜尋 symbol 的函式 find_exported_symbol_in_section 利用到一個特殊的搜尋方式 `bsearch()` 呼叫 ` __inline_bsearch`

/* SPDX-License-Identifier: GPL-2.0 */
#ifndef _LINUX_BSEARCH_H
#define _LINUX_BSEARCH_H

#include <linux/types.h>

static __always_inline
void *__inline_bsearch(const void *key, const void *base, size_t num, size_t size, cmp_func_t cmp)
{
	const char *pivot;
	int result;

	while (num > 0) {
		pivot = base + (num >> 1) * size;
		result = cmp(key, pivot);

		if (result == 0)
			return (void *)pivot;

		if (result > 0) {
			base = pivot + size;
			num--;
		}
		num >>= 1;
	}

	return NULL;
}

extern void *bsearch(const void *key, const void *base, size_t num, size_t size, cmp_func_t cmp);

#endif /* _LINUX_BSEARCH_H */

而其中 `__always_inline`

static __always_inline
void __read_once_size(const volatile void *p, void *res, int size)
{
	switch (size) {
	case 1: *(unsigned char *)res = *(volatile unsigned char *)p; break;
	case 2: *(unsigned short *)res = *(volatile unsigned short *)p; break;
	case 4: *(unsigned int *)res = *(volatile unsigned int *)p; break;
	case 8: *(unsigned long long *)res = *(volatile unsigned long long *)p; break;
	default:
		barrier();
		__builtin_memcpy((void *)res, (const void *)p, size);
		barrier();
	}
}

根據 `size` 的值來選擇如何讀取數據。根據不同的 `size`，從地址 `p` 讀取對應大小的數據並存儲到 `res` 中。

當 `size` 為 1 時，讀取 `unsigned char` 大小的數據。
當 `size` 為 2 時，讀取 `unsigned short` 大小的數據。
當 `size` 為 4 時，讀取 `unsigned int` 大小的數據。
當 `size` 為 8 時，讀取 `unsigned long long` 大小的數據。

執行 `insmod` 大量使用了 `mmap` 系統呼叫，重複的進行 `openat()`, `read()`, `newfstatat()`, `mmap()`, `close()` 一系列系統呼叫。
- [ ] 閱讀《[The Linux Kernel Module Programming Guide](https://sysprog21.github.io/lkmpg/)》(LKMPG) 並解釋 [simrupt](https://github.com/sysprog21/simrupt) 程式碼裡頭的 mutex lock 的使用方式，並探討能否改寫為 [lock-free](https://hackmd.io/@sysprog/concurrency-lockfree);
> 參照 [2021 年的筆記](https://hackmd.io/@linD026/simrupt-vwifi)。歡迎貢獻 LKMPG!
> $\to$ 搭配閱讀〈[並行和多執行緒程式設計](https://hackmd.io/@sysprog/concurrency)〉

在執行 `simrupt_read` 時會使用 `mutex_lock_interruptible` 去判斷是否要使用 mutex_lock

    if (mutex_lock_interruptible(&read_lock))
        return -ERESTARTSYS;

下面是 `mutex_lock_interruptible` 在 [/kernel/locking/mutex.c](https://elixir.bootlin.com/linux/latest/source/kernel/locking/mutex.c#L982) 裡的程式碼。

int __sched mutex_lock_interruptible(struct mutex *lock)
{
	might_sleep();

	if (__mutex_trylock_fast(lock))
		return 0;

	return __mutex_lock_interruptible_slowpath(lock);
}

`__mutex_trylock_fast` 用來在不進行睡眠的情況下快速嘗試獲取鎖。如果成功獲取鎖，函式會返回 0，表示成功。

`return __mutex_lock_interruptible_slowpath`;如果`mutex_trylock_fast` 獲取鎖失敗，函式會調用 `__mutex_lock_interruptible_slowpath`。這個函式包含了睡眠和中斷處理邏輯，允許當前執行緒在等待鎖時被中斷信號打斷。如果鎖被成功獲取，函式返回 0；如果被中斷打斷，函式返回 -ERESTARTSYS。

void __sched mutex_lock(struct mutex *lock)
{
	might_sleep();

	if (!__mutex_trylock_fast(lock))
		__mutex_lock_slowpath(lock);
}
EXPORT_SYMBOL(mutex_lock);

- [ ] 探討 Timsort, Pattern Defeating Quicksort (pdqsort) 及 Linux 核心 [lib/sort.c](https://github.com/torvalds/linux/blob/master/lib/sort.c) 在排序過程中的平均比較次數，並提供對應的數學證明;
> 對照 [fluxsort](https://github.com/scandum/fluxsort) 和 [crumsort](https://github.com/scandum/crumsort) 的分析和效能評比方式
- [ ] 研讀 [CMWQ](https://www.kernel.org/doc/html/latest/core-api/workqueue.html) (Concurrency Managed Workqueue) 文件，對照 [simrupt](https://github.com/sysprog21/simrupt) 專案的執行表現，留意到 worker-pools 類型可指定 "Bound" 來分配及限制特定 worker 執行於指定的 CPU，Linux 核心如何做到？CMWQ 關聯的 worker thread 又如何與 CPU 排程器互動？
> 搭配閱讀《Demystifying the Linux CPU Scheduler》
- [ ] 解釋 `xoroshiro128+` 的原理 (對照〈[Scrambled Linear Pseudorandom Number Generators](https://arxiv.org/pdf/1805.01407.pdf)〉論文)，並利用 [ksort](https://github.com/sysprog21/ksort) 提供的 `xoro` 核心模組，比較 Linux 核心內建的 `/dev/random` 及 `/dev/urandom` 的速度，說明 `xoroshiro128+` 是否有速度的優勢？其弱點又是什麼？
> $\to$ 搭配閱讀: [不亂的「亂數」](https://blog.cruciferslab.net/?p=599)

Xoroshiro128+ 是一種高效能的偽隨機數生成器 (PRNG)。
Xoroshiro128+ 的名稱來自其結構的組成：xor (異或操作) 和 shift (移位操作) 結合 rotate (旋轉操作)。它的狀態由兩個 64 位元的整數組成，因此總共有 128 位元的狀態空間。

狀態轉換函數
Xoroshiro128+ 通過以下步驟來更新它的狀態：
1. 定義兩個 64 位元的整數 s[0] 和 s[1]，它們代表 PRNG 的狀態。
2. 生成下一個隨機數 result，它是 s[0] 和 s[1]的結果。
3. 使用異或操作、移位操作和旋轉操作來更新狀態：

uint64_t s0 = s[0];
uint64_t s1 = s[1];
result = s0 + s1;

s1 ^= s0;
s[0] = rotl(s0, 24) ^ s1 ^ (s1 << 16); // a, b
s[1] = rotl(s1, 37); // c

rotl(x, k) 是一個將 x 左旋轉 k 位的函數。
s1 ^= s0 是對 s1 進行異或操作。
s[0] = rotl(s0, 24) ^ s1 ^ (s1 << 16) 和 s[1] = rotl(s1, 37) 是狀態更新的兩部分。

重要特性:
高效能：Xoroshiro128+ 具有非常高的運行速度，因為它只使用了基本的位操作和加法操作，這些操作在現代處理器上都能夠高效地執行。

良好的統計特性：根據論文中的描述和測試，Xoroshiro128+ 通過了大多數的隨機數生成器測試，展示了良好的統計性質。

周期：Xoroshiro128+ 的周期為 2^128 - 1，這意味著在重複之前，它可以生成約3.4 * 10^38 個隨機數。

使用場景
Xoroshiro128+ 非常適合用於需要高效且具有良好統計特性的隨機數生成的場景，如模擬、遊戲開發和蒙特卡羅方法等。然而，由於它不是密碼學安全的偽隨機數生成器，不應在需要高安全性的情境中使用。

- [ ] 解釋 [ksort](https://github.com/sysprog21/ksort) 如何運用 CMWQ 達到並行的排序;

### 閱讀教材 [並行程式設計](https://hackmd.io/@sysprog/concurrency/%2F%40sysprog%2Fconcurrency-concepts) 紀錄

#### 加快ＣＰＵ速度

* 以前 CPU 增進效能的手段
* Clock speed
* Execution Optimization
* Pipelining、Branch prediction
* Out-of-order execution 還要注意不能讓原本程式崩潰 (read/write reorder)
* Cache：盡量減少存取 Main memory 的機會
* 現在 CPU 增進效能的手段
* Hyperthreading: 在 single CPU 上同時執行多個 thread，但是共用 ALU、FPU
* Multicore：多個 CPU
* 迷思：`2 x 3GHz < 6GHz`
* Cache

#### Concurrency（並行）與 Parallelism（平行）
* Concurrency 是指程式架構，將程式拆開成多個可獨立運作的工作。案例: 裝置驅動程式，可獨立運作，但不需要平行化。
* 拆開多個的工作不一定要同時運行
* 多個工作在單核 CPU 上運行

* Parallelism 是指程式執行，同時執行多個程式。Concurrency 可能會用到 parallelism，但不一定要用 parallelism 才能實現 concurrency。案例: 向量內積計算
* 程式會同時執行 (例如：分支後，同時執行，再收集結果)
* 一個工作在多核 CPU 上運行