また夏を追う

最近的笔记

NJU ICS PA-1

✏️ 🔧 20 min read

计算机可以没有寄存器吗? (建议二周目思考)

如果没有寄存器, 计算机还可以工作吗? 如果可以, 这会对硬件提供的编程模型有什么影响呢?

就算你是二周目来思考这个问题, 你也有可能是第一次听到”编程模型”这个概念. 不过如果一周目的时候你已经仔细地阅读过 ISA 手册, 你会记得确实有这么个概念. 所以, 如果想知道什么是编程模型, RTFM 吧.

kconfig 生成的宏与条件编译

我们已经在上文提到过, kconfig 会根据配置选项的结果在 nemu/include/generated/autoconf.h中定义一些形如CONFIG_xxx的宏, 我们可以在 C 代码中通过条件编译的功能对这些宏进行测试, 来判断是否编译某些代码. 例如, 当CONFIG_DEVICE这个宏没有定义时, 设备相关的代码就无需进行编译.

为了编写更紧凑的代码, 我们在nemu/include/macro.h中定义了一些专门用来对宏进行测试的宏. 例如IFDEF(CONFIG_DEVICE, init_device());表示, 如果定义了CONFIG_DEVICE, 才会调用init_device()函数; 而MUXDEF(CONFIG_TRACE, "ON", "OFF")则表示, 如果定义了CONFIG_TRACE, 则预处理结果为"ON"("OFF"在预处理后会消失), 否则预处理结果为"OFF".

这些宏的功能非常神奇, 你知道这些宏是如何工作的吗?

预处理器解析替换

为什么全部都是函数?

阅读init_monitor()函数的代码, 你会发现里面全部都是函数调用. 按道理, 把相应的函数体在init_monitor()中展开也不影响代码的正确性. 相比之下, 在这里使用函数有什么好处呢?

面向过程编程的一种编程范式

参数的处理过程

另外的一个问题是, 这些参数是从哪里来的呢?

命令行接收的参数

究竟要执行多久?

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

潜在的威胁 (建议二周目思考)

“调用cpu_exec()的时候传入了参数-1”, 这一做法属于未定义行为吗? 请查阅 C99 手册确认你的想法.

谁来指示程序的结束?

在程序设计课上老师告诉你, 当程序执行到main()函数返回处的时候, 程序就退出了, 你对此深信不疑. 但你是否怀疑过, 凭什么程序执行到main()函数的返回处就结束了? 如果有人告诉你, 程序设计课上老师的说法是错的, 你有办法来证明/反驳吗? 如果你对此感兴趣, 请在互联网上搜索相关内容.

有始有终 (建议二周目思考)

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

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

sdb 实现

帮助(1)helphelp打印命令的帮助信息
继续运行(1)cc继续运行被暂停的程序
退出(1)qq退出 NEMU
单步执行si [N]si 10让程序单步执行N条指令后暂停执行, 当N没有给出时, 缺省为1
打印程序状态info SUBCMDinfo r info w打印寄存器状态 打印监视点信息
扫描内存(2)x N EXPRx 10 $esp求出表达式EXPR的值, 将结果作为起始内存 地址, 以十六进制形式输出连续的N个 4 字节
表达式求值p EXPRp $eax + 1求出表达式EXPR的值, EXPR支持的 运算请见调试中的表达式求值小节
设置监视点w EXPRw *0x2000当表达式EXPR的值发生变化时, 暂停程序执行
删除监视点d Nd 2删除序号为N的监视点

单步执行

static int cmd_si(char *args) {
  int step = args == NULL ? 1 : atoi(args);
  if (step <= 0) {
    return -1;
  }
  cpu_exec(step);
  return 0;
}

打印寄存器

static int cmd_info(char *args) {
  char subcmd = *args;
  switch (subcmd) {
  case 'r':
    isa_reg_display();
    break;
  case 'w':
    TODO();
    break;
  default:
    return -1;
  }
  return 0;
}

扫描内存

static int cmd_scan(char *args) {
  char *argn = strtok(args, " ");
  char *argexpr = argn + strlen(argn) + 1;
  if (argn == NULL || argexpr == NULL) {
    return -1;
  }
  int nbyte = atoi(argn);
  if (nbyte < 0) {
    return -1;
  }
  // TODO implement expr function
  vaddr_t addr = 0x80000000;
  for (int i = 0; i < nbyte; i++) {
    vaddr_t current_addr = addr;
    printf("0x%08x: 0x%08x\n", current_addr, vaddr_read(current_addr, 4));
    current_addr += 4;
  }
  return 0;
}

表达式求值

词法分析

在这里，由于表达式不止数值类型一种，因此在设计 TOKEN 类型时多加了寄存器与变量类型，设计如下：

enum {
  TK_NOTYPE = 256,
  TK_EQ,
  TK_INT,
  TK_OP,
  TK_REG,
  TK_VAR


};


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


    {" +", TK_NOTYPE},           // spaces
    {"\\t", TK_NOTYPE},          // tab
    {"\\+", TK_OP},              // plus
    {"==", TK_EQ},               // equal
    {"\\(", '('},                // '('
    {"\\)", ')'},                // ')'
    {"-", TK_OP},                // '-'
    {"\\*", TK_OP},              // '*'
    {"/", TK_OP},                // '/'
    {"[0-9]+", TK_INT},          // integer
    {"\\$[a-zA-Z0-9]+", TK_REG}, // reg
    {"[a-zA-Z_]+", TK_VAR},      // variable
};

由于写过编译原理，这部分还算简单，需要注意的是我们对 rules 的排序必须严格，因为是通过 switch 语句来判断的。

