链接

学习链接的过程，有助于构造大型程序，有助于理解虚拟内存，分页等概念，有助于理解语言的作用域，本章内容来自深入理解计算机操作系统。（这一章很多内容都需要参考编译原理，因此花了很多时间整理）

链接

链接是将各种代码数据片段合并为一个单一文件的过程；链接存在的意义，就是为了将一个程序分开编译，编写时，只需修改小的模块，再通过连接器链接就行。链接可以在程序编译时，加载时，运行时执行。

编译过程

首先，编辑代码，形成一个代码文件，经过预处理阶段；预处理阶段，主要是对文本进行替换，包括头文件的引入，宏定义的替换；处理完成后，在进行编译，这部分涉及编译原理的相关内容，组要做了下列内容

经过编译后，在有汇编器转成汇编代码，此时代码以指令的形式表示，最后一步链接，链接完成后，就是obj目标文件，此时是机器代码01表示，可以直接运行

最终程序被加载到内存中运行

内存模型

编译器执行过程

例如有两个片段mian.c和sum.c

mian.c

int sum(int x,int y);

int mian()
{
    sum(1,2);
}

sum.c

int sum(int x,int y)
{
	return x+y;
}

首先，编译器会将两个c程序预处理，比如引入头文件等，宏定义等

预处理器（cpp）

1	main.c->mian.i sum.c->sum.i

再将中间.i文件转成ASCII汇编语言文件

编译器（cc1）

1	main.i->mian.s sum.i->sum.s

再将汇编文件转成可重定位目标文件

汇编器（as）

1	main.s->mian.o sum.s->sum.o

最后由连接器（ld），将两个目标文件以及必要系统文件组合起来，生成一个可执行文件

1	mian.o,sum.o->prog

最后，系统执行prog时，由loader函数将程序加载到内存

ELF

