csapp第七章——链接

链接

链接 (linking) 是将各种代码和数据片段收集并组合成为一个单一文件的过程，这个文件可被加载（复制）到内存并执行 。

• 链接可以执行于编译时 (compile time), 也就是在源代码被翻译成机器代码时；

• 也可以执行与加载时 (load time), 也就是在程序被加载器 (loader) 加载到内存并执行时；

• 甚至执行于运行时 (run time), 也就是由应用程序来执行。

编译器驱动程序

/* main.c */
/* $begin main */
int sum(int *a, int n);

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

int main()
{
    int val = sum(array, 2);
    return val;
}
/* $end main */

/* sum.c */
/* $begin sum */
int sum(int *a, int n)
{
    int i, s = 0;

    for (i = 0; i < n; i++) {
        s += a[i];
    }
    return s;
}
/* $end sum */

1. c预处理器(cpp)将 的源程序 main.c译成一个 ASCII 码的中间文件 main.i
2. 编译器 (cc1), 它将 main.i 翻译成一个 ASCII 汇编语言文件main.s
3. 汇编器 (as), 它将 main.s 翻译成一个可重定位目标文件(relo-eatable object file) main. o:
4. 运行链接器程序 ld, 将main.o,sum.o 以及一些必要的系统目标文件组合起来，创建一个可执行目标文件 (executable object file)prog
5. shell 调用操作系统中一个叫做加载器 (loader)的函数，它将 可执行文件 prog 中的代码和数据复制到内存，然后将控制转移到这个程序的开头。

静态链接

为了构造可执行文件，链接器必须完成两个主要任务：

• 符号解析 (symbol resolution) 。目标文件定义和引用符号，每个符号对应于一个函数、一个全局变量或一个静态变量（即 中任何以 static 属性 声明的变量）。符号解析的目的是将每个符号引用正好和一个符号定义关联起来。
• 重定位 (relocation) 。编译器和汇编器生成从地址0开始的代码和数据节。链接器通过把每个符号定义与一个内存位置关联起来，从而重定位这些节，然后修改所有对这些符号的引用，使得它们指向这个内存位置 链接器使用汇编器产生的重定位条目(relocation entry) 的详细指令，不加甄别地执行这样的重定位。

目标文件

• 可重定位目标文件。包含二进制代码和数据，其形式可以在编译时与其他可重定位目标文件合并起来，创建一个可执行目标文件
• 可执行目标文件。包含二进制代码和数据，其形式可以被直接复制到内存并执行
• 共享目标文件。一种特殊类型的可重定位目标文件，可以在加载或者运行时被动态地加载进内存并链接。
• 编译器和汇编器生成可重定位目标文件（包括共享目标文件）。链接器生成可执行目标文件。

系统	格式
第一个Unix系统	a.out
Windows	可移植可执行格式(Portable Executable，PE)
MacOS-X	Mach-O
x86-64 Linux Unix	可执行可链接格式(Executable and Linkable Format, ELF)

可重定位目标文件

节
.text	已编译程序的机器代码。
.rodata	只读数据段
.data	已初始化的全局和静态变量。
.bss	未初始化全局变量和静态变量
.symtab	符号表，它存放在程序中定义和引用的函数和全局变量的信息
.debug	一个调试符号表，其条目是程序中定义的局部变量和类型定义，程序中定义和引用的全局变量，以及原始的 源文件。只有以 -g 选项调用编译器驱动程序时，才会得到这张表。

符号和符号表

全局符号	模块定义并能被其他模块引用的全局符号	非静态的C函数和全局变量
外部符号	其他模块定义并被模块引用的全局符号	其他模块定义的非静态的C函数和全局变量
局部符号	只被模块定义和引用的局部符号	带 static 属性的C函数和全局变量。

• 局部C变量运行时存储在栈中

/* $begin elfsymbol */
typedef struct {
    int   name;      /* String table offset */
    char  type:4,    /* Function or data (4 bits) */
          binding:4; /* Local or global (4 bits) */
    char  reserved;  /* Unused */
    short section;   /* Section header index */
    long  value;     /* Section offset or absolute address */
    long  size;      /* Object size in bytes */
} Elf64_Symbol;
/* $end elfsymbol */

通过readelf -s 可以查看目标文件符号表

符号解析

• 链接器解析符号引用的方法是将每个引用与它输入的可重定位目标文件的符号表中的一个确定的符号定义关联起来。
• 当编译器遇到一个不是在当前模块中定义的符号（变量或函数名）时，会假设该符号是在其他某个模块中定义的，生成一个链接器符号表条目，并把它交给链接器处理。

链接器如何解析多重定义的全局符号

• 函数和已初始化的全局变量是强符号

• 未初始化的全局变量是弱符号。

根据强弱符号的定义， Linux 链接器使用下面的规则来处理多重定义的符号名：

• 规则1：不允许有多个同名的强符号。
• 规则 2: 如果有一个强符号和多个弱符号同名，那么选择强符号。
• 规则 3: 如果有多个弱符号同名，那么从这些弱符号中任意选择一个。

