2019q1 Homework1 (list)

contributed by < ldotrg >

tags: linux2019

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

• 使用 marco 可以減少執行時期 操作satck 所需的記憶體與時間成本

在 header 中使用 inline 時，常搭配 static 出現，這樣的 static inline 函式搭配編譯器最佳化，則有 macro 的效果，並得以進行參數形態檢查

TODO: 做實驗檢查

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

1. 新增一個Character device linux/cdev.h

INIT_LIST_HEAD

Kernel Module 要註冊使用 char device 就必須新增一個 list head.

void cdev_init(struct cdev *cdev, const struct file_operations *fops)
{
	memset(cdev, 0, sizeof *cdev);
	INIT_LIST_HEAD(&cdev->list);
	kobject_init(&cdev->kobj, &ktype_cdev_default);
	cdev->ops = fops;
}

list_add

每次 user space 呼叫 open 裝置檔(/dev/xxx), 就會增加一個node.
Linux Code

static int chrdev_open(struct inode *inode, struct file *filp)
{
	const struct file_operations *fops;
	struct cdev *p;
	struct cdev *new = NULL;
	int ret = 0;

...
		if (!kobj)
			return -ENXIO;
		new = container_of(kobj, struct cdev, kobj);
		spin_lock(&cdev_lock);
		/* Check i_cdev again in case somebody beat us to it while
		   we dropped the lock. */
		p = inode->i_cdev;
		if (!p) {
			inode->i_cdev = p = new;
			list_add(&inode->i_devices, &p->list);
			new = NULL;
		} else if (!cdev_get(p))
			ret = -ENXIO;
	} else if (!cdev_get(p))
		ret = -ENXIO;
	spin_unlock(&cdev_lock);
	cdev_put(new);
	if (ret)
		return ret;
...
}

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

typeof 允許我們傳入一個變數，代表的會是該變數的型態。
舉例來說：

int a;
typeof(a) b = 10; // equals to "int b = 10;

char s[6] = "Hello";
char *ch;
typeof(ch) k = s; // equals to "char *k = s;

Real world Example: 為了避免重複呼叫函式f第三次

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

max(f(1), f(2));

解釋以下巨集的原理

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

Why we need the container_of?
If strcut x contains y, we could find the pointer to x given the pointer to y

拆解

__extension__

翻閱 gcc 文件中的 Alternative Keywords 提到

You can prevent such warnings within one expression by writing __extension__ before the expression.

GNU C Extension裏面有使用到非標準的ANSI C的語法, 因此會產生警告.
如果不想要看見這個警告，只要在表達式之加入__extension__修飾字.

__typeof__

gcc 文件中的 Alternative Keywords 可以得知__是為了相容性考量而加的，作用和 keyword typeof 相同，在 Typeof 章節中可以得知 typeof 是用來獲取變數的型別。

((type *) 0)->member

照理來說 NULL pointer dereference 應該會出錯.

The operand of typeof is evaluated for its side effects if and only if it is an expression of variably modified type or the name of such a type.
黑人問號？？

offsetof

找出 C99 規格中對應的說明。注意 offsetof

jserv

macro 定義

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

這裡的 &((TYPE *)0)->MEMBER 並不是求值後取地址，struct 中的成員變數地址是相對於 struct 的初始地址的，並且編譯時期就可以確定也就沒必要在運行時求值了，所以在此得到的是 0 + offset of MEMBER in struct

將

$0$ 改成

$n\in N$,會發現回傳值會增加

$n$

延伸閱讀： How to Use C's offsetof() Macro

{} compound statement

第一次看到時覺得很奇怪，這 macro 到底要怎麼 return(廣義上的) 結果阿?
gcc docs 的 Statement-Exprs 章節中提到，這被稱為 compound statement 且回傳值是最後一個 expression 的結果

The last thing in the compound statement should be an expression followed by a semicolon; the value of this subexpression serves as the value of the entire construct.

(type *) ((char *) __pmember - offsetof(type, member));

• Run yourself:

#include <stdio.h>
#define pointer(T)  typeof(T *)
#define array(T, N) typeof(T [N])
#define my_offsetof(TYPE, MEMBER) ((size_t)&((TYPE *)0)->MEMBER)
#define my_container_of(ptr, type, member) \
    __extension__({ \
          const __typeof__(((type *) 0)->member) *__ptrmember = (ptr); \
          (type *) ((char *) __ptrmember - my_offsetof(type, member));\
    })

__attribute__((packed, aligned(4))) struct hello {
    int aa; 
    int bb; 
    unsigned long cc; 
    int *dd;
};
int main (char *argv[], int argc) {
    int aa; 
    __typeof__(aa) bb; 
    struct hello hel_obj;
    array (pointer (char), 4) y;
    aa = 5566;
    bb = 7788;
    printf("%d/%d sizeof y: %d \n", aa, bb, sizeof(y));
    printf("pointer of member dd 0x%x\n", &hel_obj.dd);
    printf("pointer of hel_obj: 0x%x\n", my_container_of(&hel_obj.dd, struct hello, dd));
    return 0;
}

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

LIST_POISONING 這樣的設計有何意義？

#ifdef LIST_POISONING
    node->prev = (struct list_head *) (0x00100100);
    node->next = (struct list_head *) (0x00200200);
#endif

故意將已刪除節點的指標指向特定的位址.
這些特別的位址可以作為分析kernel panic

Reference: Kernel Debugging wiki

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

• 用
  $O(1)$ 的時間複雜度將新節點插入至尾端,無須走訪全部節點.
• 可參考list_add_tail實做

​static inline void list_add_tail(struct list_head *node, struct list_head *head)
{
​   // 1. get the tail node
​   struct list_head *prev = head->prev; 
​   // 2.  update tail node
​   prev->next = node;
​   // 3. Update new node
​   node->next = head;
​   node->prev = prev;
​   // 4. Update the head
​   head->prev = node;
}

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

Implementation Merge Sort

• list_split
  • 利用fast與slow pointer找到需要切割的點
  • 再使用list_cut_position 分成左右兩半的list
• list_merge
  • leetcode經典題,merge two sorted list, merge K sorted list
  • 動畫 https://www.youtube.com/watch?v=odUJXFJR6Q4
  • 使用的list工具：list_splice_tail,list_first_entry , list_move_tail
• list_merge_sort
  其實最難的不是實做,而是要怎麼測試

1. 在實做時,當然先用最簡單的printf觀察排序結果.
2. 接著通過題目的基本測試

• 以上基本的流程通過後,接著就是要測試效能啦(ToDo)
• 研究unit test 的技巧(ToDo)
• 導入像lab0作業的自動評分系統qtest(ToDo)

想要做的事情好多阿

Original Assignment info: F02: list

tags: Linux Linked List