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) 的效益
Sign in with Wallet
Connect another wallet