链接

1. 什么是链接，作用是啥

• 链接：一个复杂软件分为很多的模块，人们把每个模块独立地编译，然后按需组装起来的过程就是链接。主要包括地址和空间分配、符号决议（也叫符号绑定、名称绑定、地址绑定）、重定位
• 作用：把各个模块之间相互引用的部分都处理好，使得各个模块之间能够正确的衔接。

2. 什么是符号

符号表示一个地址，可能是函数的起始地址，或是变量的起始地址

3. 动态链接和静态链接的区别

• 静态链接：输出的是一个可执行文件，如果进程中有多个程序同时引用模块A，则可执行文件中有模块A的多个副本，即磁盘和内存均有模块 A 的副本，导致部分空间被浪费。并且即使部分模块更新，都需要重新链接生成可执行文件。
• 动态链接：把链接过程推迟到运行时。只需要加载一次引用的模块。例如Program.o 依赖Lib.o，运行前系统会检查内存，如果Lib.o在内存中，只需要将 Program.o 与 Lib.o 文件链接起来即可。

4. 如果两个线程同时访问一个函数，是否需要加锁

不需要，每个线程都有自己的虚拟空间，函数中的局部变量会被保存在对应的线程中。如果要访问全局变量、静态变量，则需要加锁。

5. 链接器链接的是目标文件，那么目标文件里都有啥？

1. 什么是目标文件

编译器编译源代码后生成的文件叫做目标文件。从结构上讲，它是已经编译后的可执行文件格式，只是没有经过链接的过程，其中有些符号或地址没有被调整。但它本身是按照可执行文件格式存储的。

2. 目标文件的大体结构是啥

目标文件有编译后的机器指令代码、数据以及链接时所需的信息，如符号表、调试信息、字符串等，根据属性不同以"段(segment)"存储。

• 文件头：ELF 文件头：包含整个文件的基本属性如版本、目标基本型号、程序入口地址等，以及段表（ELF文件包含的段的信息如段名、段长等）

• 程序指令：

  • 代码段(Code Section)：程序源代码编译后机器指令放在代码段，常见的名字有 .code 或 .text 等。

• 程序数据

  • 数据段(Data Section): 全局变量、局部静态变量存放在数据段，一般名为 .data
  • .bss 段：未初始化的全局变量和局部静态变量存放于此。由于未被初始化，只是被预留了位置，所以并不占据文件空间，但是在装载时占用地址空间

• 其他的段

  • 只读数据段：.rodata，程序中的只读变量(如 const 修饰的变量、字符串常量)
  • 注释信息段：.comment，编译器版本信息，如字符串“GCC:(GNU) 4.2.0”
  • 重定位段：.real.text 为代码段的重定位表，如果是 .data 的重定位表则是 .real.data
  • 符号表段：.symtab。函数、变量统称为符号，符号值为它们的地址
  • 动态链接信息：.dynamic
  • 动态链接的跳转表和全局入口表：.plt, .got

6. 静态链接的步骤

总结：链接器合并所有的输入目标文件，并计算出文件中各个段合并后的长度与位置，并把所有的符号放入全局符号表，然后分配虚拟地址，然后能够计算出各个符号的虚拟地址。根据各个段对应的重定位表，进行重定位

主要包括：空间与地址分配、符号解析与重定位

空间与地址分配

1. 链接就是将几个输入目标文件加工后合成一个输出文件。对于多个输入文件，链接器如何将各个段合并到输出文件？

   相似段合并。将相同性质的段合并到一起，例如所有文件的 .text 段合并到输出文件的 .text 段，接着是 .data 段、.bss 段。因此经过合并后，就能计算出输出文件中各个段合并后的长度与位置

2. 输出文件中每个段以及符号的地址何时被确定

   当目标文件全部合并完毕后，就会被分配虚拟地址。按照每个段在输出文件中的位置和大小，每个段被分配到了相应的虚拟地址。即空间分配完成后，各个段就会确定自己在虚拟地址空间中的位置，相应的，断种各个符号也会确定各自的地址

