# 2018q1 Homework3 (list)
contributed by < `YuanHaoHo`>
## 生日悖論

### 如何透過近似的運算式，估算上述機率計算呢？附上有效的 LaTeX 算式
生日悖論其實一直是數學家們會拿來討論的議題，然而再討論上多以數值上的計算來解釋，因此[保羅·哈爾莫斯](https://zh.wikipedia.org/wiki/%E4%BF%9D%E7%BE%85%C2%B7%E5%93%88%E7%88%BE%E8%8E%AB%E6%96%AF)在其自傳曾提出以下概念數學的方法解釋：
乘積
$$
\prod_{k=1}^{n-1}\left(1-\frac{k}{365}\right)
$$
等於`1－p（n）`，因此我們關注哪一個`n`，使`1－p（n）< 1/2`。再利用已知的`1`到`n－1`所有整數和等於`n（n－1）/2`,然後利用不等式1－x < e^−x^，我們可以得到：
$$
1-p(n) =
\prod_{k=1}^{n-1}
\left(1-\frac{k}{365}\right)
< \prod_{k=1}^{n-1}
\left({e}^{\frac{k}{365}}\right)
$$
$$
={{\left(1 - \frac{n}{730}\right)}^{n-1}} <
{\left({e^{-n/730}}\right)^{n-1}}=
{e^{-({n^2}-n)/730}}
$$
如果僅當
$$
{e^{-({n^2}-n)/730}} <\frac{1}{2}
$$
$$
{n^2}-n > 730 log_e 2 \cong 505.997
$$
最後一個表達式的值會小於`0.5`。其中 log~e~ 表示自然對數。這個數略微小於`506`，如果取 n^2^－n = 506，我們就得到`n＝23`。這個推導只顯示至少超過23人就能保證有 50% 的機會下的生日匹配。由此概念數學的方法推出與生日悖論機率的計算方式人數一樣，但機率尚有些微出入。

### [Birthday problem](https://en.wikipedia.org/wiki/Birthday_problem) 對資訊安全的影響在哪些層面？

Birthday problem 對資訊安全的影響最能聯想到的就是[birthday attack](https://en.wikipedia.org/wiki/Birthday_attack)，他主要是將 birthday problem 的數學想法用來尋找 hash table collisions 的方法，簡單來說，就是在 hash 摘要長度有限的情況下，即 hash 值的長度下界，用此下界推算可得，一個 40 bits 長的消息摘要是很不安全的，因爲僅僅用 220（大約一百萬）次隨機 Hash 可至少以 1/2 的概率找到一個碰撞。爲了抵抗 birthday attack，通常建議消息摘要的長度至少應取爲 128 bits，此時生日攻擊需要約 264 次Hash。安全的Hash標准的輸出長度選爲 160 bits 是出於這種考慮。要產生相同的 hash table 有可能重複的機率就會提升。

### 像是 [Random Number Generator](http://stattrek.com/statistics/random-number-generator.aspx) 這樣的產生器，是否能產生「夠亂」的亂數呢？

先介紹一下Random Number Generator ，他主要就是使用統計類的演算法來產生亂數，而關於 Stat Terk 的亂數產生器，產生的亂數會因下幾點規格而改變：
* 需求的變數量
* 需求最大和最小的亂數值
* 不管有沒有複製，都允許重複值的出現

然而題目想要討論是否「夠亂」，先看我們要怎麼定義「夠亂」這個形容詞，如果說此亂數產生器假設規格內的每筆數輸出的機率都是相同的，那這樣就不能用多筆數據看分佈狀況，畢竟採樣數量永遠不夠多。然而這個亂數產生器有輸出上限，且有考慮到 seed 的引用，因此當 seed 相同時會產生出固定的亂數表，雖然網站有說明他們的演算法會與時俱進，使 seed 的影響最小，但就加密亂數而言，這樣的方法就跟生日悖論的狀態很像，當演算法的公式被猜到，再改變 seed 就已經來不及了，如此網站也有說此亂數表不適合使用在加密亂數上，因此此亂數表只能說確實亂，但是亂的不夠全面性。

## Linux 風格的 linked list
### 為何 Linux 採用 macro 來實作 linked list？一般的 function call 有何成本？
為何 Linux 採用 macro 來實作 linked list，有以下理由：
1. 防止一個頭檔被重複包含
2. 重新定義一些類型，防止由於各種平臺和編譯器的不同，而產生的類型位元組數差異，方便移植。
3. 得到指定位址上的一個位元組或字
4. 得到一個field在結構體(struct)中的偏移量
5. 得到一個變數的位址（word寬度）
6. 執行速度快，沒有堆疊的 push 和 pop 動作的需要，減少時間損耗。

比起一般的 function call 最大的不同在於執行速度的快慢。巨集與函數的功能相同，但在編譯時，編譯時會以巨集取代原來的敘述，而函數則是一個跳躍敘述；在程式執行期間，由於巨集已經展開為它所代表的敘述，程式會一行一行執行下去，而碰到函數則是跳到函數定義的副程式去執行。所以，如果將子功能以巨集撰寫，執行速度較快，但編譯後的程式碼較大；函數寫法則執行速度較慢，但是執行檔較小，如何取捨完全看程式設計的目的與需求。
==參考==：
* [C語言巨集定義技巧](http://stenlyho.blogspot.tw/2007/04/c_04.html)
* [比較 macro 與 function 的優劣點](http://blog.xuite.net/lukeatnchu/blog/221675116-%E6%AF%94%E8%BC%83+macro+%E8%88%87+function+%E7%9A%84%E5%84%AA%E5%8A%A3%E9%BB%9E)

### Linux 應用 linked list 在哪些場合？舉三個案例並附上對應程式碼，需要解說，以及揣摩對應的考量
1. [linux/kernel/sched/sched.h](https://github.com/torvalds/linux/blob/master/kernel/sched/sched.h)

/*
 * 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 的 priority ，主要是建一個 struct 並在裡面使用 linked list 的技巧來製作 real-time schedule 的 priority-queue。

2. [linux/fs/inode.c ](https://github.com/torvalds/linux/blob/master/fs/inode.c)

/*
 * These are initializations that only need to be done
 * once, because the fields are idempotent across use
 * of the inode, so let the slab aware of that.
 */
void inode_init_once(struct inode *inode)
{
	memset(inode, 0, sizeof(*inode));
	INIT_HLIST_NODE(&inode->i_hash);
	INIT_LIST_HEAD(&inode->i_devices);
	INIT_LIST_HEAD(&inode->i_io_list);
	INIT_LIST_HEAD(&inode->i_wb_list);
	INIT_LIST_HEAD(&inode->i_lru);
	__address_space_init_once(&inode->i_data);
	i_size_ordered_init(inode);
}

inode 為 一種包含了資料夾資訊的資料結構，以上的程式碼為建立新的 inode ，也是使用 linked list 將所有資料相關資訊串聯上。
4. [linux/include/linux/fs.h ](https://github.com/torvalds/linux/blob/master/include/linux/fs.h#L5)

/*
 * Indicates how deep in a filesystem stack this SB is
 */
int s_stack_depth;

/* s_inode_list_lock protects s_inodes */
spinlock_t		s_inode_list_lock ____cacheline_aligned_in_smp;
struct list_head	s_inodes;	/* all inodes */

spinlock_t		s_inode_wblist_lock;
struct list_head	s_inodes_wb;	/* writeback inodes */

用來管理檔案系統，這邊舉的例子為利用 linked list 的方式取出 superblock (超級區塊)裡最底層的 inode。
superblock 是記錄整個 filesystem 相關資訊的地方， 沒有 Superblock ，就沒有這個 filesystem 了。紀錄的主要資訊有：
* block 與 inode 的總量；
* 未使用與已使用的 inode / block 數量；
* block 與 inode 的大小 (block 為 1, 2, 4K，inode 為 128bytes 或 256bytes)；
* filesystem 的掛載時間、最近一次寫入資料的時間、最近一次檢驗磁碟 (fsck) 的時間等檔案系統的相關資訊；
* 一個 valid bit 數值，若此檔案系統已被掛載，則 valid bit 為 0 ，若未被掛載，則 valid bit 為 1

==參考==：
[鳥哥的 Linux 私房菜 - Linux 磁碟與檔案系統管理](http://linux.vbird.org/linux_basic/0230filesystem.php)

### GNU extension 的 typeof 有何作用？在程式碼中扮演什麼角色？
當使用 `typeof(a)` 會回傳 `a` 的型態，若用 `typeof(a) b` 就會用 `a` 的型態宣告一個變數 `b`。如此可以避免程式碼在處理變數時產生宣告錯誤。

### 解釋以下巨集的原理

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

先介紹 `offsetof` ，這是定義在 `<linux/stddef.h>` 中，用來計算某一個struct結構的成員相對於該結構起始位址的偏移量( offset )。
再來介紹 `container_of`， 這是個巨集指令被定義在 `<linux/kernel.h>` 中，他需要引用 `offsetof` 巨集，他的作用式用來取得 `struct` 結構的起始點，只要知道該結構的任一個成員的地址，就可以使用 `container_of` 巨集來算出該結構的起始位址。
`container_of` 可分解為 2 個動作：
1. 定義一個指向 `member` 型別的指標 `__pmember` ，然後將參數 `ptr` 餵給該指標。
2. 將 `__pmember` 的位址減掉 `member` 與結構起始點的偏移(利用 offsetof )就可得到該結構的起始點位址。

==參考==：
[Linux的container_of 與 offsetof巨集](https://myao0730.blogspot.tw/2016/09/linuxcontainerof-offsetof.html)

### 除了你熟悉的 add 和 delete 操作，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.
 */

註解有說，這些 `internal functions ("__xxx")`可以用來讓 linked list 的操作更為方便好用。

### `LIST_POISONING` 這樣的設計有何意義
list poisoning 是指當 mail list 出現無效的郵件地址導致資源的消耗， LIST_POISONING 主要被定義在 [linux/inlude/list.h](https://github.com/torvalds/linux/blob/master/include/linux/poison.h)。

/**
 * list_del() - Remove a list node from the list
 * @node: pointer to the node
 *
 * The node is only removed from the list. Neither the memory of the removed
 * node nor the memory of the entry containing the node is free'd. The node
 * has to be handled like an uninitialized node. Accessing the next or prev
 * pointer of the node is not safe.
 *
 * Unlinked, initialized nodes are also uninitialized after list_del.
 *
 * LIST_POISONING can be enabled during build-time to provoke an invalid memory                
 * access when the memory behind the next/prev pointer is used after a list_del.
 * This only works on systems which prohibit access to the predefined memory
 * addresses.
 */
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
}

由上程式碼註解可以看出，LIST_POISONING 的設計是因為刪除節點時，只有刪除 list 中的節點，並沒有真正的釋放記憶體，因此在重新使用這塊記憶體時，可能會去使用到不該用的 next / prev。

==參考==：
* [configuring list debugging and "poisoning" list pointers](https://www.spinics.net/lists/newbies/msg41333.html)
* [TingL7](https://hackmd.io/s/ByUZtiniM#)

### linked list 採用環狀是基於哪些考量？
使用效能更佳，不需要在找尾端時，還要經過 loop 去找 `node -> next = NULL`，可以直接由 head 就可以找到。
### list_for_each_safe 和 list_for_each 的差異在哪？“safe” 在執行時期的影響為何？
list_for_each_safe 和 list_for_each 的差異在多了一個 safe ，哈哈哈以上屁話，來看 linux 中 [list.h](https://github.com/torvalds/linux/blob/master/include/linux/list.h) 的註解。

/**
 * 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)

原來 safe 的版本多了一個變數 `n` 去儲存當下節點 `pos` 的 `next`。其好處在於可以執行刪除當下節點的動作，因為有 safe 的存在，所以不會影響整個迴圈的運行，list 不會斷掉，但這樣就必須多消耗記憶體空間。
### for_each 風格的開發方式對程式開發者的影響為何？
for_each 是一種 for 迴圈的替代方案，但功能更加厲害。for_each 可以簡單地走訪過整個資料結構，並運用其特色 `for_each(InputIterator _First, InputIterator _Last, Function _Func`，可以讓使用者針對範圍( first 到 last )去做特定的 function 。
==參考==:
[(原創) 如何正確的使用迴圈(使用for_each)? (C/C++) (STL) (template)](http://www.cnblogs.com/oomusou/archive/2007/05/12/744000.html)
### 程式註解裡頭大量存在 @ 符號，這有何意義？你能否應用在後續的程式開發呢？
程式註解裡頭大量存在 @ 符號，與 [Doxygen](https://en.wikipedia.org/wiki/Doxygen) 有關。 Doxygen是用來生產參考文件的工具，會自動抓取內容與註解來產生說明文件，而 `@` 的符號表是註解的開頭，或是一些關鍵字的開頭。
### tests/ 目錄底下的 unit test 的作用為何？就軟體工程來說的精神為何？
tests/ 目錄底下的 unit test 主要是用來測試 function 檔案，可以先確認每個 function 可以運作，在應用到主程式中。
如此的 coding 習慣，可以加速維護和 debug 的效率，更適合在團隊合作上進行討論與分析。

## 針對 linked list 的排序演算法
### 對 linked list 進行排序的應用場合為何？