CSAPP Ch3 程序的机器级表示

Posted on 2022-05-19 Edited on 2022-06-19 In 读书笔记《CSAPP》

It is never too late to be what you might have been.

程序的机器级表示

IA32的64位扩展，也成为x86-64
gcc -Og -S mstore.c，GCC会编译该代码且编译器会进行优化
objdump -d mstore.o，由反汇编器将机器级代码转换成汇编代码，同时反汇编器会在汇编代码的Label旁注上它所对应的地址; 需要注意的是反汇编后的汇编代码地址为链接阶段重定向之后所处的地址，链接器在程序代码中会插入nop来提高访问存储器的性能(更好地放置下一个代码块)。
x86-64指令长由从1到15个字节不等。
Variable Instruction vs. Fixed Instruction，基于变长指令的ISA生成程序代码所需要的存储空间相对于定长指令更小，但增加了DECODE的开销，这也是一个Tradeoffs
ATT格式的汇编代码，AT&T是运营贝尔实验室的公司，这种格式是GCC，OBJDUMP等工具的默认格式
根据x86 AT&T语法，寄存器前要加%，立即数前要加$，注释用#来表示。
要想在C语言中编写汇编代码，可以通过GCC的内联汇编，用asm伪指令来包含简短的汇编代码
Intel用术语字来表示16位数据类型，老大补充字为CPU和Cache之间的数据交换单位，且RISC风格的ISA的字为32位
GCC生成x86的汇编代码指令都有一个操作数大小的字符后缀b、w、l、q，如：movq
区分x86不同大小的寄存器，前缀为r的寄存器的大小为四字，前缀为e的大小为双字，后缀为l或者b寄存器的大小为字节，其余的归为大小为字的寄存器
x86的操作数格式，其中比例因子必须是1、2、4、8
x86规定任何为寄存器生成32位值的指令都会把该寄存器的高四字节置为0，如：movl $256, %eax，会把rax寄存器的高32位置0
常规的movq指令只能以表示32位补码数字的立即数作为源操作数
movq会将32位的立即数拓展为64位再进行传送，而movabsq直接使用64位的立即数作为源操作数使用
mov的两个操作数不能同时为内存地址
x86-64的内存引用总是用4字长的寄存器(因为地址空间大小为64位)，如：movw %dx, (%rax)
强制转换先考虑大小，在考虑符号
pushq等价为subq加上movq两条指令的操作，popq同理，操作的数据大小为四字
x86的二元算术和逻辑操作的第二个操作数既是源也是目的
lea加载有效地址指令，在x86中可以充当算术运算(编译器经常会这么优化)，比如%rdi表示x，%rsi表示y，那么leaq (%rdi, %rsi, 4), %rax就可以等价于x + 4*y
移位操作中的寄存器操作数，只有最低字节才指示移位量，因为8个bit以内足以表示四字的偏移量了
x86 ISA支持两个64有符号或者无符号的乘法或者除法，结果是128位。乘法运算，乘法得到的结果的高64位保存到rdx中，低64位保存到rax中；除法运算，将商保存到rax中，余数存到rdx中; 高64前老大有提到过两个32位补码(i.e. 有符号数)在mips中相加得到的结果该怎么处理，因为mips没有这样的指令，可以通过编程来实现，无论是两个32位补码相加还是两个64位补码相加，得到的结果的低32位永远是无符号数，其余都是有符号数
x86有四种条件码分别是: CF: 进位标志, ZF: 零标志, SF: 符号标志, OF溢出标志
CMP指令类似于SUB指令，但不更新目的寄存器；同样TEST类似于AND指令，也不更新目的寄存器；e.g. testq %rax, %rax就生成与零比较所产生的条件码
比较和测试指令以及算数运算指令(lea除外)都会设置条件码
SET指令的目的操作数是低位单字节寄存器，它根据条件码的组合，将结果(0或1)放到寄存器中。比如:
1
2
cmpq %rsi, %rdi
setl %al
比如j, set, cmov这些指令，后缀为g或者l表示有符号的大于和小于；后缀为a或者b表示无符号的大于和小于，来将生成条件码的结果和0进行比较。
直接跳转jmp Label; 间接跳转jmp *Operand(i.e. jmp *%rax使用寄存器rax中的值作为Label；或者jmp *(%rax)使用寄存器的值作为地址来访问存储器得到Label)。
个人认为直接跳转可以直接使用label，而间接跳转需要从存储器(e.g. 寄存器或者主存)中读取label; 条件跳转只能是直接跳转
x86中的PC-relative是通过PC+4+符号位拓展的Offset来计算跳转到的地址
原本不同目标文件的虚拟地址的程序段都是由0开始，链接后，重定位到可执行目标文件后原本程序段的虚拟地址就发生了变化
rep指令后面跟ret的组合来避免使ret指令成为条件跳转指令的目标(e.g. rep; ret)
条件传送指令的tradeoff，能够提高遇到分支时流水线的效率(e.g. 减少控制冲突的可能，可以通过插一个气泡的方式来解决)，但同时也会增加指令数。不过现代微处理器的分支预测器已经足够优秀，所以比如说ARM就没有添加条件传送指令; 由编译器来决定编译出条件分支指令还是条件控制转移指令，不过GCC还是更倾向于使用条件控制转移
流水线预测错误处罚时间: $T_{MP}=2(T_{ran} - T_{OK})$；执行代码的平均时间: $T_{ran} = T_{avg} = T_{OK}+0.5T_{MP}$；其中$T_{ran}$为分支随机预测时的执行时间，$T_{OK}$为分支非常可预测的执行时间
逆向工程，简而言之就是由汇编到高级语言程序
注意编译器的优化不会总能带来性能的提升