随后，我们对字符串流一一判断，然后存入到 tokens 列表中：

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: simplify the code
        switch (rules[i].token_type) {
        case TK_NOTYPE:
          break;
        case ')':
          tokens[nr_token].type = ')';
          strncpy(tokens[nr_token].str, substr_start, substr_len);
          tokens[nr_token].str[substr_len] = '\0';
          ++nr_token;
          break;
        case '(':
          tokens[nr_token].type = '(';
          strncpy(tokens[nr_token].str, substr_start, substr_len);
          tokens[nr_token].str[substr_len] = '\0';
          ++nr_token;
          break;
        case TK_EQ:
          tokens[nr_token].type = TK_EQ;
          strncpy(tokens[nr_token].str, substr_start, substr_len);
          tokens[nr_token].str[substr_len] = '\0';
          ++nr_token;
          break;
        case TK_OP:
          tokens[nr_token].type = TK_OP;
          strncpy(tokens[nr_token].str, substr_start, substr_len);
          tokens[nr_token].str[substr_len] = '\0';
          ++nr_token;
          break;
        case TK_VAR:
          tokens[nr_token].type = TK_VAR;
          strncpy(tokens[nr_token].str, substr_start, substr_len);
          tokens[nr_token].str[substr_len] = '\0';
          ++nr_token;
          break;
        case TK_REG:
          tokens[nr_token].type = TK_REG;
          strncpy(tokens[nr_token].str, substr_start, substr_len);
          tokens[nr_token].str[substr_len] = '\0';
          ++nr_token;
          break;
        case TK_INT:
          tokens[nr_token].type = TK_INT;
          if (substr_len <= 32) {
            strncpy(tokens[nr_token].str, substr_start, substr_len);
            tokens[nr_token].str[substr_len] = '\0';
          } else {
            // TODO: handle buffer overflow
            printf("Expr %.*s is too long to handle", substr_len, substr_start);
            return false;
          }
          ++nr_token;
        default:
          break;
        }


        break;
      }
    }


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


  return true;
}

对于超过 位（超过 str 数组长度，也就是超过缓冲区大小）的内容这里没有处理，思考如何处理缓冲区溢出的情况

递归求值

处理完 token 后，我们开始进行递归求值，实际上文档写的很清楚，包括其具体框架都已给出，我们需要注意的有两个函数：

  1. check_parentheses(int p, int q, bool *success)
  2. find_main_op(int p, int q, bool *success)

第一个函数的行为是：消除由 p 到 q 的 token 所组成表达式的 最外层 括号，并判断括号序列是否合法

第二个函数的行为是：找到主操作符，其方法在文档以给出，记得重点为 优先级最低

在这里我们还需要实现关于负数的操作，我的做法很简单，在 eval 中进行判断是否当前所求值为负数（因为传入的字符流一定存在一个 - 符号）

因此，其具体实现为：

bool check_parentheses(int p, int q) {
  if (tokens[p].type == '(' && tokens[q].type == ')') {
    int stack = 0;
    for (int i = p; i <= q; i++) {
      if (tokens[i].type == '(') {
        stack++;
      } else if (tokens[i].type == ')') {
        if (stack <= 0) {
          return false;
        }
        stack--;
      }
    }
    return stack == 0 && tokens[p].type == '(' && tokens[q].type == ')';
  }
  return false;
}


int find_main_op(int p, int q, bool *success) {
  int main_op = 3, main_op_idx = -1, stack = 0;
  for (int i = p; i <= q; i++) {
    if (tokens[i].type == TK_OP || tokens[i].type == '(' ||
        tokens[i].type == ')') {
      if (tokens[i].type == '(') {
        stack++;
        continue;
      } else if (tokens[i].type == ')') {
        if (stack <= 0) {
          return -1;
        }
        stack--;
        continue;
      }
      if (stack > 0) {
        continue;
      }
      int op_level = 0;
      if (tokens[i].str[0] == '+' || tokens[i].str[0] == '-') {
        op_level = 1;
      } else if (tokens[i].str[0] == '*' || tokens[i].str[0] == '/') {
        op_level = 2;
      } else {
        *success = false;
        printf("Invalid operator %s\n", tokens[i].str);
        return -1;
      }


      if (op_level < main_op) {
        main_op = op_level;
        main_op_idx = i;
      }
    }
  }
  if (stack) {
    success = false;
    return -1;
  }
  return main_op_idx;
}

此 eval 函数如下：

word_t eval(int p, int q, bool *success) {
  if (p > q) {
    *success = false;
    return 0;
  } else if (p == q) {


    int idx = p;
    if (tokens[idx].type == TK_INT) {
      return atoi(tokens[idx].str);
    } else if (tokens[idx].type == TK_REG) {
      *success = true;
      return isa_reg_str2val(tokens[idx].str, success);
    } else if (tokens[idx].type == TK_VAR) {
      // TODO: handle variable type
      return 0;
    }


  } else if (check_parentheses(p, q) == true) {
    return eval(p + 1, q - 1, success);
  } else if (tokens[p].str[0] == '-' && p == q - 1) {
    *success = true;
    return -atoi(tokens[p + 1].str);
  } else {
    int op = find_main_op(p, q, success);
    int val1 = eval(p, op - 1, success);
    int val2 = eval(op + 1, q, success);


    if (!success) {
      return 0;
    }


    switch (tokens[op].str[0]) {
    case '+':
      return val1 + val2;
    case '-':
      return val1 - val2;
    case '*':
      return val1 * val2;
    case '/':
      if (!val2) {
        success = false;
        printf("divided by zero\n");
        return 0;
      }
      return (sword_t)val1 / (sword_t)val2;
    }
  }
  return 0;
}

成功时需要将 success 设置为 true，但感觉在最后处理是否能够成功计算时不太对，可能还需要改进

🕸️ 关系图谱