动态链接

1. 为什么要动态链接

静态链接使得不同的程序开发者和部门能够相对独立地开发和测试自己的程序模块，从某种意义上来讲大大促进了程序开发的效率，原先限制程序的规模也随之扩大。但是慢慢地静态链接的诸多缺点也逐步暴露出来，比如浪费内存和磁盘空间、模块更新困难等问题，使得人们不得不寻找一种更好的方式来组织程序的模块。

内存和磁盘空间

静态链接这种方法的确很简单，原理上很容易理解，实践上很难实现，在操作系统和硬件不发达的早期，绝大部分系统采用这种方式。随着计算机软件的发展，这种方法的缺点很快就暴露出来了，那就是静态链接的方式对于计算机内存和磁盘的空间浪费非常严重。特别是多进程操作系统情况下，静态链接极大地浪费了内存空间，想象一下每个程序内部除了公用库函数还有其他库函数及其所需要的辅助数据结构。

程序开发和发布

静态链接对程序的更新、部署和发布页会带来很多麻烦。一旦程序中有任何模块更新，整个程序就要重新链接、发布给用户。

动态链接

要解决空间浪费和更新困难这两个问题最简单的办法就是把程序的模块相互分割开来，形成独立的文件，而不再将它们静态地链接在一起。简单来讲，就是不对那些组成程序的目标文件进行链接，等到程序要运行时才进行链接。也就是说，把链接这个过程推迟到了运行时再进行，这就是动态链接（Dynamic Linking）的基本思想。

在内存中共享一个目标文件模块的好处不仅仅是节省内存，它还可以减少物理页面的换入换出，页可以增加CPU缓存的命中率，因为不用进程间的数据和指令访问都集中在了同一个共享模块上。

当我们要升级程序库或程序共享的某个模块时，理论上只要简单地将旧的目标文件覆盖掉，而无须将所有的程序再重新链接一遍。当程序下一次运行的时候，新版本的目标文件会被自动装载到内存并且链接起来，程序就完成了升级的目标。

当一个程序产品的规模很大的时候，往往会分割成多个子系统及多个模块，每个模块都由独立的小组开发，甚至会使用不同的编程语言。动态链接的方式使得开发过程中各个模块更加独立，耦合度更小，便于不同的开发者和开发组织之间独立进行开发和测试。

程序可扩展性和兼容性

动态链接还有一个特定就是程序在运行时可以动态地选择加载各种程序模块，这个优点就是后来被人们用来制作程序的插件（Plug-in）。

比如某个公司开发完成了某个产品，它按照一定的规则制定好程序的接口，其他公司或开发者可以按照这种接口来编写符合要求的动态链接文件。该产品程序可以动态地载入各种由第三方开发的模块，在程序运行时动态地链接，实现程序功能的扩展。

动态链接还可以加强程序的兼容性。一个程序在不同的平台运行时可以动态地链接到由操作系统提供的动态链接库，这些动态链接库相当于在程序和操作系统之间增加了一个中间层，从而消除了程序对不同平台之间依赖的差异性。

动态链接页有诸多的问题及令人烦恼和费解的地方。很常见的一个问题是，当程序所依赖的某个模块更新后，由于新的模块与旧的模块之间接口不兼容，导致了原有的程序无法运行。

动态链接的基本实现

动态链接的基本思想是把程序按照模块拆分成各个相对独立部分，在程序运行时才将它们链接在一起形成一个完整的程序，而不是像静态链接一样把所有的程序模块都链接成一个单独的可执行文件。那么我们能不能直接使用目标文件进行动态链接呢？理论上是可行的，但实际上动态链接的实现方案与直接使用目标文件稍有差别。

动态链接涉及运行时的链接及多个文件的装载，必须要有操作系统的支持，因为动态链接的情况下，进程的虚拟地址空间的分布会比静态链接情况下更为复杂，还有一些存储管理、内存共享、进程线程等机制在动态链接下也会有一些微妙的变化。目前主流的操作系统几乎都支持动态链接这种方式，在Linux系统中，ELF动态链接文件被称为动态共享对象（DSO,Dynamic Shared Objects），简称共享对象，它们一般都是以“.so”为扩展名的一些文件；而在Windows系统中，动态链接文件被称为动态链接库（Dynamic Linking Library），它们通常就是我们平时很常见的以“.dll”为扩展名的文件。

在Linux中，常用的C语言库的运行库glibc，它的动态链接形式的版本保存在“/lib”目录下，文件名叫做“libc.so”。整个系统只保留一份C语言库的动态链接文件“libc.so”，而所有的C语言编写的、动态链接的程序都可以在运行时使用它。当程序被装载的时候，系统的动态链接器会将程序所需要的所有动态链接库（最基本的就是libc.so）装载到进程的地址空间，并且将程序中所有未决议的符号绑定到相应的动态链接库中，并进行重定位工作。

