2024q1 Homework6 (integration)

contributed by < MathewSu-001 >

自我檢查清單

研讀前述 Linux 效能分析 描述，在自己的實體電腦運作 GNU/Linux

閱讀〈Linux 核心模組運作原理〉

• 建構核心模組
  參照程式碼準備，在編譯核心模組的命令:

$ make -C /lib/modules/`uname -r`/build M=`pwd` modules

遇到問題如下：

make: Entering directory '/usr/src/linux-headers-6.5.0-28-generic'
warning: the compiler differs from the one used to build the kernel
  The kernel was built by: x86_64-linux-gnu-gcc-12 (Ubuntu 12.3.0-1ubuntu1~22.04) 12.3.0
  You are using:           gcc-12 (Ubuntu 12.3.0-1ubuntu1~22.04) 12.3.0
  CC [M]  /home/robotics/linux2024/test/hello.o
  MODPOST /home/robotics/linux2024/test/Module.symvers
  CC [M]  /home/robotics/linux2024/test/hello.mod.o
  LD [M]  /home/robotics/linux2024/test/hello.ko
  BTF [M] /home/robotics/linux2024/test/hello.ko
Skipping BTF generation for /home/robotics/linux2024/test/hello.ko due to unavailability of vmlinux
make: Leaving directory '/usr/src/linux-headers-6.5.0-28-generic'

參考 Ubuntu 22.04 default GCC version does not match version that built latest default kernel 與 yehsudo同學後，使用 ls /usr/bin/ -l，我的 gcc-12 是連結 x86_64-linux-gnu-gcc-12 的，所以兩個 gcc 版本是一樣的，所以忽略了這個警告。

$ ls /usr/bin/ -l | grep gcclrwxrwxrwx  1 root root          23 May 13  2023 gcc-12 -> x86_64-linux-gnu-gcc-12

• 掛載核心模組

掛載編譯出來的模組：

$sudo insmod hello.ko

接著查看是否掛載成功：

$sudo dmesg
[270903.022663] Hello, world

• 卸載核心模組

卸載稍早載入的 hello 核心模組:

$ sudo rmmod hello

$sudo dmesg
[270903.022663] Hello, world
[289976.421080] Goodbye, cruel world

• 觀察 fibdrv.ko 核心模組在 Linux 核心掛載後的行為

要先透過 insmod 將模組載入核心後才會有下面的裝置檔案 /dev/fibonacci

$ ls -l /dev/fibonacci
$ cat /sys/class/fibonacci/fibonacci/dev
511:0

與預期輸入數字 256 有出入。試著對照 fibdrv.c，找尋彼此的關聯。
發現到與 register_chrdev有關

以修訂過的 LKMPG 為主要參照標的。

閱讀 Character Device drivers 該篇，我學到了輸出 511 代表 major number ，表示現在驅動程式是處理哪個 device file；0 代表 minor number ，用在以防驅動程式一次處理多個時，不知是哪個 device file。用來產生 major number 的函式為 register_chrdev

int register_chrdev(unsigned int major, const char *name, struct file_operations *fops);

當註冊一個字符設備時，避免使用重複的主要設備號（major number）是至關重要的。register_chrdev 函式提供了一種便利的方法來動態分配主要設備號，確保設備的唯一性，同時減少了衝突的風險。這種動態分配的主要好處在於簡化了裝置驅動程序的開發過程，因為開發者無需手動管理主要設備號的分配。如果註冊失敗，則返回一個負值，表明註冊操作未能成功完成，通常是因為出現了錯誤或者註冊的條件不符合系統的要求。

int rc = 0;
mutex_init(&fib_mutex);

// Let's register the device
// This will dynamically allocate the major number
rc = major = register_chrdev(major, DEV_FIBONACCI_NAME, &fib_fops);
if (rc < 0) {
    printk(KERN_ALERT "Failed to add cdev\n");
    rc = -2;
    goto failed_cdev;
}

• 解釋 insmod

fibdrv.ko 不是能在 shell 呼叫並執行的執行檔，它只是 ELF 格式的 object file。因此我們需要透過 insmod 這個程式（可執行檔）來將 fibdrv.ko 植入核心中。kernel module 是執行在 kernel space 中，但是 insmod fibdrv.ko 是一個在 user space 的程序，因此在 insmod 中應該需要呼叫相關管理記憶體的 system call，將在 user space 中 kernel module 的資料複製到 kernel space 中。

我自己有觀查到，可以利用 ls /dev 來檢測 sudo insmod name.ko 有沒有註冊成功，如果有的話 name 會出現在上面。

• MODULE_LICENSE 巨集指定的授權條款對核心的影響

以 MODULE_LICENSE("Dual MIT/GPL") 為例，被展開後的 __stringify(tag) "=" info 會是 "license = Dual MIT/GPL" 字串。

總結這部份，MODULE_XXX 系列的巨集在最後都會被轉變成

static const char 獨一無二的變數[] = "操作 = 參數"

再放到 fibdrv.ko 中 .modinfo 對應區段中。

• strace 追蹤 Linux 核心的掛載

