D05: list ========= contributed by <`afcidk`> ## 生日悖論 - [ ] 自我檢查事項 - 如何透過近似的運算式，估算上述機率計算呢？附上有效的 LaTeX 算式 $\begin{split}\ \ \ \ \ &1-每個人各佔用一天的機率\end{split}$ $\begin{split}&=1-(\prod_{i=0}^{n-1}\frac{365-i}{365})\end{split}$ - [Birthday problem](https://en.wikipedia.org/wiki/Birthday_problem) 對資訊安全的影響在哪些層面？ 這個問題敘述了一個事實：一個事件看似機率很低，事實上是因為觀察角度有問題而忽略了真實機率其實不低。 Birthday problem 在資訊安全方面的影響層面有兩個方向，hash collision 和 brute force。 > 參考影片 - [Discussion on The Birthday Attack](https://www.youtube.com/watch?v=2bEL3ok8D70) Birthday Attack 的命名源自於 Birthday problem，下面以著名的 MD5 hash collision 當例子。 我們假設輸入的資料只允許長度為 20 的字串，並且有 94 個字元可以使用，這樣總共會有 $94^{20}\approx2.9\times10^{39}$ 種可能。 MD5 的輸出會是 128 bit 的數值，也就是有 $2^{128}\approx3.4*10^{38}$ 種可能 原本如果要找到 hash collision，我們必須要一個一個計算出資料的 hash value，並且預期找到碰撞可能會需要很多時間（因為看到 $94^{20}$ 感覺很大）。 但是，問題根本就不是要找到特定的 hash collision，而是要找到在已計算的所有資料中，發生 hash collision 的機率是多少，因此實際上的機率並沒有我們想像的高，已經有人證明對於 n bit 的資料我們可以在 $O(2^\frac{n}{2})$ 的複雜度裡找到 hash collision。 - 像是 [Random Number Generator](http://stattrek.com/statistics/random-number-generator.aspx) 這樣的產生器，是否能產生「夠亂」的亂數呢？ 要看產生器產生的亂數是不是夠亂，最直覺的方式就是觀察他的數字分佈。 這次產生 1000000 筆亂數，區間一樣設定成 [0,100]，再觀察數字是否為平均分佈 ![](https://i.imgur.com/yASuwi2.png) 最多的數字和最少的數字差了差不多 350 次，看起來算是蠻平均的分佈，只佔了最高次數字的 3% 左右。 ## Linux 風格的 linked list - [ ] 自我檢查事項 - ### 為何 Linux 採用 macro 來實作 linked list？一般的 function call 有何成本？ function call 的原本用意就是讓我們可以重複使用相同功能的程式碼片段，避免性質重複的雜亂程式碼導致後續的開發困難。 利用 function call 雖然可以減少這種狀況發生，但是在大量使用的情形下卻會降低程式的運行效率，因為每次 call function 的時候都需要儲存 local variable，紀錄 return address 等工作，這些是使用 function call 才會多出來的額外工作。 macro 在 preprocessing 的階段就會被編譯器轉換為對應的程式碼，如此可以避免 function call 每次呼叫都需要在 stack 上額外花費時間，又能充分的讓程式碼保持既有的簡潔和可讀性。 - ### Linux 應用 linked list 在哪些場合？舉三個案例並附上對應程式碼，需要解說，以及揣摩對應的考量 * [linux/include/media/demux.h](https://github.com/torvalds/linux/blob/master/include/media/demux.h) mux 是 multiplex 的簡寫，在音訊處理方面指的是把聲音或影片資訊封裝到一個單獨檔案當中。 而 demux 做的事情和 mux 恰好相反，是分離的意思，在音訊處理方面指的是從一個文件中把聲音或影像分離出來。 從最上方的檔案註解可以看到 ``` The Kernel Digital TV Demux kABI defines a driver-internal interface for registering low-level, hardware specific driver to a hardware independent demux layer. ``` 看起來似乎是用來提供向硬體註冊 driver 的界面 在 332 行附近的這個 struct 有使用到 linked list，註解有提到是用來儲存可以被連接到 demux 的 frontend (要找一下這是什麼東西) ```clike=332 struct dmx_frontend { struct list_head connectivity_list; enum dmx_frontend_source source; }; ``` 為什麼要使用 linked list 應該是因為這樣比較方便管理，因為我們不確定到底 list 裡面會有多少元素。 * [linux/drivers/watchdog/watchdog_pretimeout.c](https://github.com/torvalds/linux/blob/master/drivers/watchdog/watchdog_pretimeout.c) watchdog ，全名叫做 watchdog timer 或 COP timer，是一種用來處理電腦問題的硬體計時器。當他偵測到有問題的程序發生時（像是當機之類的狀況），能夠發送訊號告知電腦重新開機讓機器回歸正常狀態。實現的方式是透過一個會定時重置的計時器，如果發現計時器沒有被重置，也許就是機器出問題了，這時候就需要重新啟動。 在現代的嵌入式系統中，watchdog 扮演了非常重要的角色。為什麼這樣說呢？因為我們有很大的可能無法隨時去監控各個機器的運作狀態，發生了問題也不一定能夠直接接觸到機器去重置他（像是維基百科上舉例的[Mars Exploration Rover](https://en.wikipedia.org/wiki/Mars_Exploration_Rover)），這時候 watchdog 的珍貴就體現出來了，因為他可以嘗試讓自己回歸正常狀態而不需要人為操控。 在第 25 行，程式先宣告了一個 linked list，由註解可以知道這個 list 用來儲存 watchdog devices。 ```clike=25 /* List of watchdog devices, which can generate a pretimeout event */ static LIST_HEAD(pretimeout_list); ``` 再看到 119 行 ```clike=119 int watchdog_register_governor(struct watchdog_governor *gov) { struct watchdog_pretimeout *p; struct governor_priv *priv; priv = kzalloc(sizeof(*priv), GFP_KERNEL); if (!priv) return -ENOMEM; mutex_lock(&governor_lock); if (find_governor_by_name(gov->name)) { mutex_unlock(&governor_lock); kfree(priv); return -EBUSY; } priv->gov = gov; list_add(&priv->entry, &governor_list); if (!strncmp(gov->name, WATCHDOG_PRETIMEOUT_DEFAULT_GOV, WATCHDOG_GOV_NAME_MAXLEN)) { spin_lock_irq(&pretimeout_lock); default_gov = gov; list_for_each_entry(p, &pretimeout_list, entry) if (!p->wdd->gov) p->wdd->gov = default_gov; spin_unlock_irq(&pretimeout_lock); } mutex_unlock(&governor_lock); return 0; } ``` 由函式名稱大致上可以猜到主要功能是註冊一個 watchdog governor，註冊的方式就是配置一塊空間，並把他加到 linked list 裡面。 * [linux/tools/usb/usbip/src/usbipd.c](https://github.com/torvalds/linux/blob/master/tools/usb/usbip/src/usbipd.c) 看不太出來這份程式碼的功能，上網查了下關鍵字 usbipd。usbipd 是 USB/IP server daemon，USB/IP 是一個致力於完成遠端 USB 裝置溝通的專案，在[How to setup and use USB/IP](https://developer.ridgerun.com/wiki/index.php?title=How_to_setup_and_use_USB/IP) 裡面有一張圖片讓人容易理解這個專案在做什麼事情的 ![](https://i.imgur.com/Sv0XyS4.png) 大致上知道這是什麼東西後再回來看程式碼 在 103 行的函式 `recv_request_import()`裡面 也有用到 `list.h` 裡面寫的 macro。 ```ctype=103 static int recv_request_import(int sockfd) { ... list_for_each(i, &driver->edev_list) { edev = list_entry(i, struct usbip_exported_device, node); if (!strncmp(req.busid, edev->udev.busid, SYSFS_BUS_ID_SIZE)) { info("found requested device: %s", req.busid); found = 1; break; } } ... ``` 這個函式從名字來看是用來接收 request import 的，他會先從 linked list 裡面查詢 busid 存不存在，再進行後續的動作。 看起來 linked list 的使用時機大部分都是在不知道資料大小會有多少的情況下提供動態的配置新節點。 - ### GNU extension 的 [typeof](https://gcc.gnu.org/onlinedocs/gcc/Typeof.html) 有何作用？在程式碼中扮演什麼角色？ GNU extension 指的是那些沒有規範在 ISO standard C 裡面的 feature，但是在 GNU C compiler 卻有被補充的那些 feature 都叫做 GNU extension。想當然爾，既然沒有規範在 ISO/IEC 9899:1999 裡面，查詢 [C99 規格書](http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1124.pdf)也不會看到 typeof 的出現。 在使用 GNU extension 時要檢查是否有 `__GNUC__` 的 macro，這是在 GCC 裡面定義的。 官方文件清楚的提到 typeof 的引數可以有兩種形式： expression 和 type。 >There are two ways of writing the argument to typeof: with an expression or with a type. Here is an example with an expression 使用 expression 當作引數時，像是 function call，會回傳函數的 type。舉例來說，假設有一個函數是 `int foo(int x)`，則 `typeof(foo(5))` 意思等同於 `int`。 或是說有一個變數是 `double a`，則 `typeof(a)` 意思等同於 `double` 使用 type 作為引數就比較單純，`typeof(int *) a, b;` 意思就是有兩個 int 指標的變數。注意到如果沒有使用 typeof 也想要達到這個目的，需要寫成 `int *a, *b;` 上面提到的這個功能可以讓程式開發者很容易的在 macro 使用指標類型的變數，像是我們可以 `#define pointer(T) typeof(T *)`，透過使用 `pointer(type)` 直接命名變數，而不用在變數名稱後面都加上星號(*)。 另外一個重要的功能是可以在 macro 裡面知道傳進來的引數到底是什麼型別。 - ### 解釋以下巨集的原理 ``` #define container_of(ptr, type, member) \ __extension__({ \ const __typeof__(((type *) 0)->member) *__pmember = (ptr); \ (type *) ((char *) __pmember - offsetof(type, member)); \ }) ``` 在 [Alternate Keywords](https://gcc.gnu.org/onlinedocs/gcc-3.0.1/gcc_5.html#SEC109) 有提到，有些編譯參數像是 `--ansi` 會導致一些關鍵字失效，解決這個問題的方式就是在關鍵字前後加上`__`，但是這只限於 GNU C Compiler 而已，若是使用其他編譯器，可以自行定義在 macro 裡面。另外，有些編譯參數還會對 GNU extension 產生許多 warning，如果不想要看到關於這些的 warning，可以在表達式之前加上 `__extension__`。 繼續往下看，一層一層把 expression 解開應該會比較好理解 * `((type *) 0)` : 把 0 轉成 type 指標的型別。 * `((type *) 0)->member)` : 這個 object 的其中一個成員 member。 * `__typeof__(((type *)0)->member)` : 相等於 `((type *)0)->member` 的型別。 * `__typeof__(((type *)0)->member) *__pmember = ptr` : 宣告一個指向 `((type *)0)->member` 的指標，並把 ptr assign 進去。 * `offsetof(type,member)` : 根據 [offsetof man page](http://man7.org/linux/man-pages/man3/offsetof.3.html)，會回傳該 member 在 field 從頭數來的 offset。 * `((char *) __pmember - offsetof(type,member))` : 把剛剛的指標轉成指向字元的指標，再減去 member 的 offset。 * `(type *) ((char *) __pmember - offsetof(type,member))` : 最後再把這個位址轉成指向 type 的指標，得到該 field 第一個元素的位址（field 的位址）。 由 macro 名稱可以知道，這個 macro 是要得到某 member 的 container，於是計算了這個 container 的起始位置，也就得到了 container of member = container。因此如果我們有一個結構的 member，就可以用這個 macro 得到該結構的起始位址。 - ### 除了你熟悉的 add 和 delete 操作，`list.h` 還定義一系列操作，為什麼呢？這些有什麼益處？ 像是 `list_rotate_left()` 和 `list_for_each_xxx`，有 `safe`，`continue` 等各種版本，這些都可以避免我們寫出許多重複性大的程式碼。 - ### `LIST_POISONING` 這樣的設計有何意義？ LIST_POISON 被定義在 [`linux/poison.h`](https://github.com/torvalds/linux/blob/master/include/linux/poison.h) 裡面，根據註解提到的 ``` These are non-NULL pointers that will result in page faults under normal circumstances, used to verify that nobody uses non-initialized list entries. ``` 我們知道這是用來確保沒有人使用沒被初始化過的 list 寫法。當需要釋放記憶體空間時，我們一般的作法是把指標設成 NULL，而 LIST_POISONING 卻是把指標設成其他也會導致 page fault 的位址。 觀察 [list.h](https://github.com/torvalds/linux/blob/master/include/linux/list.h) 和 [lib/list_debug.c](https://github.com/torvalds/linux/blob/master/lib/list_debug.c) 後發現，他們在刪除節點時把往前 (`node->prev`) 設成 `LIST_POISON2`，而往後 (`node->next`) 會設成 `LIST_POISON1` 雖然還沒有找到明確的註解寫說為什麼要這樣做，不過我猜測原因也許是為了方便除錯，我們可以透過知道什麼位址導致的 page fault 找到什麼地方出了問題，這是 assign 成 NULL 無法達到的。 - ### linked list 採用環狀是基於哪些考量？ 可以不用把 head 和 tail 當作特殊情形處理，一視同仁的環狀 linked list 可以減少複雜的判斷式。 - ### `list_for_each_safe` 和 `list_for_each` 的差異在哪？“safe” 在執行時期的影響為何？ 先看註解 `list_for each`: iterate over a list ```clike #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 ```clike #define list_for_each_safe(pos, n, head) \ for (pos = (head)->next, n = pos->next; pos != (head); \ pos = n, n = pos->next) ``` 看起來是 `safe` 版本可以解決掉 `非 safe` 在刪除節點上遇到的問題。 看程式碼差別只有在多出了一個 n 來作為類似緩衝的角色。 為什麼要這樣做呢？我們在 `list_for_each` 裡面處理的對象會是 pos，如果我們刪除了 pos 這個節點，在下一次 `pos = pos->next` 根據刪除方法可能會是 undefined 或是其他行為，但是都是我們不希望發生的事。 在 `list_for_each_safe` 裡面使用了一個相同結構的 n 當作緩衝，在刪除後可以把原本的 `pos->next` 透過 n 取回來，避免 `list_for_each` 在刪除節點時可能會發生的問題。 - ### for_each 風格的開發方式對程式開發者的影響為何？ - 提示：對照其他程式語言，如 Perl 和 Python 最直觀的影響大概就是可以用比較簡短的方式走訪過整個結構，這樣可以讓程式碼比較簡潔，應該可以算是 syntax sugar。 另外，Python 並沒有 foreach 的寫法。嚴格說起來，他的 for 迴圈就可以算是其他語言的 foreach 了，透過像是 `for book in books:` 這種寫法就可以達成不使用 iterator 拜訪整個結構的元素，並且注意到 book 其實是該元素的複本，也就是說我們無法透過 book 取更改 books 裡面的元素內容。 - ### 程式註解裡頭大量存在 `@` 符號，這有何意義？你能否應用在後續的程式開發呢？ - 提示: 對照看 [Doxygen](https://en.wikipedia.org/wiki/Doxygen) Doxygen 可以協助程式開發者透過程式碼裡面的註解產生說明文件，方便日後更改程式碼時可以透過簡單的指令一併修改文件，而不用在維護程式碼的同時還要記得特別去更改說明文件。 `@` 是 Doxygen 裡面用來辨識說明文件裡參數的字元，像是 `@param` 代表參數或是 `@return` 代表回傳值等。 在程式開發裡面，我們同樣也可以使用某些比較不常使用到的符號來當作標記看待。在編寫像是 Doxygen 這種轉換文件的程式可以讓我們提供一個比較好的規則來讓使用者遵守。 - ### `tests/` 目錄底下的 unit test 的作用為何？就軟體工程來說的精神為何？ unit test 的作用是測試每個小模組運作的正確性，透過 unit test 可以讓程式開發者比較容易找到程式有問題的地方，也可以在軟體開發完成之前就先測試已經寫好的模組而不用等到全部完成再測試。 - `tests/` 目錄的 unit test 可如何持續精進和改善呢？ ## 針對 linked list 的排序演算法 - [ ] 自我檢查事項 - ### 對 linked list 進行排序的應用場合為何？ 先思考 linked list 使用的場合為何？ linked list 的優點是插入和刪除都可以在 $O(1)$ 的複雜度完成，並且可以動態配置記憶體，不需要將資料的大小寫死。 舉例來說，linked list 可以用在管理名單上 * 在頻繁的插入和刪除中可以達到比使用陣列還要快的速度。 * 可以自行定義 linked list 裡面資料的內容。 * 有時候列出的清單我們會希望以不同的欄位來為主，這時候就可以寫出不同的規則來重新排序。 - ### 考慮到 linked list 在某些場合幾乎都是幾乎排序完成，這樣貿然套用 quick sort 會有什麼問題？如何確保在平均和最差的時間複雜度呢？ quick sort 的平均複雜度可以在最好的情況下達到 $O(nlgn)$ 。在 pivot 選擇上如果每次都選到只能分成 $|1|p|n-2|$ 的話則會退化為 $O(n^2)$。 在結構幾乎排序完成的情況下，複雜度會非常接近 $O(n^2)$，顯然不太符合我們的需求，這時候會花費的時間甚至不如 insertion sort 和 bubble sort。 [這個網站](https://www.toptal.com/developers/sorting-algorithms/)有各種排序演算法的動畫，可以發現在各種不同的情況下不同的演算法各有時間上優劣，時間複雜度越低在時務上不見得表現比較好。 - ### 能否找出 Linux 核心原始程式碼裡頭，對 linked list 排序的案例？ [lib/list_sort.c](https://github.com/torvalds/linux/blob/master/lib/list_sort.c) 裡面就是排序 linked list 的程式碼，是根據 merge sort 實做出來的。 像是 [/fs/ext4/fsmap.c](https://github.com/torvalds/linux/blob/master/fs/ext4/fsmap.c) 裡面就有對 linked list 排序，在程式碼裡面他會先在檔案系統裡面找出所有的 fixed metadata，存到 linked list ，再將結構根據額外寫的規則排序。 - ### 透過 [skiplist](https://en.wikipedia.org/wiki/Skip_list) 這樣的變形，能否加速排序？ 目前想到的方法是**先遍歷一次 linked list**，把導致排序不完全的元素挑出來，**建立 skiplist**，再**一個一個插入**，最後layer 0 就會是排序後的 linked list。 會影響效率的地方有兩個: * 排序前資料的雜亂程度（越接近排序完會越快，因為插入的比較少） * 建立 skiplist 花費的時間 插入的時間複雜度是 $O(logn)_{best}/O(n)_{average}$，影響整體效能的是要插入多少元素 因為 skiplist 的建立和機率有關，這裡假設每一層元素數量都是前一層的 1/2 (p=1/2) 這樣分析複雜度會是 $n\times(\frac{1}{2}+\frac{1}{4}+...+(1/2)^{logn}) \le n\times1 = O(n)$ 我認為是可以加速排序的， - ### 研讀 [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 大 (或小) 元素的演算法？ 使用演算法 quickselect，是一種 quicksort 的變形。 quickselect 透過隨機選取的 pivot 達到時間複雜度為 $O(n)_{best}/O(n^2)_{worst}$ 理解了 [Ying Xiao](https://stackoverflow.com/users/30202/ying-xiao) 在回答中寫的 pseudo code ，自己嘗試寫了第 k 大的版本 pseudo code ``` QuickSelect(A,k) let A1, A2 be empty linked list let pivot be random selected element from A foreach i in A if i>pivot then // 比 pivot 大的都放到 A1 append i to A1 else if i<=pivot then append i to A2 // 比 pivot 等於或小於的都放到 A2， else // 因為最後會以 A1 來判斷 do nothing if length(A1)>(k-1) then // A1 的長度比 k-1 大， QuickSelect(A1,k) // 代表要找的元素應該在 A1 else if length(A1)<(k-1) then // A1 的長度比 k-1 小， QuickSelect(A2,k) // 代表要找的元素應該在 A2 else return pivot // A1 的長度等於 k-1，代表 pivot 就是第 k 個 ``` - ### [linux-list](https://github.com/sysprog21/linux-list) 裡頭 `examples` 裡頭有兩種排序實作 （insertion 和 quick sort)，請簡述其原理 #### insertion sort: list_insertsort 和 list_insert_sorted list_insertsort 會先宣告一個 list_unsorted，再把 `main()` 裡面傳入的 unsorted list 接在 list_unsorted 後面。 在遍歷時，每次先刪除當前元素，再利用 list_insert_sorted 放到正確的位置。 ```clike static void list_insertsort(struct list_head *head) { struct list_head list_unsorted; struct listitem *item = NULL, *is = NULL; INIT_LIST_HEAD(&list_unsorted); list_splice_init(head, &list_unsorted); list_for_each_entry_safe (item, is, &list_unsorted, list) { list_del(&item->list); list_insert_sorted(item, head); } } ``` 分成三種情況： * 第一個元素（head 還是空的時候） * 中間的元素（如果比較小就加到該 node 前面） * 最後一個元素（第二種情況無法判斷，直接加到最尾端） ```clike static void list_insert_sorted(struct listitem *entry, struct list_head *head) { struct listitem *item = NULL; if (list_empty(head)) { list_add(&entry->list, head); return; } list_for_each_entry (item, head, list) { if (cmpint(&entry->i, &item->i) < 0) { list_add_tail(&entry->list, &item->list); return; } } list_add_tail(&entry->list, head); } ``` #### quicksort: list_qsort quicksort 的實做方法有點像 mergesort，只是從把元素分一半變成取第一個元素當 pivot。分類完再分別對兩群繼續做 quicksort，最後利用 `list_add`，`list_splice` 和 `list_splice_tail` 把排序好的 linked list 放回原本的 head。 ```clike static void list_qsort(struct list_head *head) { struct list_head list_less, list_greater; struct listitem *pivot; struct listitem *item = NULL, *is = NULL; if (list_empty(head) || list_is_singular(head)) return; INIT_LIST_HEAD(&list_less); INIT_LIST_HEAD(&list_greater); pivot = list_first_entry(head, struct listitem, list); list_del(&pivot->list); list_for_each_entry_safe (item, is, head, list) { if (cmpint(&item->i, &pivot->i) < 0) list_move_tail(&item->list, &list_less); else list_move(&item->list, &list_greater); } list_qsort(&list_less); list_qsort(&list_greater); list_add(&pivot->list, head); list_splice(&list_less, head); list_splice_tail(&list_greater, head); } ``` ## 參考資料 （沒有在內容提供連結的部份） * [关于音视频的一些知识（demux、filter等）](https://blog.csdn.net/haomcu/article/details/7072707)