与静态库链接

链接器只复制被程序引用的目标模块

AR工具可用于生成静态链接库

[] ~/Desktop/csapp/code/link gcc -c addvec.c multvec.c
[] ~/Desktop/csapp/code/link ar rcs libvector.a addvec.o multvec.o
[] ~/Desktop/csapp/code/link gcc -c main2.c
[] ~/Desktop/csapp/code/link gcc -static -o prog2c main2.o ./libvector.a
[] ~/Desktop/csapp/code/link ./prog2c
z = [4 6]

链接器如何使用静态库来解析引用

• 在符号解析阶段，链接器从左到右按照它们在编译器驱动程序命令行上出现的顺序来扫描可重定位目标文件和存档文件。
• 如果静态库之间有依赖关系，我们要将调用函数的静态库放在定义函数静态库之前

重定位

合并输入模块，并为每个符号分配运行时地址。

重定位由两部分组成：

• 重定位节和符号定义。在这一步中，链接器将所有相同类型的节合并为同一类型的新的聚合节。然后，链接器将运行时内存地址赋给新的聚合节，赋给输入模块定义的每个节，以及赋给输入模块定义的每个符号。
• 重定位节中的符号引用。在这一步中，链接器修改代码节和数据节中对每个符号的引用，使得它们指向正确的运行时地址。依赖于重定位条目(relocation entry)。

重定位条目

代码的重定位条目放在 .rel.text巳初始化数据的重定位条目放在 .rel.data 中。

/* $begin elfrelo */
typedef struct {
    long offset;    /* Offset of the reference to relocate */
    long type:32,   /* Relocation type */
         symbol:32; /* Symbol table index */
    long addend;    /* Constant part of relocation expression */
} Elf64_Rela;
/* $end elfrelo */

重定位类型：

• R_X86_64_PC32 。重定位一个使用 32 位PC相对地址的引用。
• R_X86_64_32 。重定位一个使用 32 位绝对地址的引用。
• …

重定位符号引用

重定位算法的伪代码：

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

[] ~/Desktop/csapp/code/link objdump -dx main.o

可能是gcc版本的问题，重定位类型不一致。都使用了相对寻址。最后也无法成功编译prog。

可执行目标文件

可执行文件是完全链接的（可重定位的）

• ELF 可执行文件被设计得很容 加载到内存，可执行文件的连 的片 (chunk) 被映射到连续的内存段 程序头部表 (program h eader table) 描述了这种映射关系。
• 所谓内核就是操作系统驻留在内存的部分。

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

加载可执行目标文件

/linux> ./prog 

Linux 系统中的每个程序都运行在一个进程上下文中，有自己的虚拟地址空间。当 shell 运行一个程序时，父 shell 进程生成一个子进程，它是父进程的一个复制。子进程通过 execve统调用启动加载器。加载器删除子进程现有的虚拟内存段，并创建一组新的代码、数据、堆和栈段。新的栈和堆段被初始化为零 通过将虚拟地址空间中的页映射到可执行文件的页大小的片 (chunk), 新的代码和数据段袚初始化为可执行文件的内容。最后，加载器跳转到 _start地址，它最终会调用应用程序的 main 函数。除了一些头部信息，在加载过程中没有任何从磁盘到内存的数据复制 。直到 CPU 引用一个被映射的虚拟页时才会进行复制，此时，操作系统利用它的页面调度机制自动将页面从磁盘传送到内存。

动态链接共享库

共享库也称为共享目标 (shared object), Linux 系统中通常用 .so 后缀来表示。微软的操作系统大最地使用了共享库，它们称为 DLL(动态链接库）。

linux > cd lib64

windows > C:\Windows\System32

生成动态链接库及动态链接的可执行程序

-fpic 选项指示编译器生成与位置无关的代码。
-shared选项指示链接器创建一个共享的目标文件。

动态链接器本身就是一个共享目标（如在 Linux 系统上的 ld - linux. so), 加载器不会像它通常所做地那样将控制传递给应用，而是加载和运行这个动态链接器。

我们可以在节中查看到动态链接所需要的动态链接库

从应用程序中加载和链接共享库

动态链接是强大有用的技术。

• 分发软件。
• 构建高性能 Web 服务器。

Linux 系统为动态链接器提供了一个简单的接口，允许应用程序在运行时加载和链接共享库。分别为dlopen 、dlsym 和 dlclose 函数

#include <stdlib.h>
#include <dlfcn.h>

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

int main()
{
    void *handle;
    void (*addvec)(int *, int *, int *, int);
    char *error;

    /* Dynamically load the shared library that contains addvec() */
    handle = dlopen("./libvector.so", RTLD_LAZY);
    if (!handle) {
        fprintf(stderr, "%s\n", dlerror());
        exit(1);
    }

    /* Get a pointer to the addvec() function we just loaded */
    addvec = dlsym(handle, "addvec");
    if ((error = dlerror()) != NULL) {
        fprintf(stderr, "%s\n", error);
        exit(1);
    }

    /* Now we can call addvec() just like any other function */
    addvec(x, y, z, 2);
    printf("z = [%d %d]\n", z[0], z[1]);

    /* Unload the shared library */
    if (dlclose(handle) < 0) {
        fprintf(stderr, "%s\n", dlerror());
        exit(1);
    }
    return 0;
}
/* $end dll */

