NJU ICS：PA(Programming Assignment) 1 思路总结
在此对PA1实验中的任务进行思路上的总结。
框架代码理解
nemu
├── configs # 预先提供的一些配置文件
├── include # 存放全局使用的头文件
│ ├── common.h # 公用的头文件
│ ├── config # 配置系统生成的头文件, 用于维护配置选项更新的时间戳
│ ├── cpu
│ │ ├── cpu.h
│ │ ├── decode.h # 译码相关
│ │ ├── difftest.h
│ │ └── ifetch.h # 取指相关
│ ├── debug.h # 一些方便调试用的宏
│ ├── device # 设备相关
│ ├── difftest-def.h
│ ├── generated
│ │ └── autoconf.h # 配置系统生成的头文件, 用于根据配置信息定义相关的宏
│ ├── isa.h # ISA相关
│ ├── macro.h # 一些方便的宏定义
│ ├── memory # 访问内存相关
│ └── utils.h
├── Kconfig # 配置信息管理的规则
├── Makefile # Makefile构建脚本
├── README.md
├── resource # 一些辅助资源
├── scripts # Makefile构建脚本
│ ├── build.mk
│ ├── config.mk
│ ├── git.mk # git版本控制相关
│ └── native.mk
├── src # 源文件
│ ├── cpu
│ │ └── cpu-exec.c # 指令执行的主循环
│ ├── device # 设备相关
│ ├── engine
│ │ └── interpreter # 解释器的实现
│ ├── filelist.mk
│ ├── isa # ISA相关的实现
│ │ ├── mips32
│ │ ├── riscv32
│ │ ├── riscv64
│ │ └── x86
│ ├── memory # 内存访问的实现
│ ├── monitor
│ │ ├── monitor.c
│ │ └── sdb # 简易调试器
│ │ ├── expr.c # 表达式求值的实现
│ │ ├── sdb.c # 简易调试器的命令处理
│ │ └── watchpoint.c # 监视点的实现
│ ├── nemu-main.c # 你知道的…
│ └── utils # 一些公共的功能
│ ├── log.c # 日志文件相关
│ ├── rand.c
│ ├── state.c
│ └── timer.c
└── tools # 一些工具
├── fixdep # 依赖修复, 配合配置系统进行使用
├── gen-expr
├── kconfig # 配置系统
├── kvm-diff
├── qemu-diff
└── spike-diff
顺利的运行
- Remove Assert(0)：
根据报错信息将monitor.c中对应的assert语句移除即可。 - 优美的退出：
因为是退出NEMU时报错，所以首先在NEMU的main.c中找报错原因，发现最后返回了is_exit_status_bad()这一函数。转到定义后发现默认返回值是1，根据函数的具体内容对sdb.c中的cmd_q函数进行调整后问题顺利解决。
PA1.1 基础设施
PA1.1.1 单步执行
根据讲义中的提示，单步执行要求我们实现si命令，并且根据si命令后面的argument执行具体步数。讲义在RTFSC中提到cpu-exec.c模拟了CPU运行，转到其中能够轻易发现相关函数，只需要传入对应参数就可以实现要求的功能。于是在sdb.c中实现了相应的cmd_si函数，值得一提的是用sscanf将指针args转化为了可以使用的变量。
PA1.1.2 打印寄存器
要求我们实现info r打印32个寄存器的值。根据提供的API文档可以发现有关寄存器的定义在isa-reg.h中，RTFSC后发现寄存器的值是gpr表示，于是在reg.c中实现了对应的API，即isa_reg_display()。然后在sdb.c中实现对应的命令。值得一提的是cmd_info在后续实现监视点的时候还会用到。
PA1.1.3 扫描内存
要求我们实现info x，给定指定的其实内存和要打印的内存个数，输出内存数据。根据RTFSC中的提示在vaddr.c中找到了相应读取内存的函数vaddr_read()，然后在sdb.c中通过循环实现具体指令，并且设定打印内存长度为4。
PA1.2 表达式求值
PA1.2.1 词法分析
在表达式求值中只允许出现的token类型有十进制整数，加减乘除，括号和空格串。expr.c中的enum编写了用于识别这些token的类型，具体识别规则见“正则表达式速览”。同一文件中的init_regex()函数会将这些规则编译成被库函数使用的pattern匹配信息，如果正则表达式语法有问题会触发assertion fail。
make_token()函数用于识别表达式中的token，用position来表示当前处理的位置，按照顺序用不同的规则匹配当前位置的字符串，如果匹配成功log()则会输出识别成功的token类型，后面通过nr_token指示已经被识别出的token数目为当前正在处理到的token赋值，其中加减乘除此类只需要记录token类型，而数字则还需要记录token的具体内容，这个用substr_start和substr_len进行具体内容的赋值。
PA1.2.2 递归求值
首先在sdb.c中实现cmd_p的指令，跳转到expr.c中的expr函数，再对expr函数进行具体编写，为了方便我重新写了一个新函数并在expr()中调用。新求值函数eval首先判断token的首位，eval的递归采用两个位置变量p和q来表示正在处理的token位置。如果末位token的位置p小于首位token的位置q则判断表达式不合法；如果p等于q则说明递归到了某一个具体的数字，这个时候要对该单一token进行类型判断，如果不是数字类型则输出报错信息，反之直接返回数字的值。值得注意的是此处不能直接返回tokens结构体中的str部分，应使用strtol将token的具体内容转换成十进制整数后再返回。
如果p < q则先进行括号判断，此处我又调用了自己写的check_parentheses()函数。函数结构非常简单，如果此时的位置变量p和q代表的首位token和末位token分别是正括号和反括号，则开始正式判断。使用一个计数变量cnt来表示当前括号的个数，如果是正括号则加一，反括号则减一。当cnt为零时判断当前处理的token是否是末尾token，以此确定首位token和末尾token的正反括号是成对的。因为首位是正括号且末位是反括号的情况有两种：(…+…)+(…+…)和(…+(…+…))，前者实际上并不需要check_parentheses，因为主运算符仍然在括号外面。因此如果首位和末位括号成对则返回true。最后如果cnt不为零的话返回false。在eval()中如果check_parentheses()返回值为真，那么将p设为p+1，q设为q-1进行下一层的递归。
如果上面三个条件都没有满足则进行主运算符的判断，在此又要调用自己写的find_major()函数。讲义中提到了主运算符的几个特点：主运算符一定是运算符(某种意义上来说是句废话)、出现在一对括号中的token不是主运算符、主运算符的优先级在表达式中是最低的、当有多个运算符的优先级都是最低时最后被结合的运算符才是主运算符。根据这几条规则我们就可以进行具体函数的编写，首先是定义计数变量cnt、用于指示当前运算符优先级的op_type和主运算符的位置变量position，我们用for循环进行p和q之间主运算符的判断。如果判断过程中遇到数字类型的token则直接跳过(根据第一条规则)，遇到正反括号则仿照check_parentheses中的思路利用cnt进行判断。如果是正括号则cnt++。是反括号则cnt–，并且判断cnt是否为零，如果是零的话find_major()直接返回-1，因为表达式不合法。在反括号的情况下判断是因为此情况下cnt为零只有两种情况：缺少了一个正括号或者多了一个反括号。比在正括号的情况下判断更加方便。如果cnt>0则continue。然后进行运算符的判断，这里新建一个比较变量tmp_type，初始值为零，根据运算符类型赋值，加减赋2，乘除为1(因为在表达式中运算符的优先级越低越可能成为主运算符，所以在这里优先级更高的被赋的值反而更低)。最后进行op_type和tmp_type的判断，如果tmp_type大于op_type则将其赋值给op_type，并且记录此时的位置。如果tmp_type等于op_type同样将其赋值给op_type(根据第四条规则)。循环结束后先进行cnt的判断，然后返回position变量。
找完主运算符后就可以进行具体值的计算，设主运算符左边的变量为val1，右边为val2，继续递归，直到递归到
等到eval()函数计算完表达式的值后expr()函数就会接收到其返回的值，expr()函数会直接将收到的值返回到sdb.c中的cmd_p()，然后输出到屏幕上。
PA1.3 监视点
PA 1.3.1 拓展表达式求值
拓展表达式求值新增了十六进制数、负数、打印寄存器、指针解引用和与或非、等于、不等于、大于、小于、大于等于、小于等于运算。与运算、或运算、等于、不等于、大于、小于、大于等于、小于等于的实现逻辑很简单。先编写匹配规则和make_token()，然后在find_major()中增加计算优先级，这些运算的优先级都是最低的，所以在find_major()中的匹配优先度度最高。最后在eval()函数中增加case计算即可。
真正麻烦的是十六进制数，打印寄存器，指针解引用，负数和非运算。其中负数和指针解引用还要更加麻烦，所以先阐释其他运算的实现。在这里我识别十六进制数的思路是匹配0x，并且在TK_NUM的匹配规则中加A-F，如此就可以将0x是为一个一元运算符进行处理，这里要注意0x的匹配规则要高于TK_NUM的匹配规则，否则就会出现只能匹配到0而不能匹配到x的问题。识别完成后正常编写make_token()。然后在find_major()中编写优先级，一元运算符的计算优先级都是最高的，所以在find_major()中赋最低的值。最后在eval()中返回十进制的值，这里我调用了自己写的一个进制转换函数。主要思路就是按位取余，然后乘以该位的位权，累加到Dec变量中，也就是最后的十进制结果。至此十六进制数的实现已经完成。
然后是打印寄存器，仿照十六进制数的思路进行处理，一直到eval()函数部分，这里要返回的值就是cpu.gpr[i]。非运算同理，eval()函数部分返回的值是!val2。
负数和指针解引用实际上使用的符号都是" - “或” * “，所以在make_token()阶段并不能将其和减法和乘法区分开来。所以我们编写特殊的check_unary()函数来检验。check_unary()函数应该放在expr()函数的make_token()后面。其主要思路就是判定当前处理的token类型是不是” * “或” - "，如果是的话进行进一步判断，如果token编号是0则证明该运算符是表达式的第一个，直接将其token类型修改为负数或者指针解引用(注意这里必须要这么判断，如果全部使用后面那条规则判断的话会产生结构体访问越界)，如果token编号不为零的话就判断前一个token的类型是不是数字或者反括号，如果不是的话证明运算符是一元运算符，则将token类型修改为负数或者指针解引用。然后仿照之前对一元运算符的处理即可，eval()函数中负数类型直接返回-value，指针解引用类型则仿照PA 1.1.3进行处理即可。
PA 1.3.2 监视点的管理
开始之前要为监视点结构体新增两个变量，一个是char *类型的expr和int类型的value。
监视点的管理包括新建监视点new_wp()和删除监视点free_wp()。在new_wp()中首先要判断监视点池是否为空，然后建立一个新的监视点结构体，将空闲监视点赋值给新建立的结构体，然后将空闲监视点向后移动一位，将head(正在处理的监视点)设定为新建立的监视点。
在free_wp()中首先判断要删除的监视点是不是head，如果是的话就直接将head设为NULL。新建一个监视点结构体flag，将其设为监视点池的第一个监视点，也就是监视点0，一个一个往后推，直到推到要删除的监视点的前一个监视点，将flag的下一个设为要删除的监视点的下一个，也就是暂时将要删除的监视点抽出监视点池。
PA 1.3.3 监视点功能的实现
首先还是在sdb.c中编写相关的指令(info w、cmd_w、cmd_d)。info w的实现很简单，就是新增一个条件判断，如果输入为w的话调用display_wp()函数(具体函数一会在watchpoint.c中实现)。
然后编写cmd_w指令，相关细节仿照PA1，将要计算的表达式读入并调用expr()计算，将计算结果赋值给result变量，再将表达式和result传给set_wp()函数(同样一会在watchpoint.c中实现)。
cmd_d指令也仿照PA1进行编写，将要删除的监视点编号传入delete_wp()函数即可。
然后是watchpoint.c中监视点功能的具体实现，包括set_wp()、delete_wp()、display_wp()和check_wp()。set_wp()的实现很简单，先建立一个新的监视点结构体，将接收到的表达式用strndup函数复制到新监视点的expr部分，将result赋值给新监视点的value部分，最后输出监视点信息。delete_wp()首先判断输入编号是否小于NR_WP，这里我用assert实现。然后建立三个监视点结构体，分别是要删除的监视点，要删除的监视点的前一个监视点和要删除的监视点的后一个监视点。建立完后先输出要删除监视点的具体信息，然后将要删除的监视点传入free_wp()，因为在free_wp()函数中将要删除的监视点抽出了监视点链表，所以调用完函数后要将要删除的监视点的expr部分设为NULL，将要删除的监视点的前一个监视点只想删除的监视点，删除的监视点指向删除的监视点的后一个监视点，到这里删除监视点的操作就正式完成了。
下一个是display_wp()函数的编写，首先新建一个监视点结构体，将其设置为监视点池中的第一个监视点，然后用while循环(循环条件设置为新建立的监视点是否成立)打印监视点信息，在循环的最后将监视点设置为下一个监视点即可。
最后是check_wp()的编写，首先还是新建一个监视点结构体，将其设置为监视点池中的第一个监视点，然后用while循环处理(循环条件设置为新建的监视点不为head的下一个监视点)，在循环中调用expr()函数计算表达式的值，如果表达式的值发生变化则输出相关信息，在循环的最后将监视点设置为下一个监视点。最后将check_wp()放进cpu-exec.c的execute()中，每执行一条指令就检查一次。