课程主页：http://www.cs.cmu.edu/afs/cs/academic/class/15213-f15/www/schedule.html

课程资料：https://github.com/EugeneLiu/translationCSAPP

课程视频：https://www.bilibili.com/video/av31289365/

这一讲介绍了链接。

链接

C程序例子

考虑如下两个C程序：

main.c

int sum(int *a, int n);

int array[2] = {1, 2};

int main()
{
    int val = sum(array, 2);
    return val;
}

sum.c

int sum(int *a, int n)
{
    int i, s = 0;

    for (i = 0; i < n; i++) {
        s += a[i];
    }
    return s;
}

静态链接

连接器将可重定位目标文件组合起来，形成一个可执行目标文件prog：

为什么要链接

  • 原因1：模块化
    • 程序可以编写为一组较小的源文件，而不是一个整体。
    • 可以构建通用功能的库（稍后会详细介绍）
      • 例如，数学库，标准C库
  • 原因2：效率
    • 时间：单独编译
      • 更改一个源文件，编译，然后重新链接。
      • 无需重新编译其他源文件。
    • 空间：库
      • 常用函数可以聚合到单个文件中。
      • 但是可执行文件和运行中的内存映像仅包含它们实际使用的函数的代码。

链接器做了什么

  • 步骤1：符号解析

    • 程序定义和引用符号（全局变量和函数）：

      void swap() {…}   /* define symbol swap */
swap();           /* reference symbol swap */
int *xp = &x;     /* define symbol xp, reference x */

    • 符号定义存储在符号表的目标文件中（由汇编程序存储）。

      • 符号表是结构数组
      • 每个整体均包含符号的名称，大小和位置。

    • 在符号解析步骤中，链接器将每个符号引用与一个符号定义完全关联。

  • 步骤2：重定位

    • 将分开的代码和数据部分合并为单个部分。
    • 将符号从.o文件中的它们的相对位置重定位到可执行文件中其最终的绝对内存位置。
    • 更新对这些符号的所有引用以反映它们的新位置。

三种目标文件

  • 可重定位目标文件（.o文件）
    • 包含可以与其他可重定位目标文件组合以形成可执行目标文件的形式的代码和数据。
    • 每个.o文件都是从一个源（.c）文件生成的。
  • 可执行目标文件（a.out文件）
    • 包含二进制代码和数据，其形式可以被直接复制到内存并执行。
  • 共享目标文件（.so文件）
    • 特殊类型的可重定位目标文件，可以在加载时或运行时加载到内存中并进行动态链接。
    • Windows称为动态链接库（DLL）。

可执行可链接格式(ELF)

  • 目标文件的标准二进制格式
  • 如下三种文件的统一格式
    • 可重定位的目标文件（.o）
    • 可执行目标文件（a.out）
    • 共享目标文件（.so）
  • 通用名称：ELF二进制文件

ELF目标文件格式

  • ELF头
    • 字大小，字节顺序，文件类型（.o，exec，.so），机器类型等
  • 段头部表
    • 页面大小，虚拟地址存储段（节），段大小
  • .text部分
    • 代码
  • .rodata部分
    • 只读数据：跳转表，…
  • .data部分
    • 初始化的全局变量
  • .bss部分
    • 未初始化的全局变量
    • “以符号开头的块”
    • “更好地节省空间”
    • 有节标题，但不占用空间
  • .symtab部分
    • 符号表
    • 过程和静态变量名
    • 节名称和位置
  • .rel.text部分
    • .text部分的重定位信息
    • 可执行文件中需要修改的指令地址
    • 修改的说明
  • .rel.data节
    • .data节的重定位信息
    • 合并后的可执行文件中需要修改的指针数据的地址
  • .debug部分
    • 符号调试的信息（gcc -g）
  • 节头部表
    • 每个部分的偏移量和大小

形式如下：

步骤1：符号解析

链接器符号
  • 全局符号
    • 模块m定义的符号，可以被其他模块引用。
    • 例如：非静态C函数和非静态全局变量。
  • 外部符号
    • 模块m引用，但由其他模块定义的全局符号。
  • 局部符号
    • 由模块m专门定义和引用的符号。
    • 例如：用static属性定义的C函数和全局变量。
    • 本地链接器符号不是局部程序变量。
链接器如何解析多重定义的全局符号
  • 程序符号要么是强，要么是弱
    • 强：过程，以及初始化的全局变量
    • 弱：未初始化的全局变量

例如：

