Try   HackMD

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’
        • 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

  • 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)

  • 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
Last changed by 
 
Vincent Chen
0
598
Published on HackMD