Ｃ开发笔记

GCC
- Built-in函数
  - Atomic Memory Access
- 实例
C库头文件备忘录
链接、装载与库
黑科技
语法
- 类型提升
- 整形溢出

这篇文章用来记录开发过程中实际需要牢固掌握的基础知识。只有在牢固的基础上才能写出高质量的代码.

GCC

Built-in函数

Atomic Memory Access

在c++11标准之前，CAS的build-in函数都是__sync开头的，新标准之后改成了__atomic开头， __atomic系列build-in函数主要实现了c++11标准中的memory model，具体参见这里

legacy的版本函数原型如下:

	type __sync_fetch_and_add (type *ptr, type value, ...)
	type __sync_fetch_and_sub (type *ptr, type value, ...)
	type __sync_fetch_and_or (type *ptr, type value, ...)
	type __sync_fetch_and_and (type *ptr, type value, ...)
	type __sync_fetch_and_xor (type *ptr, type value, ...)
	type __sync_fetch_and_nand (type *ptr, type value, ...)


	type __sync_add_and_fetch (type *ptr, type value, ...)
	type __sync_sub_and_fetch (type *ptr, type value, ...)
	type __sync_or_and_fetch (type *ptr, type value, ...)
	type __sync_and_and_fetch (type *ptr, type value, ...)
	type __sync_xor_and_fetch (type *ptr, type value, ...)
	type __sync_nand_and_fetch (type *ptr, type value, ...)


	bool __sync_bool_compare_and_swap (type *ptr, type oldval type newval, ...)
	type __sync_val_compare_and_swap (type *ptr, type oldval type newval, ...)

	__sync_synchronize (...)


	type __sync_lock_test_and_set (type *ptr, type value, ...)

	void __sync_lock_release (type *ptr, ...)

支持C++11memory model的版本如下:

	Built-in Function: type __atomic_add_fetch (type *ptr, type val, int memorder)
	Built-in Function: type __atomic_sub_fetch (type *ptr, type val, int memorder)
	Built-in Function: type __atomic_and_fetch (type *ptr, type val, int memorder)
	Built-in Function: type __atomic_xor_fetch (type *ptr, type val, int memorder)
	Built-in Function: type __atomic_or_fetch (type *ptr, type val, int memorder)
	Built-in Function: type __atomic_nand_fetch (type *ptr, type val, int memorder)


	Built-in Function: type __atomic_fetch_add (type *ptr, type val, int memorder)
	Built-in Function: type __atomic_fetch_sub (type *ptr, type val, int memorder)
	Built-in Function: type __atomic_fetch_and (type *ptr, type val, int memorder)
	Built-in Function: type __atomic_fetch_xor (type *ptr, type val, int memorder)
	Built-in Function: type __atomic_fetch_or (type *ptr, type val, int memorder)
	Built-in Function: type __atomic_fetch_nand (type *ptr, type val, int memorder)


	Built-in Function: bool __atomic_compare_exchange_n (type *ptr, type *expected, type desired, bool weak, int success_memorder, int failure_memorder)



	Built-in Function: bool __atomic_test_and_set (void *ptr, int memorder)

	Built-in Function: void __atomic_clear (bool *ptr, int memorder)

	Built-in Function: void __atomic_thread_fence (int memorder)

	Built-in Function: void __atomic_signal_fence (int memorder)

	Built-in Function: bool __atomic_always_lock_free (size_t size, void *ptr)

	Built-in Function: bool __atomic_is_lock_free (size_t size, void *ptr)

其中6中memory order宏定义为:

	__ATOMIC_RELAXED,
	__ATOMIC_CONSUME,
	__ATOMIC_ACQUIRE,
	__ATOMIC_RELEASE,
	__ATOMIC_ACQ_REL,
	__ATOMIC_SEQ_CST,

需要注意的是，并不是上面所有函数都已经在build-in中实现，有些操作是依赖于标准库中去实现的，另外，有效架构平台可能并么有提供memory order的支持，所以，建议就是，我们尽量使用__atomic系列函数，然后让编译器帮助我们自动fallback到__sync系列。

实例

假设我们的一个模块初始化API函数在进程中只想被调用一次，很常见的做法就是定义一个inited的变量，初始化前检测变量是否已经设置，由于会涉及到多线程的问题，使用atomic函数处理比使用锁优雅方便很多。

	int inited = 0;

	int module_init(){

		int expected = 0;

		if(!atomic_val_compare_exchange_8(&inited, &expected, 1)){
        	return 0;
    	}

	}


	bool atomic_val_compare_exchange_8(int8_t volatile* ptr, int8_t oldval, int8_t newval)
	{
		return  __atomic_compare_exchange_n(ptr, &oldval, newval, false,
										__ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST);

	}

C库头文件备忘录

<limits.h>头文件中包含CHAR_BIT、LONG_MAX这样的关于整形数的宏定义。

链接、装载与库

ELF可执行文件

Windows下的PE(Portable Executale)和Linux下的ELF(Executable Linkable Format)都是COFF(Common file format)格式的变种。和可执行文件接近的是目标文件，它是源代码编译后未进行链接的那些中间文件(Linux下的.o),它和可执行文件格式几乎是一样的。同时，动态链接库和静态链接库文件也都是按照ELF格式进行存储的。

粗略的来看，ELF文件就是由文件头加各种段构成的。其中我们比较熟悉的段有.text段用来存放指令;.data段用来存放全局变量和局部静态变量数据;另外一个比较特殊且容易和进程中的段内存分布混淆的段.bass段，是用来存放全局为初始化变量和局部静态变量。因为为初始化的全局变量和局部静态变量默认值都为0，本来它们也可以直接放在.data段的，但是因为它们都是0，所以为了减小ELF文件的大小，.bass段只是为为初始化全局变量和局部静态变量预留位置而已，它并没有内容，所以在文件中不占据空间。但是要清楚，最终程序运行时肯定是要给.bass段分配实际内存空间的。

int printf(const char *format, ...);

int global_init_var = 64;
int global_uninit_var;

void func(int i)
{
	printf("%d\n0", i);
}

