ICS PA 1

`init.sh`

我们在 PA0 中使用下面的指令初始化了一些子项目：

$ bash init.sh nemu
$ bash init.sh abstract-machine

在 PA1 中也使用了类似的指令初始化了一个子项目，用于检查红白机模拟器的按键：

$ bash init.sh am-kernels

我们观察 init.sh 文件：

#!/bin/bash

version=ics2021

function init() {
  if [ -d $1 ]; then
    echo "$1 is already initialized, skipping..."
    return
  fi

  while [ ! -d $1 ]; do
    git clone -b $version https://github.com/NJU-ProjectN/$1.git
  done
  log="$1 `cd $1 && git log --oneline --no-abbrev-commit -n1`"$'\n'
  rm -rf $1/.git

  git add -A $1
  git commit -am "$1 $version initialized"$'\n\n'"$log"

  if [ $2 ] ; then
    sed -i -e "/^export $2=.*/d" ~/.bashrc
    echo "export $2=`readlink -e $1`" >> ~/.bashrc

    echo "By default this script will add environment variables into ~/.bashrc."
    echo "After that, please run 'source ~/.bashrc' to let these variables take effect."
    echo "If you use shell other than bash, please add these environment variables manually."
  fi
}

function init_no_git() {
  if [ -d $1 ]; then
    echo "$1 is already initialized, skipping..."
    return
  fi

  while [ ! -d $1 ]; do
    git clone -b $version https://github.com/NJU-ProjectN/$1.git
  done
  log="$1 `cd $1 && git log --oneline --no-abbrev-commit -n1`"$'\n'

  sed -i -e "/^\/$1/d" .gitignore
  echo "/$1" >> .gitignore

  git add -A .gitignore
  git commit --no-verify --allow-empty -am "$1 $version initialized without tracing"$'\n\n'"$log"
}

case $1 in
  nemu)
    init nemu NEMU_HOME
    ;;
  abstract-machine)
    init abstract-machine AM_HOME
    init_no_git fceux-am
    ;;
  am-kernels)
    init_no_git am-kernels
    ;;
  nanos-lite)
    init nanos-lite
    ;;
  navy-apps)
    init navy-apps NAVY_HOME
    ;;
  *)
    echo "Invalid input..."
    exit
    ;;
esac

先使用 ggvG 全选，然后输入 "+y，其中 "+ 为系统剪贴板，y 为复制

似乎需要安装 vim-gui-common

以 $ bash init.sh am-kernels 为例，am-kernels 即为 $1，调用 init_no_git am-kernels。

init_no_git am-kernels 中的 -d $1 表示：若 $1 为目录则为真。当我们第一次使用该指令时，我们会从 github 中 clone 子项目，并留下 git 记录。

`make` 编译加速

多线程

首先通过 lscpu 命令来查询系统中有多少个 CPU，然后在运行 make 的时候添加一个 -j? 的参数，其中 ? 为查询到的 CPU 数量。

然而我查询到只有一个 CPU 🤣

为了查看编译加速的效果，可以在编译的命令前面添加 time 命令，它将会对紧跟在其后的命令的执行时间进行统计。

ccache

ccache 是一个 compiler cache。安装完成后 RTFM，先查看 gcc 命令的所在路径：

$ which gcc
/usr/bin/gcc

修改 ~/.bashrc，在最后一行加入 export PATH=/usr/lib/ccache:$PATH，然后使用 $ source ~/.bashrc 指令更新 PATH 环境变量，此时再查看 gcc 命令的所在路径：

$ which gcc
/usr/lib/ccache/gcc

现在就可以来体验 ccache 的效果了。清除编译结果进行测试：

$ time make ARCH=native mainargs=k run
# Building amtest-run [native]
+ CC src/tests/hello.c
+ CC src/tests/intr.c
+ CC src/tests/video.c
+ CC src/tests/vm.c
+ CC src/tests/rtc.c
+ AS src/tests/audio/audio-data.S
+ CC src/tests/devscan.c
+ CC src/tests/mp.c
+ CC src/tests/audio.c
+ CC src/tests/keyboard.c
+ CC src/main.c
# Building am-archive [native]
# Building klib-archive [native]
# Creating image [native]
+ LD -> build/amtest-native
/home/vgalaxy/ics2021/am-kernels/tests/am-tests/build/amtest-native
Try to press any key (uart or keyboard)...
Exit (0)

real  0m6.539s
user  0m3.446s
sys  0m0.110s

$ make clean
rm -rf Makefile.html /home/vgalaxy/ics2021/am-kernels/tests/am-tests/build/

$ time make ARCH=native mainargs=k run
# Building amtest-run [native]
+ CC src/tests/hello.c
+ CC src/tests/intr.c
+ CC src/tests/video.c
+ CC src/tests/vm.c
+ CC src/tests/rtc.c
+ AS src/tests/audio/audio-data.S
+ CC src/tests/devscan.c
+ CC src/tests/mp.c
+ CC src/tests/audio.c
+ CC src/tests/keyboard.c
+ CC src/main.c
# Building am-archive [native]
# Building klib-archive [native]
# Creating image [native]
+ LD -> build/amtest-native
/home/vgalaxy/ics2021/am-kernels/tests/am-tests/build/amtest-native
Try to press any key (uart or keyboard)...
Exit (0)

real  0m2.636s
user  0m1.354s
sys  0m0.043s

可以发现第二次编译的速度有了非常明显的提升。

ISA

ISA 是软件和硬件之间的接口。

ISA 的本质是一套规范。

NEMU 程序本身是 x86 的 (准确来说是 x64)，不会随着你选择的 ISA 而变化，变化的只是在 NEMU 中模拟的计算机。

在 nemu/ 文件夹执行 $ make menuconfig 这一步时，NEMU 的框架代码会把 riscv32 作为默认的 ISA，因而我们也选择 riscv32 吧。

生存手册：

The RISC-V Instruction Set Manual (Volume I, Volume II)
ABI for riscv

计算机是个状态机

在每个时钟周期到来的时候，计算机根据当前时序逻辑部件（存储器，计数器，寄存器）的状态，在组合逻辑部件（加法器）的作用下，计算出并转移到下一时钟周期的新状态。

Q: 计算机可以没有寄存器吗？如果可以，这会对硬件提供的编程模型有什么影响呢？

A: 寄存器是计算机中最基本的硬件组件之一，用于存储和处理数据。在没有寄存器的情况下，计算机无法正常工作。因此，没有寄存器的计算机是不存在的。

如果我们将问题修改为：如果没有通用寄存器，计算机还可以工作吗？那么答案是肯定的。事实上，早期的计算机并没有像现代计算机一样具有通用寄存器，而是使用专用寄存器和其他类似的组件来完成任务。例如，早期的计算机使用特定的寄存器来存储指令指针、堆栈指针、程序计数器等重要的信息。

没有通用寄存器的计算机可能会使用其他方式来处理数据，例如在内存中存储数据并使用内存地址来进行操作。这种方式可能会导致较低的性能和更复杂的编程模型，因为程序员需要手动管理内存地址，并且无法像使用寄存器那样轻松地存储和操作数据。

因此，没有通用寄存器的计算机会对硬件提供的编程模型产生重大影响，需要更复杂的程序设计和更多的手动内存管理。

程序是个状态机

程序在计算机上运行的微观视角：程序是个状态机

考虑下面一段计算 1+2+...+100 的指令序列：

// PC: instruction    | // label: statement
0: mov  r1, 0         |  pc0: r1 = 0;
1: mov  r2, 0         |  pc1: r2 = 0;
2: addi r2, r2, 1     |  pc2: r2 = r2 + 1;
3: add  r1, r1, r2    |  pc3: r1 = r1 + r2;
4: blt  r2, 100, 2    |  pc4: if (r2 < 100) goto pc2;   // branch if less than
5: jmp 5              |  pc5: goto pc5;

用一个三元组 (PC, r1, r2) 就表示程序的状态，PC 表示待执行的下一条指令。初始状态是 (0, x, x)，此处的 x 表示未初始化：

(0, x, x) -> (1, 0, x) -> (2, 0, 0) -> (3, 0, 1) -> (4, 1, 1) -> (3, 1, 2) -> (4, 3, 2) -> ... -> (3, 4950, 100) -> (4, 5050, 100) -> (5, 5050, 100)

一个是以代码 (或指令序列) 为表现形式的静态视角
另一个是以状态机的状态转移为运行效果的动态视角

准备第一个客户程序

框架代码已经实现了 TRM (Turing Machine)。

为了支持不同的 ISA，框架代码把 NEMU 分成两部分：ISA 无关的基本框架和 ISA 相关的具体实现。NEMU 把 ISA 相关的代码专门放在 nemu/src/isa/ 目录下，并通过 nemu/include/isa.h 提供 ISA 相关 API 的声明。这样以后，nemu/src/isa/ 之外的其它代码就展示了 NEMU 的基本框架。

在 NEMU 中模拟的计算机称为“客户计算机”，在 NEMU 中运行的程序称为“客户程序”。

NEMU 主要由 4 个模块构成：

monitor
cpu
memory
device

