tags: `linux2019`

2019q1 Homework1 (list)

contributed by < ambersun1234 >

環境

$ uname -a
Linux 4.15.0-45-generic #48~16.04.1-Ubuntu SMP Tue Jan 29 18:03:48 UTC 2019 x86_64 x86_64 x86_64 GNU/Linux
$ gcc -v
gcc version 5.4.0 20160609 (Ubuntu 5.4.0-6ubuntu1~16.04.11)

說明

作業說明

Sorting algorithm:

在 GitHub 上 fork linux-list 並學習裡頭的技巧，包含裡頭 unit test 的設計，透過給定的 linked list 操作，進而實作出 merge sort
- 附上你的修改過程，也需要讓 qtest 得以支援
- 可將 dict 裡頭的測試資料拿來作效能分析的輸入
- 思考提升排序效率的方法，需要做平均和最壞狀況的分析
排序演算法時間複雜度

Case Insertion sort Quick sort Merge sort

Average case \(O(n^2)\) \(O(nlogn)\) \(O(nlogn)\)

Worst case \(O(n^2)\) \(O(n^2)\) \(O(nlogn)\)

Average case 實驗
- make averagePlot
- 其實可以發現，quick sort 以及 merge sort 在 average case 的表現下並不會差太多
Worst case 實驗
- make worstPlot
- 值得一提的是，當我在跑 worst case 的測試時，會出現 segmentation fault。後來在追蹤時發現到是在 quick sort 60000 的時候發生；結果是因為 stack size 不夠大所導致，使用 ulimit -s 65536 更改 stack size 即可解決

Case	Insertion sort	Quick sort	Merge sort
Average case	\(O(n^2)\)	\(O(nlogn)\)	\(O(nlogn)\)
Worst case	\(O(n^2)\)	\(O(n^2)\)	\(O(nlogn)\)

自我檢查事項:

為何 Linux 採用 macro 來實作 linked list？一般的 function call 有何成本？

macro 是在編譯階段進行展開的，根據 man gcc 裡面的提到

-E Stop after the preprocessing stage;
do not run the compiler proper.
The output is in the form of preprocessed source code,
which is sent to the standard output.

在 compile 的時候加上 -E 這個參數即可以觀察到展開巨集之後的程式碼，就可以發現到說 macro 全部被展開到程式碼裡面( 我覺得是類似 find and replace )
function call 編譯完成後並不會像 macro 一樣全部展開到程式碼之中，而是在記憶體中實際佔有空間的。在演算中有學到 , 每次的 function call 都是要對 stack 進行 push pop 的，而這樣的操作是很耗時間的
綜合以上， macro 不會發生 function call 的 push pop 的操作，可以減少時間成本，但相對的，由於是展開巨集，所以會造成空間的浪費
那 linux 會採用 macro 實做 linked list 我想很大的原因是要避免 stack 的 push pop 造成多消耗時間

Linux 應用 linked list 在哪些場合？舉三個案例並附上對應程式碼，需要解說，以及揣摩對應的考量

GNU extension 的 typeof 有何作用？在程式碼中扮演什麼角色？

先上程式碼
```
#define max(a,b) \
({ __typeof__ (a) _a = (a); \
    __typeof__ (b) _b = (b); \
    _a > _b ? _a : _b; })
```
typeof 是 gnu c extension，它可以取得參數的型態，比如說
```
int a;
typeof(a) b;
```
則上述第二行會變成 int b;，typeof 會返回參數的類型，a 為 int 型態，因此 typeof(a) 會變成 int
上述 max 的 macro 即是可以針對各種型態的數字進行比較，傳回較大者，需要注意的是，實際上在用 typeof 的時候必須要寫成 __typeof__ 才可以編譯成功

解釋以下巨集的原理

#define container_of(ptr, type, member)                            \
    __extension__({                                                \
        const __typeof__(((type *) 0)->member) *__pmember = (ptr); \
        (type *) ((char *) __pmember - offsetof(type, member));    \
    })

在解釋 container_of 之前必須要先看 offsetof

offsetof macro

#define offsetof(TYPE, MEMBER) ((size_t)&((TYPE *)0)->MEMBER)