int main()
{
	static int static_init_var = 85;
	static int static_uninit_var;

	int a = 1;
	int b;

	func(static_init_var + static_uninit_var + a + b);
	
	return 0;
}

编译上面代码得到simpleSection.o目标文件，然后执行obidump -h simpleSection.o得到如下:

section

从上面的结果来看，simpleSection.o的段比我们想象中的要多，除了最基本的代码段、数据段和.bss段外，还有４个段是只读数据段(.rodata)、注释信息段(.comment)、堆栈提示段(.note.GNU-stack)和xx段(.eh_frame)。这个几个特殊的段先不去研究，先看看几个重要的段的属性。其中size和File off属性分别是段的大小和段在文件中的偏移字节数；第2行中的CONTENTS表示该段在文件中存在，所以我们看BSS段没有CONTENTS属性。各个段在ELF文件中的结构如下图(图中的段偏移量有出入):

sim_pic

ELF文件结构描述

elf_jg

如上图所示，ELF目标文件格式的最前部是ELF文件头，它包含了描述整个文件的基本属性，比如ELF文件版本、目标机器型号、程序入口地址等。紧接着的是各个段以及与段有关的重要结构–段表，该表描述了ELF文件中包含的所有信息，比如每个段的段名、段的长度、在文件中的偏读写权限以及段的其他属性。最后是一些ELF中的辅助结构，比如字符串表、符号表等。

可以使用readelf命令来详细查看ELF文件:

readelf

ELF文件头结构及相关常数定义在/usr/include/elf.h里:

elf_head

从前面readelf输出来看，最前面的Magic的16个字节刚好对应上面结构体中的e_ident这个成员。这16个字节被用来规定表示ELF文件的平台属性，比如字长(32/64位)、字节序、ELF文件版本。

最开始的4个字节是所有ELF文件都必须相同的标识码，分别为0x7f,0x45,0x4c,0x46，第一个字节对应ASCII字符里的DEL控制符，后面3个刚好是E/L/F这3个字母的ASCII码。者4个字节又被称为是ELF文件的魔数。这种魔数用来确认文件的类型，操作系统在加载可执行文件时会确认魔数是否正确，如果不正确会拒绝加载。第5个字节用来标示字长的，0x01代表32位，0x02代表64位。第6个字节代表字节序，也就是大小端，第7个字节规定ELF文件的主版本号，一般是1,因为ELF标准自1.2版本之后就再也没有更新了。后面的9个字节为保留位。

弱符号与强符号

理解编译器中的弱符号和强符号的定义，对于我们编写多模块代码来说是必须要掌握的。举个项目中实际的例子，我司某个项目中途需要支持自动化测试，实现方式是添加一个我们新开发的测试数据收集分析和转发的模块，这个模块在最终发布程序是肯定是不会链接进工程中的。现在出现一个问题，这个测试模块中定义了一个全局变量如g_print_level = 16，主模块需要使用这个变量，但是又不想将这个变量定义在头文件中，这时，如果在主模块中使用extern　int g_print_level;的话，那么当编译不含测试代码模块的话，就会出现变量为定义的错误。这时最简单的解决办法是什么？就是取得extern修饰符，直接定义int g_print_level;原因下面分析。

编译器默认所有函数和初始化了的全局变量为强符号，未初始化的全局变量为弱符号。当然，我们可以通过GCC的__attribute__(weak)来定义任何一个强符号为弱符号。另外，特别注意，强符号和弱符号都是针对定义来说的，不是针对符号的引用，不能和强引用弱引用混淆。

链接器按照如下规则处理与选择被多次定义的全局符号:

规则1:不允许强符号被多次定义，如果多次定义链接器就会报符号重复定义错误。
规则2:如果一个符号在某个目标文件中是强符号，而在另外一个目标文件中都是弱符号，那么选择强符号。
规则3:如果一个符号在所有目标文件中都是弱符号，那么选择其中占用空间最大的一个。

通过规则2，我们就可以理解上面的解决方法是正确可行的。

弱引用和强引用

一般情况下，在目标文件最终进行链接时，如果存在对外部目标文件的符号引用没有被正确决议，也就是没有找到该符号的定义，那么链接器就会报符号未定义错误，这种就是强引用(Strong Reference)。与之对应的就是弱引用(Weak Reference),在处理弱引用时，如果该符号为被定义，链接器对于该引用不报错，而是默认将其初始化为0，或者是一个特殊的值，以便于程序代码能够识别。

在GCC中，我们可以通过使用"__attribute__((weakref)"这个扩展关键字来声明对一个外部函数的引用为弱引用，比如下面的代码:

__attribute__((weakref)) void foo();

int main()
{
	foo();
}

我们编译通过上面的代码，但是显然运行时会发生错误，所以正确的使用方法如下:

__attribute__((weakref)) void foo();

int main()
{

	if(foo)	foo();
}

BFD库

由于现代的硬件和软件平台种类非常繁多，每个平台都有它独特的目标文件格式，即使像ELF这样的同一个格式在不同软硬件平台上都有着不同的变种。种种差异导致编译器和链接器很难处理不同平台之间的目标文件，特别是对于像GCC和binutils这种跨平台的工具来说，最后有一种统一的接口来处理这些不同格式之间的差异。

Any problem in computer science can be solved by another layer of indirection－－计算机科学领域的任何问题都可以通过增加一个中间层来解决。

BFD库就是这样一个another layer，它是一个GNU项目，目的就是希望通过一种统一的接口来处理不同的目标文件格式。BFD把目标文件抽象成一个统一的模型，充当一个中间层，使得程序只要通过操作这个抽象的目标文件模型就可以实现操作所有BFD支持的目标文件格式。

现在GCC、链接器ld、调试器GDB及binutils的其他工具都通过BFD库来处理目标文件，而不是直接操作目标文件。

特殊符号

当我们使用ld作为链接器来链接产生可执行文件时，它会为我们定义很多特殊的符号，这些特殊符号并没有在你的程序中定义，但是你可以直接使用extern进行声明然后使用，我们称之为特殊符号。