上文提到，kconfig 生成了一些可以被包含到 C 代码中的宏定义 (nemu/include/generated/autoconf.h)，这些宏的名称都是形如 CONFIG_xxx 的形式。

为此，在 nemu/include/macro.h 中定义了一些专门用来对宏进行测试的宏，如 IFDEF 和 MUXDEF。

看到定义的宏，人都傻了 🤣

另外，三个对调试有用的宏在 nemu/include/debug.h 中定义：

Log() 是 printf() 的升级版，专门用来输出调试信息，同时还会输出使用 Log() 所在的源文件、行号和函数。当输出的调试信息过多的时候，可以很方便地定位到代码中的相关位置
Assert() 是 assert() 的升级版，当测试条件为假时，在 assertion fail 之前可以输出一些信息
panic() 用于输出信息并结束程序，相当于无条件的 assertion fail

客户程序一开始并不存在于客户计算机中。我们需要将客户程序读入到客户计算机中，这件事是 monitor 来负责的。于是 NEMU 在开始运行的时候，nemu/src/nemu-main.c 中的 main 函数：

#include <common.h>

void init_monitor(int, char *[]);
void am_init_monitor();
void engine_start();
int is_exit_status_bad();

int main(int argc, char *argv[]) {
  /* Initialize the monitor. */
#ifdef CONFIG_TARGET_AM
  am_init_monitor();
#else
  init_monitor(argc, argv);
#endif

  /* Start engine. */
  engine_start();

  return is_exit_status_bad();
}

首先会调用 init_monitor() 函数 (在 nemu/src/monitor/monitor.c 中定义) 来进行一些和 monitor 相关的初始化工作。

还有一个 am_init_monitor 函数，定义在 nemu/src/monitor/monitor.c，相较于 init_monitor 函数简化了初始化逻辑，不知道什么用 🤣：
void am_init_monitor() {
       init_rand();
       init_mem();
       init_isa();
       load_img();
       IFDEF(CONFIG_DEVICE, init_device());
       welcome();
}
通过调试反汇编可知 main 函数实际调用的是 init_monitor 函数，因为 #ifdef CONFIG_TARGET_AM 为假，编译时就跳过了 am_init_monitor 函数，注意 nemu/src/monitor/monitor.c 的第 22 行。

init_monitor() 函数里面全部都是函数调用，下面按顺序分析：

parse_args

nemu/src/monitor/monitor.c

static int parse_args(int argc, char *argv[]) {
  const struct option table[] = {
    {"batch"    , no_argument      , NULL, 'b'},
    {"log"      , required_argument, NULL, 'l'},
    {"diff"     , required_argument, NULL, 'd'},
    {"port"     , required_argument, NULL, 'p'},
    {"help"     , no_argument      , NULL, 'h'},
    {0          , 0                , NULL,  0 },
  };
  int o;
  while ( (o = getopt_long(argc, argv, "-bhl:d:p:", table, NULL)) != -1) {
    switch (o) {
      case 'b': sdb_set_batch_mode(); break;
      case 'p': sscanf(optarg, "%d", &difftest_port); break;
      case 'l': log_file = optarg; break;
      case 'd': diff_so_file = optarg; break;
      case 1: img_file = optarg; return optind - 1;
      default:
        printf("Usage: %s [OPTION...] IMAGE [args]\n\n", argv[0]);
        printf("\t-b,--batch              run with batch mode\n");
        printf("\t-l,--log=FILE           output log to FILE\n");
        printf("\t-d,--diff=REF_SO        run DiffTest with reference REF_SO\n");
        printf("\t-p,--port=PORT          run DiffTest with port PORT\n");
        printf("\n");
        exit(0);
    }
  }
  return 0;
}

其中调用了 getopt_long 函数，通过查阅 man 3 getopt_long 可知，需要包含 getopt.h 头文件。

man 3 表示查阅的是库函数

getopt_long 函数签名为：

int getopt_long(int argc, char * const argv[],
          const char *optstring,
          const struct option *longopts, int *longindex);

其中 option 结构体为：

struct option {
   const char *name;
   int         has_arg;
   int        *flag;
   int         val;
};

init_rand

nemu/src/utils/rand.c

void init_rand() {
  srand(MUXDEF(CONFIG_TARGET_AM, 0, time(0)));
}

init_log

nemu/src/utils/log.c

void init_log(const char *log_file) {
  if (log_file == NULL) return;
  log_fp = fopen(log_file, "w");
  Assert(log_fp, "Can not open '%s'", log_file);
}

init_mem

nemu/src/memory/paddr.c

nemu/include/memory/paddr.h

内存通过在 nemu/src/memory/paddr.c 中定义的大数组 pmem 来模拟。在客户程序运行的过程中，总是使用 vaddr_read() 和 vaddr_write() (在 nemu/src/memory/vaddr.c 中定义) 来访问模拟的内存，vaddr 和 paddr 分别代表虚拟地址和物理地址。

init_isa

nemu/src/isa/riscv32/init.c

static void restart() {
  /* Set the initial program counter. */
  cpu.pc = RESET_VECTOR;

  /* The zero register is always 0. */
  cpu.gpr[0]._32 = 0;
}

void init_isa() {
  /* Load built-in image. */
  memcpy(guest_to_host(RESET_VECTOR), img, sizeof(img));

  /* Initialize this virtual computer system. */
  restart();
}

init_isa() 的有两项任务要做：

1、第一项工作就是将一个内置的客户程序读入到内存中。

在真实的计算机系统中，计算机启动后首先会把控制权交给 BIOS，BIOS 经过一系列初始化工作之后，再从磁盘中将有意义的程序读入内存中执行。

通过 sudo dmesg 指令观察。

我们在 PA 中做了简化：采取约定的方式让 CPU 直接从约定的内存位置开始执行。

内置客户程序就放在 nemu/src/isa/riscv32/init.c 中：

// this is not consistent with uint8_t
// but it is ok since we do not access the array directly
static const uint32_t img [] = {
  0x800002b7,  // lui t0,0x80000
  0x0002a023,  // sw  zero,0(t0)
  0x0002a503,  // lw  a0,0(t0)
  0x0000006b,  // nemu_trap
};

使用一个 uint8_t 类型的数组来对内存进行模拟。NEMU 默认为客户计算机提供 128MB 的物理内存，见 nemu/src/memory/paddr.c 中定义的 pmem：

#if   defined(CONFIG_TARGET_AM)
static uint8_t *pmem = NULL;
#else
static uint8_t pmem[CONFIG_MSIZE] PG_ALIGN = {};
#endif

在 nemu/include/generated/autoconf.h 中定义了 CONFIG_MSIZE：

#define CONFIG_MSIZE 0x8000000

我们让 monitor 直接把客户程序读入到一个固定的内存位置 RESET_VECTOR。

guest_to_host 函数定义在 nemu/src/memory/paddr.c 中：

uint8_t* guest_to_host(paddr_t paddr) { return pmem + paddr - CONFIG_MBASE; }

其中的类型 paddr_t 定义在 nemu/include/common.h 中：

#if CONFIG_MBASE + CONFIG_MSIZE > 0x100000000ul
#define PMEM64 1
#endif

typedef MUXDEF(PMEM64, uint64_t, uint32_t) paddr_t;

mips32 和 riscv32 的物理地址均从 0x80000000 开始。因此对于 mips32 和 riscv32，其 CONFIG_MBASE 将会被定义成 0x80000000。将来 CPU 访问内存时，guest_to_host 函数会将 CPU 将要访问的内存地址映射到 pmem 中的相应偏移位置。

这种机制被称为地址映射。

RESET_VECTOR 的值在 nemu/include/memory/paddr.h 中定义：

#define RESET_VECTOR (CONFIG_MBASE + CONFIG_PC_RESET_OFFSET)

在 nemu/include/generated/autoconf.h 中：

#define CONFIG_MBASE 0x80000000
#define CONFIG_PC_RESET_OFFSET 0x0

注意 CONFIG_MBASE 和 CONFIG_MSIZE 并不相同

2、init_isa() 的第二项任务是初始化寄存器，这是通过 restart() 函数来实现的。

寄存器结构体定义在 nemu/src/isa/riscv32/include/isa-def.h 中：

typedef struct {
  struct {
    rtlreg_t _32;
  } gpr[32];

  vaddr_t pc;
} riscv32_CPU_state;

其中类型 rtlreg_t 和 vaddr_t 定义在 nemu/include/common.h 中：

typedef MUXDEF(CONFIG_ISA64, uint64_t, uint32_t) word_t;

typedef word_t rtlreg_t;
typedef word_t vaddr_t;

在 nemu/src/cpu/cpu-exec.c 中定义一个全局变量 cpu

CPU_state cpu = {};

在 include/isa.h 中给类型 riscv32_CPU_state 一个别名 CPU_state，并使用 extern 关键词引用了在 nemu/src/cpu/cpu-exec.c 中定义的全局变量：

// The macro `__GUEST_ISA__` is defined in $(CFLAGS).
// It will be expanded as "x86" or "mips32" ...
typedef concat(__GUEST_ISA__, _CPU_state) CPU_state;

extern CPU_state cpu;