程序与libc.so之间真正的链接工作是由动态链接器完成的，而不是由我们前面看到过的静态链接器ld完成的。也就是说，动态链接是把链接这个过程从本来的程序装载前被推迟到了装载的时候。可能有人会问，这样的做法的确很灵活，但是程序每次被装载时都要进行重新链接，是不是很慢？的确，动态链接会导致程序在性能的一些损失，但是对动态链接的链接过程可以进行优化，比如延迟绑定（Lazy Binding）等方法，可以使得动态链接的性能损失尽可能地减小。据估算，动态链接与静态链接相比，性能损失大约在5%以下。当然经过时间的证明，这点性能损失用来换取好处呢个系在空间上的节省和程序构建和升级时的灵活性，是相当值得的。

2. 简单的动态链接例子

在静态链接中，链接过程会把主程序和链接库链接到一起，并且输出可执行文件，整个程序最终只有一个可执行文件，它是一个不可分割的整体；但动态链接中，链接的输入目标文件只有主程序，一个程序被分成了若干个文件，有程序的主要部分，即可执行文件和程序所依赖的共享对象，很多时候我们把这些部分称为模块。

动态链接程序运行时地址空间分布

整个进程虚拟地址空间中，多出了几个文件的映射：

可执行文件和程序所依赖的共享对象一样都是被操作系统用同样的方法映射至进程的虚拟地址空间，只是它们占据的虚拟地址和长度不同
动态链接形式的C语言运行库libc-2.6.1.so
Linux下的动态链接器ld-2.6.so。动态链接器与普通共享对象一样被映射到了进程的地址空间，在系统开始运行程序之前，首先会把控制权交给动态链接器，由它完成所有的动态链接工作以后再把控制权交给程序，然后开始执行。

3. 地址无关代码

固定装载地址的困扰

共享对象在被装载时，如何确定它在进程虚拟地址空间中的位置？

为了实现动态链接，我们首先会遇到的问题就是共享对象地址的冲突问题。程序模块的指令和数据中可能会包含一些绝对地址的引用，我们在链接产生输出文件的时候，就要假设模块被装载的目标地址。很明显，在动态链接的情况下，如果不同的模块目标装载地址都一样是不行的。而对于单个程序来讲，我们可以手工指定各个模块的地址。但是，如果某个模块被多个程序使用，甚至多个模块被多个程序使用，那么管理这些模块的地址将是一件无比繁琐的事情。

早期有些系统采用了这样的做法，这种做法叫做静态共享库（Static Shared Library），它跟静态库（Static Library）有很明显的区别。静态共享库的做法就是将程序的各种模块统一交给操作系统来管理，操作系统在某个特定的地址划分出一些地址块，为那些已知的模块预留足够的空间。静态共享库的目标地址导致了很多问题，除了上面提到的地址冲突的问题，静态共享库的升级也很成问题，因为升级后的共享库必须保持共享库中全局函数和变量地址的不变，如果应用程序在链接时已经绑定了这些地址，一旦更改，就必须重新链接应用程序，否则会引起应用程序的崩溃。即使升级静态共享库后保持原来的函数和变量地址不变，只是增加了一些全局函数和变量，也会受到限制，因为静态共享库被分配到的虚拟地址空间有限，不能增长太多，否则可能会超出被分配的空间。种种限制和弊端导致了静态共享库的方式在现在支持动态链接的系统中已经很少见，而彻底被动态链接取代。

为了解决这个模块装载地址固定的问题，我们设想是否可以让共享对象在任意地址加载？这个问题另一种表述方法就是：共享对象在编译时不能假设自己在进程虚拟地址空间中的位置。与此不同的是，可执行文件基本可以确定自己在进程虚拟空间中的起始位置，因为可执行文件往往是第一个被加载的文件，它可以选择一个固定空间的地址，比如Linux下一般都是0x08040000，Windows下一般都是0x0040000.

装载时重定位

为了能够使共享对象在任意地址装载，我们首先能想到的方法就是静态链接中的重定位。这个想法的基本思路就是，在链接时，对所有绝对地址的引用不作重定位，而把这一步推迟到装载时再完成。一旦模块装载地址确定，即目标地址确定，那么系统就对程序中所有的绝对地址引用进行重定位。

