Yanyan's Wiki 软件工程研究入门 (2022)

M4: C Real-Eval-Print-Loop (crepl)

⏰ 截止日期

Soft Deadline: 2022 年 5 月 8 日 23:59:59。

你需要首先阅读实验须知

在命令行中 git pull origin M4 下载框架代码。

⚠️ 特别注意

在本实验中,我们要求你实现 REPL,即主进程能获得所有表达式的值,因此请保证你在主进程打印表达式的值 (防止你把所有表达式拼接起来成一个程序打印)。

OS2022-M4 提交结果

1. 背景

大家一定很熟悉编程语言提供的交互式 read-eval-print-loop (REPL),更俗一点的名字就是 “交互式的shell”。例如我们在课堂上展示的 Python Shell,可以快速帮助大家解决高等数学作业、高精度计算等烦恼:

现代程序设计语言通常都会提供交互式的模式,方便日常使用,包非解释型的程序设计语言也提供类似的设施,例如 Scala REPL、go-eval 等——当然也包括我们的 UNIX Shell!

在学习过动态链接和加载之后,你会预期 C 同样也可以实现 “交互式” 的 shell,支持即时定义函数,而且能计算 C 表达式的数值。如果你输入一行代码,比如strlen("Hello World"),这段代码会经历 gcc 编译、动态加载、调用执行,最终把代码执行得到的数值 11 打印到屏幕上。这就是本实验的内容。

2. 实验描述

crepl - 逐行从 stdin 中输入,根据内容进行处理:

  • 如果输入的一行定义了一个函数,则把函数编译并加载到进程的地址空间中;
  • 如果输入是一个表达式,则把它的值输出。

总览

crepl

描述

解释执行每一行标准输入中的 C “单行” 代码 (假设我们只使用 int 类型,即所有输入的表达式都是整数;定义函数的返回值也永远是整数),分如下两种情况:

  • 函数总是以 int 开头,例如
    int fib(int n) { if (n <= 1) return 1; return fib(n - 1) + fib(n - 2); }
    

函数接收若干 int 类型的参数,返回一个 int 数值。如果一行是一个函数,我们希望它将会经过 gcc 编译,并被加载到当前进程的地址空间中。函数可以引用之前定义过的函数。

  • 如果一行不是以 int 开头,我们认为这一行是一个 C 语言的表达式,其类型为 int,例如
    1 + 2 || (fib(3) * fib(4))
    

函数和表达式均可以调用之前定义过的函数,但不允许访问全局的状态 (变量) 或调用标准 C 中的函数。如果一行既不是合法的函数 (例如调用了不允许调用的函数),也不是合法的表达式,crepl 可以不保证它们执行的结果 (不一定要报告错误,例如你的程序依然可以照常编译或执行,但你的程序要尽量不会 crash);重复定义重名函数你也可以当做 undefined behavior 不必做出过多处理——我们的测试用例中没有这样的情况。

以下是我们的参考实现,它调用了一些外挂程序在终端里实现了语法高亮。你完全没有做这件事情的必要——我们的环境里没有你需要的运行库,因此会导致你无情的 Compile Error 或 Wrong Answer。如果你使用外挂,一个更好的习惯 (也是编写软件常见的做法) 是在运行时检查外挂是否存在。如果存在则调用;如果不存在则直接输出没有外挂非高亮的版本。

当然,和之前的实验一样,我们对大家只有最简的实验要求:你只要你为每一个函数或表达式输出一行即可,例如你可以把你的 crepl 实现成这样:

$ ./crepl-64
int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
OK.
gcd(256, 144) * gcd(56, 84)
= 448.

这个实验表明,编译和解释并没有明确的边界——在 OpenJDK 的实现中,即便是 “解释器” 也是编译的 (只是没有经过优化)。动态 (just-in-time) 技术在程序运行时 (而非程序执行前) 进行编译,并将编译得到的二进制代码 (指令/数据) 动态加载。其中最成功的案例之一是 Sun (现在是 Oracle) 的 Java 虚拟机 HotSpot (现在是OpenJDK的一部分),它使 Java 彻底摆脱了 “性能低下” 的诟病,也是引领 Web 热潮的核心后端技术。另一个最成功的案例是 JavaScript 的 V8 引擎。借助 Webkit/v8,Chrome 成功地把微软公司的 Internet Explorer 拖下神坛,并且奠定了 Google 在互联网技术领域的霸主地位。

3. 正确性标准

