PA通关--pa1

发表于 更新于

PA的目的是要实现NEMU, 一款经过简化的全系统模拟器.

一周目，我选择最简单的riscv32作为nemu的ISA。同时，NEMU的框架代码会把riscv32作为默认的ISA

RTFSC

配置系统 kconfig

NEMU使用konfig配置系统，它来源于GNU/Linux项目中的kconfig。

Linux kernel的目录结构下一般都会存在Kconfig和Makefile两个文件。分布在各级目录下的Kconfig构成了一个分布式的内核配置数据库，每个Kconfig分别描述了所属目录源文件相关的内核配置菜单。在内核配置make menuconfig时（执行make menuconfig时会出现内核的配置界面），从Kconfig中读出配置菜单，用户配置完后保存到.config(在顶层目录下生成)中。在内核编译时，主Makefile调用这个.config，就知道了用户对内核的配置情况。

kconfig定义了一套简单的语言, 开发者可以使用这套语言来编写”配置描述文件”. 在”配置描述文件”中, 开发者可以描述:

  • 配置选项的属性, 包括类型, 默认值等
  • 不同配置选项之间的关系
  • 配置选项的层次关系

NEMU中的配置系统位于nemu/tools/kconfig目录，在NEMU项目中, “配置描述文件”的文件名都为Kconfig。

在进行NEMU的配置时（例如选择ISA等），我们只需要运行命令：

1
make menuconfig

就会打开一个图形化的配置界面，更新配置并保存即可

【挖坑：kconfig配置系统】

虽然kconfig的工作过程很复杂，但我们只需要知道保存配置后，会自动生成以下包含配置信息的文件

  • nemu/include/generated/autoconf.h, 可以被包含到C代码中的宏定义， 这些宏的名称都是形如CONFIG_xxx的形式
  • nemu/include/config/auto.conf, 可以被包含到Makefile中的变量定义

项目构建 Makefile

NEMU的项目构建采用Makefile，位于nemu/Makefile，下面对此文件进行阐释

$(NEMU_HOME)/Makefile

~ 此Makefile为项目的总Makefile

1. Sanity Check

1
2
3
ifeq ($(wildcard $(NEMU_HOME)/src/nemu-main.c),)
  $(error NEMU_HOME=$(NEMU_HOME) is not a NEMU repo)
endif

检查是否存在$(NEMU_HOME)/src/nemu-main.c文件，这是nemu系统的启动文件，含有main函数。

2. 与配置系统关联

1
2
-include $(NEMU_HOME)/include/config/auto.conf
-include $(NEMU_HOME)/include/config/auto.conf.cmd

通过包含auto.conf文件，关联kconfig生成的变量；

通过包含auto.conf文件，关联kconfig描述的依赖规则；

3. 与其他makefile关联

1
2
FILELIST_MK = $(shell find -L ./src -name "filelist.mk")
include $(FILELIST_MK)

以上代码先是通过shell命令寻找./src目录下的所有名为filelist.mk的makefile文件，然后再全部include进来。

4. 确定最终的编译文件集合

这一步做的是确定目录黑名单、文件黑名单，从而最终确定所有需要编译的源文件。

1
2
3
4
DIRS-BLACKLIST-y += $(DIRS-BLACKLIST)
SRCS-BLACKLIST-y += $(SRCS-BLACKLIST) $(shell find -L $(DIRS-BLACKLIST-y) -name "*.c")
SRCS-y += $(shell find -L $(DIRS-y) -name "*.c")
SRCS = $(filter-out $(SRCS-BLACKLIST-y),$(SRCS-y))

$(filter-out PATTERN…,TEXT)和$(filter)函数实现的功能相反。过滤掉字串“TEXT”中所有符合模式“PATTERN”的单词，保留所有不符合此模式的单词。

5. 从配置系统中提取变量

（1）提取ISA和ENGINE
1
2
3
4
5
6
remove_quote = $(patsubst "%",%,$(1))

# Extract variabls from menuconfig
GUEST_ISA ?= $(call remove_quote,$(CONFIG_ISA))
ENGINE ?= $(call remove_quote,$(CONFIG_ENGINE))
NAME    = $(GUEST_ISA)-nemu-$(ENGINE)

以上代码提取auto.config中的ISA和ENGINE配置，同时由于在auto.config文件中这些都是带引号的字符串，因此需要定义一个“小函数”remove_quote来去除字符串。

具体来说，$(patsubst <pattern>,<replacement>,<text>)的功能为查找text中的单词，如果匹配pattern,那么就用replacement的内容替换，并返回替换后的结果。

