2024q1 Homework6 (integration)

contributed by < ollieni >

自我檢查清單

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

在本機和虛擬機器進行實驗的差別為以下兩點:

1. 性能差異：
   本機： 在本機上運行 GNU/Linux 可能會獲得更好的性能，因為操作系統可以直接訪問硬體資源，如CPU、記憶體和硬碟。
   虛擬機器： 在虛擬機器中運行 GNU/Linux 則是在主機操作系統的虛擬環境中運行。虛擬機器的性能取決於主機系統的資源分配，因此可能無法完全發揮硬體效率。
2. 資源隔離：
   本機： 在本機上運行 GNU/Linux 時，可以直接訪問整個硬體資源，並且系統可以充分利用這些資源。
   虛擬機器： 在虛擬機器中運行 GNU/Linux 時，資源通常是由虛擬機器管理器分配的。可能會有性能上的限制或競爭。

• 閱讀〈Linux 核心模組運作原理〉並對照 Linux 核心原始程式碼 (v6.1+)，解釋 insmod 後，Linux 核心模組的符號 (symbol) 如何被 Linux 核心找到 (使用 List API)、MODULE_LICENSE 巨集指定的授權條款又對核心有什麼影響 (GPL 與否對於可用的符號列表有關)，以及藉由 strace 追蹤 Linux 核心的掛載，涉及哪些系統呼叫和子系統？

根據老師提供的文件，我們可以得知我們要看的程式在 kernel/module/main.c，在其中可以看到一個 function find_symbol，裡面有使用 List API list_for_each_entry_rcu 去找到 symbol。
在 resolve_symbol 這個 function 裡面，會由以下程式去檢查是否 GPL_only

	if (fsa.license == GPL_ONLY)
		mod->using_gplonly_symbols = true;

	if (!inherit_taint(mod, fsa.owner, name)) {
		fsa.sym = NULL;
		goto getname;
	}

在 inherit_taint function 裡有做確認是不是 GPL only，如果不是，會輸出錯誤訊息。

	if (mod->using_gplonly_symbols) {
		pr_err("%s: module using GPL-only symbols uses symbols %s from proprietary module %s.\n",
			mod->name, name, owner->name);
		return false;
	}

用 strace 追蹤 Linux 核心的掛載:

用 execve 啟動一個新的進程來執行指定的程序，執行 /sbin/insmod ，以 ["insmod", "fibdrv.ko"] 作為參數傳入。
用 getcwd 獲取當前工作目錄，然後尋找要加載的模組文件 /tmp/fibdrv/fibdrv.ko。
用 openat 打開了模組文件，並進行文件相關的操作（fstat 和 mmap）。
最後，使用 finit_module 將模組加載到核中。

• 閱讀《The Linux Kernel Module Programming Guide》(LKMPG) 並解釋 simrupt 程式碼裡頭的 mutex lock 的使用方式，並探討能否改寫為 lock-free;

simrupt 裡使用的 mutex lock 有三個，read_lock、producer_lock、consumer_lock。
以下是三個 mutex lock 個別的作用 :
read_lock：
作用：保護共享的 kfifo 緩衝區 (rx_fifo)，防止多個使用者空間的讀取操作同時進行。
在 simrupt_read() 函式中使用，透過 mutex_lock_interruptible(&read_lock); 取得此鎖，確保只有一個進程或線程能夠執行讀取操作。
producer_lock：
作用：用於序列化對 kfifo 緩衝區的寫入操作，確保只有一個生產者（在工作序列處理函式 simrupt_work_func 中）能夠訪問並向緩衝區添加新數據。
在 simrupt_work_func() 函式中，透過 mutex_lock(&producer_lock); 取得此鎖，以確保在工作隊列中只有一個生產者能夠向 kfifo 緩衝區寫入數據。
consumer_lock：
作用：保護 fast_buf 緩衝區，在工作序列處理函式 (simrupt_work_func) 中確保只有一個消費者能夠從 fast_buf 中提取數據。
在 simrupt_work_func() 函式中，透過 mutex_lock(&consumer_lock); 取得此鎖，以確保在工作隊列中只有一個消費者能夠從 fast_buf 中取出數據。

閱讀老師給的文件 並行程式設計: Lock-Free Programming 後，得知了有 lock-free 和 lock-less 的區別，以下是我的理解。
相同 : lock-free 和 lock-less 都避免使用 lock 。
相異 : lock-less 注重資料共用可以正確和安全，lock-free 則更重視執行序要有進展。

