作業三筆記

lkmpg 小記

ch1 Introduction

Linux 核心模組是一段可以根據需要動態載入和卸載到核心中的程式碼。這些模組可以在不需要重新啟動的情況下加強核心的功能。
如果沒有模組,目前的方法通常是 monolithic kernels (單核),需要將新功能直接整合到核心映像中。這種方法會導致需要更大的核心,並且當需要新功能時,需要重建核心和隨後重新啟動系統。

ch4 HelloWorld

在 Makefile 中加入 PWD := $(CURDIR) 很重要
因為 sudo 出於安全考慮會重置大部分的環境變數,包括 PWD
如果沒有這行程式碼,當執行 sudo make 時,Makefile 可能找不到正確的資料夾

$ lsmod | grep hello

是在尋找名稱中包含 "hello" 的已掛載核心模組。

warning: the compiler differs from the one used to build the kernel
The kernel was built by: x86_64-linux-gnu-gcc-13 (Ubuntu 13.3.0-6ubuntu2~24.04) 13.3.0
You are using: gcc-13 (Ubuntu 13.3.0-6ubuntu2~24.04) 13.3.0

journalctl --since "1 hour ago" | grep "Hello"

掛載模組後,可以輸入以上測試,應該要可以看到 Hello world 1
同理,卸載模組後應該要看到 Goodbye world 1

如果輸入

$ dmesg 

顯示

dmesg: read kernel buffer failed: Operation not permitted

可以試試看

$ sudo sysctl kernel.dmesg_restrict=0

在早期版本的 Linux 核心中,必須使用 init_modulecleanup_module 函式。但現在可以透過使用 module_initmodule_exit 巨集來自定義這些函式的名稱。

__init__exit 巨集

__init 巨集的功能是在模組被寫進核心(built-in)時,使 init function 在完成後被丟棄並釋放其記憶體空間。
他對 loadable modules 沒有影響:

  1. loadable modules 與 built-in drivers 不同,可以在系統運行期間被動態加載和卸載。
  2. built-in drivers 的 init function 只需在系統開機時執行一次;而 loadable modules 在每次被掛載時都需要執行 init function。

__exit 用於模組的 cleanup function。對於built-in drivers,函式會被完全省略(因為永遠不會被卸載);對於 loadable modules 則需要保留以便卸載時執行。

如何設定和傳遞參數給 Linux 核心模組

  1. declare the variables
    首先需要將參數變數宣告為全域變數,使用 module_param 巨集來設定參數。
    module_param 巨集本身有三個參數:
    • 變數名稱
    • 變數類型
    • sysfs 檔案的權限(若為 0 則不會在 sysfs 中建立檔案)
  2. type
  • 整數(有號或無號)
  • 字串
  • 陣列(使用 module_param_array()),必須有一個額外的 pointer to a count variable 作為第三個參數
  1. MODULE_PARM_DESC() 巨集為參數提供描述的文字
  2. 使用 insmod 命令掛載模組時,可以直接在命令後面指定參數值:
    ex.
sudo insmod hello-5.ko mystring="bebop" myintarray=-1

ch5 Preliminaries

模組始於 init_module 函式或 module_init 指定的函式
模組終於 cleanup_module 函式或 module_exit 指定的函式
每個模組必須有 entry 以及 exit function.

核心模組只能使用核心提供的函式,不能使用 standard C library。

One point to keep in mind is the difference between library functions and system calls. Library functions are higher level, run completely in user space and provide a more convenient interface for the programmer to the functions that do the real work — system calls. System calls run in kernel mode on the user’s behalf and are provided by the kernel itself.

printf 函式為例,實際上會調用 write system call。

User Space vs Kernel Space

Unix:

  • highest supervisor mode:所有操作都是允許的
  • lowest user mode

此設計是為了讓核心維持秩序,確保 users 不會任意訪問資源。

Typically, you use a library function in user mode. The library function calls one or more system calls, and these system calls execute on the library function’s behalf, but do so in supervisor mode since they are part of the kernel itself. Once the system call completes its task, it returns and execution gets transferred back to user mode.

Name Space

撰寫核心時,即使是最小的模組也會與整個核心連結,所以 The best way to deal with this is to declare all your variables as static
如果不想將所有變數宣告為靜態,另一個選擇是宣告一個 symbol table 並將其 register 到核心。

Code Space

The kernel has its own space of memory as well. Since a module is code which can be dynamically inserted and removed in the kernel (as opposed to a semi-autonomous object), it shares the kernel’s codespace rather than having its own. Therefore, if your module segfaults, the kernel segfaults.