这些符号是被定义在ld链接器的链接脚本中的，链接器会在将程序最终链接成可执行文件的时候将其解析成正确的值，几个具有代表性的特殊符号如下:

__executable_start, 该符号为程序起始地址，注意，不是入口地址，是程序的最开始的地址。
__etext,该符号为代码段结束地址，即代码段最末尾的地址。
_edata,该符号数据段结束地址。
_end, 该符号为程序结束地址。

以上说的地址都为程序被装载时的虚拟地址。测试代码如下:

#include "stdio.h"

extern char __executable_start[];
extern char __etext[];
extern char _edata[];
extern char _end[];


int main()
{
	int i = 0xa5;

	printf("Stack Start %p\n", &i);
	printf("Executable Start %p\n", __executable_start);
	printf("Text End %p\n", __etext);
	printf("Data End %p\n", _edata);
	printf("Executable End %p\n", _end);

	return 0;
}

运行结果如下:

special

静态链接

静态链接主要涉及到如何组织多个目标文件到一个可执行文件，例如下面的两个文件:

/* a.c */
extern int shared;

int main()
{
	int a = 100;
	
	swap(&a, &shared);

	return 0;
}

/* b.c */
int shared = 1;

void swap(int *a, int *b)
{
	*a ^= *b ^= *a ^= *b;
}

执行gcc -c a.c b.c将其分别编译成a.o和b.o，接下来就是看看把这两个目标文件在链接时是怎样将各个目标文件中的段进行合并最终生成可执行文件的。

可以想到的简单的方法就是将各个目标文件中的段按照一定次序叠加起来，但是显然这样会造成最终输出的可执行文件有太多的零散的段。所以现在的链接器会采用将相似段进行合并的方法，使用这种方法一般采用两步链接(Two-pass Linking)的策略。也就是说整个链接过程分成两步:

第一步　空间与地址分配　

扫描所有的输入目标文件，获得它们的各个段的长度、属性和位置，并且将输入目标文件中的所有符号定义和符号引用收集起来，统一放到一个全局符号表。同时，链接器进行目标文件中断点合并。

第二步　符号解析与重定位

使用上一步中收集到的所有信息，读取输入文件中段的数据、重定位信息，并且进行符号解析与重定位、调整代码中的地址等。

下面借助编译链接上面的a.c和b.c来具体阐述静态链接的过程和细节。

使用ld链接器将上面得到的a.o 和 b.o链接起来:

$ld a.o b.o -lc -e main -o ab

-e main 表示将main函数作为程序入口，ld链接器默认的程序入口为_start。
-lc 是为了解决ld报__stack_chk_fail未定义的错误。

让我们来查看链接前后地址的分配情况：

aaa

bbb

abab

上面的VMA列表示virtial Memory Address，即虚拟地址，LMA列表示Load Memory Address，即加载地址，正常情况下这两个值应该是一样的，但是在有些嵌入式系统中，特别在那些程序放在ROM的系统中时，LMA和VMA是不同的。

可以看到，在链接之前，目标文件中的所有段的VMA都是0,因为虚拟空间还没有分配，等到链接后，可执行文件ab中的各个段都被分配了相应的虚拟地址。a.o中的.text段大小0x51加上b.o中的.text段大小0x4b正好等于ab中.text的大小0x9c，说明它们确实是被合并了。

重定位

当前面的合并工作完成后，链接去开始计算各个符号的虚拟地址。因为各个符号在段内的相对位置是固定的，所以这时其实main、shared、swap的相对虚拟地址已经确定了，只不过链接器需要给每个符号加上一个偏移量，使它们能够调整到正确的虚拟地址。比如假设a.o中的main函数相对于a.o的.text段的偏移是x,但是经过链接合并后，a.o的.text段位于虚拟地址0x4002b0，那么main的地址应该是0x4002b0 + x。

下面结合a.o、b.o以及ab的反汇编结果进行分析静态链接的过程，先执行objdump -d a.o查看:

a_d

程序的代码里面使用的都是虚拟地址，在这里也可以看到main的起始地址为0x0000000000000000,这是因为在未进行前面提到的链接器空间分配之前，目标文件代码段中的起始地址以0x0开始，等空间分配完成之后，各个函数才会确定自己在虚拟地址空间中的位置。

其中lea 0x0(%rip), %rsi # 29 <main+0x29>就是将”shared”变量值放到rsi寄存器中作为第二个入参。那么”shared”变量就是通过0x0(%rip)来寻址的，在动态链接部分我们已经知道，rip寄存器保存的就是当前指令的下一条指令地址，所以0x0(%rip)原本的意图就是通过相对当前指令偏移的寻址方式来寻址，当由于源代码”a.c”在被编译成目标文件时，编译器还不知道”shared”的地址偏移量，所以编译器暂时把将”shared”的地址偏移设置为0,把真正的地址计算工作留个链接器。

通过前面的空间与地址分配可以得知，链接器在完成地址和空间分配之后就可以确定所有符号的虚拟地址了，那么链接器可以根据符号的地址对每个需要定位的指令进行地址修正，也就是重定位。下面我们来看一下输出程序”ab”的代码段中经过修正后的结果:

ab_shared

上图中清楚的看到，修正后的”shared”地址偏移为0x200d47, 那么”shared”真正地址为0x200d47 + 0x4002d9 = 0x601020。

下面我们将研究链接器是怎么知道哪些指令是要被调整的，另外，注意一下，上面ab的汇编代码一开始的两条关于__stack_chk_fail函数的指令。

重定位表

上面我们只是分析了重定位前后的结果，这节来探讨一下链接器是怎么进行重定位工作的，它是任何知道哪些指令是需要被调整的。事实上，在ELF文件中有一个叫重定位表(Relocation Table)的结构专门用来保存这些与重定位相关的信息。

ELF文件中可能存在多个需要被重定位的段，那么每个需要被重定位的段必须对应存在一个重定位表，比如代码段.text如果有需要重定位的地方，那么会有一个叫.rel.text的重定位段保存了代码段的重定位表。我们可以用objump来查看目标文件的重定位表:

rel_a