初始化寄存器的一个重要工作就是设置 cpu.pc 的初值，我们需要将它设置成刚才加载客户程序的内存位置。对于 mips32 和 riscv32，它们的 0 号寄存器总是存放 0，因此我们也需要对其进行初始化。

load_img

nemu/src/monitor/monitor.c

static long load_img() {
  if (img_file == NULL) {
    Log("No image is given. Use the default build-in image.");
    return 4096; // built-in image size
  }

  FILE *fp = fopen(img_file, "rb");
  Assert(fp, "Can not open '%s'", img_file);

  fseek(fp, 0, SEEK_END);
  long size = ftell(fp);

  Log("The image is %s, size = %ld", img_file, size);

  fseek(fp, 0, SEEK_SET);
  int ret = fread(guest_to_host(RESET_VECTOR), size, 1, fp);
  assert(ret == 1);

  fclose(fp);
  return size;
}

如果运行 NEMU 的时候没有给出这个参数，NEMU 将会运行内置客户程序。否则将一个有意义的客户程序从镜像文件读入到内存，覆盖刚才的内置客户程序。

剩余的初始化工作

/* Initialize differential testing. */
init_difftest(diff_so_file, img_size, difftest_port);

/* Initialize devices. */
IFDEF(CONFIG_DEVICE, init_device());

/* Initialize the simple debugger. */
init_sdb();

/* Display welcome message. */
welcome();

除了 welcome 函数，其余在后续实验内容中介绍。

运行第一个客户程序

Monitor 的初始化工作结束后，main() 函数会继续调用 engine_start() 函数，定义在 nemu/src/engine/interpreter/init.c 中：

#include <cpu/cpu.h>

void sdb_mainloop();

void engine_start() {
#ifdef CONFIG_TARGET_AM
  cpu_exec(-1);
#else
  /* Receive commands from user. */
  sdb_mainloop();
#endif
}

其中 cpu_exec 定义在 nemu/src/cpu/cpu-exec.c 中，sdb_mainloop 定义在 nemu/src/monitor/sdb/sdb.c 中。我们会执行 sdb_mainloop 函数，即进入简易调试器 (Simple Debugger) 的主循环，并输出 NEMU 的命令提示符：

$ make run
+ LD /home/vgalaxy/ics2021/nemu/build/riscv32-nemu-interpreter
/home/vgalaxy/ics2021/nemu/build/riscv32-nemu-interpreter --log=/home/vgalaxy/ics2021/nemu/build/nemu-log.txt
[src/memory/paddr.c:34 init_mem] physical memory area [0x80000000, 0x88000000]
[src/monitor/monitor.c:34 load_img] No image is given. Use the default build-in image.
[src/monitor/monitor.c:12 welcome] Debug: ON
[src/monitor/monitor.c:13 welcome] If debug mode is on, a log file will be generated to record every instruction NEMU executes. This may lead to a large log file. If it is not necessary, you can turn it off in include/common.h.
[src/monitor/monitor.c:17 welcome] Build time: 14:42:30, Sep 11 2021
Welcome to riscv32-NEMU!
For help, type "help"
(nemu)

下面是 sdb_mainloop 函数的全貌：

void sdb_mainloop() {
  if (is_batch_mode) {
    cmd_c(NULL);
    return;
  }

  for (char *str; (str = rl_gets()) != NULL; ) {
    char *str_end = str + strlen(str);

    /* extract the first token as the command */
    char *cmd = strtok(str, " ");
    if (cmd == NULL) { continue; }

    /* treat the remaining string as the arguments,
     * which may need further parsing
     */
    char *args = cmd + strlen(cmd) + 1;
    if (args >= str_end) {
      args = NULL;
    }

#ifdef CONFIG_DEVICE
    extern void sdl_clear_event_queue();
    sdl_clear_event_queue();
#endif

    int i;
    for (i = 0; i < NR_CMD; i ++) {
      if (strcmp(cmd, cmd_table[i].name) == 0) {
        if (cmd_table[i].handler(args) < 0) { return; }
        break;
      }
    }

    if (i == NR_CMD) { printf("Unknown command '%s'\n", cmd); }
  }
}

is_batch_mode 目前被定义为 false，先跳过，然后通过 rl_gets 函数读取命令和参数，其中调用了 readline 库中的 readline 函数和 add_history 函数，接着将命令与 cmd_table 中的命令一一对比并执行：

static int cmd_c(char *args) {
  cpu_exec(-1);
  return 0;
}


static int cmd_q(char *args) {
  return -1;
}

static struct {
  const char *name;
  const char *description;
  int (*handler) (char *);
} cmd_table [] = {
  { "help", "Display informations about all supported commands", cmd_help },
  { "c", "Continue the execution of the program", cmd_c },
  { "q", "Exit NEMU", cmd_q },

  /* TODO: Add more commands */

};

#define NR_CMD ARRLEN(cmd_table)

在命令提示符后键入 c 后，NEMU 开始进入指令执行的主循环 cpu_exec()：

/* Simulate how the CPU works. */
void cpu_exec(uint64_t n) {
  g_print_step = (n < MAX_INSTR_TO_PRINT);
  switch (nemu_state.state) {
    case NEMU_END: case NEMU_ABORT:
      printf("Program execution has ended. To restart the program, exit NEMU and run again.\n");
      return;
    default: nemu_state.state = NEMU_RUNNING;
  }

  uint64_t timer_start = get_time();

  Decode s;
  for (;n > 0; n --) {
    fetch_decode_exec_updatepc(&s);
    g_nr_guest_instr ++;
    IFDEF(CONFIG_DEBUG, debug_hook(s.pc, s.logbuf));
    if (nemu_state.state != NEMU_RUNNING) break;
    IFDEF(CONFIG_DIFFTEST, difftest_step(s.pc, cpu.pc));
    IFDEF(CONFIG_DEVICE, device_update());
  }

  uint64_t timer_end = get_time();
  g_timer += timer_end - timer_start;

  switch (nemu_state.state) {
    case NEMU_RUNNING: nemu_state.state = NEMU_STOP; break;

    case NEMU_END: case NEMU_ABORT:
      Log("nemu: %s at pc = " FMT_WORD,
          (nemu_state.state == NEMU_ABORT ? ASNI_FMT("ABORT", ASNI_FG_RED) :
           (nemu_state.halt_ret == 0 ? ASNI_FMT("HIT GOOD TRAP", ASNI_FG_GREEN) :
            ASNI_FMT("HIT BAD TRAP", ASNI_FG_RED))),
          nemu_state.halt_pc);
      // fall through
    case NEMU_QUIT:
      monitor_statistic();
  }
}

这里的 nemu_state 定义在 nemu/include/utils.h 中：

enum { NEMU_RUNNING, NEMU_STOP, NEMU_END, NEMU_ABORT, NEMU_QUIT };

typedef struct {
  int state;
  vaddr_t halt_pc;
  uint32_t halt_ret;
} NEMUState;

extern NEMUState nemu_state;

而结构类型 Decode 定义在 nemu/include/cpu/decode.h 中：

typedef struct Decode {
  vaddr_t pc;
  vaddr_t snpc; // static next pc
  vaddr_t dnpc; // dynamic next pc
  void (*EHelper)(struct Decode *);
  Operand dest, src1, src2;
  ISADecodeInfo isa;
  IFDEF(CONFIG_DEBUG, char logbuf[80]);
} Decode;

注意在 cmd_c() 函数中，调用 cpu_exec() 的时候传入了参数 -1，由于参数类型为 uint64_t，-1 被视为最大的无符号整数，考虑到地址空间有限，里面的 for 循环相当于无限循环。

循环中调用 fetch_decode_exec_updatepc 函数，即让 CPU 执行当前 PC 指向的一条指令，然后更新 PC：

static void fetch_decode_exec_updatepc(Decode *s) {
  fetch_decode(s, cpu.pc);
  s->EHelper(s);
  cpu.pc = s->dnpc;
}

fetch_decode 中调用了 isa_fetch_decode 函数，声明在 include/isa.h 中，具体实现在 src/isa/riscv32/instr/decode.c 中。

EHelper 为 Decode 类型中的一个函数指针，与 ISA 相关，具体实现在 src/isa/riscv32/instr 中。

后续实验中会有关于指令执行的详细说明。

此时 NEMU 将会运行上文提到的内置客户程序。NEMU 将不断执行指令，直到遇到以下情况之一，才会退出指令执行的循环：

达到要求的循环次数
客户程序执行了 nemu_trap 指令。这是一条特殊的指令，在 ISA 手册中并不存在，它是为了在 NEMU 中让客户程序指示执行的结束而加入的。为了表示客户程序是否成功结束，nemu_trap 指令还会接收一个表示结束状态的参数。当客户程序执行了这条指令之后，NEMU 将会根据这个结束状态参数来设置 NEMU 的结束状态，并根据不同的状态输出不同的结束信息，主要包括：
- HIT GOOD TRAP - 客户程序正确地结束执行
- HIT BAD TRAP - 客户程序错误地结束执行
- ABORT - 客户程序意外终止，并未结束执行

最终的结果如下：