• 研讀 CMWQ (Concurrency Managed Workqueue) 文件，對照 simrupt 專案的執行表現，留意到 worker-pools 類型可指定 "Bound" 來分配及限制特定 worker 執行於指定的 CPU，Linux 核心如何做到？CMWQ 關聯的 worker thread 又如何與 CPU 排程器互動？

根據 CMWQ 文件中所說，可以使用 alloc_workqueue() 對 work queue 設置一些 flag，包括 CPU 位置、併發限制、優先順序，另外， 可以用 apply_workqueue_attrs()，這個 API 對 unbound work queue 設置屬性。

Linux 提供了 CPU Affinity 的概念，允許用戶將特定的任務或線程綁定到特定的 CPU 核心上運行。可以通過 apply_workqueue_attrs() ，對特定的 work queue 修改 affinity_scope 或 affinity_strict 來實現。
在文件中，以 affinity_scope 的預設值 cache 的情況舉例，在這個情況下，會根據上一級快取的界限將 CPU 分組。 work queue 上排隊的 work item 將會被分配給一個與發出 CPU 共享上一級快取的 CPU 上的 thread。

An unbound workqueue groups CPUs according to its affinity scope to improve cache locality. For example, if a workqueue is using the default affinity scope of “cache”, it will group CPUs according to last level cache boundaries. A work item queued on the workqueue will be assigned to a worker on one of the CPUs which share the last level cache with the issuing CPU. Once started, the worker may or may not be allowed to move outside the scope depending on the affinity_strict setting of the scope.

和 CPU scheduler 的互動方式是將 CPU 的 worker-pool 接入 scheduler 來管理，確保並行性。每當 worker 被喚醒或進入睡眠狀態時，都會通知 worker-pool，以便追蹤當前可用的 worker 數量。此外，工作項目不應該佔用 CPU 太久。只要 CPU 上有多個 worker 正在執行，它就不會開始執行新的工作。但是當某個正在運行的 worker 進入睡眠狀態時，worker-pool 會立即分配一個新的 worker，這樣 CPU 就不會在還有待處理的工作項目時進入空閒狀態。

Each worker-pool bound to an actual CPU implements concurrency management by hooking into the scheduler. The worker-pool is notified whenever an active worker wakes up or sleeps and keeps track of the number of the currently runnable workers. Generally, work items are not expected to hog a CPU and consume many cycles. That means maintaining just enough concurrency to prevent work processing from stalling should be optimal. As long as there are one or more runnable workers on the CPU, the worker-pool doesn’t start execution of a new work, but, when the last running worker goes to sleep, it immediately schedules a new worker so that the CPU doesn’t sit idle while there are pending work items. This allows using a minimal number of workers without losing execution bandwidth.

• 解釋 xoroshiro128+ 的原理 (對照〈Scrambled Linear Pseudorandom Number Generators〉論文)，並利用 ksort 提供的 xoro 核心模組，比較 Linux 核心內建的 /dev/random 及 /dev/urandom 的速度，說明 xoroshiro128+ 是否有速度的優勢？其弱點又是什麼？

在論文中有看到 xoroshiro128+ 的程式碼 :

const int q = p;
const uint64_t s0 = s[p = (p + 1) & 15];
uint64_t s15 = s[q];
const uint64_t result_plus = s0 + s15;
const uint64_t result_plusplus = rotl(s0 + s15, R) + s15;
const uint64_t result_star = s0 * S;
const uint64_t result_starstar = rotl(s0 * S, R) * T;
s15 ^= s0;
s[q] = rotl(s0, A) ^ s15 ^ (s15 << B);
s[p] = rotl(s15, C);

可以看到用了三個 bit-wise 操作， xor 、 rot(circular shift) 、 shift。
理論概念主要是透過這些 bit-wise operation，使數值在高維中分散和混合。

• 解釋 ksort 如何運用 CMWQ 達到並行的排序

在 sort_mod.c 裡面，會在 sort_init 函式裡面用 alloc_workqueue 創建並設定 work queue ，另外，會在 sort_exit 函式裡面使用 destroy_workqueue 去安全的刪除 work queue。

另外，會通過以下兩行程式，用 module_init 這個宏將 sort_init、sort_exit，設為模組初始化函式，將會被 kernel 自動調用，執行模組所需的初始化過程。

module_init(sort_init);
module_exit(sort_exit);

在 sort_impl.c 裡可以看到有一個 init_qsort 函式，使用了 INIT_WORK 這個宏。 INIT_WORK 會使用
module_init 設定的初始化函式，將 work 初始化，以便於將這個工作結構提交到 work queue 中等待執行，因此在程式中可以看到在init_qsort 函式後，都接著一個 queue_work 函式，將工作放進 work queue 裡面。