HackMD2025q1 Homework3 (kxo)
contributed by < wurrrrrrrrrr >
縮減使用者和核心層級的通訊成本
開始改進程式碼之前，深入了解現有的程式碼架構和邏輯是第一步要做的。由作業要求可以看到我的任務是縮減使用者和核心層級的通訊成本，因此，第一步我先檢視了判定勝利的程式碼區段，以了解它如何根據棋盤狀態判斷哪一方獲勝或是否平局。
這個 lines 陣列定義了四個方向（橫向、縱向、主對角線、副對角線）的檢查規則還有起始位置跟邊界範圍。
這段函式主要邏輯是先遍歷所有四個方向，對每個方向的每個可能起點進行檢查，一旦找到連線則返回勝者；若都沒找到，再根據棋盤是否填滿來決定是遊戲未完成還是平局。
由於在遊戲的前五步內，無論怎麼下棋都不可能決出勝負，因此我設定了一個變數，讓程式僅在棋步達到有可能產生勝負局面時才調用 check_win(table) 進行勝負檢查，這樣避免了不必要的計算。
再來看到棋盤的部份：
可以看到，首先宣告了一個名為 table 的陣列，大小為 16 個 char，這個陣列代表了我們的棋盤。
在後來看到 fast circular buffer 的實作後，我想到或許可以將它應用到我的 timer_handler 中。
這樣做可以避免在中斷服務例程（ISR）中直接操作 kfifo，改為先將資料暫存到站存區（例如 fast buffer）中，再透過 queue_work 把實際寫入 kfifo 的任務延後到工作佇列中處理，進而有效縮短 IRQ 處理時間、提升中斷響應效能。
隨後發現畫面更新速度明顯提升，但在執行一段時間後卻出現不明原因的卡頓，而且接著棋盤底部會不斷的消失並跑到上面那排，目前還不知道是什麼原因導致。
再來看到 xo-user 中的 listen_keyboard_handler 這個函式可以知道他的作用為透過讀取鍵盤輸入（Ctrl-P 和 Ctrl-Q），來去修改 sysfs 屬性檔案中的狀態，達到控制 kernel 模組顯示棋盤或者是停止遊戲。同時透過全域變數（如 read_attr 與 end_attr）來記錄當前的狀態，並在必要時輸出提示訊息。
而在其中宣告了一個長度為 20 的字元陣列 buf，用來暫存從 sysfs 屬性檔案中讀取到的狀態資料。
但是看到 main.c 當中 attr_obj 的結構:
實際上我們只須三個位元來去存取 display、resume 和 end 並在需要時去變動他們的值，因此我做了以下修改：
同時也改動了 main.c 當中的 kxo_state_show 和 kxo_state_store 這兩個函式：
後來我發現，真的有必要用三個 char 變數來儲存狀態嗎？
其實我可以只用一個 char，然後透過位元（bit）來表示每一個狀態，例如這樣：
這樣每個狀態只佔用 1 bit，就能省下不少空間，而且狀態的檢查、設定與清除都可以透過位元運算（bitwise operation）來完成，例如 flags & FLAG_DISPLAY 來檢查是否顯示棋盤。
提供更多數學分析
因此我將原本使用 display、resume 和 end 三個欄位的地方，都改為一個 char flags，並以 bitops 的方式來處理對應邏輯。
並在 xo-user 中的 listen_keyboard_handler 做出了以下改動：
這是此次實做的 Commit bc45765
重新重啟遊戲
在一開始的程式碼中，我發現當使用者按下 Ctrl+Q 終止遊戲後，再次執行 ./xo-user 時，畫面卻不再更新。一開始我認為這個行為不太合理，因此決定深入檢查程式碼的邏輯。
經過閱讀程式碼後我發現，每次執行 ./xo-user，都會觸發 kxo_open()，而 kxo_open() 中會呼叫 mod_timer()，這會啟動定時器並定期呼叫 timer_handler()。照理來說，這應該可以重新啟動遊戲邏輯。
為了確保遊戲能夠重新開始，我在 kxo_open() 中加入一段判斷：如果 attr_obj.flags 中的 FLAG_END 被設為 1，就自動將它清除（也就是改回 0）。這樣理論上遊戲應該會正常重新啟動。
然而實際執行後仍然沒有畫面更新，這讓我感到困惑。最後我發現，除了 FLAG_END 之外，還需要確保 FLAG_DISPLAY 被設為 1，否則即使遊戲邏輯在背景運作，畫面也不會輸出到使用者端。
總結來說，畫面無法顯示的關鍵原因是：FLAG_DISPLAY 沒有重新開啟，因此即便遊戲邏輯有執行，畫面也不會被輸出。
因此我在 kxo_open 中做了以下改動：
但是照理說我沒有動到 attr_obj.flags 關於 display 的部份，那為什麼會設為 0 是我不了解的。
顯示多場對弈的過程
在更新程式碼的過程中，我先宣告下列這些會用到的變數：
我首先將每盤遊戲的步驟數據暫時存儲在 static unsigned long long tmp_move 中。由於我的棋盤是 4x4 大小，因此所有可能的步驟數量為 ，每一步的狀態可由 4 個 bit 來表示。為了有效存儲這些步驟，我選擇使用static unsigned long long（即 64 位元整數），這樣能夠在 64 個 bit 中儲存每盤棋的可能步驟。
為了將每盤棋的步驟數據正確儲存，我使用在 ai_one_work_func 和 ai_two_work_func 用以下方式進行棋盤的更新：
這段程式碼的邏輯如下：
- tmp_move << 4：將原來的棋步數據左移 4 位，為下一步的數據騰出空間。
- (move & 0xF)：將新的步驟（move）的 4 個 bit（每個步驟佔用 4 bit）提取出來。
- | ：將更新後的
tmp_move與當前的步驟數據合併，形成新的tmp_move。 tmp_move_step是紀錄這盤棋總共走了幾步。
這樣，通過每次左移和按位 OR 操作，我能夠將每個步驟依序存儲在tmp_move中，並且保持每盤棋的完整性和紀錄這盤棋總共走了幾步。
由於記憶體的限制，我無法選擇紀錄每一盤棋的數據。為了在有限的資源下有效地管理遊戲的歷史步驟，我決定使用一個unsigned long long move_seq[17]陣列來儲存 16 盤棋 的數據。這個陣列被設計為一個 環形緩衝區（circular buffer）。
環形緩衝區是一種常見的數據結構，專門用來儲存並管理循環的歷史數據。其運作方式是，當緩衝區已經滿了時，新的數據會覆蓋舊的數據。這樣的設計能夠確保我們始終保留最新的遊戲步驟數據，並且有效地循環利用內存，避免不必要的內存浪費。
這樣的設計有以下幾個優勢：
- 保留最新數據：即使在記憶體有限的情況下，我們也能夠保證遊戲的最新步驟能夠儲存並顯示出來。
- 循環利用記憶體：當環形緩衝區已滿，新的步驟數據會覆蓋最舊的數據，這樣可以在不浪費記憶體的情況下持續儲存最新的數據。
- 順序顯示：由於數據的存儲是循環的，因此可以確保遊戲步驟數據始終按照正確的順序顯示。
在這樣的設計下，當讀取遊戲步驟數據時，環形緩衝區能夠有效且準確地讀取並呈現最新的棋盤，確保用戶看到的是遊戲進程的最新狀態，而不會丟失任何進度。
move_seq[16]：這個位置用來儲存前 16 盤棋的步數。由於每盤棋的最大步數為 16 步，我們只需要 2 的 4 次方，即 16 個步驟來表示每一盤棋的步驟數據，這等同於需要 的 bit，剛好是unsigned long long的大小，能夠有效地儲存每一盤棋的步驟並循環管理。
在程式碼中我決定只有在確認遊戲勝利時才將這盤棋的步驟數據儲存到陣列中，這樣就能避免儲存未完成的棋局數據。
當設定完後我們需要為使用者提供一個方法來訪問這些數據。這我透過 ioctl 來實現，它允許用戶程序向核心模組發送控制指令。
完整的操作過程：
當使用者按下ctrl+q後遊戲的步驟數據我們希望能夠將這些數據傳遞給用戶，這樣他們就可以查看前幾局遊戲的步驟。
因此我使用到 LKMPG 中所提到的copy_to_user這個函式將那些核心資料轉移到使用者空間。
The put_user and get_user macros allow you to access that memory. These functions handle only one character, you can handle several characters with copy_to_user and copy_from_user . As the buffer (in read or write function) is in kernel space, for write function you need to import data because it comes from user space, but not for the read function because data is already in kernel space.
並在 xo-user.c 中實現通過 IOCTL 命令也就是使用我定義的 MY_IOCTL_GET_DATA 命令來來讀取棋盤數據和棋盤步數。
當我們成功接收到核心所傳遞的資料後，需要一個函數來處理並轉換這些資料，以符合題目要求的格式。因此，我在 xo-user.c 中實現了void print_moves()函數，這個函數負責將接收到的遊戲步驟數據轉換為題目所要求的顯示格式。
首先我先定義了一個labels，這個 labels 陣列定義了 16 個位置標籤，對應棋盤上的每一個格子。每個位置對應於井字棋的 4x4 格子（例如：A1, B2, 等等）。
隨後，當獲取遊戲的當前步驟數據後，程式將每盤遊戲的步數解析出來，並將每個步驟存儲在 moves 陣列中：
當獲取棋盤的步驟數據和該盤遊戲的步數後，程式會將這些數據轉換為題目要求的格式，從而實現正確的顯示。
在閱讀 The Linux Kernel Module Programming Guide
發現其中有一處英文表達不太正確。由於過去尚未實際使用過 pull request，這次便藉由這個機會，嘗試提出修正，並藉此學習並熟悉這項技能
這為此次的 Commit 5ce6b00 。
棋盤壓縮並將畫面顯示在使用者階層
在原始程式碼中，可以看到最初的作法是使用char table[N_GRIDS]來表示棋盤狀態，其中的內容僅包含 'o'、'x' 和空格字元。接著透過draw_board()函式，將這個單純的棋盤資料加入井字遊戲所需的線條與框架，使其在視覺上更具結構性。這些處理後的輸出會被存入char draw_buffer[DRAWBUFFER_SIZE]中，最後透過kfifo_in(&rx_fifo, draw_buffer, sizeof(draw_buffer))將結果寫入核心的 FIFO 緩衝區中，以供後續使用。
在閱讀原始程式碼 kfifo.h 時，我注意到其中對numbers的用法似乎不太正確。為了進一步釐清並修正，我參考了提交第一份 Patch 到 Linux Kernel 的教學，並嘗試實際提交了一份 patch。以下是這次的提交：kfifo: Fix grammar issues in macro documentation。
我認為draw_board()函式其實不需要放在核心模式中執行，這部分的處理邏輯應該移到使用者空間來進行會更合適。使用者端只需要接收char table[N_GRIDS]這個純資料格式的棋盤狀態即可，而不需要從核心傳送經過轉換、加上框線的視覺化結果。
將棋盤繪製的任務留在使用者端，可以有效減少核心與使用者空間之間的資料傳輸量，只需傳送簡單的棋盤狀態（例如 'x'、'o' 與空格），而不必傳送完整的視覺化字元陣列。這樣的設計也更符合核心應只處理邏輯與資料、而非介面呈現的原則。
因此我把draw_board()轉到 xo-user.c 運作使得運作更有效率。
我認為目前用 16 個位元組char table[16]來儲存棋盤狀態其實有些浪費，如果將每個棋格的狀態以 2 個位元表示（例如：00 表示空格、01 表示 'O'、10 表示 'X'），那麼整個棋盤只需要 16 × 2 = 32 個位元，用一個 32-bit 的整數（4 個位元組）就足以容納，因此我做了以下改動將空格設為 0x10 ， X 的話就設為 0x01 ，O 的話就設為 0x0：
隨後我在 xo-user.c 加入了轉換的程式碼。棋盤資料以一個 unsigned int 的變數（btable）傳入。
在函式開始的部分，宣告了一個靜態字元陣列 draw_buffer 作為畫出來的棋盤的輸出緩衝區。
在每一格的處理中，會根據目前第幾格（透過變數 k 紀錄）計算出對應的位元偏移量，然後利用位元操作從整數中取出對應的 2 位元資料。這 2 個位元對應的意義如下：0x00 表示該格是玩家 O 的棋子，0x01 表示玩家 X 的棋子，而 0x02 則代表該格為空。值得注意的是，這裡還額外保留了一種例外處理的情況，若取出的值不在上述範圍，則以問號 ? 作為佔位，避免資料錯誤造成未定義的輸出。
最後，在緩衝區結尾補上 '\0' 作為 C 字串的結尾，確保這段字元陣列能被正確處理與輸出。函式回傳值為 0，代表執行成功。
這為此次的 Commit 6e40827 。
顯示時間
在 select 的處理邏輯中加入了顯示目前時間的功能。每當從裝置端讀取資料並重新繪製畫面後，會透過 time() 取得當前的系統時間，並用 localtime() 轉換為結構化的時間資訊。接著使用 printf() 將時間格式化為 YYYY-MM-DD HH:MM:SS 的形式，印在畫面下方，作為即時畫面更新的時間戳記。
這為此次的 Commit c75297d 。
〈並行程式設計：排程器原理〉，引入若干 coroutine
在實做 coroutine 之前我先查看了 coro 了解它是如何設計與實現協程的。首先，該專案會註冊三個任務（tasks），並為每個任務定義對應的參數如下所示：
隨後呼叫 schedule() 這個函式，這個函式的功用為將所有的註冊的 task 加入到鏈結串列中，和當任務結束要呼叫此函式使其能夠將 cpu 交給剩餘的任務。
此程式會註冊三個任務，其中 task0 會計算偶數位置的費波那契數列（Fibonacci sequence）直到數值為，task1 會計算奇數位置的費波那契數列（Fibonacci sequence），而第三個任務（task1）則是單純印出 0~69 的整數。
每個 task0 和 task1 從不同的起點 0 和 1 開始，以間隔 2 的方式逐步執行 Fibonacci 計算。每次計算完會主動讓出控制權（使用 task_switch()），交由排程器選擇下一個任務，實現協程之間的交錯執行。
而 task2 則是在每次迴圈中印出當前的計數值，同樣會在每次迴圈後呼叫 task_switch()，切換到下一個排隊的任務。當所有任務執行完畢後，程式自然結束。
看完上述的程式碼流程後就可以開始著手實作使用者端的 coroutine。在使用者端實作 coroutine 之前，首先需要將 game.c、mct.c、negamax.c、xoroshiro.c 和 zobrist.c 等程式和其標頭檔的功能轉移至使用者空間，因為原本的程式碼依賴於核心相關的函式庫，這是此次改動的重點，具體改動可參考 Commit 5ff5dee。
當所有需要的函式都在使用者空間後就能來實做使用者空間的 coroutine ，如何設計 coroutine 的任務為一大重點，因此我決定設計三個任務，這三個任務分別處理不同的遊戲邏輯及用戶互動：
- 任務 0 (task0)：負責處理玩家 O 的移動。這個任務會不斷進行蒙特卡羅樹搜索（MCTS），計算玩家O的最佳步數，並更新棋盤。在每一步之後，會根據遊戲狀態進行相應的顯示更新後將當前任務加入任務隊列中，切換協程。
- 任務 1 (task1)：負責處理玩家 X 的移動。與 task0 相似，這個任務會進行MCTS運算來選擇X的最佳步數，並更新棋盤，同樣會進行顯示更新與協程切換。
- 任務 2 (task2)：負責監聽用戶輸入，並根據輸入來控制遊戲的顯示、結束或重新開始。這個任務會一直在等待用戶按下特定的鍵來切換顯示模式或結束遊戲，並相應更新遊戲狀態。
而勝利檢查則是在 task0 和 task1 的下半部份
這樣設計的目的是讓每個協程能夠專注於不同的遊戲邏輯，並且通過協程切換來實現並行運行。每個協程在運行過程中會使用 setjmp 和 longjmp 來保存與恢復上下文，這樣就能夠在需要時切換任務，達到協程的效果。
而勝利檢查則是在 task0 和 task1 的下半部分。每當玩家進行一次移動後，會先調用 task_add(task) 和 task_switch() 來切換協程，讓 task2 執行，這個任務負責監聽用戶的輸入。當控制權返回到當前任務時，會接著調用 check_win() 函式來檢查遊戲是否結束。如果 check_win() 檢查到某一方玩家獲勝，則會立即重置棋盤並結束遊戲循環。
而剩餘時間顯示和執行步驟顯示則與核心層級的所使用的方法類似，將根據其設計進行更新和呈現。
當設計完成使用者層級的遊戲後，我們需要實作模式切換，使遊戲能夠在使用者層級和核心層級之間進行切換，從而讓遊戲在不同層級上運行。
關鍵不是「不同層級」，而是 mode switch 的過程中，要傳遞什麼狀態
我採取的作法是使用一個布林代數 user_mode 來去紀錄現在是什麼模式，而 switch_counting 是來決定要開啟或關閉設備檔案所使用的變數， user_display 是使用者層級的遊戲來決定是否顯示， user_flag 則是用來判斷是否已經超過 16 盤:
當程式剛開始執行時，它會在核心模式下運行，並與設備檔案進行交互。為了實現切換至使用者模式的功能，我在 listen_keyboard_handler 函式和 main 函式中加入了下列程式碼：當電腦接收到鍵盤輸入 Ctrl+R 時，程式會執行以下操作：關閉當前打開的設備檔案，並切換至使用者模式。當再次接收到 Ctrl+R 時，程式會重新開啟設備檔案，並返回核心模式。這樣的設計使得程式能夠在核心模式與使用者模式之間靈活切換：
這為此次的 Commit 933f275 。
統計不同 AI 實作機制對系統負載的使用率
在實做之前我先閱讀了Linux 核心的浮點數運算了解到我們在 Linux 核心模式中仍可使用浮點運算，但這不僅會拖慢執行速度，還需要手動儲存/取回相關的 FPU 暫存器，因此核心文件不建議在核心中使用到浮點運算。
在過程中，我也查閱了 Load Average 的計算公式，如下所示：
- : 時間 t 的平滑均值。
- : 時間 t-1 的平滑均值。
- : 時間 t-1 的實際值。
- : 平滑因子 (smoothing factor)。
對應 Linux 核心程式碼如下所示: (取自 include/linux/sched/loadavg.h)
- = newload
- = load
- = active (目前 'RUNNABLE + TASK_UNINTERRUPTIBLE' Process 總數: 全域變數 calc_load_tasks)
- = exp
提供數學分析
在了解完上述公式後我將 #include <linux/sched/loadavg.h> 標頭檔引入 main.c ，以便於在 main.c 中使用其中定義的巨集與計算函式。
引入後，我定義了一個名為 ai_load_t 的結構體，用來描述每個 AI 的負載狀態，其成員包括一個 atomic_long_t 型別的 active_tasks，用來追蹤 AI 使用 CPU 的期間，以及一個 unsigned long 型別的 load_avg_fp，以定點數格式儲存平滑化的平均負載值。
同時也設計了兩個函式用於負載查詢與更新：
update_ai_load_time() 根據 AI 每一步實際執行所花費的時間（以奈秒為單位），計算對應的負載量，並透過指數衰減平均方式更新該 AI 的平滑負載指標；get_ai_load_percent() 則將定點數格式的平均負載轉換為整數百分比，方便進行輸出、顯示與比較。
當定義好上述的函式後，我將其整合至 ai_one_work_func 與 ai_two_work_func 中。在這兩個負責執行各自 AI 回合邏輯的工作函式中，於每一步運算結束後，會根據實際的執行耗時呼叫 update_ai_load_time()，以更新對應的負載狀態。接著，可透過 get_ai_load_percent() 取得目前的使用率百分比。
這些負載資訊不僅用於內部統計，也會與棋盤狀態一併透過 produce_board() 函式輸出至 kfifo 緩衝區，供使用者空間讀取與分析。produce_board() 負責將當前棋盤的編碼狀態，以及兩個 AI 的即時負載百分比轉換為字串格式，打包進緩衝區中。
最後成功顯示於使用者空間：
