资源：

视频课程



视频课件



《深入理解计算机系统》第七章–链接



《深入理解计算机系统》CSAPP——第七章

Linking

is the process of

collecting

and

combining

various pieces of code and data

into a single file

that can be

loaded (copied)

into

memory

and

executed

.

Linking

can be performed at

compile time

, when the source code is translated into machine code; at

load time

, when the program is loaded into memory and executed by the loader; and even at

run time

, by application programs.

Linkers

play a crucial role in software development because they enable

separate compilation

.

分开编译的好处：如果其中一个模块修改了，只需重新编译该模块然后链接整个应用程序，而无需重新编译其他部分。

7.1 Compiler Drivers

Most

compilation systems

provide a

compiler driver

that invokes the language

preprocessor

,

compiler

,

assembler

, and

linker

, as needed on behalf of the user.

示例：

过程（第一章讲过）：

1、The driver first runs the C

preprocessor

(cpp), which translates the C

source file main.c

into an

ASCII intermediate file main.i

. 预处理器会根据

#

字符修改 C语言代码，如，在

#include <stdio.h>

的命令处，会插入

stdio.h

的内容。

2、The driver runs the

C compiler

(cc1), which translates

main.i

into an

ASCII assembly-language file main.s

.

3、The driver runs the

assembler

(as), which translates

main.s

into a

binary relocatable object file main.o

. The driver goes through the

same process

to generate

sum.o

.

4、It runs the

linker

program

ld

, which

combines


main.o

and

sum.o

, along with the necessary

system object files

, to create the

binary executable object file prog

.

7.2 Static Linking

Static linkers

such as the Linux

ld

program take as

input

a

collection

of

relocatable


object files

and

command-line arguments

and generate as

output

a fully linked

executable


object file

that can be

loaded

and

run

.

The

input relocatable object files

consist of various

code and data sections

, where

each section is a contiguous sequence of bytes

.

Instructions

are in one section,

initialized global variables

are in another section, and

uninitialized variables

are in yet another section. (节的介绍在后面)

To build the

executable

, the

linker

must perform two main tasks:

• 
  Symbol resolution
  
  
  
  Object files define and reference symbols
  
  , where each
  
  symbol
  
  corresponds to a
  
  function
  
  , a
  
  global variable
  
  , or a
  
  static variable
  
  . The
  
  purpose
  
  of
  
  symbol resolution
  
  is to associate each symbol
  
  reference
  
  with exactly one symbol
  
  definition
  
  . （符号解析，为了将符号引用和符号的定义相关联）

• 
  Relocation
  
  
  
  Compilers
  
  and
  
  assemblers
  
  generate
  
  code and data sections
  
  that start at address
  
  0
  
  .
  
  The
  
  linker
  
  
  relocates
  
  these
  
  sections
  
  by associating a
  
  memory location with each symbol definition
  
  , and then modifying all of the references to those symbols so that they
  
  point to this memory location
  
  .（将符号和内存地址关联）
  
  The
  
  linker
  
  blindly performs these relocations using detailed instructions, generated by the
  
  assembler
  
  , called
  
  relocation entries
  
  . （后面介绍）
  
  （编译器编译的时候不知道符号在运行时的实际地址，这里用相对地址，节中的数据地址为相对该节开始地址的偏移，在链接重定位后才知道符号的绝对地址）

Object files

are merely

collections of blocks of bytes

.

Some of these blocks contain

program code

, others contain

program data

, and others contain

data structures that guide the linker and loader

. （后面有介绍）

A

linker


concatenates blocks together

, decides on

run-time locations

for the concatenated blocks, and

modifies

various

locations

within the

code and data blocks

.

Linkers have minimal understanding of the target machine

. The

compilers

and

assemblers

that generate the object files have already done

most of the work

.

7.3 Object Files

Object files come in

three

forms:

• 
  Relocatable object file
  
  
  Contains
  
  binary code and data
  
  in a form that can be
  
  combined with other relocatable object files
  
  at
  
  compile time
  
  to create an
  
  executable object file
  
  . （7.1 节第三步，链接前生成的 .o 文件，每个源文件生成自己的 .o，还需要链接才能生成可执行文件）

• 
  Executable object file
  
  
  Contains
  
  binary code and data
  
  in a form that can be copied
  
  directly into memory and executed
  
  .
  
  （7.1 节第4步，链接后生成的可执行文件）

• 
  Shared object file
  
  
  A special type of
  
  relocatable object file
  
  that can be
  
  loaded into memory
  
  and
  
  linked dynamically
  
  , at either
  
  load time
  
  or
  
  run time
  
  . (共享目标文件，可在加载或者运行时动态的链接)