事实上，类似的方法在很早以前就存在。早没有虚拟存储概念的情况下，程序是直接被装载进物理内存的。当时有多个程序运行的时候，操作系统根据当时内存空闲情况，动态分配一块大小合适的物理内存给程序，所以程序被装载的地址是不确定的。系统在装载程序的时候需要对程序的指令和数据中对绝对地址的引用进行重定位。但这种重定位比前面提到过的静态链接中的重定位要简单得多，因为整个程序是按照一个整体被加载的，程序中指令和数据的相对位置是不会改变的。

我们前面在静态链接时提到过重定位，那时的重定位叫做链接时重定位（Link Time Relocation），而现在这种情况经常被称为装载时重定位（Load Time Relocation），在Windows中，这种装载时重定位又被叫做基址重置（Rebasing）。

这种情况与我们碰到的问题很相似，都是程序模块在编译时目标地址不确定而需要在装载时将模块重定位。但是装载时重定位的方法并不适合用来解决上面的共享对象中所存在的问题。可以想象，动态链接模块被装载映射至虚拟空间后，指令部分是在多个进程之间共享的，由于装载时重定位的方法需要修改指令，所以没有办法做到同一份指令被多个进程共享，因为指令被重定位后对于每个进程来讲是不同的。当然，动态链接库中的可修改数据部分对于不同的进程来说有多个副本，所以它们可以采用装载时重定位的方法来解决。

地址无关代码

装载时重定位是解决动态模块中有绝对地址引用的办法之一，但是它有一个很大的缺点是指令部分无法在多个进程之间共享，这样就失去了动态链接节省内存的一大优势。我们还需要有一种更好的方法解决共享对象指令中对绝对地址的重定位问题。其实我们的目的很简单，希望程序模块中共享的指令部分在装载时不需要因为装载地址的改变而改变，所以实现的基本想法就是把指令中那些需要被修改的部分分离出来，跟数据部分放在一起，这样指令部分就可以保持不变，而数据部分 可以在每个进程中拥有一个副本。这种方案就是目前被称为地址无关代码（PIC，Position-independent Code）的技术。

对于现代的机器来说，产生地址无关的代码并不麻烦。我们先来分析模块中各种类型的地址引用方式。这里我们把共享对象模块中的地址引用按照是否为跨模块分成两类：模块内部引用和模块外部引用；按照不同的引用方式又可以分为指令引用和数据访问，这样我们就得到了4种情况：

模块内部的函数调用、跳转等。相对跳转和调用、不需要重定位，但存在共享对象全局符号介入（Global Symbol Interposition）的问题。
模块内部的数据访问，比如模块中定义的全局变量、静态变量。相对寻址。
模块外部的函数调用、跳转等。间接跳转和调用。ELF的做法是在数据段里建立一个指向这些变量的指针数组即全局偏移表（Global Offset Table，GOT）。
模块外部的数据访问，比如其他模块中定义的全局变量。间接访问（GOT）。

共享模块的全局变量问题

有一种很特殊的情况是，当一个模块引用了一个定义在共享对象的全局变量的时候，它无法判断是否为跨模块间的调用。

由于可执行文件在运行时并不进行代码重定位，所以变量的地址必须在链接过程中确定下来。为了能够使得链接过程正常进行，链接器会在创建可执行文件时，在它的.bss段创建一个变量的副本。那么问题就很明显了，变量定义在原先的共享对象中，而可执行文件的.bss段还有一个副本。如果同一个变量同时存在于多个位置中，这在程序实际运行过程中肯定是不可行的。

于是解决的方法只有一个，那就是所有的使用这个变量的指令都指向位于可执行文件中的那个副本。ELF共享库在编译时，默认都把定义在牟凯内部的全局变量当做定义在其他模块的全局变量，也就是是当做前面的类型四，通过GOT来实现变量的访问。当共享模块被装载时，如果某个全局变量在可执行文件中拥有副本，那么动态链接器就会把GOT中的相应地址指向该副本，这样该变量在运行时实际上最终就只有一个实例。如果变量在共享模块中被初始化，那么动态链接器还需要将该初始化值复制到程序主模块 中的变量副本；如果该全局变量在程序主模块中没有副本，那么GOT中的相应地址就指向模块内部的该变量副本。

数据段地址无关性

通过上面的方法，我们能够保证共享对象中的代码部分地址无关，但是数据部分是不是也有绝对地址引用的问题呢？

static int a;
static int* p = &a;

如果某个共享对象里面有这样一段代码，那么p的地址就是一个绝对地址，它指向变量a，而变量a的地址会随着共享对象的装载地址改变而改变。那么有什么办法解决这个问题呢？