gcc -rdynamic -o prog2r dll.c -ldl

调用函数后可以看到成功在运行中调用libvector.so库

Java 定义了一个标准调用规则，叫做Java 本地接口 (Java Native Interface, JNI) , 它允许Java 程序调用”本地的 “C 或C++ 函数。 JNI 的基本思想是将本地函数（如 foo) 编译到一个共享库中（如 foo.so) 当一个正在运行的 Java 程序试图调用函数 foo 时， Java解释器利用 dlopen 接口（或者与其类似的接口）动态链接和加载 foo.so, 然后再调用 foo

位置无关代码

可以加载而无需重定位的代码称为位置无关代码 (Position Independent Code, PIC)。用户对 GCC 使用 -fpic 选项指示 GNU 编译系统生成 PIC 代码。 共享库的编译必须总使用该选项。

PIC数据引用

编译器可以利用代码段和数据段之间不变的距离，直接 PC 相对引用，并增加一个重定位，让链接器在构造这个共享模块时解析它。

PIC函数调用

• 过程链接表 (PLT)PLT 是一个数组，其中每个条目是 16 字节代码。 PLT[O] 是一个特殊条目，它跳转到动态链接器中。每个被可执行程序调用的库函数都有它自己PLT 条目。每个条目都负责调用一个具体的函数。
• 全局偏移量表 (GOT)。正如我们看到的， GOT 是一个数组，其中每个条目是8 字节地址。和 PLT 联合使用时,GOT [0]和 GOT[l] 包含动态链接器在解析函数地址时会使用的信息。 GOT[2] 是动态链接器在 ld-linux.so 模块中的入口点。

延迟绑定

假设我们用调用addvec函数，首先进入PLT[2]。若为第1次调用，由于采用延迟绑定，我们需要进行动态链接，然后把控制传递给addvec。第n（n>1)调用由于addvec函数已经被加载到内存中确定的位置，则会从直接从PLT表跳转到GOT表中，在GOT表中进行函数调用。

• plt在代码段，got在数据段

• plt是地址的填写者，got是地址的保存者

库打桩机制

Linux 链接器支持一个很强大的技术，称为库打桩 (library interpositioning), 它允许你截获对共享库函数的调用，取而代之执行自己的代码。

编译时打桩

int.c

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

int main()
{
    int *p = malloc(32);
    free(p);
    return(0);
}

malloc.h

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

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

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 address 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
                                                    

gcc -c mymalloc.c -o mymalloc.o
gcc -I -o intc int.c mymalloc.o

由于有 -I.参数，所以会进行打桩，它告诉预处理器在搜索通常的系统目录之前，先在当前目录中查找 malloc.h 。

可一看到先调用了mymalloc函数后再调用malloc函数，由于再包装函数增加了printf函数，得到如下输出：

链接时打桩

Linux 静态链接器支持用 —wrap 标志进行链接时打桩。

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

gcc  -Wl,--wrap,malloc -Wl,--wrap,free -o intc1 int.o mymalloc.o

-Wl option 标志把 option 传递给链接器。 option 中的每个逗号都要替换为一个空格。所以 -Wl,—wrap,malloc 就把- -wrap malloc 传递给链接器。

运行时打桩

/* malloc wrapper function */

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

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

    mallocp = dlsym(RTLD_NEXT, "malloc"); /* Get address 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);
}
/* $end interposer */

由于printf函数会调用malloc函数，malloc打桩调用printf会陷入死循环引发段错误。因此我们将其注释掉

echo $SEHLL    //打印当前shell
chsh -s /bin/bash  //切换shell
LD_PRELOAD="./mymalloc.so" ./xxx 运行时打桩

可以对任意程序进行运行时打桩

处理目标文件的工具

Linux 系统中有大量可用的工具 可以 帮助你理解和处理目 标文件 。特别地， GNU binutils 包尤其有帮助，而且可以运行在每个Linux平台上

• AR: 创建静态库，插入、删除、列出和提取成员
• STRINGS: 列出 个目标文件中所有可打印的字符串。
• STRIP: 目标文件中删除符号表信息
• NM: 列出目标文件的符号表中定义的符号。
• SIZE: 列出目标文件中节的名字和大小
• READELF: 显示目标文件的完整结构，包括 E LF 头中编码的所有信息。包含SIZE和 NM 功能。

• OBJDUMP: 所有二进制工具之母。能够显示一个目标文件中所有的信息。它最大的作用是反汇编 .text 节中的二进制指令

• LDD: 列出一个可执行文 件在运行时所需要的共享库