Try   HackMD

2025q1 Homework3 (kxo)

contributed by < Charlie-Tsai1123 >

注意細節

問題修正

出現亂碼

在執行 sudo ./xo-user 若按下 ctrl + P 會暫停繪製棋盤的畫面但會出現以下錯誤

O| | | 
-------
 |X|X| 
-------
 | | |O
-------
O| | | 
-------
���Stopping the kernel space tic-tac-toe game...

我先找到 ctrl + P 的程式碼位子，在 xo-user.c 中

int attr_fd = open(XO_DEVICE_ATTR_FILE, O_RDWR);

XO_DEVICE_ATTR_FILE 是用來更改遊戲的狀態

case 16: /* Ctrl-P */
    read(attr_fd, buf, 6);
    buf[0] = (buf[0] - '0') ? '0' : '1';
    read_attr ^= 1;
    write(attr_fd, buf, 6);
    if (!read_attr)
        printf("Stopping to display the chess board...\n");
    break;

從這段程式可以得知，buf[0] 是用來控制程式是否顯示棋盤 read 部份負責看現在的狀態 write 部份則更改現在狀態，從這部份我對修改這個錯誤沒有頭緒，所以轉向觀察輸出棋盤的程式 main.c

發現輸出棋盤的地方好像沒有加上 '\0' 這樣 printf 處理時不知道哪裡終結可能會出現亂碼，所以做了以下修改

main.c

while (i < DRAWBUFFER_SIZE) {...}
+ draw_buffer[i - 1] = '\0';

xo-user.c

- printf("%s", display_buf);
+ printf("%s\n", display_buf);

Image Not Showing Possible Reasons
  • The image was uploaded to a note which you don't have access to
  • The note which the image was originally uploaded to has been deleted
Learn More →

改善 ctrl + Q

commit 0e1d9b4

畫面呈現在使用者層級

commit 5377a9c

修改 draw_buffer

參考 rota1001

從原本的 DRAWBUFFER_SIZE 可以得知 draw_buffer 紀錄了整個畫面的資訊，也因此從 kernel mode 傳到 user mode 會用很多資源 (66 bytes 以 4x4 為例)，那要如何減少？每格狀態只會有三種 ('O', 'X', ' ') 但三不是 2 的冪，所以要用 2 個 bit 表示 (4種狀態)，所以傳遞資訊只需要 BOARD_SIZE

× BOARD_SIZE
× 2 bits (32 bits = 1 bytes 以 4x4 為例) 因此我將 draw_buffer 的型別改用 unsigned int

- static char draw_buffer[DRAWBUFFER_SIZE];
+ static unsigned int draw_buffer;

提供更多數學分析

然後從 main.c draw_board 可以發現 draw_buffer 的更新是根據 table ，它紀錄了每個位子的符號

draw_buffer[i++] = j & 1 ? '|' : table[k++];

所以可以思考該如何把 O, X, 用三個狀態表示，我先列出他們三個的 Asquii Code:

O X
1001111 1011000 0100000

可以發現黃色標起來的地方剛好可以用 2 bits 代表不同狀態，只需要把那一格的 char 向右移動 4 格再 and 0b11 = 3 ，因此依序把值填入 draw_buffer 中

while (i < N_GRIDS) {
    draw_buffer |= ((table[k++] >> 4) & 3) << (i << 1);
    i++;
}

明明第三跟第四個 bit 就可以表示三個狀態了為什麼要用第五跟第六

O X
1001111 1011000 0100000

因為等等在 user mode 的 draw_board 不想用到 if else

移動 draw_board 到 user mode

const char mapping[3] = {'O', 'X', ' '};

仔細觀察剛剛用來代表 O, X, 的值，剛剛好分別對應 0, 1, 2 ，所以可以創見一個大小為 3 的陣列分別就把 0, 1, 2 對應到 O, X, 

