linking 复习

July 11, 2024 · 17 min read

ayanami

linking 复习

No linker Problems

• efficiency: small change requires complete recompilation

• modularity: hard to share common functions (e.g. printf)

seperate compilation: separately compiled relocatable object files

reloc object files -> executable object file

What is linker

Linking is the process of: collecting and combining various pieces of code and data into a single executable file
Executable file: Can be loaded (copied) into memory and executed

Linking can be performed

at compile time, when the source code is translated into machine code by the linker
at load time, when the program is loaded into memory and executed by the loader
at run time, by application programs

编译过程：preprocessor -> compiler -> assembler -> linker

Static Linking

Input:

A relocatable object files and command line arguments

Output:

Fully linked executable object file that can be loaded and run

Relocatable object file

Contain binary code and data in a form that can be combined with other relocatable object files to create an executable file

Sections

Various code and data sections
Instructions are in one section
Initialized global variables are in one section
Uninitialized global variables are in one section

External reference

Reference to a symbol defined in another object file
The external references are value 0 in the relocatable object files in the previous example

Symbol resolution: Resolves external references

Relocates symbols

from their relative locations in the .o files
to new absolute positions in the executable

Object files

Relocatable object file
Executable object file
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)

Executable and Linkable Format (ELF)

Standard binary format for object files
Derives from AT&T System V Unix
later adopted by BSD Unix variants and Linux
One unified format for relocatable object files (.o), executable object files, and shared object files (.so)
generic name: ELF binaries
Better support for shared libraries than old a.out formats.

ELF Header

The first part is very important,used to store meta data usually

magic number, type (.o, exec, .so), machine, byte ordering, Beginning of the section header table (as well as the program header table), etc

typedef uint64_t	Elf64_Addr;
typedef uint16_t	Elf64_Half;
typedef uint64_t	Elf64_Off;
typedef int32_t	Elf64_Sword;
typedef int64_t	Elf64_Sxword;
typedef uint32_t	Elf64_Word;
typedef uint64_t	Elf64_Lword;
typedef uint64_t	Elf64_Xword;

typedef  struct{
	unsigned char 	e_ident[16]; 	/* ELF identification */  
	Elf64_Half 		e_type; 	/* Object file type ET_REL(1)、ET_EXEC(2)、ET_DYN(3)(shared) */
	Elf64_Half 		e_machine; 	/* Machine type EM_386(3)、EM_IA_64(50)*/
	Elf64_Word 	e_version; 	/* Object file version */
	Elf64_Addr 	e_entry; 	/* Entry point address */
	Elf64_Off 		e_phoff; 	/* Program header offset */
	Elf64_Off 		e_shoff; 	/* Section header offset */
	Elf64_Word 	e_flags; 	/* Processor-specific flags */
	Elf64_Half 		e_ehsize; 	/* ELF header size */
	Elf64_Half 		e_phentsize; 	/* Size of program header entry */
	Elf64_Half 		e_phnum; 	/* Number of program header entries */
	Elf64_Half 		e_shentsize; 	/* Size of section header entry */
	Elf64_Half 		e_shnum; 	/* Number of section header entries */
	Elf64_Half 		e_shstrndx; 	/* Section name string table index */
} Elf64_Ehdr;

e_ident[0-3] ‘0x7f’ ‘E’ ‘L’ ‘F’ magic number

e_ident[4] 1(32-bit) / 2(64-bit)

e_ident[5] 1(little) / 2(big)

e_ident[15] size of e_ident[]

typedef struct {
	Elf64_Word    sh_name;	/* Section name (index into the section header string table). */ 
	Elf64_Word    sh_type;	/* Section type. SHT_PROGBITS、SHT_SYMTAB 、SHT_STRTAB、SHT_REL、SHT_NOBITS 
*/
	Elf64_Xword  sh_flags;	/* Section flags. */
	Elf64_Addr	    sh_addr;	/* Address in memory image.(If the section will be copied into the memory to execute, this member gives the address at which the section’s first byte should reside 
) */
	Elf64_Off	    sh_offset;	/* Offset in file. (the byte offset from the beginning of the file to the first byte in the section) */
	Elf64_Xword  sh_size;	/* Size in bytes. */
	Elf64_Word    sh_link;	/* Index of a related section. */
	Elf64_Word    sh_info;	/* Depends on section type. */
	Elf64_Xword  sh_addralign;	/* Alignment in bytes. */
	Elf64_Xword  sh_entsize;	  /* Size of each entry in section. (Some sections hold a table of fixed-size entries, this member gives the size in bytes of each entry)*/ 
} Elf64_Shdr;

