Extra Cookie

Yet Another Programmer's Blog

单元测试与程序的重定向和链接

在做单元测试过程中,经常需要对被测程序的一些函数实现 stub,下面三个文件

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// product.c
#include <stdio.h>
void lib_pro()
{
    printf("I'm in lib\n");
}
// user.c
int main(int argc, char *argv[])
{
    lib_pro();
    return 0;
}
// stub.c
#include <stdio.h>
void lib_pro()
{
    printf("I am in fake lib\n");
}

product.c 为产品代码提供 lib_pro 函数,user.c 为使用者,可以当作 UT 测试函数,stub.c 提供 lib_pro 函数的另一个定义。

通常,为了使用 stub,需要在测试时将 user.c 产生的 user.o 和 stub.c 产生的 stub.o 链接在一起,这样,每当要给某一个文件加 stub 时,都需要替换链接,有没有什么办法可以自动进行这一工作,如果有 stub,就链接 stub,如果没有,就链接产品代码。

当然有,

  1. gcc –c product.c 生成 product.o
  2. ar rsv product.a product.o 生成 product.a
  3. gcc user.c product.a 生成可执行文件 a.out, 执行输出 I’m in lib

不对,没有 stub 掉呀?别急,

gcc user.c stub.c product.a 同 3,生成 a.out, 执行输出 I am in fake lib

也就是说只要将产品代码编成静态库,在链接时,将 stub.c 生成的目标 (object) 文件放在产品静态链接库前面,就可以将 stub.c 包含的所有和产品中相同函数全部 stub 掉。

—————————————————————————————————

一个程序要在内存中运行,除了编译之外,还需要经过链接 (link) 和装入 (load) 两个步骤,链接主要有两个工作要做:符号解析 (symbol resolution) 和 重定向 (relocation)。

符号解析就是将符号引用和目标文件符号表中的符号定义对应起来。当一个模块使用了该模块没有定义过的函数和全局变量时,链接器 (linker) 就有责任到别的模块去找它们的定义,如果没有找到合适的定义或者合适的定义不唯一,则符号解析失败。

如何解决符号重复定义?编译时,符号被定义成 strong 或 weak 类型,然后通过汇编写入重定向目标文件的符号表中。通常函数和已初始化全局变量为强符号 (strong symbols),未初始化全局变量为弱符号 (weak symbol),Unix 链接器使用如下规则 (rule) 来解决符号重复定义:

  1. 不允许重复 strong 符号定义
  2. 如果同时有 strong 符号和多个 weak 符号,选择 strong 符号
  3. 如果有多个 weak 符号,选择任意一个
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// foo1.c
int main(int argc, char *argv[])
{
    return 0;
}
// bar.c
int main(int argc, char *argv[])
{
    return 0;
}
// foo2.c
int x = 15213;
void f()
{
}
// bar2.c
int x = 15213;
int main(int argc, char *argv[])
{
    return 0;
}

上述两份代码都违背了 rule 1,因而链接器会直接报错。

1
2
3
4
5
6
7
8
9
10
11
12
// foo3.c
int x = 15213;
int main(int argc, char *argv[])
{
    return 0;
}
// bar3.c
int x;
void f()
{
    x = 888;
}

而这样的代码却可以通过链接,因为满足了 rule 2.

在符号解析完成之后,链接器知道了代码段 (code segment) 和数据段 (data segment) 的大小,于是开始进行重定向,即将目标文件合并并分配运行时地址给每一个符号。

包括如下两个步骤:

  1. 重定向段和符号定义。在这一过程,链接器将目标文件各同类型段内容合并,例如所有 .data 段合并在一起。接着对新组合成的段分配运行时地址,在这一过程完成时,所有的指令和全局变量都会有独一的运行时地址。
  2. 符号引用重定向。这一过程,链接器修改之前每一个目标文件中的符号引用,使得其指向正确的运行时地址。

下面是文章前面的 user.c 的目标文件内容(有删减)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#objdump -dx user.o
...
...
SYMBOL TABLE:
00000000 l    df *ABS*    00000000 user.c
00000000 l    d  .text    00000000 .text
00000000 l    d  .data    00000000 .data
00000000 l    d  .bss    00000000 .bss
00000000 l    d  .note.GNU-stack    00000000 .note.GNU-stack
00000000 l    d  .comment    00000000 .comment
00000000 g     F .text    00000014 main
00000000         *UND*    00000000 lib_pro
Disassembly of section .text:

00000000 <main>:
   0:    55                       push   %ebp
   1:    89 e5                    mov    %esp,%ebp
   3:    83 e4 f0                 and    $0xfffffff0,%esp
   6:    e8 fc ff ff ff           call   7 <main+0x7>
            7: R_386_PC32    lib_pro
   b:    b8 00 00 00 00           mov    $0x0,%eax
  10:    89 ec                    mov    %ebp,%esp
  12:    5d                       pop    %ebp
  13:    c3                       ret

