# 2018q1 Homework3 (list)

[作業要求](https://hackmd.io/s/HkxZbJzif)

## 生日悖論

#### 如何透過近似的運算式，估算上述機率計算呢？附上有效的 LaTeX 算式
**先透過觀察算試找出機率函式 $p(n)$ 規律性：**

* `n = 3`
* $p(3)=1-\dfrac{364}{365}\times\dfrac{363}{365} = 1-\dfrac{364\times363}{365^2}$

* `n = 5`
* $p(5)=1-\dfrac{364}{365}\times\dfrac{363}{365}\times\dfrac{362}{365}\times\dfrac{361}{365}=1-\dfrac{364\times363\times362\times361}{365^4}$

* `n = 7`
* $p(7)=1-\dfrac{364}{365}\times\dfrac{363}{365}\times\dfrac{362}{365}\times\dfrac{361}{365}\times\dfrac{360}{365}\times\dfrac{359}{365} = 1-\dfrac{364\times363\times362\times361\times360\times359}{365^6}$

歸納出：
**`分子`** 為 $首項 = 364$ , $公差= -1$ 之等差數列的前 $(n-1)$ 項之乘積，根據[維基百科](https://zh.wikipedia.org/wiki/%E7%AD%89%E5%B7%AE%E6%95%B0%E5%88%97)得知此為下降階乘幂 $x=364$ $(x)_{n-1}=x\times(x-1)\times(x-2)...(x-n+1)=\dfrac{x!}{(x-n+1)!}$
**`分母`** 為 $365^{(n-1)}$

結論 ： $p(n)=1-\dfrac{\dfrac{364!}{(364-n+1)!}}{365^{(n-1)}}=1-\dfrac{364!}{365^{(n-1)}\times(364-n+1)!}$

計算 $p(22)=1-\dfrac{364!}{365^{22-1}\times(364-22+1)!}=1-0.4927=0.5073$

#### Birthday problem 對資訊安全的影響在哪些層面？
生日悖論在於如果站在自己的角度而言，要求有人跟我同一天生日的可能性(此為限定某日期)確實很低，需要至少 253 人在同一空間中才能保證有 50% 的發生機率。然而如果只要求有兩個人生日相同(沒有限定那一天)只需要 23 人就會有 50% 以上的發生機率(其實一樣是 magic number : 253 ，因為沒有特定要求日期因此只需要 23 個人就可以湊出這 253 種組合$C^{23}_2=253$)。

* 而在資訊安全層面，假設一個加密方式(通常為 hash function)為 f(n) 當 f(a) = f(b) 這樣一對 a 和 b 稱作一個 collision ，當 collision 發生時行加密方式被解析
* 因此若是這個加密方式的分佈不夠均勻，位元數不夠多，就可以透過 birthday attack 逐步解析這個加密方式，進而達到偽造數位簽證的效果

參考資料：
[The Birthday Attack](https://danielmiessler.com/study/birthday_attack/)
[Birthday attack Wiki](https://en.wikipedia.org/wiki/Birthday_attack)

#### 像是 Random Number Generator 這樣的產生器，是否能產生「夠亂」的亂數呢？
現在的亂數產生器生成方式大多是透過數學公式來產生隨機的亂數，例如： [Linear congruential generator](https://en.wikipedia.org/wiki/Linear_congruential_generator) 和 [Middle-square method](https://en.wikipedia.org/wiki/Middle-square_method) ，這類亂數產生器都需要輸入一個 seed 值來產生隨機的亂數序列，但是這邊的隨機其實是偽隨機，因為輸入同一個 seed 值會得到相同的序列以及這個亂數序列產生一定數量後就會循環。
而真正的隨機無法單單依靠數學算式來達成，但是可以透過觀察放射性物質在某一時間點的衰退速率或是利用環境噪音來做亂數的產生，因為這些是在現實生活中可以取得的真實隨機且無法再次重現，當然所需好廢的成本比較昂貴。

參考資料：
[Random number generation](https://en.wikipedia.org/wiki/Random_number_generation)
[Cryptographically secure pseudorandom number generator](https://en.wikipedia.org/wiki/Cryptographically_secure_pseudorandom_number_generator)

## Linux 風格的 linked list
#### 為何 Linux 採用 macro 來實作 linked list？一般的 function call 有何成本？
比較圖：
| no | Macro | Function |
| - | - | - |
| 1 | Macro is **Preprocessed** | Function is **Compiled** |
| 2 | **No Type Checking** | **Type Checking** is Done |
| 3 | **Code** Length **Increases** | **Code** Length remains **Same** |
| 4 | Use of macro can lead to **side effect** | No **side Effect** |
| 5 | Speed of Execution is **Faster** | Speed of Execution is **Slower** |
| 6 | Before Compilation macro name is replaced by macro value | During function call , Transfer of Control takes place |
| 7 | Useful where small code appears many time | Useful where large code appears many time |
| 8 | Generally Macros do not extend beyond one line | Function can be of any number of lines |
| 9 | Macro does not Check **Compile Errors** | Function Checks **Compile Errors** |

macro 和 function 十分相似但是又不同， macro 是直接用定義好的內容帶入到程式中做替換，由於 macro 沒有像 function 一樣需要 call 和 return 的程序，所以執行起來會比較快速。

參考資料：
[Difference between macro and function in C Programming](http://www.c4learn.com/c-programming/difference-between-macro-and-function/)
[What Differences are there Between Macros and Functions in C Language](https://www.sanfoundry.com/c-tutorials-differences-between-macros-functions/)

#### Linux 應用 linked list 在哪些場合？舉三個案例並附上對應程式碼，需要解說，以及揣摩對應的考量
1.linux/kernel/time/[clocksource.c](https://github.com/torvalds/linux/blob/master/kernel/time/clocksource.c)
為了避免 CPU 在熱插拔時發生死結(deadlock)： clocksource mutex 和 cpu hotplug mutex ，延後 clock source 對 watchdog 的更新。

/**
 * clocksource_mark_unstable - mark clocksource unstable via watchdog
 * @cs:		clocksource to be marked unstable
 *
 * This function is called instead of clocksource_change_rating from
 * cpu hotplug code to avoid a deadlock between the clocksource mutex
 * and the cpu hotplug mutex. It defers the update of the clocksource
 * to the watchdog thread.
 */
void clocksource_mark_unstable(struct clocksource *cs)
{
	unsigned long flags;

	spin_lock_irqsave(&watchdog_lock, flags);
	if (!(cs->flags & CLOCK_SOURCE_UNSTABLE)) {
		if (list_empty(&cs->wd_list))
			list_add(&cs->wd_list, &watchdog_list);
		__clocksource_unstable(cs);
	}
	spin_unlock_irqrestore(&watchdog_lock, flags);
}

2
3.
#### GNU extension 的 [typeof](https://gcc.gnu.org/onlinedocs/gcc/Typeof.html) 有何作用？在程式碼中扮演什麼角色？
`typeof()` 會回傳括號內變數的資料型態，在定義 macro 時是一個非常實用的 function
#### 解釋以下巨集的原理

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

在 `list.h` 可以看到和這個 macro 相似的程式碼 :

/**
 * container_of cast a member of a structure out to the containing structure
 * @ptr:        the pointer to the member.
 * @type:       the type of the container struct this is embedded in.
 * @member:     the name of the member within the struct.
 *
 */
#define container_of(ptr, type, member) ({                  \
    const typeof( ((type *)0)->member ) *__mptr = (ptr);    \
    (type *)( (char *)__mptr - offsetof(type,member) );})

#### 除了你熟悉的 add 和 delete 操作，`list.h` 還定義一系列操作，為什麼呢？這些有什麼益處？

#### `LIST_POISONING` 這樣的設計有何意義？

#### linked list 採用環狀是基於哪些考量？

#### `list_for_each_safe` 和 `list_for_each` 的差異在哪？"safe" 在執行時期的影響為何？

#### for_each 風格的開發方式對程式開發者的影響為何？
* 提示：對照其他程式語言，如 Perl 和 Python

#### 程式註解裡頭大量存在 `@` 符號，這有何意義？你能否應用在後續的程式開發呢？
* 提示: 對照看 Doxygen

#### `tests/` 目錄底下的 unit test 的作用為何？就軟體工程來說的精神為何？
#### `tests/` 目錄的 unit test 可如何持續精進和改善呢？