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_safe 和 list_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_head 的 doubly 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_safe 和 list_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

Last changed by 
 
rebvivi
0
503
Published on HackMD