$(call variable,param,param,...)的功能是将若干的param依次替换variable中的$(1)、$(2)、$(3)...，这里$(n)表示第n个临时变量

其实将varialbe类比格式化字符串，将$(call )类比C的printf()，或python中的format()就很容易理解

例如

1
a = "xxxx {1} xxx{0}".format(value1,value2)

综上，$(patsubst "%",%,$(1))表示：匹配$(1)中的所有含有双引号的字符串，并返回去掉双引号后的内容。

（2）提取编译选项
1
2
3
4
5
6
7
8
CC = $(call remove_quote,$(CONFIG_CC))
CFLAGS_BUILD += $(call remove_quote,$(CONFIG_CC_OPT))
CFLAGS_BUILD += $(if $(CONFIG_CC_LTO),-flto,)
CFLAGS_BUILD += $(if $(CONFIG_CC_DEBUG),-Og -ggdb3,)
CFLAGS_BUILD += $(if $(CONFIG_CC_ASAN),-fsanitize=address,)
CFLAGS_TRACE += -DITRACE_COND=$(if $(CONFIG_ITRACE_COND),$(call remove_quote,$(CONFIG_ITRACE_COND)),true)
CFLAGS  += $(CFLAGS_BUILD) $(CFLAGS_TRACE) -D__GUEST_ISA__=$(GUEST_ISA)
LDFLAGS += $(CFLAGS_BUILD)

$(NEMU_HOME)/include/config/auto.conf

~ 此Makefile包含配置系统的变量

$(NEMU_HOME)/include/config/auto.conf

~ 此Makefile包含配置选项的依赖规则

$(NEMU_HOME)/scripts/config.mk

~ 此Makefile定义用于menuconfig的一些规则

1. 检查.config文件是否存在

1
2
3
4
ifeq ($(wildcard .config),)
$(warning $(COLOR_RED)Warning: .config does not exists!$(COLOR_END))
$(warning $(COLOR_RED)To build the project, first run 'make menuconfig'.$(COLOR_END))
endif

如果不存在，则Warning

$(wildcard <PATTERN...>)wildcard函数是针对通配符在函数或变量定义中展开无效情况下使用的，用于获取匹配该模式下的所有文件列表，<PATTERN...>参数若有多个则用空格分隔。若没有找到指定的匹配模式则返回为空。

2. menuconfig规则

1
2
3
menuconfig: $(MCONF) $(CONF) $(FIXDEP)
	$(Q)$(MCONF) $(Kconfig)
	$(Q)$(CONF) $(silent) --syncconfig $(Kconfig)
  • 运行命令mconf nemu/Kconfig, 此时mconf将会解析nemu/Kconfig中的描述, 以菜单树的形式展示各种配置选项, 供开发者进行选择.退出菜单时, mconf会把开发者选择的结果记录到nemu/.config文件中
  • 运行命令conf --syncconfig nemu/Kconfig, 此时conf将会解析nemu/Kconfig中的描述, 并读取选择结果nemu/.config, 结合两者来生成$(NEMU_HOME)/include/generated/autoconf.h、$(NEMU_HOME)/include/config/auto.conf、$(NEMU_HOME)/include/config/auto.conf.cmd、$(NEMU_HOME)/include/config/文件

TODO（其他部分）

$(NEMU_HOME)/scripts/native.mk

~ 此Makefile为构建nemu的Makefile，很重要⚠

$(NEMU_HOMU)/scripts/build.mk

~ 此Makefile规定了编译规则

1
2
3
4
5
6
7
8
9
10
11
12
// C
$(OBJ_DIR)/%.o: %.c
	@echo + CC $<
	@mkdir -p $(dir $@)
	@$(CC) $(CFLAGS) -c -o $@ $<
	$(call call_fixdep, $(@:.o=.d), $@)
// c++
$(OBJ_DIR)/%.o: %.cc
	@echo + CXX $<
	@mkdir -p $(dir $@)
	@$(CXX) $(CFLAGS) $(CXXFLAGS) -c -o $@ $<
	$(call call_fixdep, $(@:.o=.d), $@)

NEMU运行

接下来我会以nemu的运行过程为主线，大致介绍nemu的代码

main函数

正如上文所言，nemu的main函数位于$(NEMU_HOME)/src/nemu-main.c，如下所示：