第12行,可以看到 lib_pro 被标记为 *UND* (undefined),这表示 lib_pro 在 user.c 中没有定义,需要在符号解析过程中链接器到别的模块去查找是否存在 lib_pro 的定义。

当汇编器 (assembler) 产生目标文件时,它并不知道代码和数据在内存中最终的地址,更不用说引用的外部函数和全局变量的地址。因此,每当汇编器碰到一个无法判定最终地址的外部引用时,都会生成一个重定向入口项 (relocation entry) ,来告诉链接器当它合并目标文件时如何去修改引用地址,参见上面目标文件内容第 20 行。

1
2
3
4
5
typedef struct {
    int offset;
    int symbol:24,
        type:8;
} Elf32_Rel;

上面是 ELF 重定向入口项的格式,offset 表示符号引用的段偏移,symbol 标识引用应该指向什么,type 告诉链接器如何修改新的引用。如 user.c 目标文件第20行,offset=0x7, symbol=lib_pro, type=R_386_PC32 (表示地址采用32位 PC-relative 地址)。信息有了,可以进行重定向了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
foreach section s {
    foreach relocation entry r {
        /* ptr to reference to be relocated */
        refptr = s + r.offset;
        /* relocate a PC-relative reference */
        if (r.type == R_386_PC32) {
            /* ref's run-time address */
            refaddr = ADDR(s) + r.offset;
            *refptr = (unsigned) (ADDR(r.symbol) + *refptr - refaddr);
        }
        /* rrelocate an absolute reference */
        if (r.type == R_386_32) {
            *refptr = (unsigned) (ADDR(r.symbol) + *refptr);
        }
    }

上面是重定向算法的 pseudocode。

让我们来看最终的可执行文件(有删减),

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#gcc user.c product.c
#objdump -dj .text a.out
...
Disassembly of section .text:
08048330 <_start>:
...
080483e4 <main>:
 80483e4:    55                       push   %ebp
 80483e5:    89 e5                    mov    %esp,%ebp
 80483e7:    83 e4 f0                 and    $0xfffffff0,%esp
 80483ea:    e8 09 00 00 00           call   80483f8 <lib_pro>
 80483ef:    b8 00 00 00 00           mov    $0x0,%eax
 80483f4:    89 ec                    mov    %ebp,%esp
 80483f6:    5d                       pop    %ebp
 80483f7:    c3                       ret

080483f8 <lib_pro>:
 80483f8:    55                       push   %ebp
 80483f9:    89 e5                    mov    %esp,%ebp
 80483fb:    83 ec 18                 sub    $0x18,%esp
 80483fe:    c7 04 24 d0 84 04 08     movl   $0x80484d0,(%esp)
 8048405:    e8 0e ff ff ff           call   8048318 <puts@plt>
 804840a:    c9                       leave
 804840b:    c3                       ret
 804840c:    90                       nop
 804840d:    90                       nop
 804840e:    90                       nop
 804840f:    90                       nop
...

如第11行,偏移量已经变成 0x9,简单算一下,0x80483f8 – 0x80483ef = 0x9. 这样重定向之后的可执行程序就生成了。

—————————————————————————————————

继续最前面提出来的函数 stub 方法,现在很容易就可以看出,是在符号解析过程中巧妙实现的。

链接器使用静态库解决符号引用过程是这样的:

  1. 链接器依照编译命令行顺序从左向右扫描目标文件和静态库,扫描过程中,链接器维护三个符号集合,分别为 E: 将会被合并进可执行文件的重定向目标文件集合,U: 未解决的符号引用集合,D: 已扫描过目标文件中的符号集合。
  2. 对于每一个输入文件 f,
    • 如果 f 是目标文件,则将 f 加入 E,并更新 U 和 D,继续下一个文件。
    • 如果 f 是静态库,链接器试图用静态库中某成员的符号定义来解决 U 中的符号引用,如果成员 m 定义的符号解决了 U 中的符号引用,则 m 被加入 E,并更新 U 和 D。继续遍历静态中其他成员,直到 U 和 D 不再变化,丢弃所有没有在 E 中包含的成员,继续下一个文件。
    • 如果 U 不为空,链接器完成了扫描,则报错。反之,链接器合并和重定向 E 中的所有目标文件,生成可执行文件。

从上可知,如果链接时,stub.o 放在静态库前面,则先会在它中符号匹配,匹配后更新 U,之后遇到静态库,因为该符号引用已解决,则不需要再链接该库中的对应符号。

Comments