# 2024q1 Homework6 (integration)
contributed by < `nelson0720j` >

## 開發環境

gcc --version
gcc (Ubuntu 13.2.0-23ubuntu4) 13.2.0

$ lscpu
架構：                    x86_64
  CPU 作業模式：          32-bit, 64-bit
  Address sizes:          43 bits physical, 48 bits virtual
  Byte Order:             Little Endian
CPU(s):                   12
  On-line CPU(s) list:    0-11
供應商識別號：            AuthenticAMD
  Model name:             AMD Ryzen 5 3600 6-Core Processor
    CPU 家族：            23
    型號：                113
    每核心執行緒數：      2
    每通訊端核心數：      6
    Socket(s):            1
    製程：                0
    Frequency boost:      enabled
    CPU(s) scaling MHz:   55%
    CPU max MHz:          4208.2031
    CPU min MHz:          2200.0000
    BogoMIPS:             7199.77
    Flags:                fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov pat pse36 clflush mmx fxsr sse sse2 ht syscall nx mmxext fxsr_opt pdpe1gb rdtscp lm constant_tsc rep_g
                          ood nopl nonstop_tsc cpuid extd_apicid aperfmperf rapl pni pclmulqdq monitor ssse3 fma cx16 sse4_1 sse4_2 movbe popcnt aes xsave avx f16c rdrand lahf_lm cmp_legacy 
                          svm extapic cr8_legacy abm sse4a misalignsse 3dnowprefetch osvw ibs skinit wdt tce topoext perfctr_core perfctr_nb bpext perfctr_llc mwaitx cpb cat_l3 cdp_l3 hw_pst
                          ate ssbd mba ibpb stibp vmmcall fsgsbase bmi1 avx2 smep bmi2 cqm rdt_a rdseed adx smap clflushopt clwb sha_ni xsaveopt xsavec xgetbv1 cqm_llc cqm_occup_llc cqm_mbm_
                          total cqm_mbm_local clzero irperf xsaveerptr rdpru wbnoinvd arat npt lbrv svm_lock nrip_save tsc_scale vmcb_clean flushbyasid decodeassists pausefilter pfthreshold 
                          avic v_vmsave_vmload vgif v_spec_ctrl umip rdpid overflow_recov succor smca sev sev_es
Virtualization features:  
  虛擬：                  AMD-V
Caches (sum of all):      
  L1d:                    192 KiB (6 instances)
  L1i:                    192 KiB (6 instances)
  L2:                     3 MiB (6 instances)
  L3:                     32 MiB (2 instances)
NUMA:                     
  NUMA 節點：             1
  NUMA node0 CPU(s)：     0-11
Vulnerabilities:          
  Gather data sampling:   Not affected
  Itlb multihit:          Not affected
  L1tf:                   Not affected
  Mds:                    Not affected
  Meltdown:               Not affected
  Mmio stale data:        Not affected
  Reg file data sampling: Not affected
  Retbleed:               Mitigation; untrained return thunk; SMT enabled with STIBP protection
  Spec rstack overflow:   Mitigation; Safe RET
  Spec store bypass:      Mitigation; Speculative Store Bypass disabled via prctl
  Spectre v1:             Mitigation; usercopy/swapgs barriers and __user pointer sanitization
  Spectre v2:             Mitigation; Retpolines; IBPB conditional; STIBP always-on; RSB filling; PBRSB-eIBRS Not affected; BHI Not affected
  Srbds:                  Not affected
  Tsx async abort:        Not affected

## 自我檢查清單
### 作業描述（一）
### 研讀 Linux 效能分析和準備工作

* 了解 taskset 對行程的操作
* 用統計手法去除極端值
`outlier_filter` 去除 95% 區間之外的值 (threshold = 2)
* 利用 perf 去分析效能，可以看到經過去除極端值的數據集，其波動跟沒有去除的對照組比起來明顯小很多。