$ sudo strace insmod fibdrv.ko
execve("/usr/sbin/insmod", ["insmod", "fibdrv.ko"], 0x7fffffffe548 /* 27 vars */) = 0
brk(NULL)                               = 0x55555557f000
arch_prctl(0x3001 /* ARCH_??? */, 0x7fffffffe360) = -1 EINVAL (Invalid argument)
mmap(NULL, 8192, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0) = 0x7ffff7fbb000
access("/etc/ld.so.preload", R_OK)      = -1 ENOENT (No such file or directory)
openat(AT_FDCWD, "/etc/ld.so.cache", O_RDONLY|O_CLOEXEC) = 3
newfstatat(3, "", {st_mode=S_IFREG|0644, st_size=149499, ...}, AT_EMPTY_PATH) = 0
mmap(NULL, 149499, PROT_READ, MAP_PRIVATE, 3, 0) = 0x7ffff7f96000
close(3)                                = 0
...
close(3)                                = 0
getcwd("/home/robotics/linux2024/fibdrv", 4096) = 32
newfstatat(AT_FDCWD, "/home/robotics/linux2024/fibdrv/fibdrv.ko", {st_mode=S_IFREG|0664, st_size=274800, ...}, 0) = 0
openat(AT_FDCWD, "/home/robotics/linux2024/fibdrv/fibdrv.ko", O_RDONLY|O_CLOEXEC) = 3
read(3, "\177ELF\2\1", 6)               = 6
lseek(3, 0, SEEK_SET)                   = 0
newfstatat(3, "", {st_mode=S_IFREG|0664, st_size=274800, ...}, AT_EMPTY_PATH) = 0
mmap(NULL, 274800, PROT_READ, MAP_PRIVATE, 3, 0) = 0x7ffff7e56000
finit_module(3, "", 0)                  = -1 EEXIST (File exists)
write(2, "insmod: ERROR: could not insert "..., 62insmod: ERROR: could not insert module fibdrv.ko: File exists
) = 62
munmap(0x7ffff7e56000, 274800)          = 0
close(3)                                = 0
exit_group(1)                           = ?
+++ exited with 1 +++

閱讀《The Linux Kernel Module Programming Guide》

在這之前，因為我對於 Linux 核心的並行處理還是摸不著頭緒，所以 kkkkk1109 同學推薦給我一個影片有幫助到我更了解到何謂並行處理，會遇到甚麼問題，以及後續會產生 deadlock 的問題該怎麼解決。

4 Hello World

4.3 中，有提到

These macros are defined in include/linux/init.h and serve to free up kernel memory. When you boot your kernel and see something like Freeing unused kernel memory: 236k freed, this is precisely what the kernel is freeing.

不過在運行程式碼 hello-3.c 後，

/* 
 * hello-3.c - Illustrating the __init, __initdata and __exit macros. 
 */ 
#include <linux/init.h> /* Needed for the macros */ 
#include <linux/module.h> /* Needed by all modules */ 
#include <linux/printk.h> /* Needed for pr_info() */ 
 
static int hello3_data __initdata = 3; 
 
static int __init hello_3_init(void) 
{ 
    pr_info("Hello, world %d\n", hello3_data); 
    return 0; 
} 
 
static void __exit hello_3_exit(void) 
{ 
    pr_info("Goodbye, world 3\n"); 
} 
 
module_init(hello_3_init); 
module_exit(hello_3_exit); 
 
MODULE_LICENSE("GPL");

出來的成果

$sudo dmesg
[982262.268455] Hello, world 3

似乎沒有顯示任何相關釋放記憶體的內容。

在這章，我學到如何建立最簡單的核心模組。如果需要運作的話，最少需要用到兩個函式 init_module() 以及 cleanup_module() ，從版本 2.3.13 後可透過兩個巨集module_init() 和 module_exit() 來自定義函式名稱。另外可以使用巨集 module_param() 來宣告變數，不過沒有很懂可以實際應用在何處。

5 Preliminaries

理解 User Space 和 Kernel Space 的差別，再呼叫函式(如 printf())是調動到 Kernel Space 裡的 write() 去輸出。

每一個硬體都可以由設備檔來表示，分別為 major用來告訴使用者是哪個驅動程式來控制硬體； minor 則是用來讓驅動程式在擁有相同 major 時得以區分不同硬體。另外，每個 device 可以被區分為兩種: character devices 和 block devices，兩種最大差別為 block devices 的大小會隨著 device 而有所限制；但是 character devices 的位元較為自由，因此大部分都是 character devices。

6 Character Device drivers

學習到 character device 如果需要註冊進入 kernel 裡，需要被分配一個 major 編號。如果要確保該編號沒有被使用的話 ，可以利用 register_chedev 來被分配一個動態編號；亦或者使用 register_chrdev_region 以及 alloc_chrdev_region 減少佔用資源。

此外，我們會需要一個 file_operation 來保存由驅動程式定義的指向各種設備操作函數(如 open、read 等)的指針。架構如下所示：

struct file_operations fops = { 
    .read = device_read, 
    .write = device_write, 
    .open = device_open, 
    .release = device_release 
};

實測 chardev.c

$sudo dmesg
[334113.951089] I was assigned major number 510.
[334113.951231] Device created on /dev/chardev

$ cat /proc/devices | grep chardev
510 chardev

測試如果開啟 /dev/chardev

$sudo cat /dev/chardev 
I already told you 7 times Hello world!

1. 在閱讀 chardev.c 裡的程式碼時，還是沒有很懂 device_read 跟 device_write 是如何實際應用在 kernel 裡，用途會是什麼
2. struct cdev 的存在，以及相對應的函式用途為何不清楚

7 The /proc File System

本章要在介紹在 Linux 還有一個附加機制提供內核和內核模塊之間傳遞訊息 – /proc 系統。與前面的核心模組比較不同的是：讀取函式是用來輸出訊息，但寫入函式用於輸入。原因在於如果一個進程從內核讀取某些內容，那麼內核需要輸出它；而如果一個進程向內核寫入某些內容，那麼內核接收它作為輸入。

