# 自我檢查事項(sandbox)
contributed by <`zhanyangch`, `tina0405`, `LinRiver`>
## 隔離執行環境的建構
### Trusted Execution Environment (TEE) 的應用為何?(舉出共筆以外的真實世界案例)
#### [Trusty TEE](https://source.android.com/security/trusty/)
* 在 android 上支援 TEE 的軟體,包含
* 一個運行在 TEE 處理器上的 Trusty OS
* Drivers for the Android kernel 處理在 Trusty OS 下的應用程式間溝通
* 一個函式庫處理在 Trusty OS 下的應用程式間溝通使用 kernel drivers
* TEE 處理器是獨立的微處理器或主處理器虛擬實例
* TEE processor is isolated from the rest of the system using memory and I/O protection mechanisms supported by the hardware.
* 應用 DRM,mobile payments, secure banking, full-disk encryption, multi-factor authentication, device reset protection, replay-protected persistent storage, wireless display ("cast") of protected content, secure PIN and fingerprint processing, and even malware detection.
* API
* Trusted applications or services that run on the TEE processor
* Normal/untrusted applications that run on the main processor and use services provided by Trusted applications
* 運行在主處理器的應用程式可以透過 Trusty APIs 連接可信任的應用並交換訊息,這個過程是completely asynchronous
* Trusted applications run as isolated processes under the Trusty OS kernel. Each process runs in its own virtual memory sandbox utilizing the MMU capabilities of the TEE processor
* Trusty 應用為單執行序
* Trusty applications 只在載入時初始化一次且會一直在記憶體中直到 TEE 處理器被 reset,Trusty 不支援動態載入
* Trusted applications are written as event-driven servers waiting for commands from other applications or from applications running on the main processor
* Currently all Trusty applications are developed by a single party and packaged with the Trusty kernel image. The entire image is signed and verified by the bootloader during boot. Third-party application development is not supported in this version of Trusty
* [Intel moves on Blockchain, Self-Driving Cars](https://www.enterprisetech.com/2017/08/10/intel-moves-blockchain-self-driving-cars/)
Intel 與 Microsoft 合作投入新興市場開發自動載具與區塊鏈, 此區塊鏈平台稱為 ``` Coco Framwork ```. 此平台整合了 Intel 的 Software Guard Extensions (SGX) 來強化在區塊鏈隱私和資料安全性. ``` Coco Framework ``` 應用了 SGX 所提供的 TEE 來保護執行中的資料與程式安全性.
* [IoT and TEE](https://www.artik.io/blog/2016/05/iot-and-trusted-execution/)
經由醫療感測裝置所蒐集到的用戶資料, 一般若有需要會傳送到個人照護醫生手上進行了解. 然而有時候可能會因應其他機構或是裝置需求, 傳送至他處進行資料分析. 透過 TEE 所提供的隔離環境進行資料傳送可確保其正確性.
### moxiebox 打造出隔離執行 (sandbox) 的運作環境該如何與外界溝通?列出對應的程式碼並解讀
* 輸出:函式 setreturn 會將 pointer to return buffer 放在 sregs[6]、length of return buffer 放在 sregs[7] 的位置,利用 sandbox.cc 中 gatherOutput 函式將 return buffer 的資料輸出到指定的檔案
- [ ] sandboxrt.h
```clike
extern void setreturn(void *addr, size_t length);
```
- [ ] setreturn.s
```clike
/*
* Input:
* $r0 -- pointer to return buffer
* $r1 -- length of return buffer
*
* Output:
* none
*/
.globl setreturn
.type setreturn,@function
.text
setreturn:
ssr $r0, 6
ssr $r1, 7
ret
.Lend:
.size setreturn,.Lend-setreturn
```
* 輸入 : loadRawData 函式配置記憶體
### ELF 執行檔格式包含哪些 section 呢? 又在哪裡可見到詳細描述?
* 先看了 [wikipedia](https://zh.wikipedia.org/wiki/%E5%8F%AF%E5%9F%B7%E8%A1%8C%E8%88%87%E5%8F%AF%E9%8F%88%E6%8E%A5%E6%A0%BC%E5%BC%8F) 介紹的 (ELF)Executable and Linkable Format
![](https://i.imgur.com/VCcUY5I.png)
* 但因為中間有部份 section 被略過,而在課本[深入理解計算機系統](https://www.tenlong.com.tw/products/9787111544937)中有提到
* 典型的 ELF 可重定位目標文件格式,參考 7.4 節
* 重定位(relocation): 當 compiler 和 assembler 產生了object code,linker 會把 symbol 相對應的 memory link 起來,進而 relocation 這些 section,而 linker 還會使用 assembler 所產生的 relocation entry 去使用 relocation
~~~
| ELF header | ->
| .text | -> 放置程式碼
| .rodata | -> 只讀數據 ,ro 是 rom 的意思
| .data | -> 放置初始化的 globle 和 static 變數
| .bss | -> 放置未初始化或令為 0 的 globle 和 static 變數
| .symtab | -> 放置定義和引用的 function 還有 global 變數的信息
| .rel.text | -> 程式段的重定位資訊
| .rel.data | -> 資料段的重定位資訊
| .debug | -> 除錯資訊
| .line | -> 原本行號和 .text 的對應,加入 -g 後才會有這 table
| .strtab | -> 字串表
|section header table| ->
~~~
* data 劃分為初始化與未初始化的原因:
* 為了空間效率,未初始化的數值不需佔據實際 disk 空間,只需要在 run 時都給0
* 利用 `objdump -x 執行檔` 察看 section 的類型
* 這邊我選 moxiebox/tests/rtlib 當輸入 `objdump -x rtlib`
* 顯示格式: `file format elf32-little`
* 參考[資料](http://www.jollen.org/blog/2006/11/executable_linking_format_elf_1.html)
~~~
Sections:
Idx Name Size VMA LMA File off Algn
0 .text 00000512 00001000 00001000 00000074 2**1
CONTENTS, ALLOC, LOAD, READONLY, CODE
1 .init 0000000e 00001512 00001512 00000586 2**1
CONTENTS, ALLOC, LOAD, READONLY, CODE
2 .fini 00000008 00001520 00001520 00000594 2**1
CONTENTS, ALLOC, LOAD, READONLY, CODE
3 .rodata 00000018 00001528 00001528 0000059c 2**2
CONTENTS, ALLOC, LOAD, READONLY, DATA
4 .data 00000430 00001640 00001640 000005b4 2**2
CONTENTS, ALLOC, LOAD, DATA
5 .eh_frame 00000004 00001a70 00001a70 000009e4 2**2
CONTENTS, ALLOC, LOAD, DATA
6 .ctors 00000008 00001a74 00001a74 000009e8 2**2
CONTENTS, ALLOC, LOAD, DATA
7 .dtors 00000008 00001a7c 00001a7c 000009f0 2**2
CONTENTS, ALLOC, LOAD, DATA
8 .bss 00000024 00001a84 00001a84 000009f8 2**2
ALLOC
9 .comment 0000003b 00000000 00000000 000009f8 2**0
CONTENTS, READONLY
10 .debug_aranges 00000150 00000000 00000000 00000a33 2**0
CONTENTS, READONLY, DEBUGGING
11 .debug_info 00003538 00000000 00000000 00000b83 2**0
CONTENTS, READONLY, DEBUGGING
12 .debug_abbrev 00000ead 00000000 00000000 000040bb 2**0
CONTENTS, READONLY, DEBUGGING
13 .debug_line 00000fb1 00000000 00000000 00004f68 2**0
CONTENTS, READONLY, DEBUGGING
14 .debug_frame 000001f8 00000000 00000000 00005f1c 2**2
CONTENTS, READONLY, DEBUGGING
15 .debug_str 00000a61 00000000 00000000 00006114 2**0
CONTENTS, READONLY, DEBUGGING
16 .debug_loc 000005eb 00000000 00000000 00006b75 2**0
CONTENTS, READONLY, DEBUGGING
17 .debug_ranges 00000098 00000000 00000000 00007160 2**0
CONTENTS, READONLY, DEBUGGING
~~~
* 參考[資料](https://www.crifan.com/detailed_lma_load_memory_address_and_vma_virtual_memory_address/)
* 先解釋 VMA 和 LMA
* LMA (Load Memory Address): the address at which the section will be loaded.
* 例如把指令從 Disk 搬到 Memory,就是利用這個 Load Memory Address ,我們不用 CPU 讀取 Disk 上的指令 , 而是將他 copy 到 Memory 再讀取,是因為讀取 Disk 的時間過久
* VMA(Virtual Memory Address): the address the section will have when the output file is run
* Virtual Address 和 Physical Address 透過 MMU 轉換 ![](https://upload.wikimedia.org/wikipedia/commons/thumb/d/dc/MMU_principle_updated.png/325px-MMU_principle_updated.png)
* 在 [stackoverflow](https://stackoverflow.com/questions/21718388/what-does-an-algn-of-22-and-20-mean-in-the-output-of-objdump) 中所提到的 Algn `2**n` 意思:
* Algn : $2^n$
* n : Values 0 and 1 mean the section has no alignment constraints
* File off : 參考 object.c , 會印出格式為 unsigned long 的 section->filepos
* 所以如果拿 `.text` 和 `.init` 來舉例的話, 1000+512 =1512 因為 `.text` size 512 ,`.text` 的 file 結束再 74 ,所以 `.init` 的 file 結束在 74+512=586
~~~
Idx Name Size VMA LMA File off Algn
0 .text 00000512 00001000 00001000 00000074 2**1
CONTENTS, ALLOC, LOAD, READONLY, CODE
1 .init 0000000e 00001512 00001512 00000586 2**1
CONTENTS, ALLOC, LOAD, READONLY, CODE
~~~
### 是否已掌握 GNU gprof 的使用?運作原理為何?
參考[使用 Gnu gprof 进行 Linux 平台下的程序分析](http://os.51cto.com/art/200703/41426.htm)
* GNU gprof 的使用
* 先利用 `gcc -pg test.c` 做出一份 a.out 執行檔
* test.c 內容與聯結中相同,主要是嘗試各種方法的使用
~~~c=
#include "stdio.h"
#include "stdlib.h"
void a(){
printf("\t\t+---call a() function\n");
}
void c(){
printf("\t\t+---call c() function\n");
}
int b(){
printf("\t+--- call b() function\n");
a();
c();
return 0;
}
int main(){
printf(" main() function()\n");
b();
}
~~~
* 運行方式是 main() call b() , 然後 b() 再 call a() 和 c() ,而每一個 function 在一開始會印出一行字(表示呼叫到自己)
* 執行 `./a.out` 會排列出函式呼叫的順序,產生 `gmon.out` 的檔案
~~~
main() function()
+--- call b() function
+---call a() function
+---call c() function
~~~
* 使用 `gprof -b a.out gmon.out` 會產生
~~~
Flat profile:
Each sample counts as 0.01 seconds.
no time accumulated
% cumulative self self total
time seconds seconds calls Ts/call Ts/call name
0.00 0.00 0.00 1 0.00 0.00 a
0.00 0.00 0.00 1 0.00 0.00 b
0.00 0.00 0.00 1 0.00 0.00 c
Call graph
granularity: each sample hit covers 2 byte(s) no time propagated
index % time self children called name
0.00 0.00 1/1 b [2]
[1] 0.0 0.00 0.00 1 a [1]
-----------------------------------------------
0.00 0.00 1/1 main [9]
[2] 0.0 0.00 0.00 1 b [2]
0.00 0.00 1/1 a [1]
0.00 0.00 1/1 c [3]
-----------------------------------------------
0.00 0.00 1/1 b [2]
[3] 0.0 0.00 0.00 1 c [3]
-----------------------------------------------
Index by function name
[1] a [2] b [3] c
~~~
* 會發現調用圖寫出了 main 呼叫 b ,而 b 呼叫 a 和 c
* 文中說明所花時間很少是因為函式都只有做 printf()
* 如果使用 -p 是只輸出函式調用圖 ,而上頭的 -b 是不會輸出標題的描述 ,-q 是只輸出時間消耗
* 搭配 Cflow , 使用 `cflow test.c` 生成出來的 gmon.out
* 執行 `gprof -b cflow gmon.out` 會將函式使用的情況印出
~~~
Each sample counts as 0.01 seconds.
no time accumulated
% cumulative self self total
time seconds seconds calls Ts/call Ts/call name
0.00 0.00 0.00 122 0.00 0.00 auto_processor
0.00 0.00 0.00 122 0.00 0.00 delete_parm_processor
0.00 0.00 0.00 121 0.00 0.00 move_parm_processor
0.00 0.00 0.00 114 0.00 0.00 _option_is_end
0.00 0.00 0.00 110 0.00 0.00 hash_string
0.00 0.00 0.00 110 0.00 0.00 hash_symbol_hasher
...
...
Call graph
granularity: each sample hit covers 2 byte(s) no time propagated
index % time self children called name
0.00 0.00 122/122 hash_do_for_each [31]
[1] 0.0 0.00 0.00 122 auto_processor [1]
-----------------------------------------------
0.00 0.00 122/122 hash_do_for_each [31]
[2] 0.0 0.00 0.00 122 delete_parm_processor [2]
-----------------------------------------------
0.00 0.00 121/121 hash_do_for_each [31]
[3] 0.0 0.00 0.00 121 move_parm_processor [3]
...
...
~~~
* Graphviz 工具
* 文中提到 Graphviz 有 Dot 語言直連圖的能力,所以我們使用他將程式視覺化
* 搭配 [gprof2dot](https://github.com/jrfonseca/gprof2dot) 套件
* 將 test.c 畫成圖
![](https://i.imgur.com/2gFbqyA.png)
* GNU gprof 的原理,參考 [GNU gprof](https://sourceware.org/binutils/docs/gprof/Introduction.html#Introduction)
分析步驟 :
1. You must compile and link your program with profiling enabled. See Compiling a Program for Profiling.
* The `-pg` option also works with a command that both compiles and links
* `-pg` 是 compliation 和 link 的 option,如果沒使用就沒有 call-graph data
2. You must execute your program to generate a profile data file.
* 一但程序被編譯成分析用,他還是會像原本那樣輸出,只是會多花時間蒐集和寫入資料
* 程序結束時會寫入 gmon.out file
3. You must run gprof to analyze the profile data.
* 通常在 compile 時加入 `-pg` , 就代表著每一個 function 會去 call mcount (or _mcount, or __mcount, depending on the OS and compiler) 做為第一個操作之一
* 包含 profiling library 的 mcount routine,通常利用檢查 stack frame 去找 child 的地址和返回 original parent 的地址
* mcount 是一個典型的簡短的組語 stub routine ,利用兩個參數 frompc 和 selfpc 呼叫 __mcount_internal , __mcount_internal 是負責維護 in-memory call graph
記錄 frompc (從哪個 program counter 來) , selfpc (自己的 program counter), 和調用次數。
### SGX 介紹與特性 [(Intel SGX)](https://www.techbang.com/posts/39194-intel-skylake-microarchitecture-processors-will-open-sgx-security-features)
* SGX 之特性: [參考](http://blog.csdn.net/u010071291/article/details/52750372)
* 使應用開發人員能夠保護其機密資料與程式碼在 SGX 所創建的 enclave (可理解為 TEE) 運行, 不受其他具有更高特權軟體或是惡意程式進行修改
* 能使敏感性高的程式和數據之完整性與機密性受到保護, 因為正常運作的系統軟體會對系統進行資源管理和控制
* 即使攻擊者以掌握系統控制權並且直接攻擊記憶體內部資料情況下, 透過應用程序來定義程式和數據安全區域進而受到保護
* SGX enclave 啟動與銷毀
* SGX enclave 可信任通訊通道
* SGX 之缺陷與改善:
* [研究人員打造可攻陷英特爾SGX硬體安全保護的惡意程式](https://www.ithome.com.tw/news/112724)
* [SGXKernel: A Library Operating System Optimized for Intel SGX](https://dl.acm.org/citation.cfm?id=3075572)
* SGX 之應用: [參考](http://blog.csdn.net/guiguzi5512407/article/details/51280340)
* [透明性驗證](https://pdfs.semanticscholar.org/3ff3/23cb8da17e48799af7de9d82c20ac9670617.pdf)
* [防止洩漏隱私資訊的頁錯誤](https://pdfs.semanticscholar.org/edee/079656e8b5d7111ca41a0af381201a1e1cd4.pdf)
### Cross Compiler [參考](https://www.airs.com/ian/configure/configure_5.html)
當使用 native compiler 來編譯某程式時, 此程式只能執行於同編譯器的運行平台.
然而 cross complier 編譯的是預執行於目標平台上的程式. 舉例來說, 有一 cross compiler 雖運行於 windows 7 pc 上卻可編譯程式而運行於 Android smartphoe. Cross compiler 必須能夠在多重平台上編譯.
倘若以 GCC 為例來解釋, 則有三個概念須先了解:
Build
編譯 GCC 的平台
Host
運行 GCC 的平台
Target
GCC 編譯產生的程式所運行的平台
* build = host = target 為 native compiler,例如 Ubuntu 的 GCC 就是native compiler
* build = host,但 target 與前兩者不同,就是cross compiler
### Libffi 專案功用 [參考](http://www.chiark.greenend.org.uk/doc/libffi-dev/html/Using-libffi.html#Using-libffi)
* Calling Covention (呼叫慣例)
因為函式呼叫牽涉到參數的傳遞, 所以並不只是單純跳到那個 Address 執行程式碼再跳回來這麼簡單, 呼叫副程式(函式)的主程式, 需要知道怎麼填參數, 副程式(函式)才能接到參數後進行處理, 再將結果傳給主程式. 這段協定, 稱之為Calling Convention(呼叫慣例)
* Libffi Package
有些程式在編譯期間可能不知道有什麼參數傳遞到函式. 舉例來說, 直譯器 (Interpreter) 可能在執行期間被告知關於呼叫函數上的參數的型態與數目, 而 Libffi 可以扮演這些函式從直譯器到編譯完成之程式碼的橋樑
* Libffi 函式
在使用 Libffi 之前需要先創造出 ffi_cif 物件, 方便之後的多重呼叫. 在 ffi_cif 中的 cif 扮演著 call interface, ffi_prep_cif 是進一步為了 call interface object 所使用, 如下範例程式碼所示
```c=
#include <stdio.h>
#include <ffi.h>
int main()
{
ffi_cif cif;
ffi_type *args[1];
void *values[1];
char *s;
ffi_arg rc;
/* Initialize the argument info vectors */
args[0] = &ffi_type_pointer;
values[0] = &s;
/* Initialize the cif */
if (ffi_prep_cif(&cif, FFI_DEFAULT_ABI, 1,
&ffi_type_sint, args) == FFI_OK)
{
s = "Hello World!";
ffi_call(&cif, puts, &rc, values);
/* rc now holds the result of the call to puts */
/* values holds a pointer to the function's arg, so to
call puts() again all we need to do is change the
value of s */
s = "This is cool!";
ffi_call(&cif, puts, &rc, values);
}
return 0;
}
```
### BOLOS 運作原理 [參考](https://ledger.readthedocs.io/en/0/bolos/index.html)
* BOLOS 全名為 Blockchain Open Ledger Operating System, 是為一個嵌入式安全作業系統, 可執行於 Secure Elements, Hardware Security Modules 或 CPU enclave (TEE, Intel SGX)
* 在其系統架構中, 其應用程式運行在虛擬裝置上, 可在所有硬體上重新配置, 為其一大優點
* 下圖為透過應用程式來俯視整體系統運作, 在 Appliation 周圍的方塊可被視為 coprocessor, 皆受於 Application 的直接指令之下. 有些方塊除了接收指令外, 也能夠觸發事件產生, 舉例來說, 透過使用者按下按鈕後, application 下指令給 I/O peripheral 進行運作
![](https://i.imgur.com/MfJjEj0.png)
* BOLOS 被定義成兩層的 Delegation Model. 首先當應用程式執行時, BOLOS 便只提供基礎的服務給他們. 其後執行終了, BOLOS 不會有任何指令運作也就不會更動到 I/O 操作. 下圖為 USB delegation 流程
![](https://i.imgur.com/d7HiNTV.png)
* 下圖 BOLOS 架構細節:
* BOLOS 可分成兩個晶片; 一個為 secure, 另一具有 JTAG 作為 proxy
* 在 secure 上劃分成兩部分; 一部分可與軟硬體互動且在 NDA 下, 另一部分可讓應用程式載入所用
* 透過 proxy 晶片作為數據的 Inputs/outputs 來連接 secure element, 一來消弭其安全性隱憂外, 更善用 simple asynchronous protocol 讓 secure element 與 proxy 合作執行
![](https://i.imgur.com/SCDB6J4.png)
* [moxiebox execution environment](https://github.com/ian910297/moxiebox/blob/master/sandbox-design.md) 所對應 BOLOS 運作原理為:
* Phase 1 發生在 Secure Element 當中, 並將 ELF 資料從 BOLOS Loader 匯入
* Phase 2 一樣發生在 Secure Element 中, 並將匯入的資料與程式在 BOLOS kernel 中執行. 本身是 single thread 且 single pipeline
* Phase 3 發生在 proxy 部份, 將運算結果存放在此
## Model Checking
### 自動機理論 [(Automata theory)](https://cs.stanford.edu/people/eroberts/courses/soco/projects/2004-05/automata-theory/basics.html)
自動機理論的主要目標是, 建立能夠對具有離散狀態的系統進行其動態行為的描述與分析, 在此系統中其訊號能夠被週期性地取樣.
這一類的機器具有以下三個特徵:
* 輸入: 假設從輸入訊號的有限集合選取一組符號序列
* 輸出: 從一輸出的有限集合中選取一組符號序列
* 狀態: 基於自動機類型下所定義的一有限集合
主動機有以下四種類型:
* Finite-state machine
* Pushdown automata
* Linear-bounded automata
* Turing machine
有限狀態主動機介紹:
### Model Checking in Practice
#### Case Study
[A Model Checking-based Method for Verifying Web Application Design](http://www.sciencedirect.com/science/article/pii/S1571066106003343)
[IOT: Formal Security Analysis of Smart Embedded
Systems](http://blogs.ubc.ca/karthik/files/2016/09/Farid-acsac2016.pdf)
#### Practical Application
[Stochastic Model Checking](http://www.prismmodelchecker.org/papers/sfm07.pdf)
* a probabilistic security protocol
* dynamic power management
* a biological pathway
### cbmc
Bounded Model Checker for C and C++
* 參數,詳細可以使用 cbmc --help 查看
--bounds-check
--pointer-check
--show-vcc :verification conditions
--unwind :將迴圈展開的數量上限,詳細[參考](http://www.cprover.org/cprover-manual/cbmc-loops.shtml)
--unwinding-assertions
--trace
cbmc --unwind 20 binary_search.c
```
** Results:
[test_bsearch.assertion.1] assertion linear_search_result == binary_search_result: SUCCESS
[test_sort.assertion.1] assertion is_sorted(x, size): SUCCESS
** 0 of 2 failed (1 iteration)
VERIFICATION SUCCESSFUL
```
cbmc fft.c
```
[main.assertion.1] assertion !ok: FAILURE
** 1 of 1 failed (1 iteration)
VERIFICATION FAILED
```
利用 --trace 顯示詳細資料
cbmc --trace fft.c
```
State 1620 file fft.c line 175 function main thread 0
----------------------------------------------------
k=0u (00000000000000000000000000000000)
State 1621 file fft.c line 175 function main thread 0
----------------------------------------------------
k=0u (00000000000000000000000000000000)
State 1624 file fft.c line 175 function main thread 0
----------------------------------------------------
k=1u (00000000000000000000000000000001)
State 1628 file fft.c line 175 function main thread 0
----------------------------------------------------
k=2u (00000000000000000000000000000010)
State 1632 file fft.c line 175 function main thread 0
----------------------------------------------------
k=3u (00000000000000000000000000000011)
State 1636 file fft.c line 179 function main thread 0
----------------------------------------------------
expected_value=8u (00000000000000000000000000001000)
State 1637 file fft.c line 175 function main thread 0
----------------------------------------------------
k=4u (00000000000000000000000000000100)
State 1641 file fft.c line 171 function main thread 0
----------------------------------------------------
j=4u (00000000000000000000000000000100)
State 1644 file fft.c line 169 function main thread 0
----------------------------------------------------
i=4u (00000000000000000000000000000100)
Violated property:
file fft.c line 190 function main
assertion !ok
!(ok != FALSE)
```
可以發現錯誤發生在 i,j,k=4 時
## 第 6 週作業回顧
### 是否已知曉搭配 computed goto 實作更高效的 opcode dispatch 呢?舉例說明並且附上效能分析
full-stack-hello 利用 [label as values](https://gcc.gnu.org/onlinedocs/gcc/Labels-as-Values.html) 的方式實做 computed goto
修改 full-stack-hello 的 vm_run 部份,改為使用 switch dispatch,比較兩個實做的效能差異
[修改後的 code](https://github.com/zhanyangch/full-stack-hello/commit/d705f78b8f93c023004a80bd1e35db46527bfc05)
- [ ] switch dispatch
```
Performance counter stats for 'sudo chrt -f 99 taskset -c 0 ./as_exec tests/fib-iterative.s --input 46' (100 runs):
74 cache-misses # 14.327 % of all cache refs ( +- 5.00% )
516 cache-references ( +- 0.71% )
1,675 instructions # 0.45 insn per cycle
3,682 cycles ( +- 1.40% )
0.005200966 seconds time elapsed ( +- 7.80% )
```
- [ ]computed goto
```
Performance counter stats for 'sudo chrt -f 99 taskset -c 0 ./as_exec tests/fib-iterative.s --input 46' (100 runs):
78 cache-misses # 15.177 % of all cache refs ( +- 3.95% )
513 cache-references ( +- 0.77% )
1,675 instructions # 0.47 insn per cycle
3,591 cycles ( +- 2.02% )
0.005170761 seconds time elapsed ( +- 3.95% )
```
執行時間差距不明顯,computed goto 比 switch dispatch 快 0.5%
### Fibonacci sequence 在真實世界中究竟有何應用?
#### fibonacci search
* [參考資料](https://openhome.cc/Gossip/AlgorithmGossip/FibonacciSearch.htm)
* 與二元搜尋法類似,但改用費氏數列當作搜尋間隔
* 目標 : 對一有 n 個元素且排序好的數列 a[n],找到 a[i]==key
方法 : 找到最接近的費波那契數 $fib_k$ 且 $fib_k+m=n, m \geq 0$
若 $key<a[fib[k-1]]$,則第一個搜尋位置為 fib[k-1] (即搜尋範圍為[0, fib[k]])
若 $key>a[x]$ 則第一個搜尋位置為 fib[k-1]+m (即搜尋範圍為[m, fib[k]+m])
```clike
int fibonacciSearch(int number[], int length, int key) {
int k = findK(Fib, length + 1);
int m = length - Fib[k];
int x = k - 1;
int i = x;
if(number[i] < key)
i += m;
int result = -1;
while(Fib[x] > 0) {
if(number[i] < key)
i += Fib[--x];
else if(number[i] > key)
i -= Fib[--x];
else {
result = i;
break;
}
}
return result;
}
```
* 時間複雜度:O(lg(n))
### 何謂 tail recursion 呢?舉出具體而微的案例並用 perf 解釋細部差異 (特別是 cycle count 的落差)
* tail recursion :
* A recursive function is tail recursive when the recursive call is the last thing executed by the function.
* 我們拿 Fibonacci 的數列來做比較
* Fibonacci tail recursion
~~~c=
// A tail recursive function to
// calculate n th fibnacci number
int fib(int n, int a = 0, int b = 1)
{
if (n == 0)
return a;
if (n == 1)
return b;
return fib(n-1, b, a+b);
}
~~~
* Fibonacci recursion
~~~c=
int fib(int x) {
if (x == 0)
return 0;
if (x == 1)
return 1;
return fib(x-1)+fib(x-2);
}
~~~
* 如果用 tail recursive 以 3 來說就像是:
* 因為 recursive call 是最後被執行的事,所以可以這樣 return 回去
~~~
fib (3,0,1) -> fib(2,1,1) -> fib(1,1,2)
return 2 <--- return 2 <--- return 2
~~~
* 如果用 recursive 以 3 來說就像是:
~~~
fib(3)------> fib(2)------>fib(0)
| | return 2 return 1
----->fib(1) ------>fib(1)
return 1 return 1
~~~
* 這樣比較下來發現,因為 recursive call 因為已經先把一些能計算的值放在參數中便於使用(如迴圈的複雜度),自然會比 recursive (如樹狀複雜度)用到時才呼叫快
* 另一個好處是 STACK 的使用 , [參考](https://itw01.com/ANHEWN7.html)
* 在編譯器判斷出此程式是 tail recursive (recursive call is the last thing executed by the function) 此時的 STACK 就可被重複覆蓋,像上方從尾端 return 回去的 2 都是可以重複使用同一塊空間的
* 舉出具體而微的案例並用 perf 解釋細部差異 (特別是 cycle count 的落差)
* 程式碼的部份我放在我的[上一份作業 simulator](https://hackmd.io/CYBgjCBsDMwMYFpgFZJgQFgJyQGYK2VQQFM5pkBDOAI0owHZdgg=#)
* 這邊先用 --input 10 去做跑 100 次的比較,發現 cycle 數的減少:
~~~
Performance counter stats for 'sudo chrt -f 99 taskset -c 0 ./as_exec -x Fib' (100 runs):
1622 instructions # 0.33 insn per cycle
4914 cycles ( +- 1.46% )
0.008097402 seconds time elapsed ( +- 1.50% )
~~~
~~~
Performance counter stats for 'sudo chrt -f 99 taskset -c 0 ./as_exec -x Fib' (100 runs):
1633 instructions # 0.33 insn per cycle ( +- 0.69% )
4802 cycles ( +- 1.61% )
0.007691896 seconds time elapsed ( +- 1.39% )
~~~
* 以 input 為 10 , cycle 數量的確猶如上方分析的 tail_recursion 是花比較少時間而且 cycle 數也較少
* 速度變快 (0.008097402-0.007691896) / 0.008097402 = 0.05007853136 相當於變快 5%
* cycle 數 (4914-4802) / 4914 = 0.02279202279 ,cycle 數下降 2.3%
* 做出不同 input 數值比較 (這裡列出 1~30 間隔為2,例如:1,3,5,7...)
* 所花費時間上 : 單位 second
* 有符合時間複雜度 recursion: $O(2^N)$ 和線性的tail_recursion $O(N)$
![](https://i.imgur.com/2zcGk3j.png)
* 但在 cycle 數方面
* 呈現不規則鋸齒狀:但還是可以看的出來在 number=19 後 tail 所花的 cycle 數都相對比 recursive 較少
![](https://i.imgur.com/1mOsCQ5.png)
* 尋找鋸齒狀原因:目前猜測與 cache 有關,因為用 perf 觀察 cache-misses 發現 cycle 數的趨勢和 cache-misses 趨勢雷同
* tail recursive 的 cycle
![](https://i.imgur.com/ALMQy7W.png)
* tail recursive 的 cache-misses
![](https://i.imgur.com/EvFtGDw.png)
* 如何預測 input 為多少時會有較高的 cache-misses?