Try   HackMD

How C programs work

(返回2016年暑期系統軟體課程:台南場次)

有所變,有所不變

  • source: twitter

  • USD $5995 (而且是 35 年前的物價!) 只能買到 8-bit 微處理器,搭配 64 KB 主記憶體和 10 MB 硬碟。有趣的是,當時軟體開發的模式部分還延續至今

    • 硬體突飛猛進,軟體的問題依舊還在

Maslow’s pyramid of code review

  • 21 世紀的軟體開發均已規模化,絕非「有就好」,而是持續演化和重構,code review 是免不了的訓練
  • uber 工程師 Charles-Axel Dein 認為好的程式碼應該要:
    • [ Correct ] : 做到預期的行為了嗎?能夠處理各式邊際狀況嗎?即便其他人修改程式碼後,主體的行為仍符合預期嗎?
    • [ Secure ] : 面對各式輸入條件或攻擊,程式仍可正確運作嗎?
    • [ Readable ] : 程式碼易於理解和維護嗎?
    • [ Elegant ] : 程式碼夠「美」嗎?可以簡潔又清晰地解決問題嗎?
    • [ Altruist ] : 除了滿足現有的狀況,軟體在日後能夠重用嗎?甚至能夠抽離一部分元件,給其他專案使用嗎?
  • 「需求」層次: 正確 → 安全 → 可讀 → 優雅 → 利他
  • @徐元豪 : 「工程師都會寫程式,但是 (往往) 欠了 code review 的能力。code review 不是用來戰別人,而是訓練自己如何看得懂別人程式、了解別人的想法,常看人家的程式,無形中是在訓練自己。」
  • @Chaoint  : 「沒關係。」總是講給自己聽的。
  • 「人們不敘述自己的過往,而是為自己的過往作證。」—— Frantz Fanon
  • 「如果你把游泳池當作浴缸泡著,再泡幾年還是不會游泳」 jserv

延伸閱讀: Code Reading

  • 大量篇幅回顧 C 語言概念,以及在真實世界中的程式如何展現,細節!

什麼叫做簡潔?

尤拉猜想是 Euler 在 1769 年對費馬定理的延伸: n 個正整數的 k 次方的總和,若是另一個正整數的 k 次方,則 n 不可能小於 k。n = 2 就是費馬最後定理,不過這個猜想在 1966 年被號稱「最短論文」給否定。

延伸閱讀:

「事實」很容易被遮蔽,所以我們要 Benchmark / Profiling

source: twitter

《進擊的鼓手》之後

"No pain, no gain"

source: CSAIL at MIT twitter

理解系統程式

計算機結構的改變

source ]

  • 早年計算能力相對低的年代,常常有用查表法代替計算,有空間換取時間的做法,來增進效能。 那個時候 個人電腦的 CPU 可以在一個時脈週期中讀取一筆資料,但是要做乘法計算則需要幾十個時脈週期,所以用查表的比較快。除法和超越函數更是如此,而現在還有一些低階的處理器,還在用這些技巧。

  • 後來當 CPU 時脈提高,但記憶體存取相對變慢的時候,我們必須反過來減少記憶體存取的次數,所以高階處理器 cache 越來越大,做 data  prefetch 來提早取得資料、使用 multi-threaded  architecture 來容忍資料遲到的狀況、使用壓縮的方式傳送資料,甚至還會用 speculation 的方式來猜測資料是在哪裡和是什麼。

  • 在多處理機和多核心電腦上,存取資料的問題更嚴重,除了時間延遲和頻寬之外,還要考慮到尖峰時刻塞車的問題,所以有時候簡單的工作,就可能就不分工了,要不就由一個 CPU 代表去做,做完把結果給大家,要不就大家都做同樣的事情。前者多半在有共享記憶體的多核心處理器上看到,後者多半在分散式的系統看到。

  • 到了異質計算的年代,CPU 和 GPU 的分工,更需要好好地做效能分析。因為傳統 GPU 和 CPU 不共享記憶體,透過較慢的 PCIe  Bus 交換資料,所以有些工作 CPU 自己做比較快。另一方面,當 GPU 有超過 2000 個核心的時候,用重複的計算 (redundant  computation)取代資料交換,也是常見的事。

  • 更進一步談巨量資料,為了節省資料的取得時間,我們往往費盡心思。我們花時間將資料和計算擺在同一個地方,做所謂的 data computation  co-location,將重複出現的資料利用 data  deduplication 技術節省儲存空間和取得時間,用一堆目錄 (indexing) 讓資料可以快速被找到。

  • 當計算機結構有所不同時,優化的策略可能會隨之而變,不能食古不化。但原理雖然簡單,系統和實作技巧卻越來越複雜,軟硬體優化的機會越來越多,可惜能夠真正連通理論和實務的人則越來越少。

  • 以上這些技術,講起來很容易,但在實作上,必須先搞清楚運算和資料的相對位置、距離、時間先後、相依性、數量等等,才知道該如何取捨。但很多人根本不會用效能分析工具,就在那邊瞎子摸象,隨便亂講,這時候要解決問題,就需要瞎貓遇到死耗子的運氣。

  • i586 和 i686 看起來指令相似,但本質不同!

    • 從 i686 (Pentium Pro) 開始,底層已經是** RISC 架構**
  • 因為現在計算機結構改變很大

    • 即便把程式用組合語言重寫,效能也不見得比 Compiler 產生的還好
      • 效能的問題在存取資料本身
      • 組合語言會快,是因為你分析過程式要怎樣寫才可以比較快
        • 直接照著程式碼的邏輯改寫組合語言不見得比較好
  • hyperloglog