对于数据段来说，它在每个进程都有一份独立的副本，所以并不担心被进程改变。从这点来看，我们可以选择装载时重定位的方法来解决数据段中绝对地址引用问题。对于共享对象来说，如果数据段中有绝对地址引用，那么编译器和链接器就会产生一个重定位表，这个重定位表包含了重定位入口，用于解决上述问题。当动态链接器装载共享对象时，如果发现该共享对象有这样的重定位入口，那么动态链接器就会对该共享对象进行重定位。

实际上，我们甚至可以让代码段也使用这种装载时重定位的方法，而不使用地址无关代码。但如果代码不是地址无关的，它就不能被多个进程之间共享，于是也就失去了节省内存的优点，但是装载时重定位的共享对象的运行速度要比使用地址无关代码的共享对象快，因为它省去了地址无关代码中每次访问全局数据和函数时需要做一次计算当前地址以及间接地址寻址的过程。

对可执行文件来说，默认情况下，如果可执行文件是动态链接的，那么GCC会使用PIC的方法来产生可执行文件的代码段部分，以便于不同的进程能够共享代码段，节省内存。所以我们可以看到，动态链接的可执行文件中存在.got这样的段。

4. 延迟绑定（PLT）

动态链接的确有很多优势，比静态链接要灵活的多，但它是以牺牲一部分性能为代价的。我们知道动态链接比静态链接慢的主要原因是动态链接下对于全局和静态的数据访问都要进行复杂的GOT定位，然后间接寻址；对于模块间的低啊用也要先定位GOT，然后再进行间接跳转。另外一个原因是动态链接的链接工作在运行时完成，即程序开始执行时，动态链接器都要进行一次链接工作。下面将介绍优化动态链接性能的一些方法。

延迟绑定实现

在动态链接下，程序模块之间包含了大量的函数引用（全局变量往往比较少，因为大量的全局变量导致模块之间的耦合度变大），所以在程序开始执行前，动态链接会耗费不少时间用于解决模块之间的函数引用的符号查找以及重定位。不过可以想象，在一个程序运行过程中，可能很多函数在程序执行完时都不会被用到，比如一些错误处理函数或者是一些用户很少用到的功能模块等，如果一开始就把所有函数都链接好实际上是一种浪费。所以ELF采用了一种叫做延迟绑定（Lazy Binding）的做法，基本思想就是当函数第一次被用到时才进行绑定，如果没有用到则不进行绑定。ELF使用PLT（Procedure Linkage Table）的方法来实现，这种方法使用了一些很精巧的指令序列来完成。PLT在ELF文件中以独立的段存放，段名通常叫做“.plt”，因为它本身是一些地址无关的代码，所以可以跟代码段等一起合并成同一个可读可执行的Segment被装载如内存。基本原理（略）

5. 动态链接相关结构

动态链接情况下，可执行文件的装载与静态链接情况基本一样。首先操作系统会读取可执行文件的头部，检查文件的合法性；然后从头部中的Program Header中读取每个Segment的虚拟地址、文件地址和属性，并将它们映射到进程虚拟空间的相应位置，这些步骤跟前面的静态链接情况下的装载机基本无异。在静态链接情况下，操作系统接着就可以把控制权交给可执行文件的入口地址，然后程序开始执行，一切看起来非常直观。

但是在动态链接情况下，操作系统还不能在装载完可执行文件之后就把控制权交给可执行文件，因为我们知道可执行文件依赖于很多共享对象。这时候，可执行文件里对于很多外部符号的引用还处于无效地址的状态，即还没有跟相应的共享对象中的实际位置链接起来。所以在映射完可执行文件之后，操作系统会先启动一个动态链接器（Dynamic Linker）。

在Linux下，动态链接器实际上是一个共享对象，操作系统同样通过映射的方式将它加载到进程的地址空间中，之后就将控制权交给动态链接器的入口地址。当动态链接器得到控制权之后，它开始执行一系列自身的初始化操作，然后根据当前的环境参数，开始对可执行文件进行动态链接工作。当所有动态链接工作完成以后，动态链接器会将控制权转交给可执行文件的入口地址，程序开始正式执行。

.interp段

那么系统中哪个才是动态链接器呢，它的位置由谁决定？实际上，动态链接器的位置既不是由系统配置指定，也不是由环境参数决定，而是由ELF可执行文件决定。.interp的内容很简单，里面保存的就是一个字符串，就是可执行文件所需要的动态链接器的路径。在Linux中，操作系统在对可执行文件进行加载的时候，它会去寻找装载该可执行文件所需要相应的动态链接器，即.interp段指定的路径的共享对象。

.dynamic段