(nemu) c
[src/cpu/cpu-exec.c:104 cpu_exec] nemu: HIT GOOD TRAP at pc = 0x8000000c
[src/cpu/cpu-exec.c:69 monitor_statistic] host time spent = 24 us
[src/cpu/cpu-exec.c:70 monitor_statistic] total guest instructions = 4
[src/cpu/cpu-exec.c:71 monitor_statistic] simulation frequency = 166,666 instr/s
(nemu)

cmd_c 执行完后返回值为 0，所以 sdb_mainloop 函数等待下一个命令的输入，若输入 q，cmd_q 返回 -1，从而跳出进入简易调试器的主循环。

对于 GNU/Linux 上的一个程序，怎么样才算开始？怎么样才算是结束？对于在 NEMU 中运行的程序，问题的答案又是什么呢？

与此相关的问题还有：NEMU 中为什么要有 nemu_trap？为什么要有 monitor？

然而，如果在运行 NEMU 之后直接键入 q 退出，会发现终端输出了一些错误信息：

(nemu) q
make: *** [/home/vgalaxy/ics2021/nemu/scripts/native.mk:23: run] Error 1

只要没有键入 c，键入 q 都会输出这样的错误信息。但是在调试中不会出现这个问题。

定位 native.mk 文件：

include $(NEMU_HOME)/scripts/git.mk
include $(NEMU_HOME)/scripts/build.mk

include $(NEMU_HOME)/tools/difftest.mk

compile_git:
    $(call git_commit, "compile")
$(BINARY): compile_git

# Some convenient rules

override ARGS ?= --log=$(BUILD_DIR)/nemu-log.txt
override ARGS += $(ARGS_DIFF)

# Command to execute NEMU
IMG ?=
NEMU_EXEC := $(BINARY) $(ARGS) $(IMG)

run-env: $(BINARY) $(DIFF_REF_SO)

run: run-env
    $(call git_commit, "run")
    $(NEMU_EXEC)

gdb: run-env
    $(call git_commit, "gdb")
    gdb -s $(BINARY) --args $(NEMU_EXEC)

clean-tools = $(dir $(shell find ./tools -name "Makefile"))
$(clean-tools):
    -@$(MAKE) -s -C $@ clean
clean-tools: $(clean-tools)
clean-all: clean distclean clean-tools

.PHONY: run gdb run-env clean-tools clean-all $(clean-tools)

注意 Makefile 文件中的 ?= 代表如果该变量没有被赋值，则赋予等号后的值。猜测：若没有键入 c，IMG 变量就为空，所以 NEMU_EXEC 变量就会出现问题。至于如何修正，不知道哎 🤣。

后续：zzh 告诉我错误的地方应该在 cmd_q 函数上，通过 gdb 调试可知 cmd_q 函数返回后控制转移到 main 函数，其中调用了 is_exit_status_bad 函数，定义在 nemu/src/utils/state.c 中：

int is_exit_status_bad() {
  int good = (nemu_state.state == NEMU_END && nemu_state.halt_ret == 0) ||
    (nemu_state.state == NEMU_QUIT);
  return !good;
}

由于 cmd_q 并没有改变 nemu_state.state，所以默认情况下 nemu_state.state 为 NEMU_STOP，于是 is_exit_status_bad 返回 1，就出问题了。所以我们只需要在 cmd_q 函数中添加一行 nemu_state.state = NEMU_QUIT; 即可。

调试：零

断点

这些断点的地址仅在未修改 nemu/src/monitor/sdb/sdb.c 的情形下有效！

sdb_mainloop

直接 break sdb_mainloop 即可

目前为 0x00005555555577f0

cmd_c

在 finish 后得到

目前调用在 0x000055555555794c，跳转后地址为 0x0000555555557680

cpu_exec

在 sdb_mainloop 处 disas 可得到其地址

目前为 0x00005555555569a0

fetch_decode

在 cpu_exec 处 disas 可得到其地址

目前为 0x0000555555556630

isa_fetch_decode

在 fetch_decode 处 disas 可得到其地址

目前为 0x00005555555588b0

TUI

运行 GDB 后，输入 layout split 可以切换到 TUI，详见 http://www.deansys.com/doc/gdbDebugging/gdb_23.html。

为 NEMU 编译时添加 GDB 调试信息

Build Options
  [*] Enable debug information

然后清除编译结果并重新编译即可。此时观察到 .config 文件的变化：

vgalaxy@vgalaxy-VirtualBox:~/ics2021/nemu$ diff .config.old .config
29c29
< # CONFIG_CC_DEBUG is not set
---
> CONFIG_CC_DEBUG=y

在 nemu/ 查找 CONFIG_CC_DEBUG：

include/config/auto.conf:23:CONFIG_CC_DEBUG=y
include/generated/autoconf.h:25:#define CONFIG_CC_DEBUG 1
Makefile:31:CFLAGS_BUILD += $(if $(CONFIG_CC_DEBUG),-ggdb3,)

通过输入 make -nB 观察变化，发现多了-ggdb3 选项：

echo + CC src/nemu-main.c

mkdir -p /home/vgalaxy/ics2021/nemu/build/obj-riscv32-nemu-interpreter/src/

gcc -O2 -MMD -Wall -Werror -I/home/vgalaxy/ics2021/nemu/include -I/home/vgalaxy/ics2021/nemu/src/engine/interpreter -I/home/vgalaxy/ics2021/nemu/src/isa/riscv32/include -O2  -ggdb3  -D__GUEST_ISA__=riscv32 -c -o /home/vgalaxy/ics2021/nemu/build/obj-riscv32-nemu-interpreter/src/nemu-main.o src/nemu-main.c

/home/vgalaxy/ics2021/nemu/tools/fixdep/build/fixdep  /home/vgalaxy/ics2021/nemu/build/obj-riscv32-nemu-interpreter/src/nemu-main.d  /home/vgalaxy/ics2021/nemu/build/obj-riscv32-nemu-interpreter/src/nemu-main.o unused >  /home/vgalaxy/ics2021/nemu/build/obj-riscv32-nemu-interpreter/src/nemu-main.d.tmp

mv  /home/vgalaxy/ics2021/nemu/build/obj-riscv32-nemu-interpreter/src/nemu-main.d.tmp  /home/vgalaxy/ics2021/nemu/build/obj-riscv32-nemu-interpreter/src/nemu-main.d

对于 -ggdb3 选项的作用，STFW。最显著的效果，可以发现 nemu/build 文件夹中多出了 nemu-log.txt 文件。

另外，原本所做的修改（如删去了 welcome 函数中的 assertion fail）仍然保留着（只是改变了一些宏）。

基础设施

基础设施 - 简易调试器

现在才知道我对 C 一无所知 🤣

单步执行

在 nemu/src/monitor/sdb/sdb.c 加入：

static int cmd_si(char *args) {
    if(args==NULL){
        cpu_exec(1);
    }else{
        char *ptr;
        long num = strtol(args,&ptr,10);
        cpu_exec(num);
    }
    return 0;
}

这里使用了 strtol 函数。

NEMU 默认会把单步执行的指令打印出来，这是由 nemu/src/cpu/cpu-exec.c 中的 debug_hook 函数完成的（框架代码更新后，变为了 trace_and_difftest 函数）。另外 nemu/src/cpu/cpu-exec.c 中的 MAX_INSTR_TO_PRINT 定义了最多可以打印的指令数。

打印寄存器状态

在 nemu/src/monitor/sdb/sdb.c 加入

static int cmd_info(char *args) {
    if(args==NULL){
        printf("missing info SUBCMD\n");
    }else if(strcmp(args,"r")==0){
        isa_reg_display();
    }else if(strcmp(args,"w")==0){
        wp_display();
    }else{
        printf("Unknown SUBCMD '%s'\n", args);
    }
    return 0;
}

这里的 isa_reg_display 函数定义在 nemu/src/isa/riscv32/reg.c 中：

#define NR_REGS ARRLEN(regs)

void isa_reg_display() {
    vaddr_t pc_val=cpu.pc;
    printf("pc  %x\n",pc_val);

    for(int i=0;i<NR_REGS;++i){
        rtlreg_t val=cpu.gpr[i]._32;
        printf("%s  %x\n",regs[i],val);
    }
}

注意这里 rtlreg_t 和 vaddr_t 都是 uint32_t。

nemu/src/isa/riscv32/reg.c 中还有一个 isa_reg_str2val 函数，不太会用 🤣（后来知道是表达式求值中获取寄存器的值）。

可以尝试根据 nemu_state.state 打印不同的结果。

扫描内存

在 nemu/src/monitor/sdb/sdb.c 加入

static int cmd_x(char *args) {
    if(args==NULL){
        printf("missing x SUBCMD\n");
        return 0;
    }else{
        char *ptr;
        long count = strtol(args,&ptr,10);
        paddr_t addr = 0;
        addr = strtol(ptr,&ptr,16);
        if(addr==0){
            printf("missing x SUBCMD\n");
            return 0;
        }else{
            mem_display(count,addr);
        }
    }
    return 0;
}

这里仍然使用了 strtol 函数。