这部分参考了深入理解计算机系统0F：链接ELF头部](https://www.bilibili.com/video/BV1MX4y1576E)

以最简单的helloworld为例，在编译后，编译器也不知道printf的具体实现代码的位置，此时的代码是非标准型代码，要转换成标准std代码；printf此时在程序p1.o外部,当程序运行到external printf处时，可以先给真正的printf代码留个空位置，通过ELF的机制，使链接器能找到所定义的代码(Executable可执行Linkable可链接Formate格式)

ELF功能

链接过程

ELF头对应的含义

ELF头	含义
.test	已编译程序的机器代码
.rodata	只读数据
.data	已初始化的全局变量和静态c变量
.bss	未初始化的全局和静态c变量
.symtab	一个符号表，它存放在程序中定义和引用的函数和全局变量信息
.rel.text	一个.text节中的位置的列表
.rel.data	被模块引用或定义的所有变量的重定位信息
.debug	一个调试符号表
.line	原始c源程序中的行号和.text节洪机器指令之间的映射
.strtab	一个字符串表,段的索引

详见64位ELF文件头格式介绍

节头部表section header table（SHT）

SHT的范围[offset,num*size]

有了SHT后，编译器就可以根据SHT的各种信息去索引对应的代码段

符号和符号表（.symtab）

符号解析

详细见龙书

将符号引用和符号定义关联起来，就是将变量（符号定义）与真实的数据地址（符号引用）映射起来，首先给个地址，再加个偏移量，就确定了一个数据

符号表格式

typedef struct{
	int name;		//string table offset
    char type:4,	//func or data
         binding:4; //local or globle
    char reserved;	//unused
    short section;	//section header index
    long value;		//section offset or absolute adress
    long size;		//obj size
}ELF_symble;

bind高四位，type低四位；

binding	备注	type	备注
weak	__attribute__((weak))修饰	notype	未定义的类型
local	static修饰	function	函数
global	extern修饰	object	数据

符号由汇编器构造，编译器会将符号输出到.s文件

在编译期时，编译器会进行符号映射，把符号和地址关联上，并根据类型给出对应偏移；链接器会根据binding维护不同文件之间的变量关系。

在编译期，会有三个伪节，ABS不可重定位的符号，UNDEF未定义的符号，COMMON未初始化的全局变量，是个零时性的（tentative）节。当链接器完成后，符号表中的value就是个绝对的运行地址了，同时也没有这些伪节了，因为此时程序已经确定了。

链接符号解析的三个原则

只允许一符号为define
多个弱符号定义（weak bind，undefine，tentative）和强符号定义选强符号
多个符号undefine<weak bind<define

重定位

有个程序如下

extern void func();
extern int arry[2];

void main()
{
    func();
    arry[1];
    arry[1];
}

当程序到func()时候，会发现是个外部引用，无法处理，这时，在以（I₁,I₂···I_n）的URM程序，会指向I_n+1，此时，就转化成了标准程序，I_n+1可称为占位项或重定位项

实现重定位功能的就是目标文件

每一个目标文件就是个字节序列，目标文件又分为可重定位目标文件 ，可执行目标文件，共享的目标文件

可重定位目标文件：可以和其他目标文件合并，生成一个可执行目标文件

可执行目标文件：可以直接放到内存中执行的文件

共享的目标文件：可以在加载时或者程序运行时，动态的加载到内存中链接

重定位可以分成两步

重定位节和符号定义

通俗来说就是合并表；首先，各个symblol表会定义不同符号，然后编译器根据所有符号表的各个符号定义，按照解析的三个原则，确定一个唯一的符号表map_symbol，然后合并section时，各个节先去符号表中找对应的符号，然后构建对应的节。

重定位节的符号引用

通俗来说就是修改上面生成表的地址，改为正确的运行地址

重定位只有两个段需要引用，.text函数和.data数据，如果在.text节引用就是.rel.text,如果在.data节引用就是.rel.data

重定位条目结构

typedef struct
{
    ELF_Addr offset;//相对于当前section的偏移
    ELF_Xword info;//relocation type or symbol index
    ELF_Sxword addent;//偏移值，与%rip
}Real

info是个64位的值，高32位表示重定位类型，低32位表示引用符号。重定位最主要的连个类型就是相对地址引用和绝对地址引用

深入理解计算机操作系统(P₄₈₀)给了一组重定位算法

foreach section s {
    foreach relocation entry r {
        refptr = s + r.offset;  /* ptr to reference to be relocated */
        /* Relocate a PC-relative reference */
        if (r.type == R_X86_64_PC32){
            refaddr = ADDR(s) + r.offset; /* ref's run-time address */
            *refptr = (unsigned) (ADDR(r.symbol) + r.addend - refaddr);
        }
        /* Relocate an absolute reference */
        if (r.type ==R_X86_64_32)
            *refptr = (unsigned) (ADDR(r.symbol) + r.addend);
    }
}

其中

R_X86_64_PC32:相对地址引用

R_X86_64_32:绝对地址引用

ADDR(s):每个节

ADDR(r.symbol):节运行时地址

相对地址引用

计算引用的运行时地址

1
2
3

refaddr = ADDR(s)  + r.offset
        = 0x4004d0 + 0xf
        = 0x4004df

更新引用

1
2
3

*refptr = (unsigned) (ADDR(r.symbol) + r.addend - refaddr)
        = (unsigned) (0x4004e8       + (-4)     - 0x4004df)
        = (unsigned) (0x5)

绝对地址引用

链接器从偏移量 0xa 开始绝对引用

1	ADDR(r.symbol) = ADDR(array) = 0xFFFFFF

更新引用

1
2
3

*refptr = (unsigned) (ADDR(r.symbol) + r.addend)
        = (unsigned) (0xFFFFFF       + 0)
        = (unsigned) (0xFFFFFF)

可执行目标文件

PHT维护了表实现了片的内存关系，使可执行文件连续的片可以很容易的被映射到内存上

off	目标文件偏移
vaddr/paddr	内存地址
align	对齐要求
filesz	目标文件中段大小
memsz	内存中段大小
flags	运行的访问权限

动态链接

来源

对于静态链接，如果有n个EOF程序文件，它们的源码中都引用了malloc 的定义，那么malloc的.text 与.data就会被复制n次。这对于磁盘上的程序文件而言还算可以接受，因为我们总是假设磁盘有足够大的储存空间。但是内存是更加稀缺的资源，如果这n个程序都在内存上运行，采用静态链接的话，那么内存上就有存在 malloc的n份拷贝，这无疑是对资源的浪费。

那么如果一个程序块如果被多次引用，那么就可以只在内存中存储一份，然后以共享的方式给各个块去使用，这就是共享库的意义。共享库以动态链接的方式被程序引用。

Global Offset Table

为实现动态链接，使用了位置无关代码（Position-Independent Code,PIC）的技术。PIC的实现依赖于一个简单的事实:EOF文件的Segment是按照它们在磁盘文件中的结构，被复制到运行时内存中的。因此，在.text，.rodata，.data构成的连续虚拟内存中，对任意两个符号(函数或变量）S1与S2，它们在磁盘上的地址相差是个定值；GOT本身就是对.text的一个偏移，这样只要在运行时确定动态库Mmap的地址就完成了动态链接过程

Procedure Linkage Table

程序的动态链接1 - plt 和 got

GOT解决了对共享库中全局变量的引用，对函数动态链接就是用了函数连接表(Procedure Linkage Table, PLT)，GOT和PLT共同配合实现

指令跳转到 plt 表

plt 表判断其对应的 got 表项是否已经被重定位

如果重定位完成，plt 代码跳转到目标地址执行

如果未重定位，调用动态链接器为当前的引用进行重定位，重定位完成之后再跳转。

{{moment(1648736890964).fromNow()}} {{moment(1648736890964).format('YYYY-MM-DD HH:MM:SS')}}

链接

链接