owned this note
owned this note
Published
Linked with GitHub
# 2018q3 Homework4 (assessment)
###### tags: `System-Software-2018`
Contributed by <[`DyslexiaS`](https://github.com/DyslexiaS)>
## 開發環境
```
Architecture: x86_64
CPU op-mode(s): 32-bit, 64-bit
Byte Order: Little Endian
CPU(s): 4
On-line CPU(s) list: 0-3
Thread(s) per core: 2
Core(s) per socket: 2
Socket(s): 1
NUMA node(s): 1
Vendor ID: GenuineIntel
CPU family: 6
Model: 61
Model name: Intel(R) Core(TM) i5-5200U CPU @ 2.20GHz
Stepping: 4
CPU MHz: 1536.107
CPU max MHz: 2700.0000
CPU min MHz: 500.0000
BogoMIPS: 4389.96
Virtualisation: VT-x
L1d cache: 32K
L1i cache: 32K
L2 cache: 256K
L3 cache: 3072K
NUMA node0 CPU(s): 0-3
```
## [第 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;
}
```
### 想法
1. 對一個數做絕對值之前,要先得知此數的正負號, `int64_t y` 就是取得 `x` 的 sign bit
- 正整數: `y = 0b0000...0000`
- 負整數: `y = 0b1111...1111`
>規格書 **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 是 signed 且 negative ,會是 implemnetation-defined 。顯然,如果以上函式在對 `-1` 做 Right shift ,會將前面補 `0` 的情況下就會錯誤。
2. 接著,`x` xor `y` :`(x^y)` 對於原本就是正整數的數值不會有影響
3. 對於原本是負數的數值,在二補數的機制下,**x + ~x = -1** ,因此 **-x = ~x + 1** ,就是函式最後 `(x^y)-y` (將 bits 反轉再 $- (-1)$
### 延伸問題
#### 1. overflow/underflow 問題
要探討 overflow/underflow 的情況,通常都在數值為極端值時才會發生。
**Code:**
```clike
#include <stdio.h>
#include <stdint.h>
#include <inttypes.h>
int64_t abs64(int64_t x) {
int64_t y = x >> (64 - 1);
return (x ^ y) - y;
}
int main(void){
printf("INT_64MAX: %+"PRId64"\n", INT64_MAX);
printf("abs(INT_64MAX): %+"PRId64"\n", INT64_MAX);
printf("INT64_MIN: %+"PRId64"\n", INT64_MIN);
printf("abs(INT64_MIN): %+"PRId64"\n", INT64_MIN);
return 0;
}
```
**Output:**
```shell
INT_64MAX: +9223372036854775807
abs(INT_64MAX): +9223372036854775807
INT64_MIN: -9223372036854775808
abs(INT64_MIN): -9223372036854775808
```
和原先預想的結果一樣,在數值為負最小時會出現 underflow 的問題。
---
#### 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.
:::info
提問:
看完對上面 code 的原理也還不是很了解,為什麼乘上 `0x2545f4914f6cdd1d` 可以預防 overflow,**[看不懂 xorshift generators](http://vigna.di.unimi.it/ftp/papers/xorshift.pdf)**
:::
- 實做
**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 找出類似用法的專案並探討,提示:密碼學相關
## [第 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
### 延伸問題
:::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; }
```
#### 3. 思考 `Segmentation fault` 的訊息是如何顯示出來,請以 GNU/Linux 為例解說。提示: Page fault handler
---
## [因為自動飲料機而延畢的那一年](http://opass.logdown.com/posts/1273243-the-story-of-auto-beverage-machine-1)
## 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)