CSAPP第三章知识点归纳（程序的机器级表示）（还未结合ppt，之后结合了补上）

---

基本概念

• 指令集体系结构（指令集架构）：定义机器级程序的格式和行为，它定义了处理器状态、指令的格式，以及每条指令对状态的影响

---

程序编码

• 机器代码可见的处理器状态：

  • 程序计数器PC %rip （给出下一条要执行的指令的地址）
  • 整数寄存器文件 16个 64位的
  • 条件码寄存器
  • 一组向量寄存器，存放一个或多个整数或者浮点数值

• 

  上面这一条中 -Og表示生成的代码符合原始程序的结构，-S表示生成汇编代码

• 汇编代码中所有以“.”开头的行都是指导汇编器和链接器工作的伪指令

  	.file	"010-mstore.c"
  	.intel_syntax noprefix
  	.text
  	.globl	multstore
  	.type	multstore, @function
  multstore:
  .LFB0:
  	.cfi_startproc
  	push	rbx
  	.cfi_def_cfa_offset 16
  	.cfi_offset 3, -16
  	mov	rbx, rdx
  	call	mult2
  	mov	QWORD PTR [rbx], rax
  	pop	rbx
  	.cfi_def_cfa_offset 8
  	ret
  	.cfi_endproc
  .LFE0:
  	.size	multstore, .-multstore
  	.ident	"GCC: (Ubuntu 4.8.1-2ubuntu1~12.04) 4.8.1"
  	.section	.note.GNU-stack,"",@progbits
  
  

数据格式

• 再次回顾一下字节大小

访问信息

• x86-64 CPU的16个存储64位值得通用目的寄存器

• 移动指令以寄存器为目标的时候得规则：生成1字节和2字节数字得指令会保持剩下得字节不变；生成4字节数字的指令会把高位4字节置为0。（后面这条规则是作为从IA32到x86-64的扩展的一部分而采用的）

操作数指示符

• 操作数分成3种类型：
  1. 立即数：以“$”后面跟一个整数表示 如 $0x34 或者 $-544
  2. 寄存器：表示寄存器的内容
  3. 内存引用：根据计算的有效地址访问某个内存位置

寻址模式（重点）

数据传送指令

• 源操作数指定的值是一个立即数，存储在寄存器种或内存中

• 目的操作数为内存位置or寄存器

• x86-64的限制：传送指令的两个操作数不能都指向内存位置

• movl 指令以寄存器作为目的时，会把该寄存器的高位4字节设置为0（x86-64惯例，任何为寄存器生成32位值的指令都会把该寄存器的高位部分置成零）

• 常规的movq指令只能表示为32位补码数字的立即数作为源操作数，然后把符号扩展到64位的值，放到目标位置。movabsq指令能够以任意**64位立即数作为源操作数，并且只能以寄存器**作为目的

• 下面的是零扩展指令（其中由四字节到八字节扩展用movl指令）

• 下面的是符号扩展指令（其中的cltq指令与movslq %eax ,%rax效果一样，但是编码更紧凑）

压入和弹出栈数据

• 惯例：栈是倒过来画得，栈顶在图的底部，

• 栈指针**%rsp**保存着栈顶元素的地址（注意这里的顺序是push先栈指针减，后入栈）

算术和逻辑操作

• leaq没有其他大小的变种，因为是设计来对对地址进行操作的（其他的例如add有addb、addl、addw、addq）

• 整数算术操作如下

  • 其中第二组中的是一元操作数，既是源又是目的
  • 第三组中的是二源操作数，左边的是源，右边的既是源也是目的
  • 最后一组中的是移位操作，移位量可以是一个立即数，或者是放在单字节寄存器%cl中（这些指令只允许以这个寄存器作为操作数）（移位操作对w位长的数据值进行操作，位移量是由%cl寄存器的低m位决定的，其中$ 2^m=w $​,高位会被忽略）

• 加载有效地址指令

  • 不从指定的位置读入数据，没有引用内存，而是将有效地址写入到目的操作数
  • 下面图中计算z*12要分两步是因为比例因子只能是1、2、4、8

特殊的算术操作

• clto，无操作数，隐含读出%rax的符号位，并将它复制到%rdx的所有位

• imulq和mulq指令要求一个参数必须在寄存器%rax中，另一个作为指令的源操作数给出，结果高64位放在%rdx中，低64位放在%rax中（汇编器通过计算操作数的数目来区分用哪条指令）

控制

条件码

• 最常用的条件码如下：

• leaq指令不改变任何条件码，因为它是用来进行地址计算的（除此之外，其他的运算指令都会设置条件码）

