Linux 核心專題: 改進 kxo

執行人: weiso131, Ian-Yen

任務描述

以第三份作業為基礎、搭配課堂討論和觀摩學員的成果，提出 kxo 的改進方案並落實，至少該涵蓋以下：

• 允許核心模組切換 negamax, reinforcement learning (RL), Monte Carlo tree search (MCTS), TD learning 等演算法 (可追加更多演算法的實作)，並得以在使用者空間進行訓練
• 縮減使用者和核心空間通訊的成本
• 改進棋盤展現的方式，並修訂核心通訊介面
• 支援多使用者並強化安全機制
• 在不犧牲棋力的前提，降低 CPU 使用率
• 探討 lock-free 的設計
• 充分展現多核處理器的任務執行狀況，善用 Ftrace 和 eBPF 一類的工具

縮減使用者和核心空間通訊的成本

若使用者端能保存過去的棋盤資料，傳遞一步棋的資料就能做到有效的更新
一步棋的資料包含

1. 誰下的，有 2 種可能
2. 下在哪，考慮第一步的情況有 16 種可能
3. 是否分出勝負

總共需要 6 bits 來表達一步棋的資料

此外，考慮多使用者的情形，雖然可藉由 task_id 區分不同 task 的要求
但考慮一個 task 多次開啟 kxo ，仍需要傳遞使用者 id 來區分身份
此時
read 所需的 buffer 大小就是 max(id 所需 bit, 64)
write (使用者端下棋) 所需的 buffer 大小就是 id 所需 bit + 64

改進棋盤展現的方式，並修訂核心通訊介面

在使用者端繪製棋盤

紀錄棋盤歷史紀錄

ctrl + P 與 ctrl + Q 控制

刪除 kxo_state

由於棋盤歷史紀錄已交由使用者端儲存，只要持續執行 read 操作， ctrl+P 暫停的功能可以透過控制是否繼續繪製新的棋盤來實現，不需要 attr_obj.display 來決定是否傳送新的棋盤。而 ctrl+Q 的功能其實可以單純的結束迴圈並關閉 kxo ，核心不需要針對 ctrl+Q 進行額外的處理，因此 attr_obj.end 也沒有保留的必要。至於 attr_obj.resume 原本在 main.c 就沒有被使用。

此外，在 [PATCH] sysfs: tightened sysfs permission checks 中， sysfs 預設不開放 other 的寫入權限，這沒辦法單純透過調整核心模組程式碼來更改，這對於核心模組而言可能是不必要的限制。

考慮上述的情況，應該將 kxo_state 移除。

2c63b8e
7047748
43a6056

同時顯示多個棋盤

核心通訊介面

列表

• ioctl get_id
• ioctl set id permission
• ioctl release id
• read
• write
• open
• release

permission

用一個 byte 儲存權限資料
前 8 個 bit 代表 player2 要使用的權限
前 8 個 bit 代表 player1 要使用的權限

若權限設為 USER_CTL ，輪到對應的玩家時，就能使用 write 操作，但不能使用 read 操作。 設成其他權限時，會使用對應的演算法，此時不能使用 write 操作但可以使用 read 操作。 相關的定義在 kxo_ioctl.h。

ioctl get_id

879d5fb

• 取得一個全新的 user id
• buffer 內部要放置 permission 的設定

ioctl set id permission

• 更改某個 id 的 permission ，達成動態切換 ai 算法
• 需要 lock

ioctl release id

• 釋放某個 id 的 user data

read

• 根據使用者端傳送的 buffer 中的 user_id ，取得對應 user 棋盤的更新
• 若 user_id 不存在，會回傳 EFAULT ，使用者端可做相關檢查
• 若輪到 USER_CTL 權限的玩家，會回傳 -EPERM

write

• 使用者端下棋
• 若當前輪到的玩家不是由使用者端操控的，則拒絕請求
• 若下的位置非法，拒絕請求
• 直接更新棋盤狀態，不需要 lock

open

