2019q1 Homework1 (list)

contributed by < evanjack2002 >

tags: linux2019

F02: list

Purpose

• 學習 Linux 核心原始程式碼的資料結構
• 資料封裝和 C 語言程式設計技巧
• 設計 unit test

作業要求

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

自我檢查事項

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

• 採用 macro 來實作 linked list？
  • 減少 function call 成本
  • 空間換取時間。
• 一般的 function call 有何成本？
  • jump 和 return。

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

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

• 找到 expression 所歸屬的 data type。

• e.g. typeof(a) 為 struct listitem，typeof(b) 為 integer。

  ​​​​struct listitem {
  ​​​​    uint16_t i;
  ​​​​    struct list_head list;
  ​​​​};
  
  ​​​​struct listitem a;
  ​​​​int b;
  

4. 解釋以下巨集的原理

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

• 宣告一個 __pmember 常數變數 point to member 的 data type，並 assign ptr 值給 __pmember 常數變數。
• 此 __pmember 常數變數的 lifecycle 只在此 {...} 內。
• 透過 __pmember 的位址，減去在 type 裡到 member 的位移量，得到 point to type 的位址。
• 意旨透過 structure member 的 address，去找到包含此 memeber 的 structure。
• e.g. 把 &a->list 的位址，減去 2 (offsetof(struct listitem, list) 為 2)，會得到 &a 的位址
  ​​​​struct listitem {
  ​​​​    uint16_t i;
  ​​​​    struct list_head list;
  ​​​​};
  
  ​​​​struct listitem a;
  

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

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

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

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

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

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

• list_for_each_safe 允許在 iterate 過程中，移除 list entry，也不會影響 linked list 的連結。
• safe 為 node 的下一個 entry，node 被刪除，safe 仍可以繼續尋訪下一個 entry。

#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

12. 程式註解裡頭大量存在 @ 符號，這有何意義？你能否應用在後續的程式開發呢？

• @ 為 Doxygen Special Commands。
• Doxygen 能從 source code 中，產生出文件。
  • 透過 doxygen -g 產生 Doxyfile 設定檔
  • 修改 Doxyfile 設定
  • 使用doxygen Doxyfile 產生文件
• 透過 soure code 的文件，讓新接觸的人，可以比較快瞭解 source code。
• e.g. listitem 的文件說明
  

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

• unit test 的作用為何？
  • 驗證 list.h 所提供的 functions。
• 軟體工程來說的精神為何？
  • 減少開發與維護成本。
  • 出現 bug 時，可以排除是這些 functions 照成。

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

實作出 merge sort

Implement the recursive list_merge_sort() function

static void list_merge_sort(struct list_head *head, size_t merge_size)
{
    ...
    list_merge_sort(&list_left, i);
    list_merge_sort(&list_right, merge_size - i);
    ...

Notes

• Linux 核心設計 (Spring 2019) Wiki
• 2019q1 Homework1 (作業區)
• Linux 核心設計: 第 1 週發展回顧

Suffix Rules

.c.o:
	@echo $@
	$(VECHO) "  CC\t$@\n"
	$(Q)$(CC) -o $@ $(CFLAGS) -c -MMD -MF $@.d $<

Source 10.7 Old-Fashioned Suffix Rules

• .c.o:
  • if you define a rule whose target is ‘.c.o’, make takes it to be a double-suffix rule with source suffix ‘.c’ and target suffix ‘.o’.