ch6 Character Device drivers

「一切皆為檔案」的理念與解讀

file_operations 結構

包含 pointers to functions defined by the driver that perform various operations on the device.
提供統一的介面讓核心與 driver 之間進行溝通。

struct file_operations fops = {
         .read = device_read,
         .write = device_write,
         .open = device_open,
         .release = device_release
};
  • read: 從裝置讀取資料
  • write: 寫入資料到裝置
  • open: 開啟裝置
  • release: 關閉裝置 (相當於 close)

file 結構

file 是 kernal 層級的結構,絕不會出現在 user space 中
在驅動程式的 file_operations 函式中,file 結構被作為參數傳遞,通過這個結構來維護檔案相關的狀態和操作。

Registering A Device

向 Linux 核心註冊裝置,使其能夠透過檔案系統被存取。為裝置分配一個 major number,作為識別。

  • major number 指示哪個 driver 處理該裝置
  • minor number 僅由 driver 使用,to differentiate which device it is operating on, just in case the driver handles more than one device.

書中建議使用 cdev interface
步驟一:register a range of device numbers

int register_chrdev_region(dev_t from, unsigned count, const char *name);
int alloc_chrdev_region(dev_t *dev, unsigned baseminor, unsigned count, const char *name);

The choice between two different functions depends on whether you know the major numbers for your device.

需要動態分配 major number 時使用 alloc_chrdev_region

步驟二:initialize the data structure struct cdev for our char device and associate it with the device numbers.

void cdev_init(struct cdev *cdev, const struct file_operations *fops);
int cdev_add(struct cdev *p, dev_t dev, unsigned count);
  • 先用 cdev_init 初始化 cdev 結構
  • 再用 cdev_add 新增到系統中

舊的 register_chrdev 會占用 major number 下的所有 minor number,書中不推。

ch8 sysfs : Interacting with your module

sysfs allows you to interact with the running kernel from userspace by reading or setting variables inside of modules. This can be useful for debugging purposes, or just as an interface for applications or scripts.

struct attribute

struct attribute {
    char *name;
    struct module *owner;
    umode_t mode;
};

這是一個基本結構,定義了 sysfs 中的 attribute(查了一下專有名詞叫屬性(?)),包含 attribute 的名稱、所有者模組和訪問的權限。
應該是類似於 list_head,可以包裝在不同結構體中。

struct device_attribute

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

這是擴充自 struct attribute 的結構體,專給 device 使用。

研讀 kxo

3/30 更新
原始碼說明我應該會告一段落了
剩下大家可以自己去看
我很怕我繼續看下去就很像在舉燭了
有錯誤麻煩直接提出!

kxo 的 Linux 核心模組,這個模組在 kernel 中實作了井字遊戲(Tic-Tac-Toe)。
以下搭配工具書 lkmpg 試著看懂原始碼。

kxo_attr 結構體

struct kxo_attr {
    char display;
    char resume;
    char end;
    rwlock_t lock;
};

static struct kxo_attr attr_obj;
  • display:決定是否要顯示棋盤
  • resume:目前看不出來在幹嘛
  • end:決定遊戲結束後是要重新開始還是完全停止
  • lock

main.c 全域變數說明

static char table[N_GRIDS];
static char turn;
static int finish;
static int delay = 100; 
static int major;
static struct class *kxo_class;
static struct cdev kxo_cdev;
static struct circ_buf fast_buf;
static char draw_buffer[DRAWBUFFER_SIZE];
static struct kxo_attr attr_obj;
static DECLARE_KFIFO_PTR(rx_fifo, unsigned char);
static struct timer_list timer;
static atomic_t open_cnt;
  • table[N_GRIDS]:4x4 的遊戲板,每個格子可以是 ' '(空)、'X' 或 'O'
  • turn:目前輪到哪個玩家('X' 或 'O')
  • finish:目前回合是否結束
  • delay:控制 event 產生的時間間隔,預設值為 100 毫秒,後續在 timer_handler 等函式會介紹到
  • major:device 的 major number
  • kxo_class:device 的 class
  • kxo_cdev:用於管理 character device
  • fast_buf:一個環狀的緩衝區,用於在 interrupt context 中快速儲存資料
  • draw_buffer[DRAWBUFFER_SIZE]:用於繪製棋盤的緩衝區
  • attr_obj:一個 kxo_attr 結構體,用於儲存和管理與 sysfs 相關的 attribute
  • rx_fifo:一個 KFIFO 緩衝區,用於在向 user space 傳遞資料前儲存資料
  • timer:用來模擬週期性的 interrupts
  • open_cnt

