计算机体系-链接与装载

Author Avatar
mrriddler 8月 24, 2018

本文章的主角是链接与装载,链接和装载是一段隐藏的很深的咒语,大部分程序员不会直接接触到,听到的也只是计算机的窃窃私语,但是其相关内容,却是计算机体系的核心。

编译、链接历史

编译、链接的历史基本就是计算机的进化史,是很有趣的一段故事。Long time ago… 程序员写程序都是用纸带,那时候还在写0、1机器码。纸带上打孔就是0,不打孔就是1。然后计算机读取纸带就是读取指令。这样写程序的效率怎能接受?并且,写程序如果犯了错误怎么办?重新从头到尾再用新纸带写一遍?程序员们机智的开始想办法了,先是这样解决问题:

Patch的由来

将指带有误的地方,用黑黑的小贴纸填上去,这样将0改成1了。这也是Patch名字的由来。但是这样写指令效率还是太低,程序员们再机智的想办法。后来将指令进行符号化(Symbol),抽象出指令集,这时就出现了汇编,程序员的效率上了一个档次。但是新的问题又出现了。在写过程调用的时候,要写jmp 具体的函数地址。如果后来要在被调用的函数前面添加指令,那么函数地址也要跟着改。这样牵一发动全身的感觉可不好,为了让影响(impact)缩减到最小,不如将函数地址也符号化。凡是写过程调用先写成jmp func,等到程序分配了虚拟地址后,再将func换成真正的函数地址。

随着生产力的提升,程序的规模越来越大,新的问题出现了,程序膨胀到难以维护和阅读了。程序员们就将程序模块化、层次化。这样也使编译的单位更小粒度化。编译的时候,不同编译单位之间相互隔离。比如,对于C语言系,一个.h和一个.m就构成了一个编译单位。.m汇编时,是不知道其他.m的全局变量、函数地址的。

而不同编译单位之间相互引用需要如此过程:被引用放定义符号,引用方引用符号,等编译单位分配了虚拟地址后,进行符号决议,将引用符号修正(fix)成真正调用的虚拟地址。而负责这一步的就是链接器(Linker),这也叫重定位(relocation)。

链接

链接主要的目的就是将模块中的符号进行重定位。

重定位(relocation)

所界定的重定位只针对于不同模块,相同模块不存在重定位。指令区分为绝对指令和相对指令,同一模块中的符号引用直接可以用相对指令来完成,不需要更复杂的重定位,而不同模块只能用绝对指令,通过重定位修正了。

静态链接

静态链接为两阶段链接(Two-pass Linking):

  1. 确定和分配虚拟空间:将所有模块相同section合并,再明确每个模块中的符号定义和符号引用,生成重定位表和.symtab,再为每个section分配虚拟地址,最后将.symtab中的符号置换成虚拟地址。
  2. 符号重定位:将所有符号进行重定位,通过重定位表找到所有section中需要被修正的符号位置,然后从.symtab查询出虚拟地址替换。

还有一点需要注意,链接器很聪明,只有包含真正被引用符号的目标文件才会被链接入最终可执行文件。

一体化

随着静态链接慢慢发展起来,静态链接也暴露出了问题。静态链接将链接程序和主体程序作为一体,如果多个程序链接同一份程序,那么这段程序要进入每一个主程序,这样相当于将这段程序复制了多份,占了冗余空间。更好的做法,是将链接程序和主程序隔离开,于是就诞生了动态链接。

动态链接

动态链接将链接程序和主程序隔离开,多个主程序也可以链接同一个链接程序,链接程序不必和主程序一起载入,可等到真正使用时再载入。这也就是动态库提供的两个特点:共享和运行时加载。