每个要被重定位的地方叫做一个重定位入口(Relocation Enrty),输出结果的第一列的OFFSET项就表示该入口在要被重定位的段中的位置，输出结果的第二行RELOCATION RECORDS FOR [.text]表示这个重定位表是对应.text段的，所以我们对照前面a.o的代码段可以看到，0x00000000000025这个OFFSET值就是对应a.o代码段段中的第0x25条指令，也就是shared变量的临时地址指令位置。

对于32位的x86系列处理器来说，重定位表的数据结构很简单，它就是一个Elf32_Rel结构的数组，每个数组元素对应一个重定位入口。

typedef struct{
	Elf32_Addr r_offset;
	Elf32_Word r_info;		
}Elf32_Rel;

其中，r_info表示入口的类型和符号，它的底8位表示入口的类型，高24位表示入口符号在符号表中的下标。

另外，奇怪的是，执行objdump -h a.o的结果中并没有.rel.text这一项，但是执行readelf -S a.o可以看到这个重定位段。

重定位表中的TYPE表示的是，ELF文件的重定位入口所修正的指令寻址方式,x86 32位只有两种:

绝对近址32位寻址。
相对近址32位寻址。

x86基本重定位类型

宏定义	值	重定位修正方法
R_386_32	1	绝对寻址修正　S+A
R_386_PC32	2	相对寻址修正　S+A+P

A = 保存在被修正位置的值 P = 被修正的位置(相对于段开始的偏移量或者虚拟地址) S = 符号的实际地址，即由r_info的高24位指定的符号的实际地址

从我们的实际输出结果看出，x86 64位存在R_X86_64_PC32和R_X86_64_PLT32至少这两种新的类型。其工作原理应该和32位下的类似。

COMMON块

现代的编译器和链接器都支持一种叫COMMMON块(Common Block)的机制。前面我们在SimpleSection.c这个例子中已经看到，编译器将未初始化的全局变量定义作为弱符号处理。比如其中的gloabl_unint_var,它在符号表中的各个值为:(使用readelf -s simpleSection.o)

common

从第12行可以看出，它是一个全局的数据对象，它的Ndx为COM，它占4个字节大小，这是一个典型的弱符号。那么如果我们在来另外一个文件中也定义了gloabl_uinit_var变量，且是未初始化的double类型，那情况会怎么样呢？按照COMMON类型的链接规则，原则上讲，gloabl_uinit_var的大小以输入文件中最大的那个为准。

GCC的“-fno-common”也允许我们把所有未初始化的全局变量不以COMMON块的形式处理，或者使用”attribute“扩展:

int global __attribute((nocommom))__

一旦一个未初始化的全局变量不是以COMMON块的形式存在，那么它就相当于上升为一个强符号。

动态链接

动态链接技术的实现主要涉及装载时重定位和地址无关代码两种手段。装载时重定位技术和链接时重定位技术很类似，后者是使用在静态库的链接时。地址无关代码的实现比较复杂，也是重点需要研究的。

装载时重定位

为了实现动态链接，我们首先要解决的是共享对象地址的冲突问题，如果不同的模块目标装载地址都一样肯定是不行的，所以早期的时候，通过一种叫做静态共享库(static shared library)的方式，就是手动的指定各个模块的地址，比如将0x1000到0x2000分配给模块A,将0x2000到0x3000分配给模块B。显然这种方式有很多问题，如果某个模块被多个程序使用，或者是多个模块被多个程序使用，那么管理这些模块的地址将是一件无比繁琐的事情。另外，静态链接库的升级也很成问题，因为升级后的共享库必须保持共享库中全局函数和变量地址的不变，如果应用程序中在链接时已经绑定了这些地址，一旦更改，就必须重新链接应用程序。

为了解决这个模块装载地址固定的问题，我们设想是否可以让共享对象在任意地址加载?这个问题另一种表述方式是:共享对象在编译时不能假设自己在进程虚拟地址空间中的位置。与此不同的是，可执行文件基本可以确定自己在进程虚拟地址空间的起始位置，因为可执行文件往往是第一个被加载的文件，它可以选择一个固定空闲的地址，比如Linux下一般都是0x08040000,Windows下一般都是0x00400000

为了能够使共享对象在任意地址装载，我们首先会想到可以参照静态链接中的地址重定位方法。基本思路就是，在链接时，对所有绝对地址的引用不作重定位，而把这一步推迟到装载时再完成。假设某个函数func相对于代码段的起始地址的偏移是0x100，当模块装载到0x10000000时，我们假设代码段位于模块的最开始，即代码段的装载地址也是0x1000000，那么我们就可以确定func的地址为0x10001000。这时候，系统遍历模块中的重定位表，把所有func的地址引用都重定位到0x10001000。

但是装载时重定位的方法没有完全解决动态链接中的所有问题，可以想象，动态链接模块被映射至虚拟空间后，指令部分是在多个进程之间共享的，由于装载时重定位的方法需要修改指令，所以没有办法做到同一份指令被多个进程共享，因为不同进行需要进行的重定位肯定是不一致的。这样动态链接库就失去了节省内存的最初目标，但是装载时重定位的共享对象的运行速度要比后面要介绍的使用地址无关代码的共享对象快，因为它省去了地址无关代码中每次访问全局数据和函数时需要做的一次计算当前地址以及间接地址寻址的过程。

编译动态链接库时，如果只是添加-shared参数而不加-fPIC参数的话，那么输出的共享对象就是使用装载时重定位的方法。

地址无关代码

地址无关代码(PIC,Position-independent Code)技术的基本思想就是，将需要在装载时动态计算修改的共享指令(全局变量、API函数)部分分离出来，和数据部分放在一起，这样指令部分就可以保持不变，而数据部分可以在每个进程中拥有一个副本。

程序中共享对象的地址引用按照是否为夸模块分成两类，模块内的引用和模块间的引用；按照不同的引用方式又可以分为指令引用和数据访问。这样就可以将程序中的共享对象地址引用分成4类：

