什么是程序和编译器

xeonds

2023.01.27 22:27:42

操作系统的本质：一个程序，用于管理硬件资源供其他程序调用

那问题就到了程序本身：程序应该如何定义？这引出了程序的状态机模型：

状态机

这东西我们在数电中接触过，硬件基础就是一堆触发器（RS、JK等）。状态就是寄存器保存的值，初始状态即寄存器初始值，迁移就是组合逻辑电路计算寄存器下一周期的值。

下面是一个寄存器的模拟程序。

#define REGS_FOREACH(_) _(X) _(Y) 
#define RUN_LOGIC X1 = !X && Y; \ 
                  Y1 = !X && !Y; 
#define DEFINE(X) static int X, X##1; 
#define UPDATE(X) X = X##1; 
#define PRINT(X) printf(#X " = %d; ", X); 

int main() { 
    REGS_FOREACH(DEFINE); 
    while (1) { // clock 
        RUN_LOGIC; 
        REGS_FOREACH(PRINT); 
        REGS_FOREACH(UPDATE); 
        putchar('\n'); 
        sleep(1); 
    } 
}

程序的定义

源码视角

程序就是状态机。对于C程序而言，它的状态机模型如下：

状态=栈帧+全局变量
初始状态=main
迁移=执行栈顶的语句并转到下一条指令
    函数调用=入栈
    函数返回=出栈

这定义有很多应用，比如将任何递归程序就地转为非递归。虽然实际上递归就是这么实现的（一层递归建立一层函数栈、跳转地址压栈）。例如，下面就是手写函数栈展开递归：

#include <assert.h>

typedef struct {
  int pc, n;
  char from, to, via;
} Frame;

#define call(...) ({ *(++top) = (Frame) { .pc = 0, __VA_ARGS__ }; })
#define ret()     ({ top--; })
#define goto(loc) ({ f->pc = (loc) - 1; }
  
void hanoi(int n, char from, char to, char via) {
  Frame stk[64], *top = stk - 1;
  call(n, from, to, via);
  for (Frame *f; (f = top) >= stk; f->pc++) {
    switch (f->pc) {
      case 0: if (f->n == 1) { printf("%c -> %c\n", f->from, f->to); goto(4); } break;
      case 1: call(f->n - 1, f->from, f->via, f->to);   break;
      case 2: call(       1, f->from, f->to,  f->via);  break;
      case 3: call(f->n - 1, f->via,  f->to,  f->from); break;
      case 4: ret();                                    break;
      default: assert(0);
    }
  }
}

二进制视角

实际上就是汇编视角。汇编程序分为几个段：数据段、代码段和栈段。加载程序就是加载初始状态，状态转移就是改变寄存器的值，转移方式就是执行指令。

这两个视角都可以用gdb来查看。

但是，操作系统又不是普通程序。因为操作系统不光处理计算任务，还需要能够暂停、退出程序等等。

在Linux中，有一条叫做systemcall（系统调用）的指令。它不负责计算，它把当前进程的状态交给操作系统，也就是允许操作系统任意更改程序。这使得进程可以和操作系统中的其他对象交互。

也就是说，对于程序而言，操作系统就是一个程序。参数就是应用程序本身的状态，输出就是程序要访问的资源。C程序main函数最后的return;就是这样的，它实质上是借助了syscall()，将程序状态变为某特定状态，再交给系统去处理。这就好比准备好要传递的参数，然后去调用函数一样。

回到主题。从二进制/操作系统的视角看来，程序是一个不停计算，并会穿插执行systemcall的状态机。

什么是编译器

编译器将源代码编译为二进制程序。从汇编状态机/C程序状态机的视角来看，实际上就是将后者翻译成了前者。编译（优化）的正确性（Soundness）就是在确保二者的可观测行为完全一致。

而关于编译器优化，我们可以使用compiler barrier来阻止优化：

extern int g;

void foo(int x){
    g++;
    asm volatile("nop" : : "r(x)" : "memory"); // compiler barrier
    g++;
}

上面的代码借助objdump查看反编译代码，可以看出，这两条g++并没有被-O2编译优化。

$ gcc -O2 -c a.c && objdump -d a.o

a.o:     file format elf64-x86-64


Disassembly of section .text:

0000000000000000 <foo>:
   0:   f3 0f 1e fa             endbr64
   4:   83 05 00 00 00 00 01    addl   $0x1,0x0(%rip)        # b <foo+0xb>
   b:   90                      nop
   c:   83 05 00 00 00 00 01    addl   $0x1,0x0(%rip)        # 13 <foo+0x13>
  13:   c3                      retq

除此之外，还有一种更强的barrier：__sync_synchronize();

观察编译器

使用strace，我们可以看到一个程序所有的系统调用。借助下面几个工具的组合，我们可以看到gcc如何编译程序：

// a.c
#include <stdio.h>

int main(void){
    printf("Hello, OS!");

    return 0;
}

保存上面的文件后，执行下面的指令：

strace -f gcc a.c |& vim -

我们可以在Vim中看到下面的输出

![[Pasted image 20230128215947.png]]

稍微修改后（:%!grep execve留下系统调用的行，:%!grep -v ENOENT删除失败的行，:%s/, /\r /g将参数换行显示，提高结果可读性），可以分析得到下面的结果

  1 execve("/usr/bin/gcc"
  2   ["gcc"
  3   "a.c"]
  4   0x7ffd181ca900 /* 30 vars */) = 0
  5 [pid   212] execve("/usr/lib/gcc/x86_64-linux-gnu/9/cc1"
  6   ["/usr/lib/gcc/x86_64-linux-gnu/9/"...
  7   "-quiet"
  8   "-imultiarch"
  9   "x86_64-linux-gnu"
 10   "a.c"
 11   "-quiet"
 12   "-dumpbase"
 13   "a.c"
 14   "-mtune=generic"
 15   "-march=x86-64"
 16   "-auxbase"
 17   "a"
 18   "-fasynchronous-unwind-tables"
 19   "-fstack-protector-strong"
 20   "-Wformat"
 21   "-Wformat-security"
 22   "-fstack-clash-protection"
 23   "-fcf-protection"
 24   "-o"
 25   "/tmp/ccf8oz38.s"]
 26   0x251bbd0 /* 35 vars */ <unfinished ...>
 ...

上面就是gcc编译这个程序的全流程，以及全部的参数。这些系统调用都能看得到。也就证明了前面的结论：程序=系统调用+计算。我们写的算法题就几乎属于纯计算（只有最后的return 0;算个系统调用），平时使用的各种程序就属于系统调用+计算的类型。