CSAPP笔记02程序的机器级表示（下）
CSAPP笔记02程序的机器级表示（下）
0x00 过程
过程是程序中一种重要的抽象，它将一段代码封装，可以传递参数和返回值，在程序的不同地方调用。
过程的表现形式多样，可以是函数（function）、方法（method）、子例程（subroutine）、处理函数（handler），不同的形式主要是功能不同。
要提供对过程的机器级支持，需要实现三个机制，假设P调用Q，Q执行后返回到Q:
①传递控制。在进入过程Q的时候，PC要能设置成Q的代码的起始地址，在返回时，要能返回到P的下一条指令。
②传递数据。P必须能向Q传递一个或者多个参数，而且Q能向P返回一个值。
③分配和释放内存。在开始时，要能给Q的局部变量分配空间，在Q结束时，能够释放这些空间。
为了减少过程调用的开销，只需要实现上面的三个机制即可。
运行时栈
函数的调用机制在于使用了栈数据结构的后进先处的内存管理原则，程序的栈既可以用来实现上述的三个机制（传递参数 分配占空间给局部变量，将返回地址存在栈中）。
当过程需要的储存空间超过了寄存器能够存放的大小后，就要分配栈空间来储存局部变量了。这个过程称为栈帧。
当过程P调用过程Q的时候，会把返回地址压入栈中，指明Q返回时要从P的哪个位置继续执行，这个返回地址时P的帧栈的一部分。
Q的代码会扩展当前栈的的边界，分配它的帧栈的空间，在这个空间中，用来保存寄存器的值，分配局部变量空间，为它的调用过程设置参数（也在栈中，函数的嵌套调用），大多数过程的帧栈都是定长的，在过程开始的时候分配好了（subq $size,%rsp）。但是有些过程需要变长的帧。
为了提高空间和时间效率，x86-64过程只分配自己所需要额帧栈（过程内调用的其他过程的不用负责）。实际上传递参数和局部变量都可以使用寄存器实现，而且寄存器的读写速度远远快于栈（内存）。
转移控制
将控制从过程P转移到过程Q，只需要将PC设置到Q的代码的起始位置。返回时处理器需要记录P过程内的继续执行的位置。
x86-64使用call指令来转移控制，call指令会将当前PC的地址压入栈，并将PC设置为被调用过程的其实地址。压入的地址称为返回地址，（call指令后面那条指令的地址）。对应的返回指令ret，会从栈中弹出一个地址，并将PC设置为该地址。
同jmp一样，call跳转的地址可以是直接给出的，也可以是间接给出的。（直接地址会写在编码里，间接地址则是寄存器里或者内存空间里）。
数据传送
当调用过程时，除了需要转移控制，还可能包括把数据作为参数传递，并且从过程返回时还有可能有一个返回值。
在前面的代码中，我们一直使用的是寄存器来传递参数，因为在两个过程切换时，通用寄存器是共用的，同样的也可以用通用寄存器来返回数据。
一般而言，使用以下6个寄存器来传递参数：
如果要传递的参数超过6个，那么需要用栈来传递，也就是将栈空间扩展（地址向下扩展）7-n参数的全部大小，然后将参数7-n依次写入（push）栈中。（一般而言，约定最右边的参数最先push，所以栈顶是最左边的参数。）
然后在被调用的过程里，通过访问调用过程的栈帧，即可读取参数（需要知道此时参数相对栈顶的偏移位置）。
栈上的局部储存
同样的，前面的代码使用局部变量时，都是使用寄存器保存。但是寄存器不够用时，需要使用栈空间来保存局部变量，有以下情况要使用栈空间来保存局部变量：
①寄存器不够用
②对一个局部变量要取地址”&”使用，因此必须放在内存（栈）里
③局部的数组或者结构，要通过地址偏移访问
通过减小栈顶指针，即可从栈上分配空间，分配的结果时栈帧的一部分，在过程结束的时候，重新给栈顶指针恢复，就可以释放分配的栈空间。
long caller(){
long arg1=534;
long arg2=100;
long sum=swap(&arg1,&arg2);
return sum;
}
caller:
subq $16,%rsp
movq $534,(%rsp)
movq $100,8(%rsp)
leaq 8(%rsp),%rsi
movq %rsp,%rdi
call swap
寄存器的储存空间
寄存器组时所有过程公用的资源，虽然在同一时刻只有一个过程时活动的（前台），但是我们必须保证被调用的过程不会覆盖调用者稍后使用的寄存器的值，为此，有如下约定：
寄存器%rbx %rbp 和%r12-%r15被划分为被调用者保存寄存器，也就是被调用者如果要修改这些寄存器，必须先保存，然后使用，使用完毕后恢复（在过程开始时push压入栈，结束前pop出栈，注意顺序相反）。
所有其他的寄存器，（除了栈指针），都是调用者保存寄存器，调用者如果需要这些值在调用后仍然存在，需要自己保存。
递归过程
由于实现的过程调用机制，我们可以用过程自己调用自己，和调用其他过程没有任何区别。这种调用自己的行为称为递归。
0x01 数组分配和访问
数组时一种将标量数据聚集成更大数据类型的方式。对于c语言，一块连续的内存空间即可作为一个数组，并且可以通过指针访问不同索引的元素。并且C语言支持指针运算，在机器代码中，会翻译成地址计算。
对于T A[n]，会在内存中分配一个sizeof（T）* n字节的连续的空间，A是一个指针，指向这个连续空间的首地址。通过索引i（0-n-1）来访问，对应的地址时A+i*sizeof(T).
指针运算
c语言允许对指针进行运算，而计算的结果要根据指针的大小进行伸缩。如果p是一个指向数据类型T的指针，那么p+i，对应的地址运算时x(p)+i * sizeof(T).
&操作符是给出该对象的一个指针，而*操作符是对指针的一个引用。同样 * (p+i),引用的是数组p的第i个元素。
嵌套数组
嵌套的数组，就是数组中的元素是数组，而数组本质是指针，所以，也就是一个数组里的每一个元素都是指针
int A[5] [3] ；对应是一个数组有5个元素，每个元素都是一个数组（指针），每个指针都指向自己所表示的数组的首地址。
也就是A[0]里保存的是Xa。对T D[R] [C]对应的数组元素D [I] [J]的内存地址为：X0+ L(C*i+J) * sizeof（T）
定长数组
针对下面的c代码：
for(j=0;j<n;j++){
result+=A[i][j]*B[j][k];
}
这种数组访问规律，可以发现，访问的总是A[i]指针对应的数组，因此编译器会提前算出A[I]指针的值，也就是A[I]对应数组的首地址。而不是每次都用公式 Xa+ sizeof（T）* （i*n+j）来算地址。对应的优化后的c语言：
int *Aptr=&A[i][0]
int *Bptr=&[0][k]
do{
result+=*Aptr * *Bptr
Aptr++;指针运算，指向下一个元素
Bptr+=N;指针运算，指向下N个元素，扩展成二维即使下一行同列
}while (Bptr!=Bend)
变长数组
C99引入了变长数组，即在编译时维度（宽度）未定，运行时才确定。
int var_ele(long n,int A[n][n],long i,long j){
return A[i][j];
}
参数n必须在A[n] [n]前面，这样才能计算出数组的维度。
var_ele:;n in %rdi,A in %rsi,i in %rdx,j in %rcx
imulq %rdx,%rdi;caculate n*i
leaq (%rsi,%rdi,4),%rax;计算 A[i][0]的首地址
movl (%rax,%rcx,4),%eax;将A[i][j]地址处的内容读到eax,因为结果是int
ret
变长数组相对于定长数组，主要是由于维度在寄存器或者内存空间里，编译器无法在计算地址是利用leaq来算，而要用imul，但是乘法计算的代价是很高的。
但是同样的，对于多次访问二维数组T A[5] [k]，（k是变动的）处理器也会和定长数组一样优化成A[5] [0] + K * sizeof（T），而不是每次都重新计算。
0x02 异质的数据结构
c语言有两种将不同类型的对象组合到一起创建新数据类型的机制，结构（struct），将多个对象集合到一个单位里；联合（union），用多种数据类型来引用一个对象。
结构struct
struct将不同的（也可以相同呀~）数据类型聚合到一个对象中，用名字来引用组成该结构的各个部分。类似于数组，该对象内的各个部分在一个连续的内存中，通过偏移来访问/引用各个部分。
struct rec{
int i;
int j;
int a[2];
int *p;
}new_rec;
//rec是构建的新类型 后面可以用struct rec来创建
//new_rec是创建时即声明的一个变量，类型就是struct recSS
这个结构的各个字段的偏移如上图，要产生一个指向结构内部某个字段的指针，只需要该结构struct的地址加上在结构内的偏移。
联合
联合提供一种机制，以多种类型来引用一个对象（内存块/内存对象）。
对于下面的声明：
struct S3{
char c;
int i[2];
double v;
}
union U3{
char c;
int i[2];
double v;
}
这两个类型对应的对象在x86-64 linux机器上编译时，各个字段的偏移和对象的完整大小如下：
先看S3的各个字段，发现偏移很奇怪，比如i的偏移，为啥不是1？ 即使i的偏移时4，那么v的偏移为什么不是4+8=12？ 最后大小时24？
实际上，这和数据对齐有关，将在下面讲到。
再看U3，每个字段的偏移都是0，也就是说，实际上对每个字段的引用都是从对象的基地址开始的，因此对一个对象里一个字段的修改会同时改变其他字段。（联合对象字段的使用是互斥的）
利用联合，可以实现数据转换（不是数值相同转换用其他数据类型表示，而是二进制位不变，显示其他类型的数值）。如利用联合来显示一个double数据对应的unsigned long的值：
unsigned long double2bits(double d){
union{
double d;
unsigned long u;
}temp;
temp.d=d;
return temp.u;
}
反过来干也可以。由于是二进制位的表示，因此需要注意字节序。
数据对齐
主流的计算机系统对基本数据类型的合法地址做出了限制，要求某种数据类型对象的地址必须是某个值K（通常是2、4、8）的倍数，这是数据对齐。
它的好处是简化数据的读取，设想下，一个8字节的数据，如果地址不是8的倍数，那么该数据可能分置在两个8字节的内存块中间，需要读取两次。（猜测底层数据是每8字节一读，毕竟64位。）
无论数据是否对齐，x86-64硬件都能正常工作，但是Intel建议对齐数据以提高内存性能。对齐原则是任何K字节的基本对象的地址必须是K的倍数。
以下为确保对齐的要求：
①确保每种数据类型都是按照指定的方式来组织和分配，即每种类型的对象都满足它的对齐限制，就可以保证数据对齐。
②对于全局数据（所有数据对齐后形成的内存块）的起始地址，可以通过.align N来声明起始地址是N的整数倍。如.align 8保证了语句后面的数据的起始地址是8字节的整数倍。
③对于包含结构（struct）的数据，编译器可能会在字段的中间插入间隙，以保证每个结构元素都满足它的对齐要求。而且结构的最终大小N，又要求该结构的起始地址是N的整数倍。
struct S1{
int l;
char c;
long lg;
}
S1中，lg字段大小为8字节，那么要求8字节对齐（先不考虑S1的起始地址，应当认为其满足8字节对齐），c字段由于大小为1，没有对齐要求，l字段处于开头，其对齐要求总是满足的。因此最后编译器会在c字段后面插入3字节空白（0x00），使得lg字段偏移为8，这样sizeof（S1）结果是16而非13。值得注意的是，确定S1大小为16后，那么S1的起始地址要求是16的倍数。
通过交换字段的顺序，可以不在字段间插入空白就满足对齐要求，不过仍然可能会被插入空白！！！
struct S2{
long lg;
int ;
char c;
}
上面的结构S2，按理说每个字段原本地址对齐，应该不需要再插入空白了，也就是sizeof(S2)应该是13。但是实际上，最终还是16。为什么呢？
考虑由该结构struct生成的数组 struct S2 D[4] .如果S2是13字节，D的起始地址是Xd，那么考虑第二个结构D[1],它的lg字段的地址Xd+13，显然不是其字段长度的整数倍，因此不满足对齐。其余的字段也可能不对齐。
因此，编译器还是在S2的c字段的后面加上3字节0x00，最终大小16。
拓展 任何内存分配函数malloc alloca（alloca在栈上分配空间），都要求返回的地址是16的整数倍。大多数函数的帧栈的边界都必须是16字节的倍数。
0x03 关于指针
对于指针，有以下关键点帮助理解：
①每个指针都有一个类型，这个类型由编译器维护，最终在机器代码中通常以指针的步长来反映。char *代表该指针指向的对象是一个char类型 void * 则是通用指针。
②每个指针都有一个值，指针是变量的一种类型，变量必有值，所以指针也有值，指针的值就是指向的对象的起始地址。
③运算符” & “ 用于取变量的地址，也就是变量实质是一个内存单元（如果不是用寄存器保存的话），我们用这个变量的值，是使用该内存单元里的值，而用 “ & “则是拿到该内存单元的起始地址。
④运算符” * “，用于 间接引用 指针，何谓间接引用？直接引用指针是用指针的数值，间接引用是用该数值对应的地址里的数据/对象
⑤数组与指针联系紧密，数组的名字就如同一个指针变量（类型即是该数组的类型），数组的索引和指针的运算相符合。a[3]与*(a+3)都是指向同一个对象。
int a[]={11234,2,3};
printf("%d\n",*a);//运行结果为11234
⑥将指针从一种类型转换成另一种类型，只改变类型，不改变指针的值.
也就是我们可以通过修改指针类型来改变同一个二进制数据的表示形式
double b=123.0;
long* a=&b;
printf("%ld",*a);//4638355772470722560
上面的代码和我们之前用union实现的转换效果是一样的。
⑦指针也可以指向函数（不多介绍，用的少，本质是指针的值作为跳转地址？）
内存越界引用与缓冲区溢出
①c对数组引用不做任何的边界检查（需要代码编写者自己保证）②局部变量和状态信息（例如保存的寄存器值和过程的返回地址）都在栈中。
上述两种特性导致c程序容易发生严重的错误（局部数组的内存越界引用，进一步，可能修改了栈内的状态信息，比如返回地址，导致代码的运行流程改变），我们称为缓冲区溢出
为什么会发生这种错误呢？因为栈是向下扩展的，程序位于某个过程时（这是常态），分配了一个数组作为缓冲区，那么该缓冲取缓冲区由使用者写入，如果没有进行写入大小检测，那么导致数组越界，向上写数据，最终可以覆盖栈里保存的过程的返回地址，改变程序的行为，进一步的，写入的数据里包含指令，覆盖的，新的返回地址指向这些指令，那么使用者就可以任意控制程序的行为。
gcc的汇编代码，可以发现给echo栈帧分配了24字节：
可以看到上面的echo函数，分配了8字节的缓冲区，并由用户写入缓冲区，但是没有对用户写入的大小进行限制。正常的输入，栈空间如上图。
如果输入大小远远超过echo函数分配的栈帧大小（图上是24字节），那么数据就会覆盖echo的返回地址。
对抗缓冲区溢出攻击
让程序员写出没有bug的代码是不现实的：），所以要求每个缓冲区都能检测大小也是不现实的。
因此，这里有一些除了杀一个程序员祭天以外的其他机制来对抗缓冲区溢出攻击。
①栈随机化，对于有缓冲区溢出漏洞的程序来说，攻击者往缓冲区里写入一大段数据，这些数据里有攻击者要执行的指令，通过覆盖返回地址，跳转到攻击者的指令，但是前提是攻击者知道自己的指令的地址，也就是，他得知道当前栈的栈顶地址（或许你会问到，%rsp里不就有吗？攻击者访问以下不就知道了？问题是，他要先填新的返回地址，没填新的返回地址，怎么能执行他的指令？）。
如果操作系统每次都给同一个程序分配的栈地址是相同的，那么攻击者用gdb等调试工具就可以拿到运行到缓冲区时的栈顶地址了。所以操作系统使用了栈随机化，具体实现是，每次程序开始时，用户程序栈的栈顶本来是相同的，但是操作系统先给用户程序栈里写入随机大小的数据，改变程序开始时的栈顶。这样，每次程序运行，该缓冲区的地址都是不同的。
②栈破坏检测，栈破坏的原理是，程序给缓冲区/数组边界加上哨兵，在恢复寄存器和执行过程返回之前，程序检测该哨兵是否被修改，如果修改，就直接退出。这些是由编译器实现的，并不需要c语言程序编写者实现。
最近的版本的gcc会试着检测一个函数是否容易遭受缓冲区溢出攻击，如果容易，就自动插入这种溢出检测机制。实际上，我们要展示前面那个echo函数的栈溢出，需要使用如下命令编译：
gcc -fno-stack-protector
③限制可执行代码区域，攻击者插入的执行代码，在栈里，而栈在内存中的位置和程序的代码的位置基本不在一个物理页。现在的处理器已经支持标记物理页是否可执行了（No-Execute,NX机制），主流操作系统已经支持这个特性了，允许程序标记哪些自己的虚拟地址空间中哪些地方不可以执行，然后在对应的物理页里标记。
最近gcc已经为我们的程序默认开启了这个机制，栈不可执行，如果想关闭以展示缓冲区溢出攻击，可以使用以下命令：
gcc -fno-stack-protector -z execstack
变长栈帧
在前面的代码中，栈帧的大小在编译时都能够确定，称为定长栈帧。但是有些函数中，需要的局部储存的大小是变化的。例如调用alloca函数从栈分配空间，或者在函数中定义了变长数组（运行时确定数组长度）。例如下面的代码：
long vframe(long n,long idx,long *q){
long i;
long *p[n];
p[0]=$i;
for(i=1;i<n;i++){
p[i]=q;
}
return *p[idx];
}
编译的汇编代码：
由于数组长度不定，编译时无法确定分配的长度。另外，由于要使用i的地址，因此局部变量i也是用栈分配的空间而不是寄存器保存。
为了管理变长栈帧，x86-64代码用寄存器%rbp作为帧指针（frame pointer），又称为基指针（base pointer）。%rbp是一个被调用者保存的寄存器，然后在函数的整个过程中，都使得%rbp指向当时的栈顶位置。然后所有对栈内空间的引用，都是相对于%rbp的偏移。
上图中，先分配了16字节占空间，8字节给变量i，8字节未使用。然后根据n计算数组需要的大小，再分配空间，最后使用leave指令，该指令相当于movq %rbp，%rsp popq %rbp。恢复%rsp，收回分配的栈空间。
可以看到%rbp作为帧指针，负责保存当前过程栈帧的开头位置，最后回到开头。因此被调用函数，为了保证调用函数能够顺利恢复它的栈帧，需要在开头用push %rbp保存，最后在返回前恢复成调用函数的栈帧开头。