第一种是模块内部的函数调用、跳转等。
第二种是模块内部数据的访问，比如模块中定义的全局变量、静态变量。
第三种是模块外部的函数调用、跳转等。
第四种是模块外部的数据访问，比如其他模块中定义的全局变量。

实例代码如下:

static int a;
extern int b;
extern void  func();

void bar()
{
	a = 1;
	b = 2;
}

void foo()
{
	bar();
	func();
}

显然，变量a就是第二种类型；变量b是第四种类型;函数func()的调用是第三种类型;函数bar()的调用是第一种类型。

注:当编译器在编译上面代码时，它实际上不能确定变量b和函数func()是模块外部还是内部的，因为它们有可能被定义在一个共享对象的其他目标文件中。由于无法确定，编译器只能把它们都当作模块外部的函数和变量来处理。

执行gcc -shared -fPIC -o lib.so simpleSection.c编译上面代码得到lib.so，然后执行objdump -d lib.so查看汇编代码，结合汇编代码来阐述上面四种情况。

类型一　模块内部调用或跳转

上面这四种情况中，第一种类型应该是最简单的，因为被调用的函数与调用者处于同一个模块，它们之间的相对位置是固定的，所以这种情况比较简单。对于现代的系统来讲，模块内部的跳转、函数调用都可以是相对地址调用或者是基于寄存器的相对调用，所以对于这种指令是不需要重定位的。比如上面例子中foo对bar的调用代码如下:

dis_coed

上面指令前两条很简单，就是函数调用通用流程，保存上次的帧指针(Frame Pointer)然后更新当前的帧指针为当前的栈顶指针。第3条就是foo对bar的调用指令，其实是一条相对地址调用指令，第一个字节码e8是相对地址调用指令callq的指令码，后面的a9 fe ff ff是目的地址相对于下一条指令的偏移。由于我的笔记本处理器是小端模式，所以这个偏移实际是0xfffffea9,它是-0x157的补码，下一条指令地址是0x717,所以bar的地址是0x717 - 0x157 = 0x5c0，那么只要bar和foo的相对位置不变，这条指令就是地址无关的,即无论模块被装载到哪个位置，这条指令都是有效的。这种相对地址的方式对于jmp指令也是有效的。

注:这里存在2个问题，一个是上面的0x5c0其实是bar@plt地址，至于这个地址的具体含义在下面章节中会说明。第二个问题是，上面的方式存在一个叫做共享对象全局符号介入(Global Symbol Interposition)的问题，这个也会在后面章节说明。

类型二　模块内部数据访问

因为指令中不能直接包含数据的绝对地址，所以唯一的办法就是相对寻址。我们知道，一个模块前面一般是若干页的代码，后面紧跟着若干页的数据，这些页之间的相对位置是固定的，也就是说，任何一条指令与它需要访问的模块内部数据之间的相对位置是固定的，那么只需要相对于当前指令加上固定的偏移量就可以访问模块内部数据了。在32位cpu时代，还没有相对当前指令地址的寻址方式，所以 ELF需要使用巧妙的方法来得到当前的PC值，然后再加上一个偏移量来达到访问相应变量的目的。在现在的64位cpu时代，已经支持这种新的寻址方式了: RIP-relative addressing, RIP相对寻址。

Intel对RIP有个简单的解释:

The 64-bit instruction pointer RIP points to the next instruction to be executed,and supports a 64-bit flat memory model.

Inter还谈到了RIP相对寻址的用途:

RIP-relative addressing: this is new for x86 and allows accessing data tables and such in the code relative to the current instruct pointer, making position independent code easier to implement.

下图就是我的64位笔记本下的反汇编代码。

bar_a

上图中可见，movl $0x1, 0x200936(%rip)这条指令通过rip寄存器获取下一条指令地址也就是0x6fe,然后加上0x200936这个偏移量，0x200936+0x6ef = 0x201034，正好和指令后面的注释# 201034 <a>吻合。

另外，我们执行objdump -h lib.so可以看到，.bss的地址是0x201030, 说明变量a(0x201034)正是存在.bass段内的。

bass

类型三　模块间数据访问

模块间的数据访问要比模块内稍微复杂一点，因为模块间的数据访问目标地址要等到装载时才决定。地址无关代码的基本思想就是把跟地址相关的部分放到数据段里面，很明显，像上面变量b这样定义其他模块的全局变量的地址是跟模块装载地址有关的。ELF的做法是在数据段里面建立一个指向这些变量的指针数组，也被称为全局偏移表(Global Offset Table, GOT).当代码需要引用全局变量时，可以通过GOT中相对应的项间接引用。

当指令要访问变量b时，程序会先找到GOT,然后根据GOT中变量所对应的项找到变量的目标地址。64位下，每个变量对应一个8字节的地址，链接器在装载模块时会查找每个变量所在的地址，然后填充GOT中的各个项，以确保每个指针指向正确的地址。由于GOT本身是放在数据段的，所以它可以在模块装载时被修改，并且每个进程都可以有对立的副本，互相不受影响。

从第二种类型我们可以想到，我们可以像寻址变量a一样先寻址到GOT,然后根据变量地址在GOT中的偏移就可以得到变量的地址。我们根据上面的bar函数的反汇编进行具体分析验证。

mov 0x2008d3(%rip), %rax，其中0x705 + 0x2008d3 = 0x200fd8，得到的直接就是是GOT中变量b的存放地址项的地址。我们继续通过段表来验证一下:

got

上图可见，0x200fd8确实就在.got段内。另外，我们可以执行objdump -R lib.so来看看lib.so需要在动态链接时的重定位项:

obi_r

中间R_X86_64_GLOB_DAT b这项前的地址符合我们的分析结果。

类型四　模块间调用、跳转

理解了类型三之后，对于类型四就比较简单了。但是多出了一个延时绑定(PLT)的机制。在动态链接下，程序模块之间包含了大量的函数引用(全局变量往往较少，因为大量的全局变量会导致模块间耦合度变大)，所以在程序开始执行前，动态链接会消耗不少时间用于模块间的函数引用的符合查找和重定位。不过可以想象，在一个程序运行过程中，可能很多函数在程序执行过程中始终都不会用到，如果一开始就把所有函数都链接好实际上是一种浪费。所以ELF采用了一种叫做延时绑定(Lazy Binding)的做法，基本思想就是当函数第一次被调用时才进行绑定。

