2019q1 Homework1 (list)

contributed by <ndsl7109256>

注意作業要求，符合格式規範

jserv

作業要求

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

自我檢查事項:

• 為何 Linux 採用 macro 來實作 linked list？一般的 function call 有何成本？
• Linux 應用 linked list 在哪些場合？舉三個案例並附上對應程式碼，需要解說，以及揣摩對應的考量
• GNU extension 的 typeof 有何作用？在程式碼中扮演什麼角色？
• 解釋以下巨集的原理

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

• 除了你熟悉的 add 和 delete 操作，list.h 還定義一系列操作，為什麼呢？這些有什麼益處？
• LIST_POISONING 這樣的設計有何意義？
• linked list 採用環狀是基於哪些考量？
• 什麼情境會需要對 linked list 做排序呢？舉出真實世界的應用，最好在作業系統核心出現
• 什麼情境會需要需要找到 第 k 大/小元素 呢？又，你打算如何實作？
• list_for_each_safe 和 list_for_each 的差異在哪？"safe" 在執行時期的影響為何？
• for_each 風格的開發方式對程式開發者的影響為何？
  • 提示：對照其他程式語言，如 Perl 和 Python
• 程式註解裡頭大量存在 @ 符號，這有何意義？你能否應用在後續的程式開發呢？
  • 提示: 對照看 Doxygen
• tests/ 目錄底下的 unit test 的作用為何？就軟體工程來說的精神為何？
• tests/ 目錄的 unit test 可如何持續精進和改善呢？

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

先看一下 gcc 裡對 macro 的定義

A macro is a fragment of code which has been given a name. Whenever the name is used, it is replaced by the contents of the macro.
Macros

preprocessor 會在 compile 前將每個 macro 替換成事先 define 好的內容。程式可以直接循序執行，不像 function 要做 push 或 pop 的動作。如此一來便可節省時間。

但 macro 的缺點便是因為將每個 macro 展開運作，不像 function 使用固定的 memory ，會隨著使用次數的增長增加占用的 memory space。

• Memory test
  寫了段簡單的 程式(memory.c) 並分別運行 macro 和 function 版本，看他們使用了多少 memory。

PID USER      PR  NI    VIRT    RES    SHR S  %CPU %MEM     TIME+ COMMAND 
4570 os2018    20   0    4376    824    760 R  97.0  0.0  19:56.08 macro           
4585 os2018    20   0    4376    792    728 R  89.4  0.0  18:16.96 function           

藉由 top 查看 process 使用 memory 的情形，便可發現 macro 版的比 fuction 版的多用了點 memory

• Time test
  程式(time.c)

$time ./macro

real	0m0.014s
user	0m0.003s
sys	0m0.000s

$time ./function

real	0m0.039s
user	0m0.014s
sys	0m0.000s

下 time 執行兩個程式發現 function 運行時間比 macro 多了 2 到 3 倍。

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

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

typeof 用於索引變數的 type ，可以吃兩種參數。

• expression

• type

Typeof

解釋以下巨集的原理

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

• __extension__
  此 macro 主要用於防止 gcc 產生警告，雖然我用 7.3.0 版本的 gcc ，就算把__extension__拿掉也不會產生警告。

• ((type *) 0)->member
  ((type *) 0) 用於得到一個 type 型態的 pointer ，其中的 0 換成其他整數也可以。再指向 member

• offsetof定義在 <linux/stddef.h> 中，用來計算某一個struct結構的成員相對於該結構起始位址的 offset 。

#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)

將 member 的 addrss 減去 offset 便可得到 struct 的起始位置。

#include <stdlib.h>
#include <stdio.h>
#include <string.h>

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


typedef struct {
   char name[16];
   int weight;
   char wife1[12];
   char wife2[12];
   char wife3[12];
} weeb;

int main (void)
{
    weeb nerd = {"your_name",87,"Miku","Kotori","Umi"};

    printf("address of struct     %p\n", &nerd);//0x7ffc3584dc00
    printf("address of wife3      %p\n", &nerd.wife3);//0x7ffc3584dc2c
    printf("id offset %ld\n", offsetof(weeb,wife3));//output is 44(16 + 4 + 12 +12)
    printf("offset of id        %ld\n", (long)&nerd.wife3 - (long)&nerd );
    printf("get address of struct from that of member  %p\n", container_of(&(nerd.wife3),weeb, wife3));//0x7ffc3584dc00
    return 0;
}

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

==list.h==

LIST_POISONING 這樣的設計有何意義？

確保不會使用到還沒初始化的 entry ，如果被 reference 將會產生 page fault
==poison.h==
Linux鏈結串列struct list_head 研究

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

在一個特定的排序中不斷循環時就需要使用到 circular linked list，在 CPU 排程就會使用到
可以快速的對尾端進行操作。
若操作不慎使得中間的 link 斷開，有機會復原。
可以實做一些環狀或是沒有明確頭尾的資料結構。

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

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

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

#define list_for_each(pos, head) \
　　　　for (pos = (head)->next; pos != (head); pos = pos->next)

如果 list_for_each 裡面做刪除節點，可能連 head 本身都刪掉了，==pos != (head)==就無法做判斷了。

#define list_for_each_safe(pos, n, head) \
for (pos = (head)->next, n = pos->next; pos != (head); \
pos = n, n = pos->next)

而 safe 版本的多了個 n 指向 pos 的 next ，確保， n 無效的話就會少走一次

for_each 風格的開發方式對程式開發者的影響為何？

不用了解 array 或 list 的實際物件數也可以做 traverse ，可讀性也比較好一點。

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

Doxygen 用於產生程式的說明文件，@有幾種常見用法。

• @file 檔案的註解說明
• @author 作者的資訊
• @brief 用於 class 或 function 的註解中，後面為 class 或 function 的簡易說明
• @param
  @param arg_name 參數說明
  主要用於函式說明中，後面接參數的名字，然後再接關於參數的說明。
• @return 後面接函數回傳值的說明。用於 function 的註解中。說明該函數的傳回值。
• @retval
  @retval value 回傳說明
  主要用於函式說明中，說明特定傳回值的意義。後面接回傳值，再接該回傳值的說明。

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

針對 function 逐個做測試，屬於軟體工程裡 Implementation 的過程，確認每個 function 皆正常執行後才能進到下個階段。
在每個 unit test 裡便用了許多 assert 確定每步皆正常執行。

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

tags: sysprog,2019spring