在實作上，我有分別將 procfs.c 一到三版都裝進核心模組裡，不過似乎沒有達到預期的結果，以 procfs2.c 為例

$cat /proc/buffer1k
HelloWorld!
$sudo dmesg
[532534.282581] /proc/buffer1k created
[532543.620855] procfile read buffer1k
[532543.620871] copy_to_user failed

不知道為何會出現 failed 的情況。

另外還有一個叫 seq_file 的 API 可以幫助編寫 /proc檔案。以下為實作 procfs4.c 結果：

$sudo insmod procfs.ko
$cat /proc/iter
0
$cat /proc/iter
1
$cat /proc/iter
2

8 sysfs: Interacting with your module

透過 sysfs 能夠從用戶空間與運行中的內核通過讀取或設置模塊內的變量進行交互。

• 解讀 hello-sysfs.c

透過 __ATTR（）來定義 sysfs的屬性，根據 include/linux/sysfs.h

#define __ATTR(_name, _mode, _show, _store) {				\
	.attr = {.name = __stringify(_name),				\
		 .mode = VERIFY_OCTAL_PERMISSIONS(_mode) },		\
	.show	= _show,						\
	.store	= _store,						\
}

來找到對應讀取(.show) 和寫入(.store) 的函式，所以在程式碼中 myvariable_show 將 myvariable 的值化為字符並寫入 buf ； myvariable_store 讀取 buf 並存入 myvariable 裡。

再來是創建一個目錄在 sysfs 結構裡，根據 Everything you never wanted to know about kobjects, ksets, and ktypes 可以利用 kobject_create_and_add 來創建一個簡單的目錄。

struct kobject *kobject_create_and_add(const char *name, struct kobject *parent)

不過這邊我就沒有很懂程式碼中

mymodule = kobject_create_and_add("mymodule", kernel_kobj); 

kernel_kobj 是從哪裡跑出來的，在整個程式碼中都沒有定義到。Driver Basics 裡有提到

struct kobject *parent
the parent kobject of this kobject, if any.

不過就不是很懂意思。

實做結果

$sudo lsmod | grep hello_sysfs
hello_sysfs            12288  0
$sudo cat /sys/kernel/mymodule/myvariable
0
$echo "32" | sudo tee /sys/kernel/mymodule/myvariable 
$sudo cat /sys/kernel/mymodule/myvariable
32

9 Talking To Device Files

如果要讓 process 與設備檔相互溝通的話，可以使用 device_write 來完成的，不過在 UNIX 裡還有一個特殊函式叫做 ioctl 也可以做到。

10 System Calls

如果 process 要向內核所求服務(讀取檔案、請求新的記憶體等)的話，就會需要透過 System Calls。它是一般規則的例外。System Calls 可以讓使用者不再受限於用戶模式下，而是作為作業系統核心運行。

運行 syscall-steal.c 的結果

$ sudo grep sys_call_table /proc/kallsyms
ffffffffa9000300 D sys_call_table
$ sudo insmod syscall-steal.ko sym=0xffffffff820013a0
$ sudo grep sys_call_table /proc/kallsyms
ffffffffa9000300 D sys_call_table
ffffffffc226f130 t acquire_sys_call_table       [syscall_steal]
ffffffffc2271548 b sys_call_table_stolen        [syscall_steal]
ffffffffc226f120 t __pfx_acquire_sys_call_table [syscall_steal]

與書本上寫的結果不盡相同

-ffffffffa9000300 D sys_call_table
+ffffffff82000300 R sys_call_table

不知道 D 跟 R 分別代表的含意，然後在嵌入 syscall-steal.ko 後，得到的結果也不知道什麼意思。

11 Blocking Processes and threads

當有多個進程同時呼叫一個核心模組時，內核會會透過 sleep 的方法將其他進程設置為睡眠狀態並加進 WaitQ ，等到目前的進程運行完畢後再喚醒下一個。