如何实现延时绑定呢？还是那句话,计算机科学领域的任何问题都可以通过增加一个间接的中间层来解决,所以解决办法就是在GOT技术之上再增加一层间接跳转。调用函数并不直接通过GOT跳转，而是通过一个叫作PLT项的结构进行跳转。记得我们在介绍第一种类型时留下的伏笔，出现<bar@plt>这样的符号。这就是lib.so中bar()函数在PLT中的项地址符号。这个地址是.plt段中的一项，具体的段内容如下图:

plt

为了便于理解，我们先不直接分析上面的汇编代码，而是使用伪代码来分析理解。bar@plt项的伪代码实现如下:

bar@plt:
jmp *(bar@GOT)
push n
push moduleID
jump _dl_runtime_resolve

bar@plt项中的第一条指令，即jmp *(bar@GOT),是一条通过GOT间接跳转的指令。其中bar@GOT表示的是GOT中保存bar()这个函数相应的项。如果链接器在初始化阶段已经把bar()函数的正确地址填入该项，那么这个跳转指令就直接完成跳转到bar()函数，也就不是所谓的PLT了，所以为了实现延时绑定，链接器肯定不会在初始化阶段填入bar()的地址，而是填入下面一条指令的地址，即将push n这条指令的地址填入了bar@GOT中。这样当我们执行类型一中描述的指令callq 5c0 <bar@plt>后就会执行到push n这个指令，然后继续往下执行另外２条指令。第二条指令将一个数字n压人堆栈中，这个数字是bar这个符号引用在重定位表”.rela.plt”中的下表。接着是一条将模块的ID压人堆栈的命令。最后跳转都_dl_runtime_resolve()函数。这个函数就是根据上面传入的两个参数然后完成符号解析和重定位工作，并且最后会把bar()正确的地址填入到bar@GOT中，这样下次调用bar@plt项时可以直接正确跳转到bar()函数了。

上面我们通过伪代码描述了PLT的基本原理，PLT真正的实现要比上面的伪代码复杂一些。ELF将GOT拆分成两个表分别叫”.got”和”.got.plt”。其中”.got”用来保存全局变量引用的地址，”.got.plt”用来保存函数引用的地址。另外，”.got.plt”还有一个特殊的地方是它前三项是有特殊意义的，分别含义如下:

第一项保存的是”.dynamic”段的地址。
第二项保存的是本模块的ID。
第三项保存的是_dl_runtime_resolve的地址。

其中第二项和第三项由动态链接器在装载共享模块的时候负责将它们初始化。为了减少代码量，ELF将上面伪代码指令中的最后两条指令放到了PLT中的第一项。实际的PLT基本结构如下图:

got

实际的PLT基本伪代码架构如下:

PLT0:
push *(GOT + 8)
jump *(GOT + 16)

...

bar@plt:
jmp *(bar@got)
push n
jump PLT0

下面我们回过头来分析开始的汇编代码。首先指令jmpq *0x200a52(%rip)，通过后面的注释可以快速知道，是跳转到 GOT表偏移0x18的位置上的地址，根据之前的段表可以验证0x201018确实就是”.got.plt“段内的地址，可以猜想，第一次跳转的结果应该是跳转到下面pushq $0x0这条指令，然后继续依次执行到pushq 0x2000a52(%rip)这条指令，这条指令和我们上面分析的结论吻合,就是伪代码中的push *(GOT+8)这行。这行指令的作用就是将lib.so的module id压人堆栈。最后就是跳转到_dl_runtime_reslove()函数，这个函数地址就在”.got.plt”表偏移16个字节处。

至此，所有四种类型的地址无关代码的技术实现细节已经分析完毕了。

动态链接相关结构

动态链接情况下，可执行文件的装载与静态链接情况基本一样。首先操作系统会读取可执行文件的头部，检查文件的合法性，然后从头部中的”Program Header”中读取每个”Segment”的虚拟地址，文件地址和属性，并将它们映射到进程虚拟地址空间的相应位置，不同与静态链接情况的是，操作系统接着不会立即将控制权交给可执行文件，而是会先启动一个动态链接器(Dynamic Linker)。

在Linux下，动态链接器ld.so实际上是一个共享对象，操作系统同样通过映射的方式将它加载到进程的地址空间中。那么系统中哪个才是动态链接器呢，它的位置由谁决定？是不是所有的unix系统的动态链接器都位于/lib/ld.so呢？

“.interp”段

动态链接器的位置是由ELF文件决定的，在动态链接的可执行文件中，有一个专门的段叫做.interp段(“interp”是”interpreter”的缩写)。下面是执行通过objdump查看的内容:

interp

里面的内容很简单，就是保存了链接器所在的路径，在Linux下，可执行文件所需要的链接器的路径几乎都是lib64/ld-linux-x84-64.so.2(64位下),其中ld-linux-x86-64.so.2通常是一个软链接。

另外，动态链接器在Linux下是Glibc的一部分，也就是属于系统库级别的，它的版本号往往跟系统中的Glibc库版本好是一样的。当系统中的Glibc库更新或者安装其他版本的时候，/lib/ld-linux-x86-64.so.2这个软链接就会指向新的特点链接器，而可执行文件本身不需要修改.interp段中的内容来适应系统的升级。

“.dynamic”段

类似于”.interp”这样的段，ELF中还有几个段也是专门用于动态链接的，其中最重要的就是.dynamic段。这个段里面保存了动态链接器所需要的基本信息，比如依赖哪些共享对象、动态链接符号表的位置、动态链接重定位表的位置、共享对象初始化代码的地址等。

全局符号介入与地址无关代码

全局符号介入的概念参见自制内存调试工具这篇文章里面的说明。

