# 2024q1 Homework6 (integration)

contributed by < [williamlin0518](https://github.com/williamlin0518) >

## 實驗環境

william@william-System-Product-Name:~$ gcc --version
gcc (Ubuntu 13.2.0-23ubuntu4) 13.2.0
Copyright (C) 2023 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.

william@william-System-Product-Name:~$ lscpu
架構：                    x86_64
  CPU 作業模式：          32-bit, 64-bit
  Address sizes:          46 bits physical, 48 bits virtual
  Byte Order:             Little Endian
CPU(s):                   20
  On-line CPU(s) list:    0-19
供應商識別號：            GenuineIntel
  Model name:             12th Gen Intel(R) Core(TM) i7-12700K
    CPU 家族：            6
    型號：                151
    每核心執行緒數：      2
    每通訊端核心數：      12
    Socket(s):            1
    製程：                2
    CPU(s) scaling MHz:   19%
    CPU max MHz:          5000.0000
    CPU min MHz:          800.0000
    BogoMIPS:             7219.20
    Flags:                fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge m
                          ca cmov pat pse36 clflush dts acpi mmx fxsr sse sse2 s
                          s ht tm pbe syscall nx pdpe1gb rdtscp lm constant_tsc 
                          art arch_perfmon pebs bts rep_good nopl xtopology nons
                          top_tsc cpuid aperfmperf tsc_known_freq pni pclmulqdq 
                          dtes64 monitor ds_cpl vmx smx est tm2 ssse3 sdbg fma c
                          x16 xtpr pdcm sse4_1 sse4_2 x2apic movbe popcnt tsc_de
                          adline_timer aes xsave avx f16c rdrand lahf_lm abm 3dn
                          owprefetch cpuid_fault epb cat_l2 cdp_l2 ssbd ibrs ibp
                          b stibp ibrs_enhanced tpr_shadow flexpriority ept vpid
                           ept_ad fsgsbase tsc_adjust bmi1 avx2 smep bmi2 erms i
                          nvpcid rdt_a rdseed adx smap clflushopt clwb intel_pt 
                          sha_ni xsaveopt xsavec xgetbv1 xsaves split_lock_detec
                          t user_shstk avx_vnni dtherm ida arat pln pts hwp hwp_
                          notify hwp_act_window hwp_epp hwp_pkg_req hfi vnmi umi
                          p pku ospke waitpkg gfni vaes vpclmulqdq tme rdpid mov
                          diri movdir64b fsrm md_clear serialize pconfig arch_lb
                          r ibt flush_l1d arch_capabilities
Virtualization features:  
  虛擬：                  VT-x
Caches (sum of all):      
  L1d:                    512 KiB (12 instances)
  L1i:                    512 KiB (12 instances)
  L2:                     12 MiB (9 instances)
  L3:                     25 MiB (1 instance)                  
NUMA:                     
  NUMA 節點：             1
  NUMA node0 CPU(s)：     0-19

## 閱讀 linux 核心模組教材

### [Linux 核心模組運作原理](https://hackmd.io/@sysprog/linux-kernel-module)

[ 1009.371692] hello: module verification failed: signature and/or required key missing - tainting kernel
[ 1009.372564] Hello, world
[ 1052.765868] Goodbye, cruel world

Showing hello module doesn't have a valid signature
#### Trace linux kernel insmod
`sudo strace insmod fibdrv.ko`
#### Library and Dependency Loading
when user-space program executed, requires libraries to perform its functions
`openat()`, `read()`, `fstat()`, `mmap()` : open library files, check their properties, map them into memory,
##### MODULE_LICENSE
specifies the licensing terms under which the kernel module is distributed.
##### Symbol Table
Linux kernel maintains a symbol table, where all exported symbols from the kernel and loaded modules are registered.

##### Module File Handling
`openat()` : opens the `fibdrv.ko` file for reading.
`newfstatat()` : onfirming that the file is accessible and properly formatted.

##### Kernel Module Loading
`finit_module()` : load the kernel module into the Linux kernel. The call takes a file descriptor pointing to the module file,

---
### [kernel module 前置作業](https://sysprog21.github.io/lkmpg/#headers)
---

## 自我檢查清單
- [X] 實體電腦運行 GNU/Linux
- Ubuntu 24.04 LTS

- [ ] 閱讀〈[Linux 核心模組運作原理](https://hackmd.io/@sysprog/linux-kernel-module)〉並對照 Linux 核心原始程式碼 (v6.1+)，解釋 `insmod` 後，Linux 核心模組的符號 (symbol) 如何被 Linux 核心找到 (使用 List API)、`MODULE_LICENSE` 巨集指定的授權條款又對核心有什麼影響 (GPL 與否對於可用的符號列表有關)，以及藉由 [strace](https://man7.org/linux/man-pages/man1/strace.1.html) 追蹤 Linux 核心的掛載，涉及哪些系統呼叫和子系統？
> 〈[Linux 核心模組運作原理](https://hackmd.io/@sysprog/linux-kernel-module)〉列出的程式碼較舊，歡迎編輯頁面，更新到 Linux v6.1 以上。
- [ ] 閱讀《[The Linux Kernel Module Programming Guide](https://sysprog21.github.io/lkmpg/)》(LKMPG) 並解釋 [simrupt](https://github.com/sysprog21/simrupt) 程式碼裡頭的 mutex lock 的使用方式，並探討能否改寫為 [lock-free](https://hackmd.io/@sysprog/concurrency-lockfree);
> 參照 [2021 年的筆記](https://hackmd.io/@linD026/simrupt-vwifi)。歡迎貢獻 LKMPG!
> $\to$ 搭配閱讀〈[並行和多執行緒程式設計](https://hackmd.io/@sysprog/concurrency)〉
- [ ] 探討 Timsort, Pattern Defeating Quicksort (pdqsort) 及 Linux 核心 [lib/sort.c](https://github.com/torvalds/linux/blob/master/lib/sort.c) 在排序過程中的平均比較次數，並提供對應的數學證明;
> 對照 [fluxsort](https://github.com/scandum/fluxsort) 和 [crumsort](https://github.com/scandum/crumsort) 的分析和效能評比方式
- [ ] 研讀 [CMWQ](https://www.kernel.org/doc/html/latest/core-api/workqueue.html) (Concurrency Managed Workqueue) 文件，對照 [simrupt](https://github.com/sysprog21/simrupt) 專案的執行表現，留意到 worker-pools 類型可指定 "Bound" 來分配及限制特定 worker 執行於指定的 CPU，Linux 核心如何做到？CMWQ 關聯的 worker thread 又如何與 CPU 排程器互動？
> 搭配閱讀《Demystifying the Linux CPU Scheduler》
- [ ] 解釋 `xoroshiro128+` 的原理 (對照〈[Scrambled Linear Pseudorandom Number Generators](https://arxiv.org/pdf/1805.01407.pdf)〉論文)，並利用 [ksort](https://github.com/sysprog21/ksort) 提供的 `xoro` 核心模組，比較 Linux 核心內建的 `/dev/random` 及 `/dev/urandom` 的速度，說明 `xoroshiro128+` 是否有速度的優勢？其弱點又是什麼？
> $\to$ 搭配閱讀: [不亂的「亂數」](https://blog.cruciferslab.net/?p=599)
- [ ] 解釋 [ksort](https://github.com/sysprog21/ksort) 如何運用 CMWQ 達到並行的排序;