有了上述定义，现在给出规则：

  • 规则1：不允许使用多个强符号
    • 每一项只能定义一次
    • 否则链接器错误
  • 规则2：给定一个强符号和多个弱符号，选择强符号
    • 对弱符号的引用解析为强符号
  • 规则3：如果有多个弱符号，请选择任意一个
    • 可以用gcc –fno-common覆盖它
例子

在p2中对x的写入会覆盖y。

步骤2：重定位

重定位的图示如下：

加载可执行目标文件

ELF可执行目标文件：

x86-64运行时的内存映像：

打包常用函数

  • 如何打包程序员常用的函数？
    • 数学，I / O，内存管理，字符串处理等
  • 尴尬的是，到目前为止，给出的链接器框架是：
    • 选项1：将所有函数放入单个源文件中
      • 程序员将大对象文件链接到他们的程序中
      • 时间空间效率低下
    • 选项2：将每个函数放在单独的源文件中
      • 程序员将适当的二进制文件明确链接到他们的程序中
      • 效率更高，但给程序员带来负担
旧的解决方法：静态库
  • 静态库（.a存档文件）
    • 将相关的可重定位目标文件连接到带有索引的单个文件（称为存档）中。
    • 增强链接器，以便它通过在一个或多个归档中查找符号来尝试解析未解析的外部引用。
    • 如果存档成员文件解析引用，则将其链接到可执行文件。
创造静态库

  • 存档允许增量更新
  • 重新编译函数，以更改和替换存档中的.o文件。
例子

考虑如下代码：

main.c：

#include <stdio.h>
#include "vector.h"

int x[2] = {1, 2};
int y[2] = {3, 4};
int z[2];