在 nemu/src/memory/paddr.c 中定义了 mem_display 函数，其中调用了 paddr_read 函数，paddr_read 函数又调用了 pmem_read 函数：

uint8_t* guest_to_host(paddr_t paddr) { return pmem + paddr - CONFIG_MBASE; }
paddr_t host_to_guest(uint8_t *haddr) { return haddr - pmem + CONFIG_MBASE; }

static word_t pmem_read(paddr_t addr, int len) {
  return host_read(guest_to_host(addr), len);
}

其中 host_read 定义在 nemu/include/memory/host.h 中：

static inline word_t host_read(void *addr, int len) {
  switch (len) {
    case 1: return *(uint8_t  *)addr;
    case 2: return *(uint16_t *)addr;
    case 4: return *(uint32_t *)addr;
    IFDEF(CONFIG_ISA64, case 8: return *(uint64_t *)addr);
    default: MUXDEF(CONFIG_RT_CHECK, assert(0), return 0);
  }
}

下面是 mem_display 函数的实现：

void mem_display(int count, paddr_t addr){
    for(int i=0;i<count;++i){
        word_t content = paddr_read(addr+i*4,4);
        printf("0x%x    %08x\n",addr+i*4,content);
    }
}

原始版本，只调用了 guest_to_host 获取基址，并且一次读取了 4 个字：

void mem_display(long num, paddr_t addr){
    uint8_t* base = guest_to_host(addr);
    for(int i=0;i<num;++i){
        printf("0x%08x: ",addr+i*16);
        for(int j=0;j<16;++j){
            if(j%4==0)printf("0x");
            printf("%02x",base[i*16+j]);
            if((j+1)%4==0)printf("    ");
        }
        printf("\n");
    }
}

注意这里要求以十六进制形式输出连续的 n 个 4 字节，也就是 32 位，而一个字节在内存中是 4 个单元（内存单位为 uint8_t*，即 2 位）。

表达式求值

希望简易调试器能帮我们计算一些带有寄存器和内存的表达式。

词法分析

我们先来处理一种简单的情况 - 算术表达式，即待求值表达式中只允许出现以下的 token 类型：

十进制整数
+, -, *, /
(, )
空格串 (一个或多个空格)

我们需要使用 regex.h（通过 man 3 regex 了解更多内容）。

首先，我们需要使用正则表达式分别编写用于识别这些 token 类型的规则。在框架代码中，一条规则是由正则表达式和 token 类型组成的二元组。这些规则会在简易调试器初始化的时候通过 init_regex() 被编译成（使用 regcomp 函数）一些用于进行 pattern 匹配的内部信息。

在 nemu/src/monitor/sdb/sdb.c 中的 init_sdb 调用了 init_regex：

void init_sdb() {
  /* Compile the regular expressions. */
  init_regex();

  /* Initialize the watchpoint pool. */
  init_wp_pool();
}

init_regex 在 nemu/src/monitor/sdb/expr.c 中。下面的代码若未特殊说明均在其中。

给出一个待求值表达式，make_token() 函数可以根据规则识别出其中的 token，并将 token 的信息依次记录到 tokens 数组中，nr_token 指示已经被识别出的 token 数目：

typedef struct token {
  int type;
  char str[32];
} Token;

static Token tokens[32] __attribute__((used)) = {};
static int nr_token __attribute__((used))  = 0;

Token 类型中的 str 用于记录具体的十进制整数，

下面是 make_token() 函数的实现，注意此处将空格串也记录到了 tokens 数组中（与实验指导中不太一样），还有 str 的缓冲区溢出（使用 assert(0)，这体现了KISS 法则，即不要在一开始追求绝对的完美，多做单元测试）：

static bool make_token(char *e) {
  int position = 0;
  int i;
  regmatch_t pmatch;

  nr_token = 0;

  while (e[position] != '\0') {
    /* Try all rules one by one. */
    for (i = 0; i < NR_REGEX; i ++) {
      if (regexec(&re[i], e + position, 1, &pmatch, 0) == 0 && pmatch.rm_so == 0) {
        char *substr_start = e + position;
        int substr_len = pmatch.rm_eo;

        Log("match rules[%d] = \"%s\" at position %d with len %d: %.*s",
            i, rules[i].regex, position, substr_len, substr_len, substr_start);

        position += substr_len;

        /* TODO: Now a new token is recognized with rules[i]. Add codes
         * to record the token in the array `tokens'. For certain types
         * of tokens, some extra actions should be performed.
         */

        switch (rules[i].token_type) {
            case TK_NOTYPE:
            case '(':
            case ')':
            case '+':
            case '-':
            case '*':
            case '/':
                tokens[nr_token].type = rules[i].token_type;
                break;
            case TK_DEC:
                tokens[nr_token].type = rules[i].token_type;
                if(substr_len>=32)assert(0);
                memcpy(tokens[nr_token].str, substr_start, substr_len);
                tokens[nr_token].str[substr_len] = '\0';
                break;

        }

        nr_token++;

        break;
      }
    }

    if (i == NR_REGEX) {
      printf("no match at position %d\n%s\n%*.s^\n", position, e, position, "");
      return false;
    }
  }

  return true;
}

这里的关键是 regexec 函数，观察下面一行：

if (regexec(&re[i], e + position, 1, &pmatch, 0) == 0 && pmatch.rm_so == 0)

对照 regexec 的函数签名为：

int regexec(const regex_t *preg, const char *string, size_t nmatch, regmatch_t pmatch[], int eflags);

preg 指向编译完成后的正则表达式规则，string 为待匹配的字符串，nmatch 表示最多将几个匹配结果保存在 pmatch（数组）中。pmatch 类型为 regmatch_t，定义如下：

typedef struct {
   regoff_t rm_so;
   regoff_t rm_eo;
} regmatch_t;

此处我们最多匹配一个，于是 string+pmatch.rm_so 到 string+pmatch.rm_eo 就是我们匹配的字符串。

总结来说，position 变量用来指示当前处理到的位置，并且按顺序尝试用不同的规则来匹配当前位置的字符串。当一条规则匹配成功，并且匹配出的子串正好是 position 所在位置的时候，我们就成功地识别出一个 token。Log() 宏会输出识别成功的信息。switch 语句则将 token 的信息依次记录到 tokens 数组中。

一个有趣的应用 - 语法高亮：

把源代码看作一个字符串输入到语法高亮程序中，在循环中识别出一个 token 之后，根据 token 类型用不同的颜色将它的内容重新输出一遍就可以了。如果你打算将高亮的代码输出到终端里，你可以使用 ANSI 转义码的颜色功能。

递归求值

得到 tokens 数组后，下面我们对 tokens 数组代表的字符串进行求值。我们有 expr 函数，它接受原始字符串，返回表达式的值：

word_t expr(char *e, bool *success) {
  if (!make_token(e)) {
    *success = false;
    return 0;
  }

  /* TODO: Insert codes to evaluate the expression. */
  *success = true;
  return eval(0, nr_token);
}

其中的函数 eval 定义如下，参数代表 tokens 数组所代表的子表达式的下标范围为 [p,q)：

uint32_t eval(int p, int q) {
  while(tokens[p].type==TK_NOTYPE)p++;
  while(tokens[q-1].type==TK_NOTYPE)q--;

  if (p >= q) {
    /* Bad expression */
    panic("Bad expression");
  }
  else if (p + 1 == q) {
    /* Single token.
     * For now this token should be a number.
     * Return the value of the number.
     */
    char *ptr;
    return strtol(tokens[p].str,&ptr,10);
  }
  else if (check_parentheses(p, q) == true) {
    /* The expression is surrounded by a matched pair of parentheses.
     * If that is the case, just throw away the parentheses.
     */
    return eval(p + 1, q - 1);
  }
  else {
    int op = primary_op(p, q);
    uint32_t val1 = eval(p, op);
    uint32_t val2 = eval(op + 1, q);

    switch (tokens[op].type) {
      case '+': return val1 + val2;
      case '-': return val1 - val2;
      case '*': return val1 * val2;
      case '/': if (val2 == 0) assert(0);
                    return val1 / val2;
      default: assert(0);
    }
  }
  return 0;
}

前面两行是对空格串做处理，处理后子表达式中就没有空格了。

single token 的情形也很容易理解，代表一个十进制整数。

check_parentheses() 函数用于判断表达式是否被一对匹配的括号包围着，同时检查表达式的左右括号是否匹配，实现如下：

bool check_parentheses(int p, int q) {
    int num = 0;
    bool inner = false;
    bool st = (tokens[p].type=='(');
    bool ed = (tokens[q-1].type==')');
    for(int i=p;i<q;++i){
        switch(tokens[i].type){
            case '(':num++;break;
            case ')':num--;break;
            default:break;
        }
        inner|=((num==0)&&(i!=q-1));
    }
    bool sum = (num==0);
    assert(sum==true);
    return !inner && st && ed && sum;
}

这里 assert 括号数量是匹配的，inner 主要判断下面的情形：

(4 + 3) * (2 - 1)

这种情形在最后处理，即将一个长表达式分裂成两个子表达式。为此我们需要找到分裂的主运算符（表达式人工求值时最后一步进行运行的运算符）：

