本书讲述构建程序的关键工具——链接器和加载器，内容包括链接和加载、体系结构、目标文件、存储分配、符号管理、库、重定位、加载和覆盖、共享库、动态链接和加载、动态链接的共享库，以及着眼于成熟的现代链接器所做的一些变化；并介绍一个持续的实践项目，即使用Perl语言开发一个可用的小链接器。本书适合高校计算机相关专业的学生、实习程序员、语言设计者和开发人员阅读参考。
经典著作全新译本，添加大量注释，反思20年间技术的“变”与“不变”
自计算机出现以来，链接器和加载器可以说一直是最重要的软件开发工具之一。链接器和加载器使得我们可以按照模块来开发程序，而不必开发一个单独的大文件。
早在1947年，程序员就开始使用加载器技术。这是一种很初级的加载器工作方式，如果程序的若干个例程（routine）存储在多个不同的磁带上，那么就借助加载器将它们依次加载到内存中，并将它们合并、重定位以组合成一个程序。在20世纪60年代早期，这些加载器就已经发展得相当完善了，甚至具备编辑的功能。由于当时内存很贵且容量有限，计算机的速度也很慢（以今天的标准），为了充分利用这样的硬件，这些加载器引入了很多复杂的特性。例如，使用复杂的内存覆盖策略解决内存不足的问题，将大容量的程序加载到有限的内存中；使用链接文件重编辑的机制解决算力不足的问题；使用已链接的模块以节省重新编译程序的时间；等等。
20世纪70到80年代，链接技术几乎没有什么进展。链接器趋向于更加简单。虚拟内存技术将应用程序和覆盖机制中的大多数内存管理工作都转移给了操作系统，同时，计算机的处理速度变得越来越快，硬盘容量越来越大，这使得程序员在更新个别模块时也可以重新链接整个程序，而不必仅仅链接修改的地方。从20世纪90年代起，由于增加了诸如动态链接共享库和C++的诸多现代特性，链接器又开始变得复杂起来。处理器技术的发展也促进了链接器的发展。例如，具有长指令字和编译时访存调度等特性的先进处理器架构（在IA64处理器中开始出现）需要将一些新的特性加入链接器中，以确保在链接器中生成的代码可以满足处理器的一些复杂需求，从而充分发挥硬件的新特性。
读者对象
本书可供下述几类读者阅读。
学生：由于链接过程看起来似乎非常简单，操作的过程也很简捷自然，编译原理和操作系统课程通常对链接和加载的过程缺乏重视。对于使用Fortran、Pascal、C进行简单编程的任务，以及不使用内存映射或共享库的操作系统而言，这么做可能是对的；但是现在情况不一样了。C++、Java和其他的面向对象语言需要更加复杂的链接环境。使用内存映射的可执行程序、共享库和动态链接技术都会影响操作系统的很多部分，操作系统的设计者如果忽略链接问题可能会给系统带来很大的麻烦。
程序员：程序员也需要知道链接器都做了什么，尤其是对现代语言而言。C++语言在链接器中引入了很多新的特性，如果不能正确理解这一过程，在链接大型的C++程序时就容易产生一些难以诊断的bug。例如，最常见的情况是静态构造函数没有按照程序员预期的顺序执行。反之，如果能正确合理地使用链接器，就能够发挥共享库和动态链接等特性的强大功能，提高程序的灵活性。
编程语言的设计者和开发者。编程语言的设计者应该在构建语言和编译器时了解链接器应该做什么，以及能做什么。在过去的30年中必须借助手工完成的编程细节，今天在C++中已经可以借助链接器自动处理了。（想象一下，如何能在C语言中实现和C++中的模板（template）相同的功能；或者，对于数百个C语言源文件组成的工程，如何保证这些文件中的初始化例程可以在主函数开始之前被正确地执行。为了做到这些，程序员需要完成大量工作。）有了功能更强大的链接器，未来的语言将更加智能，能够自动完成更多的常规任务。由于链接器是编译过程中唯一将整个程序的代码放在一起处理的阶段，因此链接器可以将程序作为一个整体进行变换处理，也可以引入更多的全局程序优化功能。
（编写链接器的人员当然都需要本书。但是全球所有的链接器设计者大概只能坐满一个房间，而且其中至少有一半被邀请作为本书的审阅人，相信他们已经看过本书了。）
章节内容
第1章，链接和加载。这一章对链接的过程进行了简短的历史回顾，并讨论了链接过程中的各个阶段。最后通过一个“麻雀虽小，五脏俱全”的例子来展示链接器的工作过程：对于一个“Hello，world”程序，我们分析了以编译好的目标文件为输入，生成一个可执行程序的过程。
第2章，体系结构相关问题。这一章从链接器设计的角度分析了计算机体系结构的技术发展方向。我们分析了典型的精简指令集体系结构SPARC，古老而富有活力的寄存器—内存体系结构—IBM 360/370，以及自成一派的Intel x86体系结构。对于每种体系结构，我们会讨论内存架构、程序寻址架构和指令中的地址格式等重要因素对链接器的影响。
第3章，目标文件。这一章分析了目标文件和可执行文件的内部结构。本章从分析最简单的MS-DOS的.COM文件开始，进而不断扩展到其他复杂的文件，包括DOS的EXE文件格式、Windows的COFF格式和PE格式（EXE和DLL）、UNIX的a.out格式和ELF格式以及Intel/Microsoft的OMF格式等。
第4章，存储空间管理。本章介绍了链接过程的第一个阶段，即以段为单位为被链接的程序分配存储空间。我们以一个实际使用的链接器为例分析了这一过程。
第5章，符号管理。本章介绍了符号绑定和解析的过程，这是一个将符号解析为机器地址的过程，程序中的符号可能在一个文件中被引用，而它的定义出现在另一个文件中。
第6章，库。本章介绍了关于目标代码库创建和使用的相关知识，并分析了库文件的结构和性能问题。
第7章，重定位。本章介绍了地址重定位技术，即调整程序中的目标代码，将指令的目标地址调整为其运行时实际地址的过程。本章还介绍了位置无关代码（Position Independent Code, PIC）的相关技术，使用这种技术构建的代码是无须重定位处理的。本章还分析了这种方法的优势和代价。
第8章，加载和覆盖。本章介绍了加载的过程，即将程序从文件中读取出来并装入计算机内存中以供运行的过程。本章还介绍了覆盖技术，一种基于树状结构实现的内存空间节省技术，是一种古老但是行之有效的技术。
第9章，共享库。本章讨论了在不同程序中共享同一份库代码需要完成的工作。本章主要关注静态链接的共享库。
第10章，动态链接和加载。本章将第9章的讨论延伸至动态链接的共享库，并详细分析了两个具体实例—Win32的动态链接库（DLL）和UNIX/Linux的ELF共享库。
第11章，高级技术。本章着眼于现代链接器技术发生的一些变化。这一章中讨论C++中的一些新特性，包括名称修改（name mangling）、全局构造函数与析构函数、模板扩充和消除重复代码；还介绍了增量链接、链接时垃圾收集、链接时代码生成和优化、加载时代码生成、性能监测和统计。在本章的最后，对Java的链接模式进行了简要阐述，它比本书涉及的其他链接器的语义都更加复杂。
项目
本书中将一个完整的开发项目作为贯穿全书的练习（从第3章到第11章）。这是一个使用Perl语言开发的链接器，虽然精简但是可以正常工作。尽管Perl并不是实现产品级链接器时所使用的编程语言，但对于学生而言，想在一个学期内完成一个链接器，这是很不错的选择。使用Perl省去了很多在C/C++编程中的底层细节，加快了编程速度，使得学生可以把精力集中在链接器相关的算法和数据结构上。Perl是一个免费软件，可以在当前大多数的计算机上运行，包括Windows 95/98/NT、UNIX和Linux，并且还有很多非常优秀的书籍或文档来指导新手快速上手。
在第3章的项目里，构建了一个可以用来读写目标代码的链接器框架，代码的格式虽然简单但却完备。后继章节不断地向这个框架中添加功能，直到最后变成一个支持共享库，能够生成可以动态链接目标代码的功能完善的链接器。
Perl非常擅长处理二进制文件和数据结构，因此如果你愿意，可以扩展该项目中的链接器，使它可以支持你的计算机上使用的目标文件格式。
致谢
有许多人花费了大量的时间来阅读和评论本书的草稿，感谢他们的慷慨付出。这些人中，有些是来自出版社的审阅人，更多的是来自comp.compilers新闻组的读者，他们阅读本书的在线版本并给出了宝贵的建议。下面以姓氏字母顺序列出他们的名字：Mike Albaugh、Rod Bates、Gunnar Blomberg、Robert Bowdidge、Keith Breinholt、Brad Brisco、Andreas Buschmann、David S. Cargo、John Carr、David Chase、Ben Combee、Ralph Corderoy、Paul Curtis、Lars Duening、Phil Edwards、Oisin Feeley、Mary Fernandez、Michael Lee Finney、Peter H. Froehlich、Robert Goldberg、James Grosbach、Rohit Grover、Quinn Tyler Jackson、Colin Jensen、Glenn Kasten、Louis Krupp、Terry Lambert、Doug Landauer、Jim Larus、Len Lattanzi、Greg Lindahl、Peter Ludemann、Steven D. Majewski、John McEnerney、Larry Meadows、Jason Merrill、Carl Montgomery、Cyril Muerillon、Sameer Nanajkar、Jacob Navia、Simon Peyton-Jones、Allan Porterfield、Charles Randall、Thomas David Rivers、Ken Rose、Alex Rosenberg、Raymond Roth、Timur Safin、Kenneth G Salter、Donn Seeley、Aaron F. Stanton、Harlan Stenn、Mark Stone、Robert Strandh、Bjorn De Sutter、Ian Taylor、Michael Trofimov、Hans Walheim、Roger Wong。
本书中的正确结论大部分都是他们努力的结果，而书中的错误都是由作者本人造成的（如果你发现了书中的任何错误，请按下面给出的方式联系作者，以便在后续版本中更正）。特别感谢Morgan Kaufmann出版公司的两位编辑—Tim Cox和Sarah Luger，他们容忍了我写作过程中一次又一次拖延，并把本书中支离破碎的章节拼凑在一起。
联系作者
本书有一个配套网站http://linker.iecc.com，上面有本书的样章、工程项目的Perl代码和目标文件示例，还有本书的更新和勘误。
如果想联系作者，可以向linker@iecc.com发送电子邮件。作者会阅读所有的来信，但可能因收信量过大而无法及时回复所有的问题。
计算机\程序设计
本书讨论了实现链接器和加载器所涉及的技术和面临的挑战，内容非常实用。虽然大多数示例都集中在今天广泛使用的三种计算机体系结构上，但也有许多关于过去有趣而古怪的计算机体系结构的评述。从字里行间不难看出作者曾历经的技术浪潮与思维碰撞，以及这一切过后的冷静与反思。
—— Guy Steele，美国计算机科学家
链接器和加载器是连接编程语言、操作系统、编译器和处理器体系结构的咽喉要道，其中包含多种复杂的技术细节，这些技术在本书英文版出版20余年后的今天依然重要。对于后摩尔定律时代的程序员和编程语言设计者，只有深入理解这些知识，才有可能重新定义软件和硬件系统。
本书深入且完整地揭示了编译时和运行时过程。首先通过实例阐述不同的编译器和操作系统中链接和加载过程的差异，在此基础上，提出实用的建议来帮助读者创建更高效的代码。这些建议包括如何规避和Windows DLL相关的陷阱，以及如何充分利用UNIX ELF库模式等。书中将一个完整的开发项目作为贯穿全书的练习，使用Perl语言逐步实现一个简单但完备的链接器，帮助读者掌握相关算法和数据结构。
本书特色
涵盖Windows、UNIX、Linux和BeOS等操作系统的动态链接过程。
解释了Java链接模式，以及它是如何应用在Applet和可扩展Java代码中的。
指导读者编写优雅的代码，构建能够被更加高效地编译、加载和运行的应用程序。
本书网站http://linker.iecc.com提供更多资源，包括免费的代码示例。
英国作家道格拉斯·亚当斯说道：“任何在我出生时已经有的科技都是稀松平常的世界本来秩序的一部分。”
链接器和加载器技术在程序员的世界里存在感并不强，甚至可能说是透明的。但它却是连接编程语言、操作系统、编译器、处理器体系结构的要害关键之处。如果单纯从应用的视角来看，链接隐藏在编译工具链之后，加载更是“双击”操作之后“自然”完成的。但是，实际上这个过程中包含对指令格式的分析、硬件寻址的过程、未来兼容性的设计、操作系统的支持等多种复杂的技术细节。当我们还在为操作系统和工业软件卡住“喉咙”而警醒的时候，殊不知这些看似成熟稳定到可以被忽视的技术细节，才是操作系统和工业软件的“脖颈”。如果要培养能够通透地理解计算机系统的人才，需要在后摩尔定律时代重新定义软件和硬件系统，而不理解这些知识就无法从根本上达到这一目的。
本书由“大神”John R. Levine教授所著，虽然篇幅较短，却是高屋建瓴，包罗万象，讲述了链接器和加载器一路走来的发展过程和当时展望的多种技术方向，非常值得读者细细研读。“大神”毕竟不同于常人，书中有激烈的思维跳跃，有晦涩难懂的超长句子，也有作者对同行的调侃。译者谨凭着自己的理解试图跟上作者的思路，并写下大量的译者注以期减轻读者的负担，如有贻笑大方或误导之处，恳请读者海涵。
本书英文版于2000年著成，虽已时隔20余年，但仍有很多可取之处。虽然有些书中畅想的技术已经广泛运用，但也有一些被认为是很有前景的方案则销声匿迹，穿过时光，细细读来，别有一番味道。
原书引入我国后经过多次翻译，如李勇老师翻译出版的正式书籍和colyli@gmail.com发布的在线版本等。本书在翻译过程中，受到了诸多前辈的帮助和启发，在此向他们表示感谢。由于译者水平所限，书中难免出现错误，也请各位前辈、同行以及广大读者批评指正。
译者
于南开园
译者序
前言
第1章 链接和加载 1
1.1 链接器和加载器做什么 1
1.2 从历史发展的角度分析地址绑定 1
1.3 链接与加载 3
1.3.1 两遍链接 4
1.3.2 目标代码库 5
1.3.3 重定位和代码修改 6
1.4 编译驱动器 7
1.5 链接：一个真实的例子 9
1.6 练习 12
第2章 体系结构相关问题 13
2.1 应用程序二进制接口 13
2.2 内存地址 13
2.3 地址构成规则 15
2.4 指令格式 15
2.5 过程调用和可寻址性 16
2.6 数据访问和指令引用 19
2.6.1 IBM 370 19
2.6.2 SPARC 21
2.6.3 Intel x86 23
2.7 分页和虚拟内存 24
2.7.1 程序的地址空间 26
2.7.2 文件映射 27
2.7.3 共享库和程序 28
2.7.4 位置无关代码 28
2.8 Intel 386分段 29
2.9 嵌入式体系结构 31
2.9.1 怪异的地址空间 31
2.9.2 非统一内存 31
2.9.3 内存对齐 31
2.10 练习 32
第3章 目标文件 35
3.1 目标文件中有什么 35
3.2 空目标文件格式：MS-DOS的.COM文件 36
3.3 代码分段：UNIX的a.out文件 36
3.3.1 a.out文件头 37
3.3.2 与虚拟内存的交互 38
3.4 重定位：MS-DOS的EXE文件 41
3.5 符号和重定位 43
3.6 可重定位的a.out格式 43
3.6.1 重定位项 44
3.6.2 符号和字符串 44
3.6.3 a.out格式小结 45
3.7 UNIX ELF格式 45
3.7.1 可重定位文件 47
3.7.2 ELF可执行文件 51
3.7.3 ELF格式小结 52
3.8 IBM 360目标文件格式 52
3.8.1 ESD记录 53
3.8.2 TXT记录 54
3.8.3 RLD记录 54
3.8.4 END记录 55
3.8.5 小结 55
3.9 微软的可移植可执行文件格式 55
3.9.1 PE特有区段 59
3.9.2 运行PE可执行文件 60
3.9.3 PE和COFF 61
3.9.4 PE文件小结 61
3.10 Intel/Microsoft的OMF文件格式 61
3.10.1 OMF记录 62
3.10.2 OMF文件的细节 63
3.10.3 OMF格式小结 65
3.11 不同目标文件格式的比较 65
3.12 练习 66
3.13 项目 66
第4章 存储空间管理 69
4.1 段和地址 69
4.2 简单的存储布局 69
4.3 多种类型的段 70
4.4 段与页面的对齐 72
4.5 公共块和其他特殊段 72
4.5.1 公共块 72
4.5.2 C++重复代码消除 73
4.5.3 初始化和终结 75
4.5.4 IBM伪寄存器 76
4.5.5 专用链接表 78
4.5.6 x86的存储分配策略 78
4.6 链接器控制脚本 79
4.7 嵌入式系统的存储分配 81
4.8 实际使用的存储分配策略 81
4.8.1 UNIX a.out链接器的存储分配策略 81
4.8.2 ELF文件中的存储分配策略 82
4.8.3 Windows链接器的存储分配策略 83
4.9 练习 84
4.10 项目 85
第5章 符号管理 87
5.1 符号名绑定和解析 87
5.2 符号表的格式 87
5.2.1 模块表 89
5.2.2 全局符号表 90
5.2.3 符号解析 91
5.2.4 特殊符号 91
5.3 名称修改 92
5.3.1 简单的C和Fortran名称修改 92
5.3.2 C++类型编码：类型和范围 93
5.3.3 链接时类型检查 95
5.4 弱外部符号和其他类型的符号 95
5.5 维护调试信息 96
5.5.1 行号信息 96
5.5.2 符号和变量信息 96
5.5.3 实际的问题 97
5.6 练习 98
5.7 项目 98
第6章 库 99
6.1 库的目的 99
6.2 库的格式 99
6.2.1 使用操作系统 99
6.2.2 UNIX和Windows的归档文件 100
6.2.3 扩展到64位 102
6.2.4 Intel OMF库文件 102
6.3 创建库文件 103
6.4 搜索库文件 104
6.5 性能问题 105
6.6 弱外部符号 105
6.7 练习 106
6.8 项目 106
第7章 重定位 109
7.1 硬件和软件重定位 109
7.2 链接时重定位和加载时重定位 110
7.3 符号重定位和段重定位 110
7.4 基本的重定位技术 111
7.4.1 指令重定位 112
7.4.2 ECOFF段重定位 114
7.4.3 ELF重定位 115
7.4.4 OMF重定位 116
7.5 可重链接和可重定位的输出格式 116
7.6 重定位项的其他格式 117
7.6.1 以链表形式组织的引用 117
7.6.2 以位图形式组织的引用 117
7.6.3 特殊段 117
7.7 特殊情况的重定位 118
7.8 练习 118
7.9 项目 119
第8章 加载和覆盖 121
8.1 基本的加载过程 121
8.2 带重定位的基本加载过程 122
8.3 位置无关代码 122
8.3.1 TSS/360的位置无关代码 123
8.3.2 为每个例程建立的指针表 123
8.3.3 目录表 123
8.3.4 ELF的位置无关代码 124
8.3.5 位置无关代码的开销和收益 126
8.4 自举加载 127
8.5 基于树状结构的覆盖技术 128
8.5.1 定义覆盖技术 129
8.5.2 覆盖技术的实现 131
8.5.3 覆盖技术的其他细节 132
8.5.4 覆盖技术小结 132
8.6 练习 133
8.7 项目 133
第9章 共享库 135
9.1 绑定时间 136
9.2 实际使用的共享库 136
9.3 地址空间管理 137
9.4 共享库的结构 138
9.5 创建共享库 138
9.5.1 创建跳转表 139
9.5.2 创建共享库 139
9.5.3 创建占位符库 139
9.5.4 版本命名 140
9.6 链接时使用共享库 141
9.7 运行时使用共享库 141
9.8 malloc的处理以及其他共享库问题 142
9.9 练习 144
9.10 项目 144
第10章 动态链接和加载 147
10.1 ELF动态链接 147
10.2 ELF文件的内容 147
10.3 加载动态链接的程序 150
10.3.1 启动动态链接器 150
10.3.2 库的查找 150
10.3.3 共享库的初始化 151
10.4 基于PLT的延迟过程链接 152
10.5 动态链接的其他特性 153
10.5.1 静态初始化 153
10.5.2 库的版本 153
10.6 运行时的动态链接 154
10.7 Microsoft动态链接库 154
10.7.1 PE文件中的导入符号和导出符号 155
10.7.2 延迟绑定 157
10.7.3 DLL库和线程 157
10.8 OSF/1伪静态共享库 158
10.9 让共享库快一些 158
10.10 几种动态链接方法的比较 159
10.11 练习 160
10.12 项目 161
第11章 高级技术 163
11.1 C++的链接技术 163
11.1.1 试错式链接 164
11.1.2 消除重复代码 165
11.1.3 基于数据库的方法 166
11.2 增量链接和重链接 166
11.3 链接时的垃圾收集 167
11.4 链接时优化 168
11.5 链接时代码生成 169
11.5.1 链接时采样和插桩 170
11.5.2 链接时汇编 170
11.5.3 加载时代码生成 170
11.6 Java的链接模式 171
11.7 练习 174
11.8 项目 174
参考文献 175