1
2
3
4
5
6
7
8
9
10
11
12
13
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();
}

  • 首先初始化monitor

    如果定义了CONFIG_TARGET_AM宏，那么会通过am_init_monitor函数初始化monitor，否则通过init_monitor初始化monitor。

  • 然后启动engine

    调用engine_start函数，这一步是nemu的主体过程

  • 最后检查engine结束后的nemu状态

    返回is_exit_status_bad的返回值。具体来说，只有在NEMU_QUIT或者NEMU_END并且halt返回值为0时，才算正常退出。

    如果非正常退出，main函数会返回一个非0值，make检测到可执行文件返回非0值后，会报错（这也就解释了pa1中“优雅地退出”问题）

    1
    2
    3
    4
    5
    6
    // $(NEMU_HOMU)/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;
    }

void init_monitor(int argc, char *argv[])函数

解析命令行参数parse_args

初始化monitor的若干模块，如存储、设备等

将镜像加载至内存（如果有的话）

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
// $(NEMU_HOMU)/src/monitor/monitor.c
void init_monitor(int argc, char *argv[]) {
  /* Perform some global initialization. */
  /* Parse arguments. */
  parse_args(argc, argv);
  /* Set random seed. */
  init_rand();
  /* Open the log file. */
  init_log(log_file);
  /* Initialize memory. */
  init_mem();
  /* Initialize devices. */
  IFDEF(CONFIG_DEVICE, init_device());
  /* Perform ISA dependent initialization. */
  init_isa();
  /* Load the image to memory. This will overwrite the built-in image. */
  long img_size = load_img();
  /* Initialize differential testing. */
  init_difftest(diff_so_file, img_size, difftest_port);
  /* Initialize the simple debugger. */
  init_sdb();

#ifndef CONFIG_ISA_loongarch32r
  IFDEF(CONFIG_ITRACE, init_disasm(
    MUXDEF(CONFIG_ISA_x86,     "i686",
    MUXDEF(CONFIG_ISA_mips32,  "mipsel",
    MUXDEF(CONFIG_ISA_riscv,
      MUXDEF(CONFIG_RV64,      "riscv64",
                               "riscv32"),
                               "bad"))) "-pc-linux-gnu"
  ));
#endif

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

void engine_start()函数

~ 该函数启动engine

它的实现位于$(NEMU_HOMU)/src/engine/interpreter/init.c

1
2
3
4
5
6
7
8
void engine_start() {
#ifdef CONFIG_TARGET_AM
  cpu_exec(-1);
#else
  /* Receive commands from user. */
  sdb_mainloop();
#endif
}

如果定义了CONFIG_TARGET_AM宏，那么直接执行cpu计算过程；反之，开启简易调试器（sdb），nemu会在调试器下执行cpu计算过程。

基础设施: 简易调试器

简易调试器(Simple Debugger, sdb)是NEMU中一项非常重要的基础设施. 我们知道NEMU是一个用来执行其它客户程序的程序, 这意味着, NEMU可以随时了解客户程序执行的所有信息

命令 格式 使用举例 说明
帮助(1) help help 打印命令的帮助信息
继续运行(1) c c 继续运行被暂停的程序
退出(1) q q 退出NEMU
单步执行 si [N] si 10 让程序单步执行N条指令后暂停执行, 当N没有给出时, 缺省为1
打印程序状态 info SUBCMD info r info w 打印寄存器状态 打印监视点信息
扫描内存(2) x N EXPR x 10 $esp 求出表达式EXPR的值, 将结果作为起始内存 地址, 以十六进制形式输出连续的N个4字节
表达式求值 p EXPR p $eax + 1 求出表达式EXPR的值,
设置监视点 w EXPR w *0x2000 当表达式EXPR的值发生变化时, 暂停程序执行
删除监视点 d N d 2 删除序号为N的监视点
(3)打印历史命令 history history 打印历史命令
  • (1) 命令已实现
  • (2) 与GDB相比, 我们在这里做了简化, 更改了命令的格式
  • (3) 笔者自己添加的命令

注册命令

在每次增加新命令时，需要先在命令表中进行注册，如下：

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
static struct {
  const char *name;
  const char *description;
  int (*handler) (char *);
} cmd_table [] = {
  { "help", "Display information about all supported commands", cmd_help },
  { "c", "Continue the execution of the program", cmd_c },
  { "q", "Exit NEMU", cmd_q },

  /* TODO: Add more commands */
  // si [N]
  { "si", "Let the program step through N instructions and then pause execution", cmd_si},
  // info r / w
  { "info", "Print the status of program", cmd_info},
  // p Expr
  { "p", "Evalute the expression", cmd_p},
  // x N Expr
  { "x", "Evalute the expression and take the reuslt as the begin address, print the continous N bytes as Hex", cmd_x},
  // w Expr
  { "w", "Watch the expression, if the expression change, stop the program", cmd_w},
  // d N
  { "d", "Delete the watchpoint N", cmd_d},
  // history
  { "history", "show history command", cmd_history}
};

解析命令

void sdb_mainloop()函数

~ 该函数是调试器的主循环

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
// $(NEMU_HOMU)/src/monitor/sdb/sdb.c
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; } // just read the "Enter"

    /* 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; } // if enter "q", cme_q will return -1
        break;
      }
    }

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

函数主体实现了读取并识别sdb命令的功能。

每次for循环将调用一次rl_gets()函数，获得用户在命令行中敲入的字符串（回车键以前）；然后通过strtok()函数提取第一个空格以前的字符串作为命令，其余字符串作为参数；最后依次查找注册的命令表中是否存在用户输入的命令，如果匹配到了，就把参数传递给命令表中该命令的执行函数，如果返回值>=0，则读取下一条命令，否则退出sdb。

static char* rl_gets()函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// $(NEMU_HOMU)/src/monitor/sdb/sdb.c
static char* rl_gets() {
  static char *line_read = NULL;

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

  line_read = readline("(nemu) ");

  if (line_read && *line_read) {
    add_history(line_read);
  }

  return line_read;
}
char *readline(const char *)

该函数主要调用<readline/readline.h>库中的readline()函数实现了shell中的“显示命令提示符”和“读取用户输入的命令字符串”两个功能。readline() 的参数是一个字符串，调用函数的时候会在屏幕上输出，这个函数会读取一行输入，然后返回一个指向输入字符串的指针。

需要注意的是：

  • readline 会为输入的字符串动态分配内存。
  • 由于readline是一个动态库，编译的时候需要加上-lreadline，不然会找不到相关的函数。
void add_history ((const char *))

还使用了<readline/history.h>库中的add_history() 函数实现记录历史命令的功能。

char *strtok(char *str, const char *delim)函数

strtok函数是一个string.h中的字符串切割函数，str为待切割字符串，delim为分隔符集合

  • 第一次切割时需要传入str：strtok(str,seps);
  • 再次切割不需要传入str：strtok(NULL,seps);
  • 若切割成功，则返回切割下的字符串首地址，分隔符用’\0’替代。同时，str会发生改变，指向分割后的字符串首地址。
  • 若切割失败，则返回空指针。

参考博客：C语言strtok函数的用法_strtok在c语言怎么用-CSDN博客

cmd_help 帮助

cmd_help主要用于打印命令的解释信息，这些信息在注册的命令表中。

  • 如果有参数，则只打印参数对应命令的帮助
  • 如果无参数，则打印所有命令的帮助
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// $(NEMU_HOME)/src/monitor/sdb/sdb.c
static int cmd_help(char *args) {
  /* extract the first argument */
  char *arg = strtok(NULL, " ");
  int i;

  if (arg == NULL) {
    /* no argument given */
    for (i = 0; i < NR_CMD; i ++) {
      printf("%s - %s\n", cmd_table[i].name, cmd_table[i].description);
    }
  }
  else {
    for (i = 0; i < NR_CMD; i ++) {
      if (strcmp(arg, cmd_table[i].name) == 0) {
        printf("%s - %s\n", cmd_table[i].name, cmd_table[i].description);
        return 0;
      }
    }
    printf("Unknown command '%s'\n", arg);
  }
  return 0;
}

