• 编译过程：高级语言->机器语言
  • 词法分析：扫描器->有限状态机->Token
  • 语法分析：上下无关文语法->语法树(表达式为节点)
  • 语义分析：静态语义（声明和类型匹配，类型转换等）->标记类型，动态语义
  • 中间语言生成：源代码优化、跨平台
  • 目标代码生成与优化：代码生成器（依赖机器）、目标代码优化器（替换指令、删除多余指令等） 这个过程中，index和array的wei位子还未确定。

静态链接

链接器要做的共工作其实跟“程序员人工调整地址”本质没什么两样。 过程主要包括：地址空间分配、符号决议（绑定）、重定位 main.c : 当跨模块调用另一个函数比如foo时，必须知道函数地址。 - 目标文件：编译器编译成的东西(.o,.obj) - 库：一组目标文件的包 - 重定位：当前模块无法确定目标位置，等待链接器在链接后修正，这个过程叫做重定位,被修正的地方叫做重定位入口

目标文件里有什么

• 目标文件格式：Windows的PE和Linux的ELF（源于COFF）
  • 广义上看，目标文件和可执行文件的格式几乎一样，因此可以看作一种类型
  • 动态链接库（dll/so）和静态链接库（lib/a）都是。静态链接库稍有不同，是把很多目标文件捆绑在一起形成一个文件，再加上一些索引，可以看作一个文件包。
  • ELF：可重定位文件，可执行文件，共享目标文件，核心转储文件
• COFF主要贡献：段机制
• 目标文件有什么：机器指令代码、数据、符号表、调试信息、字符串、重定位表等。
  • 存储方式：按不同的属性，以“节”（段）的形式存储。
    • 文件头：整个文件属性（是否可执行（入口地址）、静态链接、动态链接）、目标硬件、目标操作系统、段表（一个数组，偏移位置和段的属性）
    • 代码段：.code/.text
    • 数据段：.data
    • 未初始化数据段(.bss，都是0，预留位置，文件中不占据空间无CONTENTS标识)
    • 只读数据段：.rodata--只读变量和字符串常量（有些编译器会放到data）
    • 其他段：.comment注释信息段，.note.GNU-stack堆栈提示段（长度0）
  • 为什么数据指令分离：
    • 权限：数据可读写，指令可读
    • 缓存命中率：数据缓存，指令缓存
    • 最重要--共享指令：对于多个该程序的副本，指令与只读数据是一样的。数据区域是进程私有的。
      • 如果系统中运行了数百个进程，可以用共享的方法节省大量空间。
  • 全局静态变量：全局未初始化的变量放到目标文件一般放到.bss，但也有值预留一个未定义的全局变量符号。最终链接时才放到.bss段分配空间。
    • 但编译单元内部可见的静态变量确定存放在.bss段的。
• ELF文件结构描述
  • 文件头：
    • 魔数Magic：平台属性（ELF字长（32/64bit），字节序，elf文件版本）
    • 文件类型：.o,可执行，.so
    • 机器类型
  • 段表、段的类型、标志位：前面讲了，记住最重要的的那几个就行。
  • 重定位表：
  • 字符串表：集中放一起，下标-字符串存储（字符串表和段表字符串表）
• 链接的接口--符号：
  • 符号表：符号(粘合剂)--符号值
    • 全局符号：定义在本目标文件的全局符号，可以被其他目标文件引用
    • 外部符号（也是全局符号）：本目标文件引用的全局符号，没有定义在本目标文件。
    • 段名：段的起始地址
    • 局部符号：编译单元内可见（如static）。一般对于链接过程没有作用，会被链接器忽略。
    • 行号信息：
  • 符号表结构：一个段
    • 符号值:函数/变量--地址（段中偏移），未定义(COMMON块)--对齐属性，可执行文件--虚拟地址
    • size符号大小：数据类型大小，0代表大小为0或者未知
    • info：符号类型（未知，数据，函数，段，文件名）和绑定信息--LOCAL、GLOBAL、WEAK。
    • 符号所在段Ndx：
      • 绝对的值ABS
      • COMMON未初始化全局
      • UNDEF本地引用但是定义在其他目标
      • 以及当前确切所在的段
    • 符号名称Name：函数名、变量名、文件名等。

符号修饰与函数签名

