# 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

.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)]

        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

    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)

                #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

    /* 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