Try   HackMD

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

解析程式

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →

  • 主要由 driver.c 控制整個程式流程以及解析使用者輸入的參數。
    • as：處理輸入.s檔，產生對應的 objeck file ,以及設定 vm_env
    • vm：虛擬機器，內涵虛擬機器的架構,運作
    • opcode：自訂指令集,以及相關實作,實作主要用於虛擬機器
    • elf：提供產生 object file 相關的函式
      Image Not Showing Possible Reasons
      • The image file may be corrupted
      • The server hosting the image is unavailable
      • The image path is incorrect
      • The image format is not supported
      Learn More → 






























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 來得知
    Image Not Showing Possible Reasons
    • The image file may be corrupted
    • The server hosting the image is unavailable
    • The image path is incorrect
    • The image format is not supported
    Learn More →

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 格式可以分為兩種不同觀點

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →

  • 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











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 的共筆，將參數放在 #0 的位置，
由於程式執行到 driver.c 的 vm_run(...) 時若是要取得 #0 的值則會透過 vm_get_op_value(...) 去存取 vm_env 內的 temps[0] ，因此新增一個函數來設定 temps 的值







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 紀錄使用者輸入的值










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



vm_env *env = vm_new();
    vm_set_temp_value(env, 0, temp0_val);

最後在 Makefile 內新增 Fibonacci 相關的操作






TEMP0 ?= 1
IN_FILE ?= ./tests/fib.s

fib: $(EXEC)
	@./$(EXEC) --input $(TEMP0) $(IN_FILE)

實作 Fibonacci 數列

Iterative

參考 C 語言版本













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 版本





























; #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






typedef struct {
    char *labels[SYMBOL_TABLE_MAX_SIZE];
    int addresses[SYMBOL_TABLE_MAX_SIZE];
    int count;
} vm_symbol_table;

以及新增以下 function 使 .s 檔輸入程式後可以讓 label 對應到相對的 address ，詳細見 Github






































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;
        }
    }
}

測試案例








call .test
print "fail"
halt

test print "call successful"
print "finish"
halt

結果

call successful
finish

參考資料

Last changed by 
 
TsengWen
0
390
Published on HackMD