ELF String Table

Hold null-terminated character sequences (strings)
The object file uses these strings to represent symbol and section names
One references a string as an index into the string table section

Other Sections

debug section: debugging symbol table, local variables and typedefs, global variables, original C source file (gcc -g)
.line: Mapping between line numbers in the original C source program and machine code instructions in the .text section.

Sections in ELF obj file

.text section: code 代码
.rodata section: Read-only data
.data section: initialized global and static C variables
.bss section (“Block Started by Symbol” or “Better Save Space”)

–uninitialized global and static C variables, along with any global or static variables that are initialized to zero

–has section header but occupies no disk space

–at run time, these variables are allocated in memory with initial value zero

Symbol

Defined global symbols
Referenced global symbols
Local symbols(C functions and global variables with static attribute)

局部非静态变量不是symbol, 不在.symtab段占有空间

Each relocatable object file has a symbol table in .symtab section

Symbol Table包含了：

the module（file） that defines the symbol
the symbol type (local,global,extern)
the section (.text,.data,.bss)

 typedef struct {
 	int 	name ;		/* the name in string table's (byte) offset */
	char 	type:4;	/* function or data (4 bits) (usually，还有一些别的)*/
 	   	binding:4 ;	/* local or global  (4 bits) */
 	char 	reserved ;	/* unused */
 	short 	section ;	/* section header index */
  	long 	value ;		/* section offset(for relocatable), or abs address(for executable) */
 	long	size ;		/* Object size in bytes */
} Elf64_Symbol ;

**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.**Symbol和某个Section绑定，具体方法是Symbol记录对应Section在Section Header Table之中的index

There are three special pseudosections that don’t have entries in the section header table

ABS: symbols that should not be relocated
UNDEF: symbols that are referenced in this object module but defined elsewhere
COMMON: uninitialized data objects

They only exist only in relocatable object files and do not exist in executable object files

For COMMON symbols

value gives the alignment requirement
size gives the minimum size

重要:The difference between COMMON and .bss

COMMON：Uninitialized global variables

.bss：Uninitialized static variables, global or static variables that are initialized to zero

重要！！！！！

重名问题

强符号：初始化的全局变量，函数

弱符号：未初始化的全局

重名：强+强，报错；强+弱，覆盖；弱+弱，任意

静态链接

concatenate related relocatable object files into a single file with an index (called an archive， .a)
enhance linker so that it tries to resolve unresolved external references by looking for the symbols in one or more archives
If an archive member file resolves reference, link into executable

使用静态链接：经典EUD

Scan .o files and .a files in the command line order.

When scan an object file f,

Add f to E

Updates U, D

When scan an archive file f,

Resolve U

If m is used to resolve symbol, m is added to E

Update U, D using m

If any entries in the unresolved list at end of scan, then error

问题：command line order matters!

原则：总是把链接的库放在最后面，并且可以重复

Relocation

For each reference to an object with unknown location

Assembler generates a relocation entry
Relocation entries for code are placed in .rel.text
Relocation entries for data are placed in .rel.data

例如

09      e8 00 00 00 00	callq e<main+0xe> swap();
/* There is a relocation entry in rel.text */

offset   symbol	type			addend
    0a   swap	R_X86_64_PC32   	-4  /* PC32: PC-relative */

.rel.text section

relocation info for .text section
addresses of instructions that will need to be modified in the merged executable object file

.rel.data section

relocation info for .data section
addresses of pointer data that will need to be modified in the merged executable object file

typedef struct {
		long  offset ;
   long  type:32 ,
         symbol:32 ;
   long  addend;
 } Elf64_Rela ;

int *bufp0 = &buf[0] ;
00000000 <bufp0>:
	0: 00 00 00 00 00 00 00 00
