# 2019q1 Homework2 (fibdrv)
contributed by < `yunchi0921` >
###### tags: `linux_kernel`
## 自我檢查清單
### 檔案 fibdrv.c 裡頭的 MODULE_LICENSE, MODULE_AUTHOR, MODULE_DESCRIPTION, MODULE_VERSION 等巨集做了什麼事，可以讓核心知曉呢？ insmod 這命令背後，對應 Linux 核心內部有什麼操作呢？請舉出相關 Linux 核心原始碼並解讀
相對應的定義都可在[linux/include/linux/module.h](https://github.com/torvalds/linux/blob/36011ddc78395b59a8a418c37f20bcc18828f1ef/include/linux/module.h)找到。
* MODULE_LICENSE:紀錄了此專案是由哪種協議所規範，在[OSI(Open Source Initiative)](https://opensource.org/licenses/alphabetical)可以找到現在被批准的協議。
* MODULE_AUTHOR:記錄模組的作者
* MODULE_DESCRIPTION: Driver的功能與簡介
* MODULE_VERSION: Driver版本號
參考資料：[五種開源規範的比較](http://inspiregate.com/internet/trends/74-comparison-of-five-kinds-of-standard-open-source-license-bsd-apache-gpl-lgpl-mit.html)
```clike=
/* Generic info of form tag = "info" */
#define MODULE_INFO(tag, info) __MODULE_INFO(tag, tag, info)
```
上述的巨集都是由這個通用巨集，`_MODULE_INFO`又定義於[include/linux/moduleparam.h](https://github.com/torvalds/linux/blob/master/include/linux/moduleparam.h)中。
```clike=
#ifdef MODULE
#define __MODULE_INFO(tag, name, info) \
static const char __UNIQUE_ID(name)[] \
__used __attribute__((section(".modinfo"), unused, aligned(1))) \
= __stringify(tag) "=" info
#else /* !MODULE */
/* This struct is here for syntactic coherency, it is not used */
#define __MODULE_INFO(tag, name, info) \
struct __UNIQUE_ID(name) {}
#endif
```
`UNIQUE_ID(name)`定義於[linux/include/linux/compiler.h
`# define __UNIQUE_ID(prefix) __PASTE(__PASTE(__UNIQUE_ID_, prefix), __LINE__)`
`__PASTE`定義於相同檔案
```
/* Indirect macros required for expanded argument pasting, eg. __LINE__. */
#define ___PASTE(a,b) a##b
#define __PASTE(a,b) ___PASTE(a,b)
```
`__LINE__`
根據規格書[6.10.8.1](http://port70.net/~nsz/c/c11/n1570.html#6.10.8.1)
>The presumed line number (within the current source file) of the current source line (an integer constant).
於是這個聚集展開就會變成
`__UNIQUE__ID_prefix_LINE_`
參考資料:[jeffcarl67](https://hackmd.io/s/H1vRlaVDE#%E8%87%AA%E6%88%91%E6%AA%A2%E6%9F%A5%E6%B8%85%E5%96%AE)同學共筆
---
此項巨集參考[cjwind](https://hackmd.io/s/SkW25-2UV)同學的共筆，對於裡面用到的技巧都有詳細描述,以下跟著進行實驗觀察，以及嘗試補充。
`__used __attribute__((section(".modinfo"), unused, aligned(1)))`
看起來.modinfo也就是module information看起來是存在這section中
```
$ readelf -x .modinfo fibdrv.o
Hex dump of section '.modinfo':
0x00000000 76657273 696f6e3d 302e3100 64657363 version=0.1.desc
0x00000010 72697074 696f6e3d 4669626f 6e616363 ription=Fibonacc
0x00000020 6920656e 67696e65 20647269 76657200 i engine driver.
0x00000030 61757468 6f723d4e 6174696f 6e616c20 author=National
0x00000040 4368656e 67204b75 6e672055 6e697665 Cheng Kung Unive
0x00000050 72736974 792c2054 61697761 6e006c69 rsity, Taiwan.li
0x00000060 63656e73 653d4475 616c204d 49542f47 cense=Dual MIT/G
0x00000070 504c00 PL.
```
man一下readelf，可以知道 -x 是展示該 section 儲存的變數以及在section中對應的index。
```
-x <number or name>
--hex-dump=<number or name>
Displays the contents of the indicated section as a hexadecimal bytes.
A number identifies a particular section by index in the section
table; any other string identifies all sections with that name in the object file.
```
`__used`定義於 `include/linux/compiler_types.h`
```clike
#define __used __attribute__((__used__))
```
> __attribute__((used)) variable attribute
This variable attribute informs the compiler that a static variable is to be retained in the object file, even if it is unreferenced.
試用一下
```clike=
static int a=87;
int main(){
return 0;
}
```
`gcc -O1 -c test.c` compile nm 看symbol:
`0000000000000000 T main`
將`static int a=87`改為`static int a __attribte__((used))=87`
```
0000000000000000 d a
0000000000000000 T main
```
>"d" The symbol is in the initialized data section[color=#61128c]
`__attribute__((section(".modinfo"), unused, aligned(1)))`
attribute可以同時含有多個屬性，使用逗號分開即可，詳情查看 [Attribute Syntax](https://gcc.gnu.org/onlinedocs/gcc/Attribute-Syntax.html)
`__stringify` 定義於 [linux/tools/include/linux/stringify.h](https://github.com/torvalds/linux/blob/master/tools/include/linux/stringify.h)
```clike=
/* Indirect stringification. Doing two levels allows the parameter to be a
* macro itself. For example, compile with -DFOO=bar, __stringify(FOO)
* converts to "bar".
*/
#define __stringify_1(x...) #x
#define __stringify(x...) __stringify_1(x)
```
Q:為什麼macro兩次呢？
A:根據註解的描述+上[Argument Prescan](https://gcc.gnu.org/onlinedocs/cpp/Argument-Prescan.html)的敘述
>Macro arguments are completely macro-expanded before they are substituted into a macro body, unless they are stringized or pasted with other tokens. After substitution, the entire macro body, including the substituted arguments, is scanned again for macros to be expanded. The result is that the arguments are scanned twice to expand macro calls in them.
>
簡而言之參數會被優先展開，除非他是[stringized](https://gcc.gnu.org/onlinedocs/cpp/Stringizing.html)。
試玩一下：
```clike=
#include<stdio.h>
#define f(a,b) a##b
#define g(a) #a
#define h(a) g(a)
int main(){
printf("%s\n",h(f(1,2)));
printf("%s\n",g(f(1,2)));
}
```
output
`
12
f(1,2)
`
>`h(f(1,2))`因為 arguments 要完全展開在它被替換成macro body之前所以就被先替換成`12` 然後`g(#12)`再把它字串化。
`g(f(1,2))`因為 arguments 為 stringized 所以不會完全展開，故印出來為`f(1,2)`。
參考資料:[C/C++的預處理定義](https://blog.xuite.net/jesonchung/scienceview/93554778-C%2FC%2B%2B+%E7%9A%84%E9%A0%90%E8%99%95%E7%90%86%E5%AE%9A%E7%BE%A9+%3A+%23+%2C++%23%40+%2C+%23%23)
所以綜合以上，要是arguments本身也是macro就可以先展開，而不會被stringized給限制。
### insmod 這命令背後，對應 Linux 核心內部有什麼操作呢？
用strace觀察一下insmod背後用到什麼system call
```
...ignore
fstat(3, {st_mode=S_IFREG|0644, st_size=8288, ...}) = 0
mmap(NULL, 8288, PROT_READ, MAP_PRIVATE, 3, 0) = 0x7fa04ee7e000
finit_module(3, "", 0) = 0
munmap(0x7fa04ee7e000, 8288) = 0
close(3) = 0
exit_group(0) = ?
+++ exited with 0 +++
```
可以看到他呼叫了finit_module
finit_module定義在[kernel/module.c](https://elixir.bootlin.com/linux/v4.18/source/kernel/module.c#L3855)
```clike=
SYSCALL_DEFINE3(finit_module, int, fd, const char __user *, uargs, int, flags)
{
struct load_info info = { };
loff_t size;
void *hdr;
int err;
err = may_init_module();
if (err)
return err;
pr_debug("finit_module: fd=%d, uargs=%p, flags=%i\n", fd, uargs, flags);
if (flags & ~(MODULE_INIT_IGNORE_MODVERSIONS
|MODULE_INIT_IGNORE_VERMAGIC))
return -EINVAL;
err = kernel_read_file_from_fd(fd, &hdr, &size, INT_MAX,
READING_MODULE);
if (err)
return err;
info.hdr = hdr;
info.len = size;
return load_module(&info, uargs, flags);
}
```
SYSCALL_DEFINE定義在 [`include/linux/syscalls.h`](https://elixir.bootlin.com/linux/v4.4/source/include/linux/syscalls.h#L194)
暫時有空再回來補其macro的意義，暫時可先看[這篇](https://blog.csdn.net/hxmhyp/article/details/22699669)
:::danger
source code已經不同，不過有解釋大部分這個macro的意思
:::
可以觀察到最後一行有
`return load_module(&info, uargs, flags);`
>/* Allocate and load the module: note that size of section 0 is always
zero, and we rely on this for optional sections. */
此時這個先放一邊先看下面一題
### 當我們透過 insmod 去載入一個核心模組時，為何 module_init 所設定的函式得以執行呢？Linux 核心做了什麼事呢？
`module_init` 定義於[/include/linux/module.h](https://elixir.bootlin.com/linux/v4.18/source/include/linux/module.h#L129)
```clike
#define module_init(initfn) \
static inline initcall_t __maybe_unused __inittest(void) \
{ return initfn; } \
int init_module(void) __attribute__((alias(#initfn)));
```
最後一行 alias 這個 attribute 是把 #initfn 替換成 init_module(void)。
試玩一下:
```clike
#include<stdio.h>
int add(){
return 1+1;
}
int cool __attribute__((alias("add()")));
int main(){
printf("%d",cool);
}
```
```
output:
2
```
將 `initfn` alias `init_module` 再篇就是與 `init_fib_dev` alias。
`init_fib_dev` 宣告為 `static int __init_fib_dev(void)`
__init
`#define __init __section(.init.text) __cold __latent_entropy __noinitretpoline`
就是儲存在 .init.text中。
此時可回到[`load_module`](https://elixir.bootlin.com/linux/v4.18/source/kernel/module.c#L3656)去看
```clike=
static int load_module(struct load_info *info, const char __user *uargs,
int flags)
{
/* Set up MODINFO_ATTR fields */
setup_modinfo(mod, info);
...ignore
/* Done! */
trace_module_load(mod);
return do_init_module(mod);
```
load_module() 會檢查 ELF header，call setup_load_info() setup struct load_info 的資料，接著會做許多檢查、allocate memory 等等，最後 call do_init_module()。
---
這邊不怕死大膽嘗試解讀`setup_modinfo`，而`modinfo_attrs`為一個 Array of pointer ， 裡面是一些attribute。
:::info
這邊尚不清楚 attr->setup 這個回傳值 void 的指標陣列什麼時候回傳0
:::
接著 call `setup` 這個 function pointer
[/kernel/module.c](https://elixir.bootlin.com/linux/v4.18/source/kernel/module.c#L2496)
```clike=
static void setup_modinfo(struct module *mod, struct load_info *info)
{
struct module_attribute *attr;
int i;
for (i = 0; (attr = modinfo_attrs[i]); i++) {
if (attr->setup)
attr->setup(mod, get_modinfo(info, attr->attr.name));
}
}
```
[/kernel/module.c](https://elixir.bootlin.com/linux/v4.18/source/kernel/module.c#L2482) `get_modinfo`
```clike=
static char *get_modinfo(struct load_info *info, const char *tag)
{
char *p;
unsigned int taglen = strlen(tag);
Elf_Shdr *infosec = &info->sechdrs[info->index.info];
unsigned long size = infosec->sh_size;
for (p = (char *)infosec->sh_addr; p; p = next_string(p, &size)) {
if (strncmp(p, tag, taglen) == 0 && p[taglen] == '=')
return p + taglen + 1;
}
return NULL;
}
```
首先先看傳入的引入 `struct load_info` 超級重要，這是module的靈魂結構。
可以搭配此[ELF格式檔教學](http://sp1.wikidot.com/elfobjfile)一起服用效果更佳。
下面裡面有包一個 index struct，這代表著每個section代表的起始位置索引，而我們的目標是`info`。
所以看到，`get_modinfo`第3行中:
`Elf_Shdr *infosec = &info->sechdrs[info->index.info];`
就是找到 `.modinfo` section的位置。
```clike=
struct load_info {
const char *name;
Elf_Ehdr *hdr;
unsigned long len;
Elf_Shdr *sechdrs;
char *secstrings, *strtab;
unsigned long symoffs, stroffs;
struct _ddebug *debug;
unsigned int num_debug;
bool sig_ok;
#ifdef CONFIG_KALLSYMS
unsigned long mod_kallsyms_init_off;
#endif
struct {
unsigned int sym, str, mod, vers, info, pcpu;
} index;
};
```
再來馬上第5行看到`ElF_Shdr`，他是基於不同系統會給予不同定義的macro，而shdr指的是 section header ， 這裡舉 `Elf64_Shdr`來看看:
```clile
typedef struct elf64_shdr {
Elf64_Word sh_name; /* Section name, index in string tbl */
Elf64_Word sh_type; /* Type of section */
Elf64_Xword sh_flags; /* Miscellaneous section attributes */
Elf64_Addr sh_addr; /* Section virtual addr at execution */
Elf64_Off sh_offset; /* Section file offset */
Elf64_Xword sh_size; /* Size of section in bytes */
Elf64_Word sh_link; /* Index of another section */
Elf64_Word sh_info; /* Additional section information */
Elf64_Xword sh_addralign; /* Section alignment */
Elf64_Xword sh_entsize; /* Entry size if section holds table */
} Elf64_Shdr;
```
看到註解整個高潮，終於有看得懂的東西啦!簡而言之就是 section header 的整個結構組成。
再來看到第8行的，這個回圈終止條件只寫了一個p，也就是當p回`NULL`時終止這個迴圈，再來看一下他遞增的方法`next_string`
```clike=
static char *next_string(char *string, unsigned long *secsize)
{
/* Skip non-zero chars */
while (string[0]) {
string++;
if ((*secsize)-- <= 1)
return NULL;
}
/* Skip any zero padding. */
while (!string[0]) {
string++;
if ((*secsize)-- <= 1)
return NULL;
}
return string;
}
```
:::info
這邊偏猜測 next_string 這個方法，應該就是要找下一個"字串"，因為本身C語言並沒有字串這個概念，所以要透過找到'\0'的下一個當作下一筆字串的開頭，不過不知道 Skip any zero padding 是什麼意思，我的想法是照理來說就只有'\0'會進入(!string[0])這個判斷才對。
:::
接著看第10行回傳`p+taglen+1`的位置，及value的位置所在。
例如 author=yunchi。 則是位在y的記憶體位置。
---
[`do_init_module`](https://elixir.bootlin.com/linux/v4.18/source/kernel/module.c#L3435)
```clike=
static noinline int do_init_module(struct module *mod)
{
int ret = 0;
...
/* Start the module */
if (mod->init != NULL)
ret = do_one_initcall(mod->init);
```
[`do_one_initcall`](https://elixir.bootlin.com/linux/v4.18/source/init/main.c#L874)
```clike=
int __init_or_module do_one_initcall(initcall_t fn)
{
int count = preempt_count();
char msgbuf[64];
int ret;
...
do_trace_initcall_start(fn);
ret = fn();
do_trace_initcall_finish(fn, ret);
...
return ret;
}
```
在第8行看到`ret=fn();` `fn`也就是`initcall_t`的object，也是我們mod->init，初始化了我們的module。
參考資料:[johnnylord](https://hackmd.io/s/rkLAuRs8V)同學的共筆
### 試著執行 $ readelf -a fibdrv.ko, 觀察裡頭的資訊和原始程式碼及 modinfo 的關聯，搭配上述提問，解釋像 fibdrv.ko 這樣的 ELF 執行檔案是如何「植入」到 Linux 核心
```
Symbol table '.symtab' contains 59 entries:
Num: Value Size Type Bind Vis Ndx Name
0: 0000000000000000 0 NOTYPE LOCAL DEFAULT UND
...ignore
15: 0000000000000000 0 FILE LOCAL DEFAULT ABS fibdrv.c
16: 0000000000000000 16 FUNC LOCAL DEFAULT 2 fib_write
17: 0000000000000010 79 FUNC LOCAL DEFAULT 2 fib_device_lseek
18: 0000000000000060 25 FUNC LOCAL DEFAULT 2 fib_release
19: 0000000000000000 32 OBJECT LOCAL DEFAULT 15 fib_mutex
20: 0000000000000080 48 FUNC LOCAL DEFAULT 2 fib_open
21: 00000000000000b0 172 FUNC LOCAL DEFAULT 2 fib_read
22: 0000000000000000 339 FUNC LOCAL DEFAULT 4 init_fib_dev
23: 0000000000000000 0 OBJECT LOCAL DEFAULT 19 __key.27803
24: 0000000000000010 4 OBJECT LOCAL DEFAULT 19 fib_dev
25: 0000000000000008 8 OBJECT LOCAL DEFAULT 19 fib_cdev
26: 0000000000000000 0 OBJECT LOCAL DEFAULT 19 __key.27805
27: 0000000000000000 8 OBJECT LOCAL DEFAULT 19 fib_class
28: 0000000000000000 64 FUNC LOCAL DEFAULT 6 exit_fib_dev
29: 0000000000000000 12 OBJECT LOCAL DEFAULT 14 __UNIQUE_ID_version26
30: 000000000000000c 36 OBJECT LOCAL DEFAULT 14 __UNIQUE_ID_description25
31: 0000000000000030 46 OBJECT LOCAL DEFAULT 14 __UNIQUE_ID_author24
32: 000000000000005e 21 OBJECT LOCAL DEFAULT 14 __UNIQUE_ID_license23
```
看到29~32行可以發現我們前面對 macro 進行的轉換，如果忘記我幫忙再貼一遍
`__UNIQUE__ID_prefix_LINE_`
這些訊息儲存在 .modinfo 中。
而前面有說過透過 insmod ，會呼叫 system call `f_init_module`，經過上方描述 setup，接著 init 等步驟植入 Linux 核心。
### 這個 fibdrv 名稱取自 Fibonacci driver 的簡稱，儘管在這裡顯然是為了展示和教學用途而存在，但針對若干關鍵的應用場景，特別去撰寫 Linux 核心模組，仍有其意義，請找出 Linux 核心的案例並解讀。提示: 可參閱 Random numbers from CPU execution time jitter
### 查閱 ktime 相關的 API，並找出使用案例 (需要有核心模組和簡化的程式碼來解說)
[/drivers/thunderbolt/nhi.c](https://elixir.bootlin.com/linux/latest/source/drivers/thunderbolt/nhi.c#L40)
```clike=
int nhi_mailbox_cmd(struct tb_nhi *nhi, enum nhi_mailbox_cmd cmd, u32 data)
{
ktime_t timeout;
u32 val;
iowrite32(data, nhi->iobase + REG_INMAIL_DATA);
val = ioread32(nhi->iobase + REG_INMAIL_CMD);
val &= ~(REG_INMAIL_CMD_MASK | REG_INMAIL_ERROR);
val |= REG_INMAIL_OP_REQUEST | cmd;
iowrite32(val, nhi->iobase + REG_INMAIL_CMD);
timeout = ktime_add_ms(ktime_get(), NHI_MAILBOX_TIMEOUT);
do {
val = ioread32(nhi->iobase + REG_INMAIL_CMD);
if (!(val & REG_INMAIL_OP_REQUEST))
break;
usleep_range(10, 20);
} while (ktime_before(ktime_get(), timeout));
if (val & REG_INMAIL_OP_REQUEST)
return -ETIMEDOUT;
if (val & REG_INMAIL_ERROR)
return -EIO;
return 0;
}
```
第13行紀錄利用 `ktime_get()` 取得現在時間與 timeout 的總和，在13~19行進入一個無窮迴圈直到，`ktime_get()` 超過 timeout 時間為止。
### clock_gettime 和 High Resolution TImers (HRT) 的關聯為何？請參閱 POSIX 文件並搭配程式碼解說
根據[wiki頁面](https://elinux.org/High_Resolution_Timers)能知道
>The objective of the high resolution timers project is to implement the POSIX 1003.1b Section 14 (Clocks and Timers) API in Linux.
>
一個用於實時編程的標準（以前的P1003.4或POSIX.4）。這個標準在1993年被IEEE通過，被合併進ISO/IEC 9945-1。
```clike
struct timespec {
time_t tv_sec; /* seconds */
long tv_nsec; /* nanoseconds */
};
```
使用 timespec 來儲存時間的話，其精準度最高可達十億分之一秒（nanosecond），若要查詢實際的精確度，可以使用 clock_getres 函數:
```clike
#include <time.h>
#include <stdio.h>
int main() {
struct timespec t;
clock_getres(CLOCK_MONOTONIC, &t);
printf("Resolution: %ld nanosecond\n", t.tv_nsec);
return 0;
}
```
參考資料：[C/C++ 語言測量時間函數，評估程式執行效能方法整理](https://blog.gtwang.org/programming/measure-the-execution-time-in-c-language/2/)
### fibdrv 如何透過 Linux Virtual File System 介面，讓計算出來的 Fibonacci 數列得以讓 userspace (使用者層級) 程式 (本例就是 client.c 程式) 得以存取呢？解釋原理，並撰寫或找出相似的 Linux 核心模組範例
Virtual File System (VFS) ：負責提供一套統一的檔案系統介面，供 user space 使用
基本的 driver，都會實作 open 與 close 等等的 handler，也就是 user 在操作裝置檔做的 open 以及 close 等等的動作，定義 system call 界面給 user space 使用
System call： user space 與 Linux device driver 的溝通界面
透過 Virtual File System (VFS)可讓同一套System call在不同的檔案系統上使用，讓不同檔案系統可以用一致的方式存取。
而溝通方式又分為兩種:
A character device typically transfers data to and from a user application — they behave like pipes or serial ports, instantly reading or writing the byte data in a character-by-character stream. They provide the framework for many typical drivers, such as those that are required for interfacing to serial communications, video capture, and audio devices. The main alternative to a character device is a block device. Block devices behave in a similar fashion to regular files, allowing a buffered array of cached data to be viewed or manipulated with operations such as reads, writes, and seeks. Both device types can be accessed through device files that are attached to the file system tree.
必須實作出 kernel 中固定框架，就可以在 userspace 使用對應功能。
```clike
struct file_operations {
struct module *owner;
loff_t (*llseek) (struct file *, loff_t, int);
ssize_t (*read) (struct file *, char __user *, size_t, loff_t *);
ssize_t (*write) (struct file *, const char __user *, size_t, loff_t *);
ssize_t (*read_iter) (struct kiocb *, struct iov_iter *);
ssize_t (*write_iter) (struct kiocb *, struct iov_iter *);
int (*iterate) (struct file *, struct dir_context *);
int (*iterate_shared) (struct file *, struct dir_context *);
__poll_t (*poll) (struct file *, struct poll_table_struct *);
long (*unlocked_ioctl) (struct file *, unsigned int, unsigned long);
long (*compat_ioctl) (struct file *, unsigned int, unsigned long);
int (*mmap) (struct file *, struct vm_area_struct *);
unsigned long mmap_supported_flags;
int (*open) (struct inode *, struct file *);
int (*flush) (struct file *, fl_owner_t id);
int (*release) (struct inode *, struct file *);
int (*fsync) (struct file *, loff_t, loff_t, int datasync);
int (*fasync) (int, struct file *, int);
int (*lock) (struct file *, int, struct file_lock *);
ssize_t (*sendpage) (struct file *, struct page *, int, size_t, loff_t *, int);
unsigned long (*get_unmapped_area)(struct file *, unsigned long, unsigned long, unsigned long, unsigned long);
int (*check_flags)(int);
int (*flock) (struct file *, int, struct file_lock *);
...
```
### 注意到 fibdrv.c 存在著 DEFINE_MUTEX, mutex_trylock, mutex_init, mutex_unlock, mutex_destroy 等字樣，什麼場景中會需要呢？撰寫多執行緒的 userspace 程式來測試，觀察 Linux 核心模組若沒用到 mutex，到底會發生什麼問題
### 許多現代處理器提供了 clz / ctz 一類的指令，你知道如何透過演算法的調整，去加速 費氏數列 運算嗎？請列出關鍵程式碼並解說
Sign in with Wallet
Connect another wallet