《链接、装载与库》 阅读笔记 (1)- 基本概念与静态链接

一直对以 C/C++ 为代表的的编译型语言的编译、运行的原理了解不多，最近正好看到这本由国人写的书 链接、装载与库，书名已经比较言简意赅的介绍了书里相关内容，而且写得挺通俗的，值得一看。这里是书里第一、二部分内容的一些笔记，主要讲了操作系统的一些基本概念，编译生成的目标文件格式和静态链接的过程；由于笔者只摘录一些不太了解的内容，因此总体内容可能不是非常成体系，建议读原书。

操作系统基本概念

这部分主要讲了一些与操作系统相关的基本概念，了解这些基本概念是了解书中后面内容的基础

• 增加中间层解决问题
  • 避免直接访问磁盘，增加中间层：文件系统
    • 磁盘以扇区作为基本单位，一个文件会被存储在多个扇区上，文件系统保存了这些数据结构
      
  • 避免直接访问物理地址的方法，增加中间层：虚拟地址
    • 操作系统保留了从物理地址到虚拟地址的映射 (MMU)
      
    • segmentation：把一段物理地址映射到一段虚拟地址，解决了物理地址不隔离的问题
      
    • paging：将物理 / 虚拟地址切成小块 (page) 再分配，避免程序占据了整块连续物理地址； 某些小块可能当前用不着，先存到磁盘中，需要用的时候再取出来，这就是虚拟内存
• 多线程
  • 线程共享代码段，进程数据，打开的文件等资源。但是有自己的私有空间：即寄存器和栈
    
  • 进程内部默认有一个主线程
    
  • 可抢占式线程 (preemption) 与不可抢占线程， 即是否能强行中断当前线程分配资源给其他线程
    
  • 对 Linux 来说，线程不是一个通用概念
    • 所有执行实体都被称为一个 task，task 间可共享内存空间；如 fork 就是创建了一个任务（COW 机制，copy on write，即只有在新的 task 改动内存时才为新的 task 创建内存
      
  • 线程不安全的原因：代码的一个操作在被编译成汇编指令后不止一条，因此可能还行一半就被打断，不会被打断的指令也称为原子（atomic）指令，为了达到线程安全，需要同步与锁
    • 信号量 - semaphore: 允许 N 个线程并发访问一个资源
      
    • 互斥锁 - mutex：仅允许一个进程访问，与 semaphore 不同点在于 mutex 可由不同的线程来 release lock，但是 semaphore 只能由原来的线程释放
      
  • 编译器优化时可能会造成多线程的加了锁也有问题
    
  • 用户态 v.s 内核态：用户实际使用的线程是用户态的，真正执行的线程是内核态的，这种情况下有几种模式（1）一对一（2）一对多（线程内可能会阻塞） （3）多对多
• 堆栈内存区域（C 中还有静态区域，用来存储 static 变量和全局变量)
  • 堆可以理解为当前可以使用的空闲内存，但是其申请和释放都要程序员自己写代码管理。如果只申请不释放就会造成内存泄露
    
  • 栈是程序运行时自动拥有的一小块内存，大小在编译期时由编译器参数决定，用于局部变量的存放或者函数调用栈的保存
    
  • 栈的另一个作用则是保存函数调用栈，这时和数据结构的栈就有关系了。在函数调用过程中，常常会多层甚至递归调用。每一个函数调用都有各自的局部变量值和返回值，每一次函数调用其实是先将当前函数的状态压栈，然后在栈顶开辟新空间用于保存新的函数状态，接下来才是函数执行。当函数执行完毕之后，栈先进后出的特性使得后调用的函数先返回，这样可以保证返回值的有序传递，也保证函数现场可以按顺序恢复
    
  • 操作系统的栈在内存中高地址向低地址增长，也即低地址为栈顶，高地址为栈底。这就导致了栈的空间有限制，一旦局部变量申请过多（例如开个超大数组），或者函数调用太深（例如递归太多次），那么就会导致栈溢出（Stack Overflow），操作系统这时候就会直接把你的程序杀掉。