cmd_c 继续运行

1
2
3
4
5
// $(NEMU_HOME)/src/monitor/sdb/sdb.c
static int cmd_c(char *args) {
  cpu_exec(-1);
  return 0;
}

cpu_exec(n)函数的功能为CPU执行n步，这里对应着讲义中提出的一个问题：

❓究竟要执行多久?

在cmd_c()函数中, 调用cpu_exec()的时候传入了参数-1, 你知道这是什么意思吗?

其实看一下cpu_exec()的定义就知道答案

1
void cpu_exec(uint64_t n);

相信你已经发现了，我们传入的实参是有符号数-1，但cpu_exec()的形参确实无符号的uint64_t，因此编译器会进行隐式类型转换，将有符号的负数解释为一个很大的无符号数，所以这里可以理解为执行“无穷”步。

cmd_q 退出

1
2
3
4
// $(NEMU_HOME)/src/monitor/sdb/sdb.c
static int cmd_q(char *args) {
  return -1;
}

正如前面所言，如果返回一个小于0的数，sdb会退出，因此这里返回-1。

这里对应一个讲义中的小练习：

如果在运行NEMU之后直接键入q退出, 你会发现终端输出了一些错误信息. 请分析这个错误信息是什么原因造成的, 然后尝试在NEMU中修复它.