编译器对while循环的两种优化: jump to middle和guarded-do，通过量化的方式，第二种方式在流水线中相比第一种性能较好

jump to middle:

    goto test;
loop:
    body-statement
test:
    t = test-expr;
    if (t)
        goto loop

guarded-do:

t = test-expr;
if (!t)
    goto done;
loop:
    body-statement
    t = test-expr;
    if (t)
        goto loop;
done:

switch语句采用跳转表(jump table)，跳转表就是个数组，因此当值的范围跨度较大时，跳转表所占用的存储空间就会变大。当switch语句case数量比较多(4个以上)，并且值的范围跨度比较小时就会使用跳转表(GCC根据switch的case数量和值的范围来决定是否编译成生成跳转表)。
和if-elseif语句相比，使用跳转表的优点是执行switch语句的时间与case的数量无关(用空间来换时间)
GCC中前缀&表示指向数据值的指针，&&表示指向代码的指针
switch语句先判断常量值是否在switch语句范围内(可能会和某个数值做差来生成保证由0开始的数组下标)，如果不在范围内或者在范围内情况在switch语句中不存在，则跳转到defualt情况对应的label。若存在重复的情况，则两种情况使用同一个label(e.g. case 104和106就会使用同一个label)，如：
1
2
3
4
case 104:
case 106:
val *= val;
break;
Case的范围从100到106的跳转表，.align指令指定数组元素要保证8字节对齐，.quad指令用于定义64位数值，Overview:
通用栈帧结构
当x86-64过程需要的存储空间超出寄存器能够存放的大小时，就会在栈上分配空间(这部分称为栈帧(stack frame))
x86-64最多可以使用寄存器来传递6个参数，超出部分需要在栈上传递(参数7~n，参数7位于栈顶)
叶子过程：所有的局部变量保存在寄存器中，而且该函数不会调用任何其他函数，即不需要栈帧
调用call指令时，会自动(i.e.不需要手动开辟栈帧)把返回地址(紧跟在call指令后的指令地址)压入栈中，ret指令会将压入的返回地址从栈中弹出并赋给PC
Frame pointer指向本函数的栈帧顶，每个函数的fp放在其后调用的函数的栈帧中；fp一般在backtrace或者是管理变长栈帧时要用到。
通过栈传递参数(注意不是局部变量)时，所有数据大小都向8的倍数对齐。
有的时候局部数据必须存储在栈上:
- 寄存器不足以存放所有本地数据
- 使用地址运算符&(取地址)的局部变量，要为它产生一个地址(寄存器存储的局部变量取不到地址)，因此必须存储在栈上。
- 某些局部变量是数组或结构体，必须通过数组或结构体引用被访问到。
callee save寄存器(被调用函数能保证它们的值不变，要么不使用，要么压栈保存)：rbx, rbp, r12~r15；caller save寄存器(意味着任何被调用函数都能修改它们)：除了上述寄存器以及rsp外的寄存器。
T D[R][C]的数组元素D[i][j]的内存地址为：$&D[i][j]=x_D+L(C\cdot i + j)$，其中L是数据类型T以字节为单位的大小，$x_D$为数组D的起始地址。
C语言编译器能够优化定长多维数组(比如说减少寄存器的使用或者减少分支判断，具体可以参考书本3.8.4)
变长数组。C99引入了一种功能，允许数组的维度是表达式(原本只能是常量)，在遇到这个数组的时候计算出数组的维度(因此变量定义的值必须要数组使用之前)
动态的版本(i.e.变长数组)必须使用乘法指令来对i伸缩n倍，而不能用一系列的移位和加法(移位只针对于2的幂次)。在一些处理器中，乘法会导致严重的性能处罚(编器件通过优化来避免生成我们上面计算地址的表达式从而避免乘法指令，具体看书本P182)。
C语言结构体(struct)的所有组成部分都存放在内存中一段连续的区域内；编译器维护关于每个结构体类型的信息，指示每个字段(field)(i.e. 属性)的字节偏移
C语言联合体(union)是用不同的字段来引用相同的内存块(进而节约内存空间)。e.g.数据结构中的二叉树，因为内部结点中不存放数据，而叶子节点中存放数据，就可以考虑使用union来节省内存空间。如下面代码所示，union一共只需要16个字节的内存空间。
1
2
3
4
5
6
7
union node_s {
struct {
struct node_s* left;
struct node_s* right;
}
double data[2];
};
计算机系统对数据对齐限制简化了形成处理器和内存系统之间接口的硬件设计。e.g.假设一个处理器总是从内存中取8个字节，则地址必须为8的倍数(这样就可以用一个内存操作来读或者写值了)，进而提高性能。
对齐原则是任何K字节的基本对象的地址必须是K的倍数。
编译器再汇编代码中插入指令.align，指明全局数据所需的对齐。e.g..align 8，这就保证了它后面的数据的起始地址是8的倍数。
编译器可能需要在字段的分配过程中插入Gap或者在末尾进行Padding。e.g.结构体数组struct S2 d[4]，结构体元素的可能会在末尾进行填充来保证接下来的结构体数组元素是对齐的。
void*类型代表通用指针，e.g.malloc函数返回void*类型，然后通过显示的强制类型转换或者赋值操作那样的隐式强制类型转换，来转换成有类型的指针
C语言表达式p+i，这里指针值为$p$，得到的地址计算为$p+L \cdot i$，$L$是与P相关的数据类型的大小
将指针从一种类型强制转换成另一种类型，只改变它的类型，而不改变它的值
函数指针的声明int (*f)(int*);，*f两边的括号是必要的，否则就会声明成int* f(int*)，既返回类型为int*的函数f。函数指针也是个指针，可以将函数名作为函数的起始地址存放到函数指针中。
C语言对于数组引用不进行任何边界检查，因此可能会因为越界的数组元素的写操作来破坏存储在栈上的状态信息(e.g.参数，返回地址)，这可能会导致ret指令将PC返回到未知的地址。