编译与链接概述

编译的过程 (预编译 -> 编译 -> 汇编 -> 链接)

• 预编译（生成 .i 文件）：主要是处理 # 开头的语句，如进行宏展开、将被 include 的文件插入到对应的地方（递归执行）
  
• 编译（生成 .s 文件）：将代码编译成汇编代码，包括词法分析、语法分析、语义分析和生成汇编代码的优化；虽然不同语言都可通过 gcc 来统一编译，但是 gcc 对于对于不同的语言调用了不同的编译程序（如 c 是 cc1，c++ 是 cclplus，java 是 jc1）
  
• 汇编（生成.o 文件）：将汇编代码逐条转换成机器指令（有查找表）
  
• 链接（生成可执行文件）：静态链接与动态链接

其中编译这个步骤常常涉及到以下几个过程

• 词法分析：将源码分割成一系列的 token，利用 lex，编译器开发者只需要定义词法规则
  
• 语法分析：生成语法树，利用 yacc，编译器开发者只需要定义语法规则
  
• 语义分析：确定语句是否合法（编译器只能分析静态语义），为语法树中的每个节点标记出其类型

编译器的前端和后端
- 前端：生成与机器无关的中间代码（即前面的词法和语法分析步骤）
- 后端：将中间代码转换成目标机器代码
- 跨平台编译器，使用同一个前端和不同后端

关于编译器的架构可参考这篇文章：LLVM 概述 —— 基础架构

链接基本概念

• 处理各模块间的相互引用（如引用了其他模块的函数，需要在运行时知道这个函数的地址）
  
• 从原理上来说，链接就是把一些指令对于其他符号的地址的引用加以修正
  
• 库是一些常用代码被编译成目标文件后打包存放

目标文件的格式

• 目标文件就是源代码编译后但是未进行链接的那些中间文件（windows 的 .obj 和 linux 下的 .o, 它跟可执行文件的内容基本一样，所以两类文件使用同一种格式存储（windows 下的 PE-COFF 和 Linux 下的 ELF）
  
• 除了目标文件，动态库 (windows 的 .dll 和 linux 下的.so) 和静态库 (windows 的 .lib 和 linux 下的.a) 都是按照可执行文件格式存储
  
• ELF 文件格式可归为如下四类（linux 下可通过 file 格式来显示文件格式）

• 目标文件组成主要分为两部分：程序指令和程序数据；顾名思义，程度指令就是存放代码，程序数据用来存放代码中的数据，分局数据中的类型又可分为几种段

• 数据和指令代码分开存放的好处

  • 数据是可以读写的，但是代码指令是只读的
    
  • 系统中运行着该程序的多个副本运行时（多进程，多线程），只需要保存一份指令代码 / 只读数据即可，可节省大量内存
    
  • 可提高缓存命中率

• objdump 可被用来分析目标文件中所包含的各个段（代码段，数据段，bss 段）的一些信息 (如下图所示），size 则可被用来查看对应的各个段的大小

从上图可知， 目标文件中有好几个类型的数据段，但是其中某些段是不占空间如.bss 段，用于表示未初始化的全局变量和局部静态变量 (更准确地说是为这些变量预留了空间)，已初始化的保存在 .data；因此在内存中的占位如下所示

各个段的含义如下

• .text: 存储汇编后的机器指令，通过 objdump -d 反汇编可看到代码段的机器指令机器和对应的汇编代码
  
• .data: 存储已经初始化的全局变量和局部静态变量
  
• .bss: 存储未初始化的局部变量和局部静态变量
  
• .rodata: 存储只读数据段，一般用来存储 const 常量和字符常量

可将一个二进制的文件通过 objcopy copy 到目标文件中

除了上面介绍的各个段，ELF 文件还有下面几个比较重要的结构

• 文件头：描述整个文件属性（如文件版本、目标机器型号、程序入口地址等）
  
• 段表：描述上面提到的各个段的基本属性，编译器，链接器和装载器都是依赖段表来定位和访问各个段的属性
  
• 符号表：管理代码中的符号（函数名和变量名），用于进行链接，因为链接的接口就是符号名

实际上，无论是可执行文件、目标文件或库，实际上都是一样基于段的 ELF 文件或者是这种文件的集合；源代码经过编译后，按照代码和数据分别存放到相应的段中；除此之外，编译器还会将一些辅助性的信息（符号表，重定位表等）放到目标文件中。下面就是怎么把这些目标文件组装起来了，这就是链接要解决的事情。

静态链接的过程

问题：合并目标文件时，对于多个目标文件中的多个段，链接器如何将它们各个段合并到输出文件；或者说链接器怎么为目标文件分配地址和空间

先说结论，链接可简单地分为两步（two-pass linking)

