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)