學習linux kernel module，我是用qemu riscv來跑這次的範例程式一開始先記錄環境的配置與用到的工具。 下載gnu toolchain(編譯kernel和module)sudo apt install qemu-system-misc qemu-system-riscv 如果要做bare-metal programming可以下載 sudo apt install gcc-riscv64-unknown-elf (但是要小心很多linux kernel的功能就不能用，也不能用它來編kernel) 其他會用到的工具 sudo apt install make libncurses-dev flex bison libssl-dev bc

Completions 這邊書上解釋得很好就不多說了，跑出來的結果也符合預期 ~ # insmod workspace/completions.ko [ 12.746763] completions: loading out-of-tree module taints kernel. [ 12.750578] completions example [ 12.752543] Turn the crank [ 12.752878] Flywheel spins up 同步 我自己的理解是，不論mutex,spinlock,semaphore都是設計來保護一段程式碼的執行，至於為何要保護這段程式碼原因可能是

這裡要先回顧init script #!/bin/sh mount -t proc none /proc mount -t sysfs none /sys echo -e "\n\nWelcome to BusyBox RootFS on RISC-V!" /bin/sh 這一支程式run起來之後可以用ps -eo pid,ppid,sid,tty,comm查看現在有哪些process，以及他們的PID,PPID,SID,TTY,COMMAND。可能會像這樣 PID PPID SID TT COMMAND

Preliminaries 前面複習一些OS kernel/user space, system call，建議寫kernel module時，變數要設定static避免混用到kernel變數，也可以主動去註冊變數到kernel (/proc/kallsyms)，由於module是可以在kernel中動態插入或移除的程式碼，所以它共享kernel的程式碼空間，而不是有自己的空間。如果module發生segment fault，kernel也會掛掉。 寫driver時裝置分為兩種 character devices block devices 兩者的差異在於block devices有緩衝區。另外可以透過 ls -l 輸出中的第一個字元來判斷一個裝置檔案是用於block devices或character devices。如果是b則是block devices，如果是c則是character devices。

Blocking Processes and threads sleep (但我被搞到沒法sleep) 這邊利用tail -f持續read /proc/sleep 使得cat_nonblock被 if (file->f_flags & O_NONBLOCK) return -EAGAIN; 抓住，因此拋出異常。 然而，使用tail -f /proc/sleep &，tail會一直read /proc/sleep造成占用，因此會看到一直print出來Last input:，並且這個時候使用cat或echo "something" > /proc/sleep就會被卡住，直到tail -f /proc/sleep &的process被kill，一切乎也沒什麼，但是我再跑範例的時候出了大trouble。tail -f /proc/sleep &這一條指令並沒有直接show Last input:出來，反而是一直在後台run，困擾了我好久，測幾次之後發現如果開了兩個tail -f /proc/sleep &，接著將執行中(running time比較長)的那個process kill之後，另一個process才會正常print Last input:，起初還以為是我的電腦中邪了，仔細去觀察busybox 1.36.1版本的coreutils/tail.c，做了一些實驗後才發現問題。 沒做改動的結果:

題目大意: 給定一個字串，相鄰的兩個字元如果字母的大小差一可以一起消掉(a和z相鄰也可以消)?求出最小字典序的結果。 example: "rmlmlql" -> "l" "fcddccec" -> "fcdcec" 解法思路: 這題一看到就會想能不能用stack做，但總是不對，很多例外，轉個方向考慮怎麼dp，狀態怎麼設計都不對，從前面跑從後面跑都怪怪的(花了一堆時間QQ)，因為前面的結果會因為字串變長之後影響到(類似stack的概念)，左思右想只好試看看graph的方法，建圖的方式也很簡單，就是將可以消成空字元的片段記錄起來，假設"rmlmlql" (0-index) link[0][5] = 1 link[1][2] = 1

System Call 前面提到user program要用system call才能操作kernel space的資料，舉凡各種檔案操作，讀取kernel資訊像是時間或版本號等等。在舊的版本是用system call table維護syscall的function pointer，當呼叫syscall時才從這table取出對應的function pointer執行，這種方式又被稱作indirect call。 針對indirect call，硬體設計有類似if/else的branch predictor，叫做 Branch Target Buffer (BTB)，用來預測要跳轉執行的位置，使cpu pipeline減少不必要的等待。 為何要改成switch case的形式來跳到要執行的function? Spectre Attacks 先從這篇最後提供的範例了解x86架構下的Spectre attacks如何洩漏secret data 基礎概念 假設想要偷的資料secret位置是已知的，透過違法存取array1[x] 可以找到，例子中的x是array1 address 和secret address的距離，但是即便知道個位置，也只能使用branch predictor暫時的違法存取，在branch predictor校正回歸後還是拿不到secret address的值。所以這邊hacker很天才的利用cache不會被還原的機制找到一個漏洞，先建立一塊可以合法存取的buffer，一開始如果這塊buffer還沒load進cache裡面，程式去讀取它的時候會比較耗時。利用branch predictor錯誤時違法讀到的值來access這塊可以合法讀取的buffer，像是array2[array1[x] * 512];，如此一來，之後程式讀取array2[array1[x] * 512]的速度就會比讀取其他位置更快，利用時間差可以知道違法讀到的值array1[x]是什麼。