• 同個 pid 的 thread 只能 open 一次，避免 release 出問題

release

• 釋放該 pid 下的所有 user_data

支援多使用者並強化安全機制

棋盤狀態

• 核心模組: 儲存當前棋盤與相關狀態
• 使用者: 儲存當前棋盤狀態、所有棋局的移動紀錄
• 棋盤資料傳遞: 誰下了哪一步棋

在我原本的 kxo 專案，為了讓不同的使用者觀察到同一個盤面，且在任一使用者按下 Ctrl + Q 時同步輸出紀錄，移動紀錄是被存放在核心的。
然而，現在的情況是考慮多個使用者獨立的狀態，而移動紀錄也只會被存取一次，那將移動紀錄存放在核心空間就顯得不必要，而且移動到使用者端會有以下優點:

1. 在任何使用者按下 ctrl + Q 之後，就不需要再跟核心模組有任何互動，這能減少核心模組的工作負擔
2. 減少核心 heap 空間浪費
3. 讓使用者端保有棋盤紀錄，能讓資料傳遞只需要 誰下了哪一步棋

此時核心模組的主要功能就是裁判，詳細功能如下:

1. 檢查新的這步棋是否合法
2. 判斷勝負
3. namespace
4. 使用者身分驗證

第一個功能考慮到之後需要做到 人工智慧程式可指定運作於使用者/核心層級
從使用者傳過來的移動不能保證是合法的，因此有驗證的必要

第二個功能是原本就存在的功能

第三、四個功能會獨立出來討論

使用者身分驗證

參考 rota1001

最直觀的想法

• 實作一個 ioctl 讓使用者決定一些資訊，同時回傳 user_id 給使用者

如果有攻擊者反覆呼叫 ioctl ，這個系統會很容易被灌爆記憶體？

• 若在建立 id 時就分配 namespace ，明顯會被灌爆
• 若在要求第一步的時候分配 namespace ，攻擊者同樣可以只呼叫第一步再進行 ioctl

跟 rota1001 討論
我提出可能可以藉由得知 task id 來作為 ban 使用者的依據
他也認為這個解法可能可行，只要能夠得知哪個 process 建立了一堆 child process
但他也提出這個問題應該是可以不要考慮的，因為 kxo 的使用者想搞事，消耗的也是自己的資源

後來想想，若在這個前提下能拿到 task id 等等跟 task struct 綁在一起的參數，就不用另外生成核心模組的 uid

然而，在 5/20 與老師下課的討論時，問到作業要求引入 corutine 的意義，他希望我們可以利用 corutine 做到在同個畫面中顯示多個棋局，在此情況下，一個 thread 就可能有多個 user ，然而一個 thread 就只有一個 task id ，在此情況下仍要引入其他機制來辨識使用者身份。

user_data

b7fdce5

• 使用者 id
• 使用者當前棋盤狀態
• 使用者自己的 kfifo

kfifo

關於為什麼會選擇讓每個使用者擁有自己的 kfifo 。一個很明顯的好處是可以減少 lock 的使用， kfifo 雖然提供 kfifo_out_peek 可以先判斷 kfifo 的第一項是不是當前使用者在等待的資料，再決定要不要拿出來。 但 kfifo 只保證 SPSC 的情況下是 lock free 的，這種情況得加上 lock。

核心模組並行

f0242a7

原先的 work_function, tasklet_function, time_handler 的設計並沒有考慮不同使用者的問題，要讓它們能夠正確執行，必須進行修改。

work_function

原先的 work_function 分成 ai1, ai2, drawboard
並且在全域存取 table 與 turn
要處理多使用者必須將棋盤相關資訊放在該使用者對應的結構
然而， work_func 沒辦法藉由 queue_work 的時候取得參數

觀察 work_func 的格式

void work_func(struct work_struct *w)

它會傳遞 work_struct * ，也就是 work item 作為參數
因此只要把 work_struct 放進 user_data ，就能在 work_func 內利用 container_of 取得 user_data 的位址

