# 2018q3 Homework4 (assessment)
contributed by < [`dange0`](https://github.com/dange0) >
###### tags: `sysprog2018`
## 第 4 週測驗題 (上)
### 題目
考慮以下求絕對值的程式碼:
```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 = `>>`
A2 = `64`
A3 = `^`
### 解題想法
- 在做絕對值時，必須先知道該數值為正數或負數，必須要查該有號數之最高有效位
```clike
y = x >> 63
```
- 如果是正數， y 為 0
- 如果是負數，因為 c 語言在做擴展或是位移的時候，都會參照最高有效位，因此這時候的 y 為 0xffffffffffffffff
:::info
**C99 Standard 6.5.7**
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.==
:::
- 如果 x 為正號，直接將 x 回傳就好了
- 如果 x 為負號，必須將 x 做 inverse 再加 1
```clike
(x ^ y) - y
```
- 當 x 為正號，因為 y 為 0，因此並不會影響 x
- 當 x 為負號，x 與 0xffffffffffffffff 做 xor 等於將他做 inverse ，接著在 `-(-1)`
### 延伸問題
#### 解釋運作原理，並探討可能的 overflow/underflow 議題
在二補數中，因為正負號轉換的特性，因此會造成 most negative number 在做二補數轉換時仍然為自己，同樣的也有可能會在這邊發生 overflow 的問題。
假設有一個 4 bits 的二補數，其可表達範圍為 -2^3^ ~ 2^3^ ，將針對 -8 (0b1000) 做 overflow 之檢查
- `y = 0b1000 >> 3` 結果為 `0b1111`
- `(0b1000 ^ 0b1111)` 結果為 `0b0111`
- `0b0111 - 0b1111` 結果為 `0b1000`
可以發現，因為二補數之特性造成 most negative number 會產生 overflow
#### 現實中的 Interger Overflow
>[**CVE-2016-6303**](https://www.cvedetails.com/cve/CVE-2016-6303/)
> Integer overflow in the MDC2_Update function in crypto/mdc2/mdc2dgst.c in OpenSSL before 1.1.0 allows remote attackers to cause a denial of service (out-of-bounds write and application crash) or possibly have unspecified other impact via unknown vectors.
Interger overflow 曾發生於 OpenSSL。攻擊者只要利用 integer overflow 觸發函式 MDC2_Update() 就可以造成目標服務崩潰，可以被利用於 denial-of-service attack。
[**openssl 1.0.1c - crypto/mdc2/mdc2.h**](https://docs.huihoo.com/doxygen/openssl/1.0.1c/include_2openssl_2mdc2_8h_source.html)
```clike
typedef struct mdc2_ctx_st
{
unsigned int num;
unsigned char data[MDC2_BLOCK];
DES_cblock h,hh;
int pad_type; /* either 1 or 2, default 1 */
} MDC2_CTX;
```
[**openssl 1.0.1c - crypto/mdc2/mdc2dgst.c**](https://docs.huihoo.com/doxygen/openssl/1.0.1c/mdc2dgst_8c_source.html)
```clike=88
int MDC2_Update(MDC2_CTX *c, const unsigned char *in, size_t len) {
size_t i,j;
i=c->num;
if (i != 0) {
if (i+len < MDC2_BLOCK) {
/* partial block */
memcpy(&(c->data[i]),in,len);
c->num+=(int)len;
return 1;
}
else {
/* filled one */
j=MDC2_BLOCK-i;
memcpy(&(c->data[i]),in,j);
len-=j;
in+=j;
c->num=0;
mdc2_body(c,&(c->data[0]),MDC2_BLOCK);
}
}
i=len&~((size_t)MDC2_BLOCK-1);
if (i > 0) mdc2_body(c,in,i);
j=len-i;
if (j > 0) {
memcpy(&(c->data[0]),&(in[i]),j);
c->num=(int)j;
}
return 1;
}
```
Integer overflow 發生於**第 93 行**之判斷式 `if (i+len < MDC2_BLOCK)`
如果 `i` 與 `len` 的輸入都為非常大的數字，相加後造成 interger overflow 的值會小於 `MDC2_BLOCK`，這時判斷式就會成立，並且造成程式錯誤
以下為 patching 方法：
[patch](https://github.com/openssl/openssl/commit/2b4029e68fd7002d2307e6c3cde0f3784eef9c83)
```clike=91
i = c->num;
if (i != 0) {
if (len < MDC2_BLOCK - i) {
/* partial block */
memcpy(&(c->data[i]), in, len);
c->num += (int)len;
```
透過相減來避免 interger overflow 發生
## 第 4 週測驗題 (中)
考慮測試 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 呢？選出最適合的解釋。
==作答區==
* 只要函式 `g` 沒有對 `global_var` 指標做 dereference，那麼 TCO 就有機會
### 解題想法
因為 `x` 的值是存在函式 `f` 的 stack frame 中，因此 `g` 在對 `global_var` 指標做 dereference 的話， `f` 的 stack frame 就必須被保存，這也就造成 TCO 無法實現。
所以只有在函式 `g` 沒有對 `global_var` 指標做 dereference 時才可以做 TCO
### 延伸問題:
#### 探討 TCO 和遞迴程式的原理
#### 分析上述實驗的行為和解釋 gcc 對 TCO 的操作
#### 在 [Android 原始程式碼](https://android.googlesource.com/) 裡頭找出 [__builtin_return_address](https://gcc.gnu.org/onlinedocs/gcc/Return-Address.html) 的應用並解說
## 第 4 週測驗題 (下)
以下程式碼編譯並執行後，在 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 = `ptr1.c` 在執行時期會造成 Segmentation fault
K2 = `ptr2.c` 是合法 C 程式，在執行後可透過 `echo $?` 得到 exit code 為 `0`
K3 = `ptr3.c` 是合法 C 程式，在執行後可透過 `echo $?` 得到 exit code 為 `0`
K4 = `ptr4.c` 是合法 C 程式，在執行後可透過 `echo $?` 得到 exit code 為 `0`
### 解題想法
#### 參照 C 語言規格書，充分解釋其原理
- ptr1.c
```C
int main() { return *((int *) 0); }
```
將 0 強制轉型為 pointer to int，再去 dereference。因為指標指向 0 ，所以 dereference 時會造成 Segmentetion fault。
- ptr2.c
```C
int main() { return &*((int *) 0); }
```
> **C99 Standard 6.5.3.3**
> 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. If *P is an lvalue and T is the name of an object pointer type, *(T)P is an lvalue that has a type compatible with that to which T points.
因此 `&*((int *) 0)` 相當於 `((int *) 0)`，會回傳 0
- ptr3.c
```C
#include <stddef.h>
int main() { return &*NULL; }
```
同上，屬於 `even if E is a null pointer` 的範疇內，會回傳 0。
- ptr4.c
```C
#include <stddef.h>
int main() {
return &*(*main - (ptrdiff_t) **main);
}
```
由先前的解釋得知 `&*(*main - (ptrdiff_t) **main)` 相當於 `(*main - (ptrdiff_t) **main)`
> **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.
根據 C99 規格書的解釋 `*main` 與 `**main` 都會被強制轉為 function designator `main`，`main - main` 會得到 0，因此會回傳 0。
### 延伸問題
#### 解析 clang/gcc 編譯器針對上述程式碼的警告訊息
- ptr1.c
```shell
/bin/bash: line 1: 39055 Segmentation fault ./'ptr1'
shell returned 139
```
- ptr2.c
```shell
ptr2.c: In function ‘main’:
ptr2.c:1:21: warning: return makes integer from pointer without a cast [-Wint-conversion]
int main() { return &*((int *) 0); }
```
因為 `main` 的回傳值應該為 `int`，但是 ptr2.c 卻回傳了 `pointer to int` 之型態，因此出現警告
- ptr3.c
```shell
ptr3.c: In function ‘main’:
ptr3.c:2:22: warning: dereferencing ‘void *’ pointer
int main() { return &*NULL; }
^
ptr3.c:2:21: warning: return makes integer from pointer without a cast [-Wint-conversion]
int main() { return &*NULL; }
```
這裡出現了兩個 warning
第一個為對 `void*` dereference，
> **C99 6.2.5**
>The void type comprises an empty set of values; it is an incomplete type that cannot be
completed.
根據 C99 規格書解釋， void 是一個 incomlpete type，對一個 incomplete type 做 dereference 有可能會出錯，因此出現 warning
第二個 warning 同 ptr2.c 之 warning
- ptr4.c
```shell
ptr4.c: In function ‘main’:
ptr4.c:3:16: warning: return makes integer from pointer without a cast [-Wint-conversion]
return &*(*main - (ptrdiff_t) **main);
```
同上
#### 思考 `Segmentation fault` 的訊息是如何顯示出來，請以 GNU/Linux 為例解說。提示: Page fault handler
##### page 與 segment
- Page
- 若採用連續性的記憶體配置會產生 External Fragmentation 的情況，因此透過 page 使分配記憶體時不必要連續配置
- Page table 上面除了紀錄著 page number 與 physical address 的對應關係，也透過紀錄保護位元(protection bit)來判斷 page 是否可讀寫
- Segment
- 以程式設計者的角度把記憶體分為不同 segment，並且分別定義不同 segment 可讀可寫可執行的權限
- 常見的 segment 如下：
- Text segment：存放程式碼 r-x
- Data segment：存放資料 rw-
- BSS segment：存放未初始化資料 rw-
- Heap segment：存放動態分配之資料 rw-
- Stack segment：存放函式區域變數 rw-
[Source](https://en.wikipedia.org/wiki/Data_segment)
- 從 logical address 到 physical address
[Source](http://mropengate.blogspot.com/2015/01/operating-system-ch8-memory-management.html)
- logical address 會先經過 segment descriptor 轉換為 linear address
- linear address 再經過 page table 轉換為 physical address
- segment 是由許多同樣權限的 page 所組成
##### Segmentation fault 的產生
> **wiki - Segmentation fault**
> At the hardware level, the ==fault is initially raised by the memory management unit (MMU) on illegal access== (if the referenced memory exists), as part of its ==memory protection feature, or an invalid page fault== (if the referenced memory does not exist). If the problem is not an invalid logical address but instead an invalid physical address, a bus error is raised instead, though these are not always distinguished.
> [Source](https://en.wikipedia.org/wiki/Segmentation_fault)
- segmentation fault 是由 MMU 所發起
- 當 page fault 發生時，MMU 就會去查表，找尋真正的 physical address，查到 page table 時發現該 page 並沒有該權限，因此跳出 segmentation fault 之訊息
## 因為自動飲料機而延畢的那一年的起發
Sign in with Wallet
Connect another wallet