2024q1 Homework6 (integration)

contributed by < aa860630 >

實驗環境

$ gcc --version
gcc (Ubuntu 11.4.0-1ubuntu1~22.04) 11.4.0
Copyright (C) 2021 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
$ lscpu
Architecture:            x86_64
  CPU op-mode(s):        32-bit, 64-bit
  Address sizes:         39 bits physical, 48 bits virtual
  Byte Order:            Little Endian
CPU(s):                  8
  On-line CPU(s) list:   0-7
Vendor ID:               GenuineIntel
  Model name:            11th Gen Intel(R) Core(TM) i5-11300H @ 3.10GHz
    CPU family:          6
    Model:               140
    Thread(s) per core:  2
    Core(s) per socket:  4
    Socket(s):           1
    Stepping:            1
    CPU max MHz:         4400.0000
    CPU min MHz:         400.0000
    BogoMIPS:            6220.80
Virtualization features: 
  Virtualization:        VT-x
Caches (sum of all):     
  L1d:                   192 KiB (4 instances)
  L1i:                   128 KiB (4 instances)
  L2:                    5 MiB (4 instances)
  L3:                    8 MiB (1 instance)
NUMA:                    
  NUMA node(s):          1
  NUMA node0 CPU(s):     0-7
$ uname -r
6.5.0-26-generic

自我檢查清單

研讀前述 Linux 效能分析描述，在自己的實體電腦運作 GNU/Linux，做好必要的設定和準備工作
$\to$ 從中也該理解為何不希望在虛擬機器中進行實驗;
閱讀〈Linux 核心模組運作原理〉並對照 Linux 核心原始程式碼 (v6.1+)，解釋 insmod 後，Linux 核心模組的符號 (symbol) 如何被 Linux 核心找到 (使用 List API)、MODULE_LICENSE 巨集指定的授權條款又對核心有什麼影響 (GPL 與否對於可用的符號列表有關)，以及藉由 strace 追蹤 Linux 核心的掛載，涉及哪些系統呼叫和子系統？

insmod 的主要功能是將特定的模組檔案載入到核心中。這個程序直接處理模組插入，因此並不會自動處理模組間的依賴關係。如果模組有未解決的依賴，insmod 可能會失敗。

藉由 strace 追蹤 Linux 核心的掛載，涉及哪些系統呼叫和子系統？
```
$ sudo strace insmod fibdrv.ko

execve("/usr/sbin/insmod", ["insmod", "fibdrv.ko"], 0x7ffd6b299d08 /* 26 vars */) = 0
brk(NULL)                               = 0x5cafc9612000
arch_prctl(0x3001 /* ARCH_??? */, 0x7ffec5eccf40) = -1 EINVAL (Invalid argument)
mmap(NULL, 8192, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0) = 0x78d3c2a8a000
access("/etc/ld.so.preload", R_OK)      = -1 ENOENT (No such file or directory)
openat(AT_FDCWD, "/etc/ld.so.cache", O_RDONLY|O_CLOEXEC) = 3
newfstatat(3, "", {st_mode=S_IFREG|0644, st_size=71415, ...}, AT_EMPTY_PATH) = 0
mmap(NULL, 71415, PROT_READ, MAP_PRIVATE, 3, 0) = 0x78d3c2a78000
close(3)                                = 0
```
利用 strace 追蹤執行insmod fibdrv.ko的過程可以發現如 close()、mmap()、read()、openat()等函式：

openat() :openat()系統調用的操作方式與open()完全相同,如果pathname中給出的路徑名是相對的，則它將相對於由檔案描述符dirfd指示的目錄進行編譯
int openat(int dirfd, const char *pathname, int flags, mode_t mode);
close() : close()關閉檔案描述符，使其不再指向任何文件並且可能被重新使用。
read():read()函數將嘗試從與打開的檔案描述符 fildes 相關的文件中讀取nbyte字節，並將其放入由buf指向的緩衝區。
ssize_t read(int fildes, void *buf, size_t nbyte);
mmap : mmap()會在呼叫進程的虛擬地址空間中創建一個新的映射。這個映射的起始地址由addr指定，而length參數指定了映射的長度。
void *mmap(void *addr, size_t lengthint " prot ", int " flags , int fd, off_t offset);int munmap(void *addr, size_t length);

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

Producer (生產者)：產生新資料，並將其插入到 fast_buf 中，以便快速存儲，或插入到 kfifo 中，以便後續傳輸或消費
Consumer (消費者)：從 fast_buf 中讀取資料，然後進一步處理這些資料，可能是將其傳輸到 kfifo，或者進行其他操作

不管是生產者在產生新資料抑或是消費者在讀取資料，我們都不希望這個期間被干擾。舉例來說，當消費者在讀取資料時，我們希望操作是原子性的，不受其他操作的影響。這樣做的目的是避免數據競爭或緩衝區內資料的不一致。

在這個程式碼片段中，consumer_lock用於保護從fast_buf中讀取資料的操作。在mutex_lock(&consumer_lock)和mutex_unlock(&consumer_lock)之間，確保只有一個執行緒可以訪問fast_buf，避免同時讀取或修改帶來的競爭條件，mutex_lock(&producer_lock)與mutex_unlock(&producer_lock)亦是如此
```
while (1) {
        /* Consume data from the circular buffer */
        mutex_lock(&consumer_lock);
        val = fast_buf_get();
        mutex_unlock(&consumer_lock);

        if (val < 0)
            break;

        /* Store data to the kfifo buffer */
        mutex_lock(&producer_lock);
        produce_data(val);
        mutex_unlock(&producer_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$ 搭配閱讀: 不亂的「亂數」
解釋 ksort 如何運用 CMWQ 達到並行的排序;

2024q1 Homework6 (integration)

實驗環境

自我檢查清單

藉由 strace 追蹤 Linux 核心的掛載，涉及哪些系統呼叫和子系統？

Read more

透過 Netfilter 自動過濾廣告

2024q1 Homework5 (assessment)

2024q1 Homework4 (quiz3+4)

2024q1 Homework1 (lab0)