# 開發紀錄(sandbox)
contributed by <`amikai`, `Nienzu`>

> 事情要有源頭, 前因後果, 要先研究源頭在了解技術

# 什麼是 crt0
每個人都知道 main function 是 c 語言的進入點, 那誰要來呼叫 main funtion 讓 c 程式啟動呢? 其實 crt0 就在做這件事情, 至於為什麼會對這支 crt0 的程式這麼陌生是因為 linker 都幫你把這件事情做完了, crt 的意思其實就是 c runtime, 0 的意思就代表一開始

> 有 crt0 有沒有 crt1?
> https://stackoverflow.com/questions/2709998/crt0-o-and-crt1-o-whats-the-difference

參考資料 2 提到 crt0 通常會做哪些事情:
1. 將目標平台所需要的狀態設定好， e.g. 設置合適的中斷向量
2. 初始化 stak 和 frame 的指標
3. 呼叫 c constructor 並且確認 destructor 在結束時會被呼叫
4. 實作其他平台所需要某些特定功能的初始化
5. 呼叫 main 函式
6. exit 之後並回傳 return code

> 探討參考資料的來源
> 例如應該要用 e.g.

其實 moxie box 的 crt0 都有相對應的程式碼

	.globl	__start
	.weak	_start
	.text
	.type	__start,@function
__start:
_start:
	/* zero fp to allow unwinders to stop */
	xor	$fp, $fp

	/* load sim stack pointer */
	gsr	$sp, 7

	/* zero the bss area */
	ldi.l	$r0, __bss_start__
	xor	$r1, $r1
	ldi.l	$r2, __bss_end__
	sub	$r2, $r0
	jsra	memset

	/* load sim memory descriptor base address */
	gsr	$r0, 6
	sta.l	moxie_memmap, $r0

	/* Set argc and argv (empty). */
	xor	$r0, $r0
	xor	$r1, $r1

	/* Call _init to invoke static constructors, etc.  */
	jsra	_init
	
	/* Call _fini at exit time for static destructors.  */
	ldi.l	$r0, _fini
	jsra	atexit

	jsra	main
	jsra	exit

.Lend:
	.size	__start,(.Lend-__start)

看到以下這段, 為何要將 bss 區段都塞 0?
bss 區段是放的是 static 變數或是未初初始化的全域變數, 在某些平台上會將此區段都塞 0. 在這個 case 裡使用 memset 將此區段都塞 0

 	/* zero the bss area */
	ldi.l	$r0, __bss_start__
	xor	$r1, $r1
	ldi.l	$r2, __bss_end__
	sub	$r2, $r0
	jsra	memset

> 可以之後跟老師問這邊哪邊講不好...

TODO: 為什麼需要 constructor 和 destructor

crt0 -> mmap 中間的起承轉合，還有為什麼要講 mmap？
--

參考資料:
1. https://en.wikipedia.org/wiki/Crt0
2. http://www.embecosm.com/appnotes/ean9/html/ch05s02.html
3. Understanding the linux kernel, 2nd
# memory map 介紹
>　跟上面那段一樣沒有觀察，沒頭沒尾滴　

當一個 process 使用了 mmap() 這個系統呼叫, 則 kernerl 會在此 process 的虛擬記憶體空間產生一個記憶體映射.

