2017q3 Homework4 (sandbox)

tags: `sysprog2017` `dev_record`

contributed by <HMKRL, HTYISABUG>

gprof

代碼剖析工具
能幫助找出諸如函式執行時間, 執行次數等資訊
無法測量 kernal space 的花費時間
詳細操作參閱 man gprof

實作 moxiebox 環境的 fibonacci 數列

不先試試什麼都不會知道
先寫了含 -i, --input 參數的 fib-iterative.c
修改 tests/Makefile 以編譯自己的程式

/home/hty/x-tools/moxie-none-moxiebox/lib/gcc/moxie-none-moxiebox/7.2.0/../../../../moxie-none-moxiebox/lib/libc.a(lib_a-writer.o): In function `_write_r':
/home/hty/Downloads/build-toolchain/.build/moxie-none-moxiebox/src/newlib/newlib/libc/reent/writer.c:58: undefined reference to `_write'
/home/hty/x-tools/moxie-none-moxiebox/lib/gcc/moxie-none-moxiebox/7.2.0/../../../../moxie-none-moxiebox/lib/libc.a(lib_a-closer.o): In function `_close_r':
/home/hty/Downloads/build-toolchain/.build/moxie-none-moxiebox/src/newlib/newlib/libc/reent/closer.c:53: undefined reference to `_close'
/home/hty/x-tools/moxie-none-moxiebox/lib/gcc/moxie-none-moxiebox/7.2.0/../../../../moxie-none-moxiebox/lib/libc.a(lib_a-lseekr.o): In function `_lseek_r':
/home/hty/Downloads/build-toolchain/.build/moxie-none-moxiebox/src/newlib/newlib/libc/reent/lseekr.c:58: undefined reference to `_lseek'
/home/hty/x-tools/moxie-none-moxiebox/lib/gcc/moxie-none-moxiebox/7.2.0/../../../../moxie-none-moxiebox/lib/libc.a(lib_a-readr.o): In function `_read_r':
/home/hty/Downloads/build-toolchain/.build/moxie-none-moxiebox/src/newlib/newlib/libc/reent/readr.c:58: undefined reference to `_read'
/home/hty/x-tools/moxie-none-moxiebox/lib/gcc/moxie-none-moxiebox/7.2.0/../../../../moxie-none-moxiebox/lib/libc.a(lib_a-sbrkr.o): In function `_sbrk_r':
/home/hty/Downloads/build-toolchain/.build/moxie-none-moxiebox/src/newlib/newlib/libc/reent/sbrkr.c:58: undefined reference to `_sbrk'
/home/hty/x-tools/moxie-none-moxiebox/lib/gcc/moxie-none-moxiebox/7.2.0/../../../../moxie-none-moxiebox/lib/libc.a(lib_a-fstatr.o): In function `_fstat_r':
/home/hty/Downloads/build-toolchain/.build/moxie-none-moxiebox/src/newlib/newlib/libc/reent/fstatr.c:62: undefined reference to `_fstat'
/home/hty/x-tools/moxie-none-moxiebox/lib/gcc/moxie-none-moxiebox/7.2.0/../../../../moxie-none-moxiebox/lib/libc.a(lib_a-isattyr.o): In function `_isatty_r':
/home/hty/Downloads/build-toolchain/.build/moxie-none-moxiebox/src/newlib/newlib/libc/reent/isattyr.c:58: undefined reference to `_isatty'
collect2: error: ld returned 1 exit status
make: *** [fib-iterative] Error 1

編譯後馬上遇到一大堆錯誤
從錯誤訊息可以得知，這些錯誤是因為不存在相應 library 導致的
從 sandbox-design.md 得知 moxiebox 不提供任何 POSIX API
可用 library 只有以下幾種

Runtime environment:
- moxie_memmap - Global variable, pointer to list of struct moxie_memory_map_ent, which describes the execution environment's input data.
- setreturn(3) - Pointer to environment's output data buffer. This is the data returned from the sandbox to the user.
- stdlib.h: abort(3), exit(3)
- string.h: memchr(3), memcmp(3), memcpy(3), memset(3)
- string.h: strchr(3), strcmp(3), strcpy(3), strlen(3), strncpy(3), strcpy(3), strstr(3)
Runtime environment - crypto:
- sha256: sha256_init(), sha256_update(), sha256_final()
System calls:
- mmap(2) - MAP_PRIVATE|MAP_ANONYMOUS to allocate heap memory.
- _exit(2) - End process