这个段里面保存了动态链接器所需要的基本信息，比如依赖于那些共享对象、动态链接符号表的位置、动态链接重定位表的位置、共享对象初始化代码的地址等。

typedef struct {
    Elf32_Sword d_tag;
    union {
        Elf32_Word d_val;
        Elf32_Addr d_ptr;
    } d_un;
} Elf32_Dyn;

Elf32_Dyn结构由一个类型值加上一个附加的数值或指针，对于不同的类型，后面附加的数值或指针有不同的含义。这里列举几个比较常见的类型值：

d_tag类型	d_un的含义
DT_SYMTAB	动态链接符号表的地址
DT_STRTAB	动态链接字符串表地址
DT_STRSZ	动态链接字符串大小
DT_HASH	动态链接哈希表地址
DT_SONAME	本共享对象的SO-NAME
DT_RPATH	动态链接共享对象搜索路径
DT_INIT	初始化代码地址
DT_FINIT	结束代码地址
DT_NEED	依赖的共享对象文件
DT_REL/DT_RELA	动态链接重定位表地址
DT_RELENT/DT_RELAENT	动态重读位表入口数量

动态符号表

为了完成动态链接，最关键的还是所依赖的符号和相关文件的信息。我们知道静态链接中有一个专门的段叫符号表，里面保存了所有关于该目标文件的符号的定义和引用。动态链接的符号表示实际上跟静态链接十分相似。但有导入函数（Import Function）和导出函数（Export Function）的概念，这种导入导出关系放到静态链接的情形下，可以看作普通的函数定义和引用。

为了表示动态链接这些模块之间的符号导入导出关系，ELF专门有一个叫做动态符号表（Dynamic Symbol Table）的段用来保存这些信息，这个段的段名通常叫做.dynsym（Dynamic Symbol）。与静态链接不同的是，只保存了与动态链接相关的符号，对于那些模块内部的符号，比如模块私有变量则不保存。动态符号表也需要一些辅助的表，比如用于保存符号名的字符串表。这里就是动态符号字符串表“.dynstr”（Dynamic String Table）。由于动态链接下，我们需要在程序运行时查找符号，为了加快符号的查找进程，往往还有辅助的符号哈希表“.hash”。

动态链接符号表的结构与静态链接的符号表几乎一样，我们可以简单地将导入函数看作是对其他目标文件中函数的引用；把导出函数看作是在本目标文件定义的函数就可以了。

动态链接重定位表

共享对象需要重定位的主要原因是导入符号的存在。动态链接下，无论是可执行文件或共享对象，一旦它依赖于其他共享对象，也就是说有导入的符号时，那么它的代码或数据中就会有对于导入符号的引用。在编译时这些导入符号的地址未知，在静态链接中，这些未知的地址引用在最终链接时被修正。但是在动态链接中，导入符号的地址在运行时才能确定，所以需要在运行时将这些导入符号的引用修正，即需要重定位。

地址无关章节中提到过，动态链接的可执行文件使用的是PIC方法，但这不能改变它需要重定位的本质。对于动态链接来说，如果一个共享对象不是以PIC模式编译的，那么它是需要在装载时被重定位的；如果一个共享对象是PIC模式编译的，它还需要在装载时进行重定位吗？是的。

对于使用PIC技术的可执行文件或共享对象来说，虽然它们的代码段不需要重定位（因为地址无关），但是数据段还包含了绝对地址的引用，因为代码段中绝对地址相关的部分被分离了出来，变成了GOT，而GOT实际上是数据段的一部分。除了GOT以外，数据段还可能包含绝对地址引用。

动态链接重定位相关结构(略)

共享对象的重定位与静态链接中分析过的目标文件的重定位十分类似，唯一有区别的是目标文件的重定位是在静态链接时完成的，而共享对象的重定位是在装载时完成的。

动态链接时进程堆栈初始化信息

站在动态链接器的角度看，当操作系统把控制权交给它的时候，它将开始做链接工作，那么至少它需要知道关于可执行文件和本进程的一些信息，比如可执行文件有几个段、每个段的属性 、程序的入口地址等。这些信息往往由操作系统传递给动态链接器，保存在进程的堆栈里面。进程初始化的时候，堆栈里面保存了关于进程执行环境和命令行参数等信息。事实上，堆栈里面还保存了动态链接器所需要的一些辅助信息数组（Auxiliary Vector）。

typedef struct
{
    unit32_t a_type;
    union
    {
        unit32_t a_val;
    } a_un;
} Elf32_auxv_t;

它位于环境变量指针的后面。

6. 动态链接的步骤和实现

动态链接器自举

