2019q1 Homework1 (list)

contributed by < joey-ycpeng >

自我檢查事項

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

Anwser:

1. macro 等於把程式碼嵌入展開(ref: Macro-Expansion)執行，不需要 call function 所需的 overhead

「展開」(expand) 和「嵌入」(embed) 這兩個詞彙意義不同，回頭看 C preprocessor 用了哪個詞。工程人員用語務必精準，及早脫離「文組^TM」
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

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

Yu-Cheng PengTue, Mar 5, 2019 12:26 AM
根據 System V ABI - AMD64 Architecture Processor Supplement

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 有何作用？在程式碼中扮演什麼角色？

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 將轉型的指標變成整個 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 大/小元素 呢？又，你打算如何實作？

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