1
2
3
4
5
6
Welcome to riscv32-NEMU!
For help, type "help"
(nemu) log
Unknown command 'log'
(nemu) q
make: *** [/home/ubuntu/ics2022/nemu/scripts/native.mk:38: run] Error 1

报错的原因前面也提到过，那就是is_exit_status_bad函数会检查nemu_state.state的状态。只有在NEMU_QUIT或者NEMU_END并且halt返回值为0时，才算正常退出；如果非正常退出，main函数会返回一个非0值，make检测到可执行文件返回非0值后，就会报以上错误。

while make was building the targetruntests, one of the commands that it ran exited with an error code of1. In POSIX (and make),any exit code other than 0 is considered a failure; only 0 means that the command succeeded.

Link🔗：c - Makefile error that works fine in console - Stack Overflow

所以解决方案只需要在cmd_q函数中将nemu_state.state的状态设置为NEMU_QUIT

1
nemu_state.state = NEMU_QUIT;

cmd_si 单步执行

1
si命令格式：	si [N]

用strtok()提取参数字符串，然后用sscanf()将字符串转为整型，最后调用cpu_exec()单步执行

1
2
3
4
5
6
7
8
9
10
11
12
13
// $(NEMU_HOME)/src/monitor/sdb/sdb.c
static int cmd_si(char *args) {
  char *num_str = strtok(NULL, " ");
  int num = 0;
  if (num_str != NULL) {
    Assert(sscanf(num_str, "%d", &num), "The input step num is not a number");
  } else {
    /* no argument given, the default num of step is 1 */
    num = 1;
  }
  cpu_exec(num);
  return 0;
}

cmd_info r 打印寄存器

打印寄存器的功能实现在info命令当中，并需要参数r来指定。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// $(NEMU_HOME)/src/monitor/sdb/sdb.c
static int cmd_info(char *args) {
  char *arg = strtok(NULL, " ");
  if (strcmp(arg, "r") == 0) {
    /* info r : print the status of Rigister File*/
    isa_reg_display();
  } else if (strcmp(arg, "w") == 0) {
    /* info w : print the info of watch point*/
    print_watchpoint();
  } else {
    printf("command info need argument r or w\n");
  }
  return 0;
}

但显然寄存器是与ISA密切相关的，不同的ISA中寄存器的约定不一样，所以sdb为了屏蔽ISA的差异，定义了一个APIisa_reg_display()，功能是打印全部寄存器，并在不同的ISA中实现功能，这里以riscv32为例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// $(NEMU_HOME)/src/isa/riscv32/reg.c
const char *regs[] = {
  "0", "ra", "sp", "gp", "tp", "t0", "t1", "t2",
  "s0", "s1", "a0", "a1", "a2", "a3", "a4", "a5",
  "a6", "a7", "s2", "s3", "s4", "s5", "s6", "s7",
  "s8", "s9", "s10", "s11", "t3", "t4", "t5", "t6"
};

void isa_reg_display() {
  printf(ANSI_FMT("[Register status]", ANSI_BG_YELLOW) "\n");
  printf("Reg \tHex\t\tDec\n");
  printf("%-4s\t" FMT_WORD "\n", "PC", cpu.pc);
  for(int i = 0; i < MUXDEF(CONFIG_RVE, 16, 32); i++) {
    // printf("[%s] / [x%d] => " FMT_WORD "\n", reg_name(i), i, gpr(i));
    printf("%-4s%-4d" FMT_WORD "\t%-20d\n", reg_name(i), i, gpr(i), gpr(i));
  }
  return;
}

依次遍历全部寄存器，并打印寄存器的值即可，效果如下：

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
[Register status]
Reg 	Hex		   Dec
PC  	0x80000000
0   0   0x00000000	0                   
ra  1   0x00000000	0                   
sp  2   0x00000000	0                   
gp  3   0x00000000	0                   
tp  4   0x00000000	0                   
t0  5   0x00000000	0                   
t1  6   0x00000000	0                   
t2  7   0x00000000	0                   
s0  8   0x00000000	0                   
s1  9   0x00000000	0                   
a0  10  0x00000000	0                   
a1  11  0x00000000	0                   
a2  12  0x00000000	0                   
a3  13  0x00000000	0                   
a4  14  0x00000000	0                   
a5  15  0x00000000	0                   
a6  16  0x00000000	0                   
a7  17  0x00000000	0                   
s2  18  0x00000000	0                   
s3  19  0x00000000	0                   
s4  20  0x00000000	0                   
s5  21  0x00000000	0                   
s6  22  0x00000000	0                   
s7  23  0x00000000	0                   
s8  24  0x00000000	0                   
s9  25  0x00000000	0                   
s10 26  0x00000000	0                   
s11 27  0x00000000	0                   
t3  28  0x00000000	0                   
t4  29  0x00000000	0                   
t5  30  0x00000000	0                   
t6  31  0x00000000	0

