2019q1 Homework1 (list)

contributed by < fakepaper56 >

自我檢查事項

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

可由下列.c檔與其編譯出來的x86-64來描述一般function call的成本:

add.c:

int add(int a, int b) {
    return a + b;
}

int main() {
    return add(1,2);
}

add.s:

add:
    leaq (%rdi, %rsi) %rax
    ret
main:
    movel %esi 2
    movel %edi 1
    call add
    rep ret

我們必須要把參數1,2放到指定的暫存器上，並叫起add()與回到main()，這時我們又要付出一些代價在stack的操作上。

不要只寫「因為某些情況」，程式設計不是玄學，要分析就要拿出案例！

jserv

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

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

功能上有點像C++的decltype()。 在C語言上拓展了macro的實現，我們可以利用typeof做出類似template功能。下面的程式碼試著模仿了C ++的std::swap()。

#define SWAP(a,b) do{ \
    typeof(a) tmp = a; \
    a = b; \
    b = tmp; \
} while(0)

解釋以下巨集的原理

offsetof 在stddef.h的定義如下，他提供了@st中@m到＠st起始位置的距離。

#define offsetof(st, m) ((size_t)&(((st *)0)->m))

container_of則是利用指著@type中@member的指標＠ptr，來取得包含＠member的結構@type指標

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

LIST_POISONING 這樣的設計有何意義？

我們希望可以每次使用free()的時候，都是對我們曾分配過的空間。LIST_POISONING可以提醒我們free()掉一個空的東西，因為free(NULL)程式是不會出問題的(free(3)):

If ptr is NULL, no operation is performed.

但當我們free() 作用在 0x00100100 0x00200200的時候會發生page fault(但我現在還不清楚為什麼free(0x00100100)以及free(0x00200200)時一定會page fault)。

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

如果不使用的環狀的話，程式碼會變得很複雜: 在做節點操作的後，你必須知道你操作的節點是否在頭部或尾部，甚至也要考慮他的周圍。

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

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

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

除了提示所寫的 Perl 或 python 之外，C++ 也有 for_each 和 for ( : )。
這種風格可以始維護者一目了然，這是一個從頭到尾的操作。開發者也可以直接以較高抽象化的觀點來開發程式碼。

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

list_for_each_safe在進行for底下的操作前，都會紀錄下個節點的位置。如果你希望在for底下改變當前節點 next 的值(e.g 操作list_del_init())，那list_for_each_safe是比較好的選擇。

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

如下面出現在 list.h 的程式碼，＠node 的意思是指所使用的參數 node。這種風格可以清楚的取代 node, the parameter of list_del_init()，並且增加註解的維護性（ e.g 當今天我們使用後者的風格並改寫函數的名稱，可能會忘記改註解的名子）。

/**
 * list_del_init() - Remove a list node from the list and reinitialize it
 * @node: pointer to the node
 *
 * The removed node will not end up in an uninitialized state like when   using
 * list_del. Instead the node is initialized again to the unlinked state.
 */
static inline void list_del_init(struct list_head *node)
{
     list_del(node);
     INIT_LIST_HEAD(node);
}

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

unit test 顧名思義，就是做最小單位的測試，一般來說是以函數或 Macro 來做測試。軟體工程來講就是希望做好每一個環節就做測試，期望可以在開發時越早發現問題越好。

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