1. 空间地址与分配：扫描输入文件，合并相同类型的段，输出合并后的段的长度与位置
   
2. 符号解析与重定位：利用第一步搜集到的信息，进行符号解析与重定位、调整代码中的地址等；这一步是链接过程的核心，尤其是重定位部分

上面提到的 “链接器怎么为目标文件分配地址和空间” 中的 “地址和空间” 实际包括两方面: (1) 输出的可执行文件中的空间 (2) 装载后的虚拟地址中的虚拟地址空间； 对于目标文件中像 .text 和 .data 的段这两方面都要考虑，但是对于 .bss 的段只需要考虑虚拟地址空间，因为 .bss 不在可执行文件中占用空间，后面说的分配也着重于虚拟地址空间的分配

这里以下面两个源文件 a.c 和 b.c 说明

空间地址与分配

链接前后使用的虚拟地址（VMA，Virtual Memory Address） 已经是程序在进程中的虚拟地址（通过 objdump 可看到目标文件中各个段的 VMA）；如下图所示是将两个目标文件 a.o 和 b.o 链接成一个可执行文件 ab（通过命令 ld a.o b.o -e main -o ab 可生成可执行文件 ab, 其入口为函数 main【通过 -e 参数指定，ld 链接器默认的入口为 _start】）

通过 objdump 可分析出目标文件与可执行文件中 VMA 的变化

从上面可以看到，链接前目标文件的 VMA 都是 0，因为虚拟空间还没有被分配，等链接后，可执行文件中的各个段都被分配到了相应的虚拟地址

下图展示了将两个目标文件 a.o 和 b.o 链接成可执行文件 ab 后目标文件与可执行文件各个段的映射关系，以及可执行文件与虚拟地址的映射关系

在确定了各个段的地址后，由于符号地址在本来段内就是确定的（从前面的 objdump 命令输出结构可知），因此可以根据各个段的地址偏移确定各个符号的地址

符号解析与重定位

完成空间地址分配后，进入到了符号的解析与重定位，这也是静态编译的重点

首先，通过 objdump -d 可以看到 a.o 代码的反汇编结果如下图所示

从上图输出可知，目标文件 a.o 中定义了一个函数 main, 其起始地址是 0x00000000，这是因为在程序代码里使用的都是虚拟地址，且在空间地址与分配之前，目标文件中的起始地址是 0x00000000，等到空间分配完成后，各个函数才会确定自己在虚拟地址空间的地址。

此外，上图中命令的输出中的 main 函数下面每行都是一条指令， 从左到右依次是指令的偏移量、指令的机器码，右边是指令对应的汇编代码。

因此，上图中的 main 函数共占了 0x33 个字节， 17 条指令，其中 0x18 的指令占了两行，加粗的两条指令分别对应于 a.c 中引用的 shared 和 swap,

对于 shared 的引用是偏移为 0x18 的 mov 指令，这条指令共 8 个字节，前 4 个字节是指令吗，后面 4 个字节是 shared 的地址，从图中看到这个地址为全 0，这是因为 a.c 被编译成目标文件时，并不知道 shared 和 swap 的地址，因此暂时用全 0 来表示

