# 2018q3 Homework3 (list)
contributed by < `happyincent` >
## 自我檢查事項
### 為何 Linux 採用 macro 來實作 linked list？一般的 function call 有何成本？
從 [list.h](https://github.com/sysprog21/linux-list/blob/master/include/list.h) 可以看出
* 更動 list 的 function 是使用 `static inline` 而非 `#define`
* `#define` 除了使用在 ==簡化並展開程式碼==，也在 `container_of` 使用 [Statements and Declarations in Expressions](https://gcc.gnu.org/onlinedocs/gcc/Statement-Exprs.html) 來替換 function call
#### macro
* 在 preprocessed 時處理
* 文本替換 (增加程式碼可讀性)，重複使用 macro (large code) 會使執行檔變大
* 不檢查輸入參數的類型，很難發現編譯錯誤，也可能導致無法預料的後果，[例如：](https://www.geeksforgeeks.org/macros-vs-functions/)
```c
#include<stdio.h>
#define CUBE(b) b*b*b // 1+2*1+2*1+2
#define CUBE2(b) (b)*(b)*(b) // (1+2)*(1+2)*(1+2)
int main()
{
printf("%d %d\n", CUBE(1+2), CUBE2(1+2)); // 7 27
return 0;
}
```
* [Macro v.s. Function](https://stackoverflow.com/a/33953761)
* ==function 呼叫時需要做額外的 stack 操作==
#### [inline function](http://gnitnaw.github.io/%E7%A8%8B%E5%BC%8F%E8%AA%9E%E8%A8%80/2016/06/14/C_inline.html)
* inline 是一種編譯最佳化的方式，將指定的函式插入並取代每一處呼叫該函式的地方
* 編譯器可以不接受原始碼給的 inline 建議，不用取代的方式而維持呼叫該指定函式。但是 macro 一定得替換。
---
### Linux 應用 linked list 在哪些場合？舉三個案例並附上對應程式碼，需要解說，以及揣摩對應的考量
* Android kernel 3.18 - OSS sound_core ([./sound/sound_core.c](https://android.googlesource.com/kernel/common/+/android-3.18/sound/sound_core.c))
```c
struct sound_unit
{
int unit_minor;
const struct file_operations *unit_fops;
struct sound_unit *next;
char name[32];
};
```
* sound_unit
* unit_minor: 0 ~ 15 (SOUND_STEP=16, device number % SOUND_STEP)
* unit_fops: filesystem 檔案操作
```c
static const struct file_operations soundcore_fops =
{
/* We must have an owner or the module locking fails */
.owner = THIS_MODULE,
.open = soundcore_open,
.llseek = noop_llseek,
};
```
* name: device name ("mixer", "sequencer", "midi", "dsp", ...)
* sound_insert_unit:
* 註冊特定種類的 device 時 (e.g., `register_sound_mixer`)，會傳入 global 的 `static struct sound_unit *chains[SOUND_STEP];` 中的其中一個 list head (e.g., Mixers: `&chains[0]`) 給此 function 的 parameter `struct sound_unit **list`，然後 insert 一個新的 sound_unit 到這個 chain 中
---
### GNU extension 的 [typeof](https://gcc.gnu.org/onlinedocs/gcc/Typeof.html) 有何作用？在程式碼中扮演什麼角色？
[GNU typeof](https://gcc.gnu.org/onlinedocs/gcc/Typeof.html) (ISO C - `__typeof__`)
* refer to the type of an expression
* `typeof` is evaluated if and only if it is
* an expression of variably modified type
* the name of such a type
* [__builtin_types_compatible_p](https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html)
```c
#include <stdio.h>
/* https://medium.com/@maicki/type-inference-with-auto-type-55a38ef56372 */
#define let __auto_type const
#define var __auto_type
/* https://stackoverflow.com/a/36588221 */
#define __is_constant_int(X) _Generic((&X), \
const int *: "a const int", \
int *: "a non-const int")
/* https://stackoverflow.com/a/1666362 */
typedef void (*stdfx)(int);
void fx_typ(stdfx fx); // ok
#define FX_TYPE void (*)(int)
// void fx_def(FX_TYPE fx); // error, no type: void (*)(int)
int main()
{
let a = 123;
var b = 123.0;
printf("%d\n", __builtin_types_compatible_p( typeof(a), int const )); // 1
printf("%d\n", __builtin_types_compatible_p( typeof(a), int )); // 1
printf("%d\n", __builtin_types_compatible_p( typeof(a), typeof(int *) )); // 0
printf("%d\n", __builtin_types_compatible_p( typeof(a), typeof(b) )); // 0
var a1 = a;
printf("%s\n", __is_constant_int(a1)); // a const int
var b1 = (int)b;
printf("%s\n", __is_constant_int(b1)); // a non-const int
}
```
---
### 解釋以下巨集的原理
```Clike
#define container_of(ptr, type, member) \
__extension__({ \
const __typeof__(((type *) 0)->member) *__pmember = (ptr); \
(type *) ((char *) __pmember - offsetof(type, member)); \
})
```
#### container_of 的 parameters
```c
/**
* container_of() - Calculate address of object that contains address ptr
* @ptr: pointer to member variable
* @type: type of the structure containing ptr
* @member: name of the member variable in struct @type
*
* Return: @type pointer of object containing ptr
*/
```
* ptr: pointer to list node
* type: 包含 list node 的 struct 是什麼 type
* member: struct 中 type 為 list node 的 member 的名字
* return: pointer to 包含 list node 的 struct
#### list.h 中 container_of 只使用於 list_entry
```c
#define list_entry(node, type, member) container_of(node, type, member)
```
#### `({ ... })`
* A compound statement enclosed in parentheses
```c
#define Square(x) ({ \
typeof(x) y = (x); \
y*y; \
})
```
* [Statements and Declarations in Expressions](https://gcc.gnu.org/onlinedocs/gcc/Statement-Exprs.html)
#### `__extension__`
* `-pedantic` or `-Wpedantic`
* Issue all the warnings demanded by strict ISO C and ISO C++; reject all programs that use forbidden extensions.
* ISO C `-std`、`-ansi`
* `-Wpedantic` 不會 warning 開頭和結尾為 `__`
* 不會 Warning the expression that follows `__extension__`
* only system header files should use these escape routes
* source: gnu gcc
* [Warning-Options](https://gcc.gnu.org/onlinedocs/gcc/Warning-Options.html#Warning-Options)
* [Alternate-Keywords](https://gcc.gnu.org/onlinedocs/gcc/Alternate-Keywords.html#Alternate-Keywords)
#### `__typeof__` 同 `typeof`
* `((type *) 0)->member`: 將位址 0 轉為 pointer (point to the struct type)
* `__typeof__(((type *) 0)->member)`: 取得 struct 中此 member 的 type
:::info
`const __typeof__(((type *) 0)->member) *__pmember = (ptr);` 可以用來確認傳入 ptr 的 type 是否正確 [[stackoverflow](https://stackoverflow.com/questions/6083734/rationale-behind-the-container-of-macro-in-linux-list-h)]
:::
```c
#include <stdio.h>
#include <stddef.h>
#define container_of(ptr, type, member) \
__extension__({ \
const __typeof__(((type *) 0)->member) *__pmember = (ptr); \
(type *) ((char *) __pmember - offsetof(type, member)); \
})
#define container_of_2(ptr, type, member) \
((type *) ((char *) (ptr) -offsetof(type, member)))
typedef struct _foo { int bar; } foo;
int main()
{
foo f;
double *ptr = (double *)&f.bar;
foo *p1 = container_of(ptr, foo, bar);
// ↑ warning: pointer type mismatch in conditional expression
// const __typeof__(((type *) 0)->member) *__pmember = (ptr);
// ^
foo *p2 = container_of_2(ptr, foo, bar);
// ↑ no warning
printf("%d\n", (p1 == p2) ? 1 : 0); // 1
}
```
#### `offsetof`
* [stddef.h](https://github.com/torvalds/linux/blob/master/include/linux/stddef.h)
```c
#undef offsetof
#ifdef __compiler_offsetof
#define offsetof(TYPE, MEMBER) __compiler_offsetof(TYPE, MEMBER)
#else
#define offsetof(TYPE, MEMBER) ((size_t)&((TYPE *)0)->MEMBER)
#endif
```
* 第一種使用 compiler 內建函式，`__compiler_offsetof` 定義在 `compiler_types.h`
```c
#define __compiler_offsetof(a, b) __builtin_offsetof(a, b)
```
* 第二種將 0 轉為 popinter (TYPE 起始位址為 0)，然後以 `&` 拿到 MEMBER 的位址，即可得到 member 在 TYPE 中的 offest
* 由以下範例，可以看出
* a structure is a type consisting of a sequence of members, whose storage is allocated in an ordered sequence (6.7.2.1 - 5)
* struct 會對齊 word size (8 bytes for 64-bit cpu, 4 bytes for 32-bit cpu)
```c
#include <stdio.h>
#include <stddef.h>
#define container_of(ptr, type, member) \
__extension__({ \
const __typeof__(((type *) 0)->member) *__pmember = (ptr); \
(type *) ((char *) __pmember - offsetof(type, member)); \
})
typedef struct T {
int member_bit : 9;
char member_char;
long member_long;
} TYPE;
int main()
{
printf("%zu\n", sizeof(TYPE)); // 16, 8 (armv7l)
printf("%zu\n", offsetof(TYPE, member_char)); // 2, 2 (armv7l)
printf("%zu\n", offsetof(TYPE, member_long)); // 8, 4 (armv7l)
// printf("%zu\n", offsetof(TYPE, member_bit)); // error
TYPE t;
printf("%p, ", &t);
printf("%p, ", &t.member_long);
printf("%p\n", container_of(&t.member_long, TYPE, member_long));
// 0x7ffff9572f00, 0x7ffff9572f08, 0x7ffff9572f00 (x86-64)
// 0x7ea6b20c, 0x7ea6b210, 0x7ea6b20c (armv7l)
}
```
#### `(type *) ((char *) __pmember - offsetof(type, member));`
* offsetof return `type size_t with the number of bytes (offset)` [[source](http://www.cplusplus.com/reference/cstddef/offsetof/)]
* `type pointer` 在做 arithmetic 運算時會以 `sizeof(type)` 的作為一個單位的大小，因此要先將 `__pmember` 轉為 (char *) ==以 byte 為單位==進行運算
---
### 除了你熟悉的 add 和 delete 操作，`list.h` 還定義一系列操作，為什麼呢？這些有什麼益處？
* 還定義了 `list_empty`、`list_is_singular`、`list_splice`、`list_move` 以及 `#define` 了許多可以簡化程式碼的 Macro
* [Manipulating Linked Lists](https://notes.shichao.io/lkd/ch6/#manipulating-linked-lists)
* 在 `list.h` 定義常用 linked list 的實作可以避免在 kernel 其他地方用到 list 時實作重複的程式碼
### `LIST_POISONING` 這樣的設計有何意義？
`list_del()` 的註解中提到刪除時先將 `next/prev` 改為 predefined 的 memory address (systems prohibit access)，之後使用這段記憶體時才能知道錯誤是發生在用到 poisoning 的記憶體
### linked list 採用環狀是基於哪些考量？
環狀可以做到單向或雙向 linked list 做到的事情
### `list_for_each_safe` 和 `list_for_each` 的差異在哪？"safe" 在執行時期的影響為何？
```c
#define list_for_each(node, head) \
for (node = (head)->next; node != (head); node = node->next)
```
在 `list_for_each` 裡面做 `list_del` 時 ([list_for_each.c](https://github.com/sysprog21/linux-list/blob/master/tests/list_for_each.c#L37)) 如果
* 有 `LIST_POISONING` 會改掉 `node->next`
* 迴圈結束後 node->next 不是預期的
* `free(node)`
* 迴圈結束後 node->next 是 undefined behavior
```c
#define list_for_each_safe(node, safe, head) \
for (node = (head)->next, safe = node->next; node != (head); \
node = safe, safe = node->next)
```
第一次執行、迴圈結束時會記錄 safe 為 node->next，因此每次迴圈結束後 node = safe 可以確保 node 是正確的
### for_each 風格的開發方式對程式開發者的影響為何？
* Python - For loops
* The Python `for` statement iterates over `the members of a sequence` in order, executing the block each time.
* 不用額外寫結束的判斷、移動到下一步的程式碼
* 可以明確地知道迴圈是在 iterate 使用的資料結構
### 程式註解裡頭大量存在 `@` 符號，這有何意義？你能否應用在後續的程式開發呢？
* `@` 代表 parameter
* Name of a function parameter. (No cross-referencing, just formatting.)
* linux 的 [kernel doc](https://www.kernel.org/doc/html/v4.9/kernel-documentation.html) 使用 [Sphinx](https://github.com/sphinx-doc/sphinx) (Python 69.5%) 生成
* example from linux kernel doc
```c
/**
* foobar() - Brief description of foobar.
* @arg: Description of argument of foobar.
*
* Longer description of foobar.
*
* Return: Description of return value of foobar.
*/
int foobar(int arg)
```
* [Doxygen](https://github.com/doxygen/doxygen) (C++ 85.4%)
* example from Doxygen doc
```c
/*!
* Copies bytes from a source memory area to a destination memory area,
* where both areas may not overlap.
* @param[out] dest The memory area to copy to.
* @param[in] src The memory area to copy from.
* @param[in] n The number of bytes to copy
*/
void memcpy(void *dest, const void *src, size_t n);
```
### `tests/` 目錄底下的 unit test 的作用為何？就軟體工程來說的精神為何？
* `tests/` 目錄下的每個 .c 檔使用 `assert(expr)` 做測試
* `man assert`: If expression is false , assert() prints an error message to standard error and terminates the program by calling abort(3).
* 針對 list.h 中的 `static inline` function 或 `#define` macro 做測試除了
```
$ diff -y <(cat ./include/list.h | grep "static inline\|#define" | sed 's/#define //g' | sed 's/static inline void //g' | sed 's/static inline int //g' | cut -d'(' -f1 | tail -n+4 | sort) <(ls ./tests/ | tail -n+2 | cut -d'.' -f1 | sed 's/containerof/container_of/' | sort)
container_of container_of
INIT_LIST_HEAD <
list_add list_add
list_add_tail list_add_tail
list_cut_position list_cut_position
list_del list_del
list_del_init list_del_init
list_empty <
list_entry list_entry
list_first_entry list_first_entry
list_for_each list_for_each
list_for_each_entry list_for_each_entry
list_for_each_entry_safe list_for_each_entry_safe
list_for_each_safe list_for_each_safe
LIST_HEAD | list_init-explicit
> list_init-global
> list_init-local
list_is_singular list_is_singular
list_last_entry list_last_entry
list_move list_move
list_move_tail list_move_tail
list_splice list_splice
list_splice_init list_splice_init
list_splice_tail list_splice_tail
list_splice_tail_init list_splice_tail_init
```
* Unit testing ([wiki](https://en.wikipedia.org/wiki/Unit_testing))
* Advantages
* to isolate each part of the program and show that the individual parts are correct
* finds problems early in the development cycle
* bugs in the programmer's implementation
* flaws or missing parts of the specification for the unit
* Limitations and disadvantages
* cannot evaluate every execution path in any but the most trivial programs
* not catch integration errors or broader system-level errors
* rigorous discipline is needed
### `tests/` 目錄的 unit test 可如何持續精進和改善呢？
加上註解來解釋個別 unit test 想達成的 specification
---
## 改寫 [Homework1: lab0](https://hackmd.io/s/BJp_jq-tm)
### queue.h 更動
```c
typedef struct ELE {
char *value;
struct list_head list;
} list_ele_t;
typedef struct {
struct list_head q_head;
size_t q_size;
} queue_t;
```
* list_ele_t 改為存放
1. 字串 value
2. 存放 prec 和 next 的 list (`struct list_head`, `list.h`)
* queue_t 改為存放
1. circular doubly-linked list 中的 q_head
2. queue 現在的大小 q_size
### queue.c 更動
#### q_new
```c
INIT_LIST_HEAD(&(q->q_head));
```
使用 macro `INIT_LIST_HEAD` 初始化 empty list head (circular)
#### q_free
```c
struct list_head *li = NULL, *lis = NULL;
list_ele_t *item;
list_for_each_safe(li, lis, &(q->q_head))
{
item = list_entry(li, list_ele_t, list);
if (item->value != NULL) {
free(item->value);
item->value = NULL;
}
list_del(&(item->list));
free(item);
item = NULL;
}
```
使用 macro `list_for_each_safe`、`list_entry` 來進行 free 的動作
#### q_insert_head、q_insert_tail
```c
list_ele_t *item = malloc(sizeof(list_ele_t));
/* insert head */
list_add_tail(&(item->list), &(q->q_head));
/* insert tail */
list_add_tail(&(item->list), &(q->q_head));
```
使用 macro `list_add`、`list_add_tail` 進行 insert
:::info
* cppcheck 指出之後會用到的 item 沒有被 free 掉
* 暫時在 `queue.c` 加上 `// cppcheck-suppress memleak`、修改 `pre-commit.hook` 加上 `--inline-suppr` 到 `CPPCHECK_OPTS`
```
$ cppcheck queue.c
Checking queue.c...
Checking queue.c: INTERNAL...
[queue.c:106]: (error) Memory leak: item
[queue.c:153]: (error) Memory leak: item
Checking queue.c: LIST_POISONING...
Checking queue.c: __GNUC__...
Checking queue.c: __cplusplus...
```
:::
#### q_remove_head
```c
list_ele_t *item = list_first_entry(&(q->q_head), list_ele_t, list);
...
list_del(&(item->list));
free(item);
...
```
使用 macro `list_first_entry` 取得 queue 的第一個 element，`list_del` 更新 list 中指標的連接
#### q_reverse
```c
/* iterate the queue to reverse each node's next and prev */
struct list_head *li = NULL, *lis = NULL, *tmp = &(q->q_head);
list_for_each_safe(li, lis, &(q->q_head))
{
li->prev = lis;
li->next = tmp;
tmp = li;
}
q->q_head.prev = q->q_head.next;
q->q_head.next = tmp;
```
以 macro `list_for_each_safe` 對 list 中 (屬於 queue) 的 node 反轉其 prev、next，最後更改 q_head 的 prev、next
### qtest.c 更動
#### show_queue
```c
...
struct list_head *e = &(q->q_head);
...
if (ok && !list_empty(&(q->q_head)) && cnt < qcnt) {
list_ele_t *item;
list_for_each(e, &(q->q_head))
{
item = list_entry(e, list_ele_t, list);
if (cnt < big_queue_size)
report_noreturn(vlevel, cnt == 0 ? "%s" : " %s",
item->value);
cnt++;
ok = ok && !error_check();
}
}
...
if (e == &(q->q_head)) {
if (cnt <= big_queue_size)
report(vlevel, "]");
else
report(vlevel, " ... ]");
}
...
```
改用 list_for_each 來 traverse list 直到 `node == (head)` 時停止
#### 其他
* 將 `q->head->value` 改為 `list_first_entry(&(q->q_head), list_ele_t, list)->value`
* 將 `q->head == NULL` 改為 `list_empty(&(q->q_head))`
### mytest.sh
```bash
#!/bin/bash
n=$(wc -l cities.txt | cut -d' ' -f1)
ih=$(cat cities.txt | head -n$n | cut -d',' -f1 | sed 's/ /_/g' | sed 's/^/ih /g')
it=$(cat cities.txt | head -n$n | cut -d',' -f2 | sed 's/ /_/g' | sed 's/^/it /g')
rh=$(for (( i=0; i<$n; i++ )); do echo rh; done)
SECONDS=0
cat <<EOF | ./qtest &> /dev/null
option fail 0
option malloc 0
new
$ih
$it
size
reverse
size
$rh
show
free
quit
EOF
echo "echo \$? = $(echo $?)"
echo "Elapsed $SECONDS seconds."
```
```
$ ./mytest.sh
echo $? = 0
Elapsed 1006 seconds.
```
先將 qtest.c 第 309、449、453-456 行 report 的部分註解掉，再以 cities.txt 為測資丟入 qtest
Sign in with Wallet
Connect another wallet