Object files

are organized according to specific

object file formats

, which

vary from system to system

.

本书以

ELF（Executable and Linkable Format）

格式为例讨论。

7.4 Relocatable Object Files

ELF 格式如下：

各部分内容的介绍：

1、

ELF header

，提供关于这个二进制文件的信息，如 word size, byte ordering, file type（.o, exec, .so), machine type，etc.

2、

.text

已编译程序的机器代码。

3、

.bss

原始的含义是

block started by symbol

，但为了好记可以当作

Better Save Space

的缩写。

4、

.symtab

符号表包含函数，全局变量和静态变量。每个符号都有一个条目（一个结构体），包含该符号的信息。

5、

.rel.text

节，包含

.text

节中需要重定位的信息；在重定位生成可执行文件后才能确定地址的指令的地址。如在符号表中的函数，其地址为相对地址，只有重定位后才知道绝对地址。

6、

.rel.data

节，包含

.data

节中需要重定位的信息，如某个已初始化的全局变量存在

.data

节中，该全局变量（符号）在符号表中的地址为相对地址，在链接器重定位后才能知道在内存中的地址。

7、

Section header table

节，包含不同节的起始位置信息。（offsets and sizes of each section）

7.5 Symbols and Symbol Tables

Each

relocatable object module

,

m

, has a

symbol table

that contains information about the

symbols

that are defined and referenced by

m

.

In the context of a

linker

, there are

three

different kinds of symbols:

注意

local symbols

不是程序的局部变量，程序的非静态局部变量是在运行时存储在栈上。

示例（a pair of functions in the same module define a static local variable x）：

1 int f()
2 {
3 	static int x = 0;
4 	return x;
5 }
6 
7 int g()
8 {
9 	static int x = 1;
10 	return x;
11 }

In this case, the

compiler

exports

a pair of local linker symbols

with

different names

to the

assembler

. 如可能用

x.1

表示函数

f

中的变量

x

，用

x.2

表示函数

g

中的

x

。

Symbol tables

are built by

assemblers

, using

symbols

exported by the

compiler

into the

assembly-language .s file

.

ELF 格式的符号表包含在

.symtab

节中，符号表的条目结构见下图：


name

是符号名字的字符串在

.strtab

中的字节偏移量。


value

是符号的地址，对于

relocatable modules

是在对应节中的偏移量；如果是可执行文件，则是绝对地址。

Each

symbol

is assigned to some

section

of the object file, denoted by the

section field

, which is an

index

into the

section header table

.

有三个伪节在节表头中没有索引：

• 
  ABS
  
  
  不该被重定位的符号

• 
  UNDEF
  
  
  未定义的符号，即在其他 module 中定义，但在本 module 中使用的符号

• 
  COMMON
  
  
  未初始化的数据，即未被分配位置。
  
  For
  
  COMMON
  
  symbols, the
  
  value
  
  field gives the
  
  alignment requirement
  
  , and
  
  size
  
  gives the
  
  minimum
  
  size.

注意：

1、

COMMON

伪节 和

.bss

节的区别：

2、上面三个伪节只在

可重定位文件

中有，在

可执行文件

中没有。

示例：

用

GNU READELF

程序查看

main.o

文件的最后三个符号表条目：

1、

符号

main

是一个函数（FUNC），大小为 24 字节，该符号被分配在

.text

节中（NDx 为1，根据图 7.3 中表可知，索引为 1 的节为

.text

节），其在

.text

节中位置偏移量为 0（Value），该函数是全局的函数（Bind），

Num

表示该条目的索引，8代表是第 9 个条目，前面还有 8 个符号表条目。

2、

符号

array

是一个全局的对象，8字节，位于

.data

节偏移量为 0 的位置处。

3、

符号

sum

是引用的外部符号，因此在这里无位置和大小的参数。

7.6 Symbol Resolution

链接器进行符号解析的过程

：将每个

引用

和该

符号

在

可重定位符号表

中的

唯一 符号定义

关联起来。

The

compiler

allows

only one definition

of each

local symbol per module

.

如果链接器在当前模块中未找到符号定义，则会当作该符号在其他模块中定义，生成一个 linker symbol table entry，然后让链接器去处理，如果链接时不能在其他模块中找到该符号的定义，则打印错误信息并结束链接。

7.6.1 How Linkers Resolve Duplicate Symbol Names

Linux 编译系统对

链接时发现多个模块定义了相同名字的全局变量

的处理：