while (atomic_cmpxchg(&already_open, 0, 1)) { 
    int i, is_sig = 0; 

    wait_event_interruptible(waitq, !atomic_read(&already_open));
    
    for (i = 0; i < _NSIG_WORDS && !is_sig; i++) 
        is_sig = current->pending.signal.sig[i] & ~current->blocked.sig[i]; 

    if (is_sig) { 
        module_put(THIS_MODULE); 
        return -EINTR; 
} 

module_open 可以判斷有沒有其他進程會打擾，透過 return -EAGAIN 來中斷其他進程。不過 is_sig 的用途及用法我沒有很瞭解。

運行 sleep.c 的結果，透過指令 tail -f [file] 用於實時查看指定文件的末尾部分

$ ./cat_nonblock /proc/sleep 
Last input:
$ tail -f /proc/sleep &
[3] 1464856
Last input:
Last input:
$ ./cat_nonblock /proc/sleep 
Open would block

可以看到重新查看 /proc/sleep 的話，就會發現被阻擋。查看後台進程

$ jobs
[2]+  Stopped                 ./fixed  (wd: ~/linux2024)
[3]-  Running                 tail -f /proc/sleep &

如果要關掉的話，有別於書上寫的，需要改寫成 kill %3 來終止作業號為 3 的後台進程。並且再次查看後台進程可以看到有確實中止掉

$ kill %3
[3]-  Terminated              tail -f /proc/sleep
$ jobs
[2]+  Stopped                 ./fixed  (wd: ~/linux2024)

如果在擁有多個線程中，想要確保某個事件要在另一個事件前發生的話，可以利用 wait_for_completion()。

運行 completions.c 的結果

$ sudo insmod completions
$ sudo dmesg
[2522084.118374] completions example
[2522084.118453] Turn the crank
[2522084.118460] Flywheel spins up

12 Avoiding Collisions and Deadlocks

如果有多個進程嘗試存取相同的記憶體，則可能會發生存取錯誤的問題。因此 linux 提供多種 mutex 的方法來進行解鎖與開鎖的動作。

• mutex

在 linux/mutex.c 中，有定義 mutex_trylock 的功用

Try to acquire the mutex atomically. Returns 1 if the mutex has been acquired successfully, and 0 on contention.

因此可以透過此函式來確定有沒有被鎖上。

• spinlock

透過自旋鎖，會鎖定正在執行程式碼的 CPU，佔用其 100% 的資源。

追蹤 spin_lock_irqsave 的用法，從 linux/spinlock.h 可以得知

#define raw_spin_lock_irqsave(lock, flags) \
do {					     \
    typecheck(unsigned long, flags);	     \
    flags = _raw_spin_lock_irqsave(lock);  \
} while (0)

#define spin_lock_irqsave(lock, flags)     \
do {								\
	raw_spin_lock_irqsave(spinlock_check(lock), flags);	\
} while (0)

再往前追朔到 locking/spinlock.c

#ifndef CONFIG_INLINE_SPIN_LOCK_IRQSAVE
noinline unsigned long __lockfunc _raw_spin_lock_irqsave(raw_spinlock_t *lock)
{
	return __raw_spin_lock_irqsave(lock);
}
EXPORT_SYMBOL(_raw_spin_lock_irqsave);
#endif

繼續追朔到 linux/spinlock_api_smp.h

static inline unsigned long __raw_spin_lock_irqsave(raw_spinlock_t *lock)
{
	unsigned long flags;

	local_irq_save(flags);
	preempt_disable();
	spin_acquire(&lock->dep_map, 0, 0, _RET_IP_);
	LOCK_CONTENDED(lock, do_raw_spin_trylock, do_raw_spin_lock);
	return flags;
}

閱讀 Linux 核心設計: Interrupt 得知 local_irq_save 的用途為將狀態存入一個 Interrupt flag 並且關閉 interrupt； 追蹤 spin_unlock_irqrestore 到 linux/spinlock_api_smp.h 可以找到函式 local_irq_restore ，其功用會回存 flag，回復到 local_irq_save 之前的狀態。

透過 spinlock 可以確保不會有其他進程搶佔的問題，程式碼獨占 CPU 的情況就稱作 atomic contexts，但是需確保沒有含有任何休眠的函數。

• read and write locks
  用法跟 spinlock 差不多，不同的是可以獨佔讀取某些內容或寫入某些內容。

在本篇段落末尾，有提到說如果不會觸發 irq 的話，可以將 read_lock_irqsave(&myrwlock, flags); 替換為 read_lock(&myrwlock) 。但這邊不太了解 irq 是什麼？

• Atomic operations

如果想要確保在進行算術時，不會受到其他多現成影響，可以使用 atomic operations 。

執行 example_atomic.c 結果

$ sudo insmod example_atomic.ko 
$ sudo dmesg
[82985.280558] example_atomic started
[82985.280560] chris: 50, debbie: 52
[82985.280561] Bits 0: 00000000
[82985.280562] Bits 1: 00101000
[82985.280562] Bits 2: 00001000
[82985.280563] Bits 3: 00000000
[82985.280563] Bits 4: 00001000
[82985.280564] Bits 5: 11111111

作業主題二: 整合井字遊戲對弈

期末專題影片

整合 tic-tac-toe 遊戲

在整合之前，先實做 作業三 出來。已經完成的步驟有轉換為定點數數算，電腦與電腦對奕的演算法其一為 MCTS，另一者參照作業三後選擇 negamax。

整合 tic-tac-toe 遊戲

fork simrupt 並且與作業三整合

• 解析程式碼 simrupt.c

初始化函式 simrupt_init 首先透過 alloc_chrdev_region 向核心註冊設備號碼。

 /* Register major/minor numbers */
ret = alloc_chrdev_region(&dev_id, 0, NR_SIMRUPT, DEV_NAME);
if (ret)
    goto error_alloc;
major = MAJOR(dev_id);

同一個初始化函式裡，在 13.2 Flashing keyboard LEDs 中提到，可以透過 timer_setup 初始化計時器，並指定處理函式 timer_handler。

/* Setup the timer */
timer_setup(&timer, timer_handler, 0);
atomic_set(&open_cnt, 0);

於是，當在終端機輸入 cat /dev/simrupt 時，會觸發 simrupt_open 函式。此時，透過 atomic_inc_return 檢查是否為第一次打開文件，如果條件成立，便會執行 mod_timer 指令。根據 How to use timers in Linux kernel device drivers? 的說明，該函式用於設置計時器 timer，並且根據前述設置，將觸發 timer_handler 函式來執行其內部內容。

static int simrupt_open(struct inode *inode, struct file *filp)
{
    pr_debug("simrupt: %s\n", __func__);
    if (atomic_inc_return(&open_cnt) == 1)
        mod_timer(&timer, jiffies + msecs_to_jiffies(delay));
    pr_info("openm current cnt: %d\n", atomic_read(&open_cnt));

    return 0;
}

timer_handler 函式會禁用本地中斷並呼叫 process_data，並且利用 mod_timer 在每次觸發後都會重新設置為在下一個 delay time 後觸發，以此達到循環。在將新數據放入快速循環緩衝區（fast buf）後，根據 14.1 Tasklets 的內容，我們可以了解到，利用巨集 DECLARE_TASKLET_OLD，當執行到 tasklet_schedule 後，會呼叫 simrupt_tasklet_func 函式。

/* Tasklet for asynchronous bottom-half processing in softirq context */
static DECLARE_TASKLET_OLD(simrupt_tasklet, simrupt_tasklet_func);

static void process_data(void)
{
    WARN_ON_ONCE(!irqs_disabled());

    pr_info("simrupt: [CPU#%d] produce data\n", smp_processor_id());
    fast_buf_put(update_simrupt_data());

    pr_info("simrupt: [CPU#%d] scheduling tasklet\n", smp_processor_id());
    tasklet_schedule(&simrupt_tasklet);
}

透過巨集 DECLARE_WORK 宣告一個 workqueue 項目，並指派一個處理函式 simrupt_work_func 給它。當工作佇列中的項目被執行時，simrupt_work_func 函數會被呼叫。這個函數會從快速循環緩衝區中提取數據，並透過 produce_data 函數將其放入 kfifo 緩衝區中。

/* Workqueue for asynchronous bottom-half processing */
static struct workqueue_struct *simrupt_workqueue;

/* Workqueue handler: executed by a kernel thread */
static void simrupt_work_func(struct work_struct *w)
{
    
    ...

    while (1) {
        /* Consume data from the circular buffer */
        mutex_lock(&consumer_lock);
        val = fast_buf_get();
        mutex_unlock(&consumer_lock);

        if (val < 0)
            break;

        /* Store data to the kfifo buffer */
        mutex_lock(&producer_lock);
        produce_data(val);
        mutex_unlock(&producer_lock);
    }
    wake_up_interruptible(&rx_wait);
}

現在有點被搞混，快速循環緩衝區 fast_buf ,workqueue 跟 kfifo 緩衝區的差別是什麼以及各自的用途？

Linux 核心的並行處理

那麼放入 kfifo 的資料是怎麼顯示在 userspace 上的呢？

在 simrupt_read 函數中，會使用 wait_event_interruptible 函式進行等待。當在 simrupt_work_func 函數中使用 wake_up_interruptible 觸發時，將會喚醒所有在等待隊列上的任務。這時，將會把 rx_fifo 中的資料打印到 userspace 上

do {
        ret = kfifo_to_user(&rx_fifo, buf, count, &read);
        if (unlikely(ret < 0))
            break;
        if (read)
            break;
        if (file->f_flags & O_NONBLOCK) {
            ret = -EAGAIN;
            break;
        }
        ret = wait_event_interruptible(rx_wait, kfifo_len(&rx_fifo));
    } while (ret == 0);

實際跑過 simrupt.c 程式的結果如下

$sudo cat /dev/simrupt
^abcdefghijklmnopqrstuvwxyz{|}~ !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQR

• 如何與作業三做整合？

參閱 vax-r 同學的程式碼後，我發現要將數據存儲在 kfifo 中的 rx_fifo，然後透過 simrupt_read 函數來提取 rx_fifo 中的值。

所以我的初步作法會是：

1. 在 simrupt_init 裡面初始化一個空的棋盤。
2. 設置一個參數紀錄現在是換哪個演算法下棋，每當 timer_handler 觸發時，判斷是否有贏家，就會讓電腦去選擇下在哪一步，透過 fast_buf_put 存放在快速循環緩衝區中。
3. 更新棋盤的棋子，並且利用 produce_data 函數將其放入 kfifo 緩衝區中。
4. 透過 simrupt_read 去提取 rx_fifo 的值，並打印在 userspace 。

• 整合過程

透過 init_board 函式來初始化一個空的棋盤，然後利用 produce_data 函式依次將 O 放入棋盤格中。接著，使用 kfifo_in 函數將更新後的棋盤格存入 kfifo 的 rx_fifo 中。當 simrupt_read 函數被觸發時，就可以將這些數據呈現在 userspace 上。

步驟一測試成果

$ sudo cat /dev/simrupt 
|O| | | |
---------
| | | | |
---------
| | | | |
---------
| | | | |
---------

|O|O| | |
---------
| | | | |
---------
| | | | |
---------
| | | | |
---------

|O|O|O| |
---------
| | | | |
---------
| | | | |
---------
| | | | |
---------

commit a418265

如果要引入第三次作業的相關檔案，C 的函式庫在 Linux 核心中無法直接引入，需採用相對應的替代方法。此外，在 mcts.c 中需要使用隨機數來進行模擬，但無法使用 rand() 函式生成隨機數。因此，我引入了linux/random.h 中的 get_random_bytes 函式來取得隨機數。

This returns random bytes in arbitrary quantities. The quality of the random bytes is good as /dev/urandom.

while (1) {
        char win;
        int *moves = available_moves(temp_table);
        if (moves[0] == -1) {
            kfree(moves);
            break;
        }
        int n_moves = 0;
        while (n_moves < N_GRIDS && moves[n_moves] != -1)
            ++n_moves;
+       unsigned long rand_num;
+       get_random_bytes(&rand_num, sizeof(rand_num));
+       int move = moves[rand_num % n_moves];
-       int move = moves[rand() % n_moves];
        kfree(moves);
        temp_table[move] = current_player;
        if ((win = check_win(temp_table)) != ' ')
            return calculate_win_value(win, player);
        current_player ^= 'O' ^ 'X';
    }

然後在編譯過程中，出現問題如下：

$ make
ERROR: modpost: missing MODULE_LICENSE() in /home/robotics/linux2024/simrupt/mcts.o
ERROR: modpost: missing MODULE_LICENSE() in /home/robotics/linux2024/simrupt/game.o
ERROR: modpost: missing MODULE_LICENSE() in /home/robotics/linux2024/simrupt/negamax.o
ERROR: modpost: missing MODULE_LICENSE() in /home/robotics/linux2024/simrupt/zobrist.o
ERROR: modpost: missing MODULE_LICENSE() in /home/robotics/linux2024/simrupt/mt19937-64.o
ERROR: modpost: "negamax_init" [/home/robotics/linux2024/simrupt/simrupt.ko] undefined!
ERROR: modpost: "check_win" [/home/robotics/linux2024/simrupt/simrupt.ko] undefined!
ERROR: modpost: "calculate_win_value" [/home/robotics/linux2024/simrupt/simrupt.ko] undefined!
ERROR: modpost: "available_moves" [/home/robotics/linux2024/simrupt/simrupt.ko] undefined!
ERROR: modpost: "negamax_predict" [/home/robotics/linux2024/simrupt/simrupt.ko] undefined!
ERROR: modpost: "check_win" [/home/robotics/linux2024/simrupt/mcts.ko] undefined!
...
WARNING: modpost: suppressed 7 unresolved symbol warnings because there were too many)