反观静态链接,在链接阶段就可以确定出虚拟地址,而动态链接就不行了,动态链接无法“预测”出主体程序地址。这导致动态链接要将重定位推迟到动态库装载后。不仅如此,动态链接不仅无法“预测”出主体程序地址,动态链接也无法“预测”出自己程序地址,这导致动态链接无法直接使用绝对地址。动态链接同样为两阶段链接(Two-pass Linking):

  1. 地址重定位:装载并确定和分配虚拟空间后,要对使用的地址进行重定位。
  2. 符号重定位:与静态链接第二阶段类似。

地址重定位

地址重定位有两种思路:

  • 地址无关码(PIC):其代码中对地址的引用不能有绝对地址,动态链接库必须“间接”引用,而“间接”引用待装载后再修正。
  • 基址重置(Rebasing):其代码中对地址的引用使用相对地址,待装载后得出自己地址后,再将所有相对地址添加offset,置换成绝对地址。

这两种思路的区别在于,是否保留动态链接共享的特点。动态库被多个程序链接而只存在一份,被链入的不同程序其虚拟地址空间不同,其对主程序的符号引用地址是完全不同的。

地址无关代码(PIC):大体思路是将代码仍放在.text,而引用地址放在.data,引用“间接”到.data中去寻找,这样每个主程序可以保持动态库代码是一份,而引用地址各不同。内部引用同样用相对地址指令解决。

ELF通过.got(global offset table)来完成“间接”引用,.got就是一个指针数组,.got存储引用符号的实际地址。而代码段引用符号直接更改为引用.got项的位移,这在链接阶段以后就不会再改变了。然后将.got分配在.data section,装载时每个进程复制一份并修正。动态链接在装载的时候,根据符号表修正.got表项。动态链接库使用全局变量、静态变量、引用文件外过程调用都要经过.got。

这样,动态链接库虽然在不同进程中有不同的映射虚拟空间,但物理空间上共享。.got在不同进程中,虚拟空间和物理空间都不共享。如下图所示:

    virtual address             ->             physical address
  —— —— —— —— —— —— ——
 |processA            |  
 |—— —— —— —— —— —— ——|
 |.....               |  
 |—— —— —— —— —— —— ——|
 |dynamic libiraries  |----------                
 |—— —— —— —— —— —— ——|         |
 |.....               |         |           |.....               |
 |—— —— —— —— —— —— ——|         |           |—— —— —— —— —— —— ——|
 |.got                |---------|---------->|.got                |
 |—— —— —— —— —— —— ——|         |           |—— —— —— —— —— —— ——|
 |.....               |         |           |.....               |  
 |—— —— —— —— —— —— ——|         |           |—— —— —— —— —— —— ——|
                                ----------->|dynamic libiraries  |                 
  —— —— —— —— —— —— ——          |           |—— —— —— —— —— —— ——|
 |processB            |         |           |.....               |
 |—— —— —— —— —— —— ——|         |           |—— —— —— —— —— —— ——|
 |.....               |         |    ------>|.got                |
 |—— —— —— —— —— —— ——|         |    |      |—— —— —— —— —— —— ——|
 |dynamic libiraries  |----------    |      |.....               |
 |—— —— —— —— —— —— ——|              |
 |.....               |              |
 |—— —— —— —— —— —— ——|              |
 |.got                |---------------  
 |—— —— —— —— —— —— ——|       
 |.....               |  
 |—— —— —— —— —— —— ——|

基址重置(Rebasing):大体思路是将所有对地址的引用生成.rel,等待动态库装载后,重定位阶段对所有.rel中的表项进行原地址和基地址的加操作,再将结果置换掉原地址引用。而这种思路就无法保证每个进程主程序可以共享动态库代码,每个进程要复制自己的动态库副本。

这两种思路相比而言,地址无关代码(PIC)保持共享的特点,节省了内存,而基址重置(Rebasing)仍然是直接引用,节省了时间。

延迟绑定(PLT)

由于要在装载进行重定位,装载动态库会带来性能消耗,针对这点还可以进行优化,直接延迟绑定,等到过程调用符号运行时被用到再进行重定位,这就会导致调用动态链接符号比静态链接符号慢5%左右。