int main()
{
    addvec(x, y, z, 2);
    printf("z = [%d %d]\n”, z[0], z[1]);
    return 0;
}

addvec.c：

void addvec(int *x, int *y,
            int *z, int n) {
    int i;

    for (i = 0; i < n; i++)
        z[i] = x[i] + y[i];
}

multvec.c：

void multvec(int *x, int *y,
             int *z, int n)
{
    int i;

    for (i = 0; i < n; i++)
        z[i] = x[i] * y[i];
}

整个过程如下：

使用静态库

  • 链接器解析外部引用的算法：

    • 按命令行顺序扫描.o文件和.a文件。
    • 在扫描过程中，保留当前未解析引用的列表。
    • 当遇到每个新的.o或.a文件obj时，请尝试针对obj中定义的符号来解析列表中的每个未解析的引用。
    • 如果扫描结束后未解决列表中有任何条目，则错误。

  • 问题：

    • 命令行顺序很重要！

    • 方法：将库放在命令行末尾。

      unix> gcc -L. libtest.o -lmine 
unix> gcc -L. -lmine libtest.o 
libtest.o: In function `main': 
libtest.o(.text+0x4): undefined reference to `libfun'
新的解决方法：共享库
  • 静态库具有以下缺点：
    • 复制已存储的可执行文件（每个函数都需要libc）
    • 复制正在运行的可执行文件
    • 系统库的一些小错误修复要求每个应用程序显式重新链接
  • 现代解决方案：共享库
    • 共享库是目标模块，在运行或加载时，可以加载到任意内存地址，并和一个在内存中的程序链接起来
    • 也称为：动态链接库，DLL，.so文件
  • 动态链接可能在首次加载并运行可执行文件时发生（加载时链接）。
    • Linux的常见情况，由动态链接程序（ld-linux.so）自动处理。
    • 标准C库（libc.so）通常是动态链接的。
  • 程序开始后也可能发生动态链接（运行时链接）。
    • 在Linux中，这是通过调用dlopen（）接口来完成的
      • 分布式软件。
      • 高性能Web服务器。
      • 运行时库打桩。
  • 共享的库例程可以由多个进程共享。
    • 当我们了解虚拟内存时，将对此进行更多介绍。

整个过程如下：

链接总结

  • 链接是一种允许从多个目标文件构造程序的技术。
  • 链接可以在程序生命周期的不同时间发生：
    • 编译时间（程序编译时）
    • 加载时间（将程序加载到内存中时）
    • 运行时间（程序正在执行时）
  • 了解链接可以帮助您避免讨厌的错误，并使您成为更好的程序员。

案例学习：库打桩

库打桩

  • 库打桩：强大的链接技术，使程序员可以拦截对任意函数的调用
  • 打桩可以发生在：
    • 编译时间：编译源代码时
    • 链接时间：将可重定位目标文件静态链接以形成可执行目标文件时
    • 加载/运行时间：将可执行对象文件加载到内存中，进行动态链接，然后执行。

应用

  • 安全
    • 沙盒
    • 幕后加密
  • 调试
  • 监控和分析
    • 计算函数调用次数
    • 表征调用站点和函数参数
    • Malloc跟踪
      • 检测内存泄漏
      • 生成地址跟踪

例子

int.c：

#include <stdio.h>
#include <malloc.h>

int main()
{
    int *p = malloc(32);
    free(p);
    return(0);
}
  • 目标：在不破坏程序且不修改源代码的情况下，跟踪分配和释放块的地址和大小。
  • 三种解决方案：在编译时，链接时和加载/运行时打桩。
编译时打桩

mymalloc.c：

#ifdef COMPILETIME
#include <stdio.h>
#include <malloc.h>

/* malloc wrapper function */
void *mymalloc(size_t size)
{
    void *ptr = malloc(size);
    printf("malloc(%d)=%p\n",
           (int)size, ptr);
    return ptr;
}

/* free wrapper function */
void myfree(void *ptr)
{
    free(ptr);
    printf("free(%p)\n", ptr);
}
#endif

malloc.h：

#define malloc(size) mymalloc(size)
#define free(ptr) myfree(ptr)

void *mymalloc(size_t size);
void myfree(void *ptr);

运行如下命令得到结果：

linux> make intc
gcc -Wall -DCOMPILETIME -c mymalloc.c
gcc -Wall -I. -o intc int.c mymalloc.o
linux> make runc
./intc
malloc(32)=0x1edc010
free(0x1edc010)
linux>
链接时打桩

mymalloc.c：

#ifdef LINKTIME
#include <stdio.h>

void *__real_malloc(size_t size);
void __real_free(void *ptr);

/* malloc wrapper function */
void *__wrap_malloc(size_t size)
{
    void *ptr = __real_malloc(size); /* Call libc malloc */
    printf("malloc(%d) = %p\n", (int)size, ptr);
    return ptr;
}

/* free wrapper function */
void __wrap_free(void *ptr)
{
    __real_free(ptr); /* Call libc free */
    printf("free(%p)\n", ptr);
}
#endif

运行如下命令得到结果：

linux> make intl
gcc -Wall -DLINKTIME -c mymalloc.c
gcc -Wall -c int.c
gcc -Wall -Wl,--wrap,malloc -Wl,--wrap,free -o intl int.o mymalloc.o
linux> make runl
./intl
malloc(32) = 0x1aa0010
free(0x1aa0010)
linux>
  • “-Wl”标志将参数传递给链接器，并用空格替换每个逗号。
  • “—wrap，malloc” arg指示链接器以特殊方式解析引用：
    • 对malloc的引用应解析为$\text{wrap_malloc}$
    • 对$\text{__real_malloc}$的引用应解析为malloc
运行时打桩

mymalloc.c：

#ifdef RUNTIME
#define _GNU_SOURCE
#include <stdio.h>
#include <stdlib.h>
#include <dlfcn.h>

/* malloc wrapper function */
void *malloc(size_t size)
{
    void *(*mallocp)(size_t size);
    char *error;

    mallocp = dlsym(RTLD_NEXT, "malloc"); /* Get addr of libc malloc */
    if ((error = dlerror()) != NULL) {
        fputs(error, stderr);
        exit(1);
    }
    char *ptr = mallocp(size); /* Call libc malloc */
    printf("malloc(%d) = %p\n", (int)size, ptr);
    return ptr;
}

/* free wrapper function */
void free(void *ptr)
{
    void (*freep)(void *) = NULL;
    char *error;

    if (!ptr)
        return;

    freep = dlsym(RTLD_NEXT, "free"); /* Get address of libc free */
    if ((error = dlerror()) != NULL) {
        fputs(error, stderr);
        exit(1);
    }
    freep(ptr); /* Call libc free */
    printf("free(%p)\n", ptr);
}
#endif

运行如下命令得到结果：

linux> make intr
gcc -Wall -DRUNTIME -shared -fpic -o mymalloc.so mymalloc.c -ldl
gcc -Wall -o intr int.c
linux> make runr
(LD_PRELOAD="./mymalloc.so" ./intr)
malloc(32) = 0xe60010
free(0xe60010)
linux>
  • LD_PRELOAD环境变量通过首先查看mymalloc.so来告诉动态链接器解析未解析的引用（例如，解析为malloc）。

打桩回顾

  • 编译时
    • 对malloc/free的显式调用将宏扩展为对mymalloc/myfree的调用
  • 链接时
    • 使用链接程序技巧进行特殊的名称解析
      • $\text{malloc}\to \text{__wrap_malloc}$
      • $\text{__real_malloc}\to \text{malloc}$
  • 加载/运行时
    • 实现自定义版本的malloc/free，该版本使用动态链接以不同的名称加载库malloc/free