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

Last changed by 
 
劉亮谷
0
2892
Published on HackMD