动态链接器本身也是一个共享对象，但是事实上它有一些特殊性。对于普通共享文件来说，它的重定位工作由动态链接器来完成；它也可以依赖于其他共享对象，其中的被依赖的共享对象由动态链接器负责链接和装载。可是对于动态链接器本身来说，它的重定位工作由谁完成？它是否可以依赖于其他的共享对象？

这是一个“鸡生蛋，蛋生鸡”的问题，为了解决这种无休止的循环，动态链接器这个鸡必须有些特殊性。首先是，动态链接器本身不可以依赖于其他任何共享对象；其次是动态链接器本身所需要的全局和静态变量的重定位工作由它本身完成。对于第一个条件我们可以认为地控制，在编写动态链接器时保证不适用任何系统库、运行库；对于第二个条件，动态链接器必须在启动时有一段非常精巧的代码可以完成这项艰巨的工作而同时又不能用到全局和静态变量。这种具有一定限制条件的启动代码往往被称为自举（Bootstrap）。

动态链接器入口地址即是自举代码的入口，当操作系统将进程控制权交给动态链接器时，动态链接器的自举代码即开始执行。自举代码首先会找到它自己的GOT。而GOT的第一个入口保存的即是.dynamic段的偏移地址，由此找到了动态链接器本身的.dynamic段。通过其中的信息，自举代码便可以获得动态链接器本身的重定位表和符号表等，从而得到动态链接器本身的重定位入口，先将它们全部重定位。从这一步开始，动态链接器代码中才可以开始使用自己的全局变量和静态变量。

实际上在动态链接器的自举代码中，除了不可以使用全局变量和静态变量之外，甚至不能调用函数，即动态链接器本身的函数也不能调用。这是为什么呢？实际上使用PIC模式编译的共享对象，对于模块内部的函数调用也是采用跟模块外部函数调用一样的方式，即使用GOT/PLT的方式，所以在GOT/PLT没有被重定位之前，自举代码不可以使用任何全局变量，也不可以调用函数。

装载共享对象

完成基本自举以后，动态链接器将可执行文件和链接器本身的符号表都合并到一个符号表当中，可以称它为全局符号表（Global Symbol Table）。然后链接器开始寻找可执行文件所依赖的共享对象，并将这些共享对象的名字放入到一个装载集合中。然后链接器开始从集合里取一个所需要的共享对象的名字，找到相应的文件后打开该文件，读取相应的ELF文件头和.dynamic段，然后将它相应的代码段和数据段映射到进程空间中。如果这个共享对象还依赖于其他共享对象，那么将所依赖的共享对象的名字放到装载集合中。如此循环知道所有依赖的共享对象都被装载进来为止，当然链接器可以有不同的装载顺序，如果我们把依赖关系看作一个图的话，那么这个装载过程就是一个图的遍历过程，链接器可能会使用深度优先或者广度优先或者其他的顺序来遍历整个图，这取决于链接器，比较常见的算法一般都是广度优先的。

当一个新的共享对象被装载进来的时候，它的符号表会被合并到全局符号表中，所以当所有的共享对象都被装载进来的时候，全局符号表里面将包含进程中所有的动态链接所需要的符号。

符号的优先级

在动态链接器按照各个模块之间的依赖关系，对它们进行装载并且将它们的符号并入到全局符号表时，有可能两个不同的模块定义了同一个符号。这种一个共享对象里面的全局符号被另一个共享对象的同名全局符号覆盖的现象又称为共享对象全局符号介入（Global Symbol Interpose）。

关于全局符号介入这个问题，实际上Linux下的动态链接器是这样处理的：它定义了一个规则，那就是当一个符号需要别加入全局符号表时，如果相同的符号名已经存在，则后加入的符号被忽略。

由于存在这种重名符号被直接忽略的问题，当程序使用大量共享对象时应该非常小心符号的重名问题，如果两个符号重名又执行不同的功能，那么程序运行时可能会将所有该符号名的引用解析到第一个被加入全局符号表的使用该符号名的符号，从而导致程序莫名其妙的错误。

全局符号介入与地址无关代码

前面介绍地址无关代码时，对于第一类模块内部调用或跳转的处理时，我们简单地将其当作是相对地址调用/跳转。但实际上这个问题比想象中要复杂，结合全局符号介入，关于调用方式的分类的解释会更加清楚。由于可能存在全局符号介入的问题，foo函数对于bar的调用不能够采用第一类模块内部调用的方法，因为一旦bar函数由于全局符号介入被其他模块中的同名函数覆盖，那么foo如果采用相对地址调用的话，那个相对地址部分就需要重定位，这又与共享对象的地址无关性矛盾。所以对于bar函数的调用，编译器只能采用第三种，即当作模块外部符号处理，bar函数被覆盖，动态链接器只需要重定位.got.plt，不影响共享对象的代码段。