cmd_x 扫描内存

1
x命令格式： x N Expr

由于目前还没有实现表达式求值的功能，所以先实现一个简单的版本：规定表达式EXPR中只能是一个十六进制数。

还是按照惯例通过strtok()提取字符串，然后可以通过sscanf()或strtol()将字符串转化为整型。

最后通过word_t vaddr_read(vaddr_t addr, int len)函数（读取以addr为起始地址，len个字节的虚拟内存）以十六进制形式输出连续的N个4字节

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// $(NEMU_HOME)/src/monitor/sdb/sdb.c
static int cmd_x(char *args) {
  char *N_str = strtok(NULL, " ");
  if (N_str == NULL) {
    printf("cmd_x Usage: x N Expr\n");
    return 0;
  }
  int32_t N = strtol(N_str, NULL, 10);
  char *addr_str = strtok(NULL, " ");
  if (addr_str == NULL) {
    printf("cmd_x Usage: x N Expr\n");
    return 0;
  }
  vaddr_t addr = strtol(addr_str, NULL, 16);
  printf(ANSI_FMT("[Memory status]", ANSI_BG_GREEN) "\n");
  printf("[ADDRESS] --> [VALUE]\n");
  for (int i = 0; i < N; i++) {
    printf("0x%08x : 0x%08x\n", addr, vaddr_read(addr, 4));
    addr += 4;
  }
  return 0;
}

表达式求值

为了方便使用, 我们还希望简易调试器能帮我们计算一些带有寄存器和内存的表达式. 所以你需要在简易调试器中添加表达式求值的功能

数学表达式

简单起见，首先考虑数学表达式的求值，也就是只有+ - * /、数字和括号的表达式

word_t expr(char *e, bool *success)函数为表达式求值的主函数，参数char *e为表达式字符换，参数bool *success指示求值是否成功。

该函数首先进行词法分析，生成token串（tokens为存储token串的数组，nr_token为其指针）；然后，通过eval()函数对0~nr_token范围内的token串进行求值；最后返回表达式的值。

1
2
3
4
5
6
7
8
word_t expr(char *e, bool *success) {
  *success = true;
  if (!make_token(e)) {
    *success = false;
    return 0;
  }
  return eval(0, nr_token);
}

词法分析

token是指有独立含义的子串，词法分析就是将表达式字符串转化为token串。

make_token()函数对传入的字符串进行词法分析。具体来说，通过while遍历字符串，通过正则表达式尝试匹配事先定义好的token规则。如果匹配成功，说明已经识别出这个token，只需要通过switch分别处理不同token类型即可。

如果全部字符串都成功匹配完，则返回true；否则，匹配失败，返回false

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
// $(NEMU_HOME)/src/monitor/sdb/expr.c
typedef struct token {
  int type;
  char str[32];
} Token;

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

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;

        switch (rules[i].token_type) {
          case TK_NOTYPE:
              break;
          case '+':
              tokens[nr_token++].type = '+';
              break;
          case '-':
              tokens[nr_token++].type = '-';
              break;
          case '*':
              tokens[nr_token++].type = '*';
              break;
          case '/':
              tokens[nr_token++].type = '/';
              break;
          case '(':
              tokens[nr_token++].type = '(';
              break;
          case ')':
              tokens[nr_token++].type = ')';
              break;
          case TK_EQ:
              tokens[nr_token++].type = TK_EQ;
              break;
          case TK_NEQ:
              tokens[nr_token++].type = TK_NEQ;
              break;
          case TK_DEC:
              tokens[nr_token].type = TK_DEC; 
              Assert(substr_len < 32, "length of int is too long (> 31)");
              strncpy(tokens[nr_token].str, substr_start, substr_len);
              tokens[nr_token++].str[substr_len] = '\0';
              break;
          default:
              TODO();
              break;
        }
        break;
      }
    }

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

正则表达式

