Simulator Lab

ICS Lab5: Y86-64 Simulator

在Lab5中，我们要实现一个Y86-64 Simulator来模拟执行y86二进制代码的硬件行为。

y86sim.c程序读进一个y86 instruction文件，根据y86指令结构来parse二进制代码。分析并确定指令后，该程序修改y86处理器状态。

Skeleton Code

开始coding之前先认真看一下skeleton code的结构：

关键是y64sim_t结构，用了4个变量分别表示y86处理器状态：PC, 寄存器，内存和CC，其中寄存器和内存各自用一块连续空间的数组表示，通过register specifer和内存地址作为数组index访问相应的寄存器和内存地址。

1
2
3
4
5
6
7
8
9
10
11
typedef struct mem {
    int len;
    byte_t *data;
} mem_t;

typedef struct y64sim {
    long_t pc;
    mem_t *r;
    mem_t *m;
    cc_t cc;
} y64sim_t;

Implementation (Code Alert!)

这个lab的关键在于实现nexti函数，这个函数的输入是当前的y86 image（包括PC， 寄存器，内存和CC）。

首先第一步是parse指令，根据instruction code来获取寄存器和立即数。获取到的寄存器分别存在rA和rB里面，立即数存在valC里面。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
byte_t codefun = 0; /* 1 byte */
itype_t icode;
alu_t ifun;
long_t next_pc = sim->pc;

/* get code and function （1 byte) */
if (!get_byte_val(sim->m, next_pc, &codefun))
{
    err_print("PC = 0x%lx, Invalid instruction address", sim->pc);
    return STAT_ADR;
}
/* get the instruction code */
icode = GET_ICODE(codefun);
/* get the ALU code */
ifun = GET_FUN(codefun);
next_pc++;

/* get registers if needed (1 byte) */
reg_t rA = {0}, rB = {0};
if (get_register_needed(icode))
{
    /* get the register specifier */
    if (!get_byte_val(sim->m, next_pc, &codefun))
    {
        err_print("PC = 0x%lx, Invalid instruction address", sim->pc);
        return STAT_ADR;
    }
    rA = reg_table[GET_REGA(codefun)];
    rB = reg_table[GET_REGB(codefun)];
    next_pc++;
}

/* get immediate if needed (8 bytes) */
long_t valC = 0;
if (get_immediate_needed(icode))
{
    if (!get_long_val(sim->m, next_pc, &valC))
    {
        err_print("PC = 0x%lx, Invalid instruction address", sim->pc);
        return STAT_ADR;
    }
    next_pc += 8;
}

这里我用了两个helper function: get_register_needed和get_immediate_needed来根据instruction code确定是否需要获取register specifier和8位的immediate，参考下图y86指令集：

Y86-64指令集

然后就是补全switch语句根据指令前4 bits的instruction code来分别执行相应的操作，需要注意以下几类指令：

  1. OPq: 根据function code确定具体需要执行的ALU操作。需要实现compute_alu执行ALU操作，compute_cc根据ALU操作结果设置CC。

    如何判断ADD和SUB操作有无overflow?

    如果两个long_t类型数相加，得到的和的符号与原本两个数符号相反，则overflow：

    1
    ovf = ((argA ^ val) & (argB ^ val)) >> 63;

    减法可以转化成第一个数加第二个数的相反数，与加法overflow判断方式相同。

  2. jXX和cmovXX: 需要实现cond_doit，先根据function code和当前的cc来判断能否执行。

    如何判断Less和Greater?

    两个数相减，如果是负数且没有overflow，或是正数但overflow，那么说明第一个数Less than第二个数：

    1
    2
    case C_L:
            return (sf ^ of);

    Greater就是Less反过来并加上!zero。

