# D05: list
contributed by < `e94046165` >
## 生日悖論
### 如何透過近似的運算式，估算上述機率計算呢？附上有效的 LaTeX 算式
若今天進入一個有22個人的房間內，加上自己有23個人。若用一年365天來計算，則在這個房間至少有一個人與我生日相同的機率已經超過50% 。
https://en.wikipedia.org/wiki/Birthday_problem
其實這個議題在 wiki 上就有很完整的分析了，晚點有空再來把證明用自己的話打一次。先繼續往下看。
### [Birthday problem](https://en.wikipedia.org/wiki/Birthday_problem) 對資訊安全的影響？
第一眼看到這個問題，我聯想到的是密碼的安全性，~~畢竟我是一個熱愛猜密碼的人，曾經為了作業寫不出來去猜別人的 Moodle 借東西來交(汗~~
經過一番搜尋之後發現，其實不只是猜密碼這麼簡單，更重要的是可以用來破解加密訊息。以下節錄自 [birthday attack in wiki](https://en.wikipedia.org/wiki/Birthday_attack)
The attack depends on the higher likelihood of collisions found between random attack attempts and a fixed degree of permutations. With a birthday attack, it is possible to find a collision of a hash function in 2^n/2^, with 2^n^ being the classical preimage resistance security。
利用 birthday problem 的概念，只要輸入 2^n/2^ 筆資料，就可以令一個 2^n^ 大小的 Hash function 發生 collision。以下是證明(參考自[看起來很猛的開放課程](https://www.coursera.org/learn/crypto/lecture/pyR4I/generic-birthday-attack))
**Proof**
$\ let\ r_1.....r_n\ 屬於\ hashfunction\ key\ 值集合\{1\ ...\ B\}$且 Be independent、identically distributed integers.
證明當 $n = 1.2\times B^\dfrac{1}{2} , Pr[\exists\ i\neq j, r_i=r_j]=0.5$ 即發生碰撞機率達 50%
$Pr[\exists\ i\neq j, r_i=r_j]=1-Pr[\forall i\neq j,r_i\neq r_j]\\
=1-(\dfrac{B}{B}\cdot\dfrac{B-1}{B}\cdot\dfrac{B-2}{B}...\cdot\dfrac{B-n+1}{B})\\
=1-(1-\prod_{i=0}^{n-1}\frac{i}{B})\geq1-\prod_{i=0}^{n-1}e^\frac{i}{B}=1-e^{-\frac{1}{B}\sum_{i=1}^{n-1}\ \ \ i}\\
\geq e^{-\frac{n^2}{2B}}$
將 $n = 1.2\times B^\frac{1}{2}$代入上式可得 53...%
這個數據顯示出，只要輸入B^1\2^的資料量，就有一半機率發生 collision
上面證明出來的結果可以用來檢視一開始的 birthday problem
B = 365 代入，n = 1.2*365^1\2^ = 22.9
## Linux 風格的 linked list
#### 為何 Linux 採用 macro 來實作 linked list？一般的 function call 有何成本？
參考自[阿夢的程式設計天地](https://dotblogs.com.tw/ace_dream/2016/01/16/function_macro)
巨集( macro )和函式( function )的比較
函式是拿時間換取空間的，透過執行時期在函式堆疊的切換，相同邏輯區塊只要抽出成為函式，則大家共用同一份程式即可(在記憶體中只有一份實體，較節省記憶體空間)。函式實務上還有另一個好處是可以取得函式位址，也就是說可以把函式當參數。
而巨集則是拿空間換取時間，在編譯之前，前置處理器就將該程式替換至各個呼叫區塊，所以相同的邏輯在會重複出現在各個地方，但是由於執行時間不需要在函式堆疊切換，減少時間的耗損。
也就是說選擇使用 macro 還是 function call 來實作，取決於著重在時間還是空間的成本。
#### Linux 應用 linked list 在哪些場合？舉三個案例並附上對應程式碼，需要解說，以及揣摩對應的考量
首先想到的是上學期修作業系統的時候，寫了一支模擬 CPU 排班的程式，其中各個 queue(如 ready queue、waiting queue 等等)用 linked list 來實作感覺上不錯。因此在 linux source code 關於 CPU 排班的部份試著找尋 linked list 的蹤跡：
1. [include/linux/sched.h](https://elixir.bootlin.com/linux/latest/source/include/linux/sched.h#L524)
裡的 task_struct... 嗯....是個看不到底的 struct 呢，裡面不只有指向其他 task_struct 的 link，還有一大堆名稱很熟悉的成員與其他 struct ，以下僅挑幾個我們較關心的 link 出來討論：
```C=
struct task_struct __rcu *real_parent;
/* Recipient of SIGCHLD, wait4() reports: */
struct task_struct __rcu *parent;
/*
* Children/sibling form the list of natural children:
*/
struct list_head children;
struct list_head sibling;
struct task_struct *group_leader;
```
在 Linux 系统中，所有 Process 之間都有著直接或間接的聯繫，每个 process 都有其 parent process，也可能擁有 0 或 多個 children。而同一個 parent process 底下的所有 children 為各自的 sibling 。
~~這個 task_struct 根本把我能想到 link 都用上了，我為什麼不選個只有單純 next link 的 struct 就好。~~
在追蹤這些 link 使用情形時，遇到了瓶頸~~還有瓶蓋~~：想觀察一個 kernel 裡的 function 運作情形時，可能必須追蹤數十個其他的 function，因為這些 function 往往是一個 call 一個，一直綿延下去的。更令人感到害怕的是，如果一個 kernel 裡的 function 改變了某個變數值或是鏈結(如 task_struct 裡的成員)，那麼其他使用到這個被改變變數的函式也都要考慮進去，頭有夠痛...
在所有跟排程相關的函式裡都會看到這個 task_struct ，用來追蹤 child process 進行狀況的 ptrace 就會使用到 parent、real_parent、child 等指標，來確定 process 間的親屬關係。
#### GNU extension 的 typeof 有何作用？在程式碼中扮演什麼角色？
#### typeof [參考資料](https://feichashao.com/kernel-doubly-linked-list/)
typeof 用來回傳輸入變數的 type，應用上可以靈活的定義為變數定義 type (可能依照不同的情境需要)，下面試著使用 typeof 做些練習：
```C
#define swap(a, b) \
do { typeof(a) __tmp = (a); (a) = (b); (b) = __tmp; } while (0)
int main(int agrc, char **argv)
{
char a = 'a';
char b = 'b';
printf("a = %c, b = %c\n",a ,b);
swap(a, b);
printf("new a = %c, new b = %c\n",a ,b);
int c = 1;
int d = 2;
printf("c = %d, d = %d\n",c ,d);
swap(c, d);
printf("new c = %d,new d = %d\n",c ,d);
}
```
```
root@acnes-X550JX:~/tests#./typeof
a = a, b = b
new a = b, new b = a
c = 1, d = 2
new c = 2,new d = 1
```
可以看到同一個 macro swap 在使用了 typeof 便可以處理不同 type 的 swap 功能。
#### 解釋以下 container_of 巨集的原理
```clike
#define container_of(ptr, type, member) \
__extension__({ \
const __typeof__(((type *) 0)->member) *__pmember = (ptr); \
(type *) ((char *) __pmember - offsetof(type, member)); \
})
```
container_of 巨集分為兩個部份：
第一部份：
```C
const typeof (((type *)0)->member)*__pmember = (ptr);
```
通過 typeof 定義一個 member 指針類型的指針變量 __pmember，並將其賦值為 ptr
第二部份：
```C
(type *)((char *)__pmember - offsetof(type, member));
```
透過 offsetof 巨集算出 member 在 struct 中的偏移，後用 member 的地址 __pmember 減掉偏移，得到 struct 的起始位置。offsetof 的巧妙之處在於將地址 0 強制轉換為 type 類型的指針，編譯器認為 0 是一個有效的地址，從而認為 0 是 type 指針的起始地址。如此一來 Member 的地址就為偏移量。可以做一個小實驗來驗證這件事：
```clike=
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define offsetof(type, member) ((size_t)&((type *)0)->member)
//注意此時將 0 轉型成 Type 類型的指針
#define container_of(ptr, type, member) \
__extension__({ \
const __typeof__(((type *) 0)->member) *__pmember = (ptr); \
printf("__pmember address:%p\n", __pmember); \
(type *) ((char *) __pmember - offsetof(type, member)); \
})
typedef struct student_info
{
int id;
char name[32];
int age;
}student_info;
int main()
{
size_t off_set = 0;
off_set = offsetof(student_info, id);
printf("id offset: %u\n",off_set);
off_set = offsetof(student_info, name);
printf("name offset: %u\n",off_set);
off_set = offsetof(student_info, age);
printf("age offset: %u\n",off_set);
return 0;
}
```
```
root@acnes-X550JX:~/tests#./container_of
id offset: 0
name offset: 4
age offset: 36
```
可以看到此時輸出正確的偏移量。
那麼把 0 改成 1 會發生什麼事呢？
```
root@acnes-X550JX:~/tests#./container_of
id offset: 1
name offset: 5
age offset: 37
```
如同預期的，全部 Member 的偏移量都增加了 1。
```clike=
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define offsetof(type, member) ((size_t)&((type *)0)->member)
#define container_of(ptr, type, member) \
__extension__({ \
const __typeof__(((type *) 0)->member) *__pmember = (ptr); \
printf("__pmember address:%p\n", __pmember); \
(type *) ((char *) __pmember - offsetof(type, member)); \
})
typedef struct student_info
{
int id;
char name[32];
int age;
}student_info;
int main()
{
size_t off_set = 0;
off_set = offsetof(student_info, id);
printf("id offset: %u\n",off_set);
off_set = offsetof(student_info, name);
printf("name offset: %u\n",off_set);
off_set = offsetof(student_info, age);
printf("age offset: %u\n",off_set);
printf("\n");
student_info *stu = (student_info *)malloc(sizeof(student_info));
printf("stu->age address:%p\n", &(stu->age));
student_info *ptr = container_of(&(stu->age), student_info, age);
printf("\n");
printf("stu address:%p\n", stu);
printf("ptr address:%p\n", ptr);
return 0;
}
```
測試結果：
```
id offset: 0
name offset: 4
age offset: 36
stu->age address:0xfc8444
__pmember address:0xfc8444
stu address:0xfc8420
ptr address:0xfc8420
```
從上面的測試結果可以清楚的了解到 offsetof 與 container_of 的作用：
首先是在透過 offsetof 得到某個 member 量後就可以用已知的 member 的 addr 減掉偏移量，獲得 struct 起始位置的記憶體地址。
本來覺得好像可以用 sizeof 做一樣的事，但是在不知道 struct 裡有多少成員、不知道已知 member 離 struct 開頭地址多遠的情況下，只用 sizeof 獲得某成員佔的空間好像沒有太大的意義。
#### 除了你熟悉的 add 和 delete 操作，list.h 還定義一系列操作，為什麼呢？這些有什麼益處？
由於看了一整天的程式碼，~~豆頁ㄔ艮痛~~，不如這次先把 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.
*/
```
從這段註解可以看到，除了基本版本的 functions，list.h 裡還提供了很多針對不同情境設計的 functions，他們都用 ___xxx 標示出來，有的是出於安全考量，而有的是為了效能考量。例如：
```
/*
* Insert a new entry between two known consecutive entries.
*
* This is only for internal list manipulation where we know
* the prev/next entries already!
*/
```
```clike
static inline void __list_add(struct list_head *new,
struct list_head *prev,
struct list_head *next)
{
if (!__list_add_valid(new, prev, next))
return;
next->prev = new;
new->next = next;
new->prev = prev;
WRITE_ONCE(prev->next, new);
}
```
這個 __list_add 可以讓我們在任何已知 prev 、 next 的情況下將新節點 new 加到 list 中特定的位置，而更有趣的是也可以當我們只是要將 new 加到 head 之後，對應的 list_add 也是 call 這個 function
```clike
static inline void list_add(struct list_head *new, struct list_head *head)
{
__list_add(new, head, head->next);
}
```
因為置入 head 之後，所以 prev 當然是 head，而 next 則是原來的第一個節點，也就是 head->next。
```
/**
* list_add - add a new entry
* @new: new entry to be added
* @head: list head to add it after
*
* Insert a new entry after the specified head.
* This is good for implementing stacks.
*/
```
在這個加入 entry 在 head 後一個的 function 旁有一段註解，最後一句提到 "This is good for implementing stacks"因為這符合 stack LIFO 的特性，猜測在 list.h 中應該也可以找到一個刪除 head 後的第一個 entry 的 list_del function 兩者合起來就可以實作 stack 的 pop/push 動作。
雖只看了幾個 functions 但是可以深刻的感受到，如果依照特定的需求，找到適合的 function，實作起來應該可以事半功倍，整份 list.h 應也是因應不同的場景需求，每個 linked list 的動作(add、del...)都維護了數種不同的實作方式。
#### LIST_POISONING 這樣的設計有何意義？
#### linked list 採用環狀是基於哪些考量？
Sign in with Wallet
Connect another wallet