2018q3 Homework4 (assessment)

# 2018q3 Homework4 (assessment) contributed by < [allenchen8210](https://github.com/allenchen8210) > ### 測驗 `1` 考慮以下求絕對值的程式碼: ```C #include <stdint.h> int64_t abs64(int x) { if (x < 0) return -x; return x; } ``` 移除分支並善用[二補數](https://en.wikipedia.org/wiki/Two%27s_complement)特性，改寫為下方程式碼: ```C #include <stdint.h> int64_t abs64(int64_t x) { int64_t y = x A1 (A2 - 1); return (x A3 y) - y; } ``` ==作答區== 二補數可以參考[這裡](http://squall.cs.ntou.edu.tw/cprog/old/Materials/TwosComplementFormat.html) 一補數可以參考[這裡](https://zh.wikipedia.org/wiki/%E4%B8%80%E8%A3%9C%E6%95%B8) 可以發現到由正數轉成負數,由負數轉成正數，可以先取一補數再加一。例如: `a` 的二補數就是　`~a+1`。 #### 解釋運作原理其實一開始也想破頭，想了好久。對一個數想取決絕對值，需要知道他是正數還是負數。正負號表示都在最高位元。` y = x >> 63`，可以拿我們拿到 sign bit。所以 y 如果是正數 y = `0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000` 或是 y 如果是負數 y = `1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111 1111` 我們想要正數不要有任何變動，負數取一補數再加一。 bitwise operator `^`　可以幫我們做到這件事。當如果 x 是正數， `x^y = x`，當如果 x 是負數　`x^y = ~x`。最後就是加一，如果是正數，`-0`，如果是負數　`--1`。 A1 = >> A2 = 64 A3 = ^ #### [overflow/underflow](https://www.youtube.com/watch?v=XlZ952947Rw) 議題 * overflow: Sum of two positive number is "too positive" * underflow: Sum of two negative number is "too negative" 如果按照上面的定義，其實在做上面的操作，不會發生　overflow　或是　underflow　狀況。因為只有這兩種可能 * 正數+0 * 負數+1 但是再傳入　most negative number 時的確會生錯誤，會沒有變化。例如: 3 bits `100` 還會變成 `100`。　這個題目有假設在做`>>` 時，是補 sign bit。 [C99 6.5.7](http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1124.pdf) :::info The result of E1 >> E2 is E1 right-shifted E2 bit positions. If E1 has an unsigned type or if E1 has a signed type and a nonnegative value, the value of the result is the integral part of the quotient of $E1 / 2^{E2}$. If E1 has a signed type and a negative value, the resulting value is implementation-defined. ::: ### 測驗 `2` 考慮測試 C 編譯器 [Tail Call Optimization](https://en.wikipedia.org/wiki/Tail_call) (TCO) 能力的程式 [tco-test](https://github.com/sysprog21/tco-test)，在 gcc-8.2.0 中抑制最佳化 (也就是 `-O0` 編譯選項) 進行編譯，得到以下執行結果: ```shell $ gcc -Wall -Wextra -Wno-unused-parameter -O0 main.c first.c second.c -o chaining $ ./chaining No arguments: no TCO One argument: no TCO Additional int argument: no TCO Dropped int argument: no TCO char return to int: no TCO int return to char: no TCO int return to void: no TCO ``` 而在開啟最佳化 (這裡用 `-O2` 等級) 編譯，會得到以下執行結果: ```shell $ gcc -Wall -Wextra -Wno-unused-parameter -O2 main.c first.c second.c -o chaining $ ./chaining No arguments: TCO One argument: TCO Additional int argument: TCO Dropped int argument: TCO char return to int: no TCO int return to char: no TCO int return to void: TCO ``` 注意 [__builtin_return_address](https://gcc.gnu.org/onlinedocs/gcc/Return-Address.html) 是 gcc 的內建函式: > This function returns the return address of the current function, or of one of its callers. The level argument is number of frames to scan up the call stack. A value of 0 yields the return address of the current function, a value of 1 yields the return address of the caller of the current function, and so forth. When inlining the expected behavior is that the function returns the address of the function that is returned to. To work around this behavior use the noinline function attribute. > The level argument must be a constant integer. 從實驗中可發現下方程式無法對 `g` 函式施加 TCO: ```C void g(int *p); void f(void) { int x = 3; g(&x); } void g(int *p) { printf("%d\n", *p); } ``` 因為函式 `f` 的區域變數 `x` 在返回後就不再存在於 stack。考慮以下程式碼: ```C= int *global_var; void f(void) { int x = 3; global_var = &x; ... /* Can the compiler perform TCO here? */ g(); } ``` 思考程式註解，在第 8 行能否施加 TCO 呢？選出最適合的解釋。 ==作答區== * `(a)` 編譯器不可能施加 TCO * `(b)` 編譯器一定可施加 TCO * `(c)` 只要函式 `g` 沒有對 `global_var` 指標作 dereference，那麼 TCO 就有機會 Ans: 無解 #### [TC(tail call)](http://www.ruanyifeng.com/blog/2015/04/tail-call.html) * Tail Call, 簡單來說就是在函數裡最後一步是呼叫另一個函數。例如: f(x) 裡面最後一個指令是呼叫另一個函數, g(x) 為 Tail Call. ```c= function f(x){ return g(x); } ``` #### [TCO(tail call optimization)](https://stackoverflow.com/questions/310974/what-is-tail-call-optimization) * 如果在函数 A 的内部呼叫函数 B ，那麼在 A 的呼叫紀錄上方，會有一個 B 的呼叫紀錄。等到 B 结束時，將结果返回到 A ， B 的呼叫紀錄才會消失。如果函数 B 内部還呼叫函數 C，那就還有一個 C 的呼叫紀錄。所以當你呼叫越多時候，就需要紀錄越多。 * TC 因為是函數的最後一步操作，所以不需要保留外層函数的呼叫紀錄，因为呼叫位置、内部變量等資料都不會再用到了，只要直接用内層函數的呼叫紀錄，取代外層函数的呼叫紀錄就可以了。那這邊是不是有優化的可能？即 TCO ![](https://i.imgur.com/TSG5qjR.png) * ex1. ```c= function f() { int m = 1; int n = 2; return g(m + n); } f(); ``` * ex2. ```c= function f() { return g(3); } f(); ``` * ex3. ```c= g(3); ``` ex1 可以簡化成 ex2, ex2 可以簡化成 ex3, 因為呼叫 g() 之後，函數 f() 就结束了，所以執行到最後一步，完全可以删除 f() 的呼叫紀錄，只保留 g(3) 的呼叫紀錄。 --- 以下參考[同學 happyincent 的實驗](https://hackmd.io/q3kchn4xR7CHOyCW_qTO1Q?both) ```c= #include <stdio.h> void *first_ra; void *second_ra; int *global_var; int g() { second_ra = __builtin_return_address(0); // int a = *global_var; // global_var = &a; // return *global_var; } void f(void) { first_ra = __builtin_return_address(0); int x = 3; global_var = &x; g(); } int main() { f(); printf(first_ra == second_ra ? "TCO\n" : "no TCO\n"); } ``` 在以 `-O1` 編譯的情況下 * 只加第 10 行，雖然有對 `global_var` 指標做 dereference，但因為函示 return (0) 時沒有用到 `global_var` 因此輸出為 ==TCO== * 只加第 11 行，改動到 `global_var` 因此輸出為 ==no TCO== * 只加第 12 行，return 時用到 `global_var` 因此輸出為 ==no TCO== --- >從同學上面的實驗可以發現到，就算有對 global_var 指標做 dereference，也會輸出是 TCO , 因為 return 是 0. >[name=jn] >[color=purple] 重新跑了同學的實驗發現，雖然只加第 10 行，輸出是 ==no TCO==，就算不加第 10 行，也是一樣 ==no TCO==。還有需要了解一下..... ``` mec@mec-MS-7A63:~/JN_work/trash$ gcc -o1 -g test.c -o test mec@mec-MS-7A63:~/JN_work/trash$ gdb ./test GNU gdb (Ubuntu 7.11.1-0ubuntu1~16.5) 7.11.1 Copyright (C) 2016 Free Software Foundation, Inc. License GPLv3+: GNU GPL version 3 or later <http://gnu.org/licenses/gpl.html> This is free software: you are free to change and redistribute it. There is NO WARRANTY, to the extent permitted by law. Type "show copying" and "show warranty" for details. This GDB was configured as "x86_64-linux-gnu". Type "show configuration" for configuration details. For bug reporting instructions, please see: <http://www.gnu.org/software/gdb/bugs/>. Find the GDB manual and other documentation resources online at: <http://www.gnu.org/software/gdb/documentation/>. For help, type "help". Type "apropos word" to search for commands related to "word"... Reading symbols from ./test...done. (gdb) disas f Dump of assembler code for function f: 0x00000000004005b4 <+0>: push %rbp 0x00000000004005b5 <+1>: mov %rsp,%rbp 0x00000000004005b8 <+4>: sub $0x10,%rsp 0x00000000004005bc <+8>: mov %fs:0x28,%rax 0x00000000004005c5 <+17>: mov %rax,-0x8(%rbp) 0x00000000004005c9 <+21>: xor %eax,%eax 0x00000000004005cb <+23>: mov 0x8(%rbp),%rax 0x00000000004005cf <+27>: mov %rax,0x200a72(%rip) # 0x601048 <first_ra> 0x00000000004005d6 <+34>: movl $0x3,-0xc(%rbp) 0x00000000004005dd <+41>: lea -0xc(%rbp),%rax 0x00000000004005e1 <+45>: mov %rax,0x200a68(%rip) # 0x601050 <global_var> 0x00000000004005e8 <+52>: mov $0x0,%eax 0x00000000004005ed <+57>: callq 0x400596 <g> 0x00000000004005f2 <+62>: nop 0x00000000004005f3 <+63>: mov -0x8(%rbp),%rax 0x00000000004005f7 <+67>: xor %fs:0x28,%rax 0x0000000000400600 <+76>: je 0x400607 <f+83> 0x0000000000400602 <+78>: callq 0x400460 <__stack_chk_fail@plt> 0x0000000000400607 <+83>: leaveq 0x0000000000400608 <+84>: retq End of assembler dump. (gdb) [3]+ Stopped gdb ./test mec@mec-MS-7A63:~/JN_work/trash$ cat test.c #include <stdio.h> void *first_ra; void *second_ra; int *global_var; int g() { second_ra = __builtin_return_address(0); int a = *global_var; // global_var = &a; // return *global_var; } void f(void) { first_ra = __builtin_return_address(0); int x = 3; global_var = &x; g(); } int main() { f(); printf(first_ra == second_ra ? "TCO\n" : "no TCO\n"); } ``` #### 遞迴程式的原理可以參考 [寫點科普，請給指教。](https://kopu.chat/2017/08/19/%E9%81%9E%E8%BF%B4-recursive-%E4%BB%8B%E7%B4%B9%E8%88%87%E7%B6%93%E5%85%B8%E9%A1%8C%E5%9E%8B/) #### 在 Android 原始程式碼裡頭找出 __builtin_return_address 的應用並解說 [android / platform / bionic / master / . / libc / malloc_hooks / malloc_hooks.cpp](https://android.googlesource.com/platform/bionic/+/master/libc/malloc_hooks/malloc_hooks.cpp) ```c= void* hooks_malloc(size_t size) { if (__malloc_hook != nullptr && __malloc_hook != default_malloc_hook) { return __malloc_hook(size, __builtin_return_address(0)); } return g_dispatch->malloc(size); } void hooks_free(void* pointer) { if (__free_hook != nullptr && __free_hook != default_free_hook) { return __free_hook(pointer, __builtin_return_address(0)); } return g_dispatch->free(pointer); } void* hooks_calloc(size_t nmemb, size_t bytes) { if (__malloc_hook != nullptr && __malloc_hook != default_malloc_hook) { size_t size; if (__builtin_mul_overflow(nmemb, bytes, &size)) { return nullptr; } void* ptr = __malloc_hook(size, __builtin_return_address(0)); if (ptr != nullptr) { memset(ptr, 0, size); } return ptr; } return g_dispatch->calloc(nmemb, bytes); } ``` 待更新.... ### 測驗 `3` 以下程式碼編譯並執行後，在 x86_64 GNU/Linux 會遇到記憶體存取錯誤: ```shell $ cat ptr.c int main() { int *ptr = 0; return *ptr; } $ gcc -o ptr ptr.c $ ./ptr Segmentation fault: 11 ``` 分別考慮以下 4 個程式，探討其行為。 - [ ] `ptr1.c` ```C int main() { return *((int *) 0); } ``` - [ ] `ptr2.c` ```C int main() { return &*((int *) 0); } ``` - [ ] `ptr3.c` ```C #include <stddef.h> int main() { return &*NULL; } ``` - [ ] `ptr4.c` ```C #include <stddef.h> int main() { return &*(*main - (ptrdiff_t) **main); } ``` ==作答區== K1 = ? * `(a)` `ptr1.c` 在執行時期會造成 Segmentation fault * `(b)` 對於 `ptr1.c`, C 語言規格書聲明這是 undefined behavior 或者語法錯誤 * `(c)` `ptr1.c` 是合法 C 程式，在執行後可透過 `echo $?` 得到 exit code 為 `0` K2 = ? * `(a)` `ptr2.c` 在執行時期會造成 Segmentation fault * `(b)` 對於 `ptr2.c`, C 語言規格書聲明這是 undefined behavior 或者語法錯誤 * `(c)` `ptr2.c` 是合法 C 程式，在執行後可透過 `echo $?` 得到 exit code 為 `0` K3 = ? * `(a)` `ptr3.c` 在執行時期會造成 Segmentation fault * `(b)` 對於 `ptr3.c`, C 語言規格書聲明這是 undefined behavior 或者語法錯誤 * `(c)` `ptr3.c` 是合法 C 程式，在執行後可透過 `echo $?` 得到 exit code 為 `0` K4 = ? * `(a)` `ptr4.c` 在執行時期會造成 Segmentation fault * `(b)` 對於 `ptr4.c`, C 語言規格書聲明這是 undefined behavior 或者語法錯誤 * `(c)` `ptr4.c` 是合法 C 程式，在執行後可透過 `echo $?` 得到 exit code 為 `0` :::success 延伸問題: 1. 參照 C 語言規格書，充分解釋其原理 2. 解析 clang/gcc 編譯器針對上述程式碼的警告訊息 3. 思考 `Segmentation fault` 的訊息是如何顯示出來，請以 GNU/Linux 為例解說。提示: Page fault handler ::: --- - [ ] `ptr1.c` ```C int main() { return *((int *) 0); } ``` * 會造成 Segmentation fault，對 0x0 dereference，如果是只有 `int main() { return ((int *) 0); }`，不會有問題。 - [ ] `ptr2.c` ```C int main() { return &*((int *) 0); } ``` * 原來 `int main() { return &*((int *) 0); }` 等於 `int main() { return ((int *) 0); }`， `*&` 或是 `&*` 等於沒有作用。 :::success C99 Standard (6.5.3.2) Thus, &*E is equivalent to E (even if E is a null pointer), and &(E1[E2]) to ((E1)+(E2)). It is always true that if E is a function designator or an lvalue that is a valid operand of the unary & operator, *&E is a function designator or an lvalue equal to E. ::: - [ ] `ptr3.c` ```C #include <stddef.h> int main() { return &*NULL; } ``` * NULL 定義為 void *0，echo $? 得到 exit code 為 0。 - [ ] `ptr4.c` ```C #include <stddef.h> int main() { return &*(*main - (ptrdiff_t) **main); } ``` 原來的 `&*(*main - (ptrdiff_t) **main)` 等於 `(*main - (ptrdiff_t) **main)`， `*main` 與 `**main` 都會被強制轉為 function designator ，main - main 會得到 0。 :::success C99 Standard (6.5.3.2) The unary * operator denotes indirection. If the operand points to a function, the result is a function designator; if it points to an object, the result is an lvalue designating the object. If the operand has type ‘‘pointer to type’’, the result has type ‘‘type’’. If an invalid value has been assigned to the pointer, the behavior of the unary * operator is undefined. ::: ### 紀錄閱讀因為自動飲料機而延畢的那一年的啟發，特別在學習本課程 4 週之後的感想這份作業算是遲交，也不算是四週的感想，可以當作是修課的感想。老師常常說，你承受不住這些就趕快滾。想賺錢不要來當工程師，去炒股票，炒房。等等許多...。對我來說都算是很多衝擊，但人生就是這樣，這個世代，資訊來得很快，隨時都在變化，洪流般的資訊，要選擇哪些是你要的, 哪些是你可能可以做的。老師也常常講，最忌諱的就是見風轉舵，我只能苦笑，因為正好戳中我的要害，也不是說沒能力，是沒辦法承受挫折，沒有自信認為自己可以解決問題，常常想要一蹴可及的成功。想要的是在這之間找到成就感，但結果往往碰到許多挫折後，常常想要放棄，想要逃開。上完這堂課，自己還有很多欠缺的，不管是能力還是心智。我想老師在這堂課，想教的是勇於面對困難並解決它，說起來很簡單，但做起來真的不容易。這學習快結束了，明年再繼續上吧。

Syntax	Example	Reference
# Header	Header	基本排版
- Unordered List	Unordered List
1. Ordered List	Ordered List
- [ ] Todo List	Todo List
> Blockquote	Blockquote
Bold font	Bold font
Italics font	Italics font
~~Strikethrough~~	~~Strikethrough~~
19^th^	19^th
H~2~O	H₂O
++Inserted text++	Inserted text
==Marked text==	Marked text
[link text](https:// "title")	Link
![image alt](https:// "title")	Image
`Code`	`Code`	在筆記中貼入程式碼
```javascript var i = 0; ```	`var i = 0;`
:smile:		Emoji list
{%youtube youtube_id %}	Externals
$L^aT_eX$	L^aT_eX
:::info This is a alert area. :::	This is a alert area.