你只要能正确解析单行的函数 (以 int 开头),并且默认其他输入都是表达式即可。我们可能会输入不合法的 C 代码 (例如不合法的表达式);你的程序应该给出错误提示而不应该 crash。你可以做出比较友好的假设——不像之前的实验,会为了 “强迫” 你掌握某些知识而使你疯狂 Wrong Answer。这个实验纯属放松,Online Judge 没有刁难你的测试用例,都和 demo 中的差不多。

  • 注意我们允许函数和表达式调用之前 (在 crepl 中) 定义过的函数;
  • 你可以假设我们输入的命令/表达式数量不超过 100 个;
  • 注意你处在的运行目录可能没有写入的权限。建议你将创建的临时文件都放在 /tmp/ 目录下。建议使用 mkstemp family API 创建临时文件;
  • 主进程确实求出了所有表达式的值。
  • 禁止使用 C 标准库 system 和 popen。这稍稍增加了实验的难度,不过并没有增加多少。请把这个限制理解成强迫大家掌握操作系统知识的训练。

禁止使用 system() 和 popen()

调用它们将会导致编译错误。好消息是这个实验我们不禁止 exec family 的系统调用:execl, execlp, execle, execv, execvp, execvpe 都是允许的。

4. 实验指南

4.1 解析读入的命令

框架代码里已经包含了读入命令的循环 (看起来像是一个小 shell),它打印出一个提示符,然后接受输入并解析:

int main(int argc, char *argv[]) {
  static char line[4096];
  while (1) {
    printf("crepl> ");
    fflush(stdout);
    if (!fgets(line, sizeof(line), stdin)) {
      break;
    }
    printf("Got %zu chars.\n", strlen(line)); // WTF?
  }
}

当你在终端里按下 Ctrl-d,会结束 stdin 输入流,fgets 会得到 NULL

这段代码里一个有趣的小细节是对 fflush 的调用:你会发现把它去掉对程序的运行并没有什么影响。但如果你在 fgets 之前插入一些延迟,例如 sleep(1),你会发现 fgets 会 flush stdout 的缓冲区。但 C 标准并没有规定这个行为,glibc 只是因为大家用错得太多,为大家贴心地兜了——其实 System 领域这种 “事实行为” 并不少见,大家错得多了,我们的库函数、编译器等不得不做出防御性的行为容忍大家犯错。一个例子是某一时期本的 gcc 会非常激进地对能证明的 undefined behavior 进行优化,但却导致不少以前 “正确” 工作的代码的崩溃,到新版本里反而不再做这些激进的优化了。

回到实验,在上面的代码里,如果读入的字符串以 int 开头,你就可以假设是一个函数;否则就可以假设是一个表达式。

4.2 把函数编译成共享库

对于一个一行的函数,比如

int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }

如何把它编译成共享库?我们在课堂上讲解过编译成共享库 (shared object, so) 的代码,我们的 M2 (libco) 也实现了共享库。我们只需要把这个文件保存到临时文件里,例如 a.c 中,然后使用正确的选项调用 gcc 即可。

选取合适的路径和文件名

如果你的工具在当前目录下创建文件,有可能会失败——例如,你可能在一个没有访问权限的工作目录上 (例如文件系统的根 /)。在 /tmp 中创建临时文件是更安全的做法。此外,glibc 还为我们提供了 mkstemp family API 调用,能够帮助我们生成名称唯一的临时文件。

除了编译和命名的问题,大家可能会感到困惑是,如果我的函数调用了其他函数怎么办?

int foo() { return bar() + baz(); }

你不妨试着编译这个程序……它竟然可以被编译!所以忽略所有的 warnings 就好了!最后,为了巩固大家在上一个实验中学过的知识,我们限制你不能使用 libc 中的 system 和 popen——它们会让实验变得有些过于简单。

4.3 把表达式编译成共享库

把函数编译成共享库是常规操作——库函数主要就是为我们提供函数的。但表达式怎么办?又用到我们这门课里反复用的小技巧了:我们可以做一个 wrapper 呀!每当我们收到一个表达式,例如 gcd(256, 144) 的时候,我们都可以 “人工生成” 一段 C 代码

int __expr_wrapper_4() {
  return gcd(256, 144);
}

注意到函数名里的数字——我们通过加上数字为表达式生成不一样的名字。我们的表达式变成一个函数,我们就可以把它编译成共享库了。把动态库加载到地址空间并得到 __expr_wrapper_4 的地址,直接进行函数调用就能得到表达式的值了。

4.4 共享库的加载

我们可以使用 dlopen 加载共享库。我们已经为大家提供了 -ldl 的链接选项,大家可以阅读相关库函数的手册。另一个很不错的手册是 elf (5)。

4.5 试试自己用 mmap 加载?

参考 loader-static,你也可以自己实现 dlopen。在这个实验里,我们的假设很简单,函数只访问局部变量,不涉及任何全局符号,因此只需要加载程序的代码即可——也就是说,你只需要把代码 mmap 到地址空间中,再解析符号找到入口地址,就可以不调用库函数实现加载了!

Creative Commons License    苏 ICP 备 2020049101 号