这个Linkers的学习系列，来自Ian Lance Taylor大神的博客。想深入了解的可以直接阅读参考资料里面的链接。
共享库(shared libraries)是为了优化虚拟内存系统而设计的。在没有共享库之前，一些公用函数在每个进程中都存在一份拷贝。现在，在虚拟内存系统中，只需要映射单一拷贝到每个进程的地址空间即可。
据我所知，共享库第一次实现是在SVR3，基于COFF格式。这个实现很简单，只是把每个共享库放在虚拟地址空间的固定位置。这不需要链接器做任何显著的改变。但是要求每个共享库保留一个合适的虚拟地址是不方便的。
SunOS4引入了一种更灵活的共享库，后来被SVR4采纳。这个实现把链接阶段的一些操作延后(postpone)到加载阶段，当程序启动后，自动运行一个限制版本的链接器(limited version of the linker)，将程序链接到相关的共享库。这个限制版本的链接器被称为动态链接器(dynamic linker)。Ian把创建程序的链接器称为程序链接器（program linker），这种共享库的支持需要程序链接器做出显著的改变：创建足够的链接信息，保证动态链接器可以工作。
链接器操作几种基本数据类型：符号（symbols）、重定向（relocations）和内容（contents），这些定义在输入的目标文件中。
符号基本上就是名字或值，符号通常表示源文件的静态目标（static objects），静态即表示在程序中固定在一个单一的位置（single place），如c中的函数、全局变量和静态变量。符号的值仅仅是内容（contents）中的偏移。这种符号被称为定义符号（defined symbol）。
符号也被用来表示对其它目标文件定义的名字的引用，这种符号被称为未定义符号（undefined symbol），还有一些其它比较不常用的符号。
在链接处理过程中，链接器为每个定义符号分配唯一的地址，也会解析每个未定义符号，为其找到相同名字的定义符号。
重定向是在contents上的计算，大多数重定向涉及一个符号，及在contents中的偏移。许多重定向还提供一个额外的操作，叫做addend。一个简单的常用的重定向是设置contents中某个位置到符号的值加addend（set this location in the contents to the value of this symbol plus this addend）。这种计算依赖于处理器架构。
在链接处理过程中，链接器按照要求执行所有的重定向计算。目标文件中的重定向可以涉及未定义符号。如果链接器不能解析符号，通常产生一个错误，但一些符号类型和一些重定向类型除外。
Contents是程序执行过程中的内存情况。内容有一个大小（size），一个字节数组（array of bytes）、和一个类型（type）。包括编译器和链接器产生的机器码（machine code）。包括已初始化变量的值（data）。包括静态无名数据（static unnamed data），如字符串常量和swtich表，（read-only data or rdata）。包括未初始化变量（bss），这种段不包含字节数组，字节数组被假想为0。
编译器和汇编器按照规则严格产生正确的contents，但是链接器不关心他们，当做raw data处理。链接器读取每个文件的所有contents。按照type顺序把他们拼接在一起，执行重定向，将结果写入到可执行文件。
至此，我们已经知道的够多了，可以理解每个链接器的基本步骤：
读取输入目标文件，获取contents的长度及类型，获取符号。
建立包含所有符号的符号表，链接未定义符号到他们的定义。
决定所有的contents应该待在输出可执行文件的哪个位置，意味着决定他们在程序运行时，待在内存的哪个地方。
读取contents data和relocations，执行重定向到contents，输出结果到输出文件。
可选输出包含完整的符号最终值的符号表。
地址空间只是内存的一个view，每一个字节都有一个地址，链接器处理3种不同类型的地址空间。
每一个输入目标文件都是一个小地址空间，contents有地址，符号和重定向通过地址指向（refer to）contents。
输出程序在运行的时候，被放到内存的一个区域，这是输出地址空间，我通常叫它虚拟内存地址（virtual memory addresses）。
输出程序加载到内存的某个地址，这个是加载内存地址（load memory addresses）。在典型的Unix系统上，虚拟内存地址和加载内存地址相同，但是在嵌入式系统上通常不同，初始数据段可能以加载内存地址加载到ROM，然后以虚拟内存地址拷贝到RAM。
共享库通常运行在不同进程的不同的虚拟内存地址，共享库创建的时候有一个基地址（base addresses），基地址通常为0。当动态链接器把共享库拷贝到进程的虚拟地址空间时，它必须执行重定向，以便共享库运行在虚拟地址空间。共享库会最小化重定向次数，因为重定向消耗时间。
目标文件格式设计为做为linker的输入，可执行文件格式设计为作为操作系统或者加载器的输入，通常目标文件格式和可执行文件格式非常相似。
大多数目标文件格式定义段（sections），一个段典型地包含内存内容，或者用来包含其它类型的数据，段通常有一个名字、类型、大小、地址以及相关的数据数组。
目标文件格式可以分成两种常用类型：record oriented 和 section oriented。
IEEE-695和Mach-O是record oriented 目标文件格式。
section oriented目标文件格式包含一个section table，有特定数量的sections。ELF, COFF, PE和a.out都是这种类型的目标文件格式。
目标文件可以包含调试信息（debugging information）。通常链接器像其他类型的数据一样对待调试信息，然而链接器为了减少输出文件大小，需要了解调试信息。
a.out格式将调试信息以特殊字符串存储到符号表中，stabs。这些字符串只是一个特殊类型的符号。
COFF格式将调试信息存储到符号表中特殊的域。
ELF格式存储调试信息到段，用特殊的名字，可以是stabs字符串或者DWARF调试格式。
当程序链接器创建共享库时，它还不知道共享库运行在什么虚拟地址。实际上，不同的进程，同一个共享库将运行不同的地址，这依赖于动态加载器的决定。这意味着动态链接库代码必须是位置独立（position independent）的。更精确的说，动态链接器加载完后必须是位置独立的。动态链接库当然可以将任何代码片段转换为可运行在任何虚拟地址，只要提供足够的可重定向信息，但是这样会使加载变的缓慢，因此任何共享库系统寻求产生位置无关代码，以保证运行时只要求很少的重定向。
ELF共享库的一个额外的复杂性是，其被设计成和普通的archives完全一样。这意味着可执行文件可能覆盖共享库的符号，如此共享库可能调用可执行文件的定义，即使共享库已经定义了该符号。
通常，代码可以编译成两种模式：
缺省，代码是位置依赖（position dependent）的，将位置依赖的代码放入共享库将导致程序链接器产生很多重定向信息，导致动态链接器需要做更多的运行时处理。
也可以编译成位置独立模式，通过-fPIC选项，位置独立代码会稍微慢一点，当他调用非静态函数或引用全局或静态变量时。然而位置独立代码不要求很多的重定向信息，因此动态链接器启动程序更快。
位置独立代码通过PLT(Procedure Linkage Table)来调用非静态函数。这种PLT不存在.o文件中，在.o中，使用PLT意味着特殊的重定向，当程序连接器产生这种重定向，它在PLT中添加一个条目，它调整指令以便其成为PC相对PLT条目的调用（PC-relative call to PLT entry）。PC相对调用是位置无关的，因为它不要求重定向信息。程序链接器创建PLT条目的重定向信息，告诉动态链接器哪个符号和该条目关联，这个处理减少了共享库中从一个函数到另一个函数调用的动态重定向信息。
PLT条目的重定向是被动态链接器懒加载的，直到一些代码真的调用函数时，动态链接器才执行重定向。在大多数ELF系统中，可以通过LD_BIND_NOW环境变量来关闭。
程序链接器初始化条目，加载一个索引到一些寄存器或者压入栈，然后跳转到公共代码，公共代码跳入动态链接器，其使用索引来找到合适的PLT重定向信息，找到要调用的函数，动态链接器然后使用函数的地址初始化PLT条目，然以跳入函数代码。函数下次被调用时，PLT条目直接跳到函数。
在给出例子前，我想谈论一下位置独立代码的另一个主要结构，Global Offset Table。GOT用于全局和静态变量。对于位置独立代码中对全局变量的每个引用，编译器将产生一个加载：从GOT中获取变量的地址，第二个加载获得变量的实际值。基于效率考虑，GOT的地址通常保存在一个寄存器中。和PLT类似，GOT不存在.o文件中，其由程序链接器产生。程序链接器产生动态重定向，动态链接器用它来初始化GOT。和PLT不同，GOT是在程序开始时完全初始化。
下面是i386的例子：
GOT的地址存储在%ebx寄存器，这个寄存器在每个函数的入口处被设置。设置指令代码不同的编译器不同，但是典型地如下：
call __i686.get_pc_thunk.bx add $offset,%ebx |
__i686.get_pc_thunk.bx函数，看起来如下：
| mov (%esp),%ebx ret |
这个指令序列使用位置独立代码来获取GOT的地址，这要求GOT始终相对于代码为一个固定的偏移，而不管共享库加载在何处。这要求动态链接器加载共享库作为一个固定的单元，而不能不同的部分到变化的地址。
第一个加载完成了，程序链接器为每一个条目创建动态重定向，告诉动态链接器如何初始化条目，这些重定向是GLOB_DAT类型。对于函数调用，程序链接器设置PLT条目，看起来如下：
jmp *offset(%ebx) pushl #index jmp first_plt_entry |
程序链接器为每一个PLT条目分配一个GOT条目，这样就创建了GOT的动态重定向，类型为JMP_SLOT。它初始化GOT条目到共享库的基地址加上上述代码许了第二条指令的地址。当动态链接器初始化懒绑定，执行JMP_SLOT重定向时，它简单地加上共享库加载地址和基地址的差。第一个jmp指令的效果是跳转到第二个指令，其将index entry压栈，跳转到第一个PLT条目，第一个PLT条目有点特别，看起来如下：
| pushl 4(%ebx) jmp *8(%ebx) |
这引用了GOT的第二和第3个条目，动态链接器将初始化它们到合适的值，以便调回动态链接库。动态链接库通过压入的索引来找到JMP_SLOT重定向，当动态链接器决定要调用的函数后，将其地址存到GOT条目，下次调用时，jmp指令就直接跳到了正确的位置。
上述是许多细节的快速带过，但是我希望它表达了主要的信息。对于i386的PIC，每个全局函数的调用第一次需要一个额外的指令，每个全局或静态变量都需要一个额外的指令。几乎每个函数使用4个额外的指令来初始化%ebx。不使用全局变量和静态变量的叶子函数不需要初始化%ebx。这些对程序缓存有一个副作用。这也是动态链接器快速启动程序的运行时惩罚。
在其它处理器，细节自然不同，但是基本相似，PIC使启动更快，但是运行稍微慢一点。
[1] Ian Lance Taylor. Linkers part 2. http://www.airs.com/blog/archives/39
[2] Ian Lance Taylor. Linkers part 3. http://www.airs.com/blog/archives/40
[3] Ian Lance Taylor. Linkers part 4. http://www.airs.com/blog/archives/41
[4] Ulrich Drepper. How To Write Shared Libraries. Dec, 10, 2011.