# 2018q3 Homework1
contributed by <`ian910297`>
###### tags: `note`
實驗環境：使用 google cloud platform 服務，免費 300 美金額度，環境如下
```
Architecture: x86_64
CPU op-mode(s): 32-bit, 64-bit
Byte Order: Little Endian
CPU(s): 1
On-line CPU(s) list: 0
Thread(s) per core: 1
Core(s) per socket: 1
Socket(s): 1
NUMA node(s): 1
Vendor ID: GenuineIntel
CPU family: 6
Model: 62
Model name: Intel(R) Xeon(R) CPU @ 2.50GHz
Stepping: 4
CPU MHz: 2500.000
BogoMIPS: 5000.00
Hypervisor vendor: KVM
Virtualization type: full
L1d cache: 32K
L1i cache: 32K
L2 cache: 256K
L3 cache: 30720K
NUMA node0 CPU(s): 0
Flags: fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov pat pse36 clflush mmx fxsr sse sse2 ss ht syscall nx pdpe1gb rdtscp lm constant_tsc rep_good nopl xtopology nonstop_tsc cpuid pni pclmulqdq ssse3 cx16 pcid sse4_1 sse4_2 x2apic popcnt aes xsave avx f16c rdrand hypervisor lahf_lm pti fsgsbase tsc_adjust smep erms xsaveopt
```
如果實驗有需要好的配備，本機端也已經灌好 linux 系統，只是礙於平常要打電動，不便切換系統
# 指標篇
* 參考資料
- [ ] [指標篇共筆](https://hackmd.io/s/HyBPr9WGl)
- [x] [直播錄影(上)](https://www.youtube.com/watch?v=G7vERppua9o&feature=youtu.be)
- [x] [直播錄影(下)](https://www.youtube.com/watch?v=Owxols1RTAg)
* [頭腦體操](https://stackoverflow.com/questions/8208021/how-to-increment-a-pointer-address-and-pointers-value/8208106#8208106)
operator 優先權如下
1. `()`
2. `++`
3. `*`
我先是照做頭腦體操上面的程式碼，其中只有最後兩個部分，執行起來沒什麼問題，不太能理解為啥會發生 segfault
```clike=
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int main() {
char *ptr, *head;
head = ptr = malloc(sizeof(char) * 100);
strcpy(ptr, "Hello,World!");
printf("%c\n", *++ptr);
printf("%c\n", *(++ptr));
free(head);
return 0;
}
```
>你有 指標篇 (上) 對應的共筆嗎？
>[name=課程助教][color=red]
>應該是第一筆參考資料吧，只是我前幾天懶得寫筆記做實驗......，剛剛才發現連結貼錯
>[name=ian910297][color=blue]
* Understanding Declarations 取自 [C Traps and Pitfalls](http://www.literateprogramming.com/ctraps.pdf)
```clike=
(*(void(*)())0)();
```
一開始完全看不懂，只好先從 [C Traps and Pitfalls](http://www.literateprogramming.com/ctraps.pdf) 看一下他的解說，先解釋了幾個概念
```clike=
int main() {
int *g(), (*h)();
retrun 0;
}
```
* g is a function return pointer to int
* h is a pointer to function return int
:::warning
:question:
這邊有個點讓我很疑惑，在 main 裡面是可以宣告 function 的嗎？於是就查了一些資料 [Declaration of a function inside main()](http://qa.geeksforgeeks.org/2839/qa.geeksforgeeks.org/2839/declaration-of-a-function-inside-main.html)。反正，是可以宣告 function 的
:::danger
去 C99/C11 規格書找出對應的描述
:notes: jserv
:::
那就可以來解析這條式子了
1. `void (*)()` means `a pointer to function returning void`
2. `(*0)()` means `a pointer to function returning void` ，這個部份不太能理解怎麼把 0 轉型過去的，反正他就是這個意思
最後可以使用 `typedef` 將他簡化為下列的式子
```clike=
typedef void (*funcptr)();
(*(funcptr)0)();
```
有一題額外的練習題可以練習解構 [How to read this prototype?](https://stackoverflow.com/questions/15739500/how-to-read-this-prototype)
```clike=
void ( *signal(int sig, void (*handler)(int)) ) (int);
```
* signal is a pointer to function that takes two parameters
* a integer
* a pointer to function takes one parameter
* a integer
* return a void
* return a function pointer takes one parameter
* a interger
* return a void
* Go 語言也有指標
這個部份我現在就懶得看，因為還沒有要寫 golang
* 已經知道的部分 [C語言: 超好懂的指標](https://kopu.chat/2017/05/15/c%E8%AA%9E%E8%A8%80-%E8%B6%85%E5%A5%BD%E6%87%82%E7%9A%84%E6%8C%87%E6%A8%99%EF%BC%8C%E5%88%9D%E5%AD%B8%E8%80%85%E8%AB%8B%E9%80%B2%EF%BD%9E/)
老師在直播的時候有提到，當你宣告變數的時候，編譯器未必會把變數照順序放在記憶體位置上。使用 gdb 在觀察時發現，若有下 `-O` 相關的參數時，會完全找不到變數位置，我並不確定產生出來的程式碼是有什麼差別，以下使用 [godbolt](https://gcc.godbolt.org/) 做一些觀察
```clike=
int func() {
int a = 10;
int b = 100;
return b;
}
```
沒有參數時
```clike=
func():
push rbp
mov rbp, rsp
mov DWORD PTR [rbp-4], 10
mov DWORD PTR [rbp-8], 100
mov eax, DWORD PTR [rbp-8]
pop rbp
ret
```
參數為 `-O1`
```clike=
func():
mov eax, 100
ret
```
當有最佳化的時候，先不要管變數放在哪了，其實編譯器根本沒有把變數儲存到記憶體上，可能是直接塞一個 immediate value 到 register
* c 語言的一些想法
* 編譯器可以用 c 寫，不用使用別的語言。
* c 語言開發者的想法
* 開發 Unix 作業系統
* 充分掌握硬體、記憶體
* 代表的文化是 Unix
* [c99規格書](http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1256.pdf) 部分章節
* C99 [3.14] object
* region of data storage in the execution environment, the contents of which can represent values
* 記憶體位置
* The pronunciation of `&` is `address of`
* call-by-value
* C99 [6.2.5] types
*
* `void *`
`void *` 需要強制轉型，去做 alignment
```clike=
int main() {
char *X;
void *Y;
char c = *X;
char d = * (char *) Y;
}
```
* alignment
* pointer to pointer
為什麼要這樣設計？
因為 c 都是以 call by value 的形式在傳遞，這樣的設計可以讓我們在 function 裡面修改變數，透過 pointer to pointer ，可以規避 lifetime 一到 function 裡面宣告的變數就被清空
:::info
不見得會「被清空」，這與編譯器實作有關
參見 [2018q1 第 11 週測驗題](https://hackmd.io/s/r1zL9gnaf) 測驗 2，試著作答並解釋 clang 和 gcc 行為的落差。
:notes: jserv
:::
題目是解釋這段程式碼在 clang 和 gcc 行為的落差
```clike=
int main(int argc, char *argv[]) {
char *p, *q;
uintptr_t pv, qv;
{
char a = 3;
p = &a;
pv = (uintptr_t) p;
}
{
char b = 4;
q = &b;
qv = (uintptr_t) q;
}
if (p != q) {
printf("%p is different from %p\n", (void *) p, (void *) q);
printf("%" PRIxPTR " is not the same as %" PRIxPTR "\n", pv, qv);
} else {
printf("Surprise!\n");
}
return 0;
}
```
首先我們可以看到要比較的兩個變數 `pv`, `qv` ，他們的型態是 `uintptr_t`，這是一個會根據現在是什麼位元的系統，去做相對應的型態
使用 [godbolt](https://gcc.godbolt.org/) 做一些觀察
* clang6.0.0
```clike=
main: # @main
push rbp
mov rbp, rsp
sub rsp, 64
lea rax, [rbp - 50]
lea rcx, [rbp - 49]
mov dword ptr [rbp - 4], 0
mov dword ptr [rbp - 8], edi
mov qword ptr [rbp - 16], rsi
mov byte ptr [rbp - 49], 3 /* char a = 3; */
mov qword ptr [rbp - 24], rcx /* p = &a; */
mov rcx, qword ptr [rbp - 24] /* pv = (uintptr_t) p; */
mov qword ptr [rbp - 40], rcx /* pv = (uintptr_t) p; */
mov byte ptr [rbp - 50], 4 /* char b = 4; */
mov qword ptr [rbp - 32], rax /* q = &b; */
mov rax, qword ptr [rbp - 32] /* qv = (uintptr_t) q; */
mov qword ptr [rbp - 48], rax /* qv = (uintptr_t) q; */
mov rax, qword ptr [rbp - 24] /* if (p != q) { */
cmp rax, qword ptr [rbp - 32] /* if (p != q) { */
je .LBB0_2 /* if (p != q) { */
```
* gcc7.2.0
```clike=
main:
push rbp
mov rbp, rsp
sub rsp, 64
mov DWORD PTR [rbp-52], edi
mov QWORD PTR [rbp-64], rsi
mov BYTE PTR [rbp-33], 3 /* char a = 3; */
lea rax, [rbp-33] /* p = &a; */
mov QWORD PTR [rbp-8], rax /* p = &a; */
mov rax, QWORD PTR [rbp-8] /* pv = (uintptr_t) p; */
mov QWORD PTR [rbp-16], rax /* pv = (uintptr_t) p; */
mov BYTE PTR [rbp-34], 4 /* char b = 4; */
lea rax, [rbp-34] /* q = &b; */
mov QWORD PTR [rbp-24], rax /* q = &b; */
mov rax, QWORD PTR [rbp-24] /* qv = (uintptr_t) q; */
mov QWORD PTR [rbp-32], rax /* qv = (uintptr_t) q; */
mov rax, QWORD PTR [rbp-8] /* if (p != q) { */
cmp rax, QWORD PTR [rbp-24] /* if (p != q) { */
je .L2 /* if (p != q) { */
```
兩者主要差異是在做 `&`(address of) 時，讓我們鎖定有使用到的 register rax
* clang 的實作是 mov
* mov 會直接改變數值
* value of p is qword ptr [rbp - 24]
* value of q is qword ptr [rbp - 32]
* rax 的地址從頭到尾都在 [rbp - 50] 上
* gcc 的實作是 lea, mov
* lea 是間接改變數值，他會先載入那個位置的地址
* value of p is QWORD PTR [rbp - 8]
* value of q is QWORD PTR [rbp - 24]
* rax 的地址一直在改變，從 [rbp - 33] 到 [rbp - 34]
答案我認為是 (d)
gcc 的實作與規格書不符，他不應該可以操作 [rbp - 34] ，照規格書來看 lifetime 已經結束
* 找 *** 的 project
:::info
提示: 數學運算相關專案很容易看到
:notes: jserv
:::
在 github 上翻了半天，數學運算相關的專案，不知道為啥就是沒看到，不過看到一些奇怪的地方有用到 <s>triple pointer</s> the pointer to the pointer to the pointer ，大多是在開啟檔案讀資料的時候。
:::danger
不要濫用詞彙，務必依據 C 語言規格書來描述
:notes: jserv
:::
>好的，我會更加注意
>[name=ian910297][color=blue]
在 github 下載專案後，我都是使用 grep 來搜尋在哪邊有使用到
```shell
grep -F "***" --include=\*.c -r ./
```
以下是在 [jakogut/tinyvm](https://github.com/jakogut/tinyvm.git) 專案裡面，有發現到 the pointer to the pointer to the pointer 的應用
檔案 [libtvm/tvm_lexer.c](https://github.com/jakogut/tinyvm/blob/master/libtvm/tvm_lexer.c)
```clike=52
/* NULL terminate the array to make iteration later easier*/
lexer->source_lines[i] = NULL;
/* Split the source into individual tokens */
for (i = 0; lexer->source_lines[i]; i++) {
lexer->tokens = (char ***)realloc(
lexer->tokens, sizeof(char **) * (i + 2));
lexer->tokens[i] = (char **)calloc(MAX_TOKENS, sizeof(char *));
tokp = strtok(lexer->source_lines[i], " \t,");
for (j = 0; (tokp && j < MAX_TOKENS); j++) {
char *token = tvm_htab_find_ref(defines, tokp);
token = token ? token : tokp;
lexer->tokens[i][j] = calloc(1, (strlen(token) + 1));
strcpy(lexer->tokens[i][j], token);
tokp = strtok(NULL, " \t,");
}
}
```
lexer 顧名思義是用來解析文字，將其切成一個一個 token 的程式，讓我們看一下現在 lexer 這個物件是什麼
檔案 [include/tvm/tvm_lexer.h](https://github.com/jakogut/tinyvm/blob/master/include/tvm/tvm_lexer.h)
```clike=9
struct tvm_lexer_ctx {
char **source_lines;
char ***tokens;
};
```
`lexer->tokens` 的部分，在每次遞迴時，都不斷重複<s>調用</s> 呼叫 `realloc()` ，因為已經執行過 `calloc()` ，只需要重新調整空間即可，再來就不斷的把 `token` 塞進 `lexer->tokens[i]` 裡面
:::success
call 和 invoke 在繁體中文的翻譯是「呼叫」
:notes: jserv
:::
這邊 *** 主要應用是根據檔案有多少行(lines)來儲存相對應的 `token`
* forward declaration
這個部份我有一個疑問，記得以前學過 function prototype ，這個東西聽起來跟他很像，先查閱 [c99規格書](http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1256.pdf)
* C99 [6.2.1] Scope of identifiers
* A function prototype is a declaration of a function that declares the type of its parameters
* array v.s. pointer
不能變更為 pointer
```clike=
// In declaration
extern char x[];
char a[10];
```
以前在寫字串的時候，覺得這樣操作是合法的，沒有思考過 pointer 本質上就是只有一個 word 長度的變數( pointer 的 size 會依據不同位元的作業系統來做一些改變)，是透過儲存地址來指向目標
```clike=
int main() {
char a[10];
strcpy(a, "abcdefghij");
printf("%s\n", a);
printf("%c\n", *a);
printf("%c\n", *(a+1));
return 0;
}
```
可以變更為 pointer
```clike=
// In declaration
func(char x[]);
func(char *x);
// In expression
int main() {
int x[10] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
printf("%d %d %d %d\n", x[4], *(x + 4), *(4 + x), 4[x]);
}
```
c 沒有真正的陣列，只有 C99 [6.5.2.1] <b>Array subscripting</b>
* 使用 gdb 做實驗
```clike=
struct tags {
int a;
double b[3];
char token[20];
};
int main() {
struct tags var[17];
int a[10][10];
return 0;
}
```
最基礎的指令
```shell=
# print
p var
# eval
p var.a = 10
```
:::info
GDB 的 pretty print 很好用，參見:
* [GDB Manual](https://sourceware.org/gdb/onlinedocs/gdb/Pretty_002dPrinter-Commands.html)
* [不為人知的gdb 使用方式系統-gdb pretty printer](https://yodalee.blogspot.com/2016/09/gdb-gdb-pretty-printer.html)
:notes: jserv
:::
在觀察 structure 時，可以先做一些設定以便閱讀
```shell=
(gdb) p var[0]
$1 = {a = -10176, b = {6.9533488729516863e-310, 0, 6.9533490664387614e-310},
token = "\340\333\377\377\001\000\000\000\312\a\000\000\000\000\000\000\006\000\000\000\000\000\000\000@\330\377\377\377\177\000\000\240b\000\000\003\000\000\000@\341\377\367\377\177\000\000`\355\377\367\377\177\000\000\000\000\000\000\000\000\000\000\001\b\000\000\000\000\000\000\312\a\000\000\000\000\000\000\001\000\000\000\000\000\000\000\355\201\000\000\000\000\000\000\000\000\000"}
(gdb) set print pretty
(gdb) p var[0]
$2 = {
a = -10176,
b = {6.9533488729516863e-310, 0, 6.9533490664387614e-310},
token = "\340\333\377\377\001\000\000\000\312\a\000\000\000\000\000\000\006\000\000\000\000\000\000\000@\330\377\377\377\177\000\000\240b\000\000\003\000\000\000@\341\377\367\377\177\000\000`\355\377\367\377\177\000\000\000\000\000\000\000\000\000\000\001\b\000\000\000\000\000\000\312\a\000\000\000\000\000\000\001\000\000\000\000\000\000\000\355\201\000\000\000\000\000\000\000\000\000"
}
```
相關設定，我們可以寫在 `~/.gdbinit` 檔案裏面，避免每次都要重新輸入
```shell=
# print pretty structure
set print pretty
# 保存歷史命令
set history filename ./.gdb_history
set history save on
```
也可以在裡面定義屬於自己的格式，在 gdb 定義自己的 command
* [User-defined commands](ftp://ftp.gnu.org/old-gnu/Manuals/gdb/html_node/gdb_188.html)
```clike=
define printhello
print "Hello, World!"
end
```
可以透過下列指令來查看已定義的 command
```shell=
show user
show user printhello
```
介紹了這些，再來就是做個簡單的練習，自定義一個專屬的格式，來印出我的 structure ，目標是不要印出數字
```clike=
define printtags
set $i = 0
set $len = strlen($tags_token)
printf "(tags token) %s, (length) %d\n", $tags_token, $len
while $i < $len
set $c = $tags_token[$i++]
if $c <48 || $c > 57
printf "%c", $c
end
end
printf "\n"
end
```
需要做一點前置處理，因為這是 User-defined command 不是 function or macro ，不能傳遞參數進去，必須要先指定好要用的變數是什麼
```shell=
Reading symbols from a.out...done.
(gdb) b 12
Breakpoint 1 at 0x400560: file var.c, line 12.
(gdb) r
Starting program: /home/ian910297/c/a.out
Breakpoint 1, main () at var.c:13
13 return 0;
(gdb) p strcpy(var[0].token, "Hello, 1234World!")
$1 = -8304
(gdb) set $tags_token = var[0].token
(gdb) printtags
(tags token) Hello, 1234World!, (length) 17
Hello, World!
```
gdb 還有一個東西叫做 [pretty printer](https://sourceware.org/gdb/onlinedocs/gdb/Pretty-Printing.html#Pretty-Printing) ，可以讓我們更輕易達到目的，不一定要使用 User-defined command
而且在 gdb v7 之後開始支援 python ，所以我們可以使用 python 來撰寫 pretty-printer
先來一個簡單的範例程式，依據 [23.2.2.5 Pretty Printing API](https://sourceware.org/gdb/onlinedocs/gdb/Pretty-Printing-API.html#Pretty-Printing-API) 裡面有提到，我們必須宣告一個 class 可以有四個 Function
* to_string
* necessnary
*
* display_hint
* optional
* 只有三種回傳值
* array
* map
* string
* children
* optional
*
* default_visualizer
```python=
import gdb.printing
class Tags(object):
def __init__(self, val):
self.val = val
def to_string(self):
return "I'm tags!"
pp = gdb.printing.RegexpCollectionPrettyPrinter('TagsPrettyPrinter')
pp.add_printer('Tags', '^tags', Tags)
gdb.printing.register_pretty_printer(gdb.current_objfile(), pp)
```
原來要在 gdb 裡面載入 python 程式，直接做使用，我一開始在嘗試使用 pip 安裝 gdb package ，然後發現完全找不到
```shell=
Reading symbols from a.out...done.
# load pretty printer
(gdb) source tags.py
# list pretty printer
(gdb) info pretty-printer
global pretty-printers:
TagsPrettyPrinter
Tags
builtin
mpx_bound128
(gdb) b 12
Breakpoint 1 at 0x400560: file var.c, line 12.
(gdb) r
Starting program: /home/ian910297/c/a.out
Breakpoint 1, main () at var.c:13
13 return 0;
(gdb) p var
$1 = {I'm tags, I'm tags, I'm tags, I'm tags, I'm tags, I'm tags, I'm tags, I'm tags, I'm tags, I'm tags, I'm tags, I'm tags, I'm tags, I'm tags, I'm tags, I'm tags, I'm tags}
(gdb)
```
如果要有跟上面 User-defined command 一樣的效果， to_string() 要做一些改寫
```python=
addr = self.val.address
token = self.val['token']
strlen = len(token)
i = 0
content = []
while i < strlen:
c = token[i]
if c <48 or c>57:
content.append(chr(c))
i = i + 1
return '(token)%s (length=%d): "%s"' % (addr, strlen, "".join(content))
```
不知道為什麼一直執行失敗，顯示 `Python Exception <class 'NotImplementedError'> Invalid operation on gdb.Value.:`
發現是不能呼叫 len() ，猜測可能是 char 型態的問題，導致呼叫 len() 失敗，但我實在懶得理他，反正把字串長度寫死就好了
```shell=
Reading symbols from a.out...done.
(gdb) b 12
Breakpoint 1 at 0x400560: file var.c, line 12.
(gdb) r
Starting program: /home/ian910297/c/a.out
Breakpoint 1, main () at var.c:13
13 return 0;
(gdb) source tags.py
(gdb) p strcpy(var[0].token, "Hello, 1234World!")
$1 = -8304
(gdb) p var[0]
$2 = (token)Hello, 1234World! (pretty printer)Hello, World!
```
查了一堆 GDB 的資料，學到不少用法，還是覺得稍嫌無聊，記得以前看過一個專案 [CS:APP二进制炸弹开篇](https://blog.csdn.net/astrotycoon/article/details/73201149)([檔案下載](https://github.com/astrotycoon/CS-APP-binary-bomb))，是搭配課本第三章使用的 LAB ，感覺是一個蠻好玩的 GDB 練習，但難度有點高
* 字串操作
```clike=
char *r = malloc(strlen(s) + strlen(t) + 1); // use sbrk; change progrram break
if (!r) exit(1); /* print some error and exit */
strcpy(r, s); strcat(r, t);
```
可能錯誤
* 呼叫 `strcpy`, `strcat` 時，可能會因為字串過長，超出原本配置的記憶體空間，導致錯誤
* `malloc` 也可能失敗
解決方法
* 每次檢查 `malloc` 的回傳結果
* 多給一點記憶體
:::warning
:question:
1. 實際應用時，會有這樣記憶體配置相關的錯誤，但比如說 c++ 就有 `vector` 的型態可以使用，不知道這又是怎麼實作，可能用 c 實作出 `vector` 的效果嗎？
2. 找一個 strdup 的 invalid example
:::
在 github 上找到一個專案 [eteran/c-vector](https://github.com/eteran/c-vector) ，使用 c 實作 `std::vector`
```clike=
```
* function pointer
Sign in with Wallet
Connect another wallet