2021q3 Homework1 (quiz1)

# 2021q3 Homework1 (quiz1) contributed by < `st9540808` > ###### tags: **`linux2021`** 實驗平台 | CPU | Distro | Kernel | | -------- | -------- | -------- | | i7-11700 (8C16T) | Ubuntu 20.04-LTS | 5.11.0-25-generic | 為何使用 5.11 的 kernel？因為我的硬體的驅動程式只有在較新的版本有提供，使用舊版 (5.4) 則無法正常運作，如螢幕解析度有問題或沒有音訊等等。第三題兩個功能分開寫，而不把功能合併在一起。 ## 1. 解釋程式碼運作原理，包含 ftrace 的使用 ### ftrace hideproc 的原理是藉由 ftrace hook 覆蓋原本核心內部的 `find_ge_pid()` 函式，進而變更原本 `find_ge_pid()` 的行為。 ```c err = ftrace_set_filter_ip(&hook->ops, hook->address, 0, 0); ``` 首先，上述的程式碼會將我們的 callback 函式註冊到 `hook->address` 指向的核心函式上，當對應的核心函式被呼叫時就會執行我們的 callback，以本題來說是我們的 callback 函式 `hook_ftrace_thunk()` 會註冊到 `find_ge_pid()` 上。先觀察看看行為是否如同我們所想 ```shell $ sudo bpftrace -e 'kprobe:find_ge_pid { @[kstack] = count(); }' ... @[ hook_ftrace_thunk+1 ftrace_trampoline+227 find_ge_pid+5 next_tgid+113 proc_pid_readdir+282 proc_root_readdir+58 iterate_dir+162 __x64_sys_getdents64+129 do_syscall_64+56 entry_SYSCALL_64_after_hwframe+68 ]: 1270 ``` 由以上 bpftrace 的 stack trace 可以看到 `hook_ftrace_thunk()` 確實是由 `find_ge_pid()` 所觸發，所以我們的 callback 函式有被正確執行，而且還可以看到整個 kernel stack 的最底層是 `getdents64(2)` 系統呼叫。所以可以整理，當使用者在 shell 中執行 pidof 命令時會呼叫 `getdents64(2)` (在 strace 也可以看到確實有此系統呼叫)，而到了核心時當呼叫到 `find_ge_pid` 時便會觸發 ftrace 的 hook。 ```c regs->ip = (unsigned long) hook->func; ``` 以上程式碼在我們的 callback 函式 `hook_ftrace_thunk()` 中，這一行會設定 PC (Program Counter) 跳到 `hook_find_ge_pid()`，藉此 "hijack" 原本的函式 `find_ge_pid()`。 > `find_ge_pid()` 原本應該在 callback 函式回傳之後繼續執行，結果現在卻在 callback 中直接跳到另一個函式 `hook_find_ge_pid()`，這會讓原本函式 ==`find_ge_pid()`== 的回傳值，以新函式 ==`hook_find_ge_pid()`== 的回傳值所取代。 > > > 另外當 hideproc 掛載之後，用 ftrace (trace-cmd) 追蹤 `find_ge_pid()` 只會有 funcgraph_entry 而看不到 funcgraph_exit ```c static struct pid *hook_find_ge_pid(int nr, struct pid_namespace *ns) { struct pid *pid = real_find_ge_pid(nr, ns); while (pid && is_hidden_proc(pid->numbers->nr)) pid = real_find_ge_pid(pid->numbers->nr + 1, ns); return pid; } ``` 以上程式碼檢查此 pid 是否在核心模組的 `hidden_proc` 鏈結串列的資料結構裡面，如果有的話那就加 1，故意讓 `find_ge_pid` 找不到，所以就會輸出非預期結果。 > 參考: [Using ftrace to hook to functions ](https://www.kernel.org/doc/html/latest/trace/ftrace-uses.html) ### character device 本題程式碼實作一個字元驅動裝置當作使用者界面，使用者藉由存取 `/dev/hideproc` 虛擬檔案指定要隱藏的 pid。 ```shell $ ls -l /dev/hideproc crw------- 1 root root 511, 1 七 25 23:24 /dev/hideproc ``` 對此裝置檔案下 ls 命令，可以看到兩個數字 511, 1，他們分別對應到 major number 和 minor number，在 Linux 中每個裝置都有唯一的 major number，而 minor number 則由驅動裝置開發者指定。 ```shell $ ls -l /sys/dev/char/511\:0 lrwxrwxrwx 1 root root 0 七 27 00:37 /sys/dev/char/511:0 -> ../../devices/virtual/hideproc/hideproc ``` 同時在 sysfs 也可以用 `major` : `minor` 看到此字元裝置 #### 註冊過程 ```c int alloc_chrdev_region (dev_t *dev, unsigned baseminor, unsigned count, const char *name); ``` [`alloc_chrdev_region`](https://www.kernel.org/doc/htmldocs/kernel-api/API-alloc-chrdev-region.html) 要求核心分配分配一段 char device numbers 寫入 `dev` 指標中 (裝置開發者要自行分配一個 dev_t 物件)，major number 是動態決定的，而 `baseminor` 指定 minor number 的起始數值，總共分配 `count` 個 minor number。`name` 為字元裝置的名稱。 `dev_t` 這個型態是核心用來表示 device numbers，資料大小為 32 bit，12 bit 分配給 major number，20 bit 給 minor number。 ```c dev_major = MAJOR(dev); ``` - `MAJOR(dev_t dev)` 巨集可以從 `dev_t` 的物件取出 major number - `MKDEV(int major, int minor)` 可以把 major number 和 minor number 轉換成 `dev_t` 物件 ```c hideproc_class = class_create(THIS_MODULE, DEVICE_NAME); ``` `class_create` 會動態分配一個 class 物件。 > A class is a higher-level view of a device that abstracts out low-level implementation details. > [API-struct-class](https://www.linuxtv.org/downloads/v4l-dvb-internals/device-drivers/API-struct-class.html) ```c cdev_init(&cdev, &fops); cdev_add(&cdev, MKDEV(dev_major, MINOR_VERSION), 1); device_create(hideproc_class, NULL, MKDEV(dev_major, MINOR_VERSION), NULL, DEVICE_NAME); ``` - `cdev` 為 `struct cdev` 型別的物件，用來表示一個字元裝置 - `fops` 定義對應的系統呼叫作用在裝置上時應該要呼叫哪些函式。 ```c struct device * device_create(struct class *class, struct device *parent, dev_t devt, void *drvdata, const char *fmt, ...) ``` [`device_create`](https://www.kernel.org/doc/html/latest/driver-api/infrastructure.html?highlight=class_create#c.device_create): 核心會建立這個裝置並將它註冊到 sysfs。 > 參考: > [Character device drivers](https://linux-kernel-labs.github.io/refs/heads/master/labs/device_drivers.html) > [Chapter 15. Char devices API](https://www.kernel.org/doc/htmldocs/kernel-api/chrdev.html) > [Linux Device Drivers, 3/e](https://lwn.net/Kernel/LDD3/) Chapter 3: Char Drivers > [Device drivers infrastructure](https://www.kernel.org/doc/html/latest/driver-api/infrastructure.html?highlight=class_create#device-drivers-infrastructure) ## 2. 本程式僅在 Linux v5.4 測試，若你用的核心較新，請試著找出替代方案新版遇到的問題 - `ftrace_func_t` 的定義在新版有變動 [commit d19ad0775dcd64b49eecf4fa79c17959ebfbd26b ](https://lore.kernel.org/patchwork/patch/1338176/) - `FTRACE_OPS_FL_RECURSION_SAFE` 巨集變更為 `FTRACE_OPS_FL_RECURSION` > 參考: [ftrace flags](https://www.kernel.org/doc/html/latest/trace/ftrace-uses.html#the-ftrace-flags) - `kallsyms_lookup_name` undefined 問題，使用 livepatch 繞過 unexport 的保護進而存取此 symbol ```c unsigned long kallsyms_lookup_name(const char *name) { return ((unsigned long(*)(const char *))funcs->old_func)(name); } ``` 首先定義好我們的 `kallsyms_lookup_name`，否則無法編譯，接著此函式藉由 livepatch 提供的界面呼叫 `old_func`，而 `old_func` 就是原本 `kallsyms_lookup_name` 的實作。 > 參考: > [Live patching the Linux kernel](https://developer.ibm.com/tutorials/live-patching-the-linux-kernel/) > [Livepatch documentation](https://www.kernel.org/doc/html/latest/livepatch/livepatch.html) 另外發現如果卸載核心模組後再次掛載，整個系統過幾秒後會直接當機，~~目前還不知道原因~~。 :::warning 很好，你發現問題了。留意資源釋放和 Ftrace 的操作 :notes: jserv ::: ## 3.1 擴充為允許其 PPID 也跟著隱藏先使用 `find_vpid` 核心函式找出此 pid 對應的 `struct pid` 指標，再用 `pid_task` 找出 `task_struct` 之後 `ts->real_parent->pid` 就是其父行程的 pid。 ```diff static ssize_t device_write(struct file *filep, const char *buffer, size_t len, loff_t *offset) { + struct task_struct *ts; - long pid; + long pid, ppid = 0; ... if (!memcmp(message, add_message, sizeof(add_message) - 1)) { kstrtol(message + sizeof(add_message), 10, &pid); + + rcu_read_lock(); + ts = pid_task(find_vpid(pid), PIDTYPE_PID); + if (ts) + ppid = ts->real_parent->pid; + rcu_read_unlock(); + + if (ppid) + hide_process(ppid); hide_process(pid); } ... } ``` 因為 `pid_task` 裡有用到 `rcu_dereference`，因此必須使用 RCU synchronization primitive。先取出 ppid 後呼叫 `hide_process(ppid)` 即可將 ppid 一起隱藏起來。 ```diff static int hide_process(pid_t pid) { pid_node_t *proc = kmalloc(sizeof(pid_node_t), GFP_KERNEL); proc->id = pid; + if (is_hidden_proc(pid)) { + kfree(proc); + printk(KERN_INFO "@ %s pid=%d already exists\n", __func__, pid); + return SUCCESS; + } list_add_tail(&proc->list_node, &hidden_proc); return SUCCESS; } ``` 另外多個子行程可能有相同的父行程，因此要先檢查一個 pid 是否已存在鏈結串列中。 > 參考: > - [ChinYikMing](https://hackmd.io/@dNNN2mItS4euNM5VnjPLpQ/hw1-hideproc) > [time=Tue, Jul 27, 2021 6:45 PM] > - [`parent` vs. `real_parent`](https://ypl.coffee/parent-and-real-parent-in-task-struct/) ### 簡單測試在另一個 shell 中下兩個 sleep 命令行程樹狀結構如下 ``` -gnome-terminal-(4344)-+-bash(4352)-+-sleep(19719) `-sleep(19725) ``` ```shell $ echo "add 19719" | sudo tee /dev/hideproc $ echo "add 19725" | sudo tee /dev/hideproc ``` #### dmesg 輸出 ``` [ 6470.146747] @ _hideproc_init [ 6481.789351] @ hide_process pid=4352 already exists ``` ## 3.2 允許給定一組 PID 列表，而非僅有單一 PID 使用 [`strsep`](https://man7.org/linux/man-pages/man3/strsep.3.html) 函式切割出一個個 token，用空白字元分開 pid，程式碼有點長所以隱藏在下面。使用方法 ```bash $ echo "add 184450 184448 184444" | sudo tee /dev/hideproc ``` :::spoiler `device_write` ```c static ssize_t device_write(struct file *filep, const char *buffer, size_t len, loff_t *offset) { long pid; char *message, *cptr, *token; char add_message[] = "add", del_message[] = "del"; char delim[] = " "; if (len < sizeof(add_message) - 1 && len < sizeof(del_message) - 1) return -EAGAIN; message = kmalloc(len + 1, GFP_KERNEL); memset(message, 0, len + 1); copy_from_user(message, buffer, len); if (!memcmp(message, add_message, sizeof(add_message) - 1)) { cptr = message + sizeof(add_message); for (token = strsep(&cptr, delim); token != NULL; token = strsep(&cptr, delim)) { kstrtol(token, 10, &pid); if (pid) hide_process(pid); } } else if (!memcmp(message, del_message, sizeof(del_message) - 1)) { cptr = message + sizeof(del_message); for (token = strsep(&cptr, delim); token != NULL; token = strsep(&cptr, delim)) { kstrtol(token, 10, &pid); if (pid) unhide_process(pid); } } else { kfree(message); return -EAGAIN; } *offset = len; kfree(message); return len; } ``` ::: <br> > 參考: > - [mfinmuch](https://hackmd.io/@mfinmuch/hideproc) > [time=Tue, Jul 28, 2021 5:20 AM] ## 4. 指出程式碼可改進的地方，並動手實作 ### `_hideproc_exit()` 沒有釋放相關資源 ```c static void _hideproc_exit(void) { pid_node_t *proc, *tmp_proc; printk(KERN_INFO "@ %s\n", __func__); device_destroy(hideproc_class, MKDEV(dev_major, 0)); cdev_del(&cdev); class_destroy(hideproc_class); unregister_chrdev_region(MKDEV(dev_major, 0), MINOR_VERSION); hook_remove(&hook); list_for_each_entry_safe (proc, tmp_proc, &hidden_proc, list_node) { list_del(&proc->list_node); kfree(proc); } } ``` 把 `_hideproc_init` 中對註冊字元裝置的操作反向，就能回收資源。 - `device_create` / `device_destroy` 註銷 device 並移除 /dev 和 sysfs 的虛擬檔案 - `cdev_add` / `cdev_del` 從核心中移除字元裝置 - `device_create` / `class_destroy` 注意這邊 class 物件 (`hideproc_class`) 是動態分配的，所以一定要回收此記憶體資源。 - `alloc_chrdev_region` / `unregister_chrdev_region` 回收核心分配的 `major` : `minor` 值域範圍。 ~~目前還是~~ 之前會印出錯誤，原因是呼叫了多餘的函式 `class_unregister`。 ```shell [22612.320281] @ _hideproc_init [22671.469957] @ _hideproc_exit [22671.470217] ------------[ cut here ]------------ [22671.470222] refcount_t: underflow; use-after-free. [22671.470239] WARNING: CPU: 5 PID: 51597 at lib/refcount.c:28 refcount_warn_saturate+0xae/0x ... [22671.470557] Call Trace: [22671.470563] kobject_put+0x56/0x60 [22671.470570] kset_unregister+0x32/0x40 [22671.470577] class_unregister+0x2c/0x50 [22671.470586] class_destroy+0x1c/0x20 [22671.470592] _hideproc_exit+0x49/0x943 [hideproc] [22671.470602] __x64_sys_delete_module+0x14a/0x260 [22671.470612] do_syscall_64+0x38/0x90 ``` ### minor number 不匹配在一開始的 `alloc_chrdev_region` 函式呼叫中分配了 major number 和 minor number。 ```c err = alloc_chrdev_region(&dev, 0, MINOR_VERSION, DEVICE_NAME); ``` 因為 minor number 是從 0 (第二個引數) 開始分配的，因此必須指定 0 而非 1 (原本 `MINOR_VERSION` 的值)，以下修改所有用到此值的地方。 ```diff static int _hideproc_init(void) { ... - cdev_add(&cdev, MKDEV(dev_major, MINOR_VERSION), 1); - device_create(hideproc_class, NULL, MKDEV(dev_major, MINOR_VERSION), NULL, + cdev_add(&cdev, MKDEV(dev_major, 0), 1); + device_create(hideproc_class, NULL, MKDEV(dev_major, 0), NULL, DEVICE_NAME); ... } ``` ### 使用 hlist 加速 `hook_find_ge_pid` 和 `unhide_process` 效能原本這兩個函式都有走訪 list，所以要花 $O(n)$ 的時間，因此用 hlist (separate chaining hash table) 加速此函式。實驗步驟 1. 掛載 hideproc 後加入很多 pid 2. 使用 eBPF 在 `hook_find_ge_pid` 函式的首尾各插入 probe 3. 每一次下 `$ pid sleep` 都會觸發很多次 `hook_find_ge_pid` 函式的呼叫，每次呼叫都紀錄函式所耗費的時間原始 `hook_find_ge_pid` 的效能如下圖，x 軸是加入 pid 的個數，y 軸是函式耗費的時間，單位是 µs。延遲分佈分為兩群，絕大多數 (>99%) 耗費 3 µs 以下，其餘可看到延遲往上增長。   ![](https://i.imgur.com/qTFKPhb.png) > 尚未釐清為何出現離群值，而且他的值會快速往上增長的原因。 > [time=Thr, Jul 29, 2021 04:08 AM] > ==TODO==: 把 stack 印出來看看 kernel 當時怎麼呼叫 > > 用 ftrace 看了一下出現離群值大概是跟 timer interrupt 有關，另外我用 eBPF 測出來的延遲跟 ftrace 上看到的不一致，ftrace 上面沒有出現特別極端的值 (如超過 1000 µs)，這也是個謎。 > ``` > pidof-57493 [004] 3329.834525: funcgraph_entry: | hook_find_ge_pid() { > pidof-57493 [004] 3329.834525: funcgraph_entry: 0.115 us | find_ge_pid(); > pidof-57493 [004] 3329.834556: funcgraph_entry: 0.151 us | find_ge_pid(); > pidof-57493 [004] 3329.834564: funcgraph_entry: 0.077 us | irq_enter_rcu(); > pidof-57493 [004] 3329.834564: funcgraph_entry: | __sysvec_apic_timer_interrupt() { > pidof-57493 [004] 3329.834564: funcgraph_entry: | hrtimer_interrupt() { > pidof-57493 [004] 3329.834564: funcgraph_entry: 0.074 us | _raw_spin_lock_irqsave(); > pidof-57493 [004] 3329.834564: funcgraph_entry: 0.095 us | ktime_get_update_offsets_now(); > pidof-57493 [004] 3329.834564: funcgraph_entry: 3.264 us | __hrtimer_run_queues(); > pidof-57493 [004] 3329.834568: funcgraph_entry: 0.193 us | hrtimer_update_next_event(); > pidof-57493 [004] 3329.834568: funcgraph_entry: 0.126 us | __lock_text_start(); > pidof-57493 [004] 3329.834568: funcgraph_entry: 0.214 us | tick_program_event(); > pidof-57493 [004] 3329.834568: funcgraph_exit: 4.504 us | } > pidof-57493 [004] 3329.834568: funcgraph_exit: 4.682 us | } > pidof-57493 [004] 3329.834568: funcgraph_entry: | irq_exit_rcu() { > pidof-57493 [004] 3329.834569: funcgraph_entry: 0.070 us | idle_cpu(); > pidof-57493 [004] 3329.834569: funcgraph_exit: 0.196 us | } > pidof-57493 [004] 3329.834636: funcgraph_exit: ! 110.331 us | } > ```  #### hlist 的結構體 ```c struct hlist_head { struct hlist_node *first; }; struct hlist_node { struct hlist_node *next, **pprev; }; ``` ```graphviz digraph G { node [shape="record"] struct1 [label=" <f0> | <f1> | <f2> first | <f3> ..."]; struct2 [label="<f0> next | <f1> pprev"] struct3 [label="<f0> next | <f1> pprev"] struct1:f2 -> struct2 struct2:f1 -> struct1:f2 struct2:f0 -> struct3 struct3:f1 -> struct2:f0 rankdir = LR {rank=same; struct2;} } ``` 為何 `struct hlist_head` 只有一個資料成員？這是為了要減少 hash table 的大小，如果一個 hash table 的元素有兩個指標，那他的大小會變成兩倍！因此 `pprev` 型態會是指標的指標，為了要指向前一個元素的指標。改的過程還滿容易的，下圖為使用 hlist 的函式延遲，延遲分佈還是分成兩部份，大部分 (>99%) 小於 0.5 µs，但注意 y 軸的最大值變成 120 µs。   ![](https://i.imgur.com/7pwtNQO.png) --- #### 比較 `hook_find_ge_pid` 用 list 和 hlist 實作的效能 ##### 用 scatter plot 把全部資料畫上去 ![](https://i.imgur.com/vlpBpMk.png) ##### 畫出 95% 信賴區間 Y 軸從 1200 µs 變成 8 µs ![](https://i.imgur.com/unfpoya.png)  --- #### 比較 `unhide_process` 用 list 和 hlist 實作的效能 scatter plot  ![](https://i.imgur.com/7Iq304y.jpg)  #### 結論資料結構從 list 換成 hlist 可以有效降低 `hook_find_ge_pid` 耗費的時間 :::spoiler benchmark 用的程式 ```python from __future__ import print_function from bcc import BPF import subprocess import multiprocessing import random import time from math import pow # define BPF program prog = """ #include <asm/ptrace.h> BPF_HASH(last); int trace_hook_find_ge_pid(struct pt_regs *ctx) { u64 key = bpf_get_current_pid_tgid(); u64 time = bpf_ktime_get_ns(); last.update(&key, &time); return 0; } int traceret_hook_find_ge_pid(struct pt_regs *ctx) { u64 lat, *tsp, time = bpf_ktime_get_ns(); u64 key = bpf_get_current_pid_tgid(); // unsigned long pid = PT_REGS_RC(ctx); tsp = last.lookup(&key); if (!tsp) return 0; lat = time - *tsp; last.delete(&key); bpf_trace_printk("%d\\n", lat); return 0; } """ def main(num): # load BPF program b = BPF(text=prog) b.attach_kprobe(event="hook_find_ge_pid", event_off=+5, fn_name="trace_hook_find_ge_pid") # b.attach_kprobe(event="hook_find_ge_pid", event_off=+119, # fn_name="traceret_hook_find_ge_pid") b.attach_kprobe(event="hook_find_ge_pid", event_off=+105, fn_name="traceret_hook_find_ge_pid") # format output myfile = open("log.txt", "a") while 1: try: (task, pid, cpu, flags, ts, msg) = b.trace_fields() # ret = msg.decode().split(' ') # print(ret[0], hex(int(ret[1]))) print(msg) myfile.write(f'{num}, {int(msg)}\n') myfile.flush() except ValueError: continue def print_stderr_if_ret_nonzero(p): if p.returncode: cmd = "".join(p.args) print(f"{cmd} return {p.returncode}, stderr: {p.stderr}") def benchmark_round(num): complete_proc = subprocess.run(["sudo", "insmod", "hideproc.ko"]) print_stderr_if_ret_nonzero(complete_proc) main_proc = multiprocessing.Process(target=main, args=(num,)) main_proc.start() time.sleep(0.3) sleep_proc_list = [subprocess.Popen(["sleep", "600"]) for _ in range(num)] proc_list = [str(proc.pid) for proc in sleep_proc_list] # ret = subprocess.run(f'pidof -s sleep', shell=True) sleep_ids = " ".join(proc_list) complete_proc = subprocess.run( f'echo "add {sleep_ids}" | sudo tee /dev/hideproc', shell=True) subprocess.run(f'pidof sleep', shell=True) for proc in sleep_proc_list: proc.kill() complete_proc = subprocess.run(["sudo", "rmmod", "hideproc.ko"]) print_stderr_if_ret_nonzero(complete_proc) # time.sleep(0.2) main_proc.terminate() if __name__ == "__main__": for i in range(10, 1005, 5): benchmark_round(i) # benchmark_round(10) ``` ::: <br> > 參考: > [A generic hash table](https://lwn.net/Articles/510202/) > [linux/hashtable.h](https://elixir.bootlin.com/linux/latest/source/include/linux/hashtable.h) (API 說明都在此標頭檔)