static int draw_board(unsigned int display_buf)
{
    const char mapping[3] = {'O', 'X', ' '};
    for (int i = 0; i < BOARD_SIZE; i++) {
        putchar(mapping[display_buf & 3]);
        display_buf >>= 2;
        for (int j = 0; j < BOARD_SIZE - 1; j++) {
            putchar('|');
            putchar(mapping[display_buf & 3]);
            display_buf >>= 2;
        }
        putchar('\n');
        for (int j = 0; j < (BOARD_SIZE << 1) - 1; j++) {
            putchar('-');
        }
        putchar('\n');
    }

    return 0;
}

[to do] 測試是否真的效率較好

引入 coroutine

首先我看了 <並行程式設計：排程器原理> 中的 coro.c 程式碼，裡面使用了 setjmp 跟 longjmp 處理 coroutine

嘗試在 main.c 使用 setjmp.h 出現以下錯誤

/home/charlie-tsai/linux2025/hw/kxo/main.c:15:10: fatal error: setjmp.h: No such file or directory
   15 | #include <setjmp.h>
      |          ^~~~~~~~~~
compilation terminated.

根據 《The Linux Kernel Module Programming Guide》(lkmpg) 5.2

One point to keep in mind is the difference between library functions and system calls. Library functions are higher level, run completely in user space and provide a more convenient interface for the programmer to the functions that do the real work — system calls. System calls run in kernel mode on the user’s behalf and are provided by the kernel itself.

因為 setjmp/longjmp 是 glibc 提供的函式，設計給 user space 使用，依賴 user space 的 stack ，因為 kernel 沒有使用 glibc 所以無法使用

想法：
將不同演算法下棋也可以運作在 user space 並用 coroutine 在 AI1, AI2, draw_board 間輪流執行

讓 user space 可以使用 kernel space 函式 (mcts, negamax)

Commit 166d6e4

首先要讓 user space 可以使用 mcts 跟 negamax 這兩個函式，先去翻了 lkmpg 並學習了 ioctl 的用法以及第六章提及的 character device driver

Device

device 分成兩種 character devices 跟 block devices

character devices block devices
input or output many or as few bytest they like input output through fix-sized buffer
buffer for request 可以選擇順序(就像選擇更近的 sector 存取資料)

修改 file_operations
file_operations 定義了各種 device 的函式

static const struct file_operations kxo_fops = {
    .read = kxo_read,
    .llseek = no_llseek,
    .open = kxo_open,
    .release = kxo_release,
    .owner = THIS_MODULE,
+   .unlocked_ioctl = kxo_ioctl,
};

define magic number
magic number 可以辨別不同的 ioctl 指令來源，這裡想要讓 mcts negamax_predict 讓使用者使用，所以需要用到兩組 magic number

#define MY_IOCTL_MAGIC_MCTS 'O'
#define MY_IOCTL_MCTS _IOWR(MY_IOCTL_MAGIC_MCTS, 1, unsigned int)
#define MY_IOCTL_MAGIC_NEGAMAX 'X'
#define MY_IOCTL_NEGAMAX _IOWR(MY_IOCTL_MAGIC_NEGAMAX, 1, unsigned int)

完成 kxo_ioctl
進行四個步驟：

  1. kernel space 讀取 user space 傳過來的資料 –> copy_from_user
  2. 將收到的 unsigned int 轉成 char* –> int_to_table
  3. run mcts 或 negamax_predict
  4. 將 kernel space 產生的最佳位子傳回到 user space –> copy_to_user