词法分析借助正则表达式进行

标准的C和C++都不支持正则表达式，需要使用<regex.h>库。C语言处理正则表达式常用的函数有regcomp()、regexec()、regfree()和regerror()。

通过C语言使用正则表达式参考链接：C语言正则表达式使用详解_c语言 正则提取字符串-CSDN博客

使用正则表达式步骤：

  1. 编译正则表达式 regcomp()
  2. 匹配正则表达式 regexec()
  3. 释放正则表达式 regfree()

1. 编译正则表达式

1
int regcomp(regex_t *compiled, const char *pattern, int cflags)

这个函数把指定的正则表达式pattern编译成一种特定的数据格式（regex_t），这样可以使匹配更有效率。

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
// $(NEMU_HOME)/src/monitor/sdb/expr.c
static struct rule {
  const char *regex;
  int token_type;
} rules[] = {
  {" +", TK_NOTYPE},    // spaces

  {"\\+", '+'},         // plus (the first \ is to escape the second \ in C, the second \ is to escape the + in regex)
  {"\\-", '-'},         // minus
  {"\\*", '*'},         // mutiply
  {"\\/", '/'},         // divide

  {"\\(", '('},         // left bracket
  {"\\)", ')'},         // right bracket

  {"[1-9]+[0-9]*", TK_DEC},  // decimal integer
};

#define NR_REGEX ARRLEN(rules)

static regex_t re[NR_REGEX] = {};

void init_regex() {
  int i;
  char error_msg[128];
  int ret;

  for (i = 0; i < NR_REGEX; i ++) {
    ret = regcomp(&re[i], rules[i].regex, REG_EXTENDED);
    if (ret != 0) {
      regerror(ret, &re[i], error_msg, 128);
      panic("regex compilation failed: %s\n%s", error_msg, rules[i].regex);
    }
  }
}

2. 匹配正则表达式

1
int regexec (regex_t *compiled, char *string, size_t nmatch, regmatch_t matchptr [], int eflags)

当我们编译好正则表达式后，就可以用regexec()匹配我们的目标文本串了，执行成功返回０。

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

regmatch_t 是一个结构体数据类型，在regex.h中定义： 

1
2
3
4
5
typedef struct
{
   regoff_t rm_so;
   regoff_t rm_eo;
} regmatch_t;

成员rm_so 存放匹配文本串在目标串中的开始位置，rm_eo 存放结束位置。

求值

static word_t eval(int p, int q)函数根据数学表达式的BNF对表达式进行递归求值

数学表达式的BNF为

1
2
3
4
5
6
7
<expr> ::= 
    <decimal-number>
  | "(" <expr> ")"          # 在表达式两边加个括号也是表达式
  | <expr> "+" <expr>       # 两个表达式相加也是表达式
  | <expr> "-" <expr>       # minus
  | <expr> "*" <expr>       # mutiply
  | <expr> "/" <expr>       # divide

使用两个整数p和q来指示这个子表达式的开始位置和结束位置，eval的伪代码可表示为

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
eval(p, q) {
  if (p > q) {
    // 表达式求值异常
  }
  else if (p == q) {
    // 表达式仅为一个token，应该是一个数字
  }
  else if (check_parentheses(p, q) == true) {
    // 如果表达式被一对括号包围，那么去掉括号即可
    return eval(p + 1, q - 1);
  }
  else {
    // 此时表达式可以分为多个子表达式，需要寻找 “主运算符”，再将子表达式按照主运算符进行运算
    int op = find_main_op(p, q);
    word_t val1 = eval(p, op-1);
    word_t val2 = eval(op+1, q);
    switch (tokens[op].type) {
      case '+': return val1 + val2;
      case '-': return val1 - val2;
      case '*': return val1 * val2;
      case '/': return val1 / val2;
    }
  }
}

检查表达式是否被括号包围

首先，检查表达式的首尾是否被括号包围

然后，检查括号是否闭合。遍历表达式，用变量diff表示左括号与右括号数量的差值，如果有以下情况，则表达式括号未闭合：

  • 遍历过程中出现右括号多于左括号，即diff<0
  • 遍历结束后左右括号的数量不相等，即diff!=0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
// $(NEMU_HOME)/src/monitor/sdb/expr.c
static bool check_parentheses(int p, int q) {
  // Step 1, check if the entire expr is surrounded by ()
  if (!(tokens[p].type == '(' && tokens[q].type == ')')) return false;
  // Step 2, check if the expr is closed by ()
  int diff = 0;
  for (int i = p; i <= q; i++) {
    if (tokens[i].type == '(') diff++;
    if (tokens[i].type == ')') diff--;
    if (diff < 0) return false;
  }
  if (diff != 0) return false;
  return true;
}