查看了 4.6 Modules Spanning Multiple Files 才發現到說如果要引用多個檔案的話，要先創造一個組合模塊，告訴 make 這個模塊包含哪些目標文件。

-NAME = simrupt
+NAME = ttt
obj-m := $(NAME).o 
+ttt-objs := simrupt.o mcts.o game.o negamax.o zobrist.o mt19937-64.o 

重新編譯一次結果如下：

make -C /lib/modules/6.5.0-41-generic/build M=/home/robotics/linux2024/simrupt modules
make[1]: Entering directory '/usr/src/linux-headers-6.5.0-41-generic'
warning: the compiler differs from the one used to build the kernel
  The kernel was built by: x86_64-linux-gnu-gcc-12 (Ubuntu 12.3.0-1ubuntu1~22.04) 12.3.0
  You are using:           gcc-12 (Ubuntu 12.3.0-1ubuntu1~22.04) 12.3.0
  CC [M]  /home/robotics/linux2024/simrupt/simrupt.o
  CC [M]  /home/robotics/linux2024/simrupt/mcts.o
  CC [M]  /home/robotics/linux2024/simrupt/game.o
  CC [M]  /home/robotics/linux2024/simrupt/negamax.o
  CC [M]  /home/robotics/linux2024/simrupt/zobrist.o
  CC [M]  /home/robotics/linux2024/simrupt/mt19937-64.o
  LD [M]  /home/robotics/linux2024/simrupt/ttt.o
  MODPOST /home/robotics/linux2024/simrupt/Module.symvers
  CC [M]  /home/robotics/linux2024/simrupt/ttt.mod.o
  LD [M]  /home/robotics/linux2024/simrupt/ttt.ko
  BTF [M] /home/robotics/linux2024/simrupt/ttt.ko
