changed a year ago  
Published Linked with GitHub

2024q1 Homework6 (integration)

contributed by < 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 核心模組運作原理




[ 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 前置作業

自我檢查清單

  • 實體電腦運行 GNU/Linux

    • Ubuntu 24.04 LTS

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

    〈Linux 核心模組運作原理〉列出的程式碼較舊，歡迎編輯頁面，更新到 Linux v6.1 以上。

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

    參照 2021 年的筆記。歡迎貢獻 LKMPG!
    \(\to\) 搭配閱讀〈並行和多執行緒程式設計〉

  • 探討 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 達到並行的排序;

Select a repo