寻找主运算符

主运算符有以下规则：

  • 非运算符的token不是主运算符.
  • 出现在一对括号中的token不是主运算符. 注意到这里不会出现有括号包围整个表达式的情况, 因为这种情况已经在check_parentheses()相应的if块中被处理了.
  • 主运算符的优先级在表达式中是最低的. 这是因为主运算符是最后一步才进行的运算符.
  • 当有多个运算符的优先级都是最低时, 根据结合性, 最后被结合的运算符才是主运算符. 一个例子是1 + 2 + 3, 它的主运算符应该是右边的+.

find_main_op()函数的实现与以上规则一致。该函数从左向右遍历token[p~q]寻找主运算符，并记录每个可能的主运算符的位置和优先级，如果右侧的主运算符优先级小于等于左侧，则右侧为主运算符。如此一来，保证了：优先级最低的为主运算符，优先级相同时最右侧的为主运算符

实现了一个返回C语言规范中运算符优先级的函数static int get_op_priority(int op)，返回的值越大，表示优先级越低

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
// $(NEMU_HOME)/src/monitor/sdb/expr.c
static int get_op_priority(int op) {
  switch(op) {
    case TK_NEG:
    case TK_DEREF:
      return 2;
    case '*':
    case '/':
      return 3;
    case '+':
    case '-':
      return 4;
    case TK_EQ:
    case TK_NEQ:
      return 7;
    case TK_L_AND:
      return 11;
    case TK_L_OR:
      return 12;
    default:
      return 0;
  }
}

static int find_main_op(int p, int q) {
  int op = -1;
  int last_priority = 0;
  for (int i = p; i <= q; i++) {
    int op_type = tokens[i].type;
    int op_priority = get_op_priority(op_type);
    // Log("[%d] Priority:%d", op_type, op_priority);
    // if the token is not op type, it can not be the main op 
    if (op_priority == 0) continue;
    // if the op is surrounded by bracket, it can not be the main op
    if (!surrounded_by_bracket(i, p, q)) continue;
    // Consider the op type priority and the sequence priority between this op and last op
    // in case the op priority is different, the low priority op will be the domain op
    if (op_priority > last_priority) {
      last_priority = op_priority;
      op = i;
    }
    // in case the priority is the same, the right one will be the domain op
    else if (op_priority == last_priority) {
      op = i;
    }
  }
  Assert(op >= 0, "Find No main op");
  return op;
}

检查运算符是否被括号包围

static bool surrounded_by_bracket(int x, int p, int q)用于检查位于x位置的运算符在p~q的表达式中是否被括号包围

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// $(NEMU_HOME)/src/monitor/sdb/expr.c
static bool surrounded_by_bracket(int x, int p, int q) {
  int left_bracket = 0;
  int right_bracket = 0;
  for (int i = x - 1; i >= p; i--) {
    if (tokens[i].type == '(') left_bracket++;
    if (tokens[i].type == ')') left_bracket--;
  }
  for (int i = x + 1; i <= q; i++) {
    if (tokens[i].type == ')') right_bracket++;
    if (tokens[i].type == '(') right_bracket--;
  }
  // Log("left_bracket = %d, right_bracket = %d\n", left_bracket, right_bracket);
  if (left_bracket == 0 && right_bracket == 0) return true;
  Assert(left_bracket == right_bracket, "The bracket is not closed!");
  return false;
}

首先，由于check_parentheses()函数已经将“表达式被括号包围”的情况剔除了，因此可以不用考虑。

向左遍历从x-1到p的所有token，计算净左括号的数量；向右遍历从x+1到q的所有token，计算净右括号的数量

  • 如果净左括号与净右括号数量均为0，则认为该运算符不在一对括号中
  • 如果净左括号与净右括号数量相等但不为0，则认为运算符在净左（右）括号数量的括号中
  • 如果净左括号与净右括号数量不相等，则括号未闭合

举例说明：

1
(1+2) * ((3-4))
运算符 净左括号 净右括号
+ 1 1
* 0 0
- 2 2

扩展表达式

目前，表达式只能进行四则运算，这对调试器来说是很受限的。这是因为很多情况下调试器需要借助寄存器和内存的值来进行表达式计算，并且还需要识别十六进制数

扩展十六进制

扩展逻辑运算

扩展寄存器

扩展解引用

cmd_p 表达式求值