3. 符号地址怎么被确定的

   在第一步的扫描和空间分配阶段，链接器会对各个段进行空间分配，此时各个段在链接后的虚拟地址就被确定了。例如 .text 段的起始地址未 0x08048094。

   由于各个符号在段内的相对位置固定，各个符号的地址也就确定了，链接器只需要给每个符号加上一个偏移量，使它们能调整到正确的虚拟地址。例如， a.o 中的 main 函数相对于 a.o 的 .text 段的偏移是 X，经过链接合并后，a.o 的 .text 段位于虚拟地址 0x08048094，那么 main 的地址为 0x08048094 + X，而 main 位于 a.o 的 .text 段的最开始，即偏移为 0，所以 main 这个符号在最终的输出文件中的地址应该为 0x08048094 + 0，即 0x08048094

符号解析与重定位

1. 符号解析

   重定位过程中，每个重定位入口都是对一个符号的引用。当链接器要对某个符号的引用进行重定位时，就要确定这个符号的目标地址，因此会去由所有输入目标文件的符号组成的全局符号表中，查找对应的符号进行重定位。

   即，如果某个文件定义了一个全局的符号，当该符号的地址确定以后，会在全局符号表中更新自己的地址，以便其它引用该符号的目标文件进行重定位时使用。

2. 什么是重定位？

   源代码被编译成目标文件时，编译器并不知道里面的符号的地址，因为大部分符号是被定义在其他的目标文件中，因此暂时用地址 0 作为符号的地址。链接器在完成空间和地址分配以后，就可确定所有符号的虚拟地址，链接器就可以根据符号的地址对每个需要重定位的指令进行地址修正

3. 链接器怎么知道哪些指令要被调整？这些指令的哪些部分要被调整？怎么调整？

   每个要被重定位的 ELF 段都有一个对应的重定位段（也叫重定位表），例如代码段 .text 如有要被重定位的地方，就会有一个相应的 .rel.text 的段保存了代码段的重定位表。

   每个要被重定位的地方叫一个重定位入口。重定位入口的偏移表示该入口在要被重定位的段中的位置。具体参见《程序员的自我修养》107页。例如，重定位段 .rel.text 中内容 OFFSET 为 0000001c 、 VALUE 为 shared 表示代码段中偏移为 0000001c 的位置要被调整。书中 0x1c 为代码段中 mov 指令的地址部分

链接是以一个文件为单位吗？如果只用到某个文件中的一个函数，也要链接整个文件吗？

链接器在链接静态库时是以目标文件为单位的。因此即使只用一个函数，也要将整个目标文件链接在一起。这也是很多静态运行库里面一个目标文件只包含一个函数的原因。

例如我们引用了静态库中的 printf() 函数，那么链接器会把库中包含 printf() 函数的那个目标文件链接进来，如果很多函数都放在一个目标文件，很可能很多没用的函数都被一起连接筋了输出结果中。由于运行库有成百上千个函数，每个函数独立放在一个目标文件中可以尽量减少空间的浪费，那些没有被用到的目标文件（函数）就不要链接进最终的输出文件中。

7. 静态链接重复的代码太多时，有什么方法解决吗？

重复代码消除

8. 可执行文件在内存中怎么分布的

装载是什么？作用是什么？

程序只有在内存中才能被 CPU 执行。将程序从外部存储器中读取到内存中的某个位置的过程就是装载。

目前使用的装载是哪种方式？

• 静态装入：将程序执行时所需要的指令和数据全都装入内存中。
• 动态装入：程序运行时有局部性原理，因此只将程序最常用的部分驻留在内存中，而将一些不常用的数据存放在磁盘中。基本思想：程序用到那个模块，就将哪个模块装入内存中，如果不用就暂时不装入，放在磁盘中。
  • 覆盖装入：将模块按照它们之间的调用依赖关系组织成树状结构
  • 页映射：将内存和磁盘中数据和指令按照页为单位划分为若干个页，所有的装载和操作的单位为页。内存不足时会使用 FIFO（先进先出算法）、LUR（最少使用算法）等来放弃正在使用的内存页，来装载新的需要使用的页