• C：_ + name(Windows)
• C++:namesapce + class + name + params
• 名称修饰：函数名称、静态变量冲突
• extern C: C++与C兼容
• 弱符号与强符号：链接错误--符号重复定义问题
  • 多个global：初始化的全局变量为强符号，未初始化的全局变量为弱符号
  • extern：既非强也非弱，外部变量的引用。
  • 可以使用扩展关键字强制声明为弱引用。
  • 强弱规则规则：
    • 不允许强符号多次定义
    • 一个文件强，其他文件弱，选择强符号
    • 都是弱，选择占用空间最大的那个
  • 弱符号容易非法地址访问，可以if来判断是否非法访问。可以用来裁剪组合功能。

调试信息

略，太超过了。

静态链接

1. 空间地址分配
   • 按序叠加：各个目标依次合并，但是这样会有很多零散的段，浪费空间，NOT GOOD
   • 相似段合并：text合一起，data合一起，bss再和一起（文件不占空间，装载时分配虚拟空间）。
   • 两步链接：
     • 空间地址分配: 扫描所有的输入文件，相似段合并，符号表中的所有符号定义和引用统一收集起来，放进全局符号表。链接器在这一步能获得所有输入目标文件的段长度，合并计算出长度与位置建立映射
     • 符号解析与重定位(核心)：根据收集的信息，读取输入文件中段的数据、重定位信息，并进行符号解析与重定位，调整代码地址。
   • 链接前后的程序已经是虚拟内存地址（VMA），链接之前按所有段的VMA都是0，虚拟空间还没有被分配。
   • 符号地址确定：虚拟地址起始（有个固定较大值）+偏移量。
2. 符号重定位
   • 重定位前
     • 编译成目标文件时，不知道变量地址，则先将地址填充为0
     • call调用时，不知道地址，直接填充近址相对位移，是相对于调用指令的下一条指令的偏移量（0xFFFFFFFC，-4）。
       • 紧接着add指令的地址，实际指令为(0x2b-4 )= 0x27, 实际调用的是0x27，是一个临时的假地址。
   • 重定位修正:需要对每个需要重定位的指令进行地位修正
     • 变量好理解，直接替换掉。
     • swap地址记录的是偏移量，那么就由下一条指令偏移量+偏移获得新的swap地址。
   • 重定位表(段)：依依对应数据段，代码段
     • 重定位入口：
       • 偏移：每个要重定位的地方，可重定位文件中：偏移代表重定位段中的位置。可执行文件和共享文件： 要修正的位置的第一个字节的虚拟地址
       • info类型和符号：低8位类型，高24位对应符号表中符号的下标
   • 符号解析：程序员看到的主要内容
     • undefined需要在全局符号表找到定义（段号），否则报符号未定义错误。
   • 指令修正方式：寻址方式太多了！略吧，感觉没啥意义
     • 主要就还是绝对寻址和相对寻址的区别
3. COMMON块（Common Block）
4. C++相关问题
   • 重复代码消除：模板、外部内联函数、虚表
   • 程序都是从main开始到main结束，因此main异常重要。不过有些一些特定的函数必须在mian前后执行。比如全局对象的构造和析构，用.init段和.fini段来做。
   • C++与ABI
     • 跨编译器的二进制库需要做到非常标准，规定一致。不同编译器难以兼容，故只有API的说法
5. 静态库链接：
   • 静态库：一组目标文件的集合（压缩，编号索引）
6. 链接过程控制：

Windows PE/COFF

略

第三部分 装载与动态链接

可执行文件的装载与进程

可执行文件只有装载到内存后才能被CPU执行。随着mmu诞生，装载百年的异常复杂

• 虚拟地址空间:每个程序运行起来后将有自己独立的虚拟地址空间：PAR，AWE，mmap
• 装载方式：静态装入、覆盖装入和页映射
  • 静态装入：所需内存大于物理内存，不实际。
  • 覆盖装入：按模块划分，树状调用
  • 页映射：
• 进程建立：
  • 进程虚拟空间：
    • VMA虚拟内存区域，一个段（虚拟段）：加载文件段的映射，并对齐。
    • 页错误/缺页中断
• 进程虚存空间分布
  • 多个段Section按照权限分配在一起。形成整体的Segament代码段和数据段、只读、映射到VMA1和VMA2。
  • 描述Segament的结构叫做程序头，用来存Segment信息。有两个区域必定是堆和栈。还有一块vdso是分配给内核的，可以用来访问这块进行内核通信。
  • 进程栈初始化：命令行