/* There is a relocation entry in rel.data */
offset   symbol	type			addend
    0	   buf	R_X86_64_64   	0

addend是重定位条目中的一个数值，它在链接时与符号的地址相加，以确定最终的内存地址。这个参数提供了一种机制，允许编译器生成更灵活和可移植的代码。

Two steps

Relocating sections and symbol definitions
Relocating symbol references within sections

reloc过程的伪代码：

foreach section s {
    foreach relocation entry r {
        refptr = s + r.offset ; /* ptr to reference to be relocated */

        /* relocate a PC-relative reference */
        if (r.type == R_X86_64_PC32) {
            refaddr = ADDR(s) + r.offset ; /* ref’s runtime address */
            *refptr=(unsigned) (ADDR(r.symbol)+r.addend–refaddr) ;
         }

         /* relocate an absolute reference */
         if ( r.type == R_X86_64_64 || r.type == R_X86_64_32||…)
              *refptr = (unsigned) (ADDR(r.symbol) + r.addend) ;
     }
 }

Executable ELF Object

typedef  struct{
	unsigned char 	e_ident[16]; 	/* ELF identification */
	Elf64_Half 		e_type; 	/* Object file type */
	Elf64_Half 		e_machine; 	/* Machine type */
	Elf64_Word 	e_version; 	/* Object file version */
	Elf64_Addr 	e_entry; 	/* Entry point address */
	Elf64_Off 		e_phoff; 	/* Program header offset */
	Elf64_Off 		e_shoff; 	/* Section header offset */
	Elf64_Word 	e_flags; 	/* Processor-specific flags */
	Elf64_Half 		e_ehsize; 	/* ELF header size */
	Elf64_Half 		e_phentsize; 	/* Size of program header entry */
	Elf64_Half 		e_phnum; 	/* Number of program header entries */
	Elf64_Half 		e_shentsize; 	/* Size of section header entry */
	Elf64_Half 		e_shnum; 	/* Number of section header entries */
	Elf64_Half 		e_shstrndx; 	/* Section name string table index */
} Elf64_Ehdr;

typedef struct {
	Elf64_Word    p_type;       /* Entry type.(PT_LOAD (1): loadable segment) */
	Elf64_Word    p_flags;      /* Access permission flags. Run time permissions (rwx)*/
	Elf64_Off        p_offset;    /* File offset of contents. (Offset from the beginning of the file to the first byte in the segment)*/
	Elf64_Addr     p_vaddr;    /* Virtual address in memory image. (The virtual address of the first byte in the segment)*/
	Elf64_Addr     p_paddr;    /* Physical address (not used). */
	Elf64_Xword  p_filesz;     /* Size of contents in file.Segment size in the object file (>=p_memsz)
 */
	Elf64_Xword  p_memsz;	/* Size of contents in memory. */
	Elf64_Xword  p_align;	/* Alignment in memory and file.Usually 4KB or 2MB*/
} Elf64_Phdr;

Difference between filesz and memsz means the uninitialized data in .bss

.init section contains a small function _init called by program’s initialization code

startup code

_start: the entry point of the program. Defined in the crt1.o, Same for all C program, Calls system startup function

__libc_start_main: Defined in libc.so, Initializes the execution environment, Calls the main function, Handles return value, Returns control to OS (if necessary)

Loader

Memory-resident operating system code

Invoked by call the execve function
Copy the code and data in the executable object file from disk into memory
Jump to the entry point
Run the program

Dynamic Link 动态链接

Dynamic Linking
Position Independent Code (PIC)
Loading and Linking Shared Libraries from applications

静态链接缺点：底层库修改需要所有应用重编译，应用体积过大，冗余代码

Shared Libraries

.so(shared obj) on Linux, .dll(dynamic linking lib) on Windows

gcc –shared –fPIC –o libvector.so addvec.c multvec.c
# –shared: creating a shared object
# –fPIC:  creating the position independent code

Partial Linking

在编译时，.so文件没有将.data，.text段等copy，而只是copy了一些relocation and symbol table info

code and data是在memory之中execve() & ld-linux.so链接的

After linking, the locations of the shared libraries are fixed and do not change during the execution time

