D05: list

contributed by < e94046165 >

生日悖論

如何透過近似的運算式，估算上述機率計算呢？附上有效的 LaTeX 算式

若今天進入一個有22個人的房間內，加上自己有23個人。若用一年365天來計算，則在這個房間至少有一個人與我生日相同的機率已經超過50% 。
https://en.wikipedia.org/wiki/Birthday_problem
其實這個議題在 wiki 上就有很完整的分析了，晚點有空再來把證明用自己的話打一次。先繼續往下看。

Birthday problem 對資訊安全的影響？

第一眼看到這個問題，我聯想到的是密碼的安全性，~~畢竟我是一個熱愛猜密碼的人，曾經為了作業寫不出來去猜別人的 Moodle 借東西來交(汗~~
經過一番搜尋之後發現，其實不只是猜密碼這麼簡單，更重要的是可以用來破解加密訊息。以下節錄自 birthday attack in wiki
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ⁿ being the classical preimage resistance security。
利用 birthday problem 的概念，只要輸入 2^n/2 筆資料，就可以令一個 2ⁿ 大小的 Hash function 發生 collision。以下是證明(參考自看起來很猛的開放課程)
Proof

l e t r_{1} . . . . . r_{n} 屬 於 h a s h f u n c t i o n k e y 值 集 合 {1 . . . B}

且 Be independent、identically distributed integers.
證明當

n = 1.2 \times B^{\frac{1}{2}}, P r [\exists i \neq j, r_{i} = r_{j}] = 0.5

即發生碰撞機率達 50%

P r [\exists i \neq j, r_{i} = r_{j}] = 1 - P r [\forall i \neq j, r_{i} \neq r_{j}] = 1 - (\frac{B}{B} \cdot \frac{B - 1}{B} \cdot \frac{B - 2}{B} . . . \cdot \frac{B - n + 1}{B}) = 1 - (1 - \prod_{i = 0}^{n - 1} \frac{i}{B}) \geq 1 - \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}}{2 B}}

將

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 有何成本？

參考自阿夢的程式設計天地
巨集( macro )和函式( function )的比較

函式是拿時間換取空間的，透過執行時期在函式堆疊的切換，相同邏輯區塊只要抽出成為函式，則大家共用同一份程式即可(在記憶體中只有一份實體，較節省記憶體空間)。函式實務上還有另一個好處是可以取得函式位址，也就是說可以把函式當參數。

而巨集則是拿空間換取時間，在編譯之前，前置處理器就將該程式替換至各個呼叫區塊，所以相同的邏輯在會重複出現在各個地方，但是由於執行時間不需要在函式堆疊切換，減少時間的耗損。

也就是說選擇使用 macro 還是 function call 來實作，取決於著重在時間還是空間的成本。

Linux 應用 linked list 在哪些場合？舉三個案例並附上對應程式碼，需要解說，以及揣摩對應的考量

首先想到的是上學期修作業系統的時候，寫了一支模擬 CPU 排班的程式，其中各個 queue(如 ready queue、waiting queue 等等)用 linked list 來實作感覺上不錯。因此在 linux source code 關於 CPU 排班的部份試著找尋 linked list 的蹤跡：

include/linux/sched.h
裡的 task_struct… 嗯…是個看不到底的 struct 呢，裡面不只有指向其他 task_struct 的 link，還有一大堆名稱很熟悉的成員與其他 struct ，以下僅挑幾個我們較關心的 link 出來討論：











    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 參考資料

typeof 用來回傳輸入變數的 type，應用上可以靈活的定義為變數定義 type (可能依照不同的情境需要)，下面試著使用 typeof 做些練習：

#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 巨集的原理

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

container_of 巨集分為兩個部份：
第一部份：

const typeof (((type *)0)->member)*__pmember = (ptr);

通過 typeof 定義一個 member 指針類型的指針變量 __pmember，並將其賦值為 ptr
第二部份：

(type *)((char *)__pmember - offsetof(type, member));

透過 offsetof 巨集算出 member 在 struct 中的偏移，後用 member 的地址 __pmember 減掉偏移，得到 struct 的起始位置。offsetof 的巧妙之處在於將地址 0 強制轉換為 type 類型的指針，編譯器認為 0 是一個有效的地址，從而認為 0 是 type 指針的起始地址。如此一來 Member 的地址就為偏移量。可以做一個小實驗來驗證這件事：
































#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。












































#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!
 */

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

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…)都維護了數種不同的實作方式。