• 内核装载ELF过程：
  • bash进程会调用用fork()创建新的进程,然后新的进程条用 execve()执行指定的elf文件。原先bash进程继续返回会等待waitpid刚才启动的新进程结束，然后继续等待用户输入命令。
  • exev三个参数：文件名，执行参数，环境变量。
  • load_elf_binary：
    • 检查elf可执行文件有效性（魔数，程序头表中 段Segment数量）
    • 寻找动态链接段.interp
    • elf可执行文件的程序头表描述
    • 根据程序头表，对elf文件进行映射。
    • 初始化elf进程环境，比如进程启动时EDX寄存器的地址应该是DT_FINI的地址。
    • 系统调用的返回地址，应该修改成elf可执行文件的入口点，这个入口点取决于程序的链接方式：静态，文件头中指定的地址。动态，入口点是动态链接器。 PE装载：文件一般没有那么多段了，直接就是代码段、数据段、只读数据段和bss等位数不多的几个段。
• PE文件被设计为可以装载到任何地址。

动态链接

• 为什么要动态链接：静态链接浪费内存、磁盘空间（重复使用）、模块更新困难。
• 动态链接优点：
  • 共享：节省内存，减少物理页面换入换出，增加Cache命中。
  • 插件：可扩展性和兼容性
  • 性能损失只有接近5%
• 问题：
  • 性能损失
  • DLL HELL
• Linux：动态共享对象DSO(.so),Windows动态链接库(.dll)
• 例子

  gcc -fPIC -shared -o Lib.so Lib.c
  gcc -o Program1 Program1.c ./Lib.so
  

• shared： 表示产生共享对象
  • Program1编译成Program1.o，编译器还不知道函数的foobar地址。
  • 链接器将Program1.o链接成可执行文件时，必须确定foobar性质。
    • 静态--重定位
    • 动态--将这个符号的引用标记为一个动态链接的符号，过程留到装载时再进行。
  • 如何知道静态还是动态信息？
    • 需要将Lib.so作为链接的输入文件之一，链接器再解析符号时就知道了。
    • Lib.so是保留了完整的符号信息的
    • 装载属性：Lib.so除了文件类型不同，其他的基本和普通程序一致
    • 装载地址：从0x0000000（无效地址）开始，共享对象的最终装载地址是不确定的。实际上是根据当前地址空间的空闲大小，动态分配一块足够大小的虚拟地址空间给共享对象。
  • 链接过程：
    • Lib.so和Program1用同样的方法映射至进程的虚拟空间，只是地址和长度有区别（只读和读写）
