# 2018q3 Homework4(assessment)
contributed by <[pjchiou](https://github.com/pjchiou)>
---
## outline
- 第四週測驗題(上) - 求絕對值
* 運作原理
* 測試程式設計
* GitHub 案例
- 第四週測驗題(中) - TCO
* TCO 與 tail recursion 原理
* Android 原始程式碼內使用 __builtin_return_address 的案例
- 第四週測驗題(下) - segmentation fault
* Segmentation fault
- 對[因為自動飲料機而延畢的那一年](http://opass.logdown.com/posts/1273243-the-story-of-auto-beverage-machine-1)一文的感想
---
## 第四週測驗題(上) - 求絕對值
以下是一個求**絕對值的程式**
```clike=1
int64_t abs64(int64_t x)
{
int64_t y = x >> (64 - 1);
return (x ^ y) - y;
}
```
以下將解釋運作原理、測試程式設計以及 GitHub 中的使用案例。
### 運作原理
首先先搞情楚幾件事
- 我的系統是表示整數是用**二補數**，在二補數下有一個重要的關係式 **x + ~x = -1**，即==任何數與其補數相加為 -1== 舉例來說，若以占 1 byte 的有號整數做為例子來看，下方左邊為 5 ； 右方為其補數 = -6 。
```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"]
}
```
- 有號數與無號數做 `>>` (bitwise right shift) 的行為，在 [The C Programming Language 2/e](https://www.dipmat.univpm.it/~demeio/public/the_c_programming_language_2.pdf) 對 `>>` 的描述寫著
:::warning
Right shifting a signed quantity will fill with sign bits ("arithmetic shift") on some machines and with 0-bits ("logical shift") on others.
:::
對於有號整數的 `>>` 運算，在有些機器上是補 sign bits ，有些是補 0 。這對 sign bit 是 1 的時候(負數)會有分岐。
果然在 [C99 3.4.1](http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1124.pdf) 對於 implementation-defined behavior 的解釋。
:::warning
Unspecified behavior where each implementation documents how the choice is made. An example of implementation-defined behavior is the propagation of the high-order bit when a signed integer is shifted right.
:::
看來對 signed integer 做 `>>` 運算，經典到直接被拿來當做例子...我們再看在 [C99 6.5.7](http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1124.pdf) 的解釋。
:::warning
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 是 unsigned 或 nonnegative signed 都沒關係，其值為 $E1/2^{E2}$ 。
- E1 是 signed 且 negative ，那就是 implemnetation-defined 了。
顯然我們的這個函式在那些會補 0 的機器上不能用，我的機器是屬於前者，會補 sign bit ，我用下表分析其行為。可以知道當 x>=0 或 x<0 時函式的行為
==-1 相當於每個 bit 都是 1 。==
||x>=0|x<0|
|:-:|:-:|:-:|
|y|0|-1|
|x^y|x|~x|
|(x^y)-y|(x)-0|(~x)-(-1)|
當 x>=0 時回傳 x ； x<0 時，正是回傳 ==x 的補數再加 1== 。
### 測試程式設計
對於這個程式的測試我的想法是
- 不可能窮舉，算不完的。
\begin{align*}
y &=
\begin{cases}
0 & \text{if } x \geq 0 \\
-1 & \text{otherwise}
\end{cases}
\end{align*}
- 這個式子一定要成立。
- 最後 (~x)-(-1) 不能 overflow
#### 判斷時可能會有問題
有號整數的值域負數會比正數還多一個，這時候當 `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
:::
---
### GitHub 案例
- 在 [Awesome bit](https://github.com/keon/awesome-bits) 這個 repository 底下有列出很多 bit operation 的手法，在求絕對值的部分 version 2 就是這篇的方法。這個 repository 完全沒有程式碼，只有 README.md ，我看的時候有 2,426 個 star、148 個fork。
```clike
//version 1
x < 0 ? -x : x;
//version 2
(x ^ (x >> 31)) - (x >> 31);
```
## 第四週測驗題(中) - TCO
測驗附上的[程式](https://github.com/sysprog21/tco-test)非常短...沒有看過這種用法。利用了 C 語言實作與宣告可以分開的特性，結合前置處理器，拿 tests.h 的內容同時做宣告、實作、呼叫，太神了...
這個[網頁](https://david.wragg.org/blog/2014/02/c-tail-calls-1.html)有對這個測驗的詳細解釋。
```clike=1
void f(void)
{
int x = 42;
global_var = &x;
...
/* The compiler cannot perform TCO here,
* unless it can establish that g does not
* dereference the pointer in global_var. */
g();
}
```
### 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();
}
```
### 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));
}
```
---
## 第四週測驗題(下) - segmentation fault
以下四個程式分別探討其行為屬於何者
1. 在執行時期會造成 Segmentation fault
2. C 語言規格書聲明這是 undefined behavior 或者語法錯誤
3. 是合法 C 程式，在執行後可透過 echo $? 得到 exit code 為 0
```clike=1
int main() { return *((int *) 0); }
int main() { return &*((int *) 0); }
#include <stddef.h>
int main() { return &*NULL; }
#include <stddef.h>
int main() {
return &*(*main - (ptrdiff_t) **main);
}
```
[C99 6.5.3.2](http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1124.pdf) 節對 `&` 與 `*` 的描述，節錄幾個重點。
- `&` 運算子的運算元有三種，且不能是 bit-field 或宣告成 register 的變數
* function designator
* `[]` 或 `*` 運算子的結果
* lvalue
- `*` 運算子的運算元有兩種
* function designator
* pointer
- `&` 的運算元是 `*` 的結果的時候，`&` 與 `*` 都不會作用，==並非是等價，而是真的跟不存在一樣==。
- 若運算元是 `[]` 的結果，則會被置換成 `+` 運算子，例如 `&a[2] = a+2`。
- `*` 的運算元是 function 的時候，結果為 function designator ； 若運算元為 pointer ，則結果為一個 lvalue ，若該 pointer 指向一個無效的地址則為 undefined behavior 。
- &*E 相當於 E ，即使 E 是一個 null pointer 一樣成立。
- `*` 無效的地址有以下三種
* null pointer
* 沒有適當 aligned 的地址
* 指向超出生命週期物件的指標
基於這些規則來解釋上方四個程式發生了什麼事。
### 第一個程式
- 對無效的地址做 dereference ，這是一個 undefined behavior 。
- 對 (int *)0 這個不屬於我的位置做 dereference 會得到 segmentation fault ，這個程式確實可以執行，應該選在執行時期會造成 Segmentation fault 比較洽當。
```clike
int main() { return *((int *) 0); }
```
這個程式不會有 gcc 的警告。
### 第二個程式
- `&*` 會被忽略，變成回傳 (int *)0 ，這是合法 C 程式，在執行後可透過 echo $? 得到 exit code 為 0。
```clike
int main() { return &*((int *) 0); }
```
gcc 的警告
:::warning
warning: return makes integer from pointer without a cast [-Wint-conversion]
:::
- 因最後回傳 (int*) 0 ，與 int main 的型別不同。
- 若改成 int *main ，變成有 **warning: return type of ‘main’ is not ‘int’ [-Wmain]** 的警告。
### 第三個程式
- `&*` 會被忽略，回傳 NULL 。
- NULL 被定義為一個 (void *)0
所以這是合法 C 程式，在執行後可透過 echo $? 得到 exit code 為 0。
```clike
#include <stddef.h>
int main() { return &*NULL; }
```
gcc 的警告為
:::warning
ptr.c:4:13: warning: dereferencing ‘void *’ pointer
ptr.c:4:12: warning: return makes integer from pointer without a cast [-Wint-conversion]
:::
- NULL 相當於 (void *)0 ， 不能對其做 dereference ， `&*` 應該要抵消才對...後來想想有抵消沒錯，如果程式真的做了 dereference 的話，應該要看到 segmentation fault ，但是沒有。
### 第四個程式
- main 是 function designator ，其會轉為 pointer to function
- *main 也是 function designator ，同上被轉為 pointer to function
- 兩個指標相減的結果是一個 (ptrdiff_t) 類別，根據 C99 7.17 節所說，這是一個 signed integer 。
- `&*` 0 ，跟第二個程式相同
這是合法 C 程式，在執行後可透過 echo $? 得到 exit code 為 0。
```clike
#include <stddef.h>
int main() {
return &*(*main - (ptrdiff_t) **main);
}
```
:::warning
ptr.c:4:12: warning: return makes integer from pointer without a cast [-Wint-conversion]
:::
- 跟第二個一樣，回傳的型別與 main 不同。
### Segmentation fault
[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)
---
## 對[因為自動飲料機而延畢的那一年](http://opass.logdown.com/posts/1273243-the-story-of-auto-beverage-machine-1)一文的感想
這篇文章看了很有感觸，我是土木系畢業的，還記得有一天上鋼筋混凝土學的時候，老師分享了一篇報導，關於一位國外的土木系教授親自設計、建造了一座橋(那時其實有準確地提到是哪個教授、哪座橋，但年代久遠我忘了...)。
==只有「橋」是土木工程師可以獨立完成的設計，其他結構體都要有建築師的參與。==
話鋒一轉，提到他認為成大土木系的老師們都沒有這個能力...不只「資工系的學生不會寫程式，機械系的學生不會做機械」，抱歉土木系也不會蓋房子...
### 理論與實務不並重的台灣高等教育
老師上課常在嗆大家不是理論與實務不並重，而是理論與實務都沒有...也承認自己真的學得不扎實，常常是知其然而不知其所以然。從以前一直有一種感覺，真正弄懂的東西，其實很不容易忘，就像用筷子一樣，不會因為被丟到只用刀子叉子的地方就忘了怎麼用筷子，可能有點生疏了，但一碰到筷子很快就會想起來。
資工系的學生有一個優勢，是可以很輕易、快速、便宜、安全地在自己的電腦上**動手**實現想法。像我是土木系的學生，做混凝土的實驗時間都是用「天」來算的，材料、場地、實驗器材都不是隨手可得的東西，就連我只是想測手指粗鋼筋的強度，可能都要有 4 噸的拉力它才會斷，在這種情況下不太可能有人可以在學生時期就搞出一個有強度的東西。
### Master of xxx engineering?
在遊戲裡面，如果看到 master 這個稱號的，通常在該領域已經是至高無上的存在了，但看看我的碩士學歷上也是寫 master ，深深覺得自己根本配不上這個字。成大的學歷其實很好拿，整個四年可能遇不到比入學考還大的挑戰了，念不會這章就背考古題、背不起來就逃、逃到無處可逃搞不好老師還會放水，莫名奇妙地過了、畢業了。然後拿著成大的學歷出去招搖撞騙，但發現可以拿成大學歷招搖撞騙的地方，不是你想待的地方。
以前碩班的指導老師也曾說「台灣的這個現象很不好，在 MIT ，錄取進去卻無法畢業的大有人在」。其實早點知道自己不適合是好事，重點是==在放棄以前努力過了嗎?==
「你不能現在就放棄，要是現在就放棄的話，你這輩子日後遇到這種等級的困難，就只會想逃避而已」，工作了幾年後，對這句話很有感觸，有時候找不到 root cause ，或有些人根本沒花心力去找、一直逃避，久而久之一堆無頭公案，逃到最後呢?擺爛嗎?推給別人?辭職嗎?那其實也是某些人的生存方式，但我自己不喜歡。
### No pain no gain
這是我對這四週以來的感想，沒有什麼快樂學習、快樂成長，那都是幹話，所有東西都是「等價交換」(鋼鍊也是我心中的神作)。動手去實做很重要，不是為了要自幹出什麼東西丟到業界去跟人家拼(當然如果真的做的到也是很好)，而是唯有這樣才能了解每一處細節。
本來以為辭職專心在這門課上可以每天過著規律的生活、早睡早起身體好，但自己常常在睡前寫作業直到上床後還一直在想，導致睡不著又爬起來繼續，日夜顛倒又失眠，睡眠品質也不好，所以可以看到我 commit 的時間或寫筆記的時間常常在半夜...幸好現在也只有修這門課，除了拜五外是可以睡到自然醒。
有時候自己也問自己，之前那樣爽爽過的生活不好嗎?工作時間也不算長、上班也沒什麼壓力、技術含量也不高、也很少上台被砲轟、錢也不算少。這樣的日子太安逸，沒人可以保證這間公司可以撐到我退休，會做這樣選擇的理由很實際，就是希望可以找到我理想中的工作，到現在我還不是很清楚什麼是我想要的工作，但我知道什麼我不想，我不想要==再過幾年後，我完全沒有選擇的自由==。
希望學期結束後我回頭看這段日子，會覺得一切都是值得的。
> 收件匣還看到有人跟我一樣在寫筆記，感到欣慰
> [name=Po-Jyun Chiou] [time=Mon, Oct 22, 2018 3:39 AM] [color=#907bf7]
Sign in with Wallet
Connect another wallet