为了提高模块内部函数调用的效率，有一个办法是把bar函数变成编译单元私有函数，即使用static关键字定义bar函数，这种情况下，编译器要确定bar函数不被其他模块覆盖，就可以使用第一类的方法，即模块内部调用指令，可以加快函数的调用速度。

重定位和初始化

接下来链接器开始重新遍历可执行文件和每个共享对象的重定位表，将它们的GOT/PLT中的每个需要重定位的位置进行修正。因为此时动态链接器已经拥有了进程的全局符号表，所以这个修正过程也显得比较容易，跟地址重定位的原理基本相同。

当完成重定位和初始化之后，所有的准备工作就宣告完成了，所需要的共享对象也都已经装载并且链接完成了，这时候动态链接器就将进程的控制权转交给程序的入口并且开始执行。

Linux动态链接器实现

其实Linux的内核在执行execve()时不关心目标ELF文件是否可执行，它只是简单按照程序头表里面的描述对文件进行装载然后把控制权转交给ELF入口地址。这样我们就很好理解为什么动态链接器本身可以作为可执行程序运行，这也从一个侧面证明了共享库和可执行文件实际上没什么区别，除了文件头的标志位和扩展名有所不同之外。Windows系统中的exe和dll也是类似的区别，Windows提供了一个叫做rundll32.exe的工具可以把一个dll当做可执行文件运行。

动态链接器本身是动态链接的还是静态链接的？

动态链接器本身应该是静态链接的，它不能依赖于其他共享对象，动态链接器本身是用来帮助其他ELF文件解决共享对象依赖问题的。

动态链接器本身必须是PIC的吗？

并不关键，但往往使用PIC会更加简单一些。一方面，不是PIC的话会使得代码段无法共享，浪费内存；另一方面也会使本身初始化更加复杂，因为自举时还需要对代码段进行重定位。

动态链接器可以被当作可执行文件运行，那么它的装载地址应该是多少？

跟一般的共享对象没区别，即为0x00000000。这个装载地址是一个无效的装载地址，作为一个共享库，内核在装载它时会为其选择一个合适的装载地址。

7. 显式运行时链接

支持动态链接的系统往往都支持一种更加灵活的模块加载方式，叫做显式运行时链接（Explicit Runtime Linking），有时候也叫做运行时加载。也就是让程序自己在运行时控制加载指定的模块，并且可以在不需要该模块时将其卸载。如果动态链接器可以在运行时将共享模块装载进内存并且可以进行重定位等操作，那么这种运行时加载在理论上也是很容易实现的。而且一般的共享对象不需要进行任何修改就可以进行运行时装载，这种共享对象往往被叫做动态装载库（Dynamic Loading Library），其实本质上它跟一般的共享对象没什么区别，只是程序开发者使用它的角度不同。

这种运行时加载使得程序的模块组织变得很灵活，可以用来实现一些诸如插件、驱动等功能。当程序需要用到某个插件或者驱动的时候，才将相应的模块装载进来，而不需要从一开始就将他们全部装载进来，从而减少了程序启动时间和内存使用。并且程序可以在运行的时候重新加载某个模块，这样使得程序本身不必重新启动而实现模块的增加、删除、更新等，这对于很多需要长期运行的程序来说是很大的优势。

动态库实际上跟一般的共享对象没有区别，主要的区别是共享对象是由动态链接器在程序启动之前 负责装载和链接的，这一系列由动态链接器自动完成，对于程序本身是透明的；而动态库的装载则是通过一系列由动态链接器提供的API，具体地讲共有4个函数：打开动态库（dlopen）、查找符号（dlsym）、错误处理（dlerror）以及关闭动态库（dlclose），程序可以通过这几个API对动态库进行操作。

dlopen()

用来打开一个动态库，并将其加载到进程的地址空间，完成初始化过程。

void* dlopen(const char* filename, int flag);

第一个参数是被加载动态库的路径，如果这个路径是绝对路径，则该函数将会尝试直接打开该动态库；如果是相对路径，那么会尝试在以一定的顺序去查找该动态库文件：

查找有环境变量LD_LIBRARY_PATH指定的一系列目录
查找由/etc/ld.so.cache里面所指定的共享库路径
/lib、/usr/lib 注意：这个查找顺序与旧的a.out装载器的顺序刚好相反

当然，这在理论上不应该称为一个问题，因为所有的库都应该只存在于某个目录中，而不应该在多个目录有不同的副本，这将会导致系统变得极为不可靠。

