# 2018q3 Homework2 (lab0)
contributed by < happyincent >
## Environment
#### VM
```
$ cat <(echo) <(echo "CPU: " `lscpu | grep "Model name" | cut -d' ' -f12-17`) <(echo "OS: " `lsb_release -d | cut -f2`) <(echo "Kernel: " `uname -a | cut -d' ' -f1-3,14`) <(echo "gcc: " `gcc --version | head -n1`) <(echo "ldd: " `ldd --version | head -n1`) <(echo "Make: " `make --version | head -n1`)
CPU: Intel(R) Core(TM) i5-2400 CPU @ 3.10GHz
OS: Ubuntu 18.04.1 LTS
Kernel: Linux xubuntu 4.15.0-36-generic x86_64
gcc: gcc (Ubuntu 7.3.0-27ubuntu1~18.04) 7.3.0
ldd: ldd (Ubuntu GLIBC 2.27-3ubuntu1) 2.27
Make: GNU Make 4.1
```
#### RPi
```
$ cat <(echo) <(echo "CPU: " `lscpu | grep "Model name" | cut -d' ' -f14-18`) <(echo "OS: " `lsb_release -d | cut -f2`) <(echo "Kernel: " `uname -a | cut -d' ' -f1-3,12`) <(echo "gcc: " `gcc --version | head -n1`) <(echo "ldd: " `ldd --version | head -n1`) <(echo "Make: " `make --version | head -n1`)
CPU: ARMv7 Processor rev 4 (v7l)
OS: Raspbian GNU/Linux 9.4 (stretch)
Kernel: Linux raspberrypi 4.14.52-v7+ armv7l
gcc: gcc (Raspbian 6.3.0-18+rpi1+deb9u1) 6.3.0 20170516
ldd: ldd (Debian GLIBC 2.24-11+deb9u3) 2.24
Make: GNU Make 4.1
```
## Makefile
* 加上 `-std=gnu11`、嘗試 Implicit Rules、加上 dependency
```diff
.PHONY: dep test clean
CC = gcc
CFLAGS = -O0 -g -Wall -Werror -std=gnu11
GIT_HOOKS := .git/hooks/applied
all: $(GIT_HOOKS) qtest
$(GIT_HOOKS):
@scripts/install-git-hooks
@echo
# queue.o: queue.c queue.h harness.h
# $(CC) $(CFLAGS) -c queue.c
# qtest: qtest.c report.c console.c harness.c queue.o
# $(CC) $(CFLAGS) -o qtest qtest.c report.c console.c harness.c queue.o
queue.o: queue.c queue.h harness.h
qtest: qtest.c report.c console.c harness.c queue.o
dep:
@$(CC) -MM *.c
@$(CC) -M *.c > depend
test: qtest scripts/driver.py
scripts/driver.py
clean:
rm -f *.o *~ qtest depend
rm -rf *.dSYM
(cd traces; rm -f *~)
```
* `.PHONY`
* A phony target is one that is not really the name of a file. [[source](https://www.gnu.org/software/make/manual/html_node/Phony-Targets.html#Phony-Targets)]
* `CFLAGS` [[source](https://gcc.gnu.org/onlinedocs/gcc/Option-Summary.html)]
* `-O0`: 關閉優化，default optimization level
* `-g`: Options for Debugging
* `-Wall`: 啟用容易被避免的 warnings
* `-Werror`: Make all warnings into errors.
* `-std=gnu11`
* gcc version 6.3.1 - 7.3.1: default is '-std=gnu11' [[source](https://stackoverflow.com/a/44057210)]
* GNU C Library 有 ISO C 也有 POSIX [[source](https://www.gnu.org/software/libc/manual/html_node/Introduction.html#Introduction)]
* 若用 `-std=c11` 會無法編譯
* `console.h`: unknown type name ‘fd_set’
* `fd_set` 定義在 <sys/select.h> 屬於 [C POSIX library](https://en.wikipedia.org/wiki/C_POSIX_library) 而非 ISO C
* `harness.c`: implicit declaration of function ‘random’ (‘sigsetjmp’)
* 同上述原因, random: <stdlib.h> ([BSD Random](https://www.gnu.org/software/libc/manual/html_node/Pseudo_002dRandom-Numbers.html)), sigsetjmp: <setjmp.h>
* `$(GIT_HOOKS)`
* target 設為 .git/hooks/applied
* 執行 `scripts/install-git-hooks` 時會 touch 檔案: `.git/hooks/applied`
* 第二次後 Make 時因為 `$(GIT_HOOKS)` 檔案已存在且這個 target 沒有 prerequisites 需要確認，因此 Make 會認為已經 up to date 便不會再執行
```
$ rm .git/hooks/applied
$ make clean all > /dev/null && ls -l .git/hooks/applied
-rw-rw-r-- 1 ddl ddl 0 Oct 3 02:40 .git/hooks/applied
$ make clean all > /dev/null && ls -l .git/hooks/applied
-rw-rw-r-- 1 ddl ddl 0 Oct 3 02:40 .git/hooks/applied
$ make .git/hooks/applied
make: '.git/hooks/applied' is up to date.
```
* install-git-hooks 在 [.git/hooks](https://git-scm.com/book/zh-tw/v2/Customizing-Git-Git-Hooks) 建立兩個在 commit 前會執行的 scripts
* pre-commit: clang-format (檢查格式)、cppcheck (檢查 bugs)
* commit-msg: 檢查 commit message ([git-good-commit](https://github.com/tommarshall/git-good-commit))
* a line starts with`@`: 不 echo 該行指令 ([Recipe Echoing](https://www.gnu.org/software/make/manual/html_node/Echoing.html#Echoing))
* `:=` : Simply expanded variables, `=` : recursively expanded variables,
`?=` : conditional variable assignment [[source](https://www.gnu.org/software/make/manual/html_node/Flavors.html)]
```make
A = $(B)
B = $(C)
C ?= World!
C ?= World!!!
X := Hello $(A)
Y = Hello $(A)
C = DDL!
all:
@echo $(X) ## Hello World!
@echo $(Y) ## Hello DDL!
```
* `all`
* default target ([Standard Targets](https://www.gnu.org/software/make/manual/html_node/Standard-Targets.html))
* `queue.o, qtest`
* `-c`: compile or assemble the source files, but do not link
* `-o file`: output in file *file*
* 如果 rule 中沒有 recipe，Make 會依據 target、prerequisites (the source files) 來決定 [Implicit Rules](https://www.gnu.org/software/make/manual/html_node/Using-Implicit.html#Using-Implicit) ([recursively](https://www.gnu.org/software/make/manual/html_node/Implicit-Rule-Search.html#Implicit-Rule-Search))
* [Built-In Rules](https://www.gnu.org/software/make/manual/html_node/Catalogue-of-Rules.html#Catalogue-of-Rules): Compiling C programs、Linking a single object file
* `dep` [[source](https://gcc.gnu.org/onlinedocs/gcc/Preprocessor-Options.html#Preprocessor-Options)]
* `-M`: output a rule suitable for make describing the dependencies of the main source file
* `-MM`: 找出非 include 系統且非間接 include 的 source file dependencies
```
$ make dep
console.o: console.c console.h report.h
harness.o: harness.c report.h harness.h
qtest.o: qtest.c harness.h queue.h console.h report.h
queue.o: queue.c harness.h queue.h
report.o: report.c report.h
```
* `test`
* prerequisites: qtest、scripts/driver.py
* 不帶參數執行 scripts/driver.py，依據 ./traces/*.cmd 執行 qtest 並算出分數
* `clean`
* 刪掉 make 出來的 .o、執行檔等
* `.dSYM`: [debug symbols](https://en.wikipedia.org/wiki/Debug_symbol)
* `*~`: 編輯器備份檔
## queue
* Queue Structure
```c
typedef struct {
list_ele_t *head; /* Linked list of elements */
list_ele_t *tail;
size_t q_size; /* Linked list's size */
} queue_t;
```
* 加入 `size_t q_size` 來達成在 O(1) 時間內得到 queue elements 的數目
* size_t: unsigned integer type
* `sizeof(long) = sizeof(size_t)` [[stackoverflow: size_t ](https://stackoverflow.com/questions/46508831/is-the-max-value-of-size-t-size-max-defined-relative-to-the-other-integer-type)]
* Limit of size_t type [[stdint.h](https://code.woboq.org/userspace/glibc/sysdeps/generic/stdint.h.html)]
* SIZE_MAX: 18446744073709551615 (64 bit), 4294967295 (32 bit)
```c
#include <stdio.h>
#include <stdint.h>
int main() {
printf("SIZE_MAX: %lu\n", SIZE_MAX);
size_t a = 18446744073709551615U;
printf("(%lu + 1) > 1: %s\n", a, (a + 1 > 1) ? "true" : "false");
}
```
```
$ gcc -Wall a.c && ./a.out
SIZE_MAX: 18446744073709551615
(18446744073709551615 + 1) > 1: false
```
* 加入 `list_ele_t *tail` 紀錄 queue 中 tail element 的位址
* q_insert_head
* [本來](https://github.com/happyincent/lab0-c/commit/291b8d95e8605b95dfd851a66d137e77ce8824c6)將 insert 的存放字串另外寫成 `static inline list_ele_t *ele_new(char *s)`，但發現會造成更多的 jmp (BL, BNE, ...) 次數
* gcc `-O0` (optimization level 0) 時可能不會展開 inline [[source](https://www.cnblogs.com/cnmaizi/archive/2011/01/19/1939686.html)] [[gcc-inline](https://gcc.gnu.org/onlinedocs/gcc/Inline.html)]
* 除非在 function 加上 **`__attribute__((always_inline))`** 強制做 inline
* q_reverse
```c
/* iterate the queue to reverse each next pointer */
list_ele_t *left = q->head;
list_ele_t *right = NULL;
list_ele_t *tmp = NULL;
q->tail = left;
while (left != NULL) {
tmp = left->next;
left->next = right;
right = left;
left = tmp;
}
q->head = right;
```
## 比較不同環境的 Grade 分數
#### 結論: 我沒有能力把 C 寫到 -O0 和 -O1 一樣好
* 分別以 optimization level: `-O0` (下圖左)、`-O1` (下圖右) compile [queue.c](https://github.com/happyincent/lab0-c/blob/82d82fefa826be23ae11528d627a996043383b75/queue.c)，並比較 IDA Pro disassemble 後 `q_insert_head` 的 graph 圖
* 在 **VM** 環境下 (gcc Ubuntu 7.3.0)
* `O0` 最多需 8 次 jmp
* `O1` 最多需 6 次 jmp
* 在 **RPi** 環境下 (gcc Raspbian 6.3.0)
* `O0` 最多需 6 次 jmp
* `O1` 最多需 3 次 jmp
#### 執行結果
* 在 **RPi** 環境 `-O0`
* 從 trace 13 開始就會因為 ih 或 it 的次數較大發生 **`ERROR: Time limit exceeded`**
```
ddl@raspberrypi:~/lab0-c $ make clean all test
...
+++ TESTING trace trace-13-perf:
# Test performance of insert_tail
ERROR: Time limit exceeded. Either you are in an infinite loop, or your code is too inefficient
ERROR: Insertion of dolphin failed (1 failures total)
--- trace-13-perf 0/7
...
```
* 使用 [grade.sh](https://github.com/happyincent/lab0-c/blob/master/grade.sh) 分別以 `-O0, -O1, -O2, -O3` 測試 10 次並計算平均分數 (timeout 10 秒 total = 0)
* **VM** 環境
```
ddl@xubuntu:~/Desktop/sysprog/lab0-c$ ./grade.sh
-O0 grade: 100
-O1 grade: 100
-O2 grade: 100
-O3 grade: 100
```
* **RPi** 環境
```
ddl@raspberrypi:~/lab0-c $ ./grade.sh
-O0 grade: 23
-O1 grade: 98
-O2 grade: 98
-O3 grade: 99
```
Sign in with Wallet
Connect another wallet