---
# System prepended metadata

title: 2018q1 Homework3 (list)
tags: [NCKU, Linux, rwe0214]

---

2018q1 Homework3 (list)
===
contributed by <`rwe0214`>
###### tags: `Linux`, `rwe0214`, `NCKU`
## 作業說明
* [D05: list](https://hackmd.io/s/HkxZbJzif#)

## 生日悖論
### 如何透過近似的運算式，估算上述機率計算呢？附上有效的 LaTeX 算式
* 假設 1 年有 365 天
* n 個人生日不重複的事件為 $C_{n}^{365} \times\ n!$
* 樣本數為 $365^{n}$
* 機率 $p$ 為 $\dfrac{C_{n}^{365} \times\ n!}{365^{n}}$
* 則 n 個人生日重複的機率 $p'$ 為 $1-\dfrac{C_{n}^{365} \times\ n!}{365^{n}}$
    * $C_{n}^{365}$ 怎麼計算？
* 將 $p$ 展開可得 $\frac{365}{365} \times \frac{364}{365} \times \frac{363}{365} \times\ ... \times\ \frac{365-n+1}{365}= 1 \times (1 - \frac{1}{365}) \times (1 - \frac{2}{365}) \times (1 - \frac{3}{365}) \times\ ...\times\ (1 - \frac{n-1}{365})$
    * 引入泰勒級數且因為 $x<<1$，所以 $e^{x} ≈ 1 - x$
    * 原式變成 $1 \times e^{\frac{-1}{365}} \times e^{\frac{-2}{365}} \times e^{\frac{-3}{365}} \times\ ...\times\ e^{\frac{-n}{365}} = e^\frac {-n(n-1)/2}{365} = e^\frac {-n(n-1)}{730}$ 
    * $p' = 1 - e^\frac {-n(n-1)}{730}$
* 將 n = 22 代入 $p' ≈ 1 - e^\frac {-462}{730} = 1 - e^\frac {-231}{365} = 1 - e^{-0.6328} ≈ 1 - 0.531 = 0.469$
* 將 n = 23 代入 $p' ≈ 1 - e^\frac {-506}{730} = 1 - e^\frac {-253}{365} = 1 - e^{-0.69315} ≈ 1 - 0.4999 = 0.5001$，機率為 $50.01％$

### [Birthday problem](https://en.wikipedia.org/wiki/Birthday_problem) 對資訊安全的影響在哪些層面
* [生日攻擊](http://blog.renren.com/share/250153535/16381267487/0) 即利用在 hash function 中的 collision 現象做攻擊。
* 一個設計良好的 hash function 不容易利用 hash value 反推回原本的明文 $t_1$，但是若是這個 hash value $h(t_1)$ 的 bit 數不夠多（ 即值域不夠大 ），那麼我們可以透過生日悖論的想法，去枚舉找到另一份明文 $t_2$ 其 $h(t_2) = h(t_1)$
* 也許枚舉這個動作聽來不怎麼可怕，但是將生日悖論求得的數學式代入會發現 
    * $p = e^\frac {-m(m-1)/2}{2^n} ≈ e^\frac {m^2}{2^n}$
    * $p' ≈ 1 - e^\frac {m^2}{2^n}$
    * 若 $p' > 0.5$ 則 $m ≈ 2^{n/2}$
    * 換句話說，我只需要枚舉 $2^{n/2}$ 的 $t_2$ 就有超過一半的機率使得 $h(t_2) = h(t_1)$
### 像是 [Random Number Generator](http://stattrek.com/statistics/random-number-generator.aspx) 這樣的產生器，是否能產生「夠亂」的亂數呢？
* 在這個亂數產生器中的 FAQ 有寫到一點：
```
Although no computer algorithm can produce numbers that are truly random, 
Stat Trek's Random Number Generator produces numbers that are nearly random.
```
* 換句話說這個產生器也只能產生接近真的亂數的偽亂數而已
* 那要如何產生真正的亂數呢？
    * 在這個產生器裡，亂數產生是根據使用者輸入的 seed 所 "計算" 出來的。
    * 所以我們只要在每次產生亂數的時候，隨機的輸入 seed 的就行了！
        * ？？？
        * 產生亂數的時候要先隨機輸入 seed，這不就是蛋生雞還是雞生蛋一樣的問題了嗎！
* 參考資料
    * [隨機亂數生成演算法獲突破](https://www.inside.com.tw/2016/05/28/new-technique-produces-real-randomness)
    * [你的程式夠「亂」嗎？](https://www.ithome.com.tw/voice/110007)

## Linux 風格的 linked list
### 為何 Linux 採用 macro 來實作 linked list？一般的 function call 有何成本？
* function call 會在程式呼叫時將 function 所需 argument 和 pc 返回地址 `push` 進 stack，並且在 function 結束時從 stack `pop` 出正確的 pc 返回地址。
* 而 macro 則是會在程式呼叫的地方直接展開插入程式碼，而省略了 push 和 pop 的動作。
### Linux 應用 linked list 在哪些場合？舉三個案例並附上對應程式碼，需要解說，以及揣摩對應的考量
* 在老師的講座中有提到，linux 在排程管理上使用了 linked list 來實做，所以我便以這個方向去查詢。
1. [linux/kernel/sched/sched.h](https://github.com/torvalds/linux/blob/master/kernel/sched/sched.h)
```clike=
/*
 * This is the priority-queue data structure of the RT scheduling class:
 */
struct rt_prio_array {
	DECLARE_BITMAP(bitmap, MAX_RT_PRIO+1); /* include 1 bit for delimiter */
	struct list_head queue[MAX_RT_PRIO];
}; 
```
* 功能：process 管理
* 依據註解的說明這個 struct 是 real-time schedule 的 priority-queue，而這個 queue 是以 linked list 來實做

2. [linux/mm/slab.h](https://github.com/torvalds/linux/blob/master/mm/slab.h)
```clike=
/*
 * Common fields provided in kmem_cache by all slab allocators
 * This struct is either used directly by the allocator (SLOB)
 * or the allocator must include definitions for all fields
 * provided in kmem_cache_common in their definition of kmem_cache.
 *
 * Once we can do anonymous structs (C11 standard) we could put a
 * anonymous struct definition in these allocators so that the
 * separate allocations in the kmem_cache structure of SLAB and
 * SLUB is no longer needed.
 */
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 */
};
```
* 功能：kernel memory 的管理
* 由註解中可以看到在這個 struct 中也是以 linked list 穿接起系統中所有的 slab cache
* What is slab cache ?
    * Slab 算是 Kernel 裡最早的一種演算法，事實上，除了 Slab 之外，Linux Kernel 已經實作出數種演算法，以優化記憶體的配置機制。前面提到，Kernel 的底層是以 page 為記憶體配置的單位，因此，哪怕只是需要 1 Byte 的空間，都會佔用一個 page，所以良好的 Slab 演算法，才能盡可能避免記憶體浪費和破碎的問題。
    * Slab Allocator 實作了一個 cache 的架構（這裡的 cache 並非意指快取），對系統程式下的記憶體需求群組化，以達到管理的目的。一般的程式可以藉由向 Slab 註冊 cache，以得到記憶體的配置。
    * 參考資料：[Linux Kernel 記憶體管理機制之美](http://fred-zone.blogspot.tw/2009/03/linux-kernel.html)

3. [linux/mm/swap.c](https://github.com/torvalds/linux/blob/master/mm/swap.c)
```clike=
/**
 * put_pages_list() - release a list of pages
 * @pages: list of pages threaded on page->lru
 *
 * Release a list of pages which are strung together on page.lru.  Currently
 * used by read_cache_pages() and related error recovery code.
 */
void put_pages_list(struct list_head *pages)
{
	while (!list_empty(pages)) {
		struct page *victim;

		victim = list_entry(pages->prev, struct page, lru);
		list_del(&victim->lru);
		put_page(victim);
	}
}
```
* 功能：釋放一連串的 page ( 以 lru 法則挑選 )
* 不僅行程排班是以 linked list 實做，連記憶體的 page 結構也是以 linked list 來完成。



### GNU extension 的 typeof 有何作用？在程式碼中扮演什麼角色？
* 回傳一個 type，e.g. `typeof(a) b` 就會以 a 的型態宣告一個變數 b
* 可以幫助我們以更高層次的角度去封裝程式碼
* 參考資料：[Using the GNU Compiler Collection (GCC): 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));    
    })
```
* 這個 macro 定義了 `ptr` 去指向 `member` 這個結構成員的地址，這個地方也使用 typeof 來讓 `ptr` 可以是使用者所指定的 type。
* 最後再減掉這個 member 在原本 `struct` 中的記憶體位移量來算出 `struct` 的記憶體起始位置。

### 除了你熟悉的 add 和 delete 操作，list.h 還定義一系列操作，為什麼呢？這些有什麼益處？
* [linux/inlude/list.h](https://github.com/torvalds/linux/blob/master/include/linux/list.h)
* 一打開便在開頭發現了註解
```
/*
 * Simple doubly linked list implementation.
 *
 * Some of the internal functions ("__xxx") are useful when
 * manipulating whole lists rather than single entries, as
 * sometimes we already know the next/prev entries and we can
 * generate better code by using them directly rather than
 * using the generic single-entry routines.
 */
```
* 說明在某些已經知道 pre/next 節點的情況下，使 __xxx 版本的 linked list 操作會更 useful。

### `LIST_POISONING` 這樣的設計有何意義？
* [linux/include/poison.h](https://github.com/torvalds/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 *) 0x100 + POISON_POINTER_DELTA)
#define LIST_POISON2 ((void *) 0x200 + POISON_POINTER_DELTA)
```
* 當程式 access 到 `LIST_POISONING` 時便會發出 page fault 以便確保沒有人會使用到沒有初始化過得 list entry ( 被刪除掉的 )
* 而在 `list_del()` 中可發現被刪除的 list entry 都會指向 `LIST_POISONING`
```clike=
static inline void list_del(struct list_head *entry)
{
	__list_del_entry(entry);
	entry->next = LIST_POISON1;
	entry->prev = LIST_POISON2;
}
```

### linked list 採用環狀是基於哪些考量？
* 因為 linux 使用 doubly linked list 使用 circular 可以省掉總是需要兩個指標去指向頭和尾的空間，並在操作上也省去這些步驟。
* 
### `list_for_each_safe` 和 `list_for_each` 的差異在哪？"safe" 在執行時期的影響為何？
* 參考 [`LIST_POISONING` 這樣的設計有何意義？](#LIST_POISONING-%E9%80%99%E6%A8%A3%E7%9A%84%E8%A8%AD%E8%A8%88%E6%9C%89%E4%BD%95%E6%84%8F%E7%BE%A9%EF%BC%9F)
* 在 `list_for_each_safe` 中多了一個變數儲存 pos 的地址，這樣可以確保如果在迴圈中使用 `list_del` 刪除節點後，程式指標不會發生找不到 head 而無限迴圈的現象。
```clike=
#define list_for_each(pos, head) 
for (pos = (head)->next; pos != (head); pos = pos->next)
    
#define list_for_each_safe(pos, n, head) 
for (pos = (head)->next, n = pos->next; pos != (head); pos = n, n = pos->next)
```

### for_each 風格的開發方式對程式開發者的影響為何？
* 參考資料：[Foreach loop | Programmer's Wiki | FANDOM powered by Wikia](http://code.wikia.com/wiki/Foreach_loop)
* 以程式開發者來說 for 已經相當方便並且可以自由的制定範圍，但是若只是單純想要走訪一個資料結構的全部資料，使用 for 迴圈可能需要撰寫額外的程式碼，但是若使用 for_each 可以使程式碼更簡潔。
* 
### 程式註解裡頭大量存在 `@` 符號，這有何意義？你能否應用在後續的程式開發呢？
* 參考資料：[Doxygen Manual: Special Commands](https://www.stack.nl/~dimitri/doxygen/manual/commands.html)
* Doxyygen 是一個可以自動根據程式碼的註解內容產生說明文件的產生器，如果依照其規定的格式撰寫註解，這樣就可以省下額外多寫一份說明文件的步驟。
* 而 `@` 符號是 Doxygen 裡規定的註解開頭。
### `tests/` 目錄底下的 unit test 的作用為何？就軟體工程來說的精神為何？
```
:~/linux-list/tests$ ls
common.h           list_add_tail.ok       list_del.ok            list_for_each_entry.o         list_for_each_safe.ok   list_init-local.ok    list_move.ok          list_splice.ok
containerof        list_cut_position      list_entry             list_for_each_entry.o.d       list_init-explicit      list_is_singular      list_move_tail        list_splice_tail
containerof.c      list_cut_position.c    list_entry.c           list_for_each_entry.ok        list_init-explicit.c    list_is_singular.c    list_move_tail.c      list_splice_tail.c
containerof.o      list_cut_position.o    list_entry.o           list_for_each_entry_safe      list_init-explicit.o    list_is_singular.o    list_move_tail.o      list_splice_tail_init
containerof.o.d    list_cut_position.o.d  list_entry.o.d         list_for_each_entry_safe.c    list_init-explicit.o.d  list_is_singular.o.d  list_move_tail.o.d    list_splice_tail_init.c
containerof.ok     list_cut_position.ok   list_entry.ok          list_for_each_entry_safe.o    list_init-explicit.ok   list_is_singular.ok   list_move_tail.ok     list_splice_tail_init.o
list_add           list_del               list_first_entry       list_for_each_entry_safe.o.d  list_init-global        list_last_entry       list_splice           list_splice_tail_init.o.d
list_add.c         list_del.c             list_first_entry.c     list_for_each_entry_safe.ok   list_init-global.c      list_last_entry.c     list_splice.c         list_splice_tail_init.ok
list_add.o         list_del_init          list_first_entry.o     list_for_each.o               list_init-global.o      list_last_entry.o     list_splice_init      list_splice_tail.o
list_add.o.d       list_del_init.c        list_first_entry.o.d   list_for_each.o.d             list_init-global.o.d    list_last_entry.o.d   list_splice_init.c    list_splice_tail.o.d
list_add.ok        list_del_init.o        list_first_entry.ok    list_for_each.ok              list_init-global.ok     list_last_entry.ok    list_splice_init.o    list_splice_tail.ok
list_add_tail      list_del_init.o.d      list_for_each          list_for_each_safe            list_init-local         list_move             list_splice_init.o.d
list_add_tail.c    list_del_init.ok       list_for_each.c        list_for_each_safe.c          list_init-local.c       list_move.c           list_splice_init.ok
list_add_tail.o    list_del.o             list_for_each_entry    list_for_each_safe.o          list_init-local.o       list_move.o           list_splice.o
list_add_tail.o.d  list_del.o.d           list_for_each_entry.c  list_for_each_safe.o.d        list_init-local.o.d     list_move.o.d         list_splice.o.d

```
* 可以看到在 test/ 目錄底下有許多小程式，且幾乎每個裡面皆有使用 `assert()` ，這時查看 `MAKEFILE` 發現在 make 的時候便會執行所有的小程式，並測試這些程式能不能正確執行完畢。
* 這些小程式的目的即檢測 `list.h` 內的 function 能不能正確執行。
* 當我們在撰寫大型專案的時候，常常會寫許多工具函式，如果沒有先確保這些工具函式的正確性，往後向上層設計整個系統的時候便會不知道是在何處出錯，是使用的工具函式的邏輯錯誤還是整個工具函式有問題
* 如果我們能夠先行利用 `tests` 的手法確認函式的正確性，更能增進往後撰寫程式的效率。

### `tests/` 目錄的 unit test 可如何持續精進和改善呢？
* 參考 `rex662624`
* 可以增加變異性，並測試一些 boundary condition。或是故意測試一些會出錯的值，看程式碼是否能夠抓到並印出 warning。

## 針對 linked list 的排序演算法
### 對 linked list 進行排序的應用場合為何？
* 因 linux 行程管理是使用 linked list 串接，所以假設我們需要查看現在是哪些行程佔用了 cpu，並比較何行程佔的比例最大，就會使用到 linked list 的排序。
### 考慮到 linked list 在某些場合幾乎都是幾乎排序完成，這樣貿然套用 quick sort 會有什麼問題？如何確保在平均和最差的時間複雜度呢？
* quick-sort 的時間複雜度，取決於一開始的 pivot 值能否有效的把資料有效切割。因為一般情形下 quick-sort 的 pivot 值通常是取第一個或是最後一個 element，所以如果對已經排序過的資料做 quick-sort，取出的 pivot 就會是最大值或最小值，此情形即為 quick-sort 的 worst-case。

* 如果能在取 pivot 的過程動一些些手腳，使 pivot 不為最大或最小，即能提昇時間複雜度，例如使用 medium-of-mediums 的方法。
### 能否找出 Linux 核心原始程式碼裡頭，對 linked list 排序的案例？
* 參閱 `rex662624` 的[工具](https://livegrep.com/search/linux)可以直接搜尋 linux 的程式碼
* 輸入指令 `path: list_sort.h` 可以看到所有使用 list_sort.h 函式庫的程式。
* 總共 `28 matches found`
### 透過 [skiplist](https://en.wikipedia.org/wiki/Skip_list) 這樣的變形，能否加速排序？
### 研讀 [How to find the kth largest element in an unsorted array of length n in O(n)?](https://stackoverflow.com/questions/251781/how-to-find-the-kth-largest-element-in-an-unsorted-array-of-length-n-in-on)，比照上方連結，是否能設計出針對 linked list 有效找出第 k 大 (或小) 元素的演算法？
### [linux-list](https://github.com/sysprog21/linux-list) 裡頭 `examples` 裡頭有兩種排序實作 （insertion 和 quick sort)，請簡述其原理
* insert-sort 是將資料從第一個 element 插入進一個新的 linked list ( head )，而新的 list 中是已經排序過的資料，並從頭比對資料大小做插入排序，而因為這個過程須走訪每個節點，所以時間複雜度為 $O(n^2)$。
* quick-sort 是利用 pivot 值將原本的資料序列做分割，然後分割後的 list 再遞迴呼叫 quick-sort 排序。
    * 分割過程為將資料和 pivot 比大小，將比 pivot 小的是值搬到 list 頭，將比 pivot 小的值搬到 list 尾。
    * 此過程是要確保在 pivot 之前資料都是小於 pivot 的，反之在 pivot 後的資料皆大於 pivot。
* 平均情形： $O(nlogn)$
    * $T(n) = \frac{1}{n}\sum_{s=1}^n(T(s) + T(n-s)) + cn$
    * $T(n) = \frac{1}{n}{[T(1)+T(n-1)]+[T(2)+T(n-2)]+ ... +[T(n-1)+T(1)]+[T(n)+T(0)]} + cn$
    * $T(n) = \frac{2}{n}[T(1)+...+T(n-1)] + \frac{T(n)}{n} + cn$
    * $nT(n) = 2[T(1)+...+T(n-1)] + T(n) + cn^2$ --------- ①
    * $(n-1)T(n-1) = 2[T(1)+...+T(n-2)] + T(n-1) + c(n-1)^2$ --------- ②
    * ① - ② 可得 $(n-1)T(n) = nT(n-1) + c(2n-1)$
    * $\dfrac{T(n)}{n} = \dfrac{T(n-1)}{n-1} + c(\frac{1}{n} + \frac{1}{n-1})$
    * $\dfrac{T(n)}{n} = c(\frac{1}{n} + \frac{1}{n-1} + ... + \frac{1}{2}) + c(\frac{1}{n-1} + \frac{1}{n-2} + ... + \frac{1}{1})$
    * $\dfrac{T(n)}{n} = c(H_n-1) + c(H_n - \frac{1}{n})$
    * $T(n) = cn(H_n-1) + c(nH_n - 1)$
    * $T(n) = 2cnH_n - cn -c$
    * $T(n) = 2cnlogn - cn -c$
    * $T(n) = O(nlogn)$

## 實作測試程式，批次建立包含若干大小的 linked list，隨機放入數值為介於 1 到 366 之間 (包含) 的節點 (代表 [day number](https://www.epochconverter.com/daynumbers)) ，至少應該涵蓋 10^1^, 10^2^, 10^3^, ... 10^6^ 等數量，透過前述的 insert, quick, merge sort 進行排序，分析執行時間並解讀其行為

* [檢驗程式碼](https://github.com/rwe0214/linux-list/blob/master/examples/sort_analyze.c)
* 程式執行結果：
```
$ ./analyze
size	insert-sort	quick-sort	merge-sort
10^1	0.0000020971	0.0000040781	0.0000070296
10^2	0.0000390438	0.0000373689	0.0000674257
10^3	0.0018955263	0.0003176225	0.0005918828
10^4	0.2778701301	0.0058945494	0.0080722889
10^5	59.8833043724	0.2961517506	0.1274873439
```
可以看到 insert-sort 在時間上耗費相當的大，所以之後的比較省略 insert-sort。
```
$ ./analyze
size	quick-sort	merge-sort	which is fast
2^1	0.0000004582	0.0000008401	quick-sort (1.83 X)
2^2	0.0000011706	0.0000018430	quick-sort (1.57 X)
2^3	0.0000029139	0.0000042060	quick-sort (1.44 X)
2^4	0.0000065810	0.0000112332	quick-sort (1.71 X)
2^5	0.0000103636	0.0000182269	quick-sort (1.76 X)
2^6	0.0000133417	0.0000234677	quick-sort (1.76 X)
2^7	0.0000292101	0.0000531666	quick-sort (1.82 X)
2^8	0.0000681951	0.0001245088	quick-sort (1.83 X)
2^9	0.0001520672	0.0002769880	quick-sort (1.82 X)
2^10	0.0003306429	0.0005956724	quick-sort (1.80 X)
2^11	0.0007398336	0.0013145460	quick-sort (1.78 X)
2^12	0.0017331422	0.0028466553	quick-sort (1.64 X)
2^13	0.0043816538	0.0063244468	quick-sort (1.44 X)
2^14	0.0121712947	0.0136517630	quick-sort (1.12 X)
2^15	0.0380133697	0.0310422692	merge-sort (1.22 X)
2^16	0.1327709013	0.0761860735	merge-sort (1.74 X)
```
可以發現 merge-sort 在資料量大的時候表現比 quick-sort 優異許多。

## 設計 deduplication 程式，將上述輸入中的數值挑出重複的節點並與刪除，透過統計分析，解讀執行時間分佈，以及探討 [data deduplication](https://en.wikipedia.org/wiki/Data_deduplication) 的效益