2025q1 Homework3 (kxo)

contributed by < Nsly0204 >

先備知識摘要

作業要求

2025 年 Linux 核心設計課程作業 —— kxo (B)

• 一切皆為檔案描述子
• Linux 核心模組運作原理
• LKMPG until chapter 15

Device 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

參考： 一切皆為檔案描述子
這種統一抽象層使不同類型的 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 )

• Linux 核心設計: 中斷處理和現代架構考量
• 並行程式設計: Atomics 操作

問題

• what does slave PIC do?

Slides (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，部份內容也是引述本篇描述。

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

掛載 kxo 對弈模組，並嘗試執行。

$ 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 紀錄並顯示過往棋局

/* 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 註冊使用。
   ​​​​#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)
   

   ​​​​/* 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。
   ​​​​/* 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。
   ​​​​$ cat /proc/devices
   

sysfs
device 可以註冊成為 sysfs ，提供 userspace 讀寫核心模組變數的界面，其理所當然的需要一個與 cdev 相似的結構體 device_attribute。

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()。

   ​​​​/**
   ​​​​ * ...
   ​​​​ *
   ​​​​ * 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 {
   

   ​​​​kxo_class = class_create(DEV_NAME);
   

2. 建立一個新的 device 並註冊成 sysfs。

   ​​​​/**
   ​​​​ * 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, ...)
   

   ​​​​/* 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);
   

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;
}

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;
}

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
...