2017q3 Homework3 (simulator) === ###### tags: `sysprog2017` contributed by <`TsengWen`, `vasv75182366`> ## 系統環境 ``` 16.04.1-Ubuntu Architecture: x86_64 Byte Order: Little Endian CPU(s): 4 Model name: Intel(R) Core(TM) i5-7200U CPU @ 2.50GHz L1d cache: 32K L1i cache: 32K L2 cache: 256K L3 cache: 3072K ``` ## 解析程式 ![](https://i.imgur.com/SXjpCUj.png) - 主要由 `driver.c` 控制整個程式流程以及解析使用者輸入的參數。 - `as`：處理輸入`.s`檔，產生對應的 objeck file ,以及設定 `vm_env` - `vm`：虛擬機器，內涵虛擬機器的架構,運作 - `opcode`：自訂指令集,以及相關實作,實作主要用於虛擬機器 - `elf`：提供產生 object file 相關的函式 ![](https://i.imgur.com/809W9HB.png) ```clike= switch (req) { case ASSEMBLE_AND_EVAL: { assemble_from_fd(env, in_fd); hook_opcodes(env); vm_run(env); vm_free(env); break; } case ASSEMBLE_AND_WRITE_ELF: { int len; assemble_from_fd(env, in_fd); len = write_to_elf(env, out_fd); vm_free(env); if (len < 0) FATAL(-1, "write ELF file %s failed (%s)\n", out_file, strerror(errno)); break; } case LOAD_ELF_AND_EVAL: { load_from_elf(env, in_fd); hook_opcodes(env); vm_run(env); vm_free(env); break; } default: FATAL(-1, "unknown request: %d\n", req); break; } ``` - VM架構 由 `vm_env` 來得知 ![](https://i.imgur.com/jjlwIla.png) ### vm_regs： * pc：program counter，目前執行的指令的位置 * sp：stack pointer，目前 stack 最後的位置 * from：最後一個 branch/return 之前 pc 的位置 * to：最後一個 branch/return 之後 pc 的位置 ### storage： - insts：存放 program 中每個 instruction - cpool：存放 program 中被使用的常數 - temps：從 0 開始存放暫存的變數，從尾端開始則是 stack，用於處理 call 跟 ret 指令 ### ELF - Elf(Executable and Linking Format）是 object file 的檔案格式，由 AT&T 公司在設計第五代UNIX (UNIX System V) 時所發展出來。 ##### Object file 主要有 3 種類別： 1. relocatable file 2. executable file 3. shared object file relocatable file 即副檔名為 .o 的檔案、 executable file 為一般的執行檔、 shared object file 則是 *.so（shared libraries）檔案。 #### ELF 格式可以分為兩種不同觀點 ![](https://i.imgur.com/XsfKuti.png) - Linking view 指的是經由 assembler 或 linkage editor 編譯過，可被 CPU 執行的檔案格式，也就是儲存在儲存裝置上的程式格式（stored programs），以 **分段 (Section)** 為主的結構。 - Execution view 指的是由 loader 載入後，程式執行時的格式，也就是存在於記憶體上的程式格式（process），是以 **分區 (Segment)** 為主的結構。 #### 檔頭 ELF header 在ELF檔案格式中，最基本的就是它的檔頭（header）部份，儲存 object file 的各種資訊。 ``` struct __attribute__((__packed__)) _elf32_dr_entry { uint8_t e_ident[16]; uint16_t e_type; uint16_t e_machine; uint32_t e_version; uint32_t e_entry; uint32_t e_phoff; uint32_t e_shoff; uint32_t e_flags; uint16_t e_ehsize; uint16_t e_phentsize; uint16_t e_phnum; uint16_t e_shentsize; uint16_t e_shnum; uint16_t e_shstrndx; }; ``` ##### 檔頭格式 |Field |Description| | -------- | -------- | e_ident |用來辨別檔案是否為ELF，並包含一些machine independent 的資料。 e_type |檔案的類型 e_machine |檔案的平臺 e_version |版本資訊 e_entry |程式的起始位址（process virtual address） e_phoff |program header table的檔案偏移值（offset），單位是bytes。如果沒有program header table則此值為0。 e_shoff |section header table的檔案偏移值（offset），單位是bytes。如果沒有section header table則此值為0。 e_flags |與processor有關的旗標值 e_ehsize |ELF header的長度，單位是bytes。 e_phentsize |program header table每個entry的長度（bytes），每個entry的長度都相等。 e_phnum |program header table的entry個數，若無program header table 則此欄的值為0。 e_shentsize |section header table每個entry的長度（bytes），每個entry的長度都相等。 e_shnum |section header table的entry個數，若無program header table則此欄的值為0。 e_shstrndx |section header table的index值，索引至section name string table entry。如果檔案沒有section name string table，則此欄的值為SHN_UNDEF。 ### ELF Identification 在 header 資料結構中，e_ident欄位用來判斷檔案是否為ELF格式。 ##### 表 e_ident[] 索引值定義 |Name | Value | 說明| | -------- | -------- | -------- | EI_MAG0 |0 |ELF 識別字元 EI_MAG1 |1 |ELF 識別字元 EI_MAG2 |2 |ELF 識別字元 EI_MAG3 |3 |ELF 識別字元 EI_CLASS|4 |檔案類別 (class) EI_DATA |5 |資料編碼方式 (Data encoding) EI_VERSION | 6 |檔案版本 EI_PAD |7 |padding bytes 的開頭 ##### EI_CLASS |Name |Value |Meaning | -------- | -------- | -------- | ELFCLASSNONE |0 |Invalid class ELFCLASS32 |1 |32-bit objects ELFCLASS64 |2 |64-bit objects ##### EI_DATA Name |Value |Meaning | -------- | -------- | -------- | ELFDATANONE |0 |Invalid data encoding ELFDATA2LSB |1 |LSB ELFDATA2MSB |2 |MSB - elf.c 所設定default ```clike= static const char elf_hdr_default[] = { /* 00 */ 0x7f, 0x45, 0x4c, 0x46, /* magic */ 0x02, /* 64-bit */ 0x01, /* little-endian */ 0x01, /* original version of ELF */ 0x00, /* System V */ /* 08 */ 0x00, /* ABI Version */ 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, /* Unused */ ... ``` ##### $ readelf -h tests/mul.a ``` ELF Header: Magic: 7f 45 4c 46 02 01 01 00 00 00 00 00 00 00 00 00 Class: ELF64 Data: 2's complement, little endian Version: 1 (current) OS/ABI: UNIX - System V ABI Version: 0 Type: EXEC (Executable file) Machine: None Version: 0x1 Entry point address: 0x0 Start of program headers: 0 (bytes into file) Start of section headers: 0 (bytes into file) Flags: 0x0 Size of this header: 52 (bytes) Size of program headers: 56 (bytes) Number of program headers: 3 Size of section headers: 0 (bytes) Number of section headers: 0 Section header string table index: 0 ``` ### Program header table 由 "execution view" 的角度來看程式（即 process），所謂的節區（section）已經被進化成區段（segment）的觀念了。 廣義來說，section 可被分為以下 3 種 segment： 1. Text segment - 指存放唯讀（read-only）程式碼與資料的所有 section 。 2. Data segment - 指存放可寫（writable data）程式碼與資料的所有 section。 3. BSS segment - 即 .bss section。 重要的觀念： * Program header table 是程式要能執行的重要資訊，program header table 紀錄 ELF image 裡的 'segment' 分佈。 * 對 dynamic loader/linker 來說，ELF 的 'section' 是通透性的（transparent），也就是在整個載入的過程裡，dynamic loader/linker 並不會知道他所載入的 'segment' 與實際的 section 有何關係。整個載入過程只讀取 program header table 所紀錄的 'segment'。 * 也就是說，section header table 在此時期是用不到的，就算沒有 section header table 也不影響程式載入與執行。 ##### program header struct ``` struct __attribute__((__packed__)) _elf64_prog_hdr_entry { uint32_t p_type; // 分區類型 uint32_t p_flags; // 分區旗標 uint64_t p_offset; // 分區位址 (在目的檔中) uint64_t p_vaddr; // 分區的虛擬記憶體位址 uint64_t p_paddr; // 分區的實體記憶體位址 uint64_t p_filesz; // 分區在檔案中的大小 uint64_t p_memsz; // 分區在記憶體中的大小 uint64_t p_align; // 分區的對齊資訊 }; ``` ## 允許使用者輸入參數 參考 [st9007a 的共筆](https://hackmd.io/s/Hkf6pkPAb)，將參數放在 `#0` 的位置， 由於程式執行到 `driver.c` 的 `vm_run(...)` 時若是要取得 `#0` 的值則會透過 `vm_get_op_value(...)` 去存取 `vm_env` 內的 `temps[0]` ，因此新增一個函數來設定 `temps` 的值 ```clike= void vm_set_temp_value(vm_env *env, int pos, int val) { vm_value temp_v = {.type = INT}; temp_v.value.vint = val; env->temps[pos] = temp_v; } ``` 在 `driver.c` 內參數處理的部份加上 `temp0_val` 紀錄使用者輸入的值 ```clike= int temp0_val = 0; ... else if (!strcmp(argv[i], "--input")) { if (!argv[i + 1]) FATAL(-1, "--input need an integer argument, see -h\n"); temp0_val = atoi(argv[++i]); } ``` 在 `driver.c` 內初始化 `env` 時順便設定 `temp[0]` 的值為 `temp0_val` ```clike= vm_env *env = vm_new(); vm_set_temp_value(env, 0, temp0_val); ``` 最後在 `Makefile` 內新增 Fibonacci 相關的操作 ```clike= TEMP0 ?= 1 IN_FILE ?= ./tests/fib.s fib: $(EXEC) @./$(EXEC) --input $(TEMP0) $(IN_FILE) ``` ## 實作 Fibonacci 數列 ### Iterative 參考 C 語言版本 ```clike= fib_iterative (int n) { int f0 = 0; int f1 = 1; int sum = 0; for (int i = 0; i <= n; i++) { sum = f1 + f0; f0 = f1; f1 = sum; } return sum; } ``` 實做此 vm 的 assembly 版本 ```clike= ; #0 = 0, then print 0 xor #0 $0 #1 jz #1 #15 sub #0 $1 #0 ; f0 = 0, f1 = 1, i = 0 or $0 $0 #1 or $1 $0 #2 or $0 $0 #4 ; iteration add #1 #2 #3 or $0 #2 #1 or $0 #3 #2 add #4 $1 #4 xor #4 #0 #5 jz #5 #13 jgt #0 #6 ; print result print #3 halt ; print result if input = 0 print $0 halt ``` ## 支援 Label 功能 新增一個 struct 結構來對應 Label ```clike= typedef struct { char *labels[SYMBOL_TABLE_MAX_SIZE]; int addresses[SYMBOL_TABLE_MAX_SIZE]; int count; } vm_symbol_table; ``` 以及新增以下 function 使 `.s` 檔輸入程式後可以讓 label 對應到相對的 address ，詳細見 [Github](https://github.com/TsengWen/full-stack-hello/commit/3457ff1e43e4d348bcd5e23b78df41f9c0c6bbf9) ```clike= void insert_symtab(vm_env *env, char *label, int address) { assert(env->symtab.count < SYMBOL_TABLE_MAX_SIZE); for (int i = 0; i < env->symtab.count; i++) { assert(strcmp(label, env->symtab.labels[i]) != 0); } env->symtab.labels[env->symtab.count] = strdup(label); env->symtab.addresses[env->symtab.count] = address; env->symtab.count++; } int search_symtab(vm_env *env, char *label) { for (int i = 0; i < env->symtab.count; i++) { if (!strcmp(env->symtab.labels[i], label) != 0) return env->symtab.addresses[i]; } return -1; } void set_addresses(vm_env *env) { vm_inst *inst = NULL; for (int i = 0; (inst = vm_get_inst_by_address(env, i)) != NULL; i++) { if (inst->op1.type == LABEL) { int new_addr = search_symtab(env, inst->op1.value.label); assert(new_addr != -1); inst->op1.value.id = new_addr; } if (inst->op2.type == LABEL) { int new_addr = search_symtab(env, inst->op2.value.label); assert(new_addr != -1); inst->op2.value.id = new_addr; } } } ``` 測試案例 ```clike= call .test print "fail" halt test print "call successful" print "finish" halt ``` 結果 ``` call successful finish ``` ## 參考資料 - [Tool Interface Standard (TIS) Executable and Linking Format (ELF) Specification Version 1.2](http://refspecs.linuxbase.org/elf/elf.pdf) - [目的檔格式 (ELF) - 教科書：系統程式](http://sp1.wikidot.com/elfobjfile) - [Jollen 網路學院 :: Program Loading 教學專欄](http://www.jollen.org/EmbeddedLinux/Program_Loading.html) - [st9007a 的共筆](https://hackmd.io/s/Hkf6pkPAb)