user_data 內的 work_struct 可利用 INIT_WORK 進行初始化

觀察原本的 ai_one_work_func 與 ai_two_work_func 的程式可發現，它們的差異只有使用的 AI 算法和棋子的圖案相反，剩下的實作邏輯完全一樣
考慮之後需要動態切換 ai 演算法，實作一個通用的 ai_work_func 然後存取 user_data 當下的資訊決定輪到誰比較合理

至於 drawboard 這個函式，其原本的功能是繪製出用來顯示的棋盤，並放入 kfifo ，然而，在往後的修改中，需要放入 kfifo 的資訊只有下了哪一步棋 ，如果能跟 ai_work_func 放在一起就能直接取得結果，不用額外的 buffer 存放。
此外，能將下棋與將結果放入 kfifo 在同個 work 處理，會有更好的可擴展性， work 不必等待前一個 work 執行完畢再執行。

drawboard 還有另外一個重要的功能，就是 wake_up_interruptible(&rx_wait);
使用者在 read 的時候，若 kfifo 內沒有東西，會進入睡眠狀態，直到 wake_up_interruptible(&rx_wait); 被呼叫，此時再嘗試取得 kfifo 的內容。
在多個使用者的情況下，若共用一個 rx_wait 會導致多個 read 被頻繁喚醒，但只有部份的 read 能真正結束等待，比較合理的作法是讓 user_data 也保有一個 rx_wait

time_handler

原本的 time_handler 負責的是確認棋盤時否分出勝負
來決定要重置棋盤，還是呼叫 tasklet_function 將 work_item 放進 workqueue

然而，判斷是否分出勝負以及重製棋盤這兩個功能，其實可以在 work_func 完成，若保留在 time_handler 還會有兩個缺點

1. 每個 user 都會需要 consumer, producer lock 來維護

   在有多個 cpu 的情況下， time_interrupt 與 work 可能發生在不同 cpu ，導致 racing 嗎？

2. 隨著使用者越來越多， time_handler 的執行時間會變更長，但 time_interrupt 是沒辦法被排程的，因此執行時間不應該那麼長

因此，原本的 time_handler 的功能只有呼叫 tasklet_function 會被保留

tasklet_function

原本的 tasklet 會需要一個 finish ，確保下棋完成
否則可能會出現連下兩步的情況
然而，只有一種 work_item 則沒有這個問題

由於 tasklet 物件不會被重複排列的特性，可以確保系統不需要反覆的存取所有 work 並且嘗試放進 workqueue

為了方便存取，可以利用 list_head 將所有 user_data 串起來

注意用語: access 是「存取」，而非「訪問」(visit)

若現在輪到使用者下棋，則不排入 work_queue

除此之外，在多使用者的情況下，它還需要做到回收使用者資料的功能
在原本的程式中，只有單個使用者的情況下 release ，可以無腦的把 work_queue 清空
然而，在多使用者的情況下不能這麼做，而且需要釋放不再使用的使用者

若需要釋放的使用者已經不在 work_queue 中，可以直接將它釋放
反之，則等待它完成工作，此時就與上述情況相同
這會需要一個變數紀錄它是否已經不再使用

然而，在實際考慮到 work_queue API 之後，發現直接在 tasklet_function 內直接進行 release 是不可行的。
work_queue 提供 cancel_work_sync ，可確保在這個函式回傳之後，可以安全的釋放 work_item ，然而，這個函式可能會進入睡眠， tasklet function 是不允許睡眠的。
因此，應該要將 release 的工作放在其他地方，可藉由將需要 release 的 user_data 放入一個 trash_list ，再藉由其他方法釋放記憶體

namespace

namespace 資料結構選擇

124ceaa

根據前面的討論， namespace 需要區分不同的 tid ，同個 tid 也會有多個不同的使用者，某個 tid 使用 close 時，需要將對應 tid 之下的所有 user_data 釋放。