ioctl 為何要設定magic code?仔細看unlocked_ioctl在file_operations裡面是由driver決定的，command也是在device_ioctl定義的好好的，為何還要多此一舉#define IOCTL_SET_MSG _IOW(MAJOR_NUM, 0, char *)，而不是直接定義0,1,2,...就好。 避免user program使用錯誤的IOCTL_SET_MSG，假如使用者用A driver操作device file時誤以為自己使用的是B driver，他們又有共通的IOCTL_SET_MSG，就會不好除錯 如果後面的人想要將多個driver合併時會比較清楚不同code要做什麼 使用strace時比較不會出問題? 所以說magic code如果不分清楚，小規模的測試不會有問題，就是之後維護的人會比較麻煩? 順帶一提，這邊的user program要編譯時要這樣設定

sysfs: Interacting with your module 要看懂sysfs首先要了解的就是kobject，這邊附上doc連結 kobject 很重要必看，看完功力大增，考試100分 (source code) 按照前面的邏輯，底層的運作sysfs其實也是由類似inode和dentry去管理file的資訊和整個樹的結構，但是這裡要釐清一下sysfs和VFS之間還夾著kernfs，整個關係有點像是OOP裡面的繼承，VFS就是個抽象介面只要符合介面要求就能mount，kernfs定義了目錄的樹狀結構(kernfs_node組成的tree)以及kernfs_ops對應syscall的interface，權限控制，inode和dentry等等的細節，基本上kernfs就是一個符合VFS的平台，而sysfs只是借用這個平台維護kobject的一個特例，其他還有cgroupfs也是在kernfs上實現的。 kobject是階層化的樹狀資料結構，所以會有parent pointer，kobject的內容實際上是存在kernel module裏面的一些attribute，就像之前說/proc file一樣不是真的存在硬碟上的檔案，偽裝成檔案主要目的就是讓user program可以透過VFS(virtual file system)的interface(file_operations,proc_ops)去操作這些attribute，統一管理簡化邏輯，也避免不必要的安全風險。 具體的分析可以從kobject_create_and_add和sysfs_create_file這兩個function開始，kobject_create_and_add會造一個kobject並且連接上parent，並且在sysfs裡面產生一個directory代表這個kobject，當sysfs_create_file之後，那個directory下才看的到那個attribute的file，至於如何操作attribute file則是要定義sysfs_ops也可以用macro __ATTR(myvariable, 0660, myvariable_show, myvariable_store);設定，sys_ops可以對應到file_operations。

The /proc File System why proc_ops instead file_operations /proc底下放的檔案是為了user space program和kernel space program溝通，前面有講到file_operations這個結構，是為了讓device file應對不同syscall執行不同的函數，現在的proc_ops則是特別為了操作/proc底下的file設計，很像以前寫開檔讀檔那樣，只不過現在的問題是建立檔案的是kernel module，裡面的東西並不實際存在disk上面，它實際是一段kernel memory (可以在procfs3.c看出來，所有的操作都是對 static char procfs_buffer[PROCFS_MAX_SIZE];這塊記憶體)，所以用途也比較特殊，為了避免誤用一些syscall，proc_ops砍掉一些對kernel space memory來說不合理或危險的syscall，在較新的linux版本會強制要求使用proc_ops去控制proc file。 好處&目的 user space program依舊是透過syscall去讀寫檔案，kernel module讀到這些資訊就可以在kernel mode做出相對應的動作，以往user program要跟kernel溝通就只能透過syscall去操作，syscall又是寫死在kernel image的syscall table上，如果你想做一些kernel space複雜的操作，可能就要做很多次且很多種的syscall，這樣很沒效率，寫一個自己的syscall又要重新compile kernel太麻煩，所以如果將這些操作寫在kernel module裡面，user program就只要在proc_ops寫下要做什麼，一次寫檔就好，kernel module收到這筆命令去完成對應的複雜任務。其他用法還有紀錄kernel的訊息，方便debug之類的。 接下來要說的就是之前看過的put_user，類似的功能還有get_user, copy_from_user, copy_to_user，目的就是要將kernel space memory的內容送到user space memory，反之亦然，不能直接dereference pointer，因為是來自不同的memory block(也要避免user傳進非法的reference導致kernel crush)。