### [Linux 核心模組運作原理](https://hackmd.io/@sysprog/linux-kernel-module)
#### 閱讀紀錄
* 閱讀[你所不知道的 C 語言：前置處理器應用篇](https://hackmd.io/@sysprog/c-preprocessor)了解巨集等應用。
* 間接巨集

/* Indirect macros required for expanded argument pasting, eg. __LINE__. */
#define ___PASTE(a,b) a##b
#define __PASTE(a,b) ___PASTE(a,b)

如果不使用間接巨集，傳入一個巨集的參數，他會被當成字串，而不會展開。
e.q. `__PASTE(value) hello##value` 傳入 `__line__` 巨集，會得到 `hello__value__` 。
* 工具指令
1. modinfo
檢查模組訊息。
2. readelf
讀取和顯示 ELF，檢查可執行文件和共享庫中的結構、部分和符號表等信息。
3. insmod
將模組檔案複製到 kernel space 。
4. strace
觀察執行哪些系統呼叫。
#### 問題回答
- [ ] insmod 後，Linux 核心模組的符號 (symbol) 如何被 Linux 核心找到 (使用 List API)
[find_symbol](https://github.com/torvalds/linux/blob/master/kernel/module/main.c#L302) 中的 [find_exported_symbol_in_section](https://github.com/torvalds/linux/blob/5eb4573ea63d0c83bf58fb7c243fc2c2b6966c02/kernel/module/main.c#L276) 可得知，透過 [bsearch](https://github.com/torvalds/linux/blob/master/include/linux/bsearch.h) 實現 binary search 來搜尋核心模組的符號。
* inline/extern
inline: 只有本文件可見。
extern: 使編譯器可以使用這個在其他文件中的變數/函數。
- [ ] MODULE_LICENSE 巨集指定的授權條款又對核心有什麼影響 (GPL 與否對於可用的符號列表有關)
`load_module` 會執行 `find_symbol` 其中 `find_exported_symbol_in_section` 會去檢查是否可以查找有 gpl 的 symbol ，若沒有 gpl 則不會導出到 symbol 表中，這個模組的 symbol 也不會模組使用 。
- [ ] 藉由 strace 追蹤 Linux 核心的掛載，涉及哪些系統呼叫和子系統？
[strace](https://strace.io/) 可以追蹤 `getdents` ， `lstat` ， `write` ， `open` ， `close` ， `read` ， `fstat` ， `mmap` ， `mprotect` ， `munmap` ， `brk` ， `access` ， `execve` ， `sysinfo` ， `arch_prctl` 等。

### [The Linux Kernel Module Programming Guide](https://sysprog21.github.io/lkmpg/#registering-a-device)

#### 閱讀紀錄
[simrupt筆記](https://hackmd.io/@linD026/simrupt-vwifi)
#### 問題回答
- [ ] 解釋 simrupt 程式碼裡頭的 mutex lock 的使用方式，並探討能否改寫為 lock-free。
[`producer_lock`](https://github.com/sysprog21/simrupt/blob/6093cddab984286fff2f709f043a0a9bef2f93b6/simrupt.c#L75C21-L75C34) 來保護對 `kfifo buffer` 的寫入。</br> [`consumer_lock`](https://github.com/sysprog21/simrupt/blob/6093cddab984286fff2f709f043a0a9bef2f93b6/simrupt.c#L80C21-L80C34) 來保護 [`simrupt_work_func`](https://github.com/sysprog21/simrupt/blob/6093cddab984286fff2f709f043a0a9bef2f93b6/simrupt.c#L143C13-L143C30) 的 `fast_buf` 讀取。
`read_lock` 在 [simrupt_read](https://github.com/sysprog21/simrupt/blob/6093cddab984286fff2f709f043a0a9bef2f93b6/simrupt.c#L250) 中對讀取 `rx_fifo` 這個指針指向的內存空間作互斥保護。
lock-free 問題尚未有解答。
### Timsort, Pattern Defeating Quicksort (pdqsort)
### 閱讀紀錄
* [pdqsort](https://github.com/orlp/pdqsort?tab=readme-ov-file) 採取以下技巧
三向分段法: 根據不同資料結構採取最佳的排序法。
bad partition: 根據 bad partition 來決定切換成 heap sort 的時機
median-of-3 ninther 選擇 pivot: 將資料切分成三組，每組找 pivot 在從這 3 個 pivot 中找最佳的 pivot 。
[pdqsort學習參考](https://hackmd.io/@Chang-Chia-Chi/pdqsort)
:::info
好奇 [crumsort](https://github.com/scandum/crumsort?tab=readme-ov-file) 中的 memory visualiztion 是怎麼製作出來的?
:::
#### 問題回答
- [ ] 探討 Timsort, Pattern Defeating Quicksort (pdqsort) 及 Linux 核心 lib/sort.c 在排序過程中的平均比較次數，並提供對應的數學證明

### [CMWQ](https://www.kernel.org/doc/html/latest/core-api/workqueue.html)

#### 問題回答

## 作業主題