Linking and Runtime Memory

Introduction

在学习了两个学期的计算机系统之后，对os以及C语言的一些元素有了更深一点的理解

Linking链接在编译语言中是很重要的一个概念，但是在Go/Rust中的linking都是默认的静态链接，C/C++中则是最典型的，需要显式的链接步骤

其实对于普通的c语言编程，只要了解链接的概念和其用法应该就可以了，掌握到makefile / CMake就完全可以了

但是我认为linking最重要的一点是帮助理解内存的布局，以及代码最终是在怎么从存储里到内存中，最后运行起来的

所以这里从linking出发，串联起runtime的内存布局，进行一个梳理，也会稍微提一嘴VM的事情

前置知识

• C / C++ 语言基础
• 对汇编语言有了解
• 对内存空间有认识

---

Linking

链接，是指将多个代码和数据部分（通常是目标模块、静态库或动态库）收集并组合成为一个单一文件的过程，这个文件可以被加载（复制）到内存中并执行

机器能执行的语言是二进制语言，而我们编写的是高阶的编程语言。从代码到可执行文件，往往经历这样的过程

当编写源代码（.c）并执行编译的时候，编译器并不能直接将这个代码转换为可以执行的二进制文件，而是往往要经过这样的过程

1. Preprocessing 预处理：处理宏定义，展开头文件
2. Compilation 编译：将预处理后的代码翻译成汇编语言，得到.s文件
3. Assembly 汇编：将汇编代码翻译成机器码, 生成Object File（目标文件）.o

每一个源文件都会被编译成一个.o，而这些源文件之间相互依赖，想要形成一个最终的可执行文件，就需要链接起所有的目标文件

而最终的一个目标文件，如果做一次反汇编的话，就是把所有的变量、代码等等放到了一个地址空间里；而为了让不同的程序都能普适的运行在机器上，这里使用的地址肯定不能是机器真实的物理地址，因为这样需要不同程序之间彼此知道在用什么地址，对链接过程提出了很高的要求；同时不同程序之间也没有隔离，甚至能修改别的程序里的变量

所以这里最终的地址空间是一个虚拟的地址，任何一个程序都能从0x0开始使用地址一直到最大的边界，这样链接器只要独立的完成这些目标文件的编写就行了

至于这些虚拟地址和机器的物理地址是什么样的映射关系，会在VM章节里介绍

Variable Type

要想知道目标文件是怎么被链接的，就要先知道它内部的结构是什么样的

但在这之前，先阐明一下c中几种变量的类型，方便和之后的目标准见中的数据段section进行比对

• global：在任意的function的作用域{}之外
• local：在某一个function的作用域里

每一个变量所处的区域无外乎这两个，所以分类上可以被划分成这两种

还有一个常见的额外字段static，他会把当前变量的生命周期延长到和程序一样长，同时只在当前的文件内可见。而它作用在上面的两种类型上有不同的表现：

• static
  • local ：生命周期延长
  • global：限制文件内

static变量还有一个特性，就是只会被初始化一次，就算多次调用初始化代码，也只会初始化最开始的一次

#include <stdio.h>

int main() {
    for (int i = 0; i < 5; i++) {
        static int x = 1;   // 这行在编译期就处理好了，运行时第一次执行时初始化一次
        x++;
        printf("第 %d 次循环，x = %d\n", i+1, x);
    }
    return 0;
}

Object File

在类Unix系统中,.o文件遵守着ELF(Excutable and Linkable Forma)的文件格式，见下图

其中对应的部分：

Section	Usage
.text	存放编译好的机器指令
.data	存放已经初始化的全局变量和静态变量
.bss	存放未初始化的全局变量（在文件中不占实际磁盘空间，只记录大小，运行时由内核清零。这一点在之后的VM部分也会提及）
.symtab	记录这个 .o 文件里定义和引用的所有符号
.rel.text	text 中包含需要重定位(见下文)的符号，其位置、类型等信息会记录在这里
.rel.data	data 中包含需要重定位(见下文)的符号，其位置、类型等信息会记录在这里
Section Header Table	描述了文件中每一个 Section 的名字、大小以及在文件中的偏移量。是一个meta data

了解完一个目标文件内部的对应关系之后，在进入链接部分前有这几个问题：

• 文件的代码是怎么使用外部引用的函数/全局变量的？
• 汇编语言中，函数的跳用是通过跳转地址来实现的，那么调用其他文件里的变量的时候，要跳到的地址是哪里？
• 合并后生成文件的内部结构是什么样的？

---

1.符号解析 Symbol Resolution

回答刚刚提出的第一个问题的，就是符号解析

在.symtab中，一张符号表会记录下

1. 被本文件定义的符号：可以提供给自己/外界使用的函数或全局变量
2. 本文件引用，但是由外部定义的符号：在代码里用了，但实现代码在别的源文件或第三方库里（extern int shared_var ; prinft）

符号解析的这一步，就是要把所有”引用但未定义”的符号，在其他 .o 文件的符号表里找到对应的”定义”，将他们一一匹配