1. 编译阶段，编译器将所有的全局符号分类为 strong 或者 weak 再给汇编器。函数和初始化后的全局变量为 strong 符号，未初始化的全局变量为 weak 符号。
2. 汇编生成符号表时含有 strong 和 weak 的信息。
3. 链接时根据 strong 和 weak 信息处理 重名的全局符号：
   
   规则1：不允许存在多个同名的 strong 符号；
   
   规则2：如果有一个 strong 符号和多个 weak 符号，选择 strong 符号；
   
   规则3：多个 weak 符号，则随便选择一个 weak 符号；（容易产生 bug）

7.6.2 Linking with Static Libraries

All

compilation systems

provide a mechanism for

packaging related object modules into a single file

called a

static library

, which can then be supplied as

input to the linker

.

链接生成可执行文件时，链接器只复制静态库中程序中

用到的模块

。

Linux 系统中，静态库以一种

archive

的文件格式存在磁盘中。

An

archive

is a

collection of concatenated relocatable object files

, with a

header

that describes the

size

and

location

of each member

object file

.

Archive

filenames are denoted with the

.a suffix

.

例子见书中示例

7.6.3 How Linkers Use Static Libraries to Resolve References

符号解析

时，

链接器

按照编译时输入在

命令行

中的位置

从左到右

扫描

可重定位文件

和

归档文件（archives）

。

链接器

在扫描过程中，将那些要

被组合

起来生成

可执行文件

的 relocatable 文件归到

E

集合中。

链接

时将还

未解析

的

符号

放到

U

集合中。（如引用了，但在别的文件中定义的符号）

链接

时将那些在

前面

的

输入文件

中

已经定义了的符号

放到

D

集合中。

• 对命令行中的每个文件
  
  f
  
  ，如果是
  
  可重定位目标文件
  
  ，则放入
  
  E
  
  集合中，并根据该文件中
  
  符号
  
  的状态跟新 U 和 D 的集合，然后处理下一个文件。
• 如果文件
  
  f
  
  是
  
  归档文件
  
  ，链接器会尝试将
  
  U 中的符号
  
  和
  
  归档文件中已经定义的符号
  
  进行
  
  匹配
  
  ，如果在归档文件成员 m 中找到 U 中符号的定义，则将该符号转到 D 中，将 m 加入 E 集合中。通过这种方式扫描
  
  归档文件
  
  中所有的
  
  可重定位目标文件
  
  ，
  
  最后将没有用到的目标文件丢弃
  
  ，然后处理
  
  后面的输入文件
  
  。
• 如果
  
  链接器
  
  扫描完所有的
  
  输入文件
  
  后
  
  U 是非空
  
  的，则打印错误然后终止链接；否则将 E 中所有的文件构建生成
  
  可执行文件
  
  。

从上述过程可以看出，

链接

时对命令行中

输入文件的顺序

有要求，

库文件

必须放在需要用到它的

可重定向目标文件

的后面，否则会链接失败。

7.7 Relocation

在

链接器

完成

符号解析

的步骤后，知道了每个输入模块中代码（

.text

节）和 数据（

.data

节）的大小。然后开始执行

重定位

过程，即将所有的

输入模块合并起

来然后为每个

符号

分配

运行时的地址

。该过程包含以下两个步骤：

• 
  Relocating sections and symbol definitions
  
  
  将所有相同类型的节（如
  
.data

  节）合并为一个新的
  
  同类型聚合节
  
  用于可执行文件。然后为聚合节分配 run-time memory addresses。

• 
  Relocating symbol references within sections
  
  
  链接器将代码（
  
.rel.text

  ）和数据（
  
.rel.data

  ）节中的符号引用指向正确的地址。 (前面讲过有两个节存放需要重定位的信息)

7.7.1 Relocation Entries

汇编器

生成

目标模块（object mudule)

时，不知道代码和数据最终将被存在内存中的什么地方，因此当

汇编器

遇到一个

不知道地址的引用

时，会生成一个

重定位条目

（relocation entry），告诉

链接器

在合并

目标文件

以生成

可执行文件

时怎么

修改这个引用的地址

。

Figure 7.9 shows the format of an ELF relocation entry.

7.8 Executable Object Files

Figure 7.13 summarizes the kinds of information in a typical

ELF executable file

.

可执行文件

的格式和

可重定位文件

基本相似，有几处不同如下：

1. 
ELF

   表头均描述文件的基本信息，但
   
   可执行文件
   
   中也包含程序的
   
   入口点（entry point）
   
   ，即程序运行时执行
   
   第一条指令的地址
   
   。

2. 可执行文件多了一个
   
Segment header table

   节

3. 可执行文件中多了
   