int primary_op(int p, int q) {
    int num = 0;
    int index=0, priority=3;
    for(int i=p;i<q;++i){
        switch(tokens[i].type){
            case '(':num++;break;
            case ')':num--;break;
            case '+':case '-':if(num==0&&priority>=1){index=i;priority=1;}break;
            case '*':case '/':if(num==0&&priority>=2){index=i;priority=2;}break;
            default: break;
        }
    }
    assert(index!=0);
    return index;
}

注意这里对优先级的考虑，另外当有多个运算符的优先级相同时，根据结合性，最后被结合的运算符才是主运算符。

另外，我们约定所有运算都是无符号运算，即类型 uint32_t。

目前对除 0 行为直接报错。

尚未实现带有负数的算术表达式的求值。

与编译原理的对应：

表达式结构的分析：语法分析

表达式最后的求值：代码生成

调试：一

调试公理：

The machine is always right. (机器永远是对的)
- Corollary: If the program does not produce the desired output, it is the programmer’s fault.
Every line of untested code is always wrong. (未测试代码永远是错的)
- Corollary: Mistakes are likely to appear in the “must-be-correct” code.

我们使用随机测试。

首先我们需要来思考如何随机生成一个合法的表达式，在 nemu/tools/gen-expr/gen-expr.c 中，我们定义了 gen_rand_expr 函数：

static void gen_rand_expr() {
  uint32_t space = choose(2);
  for(int i=0;i<space;++i)
      buf[buf_index++] = ' ';
  switch (choose(3)) {
    case 0: {gen_num();}break;
    case 1: if(buf_index<50){gen('(');gen_rand_expr();gen(')');}
                else{gen('(');gen_num();gen(')');}break;
    default: if(buf_index<50){gen_rand_expr();gen_rand_op();gen_rand_expr();}
                 else{gen_num();gen_rand_op();gen_num();}break;
  }
}

这里 buf 代表生成的字符串，而 buf_index 代表目前的下标（框架代码中并没有）。

对 buf_index 进行判断是为了防止生成的表达式太长（注意将 gen_rand_expr 换成了 gen_num，防止生成的表达式不合法）。

前面的一部分是为了随机插入空格。

下面是一些辅助函数的实现：

uint32_t choose(uint32_t n) {
    return rand() / ((RAND_MAX + 1u) / n);
}

void gen(char c) {
    buf[buf_index++] = c;
    return;
}

void gen_num() {
    uint32_t num = rand();
    if (num==0)
        num++;
    sprintf(buf+buf_index,"%u",num);

    while(num){
        num/=10;
        buf_index++;
    }
}

void gen_rand_op() {
  switch (choose(4)) {
    case 0: buf[buf_index++] = '+'; break;
    case 1: buf[buf_index++] = '-'; break;
    case 2: buf[buf_index++] = '*'; break;
    default: buf[buf_index++] = '/'; break;
  }
}

choose 函数接受一个参数 n，返回 1 ~ n - 1 中的一个整数。

gen_num 则使用 sprintf 生成一个非 0 的无符号整数（本来这样做是为了避免除 0 行为，然而发现还是避免不了 🤣）。

下面的关键是 gen-expr.c 中的 main 函数：

// this should be enough
static char buf[65536] = {};
static char code_buf[65536 + 128] = {}; // a little larger than `buf`
static char *code_format =
"#include <stdio.h>\n"
"int main() { "
"  unsigned result = %s; "
"  printf(\"%%u\", result); "
"  return 0; "
"}";

int main(int argc, char *argv[]) {
  int seed = time(0);
  srand(seed);
  int loop = 1;
  if (argc > 1) {
    sscanf(argv[1], "%d", &loop);
  }
  int i;
  for (i = 0; i < loop; i ++) {
    buf_index = 0;
    gen_rand_expr();
    buf[buf_index]='\0';

    sprintf(code_buf, code_format, buf);

    FILE *fp = fopen("/tmp/.code.c", "w");
    assert(fp != NULL);
    fputs(code_buf, fp);
    fclose(fp);

    int ret = system("gcc /tmp/.code.c -o /tmp/.expr");
    if (ret != 0) continue;

    fp = popen("/tmp/.expr", "r");
    assert(fp != NULL);

    int result;
    fscanf(fp, "%d", &result);
    pclose(fp);

    printf("%u %s\n", result, buf);
  }
  return 0;
}

编译得到的 gen-expr 接受一个循环次数的参数（生成表达式的个数）。

通过元编程的方式，在代码模板中嵌入随机生成的表达式，然后使用 system 和 popen 函数，执行并得到表达式求值的结果。

这样的结果通常是正确的，然而对于下面的情形：
1 / (1 / 3)
会出现除 0 行为。然而最终还是会被打印出来，就像这样：
2370368656 134767682/(( ( (1999988489)))*( ((((632216280)))*(636492772/1060985738)))/963486453)
总结来说，这种计算的特征是：

进行的都是无符号运算

数据宽度都是 32 bits

溢出后不处理

这样就可以用来生成表达式求值的测试用例了：

./gen-expr 10000 > input

将会生成 10000 个测试用例到 input 文件中，其中每行为一个测试用例，其格式为：

结果 表达式

再稍微改造一下 NEMU 的 main() 函数，让其读入 input 文件中的测试表达式后，直接调用 expr()，并与结果进行比较：

int main(int argc, char *argv[]) {
  /* Initialize the monitor. */
#ifdef CONFIG_TARGET_AM
  am_init_monitor();
#else
  init_monitor(argc, argv);
#endif

  /* Start engine. */
  // engine_start();
  test_expr();

  return is_exit_status_bad();
}

//
static char* rl_gets() {
  static char *line_read = NULL;

  if (line_read) {
    free(line_read);
    line_read = NULL;
  }

  line_read = readline("(expr) ");

  return line_read;
}

void test_expr() {
    for (char *str; (str = rl_gets()) != NULL; ) {
        char *expression;
        uint32_t real = strtol(str,&expression,10);

        bool success;
        uint32_t actual = expr(expression,&success);
        if (success) {
            if (real != actual) {
                printf("Wrong: %s, real is %u, actual is %u\n", expression, real, actual);
                assert(0);
            }
            else
                printf("Accept!\n");
        }
        else
            assert(0);
    }
}

这里的 rl_gets 照搬了 nemu/src/monitor/sdb/sdb.c 中的 rl_gets。

思考编译时是如何定位到 nemu/src/monitor/sdb/expr.c 中的 expr 函数。

后来将 rl_gets 和 test_expr 转移到 nemu/src/monitor/sdb/expr.c 中。注意在 main() 函数添加 #include "monitor/sdb/sdb.h"，在 nemu/src/monitor/sdb/sdb.h 添加函数声明 void test_expr();。

监视点

扩展表达式求值

扩展功能：

==、!=、&&
十六进制常数
获取寄存器的值
指针解引用

我们增加正则表达式规则：

static struct rule {
  const char *regex;
  int token_type;
} rules[] = {

  /* TODO: Add more rules.
   * Pay attention to the precedence level of different rules.
   */

  {" +", TK_NOTYPE},    // spaces
  {"\\(", '('},
  {"\\)", ')'},
  {"\\*", '*'},
  {"\\/", '/'},
  {"\\+", '+'},
  {"\\-", '-'},
  {"==", TK_EQ},
  {"!=", TK_UNEQ},
  {"&&", TK_AND},
  {"0x[0-9A-Fa-f]+", TK_HEX},
  {"[0-9]+", TK_DEC},
  {"\\$[\\$0-9A-Za-z]+", TK_REG},
};

注意有个寄存器叫 $0，并且 TK_HEX 规则在 TK_DEC 规则的前面。

功能一很容易扩展，只需要注意运算符优先级即可：

int primary_op(int p, int q) {
    int num = 0;
    int index=0, priority=10;
    for(int i=p;i<q;++i){
        switch(tokens[i].type){
            case '(':
                num++;
                break;
            case ')':
                num--;
                break;
            case '+':
            case '-':
                if(num==0&&priority>=8){index=i;priority=8;}break;
            case '*':
            case '/':
                if(num==0&&priority>=9){index=i;priority=9;}break;
            case TK_EQ:
            case TK_UNEQ:
                if(num==0&&priority>=7){index=i;priority=7;}break;
            case TK_AND:
                if(num==0&&priority>=6){index=i;priority=6;}break;
            default: break;
        }
    }
    assert(index!=0);
    return index;
}

功能二也不难，略去。

功能三是获取寄存器的值，这显然是一个 ISA 相关的功能。框架代码已经准备了如下的 API：

// nemu/src/isa/$ISA/reg.c
word_t isa_reg_str2val(const char *s, bool *success);

它用于返回名字为 s 的寄存器的值，并设置 success 指示是否成功。

具体实现如下，别忘了寄存器 pc：

word_t isa_reg_str2val(const char *s, bool *success) {
    if(strcmp(s,"pc")==0){
        *success=true;
        return cpu.pc;
    }
    for(int i=0;i<NR_REGS;++i)
        if(strcmp(s,regs[i])==0){
            *success=true;
            return cpu.gpr[i]._32;
        }
    *success=false;
    return 0;
}

