# 2018q3 Homework3 (list)
contributed by <[pjchiou](https://github.com/pjchiou)>
---
這個作業有一堆問題，看了直播後提醒自己要小心不要==舉燭==。
以下是 outline
- 自我檢查表
- 為什麼要有 list.h ?
- 為何採用 macro 來實作? function call 的成本?
- typeof 與 container_of
- add 與 delete 之外一糸列操作的原因
- `LIST_POISONING` 這樣的設計有何意義？
- 環狀 linked list 的考量
- `list_for_each_safe` 和 `list_for_each` 的差異在哪？"safe" 在執行時期的影響為何？
- for_each 風格的開發方式對程式開發者的影響為何？
- 程式註解裡頭大量存在 `@` 符號
- tests/ 目錄
- 修改 lab0
---
## 自我檢查表
- 為何 Linux 採用 macro 來實作 linked list？一般的 function call 有何成本？
- Linux 應用 linked list 在哪些場合？舉三個案例並附上對應程式碼，需要解說，以及揣摩對應的考量
- GNU extension 的 [typeof](https://gcc.gnu.org/onlinedocs/gcc/Typeof.html) 有何作用？在程式碼中扮演什麼角色？
- 解釋以下巨集的原理
```Clike
#define container_of(ptr, type, member) \
__extension__({ \
const __typeof__(((type *) 0)->member) *__pmember = (ptr); \
(type *) ((char *) __pmember - offsetof(type, member)); \
})
```
- 除了你熟悉的 add 和 delete 操作，`list.h` 還定義一系列操作，為什麼呢？這些有什麼益處？
- `LIST_POISONING` 這樣的設計有何意義？
- linked list 採用環狀是基於哪些考量？
- `list_for_each_safe` 和 `list_for_each` 的差異在哪？"safe" 在執行時期的影響為何？
- for_each 風格的開發方式對程式開發者的影響為何？
- 程式註解裡頭大量存在 `@` 符號，這有何意義？你能否應用在後續的程式開發呢？
- `tests/` 目錄底下的 unit test 的作用為何？就軟體工程來說的精神為何？
- `tests/` 目錄的 unit test 可如何持續精進和改善呢？
---
## 為什麼要有 list.h ?
**這個東西的設計就是來應付全部的 list**
在 [Linux Device Drivers 3/e page 295](https://bootlin.com/doc/books/ldd3.pdf) 有提到
:::info
Operating system kernels, like many other programs, often need to maintain lists of data structures. The Linux kernel has, at times, been host to several linked list implementations at the same time. To reduce the amount of duplicated code, the kernel developers have created a standard implementation of circular, doubly linked lists; others needing to manipulate lists are encouraged to use this facility.
:::
Linux kernel 同時有好幾個 linked list 在運作，這些 linked list 有不同的作用，為了減少大量重複的 code ，因此就先做了一個==基礎建設==, circular doubly linked list, 這樣的東西可以應付所有 list 的需求。
---
## 為何採用 macro 來實作? function call 的成本?
- 適當使用可以增加程式可讀性
- macro 的效能會比較好，因為
- 編繹時期就已知道結果
- 省去了在 stack frame 間的跳躍(也就是 function call 會有的成本)
- 若有大量、重複的 code ，可以省下許多開發上的時間
參考資料
- [list_for_each_entry(pos, head, member) 的範例](https://stackoverflow.com/questions/21361854/how-are-linux-kernel-macros-used-as-functions)
- [Difference between macro and function](https://www.quora.com/What-is-the-difference-between-a-macro-and-a-function-in-C-programming)
- [Macro vs Function](http://www.crazyforcode.com/macros-functions/)
---
## linked list 應用的場合
我們直接從 [Linux Device Drivers 3/e](https://bootlin.com/doc/books/ldd3.pdf) 蒐尋 linked list 就可以找到許多結果。
- Process 在等待佇列時，其資料結構正是 linked list ， [wait.h](https://github.com/torvalds/linux/blob/6f0d349d922ba44e4348a17a78ea51b7135965b1/include/linux/wait.h#L169) 之可以看到其對 linked list 的各項操作是直接使用 list.h 內的函式。以下是其 struct 宣告與對 linked list 的操作。
```clike
struct wait_queue_entry {
unsigned int flags;
void *private;
wait_queue_func_t func;
struct list_head entry;
};
struct wait_queue_head {
spinlock_t lock;
struct list_head head;
};
...
static inline void __add_wait_queue
(struct wait_queue_head *wq_head, struct wait_queue_entry *wq_entry)
{
list_add(&wq_entry->entry, &wq_head->head);
}
...
static inline void __add_wait_queue_entry_tail
(struct wait_queue_head *wq_head, struct wait_queue_entry *wq_entry)
{
list_add_tail(&wq_entry->entry, &wq_head->head);
}
```
---
## typeof 與 container_of
先來比較兩個 structure
```clike=1
/*我們自己寫的 doubly-linked list*/
struct A{
int iData;
char cData;
struct A *prev,*next;
};
/*使用 list.h */
struct list_head{
struct list_head *next,*prev;
};
struct B{
int iData;
char cData;
struct list_head list;
};
```
list.h 在使用上的時候一定是像 `struct B` 的型式，這時候如果我們有一個 `struct B obj` ，我們要怎麼拿到 obj 下一個物件的 `iData` 或 `cData` ? list.next 指向的是 struct list_head 物件，不是 struct B 物件。
這時候就需要 `typeof` 、 `container_of` 與 `offsetof` 了，要了解這個東西首先要有一些背景知識
- [typeof](https://gcc.gnu.org/onlinedocs/gcc/Typeof.html) 可以讓我們動態地得到物件的型別，有一個蠻好的例子是 macro 的使用。C 語言並不允許函式重載，如果是以下的 macro 如果要用函式來實作，就要寫成好幾個版本，對應不同的資料型別。
```clike
#define max(a,b) \
({ typeof (a) _a = (a); \
typeof (b) _b = (b); \
_a > _b ? _a : _b; })
```
- [structure 內每個成員在記憶體內的分佈方式與宣告的順序有關](https://fresh2refresh.com/c-programming/c-structure-padding/)
- `offsetof` 定義在 <linux/stddef.h> 中，用來計算某一個struct結構的成員相對於該結構起始位址的偏移量。
有了這些，就可以看懂 `container_of` 是什麼東西了。以上述的 `struct B` 為例，畫圖說明。
```clike
#define container_of(ptr, type, member) \
__extension__({ \
const __typeof__(((type *) 0)->member) *__pmember = (ptr); \
(type *) ((char *) __pmember - offsetof(type, member)); \
})
```
想得到 `&struct B` 有好幾種方式，而這個 macro 就是讓你用任一種方式都能達到。
- &iData - offsetof(struct B,iData);
- &cData - offsetof(struct B,cData);
- &list - offsetof(struct B,list);
```graphviz
digraph ContainerOf{
node[shape=record]
structB [label="<int> iData|<char> cData|<list> list"]
AddB [label="&struct B | &iData", shape=plaintext]
AddC [label="&cData", shape=plaintext]
Addl [label="&list", shape=plaintext]
AddB -> structB:int:nw
AddC -> structB:char:nw
Addl -> structB:list:nw
}
```
==只要有任一個變數==，就可以找到其容器，進而存取其它變數。
參考資料
- [Linux的container_of 與 offsetof巨集](https://myao0730.blogspot.com/2016/09/linuxcontainerof-offsetof.html)
---
## add 與 delete 之外一糸列操作的原因
我們從 [list.h](https://github.com/torvalds/linux/blob/master/include/linux/list.h) 來看、搭配 [Linux Device Drivers 3/e](https://bootlin.com/doc/books/ldd3.pdf) ，從註解與內文描述我們就可以看出一些函式的設計理念，有一部分雖然看得懂是什麼作用，但不知道何時可以用到，要看懂必須先搞懂幾件事。
- entry 直接代表一個進入點
- head 與其它的 node 在 list 的操作上沒有差別，如果我們要拿 node 上的 data 會透過 `container_of`
```graphviz
digraph list{
splines=true
node[shape=record]
edge[dir=both]
headptr [label="head", shape=plaintext]
node1ptr [label="node1_entry", shape=plaintext]
node2ptr [label="node2_entry", shape=plaintext]
head [label="<prev> prev|<next> next"]
node1 [label="Data|<prev> prev|<next> next"]
node2 [label="Data|<prev> prev|<next> next"]
headptr -> head:prev:nw [dir=forward]
node1ptr -> node1:prev:nw [dir=forward]
node2ptr -> node2:prev:nw [dir=forward]
head:next -> node1:prev
node1:next -> node2:prev
node2:next -> head:prev
}
```
接著我們從 list.h 開始
- 提供編繹時期與執行時期的初始化
```clike
/* 編繹時期 */
#define LIST_HEAD_INIT(name) { &(name), &(name) }
#define LIST_HEAD(name) \
struct list_head name = LIST_HEAD_INIT(name)
/* 執行時期 */
static inline void INIT_LIST_HEAD(struct list_head *list)
{
WRITE_ONCE(list->next, list);
list->prev = list;
}
```
- 如果有 stack 的需要可以用 list_add ；如果需要一個 queue 可以直接改用 list_add_tail 。
- void list_replace(struct list_head *old,struct list_head *new) 用來置換 node ，但暫時不知什麼情況下會用到。
- void list_move(struct list_head *list, struct list_head *head) 從原本的 list 移出，並加入到 head 之中。看起來像在分配 node ?
- list_rotate_left ，旋轉 list 。
- void __list_splice(const struct list_head *list, struct list_head *prev,struct list_head *next) ，用以將 list 插入到 prev 與 next 之間。( list 是一串 node )
- void list_cut_position(struct list_head *list, struct list_head *head, struct list_head *entry) ，與 __list_splice 相反，將 head->next 到 entry (包含) 這段，移出至 list 內。
- list_entry(ptr, type, member) ， 就是 container_of(ptr,type,member) ，取得其容器。
此外，定義了一系列的 macro ，用以走過所有的 node ，假設我們今天有一個 todo_list ，我們要插入一個新的工作，而這個 list 必須要照 priority 由高到低排序。程式碼如下
```clike=1
void todo_add_entry(struct todo_struct *new)
{
struct list_head *ptr;
struct todo_struct *entry;
for (ptr = todo_list.next; ptr != &todo_list; ptr = ptr->next) {
entry = list_entry(ptr, struct todo_struct, list);
if (entry->priority < new->priority) {
list_add_tail(&new->list, ptr);
return;
}
}
list_add_tail(&new->list, &todo_struct)
}
```
可以看出在 #5~#6 的 for 迴圈有一點複雜，如果可以使用 list.h 定義的 macro 的話。可以看出 for 迴圈的部分被大幅簡化。
```clike=1
void todo_add_entry(struct todo_struct *new)
{
struct list_head *ptr;
struct todo_struct *entry;
list_for_each(ptr, &todo_list)
{
entry = list_entry(ptr, struct todo_struct, list);
if (entry->priority < new->priority) {
list_add_tail(&new->list, ptr);
return;
}
}
list_add_tail(&new->list, &todo_struct)
}
```
這類走訪節點的 macro 在 list.h 內有各種不同的變型。
---
## `LIST_POISONING` 這樣的設計有何意義？
直接從 [poison.h](https://github.com/spotify/linux/blob/master/include/linux/poison.h) 來看。
```clike
/*
* These are non-NULL pointers that will result in page faults
* under normal circumstances, used to verify that nobody uses
* non-initialized list entries.
*/
#define LIST_POISON1 ((void *) 0x00100100 + POISON_POINTER_DELTA)
#define LIST_POISON2 ((void *) 0x00200200 + POISON_POINTER_DELTA)
```
這個東西是為了 debug 的時候用的，在確保沒有誤用沒有初始化的記憶體。在 [Linux Device Drivers 3/e](https://bootlin.com/doc/books/ldd3.pdf) 第四章 Debugging Techniques 的引言提到，kernel code 不容易在 debugger 下執行、error 也不容易重現，引發 error 時有可能整個系統一起掛掉，而造成 error 的證據也一併消失。
debug 的其中一個手法就是將這種**有毒的**值設在使用前、後，當這個值被改變我們就會知道有 bug 產生。
---
## 環狀 linked list 的考量
總結使用環狀 doubly-linked list 的原因就是 ==flexibility== 。
- [google 工程師歸納幾種使用 linked list 的情況](https://www.quora.com/Why-are-all-the-linked-lists-circular-in-the-Linux-Kernel)
* singly or doubly
1. 從 memory 與 processing 的成本來看，兩者維護的差異小到可以忽略。
2. doubly 可以完全 cover singly 所有的情況。
3. 某些需求 doubly 會非常好做，例如合併兩個 linked list 。
* circular or not
兩者都有適合的時機， non-circular 甚至還比較常用。如果我們看以下的例子，就會發現這兩個東西長超像，所以直接重複利用同一種東西就好。
```clike
/* Doubly-linked list head */
typedef struct head {
node *head, *tail;
} head;
/* Doubly-linked list element */
typedef struct node {
struct node *next,*prev; //這裡就是一個 struct head
int iMyData;
} node;
```
有了 head 跟 node 當作同一種東西來處理的想法
- 在 list.h 中有一段初始化是這麼寫
```clike
#define LIST_HEAD_INIT(name) { &(name), &(name) }
#define LIST_HEAD(name) \
struct list_head name = LIST_HEAD_INIT(name)
```
乍看之下這跟我學的 C 不一樣阿...看到了使用 circular doubly linked list 的理由後，發覺這個寫法實在是太簡潔、太巧妙了。
- insert 、 list_add_head 、 list_add_tail 變成同一件事
```clike
void __list_add(struct list_head *new,
struct list_head *prev,
struct list_head *next)
{
if (!__list_add_valid(new, prev, next))
return;
next->prev = new;
new->next = next;
new->prev = prev;
WRITE_ONCE(prev->next, new);
}
// 插入到 head 與 head->next 間
void list_add(struct list_head *new, struct list_head *head)
{
__list_add(new, head, head->next);
}
// 插入到 head->prev 與 head 間
void list_add_tail(struct list_head *new, struct list_head *head)
{
__list_add(new, head->prev, head);
}
```
參考資料
- [stackoverflow](https://stackoverflow.com/questions/46089965/why-does-the-linux-kernel-use-circular-doubly-linked-lists-to-store-the-lists-of)
- [Why are all the linked lists circular in the Linux Kernel?](https://www.quora.com/Why-are-all-the-linked-lists-circular-in-the-Linux-Kernel)
## `list_for_each_safe` 和 `list_for_each` 的差異在哪？"safe" 在執行時期的影響為何？
我們直接從 list.h 來看看這兩個 macro ，而且是要連註解一起看，這裡面許多 function 或 macro 都會提示設計這個東西是為了什麼情況。
```clike
/**
* list_for_each - iterate over a list
* @pos: the &struct list_head to use as a loop cursor.
* @head: the head for your list.
*/
#define list_for_each(pos, head) \
for (pos = (head)->next; pos != (head); pos = pos->next)
/**
* list_for_each_safe - iterate over a list safe against removal of list entry
* @pos: the &struct list_head to use as a loop cursor.
* @n: another &struct list_head to use as temporary storage
* @head: the head for your list.
*/
#define list_for_each_safe(pos, n, head) \
for (pos = (head)->next, n = pos->next; pos != (head); \
pos = n, n = pos->next)
```
list_for_each_safe 之中，n 預先存了 pos->next ，是為了避免若迴圈內刪除 pos 這個節點會導致找不到下一個節點，n 僅僅作為一個暫存的空間。
---
## for_each 風格的開發方式對程式開發者的影響為何？
- 在 [Linux Device Drivers 3/e](https://bootlin.com/doc/books/ldd3.pdf) 內提到這可以避免簡單的錯誤（例如不小心寫錯條件），開發者花了一定程度的努力在設計這些 macro 。
- 為了可讀性。像是 vb、C# 這類相對 C 高階的程式語言，都有 for_each 的設計，這樣子的語法更接近人的語言，
---
## 程式註解裡頭大量存在 `@` 符號
看了 doxygen 之後，知道這是給那種可以自動從 code 產生說明文件的程式， `@` 是給這個程式在看的。
不過[這個網站](https://www.kernel.org/doc/)寫 linux 是用 sphinx 這套軟體來產生產件， doxygen 與 sphinx 寫 comment 的語法不太一樣， [sphinx 產生的結果](https://www.kernel.org/doc/html/latest/core-api/kernel-api.html?highlight=list_add#c.list_add)應該是要長這樣。(以 list_add 為例)
```cpp
/**
* list_add - add a new entry
* @new: new entry to be added
* @head: list head to add it after
*
* Insert a new entry after the specified head.
* This is good for implementing stacks.
*/
static inline void list_add(struct list_head *new, struct list_head *head)
{
__list_add(new, head, head->next);
}
```
---
## tests/ 目錄
這個目錄看起來是用簡單的程式測試每個函式是否如預期的運作。
- 程式上常可以看到 divide and conquer 的精神
- 有一些功能有用到 malloc 與 free ，可以加入是否有 memory leak 的測試。
:::info
:question:
有時候逐個 function 測試沒有問題，同時運作又會出問題，但這樣的測試又不可能包含所有的可能性，那我們要如何對這種情況做類似的測試?
還是這樣的測試不在 unit test 的範疇內?
:::
---
## 修改 lab0
原本我們自己寫的時候，跟 list 相關的操作都是自己寫，現在我們要利用這個作業內附的 list.h 來重寫 lab0 。
**首先我在 queue.h 稍做修改。**
```clike
#include <stdbool.h>
#include "list.h"
/************** Data structure declarations ****************/
/* Linked list element (You shouldn't need to change this) */
// typedef struct ELE {
/* Pointer to array holding string.
This array needs to be explicitly allocated and freed */
// char *value;
// struct ELE *next;
//} list_ele_t;
/* Queue structure */
typedef struct {
unsigned int iSize;
char *value;
struct list_head entry;
} queue_t;
```
- #include "list.h" ，這個檔案直接從 linux-list 而來。
- 把 list_ele_t 註解掉，linux 風格的 linked list ，head 跟 node 是一樣的東西。
- queue_t 加入 `char *value` 與 `struct list_head entry`
**q_new** 的修改
```clike=1
queue_t *q_new()
{
queue_t *q = malloc(sizeof(queue_t));
if (!q)
return (NULL);
INIT_LIST_HEAD(&q->entry);
q->iSize = 0;
return q;
}
```
變化不大，只有初始化的地方 #6 變了。
**q_free**
```clike=1
void q_free(queue_t *q)
{
struct list_head *node, *safe;
if (!q)
return;
list_for_each_safe(node, safe, &q->entry)
{
free(container_of(node, queue_t, entry)->value);
free(container_of(node, queue_t, entry));
}
q->iSize = 0;
free(q);
}
```
- 想法還是一樣，從 head 逐步刪掉，看起來簡潔很多
**insert_head**
```clike=1
bool q_insert_head(queue_t *q, char *s)
{
queue_t *newh;
if (!q)
return false;
newh = malloc(sizeof(queue_t));
if (!newh)
return false;
newh->value = malloc(sizeof(char) * strlen(s) + 1);
if (!newh->value) {
free(newh);
return false;
}
strcpy(newh->value, s);
list_add(&newh->entry, &q->entry);
q->iSize++;
return true;
}
```
- 前半段一樣，一直到 #17 前都沒什麼特別，但我之前的版本沒用 strlen 與 strcpy ，後來想了一下，==即使這些 function 很簡單，我們也會寫。若能使用行之有年、常見的函式，一來減少自己出錯的機會，二來提高可讀性，這些函式大家都看過，馬上就可以知道我在做什麼==。
- 原本還要判斷是否為唯一的 node ，現在直接用 list_add 就好。
```clike=1
bool q_insert_tail(queue_t *q, char *s)
{
queue_t *newh;
if (!q)
return false;
newh = malloc(sizeof(queue_t));
if (!newh)
return false;
newh->value = malloc(sizeof(char) * strlen(s) + 1);
if (!newh->value) {
free(newh);
return false;
}
strcpy(newh->value, s);
list_add_tail(&newh->entry, &q->entry);
q->iSize++;
return true;
}
```
- 幾乎完全跟 q_insert_head 一樣，只是換成 list_add_tail 。
**q_remove_head**
```clike=1
bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
/* You need to fix up this code. */
if (!q || list_empty(&q->entry))
return (false);
struct list_head *first = q->entry.next;
if (sp && container_of(first, queue_t, entry)->value) {
strncpy(sp, container_of(first, queue_t, entry)->value, bufsize - 1);
sp[bufsize - 1] = '\0';
}
list_del(first);
free(container_of(first, queue_t, entry)->value);
free(container_of(first, queue_t, entry));
q->iSize--;
return true;
}
```
- 是否為 empty list 與陣列的操作都改由 list.h 內的 function 來做。
**q_reverse**
改變最大的一個函式，比起之前的版本，這一個我沒什麼多想就知道怎麼做了。
```clike=1
void q_reverse(queue_t *q)
{
if (!q || list_empty(&q->entry))
return;
struct list_head *node, *safe, *temp;
list_for_each_safe(node, safe, &q->entry)
{
temp = node->next;
node->next = node->prev;
node->prev = temp;
}
temp = q->entry.next;
q->entry.next = q->entry.prev;
q->entry.prev = temp;
}
```
- 只要把全部的 prev 與 next 對調就好。
剩下在 qtest.c 內的修改沒什麼特別的，只是把原本的 q->head 的部分改成用 container_of ，讓我可以正確取到 value 指向的字串。
利用 linux 風格的 linked list 修改程式後，除了可讀性變好之外，有很大一部份的好處是因為其 circular 的設計，省去了許多判斷式。
Sign in with Wallet
Connect another wallet