程序的编译过程
- 预处理器cpp：.c(源文件)->.i(展开后的源文件)
- 编译器cc：.i->.s(汇编文件)
- 汇编器：.s->.o(目标文件)
- 链接器：1.o+2.o+x.o->.elf(.elf==.bin)
硬件组成与程序的运行
- 硬件组成
- 主要部分：CPU（PC、reg、ALU、cache、总线接口）、IO桥、内存
- 通道部分：系统总线（总线接口<->IO桥）、内存总线（IO桥<->内存）、IO总线（IO桥<->外设）
- 外设部分：总线<-控制器<-外设、总线->适配器->外设
- 简单的程序运行
- shell输入
- 从磁盘中，将程序（和它所需的数据）调取至内存
- 从内存中，将程序（和它所需的数据）调取至CPU
- shell显示
- 存储器层次模型
- L1-L3高速缓存为SRAM
- 主存为DRAM
- 操作系统提供的抽象：进程、虚拟地址空间、文件
- 单进程的上下文切换：保存当前进程上下文、切换进程、恢复新进程的上下文
- 单进程的多线程：共用该进程的代码段和全局数据
- 虚拟地址空间：给每个进程提供相同的内存空间结构（不同进程中只有其中的地址不一样）
- 内核内存部分（仅OS使用，进程无法访问，只能通过调用内核来进行操作）
- 用户栈（函数调用，向下生长）、共享库（动态链接）、运行时堆（内存申请，向上生长）
- 只读代码和数据区
- 文件：略
重要话题
- Amdahl定理
- 要想显著加速整个系统，必须提升全系统中相当大的部分的速度。
- 并发（时间段内交替执行多个元素）和并行（时间点内同时执行多个元素）
- 线程级并发
- 指令级并行：单周期(n cpi)->流水线(1 cpi)->超标量(<1 cpi)
- cpi：clk per inst，同理还有ipc(更常用)
- 单指令、多数据并行(SIMD并行)：一条指令可以拆分为多个操作，这些操作可以并行执行
程序的结构和执行
三种数字表示
- 二进制表示法：无符号整数
- 整数表示法：补码->无符号整数、有符号整数
- 基2的科学计数法：浮点数
程序的信息存储
- 程序和OS能看见的：进程->虚拟地址空间->虚拟地址->虚拟内存-/>物理内存（它们看不见物理内存）
- 这样的虚拟地址是由实际地址经过抽象和映射而来的
- 程序的信息就存在对应进程的虚拟内存中
- 参数：字长（若字长有x为，则虚拟地址空间范围为$0\sim2^x-1$字节）、寻址顺序
- 二进制表示：位运算
- 整数表示：补码运算、零扩展、符号扩展、截断
- 基2的科学计数法：
- 组成
- 规格化组成（exp不全0或1）：符号位s、阶码E=exp-Bias、尾数M=1+frac
- 非规格化组成（exp全0）：符号位s、阶码E=1-Bias、尾数M=frac
- 作用：提供一种近似为0的数、提供逐渐溢出特性
- 特殊值（exp全1）
- 舍入方式：向0舍入、向下舍入、向上舍入、向偶数舍入
- 浮点运算
程序的机器级表示
- 常用编译方式：gcc编译方式、clang(前端)+llvm(后端)编译方式
- 操作数指示符：立即数、寄存器、内存引用（立即数、寄存器、绝对、间接、偏移量、变址）
- 指令
- 数据传送
- 入栈和出栈
- 算术和逻辑
- 加载有效地址：实际上不是内存引用，只是将内存地址赋值给寄存器（link操作）
- 分支跳转
- 有条件跳转的优化：将跳转和不跳转的地址都计算一遍，即实现分支预测功能
- 确定分支预测错误的惩罚：假设预测错误的概率为p，预测错误的惩罚时间为$T_{MP}$，执行指令的时间为$T_{OK}$
- 则有平均执行时间$T_{avg}=(1-p)T_{OK}+p(T_{MP}+T_{OK})=pT_{MP}+T_{OK}$
- 若已知p和$T_{OK}$，则可以估算$T_{MP}$
- 过程与栈
- 调用函数时的栈帧结构（假设函数P调用函数Q）
- 挂起栈帧P：参数构造区+返回地址区（当Q释放时，需要回到P的返回地址处，继续执行）
- 运行栈帧Q：寄存器保存区+局部变量区+参数构造区（保存P传递进来的参数）
- 栈指针寄存器始终指向栈顶
- 栈帧的参数传递：函数参数的传递有两种方式，寄存器传递和栈的参数构造区传递。先往寄存器中保存，保存不下才会去栈中申请参数构造区来保存
- 栈帧的局部存储：如果寄存器满了、对局部变量使用“&”、局部变量为数组等情况，则会在局部变量区申请，在函数完成时释放。
- 栈帧的寄存器区存储：CPU寄存器是所有过程共享的，所以有一部分寄存器是不重要的、临时的信息，另一部分是重要的、跨函数调用的信息（这一部分就是寄存器区传递）。
- 被调用者保存寄存器：P可以任意修改，P调用Q后，需要Q栈帧中的保存寄存器区负责维护这一部分寄存器不变。（Q保存P的跨函数信息）
- 调用者保存寄存器：P栈帧中的保存寄存器区负责维护一部分寄存器不变，P调用Q后，Q可以任意修改。（P清除Q的临时信息）
- 调用指令call和返回指令ret：无参数调用/无返回值返回、有参数调用/有返回值返回
- 先放置参数/返回值，再进行call或者ret
- 利用栈的规则，可以体会递归过程
- 数组
- 定长数组：指针操作
- 变长数组：malloc/calloc方法，表达式维度方法（与编译器对乘法表达式的优化）
- 数据结构
- 结构体：访问方式（对象基址+偏移量，地址在编译时就确定，因此机器代码不包含字段声明，只有基址和偏移量），结构体对齐（每一个成员的字节填充）
- 联合体：访问方式同结构体，联合体对齐（最大成员的字节填充，联合体大小计算）
- 虚拟内存的对齐指定：“.align N”
- 内存越界引用、缓冲区溢出和缓冲区溢出攻击
- 有两个函数main和echo，main调用echo，而echo内部创建了一个字符数组buf，然后试图输入一个字符串到buf中
- 此时main有main栈帧，echo有echo栈帧（包含buf空间），由于main调用echo，所以main栈帧在上侧，echo栈帧在下侧且相连。
- 此时用get()输入了一个过长的字符串，它就可能使得echo栈帧中的buf入侵上部区域，即破坏main栈帧（破坏范围：main中未使用的栈帧空间->main的返回地址->main的寄存器区）
- GCC提供的对抗缓冲区溢出攻击
- 栈随机化ASLR：每次运行程序时，每次运行时，改变栈的地址。
- 栈保护者检测机制
- 限制可执行代码区域
- 支持变长栈帧：有些函数的局部变量会变长，导致栈帧中的局部变量区会不停变长，此时可以适配变长的栈帧
- 使用帧指针寄存器（区别于栈指针寄存器）
在系统上运行程序
常用分析工具
-
目标文件（elf结构）完整分析
-
objdump：分析目标文件中的所有信息
-
readelf：显示目标文件的完整elf
- strings：列出目标文件中的所有可打印的字符串
-
size：列出目标文件中各个节的名字和大小
-
目标文件的符号分析
-
nm：列出符号表的符号
-
strip：删除符号表信息
-
目标文件的库分析
- ar：操作静态库
- ldd：列出可执行文件在运行中，需要的共享库
链接
- 分离编译过程：若一个项目包含多个源程序，则编译器分别进行编译和汇编，使得.c->.o(可重定位/共享目标文件)，最终，链接器可以将多个分别编译的产物合为完全链接的目标文件
- 目标文件分类
- 可重定位：它必须与其他可重定位目标文件链接->可执行目标文件
- 可执行：它可以直接被复制进内存并执行
- 共享：在可执行目标文件加载进内存时、或者运行时，它动态加载进内存，并进行动态链接
-
常见的可执行目标文件格式：可执行目标文件.out（类Unix）、可执行可链接目标文件.elf（Linux）、可移植可执行目标文件.exe（Windows）
-
ELF文件格式
- ELF头
- .text、.rodata、.data、.bss
- .rodata：只读变量（const、string）
- .data：已初始化的全局变量和静态局部变量
- .bss：未初始化的全局变量和静态局部变量
- .symtab：一张符号表，每一项都保存程序中定义或引用==函数和全局变量==的信息（局部变量是不存在符号表里的）
- 它提供st_shndx，st_shndx指向ELF文件的.strtab的==基址==
- 它提供st_name，st_name表示这一项的名称存放在.strtab的==偏移量==位置
- 链接完成后将不需要符号表
- .rel.text（便于链接时调整text段中对符号的引用，使其指向正确的运行时内存地址）、.rel.data
- debug、line
-
.strtab：一张字符串表，不会加载进内存中
- 函数/全局变量名 = ELF[st_shndx+st_name]
-
链接过程：
-
链接器进行静态链接
- 符号解析（重整、处理多重定义等）
- 重定位（重定位“节和符号定义”、重定位“节中的符号引用”、删除rel节）
-
动态链接器进行动态链接
- 符号解析、重定位
-
符号解析
-
符号重整mangling和符号恢复demangling
- 函数重载（函数名相同，而参数列表不同），会使得strtab中查找到的名称一样而导致报错“重复定义”
- 此时需要进行mangling，即根据函数名、参数列表和类名等信息，生成一个唯一的新名字
-
处理多重定义
- 定义符号的强弱：函数、已初始化全局变量为Strong；未初始化全局变量Weak
- 处理规则：强强同名时报错、强弱同名时选择强符号、弱弱同名时任意选择一个
- 使用GCC-fno-common标志，来更快地查找这类错误
-
重定位
-
静态链接和动态链接都需要重定位。
-
重定位“节和符号定义”
- 将相同类型的节聚合为新节
- 将运行时的内存地址赋值给所有符号定义
-
重定位“节中的符号引用”
- 汇编器生成重定位条目：汇编器在生成目标文件时，每次遇到一个外部定义的函数/全局变量，就会生成一个重定位条目。它存放在rel.data/rel.text节中。它告知链接器offset(需要重定位处对应的节偏移)、type(重定位方式：相对/绝对)、symbol(需要重定位处对应的名称，它是strtab的偏移)。
- 链接器重定位符号引用
-
静态链接
- 静态库：它可以用做链接器的输入，当链接器构造一个输出的可执行文件时，它只复制静态库里被应用程序引用的目标模块。
- ar生成静态库的过程：将若干个.o中的每一个函数都提取成独立的可重定位目标文件（类似于文件夹中的文件），然后整合为.a（类似于文件夹）
- 理解静态链接的过程：可重定位目标文件->完全链接的可执行目标文件
-
静态链接时的要求：依赖在前，定义在后。
- 顺序调用：如果test.c调用libx.a调用liby.a，则命令为“gcc test.c libx.a liby.a”
- 环调用：如果test.c调用libx.a调用liby.a，但是liby.a也调用libx.a，此时libx.a和liby.a形成调用环
- 解决方法1：使用重复调用，命令为“gcc test.c libx.a liby.a libx.a”
- 解决方法2：使用合并，将环上的所有文件（libx.a和liby.a）全部合并为新的.a
-
动态链接
- 共享库：共享库也是一个目标模块，在运行或加载时，可以被动态链接器加载到任意的内存地址。
- 生成共享库的过程
- 传统静态库的方案：源文件.c->编译->可重定位目标文件.o->ar打包->.a
- 共享库的方案：源文件.c->编译时生成共享库（使用-fpic和-shared）->.so
- 理解动态链接过程：可重定位目标文件+共享库文件->部分链接的可执行目标文件+共享库文件->完全链接的可执行目标文件
- 链接器：复制一份.so中的符号表和重定位信息，并链接.o和.a文件，形成部分链接的可执行目标文件OUT
- 加载器：执行OUT文件<参见加载可执行目标>
- 动态链接器：
- 加载后执行前：加载过程中如果引用了共享库的函数/变量，会查找到.interp节，于是加载器会启动动态链接器，实现共享库的符号重定位（仅限使用的那部分符号），此时虚拟内存中共享库的位置就固定了
- 执行中：使用动态链接器的接口dlopen（打开共享库）、dlsym（在打开的共享库中，用符号名，查找符号所在的地址，一般用函数指针或指针变量来接收）、dlclose（关闭共享库）、dlerror
- 实现跨语言调用：Java本地接口JNI
-
多进程使用相同共享库的解决方法：位置无关代码PIC
- 位置无关代码PIC：可以加载而无需重定位的代码
- PIC的目的：无限多个进程可以共享一个共享模块的代码段的单一副本
- 生成全局变量引用的PIC：在数据段开头使用GOT（全局偏移量表），每个条目记录一个全局变量
- 生成函数调用的PIC：利用GOT和PLT（过程链接表），实现延迟绑定技术
- 延迟绑定：正常是为函数生成重定位记录，然后在加载时修改为调用代码的地址；而延迟绑定是在调用时才修改为调用代码的地址
-
加载可执行目标文件
- 总结：linux调用execve函数来使用加载器，加载器和操作系统会将程序的代码、数据从磁盘中复制到内存中。
-
理解加载的具体行为：
-
父shell进程生成一个子进程（父进程的复制），子进程调用execve启动加载器
- 加载器删除子进程的虚拟内存部分，然后创建全新的段，进行地址映射
-
加载器将子进程的虚拟内存初始化为可执行文件的内容
-
包含：内核内存、用户栈、共享库、运行时堆、只读代码和数据区（读写段=.data,.bss；只读代码段=.init,.text,.rodata）
-
会进行段对齐和ASLR（地址空间布局随机化），造成一些空隙
- 当CPU引用到被映射的虚拟页时，操作系统通过页面调度机制，将磁盘中的块传送至内存中的页。
-