# 2018q3 Homework4 (assessment)

contributed by < [p61402](https://github.com/p61402) >

###### tags: `sysprog`

## 測驗 `1`

### 題目描述

考慮以下求絕對值的程式碼:

#include <stdint.h>
int64_t abs64(int x) {
    if (x < 0) return -x;
    return x;
}

移除分支並善用[二補數](https://en.wikipedia.org/wiki/Two%27s_complement)特性，改寫為下方程式碼:

#include <stdint.h>
int64_t abs64(int64_t x) {
    int64_t y = x A1 (A2 - 1);
    return (x A3 y) - y;
}

請補完，其中 `A1` 和 `A3` 都是 operator。

==作答區==

A1 = ?
* `(a)` &
* `(b)` |
* `(c)` ^
* `(d)` <<
* `(e)` >>

A2 = ?
* `(a)` 0
* `(b)` 1
* `(c)` 61
* `(d)` 62
* `(e)` 63
* `(f)` 64

A3 = ?
* `(a)` &
* `(b)` |
* `(c)` ^
* `(d)` <<
* `(e)` >>

:::success
延伸問題:
1. 解釋運作原理，並探討可能的 overflow/underflow 議題;
2. 搭配下方 pseudo-random number generator (PRNG) 和考量到前述 (1)，撰寫 `abs64` 的測試程式，並探討工程議題 (如：能否在有限時間內對 int64_t 數值範圍測試完畢？)

static uint64_t r = 0xdeadbeef
int64_t rand64() {
    r ^= r >> 12;
    r ^= r << 25;
    r ^= r >> 27;
    return (int64_t) (r * 2685821657736338717);
}

3. 在 GitHub 找出類似用法的專案並探討，提示：密碼學相關
:::

### 想法

在二補數表示法中，若要對一個有號整數`x`取絕對值，要考慮兩種情況：
1. 當`x`是正數或 0 時，則不用進行任何轉換，因為`x`取絕對值後還是自己。
2. 種是當`x`為負數時，若要取絕對值則需將`x`做二補數。

但是因為移除了分支，因此不能進行`x`是正負數的判斷。

觀察一下題目，`A1`比較有可能是`<<`或`>>`，`A2`有可能是`0`或`64`。

但是當`A2`為 0 的時候，代表要將`x`左移或右移 -1 個 bit，感覺不太合理，因此查了一下 C 語言的規格書：
> **C99 Standard (§ 6.5.7) Bitwise shift operators**
The integer promotions are performed on each of the operands. The type of the result is that of the promoted left operand. **If the value of the right operand is negative** or is greater than or equal to the width of the promoted left operand, **the behavior is undefined**.

因此可以知道左移或右移 -1 個 bit 是一個 undefined behavior，所以`A2`不會是 0。

所以當`A2`= 64，代表將`x`左移或右移 63 個 bits，但因為`x`有可能是負數，我不知道有號數的左移及右移要怎麼執行，所以再次查看 C 語言規格書：
> **C99 Standard (§ 6.5.7) Bitwise shift operators**
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 × 2^E2^, reduced modulo one more than the maximum value representable in the result type. **If E1 has a signed type and nonnegative value, and E1 × 2^E2^ is representable in the result type, then that is the resulting value; otherwise, the behavior is undefined.**

> **C99 Standard (§ 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 E1 / 2^E2^. **If E1 has a signed type and a negative value, the resulting value is implementation-defined.**

可以知道在`E1`在 signed type 的時候，若`E1`為非負，`E1`左移與右移`E2`個位元的結果會等同於 E1 x 2^E2^ 以及 E1 / 2^E2^；但是當`E1`為負數時，左移是一個 undefined behavior，右移則是 implementation-defind。

既然是 implementation-defined，那就來測試一下吧，使用 64 位元的有號整數來觀察：

int main()
{
    int64_t m = 0x8000000000000300;
    int64_t n = 0x0000000000000300;
}

開啟好用的 gdb 模式，雖然將負數左移是 undefined behavior，不過基於好奇心還是來看一下左移會發生什麼事：

(gdb) p/t m
$1 = 1000000000000000000000000000000000000000000000000000001100000000
(gdb) p/t m << 1
$2 = 11000000000    # 前方的 0 被省略了
(gdb) p/t m << 2
$3 = 110000000000   # 前方的 0 被省略了

可以看到左移的動作直接把`m`當作 unsigned type 來處理，無視最左方的 sign bit，將整個數進行位移。

接下來觀察右移的情形：

(gdb) p/t m
$4 = 1000000000000000000000000000000000000000000000000000001100000000
(gdb) p/t m >> 1
$5 = 1100000000000000000000000000000000000000000000000000000110000000
(gdb) p/t m >> 2
$6 = 1110000000000000000000000000000000000000000000000000000011000000

看起來也是直接將`m`當作 unsigned type 進行處理，不過會有 sign extension 的動作，將左方的 bit 補上 1。

接著觀察將負數`m`往右移 63 個位元的時候得出的結果所有的 bit 都會是 1。

(gdb) p/t m >> 63
$7 = 1111111111111111111111111111111111111111111111111111111111111111

再來觀察非負的數`n`往右移 63 個位元時得出的結果所有的 bit 都是 0。

(gdb) p/t n >> 63
$8 = 0

在此可以推測程式碼第一行應為：

int64_t y = x >> (64 - 1);

我們的目的是要將負數進行二補數運算，而非負數則維持不變。

所以仔細觀察一下，當`A3`為`^`時，

(gdb) p/t m
$9 = 1000000000000000000000000000000000000000000000000000001100000000
(gdb) p/t m ^ (m >> 63)
$10 = 111111111111111111111111111111111111111111111111111110011111111    
# $10 最前方的 0 被省略，所以才會少一個 bit

對齊一下比較好觀察，可以發現這不就是一補數的計算嗎：

1000000000000000000000000000000000000000000000000000001100000000    # x
0111111111111111111111111111111111111111111111111111110011111111    # x ^ y

計算式為`(x ^ y) - y`，因此還需要再減掉一次`y`，`y`的值是`0xffffffffffffffff`，在二補數表示法中代表 -1，不就是加一嗎？所以`(x ^ y) - y`在`x`是負數的時候就是做二補數啊！

(gdb) p/t (int64_t)-1
$11 = 1111111111111111111111111111111111111111111111111111111111111111
(gdb) p/x (int64_t)-1
$12 = 0xffffffffffffffff

那麼當`x`是非負整數時的情況呢？`y`的值是`0x0000000000000000`，`x ^ y`的結果仍然是`x`，`x - y`的結果也依舊是`x`。

(gdb) p/t n
$13 = 1100000000
(gdb) p/t n >> 63
$14 = 0
(gdb) p/t n ^ (n >> 63)
$15 = 1100000000
(gdb) p/t n ^ (n >> 63) - (n >> 63)
$16 = 1100000000

真是太神奇了！這段程式碼在`x`是非負整數時計算結果維持不變，而在`x`是負整數的時候卻進行了二補數的運算！

#include <stdint.h>
int64_t abs64(int64_t x) {
    int64_t y = x >> (64 - 1);
    return (x ^ y) - y;
}

### 延伸問題

64-bit的二補數表示法可表達的範圍為 -2^63^~2^62^-1，因此有可能產生 Overflow 的值只有 -2^63^，因為沒有對應的正數可以表示。

寫個程式測試需要多少時間能夠檢查完所有的數：

#define the_abs(n) ((n) < 0 ? (-n) : (n))

double test(int64_t base, int64_t length)
{
    clock_t begin = clock();
    int64_t i;
    for (i = base; i < length; i++)
        assert(abs64(i) == the_abs(i));
    clock_t end = clock();
    double time_spent = (double)(end - begin) / CLOCKS_PER_SEC;
    return time_spent;
}

void a_test(int64_t b, int64_t l)
{
    double time_spent = test(b, l);
    printf("%f seconds\n", time_spent);
}

int main()
{
    int64_t b = -10000;
    int64_t l = 1;
    int i;

    for (i = 0; i < 7; i++)
    {
        a_test(b, l);
        b *= 10;
    }
}

0.000050 seconds    # 1e4  筆資料
0.000473 seconds
0.004556 seconds
0.042300 seconds
0.341621 seconds
3.393501 seconds    # 1e9  筆資料
34.005079 seconds   # 1e10 筆資料

可以看到資料筆數與執行時間呈線性增長，10 億筆資料約需 3.4 秒執行，100 億筆資料約需 34 秒執行。

而`int64_t`的範圍為 -9,223,372,036,854,775,808 到 9,223,372,036,854,775,807，總共 18,446,744,073,709,551,616 筆資料，是 100 億的 1844674407 倍，因此執行時間預估需要 62718929838 秒。

Python 3.7.0
>>> (int)(2**64 / 1e10)
1844674407
>>> (int)(2**64 / 1e10) * 34
62718929838

將[秒數轉換成年](https://www.calculateme.com/time/seconds/to-years/)，大概需要 1,987 年才能夠檢查完所有的資料。

---

## 測驗 `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` 編譯選項) 進行編譯，得到以下執行結果:

$ 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` 等級) 編譯，會得到以下執行結果:

$ 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:

void g(int *p);
void f(void) {
    int x = 3;
    g(&x);
}
void g(int *p) { printf("%d\n", *p); }

因為函式 `f` 的區域變數 `x` 在返回後就不再存在於 stack。考慮以下程式碼:

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 (TCO)
[Tail call](https://en.wikipedia.org/wiki/Tail_call) recursion 指的是在遞迴的函式中，最後一個動作是呼叫自己本身，例如以下函式`factorial`即為尾端遞迴：

int factorial(int n, int i)
{
    if (i == 1)
        return n;
    return factorial(n * i, i - 1);
}

int main()
{
    int a = factorial(1, 5);
    printf("%d\n", a);
}

而將遞迴寫成 tail call 有什麼好處呢？

首先要知道當一個函式 (caller) 呼叫另一個函式 (callee) 時，程式要記得在 callee 回傳後，caller 需要執行的下一個指令，在組合語言中就是 return address (PC + 4)，包含 caller 的 function argument 以及 local variable 等物件都會被儲存在 caller 的 [call stack](https://en.wikipedia.org/wiki/Call_stack) 中。

若 compiler 有支援 TCO，在 tail call 的函式中，由於 caller 在 callee 回傳後就不會執行任何的指令，直接返回上一層，因此不需要儲存 caller 的資訊，甚至可以直接將 return address 設為 original caller。

考慮以下程式碼：

int *global_var;
void f(void)
{
    int x = 3;
    global_var = &x;
    ...
    /* Can the compiler perform TCO here? */
    g();
}

在函式`f`中，將全域變數指標`global_var`設為區域變數`x`的位址，若`g`想要存取到`x`的值，函式`f`勢必得將區域變數`x`的值儲存起來，很明顯的，這樣不可能對函式`g`施加 TCO，因為 TCO 的條件是 caller 不再佔用 stack 的空間，直接回傳 callee 的回傳值。

因此答案為：`(c)` 只要函式 `g` 沒有對 `global_var` 指標作 dereference，那麼 TCO 就有機會。

---

## 測驗 `3`
### 題目敘述
以下程式碼編譯並執行後，在 x86_64 GNU/Linux 會遇到記憶體存取錯誤:

$ cat ptr.c
int main() {
    int *ptr = 0;
    return *ptr;
}
$ gcc -o ptr ptr.c
$ ./ptr
Segmentation fault: 11

分別考慮以下 4 個程式，探討其行為。
- [ ] `ptr1.c`

int main() { return *((int *) 0); }

- [ ] `ptr2.c`

int main() { return &*((int *) 0); }

- [ ] `ptr3.c`

#include <stddef.h>
int main() { return &*NULL; }

- [ ] `ptr4.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
:::

### 想法
觀察底下程式碼：

int main() {
    int *ptr = 0;
    return *ptr;
}

第二行將整數型別指標`ptr`設為`0`，也就是`0x0`這個記憶體位址，但是這個記憶體位址並沒有被這個函式宣告，很明顯存取`0x0`這個記憶體是違法的，因此才會產生 segmenatation fault 的錯誤。

接下來一一探討以下程式碼：

- `ptr1.c`

int main() { return *((int *) 0); }

`((int *) 0)`就是將`0x0`這個位址轉型為`int`型別的指標，`*((int *) 0)`則是將這個位址 dereference。將未宣告的位址進行 dereference 很明顯是違法的，因此會產生 segmentation fault 的錯誤。

- `ptr2.c`

int main() { return &*((int *) 0); }

`&*`這傢伙在[上次的作業](https://hackmd.io/s/B16SishFm#%E7%AC%AC-2-%E9%80%B1-%E6%B8%AC%E9%A9%97%E9%A1%8C-5)就有看到，再次回顧一下 C 語言的規格書：

>**C99 Standard (§ 6.5.3.2)**
The operand of the unary & operator shall be either a function designator, the result of a [] or unary * operator, or an lvalue that designates an object that is not a bit-field and is not declared with the register storage-class specifier.

>**C99 Standard (§ 6.5.3.2)**
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.

>**C99 Standard (§ 6.5.3.2) 註釋 84**
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.

所以基本上`&*((int *) 0)`就等同`((int *) 0)`，回傳`0x0`這個記憶體位址，沒毛病，基本上就是可以編譯成功的程式碼，不過我認為應該將 return type 改為`int*`會比較好。

- `ptr3.c`

#include <stddef.h>
int main() { return &*NULL; }

跟上一題一樣，`&*NULL`基本上就等同`NULL`，所以也是可以編譯，不過還是應該將 return type 改為指標比較好。

- `ptr4.c`

#include <stddef.h>
int main() {
    return &*(*main -  (ptrdiff_t) **main);
}

[`ptrdiff_t`](https://en.cppreference.com/w/c/types/ptrdiff_t)定義在`stddef.h`中，是一個有號整數型別，代表兩個指標相減的值。

>**C99 Standard (§ 6.3.2.1)**
A function designator is an expression that has function type. Except when it is the operand of the sizeof operator) or the unary & operator, a function designator with type ‘‘function returning type’’ is converted to an expression that has type ‘‘pointer to function returning type’’.

>**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.)

`*main`以及`**main`都是 function designator，會被轉成「指向函式回傳型別的指標」，因此兩個表示法都等同於`main`，而前方的`&*`又可被消除，因此以上程式碼基本上就是等同於`return (main - (ptrdiff_t) main)`，為合法的表示方法。

因此只有第一題答案是`a`，其餘答案都是`c`。

### 延伸問題
#### 解析警告訊息
除了第一題結果為 segmentation fault 之外，其餘出現的警告都是像下面這種：

warning: return makes integer from pointer without a cast [-Wint-conversion]
 int main() { return &*((int *) 0); }
                     ^~~~~~~~~~~~~

回傳的型別為應該為指標但卻是`int`，所以才會產生以上警告訊息。

#### 思考 Segmentation Fault 訊息如何產生
[segmentation fault](https://en.wikipedia.org/wiki/Segmentation_fault) 是由硬體基於 memory protection 的機制所發起的錯誤訊息，通常發生於程式試圖存取自身沒有權力存取的記憶體等原因。

倘若 CPU 將某個位址傳給 MMU，但 MMU 卻尚未轉譯這個記憶體位址，這時 page fault handler 會傳送`SIGSEGV`這個訊號給 process，若程式中沒有定義如何處理這個訊號，則預設會終止 process 以及產生 [core dump](https://en.wikipedia.org/wiki/Core_dump)。([參考資料](https://unix.stackexchange.com/questions/257598/how-does-a-segmentation-fault-work-under-the-hood))