2025q1 Homework3 (kxo)

contributed by < salmoniscute >

研讀 kxo

在開始寫作業三之前，另外撰寫了一個筆記，主要是關於看程式碼的部分。

待整理

IXON

首先嘗試跑起來程式
在測試按下 Control-Q 結束遊戲的行為時，發現 terminal 並不會成功吃進去 Control-Q。
詢問 AI 工具後，嘗試在 raw_mode_enable 函式中加入：

+   raw.c_iflag &= ~(IXON);

即可成功停止遊戲。

對應的 commit，後來也看到有同學發相關的 pr。

去了解了一下為什麼需要這個改動：

在 terminal 中，IXON 是一個 software flow control 的 code 。
當 IXON 啟用時，terminal 會攔截 Ctrl-Q 和 Ctrl-S 按鍵，因此要把 IXON disable，這樣 Ctrl-S 就不再用於暫停輸出， Ctrl-Q 也不再用於恢復輸出，兩個按鍵都會作為普通的按鍵輸入。

pr

fix typo
compatibiity -> compatibility

READ_ONCE

commit

-    READ_ONCE(finish);
-    READ_ONCE(turn);
+    int finish_val = READ_ONCE(finish);
+    char turn_val = READ_ONCE(turn);
     smp_rmb();
 
-    if (finish && turn == 'O') {
+    if (finish_val && turn_val == 'O') {
         WRITE_ONCE(finish, 0);
         smp_wmb();
         queue_work(kxo_workqueue, &ai_one_work);
-    } else if (finish && turn == 'X') {
+    } else if (finish_val && turn_val == 'X') {

以下用工具觀察兩種情況下的組合語言：
我是先用 x86-64 gcc 12.2

#define READ_ONCE(var) (*((volatile typeof(var) *)(&(var))))
#define WRITE_ONCE(var, val) \
	(*((volatile typeof(val) *)(&(var))) = (val))

這兩個 macro 的定義是參考 linux/tools/virtio/linux/compiler.h
以 READ_ONCE 為例，會將變數轉成 volatile 指標，告訴 compiler 不要優化掉這次讀取，也不能和別的讀取合併。所以 GCC 依然會保留這部分對應的 mov 指令，即使程式碼沒有用到讀取的值。

c99 6.7.3
A volatile declaration may be used to describe an object corresponding to a memory-mapped input/output port or an object accessed by an asynchronously interrupting function. Actions on objects so declared shall not be ‘‘optimized out’’ by an implementation or reordered except as permitted by the rules for evaluating expressions.

#define barrier() __asm__ __volatile__("": : :"memory")
#define smp_rmb() barrier()
#define smp_wmb() barrier()

對照看 Linux 核心的文件

READ_ONCE(finish);

static int finish;

void test(void) {
    READ_ONCE(finish);
    if (finish) {
        WRITE_ONCE(finish, 0);
    }
}














test:
        push    rbp
        mov     rbp, rsp
        mov     eax, OFFSET FLAT:finish
        mov     eax, DWORD PTR [rax]
        mov     eax, DWORD PTR finish[rip]
        test    eax, eax
        je      .L3
        mov     eax, OFFSET FLAT:finish
        mov     DWORD PTR [rax], 0
.L3:
        nop
        pop     rbp
        ret

第四行把 finish 的地址放進 eax 暫存器裡。然後從 rax 指向的位置抓資料到 eax。第四行跟第五行一起就是在做 READ_ONCE(finish) 這種 volatile 的載入。
第六行又從 finish 載資料到 eax 一次，這是給 if statement 用的。GCC 會重複載入是因為它不能假設 finish 的值在中間不會被改變。

int a = READ_ONCE(finish);

static int finish;

void test(void) {
    int a = READ_ONCE(finish);
    if (a) {
        WRITE_ONCE(finish, 0);
    } 
}














test:
        push    rbp
        mov     rbp, rsp
        mov     eax, OFFSET FLAT:finish
        mov     eax, DWORD PTR [rax]
        mov     DWORD PTR [rbp-4], eax
        cmp     DWORD PTR [rbp-4], 0
        je      .L3
        mov     eax, OFFSET FLAT:finish
        mov     DWORD PTR [rax], 0
.L3:
        nop
        pop     rbp
        ret

可以看到第六行會再把 eax 暫存器存到堆疊裡面，然後再和 0 比較，但不會再一次存取 finish 的值。

參考文件把兩者都做了編譯器優化（-O2）

READ_ONCE(finish);

test:
        mov     eax, DWORD PTR finish[rip]
        mov     eax, DWORD PTR finish[rip]
        test    eax, eax
        je      .L1
        mov     DWORD PTR finish[rip], 0
.L1:
        ret

會有兩個 mov eax, DWORD PTR finish[rip]，就如同先前所提及，GCC 無法假設兩次讀取結果是一樣的，因為 volatile 代表其他 CPU/ device 可能會改變記憶體內容。所以在這樣的情況下兩次 load 不會合併成一個。

為何上述的 compiler barrier 能發揮作用？

以 kxo main.c 中的程式碼來說，以下節錄

READ_ONCE(finish);
READ_ONCE(turn);
smp_rmb();

if (finish && turn == 'O') {
    WRITE_ONCE(finish, 0);
    smp_wmb();
    queue_work(kxo_workqueue, &ai_one_work);
}

第一次的 READ_ONCE(finish) 是獨立的讀取操作，回傳值實際上沒有被使用。接著程式碼執行了 smp_rmb，這確保之後的所有讀取操作不會被重排到 barrier 之前。然後在 if statement 中，編譯器會再次對 finish 做讀取操作。

第二次 mov eax, DWORD PTR finish[rip] 的結果是否有可能跟第一次不同？

int a = READ_ONCE(finish);

test:
        mov     eax, DWORD PTR finish[rip]
        test    eax, eax
        je      .L1
        mov     DWORD PTR finish[rip], 0
.L1:
        ret

可以看到優化後只會有一個 mov eax, DWORD PTR finish[rip]

接著直接看看 kxo main.c 的組語
我耍白痴應該要一開始就看這個的前面時間都浪費掉==
首先在 Makefile 裡面新增

asm:
    $(MAKE) -C $(KDIR) M=$(PWD) CFLAGS_main.o="-S -fverbose-asm" main.s

然後執行命令

$ make asm

就會產生對應的 main.s 檔案

READ_ONCE(finish);

# /home/salmon/Linux2025/kxo/main.c:272:     tv_start = ktime_get();
	call	ktime_get	#
	movq	%rax, %rbx	# tmp115, tv_start
# /home/salmon/Linux2025/kxo/main.c:274:     READ_ONCE(finish);
	movl	finish(%rip), %eax	# MEM[(const volatile int *)&finish], _22
# /home/salmon/Linux2025/kxo/main.c:275:     READ_ONCE(turn);
	movzbl	turn(%rip), %eax	# MEM[(const volatile char *)&turn], _23
# /home/salmon/Linux2025/kxo/main.c:276:     smp_rmb();
# /home/salmon/Linux2025/kxo/main.c:282:     if (finish && turn == 'O') {
	movl	finish(%rip), %eax	# finish,
	testl	%eax, %eax	#

int a = READ_ONCE(finish);

# /home/salmon/Linux2025/kxo/main.c:272:     tv_start = ktime_get();
	call	ktime_get	#
# /home/salmon/Linux2025/kxo/main.c:278:     int finish_val = READ_ONCE(finish);
	movl	finish(%rip), %edx	# MEM[(const volatile int *)&finish], _24
# /home/salmon/Linux2025/kxo/main.c:272:     tv_start = ktime_get();
	movq	%rax, %rbx	# tmp123, tv_start
# /home/salmon/Linux2025/kxo/main.c:279:     char turn_val = READ_ONCE(turn);
	movzbl	turn(%rip), %eax	# MEM[(const volatile char *)&turn], _25
# /home/salmon/Linux2025/kxo/main.c:280:     smp_rmb();
# /home/salmon/Linux2025/kxo/main.c:282:     if (finish_val && turn_val == 'O') {
	testl	%edx, %edx	# _24

兩種寫法主要有兩個地方不同：

跟一開始的觀察一樣，READ_ONCE(finish);的寫法會執行 movl finish(%rip), %eax 兩次

是否 movl 一次就夠了？為什麼會需要到兩次？

第二個方法的 tv_start = ktime_get(); 對應的兩個指令不知道為什麼被拆開了，發生了 Instruction Reorder

/* Tasklet handler.
 *
 * NOTE: different tasklets can run concurrently on different processors, but
 * two of the same type of tasklet cannot run simultaneously. Moreover, a
 * tasklet always runs on the same CPU that schedules it.
 */

猜測為什麼原本的程式碼執行正確是跟 tasklet 的行為模式有關

注意到 softirq 和 tasklet 同樣運行在 interrupt context (software irq context) 之下，因此不允許 sleep / preempt / context switch，也不允許存取 userspace 的資料。此外，同一個 tasklet 不允許在多個 CPU 上平行處理，每個 tasklet 將僅在調度它的 CPU 上運行，以優化 cache 使用。

使畫面呈現的部分全部在使用者層級

commit
這邊是參考 rota1001

提供細節

對弈的過程中，在螢幕顯示當下的時間

commit

顯示多場對弈的過程

commit

目前是模仿 kxo_attr，用 sysfs 來記錄遊戲的歷史紀錄。

static ssize_t kxo_move_history_show(struct device *dev,
                                     struct device_attribute *attr,
                                     char *buf)
{
    return snprintf(buf, MOVE_BUFFER_SIZE, "%s\n", move_history);
}

因為 move_history 不需要被 user space 的程式來寫入，所以只新增了 kxo_move_history_show 函式。

static DEVICE_ATTR_RO(kxo_move_history);

用 DEVICE_ATTR_RO 巨集來定義一個 read only 的 sysfs attribte。

接著一樣模仿 kxo_attr，kxo_init 函式中需要新增以下：

ret = device_create_file(kxo_dev, &dev_attr_kxo_move_history);
    if (ret < 0) {
        printk(KERN_ERR "failed to create sysfs file kxo_move_history\n");
        goto error_cdev;
    }

這段是在先前已經創建好的 character device 底下的 sysfs entry point 再新增一個名為 kxo_move_history 的 sysfs file，這樣 user space 的程式就可以讀取到 move_history 的值。
如同在 xo-user.c 中新增以下程式碼：

#define XO_MOVE_HISTORY_FILE "/sys/class/kxo/kxo/kxo_move_history"

目前是開一個長度 512 的字串 buffer（move_history）去存紀錄，move_history 內容的插入都只在 kernel space 做，然後使用者按下 Control-Q 後，在 xo-user.c 裡面把他們一次全部印出來。
另外在 timer_handler 函式裡面判斷雙方是否分出個勝負，也會存勝方進去 move_history。

輸出如下：

Moves 1: B4 -> C2 -> A1 -> C3 -> D2 -> B3 -> A2 -> A3 (X Wins)
Moves 2: A3 -> D2 -> A1 -> D3 -> A2 (O Wins)
Moves 3: C3 -> D1 -> C2 -> D2 -> D3 -> B1 -> B3 (X Wins)
Moves 4: A3 -> D2 -> A1 -> D3 -> A2 (O Wins)

todo
把整段字串改成其他更好的資料結構比如說鏈結串列或二維陣列？

2025q1 Homework3 (kxo)

研讀 kxo

待整理

IXON

pr

READ_ONCE

使畫面呈現的部分全部在使用者層級

對弈的過程中，在螢幕顯示當下的時間

顯示多場對弈的過程

Read more

EEVDF 論文研讀

2025q1 Homework5 (assessment)

2025q1 Homework4 (quiz3+4)

2025q1 Homework1 (lab0)