# 2018q3 Homework4 (assessment)
contributed by < `happyincent` >
## Environment
```
$ cat <(echo "CPU: " `lscpu | grep "Model name" | cut -d':' -f2 | sed "s/ //"`) <(echo "OS: " `lsb_release -d | cut -f2`) <(echo "Kernel: " `uname -a | cut -d' ' -f1,3,14`) <(echo "gcc: " `gcc --version | head -n1`) <(echo "bash: " `bash --version | head -n1`)
CPU: Intel(R) Xeon(R) CPU E5520 @ 2.27GHz
OS: Ubuntu 16.04.5 LTS
Kernel: Linux 4.15.0-36-generic x86_64
gcc: gcc (Ubuntu 5.4.0-6ubuntu1~16.04.10) 5.4.0 20160609
bash: GNU bash, version 4.3.48(1)-release (x86_64-pc-linux-gnu)
```
## [第 4 週測驗題(上)](https://hackmd.io/s/HyyxpJE5X)
```c
#include <stdint.h>
int64_t abs64(int64_t x) {
int64_t y = x >> (64 - 1);
return (x ^ y) - y;
}
```
#### 運作原理
* x 的 signed bits 為 0 時
* y 為 `0x0000000000000000`
* (x ^ 0) - 0 還是 `x`
* x 的 signed bits 為 1 時
* y 為 `0xffffffffffffffff` (-1) (gcc)
* (x ^ y) - y
* x 做 [1's complement](https://en.wikipedia.org/wiki/Ones%27_complement) 後 - (-1)
```
x + ~x = -1 // 1's complement
~x - (-1) = x // (x ^ y) - y
```
* 與 x 做 [2's complement](https://en.wikipedia.org/wiki/Two%27s_complement) 相同
* Invert all the bits and add one to the result
* `>>` (右移)
* [C99 6.5.7](http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1124.pdf)
> 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.==
* [gcc - Integers](https://gcc.gnu.org/onlinedocs/gcc/Integers-implementation.html)
> Bitwise operators act on the representation of the value including both the **sign** and value bits, where the sign bit is considered immediately above the highest-value value bit. ==Signed ‘>>’ acts on negative numbers by sign extension.==
#### 延伸問題
* 可能的 overflow/underflow 議題
* 絕對值定義 [[wiki](https://en.wikipedia.org/wiki/Absolute_value)]
* 從 wiki 的 [2's complement](https://en.wikipedia.org/wiki/Two%27s_complement#Most_negative_number) 得知當 x 為 `int64_t` 中最小的負數 `0x8000000000000000` 時，會發生 ==overflow== (there was a carry into but not out of the most-significant bit)
```c
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
int64_t abs64(int64_t x) {
int64_t y = x >> (64 - 1);
return (x ^ y) - y;
}
int main()
{
int64_t minInt64 = 0x8000000000000000;
printf("0x%016lx %ld\n", minInt64, minInt64);
printf("0x%016lx %ld\n", abs64(minInt64), abs64(minInt64));
printf("0x%016llx %lld\n", llabs(minInt64), llabs(minInt64));
}
```
```
$ gcc -Wall a.c && ./a.out
0x8000000000000000 -9223372036854775808
0x8000000000000000 -9223372036854775808
0x8000000000000000 -9223372036854775808
```
* 二補數 `int64_t` 中的最小負數 `0x8000000000000000` 經過題目的 abs64 或是 `stdlib.h` 中的 llabs 輸出與原值相同，都不符合絕對值定義
* 0 經過 abs64、llabs 輸出 (0, +overflow) 與原值相同，但符合絕對值定義
* 搭配下方 pseudo-random number generator (PRNG) 和考量到前述 (1)，撰寫 `abs64` 的測試程式，並探討工程議題
```C=
static uint64_t r = 0xdeadbeef
int64_t rand64() {
r ^= r >> 12;
r ^= r << 25;
r ^= r >> 27;
return (int64_t) (r * 2685821657736338717);
}
```
* 能否在有限時間內對 int64_t 數值範圍測試完畢？
* 可以，根據 [xorshift wiki](https://en.wikipedia.org/wiki/Xorshift#xorshift*)，64-bit generator 最大值為 2^64^ -1 (`0xffffffffffffffff`)，因此可以測試完 `int64_t` 的所有數值
## [第 4 週測驗題(中)](https://hackmd.io/s/Syl6me49Q)
考慮以下程式碼:
```C=
int *global_var;
void f(void)
{
int x = 3;
global_var = &x;
...
/* Can the compiler perform TCO here? */
g();
}
```
* `(a)` 編譯器不可能施加 TCO
* `(b)` 編譯器一定可施加 TCO
* `(c)` 只要函式 `g` 沒有對 `global_var` 指標作 dereference，那麼 TCO 就有機會
思考程式註解，在第 8 行能否施加 TCO 呢？選出最適合的解釋。
Ans: None
### TCO 原理
#### Tail call
a tail call is a subroutine call performed as the final action of a procedure [[wiki](https://en.wikipedia.org/wiki/Tail_call)]
[example](http://www.ruanyifeng.com/blog/2015/04/tail-call.html):
* 函式 g 為 f 中最後執行的動作，g 即為 tail call
```
function f(x){
return g(x);
}
```
* 函示 g 之後還有別的動作，因此 g 不是 tail call
```
function f(x){
let y = g(x);
return y;
}
---
function f(x){
return g(x) + 1;
}
```
* stack frame
#### Tail call optimization (Elimination)
以 [tco-test](https://github.com/sysprog21/tco-test) 的 No arguments 為例:
> [__builtin_return_address](https://gcc.gnu.org/onlinedocs/gcc/Return-Address.html)
> This function returns the return address of the current function, or of one of its callers.
> A value of 0 yields the return address of the current function.
```c
#include <stdio.h>
void *first_ra;
void *second_ra;
void first_zero (void);
void second_zero (void);
void first_zero (void) { first_ra = __builtin_return_address(0); second_zero (); }
void second_zero (void) { second_ra = __builtin_return_address(0); }
int main()
{
printf("%-45s", "No arguments" ":");
first_zero();
printf(first_ra == second_ra ? "TCO\n" : "no TCO\n");
}
```
以 `-O0` 編譯
```
$ gcc -O0 a.c && ./a.out && gdb -q a.out
No arguments: no TCO
Reading symbols from a.out...(no debugging symbols found)...done.
gdb-peda$ disas first_zero
Dump of assembler code for function first_zero:
0x0000000000400526 <+0>: push rbp
0x0000000000400527 <+1>: mov rbp,rsp
0x000000000040052a <+4>: mov rax,QWORD PTR [rbp+0x8]
0x000000000040052e <+8>: mov QWORD PTR [rip+0x200b0b],rax # 0x601040 <first_ra>
0x0000000000400535 <+15>: call 0x40053d <second_zero>
0x000000000040053a <+20>: nop
0x000000000040053b <+21>: pop rbp
0x000000000040053c <+22>: ret
End of assembler dump.
gdb-peda$ disas second_zero
Dump of assembler code for function second_zero:
0x000000000040053d <+0>: push rbp
0x000000000040053e <+1>: mov rbp,rsp
0x0000000000400541 <+4>: mov rax,QWORD PTR [rbp+0x8]
0x0000000000400545 <+8>: mov QWORD PTR [rip+0x200afc],rax # 0x601048 <second_ra>
0x000000000040054c <+15>: nop
0x000000000040054d <+16>: pop rbp
0x000000000040054e <+17>: ret
End of assembler dump.
```
以 `-O1` 編譯
```
$ gcc -O1 a.c && ./a.out && gdb -q a.out
No arguments: TCO
Reading symbols from a.out...(no debugging symbols found)...done.
gdb-peda$ disas first_zero
Dump of assembler code for function first_zero:
0x0000000000400546 <+0>: mov rax,QWORD PTR [rsp]
0x000000000040054a <+4>: mov QWORD PTR [rip+0x200aef],rax # 0x601040 <first_ra>
0x0000000000400551 <+11>: mov QWORD PTR [rip+0x200af0],rax # 0x601048 <second_ra>
0x0000000000400558 <+18>: ret
End of assembler dump.
```
:::info
從 gdb 的結果中可以看出以`-O1` 做 TCO 最佳化後，`first_zero` 並沒有 call `second_zero`，而是直接將 `rax` assign 給 `second_ra`。
:::
### 題目解釋
改寫題目:
```c=
#include <stdio.h>
void *first_ra;
void *second_ra;
int *global_var;
int g()
{
second_ra = __builtin_return_address(0);
// int a = *global_var;
// global_var = &a;
// return *global_var;
}
void f(void)
{
first_ra = __builtin_return_address(0);
int x = 3;
global_var = &x;
g();
}
int main()
{
f();
printf(first_ra == second_ra ? "TCO\n" : "no TCO\n");
}
```
在以 `-O1` 編譯的情況下
* 只加第 10 行，雖然有對 `global_var` 指標做 dereference，但因為函示 return (0) 時沒有用到 `global_var` 因此輸出為 ==TCO==
* 只加第 11 行，改動到 `global_var` 因此輸出為 ==no TCO==
* 只加第 12 行，return 時用到 `global_var` 因此輸出為 ==no TCO==
## [第 4 週測驗題(下)](https://hackmd.io/s/By7Lwz4qm)
分別考慮以下 4 個程式，探討其行為。
- `ptr1.c`
```C
int main() { return *((int *) 0); }
```
- Ans: 在執行時期會造成 Segmentation fault
- 先將 0 轉型為 NULL pointer，再對 NULL pointer 做 dereference
> C99 - 6.5.3.2 - 4
If an invalid value has been assigned to the pointer, the behavior of the unary * operator is **undefined**.`87)`
`87)` Among the invalid values for dereferencing a pointer by the unary * operator are **a null pointer**, an address inappropriately aligned for the type of object pointed to, and the address of an object after the end of its lifetime.
- ==Segmentation fault== 訊息
```
(gdb) disas main
Dump of assembler code for function main:
0x00000000004004d6 <+0>: push rbp
0x00000000004004d7 <+1>: mov rbp,rsp
0x00000000004004da <+4>: mov eax,0x0
0x00000000004004df <+9>: mov eax,DWORD PTR [rax]
0x00000000004004e1 <+11>: pop rbp
0x00000000004004e2 <+12>: ret
End of assembler dump.
(gdb) r
Starting program: /home/ddl/a.out
Program received signal SIGSEGV, Segmentation fault.
0x00000000004004df in main () at a.c:1
```
- 以 gdb 看出在執行 `mov eax, DWORD PTR [rax]` 時發生 Segmentation fault
- Move 4 bytes at memory address rax (0x0) into eax
- the 64-bit version of 'EAX' is called 'RAX' ([x86 architecture](https://en.wikibooks.org/wiki/X86_Assembly/X86_Architecture))
- the caller can expect to find the return value of the subroutine in the register EAX ([x86 Assembly Guide](http://www.cs.virginia.edu/~evans/cs216/guides/x86.html))
- SIGSEGV
- an invalid access to storage, C99 7.14.3
- What happens in OS when we dereference a NULL pointer in C? [[stackoverflow](https://stackoverflow.com/questions/12645647/what-happens-in-os-when-we-dereference-a-null-pointer-in-c)]
- run user-level code in protected mode, which uses paging to convert virtual addresses into physical addresses.
- For each process, the OS keeps a page table which dictates how the addresses are mapped.
- if any memory access generates an invalid address, the processor raises a page fault exception. This triggers a transition from user mode into kernel mode
- The kernel regains control and, based on the information from the exception and the process's page table, figures out what happened.
- Page Fault handler [[source](https://mhackeroni.it/archive/2018/06/29/google-ctf-2018-execve-sandbox.html)]
- do_page_fault() Flow Diagram [[source](https://sungju.github.io/kernel/internals/memory_management)]
- `ptr2.c`
```C
int main() { return &*((int *) 0); }
```
- Ans: 是合法 C 程式，在執行後可透過 echo $? 得到 exit code 為 0
- `&*((int *) 0)` 等於 `((int *) 0)` 等於 a null pointer with the value 0
> C99 6.3.2.3 - 3
An integer constant expression with the **value 0**, or such an expression cast to type void *, is called a null pointer constant. If a null pointer constant is converted to a pointer type, the resulting pointer, called **a null pointer**
> C99 - 6.5.3.2 - 87)
&*E is equivalent to E (even if E is a null pointer)
- ==warning==: return makes integer from pointer without a cast [-Wint-conversion]
- 與 main 的 return type (int) 不同
- `ptr3.c`
```C
#include <stddef.h>
int main() { return &*NULL; }
```
- Ans: 是合法 C 程式，在執行後可透過 echo $? 得到 exit code 為 0
- 同 `ptr2.c`
> C99 7.17 - 3
The macros are **NULL** which expands to an **implementation-defined null pointer constant**;
- ==warning==:
- dereferencing ‘void *’ pointer
- C99 - 6.5.3.2 - 4
- return makes integer from pointer without a cast
- 與 main 的 return type (int) 不同
- `ptr4.c`
```C
#include <stddef.h>
int main() {
return &*(*main - (ptrdiff_t) **main);
}
```
- Ans: 是合法 C 程式，在執行後可透過 echo $? 得到 exit code 為 0
- `main`、`*main`、`**main` 為 function designator，被轉成 pointer 進行運算
> C99 6.5.3.2 - 4
The unary * operator denotes indirection. If the operand points to a function, the result is a **function designator**;
> C99 6.3.2 - 4
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’’.++
- `*main - (ptrdiff_t) **main` 運算完還是 pointer
> C99 7.17 - 2
The types are **ptrdiff_t** which is the **signed integer type** of the result of subtracting two pointers
> C99 6.5.6 - 8
When an expression that has **integer type** is added to or **subtracted from a pointer**, the result has the type of the **pointer** operand
- `&*(*main - (ptrdiff_t) **main)` == `*main - (ptrdiff_t) **main`
> C99 - 6.5.3.2 - 87)
&*E is equivalent to E (even if E is a **null pointer**)
- 小實驗
```c
#include <stdio.h>
#include <stddef.h>
typedef int (*func)();
int main()
{
__auto_type a1 = main - (ptrdiff_t)main;
__auto_type a2 = main - main;
// __auto_type a3 = (ptrdiff_t)main - main;
__auto_type b1 = &*( a1 );
// __auto_type b2 = &*( a2 );
printf("%d\n", __builtin_types_compatible_p( typeof(a1), func )); // 1
printf("%d\n", __builtin_types_compatible_p( typeof(a2), long int )); // 1
printf("%d\n", __builtin_types_compatible_p( typeof(b1), func )); // 1
/*
error: invalid operands to binary - (have ‘long int’ and ‘int (*)()’)
__auto_type a3 = (ptrdiff_t)main - main;
^
error: invalid type argument of unary ‘*’ (have ‘long int’)
__auto_type b2 = &*( a2 );
^
*/
}
```
> C99 6.2.5 - 18
Integer and floating types are collectively called **arithmetic types**
> C99 6.5.6
For subtraction, one of the following shall hold:
— both operands have arithmetic type;
— both operands are pointers to qualified or unqualified versions of compatible object types; or
==—== the left operand is a pointer to an object type and the right operand has integer type.
> C99 6.5.3.2 - 2
The operand of the unary * operator shall have pointer type.
- ==warning==: return makes integer from pointer without a cast [-Wint-conversion]
- 與 main 的 return type (int) 不同
## 閱讀啟發、學習感想
> 人不付出犧牲，就得不到任何回報。如果要得到什麼，就必須付出同等的代價，這就是鍊金術的基本原則，等價交換。當時我們深信著，這就是這世界的真理。------《鋼之鍊金術師》
Sign in with Wallet
Connect another wallet