.init

   节，该节定义程序的
   
   初始化代码
   
   需要调用的函数
   
_init

   。 初始化代码是程序
   
   最先运行
   
   的一段代码，在 main 函数之前运行。

4. 可执行文件中
   
   不需要重定位信息的节
   
   
.rel.text

   和
   
.rel.data

   。

5. 
.text

   ，
   
.rodata

   和
   
.data

   节的内容是一样的，但可执行文件中这些节被重定位到最终
   
   运行时的内存地址
   
   。

7.9 Loading Executable Object Files

loading

：通过加载器（loader) 复制

可执行文件

的

代码

和

数据

到

内存

中，然后依据

入口点

（entry point）跳到第一条指定的地方来运行程序的过程。

Every running Linux program has a

run-time memory image

similar to the one in Figure 7.15.

1. 代码段（code segment）：在 Linux x86-64 系统中，代码段的起始地址为 0x400000。
2. 数据段（data segment）：
   
.data

   和
   
.bss

   中数据。
3. 运行时堆（heap）：调用
   
malloc

   库时用到，向上增长。
4. 预留给共享库使用的区域。
5. 用户栈（user stack）：起始地址为最大的合法地址（largest legal user address，
   
   
   
   2

   48

   −

   1

   2^{48} – 1
   
   
   
   
   
   
   
   2
   
   
   
   
   
   
   
   
   
   
   
   48
   
   
   
   
   
   
   
   
   
   
   
   
   −
   
   
   
   
   
   
   
   
   1
   
   
   
   
   
   ），然后向下增长。

6. 用户栈以上的区域，起始地址为
   
   
   
   2

   48

   2^{48}
   
   
   
   
   
   
   
   2
   
   
   
   
   
   
   
   
   
   
   
   48
   
   
   
   
   
   
   
   
   
   
   
   
   
   ，是预留给内核（kernel）中的代码和数据使用的。

7.10 Dynamic Linking with Shared Libraries

静态库的缺点：

1. 更新库时需要重新链接程序
2. 运行时库中代码被复制到 text segment of each running process，浪费内存资源。

A

shared library

is an

object module

that, at either

run time

or

load time

, can be

loaded

at an

arbitrary memory address

and

linked

with a program in memory.

该过程被称为

动态链接

，由

动态链接器

实现。

动态库在 Linux 的为

.so

的文件，在微软的操作系统中为

DLL

文件。

共享库动态链接过程：

共享库特点：

1. In any given file system, there is
   
   exactly one .so file
   
   for
   
   a particular library
   
   .

2. 这个库中的
   
   代码
   
   和
   
   数据
   
   被
   
   所有引用该库的可执行文件
   
   共享。

3. 在生成
   
   可执行文件
   
   的过程中，不会复制共享库的代码或数据；只是复制一些
   
   重定位和符号表
   
   的信息，为了在程序加载到内存时能引用共享库中的数据和代码。

4. 加载器加载和运行
   
   可执行程序
   
   时，如果看到
   
   可执行程序
   
   中有一个
   
.interp

   节（包含动态链接器的路径名），则会加载并允许动态链接器（一个共享库）来执行如下重定位过程：

   • 重定位用到的
     
     动态库的代码和数据
     
     到
     
     内存段
     
     。
   • 重定位可执行程序中定义在动态库中引用。

5. 动态链接器完成重定位后，将控制权交给应用程序，动态库的位置将在程序执行期间
   
   保持不变
   
   。

上述链接过程是在

程序加载

时

链接

。（dynamic linking at load-time）

7.11 Loading and Linking Shared Libraries from Applications

动态库

也能在

程序运行时

进行

动态链接

。（dynamic linking at run-time）

7.12 Position-Independent Code (PIC)

一个共享库

能被

多个运行的进程

使用。

PIC

：不需要重定位就能被加载的代码称为 PIC ( positionin dependent code )。

PIC Data References：


目标模块的数据段和代码段之间的距离在运行时是常量，保持不变。

7.13 Library Interpositioning

library interpositioning

：拦截对共享库的调用，然后执行自己的代码。

作用：


Using

interpositioning

, you could

trace the number of times

a particular library function is called,

validate

and

trace

its input and output values, or even

replace

it with a completely different implementation.

方法：


对于一个需要被打桩的函数，创建一个和该函数原型相同的包装函数（wrapper function），通过特殊的 interpositioning mechanism 来欺骗系统调用包装函数而非目标函数。

Interpositioning

can occur at

compile

time,

link

time, or

run

time as the program is being

loaded

and

executed

.

不同阶段库打桩的实现：

库打桩机制