offsetof 的 macro 是定義在 include/linux/stddef.h 中，其功用為計算 struct 成員在 struct 中的偏移量。

在 offsetof 的 macro 中，它會把 0 強制轉型至 TYPE 指標型態，以此為 TYPE 的起始位置，得到 MEMBER 的位置，由於 0 視為該 TYPE 的起點，因此就會得到 MEMBER 在 TYPE 中的偏移量。考慮以下程式碼:



















#include <stdio.h>

#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)

typedef struct mdata {
    int a, b, c;
    char *hello; 
    struct mdata *next;
} data;

int main() {
    printf("-- a = %d --\n", offsetof(data, a));
    printf("-- b = %d --\n", offsetof(data, b));
    printf("-- c = %d --\n", offsetof(data, c));
    printf("-- hello = %d --\n", offsetof(data, hello));
    printf("-- next = %d --\n", offsetof(data, next));

    return 0;
}

其輸出結果為





-- a = 0 --
-- b = 4 --
-- c = 8 --
-- hello = 16 --
-- next = 24 --

a 的偏移量是 0，因為他是該 TYPE 的起點，b 跟 c 的偏移量分別是 4, 8(int 大小為 4 byte)，hello 的偏移量為 16(char * 的大小為 8 byte, 位置 12 無法被 8 整除，所以要新增 padding 變成 16)

struct alignment

回到 container_of

reference container_of
```
#define container_of(ptr, type, member)                            \
    __extension__({                                                \
        const __typeof__(((type *) 0)->member) *__pmember = (ptr); \
        (type *) ((char *) __pmember - offsetof(type, member));    \
    })
```
- __extension__
  
  GCC uses the extension attribute when using the -ansi flag to avoid warnings in headers with GCC extensions. This is mostly used in glibc with function declartions using long long
- 它宣告了一個型態為 ((type *)0)->member 的指標變數 __pmember 並將 ptr 指派給 __pmember
- 再將 __pmember 扣掉 member 的偏移量，即可得到該 TYPE 的位置

除了你熟悉的 add 和 delete 操作，`list.h` 還定義一系列操作，為什麼呢？這些有什麼益處？

linux/list.h
多人開發時，為避免重造輪子，於是團隊開發出一系列 API 提供團隊自己使用。

`LIST_POISONING` 這樣的設計有何意義？

LIST_POISONING 一系列定義於 linux/poison.h 中。該檔案定義了許多的 magic number ，這些 magic number 被用在許多的地方 e.g. mm, arch, drivers, kernel 等。我有找到一篇 what is the meaning of 0xdead000000000000? 是在探討這些 magic number 的設計考量點。
對於非法的 linked list 節點，一般的作法是將其設為 NULL；在龐大的系統中，一定不只有一個 linked list，如果要對其進行除錯的時候，會變得相對困難，因為全部都是 NULL；而有了 LIST_POISONING，可以很快速的辨別是哪裡出錯

linked list 採用環狀是基於哪些考量？

circular linked list 在結構上是屬於環狀的，也就是說它沒有一個特定的頭尾，相比 singly 或 doubly linked list，circular 的結構較為單純；在實做上，可以不用考慮一些 corner case 比如刪掉頭或刪掉尾巴，circular 僅須考慮 linked list 是否沒有連接上的問題

什麼情境會需要對 linked list 做排序呢？舉出真實世界的應用，最好在作業系統核心出現

作業系統實做上一定會面臨到排程問題，電腦上的任務也會時常進行刪減，所以是以 linked list 進行實做；排程工作又會面臨到執行先後順序的問題，因此排程也會需要進行排序的工作

什麼情境會需要需要找到第 k 大/小元素呢？又，你打算如何實作？

`list_for_each_safe` 和 `list_for_each` 的差異在哪？"safe" 在執行時期的影響為何？



#define list_for_each_safe(node, safe, head)                     \
    for (node = (head)->next, safe = node->next; node != (head); \
         node = safe, safe = node->next)

safe 的版本相較於普通的 for_each 來說，最大的不同就是增加一個變數 safe，去紀錄當前 node 的下一個。直播中有提到，如果 head 不見了，那麼就會出錯，由於 linux kernel 的 linked list 是屬於 circular ，當 head 在執行的時候被刪除了，safe 這個變數可以先將 head 的下一個保存起來，確保執行順利