每次页被装入时都需要进行重定位吗？

几乎所有的硬件都采用 MMU(Memory Management Uint) 进行页映射。在页映射模式下，CPU 发出的是 Virtual Address，即程序中看到的虚拟地址。经过 MMU 转换以后变成了 Physical Address。一般 MMU 都集成在 CPU 内部，不会以独立的部件存在。

因此，程序的虚拟地址可能有2G，而实际的物理地址只有1G，通过页映射与装载，用到的页在发生页错误时会被操作系统重新建立虚拟页和物理页的映射关系

进程建立的过程分为几步

1. 创建一个独立的虚拟地址空间：创建虚拟空间到物理内存的映射关系。虚拟空间由一组映射函数将虚拟空间的各个页映射至相应的物理空间。以 i386 的 Linux为例，创建虚拟地址空间实际只是分配一个页目录即可。
2. 读取可执行文件头，并建立虚拟地址空间与可执行文件的映射关系：创建虚拟空间与可执行文件的映射关系。当程序执行发生页错误时，操作系统从物理内存中分配一个物理页，然后将程序中发生错误的“缺页”从磁盘中读取到内存，再设置缺页的虚拟页与物理页的映射关系，因此操作系统需要知道程序当前的页在可执行文件中的具体位置，即虚拟空间与可执行文件之间的映射关系。
3. 将 CPU 的指令寄存器设置成可执行文件的入口地址，启动运行

ELF 文件被映射时是按照系统的页长度为单位的，如果每个段的长度不是系统页的长度，是否会产生很多内存浪费？

段有可读、可写、可执行几种权限，对于相同权限的段，操作系统会把它们合并到一起当做一个段进行映射。例如 .text 和 .init 分别为程序的可执行代码和初始化代码，都为可读可执行权限，因此会被系统作为一个整体，映射为同一个 segment(ELF 文件中概念，与目标文件中 section 名字都为段，意义不同)。

一个进程基本可以分为以下几种 VMA 区域：

• 代码 VMA，权限只读、可执行：有映像文件
• 数据 VMA，权限可读写、可执行：有映像文件
• 堆 VMA，权限可读写、可执行：无映像文件，匿名，可向上扩展
• 栈 VMA，权限可读写、不可执行：无映像文件，匿名，可向下扩展

9. 动态链接

动态链接的基本步骤是什么？

动态链接的基本思想是把程序按照模块拆分成各个相对独立的部分，在程序运行时才将它们链接在一起形成一个完整的程序，而不是像静态链接一样把所有的程序模块都链接成一个单独的可执行文件。

当程序被装载时，系统的动态链接器会将程序所需要的所有动态链接库（.so 文件，即动态共享对象，也称共享对象）装载到进程的地址空间，并将程序中所有未绑定的符号绑定到相应的动态链接库中，并进行重定位工作。

程序与 .so 文件之间的链接工作是由动态链接器完成的，动态链接器把链接这个过程从本来的程序装载前推迟到了装载的时候，因此共享对象的最终装载地址在编译时是不确定的，而是在装载时被分配了虚拟地址。

程序模块 A 引用共享对象中函数 B，实际链接时，编译器如何确定符号 B 是一个静态符号，还是一个动态符号？

共享对象中保存了完整的符号信息，链接器在解析符号时就可以知道：符号 B是一个定义在共享对象中的动态符号。这样链接器就可以对 B 的引用做特殊处理，使它成为一个对动态符号的引用。

动态链接有什么缺点？

程序所依赖的某个模块更新后，由于新旧模块间的接口不兼容，导致原有的程序无法运行。因为它们缺少一种有效的共享库版本管理机制，这个问题被称为 "DLL Hell"。

