# 2018q3 Homework3 ([list](https://hackmd.io/s/SyVPDd1cX))
contributed by < [wingard](https://github.com/wingard) >
###### tags: `HW3`
## 作業要求
* 回答上述「Linux 風格的 linked list」裡頭「自我檢查清單」的所有問題，需要附上對應的參考資料和必要的程式碼
* 從 [linux-list](https://github.com/sysprog21/linux-list) 學習裡頭的技巧，包含裡頭 unit test 的設計，之後改寫 [Homework1: lab0](https://hackmd.io/s/BJp_jq-tm) 的程式碼，需要重新 fork，命名為 ==lab-list==，使其成為 doubly-linked list 且充分考慮到 circular
* 附上你的修改過程，也需要讓 `qtest` 得以支援
* 可將 [dict](https://hackmd.io/s/B1Bq5Jat7) 裡頭的測試資料拿來作效能分析的輸入
---
## 自我檢查清單
### 1. 為何 Linux 採用 macro 來實作 linked list？一般的 function call 有何成本？
macro 是由 gcc toolchain 中的 preprocesser 提供的一個語言特性，會在編譯時期將代碼中的 macro 展開，而不是使用 function call，就如同 inline function 一樣。function call 相較於 macro 多出了兩個階段，會增加stacking / unstacking 的成本:
* function prolologe
* function epologe
分別是用於建立與摧毀 function 存放區域變數所需的 stack frame，過程中會對 stack 進行讀寫(push, pop)，造成記憶體讀寫的時間開銷。所以若是沒有需要維護 function 中的區域變數時，或許可以改採用 macro 的形式來寫作，而 linux kernel 中的 linked list 操作就是如此。
### 2. Linux 應用 linked list 在哪些場合？舉三個案例並附上對應程式碼，需要解說，以及揣摩對應的考量
#### struct list_head
```c
struct list_head {
struct list_head *next, *prev;
};
```
和一般撰寫程式時直接利用該 struct 的指標操作不同，linux kernel 中的 linked list 實作多是這種單一作用的元件，配合 `container_of` macro 讓 linked list 變成是一個能夠被模組化的特性，也就不必為每個 struct 寫不同的 linked list 操作函式。
#### include/linux/sched.h
```c
struct task_struct {
...
struct list_head children;
struct list_head sibling;
...
}
```
在 `task_struct` 中利用 `list_head` 來建立 parent, children 的樹狀關係
#### 新增一個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.
```c=1
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;
...
}
```
### 3. GNU extension 的 [typeof](https://gcc.gnu.org/onlinedocs/gcc/Typeof.html) 有何作用？在程式碼中扮演什麼角色？
* typeof(a) 可以回傳 a 的 type ， 經常與 statement expression 搭配使用，例如以下的 `max` 巨集適用於各種形式的資料比較:
```c=1
#define max(a,b) \
({ typeof (a) _a = (a); \
typeof (b) _b = (b); \
_a > _b ? _a : _b; })
```
### 4. 解釋以下巨集的原理
```c=1
#define container_of(ptr, type, member) \
__extension__({ \
const __typeof__(((type *) 0)->member) *__pmember = (ptr); \
(type *) ((char *) __pmember - offsetof(type, member)); \
})
```
看起來很複雜，總之先一步步拆解
### 4.1 先分析`__extension__ ({ ... \ ... \ ... })`
#### `__extension__`
翻閱 gcc 文件中的 [Alternative Keywords](https://gcc.gnu.org/onlinedocs/gcc/Alternate-Keywords.html#Alternate-Keywords) 提到
> -pedantic and other options cause warnings for many GNU C extensions. You can prevent such warnings within one expression by writing `__extension__` before the expression. `__extension__` has no effect aside from this.
看來是為了 surpress 可能的警告訊息。
#### `({ ... \ ... \ ... })`
這樣的表示，這個是 gcc 的 [Statements and Declarations in Expressions](https://gcc.gnu.org/onlinedocs/gcc/Statement-Exprs.html#Statement-Exprs) ;
這被稱為 **compound statement** ，編譯器會將整個 block 視為一個整體，並將 block 內最後一個 statement 作為回傳值:
> 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. (If you use some other kind of statement last within the braces, the construct has type void, and thus effectively no value.)
Example:
```c
int x = ({1; 2; 3;});
printf("%d\n", x); // print 3
```
也就是說，`container_of` 這個 macro:
```c=1
#define container_of(ptr, type, member) \
__extension__({ \
const __typeof__(((type *) 0)->member) *__pmember = (ptr); \
(type *) ((char *) __pmember - offsetof(type, member)); \
})
```
會回傳最後一行 `(type *) ((char *) __pmember - offsetof(type, member));` 的編譯結果。
### 4.2 再分析 `const __typeof__(((type *) 0)->member) *__pmember = (ptr);`
#### `__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 是用來獲取變數的型別。
:::info
Question: 為何要加 `const` 在 `__typeof__` 之前?
:::
#### `((type *) 0)->member`
照理來說 NULL pointer dereference 應該會出錯，不過在這裡的寫法行得通的原因我認為是使用了 `typeof` 的緣故，[Typeof](https://gcc.gnu.org/onlinedocs/gcc/Typeof.html#Typeof) 章節中提到參數只有在特殊情況下(type 在編譯時期無法確定)才會被 evaluate。
> 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`
給出 macro 定義
```c
#define offsetof(type, member) ((size_t) &((type *)0)->member)
```
這裡的 `&((TYPE *)0)->MEMBER` 並不是求值後取地址，struct 中的成員變數地址是相對於 struct 的初始地址的，並且編譯時期就可以確定也就沒必要在運行時求值了，所以在此得到的是 `0 + offset of MEMBER in struct`
#### 拼湊起來
`const __typeof__(((type *) 0)->member) *__pmember = (ptr);`
* 將數值 `0` 強制轉型成TYPE指標型別，`0` 會被當作該TYPE的起始地址。
* 然後再指向 `member` 成員，就可以得到 `member` 的地址。
* 因為起始地址等於 `0`，所以 `member` 的地址也就等於 `member` 與起始地址 `0` 的偏移 (offset)。
* 產生一個 pointer to 給該型別的 `__pmember` 。
* 將 `ptr` assign 給 `__pmember`，故`__pmember` 目前指向的是 `member` 的地址。
一個類似 `((type *) 0)->member)` 的例子:
```c=1
struct s {
char m1;
char m2;
};
/* This will print 1 */
printf("%d\n", &((struct s*)0)->m2);
```
### 4.3 最後分析 `(type *) ((char *) __pmember - offsetof(type, member));`
* `offsetof(type, member)`用來計算某一個結構的成員相對於該結構起始位址的偏移量，也就是離起始位址有多遠的距離
* 將絕對位址 `(char*) __pmember` 減去 `offsetof(type, member)` ，就可以得到 struct 的起始位址。
* 最後透過`(type*)` 將起始位置轉型為 pointer to `type`。
### 4.4 完整拼湊起來
```c
#define container_of(ptr, type, member) \
__extension__({ \
const __typeof__(((type *) 0)->member) *__pmember = (ptr); \
(type *) ((char *) __pmember - offsetof(type, member)); \
})
```
1. 定義一個指向`member`型別的指標`__pmember`，然後將參數`ptr`餵給該指標。
2. 將`__pmember`的位址減掉member與結構起始點的偏移(利用offsetof)就可得到該結構的起始點位址。
3. 最後透過`(type*)` 將起始位置轉型為 pointer to `type` ，並回傳此結果。
也就是說，container_of 是用來取得struct結構的起始位址:
只要知道該結構的任一個成員的位址，就可以使用container_of macro來算出該結構的起始位址。
下面是簡圖:
#### 用法:
```c
struct task_struct *ts = container_of(p, struct task_struct, children);
```
可以取得此*ts task handle的起始位址
#### 簡例:
```c=1
#include <stdio.h>
#define offsetof(type, member) ((size_t) &((type *)0)->member)
#define container_of(ptr, type, member) \
__extension__({ \
const __typeof__(((type *) 0)->member) *__pmember = (ptr); \
(type *) ((char *) __pmember - offsetof(type, member)); \
})
struct MY_DATA {
int Data_A ,Data_B , Data_C;
struct MY_DATA *next;
};
int main(){
struct MY_DATA Obj_one ;
struct MY_DATA *RET;
Obj_one.Data_A = 123;
Obj_one.Data_B = 321;
Obj_one.Data_C = 987;
int *Data_B_ptr = &Obj_one.Data_B;
RET = container_of(Data_B_ptr, struct MY_DATA , Data_B );
puts("\n----------- index member = Data_B -----------");
printf("Obj_one's addr = %p\nRET addr = %p\n",&Obj_one , RET );
printf("RET->Data_A = %d\nRET->Data_B = %d\nRET->Data_C = %d\n",\
RET->Data_A, \
RET->Data_B, \
RET->Data_C);
}
```
godbolt: https://gcc.godbolt.org/z/Zx83G2
### linux kernel 內使用 container_of 的例子
[透過github search](https://github.com/torvalds/linux/search?l=C&q=container_of)
### 4.5 參考資料
[Linux的container_of 與 offsetof巨集](https://myao0730.blogspot.com/2016/09/linuxcontainerof-offsetof.html)
[The Magical container_of() Macro](https://radek.io/2012/11/10/magical-container_of-macro/)
### 5. 除了你熟悉的 add 和 delete 操作，`list.h` 還定義一系列操作，為什麼呢？這些有什麼益處？
* 主要的目的是為了提供 linked list 的 Linux Kernel API 。
* 在 list.h 中的各種操作都是只針對 linked list 本身而已，完全不影響資料的部份。
* 透過這種寫法，只要將 list_head 包含進 structure ，就可以讓它也能隨心所欲地放資料，同時又不用自己維護一套 doubly linked list 。
### 6.`LIST_POISONING` 這樣的設計有何意義？
* 當存取到 0x00100100/0x00200200 這兩個特別位址時會發生page fault。
* 用來標記那些沒有被初始化以及沒有在 linked list 內的 pointer ，讓它們不可被存取。
#### linked list 採用環狀是基於哪些考量？
* 可以讓head / tail 與其他 node 視為相同的一個點，不需要針對 head 做額外的處理。
#### `list_for_each_safe` 和 `list_for_each` 的差異在哪？"safe" 在執行時期的影響為何？
```C=1
/**
* 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`，可以避免在做itertion時指向已刪除節點的狀況。
以下摘錄 LDD3 page 299 的解釋
> If your loop may delete entries in the list, use this version. It simply stores the next entry in the list in next at the beginning of the loop, so it does not get confused if the entry pointed to by cursor is deleted.
#### for_each 風格的開發方式對程式開發者的影響為何？(提示：對照其他程式語言，如 Perl 和 Python)
* for_each 迴圈風格最大的特點在於沒有明顯的 counter ，基本上就是把集合中的所有元素都跑過一遍。
* python的 for each:
```python=1
fruits = ["apple", "banana", "cherry"]
for x in fruits:
print(x)
```
* 可以避免 [off-by-one error (OBOE)](https://en.wikipedia.org/wiki/Off-by-one_error) ，指的是執行迴圈時的邊界條件判斷寫錯，導致迴圈多跑或少跑一次。
#### 程式註解裡頭大量存在 `@` 符號，這有何意義？你能否應用在後續的程式開發呢？ (提示: 對照看 Doxygen)
`@` 是用來註解 function 的輸入參數以及輸出，做詳細的介紹以及如何使用 : [Source](http://www.doxygen.org/manual/docblocks.html)
>For functions one can use the @param command to document the parameters and then use [in], [out], [in,out] to document the direction.
使用 doxygen 的幾個好處
* 讓程式碼的註解有統一格式，方便閱讀
* 使用 doxygen 掃描程式碼產生 web 格式的說明文件以及 function / source code 之間的關聯圖( class hierarchy )，省去另外寫文件的時間
#### `tests/` 目錄底下的 unit test 的作用為何？就軟體工程來說的精神為何？
設計 test case 用來測試每一個單一功能（ 例如`list_add` / `list_add_tail` / `list_del` / ... ） 是否正確實作。
在軟體工程的角度，unit test 是整個測試流程的最小單元，也是測試的最基本步驟。
[Source](http://softwaretestingfundamentals.com/unit-testing/)
* unit test：測試對象為單一函式。
* integration test：測試對象為數個單元函式的複合體。我沒特別區分這個和 unit test [*1]，以下兩者一起用 unit test 表示。
* system test：測試整個系統。
* acceptance test：客戶驗收用的測試。將使用情節或使用需求轉成 acceptance test，藉以確認產品滿足客戶要求
以下摘錄 [為什麼要寫 unit test？為什麼要先寫測試？](https://fcamel-fc.blogspot.com/2009/06/unit-test.html)
> 為什麼要寫 unit test？
> 首先，unit test 著眼點比 system test 小，也意味著當測試結果不對時，unit test 可以指出更明確的問題點，而 system test 只能粗略地和我們說輸出不對，接著我們得比對正確和錯誤的輸出，開始推測 bug 在那，並用 debugger 設中斷，或在程式內輸出訊息一步步找出問題源頭。相信大家都能明白除錯的痛苦。而 unit test 可以協助我們釐清那些程式是對的，那些是錯的，將問題範圍縮小。若 unit test 寫得好，幾乎用不到 debugger 和輸出訊息，光看那個 unit test 錯誤，就知道 bug 在那。
> 除了幫自己省時間外，unit test 也可幫助別人維護和理解程式。維護的人不如自己熟悉，難免不小心改爛程式，unit test 可以減少這類問題，也讓原作者安心給其他人修改。新手要閱讀程式時，unit test 可看成是各函式的使用範例，相信大家都同意讀例子比讀全部程式碼來得容易吧。好的範例有時比註解還有用。
#### `tests/` 目錄的 unit test 可如何持續精進和改善呢？
可以針對邊界條件 boundary condition 做一些測試，看是否會發生 fail 的情況。
## 改寫 Homework 1
### 改寫目標
* 學習 linux-list 裡頭的技巧與 unit test 的設計
* 改寫為 doubly-linked list 且考慮到 circular
* `qtest` 也需要修改至可支援
---
### `queue.h`
* 資料結構調整
* 增加 `list_head` 來作為 doubly-linked list 的主要部分，包含 `next` 與 `prev` 指標。
* 將原本 `list_ele_t` 的 `next` 指標改為 `list_head` 。
* 將原本 `queue_t` 內 `list_ele_t` 的 `head` 與 `tail` 指標移除，改為 `list_head` 。
* 結構如下圖 :
* 透過 linux-kernel 風格的 linked list 可以不用再特別處理 head 或 tail 指標，因為大家都是相同的。
```clike=
struct list_head {
struct list_head *prev;
struct list_head *next;
};
typedef struct ELE {
char *value;
struct list_head list;
} list_ele_t;
typedef struct {
size_t size; // size of the linked list
struct list_head head; /* Doubly Linked list of elements */
} queue_t;
```
* 新增 macro
* 為了能夠從 `list_head` 找到 `list_ele_t` 的 entry ，所以增加 `container_of` 巨集。
* 增加 `list_for_each_safe` 巨集來尋訪 linked list 。
```clike=
#define container_of(ptr, type, member) \
__extension__({ \
const __typeof__(((type *) 0)->member) *__pmember = (ptr); \
(type *) ((char *) __pmember - offsetof(type, member)); \
})
#define list_for_each_safe(node, safe, head) \
for (node = (head)->next, safe = node->next; node != (head); \
node = safe, safe = node->next)
```
* 新增 linked list 的操作函式，源自於 [linux-list](https://github.com/sysprog21/linux-list) 的 `list.h`
```clike=
static inline void list_add(struct list_head *node, struct list_head *entry)
{
struct list_head *next = entry->next;
next->prev = node;
node->next = next;
node->prev = entry;
entry->next = node;
}
static inline void list_add_tail(struct list_head *node, struct list_head *head)
{
struct list_head *prev = head->prev;
prev->next = node;
node->next = head;
node->prev = prev;
head->prev = node;
}
static inline void list_del(struct list_head *node)
{
struct list_head *next = node->next;
struct list_head *prev = node->prev;
next->prev = prev;
prev->next = next;
}
static inline void INIT_LIST_HEAD(struct list_head *head)
{
head->next = head;
head->prev = head;
}
```
---
### `queue.c`
* `q_new()`
* 新增初始化 `list_head` ，使得 `next` 與 `prev` 都指向自己的 `list_head` 。
```clike=
queue_t *q_new()
{
queue_t *q = malloc(sizeof(queue_t));
if (q == NULL)
return NULL;
INIT_LIST_HEAD(&q->head);
q->size = 0;
return q;
}
```
* `q_free()`
* 透過 `list_for_each_safe` 尋訪各個 `list_head` 並處理好要刪除節點的指標。
* 再使用 `container_of` 來取得 `list_ele_t` 的 entry 並釋放其記憶體。
```clike=
void q_free(queue_t *q)
{
if (q != NULL) {
struct list_head *li = NULL, *lis = NULL;
list_ele_t *rm_node;
list_for_each_safe(li, lis, &q->head)
{
list_del(li);
rm_node = container_of(li, list_ele_t, list);
free(rm_node);
}
free(q);
}
}
```
* `q_insert_head()`
* 產生新的 `list_ele_t * newh` ，並初始化其 `list_head` 。
* 從 `q` 內的 `list_head head` 的 next 插入。
* 示意圖，此為 circular 只是沒畫出指標。
```clike=
bool q_insert_head(queue_t *q, char *s)
{
list_ele_t *newh;
if (q != NULL) {
newh = malloc(sizeof(list_ele_t));
if (newh != NULL) {
newh->value = strdup(s);
INIT_LIST_HEAD(&newh->list);
list_add(&newh->list, &q->head);
q->size++;
return true;
}
}
return false;
}
```
* `q_insert_tail()`
* 原理和 `q_insert_head` 相同，只差在是由 prev 那端插入。
* 示意圖，此為 circular 只是沒畫出指標。
```clike=
bool q_insert_tail(queue_t *q, char *s)
{
list_ele_t *newh;
if (q != NULL) {
newh = malloc(sizeof(list_ele_t));
if (newh != NULL) {
newh->value = strdup(s);
INIT_LIST_HEAD(&newh->list);
list_add_tail(&newh->list, &q->head);
q->size++;
return true;
}
}
return false;
}
```
* `q_remove_head()`
* 所要刪除的節點位於 `q` 的下個節點。
* 使用 `container_of` 後得到刪除節點的 entry ，並在 `list_del` 刪除它。
* 最後在釋放其記憶體。
* 在刪除之後， `queue_t` 的 next 與 prev 指標會指向自己的 `list_head` 。
```clike=
bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
if (q != NULL) {
if (q->head.next != &q->head) {
list_ele_t *rm_node = container_of(q->head.next, list_ele_t, list);
if (sp != NULL) {
memcpy(sp, rm_node->value,
bufsize); // copy the removed string to sp
sp[bufsize - 1] = '\0'; // add terminator at the end
}
list_del(q->head.next);
free(rm_node); // free the removed node
q->size--;
return true;
}
}
return false;
}
```
* `q_reverse()`
* 使用 `list_for_each_safe` 尋訪每個節點，並將其 next 與 prev 指標對調。
* `list_for_each_safe` 的 `head` 不會走訪到，因為判斷式 `node != (head)` 會在走回 `head` 時跳出迴圈。
```clike
#define list_for_each_safe(node, safe, head) \
for (node = (head)->next, safe = node->next; node != (head); \
node = safe, safe = node->next)
```
* 所以還需要做最後一次指標對調才得以完成反轉佇列。
```clike=
void q_reverse(queue_t *q)
{
if (q != NULL) {
struct list_head *li = NULL, *lis = NULL, *tmp = NULL;
list_for_each_safe(li, lis, &q->head)
{
tmp = li->next;
li->next = li->prev;
li->prev = tmp;
}
tmp = li->next;
li->next = li->prev;
li->prev = tmp;
}
```
---
### `qtest.c`
* 原本的 `qtest.c` 可以直接透過 `list_ele_t` 來獲得 value 。
* 但是由於修改為 doubly-linked list ， 鏈接的部分不再是 `list_ele_t` 而是 `list_head` 。
* 這也是大部分 `qtest.c` 需要修改的部分，以 `show_queue()` 下要印出 queue 內容的部分為例。
* 修改前 : (透過走訪 `list_ele_t` 來印出 value )
```clike=
list_ele_t *e = q->head;
if (exception_setup(true)) {
while (ok && e && cnt < qcnt) {
if (cnt < big_queue_size)
report_noreturn(vlevel, cnt == 0 ? "%s" : " %s", e->value);
e = e->next;
cnt++;
ok = ok && !error_check();
}
}
```
* 需要先使用 `container_of` 來得知 `list_ele_t` 的 entry 位址才能取得其 value 。
* 修改後 : (透過 `list_head` 來走訪，使用 `container_of` 來取得 entry )
```clike=
struct list_head *e = &q->head;
if (exception_setup(true)) {
list_ele_t *ent;
while (ok && cnt < qcnt) {
e = e->next;
ent = container_of(e, list_ele_t, list);
if (cnt < big_queue_size)
report_noreturn(vlevel, cnt == 0 ? "%s" : " %s", ent->value);
cnt++;
ok = ok && !error_check();
}
}
```
* 其中的 while 迴圈內 `ok && e && cnt < qcnt` 判斷式改為 `ok && cnt < qcnt` ，原因是在 circular 的結構下， `list_head * e` 只可能會指回自己，不可能指向 `NULL` 。
* 在原 `show_queue()` 的 447 行，將 `if (e == NULL) ... else` 拿掉，原因是 `e` 在 circular 的結構下是不會為 `NULL` 的，若不移除，一定會進入 else 而產生 ERROR 。
```clike=447
if (e == NULL) {
if (cnt <= big_queue_size)
report(vlevel, "]");
else
report(vlevel, " ... ]");
} else {
report(vlevel, " ... ]");
report(
vlevel,
"ERROR: Either list has cycle, or queue has more than %d elements",
qcnt);
ok = false;
}
```
---
### 結果
* `make test` 也可以達到 ==100/100==
* 但是相較於原本的 `lab0-c` 除了程式碼更加精簡外，效率不進反退，也可能是我實作的問題 :confused:
* `lab0-c` 的 `perf stat ./scripts/driver.py`
```
Performance counter stats for './scripts/driver.py':
514.600727 task-clock (msec) # 1.001 CPUs utilized
33 context-switches # 0.064 K/sec
0 cpu-migrations # 0.000 K/sec
99,410 page-faults # 0.193 M/sec
1,835,221,189 cycles # 3.566 GHz
4,152,494,737 instructions # 2.26 insn per cycle
803,315,987 branches # 1561.047 M/sec
1,004,655 branch-misses # 0.13% of all branches
0.513896153 seconds time elapsed
```
* `lab-list` 的 `perf stat ./scripts/driver.py`
```
Performance counter stats for './scripts/driver.py':
574.978929 task-clock (msec) # 1.001 CPUs utilized
39 context-switches # 0.068 K/sec
8 cpu-migrations # 0.014 K/sec
115,044 page-faults # 0.200 M/sec
2,110,763,505 cycles # 3.671 GHz
4,498,759,005 instructions # 2.13 insn per cycle
831,566,851 branches # 1446.256 M/sec
1,089,808 branch-misses # 0.13% of all branches
0.574192893 seconds time elapsed
```
## 參考資料
[How does the kernel implements Linked Lists?](https://kernelnewbies.org/FAQ/LinkedLists)
[List head 研究](https://myao0730.blogspot.com/2016/12/linux.html)
[Container of](https://myao0730.blogspot.com/2016/09/linuxcontainerof-offsetof.html)
[2018 Spring - rex662624 共筆](https://hackmd.io/s/S1GRtsEiM)
Sign in with Wallet
Connect another wallet