# 2025-04-29 問答簡記

"**You never fail until you stop trying.**"
― Albert Einstein
(當你停下嘗試的腳步，就意味著失敗)

## 從 `ioctl` 介面談作業系統和程式語言的演化

在 [UNIX Version 7 的手冊](https://s3.amazonaws.com/plan9-bell-labs/7thEdMan/vol1/man2.bun.txt)中，`ioctl` 系統呼叫宣告為如下：

ioctl(int fildes, int op, struct sgttyb *argp);

利用獨立的宣告，把 `argp` 指向的真實型別交給程式設計師決定，並未提供任何「泛用指標」機制 (搭配看 [ioctl(2)](https://man.freebsd.org/cgi/man.cgi?manpath=Unix+Seventh+Edition&query=ioctl&sektion=2))。該寫法源於 [K&R C](https://en.wikipedia.org/wiki/C_(programming_language)#K&R_C) 時代缺乏 `void *`；當時若要傳遞任意資料，多半改用 `char *` 或任何合適的結構體指標。

`struct sgttyb` 是 UNIXv7 終端機 (tty) 子系統的核心資料結構，用以封裝速度、特殊字元與模式旗標等設定。終端機驅動程式將目前狀態保存在這個結構體中，應用程式若想查詢或修改終端機行為，必須把 `sgttyb` 實例的位址傳入 `ioctl`。其典型流程如下：
1. 準備 `struct sgttyb buf` 變數
2. 以 `ioctl(fd, TIOCGETP, &buf)` 取得現有參數，核心把內部狀態複製到使用者空間的 `buf`
3. 程式修改 `buf.sg_flags`, `buf.sg_ispeed`, `buf.sg_ospeed` 等欄位後，再呼叫 `ioctl(fd, TIOCSETP, &buf)` 或 `TIOCSETN` 把更新後的值寫回核心

在 UNIXv7 中，該呼叫方式正式取代更早期的 `stty` 與 `gtty` 系統呼叫，後二者不過是內部直接轉呼叫 `ioctl` 的封裝。因此 `ioctl` 的第三參數必須接受 `struct sgttyb *`，而當時尚無 `void *`，於是只能明確寫出結構體指標型別或退而使用 `char *`。

所有與終端機相關的 `ioctl` 程式碼（例如 `TIOCGETP`, `TIOCSETP`, `TIOCSETN`）在 `<sgtty.h>` 中定義，並規定第三參數應指向 `sgttyb`；唯有透過這個結構體，核心與使用者程式才能在單一系統呼叫中交換多個屬性值。例如 `sg_ispeed` 與 `sg_ospeed` 以常數 0–15 編碼對應 50, 75, 110, ..., 9600 及二個外部擴充速率的 baud rate，而 `sg_flags` 的位元組合則控制 raw 模式、行緩衝模式、大小寫自動轉換與本地 `echo` 等行為。
> 參見: [Seventh Edition Unix terminal interface](https://en.wikipedia.org/wiki/Seventh_Edition_Unix_terminal_interface?utm_source=chatgpt.com)

由於這整套介面將結構體本身視為交換資料的載體，所以 `struct sgttyb` 與 UNIXv7 的 `ioctl` 介面形成緊密耦合：沒有 `sgttyb` 的欄位定義，就無法解釋 `ioctl` 控制碼的語意；而離開 `ioctl`，`sgttyb` 也失去與核心溝通的管道。

Linux 的手冊 [ioctl(2)](https://man7.org/linux/man-pages/man2/ioctl.2.html) 仍保留這段歷史說明：
> the third argument is an untyped pointer to memory. It’s traditionally `char *argp` (from the days before `void *` was valid C)

同頁亦列出數個舊版原型宣告：UNIXv7 採取 `struct sgttyb *`、4.3BSD 直接寫成 `char *`，而 SysV Release 3/4 則允許「省略型別」或使用省略號。

ANSI C (C89，[ISO/IEC 9899:yyyy](https://www.open-std.org/jtc1/sc22/wg14/www/docs/n2310.pdf)) 正式引入 `void` 與 `void *`。標準在 §6.2.5 給出定義：
> The void type comprises an empty set of values; it is an incomplete object type that cannot be completed.

在 [ISO/IEC 9899:yyyy](https://www.open-std.org/jtc1/sc22/wg14/www/docs/n2310.pdf) §6.3.2.3 指定 `void *` 的轉換規則：
> A pointer to void may be converted to or from a pointer to any object type. A pointer to any object type may be converted to a pointer to void and back again; the result shall compare equal to the original pointer.

這段文字賦予 `void *` 作為真正「泛用指標」的語意，消除過去 `char *` 需要顯式 cast 的繁瑣與風險。

[ISO/IEC 9899:yyyy](https://www.open-std.org/jtc1/sc22/wg14/www/docs/n2310.pdf) 標準同時限制 `void *` 無法直接做指標運算 (§6.5.6 Additive operators)：
> For addition, either both operands shall have arithmetic type, or one operand shall be a pointer to a complete object type and the other shall have integer type.

因此，欲做位元組位移仍須先轉回 `char *`。

C 語言演化後，glibc 與多數 BSD 系統把 `ioctl` 的第三參數改宣告為 `void *`，而 Linux 核心為了與系統呼叫 ABI 相容，內部仍維持 `unsigned long arg`，真正的位址或數值由巨集 `_IOR` / `_IOW` / `_IOWR` 處理和判斷；使用者空間呼叫時再以 `void *` 帶入。

LKMPG 的 [pull request #314](https://github.com/sysprog21/lkmpg/pull/314) 儘管沒被收錄，但引來上述的討論，值得留意。

---

## 善用人工智慧工具
> [DeepWiki: LKMPG](https://deepwiki.com/sysprog21/lkmpg)

Cognition AI 推出一款名為 DeepWiki 的工具，針對 GitHub 上的程式碼倉庫，藉由人工智慧技術，產生詳盡的專案說明文件，還配備互動式圖表，例如類別階層圖、元件相依圖，輔助使用者視覺化理解專案結構。以 LKMPG 來說，儘管視覺化的展現很有限 (Makefile 其實不值得探討，真正的內文在 LaTeX 內文)，使用者可在 DeepWiki 頁面下方，進行提問和要求對比特定概念間的落差，效果尚可，不過讀者務必參照第一手材料來驗證。

---

## 討論《Demystifying the Linux CPU Scheduler》
> [筆記](https://hackmd.io/@salmonii/rJUas6NJle)

### HenryChaing

- [x] SPSC

$ ps -e -o pid,ppid,pgid,comm | less

### devarajabc
server 如何及時更新設定檔？

### EricccTaiwan
- `getpid()` 永遠 return 成功，因為有 process 才能執行 `getpid()`
- softlookup 是核心防止 CPU 被長時間執行任務完全佔據的手段，但 softlookup 的偵測是可關閉

---

:::warning
討論 [Homework3](https://hackmd.io/@sysprog/linux2025-homework3)
:::

## BigMickey69
> [kxo](https://hackmd.io/@BigMickey/linux2025-homework3)

### 原本 kernel <--> user 通訊成本為何較高？
-> 因為 Page size 。
主記憶體管理單元 (MMU) 的最小單位管理為 Page ， 所有記憶體讀取、寫入、配置記憶體時都是它為單位。一般消費者級別的處理器中， Page 大小為 4 Kib。

kernel 與 user 溝通時，其通訊時，資料會寫於一 device file 之中，寫入資料越大不只是需要花比較多時間寫入(差別很小)，更是提升了資料跨越 Page 的風險，一旦跨越就得花更多時間處理第二個 Page。

#### 為甚麼只是多一個 Page 卻會增加通訊成本?
Linux 核心的責任是 page walking，若此新的一頁不在 轉譯後備緩衝區 (Translation Lookaside Buffer or TLB) 上，就得走 (walk) 過一遍。若是甚至還沒被 touch 過的記憶體而觸發 Page fault，就得配置實體記憶體、映射到 process address space 中、更新 Page table 等...

TLB 也是 cache，也會有 cache miss (TLB miss)

shared memory 的實作手段: 將不同的 virtual memory area (VMA) 映射 (map) 到同一個 physical pages

### 遊戲的棋盤該用哪個單字: table vs. board
:::info
**🔹Table:**
Oxford English Dictionary:

"A flat surface, especially one that is used for a particular activity such as eating, writing, or playing games."

Cambridge Dictionary:

"A flat surface, usually supported by legs, used for putting things on."

**🔹Board:**
Oxford English Dictionary:

"A flat, thin, rectangular object used as a surface to play games on, especially board games."

Cambridge Dictionary:

"A flat object or surface on which a game is played."
:::
在我們假設的情況(遊戲)， Board 是遊戲進行的地方，有明確規則、卡牌或是旗子放置位子、棋盤等。換句話說 Board 就是遊戲本身。Table 較抽象， Table 可視為遊玩空間，可有可無的存在

### NULL == `(void *) 0` 在核心模式中，要如何解讀？
在核心模式中，乃至 C lib 中使用 `#include <stdlib.h>`，此式為 True。定義上 NULL 為指向 0 的指標，而 0 為非法地址。
結論：NULL 就是 ((void *) 0)，代表「沒有指向任何記憶體」的指標

### 為何要有多種 page size?
`TODO: 去算盤書找為何當初設計用 4KB`
[Computer Organization and Design: The Hardware/Software Interface, 5/e](https://drive.google.com/file/d/1pSJeDf3QJ8m530Sw0n7qdoy8_dmnThFQ/view?usp=drive_link) 中的第 5.6 章

Many design choices in virtual memory systems are motivated by the high cost
of a page fault. A page fault to disk will take millions of clock cycles to process.
(The table on page 378 shows that main memory latency is about 100,000 times
quicker than disk.) This enormous miss penalty, dominated by the time to get the
first word for typical page sizes, leads to several key decisions in designing virtual
memory systems:

    ■ Pages should be large enough to try to amortize the high access time. Sizes
from 4 KiB to 16 KiB are typical today. New desktop and server systems are
being developed to support 32 KiB and 64 KiB pages, but new embedded
systems are going in the other direction, to 1 KiB pages.

    ■ Organizations that reduce the page fault rate are attractive. The primary
technique used here is to allow fully associative placement of pages in
memory.

    ...

算盤書中寫道 Page size 是為了 armortize 存取時間，具體為甚麼 4 kiB 得從別處尋找答案。

一個 2009 年 IEEE 國際資訊重用與整合的會議論文 [Using 4KB Page Size for Virtual Memory is Obsolet](https://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=5211562) 中提出 4KiB Page size 已過時的概念，並提供許多實驗數據來佐證他的論點，最後提出了兩個結論：
- 16 KiB base pages greatly reduce iTLB misses with minimal memory overhead.
- 256 KiB superpages help with large data segments (reducing dTLB misses).

第二點有問題，因為他最大只有測到 256 KiB ，因此實際上 superpages 理想大小極有可能會更大。但就論第一點，若 16 KiB 有助於減少 iTLB ，那麼為甚麼現代消費者級別處理器仍然使用 4 KiB?

以下是幾個可能的原因：
- 相容性
- 幾十年前 x86 架構就將 4 KiB 作為 Page 大小，從作業系統、虛擬機、啟動程式到 malloc/mmap、JIT、垃圾回收等等等都假設這個單位。
- 記憶體碎片 Memory Fragmentation
- Page 大小越大越會遇到記憶體碎片的問題
- 記憶
- 以 16 KiB 為單位設定讀/寫/執行權限將更加不精確，提升資安的風險
- 早已有 superpage 等技術
- 若有更大的 Page size 需求，現代 Intel 與 AMD 處理器可透過 THP 或 MAP_HUGETLB 等使用 2 MiB/1 GiB 的巨大 Page，當然 superpage 本身也有許多性能相關問題

https://en.wikipedia.org/wiki/CPU_cache (PIPT, VIPT, VIVT)

## ?
https://hackmd.io/@sysprog/c-linked-list --> 列出解說錄影的錯誤
TODO: 用 indirect pointer 實作 insert_tail

void insert_tail(List *list, Node *New_node)
{
    Node *prev = NULL;
    Node **indirect = &list->head;
    //多了一個指向head的指標
    while (*indirect!= NULL){
        indirect = &(*indirect)->next;
    }
    
    *indirect = New_node;
    
}
`//此程式碼解決了需要判斷原為空link或非空link執行不同的指令
Now! 等你寫程式啊，同學

## weiso131
> [kxo](https://hackmd.io/@weiso131/linux2025-homework3)

commit [98edb0](https://github.com/weiso131/kxo/commit/98edb068e9b806b4c2cb14b2ea03d22ad76af7a8)
commit message 的問題是「沒有探討如何重現 (reproduce) 你發現的疑慮」

如何讓 `xo-user` 可在 non-root (一般使用者) 權限執行？
$\to$ 變更 `/dev/kxo` 裝置檔案的存取權限後，是否有安全/正確性顧慮？

從

crw------- 1 root root    235,   0 May  1 20:48 kxo

改為

crw-rw-rw- 1 root root    235,   0 May  1 20:48 kxo

多個使用者 (account) 「同時」開啟
bill, amy, johnny
TODO: per-account state
https://en.wikipedia.org/wiki/Linux_namespaces

UID 100 101 102
[ Amy ] [ Johnny ] [ Bill ]
Ctrl-Q
Ctrl-P

數學分析著重於，用幾個 bit 得以表示 state transition (encoding)
MVC pattern

Claude sonnet-3.7
sandbox
鑑賞 (!)

### 沒有探討如何重現 (reproduce)
關於這個問題，仔細觀察我的 commit [98edb0](https://github.com/weiso131/kxo/commit/98edb068e9b806b4c2cb14b2ea03d22ad76af7a8) 第一段其實有提到：

when the user space program was paused using
a keyboard event and then immediately interrupted with
Ctrl+C, subsequent executions or other windows running
the program

這邊其實就有討論這個錯誤是如何發生的，然而 `a keyboard event` 似乎沒有 `Ctrl + P` 來的明確。
所以我使用 git rebase 修改 commit message
[ef25b4d](https://github.com/weiso131/kxo/commit/ef25b4dc69e175d0a9259c59021a322ff9bf9fd1)

### 更改 kxo 權限
在 main.c 加入此函式

static char* kxo_devnode(const struct device *dev, umode_t *mode) {
    if (mode)
        *mode = 0666;
    return NULL;
}

並且在 `kxo_init` 做更改

#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
+   kxo_class->devnode = kxo_devnode;

在終端機執行 `ls -l /dev`

crw-rw-rw-   1 root     root    510,     0  5月  5 22:59 kxo

可以看到它的權限已經變更為所有人都能讀寫
然而，若是我直接執行 `./xo-user` ，會發生段錯誤
之後 kxo 將無法移除
過一段時間風扇就開始運轉，使用 `top` 觀察 cpu 使用情形

 PID USER      PR  NI    VIRT    RES    SHR S  %CPU  %MEM     TIME+ COMMAND                                                                       
    479 root      20   0       0      0      0 I  33.9   0.0   0:26.29 kworker/u32:14-kxod                                                           
   4684 root      20   0       0      0      0 I  16.6   0.0   0:22.61 kworker/u32:0-events_freezable_pwr_efficient                                  
   4388 root      20   0       0      0      0 I  15.9   0.0   0:30.89 kworker/u32:6-kxod

發現 kxo 相關的任務佔用了不少 cpu 資源

觀察 sysfs 的讀取權限

ls -l /sys/class/kxo/kxo/kxo_state
-rw-r--r-- 1 root root 4096  5月  7 01:35 /sys/class/kxo/kxo/kxo_state

發現它在使用者端是只能讀不能寫
然而，嘗試更改其權限會出現編譯錯誤

BUILD_BUG_ON_ZERO((perms) & 2) 

基於安全考量，不能將 sysfs 的權限設定成全域可寫入

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

在我原本的 kxo 專案，為了讓不同的使用者觀察到同一個盤面，且在任一使用者按下 Ctrl + Q 時同步輸出紀錄，移動紀錄是被存放在核心的。
然而，現在的情況是考慮多個使用者獨立的狀態，而移動紀錄也只會被存取一次，那將移動紀錄存放在核心空間就顯得不必要，而且移動到使用者端會有以下優點:
1. 在任何使用者按下 ctrl + Q 之後，就不需要再跟核心模組有任何互動，這能減少核心模組的工作負擔
2. 減少核心 heap 空間浪費
3. 讓使用者端保有棋盤紀錄，能讓資料傳遞只需要 `誰下了哪一步棋`

此時核心模組的主要功能就是裁判，詳細功能如下:
1. 檢查新的這步棋是否合法
2. 判斷勝負
3. namespace
4. 使用者身分驗證

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

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

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

#### namespace
- 使用者 id
- 使用者當前棋盤狀態
- 使用者自己的 kfifo

namespace 對應的資料結構可利用 user id 進行搜尋
而搜尋的時間複雜度與使用者的數量上限則與使用哪種資料結構有關
可能的方法有
1. 陣列
2. 鏈結串列
3. 鏈結串列組成的陣列

對於這個專案，我認為使用陣列可能就足夠使用。如果使用者的數量過多，可能會導致每個使用者的服務品質不佳。因此需要限制最大的連線人數。在這個前提下就可以直接使用陣列來儲存 namespace 。
至於如何快速取得這個陣列哪些位置是空的，則可以使用鏈結串列做到 O(1) 的操作。

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

再來，觀察程式碼與其運作行為，可以發現 workqueue 是 first in first out ， ai1, ai2, drawboard 彼此之間是不會發生競爭的。然而，如果 time_interrupt 遇到已經分出勝負的情況，就會有競爭的問題，producer 跟 consumer lock 就是這樣才需要存在。
目前程式的問題就是，判斷勝負的部份是 time_interrupt 處理，若直接將 time_interrupt 需要 lock 的部份刪掉，非常有可能(基本上是每次)會發生 ai 已經分出勝負但沒有執行 drawboard 把資料放到 kfifo，導致最後一步使用者總是看不到。
如果能將判斷勝負的東西放在最後一步丟進 kfifo 再處理
應該是能把 consumer, producer lock 全部拿掉(這種情況符合 Single producer single consumer)

- 參考第十一周測驗題

根據上面的論述，若每個使用者擁有自己的 kfifo ，是能做到 lock free 的。

#### 使用者身分驗證

### 用幾個 bit 得以表示 state transition

## rota1001
如何從 userspace 「控制」kxo (LKM; Linux kernel module)？
註冊 `struct file_operations`，提供從 userspace 存取 kxo 的 VFS operation
利用 cookie 進行使用者的識別
hash?
salt
session ID
> https://hackmd.io/J5wYE-XzSkaekqe-OQw6mg

TODO: 分析
assume
sizeof(cookie) <= word size
session-aware

原本之所以會認為 cookie 的大小會卡到安全性的上界是因為以為他的長度是 32 位元，如果是這種量級的話那麼如果以一個固定的 cookie 字串是在「理論上」能被枚舉出來的（因為所有狀態總共只有 $2^{32}$ 種）。那這種情況下只能增加 cookie 的長度，或是讓核心提供一種使用者看不到也不能修改的識別使用者的方式。而 64 位元的 cookie 其實是沒辦法被枚舉的，所以會出現的安全移慮主要會出現在被 hash 的資料可以被枚舉，或者是雜湊函數可以被逆向破解。

以下討論的範疇是假設是所有使用者都只能透過 VFS 這個界面去和外界互動，中間的呼叫是不會被攔截和修改的。

這樣的假設下，如果 cookie 被驗證是正確的，那麼資料就一定是可信任的（指的是不會只有資料被修改但 cookie 沒被修改的情況，但不代表能無條件信任資料裡的資訊，譬如使用者這樣的資訊要放在 cookie 中而非 data 中），所以要思考的事情是怎麼將 `cookie` 和 `data` 放在 64 位元中，並且改進查詢的效率。先不去管 `cookie` 怎麼生成的，只要知道它是一個指定大小的隨機數。至於 `user_id` 的部份可以由核心模組分配，這樣的話可以思考怎樣分配會比較有效率。首先思考使用者數量在一定範圍內，之後在拓展，先以最多 64 個使用者為例。將 0 到 63 的號碼放進一個鏈結串列中（實作上在拿第一次的號碼時可以記個數字就好，回收的號碼再放進去），分配新的使用者可以從裡面拿一個 `user_id`，用完放回去（這裡可以有個定期檢查某個使用者是否太久沒有和核心模組交互的機制，防止有使用者意外斷線造成 zombie user id），這樣如果使用者沒有超過 64 就能成功拿到和別人不重複的 `user_id`。把 `user_id` 限定在一定範圍內有個好處，就是他們的 `cookie` 和其他資訊可以存在陣列中（或者是一個結構體的指標的陣列），可以做到 $O(1)$ 的查詢。那如果超過 64 的話怎麼處理呢？這裡的概念就是一個區塊一個區塊去分配，區塊大小由預期的使用者的數量決定，盡量選 2 的羃，好處是可以通過位元運算來快速尋找在哪個區塊與在那個區塊的偏移量多少。這樣能同時做到不需要一開始就分配所有的空間，但是分配完卻一樣可以做到 $O(1)$ 的查詢。以這裡 64 來說的話，如果出現第 65 個使用者的話，那麼就會分配第 2 個區塊，接下來產生 64 號到 127 號，分別對應到第 2 個區塊的偏移量 0 到 63。這樣就獲得了一個產生 `user_id` 和儲存對應資料的方式。

接下來是傳輸和驗證機制，一開始核心模組會產生一個 `user_id` 和一個 `cookie`，並傳給使用者，接下來使用者每次與核心模組溝通都要將 `user_id`、`cookie` 和 `data` 傳給核心模組。至於這三者要怎麼分配那 64 bit 取決於使用者的生命週期、使用者的最大數量和資料的最大長度。密碼學的安全只要做到計算安全，也就是在一個使用者的生命週期中他的 `cookie` 不會被窮舉出來就好。分配給 `cookie` 50 個位元在任何情況都是一個非常足夠的數字了。就算 1 秒能完成 $10^9$ 次的呼叫（實際上不可能達成），期望上也需要不間斷的呼叫 6.5 天才能窮舉的出來：
$$\frac{1}{2^{50}}\times\frac{2^{50}(2^{50}+1)}{2}\times \frac{1}{86400\times 10^9}\approx 6.5$$
要做到有效程度的惡意行為是很容易觀察和防範的。這件事情我想到一個和前面的定期回收 `user_id` 合併處理的方式，我們把 `user_id` 分成 3 區，分別在 `active_list`、`now_list` 和 `bin_list` 三個鏈結串列中。我們把時間分成一個一個的週期，一個週期要是 `cookie` 被窮舉出來的機率極低的一段時間。一開始，所有被分配的 `user_id` 都被放在 `active_list` 裡面，每當一個時間週期結束，`now_list` 中的東西會被放到 `bin_list` 中，而 `active_list` 會變成新的 `now_list`，`active_list` 會變成空的。另外，被回收的 `user_id` 會放到 `bin_list` 裡面。（簡單來說就是會定期把 `now_list` 中的 `user_id` 做回收）。在核心模組裡面紀錄的資訊要包括這個使用者現在在哪個鏈結串列裡面。使用者被要求至少在每個時間週期內要與核心模組要一個新的 `cookie`，當做了這件事情後，這個 `user_id` 會被放到 `active_list` 中。另外，只有在 `now_list` 和 `active_list` 中的使用者是被認可的使用者。我想，要求一個使用者以分鐘以上的時間單位更換一次 `cookie` 是符合效益的要求。

那用了 50 個位元，譬如以 kxo 這個使用情境，4 位元拿來輸入指令是夠用的，10 位元來放 `user_id` 可以支援最多 1024 個使用者。

依照機率，可以在時間週期、`cookie`、使用者數量和資料大小間做平衡，而如果需要有更多的使用者和更多的指令的話，可以寫一個結構體，裡面放 `cookie`、`user_id` 和 `data`，傳入時傳結構體的指標。
:::success
TODO：看看 Linux 核心中的 bpf 是怎麼做的
:::
這裡去看了一個 bpf 的使用案例，在 [`linux/samples/bpf/cookie_uid_helper_example.c`](https://github.com/torvalds/linux/blob/ebd297a2affadb6f6f4d2e5d975c1eda18ac762d/samples/bpf/cookie_uid_helper_example.c#L264) 中看到它呼叫 `bpf_map_lookup_elem` 的時候帶入了 `cookie` 這個參數：

res = bpf_map_lookup_elem(map_fd, &cookie, &dataEntry);

追進去後發現它把 `cookie` 放在 `attr.key`，把 `dataEntry` 放在 `value` 裡面，進行系統呼叫：

int bpf_map_lookup_elem(int fd, const void *key, void *value)
{
	...
    attr.key = ptr_to_u64(key);
    attr.value = ptr_to_u64(value);
    ...
    ret = sys_bpf(BPF_MAP_LOOKUP_ELEM, &attr, attr_sz);
    ...
}

於是去看了系統呼叫的[定義](https://github.com/torvalds/linux/blob/ebd297a2affadb6f6f4d2e5d975c1eda18ac762d/kernel/bpf/syscall.c#L5939)，會發現它呼叫了 `__sys_bpf`，看到 [`BPF_MAP_LOOKUP_ELEM`](https://github.com/torvalds/linux/blob/ebd297a2affadb6f6f4d2e5d975c1eda18ac762d/kernel/bpf/syscall.c#L5818) 這個選項下會去呼叫 `map_lookup_elem`：

case BPF_MAP_LOOKUP_ELEM:
    err = map_lookup_elem(&attr);

在其中，會取出 `key`，去呼叫 `bpf_map_copy_value`：

err = bpf_map_copy_value(map, key, value, attr->flags);

然後裡面會按照 `map->map_type` 選擇不同的查詢方式，譬如說之前小考出現過的 bloom filter 也是其中一個選項（`BPF_MAP_TYPE_BLOOM_FILTER`）。我沒有每個函式追進去看，不過看上下文來說他是允許不同型態的雜湊表，並且會查詢 key 對應的元素值，放進 value 指向的位置（至於 bloom filter 就是直接回傳存不存在）。所以，cookie 是作為雜湊表的 key 來使用的。

if (map->map_type == BPF_MAP_TYPE_PERCPU_HASH ||
    map->map_type == BPF_MAP_TYPE_LRU_PERCPU_HASH) {
    err = bpf_percpu_hash_copy(map, key, value);
} else if (map->map_type == BPF_MAP_TYPE_PERCPU_ARRAY) {
    err = bpf_percpu_array_copy(map, key, value);
} else if (map->map_type == BPF_MAP_TYPE_PERCPU_CGROUP_STORAGE) {
    err = bpf_percpu_cgroup_storage_copy(map, key, value);
    ...

簡單來說，它一開始會生一個 `cookie` 給使用者，並且有一個雜湊表可以來查詢這個使用者對應的資料。

接下來來比較這個作法和我的作法。首先是不可能用 bloom filter 實作，因為如果只檢測 `cookie` 存不存在的話核心模組無法確定對方是什麼使用者（攻擊者可以使用自己的 `cookie` 卻對其他使用者做操作），所以要使用的雜湊表必須是可以回傳 value 的。在看上面 `cookie_uid_helper_example.c` 中的實作的時候，發現他的 `cookie` 是由 `getsockopt` 產生的，並且後面使用 `bpf_map_lookup_elem` 去看看雜湊表裡面有沒有這個 `cookie`，如果有的話就代表這個 socket 的資訊已經存在了，就回傳錯誤。所以我判斷這裡並不是出於資安考量去做這件事情，而是使用一些資訊做 hash 之後判斷這個東西存不存在以防申請到同樣的資源。那在我看來，以 kxo 這樣的使用情境下，使用 hash 作為 key 只是增加查詢的成本而已。使用 `user_id` 這樣簡單的索引值就能得到相同的效果了，而且如果要增加安全性（增加 `cookie` 的長度）的話，不需要對查詢方面做太多的變更（他的成本取決於使用者的數量，所以成本也不會增加），只是隨著 `cookie` 長度線性的增加儲存空間和比較時間而已。另外，如果有要對使用者做管理的需求的話（譬如上面所述，想移除一些太久沒互動的使用者），那麼使用 `user_id` 可以做到較好的管理。否則，如果使用雜湊表又另外增加這種機制，那還不如一開始就不使用雜湊表。