前面介绍地址无关代码时，对于第一类模块内部调用或者跳转的处理时，我们简单地将其当作时相对地址调用、跳转。但实际上，由于全局符号介入问题的存在，编译器在处理这种没有static修饰的内部函数调用、跳转时是当作模块外部符号处理的。因为一旦类似于上面例子中的bar函数由于全局符号介入被其他模块中的相同名的函数覆盖，那么foo如果采用相对地址调用的话，那个相对地址部分就需要重定位，这又与共享对象的地址无关性矛盾。所以即使ba函数被覆盖了，动态链接器只需要重定位”.got.plt”，不影响共享对象的代码段。

黑科技

二级指针的妙用

“指针是C的灵魂”，这句话大家都知道，但是在编写代码时能够熟练恰当的使用二级指针的人不是很多。下面介绍二级指针在操作单向链表方面的妙用。

作为对比，我们先贴教科书上的给出的单向链表的实现：

/**
 * without use of pointers-to-pointers
 */

#include <stdio.h>
#include <stdlib>

typedef struct node{
	int id;
	struct node *next;
}node_t

node_t *first, *last;

static void add_node(int id)
{
	node_t *node = malloc(sizeof(*node));
	
	if(node){
		node->id = id;
		node->next = NULL;
	
	        /**
		 * hava to figure out if we are adding the first node
		 */
		if(!first){
			first = last = node;
		}else{
			last->next = node;
			last = node;
		}	
	}
}

static void delete_node(int id)
{
	node_t *prev, *node, *next;
	
	for(prev = NULL, node = first; node != NULL;){
		next = node->next;
		
		if(node->id == id){
			/**
			 * have to deal with the situation where we encounter the first node 
			 */
			if(prev){
				prev->next = next;
			}else{
				first = next;
			}
			
			free(node);			
		}else{
			prev = node;
		}
		
		node = next;
	}
}

static void print_node(void)
{
	node_t *node;
	
	for(node = first; node != NULL; node = node->next){
		printf("%d -> ", node->id);
	}
	
	printf("NULL\n");
}

/**
 * test.c
 */

int main(void)
{
	int i;
	
	for(i = 0; i < 8; i++){
		add_node(i)
	}

	print_node();
	
	delete_node(3);
	
	print_node();
	
	return 0;
}

上面代码涉及单向链表的创建和节点删除，虽然功能正常，但是需要额外地使用分支语句，让代码看起来很难受。下面使用二级指针优化上面的实现。

/**
 * optimized with pointers-to-pointers
 */
 
 node_t *first;
 node_t **last = &first;
 
 static void add_node(int id)
 {
 	node_t *node = malloc(sizeof(*node));
	
	if(node){
		node->id = id;
		node->next = NULL;
		
		*last = node;
		last = &node->next;
	}
 
 }
 
 static void delete_node(int id)
 {
 	node_t **cur;
	node_t *node;
	
	for(cur = &first; *cur;){
		node = *cur;
		
		if(node->id == id){
			*cur = node->next;
			free(node);
		}else{
			cur = &node->next;
		}
	}
 
 }

经过优化，没有了多余的分支，代码开起来爽朗整洁了很多。而且根据我们在性能优化方面的基础知识，少了分支，代码的执行效率会得到提高。

Gapless Ring Buffer

Ring Buffer在许多业务中有种广泛而频繁的使用，尤其是音视频开发项目中。Ring Buffer的代码实现很简单，但是对于通常实现中对读写指针的wrap处理，常常让人感觉很难受，比如向Ring Buffer中填充数据write方法的实现，代码一般如下:

#define BUFFER_SIZE   (4096)

struct ring_buffer_t{
	uint8_t data[BUFFER_SIZE];
	uint32_t read;
	uint32_t write;
};

int write(ring_buffer_t *rb, uint8_t *p, uint32_t size)
{
	uint32_t bytes_to_write = (BUFFER_SIZE - rb->write + rb->read - 1) % BUFFER_SIZE;
	
	if(bytes_to_write < size)
		return -1; 
	
	if(rb->write > rb->read)
	{
		if(BUFFER_SIZE - rb->write >= size)
		{
			memcpy(&rb->data[rb->write], p, size);
		}
		else
		{
			uint32_t offset = BUFFER_SIZE - rb->write;
		
			memcpy(&rb->data[rb->write], p, offset);
			memcpy(rb->data, p + offset, size - offset);
		}
	}
	else
	{
		memcpy(&rb->data[rb->write], p, size);	
	}

	rb->write = (rb->write + size) % BUFFER_SIZE;
	
	return 0;
}

上面的代码是不是看得浑身不舒服，但好像也没有办法再写得好看点了我们仔细想一想，为什么上面的实现会如此的不堪？根本的原因是，ring buffer的缓存逻辑地址的连续和读写指针操作的逻辑地址的不连续之间的矛盾。也就是说，上面的rb->data是在系统中分配的连续的静态虚拟内存，而rb->write和rb->read实际操作的逻辑地址是非连续的。所以，解决办法有两个:

让rb->write和rb->read操作的逻辑地址是连续的。
为rb->data申请非连续的虚拟内存。

其中，alsa驱动中的输出缓存就是”近似于”使用了第一种解决方案，说是近似，因为虚拟地址总共是有最大值的，而rb->write终究会超过这个值，所以为了 alsa将输出缓存的ring buffer的大小设定为接近无符号长整型的最大值。

本文就是要通过第二个方案优雅地实现Ring Buffer，让代码实现的赏心悦目。

核心思想就是，将一段物理内存映射到两段虚拟地址上，而且这两段虚拟地址是紧挨着的。示意图如下:

ringbuffer

这样，我们在写入和读取Ring Buffer中的数据时，不用自己处理虚拟地址不连续的问题。比如，rb->write > rb->read时，这时我们将要写入的数据量大于BUFFER_SIZE - rb->write，按照上面的代码，我们需要分2次copy,但是，现在我们直接执行 memcpy(&rb->data[rb->write], p, size)一次拷贝完成。因为越掉第一个虚拟地址访问到第二个虚拟地址开始部分的内存，和回头访问第一个虚拟地址开始部分对应的物理内存是一样的。这就是这个实现的trikey所在。

核心代码如下，具体完整代码实现和测试代码见github