当链接器（Linker）处理多个 .o 文件时，它会把每个 .o 文件里的符号表提取出来，在内存中维护一个全局符号表，也就是未来将作为链接产物的文件的.symtab

全局符号表的建立过程如下：

维护三个集合：
    E: 最终将被合并的可执行文件集合
    U: 未解析符号集合
    D: 已定义符号集合

  扫描每个输入文件：
    1. 如果是目标文件(.o):
       - 加入E
       - 将定义的符号加入D
       - 将引用的未解析符号加入U

    2. 如果是静态库(.a):
       - 遍历库中的每个.o文件
       - 如果该.o文件定义了U中的符号
          * 将该.o文件加入E
          * 更新D和U
       - 重复直到U不再变化

错误检查：
  - 多重定义错误（相同符号被定义多次）
  - 未定义符号错误（链接结束后U不为空）

这里的静态库和多重定义会在下文被提及

但是这就又引出了一个问题，那就是，如果有多个目标文件都定义了同名的一个变量，最后的symtab会如何记录这个变量？这就是所谓的符号冲突，因为所有的符号都只能有唯一的定义

为此，编译器引入了强弱符号的规则：

• 强符号：编译器把函数和已经初始化的全局变量视为强符号
• 弱符号：编译器把未初始化的全局变量视为弱符号

而链接器处理同名冲突的规则非常naive

1. 强强冲突：不允许有多个同名的强符号。如果两个 .o 里都定义了 int g_val = 10;，链接器就会直接报错：multiple definition of...多重定义

2. 强弱共存：如果一个是强符号，一个是弱符号，链接器会默默选择强符号，把弱符号覆盖掉

3. 弱弱冲突：如果全是弱符号，链接器会从里面随便挑一个使用

这种强弱符号的机制会带来一些隐患。例如你在 file1.c 里写了未初始化的全局变量 double x;（弱），在 file2.c 里写了已初始化的 int x = 1;（强）。链接器不会报错，它会把全局的 x 认作 int 类型，并给他分配4byte。但当 file1.c 尝试去读写 double（8byte）大小的 x 时，就会悄悄把邻近的其他内存数据给写坏

为了防止这种bug的出现，也有相应的应对机制，这里不展开介绍

2. 重定位 Relocation

当所有的符号都对上号之后，链接器就要开始分配内存地址了，也就是进行重定位

在编译成 .o 文件时，因为是独立编译，汇编器根本不知道这个文件里的机器指令最终会被拼在可执行文件的哪个位置。因此，.o 文件里的所有函数和变量的地址，默认都是从 0 开始的相对地址，这也是虚拟内存带来的编码的便捷之处

而重定位就分为这样的两步：

1. 合并相同的段（Section Merging）： 目标文件（.o）里通常有很多段。比如 .text 段放机器指令，.data 段放已初始化的全局变量。链接器会把所有 .o 文件的 .text 段粘成一个巨大的 .text 段，把所有 .data 段粘成一个巨大的 .data 段。 合并后，可执行文件里的每一个函数、每一个全局变量，就都有了在整个程序里唯一且确定的虚拟内存地址
2. 修改符号引用（Fixing References）： 有了确定的地址后，链接器会回过头去，翻看 .o 文件自带的重定位表（Relocation Table）。重定位表就像一张”待办清单”，上面写着：“请注意，main.o 的第 0x20 字节处有一条 call 指令，它调用了 foo 函数，编译时我填的是 0，现在请把它改成 foo 函数的真实地址。” 链接器把这些占位符全部抹去，填入真正的绝对地址（或者相对偏移量）。至此，程序里所有的函数调用和变量访问才真正能运行

这里图是address space或者说是virtual memory的图，相当于是从最终的目标文件出发，用一个加载器Loader：

1. 把文件里的section搬运到了它们对应的虚拟地址
2. 额外开辟了动态区域stack / heap
3. 约定好一片区域用来对应共享的动态链接的库，下面会介绍

3. 静态链接与动态链接 Static/Dynamic Linking

TODO：

简单来说就是静态链接会把所有的相关的文件和库链接到一起成为一个完整的目标文件；

而动态链接则是把共享的库/代码只存一份在物理内存里，对应的地址使用一个相对偏移量的表，避免一些相同的字段反复占据内存，这里和对整个runtime的内存理解来说就先介绍到这。它具体的过程涉及到了GOT（全局偏移表） 和 PLT（过程链接表） 进行间接跳转，这里先不深入介绍

---

VM

VM，Virtual Memory即虚拟内存，正如上面提到的，是解决程序链接的独立性和便捷性而使用的；由一个目标文件，对应到它运行的runtime使用的空间如下图所示，可以看到和重定位之后没有什么太大的区别

关于VM这一块其实有很多内容，详情可以看笔记, 这里就不重复了

大体上来说，就是VM和PM(Physical Memory)会被切分成一个一个的page，VP(Virtual Page)和PP(Physical Page)会按照某种规则进行映射