我们修改 eval 函数：

  else if (p + 1 == q) {
    /* Single token.
     * For now this token should be a number.
     * Return the value of the number.
     */
    char *ptr;
    switch(tokens[p].type){
        case TK_DEC:
            return strtol(tokens[p].str,&ptr,10);
        case TK_HEX:
            return strtol(tokens[p].str,&ptr,16);
        case TK_REG:
            {
                bool success;
                word_t res = isa_reg_str2val(tokens[p].str, &success);
                if (success)
                    return res;
                else
                    assert(0);
            }
        default:
            assert(0);
    }
  }

注意在 make_token 中对 TK_HEX 和 TK_REG 的识别。

功能四是指针解引用。首先我们需要区分乘法和指针解引用，为了优雅的实现这一点，我们不再将空格串记录到 tokens 数组中（有匹配的 Log 记录，但是不会增加 nr_token），并在 make_token 后扫描一遍 tokens 数组：

word_t expr(char *e, bool *success) {
  if (!make_token(e)) {
    *success = false;
    return 0;
  }

  /* TODO: Insert codes to evaluate the expression. */

  for(int i=0;i<nr_token;++i) {
      if(tokens[i].type=='*'&&i==0){
          tokens[i].type=TK_DEREF;
      }else if(tokens[i].type=='*'&&i>=1){
          if(tokens[i-1].type=='+'
                  ||tokens[i-1].type=='-'
                  ||tokens[i-1].type=='*'
                  ||tokens[i-1].type=='/'
                  ||tokens[i-1].type==TK_EQ
                  ||tokens[i-1].type==TK_UNEQ
                  ||tokens[i-1].type==TK_AND
                  ||tokens[i-1].type==TK_DEREF
                  ||tokens[i-1].type=='('){
              tokens[i].type=TK_DEREF;
          }
      }
  }

  for(int i=0;i<nr_token;++i) {
      if(tokens[i].type=='-'&&i==0){
          tokens[i].type=TK_MINUS;
      }else if(tokens[i].type=='-'&&i>=1){
          if(tokens[i-1].type=='+'
                  ||tokens[i-1].type=='-'
                  ||tokens[i-1].type=='*'
                  ||tokens[i-1].type=='/'
                  ||tokens[i-1].type==TK_EQ
                  ||tokens[i-1].type==TK_UNEQ
                  ||tokens[i-1].type==TK_AND
                  ||tokens[i-1].type==TK_MINUS
                  ||tokens[i-1].type=='('){
              tokens[i].type=TK_MINUS;
          }
      }
  }

  *success = true;
  return eval(0, nr_token);
}

若 * 为第一个 token 或者 * 前一个 token 的类型为二元运算符（或者就是解引用，或者是左括号），那么这个 * 就是指针解引用。

上述框架也处理了负数问题

另外，我们约定指针没有类型，进行指针解引用的时候，我们总是从客户计算机的内存中读出一个 uint32_t 类型的整数，所以我们对应修改 eval 函数：

  else {
    int op = primary_op(p, q);
    uint32_t val1 = 0, val2 = 0;
    if(tokens[op].type!=TK_DEREF&&tokens[op].type!=TK_MINUS)
        val1 = eval(p, op);
    val2 = eval(op + 1, q);

    switch (tokens[op].type) {
      case '+': return val1 + val2;
      case '-': return val1 - val2;
      case '*': return val1 * val2;
      case '/': {
                    if (val2 == 0) assert(0);
                    return val1 / val2;
                }
      case TK_EQ: return val1 == val2;
      case TK_UNEQ: return val1 != val2;
      case TK_AND: return val1 && val2;
      case TK_DEREF: {
                         uint8_t* base = guest_to_host(val2);
                         uint32_t res = 0;
                         for(int i=3;i>=0;--i) res=res*256+(*(base+i));
                         return res;
                     }
      case TK_MINUS: return -val2;
      default: assert(0);
    }
  }
  return 0;
}

这里我们使用了 guest_to_host 函数，注意字节顺序是小端法。

别忘了更新 primary_op 函数：

int primary_op(int p, int q) {
    int num = 0;
    int index=0, priority=11;
    int tag = 1;
    for(int i=p;i<q;++i){
        switch(tokens[i].type){
            case '(':
                num++;
                break;
            case ')':
                num--;
                break;
            case '+':
            case '-':
                if(num==0&&priority>=8){index=i;priority=8;}break;
            case '*':
            case '/':
                if(num==0&&priority>=9){index=i;priority=9;}break;
            case TK_EQ:
            case TK_UNEQ:
                if(num==0&&priority>=7){index=i;priority=7;}break;
            case TK_AND:
                if(num==0&&priority>=6){index=i;priority=6;}break;
            case TK_DEREF:
            case TK_MINUS:
                if(num==0&&priority>=10&&tag){index=i;priority=10;tag=0;}break;
            default: break;
        }
    }
    //assert(index!=0);
    return index;
}

注：这里假定指针解引用和一元负数运算符的优先级一致，实际上一元负数运算符的优先级更高，所以上述算法对 -*addr 这类表达式会失效（一元负数运算符被跳过），tag 是为了满足从右到左的结合性。

最后，别忘了在 nemu/src/monitor/sdb/sdb.c 中加入 cmd_p 函数，这样的话我们曾经编写的 test_expr 函数就光荣退役了 🤣：

static int cmd_p(char *args) {
    if(args==NULL){
        printf("missing p SUBCMD\n");
        return 0;
    }else{
        bool success;
        word_t res = expr(args,&success);
        if(success){
            printf("%s = %u\n",args,res);
            return 0;
        }else{
            printf("Wrong format: %s\n",args);
            return 0;
        }
    }
}

实现监视点

我们使用链表将监视点的信息组织起来。框架代码中已经定义好了监视点的结构体，在 nemu/src/monitor/sdb/watchpoint.c 中：

typedef struct watchpoint {
  int NO;
  struct watchpoint *next;

  /* TODO: Add more members if necessary */
  uint32_t val;
  char str[32];

} WP;

static WP wp_pool[NR_WP] = {};
static WP *head = NULL, *free_ = NULL;

void init_wp_pool() {
  int i;
  for (i = 0; i < NR_WP; i ++) {
    wp_pool[i].NO = i;
    wp_pool[i].next = &wp_pool[i + 1];
  }
  wp_pool[NR_WP - 1].next = NULL;

  head = NULL;
  free_ = wp_pool;
}

代码中定义了监视点结构的池 wp_pool，还有两个链表 head 和 free_，其中 head 用于组织使用中的监视点结构，free_ 用于组织空闲的监视点结构，init_wp_pool() 函数会对两个链表进行初始化（在 nemu/src/monitor/sdb/sdb.c 中的 init_sdb 调用了 init_wp_pool）。

注意这里的 static 关键词，由此我们不需要显式地进行 malloc 和 free 了，所用的空间都在 wp_pool 中。

为了使用监视点池，需要编写以下两个函数：

void new_wp(char *arg) {
    if(free_==NULL)
        assert(0);
    WP* now=free_;
    free_=free_->next;
    now->next=NULL;

    strcpy(now->str,arg);
    bool success;
    uint32_t init = expr(now->str,&success);
    if(success){
        now->val=init;
        printf("Watchpoint %d: %s\nInitial value %u\n", now->NO, now->str, now->val);
    }else{
        assert(0);
    }

    if(head==NULL)
        head=now;
    else
        head->next=now;
    return;
}

void free_wp(int index) {
    assert(index>=0);
    if(head==NULL)
        assert(0);

    WP* now=head;
    WP* target=NULL;
    int num=0;
    while(now){
        if(now->NO==index){
            target=now;
            break;
        }
        if(now->next!=NULL){
            num++;
            now=now->next;
        }
        else
            break;
    }

    if(target==NULL){
        printf("Watchpoint %d not found!\n", index);
        return;
    }

    WP* before;
    WP* after=target->next;
    if(num==0){
        head=after;
    }else{
        now=head;
        while(num>1){
            now=now->next;
            num--;
        }
        before=now;
        before->next=after;
    }

    target->next=free_;
    free_=target;
    free_->val=0;
    free_->str[0]='\0';
    return;
}

大概思路是 new_wp 函数接受一个表达式，从 free_ 链表的开头得到一个 watchpoint，并加入到 head 链表的最后；而 free_wp 函数接受一个序号，在 head 链表中查找相同序号的 watchpoint，删除后再加入到 free_ 链表中。

实现了监视点池的管理之后，我们就可以考虑如何实现监视点的相关功能了：

设置监视点
删除监视点
打印监视点信息

首先是打印监视点信息，我们添加一个新的函数 wp_display：

void wp_display(){
    WP* now=head;
    if(now==NULL){
        printf("No watchpoints.\n");
        return;
    }else{
        while(now){
            printf("Watchpoint %d: %s = %u\n", now->NO, now->str, now->val);
            now=now->next;
        }
        return;
    }
}

在 cmd_info 相应的地方调用 wp_display 即可。

对于设置和删除监视点，分别调用 new_wp 函数和 free_wp 函数即可。

