编译原理/计算机系列

来源：MRRiddler ，

blog.mrriddler.com/2017/02/10/计算机体系-编译体系漫游/

要想让代码乖乖运行，自然代码要先经过编译，这篇文章就来聊聊编译体系。

代码的编译过程分为四个阶段，预处理、编译、汇编、链接。而编译阶段是整个过程中最复杂的阶段，编译阶段还可以分为词法分析、语法分析、语义分析。

在一头扎进这四个阶段之间，先聊一下语法、语义。人类之所以能在进化的历史长河中，成为动物中的佼佼者，进化出的复杂的沟通机制—语言功不可没。假如，我说出这句话：你个产品狗还在改需求！那么语法是啥呢？简单说就是构成这句话的顺序，假如顺序错乱意思就不同了。那么语义是啥呢？就是语境，根据我说这句话的情景，才能解释出你指的是谁。语法在编程语言中，表现出来的就是语法结构和结合律。语义表现出来的就是上下文(context)。

预处理(Preprocess)：处理预处理符(#)，包括宏展开、头文件引入。 词法分析(Lexical Analysis、Tokenizer)：写出的代码实际上就是字符串，此阶段需要对字符串进行扫描(Scanner)，将字符串扫描出分析的最基本单位(token)，并在扫描过程中将它们分类，此阶段是没有任何语义的。也可以理解成将代码扫描出基本表达式。 语法分析(Syntactic analysis、Parser)：生成AST抽象语法树，检查语法结构，此阶段是上下文无关的。也可以理解成将基本表达式按语法结构组合成复合表达式。 语义分析(Semantic Analysis)：语义检查(比如检查浮点数乘以指针，虽然语法结构正确但是语义检查不合格)，将程序与上下文结合，进行静态类型分析，确定AST每个节点的类型。也可以理解将复合表达式结合环境(Environment)，并且确定基本表达式、复合表达式的类型。 中间码(Intermediate Representation)：与语言无关、平台无关的中间码。如果编译器面向多语言，对于任意语言编译阶段后可以生成通用的中间码，这样编译器就有多语言的高拓展性了。生成中间码后再交给汇编阶段，再生成与平台相关的汇编，这样使编译器将平台相关性尽量往后推移。中间码除了做为“桥接“，对中间码的优化也是整个编译过程中的关键优化。 汇编(Assemble)：对中间码生成平台具体的汇编，在这个阶段添加对多个平台的支持，编译器就可以跨平台了。最后生成机器码。 链接(Link)：将每个机器码编译单位中引用的其他编译单位中的变量、函数符号修正(fix)成真实地址。

编译历史

编译的历史基本就是计算机的进化史，是很有趣的一段故事。Long time ago… 程序员写程序都是用纸带，那时候还在写0、1机器码。纸带上打孔就是0，不打孔就是1。然后计算机读取纸带就是读取指令。但是就像互联网本质就是提高效率一样，这样写程序的效率怎能接受？并且，写程序如果犯了错误怎么办？重新从头到尾再用新纸带搞一遍？程序员们机智的开始想办法了，先是这样搞：

将指带有误的地方，用黑黑的小贴纸填上去，这样将0改成1了。这也是Patch名字的由来。但是这样写指令效率还是太低，程序员们再机智的想办法。后来将指令进行符号化(Symbol)，抽象出指令集，这时就出现了汇编，程序员的效率上了一个档次。但是新的问题又出现了。在写过程调用的时候，要写jmp 具体的函数地址。如果后来要在被调用的函数前面添加指令，那么函数地址也要跟着改。这样牵一发动全身的感觉可不好，为了让影响(impact)缩减到最小，不如将函数地址也符号化。凡是写过程调用先写成jmp func，等到程序生成机器码的时候，再将func换成真正的函数地址，这一步也就是将程序员手动修正交由汇编器修正。

随着生产力的提升，程序的规模越来越大，新的问题出现了，程序膨胀到难以维护和阅读了。程序员们就将程序模块化、层次化。这样也使编译的单位更小粒度化。编译的时候，不同编译单位之间的细节是互相隔离的。比如，对于C语言系，一个.h和一个.m就构成了一个编译单位。.m汇编时，是不知道其他.m的全局变量、函数地址的，而调用的时候就只能用符号进行调用，等到最后所有.m都生成机器码后再进行统一的修正。而负责这一步的就是链接器(Linker)，这一步也叫重定位(Relocation)。

目标文件

经过汇编这一阶段后，就会生成目标文件。目标文件和可执行文件已经非常相近了，只是有些符号还未修正，结构上会进行调整。Windows平台下为PE(Portable Executable)，Linux平台下为ELF(Executable Linkable Format)，Mac平台下为Mach-O。虽然不同平台都有自己的格式，但是它们实际上都大同小异。下面大体聊一下文件的实际字段，这些知识会为后面我们搞一些符号重绑定做铺垫。

section

首先，文件分段(section)。不同的Section放置不同的信息，文件还有一个section header table放置控制信息。实际上，就类似图片格式和mutipart的HTTP报文。以下是一个ELF目标文件的常见section：

—— —— —— —— —— —— ——

|header | -----> 文件头

|—— —— —— —— —— —— ——|

|.text | -----> 代码段

|—— —— —— —— —— —— ——|

|.data | -----> 已初始化全局变量、静态变量

|—— —— —— —— —— —— ——|

|.bss | -----> 未初始化全局变量、静态变量

|—— —— —— —— —— —— ——|

|other sections... |

|—— —— —— —— —— —— ——|

|section header table| -----> section控制信息表

|—— —— —— —— —— —— ——|

|.strtab | -----> 字符串表

|—— —— —— —— —— —— ——|

|.symtab | -----> 符号表

|—— —— —— —— —— —— ——|

|..... |

—— —— —— —— —— —— —— —

.text放置代码，.data放置已初始化的全局变量和静态变量，.bss放置未初始化的全局变量和静态变量。为什么代码和全局变量、静态变量要分开放？实际上，这就是个等同性问题。代码段就是可读的数据，而全局变量、静态变量是可读可写的数据。如果有多个进程进行同一份代码，这些代码都是等同的，不需要各自复制一份。而全局变量、静态变量是不等同的，需要各自复制一份。而分什么又要分已初始化、未初始化呢？目标文件未初始化的全局、静态变量只需要放置一个占位符，代表其在.bss。而.bss在链接阶段，变量不占空间，在装载时由操作系统再分配空间。可以看到，既然是文件格式，不管怎么设计，主要的目的就是占更少的空间。

header有很多文件控制信息，就不一一表述了，其中最重要的就是记录了section header table的起始地址。而section header table记录了所有section的名字、类型、长度、在文件中的偏移量(offset)等。如果想要寻址到任意section都要通过这个header table。section header table实际上是由struct构成的数组。

.strtab放置section名、变量名，包括符号名的字符串。由于在整个结构中，字符串的长度是不定的，一般将这些字符串统一放置在一个table中，然后存储table中的offset，最后寻址到字符串。比如，在下表中，我想找到girlfriend一词，我只要拿到.strtab的base地址，加上girlfriend的offset 9就可以找到这个字符串。

0 1 2 3 4 5 6 7 8

i 0 w a n t 0 a 0

g i r l f r i e n

d

.symtab就是大名鼎鼎的符号表。每个目标文件都有自己的符号表，符号表记录符号的映射，符号可以这样分：文件外符号和文件内符号，文件外符号就是使用在其他文件定义的符号，文件内符号除了在文件内定义给其他文件使用的符号，还包括每个section符号，在文件内定义光是文件内使用的符号。光文件内使用的符号，对链接没有帮助，主要为了崩溃后分析而存在。符号表也是一个由struct构成的数组。ELF的32位符号sturct：

typedef struct {

int32_t st_name;

uint32_t st_value;

int32_t st_size;

unsigned char st_info;

unsigned char st_other;

uint16_t st_shndx;

} ELF32_Sym;

st_name字段就是符号的名字，表示为在.strtab中的字符串offset。st_info表示是局部符号、全局符号还是弱符号。符号也可以分为强符号(Strong Symbol)、弱符号(Weak Symbol)，顾名思义，强符号有唯一性，弱符号没有唯一性，一个强符号可以和多个弱符号共存，多个重复的强符号不可以共存，链接器会报出duplicate dymbol，可以用attribute((weak))指明弱符号。相对的，符号也有强引用(Strong Reference)、弱引用(Weak Reference)，在链接进行符号修正的时候，强引用必须修正，而弱引用可以不修正，可以用attribute((weakref))指明符号弱引用。

st_shndx字段指明了符号是文件外符号，还是文件内符号。如果是文件外符号就为SHN_UNDEF。如果是文件内符号包括给其他文件使用的、光自己使用的、section符号，就为所在section的索引号，而st_value表示所在section的offset。等到链接过后，不管是文件外符号还是文件内符号，st_value指明实际地址。

符号修饰(Symbol-Decoration)与函数签名(Function-Signature)

机智的同学已经发现了，如果光按上面聊的方式进行符号链接是有问题的，假如目标文件有个func符号又引用了其他文件同名的func符号，那符号不就出现冲突了？这里就需要引入函数签名，函数签名是一个函数的名字、参数类型、所在类名组成的字符串，不同语言、不同编译器对同一个函数生成的函数签名是不一样的，比如OC中函数签名还要加上返回变量类型，C++中还要加上NameSpace。在链接的时候，过程调用符号不光是函数名，是对函数签名处理后的结果，全局变量符号也是经过类似用函数签名处理后的结果。这一处理过程就是符号修饰。

fishhook

fishhook是facebook开源的重绑定Mach-O符号的库，最常用来hook C语言函数，而且实际上只能重新绑定C符号，因为符号修饰这一步只去掉了”_”，相当于只针对C语言做了符号修饰。在了解了目标文件后，重绑定就不是那么困难了。最基本的思路就是先拿到header，然后通过header拿到section header table，再找到.hash，.hash是一个用于加快访问.symtab的哈希结构，再索引到.symtab，详见这里，通过name去.strtab比对符号名，如果匹配就置换value。

https://docs.oracle.com/cd/E2382401/html/819-0690/chapter6-48031.html

fishhook大体实现原理就是这样，只不过对Mach-O平台特性改进一下方案就行。在Mach-O中类似于section header table的段叫做load commands。并且Mach-O中使用二级命名空间，先分segment，就相当于上文中的section，然后再在同一segment中区分section。

先拿到header，通过header中的ncmds(segment的个数)和cmdsize(segment的大小)字段就可以找到所有的segment。然后找到.strtab、.symtab、indirect symbol table。这个indirect symbol table是一个uint32_t的数组。它就是nl_symbol_ptr(non-lazy)和la_symbol_ptr(lazy )对应的.symtab struct数组的索引。nl_symbol_ptr和la_symbol_ptr section section中的reserved1字段指明对应的indirect symbol table起始offset。只要从这两个section对应的indirect symbol table起始表项再跳到.symtab去匹配、置换就可以了。

下面是32位下.symtab的struct，可以看到和上段文章讲的几乎一致：

struct nlist {

union {

char *n_name; /* for use when in-core */

uint32_t n_strx; /* index into the string table */

} n_un;

uint8_t n_type; /* type flag, see below */

uint8_t n_sect; /* section number or NO_SECT */

int16_t n_desc; /* see <mach-o/stab.h> */

uint32_t n_value; /* value of this symbol (or stab offset) */

};

上文提到的Mach-O格式如下：

—— —— —— —— —— —— ——

|header |

|—— —— —— —— —— —— ——|

|load commands |

|—— —— —— —— —— —— ——|

|__Text |

|—— —— —— —— —— —— ——| —— __nl_symbol_ptr

|__Data | -----> |

|—— —— —— —— —— —— ——| —— __la_symbol_ptr

|other sections... |

|—— —— —— —— —— —— ——|

|.strtab |

|—— —— —— —— —— —— ——|

|.dynsym | -----> indirect symbol table

|—— —— —— —— —— —— ——|

|..... |

—— —— —— —— —— —— —— —

更加详细的格式，推荐这篇文章。

http://turingh.github.io/2016/03/07/mach-o文件格式分析/

链接

上面聊了这么多 ，那静态链接到底是如何将多个目标文件链接成一个可执行文件的呢？

静态链接分为两阶段(Two-pass Linking)，第一阶段先扫描所有目标文件，调整结构。将所有目标文件相同section合并，包括.symtab合并成全局.symtab，然后为每个section分配虚拟地址，再将全局.symtab中的符号进行置换成虚拟地址。

这里如何将全局.symtab中的符号置换成虚拟地址呢？实际上，在分配section虚拟地址后，符号的虚拟地址按所在section虚拟地址加offset就可以计算出了。

第二阶段将所有符号进行修正。通过重定位表找到所有section中需要被修正的符号位置，然后从全局.symtab查询出虚拟地址置换。

每个section都会对应一个重定位段，这些重定位段组成一个重定位表。每个重定位表项叫做重定位入口(Relocation Entry)，它记录了所需重定向符号所在段的offset。

静态链接库

静态链接库就是一组目标文件，经过压缩、索引而成的一个文件形式。当我们平时在使用静态链接库的时候，实际上链接器会根据所需的符号，在库中搜索到相应的目标文件，并将其链接入最终可执行文件。

动态链接

随着静态链接慢慢发展起来，静态链接也暴露出了问题。静态链接将链接与被链接的目标文件结合的太紧密了，导致如果多个目标文件要链接同一个目标文件，那这个被链接的目标文件相当于要被复制多份，每个可执行文件都要包含这个被链接的目标文件的内容，这样会占太多冗余空间。那怎么办？将链接与被链接的目标文件先隔离开，将链接的时机往后推移，等到装载的时候再进行链接。这样，让被链接的目标文件只占一份空间就好。

既然动态链接隔离开了链接、被链接目标文件，链接目标文件需动态链接的符号，就需要先做个动态链接占位符。这也就是说，在目标文件链接成可执行文件时，即使是用作动态链接的目标文件也要作为动态链接库输入到链接阶段，以供目标文件识别哪些符号是动态符号。

动态链接重定位

上面已经聊完了在链接阶段对静态链接进行重定位，根据符号所在section的虚拟地址和所在section的offset。而动态链接可以这样重定位吗？不行，这时动态链接库的地址还没有确定，必须等到装载以后操作系统分配。那可以等到装载以后，确定地址后再直接进行重定位吗？不行，假如动态链接库被多个进程引用，装载时动态链接库进行重定位，动态链接库映射到每个进程中的虚拟地址都不一样，动态链接库只能对一个进程重定位，那么动态链接库就不是共享的了。那怎么搞？

通过.got(global offset table)，.got就是一个指针数组，.got存储引用符号的实际地址。而代码段引用符号直接更改为引用.got项的位移，这在链接阶段以后就不会再改变了。然后将.got分配在.data section，装载时每个进程复制一份并修正。实际上，动态链接重定位指的就是在装载的时候，根据全局符号表修正.got表项。动态链接库使用全局变量、静态变量、引用文件外过程调用都要经过.got。.got就像indirection table一样，解决多进程共享动态链接库。

这样，动态链接库虽然在不同进程中有不同的映射虚拟空间，但物理空间上共享。.got在不同进程中，虚拟空间和物理空间都不共享。如下图所示：

virtual address -> physical address

—— —— —— —— —— —— ——

|processA |

|—— —— —— —— —— —— ——|

|..... |

|—— —— —— —— —— —— ——|

|dynamic libiraries |----------

|—— —— —— —— —— —— ——| |

|..... | | |..... |

|—— —— —— —— —— —— ——| | |—— —— —— —— —— —— ——|

|.got |---------|---------->|.got |

|—— —— —— —— —— —— ——| | |—— —— —— —— —— —— ——|

|..... | | |..... |

|—— —— —— —— —— —— ——| | |—— —— —— —— —— —— ——|

----------->|dynamic libiraries |

—— —— —— —— —— —— —— | |—— —— —— —— —— —— ——|

|processB | | |..... |

|—— —— —— —— —— —— ——| | |—— —— —— —— —— —— ——|

|..... | | ------>|.got |

|—— —— —— —— —— —— ——| | | |—— —— —— —— —— —— ——|

|dynamic libiraries |---------- | |..... |

|—— —— —— —— —— —— ——| |

|..... | |

|—— —— —— —— —— —— ——| |

|.got |---------------

|—— —— —— —— —— —— ——|

|..... |

|—— —— —— —— —— —— ——|

动态链接库文件外符号重定位用.got就搞定了，那动态链接库文件内符号呢？静态链接同样是在链接阶段重定位就搞定了。动态链接将绝对寻址指令更换成相对寻址指令，只要指令的offset不变，相对寻址指令就可根据当前地址和offset得到正确的地址，这样文件内符号根本不需要重定位了。基于以上两点的处理，代码段在链接后就不需要更改了，这样的代码段也叫做地址无关码(PIC)，也就是说代码段和装载后的地址无关。

延迟绑定(PLT)

由于要跳过.got引用动态链接库的符号，动态链接库比静态链接库慢5%左右，但相比于节省的大量空间还是很划算的。除此之外，动态链接还会有其他的问题，装载时需要进行重定位，会导致性能下降。不如，直接延迟绑定，等到过程调用符号运行时被用到再进行重定位。

整个过程强烈推荐这篇文章，要想理解动态链接重定位，没有比追汇编更好的方法了。动态链接和延迟绑定整个过程都是由动态链接器帮我们完成的。当引用符号(callq)时，先jmpq去plt结构，使用了PLT，引用符号就要先jmpq去plt结构。如果没找到相应的地址，然后再jmpq去.got.plt或.got中。再把符号相应.rela.plt表中的索引和.got.plt相应的表项，pushq入栈，rela.plt中有符号的类型和名字。再jmp到动态链接库中(_dl_fixup)，去全局符号表中找到符号相应的地址。再将地址reloc到.got.plt或.got相应表项。然后就完成了延迟绑定，下次引用同样的符号就可以jmpq去plt结构找到地址。

http://sysfork.com/post/linux-dynamic-lib-lazy-load/

引用

程序员的自我修养—链接、装载与库

关注「ImportNew」，看技术干货

一、什么是编译

1、利用编译程序从源语言编写的源程序产生目标程序的过程。

2、用编译程序产生目标程序的动作。 编译就是把高级语言变成计算机可以识别的2进制语言，计算机只认识1和0，编译程序把人们熟悉的语言换成2进制的。 编译程序把一个源程序翻译成目标程序的工作过程分为五个阶段：词法分析；语法分析；语义检查和中间代码生成；代码优化；目标代码生成。主要是进行词法分析和语法分析，又称为源程序分析，分析过程中发现有语法错误，给出提示信息。

二、什么是反编译

计算机软件反向工程（Reverse engineering）也称为计算机软件还原工程，是指通过对他人软件的目标程序（可执行程序）进行“逆向分析、研究”工作，以推导出他人的软件产品所使用的思路、原理、结构、算法、处理过程、运行方法等设计要素，某些特定情况下可能推导出源代码。反编译作为自己开发软件时的参考，或者直接用于自己的软件产品中。

三、 Java类的编译与反编译

我们在最初学习Java的时候，会接触到两个命令：javac和java,那个时候我们就知道，javac是用来编译Java类的，就是将我们写好的helloworld.java文件编译成helloworld.class文件。

class文件打破了C或者C++等语言所遵循的传统，使用这些传统语言写的程序通常首先被编译，然后被连接成单独的、专门支持特定硬件平台和操作系统的二进制文件。通常情况下，一个平台上的二进制可执行文件不能在其他平台上工作。而Java class文件是可以运行在任何支持Java虚拟机的硬件平台和操作系统上的二进制文件。

那么反编译呢，就是通过helloworld.class文件得到java文件（或者说是程序员能看懂的Java文件）

四、什么时候会用到反编译

1、我们只有一个类的class文件，但是我们又看不懂Java的class文件，那么我们可以把它反编译成我们可以看得懂的文件。

2、学习Java过程中，JDK的每个版本都会加入越来越多的语法糖，有些时候我们想知道Java一些实现细节，我们可以借助反编译。

关注“动力节点Java学院”微信公众号，获取更多最新Java技术，如果你对编程有兴趣，想要成为优秀的Java程序员，那么动力节点Java零基础班现已开启免费试学阶段，对于想学Java的同学无疑是好消息，亲自考察教学质量，机会就在眼前,针对不方便前来的同学，可以关注动力节点Java全套免费视频，赶快学起来吧