符号

符号类型

符号类型有三个维度,从可用范围:

  • 导出(export):在本模块定义,其他模块可以引用。
  • 导入(import):在其他模块定义,本模块引用。
  • 私有(private):在本模块定义,只能由本模块引用。

冲突:

  • 强(strong):强符号有唯一性,多个重复的强符号不可以共存。
  • 弱(weak):弱符号没有唯一性,一个强符号可以和多个弱符号共存,多个重复的弱符号可以共存。

引用:

  • 强引用(strong reference):强引用必须被决议出来。
  • 弱引用(weak reference):弱引用不用必须被决议出来。

函数签名(Function-Signature)与符号修饰(Symbol-Decoration)

函数签名是一个函数的名字、参数类型、所在类名组成的字符串,不同语言、不同编译器对同一个函数生成的函数签名是不一样的,比如OC中函数签名还要加上返回变量类型,C++中还要加上NameSpace。

过程调用符号不光是函数名,是对函数签名处理后的结果,全局变量符号也是经过类似用函数签名处理后的结果。这一处理过程就是符号修饰。

目标文件

了解了链接、重定位原理和思路后,近距离观察一下目标文件以加深理解。目标文件在,Windows平台下为PE(Portable Executable),Linux平台下为ELF(Executable Linkable Format),Mac平台下为Mach-O。虽然不同平台都有自己的格式,但是它们实际上都大同小异。先来以ELF为例子,详见这里

ELF

首先,文件分segment(段),而不同segment主要区分映射到不同的进程虚拟空间。每个segment又包含多个section,section是包含具体数据的部分。文件还包含一个header放文件描述信息,一个program header table(程序头)放置segment控制信息,一个section header table放置section控制信息。program header table和section header table都是数组,program header table中的每一项对应一个segment,section header table中的每一项对应一个section。ELF的文件格式是从映射空间->实体的一个抽象层级结构。

以下是一个ELF目标文件:

                                       |.text         |
                                       |—— —— —— —— ——
                                       |.rodata       |
  —— —— —— —— —— —— ——                 |—— —— —— —— ——
 |header              |                |.hash         |
 |—— —— —— —— —— —— ——|        ------> |—— —— —— —— ——
 |program header table|       |        |.dynsym       |
 |—— —— —— —— —— —— ——|       |        |—— —— —— —— ——
 |section header table|       |        |.strtab       |
 |—— —— —— —— —— —— ——|       |        |—— —— —— —— ——
 |__TEXT              |  ------        |.plt          |                   
 |—— —— —— —— —— —— ——|
 |__DATA              |  ------        |.data         |
 |—— —— —— —— —— —— ——|          |        |—— —— —— —— ——
 |other segment...    |       ------>  |.got          |
 —— —— —— —— —— —— —— —                |—— —— —— —— ——
                                       |.bss          |

注意一点,这个顺序是逻辑上的,真正物理存储上的顺序不一定的。

.text放置代码,.data放置已初始化的全局变量和静态变量,.bss放置未初始化的全局变量和静态变量。

header有很多文件控制信息,就不一一表述了,其中最重要的就是记录了section header table的起始地址。而section header table记录了所有section的名字、类型、长度、在文件中的偏移量(offset)等。如果想要寻址到任意section都要通过这个header table。section header table实际上是由struct构成的数组。

.strtab放置section名、变量名,包括符号名的字符串。由于在整个结构中,字符串的长度是不定的,一般将这些字符串统一放置在一个table中,然后存储table中的offset,最后寻址到字符串。比如,在下表中,我想找到girlfriend一词,我只要拿到.strtab的base地址,加上girlfriend的offset 9就可以找到这个字符串。

0  1  2  3  4  5  6  7  8 
i \0  w  a  n  t \0  a \0
g  i  r  l  f  r  i  e  n
d