( 從測驗來刺激思考: Quiz-0 )

你所不知道的 C 語言」系列講座

A circuit-like notation for lambda calculus

  • 1928年,Alonzo Church 發明了lambda演算(當時他 25 歲)。Lambda 演算被設計為一個通用的計算模型,並不是為了解決某個特定的問題而誕生的。1929 年,Church 成為普林斯頓大學教授。1932 年,Church 在 Annals of Mathematics 發表了一篇論文,糾正邏輯領域裡幾個常見的問題,他的論述中用了lambda演算。1935年,Church 發表論文,使用 lambda 演算證明基本數論中存在不可解決的問題。1936 年 4 月,Church發 表了一篇兩頁紙的 “note”,指出自己 1935 年那篇論文可以推論得出,著名的Hilbert“可判定性問題”是不可解決的

Programming Small

#include<stdint.h> int32_t a, b;
  • 然後原本涉及到分支的陳述:

    if (b < 0) a++;

  • 可更換為沒有分支的版本: # superscalar https://en.wikipedia.org/wiki/Superscalar_processor

    a -= b >> 31;

  • 為什麼呢?一旦 b 右移 31 個 bit,在右移 >> 時在前面補上 sign bit ,所以移完會是 0xffff 也就是-1,故結果會是 a -= -1,即 a++,於是,原本為負數的值就變成 1 ,而原本正數的值就變成 0,又因為原本的行為是有條件的 a++,如此就是數值操作,沒有任何分支指令。

GNU Toolchain

  • gcc : GNU compiler collection
  • as : GNU assembler
  • ld : GNU linker
  • gdb : GNU debugger

介紹完編譯工具後,來講點大概編譯的流程還有格式

**Compile flow **

先來看這張圖:

.c 和 .s 我想大家比較常見,所以就解釋一下 .coff 和 .elf 是什麼:

GAS program format (AT&T)

* .file “test.s” * .text * .global main * .type main, %function * main: * MOV R0, #100 * ADD R0, R0, R0 * SWI #11 * .end

由一個簡短的 code 來介紹,在程式的section 會看到 . ,是定義一些 control information,如 .file , .global 等

  • %function : 是一種 type 的表示方式 .type 後面可以放 function 或者是 object 來定義之
  • SWI #11 : 透過 software interrupt 去中斷現有程式的執行,通常會存取作業系統核心的服務 (system call)
  • .end : 表示是 the end of the program

注意,在後來的 ARM 中,一律以 "SVC" (Supervisor Call) 取代 "SWI",但指令編碼完全一致

==> ARM Instruction Set Quick Reference Card

以下簡介 ELF 中個別 section 的意義: (注意: ELF section 的命名都由 . 開頭)

  • .bss : 表示未初始化的 data,依照定義,系統會賦予這些未初始化的值 0
  • .data : 表示有初始過的 data
  • .dynamic : 表示 dynamic linking information
  • .text : 表示 "text" 或者是 executable instructions

寫程式的要點

  • 程式是拿來實現一些演算法 (想法) 進而去解決問題的
  • 可以透過 Flow of control 去實現我們的程式
    • Sequence
    • Decision: if-t
    • hen-else, switch
    • Iteration: repeat-until, do-while, for
  • 將問題拆成多個更小而且方便管理的單元 (每一個單元或稱 function ,盡量要互相獨立)
  • Think: In C, for / while ?

Procedures

來複習一下名詞

  • Arguments: expressions passed into a function
  • Parameters: values received by the function
  • Caller & callee [呼叫者(通常就是在其他函式呼叫的function) 與 被呼叫者(被呼叫的 function)]