共享对象会被多个程序引用，由于虚拟内存的原因，共享对象在各个程序（模块）中的地址不一样，指令中对绝对地址的重定位就会出现冲突，应该怎么办？

将指令中那些需要被修改的部分分离出来，跟数据部分放在一起，这样指令部分就可保持不变，而数据部分可以在每个进程中有一个副本，这种方案为地址无关代码技术。程序主模块的代码不是地址无关代码

共享对象中地址引用有哪几种？

• 模块内部调用或跳转：模块内部调用的函数与调用者处于同一个模块，它们之间的相对位置是固定的，因此可以用相对地址调用或基于寄存器的相对调用
• 模块内部数据访问：任何一条指令与它需要访问的模块内部数据之间的相对位置是固定的，只需要相对于当前指令加上固定的偏移量就可以访问模块内部数据了。
• 模块间数据访问：ELF 的做法是在数据段里建立一个指向这些变量的指针数组，称为全局偏移表（Global Offset Table, GOT），当代码需要引用该全局变量时，可通过 GOT 中相对应的项间接引用。例如模块 A 使用模块 B 中变量 b，变量 b 的地址在装载时才能确定，具体是链接器在装载模块的时候会查找每个变量所在的地址，然后填充 GOT 中的各个项，以确保每个指针指向的地址正确。当指令要访问变量 b时，程序会先找到 GOT，然后根据 GOT 中变量所对应的的项找到变量的目标地址。由于 GOT 本身是放在数据段，所以它可以在模块装载时被修改，并且每个进程都可以有独立的副本，不受影响。
• 模块间调用、跳转：与模块间数据访问类似，GOT 中对应的项保存的是目标函数的地址，当模块要调用目标函数时，可通过 GOT 中的项进行间接跳转。

动态链接将 .got 中的全局变量的地址直接放到放到全局符号表中不就可以了吗，为何要单独建一个 .got？

全局符号表只有一个，当共享文件需要被多个程序引用时，无法做到每个符号在不同的程序中都是不同的，因此要用到 .got，在每个程序中保存一份独有的数据

动态链接相对于静态链接要慢的原因是什么？

1. 动态链接下对于全局和静态的数据访问都要进行复杂的 GOT 定位，然后间接寻址，对于模块间的调用也要先定位 GOT，然后再进行间接跳转
2. 动态链接的链接工作在运行时完成，即程序开始执行时，动态链接器都要进行一次链接工作。动态链接器会寻找并装载所需要的共享对象，然后进行符号查找地址重定位

针对动态链接速度慢的问题的优化方式是什么？

延迟绑定（PLT），即函数第一次被用到时才进行绑定（符号查找、重定位等）。

当调用某个外部模块的函数时，应该是通过 GOT 中相应的项进行间接跳转。PLT 为了实现延迟绑定，在这个过程中增加了一层间接条状。调用函数通过一个叫做 PLT 项的结构来跳转。以共享对象中 bar() 函数为例，具体过程如下：参考《程序员的自我修养》201 页

bar() 函数在 PLT 中项的地址为 bar@plt。

1. 类似于 iOS 开发中的 lazy var 或者 单例。当链接器在初始化阶段已经初始化该项，并将该项的地址填入该项，则跳转指令直接跳转。
2. 为了实现延迟绑定，链接器初始化阶段没有填入该项。而是将 .rel.plt 中 bar 符号的下标以及 bar 符号待绑定模块 id 填入其中。当需要重定位时会调用动态链接器完成符号解析和重定位，并将真正的地址填入 bar@plt 中。

动态链接特有的段有哪几个？

1. .interp 段：表明可执行文件所需要的动态链接器的路径
2. .dynamic 段：动态链接 ELF 中最重要的结构，保存了动态链接器所需要的基本信息，如依赖于哪些共享对象、动态链接符号表的位置、动态链接重定位表的位置、共享对象初始化代码的地址，类似于 ELF 文件头中保存的静态链接时相关的内容
3. .dynsym 段：保存动态链接相关的符号，而静态链接只有 .symtab，动态链接中 .symtab 保存了所有的符号，包括了 .dynsym 中的符号
4. .rel.dyn：相当于静态链接的 .rel.text。是对数据引用的修正，它所修正的位置位于 .got 以及数据段
5. .rel.plt：相当于静态链接的 .rel.data，是对函数引用的修正，它所修正的位置位于 .got.plt