Skipping BTF generation for /home/robotics/linux2024/simrupt/ttt.ko due to unavailability of vmlinux
make[1]: Leaving directory '/usr/src/linux-headers-6.5.0-41-generic'

這邊不知道 BTF 的用途為何

commit 5749eac

遇到問題，只要執行電腦的某一個線程就會 100% 被佔用，然後執行 cat /dev/simrupt 就會卡死無法使用，想要移除也沒有辦法，只能重開機。

$ sudo insmod ttt.ko 
Killed
$ sudo cat /dev/simrupt

$ sudo dmesg | tail
[  872.923504] note: insmod[9882] exited with irqs disabled
[ 1202.543450] openm current cnt: 1
$ sudo rmmod ttt
rmmod: ERROR: Module ttt is in use

所以接下來我就先測試都使用 mcts 下棋的成果如何

$ sudo cat /dev/simrupt 
| | | | |
---------
|X| | | |
---------
| | | | |
---------
| | | | |
---------

| | | | |
---------
|X| | | |
---------
| | | | |
---------
| | |O| |
---------

| | | | |
---------
|X| | | |
---------
| | | | |
---------
|X| |O| |
---------

| | | | |
---------
|X| | | |
---------
|O| | | |
---------
|X| |O| |
---------

| | | | |
---------
|X|X| |
---------
|O| | | |
---------
|X| |O| |
---------

| | | | |
---------
|X|X|O| |
---------
|O| | | |
---------
|X| |O| |
---------

| | | | |
---------
|X|X|O| |
---------
|O| |X| |
---------
|X| |O| |
---------

|O| | | |
---------
|X|X|O| |
---------
|O| |X| |
---------
|X| |O| |
---------

|O| | | |
---------
|X|X|O| |
---------
|O| |X| |
---------
|X| |O|X|
---------

