2018q3 Team work (quiz4)

# 2018q3 Team work (quiz4) ###### tags: `System-Software-2018` Contributed by < [DyslexiaS](https://github.com/DyslexiaS), [siahuat0727](https://github.com/siahuat0727), [pjchiou](https://github.com/pjchiou) > ## [第 4 週測驗題(上)](https://hackmd.io/s/HyyxpJE5X) ### 題目與解答 + 利用**二補數**特性完成無分支版本的 `abs()` (取絕對值) ```c #include <stdint.h> int64_t abs64(int64_t x) { int64_t y = x >> (64 - 1); return (x ^ y) - y; } ``` ### 想法 [解說](https://www.youtube.com/watch?v=9_15-3BQQI8) - 在二補數下有一個重要的關係式 **x + ~x = -1**，即==任何數與其補數相加為 -1== 舉例來說，若以占 1 byte 的有號整數做為例子來看，下方左邊為 5 ；右方為其補數 = -6 。因此若要得到變號的值要做 `~x+1`。 ```graphviz digraph byte{ node [shape=record] posi [label="0|0|0|0|0|1|0|1"] nega [label="1|1|1|1|1|0|1|0"] } ``` - `>>` 運算在規格書的描述 >規格書 **6.5.7 Bitwise shift operators** >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 $\frac{E1}{ 2^{E2}}$. If E1 has a signed type and a negative value, the resulting value is implementation-defined. 由以上描述得知， - E1 是 unsigned 或 nonnegative signed 時， `E1 >> E2` 其值為 $E1/2^{E2}$ 。 - E1 是 signed 且 negative ，是 implementation-defined。也就是有兩種可能性，補 sign bit 或補 `0`。 `^`(XOR)運算子的行為如果從文氏圖來看，蠻難以理解這跟補數運算有什麼關係。 ![](https://i.imgur.com/ujTgxIg.png) 如果從下表就很清楚了，遇到 `0` 不變，遇到 `1` 時變，這樣子就很容易理解，==任何數跟 `-1` 做 XOR 運算時，每一位都變，就相當於補數運算==。 |x|y|$\oplus$| |:-:|:-:|:-:| |0|0|0| |1|0|1| |0|1|1| |1|1|0| 1. 對一個數做絕對值之前，要先得知此數的正負號， `int64_t y` 就是取得 `x` 的 sign bit - 正整數： `y = 000000...0000` - 負整數： `y = 111111...1111` 顯然，如果以上函式在對負數做 Right shift ，會將前面補 `0` 的情況下(logical right shift)就會錯誤。 2. 接著，`x` $\oplus$ `y` :`(x^y)` 對於原本就是正整數的數值不會有影響，前面提到可以將 XOR 運算看成遇到 `0` 不變，遇到 `1` 切換。遇到每一個 bit 都是 1 時，相當於補數運算。 3. 對於原本是負數的數值，在二補數的機制下，**x + ~x = -1** ，因此 **-x = ~x + 1** ，就是函式最後 `(x^y)-y` （將 bits 反轉再 $- (-1)$) ### 延伸問題 #### 1. overflow/underflow 問題要探討 overflow/underflow 的情況，通常都在數值為極端值時才會發生。 **判斷時可能會有問題** 有號整數的值域負數會比正數還多一個，這時候當 `value` 為最小負整數的時候，如果直接用 `-value == abs64(value)` 來判斷函式是否正確的話，在前面的 `-value` 就已經得到跟期望中不同的值了。因此我先轉成 double 、然後相減，判斷結果是否小於一個極小的值。我分別用正數最大、正數最小、負數最大、負數最小以及 0 代入。 ```clike=1 #include <stdint.h> #include <stdio.h> #define epsilon 1e-10 #define compare(value) \ (value < 0 ? -(double) value : (double) value) - abs64(value) < epsilon \ ? "pass" \ : "failed" #define Test(value) printf("Test value: %ld\t%s\n", value, compare(value)) int64_t abs64(int64_t x) { int64_t y = x >> (64 - 1); return (x ^ y) - y; } int main(){ int64_t NegMax = 0xffffffffffffffff, NegMin = 0x8000000000000000, PosMax = 0x7fffffffffffffff, PosMin = 1, Zero = 0; Test(NegMax); Test(NegMin); Test(PosMax); Test(PosMin); Test(Zero); return(0); } ``` 從前述的規則來看， `y = x >> (64-1)` 沒問題，都會補 sign bit，但後方的 `(x^y) - y` 就不行了，在負最小的時候會 underflow 。其輸出為 :::success Test value: -1 pass Test value: -9223372036854775808 failed Test value: 9223372036854775807 pass Test value: 1 pass Test value: 0 pass ::: --- #### 2. pseudo-random number generator (PRNG) 搭配下方 pseudo-random number generator (PRNG) 和考量到前述 (1)，撰寫 abs64 的測試程式，並探討工程議題 (如：能否在有限時間內對 int64_t 數值範圍測試完畢？) - 概念 PRNG都是通過一個內部狀態來進行運算，生成一個**看似隨機**的數列。常見的PRNG算法分為加密和不加密兩類，不加密算法一般比加密算法更快，但是不能在需要安全的情況下使用。各種算法的[優劣比較](http://gad.qq.com/article/detail/10069)，現在最廣泛被應用的算法為[線性同餘法（LCG）](https://blog.csdn.net/dukai392/article/details/71155740) - 利用 xorshift64 方式快速產生亂數 ```C static uint64_t r = 0xdeadbeef int64_t rand64() { r ^= r >> 12; r ^= r << 25; r ^= r >> 27; return (int64_t) (r * 2685821657736338717); } ``` >[code 說明](https://forum.mikrotik.com/viewtopic.php?t=100868) >constant 2685821657736338717LL which has a hex representation of 2545f491 4f6cdd1d where the space indicates the 32 bit boundary. This means that the largest multiplication result within a "32bit half" is 4f6cdd1d * (2**32 -1 ) < 4f6cdd1d00000000. Thus overflow will never occur. Note that additions are done only using 32-bit halves thus overflow can never occur. - 實做 **Code：** ```clike= #include <stdio.h> #include <stdint.h> #include <inttypes.h> #include <time.h> #define check_abs(x){ \ if (abs64(x)<0) \ printf("Overflow: %+"PRId64"\n", x); \ } int64_t abs64(int64_t x) { int64_t y = x >> (64 - 1); return (x ^ y) - y; } static uint64_t r = 0xdeadbeef; uint64_t rand64() { r ^= r >> 12; r ^= r << 25; r ^= r >> 27; return (uint64_t) (r * 2685821657736338717LL); } int main(){ time_t t1 = clock(); for(long long i=0; i<INT32_MAX; ++i){ check_abs(rand64()); } time_t t2 = clock(); printf("Time : %lf sec\n", (t2 - t1)/(double)(CLOCKS_PER_SEC)); return 0; } ``` **Output：** ```shell gcc int64_abs.c -o int64_abs ./int64_abs Time : 37.095627 sec ``` **gcc 優化：** ```shell gcc int64_abs.c -o int64_abs -O3 ./int64_abs Time : 19.307838 sec ``` 改成 Unrolling： ```clike= for(long long i=0; i<UINT32_MAX; i+=4){ check_abs(rand64()); check_abs(rand64()); check_abs(rand64()); check_abs(rand64()); } ``` ```shell ./int64_abs Time : 12.868990 sec ``` 測試 Unrolling 次數 ```shell ./int64_abs unrolling 4, Time : 12.868990 sec unrolling 8, Time : 12.193703 sec unrolling 16, Time : 11.810844 sec unrolling 32, Time : 11.615933 sec ``` Unrolling 的次數在數度上的提昇很有限 - 推測： `UINT32_MAX` 到 `UINT64_MAX` 還需要乘上 $2^{32}$ ，因此取秒數 $12*2^{32}$ 得出 51539607552 sec，換算一下大約為 1634 年，上面驗證絕對值的 `check_abs()` 也寫得很簡略，所以實際上會花更多時間來測試所有數值。 #### 3. 在 GitHub 找出類似用法的專案並探討，提示：密碼學相關 >使用 `[]()` 列出共筆作者(GitHub ID) 與標題 >[name=課程助教][color=red] 這裡統整了其他同學找到的資料： [<`jesus255221`> Timing-attack](https://hackmd.io/YdbQ2ubBRk63apUNpcYdOA#Timing-attack) [<`dange0`> 現實中的 Interger Overflow](https://hackmd.io/s/ByYJlgws7#%E7%8F%BE%E5%AF%A6%E4%B8%AD%E7%9A%84-Interger-Overflow) ## [第 4 週測驗題(中)](https://hackmd.io/s/Syl6me49Q) ### 題目與解答考慮測試 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(); } ``` ==答案==：只要函式 `g` 沒有對 `global_var` 指標作 dereference，那麼 TCO 就有機會 - TCO：這種做法不只加快效率，也避免了可能 Stack Overflow 等問題。使用尾遞歸可以帶來一個好處：因為進入最後一步後不再需要參考外層函數（caller）的信息，因此沒必要保存外層函數的 stack，遞歸需要用的 stack 只有目前這層函數的，因此避免了 Stack Overflow 風險。 - 解釋因為在做 TCO 時會把 caller 的 stack 捨棄掉，但如果函式 `g` 對 `global_var` 指標作 dereference ，也就表示會用到函式 `f` 裡的變數 `x` ，若使用到外部變量將無法做 TCO ### 想法 #### TCO 與 tail recursion 原理若 g 函式內沒有對其做 dereference 則編繹器有機會對其做 TCO，以下有一些對 TCO 的資料。 - [wiki pedia](https://zh.wikipedia.org/wiki/%E5%B0%BE%E8%B0%83%E7%94%A8) - [Tail Recursion](https://www.geeksforgeeks.org/tail-recursion/) - [Tail Call Elimination](https://www.geeksforgeeks.org/tail-call-elimination/) 其中，有一種特殊的型式是 Tail Recursion Optimization ，意即利用編繹器最佳化讓遞迴呼叫轉為一般的迴圈或用 `goto` 取代，可以大幅節省記憶體、提高可讀性。如何判斷是否可以被轉為 Tail recursion 呢? - 在[什麼是尾端遞迴](http://cch125.blogspot.com/2015/11/tail-recusion.html)一文中寫著 * 普通 recursion：典型的遞迴就是一個函式直接或是間接的調用自己，接著利用函式回傳的值計算出結果。假如使用這個方法，==在還沒得到每一個遞迴函式回傳值之前，沒有辦法計算出最後的結果==。 * Tail recursion：不同於普通的recursion，tail recursion是指一個函式在其尾端調用自己，而其==結果被直接傳回，也就不需要等待每個函式回傳值==。 - [How does compiler know whether the recursion is a tail recursion or not and how does it optimize tail recursion?](https://www.quora.com/How-does-compiler-know-whether-the-recursion-is-a-tail-recursion-or-not-and-how-does-it-optimize-tail-recursion) 提到 stack frame 內有的資訊就是 * local variable * return address 如果還需要保留這兩個東西，那就沒辦法做 Tail recursive optimization ，以下例子都沒辦法做最佳化，就是因為還得保留區域變數或 return address 來找到 y 與常數 1 。 ```javascript= function foo(a, b, c) { let x = a + b * c; let y = baz(a, b); return y + bar(x, x + 1); //Have to keep y } function foo(a, b, c) { let x = a + b * c; return 1 + bar(x, x + 1); //Have to keep address to find constant 1 } ``` 用這樣的觀念，來重新看一次這個測式的程式。先用 ``` gcc -E -g main.c first.c second.c > code.c ``` 讓前置處理器整理一下程式。 ```clike=1 void second_zero (void) { second_ra = __builtin_return_address(0); } void first_zero(void) { first_ra = __builtin_return_address(0); second_zero(); } void second_one (int a) { second_ra = __builtin_return_address(0); } void first_one(int a) { first_ra = __builtin_return_address(0); second_one(0); } void second_zero_one (int a) { second_ra = __builtin_return_address(0); } void first_zero_one(void) { first_ra = __builtin_return_address(0); second_zero_one(0); } void second_one_zero (void) { second_ra = __builtin_return_address(0); } void first_one_zero(int a) { first_ra = __builtin_return_address(0); second_one_zero(); } ``` 前四種很單純不意外，可以做 TCO - 呼叫函式是最後一個 expression - 沒有需要留下的區域變數。 - 也沒有 return value ，不需要等。接下來看後面四個函式，原本只有三個，因為我對結果覺得怪，所以加了一個作為驗證。 ```clike=1 char second_ret_int_char(void) { second_ra = __builtin_return_address(0); return 0; } int first_ret_int_char(void) { first_ra = __builtin_return_address(0); return second_ret_int_char(); } int second_ret_char_int(void) { second_ra = __builtin_return_address(0); return 0; } char first_ret_char_int(void) { first_ra = __builtin_return_address(0); return second_ret_char_int(); } int second_ret_void_int(void) { second_ra = __builtin_return_address(0); return 0; } void first_ret_void_int(void) { first_ra = __builtin_return_address(0); second_ret_void_int(); } int second_ret_int_int(void) { second_ra = __builtin_return_address(0); return 0; } int first_ret_int_int(void) { first_ra = __builtin_return_address(0); return second_ret_int_int(); } ``` 這邊測試的結果是 :::success char return to int: no TCO int return to char: no TCO int return to void: TCO int return to int: TCO ::: 對於前兩個無法做 TCO ，本來感到很意外，明明也都符合上述的條件，除了有 return value 之外，看起來沒有等待內層函式 return 的需要，我懷疑是型別轉換的關係，寫了第四做作為對照，果然可以做 TCO，前兩個函式會看成以下。 ```clike=1 char second_ret_int_char(void) { second_ra = __builtin_return_address(0); return 0; } int first_ret_int_char(void) { first_ra = __builtin_return_address(0); return (int)second_ret_int_char(); } int second_ret_char_int(void) { second_ra = __builtin_return_address(0); return 0; } char first_ret_char_int(void) { first_ra = __builtin_return_address(0); return (char)second_ret_char_int(); } ``` ### TCO 解構這裡是以比較 caller（first_xxx）和 callee（second_xxx）的 return address，來判斷是否發生 TCO。（若兩者相同則表示呼叫 function 時沒有創建新的 stack frame => 發生 TCO） --- :heavy_check_mark: TCO ```C void second_zero (void) { second_ra = __builtin_return_address(0); } void first_zero (void) { first_ra = __builtin_return_address(0); second_zero(); } ``` TCO 之前：(optimization flag `-O`) ``` <first_zero>: sub $0x8,%rsp mov 0x8(%rsp),%rax mov %rax,0x20083d(%rip) # 201018 <first_ra> callq 88e <second_zero> add $0x8,%rsp retq ``` 詳細過程如下： 1. caller of `first_zero` 把 pc push 進 stack 之後跳到 `first_zero` 2. 執行 `first_zero` 3. `first_zero` 把 pc push 進 stack 之後跳到 `second_zero` 4. 執行 `second_zero` 5. `second_zero` 把 pc 從 stack pop 出來（回到 `first_zero`） 6. `first_zero` 把 pc 從 stack pop 出來（回到 caller of `first_zero` ）由於過程 5 和 6 之間沒做任何事情，因此過程可以進行所謂的 TCO 簡化如下： 1. caller of `first_zero` 把 pc push 進 stack 之後跳到 `first_zero` 2. 執行 `first_zero` 3. `first_zero` 直接跳到 `second_zero` (沒有把目前的 pc 存起來當作 callee 的 return address) 4. 執行 `second_zero` 5. `second_zero` 把 pc 從 stack pop 出來（直接回到 caller of `first_zero`） _這裡所謂的 "把 pc 從 stack pop 出來" 是指把 pc 設成 stack 的 top（剛好是之前某時刻的 pc 值）後 pop stack_ 進行 TCO 後：(optimization flag `-O2`) ``` <first_zero>: mov (%rsp),%rax mov %rax,0x2007ad(%rip) # 201018 <first_ra> jmpq 910 <second_zero> ``` --- :x: TCO ```C char second_ret_int_char (void) { second_ra = __builtin_return_address(0); return 0; } int first_ret_int_char (void) { first_ra = __builtin_return_address(0); return second_ret_int_char (); } ``` ``` <first_ret_int_char>: sub $0x8,%rsp mov 0x8(%rsp),%rax mov %rax,0x200748(%rip) # 201018 <first_ra> callq 950 <second_ret_int_char> add $0x8,%rsp movsbl %al,%eax retq ``` 這裡因爲 return type 的不同，導致 function call 之後不只是 pop stack frame 和 return，還有轉型 `movsbl %al,%eax` （根據 `%al` 的 signed bit 設置 `%eax` 的高 24 位），所以沒辦法 TCO。這是因爲若直接 `jmpq <second_ret_int_char>`，`second_ret_int_char` 只會設定 `%eax` 的低 8 位 `%al`，但 `first_ret_int_char` 的 caller 可以使用整個 `%eax`。 --- :x: TCO :question: ```C int second_ret_char_int (void) { second_ra = __builtin_return_address(0); return 0; } char first_ret_char_int (void) { first_ra = __builtin_return_address(0); return second_ret_char_int (); } ``` ``` <first_ret_char_int>: sub $0x8,%rsp mov 0x8(%rsp),%rax mov %rax,0x200728(%rip) # 201018 <first_ra> callq 960 <second_ret_char_int> add $0x8,%rsp retq ``` 這裡是 int 轉 char，不需要額外的指令轉型（caller of first_ret_char_int 只會讀 `%eax` 的低 8 位 `%al`），所以其實是有機會進行 TCO 的。改用 clang 測試，發現結果也一樣。 >這表示 compiler 還有進步的空間？ ### Android 原始程式碼內使用 __builtin_return_address 的案例在 [panic.c](https://android.googlesource.com/kernel/common/+/android-3.10/kernel/panic.c) 中有利用這個函式來做 debug ，輸出 stack 的位置。 ```clike void __stack_chk_fail(void) { panic("stack-protector: Kernel stack is corrupted in: %p\n", __builtin_return_address(0)); } ``` ### 延伸問題 :::success 延伸問題: 1. 探討 TCO 和遞迴程式的原理 2. 分析上述實驗的行為和解釋 gcc 對 TCO 的操作 3. 在 [Android 原始程式碼](https://android.googlesource.com/) 裡頭找出 [__builtin_return_address](https://gcc.gnu.org/onlinedocs/gcc/Return-Address.html) 的應用並解說 ::: --- ## [第 4 週測驗題(下)](https://hackmd.io/s/By7Lwz4qm) ### 題目與解答以下程式碼編譯並執行後，在 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); } ``` ==答案：== `ptr1.c` 在執行時期，對 NULL pointer 做 derefrence 操作，會造成 Segmentation fault - [ ] `ptr2.c` ```C int main() { return &*((int *) 0); } ``` ==答案：== `ptr2.c` 是合法 C 程式，`&*` 抵銷回傳 `(int *) 0` ，故回傳為 `0`，在執行後可透過 `echo $?` 得到 exit code 為 `0` - [ ] `ptr3.c` ```C #include <stddef.h> int main() { return &*NULL; } ``` ==答案：== `ptr3.c` 是合法 C 程式，`&*` 抵銷回傳 `NULL` ，因此在執行後可透過 `echo $?` 得到 exit code 為 `0` - [ ] `ptr4.c` ```C #include <stddef.h> int main() { return &*(*main - (ptrdiff_t) **main); } ``` ==答案：== - `ptr4.c` 是合法 C 程式，在執行後可透過 `echo $?` 得到 exit code 為 `0` - `**main` ， `main` 本來是一個 function designator ，但因為不是搭配 `&`， `sizeof` 使用，所以會被轉成為 pointer to function，再被 * 轉成 function designator，然後又和 `*` 重複做一次上述步驟，最後才被 compiler 轉成 pointer to function - `ptrdiff_t` 是二個指標相減結果所擁有的有符號整數類型 - `&*` 抵銷，`(*main - (ptrdiff_t) **main)` 都是指向 `main` 的指標，因此相減為 `0` ### 延伸問題 #### 1. 參照 C 語言規格書，充分解釋其原理 - 對於一個無效的值做 dereference 是個為定義的行為 >C99[6.5.3.2] >If an invalid value has been assigned to the pointer, the behavior of the unary * operator is undefined. :::success - 對一個數同時做 dereferencd 和 reference `&* x` ，可以將兩個一起抵銷，但是省略之後原本的數會變成 **lvalue** ::: - `(int *)0` is not an integer constant expression, although it is a constant expression. >C99 [6.5.3.2] >If the operand is the result of a unary * operator, neither that operator nor the & operator is evaluated and the result is as if both were omitted, except that the constraints on the operators still apply and the result is not an lvalue. #### 2. 解析 clang/gcc 編譯器針對上述程式碼的警告訊息 **Code：** ```C int main() { return &*((int *) 0); } ``` **Output：** ```shell warning: return makes integer from pointer without a cast [-Wint-conversion] int main() { return &*(int *) 0; } ^~~~~~~~~~~ ``` **Analysis：** `&*` 抵銷之後，剩下的 `(int *) 0` 是 pointer，但回傳型態是 `int` ，把回傳型態改成 `int*` 便不會出現 warning --- **Code：** ```C #include <stddef.h> int main() { return &*NULL; } ``` **Output：** ```shell warning: dereferencing ‘void *’ pointer int main() { return &*NULL; } ^ warning: return makes integer from pointer without a cast [-Wint-conversion] int main() { return &*NULL; } ^ ``` **Analysis：** 第一個 warning，`void *` is called a null pointer constant，不可以對 `void*` 取值，因此需要先做 cast 第二個 warning和上面那題一樣，把回傳型態 `int` 改成 `int*` ```clike #include <stddef.h> int* main() { return &*(int *)NULL; } ``` 從規格書可以發現，`main` 的應爲 `int`，因此比較好的改法應該是： ```clike #include <stddef.h> #include <stdint.h> int main() { return (intptr_t)(void*)&*(int *)NULL; } ``` [爲什麼要先轉成 `void*` ？](https://docs.google.com/document/d/12cR0qb-kl7jB8RA_eHQu8OSmGKEOshwLeX4Mx5qBzUE/edit?pli=1#bookmark=id.96t1jak51zgw) > **C99 Standard (§ 5.1.2.2-1)** **Program startup** **1** The function called at program startup is named main. The implementation declares no prototype for this function. It shall be defined with a return type of int and with no parameters: **`int main(void) { /* ... */ }`** or with two parameters (referred to here as argc and argv, though any names may be used, as they are local to the function in which they are declared): **`int main(int argc, char *argv[]) { /* ... */ }`** or equivalent; 9) or in some other **implementation-defined manner**. ##### `&*` 不是單純抵消 >**C99 Standard (§ 6.5.3.2-3)** The unary & operator yields the address of its operand. If the operand has type ‘‘type’’, the result has type ‘‘pointer to type’’. If the operand is the result of a unary * operator, neither that operator nor the & operator is evaluated and the result is as if both were omitted, except that the constraints on the operators still apply and the result is not an lvalue. 留意到上述描述中，except that the **constraints on the operators still apply** and **the result is not an lvalue**，前者表示 `&*` 不能加在任意位置，後者表示會造成結果不是 lvalue。舉例： ```C #include <stdio.h> int main() { int *ptr; ptr = NULL; return 0; } ``` 合法。 --- **constraints on the operators still apply** ```C #include <stdio.h> int main() { int *ptr; ptr = NULL; return &*0; } ``` ``` error: invalid type argument of unary ‘*’ (have ‘int’) return &*0; ^~ ``` --- **the result is not an lvalue** ```C #include <stdio.h> int main() { int *ptr; &*ptr = NULL; return 0; } ``` ``` error: lvalue required as left operand of assignment &*ptr = NULL; ^ ``` --- #### 3. 思考 `Segmentation fault` 的訊息是如何顯示出來，請以 GNU/Linux 為例解說。提示: Page fault handler ### Segmentation fault (pjchiou) [What is segmentation fault](https://stackoverflow.com/questions/2346806/what-is-a-segmentation-fault) 中說明當 accessing memory that “does not belong to you.” [Core Dump](https://www.geeksforgeeks.org/core-dump-segmentation-fault-c-cpp/) 一文指出常見造成的原因有以下 - 修改 string literal - Access 已經 free 的空間 - Dereference 一個**越界**的指標程式在執行的時候都是使用虛擬記憶體，這些虛擬記憶體透過 Memory Management Unit(MMU) 對應到實際上的記憶體位置。當程式存取已在虛擬記憶體中，但尚未在實體記憶體中的資料時，就會發生 page fault，這時 CPU 會發出 interrupt 給作業系統，page fault 一共有三種，各自有不同的應對機制。==page fault 並不是一個 error ，這是一個使程式增加可用記憶體的正常機制==。 - Minor : 想存取的資料實際上已經讀進實體記憶體，但沒有在 MMU 註冊，這時要做的事只有將其註冊到 MMU 中，使虛擬記憶體可以對應到實體記憶體。 - Major : 想存取的資料真的不在實體記憶體中。 - 就尋找一個 free 的空間，將需要的資料從硬碟讀進來，並在 MMU 中註冊。 - 或其他程式暫時不用的空間，將其原有資料寫回硬碟，註銷其在 MMU 中的記錄，再把所需要的資料從硬碟讀入。 - Invalid : 嘗試取用不在虛擬記憶體的位址，這時 MMU 無法透過這個位址對應到實體記憶體，就會產生 segmentation fault 並且結束該程式。 Linux 對於 Invalid page fault 的處理機制是發出一個 SIGSEGV 訊號到該程式，而 linux 有一個預設的 function 去處理。[How to handle SIGSEGV, but also generate a core dump](http://www.alexonlinux.com/how-to-handle-sigsegv-but-also-generate-core-dump) 一文中有一段程式碼，我將其稍做修改後如下。 ```clike=1 #include <stdio.h> #include <sys/types.h> #include <unistd.h> #include <signal.h> void sighandler(int signum) { printf("Test process %d got signal %d\n", getpid(), signum); signal(signum, SIG_DFL); kill(getpid(), signum); } int main() { signal(SIGSEGV, sighandler); *((char *)0) = 0; return (0); } ``` 先利用 signal 函式，把接到 SIGSEGV 訊號時執行我自定的函式，在這個自定函式中，再用 signal 函式把收到 SIGSEGV 時的行為導回預設函式，再自己發一個 SIGSEGV 給自己。 `man 7 signal` 的內容中，寫 SIGSEGV 對應到的預設函式，其行為是終止 process 並且 dump core 。參考資料 - [wiki pedia](https://en.wikipedia.org/wiki/Page_fault) - [What is the default behavior of the page fault handler?](https://www.quora.com/What-is-the-default-behavior-of-the-page-fault-handler) --- ## Reference [隨機數常見算法優劣剖析](http://gad.qq.com/article/detail/10069) [Pseudo Random Number Generator Script (xorshift64* )](https://forum.mikrotik.com/viewtopic.php?t=100868) [尾調用優化](http://www.ruanyifeng.com/blog/2015/04/tail-call.html) [NULL與0的區別](https://kknews.cc/zh-tw/other/jvbymy.html)

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.