# 2025q1 Homework3 (kxo)
contributed by < `horseface1110` >

## 開發環境

$ gcc --version
gcc (Ubuntu 13.3.0-6ubuntu2~24.04) 13.3.0

$ lscpu
Architecture:             x86_64
  CPU op-mode(s):         32-bit, 64-bit
  Address sizes:          40 bits physical, 48 bits virtual
  Byte Order:             Little Endian
CPU(s):                   1
  On-line CPU(s) list:    0
Vendor ID:                GenuineIntel
  Model name:             QEMU Virtual CPU version 2.5+
    CPU family:           15
    Model:                107
    Thread(s) per core:   1
    Core(s) per socket:   1
    Socket(s):            1
    Stepping:             1
    BogoMIPS:             5199.99
    Flags:                fpu de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov pat pse36 clflush mmx fxsr sse sse2
                          syscall nx lm constant_tsc nopl xtopology cpuid tsc_known_freq pni ssse3 cx16 sse4_1 sse4_2 x2
                          apic popcnt aes hypervisor lahf_lm cpuid_fault pti
Virtualization features:
  Hypervisor vendor:      KVM
  Virtualization type:    full
Caches (sum of all):
  L1d:                    32 KiB (1 instance)
  L1i:                    32 KiB (1 instance)
  L2:                     4 MiB (1 instance)
  L3:                     16 MiB (1 instance)
NUMA:
  NUMA node(s):           1
  NUMA node0 CPU(s):      0
Vulnerabilities:
  Gather data sampling:   Not affected
  Itlb multihit:          KVM: Mitigation: VMX unsupported
  L1tf:                   Mitigation; PTE Inversion
  Mds:                    Vulnerable: Clear CPU buffers attempted, no microcode; SMT Host state unknown
  Meltdown:               Mitigation; PTI
  Mmio stale data:        Unknown: No mitigations
  Reg file data sampling: Not affected
  Retbleed:               Not affected
  Spec rstack overflow:   Not affected
  Spec store bypass:      Vulnerable
  Spectre v1:             Mitigation; usercopy/swapgs barriers and __user pointer sanitization
  Spectre v2:             Mitigation; Retpolines; STIBP disabled; RSB filling; PBRSB-eIBRS Not affected; BHI Retpoline
  Srbds:                  Not affected
  Tsx async abort:        Not affected

## 將棋盤的顯示移到使用者層級
### 程式碼分析
| 檔案 | 說明 | 修改目標 |
| --------------------- | ----------------------------------------- | -------------------------------------------- |
| `main.c` | Linux kernel module 主入口。負責 device 註冊、初始化等 |把畫棋盤的部分改成將特定資訊傳到user_space|
| `xo-user.c` | 使用者空間程式，負責與 `/dev/kxo` 溝通 | 改寫為**從 device 讀取棋盤狀態並繪圖** |
### `main.c`棋盤狀態壓縮傳遞重構
> commit [78bf879](https://github.com/sysprog21/kxo/commit/78bf8794c080f9610084b7763ef6e301deb577c9)

#### 動機

原本的 `draw_board()` 會在 kernel 內產生完整的棋盤圖形，然後將其存入 `draw_buffer`，最終傳遞到 user space 端顯示。但這種方式傳遞的是渲染後的字串，每次都需將所有字元輸出，浪費空間且造成不必要的複製負擔。

事實上，棋盤的資訊很簡單──每格只需表達三種狀態 (`' '`, `'X'`, `'O'`)，因此完全可以只傳遞棋盤的邏輯狀態，將渲染工作移到 user space。如此不僅減少 kernel/user 的資料傳輸量，也能讓 user 端客製化顯示格式。

#### 重構步驟

1. **位元壓縮設計**
由於棋盤為 9 格，每格 3 種狀態，使用 2 bit 即可編碼一格（00 空、01 X、10 O）。因此可以用一個 `uint32_t`（32 bit）來存全部棋盤。

   static uint32_t draw_board(char *table) {
       uint32_t position = 0;
       for(int i = 0; i < N_GRIDS; i++) {
           uint32_t val = 0;
           if(table[i] == ' ') val = 0;
           else if(table[i] == 'X') val = 1;
           else if(table[i] == 'O') val = 2;
           position |= (val << (i * 2));
       }
       return position;
   }

2. **介面修改**
`drawboard_work_func` 原先只呼叫 `draw_board()` 渲染，現在改成呼叫新函式，並將回傳值存入 `position`，並傳給 `produce_board()`，將編碼後的 4 byte 放進 kfifo，供 user space 取用。

   mutex_lock(&producer_lock);
   uint32_t position = draw_board(table);
   mutex_unlock(&producer_lock);

   mutex_lock(&consumer_lock);
   produce_board(position);
   mutex_unlock(&consumer_lock);

同時調整全域 `draw_buffer` 的大小為 4 bytes，僅存 `position`。

   static char draw_buffer[4];

   static void produce_board(uint32_t position) {
       memcpy(draw_buffer, &position, sizeof(position));
       unsigned int len = kfifo_in(&rx_fifo, draw_buffer, sizeof(draw_buffer));
       // ... 
   }

#### 小節
此時，當有interrupt進來時，就會把整個棋盤的資訊傳給user_space，順利將棋盤在user_space畫出來。但我發現這樣無法達成另一個目標：紀錄棋局的落子順序。所以我改用另一種方式：每次落子時傳player和落子位置

:::danger
注意書寫規範：中英文間用一個半形空白字元區隔
:::

### 紀錄棋局的落子順序
#### 新的資料結構
> commit [5e115cb](https://github.com/sysprog21/kxo/commit/5e115cb880029a65d17375cd27b14318864b312d)

為了能夠紀錄落子資訊，我想把每次落子都分開來看。所以資訊改用1 byte傳輸，分別為：

position:4
player:1
win:3

有16格，所以需要4bit紀錄落子在哪裡；至於為甚麼win需要3 bit，因為我想湊到1 byte。如果沒有湊到1 byte，會不知道怎麼傳輸資料到user_space，buffer<s>好像</s> 沒辦法用自定義的struct為單位。

:::danger
注意書寫規範！

提供數學分析。不要說「好像」，要是 Apple 和 Google 工程師將「好像」掛在嘴邊，你敢用他們開發的產品嗎？
:::

#### 每次落子就傳資料
> commit [0512022](https://github.com/sysprog21/kxo/commit/05120222c1962c9255ccef96cda2a99f788d240)

之前傳輸資料是發生在interrrupt後，`game_tasklet_func`會負責把資料傳到user_space裡面，但這樣沒辦法傳送每個落子紀錄，因為有可能在interrupt之前已經落了多子了。所以

- 移除`produce_board`中的kfifo_in
- 由ai_one、ai_two下完棋後直接將畫圖工作放入workqueue(`queue_work(kxo_workqueue, &drawboard_work);`)
#### 成功
- 成功之前，發線總是會有重複的落子資訊出現，以為是race condition，但最後發現是因為棋局結束時，kernel也會傳送最後一步到user。所以最後才新增了`win`的標記
<s>
- fifo大小對比：
- 修改前：

- 改完後：
</s>

:::danger
注意書寫規範：文字訊息不要用圖片展現
:::