动态链接库 .so 文件在每个进程中的逻辑地址相同吗？

是否相同无关紧要。进程为动态链接库使用的全部数据分配了自己的地址空间。动态链接库只是实现了代码的复用，对于数据，各个程序要自己保存。

地址无关代码 PIC 具体怎样

数据段里简历一个指向模块要访问的外部变量和函数的指针数组，称为全局偏移表 GOT。模块要访问别的模块的函数和数据时，会先找到 GOT，根据 GOT 中变量对应的项找到变量的目标地址。

GOT 中的变量地址是何时被填充的？

链接器在装载模块时会查找每个变量所在的地址，然后填充 GOT 中每个项，由于 GOT 是放在数据段的，所以每个进程可以有一个独立的副本。GOT 表中的每一项都是对外部数据的引用，在未加载到进程空间中，表项都为空，需要在加载时进行填充。链接器在装载模块的时候会查找每个变量所在的地址，然后填充 GOT 中的各个项。那么装载器如何知道要填充哪些数据呢？答案是通过动态链接器的重定位表。因此 GOT 中地址被填充的过程即是重定位的过程

怎样找到 GOT 表

GOT 表位于数据段中，而数据段与代码段中各条指令相对位置是固定的，因此通过位置偏移即可确定 GOT 表的位置

动态链接的步骤

1. 启动动态链接器

   动态链接器也是一个共享对象，但是有如下特点：首先动态链接器不依赖于其他任何共享对象；其次，动态链接器本身所需要的全局和静态变量的重定位工作由它本身完成（这种启动代码称为自举代码）。

2. 装载所需要的共享对象

   完成基本自举以后，动态链接器将可执行文件和链接器本身的符号表合并到一个符号表当中，称为全局符号表，然后寻找可执行文件所依赖的共享对象。将 .dynamic 段中指出的可执行文件所依赖的共享对象名字放入一个装载集合中，读取对应的文件，并将对应的代码段、数据段映射到进程空间中。因此当所有的共享对象都被装载进来时，全局符号表里将包含进程中所有的动态链接所需要的符号。

3. 重定位和初始化

   完成上面的步骤后，链接器重新遍历可执行文件和每个共享对象的重定位表，将它们的 GOT、PLT 中的每个需要重定位的位置进行修正，因为此时动态链接器已经拥有了进程的全局符号表。

   完成重定位后，如果某个共享对象有 .init 段，则动态链接器会执行 .init 段中代码，用以实现共享对象特有的初始化过程，例如共享对象中 C++ 的全局/静态对象的构造就需要通过 .init 来初始化。如果进程的可执行文件也有 .init 段，动态链接器不会执行，因为可执行文件中的 .init 段由程序初始化部分代码负责执行。

10. 为什么一个编译好的简单的 Hello World 程序也需要占据好几 KB 的空间？

需要用到其他的动态库，例如 printf 所在的库

11. 程序和进程有什么区别

• 程序是静态概念，它就是一些预先编译好的指令和数据集合的一个文件。
• 进程是一个动态概念，它是程序运行时的一个过程。

程序和进程跟做菜相比较的话，程序是菜谱，计算机的 CPU 就是人，相关的厨具则是计算机的其他硬件，整个炒菜过程就是一个进程。计算机按照程序的指示，把输入数据加工成输出数据，就像菜谱指导人把原料做成菜肴。

12. 启动过程包含地址绑定，iOS App 包中的内容是链接的中间产物吗？

iOS App 是动态链接，因此包中的产物应该是汇编并处理后的结果，为加载时动态链接做准备

参考

1. 程序员的自我修养