• 对于逻辑操作，进位标志和溢出标志会设置成0

• 对于移位操作，进位标志将设置为最后一个被移除的位，而溢出标志被设置成0

• INC和DEC指令会设置溢出和零标志，但是不会改变进位标志

• 下面的指令只设置条件码而不改变其他的任何寄存器

这里注意的是cmpq的比较是$ S_2 $和$ S_1 $比较

比如

cmpq	%rsi,%rdi
setl	%al
movzbl	%al,%eax
ret

这里面setl判断的是%rdi中的值是否是小于%rsi中值

• 条件码不能直接读取，一般通过以下的方法：

• 根据条件码的某种组合，将一个字节设置为0或1（注意区分表中有符号和无符号的指令后缀区别）

• 条件跳转到某个其他部分

• 条件传送指令

跳转指令

• 直接跳转和间接跳转：直接跳转的跳转目标是作为指令的一部分编码的（e.g. jmp .L1）；间接跳转跳转目标是从寄存器或内存位置中读出的（ jmp *(%rax)）

  跳转指令：

  

注意：条件跳转只能是直接跳转

• 执行pc相对寻址时，程序计数器的值是跳转指令后面的那条指令的地址。而不是跳转指令本身的地址

用条件控制实现条件分支

• C语言中的if-else语句的通用形式模板如下：

汇编通常会使用的相应的控制流如下：

用条件传送来实现条件分支

• 条件传送指令：

（同条件跳转不同，处理器无需预测测试的结果就可以执行条件传送。处理器只是读源值，检查条件码，然后可能更新目的寄存器，可能保持不变）

要注意的是条件传送只有在一定的条件下才可以使用，因为他是计算了两个分支的值，如果分支中有别的作用，就会导致错误，这时候只能使用条件控制分支，例如下面这种：（分支中分别有lt_cnt的增加一）

long absdiff_se(long x, long y)
{
    long result;
    if (x < y) {
	lt_cnt++;
	result = y - x;
    }
    else {
	ge_cnt++;
	result = x - y; 
    }
    return result;
}
//下面这种也是不可以使用条件传送的，因为如果xp不存在，它会间接引用空指针
long cread(long *xp)
{
   return (xp?*xp:0);
}

循环

do-while循环

• 相应的goto语句：

• 例子：

long fact_do(long n)
{
    long result = 1;
    do {
	result *= n;
	n = n-1;
    } while (n > 1);
    return result;
}

• 相应的汇编代码：

fact_do:
	movl	$1, %eax
.L2:
	imulq	%rdi, %rax
	subq	$1, %rdi
	cmpq	$1, %rdi
	jg	.L2
	rep; ret

while循环

• 通用形式：
  

• 有两种形式：

  • 跳转到中间：

• guarded-do：

• 例子：

  long fact_while(long n)
  {
      long result = 1;
      while (n > 1) {
  	result *= n;
  	n = n-1;
      }
      return result;
  }
  

  ;跳转到中间
  fact_while:
  	movl	$1, %eax
  	jmp	.L5
  .L6:
  	imulq	%rdi, %rax
  	subq	$1, %rdi
  .L5:
  	cmpq	$1, %rdi
  	jg	.L6
  	rep; ret
  	
  ;guarded-do
  fact_while_gd_goto:
  	cmpq	$1, %rdi
  	jle	.L23
  .L21:
  	movl	$1, %eax
  .L22:
  	imulq	%rdi, %rax
  	subq	$1, %rdi
  	cmpq	$1, %rdi
  	jne	.L22
  	rep; ret
  .L23:
  	movl	$1, %eax
  .L20:
  	ret
  

利用guarded-do可以优化初始测试的条件

此题目多做做理解：

for循环

• 通用形式

• C语言描述

GCC为for循环产生代码是while循环中的一个，取决于优化等级，如下

跳转到中间：

guarded-do：

switch语句（重点易忘）

• 特征：使用跳转表来确定跳转指令的地址，执行开关语句的时间与开关数量无关