==> "argument" 和 "parameter" 在中文翻譯一般寫「參數」或「引數」,常常混淆

==> "argument" 的重點是「傳遞給函式的形式」,所以在 C 語言程式寫 int main(int argc, char *argv[]) 時,我們稱 argc 是 argument count,而 argv 是 argument vector

==> "parameter" 的重點是「接受到的數值」,比方說 C++ 有 parameterized type,就是說某個型態可以當作另外一個型態的「參數」,換個角度說,「型態」變成像是數值一樣的參數了。

==> https://en.wikipedia.org/wiki/Parameter_(computer_programming

在撰寫程式常常會使用呼叫( call ),在上圖中高階語言直接將參數傳入即可,那麼在組語的時候是如何實作的呢?是透過暫存器? Stack ?  memory ? In what order ?我們必須要有個 protocol 來規範

ARM Procedure Call Standard (AAPCS)

  • ARM Ltd. 定義一套規則給 procedure entry 和 exit
    • Object codes generated by different compilers can be linked together
    • Procedures can be called between high-level languages and assembly
  • AAPCS 是 Procedure Call Standard for the ARM® Architecture 的簡稱,從 10 年前開始,全面切換到 EABI (embedded ABI)
    • 過去的 ARM ABI 稱為 oabi (old ABI),閱讀簡體中文書籍時,要格外小心,因為資訊過時
  • APCS 定義了
    • Use of registers
    • Use of stack
    • stack-based 資料結構型式
    • argument passing 的機制
      • first four word arguments 傳到 R0 到 R3
      • 剩餘的 parameters 會被 push 到 stack (參數依照反過來的排序丟入堆疊中)
      • 少於 4 個 parameters 的 procedure 會比較有效率

  • Return value
    • one word value 存在 R0
    • 2 ~ 4 words 的 value 存在 ( R0-R1, R0-R2, R0-R3)

以下測試一個參數數量為 4 和 5的程式:

* int add4(int a, int b, int c , int d){ * return a + b + c + d; * } * int add5(int a, int b, int c , int d, int e){ * return a + b + c + d + e; * }

程式編譯後,用 objdump 組譯會得到類似以下:

紅框標注的是比左邊多出的程式碼,從這裡可以看到參數 1-4 是存在 R0-R3,而第 5個參數存在原本 sp + 4  的位置,隨著程式碼進行 R0-R3 存在 stack 中,圖下為 stack 恢復前的樣子:

因此若寫到需要輸入5個或以上的參數時,就必須存取外部記憶體,這也導致效能的損失。

==> xorg xserver 的最佳化案例

Standard ARM C program address space

下圖為 ARM C program 標準配置記憶體空間的概念圖:

Accessing operands

通常 procedure 存取 operands 透過以下幾種方式:

  • An argument passed on a register : 直接使用暫存器
  • An argument passed on the stack : 使用 stack pointer (R13) 的相對定址 (immediate offset)
  • A constant : PC-relative addressing
  • A local variable : 分配在 stack 上,透過 stack pointer 相對定址方式存取
  • A global variable : 分配在 static area (就是樓上圖片的 static data),透過 static base (R9) 相對定址存取

用幾張圖來表現出存取 operands 時,stack 的變化:

圖下為 passed on a register:

圖下為存取 local variables:

Target Triple

在使用 Cross Compiler 時,gcc 前面總有一串術語,例如:

  • arm-none-linux-gnueabi-gcc

這樣 arm-none-linux-gnueabi-稱為 target triple,通常規則如下:

<target>[<endian>][-<vender>]-<os>[-<extra-info>]

  • vendor 部份只是常見是可以塞 vendor 而已, 但沒有一定塞 vendor 的資訊
  • extra-info 部份大部份是在拿來描述用的 ABI 或著是 library 相關資訊

先以常見 x86 的平台為例子:

gcc  下 -v 可以看到以下:

Target: x86_64-redhat-linux

<target>-<vendor>-<os> 的形式

Android Toolchain:

Target: arm-linux-androideabi

<target>-<os>-<extra-info>

androideabi : 雖然 Android 本身是 Linux 但其 ABI 細節跟一般 linux 不太一樣

Linaro ELF toolchain:

Target: arm-none-eabi

<target>-<vender>-<extra-info>

vender = none

extra-info = eabi

Linaro Linux toolchain:

Target: arm-linux-gnueabihf

<target><endian>-<os>-<extra-info>

extra-info:

eabi: EABI

hf : Hard float, 預設有 FPU

  • soft (GPR), softfp (GPR -> float register), hardfp

Linaro big-endian Linux toolchain:

Target: armeb-linux-gnueabihf

<target><endian>-<vender>-<extra-info>

endian = be = big-endian

Buildroot 2015-02

Target: arm-buildroot-linux-uclibcgnueabi

<target>-<vender>-<os>-<extra-info>

extra-info:

uclibc 用 uclibc (通常預設是 glibc, uclibc 有些細節與 glibc 不同)

gnu : 無意義

eabi : 採用 EABI

NDS32 Toolchain:

Target: nds32le-elf

<target><endian>-<os>

Andes 家的,應該淺顯易懂不用解釋

由以上眾多 pattern 大概可以歸納出一些事情:

vender 欄位變化很大,os 欄位可不填。若不填的話,通常代表 Non-OS (Bare-metal)

source: http://kitoslab.blogspot.tw/2015/08/target-triple.html

編譯器原理

為何我們要理解編譯器?這是電腦科學最早的思想體系

GCC 會透過 builtins 來達到最佳化,在 GCC flag -funit-at-a-time 指定時 (-O3 implies),原本的:

  • sprintf(buf,"%s",str);

在 front-end 會被改寫為:

  • strcpy(buf,str);

printf 本身就是一個小型的 interpreter,所以 GCC 的作法就是簡化複雜度,這對一般情況下是 正面的,不過涉及 function rewriting 的議題,對系統程式或設計一個作業系統核心來說,就是一個潛在的問題。

Interpreter, Compiler, JIT from scratch ]

Virtual Machine Constructions for Dummies ]

A brief history of just-in-time ]

Making an Embedded DBMS JIT-friendly ]

值得注意的是,program loader 也很關鍵

作業系統的核心裡面也有編譯器

* $ sudo tcpdump -p -ni eth0 -d "ip and udp" * (000) ldh&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; [12] * (001) jeq&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; #0x800&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; jt 2&nbsp;&nbsp;&nbsp; jf 5 * (002) ldb&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; [23] * (003) jeq&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; #0x11&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; jt 4&nbsp;&nbsp;&nbsp; jf 5 * (004) ret&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; #65535 * (005) ret&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; #0

實做案例

Can we make Apache Spark 10x faster?

好比在金庸《射雕英雄傳》,馬鈺教郭靖修煉內功的方式,無外乎就是一些呼吸、走路、睡覺的法子。

(圖片來源:獵人 Hunter x Hunter)

[ 舊有的資料處理模式 ]

* class Filter(child: Operator, predicate: (Row => Boolean)) * extends Operator { * def next(): Row = { * var current = child.next() * while (current == null || predicate(current)) { * current = child.next() * } * return current * } * }

[ 以簡馭繁 ]

* var count = 0 * for (ss_item_sk in store_sales) { * if (ss_item_sk == 1000) { * count += 1 * } * }

[ 進一步改善 ]

  • No virtual function dispatches

  • Intermediate data in memory vs CPU registers

  • Loop unrolling and SIMD

  • 生日悖論

編譯器技術對於現行運算需求的重要性

  • AutoFDO, Google

  • GCC Function Instrumentation

  • 該機制出現於 GCC 2.x,由 Cygnus (現為 RedHat) 所提出,在 GCC 中對應的選項為:"finstrument-functions"

  • 測試 GCC Function Instrumentation 的小程式: (hello.c)

* #include <stdio.h> * #define DUMP(func, call) \ * printf("%s: func = %p, called by = %p\n", __FUNCTION__, func, call) * void __attribute__((__no_instrument_function__)) * __cyg_profile_func_enter(void *this_func, void *call_site) * { DUMP(this_func, call_site); } * void __attribute__((__no_instrument_function__)) * __cyg_profile_func_exit(void *this_func, void *call_site) * { DUMP(this_func, call_site); } * main() { puts("Hello World!"); return 0; }
  • 編譯與執行:
*   $ **gcc -finstrument-functions hello.c -o hello**
*   $ **./hello**
*   __cyg_profile_func_enter: func = 0x8048468, called by = 0xb7e36ebc
*   Hello World!
*   __cyg_profile_func_exit: func = 0x8048468, called by = 0xb7e36ebc
  • 看到 "attribute" 就知道一定是 GNU extension,而前述的 man page 也提到 -finstrument-functions 會在每次進入與退出函式前呼叫 "__cyg_profile_func_enter" 與 "__cyg_profile_func_exit" 這兩個 hook function。等等,「進入」與「退出」是又何解?
  • C Programming Language 最經典之處在於,雖然沒有定義語言實做的方式,但實際上 function call 皆以 stack frame 的形式存在。
  • 如果我們不透過 GCC 內建函式 "__builtin_return_address" 取得 caller 與 callee 相關的動態位址,那麼仍可透過 -finstrument-functions,讓 GCC 合成相關的處理指令,讓我們得以追蹤。而看到 __cyg 開頭的函式,就知道是來自 Cygnus 的貢獻,在 gcc 2.x 內部設計可瞥見不少。
  • 當我們試著移除 "attribute((no_instrument_function))" 那兩行來看看: (wrong.c)
  • 編譯與執行:
