Try   HackMD

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

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →
jserv

  1. 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」是否總是正確

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →
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):
    • membertype 類型裡的 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_safelist_for_each 的差異在哪?"safe" 在執行時期的影響為何?

11. for_each 風格的開發方式對程式開發者的影響為何?

​​​​* 提示:對照其他程式語言,如 Perl 和 Python

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

​​​​* 提示: 對照看 Doxygen

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

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


實做 merge sort

  • 支援 qtest
tags: homework