# 2024q1 Homework6 (integration) contributed by < `nelson0720j` > ## 開發環境 ```shell 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)了解巨集等應用。 * 間接巨集 ```clike /* 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) #### 問題回答 ## 作業主題