.symtab就是符号表。每个目标文件都有自己的符号表,符号表也是一个由struct构成的数组。ELF的32位符号sturct:

typedef struct {
  int32_t st_name;
  uint32_t st_value;
  int32_t st_size;
  unsigned char st_info;
  unsigned char st_other;
  uint16_t st_shndx;
} ELF32_Sym;

st_name字段指明符号的名字,表示为在.strtab中的字符串offset。

st_value字段指明符号的地址,也可能是offset。

st_info字段指明符号的类型,是个混合字段,指明比如,局部符号(STB_LOCAL)、全局符号(STB_GLOBAL)、弱符号(STB_WEAK)。

st_shndx字段指明符号的所属的section。

Mach-O

Mach-O与ELF类似,有一点比较特殊的是,Mach-O最外层结构是load commands,即装载操作。load commands其包含的cmd代表load command type,指示了装载操作的类型。而在每个装载操作下再区分segment和section。Mach-O的文件格式是从装载操作->映射空间->实体的一个抽象层级结构。

下面是32位下.symtab的struct,可以看到和ELF几乎一致:

struct nlist {
    union {
        char *n_name;    /* for use when in-core */
        uint32_t n_strx;    /* index into the string table */
    } n_un;
    uint8_t n_type;        /* type flag, see below */
    uint8_t n_sect;        /* section number or NO_SECT */
    int16_t n_desc;        /* see <mach-o/stab.h> */
    uint32_t n_value;    /* value of this symbol (or stab offset) */
};

Mach-O格式如下:

  —— —— —— —— —— —— ——
 |header              |            |.text                  |
 |—— —— —— —— —— —— ——|      ----> |—— —— —— —— —— —— —— ——|
 |load commands       |     |      |.const                 |
 |—— —— —— —— —— —— ——|     |      |—— —— —— —— —— —— —— ——|    |.data         |
 |__TEXT              | ----                                    |—— —— —— —— ——|
 |—— —— —— —— —— —— ——|                                         |.bss          |
 |__DATA              | --------------------------------------> |—— —— —— —— ——|
 |—— —— —— —— —— —— ——|                                         |.nl_symbol_ptr|
 |__LINKEDIT          | ----                                    |—— —— —— —  ——|
 |—— —— —— —— —— —— ——|        |      |.strtab                |    |.la_symbol_ptr|
 |other segments...   |     |      |—— —— —— —— —— —— —— ——|    |—— —— —— —— ——|
 —— —— —— —— —— —— —— —      ----> |.symtab                |    |.got          |
                                   |—— —— —— —— —— —— —— ——|     
                                     |.indirect_symbol_table |

其中,比较特殊的是non lazy symbol pointer和lazy symbol pointer。__DATA中引用符号,以直接指向符号实际地址(而不是符号表地址)的指针形式存储,有non lazy symbol pointer和lazy symbol pointer两种,区别就是是否是使用了plt(延迟绑定)技术,而这些符号如果想要获得更多符号基本信息要通过间接跳转表,所以得名indirection symbol pointer。nl_symbol_ptr为non lazy symbol pointer,la_symbol_ptr为lazy symbol pointer。

更加详细的格式,推荐这篇文章

链接器自举

链接器作为链接其他程序的程序,自然没有其他程序对其进行链接处理,这使得链接程序有这几条苛刻的限制:

  • 不依赖其他库。
  • 在没有地址重定位前,不可以使用全局变量、静态变量,以及其他涉及到地址引用的变量、函数。

在链接器发挥作用前,需要进行”自我链接“,核心过程就是地址重定位,这段”自我链接“的过程就被叫做自举。

引用

程序员的自我修养—链接、装载与库

共享声明:本作品采用 知识共享署名 4.0 国际许可协议 转载时请注明作者和原文链接
本文链接:http://blog.mrriddler.com/计算机体系-链接与装载/