# 2018q3 Homework4 (assassment)
( contributed by posutsai)
## 隨堂測驗 上
- [ ]考慮以下求絕對值的程式碼:
```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;
}
```
請補完，其中 `A1` 和 `A3` 都是 operator。
---
### 想法與思考
* 直覺上會想看到在 abs 過程中的每一個階段和自己的預期是否有不同之處於是用以下程式碼簡單觀查過程中運算子的相對應行為
```C++=
// A1 is ">>", A2 is 64 and A3 is "^"
inline void hex2(std::string i, int64_t x) {
std::cout<< i << " in hexadecimal string is 0x" << std::hex << x << std::endl;
}
int64_t abs64(int64_t x) {
hex2("x", x);
int64_t y = x >> (64 - 1);
hex2("y", y);
int64_t mid1 = x^y;
hex2("x^y", mid1);
int64_t mid2 = mid1 - y;
hex2("(x^y) - y", mid2);
return mid2;
}
```
* 嘗試輸入簡單數字
```
abs64(-1):
x in hexadecimal string is 0xffffffffffffffff
y in hexadecimal string is 0xffffffffffffffff
x^y in hexadecimal string is 0x0
(x^y) - y in hexadecimal string is 0x1
```
* y 和原本設想得很不一樣，原本以為會是 `0x0000000000000001` 左邊有空缺的 bit 全部填入 `0` ，進一步去看規格書 6.5.7 中對於 shift operator 的規範。
> left shift operator
>
>The result of E1 << E2 is E1 left-shifted E2 bit positions; vacated bits are filled with zeros. If E1 has an unsigned type, the value of the result is E1 × 2E2, reduced modulo one more than the maximum value representable in the result type. If E1 has a signed type and nonnegative value, and E1 × 2E2 is representable in the result type, then that is the resulting value; otherwise, the behavior is undefined.
>
> right shift operator
>
> 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 / 2E2. If E1 has a signed type and a negative value, the resulting value is implementation-defined.
* 規格書中提到 right shift 和 left shift 對於 vacated bit 的填補行為不同，left shift 一律填補 `0`，但對於 right shift 的行為則要看實作而定。
* 更進一步在網路上搜尋相關討論，發現 shift operator 在邊界上的處理有以下 3 種策略
* [logical shift](https://en.wikipedia.org/wiki/Logical_shift)
超出邊界的位元數，會被捨棄，反之空缺的位元數會被以 `0` 填補。
* ones shift
和 logical shift 相對應，一樣捨棄超出之位元數，但以 `1` 填補。
* [arithmetic shift](https://en.wikipedia.org/wiki/Arithmetic_shift)
這類填補策略則介於上述二者之間，根據狀況決定如何填補，而這次題目中，就是善用這個策略使得絕對值的計算過程中避開了 branch prediction 。
上圖取自參考連結中，維基百科對於 arithmetic shift 的描述，從圖中可以看到右移過後的 `MSB'` 是根據右移前的 `MSB` 所決定，這也就是為何當 x 為負值時，y 會被以 `1` 填滿的原因。
* 根據[三一律](https://zh.wikipedia.org/wiki/%E4%B8%89%E5%88%86%E5%BE%8B)，在接下來的運算中分成三個狀況討論
* x > 0
* y 在右移過後會是 `0x0`
* `x ^ y` 的結果依然是 x 本身
* 故 `(x ^ y) - y` 本質上來說就是 `x - 0` ，x 若為正值則經過上述運算後依然為自己本身
* x = 0
* y 在右移過後會是 `0x0`
* `x ^ y` 的結果還是 `0`
* `(x ^ y) - y` 會轉為 `0 - 0` 仍為 `0`
* x < 0
* 經過 arithmetic shift 後， y 會變成 `0xffffffffffffffff`
* `x ^ y` 的結果會是 `~x`
* `(x ^ y) - y` 和 `~x - y` 等價，而此時 `y` 所表示的值就是 `-1` ，也和 `~x - (-1)` 等價，而 `~x + 1` 正是 two's compliment 的定義
* 經過上述運算後，`x` 被轉為 `-x`
---
## 隨堂測驗 中
- [ ] 考慮測試 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 就有機會
:::success
延伸問題:
1. 探討 TCO 和遞迴程式的原理
2. 分析上述實驗的行為和解釋 gcc 對 TCO 的操作
3. 在 [Android 原始程式碼](https://android.googlesource.com/) 裡頭找出 [__builtin_return_address](https://gcc.gnu.org/onlinedocs/gcc/Return-Address.html) 的應用並解說
:::
---
### 想法與思考
* 首先針對 [Tail Call Optimization](https://en.wikipedia.org/wiki/Tail_call) 進行分析
* 適用場景， tail call 主要針對的是在 function block 中最後的回傳值會去呼叫另一個函式，甚至也可能是自己本身，及 recursion 中的一個特例。
```
function bar(data) {
if ( a(data) ) {
return b(data);
}
return c(data);
}
```
從上述程式碼中可以看到雖然呼叫 b function 時並不在程式碼區段中，絕對的最後一行，但在分支中也會在跳出程式時呼叫 b function 故也滿足 tail call 的定義。
* Tail Call Optimization 主要是省去一道返回中間層的步驟，以上方程式碼為例，在 `main` 中呼叫了 `bar` 再去呼叫 `c` 函式，理論上若是沒經過最佳化，在 stack 中會把 `c` 的回傳值傳給 `bar` ，最後再返回 `main` 函式中，可以最佳化的空間在於省去返回至 `bar` 的過程直接回到 `main` 函式。
* 而其中 TCO 主要鎖定的更是 recursive 的最佳化，有了 TCO 之後，不僅可以加速遞迴的執行速度，也可以避免每次呼叫函式時在 stack 中， push 進去一個 data frame 的步驟，從而也避免了可能產生 stack overflow
* 其中要想做到常數的 stack memory space 而非根據遞迴呼叫的次數限性增加，一個決定性的因素在於是否有 local variable ，若是具有區域變數，在不同層級的遞迴呼叫中，勢必存在不同狀態，放進 stack 中的也必須包含這類變數的狀態，使得 TCO 變得難以實現，指標尤其難以做到，而這也就是題目中，有了中間區域變數 x 後，難以做到 TCO 的原因。
```C=
void g(int *p);
void f(void) {
int x = 3;
g(&x);
}
void g(int *p) { printf("%d\n", *p); }
```
* 分析 [tco-test](https://github.com/sysprog21/tco-test) 的實現原理
* 首先從 [main.c](https://github.com/sysprog21/tco-test/blob/master/main.c) 著手，觀察其中的 main function
```C=
// main.c
int main(void) {
#define TCO_TEST(title, name, params1, args1, params2, args2) \
printf("%-45s", title ":"); \
first_##name args1; \
check();
#define TCO_RET_TEST(title, name, ret1, type1, type2, val) \
printf("%-45s", title ":"); \
first_##name(); \
check();
#include "tests.h"
return 0;
}
```
在經過 preprocessor 後，會把 test.h 內的內容貼在 line 12
```C=
TCO_TEST("No arguments", zero, (void), (), (void), ())
TCO_TEST("One argument", one, (int a), (0), (int a), (0))
TCO_TEST("Additional int argument", zero_one, (void), (), (int a), (0))
TCO_TEST("Dropped int argument", one_zero, (int a), (0), (void), ())
TCO_RET_TEST("char return to int", ret_int_char, return, int, char, 0)
TCO_RET_TEST("int return to char", ret_char_int, return, char, int, 0)
TCO_RET_TEST("int return to void", ret_void_int, , void, int, 0)
```
從 `TCO_TEST("No arguments", zero, (void), (), (void), ())` 開始逐步分析，會去呼叫 `first_zero()` 接著再呼叫 `check()`，進一步分析 first_zero 的實作，在 [first.c](https://github.com/sysprog21/tco-test/blob/master/first.c) 中
```C=
// first_zero
#define TCO_TEST(title, name, params1, args1, params2, args2) \
void second_##name params2; \
\
void first_##name params1 \
{ \
first_ra = __builtin_return_address(0); \
second_##name args2; \
}
```
用到了 second_zero 以及 [__builtin_return_address](https://gcc.gnu.org/onlinedocs/gcc/Return-Address.html) 的 GCC extension ， second_zero 的實作和 first_zero 的實作類似
```C=
#define TCO_TEST(title, name, params1, args1, params2, args2) \
void second_##name params2 { second_ra = __builtin_return_address(0); }
```
從 `__builtin_return_address` 的文件中可以知道當 level 參數為 0 時，會獲得當前這個函式的回傳地址， first_ra 為 first_zero 的回傳地址，而在 check 函數中
```C=
static void check(void) {
printf(first_ra == second_ra ? "TCO\n" : "no TCO\n");
}
```
若是 `seconde_ra` 和 `first_ra` 所指向的地址相同，則表示未經 TCO。
* 我找到在 Android source code 內使用到 __builtin_return_address 的部分是 [malloc_hook](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);
}
```
`__malloc_hook` 並非在 android 獨有，在 linux kernel 中也存在這一個 function pointer ，其用途為更改系統使用記憶體的模型。從上方 `hooks_malloc` 的實作中可以看到他使用了 __builtin_return_address 作為接上本來 malloc 的介面，只要在自己的實作中，使用 jump 或是 goto 這類跳轉的手段跳到這個 block 的最後就可以無縫接回本來的 malloc 介面了。
## 隨堂測驗 下
- [ ] 以下程式碼編譯並執行後，在 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
:::
---
### 想法與思考
* k1 = ( a ), k2 = ( c ), k3 = ( c ), k4 = ( c )
* 實際上針對第一支程式去編譯會發現
Sign in with Wallet
Connect another wallet