来看一个**缓冲区溢出(Buffer Overflow)**的例子，主要是因为用户输入的字符串的长度超出了为数组分配的空间

/* Implementation of library function gets() */
char *gets(char *s)
{
    int c;
    char *dest = s;
    while ((c = getchar()) != ’\n’ && c != EOF)
        *dest++ = c;
    if (c == EOF && dest == s)
        /* No characters read */
        return NULL;
    *dest++ = ’\0’; /* Terminate string */
    return s;
}
/* Read input line and write it back */
void echo()
{
    char buf[8]; /* Way too small! */
    gets(buf);
    puts(buf);
}

C语言中有一些库函数(e.g.fgets)是原始库函数的更安全的版本，它额外包括一个参数，限制待读入的最大字节数。
缓冲区溢出攻击的目的就是使执行的ret指令跳转到攻击代码(在缓冲区中)
病毒：用来指各种在系统间传播攻击代码的策略
对抗缓冲区溢出攻击常见的三种方式：栈随机化、栈破坏检测、限制可执行代码区域。
栈随机化使得栈的位置在程序每次运行时都有变化，通过在程序开始时在栈上分配一段0~n字节之间的随即大小的空间(程序不使用这段空间)。在Linux系统中，采用地址空间布局随机化(ASLR)，使得每次运行时程序中的程序代码、库代码、栈、全局变量和堆数据都被加载到内存的不同区域。
栈破坏检测能够检测到栈何时已经被破坏。因为在C语言中没有可靠的方法来防止对数组的写越界，最近的GCC版本在产生的代码中加入金丝雀(canary)来检测(在x86中为%fs:40使用fs数据段寄存器来进行段寻址，canary在段中标志为只读)。在恢复寄存状态和从函数返回之前，程序检查这个金丝雀值是否被该函数的某个操作或者该函数调用的某个函数的某个操作改变了(使用xorq指令来进行比较)，如果改变了，程序就会异常中止。最近的GCC版本会自动插入这种溢出检测(canary)。可以通过对局部变量的重新排列来提供更好的安全性(见201页)
限制内存区域中哪些区域能够存放可执行代码。许多系统允许三种访问形式：R、W、X。最近AMD和Intel处理器的内存保护引进了”NX”(No-Execute)位，将读和执行访问模式分开。这样一来栈可以被标记为可读和可写，但是不可执行(检查页是否可执行由硬件来完成，效率上没有损失)
alloca函数申请的是栈上的内存空间(与malloc不同)，用完会在退出栈时自动释放，来支持变长栈帧。为了支持变长栈帧能方便进行栈的释放，需要支持帧指针(frame pointer)来保存上一个栈帧顶的地址。x86中帧指针存放在rbp寄存器中，而RISCV将帧指针压到栈上。

浮点指令与SIMD相关的这一部分内容因为ICS课内就没有讲，所以我准备等真正用到的时候再系统地去学习。同时我打算抽空完成Attack Lab，巩固所学知识。