林本然
記得先將 UEFI Secure Boot 關閉:UEFI Secure Boot 會確保只有經過簽章的模組才能被掛載到核心。為了方便掛載,我們先關閉。
先查看 Linux 核心版本,並且安裝相對應 linux-headers
套件(與 uname -r
同個版本),並確認安裝成功(根據自己的版本改命令)。
$ uname -r
$ sudo apt install linux-headers-`uname -r`
$ dpkg -L linux-headers-6.11.0-19-generic | grep "/lib/modules"
接下來要準備取得 ksort
原始碼,首先檢查一下使用者身份,目前的使用者和 root 應該是不同的。後續也會用 sudo
而避免直接用 root 輸入。
$ whoami
linmarc
$ sudo whoami
[sudo] password for linmarc:
root
安裝其他用得到的工具:
$ sudo apt install util-linux strace gnuplot-nox
取得原始程式碼然後編譯,預期會看到 2 次綠色的 Passed [-]
字樣
$ git clone https://github.com/sysprog21/ksort
$ cd ksort
$ make check
我執行完看起來是正常的,但並沒有出現 2 次綠色的 Passed [-]
字樣。
$ make check
(...)
sudo insmod sort.ko
sudo insmod xoro.ko
make[1]: Leaving directory '/home/linmarc/linux2025/ksort'
sudo ./user
Sorting succeeded!
sudo ./test_xoro
n_bytes=0 n_bytes_read=0 value=0000000000000000
n_bytes=1 n_bytes_read=1 value=000000000000005f
n_bytes=2 n_bytes_read=2 value=000000000000ed8e
n_bytes=3 n_bytes_read=3 value=0000000000747c6a
n_bytes=4 n_bytes_read=4 value=00000000c61be1dd
n_bytes=5 n_bytes_read=5 value=000000f069befa4a
n_bytes=6 n_bytes_read=6 value=0000ebab275f98f0
n_bytes=7 n_bytes_read=7 value=0042569408ac9f4b
n_bytes=8 n_bytes_read=8 value=16b355d705d7d6d7
n_bytes=9 n_bytes_read=8 value=0b7f14b4fc108855
make rmmod
make[1]: Entering directory '/home/linmarc/linux2025/ksort'
make[1]: Leaving directory '/home/linmarc/linux2025/ksort'
掛載模組 sort.ko
並觀察加載模組後得到的裝置檔案 /dev/sort
,根據 lkmpg 的 5.6 章,裝置檔案是用來與硬體溝通的,放在 /dev
開頭的 device file 當中。使用以下命令並觀察 /dev/sort
的輸出:
$ sudo insmod sort.ko
$ ls -l /dev/sort
crw------- 1 root root 510, 0 Mar 25 11:40 /dev/sort
數字間用逗號隔開,其中第一個數字 510
代表主設備號,第二個數字 0
代表次設備號。一個主設備號只會對應到一個 driver ,而且只要設備間的主設備號相同,代表他們由同一個 driver 控制。而同個 driver 控制的硬體裝置間則用次設備號去區分,代表是不同的設備。
此外裝置可分為 character device 和 block device,差別在於 block devices 有 buffer 可以排序 requests,但是 input 和 output 都只能以 block 為單位。而 character device 沒有 buffer,他可以接受不定長度的 bytes 作為輸入和輸出。觀察上面輸出的第一個字母,若為 b
則為 block device,若為 c
則為 character device 。由此可知 /dev/sort
是 character device。
在 sort_mod.c 裡面則是由 sort_init
裡面的這行程式碼負責註冊新的主設備到 kernel。根據 lkmpg 6.3 章提到:
Adding a driver to your system means registering it with the kernel. This is synonymous with assigning it a major number during the module's initialization.
而底下這個函式的定義也在同一章節被說明,此函式是分配 dynamic major number ,確保我們能從一段 major number 的範圍內,獲得一個未被使用的主設備號。
#define DEVICE_NAME "sort"
...
static int __init sort_init(void)
{
...
if (alloc_chrdev_region(&dev, 0, 1, DEVICE_NAME) < 0)
return -1;
...
}
int alloc_chrdev_region(dev_t *dev, unsigned int baseminor, unsigned int count, const char *name);
dev
:dev_t
型別的變數,為 u32
型別,即 32-bit 無號數,定義在 linux/include/linux/types.h
當中,一次包含了主設備號和次設備號。baseminor
:一個 driver 裡面的次設備號從 baseminor
開始。count
:要分配的裝置數量,次設備號是 baseminor
~ baseminor + count - 1
name
:裝置名稱,以此例就是 sort
。用以下指令可以查看模組版本,這和 sort_mod.c
透過 MODULE_VERSION
所指定的版本號碼相同,預期是 0.1
。
$ cat /sys/module/sort/version
TODO:搞懂 MODULE_VERISON
而用以下兩個命令可知道 sort.ko
目前的 reference counting = 0,根據 lkmpg 6.4 章,reference counter 代表現在有多少 processes 在使用這個模組,如果這個值不為 0 ,則在後續 rmmod
卸載模組時會失敗。
ksort
設計為一個 character device,可理解是個能夠循序存取檔案,透過定義相關的函式,可利用存取檔案的系統呼叫以存取 (即 open
, read
, write
, mmap
等等)。因此,使用者層級的程式可透過 read 系統呼叫來得到輸出,過程中變數 fd
就是 ksort
模組的 file descriptor,讓我們可以獲得 inbuf
中被 ksort
模組排序好的資料。
int fd = open(KSORT_DEV, O_RDWR);
...
size_t n_elements = 1000;
size_t size = n_elements * sizeof(int);
int *inbuf = malloc(size);
...
ssize_t r_sz = read(fd, inbuf, size);
sort_mod.c
的 sort_read
實作 user-space 用 read 呼叫取得排序結果,從 user-space 將資料複製到 kernel-space ,再複製回 user-space。其中每個函式的作用如下:
copy_from_user
:user-space buf
to sort_buffer
copy_to_user
:kernel-space sort_buffer
to buf
sort_main
:真正實作排序演算法的函式。static ssize_t sort_read(struct file *file,
char *buf,
size_t size,
loff_t *offset)
{
void *sort_buffer = kmalloc(size, GFP_KERNEL);
len = copy_from_user(sort_buffer, buf, size);
...
sort_main(sort_buffer, size / es, es, num_compare);
len = copy_to_user(buf, sort_buffer, size);
...
}
透過 Linux Virtual File System 介面,本核心模組可排序使用者層級指定的資料,並讓 client.c
程式得以存取。
VFS 提供一統各式檔案系統的共用介面,方便使用者操作不同的裝置或檔案時,可用一致的方式存取。Linux 的裝置驅動程式大致分為:
open
, close
, read
, write
等 system call利用 你所不知道的 C 語言:物件導向程式設計篇 的方法定義 VFS 相關操作的函式界面 struct file_operations
,並宣告結構變數 fops
藉此來讓使用者在 user-space 進行 read 呼叫時,對應到的是 ksort
已經實作好的 sort_read
。
struct file_operations {
struct module *owner;
loff_t (*llseek) (struct file *, loff_t, int);
ssize_t (*read) (struct file *, char __user *, size_t, loff_t *);
ssize_t (*write) (struct file *, const char __user *, size_t, loff_t *);
...
int (*open) (struct inode *, struct file *);
...
int (*release) (struct inode *, struct file *);
int (*fsync) (struct file *, loff_t, loff_t, int datasync);
int (*fasync) (int, struct file *, int);
int (*lock) (struct file *, int, struct file_lock *);
...
} __randomize_layout;
static const struct file_operations fops = {
.read = sort_read,
.write = sort_write,
.open = sort_open,
.release = sort_release,
.owner = THIS_MODULE,
};
跟計時有關的功能主要用在二種情境:
static void q_init()
{
fail_count = 0;
INIT_LIST_HEAD(&chain.head);
signal(SIGSEGV, sigsegv_handler); // segfault
signal(SIGALRM, sigalrm_handler); // timeout
}
其中一種計時方式是用作業系統從開機以來的計時器中斷發生的次數作為計時的依據,這個計時機制叫作 jiffies,很早就存在於 Linux 核心。較舊的 Linux 核心提供一個建議在 jiffies 上的計時機制,叫作 timer wheel,但 timer wheel 這個機制受限於計時器中斷觸發和實質能處理的的頻率,而這個頻率有其極限。
TODO:讀 Linux 核心設計: 中斷處理和現代架構考量
hrtimer
則是從 Linux 2.6.16 開始有的新的計時機制,裡面使用 ktime_t
這個新的資料結構來進行計時。跟大多數 Linux 中的資料結構使用機制類似,都要使用專門的函數來對這個資料型態進行操作,在 x86-64 中這是個 64 位元整數。相關的使用方式如下:
DEFINE_KTIME(name)
:很像 LIST_HEAD
之於 struct list_head
,宣告一個 ktime_t
並初始化成 0。ktime_add(ktime_t kt1, ktime_t kt2)
:相加ktime_sub(ktime_t kt1, ktime_t kt2)
:相減timespec_to_ktime(struct timespec tspec)
:把 timespec
(秒+奈秒) 換成 ktime_t
timeval_to_ktime(struct timeval tval)
:把 timeval
(秒+微秒) 換成 ktime_t
ktime_to_timespec(ktime_t kt)
:反向轉換ktime_to_timeval(ktime_t kt)
:反向轉換ktime_to_clock_t(ktime_t kt)
:ktime_t
換成 clock_t
ktime_to_ns(ktime_t kt)
:換成以奈秒為單位的 u64
整數實際用 ktime_t
的 API 測量 ksort
的時間,概念就是用 ktime_get()
取得開始和結束的時間戳並且互減,得到運行時間。
static long long sort_time_proxy(long long k)
{
kt = ktime_get();
long long result = sort_sequence(k);
kt = ktime_sub(ktime_get(), kt);
return result;
}
static ssize_t sort_read(struct file *file,
char *buf,
size_t size,
loff_t *offset)
{
return (ssize_t) sort_time_proxy(*offset);
}
現代 CPU 幾乎都是多核架構,通常在多核心的作業系統中常使用處理器的親和性 (processor affinity,亦稱 CPU pinning) 讓行程 (process) 在特定的 CPU 核中持續執行,不受作業系統排程的干擾。
查看所有進程的 pid
:
$ ps
根據當下正在跑的 process,預期得到以下輸出:
PID TTY TIME CMD
3616 pts/0 00:00:00 bash
8024 pts/0 00:00:00 ps
接下來針對 bash
的 pid 查看 processor affinity,使用參數 -p
可以指定行程,其中 -p
和 -cp
差別只在於要將可對應的 CPU 如何表示,ffff 換成二進位是 16 個 1 ,正好一個位元對應一顆 CPU,該位元為 1 則代表這個行程可以在該 CPU 上面跑,因此 ffff 就是對應第 0~15 CPU 皆可跑此行程。
$ taskset -p 3616
pid 3616's current affinity mask: ffff
$ taskset -cp 3616
pid 3616's current affinity list: 0-15
那如果要指定行程在特定的 CPU 上面運行,我們可以在 -p
後面加入 COREMASK
參數,用十六進制數字表示要跑在哪幾顆 CPU 上面,而 -cp
後面也一樣有 CORELIST
參數可用,以下兩種命令都是指定行程 3616 在第 0 個與第 4 個 CPU 核上面跑。
$ taskset -p 0x11 3616
$ taskset -cp 0,4 3616
如果要修改一個行程的處理器親和性,必須要有 CAP_SYS_NICE 這個權限,而如果只是查看就沒有限制。
CAP_SYS_NICE 的功能:
- 修改任意行程的 nice value
- 設定任意行程的處理器親和性
還有一個設定是如果你不想要讓其他的行程干擾你正在跑的行程,可以使用 isolcpus
這個 Linux 核心起始參數,讓指定的核心只能被自己設定的行程使用。因為這個參數可以讓特定的 CPU 核在開機時就被保存下來。
設定的方式有兩種,以下這種是直接在 GRUB 的設定檔加入參數,這樣 Linux 的排程器在預設的狀況下就不會將任何一般行程放在這個被保留的 CPU 核中執行,只有那些被 taskset 特別指定的行程可使用這些 CPU 核。
isolcpus=0,1
代表保留第 0 和第 1 顆 CPU 核。$ sudo nano /etc/default/grub
$ GRUB_CMDLINE_LINUX_DEFAULT="quiet splash isolcpus=0,1"
$ sudo update-grub
$ sudo reboot
之後要跑行程,我們就可以用 taskset
命令來指定已被 isolcpus
保留的 CPU 核運行。
$
林志芸
邱繼寬
Brian
概念:把精度為 n 的浮點數向右位移 n 個位元
假設兩個精度為 n 的 2 進位浮點數 a, b
其定點數表達為
在轉換過程多乘了一個
同理發生在除法運算
fixed_power_int
解析理解為在定點數的框架下做計算, 這也是為什麼需要在乘法後做校正
值得一提的是這行
x += 1UL << (frac_bits - 1)
個人認為是做四捨五入讓右移時不會造成誤差大於單位的一半
意義:表示系統的負載量而非 cpu 的負載
系統在顯示的load average則是移動平滑後的結果
在load avg 中使用exponential moving average來作為load的計算
所以上述公式的
#define FSHIFT 11 /* nr of bits of precision */
#define FIXED_1 (1<<FSHIFT) /* 1.0 as fixed-point */
#define LOAD_FREQ (5*HZ+1) /* 5 sec intervals */
#define EXP_1 1884 /* 1/exp(5sec/1min) as fixed-point */
#define EXP_5 2014 /* 1/exp(5sec/5min) */
#define EXP_15 2037 /* 1/exp(5sec/15min) */
calc_global_load 函數就是根據指數移動平滑平均和定點數運算在5秒一個間隔去更新load avg 1,5,15的值
每列總和為1的轉移矩陣就是右隨機矩陣(right stochastic matrix)
折扣總和(discount sum)定義如下:
為什麼需要一個
自己的對這個discount的見解是下個動作之外的未來是不確定的,所需要對在這個時間點所知的報酬打折扣
在狀態s的折扣回報我們可以分成兩個部分來計算
第一個部分是選擇下一個步驟的回報s'
另一個是s'之後的每個步驟s'', s''', …,
其實這個回報就是
這樣還是有點難懂 所以去找了一些解說
Bellman Equation
Value Iteration
利用每次迭代選擇的最佳步驟 至V(s)的值收斂
左邊狀態的回報計算
第一輪:
第二輪:
右邊狀態回報計算
第一輪:
第二輪:
以此類推,終止條件是當兩輪的結果收斂
然後選出得到折扣報酬最大的動作
這個方法的必須先知道選擇動作的機率,在實務上可能是未知的
所以在專案ttt裡面的強化學習實作是使用時間差分學習
總結就是如同筆記的這句話
強化學習的核心目標是學習最佳的 𝜋,以最大化𝑉𝜋(𝑠),並透過探索與利用(exploration vs. exploitation)策略來達成最優解。
學習的目標: 價值函式
以ttt為例, 我們學習的是在某個棋盤狀態下剩餘可以放子的格子的價值
這個更新公式的關鍵想法是:目前狀態的價值應該向「即時獎勵 + 折扣後的下一狀態價值」靠攏
往下看括號項
意義是實際觀察到的狀態期望扣除當下預期期望,
換句話說,我們看到的比預期的好,遞迴狀態價值就加上學習率*
主要關注兩個檔案
**int get_action_exploit(char table, rl_agent_t agent)
int get_action_exploit(char *table, rl_agent_t *agent)
{
int max_act = -1;
float max_q = -FLT_MAX;
float *state_value = agent->state_value;
int candidate_count = 1;
#ifdef VERBOSE
printf("[ ");
#endif
// 列舉每一個可放棋子的狀態
for_each_empty_grid (i, table) {
table[i] = agent->player; //棋手是誰
float new_q = state_value[table_to_hash(table)];
#ifdef VERBOSE
printf("%f ", new_q);
#endif
if (new_q == max_q) {
++candidate_count;
if (rand() % candidate_count == 0) {
max_act = i;
}
} else if (new_q > max_q) {
candidate_count = 1;
max_q = new_q;
max_act = i;
}
table[i] = ' ';
}
#ifdef VERBOSE
printf(" ]\n");
printf("exploit %d\n", max_act);
#endif
return max_act;
}
*int table_to_hash(char table)
char *hash_to_table(int hash)
static float update_state_value
這個函式就是TD learning的遞迴函式
static float update_state_value(int after_state_hash,
float reward,
float next,
rl_agent_t *agent)
{
float curr = reward - GAMMA * next; // 不懂為啥是減
agent->state_value[after_state_hash] =
(1 - LEARNING_RATE) * agent->state_value[after_state_hash] + // 提項V(S_t)
LEARNING_RATE * curr;
#if MONTE_CARLO
return curr;
#else
return agent->state_value[after_state_hash];
}
static void train
訓練的主函式
這裡埰用兩種方法去實作下一步該往哪走
static void train(int iter)
{
int episode_moves[N_GRIDS]; // from 0 moves to N_GRIDS moves.
float reward[N_GRIDS];
int episode_len = 0;
char table[N_GRIDS];
memset(table, ' ', N_GRIDS);
int turn = (iter & 1) ? 0 : 1; // 0 for 'O', 1 for 'X'
char win = ' ';
while (1) {
if (win == 'D') {
#ifdef VERBOSE
draw_board(table);
printf("It is a draw!\n");
#endif
break;
} else if (win != ' ') {
#ifdef VERBOSE
draw_board(table);
printf("%c won!\n", win);
#endif
break;
}
#if EPSILON_GREEDY
int move = get_action_epsilon_greedy(table, &agent[turn]);
#else
int move = get_action_exploit(table, &agent[turn]);
#endif
table[move] = "OX"[turn]; // update move to the table array
win = check_win(table);
episode_moves[episode_len] = table_to_hash(table);
reward[episode_len] =
(1 - REWARD_TRADEOFF) * get_score(table, agent[turn].player) +
REWARD_TRADEOFF * calculate_win_value(win, agent[turn].player); // update reward
++episode_len;
#ifdef VERBOSE
draw_board(table);
#endif
turn = !turn;
}
//
turn = !turn; // the player who makes the last move.
float next = 0;
for (int i_move = episode_len - 1; i_move >= 0; --i_move) {
next = update_state_value(episode_moves[i_move], reward[i_move], next,
&agent[turn]);
}
}
步驟:
sudo bpftrace -e '
tracepoint:syscalls:sys_enter_openat
/str(args->filename) == "/dev/simrupt"/
{
printf("Opened /dev/simrupt by pid=%d, comm=%s\n", pid, comm);
}'
開另一個視窗執行以下命令
sudo touch /dev/simrupt
會得到類似的輸出:
Attaching 1 probe...
Opened /dev/simrupt by pid=438455, comm=touch
comm
為目前執行緒的 command name,對應於核心結構 task_struct 中的 comm 欄位,用以判斷此時執行該函式的行程名稱。
可注意到
tasklet_func: comm=bash, pid=3922, tid=362706
work_func: comm=kworker/u80:5, pid=435034, tid=435034
tasklet_func: comm=bash, pid=3922, tid=362706
work_func: comm=kworker/u80:5, pid=435034, tid=435034
tasklet_func: comm=bash, pid=3922, tid=362706
work_func: comm=kworker/u80:5, pid=435034, tid=435034
tasklet_func: comm=bash, pid=3922, tid=362706
work_func: comm=kworker/u80:5, pid=435034, tid=435034
tasklet_func: comm=bash, pid=3922, tid=362706
work_func: comm=kworker/u80:5, pid=435034, tid=435034
tasklet_func: comm=bash, pid=3922, tid=362706
work_func: comm=kworker/u80:5, pid=435034, tid=435034
tasklet_func: comm=bash, pid=3922, tid=362706
work_func: comm=kworker/u80:1, pid=437008, tid=437008
tasklet_func: comm=bash, pid=3922, tid=362706
work_func: comm=kworker/u80:1, pid=437008, tid=437008
tasklet_func: comm=bash, pid=3922, tid=362706
work_func: comm=kworker/u64:3, pid=9329, tid=9329
tasklet_func: comm=ksoftirqd/10, pid=56, tid=56
work_func: comm=kworker/u64:3, pid=9329, tid=9329
tasklet_func: comm=ksoftirqd/9, pid=50, tid=50
work_func: comm=kworker/u64:2, pid=8536, tid=8536
tasklet_func: comm=swapper/9, pid=0, tid=0
work_func: comm=kworker/u64:2, pid=8536, tid=8536
tasklet_func: comm=ksoftirqd/0, pid=16, tid=16
work_func: comm=kworker/u64:2, pid=8536, tid=8536
tasklet_func: comm=swapper/10, pid=0, tid=0
work_func: comm=kworker/u64:2, pid=8536, tid=8536
tasklet_func: comm=swapper/4, pid=0, tid=0