Linux 核心專題: 改進 ksort

執行人: yc199911
專題解說影片

Reviewed by `Terry7Wei7`

完成TODO事項，並更新在此頁面

任務簡介

重作第六次作業的 ksort，彙整其他同學的成果 (重現實驗，指出他人的錯誤和缺失)。

TODO: 回覆自我檢查清單

依據第六次作業規範

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

自我檢查清單

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

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

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

〈Linux 核心模組運作原理〉列出的程式碼較舊，歡迎編輯頁面，更新到 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 核心模組運作原理後，學習同學 vax-r 的追蹤方法透過 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》(LKMPG) 並解釋 simrupt 程式碼裡頭的 mutex lock 的使用方式，並探討能否改寫為 lock-free;

參照 2021 年的筆記。歡迎貢獻 LKMPG!

$\to$ 搭配閱讀〈並行和多執行緒程式設計〉

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

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

下面是 mutex_lock_interruptible 在 /kernel/locking/mutex.c 裡的程式碼。

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 在排序過程中的平均比較次數，並提供對應的數學證明;

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

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

$\to$ 搭配閱讀: 不亂的「亂數」

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

狀態轉換函數
Xoroshiro128+ 通過以下步驟來更新它的狀態：

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

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

TODO: 依據第六次作業規範，重作 ksort

適度彙整其他學員的成果並予以重現，比較自己實作的表現。要確保排序結果正確。

TODO: 改進並行的資料排序效能

在 ksort 的基礎，提出得以改善並行的資料排序效能的方案，並予以充分實作

TODO: 檢視其他學員在 ksort 的投入狀況，提出疑惑和建議

在課程期末專題找出同樣從事 ksort 專案開發的學員，在其開發紀錄提出你的疑惑和建議。
在此彙整你的認知和對比你的產出。