Try   HackMD

2019q1 Homework1 (list)

contributed by < rebvivi >

tags: linux2019

作業要求

  • 回答「Linux 風格的 linked list」裡頭「自我檢查清單」的所有問題,需要附上對應的參考資料和必要的程式碼
  • 從 linux-list 學習裡頭的技巧,包含裡頭 unit test 的設計,透過給定的 linked list 操作,實作出 merge sort
    • 附上你的修改過程,也需要讓qtest 得以支援
    • 可將 dict 裡頭的測試資料拿來作效能分析的輸入
    • 思考提升排序效率的方法,需要做平均和最壞狀況的分析

自我檢查清單

  1. 為何 Linux 採用 macro 來實作 linked list?一般的 function call 有何成本?
  2. Linux 應用 linked list 在哪些場合?舉三個案例並附上對應程式碼,需要解說,以及揣摩對應的考量
  3. GNU extension 的 typeof 有何作用?在程式碼中扮演什麼角色?
  4. 解釋以下巨集的原理
#define container_of(ptr, type, member)         \
__extension__({                             \
const __typeof__(((type *) 0)->member) *__pmember = (ptr);\
(type *) ((char *) __pmember - offsetof(type, member));\ })
  1. 除了你熟悉的 add 和 delete 操作,list.h 還定義一系列操作,為什麼呢?這些有什麼益處?
  2. LIST_POISONING這樣的設計有何意義?
  3. linked list 採用環狀是基於哪些考量?
  4. 什麼情境會需要對 linked list 做排序呢?舉出真實世界的應用,最好在作業系統核心出現
  5. 什麼情境會需要需要找到第 k 大/小元素呢?又,你打算如何實作?
  6. list_for_each_safelist_for_each 的差異在哪?“safe” 在執行時期的影響為何?
  7. for_each 風格的開發方式對程式開發者的影響為何?
    • 提示:對照其他程式語言,如 Perl 和 Python
  8. 程式註解裡頭大量存在 @符號,這有何意義?你能否應用在後續的程式開發呢?
    • 提示: 對照看 Doxygen
  9. tests/ 目錄底下的 unit test 的作用為何?就軟體工程來說的精神為何?
  10. tests/ 目錄的 unit test 可如何持續精進和改善呢

1. 為何 Linux 採用 macro 來實作 linked list?一般的 function call 有何成本?

  • macro:用 #define 這個語法,描述一段算式或變數,在 compile 之前, preprocessor 就會將所有算式或變數macro_name 做代換,執行時不需要 function call 一樣有 stack 的 push 或是 pop,讓執行的速度變快
    但隨著呼叫 macro 的次數增加,會大大的增加記憶體的使用量,是一種用空間換取時間的方法
#define macro_name  算式或變數
  • function call:
    執行時需要有 stack 的 push 或是 pop ,也就是主要的成本,會讓執行的時間變慢
    但是所有相同的算式都共用同一部份 code (共用同一部份記憶體) ,相對 macro 來說比較節省記憶體空間,是一種用時間換取空間的方法

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

  • 在 Linux kernel 中,有叫做 list_headdoubly linked list,包含 next 和 prev 兩個 pointer ,分別指向下一個跟前一個 node
struct list_head {
    struct list_head *next, *prev;
};

一開始都會把 next 和 prev 指向自己做 initialization
之後就可以藉此判斷 list 是否是空的

int list_empty(const struct list_head *head)
{
        return head->next == head;
}

參考資料:Linked Lists - Linux Device Drivers, Second Edition

3. GNU extension 的 typeof 有何作用?在程式碼中扮演什麼角色

typeof 是 C 語言的 extension,用於傳回物件的 type
typeof 的參數可以有兩種:

  • expression

假設 x 是一個 array of pointers to functions ,我們可以得到這個 function 回傳值的 type

typeof (x[0](1))
  • type

我們得到的 type 是 pointers to int

typeof (int *)

在 macro 的時候,可能無法判斷 a 和 b 的 type,所以如果使用 typeof 的話可以讓 macro 動態的接受不同的 type ,除了避免 type 轉換中產生錯誤,也可以讓程式更有彈性

#define max(a,b) 
  ({ typeof (a) _a = (a); \
      typeof (b) _b = (b); \
    _a > _b ? _a : _b; })

4. 解釋以下巨集的原理

#define container_of(ptr, type, member)         \
__extension__({                             \
const __typeof__(((type *) 0)->member) *__pmember = (ptr);\
(type *) ((char *) __pmember - offsetof(type, member));\ })
  • (type *) 0)->member
    0 轉型為 pointer to type 並將它指向 member

  • __typeof__(((type *) 0)->member)
    取得 "member 的 type"

  • __typeof__(((type *) 0)->member) *__pmember:
    將 __pmember 宣告為 pointer to "member 的 type"

  • __typeof__(((type *) 0)->member) *__pmember = (ptr):
    將 ptr 的位址 assign 給 __pmember

offsetof 的 Linux Man Page 寫到:

size_t offsetof(type, member);