很有意思的是，如果我们将filename这个参数设为0，那么dlopen返回的将是全局符号表的句柄，也就是说我们可以在运行时找到全局符号表里面的任何一个符号，并且可以执行它们，这有些类似高级语言反射（Reflection）的特性。全局符号表包括了程序的可执行文件本身、被动态链接器加载到进程中的所有共享模块以及在运行时通过dlopen打开并且使用了RTLD_GLOBAL方式的模块中的符号。

第二个参数flag表示函数符号的解析方式，常量RTLD_LAZY表示使用延迟绑定，当函数第一次被用到时才进行绑定，即PLT机制；而RTLD_NOW表示当模块被加载时即完成所有的函数绑定工作，如果有任何未定义的符号引用的绑定工作没法完成，那么dlopen()就返回错误。上面的两种绑定方式必须选其一。另外还有一个常量RTLD_GLOBAL可以跟上面的两者中任意一个一起使用（通过常量的‘或’操作），它表示将被加载的模块的全局符号合并到进程的全局符号表中，使得以后加载的模块可以使用这些符号。在调试程序的时候我们可以使用RTLD_NOW作为加载参数，因为如果模块加载时有任何符号未被绑定的话，我们可以使用dlerror()立即捕获到相应的错误信息；而如果使用RTLD_LAZY的话，这种符号未绑定的错误会在加载后发生，则难以捕获。当然，使用RTLD_NOW会导致加载动态库的速度变慢。

dlopen的返回值是被加载的模块的句柄，这个句柄在后面使用dlsym或dlclose时要用到。如果加载模块失败，则返回NULL。如果模块已经通过dlopen被加载过了，那么返回的是同一个句柄。另外如果被加载的模块之间有依赖关系，那么程序员需手工加载被依赖的模块。

事实上dlopen还会在加载模块时执行模块中初始化部分的代码，我们前面提到过，动态链接器在加载模块时，会执行.init段的代码，用以完成模块的初始化工作，dlopen的加载过程基本跟动态链接器一直，在完成装载、映射和重定位以后，就会执行执行.init段的代码然后返回。

dlsym()

基本上是运行时装载的核心部分，我们可以通过这个函数找到所需要的符号。

void* dlsym(void* handle, char* symbol);

第一个参数是由dlopen返回的动态库的句柄；第二个参数即所要查找的符号的名字，一个以结尾的C字符串。如果找到了相应的符号，则返回该符号的值；没有找到则返回NULL。返回的值对于不同类型的符号，意义是不同的。如果查找的符号是个函数，那么它返回函数的地址；如果是个变量，返回变量的地址；如果是个常量，返回的是常量值。

有一个问题是：如果常量的值刚好是NULL或者0，我们如何判断dlsym()是否找到了该符号？这就要用到dlerror函数了。如果符号找到了，那么dlerror返回NULL；如果没找到，返回相应的错误信息。

符号优先级

当多个同名符号冲突时，先装入的符号优先，我们把这种优先级方式称为装载序列（Load Ordering）。那么当通过dlopen装入共享对象时，模块之间的符号冲突该怎么解决呢？实际上不管是动态链接器装入的还是由dlopen装入的共享对象，动态链接器在进行符号的解析以及重定位时，都是采用装载序列。

那么当使用dlsym进行符号的地址查找时，是不是也是按照装载序列的优先级进行符号的查找呢？实际的情况是，dlsym对符号的查找优先级分两种类型。第一种情况是，如果我们是在全局符号表中进行符号查找，那么使用的是装载序列；第二种情况是如果我们是对某个通过dlopen打开的共享对象进行符号查找，那么采用的是依赖序列（Dependency Ordering）的优先级。它是以该共享对象为根节点，对它所有依赖的共享对象进行广度优先遍历，直到找到符号为止。

dlerror()

每次我们调用dlopen()、dlsym()或dlclose()以后，我们都可以调用dlerror()函数来判断上一次调用是否成功。dlerror()的返回值类型是char*，如果返回NULL，则表示上一次调用成功；如果不是，则返回相应的错误消息。

dlclose()

dlclose的作用跟dlopen刚好相反，它的作用是将一个已经加载的模块卸载。系统会维持一个加载引用计数器，每次使用dlopen()加载某模块时，相应的计数器加一；每次使用dlclose()卸载某模块时，相应计数器减一。只有当计数器减到0时，模块才被真正地卸载去除。卸载的过程跟加载刚好相反，先执行.finit段代码，然后将相应的符号从符号表中去除，取消进程空间跟模块的映射关系，然后关闭模块文件。