會在以下更進一步說明,這邊只是先條列整理。

main.c 的 kxo_init()

當模組被掛載
首先 __init 巨集 呼叫 kxo_init()
會做以下事情:

1. 配置一個 KFIFO 緩衝區

2. register character device

static const struct file_operations kxo_fops = {
    .read = kxo_read,
    .llseek = no_llseek,
    .open = kxo_open,
    .release = kxo_release,
    .owner = THIS_MODULE,
};

在開始向 kernel 註冊 device 之前,需要先定義 kxo 中的 file_operations 結構體。這個結構體會指定當 user space 程式開啟、讀取和關閉 device 時,核心會調用的函式。
接下來,使用 lkmpg 第六章的 cdev interface 進行 character device 註冊 ,分為兩步驟:

/* Register major/minor numbers */
ret = alloc_chrdev_region(&dev_id, 0, NR_KMLDRV, DEV_NAME);

動態分配一個 character device 的 major/minor number 範圍。

/* Add the character device to the system */
cdev_init(&kxo_cdev, &kxo_fops);
ret = cdev_add(&kxo_cdev, dev_id, NR_KMLDRV);

cdev_init 初始化 cdev 結構並且跟相關的操作函式連結,cdev_add 則是將 device 加到系統中。

到目前為止,kxo_cdev 已經在核心中被註冊,而且核心知道如何使用指定的 file_operations 結構體來處理對該 kxo_cdev 的操作。但是 user space 還無法存取這個 device。於是要繼續以下步驟:

3. 建立 device class:kxo_class

static struct class *kxo_class;

為什麼要建立 class?
參考資料

After creating the character device, you want to be able to access it from the user space. To do this, you need to add a device node under /dev.

簡言之就是 /dev 目錄下還沒有對應的 device node,所以 user space 還不知道要如何存取 kxo_cdev。有兩個方法可以使用:

  • 手動使用 mknod 命令 (傳統方法 不推)
$ mknod /dev/<name> c <major> <minor>
  • 利用 udev 系統自動管理 device node,即為 kxo 模組中所使用的函式 class_createdevice_create
/* Create a class structure */
#if LINUX_VERSION_CODE < KERNEL_VERSION(6, 4, 0)
    kxo_class = class_create(THIS_MODULE, DEV_NAME);
#else
    kxo_class = class_create(DEV_NAME);
#endif
    if (IS_ERR(kxo_class)) {
        printk(KERN_ERR "error creating kxo class\n");
        ret = PTR_ERR(kxo_class);
        goto error_cdev;
    }

class_create 函式會在 /sys/class/ 目錄下建立一個新的 device class 目錄,此處為 /sys/class/kxo/

4. Register the device with sysfs

struct device *kxo_dev =
        device_create(kxo_class, NULL, MKDEV(major, 0), NULL, DEV_NAME);

透過 device_create 函式,在先前創建的 kxo_class 中建立一個新的 device。

  • 這會建立 /sys/class/kxo/kxo/ 目錄。這是根據 kxo_class 所產生的 sysfs entry,如果還要創建 attribute file,需要透過後續會提及的 device_create_file 函式來註冊。
  • /dev 目錄下建立一個名為 kxo 的 device file,讓 user space 的程式可以和 device 互動。但是要注意的是確認 udev 有正常運作,udev 才會根據 device_create 提供的 major/minor number 來創建 /dev/kxo。否則就要用上述提及的手動使用 mknod 命令。
  • 回傳kxo_dev 指標,指向新建立的 device。

至此,已經完成了 註冊 device 的步驟,並建立了對應的 user space interface。


ret = device_create_file(kxo_dev, &dev_attr_kxo_state);

接下來,執行 device_create_file 函式在 sysfs 註冊 kxo_state 屬性,將已定義好的 dev_attr_kxo_statekxo_dev 關聯起來。會在 /sys/class/kxo/kxo/ 目錄下建立 kxo_state 檔案。詳見 lkmpg 第八章。

To read or write attributes, show() or store() method must be specified when declaring the attribute.

static ssize_t kxo_state_show(struct device *dev,
                              struct device_attribute *attr,
                              char *buf);

static ssize_t kxo_state_store(struct device *dev,
                               struct device_attribute *attr,
                               const char *buf,
                               size_t count);

static DEVICE_ATTR_RW(kxo_state);