*   $ **gcc -g -finstrument-functions wrong.c -o wrong**
*   $ **./wrong**
*   Segmentation Fault
  • 發生什麼事情呢?請出 gdb 協助:
*   $ **gdb -q ./wrong**
*   (gdb) **run**
*   Starting program: /home/jserv/HelloWorld/helloworld/instrument/wrong 

*   Program received signal SIGSEGV, Segmentation fault.
*   0x0804841d in __cyg_profile_func_enter (this_func=0x8048414, call_site=0x804842d) at wrong.c:7
*   7        {
*   (gdb) **bt**
*   #0  0x0804841d in __cyg_profile_func_enter (this_func=0x8048414, call_site=0x804842d) at wrong.c:7
*   #1  0x0804842d in __cyg_profile_func_enter (this_func=0x8048414, call_site=0x804842d) at wrong.c:7
*   #2  0x0804842d in __cyg_profile_func_enter (this_func=0x8048414, call_site=0x804842d) at wrong.c:7
*   ...
*   #30 0x0804842d in __cyg_profile_func_enter (this_func=0x8048414, call_site=0x804842d) at wrong.c:7
*   #31 0x0804842d in __cyg_profile_func_enter (this_func=0x8048414, call_site=0x804842d) at wrong.c:7
*   #32 0x0804842d in __cyg_profile_func_enter (this_func=0x8048414, call_site=0x804842d) at wrong.c:7
  • 既然 "__cyg_profile_func_enter" 是 function hook,則本身不得也被施以 "function instrument",否則就無止盡遞迴了,不過我們也可以發現一件有趣的事情:
*   $ **nm wrong | grep 8048414**
*   08048414 T __cyg_profile_func_enter
  • 如我們所見,"__cyg_profile_func_enter" 的位址被不斷代入 __cyg_profile_func_enter function arg 中。GNU binutils 裡面有個小工具 addr2line,我們可以該工具取得虛擬位址對應的行號或符號:
*   $ **addr2line -e wrong 0x8048414**
*   /home/jserv/HelloWorld/helloworld/instrument/wrong.c:7
  • 就 Linux 應用程式開發來說,我們可透過這個機制作以下應用:
    • 撰寫特製的 profiler
    • 取得執行時期的 Call Graph
    • 置入自製的 signal handler,實做 backtrace 功能
    • 模擬 Reflection 機制

但 profiling 的成本在許多環境,像是雲端運算來說,實在太沈重,所以 Google 提出透過 perf 工具來取得 profiling 資料的 AutoFDO:

Skymizer 針對日前釋出的 GCC 6.1,翻譯部份 GCC Release note:

"so you all hate on C++. all right. all right. tell me. does your favorite language have a concept of friendship, then? eh?

thought so." from twitter

"C++ Is my favorite garbage collected language because it generates so little garbage."

隨堂測驗

  • [ ]Quiz-0 : Give you the prototype of the function:

int p(int i, int N);

use it to print the numbers from i up to N and then down to i again, one number per line

Don’t use those keywords: do, while, for, switch, case, break, continue, goto, if.

Don’t use ’:?’

You can only use ONE statement!

==>

int p(int i, int N) { return (i < N && printf("%d\n", i) && !p(i + 1, N)) || printf("%d\n", i); }
  • [ ]Quiz-1 : 只能使用位元運算子和遞迴,在C程式中實做兩個整數的加法

void add(int a, int b) { }

=>

int add(int a, int b) { if (b == 0) return a; int sum = a ^ b; // 相加但不進位 int carry = (a & b) << 1; // 進位但不相加 return add(sum, carry); }

Reference: http://stackoverflow.com/questions/14695051/how-to-simulate-a-4-bit-binary-adder-in-c

  • [ ]Quiz-2 : 給定一個 singly-linked list 結構:
* typedef struct _List { * struct _List *next; * int val; * } List;

實做得以交換存在 list 中兩個節點的函式: (考慮 HEAD 與 TAIL)

int swap_list(List **head, List *a, List *b) {

}

==>

https://github.com/shengwen1997/sys2016_homework/blob/master/linked_list_swap/main.c