若將 tid 與 user_id 以某種方式相加並取得一個 id ，沒辦法直接反應 tid 與 user_id 的親子關係，在新增或釋放 user_data 時，需要額外的資料結構維護，因此存在一個結構，紀錄某個 tid 之下有哪些 user 會是比較好的選擇。

為了 O(1) 取得 tid 對應的結構，使用陣列是個好選擇，但是直接開一個 pid_max 大小的陣列顯得很浪費，使用 hash table 能更有效的節省空間。 當 hash table 發生碰撞時，可以使用 hlist 處理

namespace 使用 hlist 需要讀寫鎖， add, del 需要 write_lock ，存取只需要 read_lock ，為了避免一次阻塞大量的 thread ，可以每一個 hash_table 的 hlist_head 搭配一個 rw_lock

維護 user_id

完全使用 tasklet 來管理 userdata 該在 user_list 還是 trash_list

• unuse 可以 atomic
• hlist 維護需要 lock (tasklet 跟 user 建立)，此外，由於過程會有 tasklet function 參預 lock 競爭，須使用 spin_lock 避免進入睡眠

建立與刪除使用者

1. 使用爆搜取得使用者 id ，可以用 CAS 來避免 lock

   • 建立 user 的操作的次數不會那麼頻繁，而且一個 tid 的 user 數量是有限的
   • 好實作

2. 使用 queue 維護 user_id ，會需要一個 lock 來避免衝突

   • O(1) 建立 user
   • 刪除 user 仍然需要額外的資料結構維護(例如：紅黑樹)，才能做到
     $O(ln(n))$

user_data 操作

aab3436(此 commit 未實作 remove_user)

為了界面的統一， main.c 需要存取 user_data 的函式會在 namespace 實作

• add_user
• remove_user
• get_user_data
• user_list_queue_work
  tasklet function 將 work_item 放入 work_queue 的工作，會由這個函式完成，這樣能有效維護 user_list 與 trash_list
• release_namespace
  這只能在 rmmod 時被呼叫，目的是真正清空 user_list 與 trash_list 上所有 uesr_data 動態配置的記憶體，在未來可以考慮加入定期清理的函式，但這個函式能確保記憶體被徹底清空，始終有存在的必要

在不犧牲棋力的前提，降低 CPU 使用率

Todo: cmwq

探討 lock-free 的設計

lock-free vs lock-less vs wait-less

並行程式設計: Lock-Free Programming

• wait-free 是 non-blocking 之中強度最高的，它保證所有的指令可以 bound 在某個時間內完成，也就是所有的執行緒經過一段足夠的時間後，一定會有所進展
• lock-free 相較於 wait-free 稍微弱一點，它允許部份執行緒被暫停，但仍然保證整體程式的其他部份會有進展。最差的情況下，就算只有一個執行緒在執行，其他所有執行緒都在等待，仍然屬於 lock-free
• lockless: 避免使用 lock 而能夠安全無誤地操作共用資料，不使用 mutex lock (e.g. busy waiting)，不代表就是 lock-free
• obstruction-free non-blocking 中最弱的，僅保證在沒有競爭情況下，執行緒可以持續運作，倘若發生競爭，則 obstruction-free 無法提供任何保證。換言之，可能會發生 livelock

原本的程式可以移除 producer 與 consumer lock

觀察程式碼與其運作行為， ai_function 與 drawboard 之間需要一個 producer_lock 確保 table 的一致性。此外，如果 time_interrupt 遇到已經分出勝負的情況，也需要 producer, consumer lock 處理競爭問題。

若想不再依賴 producer lock 與 consumer lock ，可參考 考慮核心模組並行
原本的方法 time interrupt 存在 producer lock ，若遇到 drawboard function 拿走了 lock 並卡住，又剛好需要重製棋盤，會導致整個系統沒有進展。

在我的方法，即使存在某個 work function 卡住，因為沒有共用的 lock ，其他 work function 也能正常執行， time interrupt 與 task let 也能持續運作。