# 2019q1 Homework1 (list)
contributed by < `ldotrg` >
###### tags: `linux2019`
## 為何 Linux 採用 macro 來實作 linked list？一般的 function call 有何成本？
- 使用 marco 可以減少執行時期 操作satck 所需的記憶體與時間成本
:::info
在 header 中使用 inline 時，常搭配 static 出現，這樣的 static inline 函式搭配編譯器最佳化，則有 macro 的效果，並得以進行參數形態檢查
:::
TODO: 做實驗檢查
## Linux 應用 linked list 在哪些場合？舉三個案例並附上對應程式碼，需要解說，以及揣摩對應的考量
### 1. 新增一個Character device [linux/cdev.h](https://github.com/torvalds/linux/blob/6f0d349d922ba44e4348a17a78ea51b7135965b1/include/linux/cdev.h#L14)
#### INIT_LIST_HEAD
Kernel Module 要註冊使用 char device 就必須新增一個 list head.
```clike=
void cdev_init(struct cdev *cdev, const struct file_operations *fops)
{
memset(cdev, 0, sizeof *cdev);
INIT_LIST_HEAD(&cdev->list);
kobject_init(&cdev->kobj, &ktype_cdev_default);
cdev->ops = fops;
}
```
#### list_add
每次 user space 呼叫 open 裝置檔(/dev/xxx), 就會增加一個node.
[Linux Code](https://github.com/torvalds/linux/blob/6f0d349d922ba44e4348a17a78ea51b7135965b1/fs/char_dev.c#L376)
```clike=
static int chrdev_open(struct inode *inode, struct file *filp)
{
const struct file_operations *fops;
struct cdev *p;
struct cdev *new = NULL;
int ret = 0;
...
if (!kobj)
return -ENXIO;
new = container_of(kobj, struct cdev, kobj);
spin_lock(&cdev_lock);
/* Check i_cdev again in case somebody beat us to it while
we dropped the lock. */
p = inode->i_cdev;
if (!p) {
inode->i_cdev = p = new;
list_add(&inode->i_devices, &p->list);
new = NULL;
} else if (!cdev_get(p))
ret = -ENXIO;
} else if (!cdev_get(p))
ret = -ENXIO;
spin_unlock(&cdev_lock);
cdev_put(new);
if (ret)
return ret;
...
}
```
## GNU extension 的 [typeof](https://gcc.gnu.org/onlinedocs/gcc/Typeof.html) 有何作用？在程式碼中扮演什麼角色？
typeof 允許我們傳入一個變數，代表的會是該變數的型態。
舉例來說：
``` clike
int a;
typeof(a) b = 10; // equals to "int b = 10;
char s[6] = "Hello";
char *ch;
typeof(ch) k = s; // equals to "char *k = s;
```
Real world Example: 為了避免重複呼叫函式`f`第三次
```clike=
#define max(a,b) \
({ __typeof__ (a) _a = (a); \
__typeof__ (b) _b = (b); \
_a > _b ? _a : _b; })
max(f(1), f(2));
```
## 解釋以下巨集的原理
```clike
#define container_of(ptr, type, member) \
__extension__({ \
const __typeof__(((type *) 0)->member) *__pmember = (ptr); \
(type *) ((char *) __pmember - offsetof(type, member)); \
})
```
Why we need the `container_of`?
__If strcut x contains y, we could find the pointer to x given the pointer to y__
### 拆解
### `__extension__`
翻閱 gcc 文件中的 [Alternative Keywords](https://gcc.gnu.org/onlinedocs/gcc/Alternate-Keywords.html#Alternate-Keywords) 提到
> You can prevent such warnings within one expression by writing `__extension__` before the expression.
GNU C Extension裏面有使用到非標準的ANSI C的語法, 因此會產生警告.
如果不想要看見這個警告，只要在表達式之加入`__extension__`修飾字.
### `__typeof__`
gcc 文件中的 [Alternative Keywords](https://gcc.gnu.org/onlinedocs/gcc/Alternate-Keywords.html#Alternate-Keywords) 可以得知`__`是為了相容性考量而加的，作用和 keyword `typeof` 相同，在 [Typeof](https://gcc.gnu.org/onlinedocs/gcc/Typeof.html#Typeof) 章節中可以得知 typeof 是用來獲取變數的型別。
### `((type *) 0)->member`
照理來說 NULL pointer dereference 應該會出錯.
> The operand of typeof is evaluated for its side effects if and only if it is an expression of variably modified type or the name of such a type.
> 黑人問號？？
### `offsetof`
:::danger
找出 C99 規格中對應的說明。注意 [offsetof](http://man7.org/linux/man-pages/man3/offsetof.3.html)
:notes: jserv
:::
macro 定義
```clike=
#define offsetof(TYPE, MEMBER) ((size_t)&((TYPE *)0)->MEMBER)
```
這裡的 `&((TYPE *)0)->MEMBER` 並不是求值後取地址，struct 中的成員變數地址是相對於 struct 的初始地址的，並且編譯時期就可以確定也就沒必要在運行時求值了，所以在此得到的是 `0 + offset of MEMBER in struct`
:::success
將 $0$ 改成 $n\in N$,會發現回傳值會增加 $n$
:::
延伸閱讀： [How to Use C's offsetof() Macro](https://barrgroup.com/Embedded-Systems/How-To/C-Offsetof-Macro?fbclid=IwAR0H5IGZ7nJUmoRE2gyeyCGllQglZBhZNJkyFDNDHUdf1DDWwsQajhFg1GA)
### `{}` compound statement
第一次看到時覺得很奇怪，這 macro 到底要怎麼 return(廣義上的) 結果阿?
gcc docs 的 [Statement-Exprs](https://gcc.gnu.org/onlinedocs/gcc/Statement-Exprs.html) 章節中提到，這被稱為 **compound statement** 且回傳值是最後一個 expression 的結果
> The last thing in the compound statement should be an expression followed by a semicolon; the value of this subexpression serves as the value of the entire construct.
### `(type *) ((char *) __pmember - offsetof(type, member));`
- Run yourself:
```clike=
#include <stdio.h>
#define pointer(T) typeof(T *)
#define array(T, N) typeof(T [N])
#define my_offsetof(TYPE, MEMBER) ((size_t)&((TYPE *)0)->MEMBER)
#define my_container_of(ptr, type, member) \
__extension__({ \
const __typeof__(((type *) 0)->member) *__ptrmember = (ptr); \
(type *) ((char *) __ptrmember - my_offsetof(type, member));\
})
__attribute__((packed, aligned(4))) struct hello {
int aa;
int bb;
unsigned long cc;
int *dd;
};
int main (char *argv[], int argc) {
int aa;
__typeof__(aa) bb;
struct hello hel_obj;
array (pointer (char), 4) y;
aa = 5566;
bb = 7788;
printf("%d/%d sizeof y: %d \n", aa, bb, sizeof(y));
printf("pointer of member dd 0x%x\n", &hel_obj.dd);
printf("pointer of hel_obj: 0x%x\n", my_container_of(&hel_obj.dd, struct hello, dd));
return 0;
}
```
- [ ] 除了你熟悉的 add 和 delete 操作，`list.h` 還定義一系列操作，為什麼呢？這些有什麼益處？
## `LIST_POISONING` 這樣的設計有何意義？
```clike=
#ifdef LIST_POISONING
node->prev = (struct list_head *) (0x00100100);
node->next = (struct list_head *) (0x00200200);
#endif
```
故意將已刪除節點的指標指向特定的位址.
這些特別的位址可以作為分析kernel panic
Reference: [Kernel Debugging wiki](https://wiki.litmus-rt.org/litmus/KernelDebugging)
## linked list 採用環狀是基於哪些考量？
- 用$O(1)$ 的時間複雜度將新節點插入至尾端,無須走訪全部節點.
- 可參考`list_add_tail`實做
```clike=
static inline void list_add_tail(struct list_head *node, struct list_head *head)
{
// 1. get the tail node
struct list_head *prev = head->prev;
// 2. update tail node
prev->next = node;
// 3. Update new node
node->next = head;
node->prev = prev;
// 4. Update the head
head->prev = node;
}
```
- [ ] 什麼情境會需要對 linked list 做排序呢？舉出真實世界的應用，最好在作業系統核心出現
- [ ] 什麼情境會需要需要找到 [第 k 大/小元素](https://www.geeksforgeeks.org/kth-smallestlargest-element-unsorted-array/) 呢？又，你打算如何實作？
- [ ] `list_for_each_safe` 和 `list_for_each` 的差異在哪？"safe" 在執行時期的影響為何？
- [ ] for_each 風格的開發方式對程式開發者的影響為何？
* 提示：對照其他程式語言，如 Perl 和 Python
- [ ] 程式註解裡頭大量存在 @ 符號，這有何意義？你能否應用在後續的程式開發呢？
提示: 對照看 Doxygen
- [ ] tests/ 目錄底下的 unit test 的作用為何？就軟體工程來說的精神為何？
- [ ] tests/ 目錄的 unit test 可如何持續精進和改善呢？
## Implementation [Merge Sort](https://github.com/ldotrg/linux-list/blob/master/examples/merge-sort.c)
- list_split
- 利用fast與slow pointer找到需要切割的點
- 再使用`list_cut_position` 分成左右兩半的list
- list_merge
- leetcode經典題,merge two sorted list, merge K sorted list
- 動畫 https://www.youtube.com/watch?v=odUJXFJR6Q4
- 使用的list工具：`list_splice_tail`,`list_first_entry` , `list_move_tail`
- list_merge_sort
其實最難的不是實做,而是要怎麼測試
1. 在實做時,當然先用最簡單的`printf`觀察排序結果.
2. 接著通過題目的基本測試
- [ ] 以上基本的流程通過後,接著就是要測試效能啦(ToDo)
- [ ] 研究unit test 的技巧(ToDo)
- [ ] 導入像lab0作業的自動評分系統`qtest`(ToDo)
> 想要做的事情好多阿
### Original Assignment info: [F02: list](/u4FPWOKHQXiKrn4MMvkvWA)
###### tags: `Linux Linked List`
Sign in with Wallet
Connect another wallet