• 例子：

  void switch_eg(long x, long n,
  	       long *dest)
  { 
      long val = x; 
  
      switch (n) { 
  
      case 100: 
  	val *= 13; 
  	break; 
  
      case 102: 
  	val += 10; 
  	/* Fall through */ 
  
      case 103: 
  	val += 11; 
  	break; 
  
      case 104: 
      case 106: 
  	val *= val; 
  	break; 
  
      default: 
  	val = 0;       
      } 
      *dest = val; 
  } 
  

  翻译到扩展的C语言版本（其中“&&”指的是指向代码位置的指针）

  void switch_eg_impl(long x, long n,
  		    long *dest)
  {
      /* Table of code pointers */
      static void *jt[7] = {//line:asm:switch_jumptable
  	&&loc_A, &&loc_def, &&loc_B,
  	&&loc_C, &&loc_D, &&loc_def,
  	&&loc_D
      }; 
      unsigned long index = n - 100; 
      long val; 
  
      if (index > 6)
  	goto loc_def; 
      /* Multiway branch */
      goto *jt[index]; //line:asm:switch:c_jump
  
   loc_A:    /* Case 100 */ 
      val = x * 13; 
      goto done;
   loc_B:    /* Case 102 */
      x = x + 10;
      /* Fall through */
   loc_C:     /* Case 103 */
      val = x + 11;
      goto done;
   loc_D:    /* Cases 104, 106 */ 
      val = x * x;
      goto done;
   loc_def:  /* Default case */
      val = 0;
   done:
      *dest = val;
  } 
  

  相应的汇编语言版本：

  （其中jmp *.L4(,%rsi,8) 中的*表明这是一个间接跳转）

  switch_eg:
  	subq	$100, %rsi          #   Compute index = n-100
  	cmpq	$6, %rsi	    #   Compare index:6
  	ja	.L8 		    #   If >, goto \texttt{loc_def}
  	jmp	*.L4(,%rsi,8)       #   Goto *jt[index] # line:asm:switch:s_jump
  /* $end 230-switch-s 5 */
  /* $begin 230-switch-jt 10 */
  	.section	.rodata
  	.align 8         # Align address to multiple of 8 # line:asm:switch:align
  /* $end 230-switch-jt 10 */
  	.align 4
  /* $begin 230-switch-jt 13 */
  .L4:
  	.quad	.L3	 # Case 100: loc_A
  	.quad	.L8	 # Case 101: loc_def
  	.quad	.L5	 # Case 102: loc_B
  	.quad	.L6	 # Case 103: loc_C
  	.quad	.L7	 # Case 104: loc_D
  	.quad	.L8	 # Case 105: loc_def
  	.quad	.L7	 # Case 106: loc_D
  /* $end 230-switch-jt 13 */
  	.text
  /* $begin 230-switch-s 22 */
  .L3:	  		            # \texttt{loc_A:}
  	leaq	(%rdi,%rdi,2), %rax #   3*x
  	leaq	(%rdi,%rax,4), %rdi #   val = 13*x
  	jmp	.L2                 #   Goto \texttt{done}
  .L5:				    # \texttt{loc_B:}
  	addq	$10, %rdi           #   x = x + 10
  .L6:		     		    # \texttt{loc_C:}
  	addq	$11, %rdi	    #   val = x + 11
  	jmp	.L2  		    #   Goto \texttt{done}
  .L7:				    # \texttt{loc_D:}
  	imulq	%rdi, %rdi	    #   val = x * x
  	jmp	.L2   		    #   Goto \texttt{done}
  .L8:				    # \texttt{loc_def:}
  	movl	$0, %edi	    #   val = 0
  .L2:		    		    # \texttt{done:}
  	movq	%rdi, (%rdx)	    #   *dest = val
  	ret	      		    #   Return
  

  （一定要看书上练习题3.31，多练习，不然很容易忘了怎么做的）

---

过程

• 相关的机制（假设过程P调用过程Q）
  • 传递控制：在进入过程Q的时候，程序计数器必须被设置成Q的代码的起始地址，然后在返回时，要把程序计数器设置为P中调用Q后面那条指令的地址
  • 传递数据：P必须能够向Q提供一个或多个参数，Q必须能够向P返回一个值
  • 分配和释放内存：在开始时，Q可能需要为局部变量分配空间，而在返回前，又必须释放这些存储空间

运行时栈（重点）

• 过程需要的存储空间超出寄存器能够存放的大小时，就会在栈上分配空间，这个部分称为过程的栈帧
• 通过寄存器，过程P可以传递最多6个整数值，超出6个则P可以在调用Q之前在自己的栈帧里存储好这些参数

转移控制

• 相关的指令：

• CALL指令将返回地址压入栈中，并将PC设置为Q的起始地址

• RET指令从栈中弹出地址，并把PC设置为返回地址

• 下面的示例可看可不看（忘了就看看！）

  

数据传送

• x86-64中寄存器最多可以传递6个整型参数，寄存器的使用有特殊的顺序（背下面的表），寄存器的名字取决于要传递的数据类型的大小

