# 2019q1 Homework1 (list)
contributed by < `joey-ycpeng` >

## 自我檢查事項

### 1. 為何 Linux 採用 macro 來實作 linked list？一般的 function call 有何成本？
Anwser:
1. macro 等於把程式碼~~嵌入~~展開(ref: [Macro-Expansion](https://gcc.gnu.org/onlinedocs/cppinternals/Macro-Expansion.html#Macro-expansion-overview))執行，不需要 call function 所需的 overhead
:::warning
「展開」(expand) 和「嵌入」(embed) 這兩個詞彙意義不同，回頭看 C preprocessor 用了哪個詞。工程人員用語務必精準，及早脫離「文組^TM^」
:notes: jserv
:::

2. function call 有以下步驟：
1. 將 arguments 反序 push 到 stack
2. call function (push return address & jump to callee)
3. function 保留 stack 給 local variables
4. function 執行
5. function 執行完畢返回 return address

:::danger
查閱 Linux x86_64 application binary interface (ABI) 的規格，確保「將 arguments 反序 push 到 stack」是否總是正確
:notes: jserv
:::

> [name=Yu-Cheng Peng][time=Tue, Mar 5, 2019 12:26 AM]
> 根據 [System V ABI - AMD64 Architecture Processor Supplement](https://www.uclibc.org/docs/psABI-x86_64.pdf)
>> **3.2.3 Parameter Passing**
>> * "Arguments of types (signed and unsigned) *Bool, char, short, int, long, long long*, and pointers are in the **INTEGER** class."
>>
>> * "**INTEGER** This class consists of integral types that fit into one of the general purpose registers"
>> * "Passing Once arguments are classified, the registers get assigned (in left-to-rightorder) for passing as follows:
>> ... If the class is **INTEGER**, the next available register of the sequence ==*%rdi,%rsi, %rdx, %rcx, %r8* and %r9== is used."
>>
> 以此解釋下面 `call.c`：
> 1.

$ cat call.c
int callee(int a, int b, int c)
{
	return (a+b+c);
}

int main(void)
{
	callee(1, 2, 3);
	return 0;
}

$ gcc -S call.c
$ cat call.s
	.file	"call.c"
	.text
	.globl	callee
	.type	callee, @function
callee:
.LFB0:
	.cfi_startproc
	pushq	%rbp
	.cfi_def_cfa_offset 16
	.cfi_offset 6, -16
	movq	%rsp, %rbp
	.cfi_def_cfa_register 6
	movl	%edi, -4(%rbp)
	movl	%esi, -8(%rbp)
	movl	%edx, -12(%rbp)
	movl	-4(%rbp), %edx
	movl	-8(%rbp), %eax
	addl	%eax, %edx
	movl	-12(%rbp), %eax
	addl	%edx, %eax
	popq	%rbp
	.cfi_def_cfa 7, 8
	ret
	.cfi_endproc
.LFE0:
	.size	callee, .-callee
	.globl	main
	.type	main, @function
main:
.LFB1:
	.cfi_startproc
	pushq	%rbp
	.cfi_def_cfa_offset 16
	.cfi_offset 6, -16
	movq	%rsp, %rbp
	.cfi_def_cfa_register 6
	movl	$3, %edx
	movl	$2, %esi
	movl	$1, %edi
	call	callee
	movl	$0, %eax
	popq	%rbp
	.cfi_def_cfa 7, 8
	ret
	.cfi_endproc

---

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

---

### 3. GNU extension 的 [typeof](https://gcc.gnu.org/onlinedocs/gcc/Typeof.html) 有何作用？在程式碼中扮演什麼角色？
Anwser:
1. 作用: 拿到定義的 type
* e.g. `int x=0; typeof(x) y=1;`，`y`也是`int`
2. 角色:
* 讓程式不會依靠特定資料的 type 也能運作，不會因為 type 變了而需要修改
* e.g. `container_of`

---

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

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

Answer:
1. (type *) 0` :
* 一個指向位址 0 的 `type` 類型指標
2. `((type *) 0)->member)`:
* `type` 類型下的 `member`
3. `__typeof__(((type *) 0)->member)`：
* `member` 所屬的類型
4. `const __typeof__(((type *) 0)->member) *__pmember = (ptr)`:
* 宣告一個 `member` 所屬的類型常量的指標 `__pmember`
* Assign `ptr` to `__pmember`
5. `offsetof(type, member)`:
* `member` 在 `type` 類型裡的 byte offset
6. `(char *) __pmember - offsetof(type, member)`:
* 由 __pmember 所在位址往回推算到 type 類型的起點位址
7. `(type *) ((char *) __pmember - offsetof(type, member));`:
* 將起點位址轉型成指向 `type` 類型的指標
8. `__extension__({...;})`:
* `__extension__` 告訴 GCC 不要對 C 以外的擴充功能發出警告
* 小括弧（）是利用 GCC 的 [Statement-Expression](https://gcc.gnu.org/onlinedocs/gcc/Statement-Exprs.html) 將轉型的指標變成整個 macro 最後的 value
* **結論： `container_off(ptr, type, member)` 回傳一個指向 `struct type` 物件的指標，這個物件的 `member` 指向 `ptr`**

---

### 5. 除了你熟悉的 add 和 delete 操作，`list.h` 還定義一系列操作，為什麼呢？這些有什麼益處？
* 可以對 list 做 element 的增減，尋找
* 使用者不需要管實做，專注在更高層次的程式碼

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

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

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

### 9. 什麼情境會需要需要找到 [第 k 大/小元素](https://www.geeksforgeeks.org/kth-smallestlargest-element-unsorted-array/) 呢？又，你打算如何實作？

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

### 11. for_each 風格的開發方式對程式開發者的影響為何？
* 提示：對照其他程式語言，如 Perl 和 Python

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

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

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

---

## 實做 merge sort
* 支援 `qtest`

###### tags: `homework`