reference 你所不知道的 C 語言：linked list 和非連續記憶體操作 1:19:00

for_each 風格的開發方式對程式開發者的影響為何？

提示：對照其他程式語言，如 Perl 和 Python
- 一般而言，如果要針對特定資料型態(e.g. binary tree，linked list)進行走訪，在程式上就必須要了解資料底層如何實做，才能寫出走訪。
- 在一些程式語言，如 python, c++ 都有提供 foreach 可以使用。對於特殊資料型態，都不需要對走訪的程式碼進行變動，很大的一個原因是他們都是 ADT(Abstract Data Type, 抽象資料型態)；我們可以不用考慮資料底層的實做方式，進而實現資料封裝。

程式註解裡頭大量存在 `@` 符號，這有何意義？你能否應用在後續的程式開發呢？

提示: 對照看 Doxygen
Doxygen 是一個可以將程式裡的特定註解轉換成 Document 的產生工具
@ 是告訴 Doxygen 說這一行要轉換成為 Document，比方說
- @param a description
- @param b description
- @return return a + b
在開發的過程中可以將註解與開發文件整合，我覺得是一個不錯的功能，在未來的開發過程中，我會試著將這一個工具實際應用在專案上面

Doxygen 簡介 reference

`tests/` 目錄底下的 unit test 的作用為何？就軟體工程來說的精神為何？

unit test , 單元測試。測試是為軟體工程中相當重要的一個環節，它可以確保程式的行為是符合預期的，確保程式碼的品質。單元測試是針對程式中的最小單元，也就是 function 進行測試，通過了單元測試即表示該 function 的行為是合理的。
實務上軟體開發，每天都會收到各種的更新提交，程式碼的把關是每個團隊需要面對的事情，現在已經有很多服務可以整合測試這件事情，像是 travis-ci 與 jenkins 都有與 github 進行整合，在 push 之後立刻啟動相關測試，如此一來，可以節省許多在驗證程式碼的人力的這個部份

Syntax	Example	Reference
# Header	Header	基本排版
- Unordered List	Unordered List
1. Ordered List	Ordered List
- [ ] Todo List	Todo List
> Blockquote	Blockquote
Bold font	Bold font
Italics font	Italics font
~~Strikethrough~~	~~Strikethrough~~
19^th^	19^th
H~2~O	H₂O
++Inserted text++	Inserted text
==Marked text==	Marked text
[link text](https:// "title")	Link
![image alt](https:// "title")	Image
`Code`	`Code`	在筆記中貼入程式碼
```javascript var i = 0; ```	`var i = 0;`	在筆記中貼入程式碼
:smile:		Emoji list
{%youtube youtube_id %}	Externals
$L^aT_eX$	L^aT_eX
:::info This is a alert area. :::	This is a alert area.

tags: linux2019

2019q1 Homework1 (list)

環境

說明

Sorting algorithm:

Average case 實驗

Worst case 實驗

自我檢查事項:

為何 Linux 採用 macro 來實作 linked list？一般的 function call 有何成本？

Linux 應用 linked list 在哪些場合？舉三個案例並附上對應程式碼，需要解說，以及揣摩對應的考量

GNU extension 的 typeof 有何作用？在程式碼中扮演什麼角色？

解釋以下巨集的原理

除了你熟悉的 add 和 delete 操作，list.h 還定義一系列操作，為什麼呢？這些有什麼益處？

LIST_POISONING 這樣的設計有何意義？

linked list 採用環狀是基於哪些考量？

什麼情境會需要對 linked list 做排序呢？舉出真實世界的應用，最好在作業系統核心出現

什麼情境會需要需要找到 第 k 大/小元素 呢？又，你打算如何實作？

list_for_each_safe 和 list_for_each 的差異在哪？"safe" 在執行時期的影響為何？

for_each 風格的開發方式對程式開發者的影響為何？

程式註解裡頭大量存在 @ 符號，這有何意義？你能否應用在後續的程式開發呢？

tests/ 目錄底下的 unit test 的作用為何？就軟體工程來說的精神為何？

tests/ 目錄的 unit test 可如何持續精進和改善呢？