《程序员的自我修养—链接、装载与库》
——读书笔记（本文为记录笔记，大部分内容为书中的摘抄）
作者微博：@MTK_蛙蛙鱼
写作时间：2013年11月18日
更新时间：2014年02月18日
编译和链接
2.1 被隐藏了的过程
预编译（cpp or gcc -E）-> 编译（cc1包含了预编译 or gcc -S）-> 汇编（as or gcc -c）-> 链接（ld）
2.2 编译器做了什么
扫描（词法分析）-> 语法分析-> 语义分析-> 源代码优化-> 代码生成-> 目标代码优化
2013年11月18日
lex 词法扫描程序，它会按照用户之前描述好的词法规则将输入的字符串分割成一个个记号
yacc 语法分析程序，它会根据用户给定的语法规则对输入的记号序列进行解析，从而构建出一颗语法树，以表达式为节点的树，符号和数字就是树的叶子
静态语义，声明和类型的匹配，类型的转换，为语法树节点添加类型
源代码优化，比如2+6可以优化掉变成8，属于编译器前端，产生机器无关的中间代码
代码生成器，将中间代码转换成目标机器代码
目标代码优化器，对目标代码进行优化，比如选择合适的寻址方式、使用位移来替代乘法、删除多余的指令等
2.4 模块拼装——静态链接
地址和空间分配-> 符号决议-> 重定位
对于模块A引用到模块B的变量或函数地址时，编译器默认将其地址置为0，等待连接器在将目标文件A和B链接起来的时候再将其修正，这个地址修正的过程被叫做重定位
目标文件里有什么
3.1 目标文件格式
目标文件就是源代码编译后但未进行链接的那些中间文件，它跟可执行文件的内容与结构很相似，从广义上看，目标文件与可执行文件的格式其实几乎是一样的
PE格式（Windows Portable Executable）
ELF格式（Linux Executable Linkable Format），可重定位文件（.o）、可执行文件、共享目标文件（.so）、核心转储文件（Core Dump File）。file命令可查看文件类型
COFF格式（Common file format），从a.out格式发展而来，为了解决共享库问题，起源于Unix System V Release 3
3.2 目标文件是什么样的
.bss段只是为未初始化的全局变量和局部静态变量预留位置而已，它并没有内容，所以它在文件中也不占据空间
为什么把程序的指令和数据的存放分开？
- 指令只读，数据可读写，对指令起到保护作用
- CPU的缓存命中率，现代CPU的缓存一般都被设计成数据缓存和指令缓存分离
- 指令部分可以共享内存
2013年11月19日
3.3 挖掘SimpleSection.o
binutils工具：objdump、size、objcopy、nm、strip
readelf
CPU的字节序，就是所谓的大端和小端
__attribute__((section("FOO"))) int var = 32;，可以将变量var放入自定义的‘FOO’段中，而不会放到.data段里
3.4 ELF文件结构描述
ELF格式的魔数：0x7F 0x45 0x4c 0x46，分别代表DEL控制字符和'ELF'字符的ACSII码
a.out格式的魔数：0x01 0x07，有一段小历史
e_type文件类型：ET_REL（可重定位文件.o）、ET_EXEC（可执行文件）、ET_DYN（共享目标文件.so）
ELF Header -> Section Table ->
- sh_type段的类型：SHT_NULL（无效段）、SHT_PROGBITS（代码段和数据段类型）、SHT_SYMTAB（符号表）、SHT_STRTAB（字符串表）、SHT_RELA（重定位表）、SHT_HASH（符号表的哈希表）、SHT_DYNAMIC（动态链接信息）、SHT_NOTE（提示信息）、SHT_NOBITS（该段在文件中没有内容，如.bss段）、SHT_REL（重定位信息）、SHT_SHLIB（保留）和SHT_DYNSYM（动态链接的符号表）
- sh_flag段的标志：SHF_WRITE（该段在进程空间中可写）、SHF_ALLOC（该段在进程空间需要分配空间，如代码段、数据段和.bss段）和SHF_EXECINSTR（该段在进程空间中可以被执行，一般指代码段）
ELF Header ->
.shstrtab（段表的字符串表在段表中的下标）
3.5 链接的接口——符号
st_value符号的值：
- 如果在目标文件中定义的符号不是COMMON块，则它的值表示该符号在段中的偏移
- 如果在目标文件中定义的符号是COMMON块，则它的值表示该符号的对齐属性
- 如果在可执行文件中定义了符号，则它的值表示该符号的虚拟地址
特殊符号，被定义在ld连接器的链接脚本中，最终生成可执行文件的时候这些符号才会存在，比如__executable_start（程序起始地址）、_etext（代码段结束地址）、_edata（数据段结束地址）、_end（程序结束地址）
早期，C语言源代码文件中的所有全局变量和函数经过编译（.s）后，相应符号名前加上下划线“_”来避免与其他的语言（如Fortran编译后的符号名前后都会加上“_”）的符号冲突，但是无法避免同一种语言产生的符号冲突，-fleading-underscore/-fno-leading-underscore来打开或关闭在C语言符号前加上下划线
C++，命令空间（namespace）
C++符号修饰，c++filt工具可以解析修饰过的名称（c++filt _ZN1N1C4funcEi => N::C::func(int)），不同编译器厂商的名称修饰方法可能不同
extern "C"，这是C++编译器支持C语言（符号修饰）的编译处理手段，C++宏__cplusplus支持
强符号与弱符号（针对的是符号的定义而不是引用），编译器默认函数和初始化了的全局变量为强符号，为初始化的全局变量为弱符号。通过“__attribute__ ((weak))”可以定义任何一个强符号为弱符号
- 不允许强符号多次定义，否则报错
- 有强符号和弱符号，有限选择强符号
- 都是弱符号，选择占用空间最大的一个
强引用和弱引用（针对的是符号的引用而不是定义），对于一个外部引用没有定义，链接器会报符号未定义错误，这种被称为强引用，与之相对应的叫弱引用。一般对于未定义的弱引用，链接器默认其为0或一个特殊值。通过“__attribute__ ((weakref))”可以声明对一个外部函数的引用为弱引用（测试失败，还是报错了@||，另：那个“一个程序被设计可以支持单线程或多线程的模式”代码有误@||）
2013年11月20日
3.6 调试信息
ELF格式：DWARF（Debug With Arbitrary Record Format）
Microsoft：CodeView
strip
静态链接
4.1 空间与地址分配
两步链接：
- 空间与地址分配：扫描所有输入目标文件-> 获取各个段的长度、属性和位置信息（空间分配）-> 计算出各个段的虚拟地址->计算出目标文件中符号表中所有符号的地址（地址分配）-> 收集目标文件的符号表中的所有全局符号建立全局符号表
- 符号解析与重定位：通过目标文件中的符号表、重定位表和全局符号表来调整代码中的地址
VMA，Virtual Memory Address，即虚拟地址。
LMA，Load Memory Address，即加载地址。我们只需关注VMA
在Linux下，ELF可执行文件默认从地址0x08048000开始分配
4.2 符号解析与重定位
重定位表，如.rel.text（保存了代码段的重定位表）、.rel.data（保存了数据段的重定位表）
r_offset：重定位入口的偏移，对于可重定位文件来说，这个值是该重定位入口所要修正的位置的第一个字节相对于段起始的偏移；对于可执行文件或共享对象文件来说，这个值是...的第一个字节的虚拟地址
r_info：重定位入口的类型和符号，低8位表示重定位入口的类型，高24位表示重定位入口的符号在符号表中的下标
x86基本重定位类型：
- R_386_32：绝对寻址修正 S + A，A=保存在修正位置的值，S=符号的实际地址（这里其实就是虚拟地址）
- R_386_PC32：相对寻址修正 S + A - P，P=被修正的位置（这里其实就是该位置的虚拟地址，可通过r_offset加上段虚拟地址计算得到）
4.3 COMMON块
弱符号，编译器将未初始化的全局变量定义作为弱符号
编译选项加入“-fno-common”或者代码中使用“__attribute__((nocommon))”来取消COMMON块
4.4 C++的相关问题
模板重复代码消除，编译选项“-ffunction-sections”和"-fdata-sections"可以将每个函数或变量保持到独立的段中
ELF文件格式定义了两种特殊的段：
- .init：该段里面保存的是可执行指令，它构成了进程的初始化代码
- .fini：该段保存进程终止代码
ABI，Application Binary Interface，可执行代码的二进制兼容，两个编译器编译出来的目标文件能够互相链接
4.5 静态库连接
ar，打包工具（ar rcs libx.a a.o b.o c.o...），其实最终libx.a安排形式为：一个头 + a.o （一个头大小为0x3c +.o 整体）+ b.o + c.o +
链接器最终需要去寻找到 crt1.o、crti.o、crtbeginT.o、libgcc.a、libgcc_eh.a、libc.a、crtend.o和crtn.o这些文件来做静态链接
4.6 链接过程控制
ld -verbose，打印了连接器默认的控制脚本，已经放在了ld程序的.rodata段中
ld链接脚本，如果把整个链接过程比作一台计算机，那么ld连接器就是CPU，所以目标文件、库文件就是输入，链接输出的可执行文件就是输出，而链接控制脚本正是这台计算机的“程序”，它控制CPU的运行，以“程序”要求的方式将输入加工成所需要的输出结果
链接脚本语句分两种，一种是命令语句，另外一种是赋值语句
可以进入《ld参考手册》进行学习
2013年11月22日
Windows PE/COFF
5.1 Windows的二进制文件格式PE/COFF
PE（Protable Executable），与ELF同根同源，都是由COFF（Common Equipment File Format）格式发展而来
目标文件默认为COFF格式，可执行文件为PE格式
#pragma与“__attribute__((section("name")))”用法一致，将函数或变量放到自定义段中
5.2 PE的前身——COFF
Microsoft Visual C++ 的编译器为cl，链接器为link，类似objdump的工具dumpbin
__STDC__这个宏的定义表示了编译器禁用了Microsoft C/C++的语法扩展（它们不符合ANSI C/C++标准）
COFF文件由文件头和若干段组成，文件头包括两部分，一个是描述文件总体结构和属性的映像头，另一个是描述该文件包含段属性的段表
5.3 Windos 下的ELF——PE
PE文件是基于COFF的扩展
PE文件头包含了：DOS MZ可执行文件格式的文件头和桩代码（DOS MZ File Header and Stub）、IMAGE_NT_HEADERS（包括了原来的“Image Header”和新增的PE扩展头部结构“PE Optional Header”）、描述该文件包含段属性的段表（Section Table）
2013年12月16日
可执行文件的装载与进程
6.1 进程的虚拟地址空间
4GB的Linux虚拟地址空间安排：（0x00000000~ 0xBFFFFFFF）3G为用户进程地址空间、（0xC0000000 ~0xFFFFFFFF）1G为操作系统的地址空间
PAE（Physical Address Extension），32位地址扩展到36位
6.2 装载的方式
覆盖载入，页映射
覆盖载入，覆盖管理器（Overlay Manager），程序员需要手工将模块按照它们的之间的调用依赖关系组织成树状结构
- 这个树状结构中从任何一个模块到树的根（也就是main）模块都叫调用路径，当模块被调用时，整个调用路径上的模块必须都在内存中
- 禁止跨树间调用，任何一个模块不允许跨过树状结构进行调用
页映射，装载管理器（操作系统），至于选择放弃哪个页
6.3 从操作系统角度看可执行文件的装载
装载一个可执行文件：
- 创建一个独立的虚拟地址空间
- 读取可执行文件头，并且建立虚拟空间与可执行文件的映射关系
- 将CPU的指令寄存器设置成可执行文件的入口地址，启动运行
创建虚拟地址空间：
分配一个页目录（Page Directory）且并不设置页映射关系，等到程序发生页错误的时候在进行设置
- 可执行文件的真正指令和数据并没有装入到内存中
- 页错误产生
- 从进程的数据结构中找到空页所在的VMA，计算出相应的页面在可执行文件中的偏移
- 在物理内存中分配一个物理页面，将进程中该虚拟页与分配的物理页之间建立映射关系
- 将控制器再还回给进程，进程从刚才页错误的位置重新开始执行
读取可执行文件头，建立虚拟空间与可执行文件的映射关系：（进程中相应的数据结构中设置有一个.text段的VMA，它在虚拟空间中的地址为0x08048000~ 0x08049000，对应ELF文件中偏移为0，它的属性为只读）
CPU指令寄存器设置成可执行文件，启动运行：操作系统将控制器转交给进程
6.4 进程虚拟空间分布
空间浪费问题解决（对于相同权限的段，把他们合并到一起）：
- 以代码段为代表的权限为可读可执行的段
- 以数据段和BSS段为代表的权限为可读可写的段
- 以只读数据段为代表的权限为只读的段
readelf -l获取段（Segment）信息，这里的段其实就是程序头（
Program Header）
一个进程基本上可以分为如下几种VMA区域：
- 代码VMA，权限只读、可执行，有映像文件
- 数据VMA，权限可读写、可执行，有映像文件
- 堆VMA，权限可读写、可执行，无映像文件，匿名，可向上扩展
- 栈VMA，权限可读写、不可执行，无映像文件，匿名，可向下扩展
段地址对齐：
在保证页面属性相同的情况下又节约了物理内存的好方法，一个物理页面被多次映射到虚拟空间中
6.5 Linux内核装载ELF过程简介
bash进程-> fork()创建新进程 -> 调用execve()系统调用执行指定的ELF文件 => sys_execve()进行一些参数的检查复制 =>do_execve()解析文件的前128字节=> search_binary_handle()搜索和匹配合适的可执行文件装载处理过程（ELF文件用load_elf_binary()、a.out文件用load_aout_binary()、脚本文件用load_script()）=> 返回do_execve() => 返回sys_execve()=> 跳转到EIP寄存器指定的程序入口
load_elf_binary()：
- 检查ELF可执行文件格式的有效性，比如魔数、程序头表中段数量
- 寻找动态链接的“.interp”段，设置动态链接器路径
- 根据ELF可执行文件的程序头表的描述，对ELF文件进行映射，比如代码、数据、只读数据
- 初始化ELF进程环境，比如进程启动时EDX寄存器的地址应该是DT_FINI的地址
- 将系统调用的返回地址修改成ELF可执行文件的入口点
6.6 Windows PE的装载
可执行文件比较简单，一般仅有代码段、数据段、只读数据段和BSS段
RVA（Relative Virtual Address）,相对虚拟地址。目标地址（就是所谓的基地址 Base Address）
装载一个PE可执行文件：
- 先读取文件的第一个页，这个页包含了DOS头、PE文件头和段表
- 检查进程地址空间中目标地址是否可用，如果不可用，则另外选一个装载地址（Rebasing）
- 使用段表中提供的信息，将PE文件中所有的段一一映射到地址空间中相应的位置
- 如果装载地址不是目标地址，则进行Rebasing
- 装载所有PE文件所需要的DLL文件
- 对PE文件中的所有导入符号进行解析
- 根据PE头中指定的参数建立初始化栈和堆
- 建立主线程并且启动进程
2013年12月19日
动态链接
7.1 为什么要动态链接
内存和磁盘空间，Program1和Program2依赖的Lib.o库只需提供一份副本，不管在内存和磁盘中
程序开发和发布，只需将新开发的模块覆盖掉旧的即可
程序的可扩展性，被人们用来制作程序的插件（运行时可以动态地选择加载各种程序模块）
程序的兼容性，不同操作系统只需提供对应版本的库接口，而程序本身不用改变
动态链接器，延迟绑定
7.2 简单的动态链接例子
gcc -fPIC -shared -o Lib.so Lib.c
gcc -o Program1 Program1.c ./Lib.so
gcc -o Program2 Program2.c ./Lib.so
Program1除了使用Lib.so以外，还用到了动态链接形式的C语言运行库libc-2.6.1.so，另外还有一个共享对象是ld-2.6.so（动态链接器）
共享对象的最终装载地址在编译时是无法确定的
7.3 地址无关代码
共享对象在被装载时，如何确定它在进程虚拟地址空间中的位置？
-
手工指定各个模块的地址，比如把0x1000~0x2000分配给A模块，0x2000~0x3000分配给B模块。早期系统采用了这样的做法，叫做静态共享库。缺点：1）共享库中的全局函数和变量的地址不能改变，2）空间受到限制，无法增加太多的全局函数和变量
- 共享对象在编译时不能假设自己在进程虚拟地址空间中的位置
装载时重定位：在链接时，对所有绝对地址的引用不做重定位，而把这一步推迟到装载时在完成，-shared：
- 链接时重定位（Link Time Relocation）
- 装载时重定位（Load Time Relocation）
- 在Windows中，基址重置（Rebasing）
指令部分在多个进程中共享，目的很简单，希望程序模块中共享的指令部分在装载时不需要因为装载地址的改变而改变，基本思想是把指令中那些需要被修改的部分分离出来，跟数据部分放在一起。
地址无关代码（PIC，Position-independent Code）技术：
- 类型一、模块内部调用和跳转。相对地址调用指令
- 类型二、模块内部数据访问。利用<__i686.get_pc_thunk.cx>来获取当前PC地址指针
- 类型三、模块间数据访问。全局偏移表（GOT，Global Offset Table）
- 类型四、模块间调用、跳转。同类型三
-
类型五、模块内部全局调用或跳转。（自己添加的）
-
类型六、模块内部全局数据访问。（自己添加的）
pic，PIC，地址无关可执行文件（PIE，Position-independent Executable）
类型五、模块内部全局数据访问。当一个模块（module.c）引用了一个共享对象的全局变量的时候：
extern int global;
int foo()
{
global =1;
}
“当编译器编译module.c时，它无法根据这个上下文判断global是定义在同一个模块的其他目标文件还是定义在另一个共享对象之中”，这句话有问题。我的理解：首先，如果仅仅编译而不链接module.c，那么它会被编译成目标文件，而其中引用的global在符号表中仅是UND符号未定义类型，其次，在链接的时候，引用global的定义无非是在某个目标文件中或在某个共享对象中，这是可以判断的。因此作者的文笔是有误的。
- 假设module.c是可执行程序的一部分，链接器会在创建可执行文件时，在它的“.bss”段创建一个global变量的副本，模块内部的global全局变量访问引用可执行文件中global变量的副本的地址，存储在GOT全局偏移表中，也即模块内部全局数据访问采用模块间数据访问方式
- 假设module.c是共享对象的一部分，编译器在PIC情况下，按照模块间数据访问方式
数据段地址无关性：
static int a;
static int *p = &a;
R_386_RELATIVE，链接时重定位即装载时重定位
7.4 延迟绑定（PLT）
动态链接比静态链接慢大约1%~5%：
- 对于全局或模块间的函数调用和数据访问需要进行复杂的GOT定位
- 程序开始执行时，动态链接器需要进行一次链接工作
延迟绑定的实现，（Lazy Binding），基本的思想就是当函数第一次被用到时才进行绑定，如果没有用到则不进行绑定。实现方法PLT（Procedure Linkage Table）
00000340 <bar@plt-0x10>:
340: ff b3 04 00 00 00 pushl 0x4(%ebx)
346: ff a3 08 00 00 00 jmp *0x8(%ebx)
34c: 00 00 add %al,(%eax)
...
00000350 <bar@plt>:
350: ff a3 0c 00 00 00 jmp *0xc(%ebx)
356: 68 00 00 00 00 push $0x0
35b: e9 e0 ff ff ff jmp 340 <_init+0x30>
PC 0x00000350处，跳转到bar函数，初始时跳转到下一条指令
PC 0x00000356处，压入的值是bar函数在.rel.plt重定位表中的下标
PC 0x0000036b处，相对地址跳转
PC 0x00000340处，压入该模块的ID，存储在.got.plt段的第二项中
PC 0x00000346处，跳转到_dl_runtime_resolve函数来完成符号解析和重定位工作
.got段用来保存全局变量引用的地址，.got.plt段用来保存函数引用的地址
.got.plt段的前三项是有特殊意义的：
- 第一项是“.dynamic”段的地址
- 第二项是本模块的ID
- 第三项是_dl_runtime_resolve()的地址
7.5 动态链接相关结构
映射可执行文件——>加载动态链接器——>动态链接器入口地址——>执行自身的初始化操作——>对可执行文件进行动态链接——>可执行文件入口地址——>程序开始执行
“.interp”段，保存动态链接器路径“/lib/ld-linux.so.2”，readelf -l
“.dynamic”段，保存动态链接器所需要的基本信息，动态链接下ELF文件的”文件头“，readelf -d
”.dynsym“段，保存动态符号
”.dynstr“段，保存动态符号的字符串
”.rel.dyn“段，保存数据段”.got“的重定位信息，readelf -r
”.rel.plt“段，保存函数引用段”.got.plt“的重定位信息，readelf -r
- R_386_32，符号的实际地址 + 保存在被修正位置的值
- R_386_PC32，符号的实际地址 + 保存在被修正位置的值 - 被修正的位置
- R_386_GLOB_DAT、R_386_JUMP_SLOT，符号的实际地址
- R_386_RELATIVE，装载地址 + 保存在被修正位置的值
动态链接时进程堆栈初始化信息（当操作系统把控制器交给动态链接器的时候，它需要知道关于可执行文件和本进程的一些信息），它位于进程空间的环境变量指针后面：
- AT_NULL，辅助信息数组结束标志
- AT_EXEFD，可执行文件句柄
- AT_PHDR，可执行文件中的程序头地址
- AT_PHENT，可执行文件中每个程序头的大小
- AT_PHNUM，可执行文件中程序头的个数
- AT_BASE，动态链接器本身的装载地址
- AT_ENTRY，可执行文件入口地址
7.6 动态链接器的步骤和实现
启动动态链接器本身——>装载所有需要的共享对象——>重定位和初始化
首先：动态链接器本身不可以依赖其他任何共享对象，其次：动态链接器本身所需要的全局和静态变量的重定位工作由它本身完成（这里有个笔误，对于静态变量而言，是不需要重定位的）
自举代码——>找到”.dynamic“段地址——>获取动态链接器本身的重定位表和符号表——>重定位——>开始可以使用变量和调用函数
装载共享对象，通过读取”.dynamic“段中的DT_NEEDED字段。广度优先或深入优先
当一个新的共享对象被装载进来时，它的符号表会被合并到全局符号表中
符号的优先级，它定义了一个规则：当一个符号需要被加入全局符号表时，如果相同的符号名已经存在，则后加入的符号被忽略。全局符号介入（类型六、模块内部全局调用或跳转）
重定位（其实是被延迟绑定）——>初始化共享对象”.init“段（比如C++全局/静态对象的构造）——>将控制器转交给可执行程序入口——>程序开始执行
Linux的ELF动态链接器是Glibc的一部分，源代码位于elf目录下面
7.7 显示运行时链接
动态装载库（/lib/libdl.so.2）（dlopen、dlsym、dlerror、dlclose）
void * dlopen(const char *filename, int flag);
打开一个动态库，将其加载到进程的虚拟地址空间，完成初始化
filename为0，将返回全局符号表的句柄
flag，RTLD_LAZY表示使用延迟绑定，RTLD_NOW表示立即绑定，RTLD_GLOBAL表示将模块的符号表合并到进程的全局符号表中
void * dlsym(void *handle, char *symbol);
查找符号的值
void * dlerror();
返回上一次调用是否成功，NULL表示成功，否则是错误消息
void dlclose(void *handle);
卸载模块，相应的引用计数减一，当引用计数为0时，才被真正地卸载掉。先执行”.fini“段的代码，然后将相应的符号从符号表中去除，取消进程空间跟模块的映射关系，然后关闭模块文件
演示程序（
书上的程序是有问题的，可以用下面的代码替换尝试）
#define SETUP_STACK \
i=2; \
while (++i < argc-1) { \
switch (argv[i][0]) { \
case 'i': \
asm volatile ("push %%edx\n\t" \
"sub $4,%%esp\n\t" \
"mov %%ebx,(%%esp)\n\t" \
"call atoi\n\t" \
"add $4,%%esp\n\t" \
"pop %%edx\n\t" \
"mov %%eax,(%%esp,%%edx)":: \
"b"(&argv[i][1]),"d"(esp)); \
esp +=4; break;\
case 'd': \
asm volatile ("push %%edx\n\t" \
"sub $4,%%esp\n\t" \
"mov %%ebx,(%%esp)\n\t" \
"call atof\n\t" \
"add $4,%%esp\n\t" \
"pop %%edx\n\t" \
"fstpl (%%esp,%%edx)":: \
"b"(&argv[i][1]),"d"(esp)); \
esp +=8; break; \
case 's': \
asm volatile ("mov %%ebx,(%%esp,%%edx)":: \
"b"(&argv[i][1]),"d"(esp)); \
esp +=4; break; \
default: \
printf("Error argument type\n"); \
goto exit_runso; \
} \
}
#define RESTORE_STACK
2014年02月18日
Linux共享库的组织