所有能使用的相關內容都被記載在 runtime/sandboxrt.h

在 moxiebox 中沒有 malloc 函式
作為替代方案, 可用 mmap 搭配 MAP_PRIVATE | MAPANONYMOUS 來配置記憶體

mmap 使用上大概可以根據修改能見度跟 mapping 類型分為四類

能見度 \ 類型	file	MAP_ANONYMOUS
MAP_PRIVATE	以檔案內容初始化記憶體	配置記憶體
MAP_SHARED	memory mapping I/O, IPC	IPC

moxie_memmap 是來自 moxiebox 的輸入
為一陣列, 每一單元資料結構如下

struct moxie_memory_map_ent {
    void *addr;
    size_t length;
    char tags[32 - 4 - 4];
};

根據 moxiebox 的 usage
用 option -d 可以把文件載入為 input

這是 moxiebox 的 usage
README.md, sandbox-design.md 都沒有提到
打錯 option 時才無意中發現

Usage: src/sandbox [options]

options:
-E <directory>		Add to executable hash search path list
-e <hash|pathname>	Load specified Moxie executable into address space
-D <directory>		Add to data hash search path list
-d <file>		Load data into address space
-o <file>		Output data to <file>.  "-" for stdout
-t			Enabling simulator tracing
-g <port>		Wait for GDB connection on given port
-p <file>		Write gprof formatted profile data to <file>

gdb stub

在使用 gdb 接入 moxiebox debug 的時候
程式發生了不正常跳過程式片段的行為

向老師詢問後, 確定是 moxiebox 內建的 gdb stub 有 bug

另外也發現執行 continue 時有錯誤行為：

(gdb) c
Continuing.

Program received signal SIGTRAP, Trace/breakpoint trap.
0x00001162 in _exit ()

程式結束，但 gdb 仍收到 SIGTRAP

追蹤程式碼並檢查 gdb stub:

$ grep -r gdb
src/moxie.h:40:   gdb/config/moxie/tm-moxie.h file in the REGISTER_NAMES macro.  */
src/sandbox.cc:188:                        uint32_t &gdbPort)
src/sandbox.cc:236:            gdbPort = atoi(optarg);
src/sandbox.cc:366:static int gdb_main_loop(uint32_t &gdbPort, machine &mach)
src/sandbox.cc:383:    serv_addr.sin_port = htons(gdbPort);
src/sandbox.cc:547:    uint32_t gdbPort = 0;
src/sandbox.cc:549:    sandboxInit(mach, argc, argv, outFilename, gmonFilename, gdbPort);
src/sandbox.cc:551:    if (gdbPort)
src/sandbox.cc:552:        gdb_main_loop(gdbPort, mach);

得知 gdb stub 的程式本體在函式 gdb_main_loop 中

參考 gdb remote protocal 並對照程式碼實作
發現其中幾個部份留有 FIXME :

c (continue) 部份:

case 'c':
                    wrc = write(newsockfd, "+", 1);
                    sim_resume(mach);
                    // FIXME.. assuming BREAK for now
                    sendGdbReply(newsockfd, "S05");
                    mach.cpu.asregs.regs[16] -= 2;
                    i += 4;

S05 對應 linux signal table 即為 SIGTRAP

應該將指令的回傳訊息改為正確的 signal.

對照程式碼後，確認程式收到的 signal 會存在 cpu.asregs.exception 中

case 0x1: /* SYS_exit */
{
    cpu.asregs.exception = SIGQUIT;
    break;
}

因此搭配原有的 word2hex 將正確的 signal 回傳：

case 'c':
    wrc = write(newsockfd, "+", 1);
    sim_resume(mach);
                                                
    /* send correct signal to remote gdb */
    word2hex(reply, mach.cpu.asregs.exception);
    reply[5] = 'S';
    sendGdbReply(newsockfd, &reply[5]);

m 指令處的 FIXME 也用同樣的方法實作錯誤確認：

char *p = (char *) mach.physaddr(addr, length);
    if (!p) {
        word2hex(reply, errno);
        strncpy(reply, &reply[6], 2);
        goto cmd_m_out;
}

不同點在於 m 指令接受的回傳只有以 hex 表示的 errno 值

gdb command file

可以將 gdb 指令寫在檔案中，在常需要重複行為(例如做 remote debugging 所需的 target remote 指令)

gdb_cmd:

target remote :9999
break main
run

讀取command file:
(gdb) source gdb_cmd

在編寫 fibonacci 的過程中
一開始在使用 -o option 時會產生錯誤

Sim exception 7 (Bus error)

參考 tests/sha256.c 修改程式碼, 發現是 mmap 的 length 參數出了問題

本來閱讀參考書^[1]了解到, 就算 length 沒給到 page size
系統在分配記憶體時也會以 page size 為單位分配

但是依據這邊的程式行為來看 moxiebox 的 mmap 似乎不會自動延展記憶體配置
才會導致在 setreturn 時產生 Bus error

因此將 length 修改為以 runtime/sandboxrt.h 提供的 MACH_PAGE_SIZE 為單位
就成功修正這個錯誤了

移植 constant-time-sorts 到 moxiebox

在開始移植之前要先確認非 constant-execution-time 的 sort 在 moxiebox 會有什麼行為
參考來自 github 的樣本^[1]編寫 selection , insertion , bubble sort
在這個步驟, 我們遇到了超出預想的錯誤




















static void swap(int *a, int *b)
{
    int tmp = *a;
    *a = *b;
    *b = tmp;
}

void selectionsort(int array[], int n)
{
    int min;

    for (int i = 0; i < n; ++i) {
        min = i;

        for (int j = i; j < n; j++)
            if (array[min] > array[j]) min = j;
       
        swap(&array[i], &array[min]);
    }
}

這是一段 selection sort 的程式碼
這段程式碼在 moxiebox 中執行時會產生 Sim exception 7 (Bus error)
藉由 gdb 觀察錯誤點時會得到以下錯誤訊息

Program received signal SIGEMT, Emulation trap.
0x00001430 in swap (b=0x3304, a=0x2b08) at sort.c:49
49          *a = *b;

我們得到 SIGEMT 這個 signal 導致了程式的錯誤
上網查詢, SIGEMT 出現的情況為「虛擬環境接收到不被識別的指令」
為了得知究竟哪裡產生這個錯誤, 我們藉由 grep 挖掘程式碼中有關 SIGEMT 的片段

$ grep -ir SIGEMT

結論是程式碼中根本沒有任何相關的片段
因此我們判斷可能是 gdb stub 在傳輸接收時有問題
於是加上些觀察用程式碼，將 gdb stub 的回複字串印出來觀察：

+$S07#BA

可以發現實際上被傳送的是 SIGBUS(7) , 但接收端卻將它辨認為 SIGEMT(?)

進一步藉由 gdb 觀察產生錯誤的程式碼片段
發現錯誤是產生在 st.l 這個組語指令執行的時候

(gdb) x/8i $pc-4
   0x15ea <insertionsort+220>:  ldo.l   $r1, 0xfff4($fp)
=> 0x15ee <insertionsort+224>:  st.l    ($r0), $r1
   0x15f0 <insertionsort+226>:  ldo.l   $r0, 0xfffc($fp)
   0x15f4 <insertionsort+230>:  inc     $r0, 0x1
   0x15f6 <insertionsort+232>:  sto.l   0xfffc($fp), $r0
   0x15fa <insertionsort+236>:  ldo.l   $r1, 0xfffc($fp)
   0x15fe <insertionsort+240>:  ldo.l   $r0, 0x10($fp)
   0x1602 <insertionsort+244>:  cmp     $r1, $r0

藉由 grep 挖掘到 moxie.cc 中實作了 st.l 的功能

case 0x0b: /* st.l */
{
    int dest = (inst >> 4) & 0xf;
    int val = inst & 0xf;

    TRACE("st.l");
    wlat(mach, cpu.asregs.regs[dest], cpu.asregs.regs[val]);
} break;

順著所用函式往下挖

/* Write a 4 byte value to memory.  */

static void INLINE wlat(machine &mach, word addr, word v)
{
    if (!mach.write32(addr, v))
        mach.cpu.asregs.exception = SIGBUS;
}

可以看見 gdb stub 傳送的 SIGBUS 是在這邊被設置的
這說明 mach.writes2(addr, v) 產生了錯誤

bool machine::write32(uint32_t addr, uint32_t val)
{
    uint32_t *paddr = (uint32_t *) physaddr(addr, 4, true);
    if (!paddr)
        return false;

    *paddr = val;
    return true;
}

挖掘的成果到這裡為止, 接下來為何會發生錯誤尚未釐清