# 2019q1 Homework1 (list)
contributed by < `jeffcarl67` >
## 作業要求
* 回答上述「Linux 風格的 linked list」裡頭「自我檢查清單」的所有問題，需要附上對應的參考資料和必要的程式碼
* 從 linux-list 學習裡頭的技巧，包含裡頭 unit test 的設計，透過給定的 linked list 操作，實作出 merge sort
* 附上你的修改過程，也需要讓 qtest 得以支援
* 可將 dict 裡頭的測試資料拿來作效能分析的輸入
* 思考提升排序效率的方法，需要做平均和最壞狀況的分析
## 環境
```
Linux 4.15.0-45-generic #48~16.04.1-Ubuntu SMP
gcc (Ubuntu 5.4.0-6ubuntu1~16.04.11) 5.4.0 20160609
```
## 自我檢查事項:
* **為何 Linux 採用 macro 來實作 linked list？一般的 function call 有何成本？**
function call 有入棧及出棧操作, 會消耗更多時間, 此處以一個取得兩數中較小數的程式來比較使用 macro 與 function 在 assembly code 層面的差異
* min_macro.c
```clike
#define min(a, b) (a < b ? a : b)
int main()
{
min(3, 4);
return 0;
}
```
* min_func.c
```clike
int min(int a, int b)
{
return a < b ? a : b;
}
int main()
{
min(3, 4);
return 0;
}
```
:::danger
設計實驗時，需要特別標注你用的軟體版本和用法，例如 gcc 版本和最佳化選項
:notes: jserv
:::
使用 ``gcc min_macro.c -o min_macro`` 與 ``gcc min_func.c -o min_func`` 命令編譯再用 ``objdump -d`` 命令反組譯後可得以下結果
* min_macro
```
00000000004004d6 <main>:
4004d6: 55 push %rbp
4004d7: 48 89 e5 mov %rsp,%rbp
4004da: b8 00 00 00 00 mov $0x0,%eax
4004df: 5d pop %rbp
4004e0: c3 retq
4004e1: 66 2e 0f 1f 84 00 00 nopw %cs:0x0(%rax,%rax,1)
4004e8: 00 00 00
4004eb: 0f 1f 44 00 00 nopl 0x0(%rax,%rax,1)
```
* min_func
```
00000000004004d6 <min>:
4004d6: 55 push %rbp
4004d7: 48 89 e5 mov %rsp,%rbp
4004da: 89 7d fc mov %edi,-0x4(%rbp)
4004dd: 89 75 f8 mov %esi,-0x8(%rbp)
4004e0: 8b 45 fc mov -0x4(%rbp),%eax
4004e3: 39 45 f8 cmp %eax,-0x8(%rbp)
4004e6: 0f 4e 45 f8 cmovle -0x8(%rbp),%eax
4004ea: 5d pop %rbp
4004eb: c3 retq
00000000004004ec <main>:
4004ec: 55 push %rbp
4004ed: 48 89 e5 mov %rsp,%rbp
4004f0: be 04 00 00 00 mov $0x4,%esi
4004f5: bf 03 00 00 00 mov $0x3,%edi
4004fa: e8 d7 ff ff ff callq 4004d6 <min>
4004ff: b8 00 00 00 00 mov $0x0,%eax
400504: 5d pop %rbp
400505: c3 retq
400506: 66 2e 0f 1f 84 00 00 nopw %cs:0x0(%rax,%rax,1)
40050d: 00 00 00
```
比較後可知在預設最佳化的情況下, 使用 function call 的版本由於必須保存每一個 frame 中的執行環境, 應此會有更多指令
* **Linux 應用 linked list 在哪些場合？舉三個案例並附上對應程式碼，需要解說，以及揣摩對應的考量**
* 在 linux 中, 有許多時候申請到的記憶體小於一個 page, 在這種狀況下頻繁的申請 memory page 會對性能產生重大影響, 因此 linux 使用 kmem_cache 與 slab 對小塊記憶體進行管理, 其中就使用 linked list 來管理 kmem_cache, 可以看到 kmem_cache 的定義
* /mm/slab.h
```c=
struct kmem_cache {
unsigned int object_size;/* The original size of the object */
unsigned int size; /* The aligned/padded/added on size */
unsigned int align; /* Alignment as calculated */
slab_flags_t flags; /* Active flags on the slab */
unsigned int useroffset;/* Usercopy region offset */
unsigned int usersize; /* Usercopy region size */
const char *name; /* Slab name for sysfs */
int refcount; /* Use counter */
void (*ctor)(void *); /* Called on object slot creation */
struct list_head list; /* List of all slab caches on the system */
};
```
參考資料
> https://blog.csdn.net/YuZhiHui_No1/article/details/47305361
* 在 netlabel 子系統中, 也使用 linked list 管理所有的地址
* /net/netlabel/netlabel_addrlist.h
```
struct netlbl_af4list {
__be32 addr;
__be32 mask;
u32 valid;
struct list_head list;
};
```
參考資料
> https://blog.51cto.com/weiguozhihui/1579800
* **GNU extension 的 [typeof](https://gcc.gnu.org/onlinedocs/gcc/Typeof.html) 有何作用？在程式碼中扮演什麼角色？**
c 語言本身並未提供在執行期或編譯期獲取變量類型的方法, 藉由 gcc 的擴展, 使用 typeof 能在編譯時期取得變量的類型, 使程式撰寫變得更靈活, 此外也能用於類型檢查, 例如在 linux 中有以下程式碼用於在編譯時進行類型檢查：
* include/linux/typecheck.h
```c=
#define typecheck(type,x) \
({ type __dummy; \
typeof(x) __dummy2; \
(void)(&__dummy == &__dummy2); \
1; \
})
```
使用以下程式進行驗證
```c=
#define typecheck(type,x) \
({ type __dummy; \
typeof(x) __dummy2; \
(void)(&__dummy == &__dummy2); \
1; \
})
int main()
{
unsigned int a;
typecheck(int, a);
return 0;
}
```
在編譯時由於類型不相同, 編譯器給出如下警告
```
warning: comparison of distinct pointer types lacks a cast
(void)(&__dummy == &__dummy2); \
^
```
資料參考
> http://deltamaster.is-programmer.com/posts/37253.html
* **解釋以下巨集的原理**
```Clike
#define container_of(ptr, type, member) \
__extension__({ \
const __typeof__(((type *) 0)->member) *__pmember = (ptr); \
(type *) ((char *) __pmember - offsetof(type, member)); \
})
```
第一行語句 ``const __typeof__(((type *) 0)->member) *__pmember = (ptr);`` 會宣告一個指針指向成員變量的地址, 第二行 ``(type *) ((char *) __pmember - offsetof(type, member)); \``將成完變量的地址減去相對於結構開頭的偏移而得到結構的起始位址, 以下是用於驗證的程式
```clike
#include <stddef.h>
#include <assert.h>
#define container_of(ptr, type, member) \
__extension__({ \
const __typeof__(((type *) 0)->member) *__pmember = (ptr); \
(type *) ((char *) __pmember - offsetof(type, member)); \
})
struct test {
int a, b, c;
};
int main()
{
struct test t1;
assert(&t1 == container_of(&t1.b, struct test, b));
return 0;
}
```
資料參考
> https://myao0730.blogspot.com/2016/09/linuxcontainerof-offsetof.html
* **除了你熟悉的 add 和 delete 操作，`list.h` 還定義一系列操作，為什麼呢？這些有什麼益處？**
有些操做是為了讓程式碼協作時更加安全, 例如 ``list_entry`` 系列函數, 其中提供了取得結構體位址的方式, 若每個開發者都自行使用顯示型態轉換去取得結構位址, 則相較之下更容易出錯。而 ``list_for_each`` 系列函數提供給程式開發者更多的抽象, 使開發者能將精力集中於對每個元素的操作上。有些則提供對兩個 linked list 間的操作, 例如 ``list_splice`` 及 ``list_cut_position`` 等。有些定是則看起來只為提高可讀性, 例如 ``list_empty`` ``list_is_singular`` 等
* **`LIST_POISONING` 這樣的設計有何意義？**
閱讀完相關程式碼使註解後可知, 在使用完 list_delete 函式後, 記憶體區塊只是被移出了 linked list 而還沒有釋放, 使用 ``LIST_POISONING`` 將被移除的元素的前驅與後繼節點設為非法的記憶體區域, 防止已被移除的節點在被用來執行 linked list 相關操作
```clike
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;
#ifdef LIST_POISONING
node->prev = (struct list_head *) (0x00100100);
node->next = (struct list_head *) (0x00200200);
#endif
}
```
* **linked list 採用環狀是基於哪些考量？**
當須要不停的循環使用 linked list 中的元素時, 例如在 process 的調度中, 若採用 single linked list 則每當到達尾端要從頭開始時, 會需要額外的條件判斷
* **什麼情境會需要對 linked list 做排序呢？舉出真實世界的應用，最好在作業系統核心出現**
硬碟是一種 block device, 由於磁頭的旋轉使得訪問不同的磁道會需要不同的時間, 為了盡量加速硬碟讀寫過程, linux 實現了不同的 IO scheduler, 每一種不同的 scheduler 都會對應盤讀寫請求按照特定算法進行排序
* **什麼情境會需要需要找到 [第 k 大/小元素](https://www.geeksforgeeks.org/kth-smallestlargest-element-unsorted-array/) 呢？又，你打算如何實作？**
最簡單的實作方式為先用任ㄧ排序演算法對 linked list 排序, 之後再取出其中第 k 個元素。
或只可以使用 min heap 與 max heap, 在 heapify 後連續取出根節點 k 次即為所求
* **`list_for_each_safe` 和 `list_for_each` 的差異在哪？"safe" 在執行時期的影響為何？**
先比較二者的程式碼
```c=
#define list_for_each(node, head) \
for (node = (head)->next; node != (head); node = node->next)
```
```c=
#define list_for_each_safe(node, safe, head) \
for (node = (head)->next, safe = node->next; node != (head); \
node = safe, safe = node->next)
```
可以發現在 ``list_for_each_safe`` 中在每次對元素進行操作前都會先保存下一個元素的位址, 因此如果改變了元素的後繼節點並不會使後續的元素走訪出現問題, 迴圈能夠正常執行
* **for_each 風格的開發方式對程式開發者的影響為何？**
* 提示：對照其他程式語言，如 Perl 和 Python
如果想對一組資料進行操作, 在 perl 中可以用 ``foreach my $i (@array)`` 而在 python 中可以用 ``for i in array: ``, 使用這種風格的程式碼不僅易於閱讀也能夠不再關注每次迴圈如何變化, 可以將注意力放在要對其中元素執行的操作上
* **程式註解裡頭大量存在 `@` 符號，這有何意義？你能否應用在後續的程式開發呢？**
* 提示: 對照看 Doxygen
Doxygen 可將程式碼中的註解抽取出來生成文檔, 在 ``list.h`` 中利用 @ 標注函式參數
* **`tests/` 目錄底下的 unit test 的作用為何？就軟體工程來說的精神為何？**
對單ㄧ功能進行測試, 可防止遇到複雜的程式碼時出錯後難以定位發生問題的位置
* **`tests/` 目錄的 unit test 可如何持續精進和改善呢？**
當測試樣例眾多時, 可以考慮開發單元測試框架例如 ``Googletest`` 或 ``Check``, 且單純使用 assert 驗證有時提供的資訊較少, 可以考慮借鑒 ``qtest`` 對記憶體的使用也進行跟蹤
## merge sort
* 實作
在實作 merge sort 的過程中使用了三個函數, 分別為 ``splice`` ``split`` ``list_mergesort``
* splice : 用於將兩個已排序過的 linked list 合併並排序
* split : 將一個 linked list 分成兩個元素數量最多相差 1 的 linked list
* list_mergesort : 先用函式 split 將給定的 linked list 分割為兩個, 在對兩個子 linked list 分別用函式 list_mergesort, 當 list_mergesort返回時代表兩個子 linked list 都已排序完成, 再用函式 splice 合併兩個子 linked list 即得所求
```c=
static void splice(struct list_head *head,
struct list_head *front,
struct list_head *back)
{
while (1) {
struct listitem *a = list_first_entry(front, struct listitem, list);
struct listitem *b = list_first_entry(back, struct listitem, list);
if (list_empty(front)) {
list_splice_tail(back, head);
break;
}
if (list_empty(back)) {
list_splice_tail(front, head);
break;
}
if (a->i <= b->i) {
list_del(&a->list);
list_add_tail(&a->list, head);
} else {
list_del(&b->list);
list_add_tail(&b->list, head);
}
}
}
static void split(struct list_head *src,
struct list_head *front,
struct list_head *back)
{
struct list_head *onestep, *twostep;
onestep = src->next;
twostep = src->next->next;
while (twostep != src) {
twostep = twostep->next;
if (twostep != src) {
onestep = onestep->next;
twostep = twostep->next;
}
}
list_cut_position(front, src, onestep);
list_cut_position(back, src, src->prev);
}
static void list_mergesort(struct list_head *head)
{
struct list_head front, back;
INIT_LIST_HEAD(&front);
INIT_LIST_HEAD(&back);
if (list_empty(head) || list_is_singular(head))
return;
split(head, &front, &back);
list_mergesort(&front);
list_mergesort(&back);
splice(head, &front, &back);
}
```
資料參考
> https://www.geeksforgeeks.org/merge-sort-for-linked-list/
Sign in with Wallet
Connect another wallet