# 2019q1 Homework1 (list)
contributed by < `F74021200` >

## 自我檢查：

### 1. 為何 Linux 採用 macro 來實作 linked list？一般的 function call 有何成本？
在[C99 Standard](http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1124.pdf) 的 6.10.1 中，有定義 preprocessing ：The implementation can process and skip sections of source files conditionally, include other source files, and replace macros.These capabilities are called preprocessing,because conceptually they occur before translation of the resulting translation unit.，其中有提到：replace macros，即是將 macro 的 identifier 以define 中的 replacement-list 取代，這過程會在編譯成 Assembly code 前先執行；若使用 function call，須花費時間將參數與目前 program counter 儲存到 register 中，並花費時間 jump 到 function 程式碼所在的地方，等 function 執行完，又花費時間 jump 回呼叫此 function 的下一行；因此，若使用 macro ，可以避免額外的儲存時間與跳轉時間。

### 2. GNU extension 的 typeof 有何作用？在程式碼中扮演什麼角色？
由 [GNU Manual](https://gcc.gnu.org/onlinedocs/gcc/Typeof.html#Typeof) 中：Another way to refer to the type of an expression is with typeof.typeof 是用來取得 typeof 中 expression 的 type ；可以利用 typeof 來宣告變數，例如：

typeof (*x) y;

這行宣告 y 的 type 為 x 所指向空間的型態，
如果 x 的宣告為：

int *x;

則 y 的 type 就是 int 。

typeof 可以讓 macro 中對變數的宣告更彈性，以 contain_of 為例，

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

contain_of 的功能是：取得包含 ptr 這個變數的變數空間的位置，例如：
假設有個資料型態定義為：

strcut NODE{
    int n;
    struct list_head *list;
};

並宣告一個變數 node ，

struct NODE node;

另外，再宣告一個變數 list_ptr ，且讓 list_ptr 指向 node.list:

struct list_head *list_ptr;

list_ptr = node.list;

若使用 contain_of(list_ptr, strcut NODE, list) ，並用一變數取得 contain_of 的回傳值

void *re_add;

re_add = contain_of(list_ptr, struct NODE, list);

則 re_add 會得到 node 的位址。

在這個例子中，因為使用 typeof ， contain_of 這個 macro 可以用在不同的 type 而不僅限於 struct NODE

### 3. LIST_POISONING 這樣的設計有何意義？
在[這裡](https://elixir.bootlin.com/linux/v2.6.11-tree/source/include/linux/list.h) 提到：These are non-NULL pointers that will result in page faults under normal circumstances, used to verify that nobody uses non-initialized list entries.

### 4. 解釋以下巨集的原理

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

* [__extension__](https://gcc.gnu.org/ml/gcc-help/2003-06/msg00070.html)
* [const](http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1124.pdf)
* [typeof](https://gcc.gnu.org/onlinedocs/gcc/Typeof.html#Typeof)
* [offsetof](https://gcc.gnu.org/onlinedocs/gcc/Offsetof.html#Offsetof)

先宣告一個變數 __pmember ，這個變數是一個指向 member 的型態的指標；

`其中，先將 0 這個數的型態轉為指向 type 的指標，並利用 "->" 運算子得到 type 中的 member ，再利用 typeof 得到這個 member 的型態。`

將 ptr 的值賦予 __pmember ，接下來利用 offsetof 計算出在 type 這個型態中， member 這個 field 所在的位址與此型態的第一個位址的差值，並將 __pmember 的值( ptr 所指向節點的 member 的位址) 減去此差值，所得之值就是 ptr 所指向節點(型態為 type )的位址。

### 5. Linux 應用 linked list 在哪些場合？舉三個案例並附上對應程式碼，需要解說，以及揣摩對應的考量
#### 1. semaphore:
In include/linux/semaphore.h

struct semaphore {
	raw_spinlock_t		lock;
	unsigned int		count;
	struct list_head	wait_list;
};

In kernel/locking/semaphore.c
list_empty:

void up(struct semaphore *sem)
{
	unsigned long flags;

	raw_spin_lock_irqsave(&sem->lock, flags);
	if (likely(list_empty(&sem->wait_list)))
		sem->count++;
	else
		__up(sem);
	raw_spin_unlock_irqrestore(&sem->lock, flags);
}
EXPORT_SYMBOL(up);

list_head

struct semaphore_waiter {
	struct list_head list;
	struct task_struct *task;
	bool up;
};

list_add_tail

static inline int __sched __down_common(struct semaphore *sem, long state,
								long timeout)
{
	struct semaphore_waiter waiter;

	list_add_tail(&waiter.list, &sem->wait_list);
	waiter.task = current;
	waiter.up = false;

	for (;;) {
		if (signal_pending_state(state, current))
			goto interrupted;
		if (unlikely(timeout <= 0))
			goto timed_out;
		__set_current_state(state);
		raw_spin_unlock_irq(&sem->lock);
		timeout = schedule_timeout(timeout);
		raw_spin_lock_irq(&sem->lock);
		if (waiter.up)
			return 0;
	}

list_del

static noinline void __sched __up(struct semaphore *sem)
{
	struct semaphore_waiter *waiter = list_first_entry(&sem->wait_list,
						struct semaphore_waiter, list);
	list_del(&waiter->list);
	waiter->up = true;
	wake_up_process(waiter->task);
}

解說：...

#### 2. wait queue:

struct wait_queue_entry {
	unsigned int		flags;
	void			*private;
	wait_queue_func_t	func;
	struct list_head	entry;
};

struct wait_queue_head {
	spinlock_t		lock;
	struct list_head	head;
};

解說：

## merge-sort 實作：

### cmp_merge()

此函式將兩 list ， 也就是 list_1 與 list_2 作排序後，從 tmp_list 尾部加入。

void cmp_merge(struct list_head *tmp_list,
               struct list_head *list_1,
               struct list_head *list_2)
{
    struct listitem *item_1 = NULL, *item_2 = NULL;

    while (!list_empty(list_1) && !list_empty(list_2)) {
        item_1 = list_entry(list_1->next, struct listitem, list);
        item_2 = list_entry(list_2->next, struct listitem, list);
        if (item_1->i <= item_2->i)
            list_move_tail(list_1->next, tmp_list);
        else
            list_move_tail(list_2->next, tmp_list);
    }
    if (list_empty(list_1))
        list_splice_tail_init(list_2, tmp_list);
    else
        list_splice_tail_init(list_1, tmp_list);
}

### merge_sort()

將輸入的 unsorted_list 拆解為小的 list 並兩兩作排序；當有被拆解的 list 無人配對時，將此 list 與最近被 merge 的 list 作排序(位於 tmp_list 尾部)，排序完再加入 tmp_list 尾部，以保持第 n 次排序並 merge 的 list 中，由前到後，每 2^n 個數都是已排序的。

void merge_sort(struct list_head *unsorted_list)
{
    struct listitem *item = NULL;
    struct list_head tmp_list, sorted_1_list, sorted_2_list, tmp_no_merge,
        *list_ptr = NULL;
    int size = 0, n = 0, twice_n = 0;

    list_for_each_entry (item, unsorted_list, list) {
        size++;
    }

    INIT_LIST_HEAD(&tmp_list);
    INIT_LIST_HEAD(&sorted_1_list);
    INIT_LIST_HEAD(&sorted_2_list);
    INIT_LIST_HEAD(&tmp_no_merge);
    n = 1;
    twice_n = n << 1;
    while (n <= size) {
        int j = 0;
        for (int i = 0; i < size; i++) {
            if (j < n) {
                list_move_tail(unsorted_list->next, &sorted_1_list);
                j++;
            } else if (j >= n && j < twice_n) {
                list_move_tail(unsorted_list->next, &sorted_2_list);
                j++;
            } else if (j == twice_n) {
                cmp_merge(&tmp_list, &sorted_1_list, &sorted_2_list);
                j = 0;
                i--;
            }
        }
        if (!list_empty(&sorted_1_list)) {
            cmp_merge(&tmp_no_merge, &sorted_1_list, &sorted_2_list);

            if (!list_empty(&tmp_list)) {
                list_ptr = &tmp_list;
                for (int i = 0; i < twice_n; i++)
                    list_ptr = list_ptr->prev;

                list_ptr->prev->next = &tmp_list;
                sorted_1_list.prev = tmp_list.prev;
                tmp_list.prev = list_ptr->prev;
                list_ptr->prev = &sorted_1_list;
                sorted_1_list.prev->next = &sorted_1_list;
                sorted_1_list.next = list_ptr;
            }
            cmp_merge(&tmp_list, &sorted_1_list, &tmp_no_merge);
        }
        list_splice_init(&tmp_list, unsorted_list);

        n = n << 1;
        twice_n = n << 1;
    }
}

### 測試：

以 /examples/insert-sort.c 中的亂數作排序


將 dict 中的資料拿來排序，時間約為 0.638 sec