完整的switch代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
/* execute the instruction*/
switch (icode)
{
    case I_HALT: /* 0:0 */
        return STAT_HLT;
        break;
    case I_NOP: /* 1:0 */
        break;
    case I_RRMOVQ: /* 2:x regA:regB */
        if (cond_doit(sim->cc, ifun))
        {
            set_reg_val(sim->r, rB.id, get_reg_val(sim->r, rA.id));
        }
        break;
    case I_IRMOVQ: /* 3:0 F:regB imm */
        set_reg_val(sim->r, rB.id, valC);
        break;
    case I_RMMOVQ: /* 4:0 regA:regB imm */
        if (!set_long_val(sim->m, get_reg_val(sim->r, rB.id) + valC, get_reg_val(sim->r, rA.id)))
        {
            err_print("PC = 0x%lx, Invalid data address 0x%lx", sim->pc, get_reg_val(sim->r, rB.id) + valC);
            return STAT_ADR;
        }
        break;
    case I_MRMOVQ: /* 5:0 regB:regA imm */
        long_t valM;
        if (!get_long_val(sim->m, get_reg_val(sim->r, rB.id) + valC, &valM))
        {
            err_print("PC = 0x%lx, Invalid data address 0x%lx", sim->pc, get_reg_val(sim->r, rB.id) + valC);
            return STAT_ADR;
        }
        set_reg_val(sim->r, rA.id, valM);
        break;
    case I_ALU: /* 6:x regA:regB */
        long_t alu_val;
        /* do the ALU operation and set condition codes */
        alu_val = compute_alu(ifun, get_reg_val(sim->r, rA.id), get_reg_val(sim->r, rB.id));
        sim->cc = compute_cc(ifun, get_reg_val(sim->r, rA.id), get_reg_val(sim->r, rB.id), alu_val);
        /* save the result to the destination register */
        set_reg_val(sim->r, rB.id, alu_val);
        break;
    case I_JMP: /* 7:x imm */
        if (cond_doit(sim->cc, ifun)) {
            next_pc = valC;
        }
        break;
    case I_CALL:  /* 8:x imm */
        /*
         * Push address of next instruction onto stack;
         * Start executing instructions at Dest;
         */
        set_reg_val(sim->r, REG_RSP, get_reg_val(sim->r, REG_RSP) - 8);
        if (!set_long_val(sim->m, get_reg_val(sim->r, REG_RSP), next_pc))
        {
            err_print("PC = 0x%lx, Invalid stack address 0x%lx", sim->pc, get_reg_val(sim->r, REG_RSP));
            set_reg_val(sim->r, REG_RSP, get_reg_val(sim->r, REG_RSP) + 8);
            return STAT_ADR;
        }
        next_pc = valC;
        break;
    case I_RET:   /* 9:0 */
        /* 
         * Pop value from stack;
         * Use as address for next instruction; 
         */
        if (!get_long_val(sim->m, get_reg_val(sim->r, REG_RSP), &next_pc)) {
            err_print("PC = 0x%lx, Invalid stack address 0x%lx", sim->pc, get_reg_val(sim->r, REG_RSP));
            return STAT_ADR;
        }
        set_reg_val(sim->r, REG_RSP, get_reg_val(sim->r, REG_RSP) + 8);
        break;
    case I_PUSHQ: /* A:0 regA:F */
        /* 
         * Decrement %rsp by 8;
         * Store word from rA to memory at %rsp;
         * Like x86-64 (pushq %rsp -> save old %rsp);
         */
        long_t rA_val = get_reg_val(sim->r, rA.id);
        set_reg_val(sim->r, REG_RSP, get_reg_val(sim->r, REG_RSP) - 8);
        if (!set_long_val(sim->m, get_reg_val(sim->r, REG_RSP), rA_val))
        {
            err_print("PC = 0x%lx, Invalid stack address 0x%lx", sim->pc, get_reg_val(sim->r, REG_RSP));
            set_reg_val(sim->r, REG_RSP, get_reg_val(sim->r, REG_RSP) + 8);
            return STAT_ADR;
        }
        break;
    case I_POPQ: /* B:0 regA:F */
        /* 
         * Read word from memory at %rsp;
         * Save in rA;
         * Increment %rsp by 8;
         * Like x86-64 (popq %rsp -> movq (%rsp) %rsp);
         */
        long_t val_stack;
        if (!get_long_val(sim->m, get_reg_val(sim->r, REG_RSP), &val_stack)) {
            err_print("PC = 0x%lx, Invalid stack address 0x%lx", sim->pc, get_reg_val(sim->r, REG_RSP));
            return STAT_ADR;
        }
        set_reg_val(sim->r, rA.id, val_stack);
        if (rA.id != REG_RSP)
        {
            set_reg_val(sim->r, REG_RSP, get_reg_val(sim->r, REG_RSP) + 8);
        }
        break;
    default:
        err_print("PC = 0x%lx, Invalid instruction %.2x", sim->pc, codefun);
        return STAT_INS;
}

sim->pc = next_pc;

这个lab的error handling容易出错！：

  1. status code的返回，只要是invalid address的错误，无论是invalid instruction address, invalid data address, invalid stack address，都是返回STAT_ADR

  2. pushq和call都是先decrement rsp，然后尝试写入栈中。如果写入失败应该重新increment rsp到原来的值，如果忘记这一步的话test会fail:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    [ Testing instruction: call ]
    3a4
    > %rsp: 0x0000000000000000      0xfffffffffffffff8
    [ Result: Fail ]

    [ Testing instruction: pushq ]
    3a4
    > %rsp: 0x0000000000000000      0xfffffffffffffff8
    [ Result: Fail ]

    [ Testing application: prog10 ]
    4a5
    > %rsp: 0x0000000000000000      0xfffffffffffffff8
    [ Result: Fail ]

Test

To test and evaluate your Simulator:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
./yat -c <name> [max_steps] # get the correct status of registers and memory
e.g., ./yat -c prog9 4


./yat -s <ins_name> [max_steps] # test .bin file of single instruction in y64-ins-bin directory
e.g., ./yat –s rrmovl


./yat -S # test all instructions 1


./yat -a <app_name> [max_steps] # test single application in y64-app-bin directory.
e.g., ./yat –a asum 1


./yat -A # test all applications 1


./yat -F # test all instructions and applications, and print out the final score.


./yat -h # print this message

All tests pass!🤗

总结

这个Simulator Lab就是在编写底层硬件执行上层y86指令的行为，很机械很有意思！

完成这个Lab后，你就能理解为什么程序就是一台状态机！这个状态机每次读取一条指令，然后调动底层硬件更新处理器的状态，然后根据status code决定接下来是继续执行，halt，还是出错。

ICS > Lab
#CSAPP #Y86 #Simulator
Simulator Lab
http://oooscar8.github.io/2025/02/24/Simulator/
作者
Alex Sun
发布于
2025年2月24日
许可协议