$ sudo dmesg
[79245.104472] tic-tac-toe game start!
[79245.104477] openm current cnt: 1
[79245.206159] simrupt: [CPU#4] enter timer_handler
[79245.206177] simrupt: [CPU#4] produce data
[79245.206183] simrupt: [CPU#4] is turn X to play chess
[79247.276400] simrupt: [CPU#4] scheduling tasklet
[79247.276402] simrupt: [CPU#4] timer_handler in_irq: 2021697 usec
[79247.276423] simrupt: [CPU#4] simrupt_tasklet_func in_softirq: 0 usec
[79247.276707] simrupt: [CPU#9] simrupt_work_func
[79247.562118] simrupt: [CPU#4] enter timer_handler
[79247.562157] simrupt: [CPU#4] produce data
[79247.562162] simrupt: [CPU#4] is turn O to play chess
[79249.685823] simrupt: [CPU#4] scheduling tasklet
[79249.685825] simrupt: [CPU#4] timer_handler in_irq: 2073887 usec
[79249.685849] simrupt: [CPU#4] simrupt_tasklet_func in_softirq: 0 usec
[79249.686018] simrupt: [CPU#2] simrupt_work_func
[79249.866126] simrupt: [CPU#4] enter timer_handler
[79249.866165] simrupt: [CPU#4] produce data
[79249.866171] simrupt: [CPU#4] is turn X to play chess
[79251.279972] simrupt: [CPU#4] scheduling tasklet
[79251.279973] simrupt: [CPU#4] timer_handler in_irq: 1380667 usec
[79251.279990] simrupt: [CPU#4] simrupt_tasklet_func in_softirq: 0 usec
[79251.280350] simrupt: [CPU#2] simrupt_work_func

commit cc7560e

重新測試用兩個 agent 下棋後，程式依然無法執行，但是用 sudo dmesg 觀看報錯原因後，發現是在 zobrist_init 裡面出問題，看起來是在傳遞給 memset 時給了空指針而出現的錯誤。

[ 4013.964072] Call Trace:
[ 4013.964073]  <TASK>
[ 4013.964073]  ? show_regs+0x6d/0x80
[ 4013.964076]  ? __die+0x24/0x80
[ 4013.964078]  ? page_fault_oops+0x99/0x1b0
[ 4013.964080]  ? do_user_addr_fault+0x31d/0x6b0
[ 4013.964081]  ? exc_page_fault+0x83/0x1b0
[ 4013.964083]  ? asm_exc_page_fault+0x27/0x30
[ 4013.964085]  ? memset+0xb/0x20
[ 4013.964087]  ? zobrist_init+0x74/0xb0 [ttt]
[ 4013.964090]  negamax_init+0xe/0x20 [ttt]
[ 4013.964093]  simrupt_init+0x15c/0xff0 [ttt]
[ 4013.964096]  ? __pfx_simrupt_init+0x10/0x10 [ttt]
[ 4013.964100]  do_one_initcall+0x5b/0x340
[ 4013.964102]  do_init_module+0x68/0x260
[ 4013.964104]  load_module+0xb85/0xcd0
[ 4013.964107]  init_module_from_file+0x96/0x100
[ 4013.964108]  ? init_module_from_file+0x96/0x100
[ 4013.964111]  idempotent_init_module+0x11c/0x2b0
[ 4013.964113]  __x64_sys_finit_module+0x64/0xd0
[ 4013.964115]  x64_sys_call+0x130f/0x20b0

查閱後才知道，在 Linux 內核代碼和某些其他項目中，通常使用 u64 來表示 64 位無符號整數類型。我推測這個原因導致在使用 kmalloc 分配記憶體時，由於 zobrist_tabl 的定義錯誤而導致指針為空。解決了這個問題後，就可以將相應的程式碼整合到核心中。

-uint64_t zobrist_table[N_GRIDS][2];
+u64 zobrist_table[N_GRIDS][2];

以下為一次下棋的結果

$ sudo dmesg
[17723.337584] simrupt: [CPU#4] enter timer_handler
[17723.337604] simrupt: [CPU#4] produce data
[17723.345894] simrupt: [CPU#4] is turn X to play chess
[17723.345896] simrupt: [CPU#4] scheduling tasklet
[17723.345896] simrupt: [CPU#4] timer_handler in_irq: 8098 usec
[17723.345910] simrupt: [CPU#4] simrupt_tasklet_func in_softirq: 1 usec
[17723.346039] simrupt: [CPU#11] simrupt_work_func
[17723.449650] simrupt: [CPU#4] enter timer_handler
[17723.449691] simrupt: [CPU#4] produce data
[17725.084501] simrupt: [CPU#4] is turn O to play chess
[17725.084503] simrupt: [CPU#4] scheduling tasklet
[17725.084504] simrupt: [CPU#4] timer_handler in_irq: 1596493 usec
[17725.084530] simrupt: [CPU#4] simrupt_tasklet_func in_softirq: 0 usec
[17725.084669] simrupt: [CPU#11] simrupt_work_func
[17725.185573] simrupt: [CPU#4] enter timer_handler
[17725.185593] simrupt: [CPU#4] produce data
[17725.191203] simrupt: [CPU#4] is turn X to play chess
[17725.191204] simrupt: [CPU#4] scheduling tasklet
[17725.191205] simrupt: [CPU#4] timer_handler in_irq: 5479 usec
[17725.191218] simrupt: [CPU#4] simrupt_tasklet_func in_softirq: 0 usec
[17725.191222] simrupt: [CPU#4] simrupt_work_func
[17725.293608] simrupt: [CPU#4] enter timer_handler
[17725.293634] simrupt: [CPU#4] produce data
[17726.092664] simrupt: [CPU#4] is turn O to play chess
[17726.092666] simrupt: [CPU#4] scheduling tasklet
[17726.092666] simrupt: [CPU#4] timer_handler in_irq: 780302 usec
[17726.092688] simrupt: [CPU#4] simrupt_tasklet_func in_softirq: 0 usec
[17726.092836] simrupt: [CPU#13] simrupt_work_func
[17726.209601] simrupt: [CPU#4] enter timer_handler
[17726.209641] simrupt: [CPU#4] produce data
[17726.212130] simrupt: [CPU#4] is turn X to play chess
[17726.212138] simrupt: [CPU#4] scheduling tasklet
[17726.212143] simrupt: [CPU#4] timer_handler in_irq: 2443 usec
[17726.212201] simrupt: [CPU#4] simrupt_tasklet_func in_softirq: 6 usec
[17726.212338] simrupt: [CPU#13] simrupt_work_func
[17726.313633] simrupt: [CPU#4] enter timer_handler
[17726.313673] simrupt: [CPU#4] produce data
[17726.675172] simrupt: [CPU#4] is turn O to play chess
[17726.675173] simrupt: [CPU#4] scheduling tasklet
[17726.675174] simrupt: [CPU#4] timer_handler in_irq: 353027 usec
[17726.675184] simrupt: [CPU#4] simrupt_tasklet_func in_softirq: 1 usec
[17726.675307] simrupt: [CPU#10] simrupt_work_func
[17726.777598] simrupt: [CPU#4] enter timer_handler
[17726.777637] simrupt: [CPU#4] produce data
[17726.779573] simrupt: [CPU#4] is turn X to play chess
[17726.779582] simrupt: [CPU#4] scheduling tasklet
[17726.779587] simrupt: [CPU#4] timer_handler in_irq: 1903 usec
[17726.779642] simrupt: [CPU#4] simrupt_tasklet_func in_softirq: 5 usec
[17726.779785] simrupt: [CPU#12] simrupt_work_func
[17726.779811] simrupt: X win !!!

commit 84f98fe

人工智慧演算法固定在不同的 CPU

重新審視程式後，我認為不需要使用快速循環緩衝區（fast buf）。可以在 simrupt_work_func 函式中讓 agent 判斷棋步，並利用 produce_data 將數據放入 kfifo 中。

commita270386

但是觀看 dmesg 後發現到原本預期的排程結果應該是: work item 1 -> work item 2 -> work item 1 輪流運行，但是會遇到和 vax-r 同學提及過得問題相似： work item 1 -> tasklet enqueue -> tasklet enqueue -> work item 2 ，simrupt_tasklet_func 會重複空跑好幾次。

根據 queuework 設計實驗 的描述，透過 schedule_work() 會將 work 放到 workqueue 中，並指定 CPU 來執行 work。下面為執行成果：

$ sudo cat /dev/simrupt
...

| | | |X|
---------
| | | | |
---------
| | | | |
---------
| | | | |
---------

| | | |X|
---------
| | |O| |
---------
| | | | |
---------
| | | | |
---------

| | |X|X|
---------
| | |O| |
---------
| | | | |
---------
| | | | |
---------

| |O|X|X|
---------
| | |O| |
---------
| | | | |
---------
| | | | |
---------

| |X|X|X|
---------
| | |O| |
---------
| | | | |
---------
| | | | |
---------

commit bd95383

此時遇到的問題：

1. 如上圖示意，會有棋子放在同個位置上的問題，推測這邊是有棋盤尚未更新，就傳進另一個 agent 裡。
2. 更常發生的問題，tasklet_schedule 排程失敗，導致 kfifo 裡面沒有資料可以取用。
3. 如果想要使用特定 cpu ，特定的 workqueue 的話應該是要使用函式 queue_work_on ，但是會變成無法指定 cpu 。

待解決的問題

1. 我發現 negamax 的演算法比 mcts 還不好， negamax 會有"故意"不贏的問題。也就是明明在下一步棋子就贏了，卻下在其他地方，以下面例子為例，X 為 negamax ；O 為 mcts ，第五步應該就可以獲勝了。

| | | | |
---------
| | |X| |
---------
| | | | |
---------
| | | | |
---------

| | | | |
---------
|O| |X| |
---------
| | | | |
---------
| | | | |
---------

| | | | |
---------
|O| |X| |
---------
| |X| | |
---------
| | | | |
---------

| | | |O|
---------
|O| |X| |
---------
| |X| | |
---------
| | | | |
---------

| | | |O|
---------
|O| |X| |
---------
| |X|X| |
---------
| | | | |
---------

| | |O|O|
---------
|O| |X| |
---------
| |X|X| |
---------
| | | | |
---------

| |X|O|O|
---------
|O| |X| |
---------
| |X|X| |
---------
| | | | |
---------

| |X|O|O|
---------
|O|O|X| |
---------
| |X|X| |
---------
| | | | |
---------

| |X|O|O|
---------
|O|O|X| |
---------
| |X|X|X|
---------
| | | | |
---------

2. 作業中有提到，查閱 CMWQ 的文件，指定前述不同的人工智慧演算法固定在不同的 CPU (如 CPU #0 和 CPU #1)。但是我再查閱後，看到相關的資歷只有在 CMWQ/flag 中，有提到 WQ_CPU_INTENSIVE 在指定 CPU　上有幫助，但是還是不知道要怎麼指定？

https://shengyu7697.github.io/cpp-sched_setaffinity/
https://hackmd.io/@sysprog/HJXlHtlB2#設計實驗

問題紀錄

simrupt 如何確保每個 processor core 都有對應的任務可以執行？