:::info
解析 [kxo 專案](https://github.com/sysprog21/kxo)的程式
此資料不適合從頭到尾的閱讀，適合用查詢的方式查看。
:::
# main.c
## timer_handler()
`WARN_ON_ONCE(!in_softirq());`
-> 判斷是否在 softirq context
-> 為了模擬 hardirq ，使用 timer interrupt
`local_irq_disable();`
-> 將 CPU 關閉接收其他 interrupt
`char win = check_win(table);`
-> 判斷是否已有輸贏
-> 回傳 `' '` ，表示未有輸贏，繼續比賽；其餘則表示已有輸贏，下一場比賽。
``` c
if (win == ' ') {
ai_game();
mod_timer(&timer, jiffies + msecs_to_jiffies(delay));
}
```
-> `win == ' '` : 格子中沒有 o/x 的符號，表示未有輸贏
-> `ai_game()` : 進入 tasklet ，登記 workqueue 的排程
-> `mod_timer` : 再次呼叫 `timer_setup()`
``` c
else {
read_lock(&attr_obj.lock);
if (attr_obj.display == '1') {
int cpu = get_cpu();
pr_info("kxo: [CPU#%d] Drawing final board\n", cpu);
put_cpu();
mutex_lock(&producer_lock);
draw_board(table);
mutex_unlock(&producer_lock);
/* Store data to the kfifo buffer */
mutex_lock(&consumer_lock);
produce_board();
mutex_unlock(&consumer_lock);
wake_up_interruptible(&rx_wait);
}
if (attr_obj.end == '0') {
memset(table, ' ',
N_GRIDS); /* Reset the table so the game restart */
mod_timer(&timer, jiffies + msecs_to_jiffies(delay));
}
read_unlock(&attr_obj.lock);
pr_info("kxo: %c win!!!\n", win);
}
```
`attr_obj` : device attribute，用來與userspace溝通
`read_lock` :
`mutex_lock` / `mutex_unlock` :
`draw_board` : 將 `table` 的 ooxx 加入分隔線後填入 `draw_buffer` ，方便印出來時閱讀
`produce_board` : 將 `draw_buffer` 的資料放入 fifo 之中 ==為什麼要放入fifo?== (有API可以呼叫並且保護資料嘛？)
`wake_up_interruptible` : 用來喚醒 wait queue 中一個 process ，且該函式有 memory barrier 的功能。
- 根據 [Linux kernel memory barriers](https://www.kernel.org/doc/html/next/core-api/wrappers/memory-barriers.html)
> wake_up_process() always executes a general memory barrier.
> The available waker functions include: `wake_up_interruptible()`
>
- 根據 [Kernel Korner - Sleeping in the Kernel](https://www.linuxjournal.com/article/8144)
> wake_up_interruptible wakes up one process that was sleeping on the smbiod_wait waitqueue.
`memset` : 用給定值填滿記憶體空間
``` c
* memset - Fill a region of memory with the given value
* @s: Pointer to the start of the area.
* @c: The byte to fill the area with
* @count: The size of the area.
```
`mod_timer` : 初始化 timer ，呼叫`timer_setup(&timer, timer_handler, 0);`
## draw_board(table)
> <font color = "#F0F">將 `table` 的 ooxx 填入 `draw_buffer` ，方便印出來閱讀 </font>
`draw_buffer[0]` 跟 `draw_buffer[1]` 是為了換兩行（空一行）
``` c
int i = 0, k = 0;
draw_buffer[i++] = '\n';
smp_wmb();
draw_buffer[i++] = '\n';
smp_wmb();
```
撰寫有 **ooxx** 的文字進入 `draw_buffer`
``` c
for (int j = 0; j < (BOARD_SIZE << 1) - 1 && k < N_GRIDS; j++) {
draw_buffer[i++] = j & 1 ? '|' : table[k++];
smp_wmb();
}
```
-> `(BOARD_SIZE << 1) - 1` ：xxoo + 間隔的數量
-> `k < N_GRIDS`：確保無超出棋盤大小
撰寫**間隔**的文字進入 `draw_buffer`
``` c
for (int j = 0; j < (BOARD_SIZE << 1) - 1; j++) {
draw_buffer[i++] = '-';
smp_wmb();
}
```
## produce_board
> <font color = "#F0F">將 `draw_buffer` 的資料放入 fifo 之中 </font>
``` c
len = kfifo_in(&rx_fifo, draw_buffer, sizeof(draw_buffer));
* kfifo_in - put data into the fifo
* @fifo: address of the fifo to be used
* @buf: the data to be added
* @n: number of elements to be added
* return the number of copied elements to fifo.
```
- 根據 [lib/kfifo.c](https://elixir.bootlin.com/linux/v6.14.3/source/lib/kfifo.c#L113)
- 在 `rx_fifo` 空間充足時，`len = sizeof(draw_buffer)`
- 在 `rx_fifo` 空間不足時，`len < sizeof(draw_buffer)`
- `kfifo_in`的輸出是實際加入 fifo 的 buffer size
如果發現 `len < sizeof(draw_buffer)` ，印出警告 -> `rx_fifo` 空間不足
``` c
if (unlikely(len < sizeof(draw_buffer)) && printk_ratelimit())
pr_warn("%s: %zu bytes dropped\n", __func__, sizeof(draw_buffer) - len);
```
- `unlikely`: 表示幾乎不可能發生的情況（提醒其他人），並[優化 Compiler](https://stackoverflow.com/questions/109710/how-do-the-likely-unlikely-macros-in-the-linux-kernel-work-and-what-is-their-ben)。
``` c
# define likely(x) __builtin_expect(!!(x), 1)
# define unlikely(x) __builtin_expect(!!(x), 0)
```
- 需要嚴謹的分析後才可以使用 `likely` / `unlikely`
- `printk_ratelimit` : 會限制警告訊息的速度，避免印出過多的警告訊息。
根據 [Documentation for /proc/sys/kernel/](https://www.kernel.org/doc/html/next/admin-guide/sysctl/kernel.html#printk-ratelimit) 的定義
> Some warning messages are rate limited. printk_ratelimit specifies the minimum length of time between these messages (in seconds). The default value is 5 seconds.
>
> A value of 0 will disable rate limiting.
印出當前的 `rx_fifo` 的使用量
``` c
pr_debug("kxo: %s: in %u/%u bytes\n", __func__, len, kfifo_len(&rx_fifo));
// kxo: my_func: in 64/128 bytes
```
## attr_obj
如何利用 sysfs 建立 device attribute 讓核心模組與使用者相互溝通？
-> 參見 [Linux Kernel Module Programming Guide: Chap8](https://sysprog21.github.io/lkmpg/)
建立 device attribute
``` c
static DEVICE_ATTR_RW(kxo_state);
```
- 參見 [include/linux/device.h](https://elixir.bootlin.com/linux/v6.14.3/source/include/linux/device.h#L173)
``` c
#define DEVICE_ATTR_RW(_name) \
struct device_attribute dev_attr_##_name = __ATTR_RW(_name)
```
- `dev_attr_kxo_state = ATTR_RW(kxo_state)`
``` c
#define __ATTR_RW(_name) __ATTR(_name, 0644, _name##_show, _name##_store)
```
``` c
#define __ATTR(_name, _mode, _show, _store) { \
.attr = {.name = __stringify(_name), \
.mode = VERIFY_OCTAL_PERMISSIONS(_mode) }, \
.show = _show, \
.store = _store, \
}
```
- `kxo_state_show` : read，當使用者呼叫 cat 時
- `kxo_state_store` : write，當使用者呼叫 echo 時
建立 `kxo_state_show` for read
``` c
static ssize_t kxo_state_show(struct device *dev,
struct device_attribute *attr,
char *buf)
{
read_lock(&attr_obj.lock);
int ret = snprintf(buf, 6, "%c %c %c\n", attr_obj.display, attr_obj.resume,
attr_obj.end);
read_unlock(&attr_obj.lock);
return ret;
}
```
- ==為什麼要用read_lock==
- [`snprintf`](https://linux.die.net/man/3/snprintf) : 為比較安全的 printf，因為不會寫超過指定大小
- `s` : string
- `n` : 要輸入的 size
建立 `kxo_state_store` for write
``` c
static ssize_t kxo_state_store(struct device *dev,
struct device_attribute *attr,
const char *buf,
size_t count)
{
write_lock(&attr_obj.lock);
sscanf(buf, "%c %c %c", &(attr_obj.display), &(attr_obj.resume),
&(attr_obj.end));
write_unlock(&attr_obj.lock);
return count;
}
```
- ==為什麼要用write_lock==
- [`sscanf`](https://linux.die.net/man/3/sscanf) : 將 `buf` 的內容存進 `attr_obj` 中
- example
``` c
char input[] = "123 4.56 hello";
int a;
float b;
char word[20];
sscanf(input, "%d %f %s", &a, &b, word);
```
這段 code 會從 input 中讀出：
`%d` → `a = 123`
`%f` → `b = 4.56`
`%s` → `word = "hello"`
`sscanf()` 會回傳成功讀取的項目數，在這個例子裡會是 3。
``` c
static struct kxo_attr attr_obj;
```
``` c
struct kxo_attr {
char display;
char resume;
char end;
rwlock_t lock;
};
```
- `display` :
- `resume` :
- `end` :
- `lock` :
## ai_game()
``` c
static void ai_game(void)
{
WARN_ON_ONCE(!irqs_disabled());
pr_info("kxo: [CPU#%d] doing AI game\n", smp_processor_id());
pr_info("kxo: [CPU#%d] scheduling tasklet\n", smp_processor_id());
tasklet_schedule(&game_tasklet);
}
```
`WARN_ON_ONCE(!irqs_disabled())` : 當下若還能接收其他來自外界的中斷，就需要警告開發者；換句話說，**此程式不希望被來自外界的中斷給中斷**，因而提出警告，但是並沒辦法禁止中斷發生。
`tasklet_schedule` : 將新的 `&game_tasklet` 加入 `tasklet_vec`
- 參見 [Interrupts and Interrupt Handling. Part 9.](https://0xax.gitbooks.io/linux-insides/content/Interrupts/linux-interrupts-9.html)
``` c
static inline void tasklet_schedule(struct tasklet_struct *t)
{
if (!test_and_set_bit(TASKLET_STATE_SCHED, &t->state))
__tasklet_schedule(t);
}
void __tasklet_schedule(struct tasklet_struct *t)
{
unsigned long flags;
local_irq_save(flags);
t->next = NULL;
*__this_cpu_read(tasklet_vec.tail) = t;
__this_cpu_write(tasklet_vec.tail, &(t->next));
raise_softirq_irqoff(TASKLET_SOFTIRQ);
local_irq_restore(flags);
}
```
- 因為 tasklet 為一種 softirq，所以需要在 interrupt context中執行
- `local_irq_save(flag)` : save the state of the IF (interrupt flag) and **disable interrupt**
- `local_irq_restore(flag)` : restore IF and **enable interrupt**
- 更新 `tasklet_vec`
- `t->next = NULL;` : 將 t->next 指向一個空白的空間
- `*__this_cpu_read()` : 將 t 放置目前的 tasklet_vec 的尾端
- `__this_cpu_write()` : 將新 tasklet t 的 next 成員的地址寫入到當前 CPU 的 tasklet_vec 的 tail 成員中
- `game_tasklet` : 為一個 struct tasklet 的結構，並有一個函數指標指向 `game_tasklet_func`
### DECLARE_TASKLET_OLD
``` c
static DECLARE_TASKLET_OLD(game_tasklet, game_tasklet_func);
```
- 定義 name ，並且以 `_func` 作為 func 函數指標指向的函數
``` c
#define DECLARE_TASKLET_OLD(name, _func) \
struct tasklet_struct name = { \
.count = ATOMIC_INIT(0), \
.func = _func, \
}
```
-> 因為 `.func = _func`，這一行程式讓一個名為func的函式指標指向 `_func`
## game_tasklet_func()
如果不在 interrupt context 和 softirq context 的話，提出警告。
``` c
WARN_ON_ONCE(!in_interrupt());
WARN_ON_ONCE(!in_softirq());
```
保證「只讀一次、完整地」取值
``` c
READ_ONCE(finish);
READ_ONCE(turn);
```
- turn 表示參賽者 `'X'` 或 `'O'`
- finish 表示參賽者是否下完棋。
- 開始下棋～下完棋 `0 (False)`
- 下完棋～下次開始下棋 `1 (True)`
保證「只寫一次」值
``` c
WRITE_ONCE(finish, 0);
```
- 將 0 寫入 finish 中
輪到 `O` 時，將
``` c
if (finish && turn == 'O') {
WRITE_ONCE(finish, 0);
smp_wmb();
queue_work(kxo_workqueue, &ai_one_work);
```
`queue_work` : 將 `ai_one_work` 中的函式放入 `kxo_workqueue` 的排程中
`kxo_workqueue` : 根據排程順序放置函式的 queue
`ai_one_work` : 透過 `DECLARE_WORK` 宣告一個 `work_struct` 的結構，在這邊會呼叫此結構中的函式。
- 根據 [/include/linux/workqueue.h](https://elixir.bootlin.com/linux/v6.14.3/source/include/linux/workqueue.h#L636)
``` c
* queue_work - queue work on a workqueue
* @wq: workqueue to use
* @work: work to queue
```
- 根據 [Interrupts and Interrupt Handling. Part 9.](https://0xax.gitbooks.io/linux-insides/content/Interrupts/linux-interrupts-9.html) 說明 `queue_work` 的用途
``` c
static inline bool queue_work(struct workqueue_struct *wq,
struct work_struct *work) {...}
```
> macro that takes work_struct structure that has to be created and the function to be scheduled in this workqueue. After a work was created with the one of these macros, we need to put it to the workqueue.
-> work 結構中函數會被排入 workqueue 的排程中
- 根據 [/include/linux/workqueue_types.h](https://elixir.bootlin.com/linux/v6.14.3/source/include/linux/workqueue_types.h#L16) 查看 work_struct 的結構
``` c
struct work_struct {
atomic_long_t data;
struct list_head entry;
work_func_t func;
...
}
```
將印出 table 的函式旁入行程中，以便即時查看進度。
``` c
queue_work(kxo_workqueue, &drawboard_work);
```
`drawboard_work` 透過 `DECLARE_WORK` 宣告一個 `work_struct` 的結構
### DECLARE_WORK
> <font color = "#F0F">宣告了一個名為 `ai_one_work` 的工作項（struct work_struct），並將其處理函數設定為 `ai_one_work_func`。當 `ai_one_work` 被排入 workqueue 並執行時，`ai_one_work_func` 這個函數將會被呼叫來執行實際的工作。</font>
``` c
static DECLARE_WORK(ai_one_work, ai_one_work_func);
```
- 根據 [/include/linux/workqueue.h](https://elixir.bootlin.com/linux/v6.14.3/source/include/linux/workqueue.h#L250)
``` c
#define DECLARE_WORK(n, f) \
struct work_struct n = __WORK_INITIALIZER(n, f)
```
``` c
#define __WORK_INITIALIZER(n, f) { \
.data = WORK_DATA_STATIC_INIT(), \
.entry = { &(n).entry, &(n).entry }, \
.func = (f), \
__WORK_INIT_LOCKDEP_MAP(#n, &(n)) \
}
```
## ai_one_work_func()
後續程式會用到 mutex ，須確保程式在 process context 執行，否則會 deadlock
``` c
WARN_ON_ONCE(in_softirq());
WARN_ON_ONCE(in_interrupt());
```
-> 如果程式在 softirq context 或 interrupt context ，提出警告。
在這個區塊中的程式碼保證會在同一個 CPU 上執行，且不會被核心搶佔
``` c
cpu = get_cpu();
...
put_cpu();
```
- 參見 [Unreliable Guide To Hacking The Linux Kernel](https://www.kernel.org/doc/html/next/kernel-hacking/hacking.html) 和 [/include/linux/smp.h](https://elixir.bootlin.com/linux/v6.14.3/source/include/linux/smp.h#L244)
> get_cpu() disables preemption (so you won’t suddenly get moved to another CPU) and returns the current processor number, between 0 and NR_CPUS. Note that the CPU numbers are not necessarily continuous. You return it again with put_cpu() when you are done.
- ==`get_cpu()` vs `preempt_disable()` vs `local_irq_disable`==
- 參見 [/include/linux/smp.h](https://elixir.bootlin.com/linux/v6.14.3/source/include/linux/smp.h#L275)
``` c
#define get_cpu() ({ preempt_disable(); __smp_processor_id(); })
```
- 參見 [/include/linux/irqflags.h](https://elixir.bootlin.com/linux/v6.14.3/source/include/linux/irqflags.h#L206)
``` c
#define local_irq_disable() \
do { \
bool was_disabled = raw_irqs_disabled();\
raw_local_irq_disable(); \
if (!was_disabled) \
trace_hardirqs_off(); \
} while (0)
```
- 未閱讀 [Linux 核心設計: `PREEMPT_RT` 作為邁向硬即時作業系統的機制](https://hackmd.io/@sysprog/preempt-rt) 及 [Linux 核心搶佔](https://hackmd.io/@sysprog/linux-preempt)
==why?==
``` c
mutex_lock(&producer_lock);
... // critical section
mutex_unlock(&producer_lock);
```
將 `mcts(table, 'O')` 的回傳值輸入 `move` -> 推測是
``` c
int move;
WRITE_ONCE(move, mcts(table, 'O'));
```
-> 推測 move 是指要填入 table 的位置 ==須再細讀 `mcts()`==
只要 `move` 不是 `-1` 就可以將 `O` 填入
``` c
if (move != -1)
WRITE_ONCE(table[move], 'O');
```
-> `move = -1` 為 move 的初始值 ==?==
## ai_two_work_func()
基本上都與 `ai_one_work_func()` 相同，只有計算移動的演算法不同，不同的段落如下
- 在 `ai_one_work_func()` 的程式：
``` c
int move;
WRITE_ONCE(move, mcts(table, 'O'));
```
- 在 `ai_two_work_func()` 的程式：
``` c
int move;
WRITE_ONCE(move, negamax_predict(table, 'X').move);
```
## drawboard_work_func()
幾乎與 `timer_handler()` 某一段一模一樣 ==了解差異==
``` c
read_lock(&attr_obj.lock);
if (attr_obj.display == '0') {
read_unlock(&attr_obj.lock);
return;
}
read_unlock(&attr_obj.lock);
```
``` c
mutex_lock(&producer_lock);
draw_board(table);
mutex_unlock(&producer_lock);
```
``` c
/* Store data to the kfifo buffer */
mutex_lock(&consumer_lock);
produce_board();
mutex_unlock(&consumer_lock);
```
``` c
wake_up_interruptible(&rx_wait);
```
## open_cnt {}
存放一個計數器
``` c
static atomic_t open_cnt;
```
- 參見 [/include/linux/types.h](https://elixir.bootlin.com/linux/v6.14.3/source/tools/include/linux/types.h#L79)
``` c
typedef struct {
int counter;
} atomic_t;
```
## kxo_open()
``` c
if (atomic_inc_return(&open_cnt) == 1)
mod_timer(&timer, jiffies + msecs_to_jiffies(delay));
pr_info("openm current cnt: %d\n", atomic_read(&open_cnt));
```
- `atomic_inc_return(&open_cnt)`：原子地把 `open_cnt` 數值加 1，並回傳加完後的值。
- 如果回傳值是 1，代表這是第一次有人開啟裝置（也就是之前是 0），就執行下面的 `mod_timer()`。
- ==為什麼初始值一定是 0? 哪裡有定義？==
- 印出目前 `open_cnt` 的數值，也就是目前有多少人開啟這個裝置。
- ==`open_cnt` 怎麼修改的==
## kxo_read()
如果使用者傳來的記憶體區塊不能安全地存取，就立刻回傳 -EFAULT（記憶體錯誤）。
``` c
if (unlikely(!access_ok(buf, count)))
return -EFAULT;
```
- 參見 [/include/asm-generic/access_ok.h](https://elixir.bootlin.com/linux/v6.14.3/source/include/asm-generic/access_ok.h#L45) ==不確定是不是這份文件的解釋==
``` c
#define access_ok(addr, size) likely(__access_ok(addr, size))
```
- `buf` 是使用者提供的記憶體位址，`count` 是要讀寫的位元組數。
- 如果記憶體範圍 不合法（例如無效位址或越界），就會回傳 false。
- 參見 [/include/uapi/asm-generic/errno-base.h](https://elixir.bootlin.com/linux/v6.14.3/source/include/uapi/asm-generic/errno-base.h#L18)
``` c
#define EFAULT 14 /* Bad address */
```
如果無法順利取得 mutex（例如被中斷），就回傳 -ERESTARTSYS，表示系統呼叫被打斷，可以被重新啟動。
``` c
if (mutex_lock_interruptible(&read_lock))
return -ERESTARTSYS;
```
- 參見 [/kernel/locking/mutex.c](https://elixir.bootlin.com/linux/v6.14.3/source/kernel/locking/mutex.c#L947)
``` c
* mutex_lock_interruptible() - Acquire the mutex, interruptible by signals.
* @lock: The mutex to be acquired.
* Return: 0 if the lock was successfully acquired or %-EINTR if a
* signal arrived.
```
- 嘗試取得 `read_lock` 這個 mutex
- 如果在等待鎖的過程中被訊號打斷（例如使用者用 Ctrl+C），它會回傳 `-EINTR`
將 kfifo 的資料傳入 user space
1. 試著從 KFIFO 讀資料
2. 有資料 ➔ 直接結束
3. 沒資料
a. 非阻塞模式 ➔ 回 -EAGAIN
b. 阻塞模式 ➔ 進入睡眠，等有資料再醒來
4. 醒來後重試，直到讀到資料或出錯
``` c
do {
ret = kfifo_to_user(&rx_fifo, buf, count, &read);
if (unlikely(ret < 0))
break;
if (read)
break;
if (file->f_flags & O_NONBLOCK) {
ret = -EAGAIN;
break;
}
ret = wait_event_interruptible(rx_wait, kfifo_len(&rx_fifo));
} while (ret == 0);
```
- 參見 [/include/linux/kfifo.h](https://elixir.bootlin.com/linux/v6.14.4/source/include/linux/kfifo.h#L688) 及 [The Linux Kernel API](https://www.kernel.org/doc/html/v4.15/core-api/kernel-api.html?highlight=kfifo_to_user#c.kfifo_to_user)
``` c
* kfifo_to_user - copies data from the fifo into user space
* @fifo: address of the fifo to be used
* @to: where the data must be copied
* @len: the size of the destination buffer
* @copied: pointer to output variable to store the number of copied bytes
```
- 從 rx_fifo 把資料複製到 buf，最多 count bytes，實際讀到 read bytes
- `if (file->f_flags & O_NONBLOCK)` 當 `file->f_flags & O_NONBLOCK` 不為零時就成立。 ==須查證==
- 參見 [The File Object](https://litux.nl/mirror/kerneldevelopment/0672327201/ch12lev1sec8.html)
- file->flags 表示多個指定的 flag 被打開時
- `O_NONBLOCK` 非阻塞狀態 -> 為固定值
- 參見 [/include/linux/wait.h](https://elixir.bootlin.com/linux/v6.14.4/source/include/linux/wait.h#L481)
``` c
* wait_event_interruptible - sleep until a condition gets true
* @wq_head: the waitqueue to wait on
* @condition: a C expression for the event to wait for
* The function will return -ERESTARTSYS if it was interrupted by a
* signal and 0 if @condition evaluated to true.
```
- 如果是阻塞模式 ➔ 進入睡眠，等待 rx_fifo 裡有資料
# game.c
## line_t
> <font color = "#F0F">lines 用來定義四個方向可能連線的方式</font>
``` c
typedef struct {
int i_shift, j_shift;
int i_lower_bound, j_lower_bound, i_upper_bound, j_upper_bound;
} line_t;
const line_t lines[4] = {
{0, 1, 0, 0, BOARD_SIZE, BOARD_SIZE - GOAL + 1}, // ROW
{1, 0, 0, 0, BOARD_SIZE - GOAL + 1, BOARD_SIZE}, // COL
{1, 1, 0, 0, BOARD_SIZE - GOAL + 1, BOARD_SIZE - GOAL + 1}, // PRIMARY
{1, -1, 0, GOAL - 1, BOARD_SIZE - GOAL + 1, BOARD_SIZE}, // SECONDARY
};
```
- lines[0] 同一行，往右掃描
- lines[1] 同一列，往下掃描
- lines[2] 主角線，往右下掃描
- lines[3] 副對角線，往左下掃描
`BOARD_SIZE` : 棋盤大小 (5x5 的棋盤， `BOARD_SIZE=5` )
`GOAL` : 需要幾個連成一線才勝利 (xxoo 的 `GOAL=3` )
## check_win(t)
``` c
for (int i_line = 0; i_line < 4; ++i_line) {
line_t line = lines[i_line];
for (int i = line.i_lower_bound; i < line.i_upper_bound; ++i) {
for (int j = line.j_lower_bound; j < line.j_upper_bound; ++j) {
char win = check_line_segment_win(t, i, j, line);
if (win != ' ')
return win;
}
}
}
```
- 1st for loop: 測試四種可能連線的方向
- 2nd for loop: 橫軸範圍
- 3rd for loop: 縱軸範圍
-> 2nd & 3rd for loop 僅用來選擇連線的**起始點**
-> `check_line_segment_win()` 會判斷是否真的有連線
確認棋盤是否還有空位能填寫
``` c
for (int i = 0; i < N_GRIDS; i++)
if (t[i] == ' ')
return ' ';
return 'D';
```
`N_GRIDS` : 棋盤尺寸 ( 5x5 的棋盤， `N_GRIDS=25` )
- `N_GRIDS = BOARD_SIZE * BOARD_SIZE`
-> 確認棋盤內還有空白處
-> 若棋盤都沒有空白處則回傳 `'D'`
## check_line_segment_win()
確認是否有連線
``` c
check_line_segment_win(const char *t, int i, int j, line_t line)
```
- `t` : table ，可知整個棋盤的長相
- `i, j` : 查看是否連線的起始點
- `lines` : 說明連線方向
不允許超出邊界（!ALLOW_EXCEED）
``` c
#if !ALLOW_EXCEED
if (last == LOOKUP(t, i - line.i_shift, j - line.j_shift, ' ') ||
last ==
LOOKUP(t, i + GOAL * line.i_shift, j + GOAL * line.j_shift, ' '))
return ' ';
#endif
```
## calculate_win_value()
## available_moves()
# game.h
## DRAWBUFFER_SIZE
``` c
#define DRAWBUFFER_SIZE \
((BOARD_SIZE * (BOARD_SIZE + 1) << 1) + (BOARD_SIZE * BOARD_SIZE) + \
((BOARD_SIZE << 1) + 1) + 1)
```
`(BOARD_SIZE * (BOARD_SIZE + 1) << 1)` ：填入間隔線（ `|` 或 `-` ）的數量
`(BOARD_SIZE * BOARD_SIZE)`：填入 ooxx 的空格數量
`((BOARD_SIZE << 1) + 1) + 1`：間隔數量
# mcts.c
## mcts()
# negamax.c
## negamax_predict
# xo-user.c
::: info
使用 `sudo cat /dev/kxo` 執行程式，只會執行到 kernel module 中的 `open()`->`read()`->`release()`，並不會執行到 userspace 的程式。若要執行 xo-user.c 需要 :
- 使用 `gcc xo-user.c -o xo-user` 產生執行檔
- 且用 `./xo-user` 執行。
:::
## status_check()
> 如果 XO_STATUS_FILE 不為 `"live"` 的狀態，則回傳 false
``` c
FILE *fp = fopen(XO_STATUS_FILE, "r");
```
- `#define XO_STATUS_FILE "/sys/module/kxo/initstate"`
- 把檔案 XO_STATUS_FILE 打開成唯讀模式 ("r")
- 然後把這個打開的檔案，對應到一個 FILE 指標（也就是 fp）
- 以後你可以透過 fp 來「讀取」這個檔案的內容！`
``` c
char read_buf[20];
fgets(read_buf, 20, fp);
```
- 將 fp 中前 19 個資料存入 read_buf 中，第 20 格放 `\0`
- 若提前遇到 `\n` ，就會提前結束讀取
``` c
read_buf[strcspn(read_buf, "\n")] = 0;
```
-> 找出 read_buf 中第一個換行 `\n`，把它換成字串結束字元 `'\0'`
- 參見 [strcspn(3p) — Linux manual page](https://man7.org/linux/man-pages/man3/strcspn.3p.html)
- strcspn — get the length of a complementary substring
- `strcspn(read_buf, "\n"` 可取得 `"\n"` 在 `read_buf` 中的 index
``` c
if (strcmp("live", read_buf)) {
printf("kxo status : %s\n", read_buf);
fclose(fp);
return false;
}
```
- 如果 read_buf 的內容為 live ，`strcmp("live", read_buf)` 回傳 0
- `if (0)` 表示不成立，不會進入 if 內
-> 換句話說，read_buf 如果不為 `"live"` ，則回傳 false 。
## raw_mode_enable()
✅ 讀取現在的終端機設定
✅ 註冊還原動作
✅ 關掉 ICANON（即時讀取）和 ECHO（隱藏輸入）
✅ 啟用新的 raw 模式設定
::: info
事先閱讀：[取得終端機屬性的筆記](https://hackmd.io/@EJ7289/HkXvFfkxex)
:::
``` c
tcgetattr(STDIN_FILENO, &orig_termios);
```
- 參見 [stdin(3) — Linux manual page](https://man7.org/linux/man-pages/man3/stdin.3.html)
> On program startup, the integer file descriptors associated with the streams stdin, stdout, and stderr are 0, 1, and 2, respectively. The preprocessor symbols STDIN_FILENO, STDOUT_FILENO, and STDERR_FILENO are defined with these values in <unistd.h>.
- `STDIN_FILENO` 為標準輸入（讓程式接收鍵盤的訊號）
- STDIN = standard input （通常為 [File Descriptor](https://wiyi.org/linux-file-descriptor.html) 的 0）
- 參見 [tcgetattr(3) - Linux man page](https://linux.die.net/man/3/tcgetattr)
> The termios functions describe a general terminal interface that is provided to control asynchronous communications ports.
- termios 函式提供控制非同步溝通的 port
> `int tcgetattr(int fd, struct termios *termios_p);`
> tcgetattr() gets the parameters associated with the object referred by fd and **stores them in the termios structure referenced by termios_p**.
-> tcgetattr 會將 `STDIN_FILENO` 這 file descriptor 存入 `orig_termios` 中
==為什麼將特定的 file descriptor 存入 termios function 就是取得終端機的屬性？怎模確定放入的fd 一定是終端機的屬性，而不是其他file 的？==
➡️ 這樣等一下可以「改完之後，再還原」==chatGPT 說的==
``` c
atexit(raw_mode_disable);
```
- 參見 [atexit(3) - Linux man page](https://linux.die.net/man/3/atexit)
- 當一個正常的 process 結束後，註冊一個函式。
> The atexit() function registers the given function to be called at normal process termination, either via exit(3) or via return from the program's main().
> returns the value 0 if successful; otherwise it returns a nonzero value.
``` c
struct termios raw = orig_termios;
raw.c_lflag &= ~(ECHO | ICANON);
tcsetattr(STDIN_FILENO, TCSAFLUSH, &raw);
```
- 設定 c_lflag 為 ICANON => canonical mode （須按 Enter 才會被程式讀取）
- 設定 c_lflag 為 ECHO => 可以輸入 characters
- `~(ECHO | ICANON)` 反轉以後又使用 `&` => 可以視為 mask
-> 表示禁用 ECHO 和 ICANON
- `tcsetattr(fd, optional_actions, termios_p)` 用來設定終端機屬性
- 將文件描述 (fd) 儲存至終端機屬性 (termios_p)
- optional_actions 為修改終端機屬性的時機
- `TCSAFLUSH` 表示輸出傳完後才變更，而且清除還沒讀的輸入資料
- 解析 `atexit()`
- 其中 `atexit()` 是用來註冊還原的動作，是為了之後需要還原的時候而設定的。
- 當 process 結束 (normal termination) 的時候，會自動啟動還原的動作。
- process結束是這指一個main()執行完return 0的時候。
設定完還原檔以後，就可以設定我們需要的模式，我們後續的操作需要使用 raw mode，因此將 ECHO 和 ICANON 都關掉。
-> 完成 raw mode 設定
## listen_keyboard_handler()
1. 開啟 device attribute file -> `open(attr_fd, O_RDWR)`
2. 讀取 keyboard 的輸入 -> `read(STDIN, &input, 1)`
- 將鍵盤輸入至 input
3. 查看對應 input 指令 -> `switch(input)`
4. 讀取 attr_fd 的資料 -> `read(attr_fd, buf, 6)`
- 將 attr_fd 的資料存入 buf 中
- 執行 `kxo_state_show()`
- buf 的 6 個 element -> `"%c %c %c\n"`
- buf[0] = attr_obj.disply
- buf[2] = attr_obj.resume
- buf[4] = attr_obj.end
5. `buf[0]` 0,1互換
6. `read_attr ^= 1` 0,1互換
- read_attr = true -> 會印棋盤
- read_attr = false -> 不會印棋盤
7. 寫入 attr_fd 的資料 -> `write(attr_fd, buf, 6)`
- 將 buf 的資料存入 attr_fd 中
- 執行 `kxo_state_store()`
-> 變更 attr_fd
``` c
#define XO_DEVICE_ATTR_FILE "/sys/class/kxo/kxo/kxo_state"
...
int attr_fd = open(XO_DEVICE_ATTR_FILE, O_RDWR);
```
- device attribute 可是用來讓 user space 與 kernel space 溝通 （參考LKMPG-ch7）
- `O_RDWR` is access mode
``` c
if (read(STDIN_FILENO, &input, 1) == 1) {
...
}
```
``` c
switch (input) {
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;
case 17: /* Ctrl-Q */
read(attr_fd, buf, 6);
buf[4] = '1';
read_attr = false;
end_attr = true;
write(attr_fd, buf, 6);
printf("Stopping the kernel space tic-tac-toe game...\n");
break;
}
```
- [為什麼 Ctrl + P = 16 ?](https://www.commfront.com/pages/ascii-chart)
- `read(attr_fd, buf, 6)` -> kxo_state_show()
- `attr_fd` : 為 kxo 的 device attribute，因此會連結到 main.c 中的 kxo_read()
- `buf` : 是 user space 中準備好用來接收資料的 buffer。
- `6` : 是希望從 kernel module 中讀取的最大 byte 數。
- `buf[0] = (buf[0] - '0') ? '0' : '1';`
- 如果 `buf[0] = '0'` -> `(buf[0] - '0') = 0(False)` -> `buf[0] = '1'`
- 如果 `buf[0] != '0'` -> `(buf[0] - '0') = 1(True)` -> `buf[0] = '0'`
- 結論：這行是在做 0 與 1 的切換（toggle）！
- `read_attr ^= 1;`
- `read_attr` 為布林變數 (bool)
- 如果原本的 `read_attr = 1` -> `read_attr = 0`
- 如果原本的 `read_attr = 0` -> `read_attr = 1`
- 結論：這行同樣也在做 0 和 1 的切換。
- `write(attr_fd, buf, 6);` -> kxo_state_store()
- 把新的 `buf` 寫回 `attr_fd`，代表更新這個屬性為新的值（`0` 或 `1`）
## main()
``` c
int flags = fcntl(STDIN_FILENO, F_GETFL, 0);
fcntl(STDIN_FILENO, F_SETFL, flags | O_NONBLOCK);
```
- 參見 [fcntl(3) - Linux man page](https://linux.die.net/man/3/fcntl)
- fcntl : file control
- F_GETFL : Get the file status flags and file access modes
- Value of file status flags and access modes. The return value is not negative.
- F_SETFL : Set the file status flag
- Value other than -1.
-> 「可以利用 `fcntl(fd, F_GETFL)` 找出一個 file descriptor 所對應的 entry in open file table 中的 status flags」
-> 「可以利用 `fcntl(fd, F_SETFL, flags | O_NONBLOCK)` 重新設定 file descriptor 對應的 open file 的 status flag，並加上 O_NONBLOCK（非阻塞模式）」
- 如果沒有 `flags |`，直接寫：
``` c
fcntl(STDIN_FILENO, F_SETFL, O_NONBLOCK);
```
- 只保留 O_NONBLOCK，清除其他原本的 flags（像 O_RDWR, O_APPEND 等）
- 有 `flags |` ，會保留原有的status flag，再額外增加一個 flag
- 各種 open file status flags 的定義可以查看 [open(2) — Linux manual page](https://man7.org/linux/man-pages/man2/open.2.html)
``` c
int device_fd = open(XO_DEVICE_FILE, O_RDONLY);
```
- 參見 [open(2) — Linux manual page](https://man7.org/linux/man-pages/man2/open.2.html)
- The `open()` system call opens the file specified by *pathname*.
- access modes : O_RDONLY, O_WRONLY, or O_RDWR.
- `O_RDONLY` : opened for reading
``` c
fd_set readset;
...
int max_fd = device_fd > STDIN_FILENO ? device_fd : STDIN_FILENO;
...
int result = select(max_fd + 1, &readset, NULL, NULL, NULL);
```
`max_fd` : 為了找出最大的 file descriptor，方便之後設定監聽範圍（ `select()` ）
- 參見 [select(2) — Linux manual page](https://man7.org/linux/man-pages/man2/select.2.html)
- `select()` : allows a program to monitor multiple file descriptors, waiting until one or more of the
file descriptors become "ready" for some class of I/O operation.
- `fd_set` : A structure type that can represent a set of file descriptors.
- `max_fd + 1` : 為最高的 file descriptor + 1
- `&readset` : 此集合中的 file descriptors 會被監聽著，看是否準備被 reading ，如果是準備被reading 的 file descriptor will **not block**.
- `select(max_fd + 1, &readset, NULL, NULL, NULL)`
- `select()` 在監聽多個 file descriptor（FD）中是否可讀（readable）
- `max_fd + 1` 是 select 的第一個參數（因為 select 會檢查 [0, max_fd]）
- `&readset` 是要監控的 fd_set（用 FD_SET() 設定）
- `NULL`, `NULL` 表示不監控寫入與異常的 fd
- `NULL` 表示無 timeout（＝阻塞直到有事件）
``` c
read_attr = true;
end_attr = false;
while (!end_attr) {
FD_ZERO(&readset);
FD_SET(STDIN_FILENO, &readset);
FD_SET(device_fd, &readset);
int result = select(max_fd + 1, &readset, NULL, NULL, NULL);
if (result < 0) {
printf("Error with select system call\n");
exit(1);
}
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, DRAWBUFFER_SIZE);
printf("%s", display_buf);
}
}
```
- 參見 [select(2) — Linux manual page](https://man7.org/linux/man-pages/man2/select.2.html)
- `FD_ZERO` : 清除所有 file descriptor in the set
- `FD_SET` : adds the file descriptor fd to set
- `FD_CLR` : removes the file descriptor fd from set.
- `FD_ISSET` : 測試指定的 file descriptor 是否還存在於 set 中
# Expend
File Descriptor Table
0:
1:
2:
https://wiyi.org/linux-file-descriptor.html
# other
- [ ] 範例
``` c
// 寫入呼叫：使用者下指令，排入一個 work
static ssize_t my_write(...) {
queue_work(my_wq, &my_work);
return 0;
}
// work 執行完畢時，喚醒 read() 等待中的 process
static void my_work_func(struct work_struct *work) {
compute_result(...);
result_ready = 1;
wake_up_interruptible(&my_waitq);
}
// 使用者程式中 read()：等待結果出來
static ssize_t my_read(...) {
wait_event_interruptible(my_waitq, result_ready == 1);
result_ready = 0;
copy_to_user(...);
return ...;
}
```
- [Process State and Wait Queue](https://hackmd.io/@MEME48/Hy65Z5A_h)
- `wake_up_interruptible`：喚醒 wait queue 中的程式
- `wait_event_interruptible`：將使用者執行的程式放置 wait queue
- 喚醒 wait queue 中的程式需要滿足兩個條件
1. 滿足 `wait_event_interruptible(waitq, condition)` 中的condition
2. 呼叫 `wake_up_interruptible(waitq)`
- `read()` 與 `wake_up_interruptible(waitq)` 的差異
- `read()`: 使用這主動進入核心
- `wake_up`: 喚醒「核心中等待的 read() 」 讓它「繼續」執行
Sign in with Wallet
Connect another wallet