DEVICE_ATTR_RW 巨集會建立一個可讀寫的 attribute(即為 dev_attr_kxo_state),並連結到對應的 show 和 store 函式。
透過這個方式,user space 程式(像是 xo-user.c)可以通過開啟/sys/class/kxo/kxo/kxo_state 檔案來進行屬性的讀寫。

  • 當讀取時,呼叫 kxo_state_show 函式,回傳 attr_obj 目前的值
  • 當寫入時,呼叫 kxo_state_store 函式,更新 attr_obj 的值

這邊的 attr_obj 是最一開始介紹的,用來控制遊戲狀態的結構體。


看到這裡我自己也好混淆,總之在 user space 程式,一樣以 xo-user.c 為例子,會有兩個路徑,即為兩個 interface:

#define XO_DEVICE_FILE "/dev/kxo"
#define XO_DEVICE_ATTR_FILE "/sys/class/kxo/kxo/kxo_state"
Character Device sysfs Attribute
用途 資料傳輸 屬性的查詢或更改
路徑 /dev/kxo /sys/class/kxo/kxo/kxo_state
對應結構體 file_operations (read, write) device_attribute(show, store
如何建立 cdev interface + device_create device_create_file
  • Character Device 用法
int device_fd = open(XO_DEVICE_FILE, O_RDONLY);
read(device_fd, display_buf, DRAWBUFFER_SIZE);
printf("%s", display_buf);

open 為例,system call 會從 user space 轉去 kernel space,核心會根據路徑找到對應的 character device,然後執行在 kxo_fops 中的 kxo_open 函式。

  • sysfs Attribute 用法
int attr_fd = open(XO_DEVICE_ATTR_FILE, O_RDWR);
read(attr_fd, buf, 6);

open 為例,system call 會從 user space 轉去 kernel space,核心會根據路徑找到對應的 device attribute,然後呼叫對應的 kxo_state_show 函式,產生的輸出會被傳回給 user space。

我希望我沒講錯 QAQ 我好混亂

對於以上的第三第四點可以去看作業說明的 使用者層級互動,說明的更精準。

5. Allocate fast circular buffer

fast_buf.buf = vmalloc(PAGE_SIZE);

6. Create the workqueue

7. 初始化一些設定

negamax_init();
mcts_init();
memset(table, ' ', N_GRIDS);
turn = 'O';
finish = 1;

attr_obj.display = '1';
attr_obj.resume = '1';
attr_obj.end = '0';
rwlock_init(&attr_obj.lock);

遊戲是用兩個不同的演算法去對戰,分別是 negamax 和 mcts,掛載模組的時候也會初始化相關的設定。
另外像是 kxo_attr 結構體中的參數也會設定。

8. 設置 timer

timer_setup(&timer, timer_handler, 0);
  • &timer:timer 結構的指標,指向一個已經定義的 struct timer_list 變數。
  • timer_handler:timer 處理結束時要呼叫的 callback function。

在 kxo 中,timer 被用來模擬 hard-irq,後續會說明到。


以下內容請務必事先詳閱 Linux 核心的並行處理
aka 邱繼寬負責的部分

main.c 中的 timer_handler

主要負責遊戲的推進和狀態檢查,會以固定的時間間隔被觸發。

目標是模擬 hard-irq,所以必須確保目前是在 softirq context,欲模擬在 interrupt context 中處理中斷,所以針對該 CPU disable interrupts。

WARN_ON_ONCE(!in_softirq());

透過這行程式碼確認是在 softirq context 中執行的。這是因為 kernel timer 通常在 softirq context 中處理。

local_irq_disable();

模擬 hard-irq:使用 local_irq_disable 函式來禁用目前 CPU 的 interrupts。

char win = check_win(table);

檢查目前遊戲是否有贏家。

  • 如果遊戲仍在進行,呼叫 ai_game 函式。
  • 如果遊戲結束,畫出最終遊戲板並視情況重新開始遊戲。
mod_timer(&timer, jiffies + msecs_to_jiffies(delay));

mod_timer 函式用於在當前 timer 處理完成後,安排下一次 timer 在目前時間的 delay 毫秒之後觸發,以便定期檢查遊戲狀態或進行 AI 的移動。

local_irq_enable();

最後要重新開啟 interrupts。

另外,在 timer_handler函式中還有在開始和結束時記錄時間,用來計算執行所需的時間。

kxo 中 tasklet 與 workqueue 的關係

  • tasklet 是基於 softirq 之上建立的,適合快速、短時間的任務
  • workqueue 在 process context 中執行,適合需要較長時間處理、可能需要休眠的任務。

在 kxo 中,tasklet 是被用來「排程」workqueue 的工作。

我覺得我說錯了
是 CPU 在處理 softirq 時主動去執行 tasklet
講「排程」不太對,tasklet 只是把把工作丟到 workqueue
runqueue of kworkers

以下會說明。

main.c 中的 tasklet

tasklet 的定義和初始化

static DECLARE_TASKLET_OLD(game_tasklet, game_tasklet_func);

宣告並初始化了一個叫做 game_tasklet 的 tasklet,對應的函式為 game_tasklet_func

game_tasklet_func

static void game_tasklet_func(unsigned long __data);
WARN_ON_ONCE(!in_interrupt());
WARN_ON_ONCE(!in_softirq());

首先檢查執行環境,確認目前在 interrupt context 且在 softirq context 中執行。

為什麼要檢查兩次?以為 in_softirq() 即可
4/15 課堂問答討論

依據 finish 和 turn 變數來決定遊戲後續動作,根據當前輪到哪位玩家(O 或 X),將相應的 AI 工作(ai_one_workai_two_work)加入 workqueue。
將繪製棋盤的工作(drawboard_work)加入 workqueue。

在程式碼註解中可以觀察到的 tasklet 重要特性:

  • 執行於 softirq context,可以快速處理非阻塞式任務
  • 同一個 CPU 上的相同 tasklet 不會同時執行
  • tasklet 會在排程它的 CPU 上執行

main.c 中的 workqueue

/* Workqueue for asynchronous bottom-half processing */
static struct workqueue_struct *kxo_workqueue;

/* Work item: holds a pointer to the function that is going to be executed
 * asynchronously.
 */
static DECLARE_WORK(drawboard_work, drawboard_work_func);
static DECLARE_WORK(ai_one_work, ai_one_work_func);
static DECLARE_WORK(ai_two_work, ai_two_work_func);
  • ai_one_work_func:執行 MCTS 演算法幫 'O' 玩家選擇移動
  • ai_two_work_func:執行 Negamax 演算法幫 'X' 玩家選擇移動
  • drawboard_work_func:將遊戲板繪製到緩衝區

workqueue 中的工作會在 process context 中的 kernel thread 執行,可以執行更耗時的任務,像是 kxo 中的 AI 計算或繪製棋盤。

4/15 上課時宅問了要如何知道 kxo 中會跑在不同的 cpu 上面?
以下更新

kxo_workqueue = alloc_workqueue("kxod", WQ_UNBOUND, WQ_MAX_ACTIVE);

節錄自 Linux 核心設計: Concurrency Managed Workqueue
WQ_UNBOUND 是什麼?

表示被加入到該 queue 中的 work item 是由不指定 CPU 的特殊 worker-pools 所服務的。這種情況下 kernel 不會對該 workqueue 提供 concurrent 管理。worker-pools 會嘗試盡快開始執行 work item。

$ sudo dmesg | grep CPU
[ 1220.764809] kxo: [CPU#4] Drawing final board
[ 1220.764813] kxo: [CPU#4] timer_handler in_irq: 4 usec
[ 1220.868779] kxo: [CPU#1] enter timer_handler
[ 1220.868818] kxo: [CPU#1] doing AI game
[ 1220.868818] kxo: [CPU#1] scheduling tasklet
[ 1220.868822] kxo: [CPU#1] timer_handler in_irq: 5 usec
[ 1220.868834] kxo: [CPU#1] game_tasklet_func in_softirq: 8 usec
[ 1220.868843] kxo: [CPU#5] start doing ai_one_work_func
[ 1220.868849] kxo: [CPU#1] drawboard_work_func

由於使用了 WQ_UNBOUND,可以看到 work item 在不同的 CPU (CPU#5、CPU#1) 上執行

main.c 中的 ai_game

會在 timer_handler 函式中當遊戲尚未分出個勝負時被呼叫。

WARN_ON_ONCE(!irqs_disabled());

首先確保函式在執行時 interrupts 已經被禁止,符合 hard-irq 的要求。

ai_game 函式的主要目的是讓 game_tasklet 在適當時機執行,而這個 tasklet 會進一步安排 workqueue 中的工作,所以大致的處理順序是這樣:

  1. hard-irq (timer_handler)
  2. 排程 tasklet (ai_game)
  3. 執行 tasklet (game_tasklet_func)
  4. 排程 workqueue 工作

Interrupt Overview

參考 Linux 核心設計: 中斷處理和現代架構考量

Linux 核心中的 Top-Half 與 Bottom-Half 處理機制

為了降低 interrupt latency,將工作切割為以下:

  • top half:which receives the hardware interrupt
  • bottom half:which does the lengthy processing

Top half 和 botton half 的區分使得系統可以把 interrupt 的處理推遲。

Top-half:

  • 執行在 hard interrupt context 中
  • 處理期間會 disable interrupt
  • 執行關鍵且必須立即處理的任務

在 kxo 模組中,嚴格來說它並不是由 hardware interrupt 直接觸發的 top-half,而是由 kernel timer 在 softirq context 中模擬。

Bottom-half:
在 Linux 中,主要有三種延遲 interrupt 處理的機制:

  • softirqs
  • tasklets
  • workqueues

kxo 模組中,是使用到基於 softirq 的 tasklet 處理遊戲邏輯的計算,workqueue 來處理更耗時間的 AI 運算和棋盤繪製工作。

kxo_attr 結構體中的 lock

在跟 kfifo 相關的 lock 操作之外(後續會說明),kxo_attr 結構體中也有 lock 來保護 attribute 內容。剛剛有說明到因為 sysfs 的設定,user space 的程式是可以讀寫 attr_obj 中的內容的。

可以在 kxo_state_show 以及 kxo_state_store 函式中看到像是:

write_lock(&attr_obj.lock);
sscanf(buf, "%c %c %c", &(attr_obj.display), &(attr_obj.resume),
           &(attr_obj.end));
write_unlock(&attr_obj.lock);

另外,在其他函式中也可以看到同時使用 attribute lock 跟 kfifo lock 的情況,這部分各位自己回去看。

what is open_cnt

static atomic_t open_cnt;

用來記錄目前開啟 kxo 這個 device 的程式(?)數量。
kxo_int 函式中,counter 被初始化為 0,如下:

atomic_set(&open_cnt, 0);

kxo_open 以及 kxo_release 函式中會改動到 open_cnt 的值:

可以另外去看看 rota1001 針對這部分的 pr

atomic_inc_return(&open_cnt)

像是 open 的時候,會透過 atomic_inc_returnopen_cnt 加一,並回傳增加後的新值。

KFIFO

ongoing

前面在 kxo_init 函式快速帶過的部分,決定詳細一點拉出來講。主要說明他在 kxo 裡面在幹嘛。
參考資料:
linux/kfifo.h
lib/kfifo.c
更詳細請看之前修課學長的筆記

什麼是 KFIFO?

Linux Kernel 中一個 First-In-First-Out 的環狀結構 buffer

struct __kfifo {
    unsigned int	in;
    unsigned int	out;
    unsigned int	mask;
    unsigned int	esize;
    void		*data;
};
  • in:下次要寫入資料的 index
  • out:下次要讀取資料的 index
  • mask:用來確保 in 還有 out 都在 buffer 範圍之內循環,通常是 buffer 長度 - 1(其中 buffer 長度會是 2 的冪)
  • esize:每個元素的大小
  • data:指向實際存資料的 buffer 起始位置

kfifo_in:將資料寫入 kfifo

#define	kfifo_in(fifo, buf, n) \
({ \
	typeof((fifo) + 1) __tmp = (fifo); \
	typeof(__tmp->ptr_const) __buf = (buf); \
	unsigned long __n = (n); \
	const size_t __recsize = sizeof(*__tmp->rectype); \
	struct __kfifo *__kfifo = &__tmp->kfifo; \
	(__recsize) ?\
	__kfifo_in_r(__kfifo, __buf, __n, __recsize) : \
	__kfifo_in(__kfifo, __buf, __n); \
})
  • fifo:要操作的 kfifo 指標
  • buf:要寫入的資料 buffer
  • n:要寫入的元素數量

__recsize 是啥?
record size。

struct kfifo __STRUCT_KFIFO_PTR(unsigned char, 0, void);

#define STRUCT_KFIFO_REC_1(size) \
	struct __STRUCT_KFIFO(unsigned char, size, 1, void)

#define STRUCT_KFIFO_REC_2(size) \
	struct __STRUCT_KFIFO(unsigned char, size, 2, void)

看起來可以是 0/1/2 bytes?
上網查是說是可以處理不同長度的資料,不僅僅限於固定大小的元素。
不過 kxo 裡面宣告 kfifo 的 __recsize 是 0,我就先不探討它。

__kfifo_in 將 buf 中的資料複製到 kfifo 的 in 索引位置,然後將 in 索引增加寫入的元素數量,最後回傳實際寫入的元素數量。

kfifo_out:從 kfifo 讀取資料

#define	kfifo_out(fifo, buf, n) \
__kfifo_uint_must_check_helper( \
({ \
	typeof((fifo) + 1) __tmp = (fifo); \
	typeof(__tmp->ptr) __buf = (buf); \
	unsigned long __n = (n); \
	const size_t __recsize = sizeof(*__tmp->rectype); \
	struct __kfifo *__kfifo = &__tmp->kfifo; \
	(__recsize) ?\
	__kfifo_out_r(__kfifo, __buf, __n, __recsize) : \
	__kfifo_out(__kfifo, __buf, __n); \
}) \
)

__kfifo_out 將 kfifo 的 out 索引位置讀取資料到 buf,然後將 in 索引增加讀取的元素數量,最後回傳實際讀取的元素數量。

about lock

Note about locking: There is no locking required until only one reader and one writer is using the fifo and no kfifo_reset() will be called. kfifo_reset_out() can be safely used, until it will be only called in the reader thread. For multiple writer and one reader there is only a need to lock the writer. And vice versa for only one writer and multiple reader there is only a need to lock the reader.

kfifo 使用兩個獨立的變數 inout 來操作寫入還有讀取,所以在 writer 修改 in,reader 修改 out 的情況下,不需要鎖的設計。
如同以上原始碼中的註解所說:
如果只有一個 reader 和一個 writer 使用 kfifo,並且不會呼叫 kfifo_reset,就不需要用到 lock。
以下附上 kfifo_reset 函式的內容:

/**
 * kfifo_reset - removes the entire fifo content
 * @fifo: address of the fifo to be used
 *
 * Note: usage of kfifo_reset() is dangerous. It should be only called when the
 * fifo is exclusived locked or when it is secured that no other thread is
 * accessing the fifo.
 */
#define kfifo_reset(fifo) \
(void)({ \
	typeof((fifo) + 1) __tmp = (fifo); \
	__tmp->kfifo.in = __tmp->kfifo.out = 0; \
})

可以看到 kfifo_reset 會同時修改到 in 還有 out 的值。

如果有多個 writer 但只有一個 reader,只需要對寫入操作 lock。讀取操作因為只有一個執行緒執行,所以不需要 lock。
反之亦然。
那如果多個 writer 多個 reader?

kxo 中的 KFIFO

/* Data are stored into a kfifo buffer before passing them to the userspace */
static DECLARE_KFIFO_PTR(rx_fifo, unsigned char);

首先用 DECLARE_KFIFO_PTR 巨集宣告一個叫做 rx_fifo 的 KFIFO buffer,用來存類型是 unsigned char 的資料。回傳指向 KFIFO 結構的指標。

/* We use an additional "faster" circular buffer to quickly store data from
 * interrupt context, before adding them to the kfifo.
 */
static struct circ_buf fast_buf;

另外會再宣告一個叫做 fast_buf 的環狀 buffer。

猜測為了讓 ISR 盡快完成,會先將資料存入 fast_buf,之後,workqueue handler 再從 fast_buf 取出資料,並存入 rx_fifo
但我目前在 main.c 中找不到相關的程式碼,只有 fast_buf_clear 函式

wait queue

/* Wait queue to implement blocking I/O from userspace */
static DECLARE_WAIT_QUEUE_HEAD(rx_wait);

rx_fifo 是空的時候,讓讀取 rx_fifo 的 process 休眠。

wake_up_interruptible(&rx_wait);

當有新的資料被寫入 rx_fifo 時,會再喚醒 process。

read_lock

/* NOTE: the usage of kfifo is safe (no need for extra locking), until there is
 * only one concurrent reader and one concurrent writer. Writes are serialized
 * from the interrupt context, readers are serialized using this mutex.
 */
static DEFINE_MUTEX(read_lock);

在 kxo 模組中,寫入的操作是在 interrupt context。
但是由於有註冊一個 character device,並且提供了 user space 的 interface,像是 kxo_read 函式,代表可以有多個 user space 的程式從同一個 device 讀取資料。因此需要使用 mutex lock 來確保同一時間僅有一個進程能夠執行讀取操作。

我覺得我需要確認一下 kxo 這部分是 process 還是 thread
另外作業系統的知識需要補一下 忘光光==

來看看 kxo_read 函式內容:

if (mutex_lock_interruptible(&read_lock))
    return -ERESTARTSYS;

Lock the mutex like mutex_lock, and return 0 if the mutex has been acquired or sleep until the mutex becomes available. If a signal arrives while waiting for the lock then this function returns -EINTR.

mutex_lock_interruptible 函式會嘗試獲取 read_lock mutex,確保只有一個進程可以進行讀取。但與 mutex_lock 不同,它是 interruptible:

  • 如果 mutex lock 當下沒被抓到,函式會抓到 lock 並且回傳 0
  • 如果 mutex lock 當下被其他 process 或 thread 抓到,會 sleep 等待 lock 釋放
  • 等待過程中如果收到其他訊號的話,會被中斷然後回傳 -EINTR

當 user 按下 Ctrl+C 送出 SIGINT 的情況?

ret = kfifo_to_user(&rx_fifo, buf, count, &read);

copies data from the fifo into user space
This macro copies at most len bytes from the fifo into the to buffer and returns -EFAULT/0.

kfifo_to_user 函式將 kernel space 的 rx_fifo 資料傳到 user space 的 buf,read 會是為實際傳輸的 bytes 數量。

if (read)
    break;

如果 read 不為 0,代表有成功讀到東西,終止迴圈。

if (file->f_flags & O_NONBLOCK) {
    ret = -EAGAIN;
    break;
}

我還看不懂

ret = wait_event_interruptible(rx_wait, kfifo_len(&rx_fifo));

sleep until a condition gets true
The process is put to sleep (TASK_INTERRUPTIBLE) until the condition evaluates to true or a signal is received. The condition is checked each time the waitqueue wq is woken up.
wake_up has to be called after changing any variable that could change the result of the wait condition.
The function will return -ERESTARTSYS if it was interrupted by a signal and 0 if condition evaluated to true.

wait_event_interruptible 函式
直到條件 kfifo_len(&rx_fifo) 變為 true(即為 KFIFO 裡面有資料)

producer_lock

/* Mutex to serialize kfifo writers within the workqueue handler */
static DEFINE_MUTEX(producer_lock);
mutex_lock(&producer_lock);
draw_board(table);
mutex_unlock(&producer_lock);

確保同一時間只有一個 workqueue handler 在操作棋盤的資料和 draw_buffer 的內容。

consumer_lock

/* Mutex to serialize fast_buf consumers: we can use a mutex because consumers
 * run in workqueue handler (kernel thread context).
 */
static DEFINE_MUTEX(consumer_lock);

還是如同先前所提及,我還找不到目前程式碼 serialize fast_buf consumers 的部分。
你們可以一起來看看

/* Store data to the kfifo buffer */
mutex_lock(&consumer_lock);
produce_board();
mutex_unlock(&consumer_lock);

確保同一時間只有一個 workqueue handler 在處理

produce_board 函式:

unsigned int len = kfifo_in(&rx_fifo, draw_buffer, sizeof(draw_buffer));

使用 kfifo_in 函式將 draw_buffer 的內容寫入 rx_fifo

然後接下來就會 wake_up_interruptible(&rx_wait),因為有資料被寫入 rx_fifo,這部分請去複習前面的內容。

Memory Barriers

有請並行程式設計大師邱繼寬替各位回答 並行程式設計: Atomics 操作

為什麼需要 barriers?
現代 CPU 和編譯器會重新排序指令(Out-of-Order execution)來優化效能,代表即使程式以特定的順序撰寫,實際執行的順序可能不同。
在單個執行緒的時候,這種優化是透明的,但在多核心或多處理器系統中,這種重新排序可能會導致問題,因為不同執行緒或處理器間的操作順序變得不可預測,造成資料競爭(data race)或不一致的狀態。

為何有 memory reordering 呢?動機非常自然,CPU 要盡量塞滿每個 cycle,在單位時間內運行盡量多的指令。如前述,存取指令在等待 cache coherence 時,可能要花費數百 ns,最高效且直觀的策略是同時處理多個 cache coherence,而非一個接著一個。一個執行緒在程式碼中對多個變數的依次修改,可能會以不同的次序 cohere (coherence 的動詞) 到另一個執行緒所在的處理器上。不同處理器對資料的需求不同,也會導致 cacheline 的讀取和寫入順序的落差。

Memory Barriers 就是為了解決這個問題而設計的,它強制 CPU 和編譯器按照程式設計者預期的順序執行記憶體操作。

  • SMP Read Memory Barrier - smp_rmb
    確保 barrier 之前的所有讀取操作都完成後,才執行 barrier 之後的讀取操作。
  • SMP Write Memory Barrier - smp_wmb
    確保 barrier 之前的所有寫入操作都完成後,才執行 barrier 之後的寫入操作。