#define ALIGN(size, n)  (((size) + (n) - 1) & ~((size) - 1))
#define PAGE_ALIGN(size) ALIGN(size, sysconf(_SC_PAGE_SIZE))

int cycbuf_create(size_t size, cycbuf_t **hnd)
{
	cycbuf_t *pcb = malloc(sizeof(*pcb));
	
	if(!pcb)
	{
		return -1;
	}
	
	pcb->size = PAGE_ALIGN(size);
	pcb->tail = 0UL;
	pcb->head = 0UL;
	
	pcb->vaddr = mmap(NULL, pcb->size << 1, PROT_READ | PROT_WRITE, MAP_ANONYMOS | MAP_SHARED, -1, 0);
	if(pcb->vaddr ==  MAP_FAILED)
	{
		goto mmap_error;
	}
	
	if(remap_file_pages(pcb->vaddr + pcb->size, pcb->size, 0,0,0) < 0)
	{
		goto remap_error;
	}
	
	*hnd = pcb;
	
	return 0;
	
remap_error:
	...
}


int cycbuf_write(cycbuf_t *pcb, size_t len, void *data)
{
	size_t bytes_to_write;
	
	bytes_to_write = (pcb->size - pcb->head + pcb->tail - 1) % pcb->size;
	
	if(bytes_to_write < len)
	{
		return -1;
	}
	
	memcpy(pcb->vaddr + pcb->head, data, len);
	
	pcb->head = (pcb->head + len) % pcb->size;
	
	return 0;
}

分支预测的运用

分支预测的背景知识请参加这篇文章,

在linux内核中存在大量的likely()和unlikely()宏的使用，这个宏其实就是封装了gcc提高的built-in函数__builtin_expect()，具体定义如下:

#define likely(x)	__builtin_expect(!!(x), 1)
#define unlikely(x)	__builtin_expect(!!(x), 0)

引用网上一段关于这个内建的函数工作原理:

It optimizes things by ordering the generated assembly code correctly, to optimize the usage of thr processor pipeline. To do so, they arrange the code so that the likeliest branch is executed without performing any jmp instruction(which has the bad effect flushing the processor pipeline).

下面通过实际代码来分析研究：

/*branch.c*/
#include <stdio.h>
#include <stdlib.h>

#define likely(x) 	__builtin_expect(!!(x), 1)
#define unlikely(x)	__builtin_expect(!!(x), 0)

int main(int argc, char *argv[])
{
	int a;
	
	if(argc < 2)
	{
		printf("Usage: %s <number>\n", argv[0]);
		return -1;
	}

	a = atoi(argv[1]);
	
	if(unlikely(a == 2))
		a++;
	else
		a--;
		
	printf("a = %d\n", a);

	return 0;
}

执行gcc -O2 branch.c，发现执行结果正确。下面来分析上面程序的汇编代码，以及将unlikely换成likely后的汇编代码。

首先看一下将上面unlikely换成likely后，编译，执行objdump -S a.out，查看汇编代码实现：

likely

上面的cmp $0x2, %eax，就是代码中进行判断的地方，因为我们使用的是likely，意思就是告诉编译器，a等于2的可能性很大，所以汇编代码中选择跳转命令jne，而不是’je’，因为很大情况下是直接执行下面一条指令，即mov $0x3, %eai，实现a的自增，这样送进处理器的指令很少情况下会执行jne的跳转而浪费了加载进去的后面的mov $0x3, %eai指令。这样就减小了分支跳转带来的性能损失。

下面看一下调用unlikely时的汇编代码，可以预见差异的地方主要是将jne指令换成je指令:

unlikely

果然，上面的汇编代码和我们预测的一样。

{}的妙用

c语言中符号{ }表示一段匿名的内存，使用它可以简化很多工作，我们接触最多也是最早接触的用法应该是在初始化静态数组时，比如int array[10] = {0}。下面看一些开源代码中的”高级一些”的运用。

在linux内核文件”include/linux/rbtree.h”中，红黑树根节点的宏定义为:

 struct rb_root{
	struct rb_node *rb_node;
}

#define RB_ROOT (struct rb_root){NULL,}

其中{NULL,}表示一块初始化为NULL指针的内存，但是这块匿名的内存应该分配多大呢？所以要通过前面的(struct rb_root)来通过强制转换类型来限制或者说是确认内存大小。

在ffmpeg的libavcode/utils.c文件中的avcodec_send_frame()函数中:

static int do_encode(AVCodecContext *avctx, const AVFrame *frame, int *got_packet);

int avcode_send_frame(AVCodecContext *avctx, const AVFrame *frame)
{
	...

	return do_encode(avctx, frame, &(int){0});
}

因为avcodec_send_frame函数在调用do_encode()函数时，对于do_encode()通过入参返回的got_packet值并不关心，所以为了省去在代码一开始显式的定义一个变量传入do_encode(),直接通过(int){0}申请一个int类型大小的匿名地址传入。这里有一个值得思考的问题就是，这个匿名变量是在栈上内存申请的还是其他地方的内存申请的。

语法

类型提升

在实际的项目里，经常会出现不同类型之间互相赋值的情况。这个时候要特别注意在赋值过程中可能出现的类型提升问题。看下面一个简单的例子：


#include "stdlib.h"
#include "stdio.h" 

int main()
{
  unsigned int a = 1;
  char  b = 0x8a;
  unsigned char  c = 0x8a;

  a = b;

  printf("%x\n", a);

  a = c;

  printf("%x\n",a);

  return 0;

}

上面程序运行结果：0xffffff8a 0x8a

从这个例子可以看出无符号和有符号的变量不能随便混用。

int copy_something(char *buf, int len)
｛
	#define MAX_LEM 256
	char mybuf[MAX_LEN];

	...
	...
	if(len > MAX_LEN)
	{
		return -1;
	}

	return memcpy(mybuf,buf,len);
｝

上面的例子中，如果len传进来的是一个负值，那么会通过if语句的检查，由于memcpy的len的入参类型是unsigned int,所以会导致传进来的负值变成一个很大的值。

GCC