開發紀錄(sandbox) === - [sysprog21/moxiebox](https://github.com/sysprog21/moxiebox) Toolchain: - [crosstool-ng](https://github.com/jserv/crosstool-ng) ``` 先安裝工具 $ ./bootstrap $ ./configure 過程中缺少工具 $ sudo apt-get install gperf $ sudo apt-get install bison $ sudo apt-get install help2man $ sudo apt-get install libncurses5-dev 接著 $ make $ sudo make install $ mkdir -p ~/build-toolchain $ cd ~/build-toolchain $ ct-ng moxie-none-moxiebox $ ct-ng build ``` - PATH設定 ``` export PATH=$PATH:~/x-tools/moxie-none-moxiebox/bin ``` ## 實作 Fibonacci 數列 參考[你所不知道的C語言：遞迴呼叫篇](https://hackmd.io/s/rJ8BOjGGl)撰寫 C 語言程式，並透過 `__attribute__((optimize("O0")))` 取消最佳化，或者於 CFLAG 內新增 -o0 參數 ### Tail recursion ```clike= int __attribute__((optimize("O0"))) fib_tail_recursion(int n, int a, int b) { if (n == 0) return a; return fib_tail_recursion(n - 1 , b, a + b); } ``` 參考 moxie-none-moxiebox-gcc 產生的組合語言程式碼，以此為基礎去觀察並優化 $ moxie-none-moxiebox-gcc -S fib_tail_recursion.c $ cat fib_tail_recursion.s #### 觀察 ##### Callee saved 透過 moxie-none-moxiebox-gcc 產生的組合語言程式碼發現暫存器內的值是由 Callee 函式儲存進堆疊內 ```clike= fib_tail_recursion: dec $sp, 24 sto.l 12($fp), $r0 sto.l 16($fp), $r1 sto.l 20($fp), $r2 ... ... ``` ##### instruction set 這一份透過 moxie-none-moxiebox-gcc 產生的組合語言程式碼主要使用到 `dec` 、 `sto.l` 、 `ldo.l` 、 `mov` 、 `add` 、 `jsra` 比較不熟悉的是 `jsra` 這個可以 jump 到 subroutine 的指令，透過 gdb 可以觀察到 `jsra` 會儲存 $fp 以及 return address(也就是 $pc 進入函式前所指的下一條指令) 到堆疊，然後把 $fp 和 $sp 指向堆疊頂端，結束時配合 ret 離開 subroutine ```shell= (gdb)i r $fp 0x129b4 0x129b4 $sp 0x129a8 0x129a8 $r0 0xa 10 ... ... $pc 0x11a6 0x11a6 <main+20> $cc 0x0 0 (gdb)disas Dump of assembler code for function main: 0x00001192 <+0>: dec $sp, 0xc ... => 0x000011a6 <+20>: jsra 0x1158 <fib_tail_recursion> 0x000011ac <+26>: sto.l 0xfffc($fp), $r2 ... 0x000011b2 <+32>: ret End of assembler dump. (gdb)x/3xw $fp 0x129b4: 0x00000000 0x0000103e 0x00000000 (gdb) si 0x00001158 in fib_tail_recursion () (gdb)i r $fp 0x1299c 0x1299c $sp 0x1299c 0x1299c $r0 0xa 10 ... ... $pc 0x1158 0x1158 <fib_tail_recursion> $cc 0x0 0 (gdb)disas Dump of assembler code for function fib_tail_recursion: => 0x00001158 <+0>: dec $sp, 0xc 0x0000115a <+2>: sto.l 0xc($fp), $r0 ... ... 0x00001190 <+56>: ret End of assembler dump. (gdb)x/3xw $fp 0x1299c: 0x000129b4 0x000011ac 0x00000000 ``` #### 修改 透過 moxie-none-moxiebox-gcc 產生的組合語言程式碼取消最佳化後有一些顯而易見可以手動優化的地方，主要修改冗餘的暫存器使用以及過大的堆疊空間，[Github](https://github.com/vasv75182366/moxiebox/commit/0d867b61ee01363cadd548e2bf9138f708801bc2) ### Iterative ```clike= int __attribute__((optimize("O0"))) fib_iterative (int n) { int pre = -1; int result = 1; int sum = 0; for (int i = 0; i <= n; i++) { sum = result + pre; pre = result; result = sum; } return result; } ``` 參考 moxie-none-moxiebox-gcc 產生的組合語言程式碼 $ moxie-none-moxiebox-gcc -S fib_iterative.c $ cat fib_iterative.s #### 觀察 ##### 過多 stack 存取 透過 moxie-none-moxiebox-gcc 產生的組合語言程式碼取消最佳化後有過多 stack 存取 ```clike= fib_iterative: dec $sp, 16 sto.l 12($fp), $r0 ldi.l $r0, -1 sto.l -4($fp), $r0 ldi.l $r0, 1 sto.l -8($fp), $r0 xor $r0, $r0 sto.l -16($fp), $r0 xor $r0, $r0 sto.l -12($fp), $r0 ... ... ``` #### 修改 由於 Iterative 版本不像遞迴版本需要大量使用 stack ，暫存器的數量就足夠紀錄變數，因此使用較多的暫存器來取代 stack，[Github](https://github.com/vasv75182366/moxiebox/commit/7085a8a3e64c784d8f7062f0506e467a426e40af) ```clike= fib_iterative: ldi.l $r2, -1 ldi.l $r3, 1 xor $r4, $r4 xor $r1, $r1 ... ... ``` ### Recursive ```clike= int __attribute__((optimize("O0"))) fib_recursive(int n) { if (n == 0) return 0; if (n == 1) return 1; return fib_recursive(n - 1) + fib_recursive (n - 2); } ``` 參考 moxie-none-moxiebox-gcc 產生的組合語言程式碼 $ moxie-none-moxiebox-gcc -S fib_recursive.c $ cat fib_recursive.s #### 觀察 使用到前面兩個沒有用過的 `push` 和 `pop` ，透過 gdb 可以觀察到 `push` 會在 $sp 所指的位置存入暫存器的值， `pop` 會取出 $sp 所指位置的值放在暫存器，並且自動增減 $sp 的值 #### 修改 ## 作業要求 - [x] 在 GitHub 上 fork [moxiebox](https://github.com/sysprog21/moxiebox)，並設定協作者的寫入權限 - [x] 編輯 [2017 年秋季班第一次分組表](https://hackmd.io/s/rk7xxIGkf)，新增兩個共筆頁面: (請依循給定格式，注意空白) * ==`自我檢查事項(sandbox)`== : 答覆上述各節的「自我檢查事項」，務必詳盡回覆，誠實面對自己^TM^ * ==`開發紀錄(sandbox) / GitHub / YouTube`==: 針對下方作業要求，詳實記錄開發進度和討論，不要變成「兩個和尚沒水喝」 - [ ] 在 [moxiebox](https://github.com/sysprog21/moxiebox) 的 `tests` 目錄中，比照 [simulator](https://hackmd.io/s/BkQgqpe0Z) 作業要求，依序實作以下 Fibonacci 數列求值方法: (可用 C 程式實作，但需要附上詳盡的效能分析，善用 GNU gprof 和 GDB) - [x] recursive - [x] iterative - [x] Tail recursion - [ ] Q-Matrix - [ ] Fast doubling (加上 clz 加速) - [ ] 善用 GNU plot 製圖和解讀 - [ ] 注意 $Fib(46)$ 之後的數值會超過 2^32^ 可表達的範圍，需要設計有效的數值表示機制來處理 (如用兩個 32-bit 暫存器保存 2^64^ 數值) - [ ] 運用 GDB script/commands 來實作自動化測試和效能分析 * 注意: [moxiebox](https://github.com/sysprog21/moxiebox) 沒有 `printf` 可用，需要思考如何透過 `mmap` 來比對程式輸出和預期結果，自動化非常重要！ - [ ] 額外在 [moxiebox](https://github.com/sysprog21/moxiebox) 移植 (或者重新實作) 以下程式碼，並且充分驗證 (至少做一項) 1. [ctaes](https://github.com/bitcoin-core/ctaes): constant-time AES implementation 2. [constant-time-sorts](https://github.com/ktslabbie/constant-time-sorts): constant-execution-time versions of popular sorting algorithms 3. [cst_time_memcmp](https://github.com/chmike/cst_time_memcmp): onstant time memcmp() function 4. [constant_time_compare](https://github.com/levigross/constant_time_compare): constant time comparison written in C for Python 2.7 5. [CN_String](https://github.com/iDestyKK/CN_String): Stores length for constant time strlen - [ ] 承上，詳述原始程式的演算法和應用場合，並探討在 [moxiebox](https://github.com/sysprog21/moxiebox) 移植的工作 * 務必詳閱 [dudect: dude, is my code constant time?](https://github.com/oreparaz/dudect)