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]

• CFLAGS [source]

  • -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]
      • GNU C Library 有 ISO C 也有 POSIX [source]
    • 若用 -std=c11 會無法編譯
      • console.h: unknown type name ‘fd_set’
        • fd_set 定義在 <sys/select.h> 屬於 C POSIX library 而非 ISO C
      • harness.c: implicit declaration of function ‘random’ (‘sigsetjmp’)
        • 同上述原因, random: <stdlib.h> (BSD Random), 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 建立兩個在 commit 前會執行的 scripts
      • pre-commit: clang-format (檢查格式)、cppcheck (檢查 bugs)
      • commit-msg: 檢查 commit message (git-good-commit)
  • a line starts with@: 不 echo 該行指令 (Recipe Echoing)
  • := : Simply expanded variables, = : recursively expanded variables,
    ?= : conditional variable assignment [source]
    ​​​​​​​​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)

• 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 (recursively)
    • Built-In Rules: Compiling C programs、Linking a single object file

• dep [source]

  • -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
  • *~: 編輯器備份檔

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 ]
      • Limit of size_t type [stdint.h]
        • 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

  • 本來將 insert 的存放字串另外寫成 static inline list_ele_t *ele_new(char *s)，但發現會造成更多的 jmp (BL, BNE, …) 次數
    • gcc -O0 (optimization level 0) 時可能不會展開 inline [source] [gcc-inline]
      • 除非在 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，並比較 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 分別以 -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