記憶體映射分為兩種類型:
1. `file mapping (or file backed)`: file mapping 的概念是將某個檔案直接映射到呼叫行程的虛擬記憶體空間. 因為 [demand paging](https://en.wikipedia.org/wiki/Demand_paging) 的機制, 當 cpu 動用(touch)到此虛擬分頁 (virtual page) 時, 才會 swap in

2. `anonymous mapping`: anonymous mapping 的概念是將某個 anonymous file 對應到虛擬記憶體空間, 此 file 會由 kernel 產生, 而此 file 的內容皆為二進制的 0.
當 cpu 動用到此映射空間時, 則 kernel 會在實體記憶體找到找到一個 victim page, 若使 victim page 是 dirty 則 swap out, 再把此 page 以二進制的 0 覆寫, 並且更新 page table, 並將 valid bit 標為 resident, 因此這樣的 page 有時又稱為 demand-zero pages

映射的虛擬記憶體空間可是私有的 (private )或是共享的 (shared)
1. `Shared mapping`: 若有多的 process 將同一個 file 映射到自己的虛擬記憶體空間, 這些 process 只要對自己虛擬記憶體空間所映射的區塊有任何寫入, 則其他 process 也會看見. , 並且這些更改會反映到 disk 中, csapp 用一張很好的圖來解釋

2. `Private mapping`: 當每一個 process 將此 file 映射到自己的虛擬記憶體空間時, 此映射的虛擬記憶空間相對應的 PTE(page table entries) 則會被標示 (flag) 為唯讀, 此映射的空間被標示為 private copy on write. 只要這些 process 不要去寫入這個 private 區域, 則這些 process 會持續共享對應的實體記憶體區塊, 若有一個 process 寫入這個 private 區域, 則此寫入這個區域的某個 page 會觸發 protection fault, 而 handler 則會在實體記憶體裡複製這個 page, 將 PTE 更新改為指向此 page, 並且把將權限改為寫入. 當 handler 結束且 return 時, cpu 則重新執行寫入的動作.

+---------+------------------------------------------------------------+----------------------------------------+--+--+
|         |                            File                            |               Anonymous                |  |  |
+---------+------------------------------------------------------------+----------------------------------------+--+--+
| private | Initializing memory from contents of file                  | Memory allocation                      |  |  |
| Shared  | Memory-mapped I/O; sharing memory between processes (IPC)  | Sharing memory between processes (IPC) |  |  |
+---------+------------------------------------------------------------+----------------------------------------+--+--+

參考資料:
1. csapp 3E section 9.8
2. [csapp virtual memory 投影片](http://www.cs.cmu.edu/afs/cs/academic/class/15213-s12/www/lectures/17-vm-systems-4up.pdf)

# moxiebox 如何與外界溝通
為了要讓程式讀入輸入值, 所以我寫了一個 python 的小工具, 以每 4 bytes 以 little endian 的方式寫入 file, 以下的範例是以寫入 10 作為輸入值

newFileBytes = [0xa]
# make file
newFile = open("data", "wb")
# write to file
for byte in newFileBytes:
    print("write")
    newFile.write(byte.to_bytes(4, byteorder='little'))

當 sandbox 要讀入資料時, 則會呼叫 loadRawData 的函數, loadRawData 使用了自己定義的 open 函式, 其實內部就是使用 mmap 達成, 而為了保護資料在 moxiebox時不被竄改, loadRawData 使用 PROT_READ 當作 mmap 其中的一個參數

static bool loadRawData(machine &mach, const string &filename)
{
    // open and mmap input file
    mfile pf(filename);
    if (!pf.open(O_RDONLY))
        return false;

    static unsigned int dataCount = 0;
    char tmpstr[32];

    // alloc new data memory range
    sprintf(tmpstr, "data%u", dataCount++);
    size_t sz = pf.st.st_size;
    addressRange *rdr = new addressRange(tmpstr, sz);

    // copy mmap'd data into local buffer
    rdr->buf.assign((char *) pf.data, sz);
    rdr->updateRoot();

    // add to global memory map
    return mach.mapInsert(rdr);
}

bool mfile::open(int flags, mode_t mode, bool map)
{
    ...
    int mmap_prot;
    if (flags & O_RDWR)
        mmap_prot = PROT_READ | PROT_WRITE;
    else if (flags & O_WRONLY)
        mmap_prot = PROT_WRITE;
    else
        mmap_prot = PROT_READ;

    data = mmap(NULL, st.st_size, mmap_prot, MAP_SHARED, fd, 0);
    if (data == (void *) -1)
        return false;

    return true;
}

而 sandbox 輸出是使用以下函式, 從此 function 可以知道, sandbox 將 pointer to return buffer 放置到 $r0, return buffer 長度放到 $r1

/*
 * 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

# sandbox
sandbox 可藉由 -d 選項輸入資料, 但是資料都是二進制檔, 無法用看的就知道檢驗資料是否正確，此時可用 xxd 工具進驗證:
e 選項為 little endian, -g4選項為: 將 4 bytes 視為一個 group

$ xxd -p -e -g4 data

# GDB command file
每次都要打 target remote 實在太慢, 可以先預先寫好 command file, 以 rtlib 為例:
我的 command file 長這樣:

# command_file
file rtlib
target remote :9999
b main
c

每次只要打上 `moxie-none-moxiebox-gdb -x command_file` 就可以幫你自動執行上述的指令

> mmap 的 or 沒有講
> 參數的傳遞沒解釋
>
# fib iterative implementation

	.globl	main
	.type	main,@function
	.text
main:
    dec $sp, 8

    /* find data */
    jsra find_data
    sto.l -4($fp), $r0 # -4($fp) = find_data return val

    /* $r0 = prot = MOXIE_PROT_READ | MOXIE_PROT_WRITE | MOXIE_PROT_EXEC */
    ldi.l $r0, 7 
    /* $r1 = flags = MOXIE_MAP_PRIVATE | MOXIE_MAP_ANONYMOUS */
    ldi.l $r1, 6
    /* mmap */
    mov $r2, $r0 # $r2 = prot
    mov $r3, $r1 # $r3 = flags
    xor $r0, $r0 # $r0 = 0
    ldi.l $r1, 0x10000 # $r1 = MAP_SIZE = 0x10000
    xor $r4, $r4 # $r4 = 0
    xor $r5, $r5 # $r5 = 0
    jsra mmap # mmap(NULL, MAX_SIZE, prot, flags, 0, 0)
    sto.l -8($fp), $r0 #  -8($fp) = mmap return val

    
    ldo.l $r0, -4($fp) # load find_data  return val
    jsra fib_iter
    mov $r1, $r0 # use $r1 get the result

    
    ldo.l $r0, -8($fp) # p = $r0 = mmap return value 
    st.l ($r0), $r1 #  *p = $r2

    ldo.l $r0, -8($fp) # p = $r0 = mmap return value, pass to setreturn
    ldi.l $r1, 4 # length is 4 bytes
    jsra setreturn

    /* exit(0) */
    xor $r0, $r0
    jsra exit


    .type fib_iter,@function
    .text
fib_iter:
    dec $sp, 4
    sto.l -4($fp), $r0
    
    /* fib $r2 is result */
    xor $r0, $r0 # a = 0
    xor $r1, $r1 # b = 0
    xor $r2, $r2 # t = 0
    xor $r3, $r3 # i = 0
    xor $r4, $r4 # n = 0
    xor $r6, $r6 # z = 0
    ldi.l $r1, 1 # b = 1
    ldo.l $r4, -4($fp) # n = input

    .L:
    mov $r2, $r0 # t = a
    add $r2, $r1 # t = t + b
    mov $r0, $r1 # a = b
    mov $r1, $r2 # b = t
    dec $r4,   1 # n --
    cmp $r4, $r6 # if(n>0)
    bgt .L       # goto L

    mov $r0, $r2 # return $r0
    ret




data_tag:
    .string "data0,"
    .size data_tag, 4
    
    
    
    .type find_data,@function
    .text
find_data:
        dec $sp, 4
        xor $r0, $r0
        lda.l $r0, moxie_memmap # $r0 = moxie_memmap
        sto.l -4($fp), $r0 # -4($fp) = moxie_memmap

    .L2:
        ldo.l $r0, -4($fp) # $r0 = -4($fp) = moxie_memmap = ent
        ld.l $r1, ($r0) # $r1 = ent->addr
        xor $r0, $r0 # $r0 = 0
        cmp $r1, $r0 # if(ent->addr == 0)
        beq .L3       # goto L3 and return

        
        ldo.l $r0, -4($fp) # $r0 = ent
        inc $r0, 8 # $r0 = (ent->tags)
        ldi.l $r1, data_tag; # $r1 = "data0,"
        jsra strstr # $r0 = strstr($r0, $r1)
        xor $r1, $r1 # $r1 = 0
        cmp $r0, $r1 # if($r0 != $r1)
        bne .L4       # goto L4

        ldo.l $r0, -4($fp) # r0 = ent
        inc $r0, 32 # r0 = ent++
        sto.l -4($fp), $r0
        jmpa .L2

    .L4:

        ldo.l $r0, -4($fp) # r0 = ent
        ld.l $r0, ($r0) # $r0 = ent->addr
        ld.l $r0, ($r0) # $r0 = *(ent->addr)
        ret
        
    .L3:
        ldi.l $r0, -1
        ret

:::info
作業要求

* 在 [moxiebox](https://github.com/sysprog21/moxiebox) 的 `tests` 目錄中，比照 [simulator](https://hackmd.io/s/BkQgqpe0Z) 作業要求，依序實作以下 Fibonacci 數列求值方法: (可用 C 程式實作，但需要附上詳盡的效能分析，善用 GNU gprof 和 GDB)
* recursive
* iterative
* 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)

:::

12/8 上課檢討

Sandbox 要探討什麼？

影片缺點
* 沒頭沒尾
* 頁面要放大 175%
* 程式碼的背景色黑色的話要放大 200% 來展示
* 人的眼睛一次看九行程式碼

寫一份技術報告的重點

* 觀察隔離的執行環境裡面到底做了什麼？
* 因此要從實驗的角度來設計一支程式來測試執行環境的執行效能、成果

* 觀察問題？定義問題？
*
老師指出的問題

* runtime 資料夾需要什麼？
* newlib -> clib(libc)
* runtime 裡面會有 C 標準函式庫的實作
* 進入 Main 之前到底要做哪些事情?
* C++ constructor 做什麼？
* 有些物件要在 main 之前就要存在，有些則是在之後動態產生
* crt0 -> mmap 中間的起承轉合，還有為什麼要講 mmap？

* bare mental 裸機(hint?)
- [ ] argc、argv 需要 stack 來存(HINT?)
- [ ] 怎麼叫做隔離？
題外話...
* MetaProgramming
* meta class
* 為何 C 語言是 portable ?
* 因為它是有「規範」的
* function call -> ABI
- [ ] C 語言函式 atexit
- 進入 main 前為何要 atexit?

ni
display/i $pc