# 2019q1 Homework3 (review)
contributed by < `jeffcarl67` >
## 環境
* Linux 4.15.0-45-generic #48~16.04.1-Ubuntu SMP
* gcc (Ubuntu 5.4.0-6ubuntu1~16.04.11) 5.4.0 20160609
* 相關程式碼引用自 [linux v5.0](https://elixir.bootlin.com/linux/v5.0/source)
## 要求
* 從 [第 1 週](https://hackmd.io/s/SyrZMGYr4), [第 2 週](https://hackmd.io/s/H1Pik8M8E), [第 3 週(上)](https://hackmd.io/s/S1weT4iLE), [第 3 週(下)](https://hackmd.io/s/SkrVSKiU4), [第 4 週(上)](https://hackmd.io/s/H1KLoTEv4), [第 4 週(下)](https://hackmd.io/s/BJKk1ANv4) 選出你感興趣的 3 個題組進行作答，並且回答附帶的「延伸問題」
* 比照 [課前測驗參考解答: Q1](https://hackmd.io/s/ByzoiggIb) 和 [對 Linked List 進行氣泡排序](https://hackmd.io/s/BklGm1MhZ) 的模式來撰寫共筆，需要詳細分析自己的想法、參閱的材料 (包含 C 語言規格書的章節)，以及==進行相關實驗==
* 若有不能理解的部分，請標註出來。善用 HackMD 的語法 `:::info` 和 `:::` 標註你的提問
:::info
像是這樣標註提問
:::
* 將你的共筆加到 [2019q1 Homework3 (作業區)](https://hackmd.io/s/BJgx6jav4)
### 2019q1 第 2 週測驗題 測驗 `3`
考慮以下程式碼:
```clike
#include <stdio.h>
#define cons(x, y) E
struct llist { int val; struct llist *next; };
int main() {
struct llist *list = cons(9, cons(5, cons(4, cons(7, NULL))));
struct llist *p = list;
for (; p; p = p->next)
printf("%d", p->val);
printf("\n");
return 0; }
```
預期執行時期輸出 `9547`，補完 `E`。
E = ?
* `(a)` {x, y}
* `(b)` {{x, y}}
* `(c)` {.val = x, .next = y}
* `(d)` (struct llist[]){.val = x, .next = y}
* `(e)` (struct llist[]){{x, y}}
#### 思路
1. 首先看到使用了使用了巨集 `cons` 的程式碼
```c=
struct llist *list = cons(9, cons(5, cons(4, cons(7, NULL))));
```
從這條語句可知巨集 `cons` 展開後必須為一個指向 `struct llist` 的指針, 此時可以把選項 a, b, c 排除
2. 根據[規格書](http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1124.pdf) `6.7.8 Initialization` 第7項
>If a designator has the form
. identifier
then the current object (defined below) shall have structure or union type and the
identifier shall be the name of a member of that type.
選項 d 中 `{.val = x, .next = y}` 只能用於初始化 `struct` 或 `union` , 然而在此卻用 `(struct llist[])` 轉型為以 `struct llist` 為元素的陣列, 型態上並不匹配
3. 以排除法刪掉錯誤選項後可知正確答案為選項 e ,為什麼它是正確的呢？ 根據[規格書](http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1124.pdf) `6.5.2.5 Compound literals` 第 9 項及第 11 項給出的範例
>EXAMPLE 1 The file scope definition
int *p = (int []){2, 4};
initializes p to point to the first element of an array of two ints, the first having the value two and the second, four. The expressions in this compound literal are required to be constant. The unnamed object has static storage duration.
>EXAMPLE 3 Initializers with designations can be combined with compound literals. Structure objects created using compound literals can be passed to functions without depending on member order:
drawline((struct point){.x=1, .y=1},
(struct point){.x=3, .y=4});
Or, if drawline instead expected pointers to struct point:
drawline(&(struct point){.x=1, .y=1},
&(struct point){.x=3, .y=4});
可知語句 `{{x, y}}` 中外層括號用於初始化陣列, 而內層括號用於初始化陣列中的元素亦即 `struct llist`
#### linux 中類似的程式碼
在 `/arch/arm/mm/cache-l2x0-pmu.c` 定義了巨集 `L2X0_EVENT_ATTR` , 可以見到類似的技巧, 相關程式碼如下:
```c=
#define L2X0_EVENT_ATTR(_name, _config, _pl310_only) \
(&((struct l2x0_event_attribute[]) {{ \
.attr = __ATTR(_name, S_IRUGO, l2x0_pmu_event_show, NULL), \
.config = _config, \
.pl310_only = _pl310_only, \
}})[0].attr.attr)
```
### 2019q1 第 4 週測驗題 (下) 測驗 `1`
考慮略為複雜的 reference counting 實作，如下:
[完整題目見此](https://hackmd.io/s/BJKk1ANv4)
#### 思路
1. WW
依據題意可知 max_size 計算出最大可分配的記憶體, 因此可以先將選項 `(a) ptr` 排除, 原本我以為選項 `(b) ~((uint8_t) 0U)` 與選項 `(c) ~((size_t) 0U)` 都可以得到正確結果, 但實際將選項 b 帶入程式碼執行後 , gcc 給出錯誤訊息如下:
```
error: ‘uint8_t’ undeclared (first use in this function)
size_t const static max_size = (~((uint8_t) 0U)) - offsetof(struct refcnt_e
```
查閱 [規格書](http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1124.pdf) `7.17 Common definitions <stddef.h>` 後可知, `stddef.h` 中只定義了 `ptrdiff_t` , `size_t`, `wchar_t` , 故使用 `uint8_t` 會由於未定義而出現錯誤, 故答案為 `(c)`
2. XX
此處是要回傳給函式調用者可用的記憶體空間, 選項 `(c) (*outref)->ptr` 為語法錯誤首先排除, 選項 `(a) outref` 會導致用於管理記憶體的訊息被用戶資料破壞, 因此排除, 選項 `(b) outref->ptr` 由於成員變量 `ptr` 只用於定位而未曾給予值, 因此選項 `(b)` 會得到錯誤結果, 故只有選項 `(d)` 是正確答案
3. YY
此處是為了確保一個物件的引用數量不會超過規定值, 且函式 `refcnt_acquire` 會回傳原來的引用值, 故答案為 `(c) next < REFCOUNTER_MAX`
4. ZZ
當要執行指針運算取得成員變量在結構中的偏移時, 需要先將結構轉型為 `char*` 才能得到正確結果, 因此只有選項 `(d) (char *) ptr - rc_offset` 和選項 `(e) (void *) (((char *) ptr) - rc_offset)` 不排除, 而選項 `(d)` 最外曾少了一對括號導致計算結果錯誤因此答案為 `(e)`
#### linux 核心中類似的程式碼
在 linux module 中即存在類似的 reference counting 程式碼, 在 linux 中使用 `struct module` 管理所有與 module 相關的資訊, `struct module` 定義於 `include/linux/module.h` 中, 與 reference counting 相關的成員變數如下:
```c=
struct module {
...
...
#ifdef CONFIG_MODULE_UNLOAD
/* What modules depend on me? */
struct list_head source_list;
/* What modules do I depend on? */
struct list_head target_list;
/* Destruction function. */
void (*exit)(void);
atomic_t refcnt;
#endif
...
...
} ____cacheline_aligned __randomize_layout;
```
其中 `source_list` 記錄依賴於當前 module 的其他 module, `target_list` 記錄當前 module 所依賴的其他 module, 而類似於題目中函式 `refcnt_acquire` , `refcnt_release` , `rc_acquire` , `rc_release` 的函式分別有 `atomic_inc` , `atomic_dec` , `try_module_get`, `module_put`
`atomic_inc` , `atomic_dec` 用於增減引用計數, 在 linux 中為了確保在多核環境下對引用計數的操作依然正確, 因此相關操作的實現皆為原子操作, `atomic_inc` 與 `atomic_dec` 定義於 `/include/linux/atomic.h` 中
`try_module_get`, `module_put` 定義於 `/kernel/module.c` 中, 為實際上用於操作 `struct module` 的引用計數的函式, 除了原子操作外還增加了防止搶佔的程式碼, 相關程式碼如下:
```c=
bool try_module_get(struct module *module)
{
bool ret = true;
if (module) {
preempt_disable();
/* Note: here, we can fail to get a reference */
if (likely(module_is_live(module) &&
atomic_inc_not_zero(&module->refcnt) != 0))
trace_module_get(module, _RET_IP_);
else
ret = false;
preempt_enable();
}
return ret;
}
```
```c=
void module_put(struct module *module)
{
int ret;
if (module) {
preempt_disable();
ret = atomic_dec_if_positive(&module->refcnt);
WARN_ON(ret < 0); /* Failed to put refcount */
trace_module_put(module, _RET_IP_);
preempt_enable();
}
}
```
#### lsmod 命令輸出的 Used by 運作原理
當使用命令 `strace` 查看 `lsmod` 使用的系統調用時, 會發現 `lsmod` 取得相關資料的方式只是讀取資料夾 `/sys/module` 中對應的文件
```SHELL=
$ strace lsmod
...
...
open("/sys/module/pci_stub/refcnt", O_RDONLY|O_CLOEXEC) = 3
read(3, "1\n", 31) = 2
read(3, "", 29) = 0
close(3)
...
...
open("/sys/module/pci_stub/holders", O_RDONLY|O_NONBLOCK|O_DIRECTORY|O_CLOEXEC) = 3
fstat(3, {st_mode=S_IFDIR|0755, st_size=0, ...}) = 0
getdents(3, /* 2 entries */, 32768) = 48
getdents(3, /* 0 entries */, 32768) = 0
close(3) = 0
...
...
```
`lsmod` 中 `USED` 對應於文件 `refcnt` , 而 `by` 對應於資料夾 `holders` 下的文件名, 以下以一個小實驗驗證觀察結果
- [ ] `lsmod`
```shell=
$ lsmod
Module Size Used by
...
snd_pcm 98304 7 snd_hda_codec_hdmi,snd_hda_intel,snd_hda_codec,
snd_soc_rt5640,snd_soc_core,snd_hda_core,snd_pcm_dmaengine
...
```
- [ ] `cat refcnt`
```shell=
$ cat /sys/module/snd_pcm/refcnt
7
```
- [ ] `ls holders`
```shell=
$ ls /sys/module/snd_pcm/holders
snd_hda_codec snd_hda_core snd_pcm_dmaengine snd_soc_rt5640
snd_hda_codec_hdmi snd_hda_intel snd_soc_core
```
以上結果與觀察相符合
#### `module` 所做的事
當使用命令 `insmod` 載入 module 時, 實際將 module 載入核心的是 `finit_module` 系統調用, 其中實際執行載入工作的是函式 `load_module` , 定義於 `/kernel/module.c` 中, 以下列出函式 `load_module` 中與 `lsmod` 相關的函式調用:
```c=
/* Allocate and load the module: note that size of section 0 is always
zero, and we rely on this for optional sections. */
static int load_module(struct load_info *info, const char __user *uargs,
int flags)
{
struct module *mod;
...
/* Now module is in final location, initialize linked lists, etc. */
err = module_unload_init(mod);
if (err)
goto unlink_mod;
...
/* Link in to sysfs. */
err = mod_sysfs_setup(mod, info, mod->kp, mod->num_kp);
if (err < 0)
goto coming_cleanup;
...
}
```
在函式 `module_unload_init` 中會初始化與引用計數相關的成員變數, 程式碼如下:
```c=
static int module_unload_init(struct module *mod)
{
/*
* Initialize reference counter to MODULE_REF_BASE.
* refcnt == 0 means module is going.
*/
atomic_set(&mod->refcnt, MODULE_REF_BASE);
INIT_LIST_HEAD(&mod->source_list);
INIT_LIST_HEAD(&mod->target_list);
/* Hold reference count during initialization. */
atomic_inc(&mod->refcnt);
return 0;
}
```
接著調用函式 `mod_sysfs_setup` , 此函式同樣定義在 `/kernel/module.c` 中, 與 `lsmod` 相關程式碼如下:
```c=
static int mod_sysfs_setup(struct module *mod,
const struct load_info *info,
struct kernel_param *kparam,
unsigned int num_params)
{
int err;
err = mod_sysfs_init(mod);
if (err)
goto out;
mod->holders_dir = kobject_create_and_add("holders", &mod->mkobj.kobj);
if (!mod->holders_dir) {
err = -ENOMEM;
goto out_unreg;
}
...
err = module_add_modinfo_attrs(mod);
if (err)
goto out_unreg_param;
err = add_usage_links(mod);
if (err)
goto out_unreg_modinfo_attrs;
...
}
```
接著在函式 `mod_sysfs_setup` 中, 首先調用函式 `mod_sysfs_init` 在 `/sys/module` 文件夾中建立跟 module 名字相同的文件夾, 接著調用函式 `kobject_create_and_add` 在前面創建的 `module` 名稱文件夾中建立 `holders` 文件夾, 接著調用函式 `module_add_modinfo_attrs` 建立各種相關屬性的文件, 前述的 `refcnt` 文件即是在此時建立
用於函式 `module_add_modinfo_attrs` 的結構如下
```c=
static struct module_attribute *modinfo_attrs[] = {
&module_uevent,
&modinfo_version,
&modinfo_srcversion,
&modinfo_initstate,
&modinfo_coresize,
&modinfo_initsize,
&modinfo_taint,
#ifdef CONFIG_MODULE_UNLOAD
&modinfo_refcnt,
#endif
NULL,
};
```
與 `refcnt` 相關的定義如下,
```c=
static struct module_attribute modinfo_refcnt =
__ATTR(refcnt, 0444, show_refcnt, NULL);
```
```c=
static ssize_t show_refcnt(struct module_attribute *mattr,
struct module_kobject *mk, char *buffer)
{
return sprintf(buffer, "%i\n", module_refcount(mk->mod));
}
```
```c=
/**
* module_refcount - return the refcount or -1 if unloading
*
* @mod: the module we're checking
*
* Returns:
* -1 if the module is in the process of unloading
* otherwise the number of references in the kernel to the module
*/
int module_refcount(struct module *mod)
{
return atomic_read(&mod->refcnt) - MODULE_REF_BASE;
}
```
而 `module_add_modinfo_attrs` 實現如下:
```c=
static int module_add_modinfo_attrs(struct module *mod)
{
struct module_attribute *attr;
struct module_attribute *temp_attr;
int error = 0;
int i;
mod->modinfo_attrs = kzalloc((sizeof(struct module_attribute) *
(ARRAY_SIZE(modinfo_attrs) + 1)),
GFP_KERNEL);
if (!mod->modinfo_attrs)
return -ENOMEM;
temp_attr = mod->modinfo_attrs;
for (i = 0; (attr = modinfo_attrs[i]) && !error; i++) {
if (!attr->test || attr->test(mod)) {
memcpy(temp_attr, attr, sizeof(*temp_attr));
sysfs_attr_init(&temp_attr->attr);
error = sysfs_create_file(&mod->mkobj.kobj,
&temp_attr->attr);
++temp_attr;
}
}
return error;
}
```
結合上述程式碼後可知每當讀文件 `refcnt` 時, 總是會取得 `mod->refcnt - 1` ,亦即除了自身還有多少 module 依賴於當前 module
最後調用函式 `add_usage_links` 在 `holders` 文件夾中建立所有依賴於當前 module 的其他 module 的文件夾的符號連接
```c=
static int add_usage_links(struct module *mod)
{
int ret = 0;
#ifdef CONFIG_MODULE_UNLOAD
struct module_use *use;
mutex_lock(&module_mutex);
list_for_each_entry(use, &mod->target_list, target_list) {
ret = sysfs_create_link(use->target->holders_dir,
&mod->mkobj.kobj, mod->name);
if (ret)
break;
}
mutex_unlock(&module_mutex);
if (ret)
del_usage_links(mod);
#endif
return ret;
}
```
至此 userspace 程式可以從 `/sys/module/` 文件夾中讀取已載入核心中的 module 的各項相關資訊
#### 實驗
- [ ] `refcnt`
這個小實驗用於測試 `lsmod` 中 `Used` 顯示的數量是否與上述推測相同, 測試用程式仿照 `fibdrv` 註冊為 `char device` 並透過 vfs 使 userspace 能夠存取, 並設定讀操作會對 module 的引用記數加 10 , 而寫操作會對引用計數減 10, 以下為相關函式:
```c=
static ssize_t refcnt_read(struct file *file, char *buf, size_t size,
loff_t *offset) {
int i;
for (i = 0; i < 10; i++) {
try_module_get(THIS_MODULE);
}
return 0;
}
static ssize_t refcnt_write(struct file *file, const char *buf, size_t size,
loff_t *offset) {
int i;
for (i = 0; i < 10; i++) {
module_put(THIS_MODULE);
}
return (ssize_t)size;
}
```
實驗結果如下
```shell=
$ cd /dev
$ sudo chmod 666 refcnt
$ lsmod
Module Size Used by
refcnt 16384 0
...
$ cat refcnt
$ lsmod
Module Size Used by
refcnt 16384 10
...
$ echo "1" > refcnt
$ lsmod
Module Size Used by
refcnt 16384 0
...
```
實驗結果與先前推測相符
### 2019q1 第 1 週測驗題 測驗 `2`
考慮到以下程式碼:
```
#include <stdint.h>
#define ALIGN_uint32(x, a) __ALIGN_MASK(x, ((uint32_t)(a)) - 1)
#define __ALIGN_MASK(x, mask) (((x) + (mask)) & ~(mask))
```
考慮 4-byte boundary，當 x 是 0x1006, a 是 4, 那麼 ALIGN(x, a) 會得到什麼數值？
#### 思路
以上的巨集是為了 data alignment, 要解此題可以直接將 0x1006 與 4 帶入巨集中並展開, 即可以得到所求結果, 先代入巨集 `ALIGN_uint32` 中可得 `__ALIGN_MASK(0x1006, ((uint32_t)(4)) - 1)` , 展開後為 `(((0x1006) + (3)) & ~(3))` 等於 `0x1009 & 0xfffffffc`, 可得答案為 0x1008
#### 程式驗證
```c=
#include <assert.h>
#include <stdint.h>
#define ALIGN_uint32(x, a) __ALIGN_MASK(x, ((uint32_t)(a)) - 1)
#define __ALIGN_MASK(x, mask) (((x) + (mask)) & ~(mask))
int main() {
assert(ALIGN_uint32(0x1006, 4) == 0x1008);
return 0;
}
```
Sign in with Wallet
Connect another wallet