对于 swap 的引用则是偏移为 0x26 的 call 指令，这条指令共 5 个字节，其作用就是调用另一条指令，后面四个字节就是要调用的下一条指令的偏移量（地址），同样地，在链接前这个地址是一个 mock 的地址。

由上面描述可知，目标文件中的地址都是临时的 mock 地址，真实地址的分配与调整是由链接器来完成的，因为经过第一步的 “空间地址与分配” 后，链接器已经能够确定所有符号的地址了。同样地通过 objdump -d 我们可以看到可执行文件 ab 的反汇编的结果如下

从上图可知，main 函数地址确定了下来，同时 shared 和 swap 的地址也确定了，

链接器是怎么知道哪些指令是要被调整的？在 ELF 文件中有一个叫重定位表（Relocation Table）的结构来专门保存与重定位相关信息，重定位表实际上也是一个 ELF 文件中的一个段（重定位段），通过 objdump -r 可以看到目标文件中的重定位段，如下图所示

上图展示了 a.o 里面要重定位的地方，即 a.o 所有引用到外部符号的地址，对照前面 objdump -d a.o 的结果可知，上图中的偏移的值就是 shared 和 swap 在目标文件中的机器指令的后四个字节所在地址

那在上面重定位的过程中，链接器怎么知道 a.o 里面需要的符号在哪去查找？这就涉及到链接器是如何进行符号解析的了，实际中，链接器会查找所有输入目标文件的符号表组成的全局符号表，找到相应的符号然后重定位。我们在编译过程中常碰到的找不到符号，或者符号冲突，其实都是发生在这个过程中

通过 readelf -s 可以看到目标文件中的符号表，如下是 a.o 的符号表，可以看到 shared 和 swap 都是 UND (undefined）的

COMMOM 块

强符号与弱符号：在 C 语言中，函数和初始化的全局变量是强符号，未初始化的全局变量是弱符号

在链接中一个符号可能会出现在多个目标文件中，因此可能会出现下面几种情况

1. 两个或两个以上的强符号，类型不一致
   
2. 两个或两个以上弱符号，类型不一致
   
3. 有一个强符号，其他都是弱符号，类型不一致

第一种情况是非法的，因为不能定义多个强符号，链接器会报多重定义错误，链接器要处理的就是后两种情况，处理的方式就是下面提到的 COMMON 块 (Commom block) 机制，简单来说，COMMON 块记录了对应的符号的空间大小

对于第二种情况，会从多个弱符号中选择一个空间最大的，比如说两个弱符号，一个是 int 型，一个是 double 类型，则最终会选择 double 类型的

对于第三种情况，会选择强符号，但是如果有弱符号的空间大于强符号的，最终会报如下的 warning:

ld: warning: alignment 4 of symbol global in a.o is smaller than 8 in b.o

因此，使 COMMOM 模块的原因是因为编译器和链接器允许不同类型的弱符号存在，同时链接器不支持符号类型，即连机器无法判断各个符号类型是否一致。

静态库

一种语言的开发环境往往会带有语言库（Language Library），这些库就是对操作系统的 API 的包装；一个静态库可以看做是一组目标文件的集合

通过 ar 可以看到一个静态库中有哪些目标文件

值得注意的是，静态库里的一个目标文件只包含一个函数，这是是为了是的在链接过程中只链接那些使用到的函数对应的目标文件，如果很多函数都放在同一个目标文件中，会导致很多没用的函数都被遗弃链接进了输出结果中。

小结

综上，本文主要介绍了操作系统的一些基本概念，以及静态链接的基本过程，主要关注一下几个方面

• 目标文件由各种段组成，基本可分为代码段和数据段两大类
  
• 目标文件被链接成最终的可执行文件时，输入的目标文件中的各个段是如何被合并到输出文件中的
  
• 链接器如何为合并后的段分配在空间和地址（包含输出文件和进程虚拟地址空间）
  
• 地址确定后如何进行符号的解析与重定位，使得每个段中的指令和数据都指向正确的位置