• 地址无关代码：由于共享因素，固定地址是不可行的，但是早期有静态共享库。
  • 静态共享库：跟静态库有区别，将程序的各种模块交给OS，OS在某个特定的地址划分出一些地址块，为那些已知的模块预留空间。
    • 问题：地址冲突、升级难（全局函数和变量地址不变，增加也会受到限制--分配到的虚拟地址空间有限，不能增长太多）

  • 如何在任意地址加载：

    • 可执行文件基本可以确定自己在进程虚拟空间中的起始位置（第一个加载）
    • 装载时重定位（基址重置）：没有-fPIC
      • 问题：没有办法一份指令被多个文件共享

    • 地址无关代码PIC：组合形成四种情况。

      • 分模块：模块内部引用和模块外部引用
      • 分引用：指令引用和数据访问
      • 实际上编译时内外不太好区分，很多时候都当成外部处理了，但MSVC提供__declspec(dllimport)扩展表示以一个符号时内部还是外部模块。
      • 模块内部调用或跳转：不需要重定位，可以相对位置调用，或者基于寄存器的相对调用。（相对位置--地址无关）
        • call的是目的地址相对于当前指令的下一条指令的偏移
        • 全局符号介入问题：后面讲，简单的相对
      • 模块内部数据访问：指令不能包含数据的绝对地址，唯一的办法是相对寻址。
        • 三段寻址（指令+跨页+数据movl）
      • 模块间数据访问：
        • 复杂：装载时才能确定
        • GOT全局偏移表：将GOT表放到可执行文件的数据段，存有指针数组
          • 可以做到装载时修改。
          • 每个进程都可以有独立的副本，互不影响。
          • 数据地址无关：先找到GOT，再找到对应变量目标地址。
          • GOT本身的偏移量是编译时确定了的
          • 动态链接时进行重定位
      • 类型四：模块间相互调用、跳转：
        • GOT：一样，先得到PC，再价一个偏移量拿到GOT，实现间接调用。

    • 地址无关执行文件

    • 共享模块的全局变量问题：模块内部的全局变量如extern int，无法在编译期进行链接，难以判定在共享库或者其他模块的目标文件中。
      • 变量的地址必须在链接过程中确定下来
      • GOT将模块内的全局变量也视作普通访问数据，然后在。bss创建一个副本。然而可执行文件也含有一个副本。所以共享库编译时，默认都把定义在模块内部的全局变量当做类型四，通过GOT实现变量访问。
        • 共享模块装载时，GOT会把地址指向该副本。
        • 如果在共享库初始化，还会将初始化值复制到程序主模块的变量副本。
        • 如果主程序没有，GOT就指向模块内部的变量副本。
    • 注意：多个进程访问共享库的全局变量，本质上已经局部变量和无区别了。进程都是用的自己段的全局变量。
    • 数据段地址无关性：
      • 数据段：每个进程都有一个独立副本。
      • 如果不使用无关地址？不能被多个进程之间共享，没有节省内存的优点，但是快（省去了访问全局数据和函数需要做一次计算当前和间接地址的过程）。
      • 可执行文件：动态链接，GCC会对代码段默认PIC。
      • 延迟绑定：第一次用到再绑定
    • 目的：加快启动速度，避免大量不需要的函数进行绑定。
    • 实现方式：PLT,又一层间接跳转。
    • 具体：GOT跳转表并没有绑定目的地址，而是将push指令的地址填入到对应的GOT条目中， PLT构成三部分：
      • ".dynamic":动态链接信息（依赖，动态链接符号表等、重定位表、）
      • 本模块ID：动态链接器装载时再初始化。
      • dl_runtime_reslove的地址；动态链接器装载时再初始化。
      • 动态符号表:
    • 加快符号查找：符号哈希表
    • 为什么需要重定位：
      • 静态链接和无PIC：装载时重定位跨模块引用和数据
      • PIC：导入符号地址在运行中确定，需要运行时将导入符号修正（虽然代码段不需要了，因为地址无关。）但数据段还包含绝对地址引用，因为代码段绝对地址被分开了变成了GOT，成为数据段的一部分。
    • 动态链接时进程堆栈初始化信息。
      • 动态链接步骤：
    • 自举BootStrap
      1. 找到GOT
      2. 通过GOT找到.dynamic
      3. 通过,dynamic获取重定位表和符号表
      4. 得到链接器的重定位入口，进行全部的重定位
      5. 这时动态链接器代码才能使用全局和静态变量。
    • 装载
      1. 合并可执行文件和链接器符号表到一个符号表中（全局符号表）
      2. 列出可执行文件需要的所有共享对象，放进一个装载集合。
      3. 取一个需要的共享对象的名字，找到相应的文件打开
      4. 读取响应elf文件头和“dynamic段”，将它代码段和数据段映射到进程空间中。
      5. 还依赖其他共享对象，则循环直到所有对象被装载（链接器可以有不同装载顺序）
      6. 一个装载后，符号表会合并，类似与遍历图最终合并。
      7. 全局符号介入：动态链接，相同符号忽略后者（尽量避免重名）
    • 重定位和初始化
      1. 遍历可执行文件和每个共享对象的重定位表
      2. GOT/PLT每个需要重定位的位置都去修正（有全局符号表了）
      3. 显示运行时链接（运行时加载）：
    • 对象名称：动态装载库
    • 有对应的API支持

    DLL--windows下的动态链接

    特点： - 更加强调模块化 - DLL代码并非地址无关。 - 两个数据段：共享数据段和私有数据段 - 需要显示导出、导入（因为没有地址无关代码） - 链接时：需要链接lib，一组目标文件的集合。 - 并不包含真正的数据，而是描述dll的导出符号，也称胶水代码 - 根据函数调用规范的不同（如__ cedel,__stdcall）,会有不同的修饰规则,单独导出。 - 显示运行时链接：有专门的API - 符号导出导入表：

DLL优化：避免大量符号查找。如果dll数量多或者导入导出大，耗时耗性能。 - 重定基地址： - 前提：DLL装载时有一个固定的目标地址 - 目标地址占用，则重新分配新的空间 - 涉及到绝对地址引用的怎么办？全部绝对地址重定位（加上和目标装载地址的差值） - 序号：看不懂 DLL HELL：DLL更新覆盖导致 解决方案： - 静态链接 - 防止DLL覆盖 - 避免DLL冲突（不同程序依赖相同DLL不同版本） - .NET的解决方案：Manifest文件描述（名字、版本号、程序集各种资源）--XML - 问题：C/C++就需要完全按照版本了，否则会出错