注意此处我们修改了两个函数的签名，让工作尽可能在 nemu/src/monitor/sdb/watchpoint.c 中进行，否则在 nemu/src/monitor/sdb/sdb.c 中结构体的使用会非常麻烦！

最后，我们需要在 debug_hook() 函数 (在 nemu/src/cpu/cpu-exec.c 中定义) 的最后扫描所有的监视点，每当 cpu_exec() 的循环执行完一条指令，都会调用一次 debug_hook() 函数。在扫描监视点的过程中，你需要对监视点的相应表达式进行求值 (这就是实现表达式求值的意义！)，并比较它们的值有没有发生变化，若发生了变化，程序就因触发了监视点而暂停下来，你需要将 nemu_state.state 变量设置为 NEMU_STOP 来达到暂停的效果：

#ifdef CONFIG_DEBUG
static void debug_hook(vaddr_t pc, const char *asmbuf) {
  log_write("%s\n", asmbuf);
  if (g_print_step) { puts(asmbuf); }
  if(check_wp()&&nemu_state.state!=NEMU_ABORT&&nemu_state.state!=NEMU_END)
      nemu_state.state=NEMU_STOP;
}
#endif

CONFIG_DEBUG 宏可以通过 menuconfig 进行开关：
Testing and Debugging
[ ] Enable debug features inside NEMU

注意此处对 NEMU_ABORT 和 NEMU_END 的特判，否则若键入 w $pc，当 trap 指令修改了 nemu_state.state 后，check_wp 返回 true 又会将 nemu_state.state 设为 NEMU_STOP，从而导致程序无法正常退出，就像下面那样：

(nemu) si
invalid opcode(PC = 0x80000010):
  1c e3 d3 27 da 28 64 6c ...
  27d3e31c 6c6428da...
There are two cases which will trigger this unexpected exception:
1. The instruction at PC = 0x80000010 is not implemented.
2. Something is implemented incorrectly.
Find this PC(0x80000010) in the disassembling result to distinguish which case it is.

If it is the first case, see
       _                         __  __                         _
      (_)                       |  \/  |                       | |
  _ __ _ ___  ___ ________   __ | \  / | __ _ _ __  _   _  __ _| |
 | '__| / __|/ __|______\ \ / / | |\/| |/ _` | '_ \| | | |/ _` | |
 | |  | \__ \ (__        \ V /  | |  | | (_| | | | | |_| | (_| | |
 |_|  |_|___/\___|        \_/   |_|  |_|\__,_|_| |_|\__,_|\__,_|_|

for more details.

If it is the second case, remember:
* The machine is always right!
* Every line of untested code is always wrong!

而 check_wp 函数实现如下：

bool check_wp(){
    bool flag = false;
    WP* now=head;
    while(now){
        uint32_t ori=now->val;
        bool success;
        uint32_t real=expr(now->str,&success);
        if(success){
            if(ori!=real){
                printf("Watchpoint %d: %s\nOld value = %u\nNew value = %u\n",
                        now->NO, now->str, ori, real);
                now->val=real;
                flag=true;
            }
        }else{
            assert(0);
        }
        now=now->next;
    }
    return flag;
}

若在同一时刻触发两个及以上的监视点，我们会全部显示出来（为了更新监视点的值）。

另外，我们可以很容易地用监视点来模拟断点的功能：

w $pc == ADDR

其中 ADDR 为设置断点的地址。这样程序执行到 ADDR 的位置时就会暂停下来。

然而 gdb 设置断点的工作方式和上述通过监视点来模拟断点的方法大相径庭，可以阅读这篇文章。

如果把断点设置在指令的非首字节，上述通过监视点来模拟断点的方法就会失效（直接跳过），而在 gdb 中会提示下面的信息：

(gdb) continue
Continuing.
Warning:
Cannot insert breakpoint 1.
Cannot access memory at address 0x1169

Command aborted.

模拟器 (Emulator) 和调试器 (Debugger) 有什么不同？更具体地，和 NEMU 相比，GDB 到底是如何调试程序的？

调试：二

在实现监视点的过程中，你很有可能会碰到段错误（目前尚未发现 🤣）。

例如编写了 if (p = NULL) 这样的代码。但执行到这行代码的时候，也只是 p 被赋值成 NULL，程序还会往下执行。然而等到将来对 p 进行了解引用的时候，就会触发段错误。

从上面的这个例子中抽象出一些软件工程相关的概念：

Fault: 实现错误的代码，例如 if (p = NULL)
Error: 程序执行时不符合预期的状态，例如 p 被错误地赋值成 NULL
Failure: 能直接观测到的错误，例如程序触发了段错误

调试其实就是从观测到的 failure 一步一步回溯寻找 fault 的过程。

调试之所以不容易，是因为：

fault 不一定马上触发 error
触发了 error 也不一定马上转变成可观测的 failure
error 会像滚雪球一般越积越多，当我们观测到 failure 的时候，其实已经距离 fault 非常遥远了

理解了这些原因之后，我们就可以制定相应的策略了：

尽可能把 fault 转变成 error，方法是提高测试的覆盖度（如简化表达式求值中的随机测试）
尽早观测到 error 的存在，可以使用一些工具：
- -Wall, -Werror
- assert()
- printf, Log
- GDB
- sanitizer

如何阅读手册

学会使用目录
逐步细化搜索范围

下面是针对 gcc 和 riscv32 的一些练习：

riscv32 有哪几种指令格式？

应当阅读的手册（也许）是 Unprivileged ISA，并且是 RV32I，也就是第二章。

阅读 §2.2 和 §2.3 可知，riscv32 有四种指令格式 (R/I/S/U)。若考虑立即数，S 类型衍生出 B 类型，U 类型衍生出 J 类型。

LUI 指令的行为是什么？

同样是阅读 Unprivileged ISA 的第二章。LUI 指令为 U 类型，将高 20 位编码的立即数左移 12 位后，装入目的寄存器。

mstatus 寄存器的结构是怎么样的？

阅读 Privileged ISA 的 §3.1.6，可知 mstatus 寄存器为机器状态寄存器，具体的结构 RTFM。

打开 nemu/scripts/build.mk 文件，你会在 CFLAGS 变量中看到 gcc 的一些编译选项。请解释 gcc 中的 -Wall 和 -Werror 有什么作用？为什么要使用 -Wall 和 -Werror？

CFLAGS  := -O2 -MMD -Wall -Werror $(INCLUDES) $(CFLAGS)

man gcc 可知：

-Wall

This enables all the warnings about constructions that some users consider questionable, and that are easy to avoid (or modify to prevent the warning), even in conjunction with macros.  This also enables some language-specific warnings described in C++ Dialect Options and Objective-C and Objective-C++ Dialect Options.

-Wall 会开启一堆选项，以第一个 -Waddress 为例：

-Waddress

Warn about suspicious uses of memory addresses.

可以检测类似下面的错误：

"void func(void); if (func)"
"if (x == "abc")"

如果想要一些额外的选项，可以使用 -Wextra。

而对于 -Werror，则直接将所有的警告都报错处理。

-Werror

Make all warnings into errors.

也可以使用 -Werror=* 的格式将特定的警告报错处理。当然也有 -Wno-error=*。

统计代码行数

完成 PA1 的内容之后，nemu/ 目录下的所有 .c 和 .h 和文件总共有多少行代码，除去空行呢？

先不去除空行：

vgalaxy@vgalaxy-VirtualBox:~/ics2021/nemu$ find -name "*[.h|.c]" -type f | xargs cat | wc -l
23543

"*[.h|.c]" 为正则表达式，-type f 指定目标类型为文件，xargs 则捕获 find 的输出并传递给 wc（find 本身并不支持管道命令）。

若去除空行：

vgalaxy@vgalaxy-VirtualBox:~/ics2021/nemu$ find -name "*[.h|.c]" -type f | xargs cat | grep -v ^$ | wc -l
20331

-v 表示选取不匹配的行。而 ^ 匹配开头，$ 匹配结尾，所以 ^$ 匹配一个空行。

和框架代码相比，你在 PA1 中编写了多少行代码？

我们切换到 PA0 进行统计：

vgalaxy@vgalaxy-VirtualBox:~/ics2021/nemu$ find -name "*[.h|.c]" -type f | xargs cat | grep -v ^$ | wc -l
19868

好像只写了不到 500 行 🤣

可以把这条命令写入 Makefile 中，随着实验进度的推进，你可以很方便地统计工程的代码行数，例如敲入 make count 就会自动运行统计代码行数的命令。

ICS PA 1

TOC

ICS PA 1

init.sh

make 编译加速

ISA

计算机是个状态机

程序是个状态机

准备第一个客户程序

parse_args

init_rand

init_log

init_mem

init_isa

load_img

剩余的初始化工作

运行第一个客户程序

调试：零

断点

TUI

为 NEMU 编译时添加 GDB 调试信息

基础设施

单步执行

打印寄存器状态

扫描内存

表达式求值

词法分析

递归求值

调试：一

监视点

扩展表达式求值

实现监视点

调试：二

如何阅读手册

统计代码行数

`init.sh`

`make` 编译加速