• 如果函数的参数大于6个，超过部分通过栈来传递，参数7~n放在栈上，参数7位于栈顶，通过栈传递参数，所有数据大小都向8的倍数看齐（参数位于调用者的参数构造区中）

  

栈上的局部地址

• 局部数据必须存放在内存中的情况：

• 通过减小栈指针在栈上分配空间，分配结果为栈帧的一部分，标号“局部变量”（注意区分哪些变量需要通过栈帧来传递，如传递的参数为局部变量的地址，就需要在内存中保存）

• 一个复杂的例子（P171）

寄存器中的局部存储空间（重要）

• 寄存器**%rbx**、%rbp和**% r12**~%r15被划分**被调用者保存寄存器**。当过程P调用过程Q时，Q必须保存这些寄存器的值（保证在调用前后是一致的）（通过push进栈中和ret前pop出来）
• 所有其他的寄存器，除了栈指针**%rsp**，都分类为调用者保存寄存器，任何函数都可以修改它
• P175递归函数的练习题3.35很容易做错，多做做！

数组分配和访问

• 表示对象的表达式Expr，&Expr是给出该对象地址的一个指针；表示地址的表达式AExpr，AExpr给出该地址处的值。（Expr和*&*Expr** 是等价的）

• 假设整形数组E的起始地址和整数索引i分别存放在寄存器%rdx和%rcx中，下面是对数组相关的访问表达式（其中结果存放在**%eax**中（数据），或者%rax中（指针））

  

嵌套数组

int A[5][3];
//等价于下面的式子
typedef int row3_t[3];
row3_t A[5];

• 对应关系

  

• 访问数组元素的地址为

• 定长数组的优化，就是把指针去掉了，通过末尾元素的指针来判断是否到达结尾

  • 原始的C代码

    int fix_prod_ele (fix_matrix A, fix_matrix B, long i, long k) {
        long j;
        int result = 0;
    
        for (j = 0; j < N; j++)
    	result += A[i][j] * B[j][k];
    
        return result;
    }
    

  • 优化过的C代码

    int fix_prod_ele_opt(fix_matrix A, fix_matrix B, long i, long k) {
        int *Aptr = &A[i][0];    /* Points to elements in row i of A    */ // line:asm:fixprodele:c:aptr
        int *Bptr = &B[0][k];    /* Points to elements in column k of B */
        int *Bend = &B[N][k];    /* Marks stopping point for Bptr       */ // line:asm:fixprodele:c:bend
        int result = 0;
        do {                          /* No need for initial test */
    	result += *Aptr * *Bptr;  /* Add next product to sum  */
    	Aptr ++;                  /* Move Aptr to next column */
    	Bptr += N;                /* Move Bptr to next row    */
        } while (Bptr != Bend);       /* Test for stopping point  */
        return result;
    }
    

  • 相关的汇编代码

    

变长数组（感觉应该不重要）

• C99引入的新功能，允许数组的维度是表达式，在数组被分配的时候才计算出来

  //可以声明以下数组
  int A[expr1][expr2];
  //函数参数可以如下，其中n一定要在多维数组之前
  int var_ele(long n,int A[n][n],long i,long j){
     return A[i][j];
  }
  

---

异构的数据结构

结构

• 访问结构元素： rp->width 等价于 (*rp).width

• 结构具体的结构如下

  

  相对应的存储方式

  

---

联合

• 与结构相对应的比较

• 

---

数据对齐（重要）

• 对齐原则：任何K字节的基本对象的地址必须是K的倍数

  

• 其中struct中各字段需要满足对其的要求（而且要满足在数组中的时候每个结构的对其要求都是满足的），例如：

  struct S1 {
     int i;
     char c;
     int j;
  }
  //上面的结构需要下面的对齐
  

  

• 对于数组的，考虑如下结构：

  
  

  相对应的对其要求如右边，这样，在之后的结构中，每个元素都满足对齐的要求

---

在机器级程序中将控制与数据结合起来

• 指向函数的指针（容易忘，顺便记一下）（函数指针的值是该函数机器代码表示中第一条指令的地址）

  //函数声明
  int fun(int x,int *p);
  //创建指针fp，并赋值为上面的函数
  int (*fp)(int ,int *);
  fp = fun;
  //用函数指针来调用函数
  int y=1;
  int result=fp(3,&y);
  

---

内存越界引用和缓冲区溢出（重要）

缓冲区溢出原理

• 在栈中分配某个字符数组来保存一个字符串，但是字符串的长度超出了为数组分配的空间，如下所示：

  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);
  }
  

  上面只给buf分配了8个字节，所以只要超过8个字节，栈上的缓冲区就会溢出，可能覆盖栈上其他的信息（如覆盖返回地址、调用者的栈帧中保存的信息等等）