The macro offsetof() returns the offset of the field member from the start of the structure type.

  • offsetof(type, member)
    member 在 type 這個 structure 的 offset

  • (char *) __pmember - offsetof(type, member)
    __pmember 是指向 “member 的 type” 的,如果再減去 “member 的 type” 在 type 這個 structure 的 offset,可以得到 type 這個 structure 的起始位置

  • (type *) ((char *) __pmember - offsetof(type, member))
    將 type 這個 structure 的起始位置轉型為 type

  • __extension__
    避免 gcc 提出警告

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

  • 這樣 list 在做這一系列操作的時候,能夠讓速度變得更快,將 time complexity 盡量壓在 O(1) 之內
  • list 在做這一系列操作的時候,只有改變 list 指的位置,並沒有改變記憶體本身的資料,所以我們在放資料的時後就可以自由的放置在記憶體,並不因為使用 linkes list 這個 structure 而受到限制

參考資料:Linux source code: include/linux/list.h

6. LIST_POISONING這樣的設計有何意義

如果我們將一個 doubly linked list 中的 node 刪除

* 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
}

在刪除 node 之後, node 變成一個 uninitialized node,當我們去 access 這個 node 會變得不安全,所以我們會將 node 的 next 和 prev 指向不合法的記憶體位址,之後如果我們試圖去 access 這個被刪除的 node,就會直接產生 page fault,確保我們 access 資料時的安全性

7. linked list 採用環狀是基於哪些考量?

如果 linked list 採用環狀的結構,就沒有一般 linked list 那些 head 和 tail 的問題,對每個 node 來說並沒有操作上的不同,而且能夠任意一個 node 去 traverse 整個 linked list ,並不一定限制要從 head 開始

8. 什麼情境會需要對 linked list 做排序呢?舉出真實世界的應用,最好在作業系統核心出現

當我們在搜尋網頁的時候,網頁往往會有 page rank ,用來分析網頁的相關性和重要性,而 page rank 會隨著網頁的點擊率而上升或下降,所以我們就要使用 sorting 來幫我們依照 page rank 的大小做排序

9. 什麼情境會需要需要找到第 k 大/小元素呢?又,你打算如何實作?

  • 當搜尋引擎依照 page rank 的大小做排序之後,會需要找到第 k 大元素,把最大的 k 個網頁排在搜尋結果的前面
  • 利用 worst-case linear-time selection 實作
    1. Divide the n elements into groups of 5. Find the median of each 5-element group by rote
    2. Recursively SELECT the median x of the n/5 group medians to be the pivot.
    3. Partition around the pivot x. Let k = rank(x).
      • if(i = k)
        return x
      • else if (i < k)
        recursively SELECT the ith
        smallest element in the lower part
      • else
        recursively SELECT the (i–k)th
        smallest element in the upper part

10. list_for_each_safelist_for_each 的差異在哪?“safe” 在執行時期的影響為何?

  • list_for_each

我們並不能更改任何一個 node ,假如我們 delete 掉一個 node ,我們會因此找不到原本 node 的下一個 element,因此失去 node 的後面那些資料

#define list_for_each(node, head) \
    for (node = (head)->next; node != (head); node = node->next)
  • list_for_each_safe

list_for_each_safe 相對 list_for_each 多了一個 safe 的暫存空間,而 safe 指向 node 的下一個 element ,避免我們將 node 給 delete 掉之後,會找不到原本 node 的下一個 element

#define list_for_each_safe(node, safe, head)                     \
    for (node = (head)->next, safe = node->next; node != (head); \
         node = safe, safe = node->next)

11. for_each 風格的開發方式對程式開發者的影響為何?(提示:對照其他程式語言,如 Perl 和 Python)

for_each 不像一般我們在 C 語言使用的 for 需要有一個 counter , for_each 會將所有的 element 都跑過一遍

mylist = ['a', 'b', 'c']

    for item in mylist:

               print item

輸出結果

a
b
c

for_each 對我們人來說,使用起來更為精簡方便,可讀性也更高

12. 程式註解裡頭大量存在 @符號,這有何意義?你能否應用在後續的程式開發呢?(提示: 對照看 Doxygen)

  • Doxygen 是一個可以自動產生文件的程式,它能夠抓取程式的內容,自動產生說明程式的文件

我們在註解的前方加入一些 Doxygen 支援的指令,比如說@ 這個符號,可以告訴 Doxygen 這是特殊的指令,例如:

以下用於說明一個 function , parameter 是參數的名稱,而後方往往會連接對這個 parameter 的說明

@parameter:parameter 的說明

以下是 list_head 上方的註解,也是@ 這個符號的實際應用

 * @prev: pointer to the previous node in the list
 * @next: pointer to the next node in the list

在註解前方加入@等等的指令之後,能夠讓 Doxygen 更容易辨識一些關鍵字,更容易產生說明程式的文件

  • 之後多人共同開發一些大型程式的時候,往往需要有這些註解,能夠幫助其他共同開發者可以快速看懂彼此的程式,增快開發程式的效率

13. tests/ 目錄底下的 unit test 的作用為何?就軟體工程來說的精神為何?

  • unit test:針對程式裡最小的邏輯單元為對象,寫一個測試的程式,來檢驗這些邏輯單元是否正確
    • 從最小的邏輯單元開始測試,可以確保程式的正確性
    • 我們輸入 make ,執行 unit test ,可以用自動化的方式測試我們的程式,而不用靠我們手動自己輸入測試資料
    • 運用 unit test 能夠幫我們測試如果程式在面對一些極端情況的 input ,是否也能如期的產生我們所希望的 output

14. tests/ 目錄的 unit test 可如何持續精進和改善呢?

可以根據一些極端值或邊界值做測試,看看程式會不會因此產生錯誤,讓程式能夠因應各式各樣的 input