How to find the ld-linux.so

The pathname of the ld-linux.so is contained in the .interp segment of p2

上面那张图，memory-mapped region for shared libs

运行时Linking

Done explicitly by user with dlopen() in Linux

gcc –rdynamic –O2 –o p3 dll.c -ldl

API：

 #include <dlfcn.h>
 void *dlopen(const char *filename, int flag);
			// returns: ptr to handle if OK, NULL on error
 void *dlsym(void *handle, char *symbol) ;
			// returns: ptr to symbol if OK, NULL on error
 int  dlclose(void *handle) ;
			// returns: 0 if OK, -1 on error
 const char dlerror(void) ;
			/* returns: errormsg if previous call to
 			dlopen, dlysym, or dlclose failed,
 			NULL if previous call was OK */

运行时Linking示例程序

 #include <stdio.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 ;
 }

用处：

分发系统更新，更新dll重新运行时自动加载
高性能web server, 对不同的库动态加载卸载，使用缓存来保证函数级别的最小内存占用，也是支持热更新的来源

PIC：位置无关代码

naive: 划分一块区域专门放

actual: 让代码都是PC-relative，从而可以被任意地址加载

文件内部函数，变量：简单，直接变成PC-relative
文件外部引用，全局变量：间接跳转，以一个Private的.data段开头的GOT(全局偏移量表)作为跳板

调用外部全局变量的解决方案：

保证.data段和.text段在加载的时候不分开，一起加载
利用1，.data段和.text段现在的距离和加载到的地方没有关系了，在.data段开头的GOT里面记录各个全局的data的offset，然后在.text段记录GOT的entry_index, 访问时 .text -> .data -> GOT[idx] -> global data

GOT 012预留给dynamic linker

调用外部函数的解决方案：PLT（Procedure Linkage Table）

在.text段前面加一段plt段，留下外部函数的地址的标记，对地址暂时留空
把.text段内部的代码之中所有外部函数的地址该外plt段之中标记的地址（相对地址）
当运行时.text->plt-> 如果没有，再加载实际地址到标记留空的地方，之后再次访问不需要实际地址，只需要把plt当跳板就行

PLT：16-byte entry array

PLT[0] 为dynamic linker预留

第一次调用addvec

jmpq *GOT[4]发现没有，回来(*GOT[4]存0x4005c6下一条指令的relative，jmp相当于没jmp)，pushq $0x1 把addvec的entry ID作为栈上的参数给dynamic linker, 然后jmpq 到PLT[0]，PLT[0]压栈*GOT[1]参数后，跳转到dynamic linker，dynamic linker根据*GOT[1]和ID找到对应函数，同时更新GOT[4]，填上地址

后面调用addvec都是直接jmpq到*GOT[4],实际上是函数调用

库打桩

构造“二传手”函数, 截获转发一些已经写好的库函数，例如malloc，可以用于日志，统计等等

编译时打桩：核心在于定义一个自己的同名函数，在自己的函数去调用库函数，例如利用宏定义malloc为mymalloc，再在mymalloc里面去调用系统的malloc

运行时打桩：比较复杂，不太重要

重定向深入

深入理解相对重定向 - Anatas Luo's Blog

总结： 1. 流水线的设计，使得IP寄存器总是指向下一条指令，计算offset时，需要考虑当前指令的长度 2. 相对偏移如果确定（通常是static data），则以section为基址进行重定向，可以减少符号表大小， Addend = symbol_offset - relocation_len 3. 相对偏移如果不确定，则以symbol为基址进行重定向，Addend = - relocation_len

需要重定向的代码在汇编上以0x0(%rip)给出，%rip是PC，0x0则意味着待填充

No linker Problems​

What is linker​

Static Linking​

Relocatable object file​

Sections​

External reference​

Object files​

Executable and Linkable Format (ELF)​

ELF Header​

ELF String Table​

Other Sections​

Sections in ELF obj file​

Symbol​

重要！！！！！​

重名问题​

静态链接​

Relocation​

Executable ELF Object​

Loader​

Dynamic Link 动态链接​

运行时Linking​

PIC：位置无关代码​

库打桩​

重定向深入​