# 2018q3 Homework1 contributed by < `lainn9527` > [作業要求](https://hackmd.io/s/SkWIb_O_X) ###### tags:`c` --- ## 你所不知道的 C 語言：開發工具和規格標準篇 ### 筆記 * K&R C * 使C語言流行的關鍵 * 內容簡潔, 作業值得寫 * 處理字串就是重新檢視C語言對記憶體操作的熟悉度 * C++ * 比起OO, 更像meta language, 因為涵蓋太多東西了, 包含functional programming, generic * 改版非常非常快速, 因此很多 C++ 編譯器尚未完全符合規範 * GCC7是個有工業強度的C++ compiler * vs C * 早期只是C語言的OO extension * 1999年分道揚鑣 * 分歧點: C++不支援designated initializer * musc libc * 源由: glibc有一些授權問題, 開發者乾脆自己搞一個 * 授權條款: MIT liscence, 基本上只要附作者名字就可以 * 功能&使用: 大部分與glibc相容 * 第一個C語言編譯器是如何寫出來的？ * 現在的編譯器可以用舊的編譯器寫 * 用Assembly Language寫出只有C語言最基本功能的子集C~0~, 再用C~0~寫C~1~, C~1~寫...到C~N~, 等到C~N~的功能已接近完全了, 再開發最終的C語言 * 這就是bootstrapping * Linaro: 專門在做opensource的公司, 由 Arm 和若干 SoC 公司投資 * 如果和ARM有關的客製化, 虛擬化的opensource越多, 就越多人用, ARM可以收得授權金就越多 * 在21世紀, 自幹是幸福的事情 * 因為在更多時候是我們被迫要去研究, 改進, 除錯一個我們不熟的東西 ### Debugger工具 #### GDB :::info 有的debugger GDB, 人生就變成彩色的 ::: * 簡介 * Debugger, Instruction Simulator * 支援多種硬體&語言 * 目前由各種公司維護 * 使用 * 在gcc compiler時要加`-g`這個flag, 把debug的資訊加進去 * 可以把instruction address記錄起來, 設成breakpoint * 還能在執行時期直接設定program counter, 直接跳到欲執行instruction * 例如跳過序號檢查讓試用版變成完整版 * 可以執行printf, 因此就不用在程式裡面加了 * 在程式裡面加可能會改變時序(multi-thread) * ptrace * 用某process注入到其他process以追蹤 #### rr * 簡介: 可以記錄程式執行過程並做"Application Checkpointing", 在debug大型程式非常有用 * replay: 當下執行的環境會被整個記錄下來, 因此可以讓gdb回到那個狀態 * 如果gdb夠新還能退回之前狀態(undo) * 由Mozilla推出 * 例子: open & write到 ### C語言規格書 :::success 遇到不懂的東西就去看規格書 ::: * 為什麼要看規格書? * 規格書是第一手資料, 也就是所有東西的標準, 有了標準就不會模糊 #### 簡介 * 發行組織: ISO/IEC * Draft版本 * 公開給大家看有沒有地方要修改的, 因此是免費的, final版就要收費 * C99在1999年發佈, 不過會經歷一些微調, 例如 * 編譯器公司在實作上碰到問題, 會提交給委員會申請修改 * 不圖利特定廠商 #### 內容 * object * 佔有固定空間的單元 * `*`: * `[]`: array subscripting * C沒有真正 (數學意義上) 的array, 因為最後都會轉化成pointer * lvalue: locator * sizeof * operator * incomplete type: 不能確定大小的type * string literal: 以null terminater結束的 * NaN: 遇到NaN時要怎麼表達 :::info 延伸閱讀 [數值系統篇](https://hackmd.io/s/BkRKhQGae)，試著從規格書和 IEEE 754 找到 NaN 的表達及處理機制 :notes: jserv ::: * 指標的指標: 沒有雙重指標, 只有"指標的指標", 因為兩者不是對等的而是有階層的關係 * `const float *`: pointer to const qualified float --- ## 你所不知道的 C 語言：指標篇(上) ### 預讀: Operator Priority in C(節錄) * [source](https://en.cppreference.com/w/c/language/operator_precedence) * 對deference operator(==*==)而言, 優先級別**較高**且有影響的為的 * function call: f() * array subscripting: a[] * suffix incre/decre: a++/a-- * Case: `function call()`有較高優先度, 因此function pointer要加上`parenthese()` ```clike= int *f(); // function return int pointer int (*pf)(); // pointer to function which returns int ``` ### 預讀: K&R: Pointers #### Basic Concepts * pointer: a variable that contains the address of a variable * `&` * unary op.(operator) that gives addr. of an ==object== * `&a` is a pointer to `a` * only applies to objects in mem.(memory) * can: vars.(variables), array elements * can't: expression, constants, register vars. * `*` * unary op., indrection or dereferencing op. * when use in a pointer: `*p` * access the obj. the pointer points to * meaning of `int *ip` * value of `*ip` is an `int` * meaning of `int (*fp)(int i, int j)` * `fp` is a pointer to a function with 2 parameters #### Pointer & Array * p.97, K&R C > Any operation that can be achieved by array subscripting can also be done with pointers. The pointer version will in general be faster but, at least to the uninitiated, somewhat harder to understand. * 差別: pointer is var., array name is not. * 所以無法對array name重新賦值 * as function parameter: * `f(int *a)`和`f(int a[])`是一樣的 #### Pointer & Array: Character * `char a[] = "icc"` v.s. `char *p = "icc"` * `a`: an array that is just big enough * `p`: pointer to string ==constant== * pointer是var.可以改變, 不過改變指向內容則為undefine #### Complicated Declaration * 因為宣告時不能從左讀到右, 又有非常多的`()`, 所以複雜的宣告常常難以解讀 * 解讀方法 * 按照operator priority慢慢解 * Case: `char (*(*x())[])()` * `x()`: func. * `*x()`: func. return pointer * `(*x())[]`: func. return pointer to array * `*(*x())[]`: func. return pointer to array of pointer * `(*(*x())[])()`: func. return pointer to array of pointer to func. * `char (*(*x())[])()`: func. return pointer to array of pointer to func. return char ### 講座筆記 #### 筆記 * `qsort()` in C * 沒有指定algo., 而是用function pointer形式讓user自己指定 :::info 讓使用者指定 comparison function，參見 [qsort(3)](https://linux.die.net/man/3/qsort) :notes: jserv ::: * C語言是在開發unix的過程中發展而來的 * 所以C語言沒寫好, 是因為沒有想過自己為何而學 * 不要僅僅把C語言當成是一種語言, 而是一種生活態度 * 學日文也不是只想講摳妮基挖, 而是要了解其文化, 應用, 禁忌等等 * Compiler會有bug嗎 * 就和所有程式一樣會有 * 舊的會有很多已知的bug * 新的也會有未知的bug * 所以一定要看規格書 * Lvalue: 可存取(r/w)資源 * L for locator * 為什麼要了解硬體? * 開發軟體時一定會用到各種工具, 不同可重頭到尾自己自幹 * 而工具開發者不一定會考慮各種硬體的適用性, 所以妳在開發過程中會遇到很多問題 * 這時你得自己解決, 才能繼續做你該做的事, 把事情做完才叫做專業 * incomplete type * array: arraytype of unknown size * structure or union: structure or union type of unknown content * case: oltk * 用incomplete type: `struct oltk`當作是介面, 達到隱藏實作的效果 #### Pointer * 複雜指標操作 * Case: `(*(void(*)())0)();`: 呼叫地址為0的function * 實際運行結果: segmentation fault, 因為這個地址通常是user mode不能呼叫的 * Case: `void **(*d) (int &, char **(*)(char *, char **));`: :::success 複雜指標型式的重點在於「如何解讀」和「應用時機」 ::: * Pointer Type * pointer type is derived from reference type * 如果從int得到, 就是我們常說的"pointer to int" * reference type: function type, an object type, or an incomplete type * incomplete type: 沒有明確大小, 因此不算object * 可以用pointer指向incomplete type * 不能make instance, * Pointer Arithmetic * 只能+, - :::info 四則運算只有 `+` 和 `-` 可處理指標運算，但在規格書中還有其他 operator 可用，去找找 :notes: jserv ::: * Array, function, and pointer在本質上一樣 * Array, function, and pointer types are collectively called **derived declarator types** * `void *` & `char *`: 可以互換 * 前提是要dereference時, 必須要將`void *`強制轉型 * alignment問題: 不同平台的硬體架構, 有不同的alignment requirement * undefined behavior (UB): 例如從16-byte強制轉型成4-byte * pointer to pointer * 因為C語言只有call-by-value, 因此pointer可以為其增加彈性 * 也就是原本life-time只有在function內, 現在可以擴展到整個main or program * 案例: linked-list * 困難點: head有可能被drop掉 * 用pointer to pointer就能解決 * array vs. pointer * 如果array僅宣告(incomplete type), 則可以和pointer互換 * 如果array有佔空間, 就是個object, 無法互換 * ==C語言沒有真正的array== * 只是語法糖的存在 * 實際上只有一維陣列的資料存取 ## 你所不知道的 C 語言：指標篇(下) ### 講座筆記 #### 筆記 * 在軟體開發上, 人現在要解決的問題要放在**設計層面**, **底層**這些機器無法觸及的 * 因此只懂改善程式流程, 很危險 * 資深工程師？ * 這個人離開, 會對公司的業績, 產品開發造成衝擊 #### Pointer * pointer and array * In the expression `x[i]`, which is equivalent to ``(*((x)+(i)))` * row major and cache * 我們想要random access, 但cache是sequential access #### GDB * 好處 * 可以在執行時期交互溝通, 就不用反覆編譯 ##### 操作 * 用gcc編譯時 * `-Og`: 對debugger做最佳化 * `-g`: 加入debugger看得懂的訊息 * `whatis v`: 顯示v的type, v為variable ##### Case * `p &b+1` vs `p &(b[0]) + 1` * b是array with 17 elements * 前者是跨越整個array, 後者只+1 element大小的addr. ## 你所不知道的C語言：函式呼叫篇 ### 講座筆記 #### 筆記 * nested function * callback function * C語言不允許nested function * uplevel reference * C--: 把C語言的語法糖拿掉 * 常用來開發C的編譯器 * GDB追蹤的是stack frame * ROP * 動態產生的程式碼(如JIT compiler)會放在heap裡面, 但heap是不可被執行的 -> 用ROP繞過 * 應用: server不下線更新 * [buffer-overflow](https://access.redhat.com/security/cve/cve-2015-7547) * 用遞迴程式了解mem. layout: [source](http://gghh.name/dibtp/2015/11/11/function-calls-in-c-practical-example.html) ### 延伸閱讀 #### malloc() & free() * source: [初探](http://blog.jobbole.com/75656/), [進階](http://blog.jobbole.com/75656/) * `malloc()`: * return pointer to allocated space if success * allocated space在heap, pointer在stack * `free()`: * 釋放pointer指向的空間(heap), ==不包含pointer== * 所以pointer要再指向`NULL` * double free * 如果pointer已指向`NULL`, 再`free()`會==no operation== * 為什麼malloc要指定size, free的時候不用？ * `malloc()`其實會分配兩個空間, 一個是指定空間, 另一個是==meta data==, meta data裡面會有size of allocated space * `free()`時再根據該meta data釋放空間 #### 為什麼 glibc 可以偵測出上述程式的 “double free or corruption” 呢？ * source: [stackoverflow](https://stackoverflow.com/questions/16698688/free-no-double-free-detected) * fast bin: 用來收集small allocated space(Chunks of size 16 to 80 bytes)的freelist dat * `free()`時會查看pointer to **fast bin**是否和傳入的pointer一樣, 一樣就會courrpt ## 你所不知道的C語言：遞迴呼叫篇 ### 講座筆記 #### 筆記 * 因為編譯器優化的關係, 遞迴不一定會比迭代慢 * 不過只能對tail recursion做空間最佳化 * tail recursion: no work after recursive call, just return the value of call * 遞迴沒有區域變數, 這對雲端, multi-processor架構而言非常好 * Fibonacci的遞迴解法, 時間複雜度會從O(n^2^)~O(log n) * 為什麼要強調演算法是in-place? ==空間效率== * 如果排序過程中要額外空間, 例如1M elements就要2M的空間, 這是種浪費 * 檔案系統 * 儲存檔案時除了檔案外, 還有meta data * 不會真正全部存在檔案系統內, 而是切割成幾個blocks儲存在不同的磁碟區塊 * 例如我們在做r/w時就不用讀整個file, 而是根據meta data選定blocks * 這樣做可以讓某些操作更有效率, 例如copy * meta data就是i-node(information node) * 為什麼`opendir()`, `fopen()`回傳的是pointer? * 為了平台間的兼容, 需要有抽象層(結構)將整個資訊和操作封裝起來 * MergeSort: 切割->排序->合併 * MapReduce * 找出第k個->落點分析 * 學習遞迴是為了將共享變數降到最低 * 現在以多核, 平行運算為主 ### Functional programming * source: [wiki](https://en.wikipedia.org/wiki/Functional_programming), [stackoverflow](https://stackoverflow.com/questions/2909282/why-are-functional-languages-considered-a-boon-for-multi-threaded-environments) * intro. * a programming paradigm * treats computation as the evaluation of mathematical functions and avoids changing-state and mutable data * a declarative programming paradigm, which means programming is done with expressions or declarations instead of statements. * In functional code, the output value of a function depends only on the arguments that are passed to the function, so calling a f() twice with the same value for an argument x produces the same result f(x) each time * Eliminating side effects, i.e., changes in state that do not depend on the function inputs, can make it much easier to understand and predict the behavior of a program * 重要性 * 因為沒有share state, 因此在multi-thread架構下就不會有同步化問題 ### Recursive Programming * [source](https://web.archive.org/web/20171116063115/http://www.cs.umd.edu:80/class/fall2002/cmsc214/Tutorial/recursion2.html) ::: info Recursion solves a big problem (of size n, say) by solving one or more smaller problems, and using the solutions of the smaller problems, to solve the bigger problem ::: * 概念 * The basic unit of a recursive function is a function * helper function: 幫助function完成遞迴的function, 且是實際遞迴的function * 因為遞迴是靠return value & parameter, 而function在被使用時和遞迴時的pararmeter一樣, 所以會有helper function幫助 * 例如`print()`會call `printRec(arg1)` * 如何寫出遞迴程式 * 寫下遞迴函式的prototype * 描述該function做了什麼 * 決定base case和其solution * 決定如何將大問題分解成小問題 * 用小問題的答案解決大問題 * Avoiding Static/Global Variables * 要藉由更新argument來傳遞訊息 * 有些時候可以用reference parameter * 不要先寫loop版本再將其轉成recursive版, 一開始就要"think recursively" ### tail recursion * [source](http://blog.jobbole.com/80626/) *