4.4 链接器

4.4.1 链接器原理详解

链接器读取我们汇编器输出的数个.o文件，利用目标文件中的信息，进行符号解析，最终输出可执行的机器代码，例如（a.out）。

链接器能够得到每个文件的text和data段的大小以及它们的顺序。利用这些，链接器便可以计算每个符号的绝对地址。

为了解析符号，链接器首先搜索每个文件的符号表（即每个文件定义的符号），如果没有找到，将继续在库文件中搜索(例如printf)。一旦获取到符号的定义位置，链接器就会填入实际的地址，完善机器代码。最终链接器输出的可执行文件包括.text和.data段（加上ELF文件头）。

对于我们的链接器而言，有四类地址：

  1. PC相对地址(beq, bne)：不需要重定位，在汇编器汇编阶段已经确定了地址；
  2. 绝对地址(j, jal)：需要重定位，对应文本段中的跳转标签；
  3. 外部引用(jal)：需要重定位，对应文本段中的函数标签；
  4. 数据引用(la)：在汇编器中我们将其拆分为lui-ori指令对，需要重定位，对应数据段标签。

4.4.2 链接器具体实现

链接器实现概述

我们在汇编器中，解析了.data和.text段，因此我们在这里也将实现一个简化过的链接器，它将把一个或多个.o文件的.data和.text合并在一起来创建可执行的机器代码，但是我们不会为其添加ELF文件头，因此你可以认为我们的输出是可执行文件去掉ELF文件头以后的二进制bin文件。 具体的链接步骤如下：

  1. 创建一个空的全局符号定义表，这里将存储所有文件中符号（定义位置）的绝对地址，因此每个符号至多出现一次；
  2. 对于每个目标文件都创建一个独立的重定位表，将包含每个需要重定位符号的相对地址；
  3. 打开每个目标文件，分别读取它的.data, .text, .symbol, .relocation段：
    • 如果是.data段，读取该文件.data段的大小，用于计算上述提到的绝对地址；
    • 如果是.text段，计算指令数目，得到该文件的指令将会占用多少字节（MIPS 的每条指令固定为 4 字节）；
    • 如果是.symbol段，将其读入，将相对地址转换为绝对地址（怎么做？），并合并进第 1 步创建的全局符号表；
    • 如果是.relocation段，将其读入进该文件的重定位表，保留其相对地址。
  4. 打开输出文件；
  5. 再次打开每个目标文件，读取.text段，通过查找重定位表判断每条指令是否需要重定位，如果需要，使用符号表查找符号的绝对地址，并填入指令的相应字段，最终输出重定向后的指令即可。

链接器实现

链接器整体调用关系如下：

linker

我们在汇编器的重定位表中引入新的结构体RelocData(定义在linker_utils.h)，主要是在重定位表中加入：

  • 字段text_size用于记录该文件的.text段需要占据的字节数；
  • 字段data_size用于记录该文件的.data段需要占据的字节数；
typedef struct {
    SymbolTable *table;  //重定位表
    int text_size;       //相应文件.text段大小
    int data_size;      //相应文件.data段大小
} RelocData;

测试样例

为了便于理解，提供以下样例以供参考：

有以下两个.s文件需要进行处理：

main.s:

.data
num: .space 8

.text
main:
    la $v1, num
    li $s1, 10
    li $s2, 20
    sw $ra, 0($a3)
    sw $s1, -4($a3)
    sw $s2, -8($a3)
    move $sp, $a3
    jal add
    lw $ra, 0($sp)
    move $t0, $v0
    beq $t0, $0, end
    j end
end:

add.s:

.data

.text
add:
    lw $s5, -4($sp)
    lw $s6, -8($sp)
    addu $t0, $s5, $s6
    move $v0, $t0
    jr $ra

则在汇编结束后分别得到：

main.out:

.data
8

.text
3c010000
34230000
2411000a
24120014
acff0000
acf1fffc
acf2fff8
0007e821
0c000000
8fbf0000
00024021
11000001
08000000

.symbol
0   %num
0   main
52  end

.relocation
0   num@Hi
4   num@Lo
32  add
48  end

add.out:

.data
0

.text
8fb5fffc
8fb6fff8
02b64021
00081021
03e00008

.symbol
0   add

.relocation

最终链接以后的文件为main.o，内容如下：

3c010000
34230000
2411000a
24120014
acff0000
acf1fffc
acf2fff8
0007e821
0c000c0d
8fbf0000
00024021
11000001
08000c0d
8fb5fffc
8fb6fff8
02b64021
00081021
03e00008

代码提交

在完成my_linker_utils.h文件中声明的所有函数以后，即可提交my_linker_utils.c文件进行评测。