code 這篇主要紀錄一下如何使用OOP的概念去寫testbench，這裡我選擇寫一個testbench驗證 捲積兩個1-D array取模P的演算法 演算法概念 兩個長度為n的array捲積操作直觀的來說要O(n^2)的複雜度，利用FFT則可以達到O(nlogn)，但是要處理虛數和捨入誤差之類的問題實在太麻煩，且input的數值都是整數的情況可以考慮使用Number Theroem Transform去處理，控制好modulo P的大小(避免overflow)可以使整個操作都在整數域上，且複雜度也是O(nlogn)。 這邊我設定array的長度為256，在不同的模數P下捲積(cyclic convolution)。也可以用128長度的array(後面補0)做非循環捲積。 詳細理論推導可以查wiki

題目大意: 給定一個由數字組成字串(可以是0開頭) : num 將num重新排列，有多少排列方式是奇數位的總和與偶數為總和相等? 解法思路: 這題聞起來就很像上次讓我破大房的題目，幾乎有87%像 先統計每種數字有幾個: cnt = [0:10, 1:3, 2:4, ..., 9:3] // 10個'0',3個'1',4個2,....,3個9 dp會長這樣: `dp[i][m][sum]``:

題目大意: 給定一組int array : nums，以及int M和K 定義 seq : sequence seq 大小為 M (從int array可重複取M次) S = 2^(seq[0]) + 2^(seq[1]) + ... + 2^(seq[M-1])，S的二進位剛好有K個bits是1 prod(seq) = (nums[seq[0]] * nums[seq[1]] * ... * nums[seq[m - 1]]) 求所有滿足上面條件的prod(seq)的總和 解法思路:

題目大意: ​​​​給定一組int array，以及一些queries，每個query都有四個值`[index, value, start, x]`，會將array第`index`的數值改成`value`，求所有從`start`開始且乘積為x的子串數量。以上操作都是modulo一個給定的int k。 解法思路: [code] 從題目中大概可以看出是要搞range queries, BIT或Fenwick Tree之類的，但是難搞的部分就是range query的目標不是很直覺可以維護的，根據不同的開始位置就必須維護不同的Fenwick Tree，顯然是不會過的，更何況要update array的值，但這邊似乎也算是給個暗示，畢竟能做range update的操作選項也不多，肯定有甚麼東西要用fake segment tree去維護，最直覺的就是去維護區間的product，至此似乎還差一步，把兩個概念合併起來。 所以假設有一個結構可以O(logn)搜索/維護區間乘積，再觀察一下題目的限制，k最大只有5，也就是說可以將所有的餘數狀態個別存下來(一個餘數一個Fenwick Tree)，再再觀察一下，假設k=5，如果已經維護了每種子串乘積在[l,r]間有多少個，現在要求start開始結尾在[l,r]之間且乘積為4的子串數量，且start<l，[start,l-1]的乘積假設為3，(3*3)%5=4(mod 5)，所以[l,r]之間乘積為3的總數就會是這次query要的，所以要query的過程不同區間取的餘數會會不一樣，取決於[start,l-1]的乘積，蛋蛋蛋蛋蛋蛋蛋但是更新Fenwick Tree會很麻煩，因為一般用Fenwick Tree的range query是先求[0,r]再求[0,l-1]，再相減得到[l,r]的區間值，但是這樣必須對不需要的前綴逆操作，然而逆操作不一定總是存在(例如:0)，所以會無法推估餘數是從哪個餘數轉移回來的，硬是要使用的話要先將array翻轉才能處理要繞很大一圈，但是我就是個狒狒沒想到要如何一起處理，所以搞了醜醜的解法，且複雜度是O(n(logn)^2)。最簡單的方式是搭配fake segment tree一起維護區間乘積，許多題解都是用這種方式，且複雜度為O(nlogn)。 void dp_update(vector<vector<int>> &dp,vector<int>&tree,int pos,int v,int k,int n,int ts){ vector<int> buf = dp[pos]; int bup = pos+(pos&-pos),bdown = pos-(pos&-pos);

開發工具 $ gcc --version gcc (Ubuntu 11.4.0-1ubuntu1~22.04) 11.4.0 針對佇列排序的程式碼實作 q_sort 實作方式基於buttom up merge sort，一共寫了三個版本和改動linux kernel的list_sort.c來比較有無避免cache thrashing，由於要使用descend去決定遞增遞減，所以我將q_sort寫成: void q_sort(struct list_head *head, bool descend) { if (!head || list_empty(head))