# 2025q1 Homework3 (kxo)
contributed by < `Nsly0204` >
## 先備知識摘要
[作業要求](https://hackmd.io/@sysprog/linux2025-kxo/%2F%40sysprog%2Flinux2025-kxo-f)
### [2025 年 Linux 核心設計課程作業 —— kxo (B)](/UxosDHbcRJOClsyQ4btHGA)
- [x] [一切皆為檔案描述子](https://hackmd.io/@sysprog/io-universality#一切皆為檔案描述子)
- [x] [Linux 核心模組運作原理](/pfRzP9sxRYqYbXS6Tm0Ynw)
- [ ] LKMPG until chapter 15
[Device Driver 重點整理](https://hackmd.io/@chenging/driver)
Linux device driver 可分成 3 種類型:
1. character device driver
2. block device driver
3. network device driver
Linux device driver(以下或稱為驅動程式)扮演的角色：
userspace > system call > device driver > device file
>參考： [一切皆為檔案描述子](https://hackmd.io/@sysprog/io-universality#一切皆為檔案描述子)
>這種統一抽象層使不同類型的 I/O (如終端輸出與檔案讀寫) 皆可視為檔案操作，裝置驅動程式的核心目的即在於實作這樣的抽象層，使作業系統透過一致介面存取各類裝置。
>這些操作皆基於檔案描述子（file descriptor），如 open()、read()、write() 和 lseek()。在 UNIX 中，檔案被視為位元組序列，而所有 I/O 操作均透過這些標準介面進行。
由此觀念，可以預期一個驅動程式包含以下部份，以 `ksort` 為例：
* 註冊驅動程式： 將 driver 自己「註冊」到 kernel 的 vVirtual File System(VFS) 層，通常直接實作在 `__init` 裡。
* 結構體 file_operations： 提供核心收到 system call 與裝置對應的函式呼叫，其中 `fops` 就是指向該結構體的指標。
* 實作函式對應 system call 的操作，如範例的`main_sort` 。
### [2025 年 Linux 核心設計課程作業 —— kxo ( C )](/C7w6V41gRdyM0E5ixqAZGQ)
- [x] [Linux 核心設計: 中斷處理和現代架構考量](/DaSMrw3dRfqwLFq36fAwww)
- [ ] [並行程式設計: Atomics 操作](/OVPTyhEPTwSHumO28EpJnQ)
> 問題
> * what does slave PIC do?
[Slides (L07-LinuxEvents).pdf](https://github.com/tpn/pdfs/blob/master/Interrupts%20in%20Linux%20-%20Slides%20(L07-LinuxEvents).pdf)
**Programmable Interrupt Controller**
Programmable Interrupt Controller (PIC) 是控制 Interrupt 的硬體架構，用於把不同的 Interrupt Request Lines (IRQs) 映射成 Interrupt Vectors 送給 CPU ，PIC 在產生 Interrupt Vectors 時就會進行優先程度的分級。
**Interrupt Vectors**
當外部裝置發出中斷訊號，PIC 接受的訊號會被轉換成一組 Interrupt Vectors ，用於讓 CPU 對照 Interrupt Descriptor Table (IDT) ，找到對應的 ISR / Interrupt handler 起始位址進行處理。
現代架構中，不會同時發生的 I/O devices 可以共享一個 IRQ ，也就是共享 vector ，每一個 device 的 handler / IRS 會一起被呼叫，至於最後是哪個 device 有中斷是依照各個 device 自己決定。
> 詳細說明可以參考先前同學的整理 [Linux 核心設計: Interrupt](/WdjSFwexS4qG8cYqCSW96w)，部份內容也是引述本篇描述。
**Interrupt Handler / Interrupt Service Routine(IRS)**
在現代的作業系統中，ISR 會被切成 top half 和 botton half 兩個部份，目的是為了減少任務的延遲。Top half 和 botton half 的區分使得系統可以把 interrupt 的處理推遲。
`Top Half` 主旨為確認中斷(先上車)且只執行不可延遲的部份，過程中屏蔽其他中斷(執行在 interrupt context 不可排程)，時間須越短越好：
* 確認中斷來源：在共享 interrupt line 的情況下，檢查硬體狀態以判斷是否為本裝置觸發的中斷。
* Acknowledgement：向硬體發送確認訊號，表示中斷已被接收，防止重複觸發。
* 排程後續處理：標記需延後處理的任務。
* 其他不可延遲的關鍵任務。
`Bottom Half` 實作中斷後續處理，更準確的說是去完成 `Top Half` 也就是 Interupt Handler / IRS 不處理的剩餘事項，主要有三種實作方式:
* softirqs
* tasklets：所有 softirq 都由 tasklet(queue) 實現，同時只能有一個 tasklet 被處理器執行(多 CPUs也不行)，tasklet 中的 irq 可以有優先級之分。
* workqueues：必定被視為 kernel thread 執行，由於運作於 process context，workqueue允許睡眠。
注意 `Top Half` 和 `Bottom Half` 的分別並沒有硬性規定，給予 driver 撰寫者自行分配的空間。
**Softirqs**
每個 CPU 都會維護自己的 softirq daemon 也就是 `ksoftirqd` kernel thread ,用於處理 softirq，其流程如下：
* 在 softirq context 執行，屏蔽大部分睡眠與中斷，但可以被更高優先級的 softirq 中斷。
* 利用 `void open_softirq(softirq_id, handler)` 註冊要處理的 softirq 的 handler 。
* `raise_softirq` 觸發 softirq 的處理。
* `__do_softirq` 讓 handler 處理，結束後呼叫 `exiting_irq()`
`
**Workqueue**
* `producer` 生產數據，寫入 buffer。
* `consumer` 消費數據，讀取 buffer。
## 使對奕畫面在使用者層級呈現
> commit [2efc57d](https://github.com/sysprog21/kxo/commit/2efc57dfa0fefc09c0e35d0fdec1cd1b3c189449)
掛載 kxo 對弈模組，並嘗試執行。
```shell
$ make
$ sudo insmod kxo.ko
$ sudo ./xo-user
```
按下 `ctrl + Q` 後停止電腦 vs. 電腦的對弈。
觀察 `xo-user.c` 發現 userspace 在 `printboard()` 函式，透過讀取 kfifo buffer `display_buf`，與 kernel space 互動，為了縮減成本把 kernel space 傳送棋盤的方式改成以 16個 2 bit 表示分別對應 16 格棋盤的三種狀態 `'O'` / `'x'` / `' '` 。
## 透過 sysfs 紀錄並顯示過往棋局
```c
/* Character device stuff */
static int major;
static struct class *kxo_class;
static struct cdev kxo_cdev;
```
為了了解 character device (以下稱 `cdev`) ，和 sysfs 如何建立，觀察 `kxo_init` :
**character device**
1. 在不知道 major number 的情況下，呼叫 `alloc_chrdev_region()` ，向核心註冊 `cdev` 取得 major 和 minor number，在透過宏 `MAJOR()` 把註冊到的 major number 讀出來以供未來 sysfs 註冊使用。
```c
#define MAJOR(dev) ((unsigned int) ((dev) >> MINORBITS))
#define MINOR(dev) ((unsigned int) ((dev) & MINORMASK))
struct cdev {
struct kobject kobj;
struct module *owner;
const struct file_operations *ops;
struct list_head list;
dev_t dev;
unsigned int count;
}
int alloc_chrdev_region(dev_t *dev, unsigned baseminor,
unsigned count, const char *name)
```
```c
/* Register major/minor numbers */
ret = alloc_chrdev_region(&dev_id, 0, NR_KMLDRV, DEV_NAME);
if (ret)
goto error_alloc;
major = MAJOR(dev_id);
```
2. 初始化並呼叫 `cdev_add()` 讓 `cdev` 加入系統，加入後系統就可以使用此裝置，參考原文註解中 cdev is live。
```c
/* Add the character device to the system */
cdev_init(&kxo_cdev, &kxo_fops);
ret = cdev_add(&kxo_cdev, dev_id, NR_KMLDRV);
```
3. 可以使用以下命令觀察掛載成功的 majpt number 和 device name。
```shell
$ cat /proc/devices
```
**sysfs**
device 可以註冊成為 sysfs ，提供 userspace 讀寫核心模組變數的界面，其理所當然的需要一個與 `cdev` 相似的結構體 `device_attribute`。
```c
struct attribute {
char *name;
struct module *owner;
umode_t mode;
};
struct device_attribute {
struct attribute attr;
ssize_t (*show)(struct device *dev, struct device_attribute *attr,
char *buf);
ssize_t (*store)(struct device *dev, struct device_attribute *attr,
const char *buf, size_t count);
};
```
1. 建立作為管理 sysfs 註冊的 class struct ，需要被傳入 `device_create()`。
```c
/**
* ...
*
* A class is a higher-level view of a device that abstracts out low-level
* implementation details. Drivers may see a SCSI disk or an ATA disk, but,
* at the class level, they are all simply disks. Classes allow user space
* to work with devices based on what they do, rather than how they are
* connected or how they work.
*/
struct class {
```
```c
kxo_class = class_create(DEV_NAME);
```
2. 建立一個新的 device 並註冊成 sysfs。
```c
/**
* device_create - creates a device and registers it with sysfs
* @class: pointer to the struct class that this device should be registered to
* @parent: pointer to the parent struct device of this new device, if any
* @devt: the dev_t for the char device to be added
* @drvdata: the data to be added to the device for callbacks
* @fmt: string for the device's name
*
* This function can be used by char device classes. A struct device
* will be created in sysfs, registered to the specified class.
*
* A "dev" file will be created, showing the dev_t for the device, if
* the dev_t is not 0,0.
* If a pointer to a parent struct device is passed in, the newly created
* struct device will be a child of that device in sysfs.
* The pointer to the struct device will be returned from the call.
* Any further sysfs files that might be required can be created using this
* pointer.
*
* Returns &struct device pointer on success, or ERR_PTR() on error.
*/
struct device *device_create(const struct class *class, struct device *parent,
dev_t devt, void *drvdata, const char *fmt, ...)
```
```c
/* Register the device with sysfs */
struct device *kxo_dev =
device_create(kxo_class, NULL, MKDEV(major, 0), NULL, DEV_NAME);
ret = device_create_file(kxo_dev, &dev_attr_kxo_state);
```
```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\n", &(attr_obj.display), &(attr_obj.resume),
&(attr_obj.end));
for (int i = 0; i < N_BOARDS; i++)
sscanf(buf, "%" "l" "u" , attr_obj.board_record[i++]);
write_unlock(&attr_obj.lock);
return count;
}
```
```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, 7, "%c %c %c\n", attr_obj.display, attr_obj.resume,
attr_obj.end);
int record_size = record_get_size();
ret += snprintf(buf, 4,"%d\n", record_size);
for (int i = 0; i < record_size; i++)
ret += snprintf(buf, 9,"%llu\n", attr_obj.board_record[i++]);
read_unlock(&attr_obj.lock);
return ret;
}
```
```c
Stopping the kernel space tic-tac-toe game...
Moves: C0 -> B3 -> A0 -> C3 -> B0
Moves: A3 -> B2 -> C3 -> B3 -> B0 -> C1 -> A1 -> C2
Moves: C2 -> A3 -> B2 -> A0 -> B1 -> A1 -> A2
...
```
Sign in with Wallet
Connect another wallet