switch (cmd) {
    case MY_IOCTL_MCTS:
        if (copy_from_user(&value, (unsigned int __user *) arg,
                           sizeof(unsigned int)))
            return -EFAULT;

        int_to_table(value, user_table);
        value = mcts(user_table, 'O');
        if (copy_to_user((unsigned int __user *) arg, &value,
                         sizeof(unsigned int)))
            return -EFAULT;

        return 0;
    case MY_IOCTL_NEGAMAX:
        if (copy_from_user(&value, (unsigned int __user *) arg,
                           sizeof(unsigned int)))
            return -EFAULT;

        int_to_table(value, user_table);
        value = negamax_predict(user_table, 'X').move;
        if (copy_to_user((unsigned int __user *) arg, &value,
                         sizeof(unsigned int)))
            return -EFAULT;
        return 0;
    default:
        return -EINVAL;

修改 user space 程式
用 ioctl 傳入棋盤並回傳最佳下棋位子，接著再更新
空棋盤會是 0b10101010101010101010101010101010 每一格都是 10 因為代表 (可以看上面 mapping 的方法)

  • mcts 只要清空那一格就好 (00 代表 O) :
    user_draw_buffer &= ~(0b11 << (move << 1));
  • negamax 還要 or 01 (01 代表 X) :
    user_draw_buffer &= ~(0b11 << (move << 1));
    user_draw_buffer |= (0b01 << (move << 1));
void task_mtcs(int fd)
{
    finish++;
    unsigned int move = user_draw_buffer;
    ioctl(fd, MY_IOCTL_MCTS, &move);
    if (move != -1) {
        user_draw_buffer &= ~(0b11 << (move << 1));
    }
}

void task_negamax(int fd)
{
    finish++;
    unsigned int move = user_draw_buffer;
    ioctl(fd, MY_IOCTL_NEGAMAX, &move);

    if (move != -1) {
        user_draw_buffer &= ~(0b11 << (move << 1));
        user_draw_buffer |= (0b01 << (move << 1));
    }
}

結果
上面是 kernel space 執行的，下面是 user space 執行的

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

[to do] 目前犯了個錯誤因為 user space 沒辦法使用 check_win （因為在 kernel ）所以我是讓 mcts 跟 negamax 總共呼叫 16 次再開始新的一局，之後想要寫在 user space 判斷棋盤勝利

使用 coroutine

上面實做完後，目前是讓兩個 ai 更新完 table 後再執行 draw_board

if (FD_ISSET(STDIN_FILENO, &readset)) {
    FD_CLR(STDIN_FILENO, &readset);
    listen_keyboard_handler();
} else if (read_attr && FD_ISSET(device_fd, &readset)) {
    FD_CLR(device_fd, &readset);
    printf("\033[H\033[J"); /* ASCII escape code to clear the screen */
    read(device_fd, &display_buf, sizeof(display_buf));
+   task_mtcs(device_fd);
+   task_negamax(device_fd);
    draw_board(display_buf, user_draw_buffer);
}

那現在想要將這兩個函式跟 draw_board 還有 keyboard handler 改成使用 coroutine

讀懂程式

mcts.c

MCTS 演算法分成三步（參考Monte Carlo Tree Search 解說）

  1. sellect
  2. rollout && expand
    • rollout (還沒有更新過 ni = 0)
    • expand (有更新過了 –> 往下試探新增新的節點)
  3. backpropagate (往上更新結果 ni++ , wi++ if win)

image

ni 是右邊的數字代表模擬了幾次， wi 是贏得次數

數學分析呢？

xo-user.c

xo-user.c 用來控制並顯示來自 Linux kernel space 的圈圈叉叉（XO）遊戲，透過 /dev/kxo 與 /sys/class/kxo/kxo/kxo_state 與核心模組互動。
(/dev/kxo 內有棋盤的資訊、/sys/class/kxo/kxo/kxo_state 內有遊玩狀態的資訊)

static bool status_check(void)

main.c

閱讀　lkmpg

Last changed by 
 
Charlie1123
0
87

Read more

2025q1 Homework5 (assessment)

contributed by &lt; Charlie-Tsai1123 &gt; :::danger 注意細節！ :::

May 5, 2025
2025q1 Homework4 (quiz3+4)

contributed by &lt;Charlie-Tsai1123&gt;

Apr 22, 2025
2025q1 Homework1 (lab0)

contributed by &lt;Charlie-Tsai1123&gt;

Apr 1, 2025
2025q1 Homework2 (quiz1+2)

contributed by &lt;Charlie-Tsai1123&gt;

Mar 27, 2025
Read more from Charlie1123
Published on HackMD