• 通常，输入给程序一个字符串，其中包含一些可执行代码的字节编码，称为攻击代码，还有一些字节会用一个指向攻击代码的指针覆盖返回地址

对抗缓冲区溢出攻击（重要）

1. 栈随机化：栈随机化的思想使得栈的位置在程序每次运行时都有变化，许多机器都运行同样的代码，但是他们的栈地址都是不同的。

   实现方式：程序开始时，在栈上分配0~n字节之间的随机大小的空间，程序不使用这段空间，但是它会导致程序每次执行时后续的栈位置发生变化，分配范围n必须足够大，才能获得足够多的栈地址变化，但是又要足够小，不至于浪费程序太多的空间

   • linux中，栈随机时一类技术的一种——地址空间布局随机化（ASLR），使用ASLR，程序不同部分（程序代码，库代码，栈，全局变量和堆数据都会被加载到内存的不同区域）

2. 栈破坏检测：在栈帧中任何局部缓冲区与栈状态之间存储一个特殊的**金丝雀值（这是栈保护者机制），也成为哨兵值**，程序每次运行时随机产生的，在恢复寄存器状态和从函数返回之前，程序检查这个金丝雀值是否被该函数的某个操作改变了，如果是，程序异常终止

   

   这段汇编运用了金丝雀值（好好品味）

3. 限制可执行代码区域：限制哪些内存区域能够存放可执行代码，在典型的程序中，只有保存编译器产生的代码的那部分内存才需要可执行，其他部分可以被限制为只允许读和写

支持变长栈帧（GCC版本放弃了这个惯例）

• 简单说就是用%rbp来保存原来的栈指针，然后将栈指针减小来在栈中申请空间，用完之后通过将%rsp设置为%rbp（栈原来的指针）即可
• P203 练习题3.49很经典，涉及对齐等问题，多看看

浮点代码（考纲没有？简单归纳一下）

• Intel和AMD引入的媒体指令，这些指令本意是允许多个操作以并行模式执行，称为单指令多数据SIMD

• 发展：MMX 到SSE（Streaming SIMD Extension）流式SIMD扩展 到 最新的AVX(Advanced Vector Extension 高级向量扩展)

• 媒体寄存器：

  

• 浮点传送指令（指令中的‘a’表示align（对齐的））

  

  

  

过程中的浮点代码

• XMM寄存器**%xmm0~%xmm7**可传递8个浮点参数，可通过栈传递额外的浮点参数
• 函数使用**%xmm0**来返回浮点值
• 所有的XMM寄存器都是调用者保存

浮点运算操作指令

• 下面是AVX2浮点指令，每条指令有一个（$ S_1$）或两个（$ S_1\ S_2 $）源操作数，和一个目的操作数D。第一个源操作数$ S_1 $可以是一个XMM寄存器或一个内存位置。第二个源操作数和目的操作数都必须是XMM寄存器

  

浮点代码中的位级操作（三个操作数都是XMM寄存器）

浮点比较操作（$ S_2 $必须在XMM寄存器中，$ S_1 $可以是XMM寄存器或者内存）

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-4ZI4PJPt-1643164735156)(CSAPP第三章知识点归纳.assets/image-20210816004747411.png)]

• 三个标志位的效果：

• 在C语言中有参数NaN，就认为比较失败，奇偶标志位用于发现这样的条件（奇偶标志位在x86代码中不常见）

• 浮点传送指令（指令中的‘a’表示align（对齐的））

  

过程中的浮点代码

• XMM寄存器**%xmm0~%xmm7**可传递8个浮点参数，可通过栈传递额外的浮点参数
• 函数使用**%xmm0**来返回浮点值
• 所有的XMM寄存器都是调用者保存

浮点运算操作指令

• 下面是AVX2浮点指令，每条指令有一个（$ S_1$）或两个（$ S_1\ S_2 $）源操作数，和一个目的操作数D。第一个源操作数$ S_1 $可以是一个XMM寄存器或一个内存位置。第二个源操作数和目的操作数都必须是XMM寄存器

  

浮点代码中的位级操作（三个操作数都是XMM寄存器）

浮点比较操作（$ S_2 $必须在XMM寄存器中，$ S_1 $可以是XMM寄存器或者内存）

• 三个标志位的效果：

• 在C语言中有参数NaN，就认为比较失败，奇偶标志位用于发现这样的条件（奇偶标志位在x86代码中不常见）
• P215练习题涉及了所有浮点知识点，复习时有空做一遍即可