CSAPP / CSE 351 学习笔记（机器级表示 & 汇编语言 Assembly）

汇编代码是机器代码的文本表示，给出程序中的每一条指令。通过阅读汇编代码，我们能够理解编译器的优化能力，并分析代码中隐含的低效率。与机器代码相比，汇编代码的主要特点是它用可读性更好的文本格式表示。

源代码与对应的汇编代码的关系通常不太容易理解——就像要拼出的拼图与盒子上图片的设计有点不太一样。这是一种逆向工程（reverse engineering）——通过研究系统和逆向工作，来试图了解系统的创建过程。

历史观点

Intel 处理器系列俗称 x86，经历了一个长期的、不断进化的发展过程。开始时，它是第一代单芯片、16 位微处理器之一，由于当时集成电路技术水平十分有限，其中做了很多妥协。

Intel CPU 历史：

CPU	Date	#Transistor	MHz	Feature
8086	1978 年	29K	5-10	第一代单芯片、16 位微处理器之一
i386	1986 年	275K	16-33	IA32，增加了平坦寻址模式（flat addressing model），Intel 第一台全面支持 Unix 的机器
Pentium 4E	2004 年	125M	？	超线程（hyperthreading）、x86-64
Core 2	2006 年	291M	？	第一个多核微处理器（不支持超线程）
Core i7，Nehalem	2008 年	781M	？	多线程、多核

AMD（Advanced Micro Devices）在技术上紧跟 Intel，执行的市场策略是：生产性能稍低但是价格更便宜的处理器（slower, but cheaper）。2002 年，AMD 的处理器变得更加有竞争力，它们率先突破了可商用微处理器的1 GHz 的时钟速度屏障，并且引入了广泛采用的 IA32 的 64 位扩展 x86-64（AMD64）。

AMD usually applies aggressive designs.

程序编码

对于机器级编程来说，其中两种抽象尤为重要。第一种是指令集体系结构或指令集架构（Instruction Set Architecture，ISA）来定义机器级程序的格式和行为，它定义了处理器状态、指令的格式，以及每条指令对状态的影响。第二种抽象是，机器级程序使用的内存地址是虚拟地址，提供的内存模型看上去是一个非常大的字节数组。

x86-64 的机器代码和原始的 C 代码差别非常大。一些通常对 C 语言程序员隐藏的处理器状态都是可见的：

• 程序计数器（PC，在 x86-64 中用 %rip 表示，IA32 中用 %eip 表示）：给出将要执行的下一条指令在内存中的地址。
• 整数寄存器文件：包含 16 个命名的位置，分别存储 64 位的值。这些寄存器可以存储地址或整数数据，或记录某些重要的程序状态。而其他的寄存器用来保存临时数据，例如参数、局部变量，以及函数的返回值。
• 条件码寄存器：保存着最近执行的算术或逻辑指令的状态信息。它们用来实现控制或数据流中的条件变化，比如说用来实现 if 和 while 语句。
• 向量寄存器：可以存放一个或多个整数或浮点数值。

汇编代码不区分有符号或无符号整数，不区分各种类型的指针，甚至不区分指针和整数。

x86-64 的虚拟地址是由 64 位的字来表示的。在目前的实现中，这些地址的高 16 位必须设置为 0，所以一个地址实际上能够指定的是 $2^{48}$或 256 TB 范围内的一个字节。

代码示例：

long mult2(long, long);
void multstore(long x, long y, long *dest) {
  long t = mult2(x, y);
  *dest = t;
}

在命令行上使用-S选项，就能看到 C 语言编译器产生的汇编代码：

multstore:
  pushq %rbx
  movq  %rdx, %rbx
  call  mult2
  movq  %rax, (%rbx)
  popq  %rbx
  ret

要查看机器代码文件的内容，有一类称为反汇编器（disassembler）的程序非常有用。这些程序根据机器代码产生一种类似于汇编代码的格式。在 Linux 系统中，带-d命令行标志的程序OBJDUMP可以充当这个角色：

objdump -d mstore.o

所有以.开头的行都是指导汇编器和链接器工作的伪指令。我们通常可以忽略这些行。

本文使用的是ATT格式的汇编代码格式。

Intel（一般只在 Intel 和 Microsoft 的文档遇到）和 ATT 格式在如下方面不同：

• Intel 代码省略了指示大小的后缀，用的是push，而不是pushq。
• Intel 代码省略了寄存器名字前面的%符号，用的是rbx，而不是%rbx。
• Intel 代码用不同的方式来描述内存中的位置，用的是QWORD PTR [rbx]，而不是(%rbx)。
• 在带有多个操作数的指令情况下，列出操作数的顺序相反。

在 C 程序中插入汇编代码有两种方法：

1. 编写完整的函数，放进一个独立的汇编代码文件中，让汇编器和链接器把它和用 C 语言书写的代码合并起来。
2. 使用 GCC 的内联汇编（inline assembly）特性，用 asm 伪指令可以在 C 程序中包含简短的汇编代码。（这种方法减少了与机器代码相关的代码量）

Three basic kinds of instructions:

1. Perform arithmetic function on register or memory data
2. Transfer data between register and memory (load & store)
3. Transfer control (conditional if & unconditional jump)

数据格式

由于侍从 16 位体系结构扩展成 32 位的，Intel 用术语字（word）表示 16 位数据类型。因此，32 位数称为双字（double words），64 位数称为四字（quad words）。注意以下汇编代码的后缀：

C 声明	Intel 数据类型	汇编代码后缀	大小（字节）
char	字节	b	1
short	字	w	2
int	双字	l	4
long	四字	q	8
char*	四字	q	8
float	单精度	s	4
double	双精度	l	8

访问信息

一个 x86-64 的中央处理单元（CPU）包含一组 16 个存储 64 位值的通用目的寄存器。这些寄存器用来存储整数数据和指针。最初的 8086 中有 8 个 16 位的寄存器。每个寄存器都有特殊的用途，它们的名字就反映了这些不同的用途。在 x86-64 中，还增加了 8 个新的寄存器，它们的标号是按照新的命名规则制定的：从%r8到%r15。

栈指针是用来指明运行时栈的结束位置。

操作数指示符

大多数指令有一个或多个操作数（operand），指示出执行一个操作中要使用的源数据值，以及放置结果的目的位置。x86-64 支持多种操作数格式。源数据值可以以常数形式给出，或是从寄存器或内存中读出，结果可以存放在寄存器或内存中。各种不同的的操作数的可能性被分为三种类型：

• 立即数（immediate）：用来表示常数，如$-577或$0x1F。
• 寄存器（register）：表示寄存器的内容。
• 内存引用：根据计算出来的地址（通常叫有效地址，effective address）访问某个内存位置。

有多种不同的寻址模式，允许不同形式的内存引用。其中Imm(rb, ri, s)表示的是最常用的形式。其中，Imm是立即数偏移，rb是基址寄存器，ri是变址寄存器，和一个比例因子 s（这里的 s 必须是 1、2、4 或者 8）。基址和变址都必须是 64 位寄存器。有效地址被计算为Imm + R[rb] + R[ri] * s。引用数组元素时，会用到这种通用形式。

数据传送指令

最简单形式的数据传送指令MOV类，包括movb、movw、movl、movq。

x86-64 加了一条限制，传送指令的两个操作数不能都指向内存位置，所以将一个内存上的值复制到内存上的另一个位置需要两条指令完成。MOV 指令只会更新目的操作数指定的那些寄存器字节或内存位置。

唯一的例外是movl指令以寄存器作为目的时它会把该寄存器的高位 4 字节设置为 0。造成这个例外的原因是 x86-64 采用的惯例，即任何为寄存器生成 32 位值的指令都会把该寄存器的高位部分设置为 0。

下面列出了五种可能的组合：

movl  $0x4050, %eax
movw  %bp, %sp
movb  (%rdi, %rcx), %al
movb  $-17, (%rsp)  # (register name) -> get the value
movq  %rax, -12(%rbp)

此外，movabsq指令能够以任意 64 位立即数作为源操作数，并且只能以寄存器作为目的。

以下是从低位到高位字节的零扩展和符号扩展的 MOV 类指令：

零扩展	符号扩展
movzbw	movsbw
movzbl	movsbl
movzwl	movswl
movzbq	movsbq
movzwq	movswq
/	movslq
/	cltq（把 %eax 符号扩展到 %rax）

数据传送示例

C 代码：

long exchange(long *xp, long y) {
  long x = *xp;
  *xp = y;
  return x;
}

汇编代码：

exchange:
  movq  (%rdi), %rax  # Get x at xp. Set as return value
  movq  %rsi, (%rdi)  # Store y at xp.

压入和弹出栈数据

在 x86-64 中，程序栈存放在内存中某个区域，且栈是向下增长的（高地址到低地址）。pushq指令的功能是把数据压入到栈中，而popq指令是弹出数据。这些指令都是只有一个操作数——压入的数据源和弹出的数据目的。

pushq指令：首先将栈指针%rsp减 8，然后将值写到新的栈顶地址，其等价于：

subq  $8, %rsp      # Decrement stack pointer
movq  %rbp, (%rsp)  # Store %rbp on stack

popq指令：弹出一个四字的操作包括从栈顶位置读出数据，然后将栈指针%rsp加 8，其等价于：

movq  (%rsp), %rax  # Read %rax from stack
addq  $8, %rsp      # Increment stack pointer

算术和逻辑操作

大多数操作数都分成了指令类，这些指令类有各种带不同大小操作数的变种（只有leaq没有其他大小的变种）。这些操作被分为四组：加载有效地址、一元操作、二元操作和移位。

加载有效地址

加载有效地址（load effective address）指令 leaq 实际上是 movq 指令的变形。它的指令形式是从内存读数据到寄存器，但实际上它根本就没有引用内存。它的第一个操作数看上去是一个内存引用，但该指令并不是从指定的位置读入数据，而是将有效地址写入到目的操作数。这条指令可以：

• 为后面的内存引用产生指针
• 描述普通的算术操作

注意：目的操作数必须是一个寄存器，不能是内存地址

为了说明 leaq 在编译出的代码中的使用，看看下面这个 C 程序：

long scale(long x, long y, long z) {
  long t = x + 4 * y + 12 * z;
  return t;
}

编译时，该函数的算术运算以三条 leaq 指令实现：

scale:
  # x in %rdi, y in %rsi, z in %rdx
  leaq  (%rdi, %rsi, 4), %rax   # x + 4 * y
  leaq  (%rdx, %rdx, 2), %rdx   # z + 2 * z = 3 * z
  leaq  (%rax, %rdx, 4), %rax   # (x + 4 * y) + 4 * (3 * z) = x + 4 * y + 12 * z
  # return value stored at %rax
  ret

特殊的算术操作

两个 64 位有符号或无符号整数相乘得到的乘积需要 128 位来表示。Intel 把 16 字节的数称为八字（oct word）。

imulq指令又两种不同的形式。其中一种，是IMUL指令类中的一种。这种形式的imulq指令是一个双操作数乘法指令。

此外，x86-64 指令集还提供了两条不同的单操作数乘法指令，以计算两个 64 位值的全 128 位乘积——一个是无符号数乘法（mulq），而另一个是补码乘法（imulq）。这两条指令都要求一个参数必须在寄存器%rax中，而另一个作为指令的源操作数给出。虽然imulq可以用于两个不同的乘法操作，但是汇编器能够通过计算操作数的数目，分辨出想用哪条指令。

控制

用jump指令可以改变一组机器代码指令的执行顺序，jump指令指定控制应该被传递到程序的某个其他部分，可能是依赖于某个测试的结果。

条件码

除了整数寄存器，CPU 还维护着一组单个位的条件码（condition code）寄存器，它们描述了最近的算术或逻辑操作的属性。可以检测这些寄存器来执行条件分支指令。常用的条件码有：

• CF：进位标志。最近的操作使最高位产生了进位。可用来检查无符号操作的溢出。
• ZF：零标志。最近的操作得到的结果为 0。
• SF：符号标志。最近的操作得到的结果为负数。
• OF：溢出标志。最近的操作导致一个补码溢出——正溢出或负溢出。

比如说，假设我们用一条 ADD 指令完成等价于 C 表达式t = a + b（addq b a）的功能。然后，根据下面的 C 表达式来设置条件码：

条件码	等价的 C 表达式（a 原来的数，t 新的数）	描述
CF	(unsigned) t < (unsigned) a	无符号溢出
ZF	(t == 0)	零
SF	(t < 0)	负数
OF	(a < 0 == b < 0) && (t < 0 != a < 0)	有符号溢出

注意：leaq 指令不改变任何条件码，因为它是用来进行地址计算的。

此外，还有两类指令只设置条件码而不改变任何其他寄存器。CMP指令根据两个操作数之差来设置条件码（相当于不改变目的寄存器的SUB指令）。在 ATT 格式中，列出操作数的顺序是相反的，这使代码有点难读。如果两个操作数相等，这些指令会将零标志设置为 1，而其他的标志可以用来确定两个操作数之间的大小关系。

TEST指令的行为与AND指令一样，除了不改变目的寄存器的值。例如，testq %rax, %rax用来检查%rax是负数、零、还是正数。

• CMP S1, S2：cmpb、cmpw、cmpl、cmpq。
• TEST S1, S2：testb、testw、testl、testq。

访问条件码

条件码通常不会直接读取，常用的使用方法有三种：

1. 可以根据条件码的某种组合，将一个字节设置为 0 或者 1（使用SET指令）
2. 可以条件跳转到程序的某个其他的部分
3. 可以有条件地传送数据

# int comp(data_t a, data_t b)
# a in %rdi, b in %rsi
comp:
  cmpq    %rsi, %rdi  # Compare a:b
  setl    %al         # Set low-order byte of %eax to 0 or 1
  movzbl  %al, %eax   # Clear rest of %eax (and rest of %rax)
  ret

注意cmpq指令的比较顺序。虽然参数列出的顺序先是%rsi(b)再是%rdi(a)，实际上比较的是 a 和 b。

跳转指令

在汇编代码中，这些跳转的目的地通常用一个标号（label）指明。考虑下面的汇编代码序列：

  movq  $0, %rax
  jmp   .L1
  movq  (%rax), %rdx  # Null pointer dereference (skipped)
.L1:
  popq  %rdx  # Jump target

指令jmp .L1会导致程序跳过movq指令，而从popq指令开始继续执行。在产生目标代码文件时，汇编器会确定所有带标号指令的地址，并将跳转目标（目的指令的地址）编码为跳转指令的一部分。

jmp 指令是无条件跳转。它可以是直接跳转（jmp .L1），也可以间接跳转（如jmp *%rax和jmp *(%rax)）。

跳转指令有几种不同的编码，但是最常用都是PC 相对的（PC-relative）。也就是，它们会将目标指令的地址与紧跟在跳转指令后面那条指令的地址（PC 值）之间的差作为编码。这种实现基于位置无关代码机制。第二种编码方法是给出「绝对」地址，用四个字节直接指定目标。汇编器和链接器会选择适当的跳转目的编码。

# 编号 地址  指令字节序列  汇编代码
1     0:    48 89 f8    mov   %rdi, %rax
2     3:    eb 03       jmp   8 <loop+0x8>
3     5:    48 d1 f8    sar   %rax
4     8:    48 85 c0    test  %rax, %rax
5     b:    7f f8       jg    5 <loop+0x5>
6     d:    f3 c3       repz  retq

第 2 行中跳转指令的跳转目标指明为0x8，第 5 行中跳转指令的跳转目标是0x5。注意，03和f8（相当于十进制的-8）是偏移地址，最后分别跳到第 4 行（+ 下一条指令的地址0x5，5）和第 3 行（+ 下一条指令的地址0xd，13）。

rep和repz分别等价于retq和rep，参考：p141。

用条件控制来实现条件分支

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

if (test-expr)
  then-statement
else
  else-statement
done-statement

对于这种通用形式，汇编实现通常会使用下面这种形式：

  t = test-expr;
  if (!t)
    goto false;
  then-statement
  goto done;
false:
  else-statement
done:
  done-statement

示例：

C 代码：

void cond(long a, long *p) {
  if (p && a > *p)
    *p = a;
}

GCC 会产生下面的汇编代码：

# void cond(long a, long *p)
# a in %rdi, p in %rsi
cond:                   # 这样就解释了 p && a > *p 的写法，如果第一个条件不成立，第二个条件是不会执行的
  testq   %rsi, %rsi    # 相当于 AND %rsi, %rsi 只有 NULL 才成立
  je      .L1           # je(equal / zero) if p == NULL: jump
  cmpq    %rdi, (%rsi)
  jge     .L1           # if %rsi >= %rdi
  movq    %rdi, (%rsi)  # *p = a
.L1:
  rep
  ret

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

实现条件操作的传统方法是通过使用控制的条件转移。当条件满足时，程序沿着一条执行路径执行，而当条件不满足时，就走另一条路径。这种机制简单而通用，但是在现代处理器上，它可能非常低效。

一种替代的策略是使用数据的条件转移。这种方法计算一个条件操作的两种结果，然后根据条件是否满足从中选取一个。只有在一些受限的情况，这种策略才可行，但是如果可行，就可以用一条简单的条件传送指令来实现它。

原始 C 语言代码：

long absdiff(long x, long y) {
  long result;
  if (x < y)
    result = y - x;
  else
    result = x - y;
  return result;
}

使用条件赋值的实现：

long cmovdiff(long x, long y) {
  long rval = y - x;
  long eval = x - y;
  long ntest = x >= y;
  /* Line below requires single instruciton */
  if (ntest) rval = eval;
  return rval;
}

汇编代码：

# long absdiff(long x, long y)
# x in %rdi, y in %rsi
absdiff:
  movq  %rsi, %rax
  subq  %rdi, %rax  # rval = y - x
  movq  %rdi, %rdx
  subq  %rsi, %rdx  # eval = x - y
  cmpq  %rsi, %rdi  # Compare x : y
  cmovge  %rdx, %rax  # If >=, rval = eval
  ret

更多的条件传送指令可参考：p147

循环

汇编中没有相应的指令存在，可以用条件测试和跳转组合起来实现循环的效果。GCC 和其他汇编器产生的循环代码主要基于两种基本的循环模式。

do-while 循环

do
  body-statement
  while (test-expr);

这种通用形式可以被翻译成如下所示的条件和 goto 语句：

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

示例：

// C 代码
long fact_do(long n) {
  long result = 1;
  do {
    result *= n;
    n = n - 1;
  } while (n > 1);
}

// 等价的 goto 版本
long fact_do_goto(long n) {
  long result = 1;
  loop:
    result *= n;
    n = n - 1;
    if (n > 1)
      goto loop;
  return result;
}

汇编代码：

# long fact_do(long n)
# n in %rdi
fact_do:
  movl  $1, %eax
.L2:
  imulq  %rdi, %rax   # Compute result *= n
  subq   $1, %rdi
  cmpq   $1, %rdi     # Compare n : 1
  jg     .L2
  rep
  ret

while 循环

while (text-expr)
  body-statement

第一种翻译方法：跳转到中间（jump to middle）

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

第二种翻译方法，称为guarded-do。首先使用条件分支，如果初始条件不成立就跳出循环（先判断要不要跳转到done），把代码变换为do-while循环。当使用较高优化等级编译时（如-O1），GCC 会使用这种策略。

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

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

for 循环

GCC 为 for 循环产生的代码是 while 循环的两种翻译之一，这取决于优化的等级。和 while 两种策略的代码形式大致相同，只是在开头多了init-expr，在 body-statement 后多了update-expr。可以先将 for 循环改写成 while 循环。

switch 语句

switch（开关）语句可以根据一个整数索引值进行多重分支（multiway branching）。在处理具有多重可能结果的测试时，这种语句特别有用。它们不仅提高了 C 代码的可读性，而且通过使用跳转表（jump table）这种数据结构使得实现更加高效。跳转表是一个数组，表项 i 是一个代码段的地址，这个代码段实现当开关索引值等于 i 时程序应该采取的动作。

和使用一组很长的if-else语句相比，使用跳转表的优点是执行开关语句的时间与开关情况的数量无关。GCC 根据开关情况的数量和开关情况值的稀疏程度来翻译开关语句。当开关情况比较多并且值的范围跨度比较小时，就会使用跳转表。这些对应的信息存储在目标代码文件的.rodata节中。

过程

过程的形式多样：函数、方法、子例程（subroutine）、处理函数（handler）等等。假设过程 P 调用过程 Q，Q 执行后返回到 P。这些动作必须包括下面一个或多个机制：

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

运行时栈

C 语言过程调用机制的一个关键特性在于使用了栈数据结构提供后进先出的内存管理原则。

x86-64 的栈向低地址方向增长，而栈指针%rsp指向栈顶元素。可以用 pushq 和 popq 指令将数据存入栈中或是从栈中取出。将栈指针减小一个适当的量可以为没有指定初始值的数据在栈上分配空间。类似地，可以通过增加栈指针来释放空间。

当 x86-64 过程需要的存储空间超过寄存器能够存放的大小时，就会在栈上分配空间。这个部分称为过程的栈帧（stack frame）。

当前正在执行的过程的帧总是在栈顶。当过程 P 调用过程 Q 时，会把返回地址当做 P 的栈帧的一部分，因为它存放的是与 P 相关的状态。Q 的代码会扩展当前栈的边界，分配它的栈帧所需要的空间。在这个空间中，它可以保存寄存器的值，分配局部变量空间，为它调用的过程设置参数。

大多数过程栈帧都是定长的，在过程开始的时候就分配好了。但是有些过程需要变长的帧，这在后面会讨论到。通用寄存器，过程 P 可以传递最多 6 个整数值（也就是指针和整数），但是如果需要更多的参数，就需要使用栈帧存储。

实际上，许多函数甚至根本不需要栈帧。当所有的局部变量都可以保存在寄存器中，而且该函数不会调用任何其他函数（有时称之为叶子过程，此时把过程调用看做树结构）时，就可以这样处理。

转移控制

将控制从函数 P 转移到函数 Q 只需要简单地把程序计数器设置为 Q 的代码的起始位置。不过，当稍后从 Q 返回的时候，处理器必须记录好它需要继续 P 的执行的代码位置。

• call Q：在 x86-64 机器中，这个信息是用指令call Q调用过程 Q 来记录的。该指令把地址 A 压入栈中，并将 PC 设置为 Q 的起始地址。压入的地址 A 被称为返回地址，是紧跟在 call 指令后面那条指令的地址。
• ret：对应的指令 ret 会从栈中弹出地址 A，并把 PC 设置为 A。

注意：这些指令在程序 OBJDUMP 产生的反汇编输出中被称为callq和retq。添加的后缀q只是为了强调这些是 x86-64 版本的调用和返回，而不是 IA32 的。

传递数据

如果一个函数有大于 6 个整型参数，超出 6 个的部分就要通过栈来传递，参数 7 位于栈顶。通过栈传递参数时，所有的数据大小都向 8 的倍数对齐。参数到位以后，程序就可以执行 call 指令将控制转移到过程 Q 了。过程 Q 可以通过寄存器访问参数，有必要的话也可以通过栈访问。

考虑下面的有 8 个函数的例子：

void proc(long  a1, long  *a1p,
          int   a2, int   *a2p,
          short a3, short *a3p,
          char  a4, char  *a4p) {
  *a1p += a1;
  *a2p += a2;
  *a3p += a3;
  *a4p += a4;
}

对应的汇编代码：

# void proc(a1, a1p, a2, a2p, a3, a3p, a4, a4p)
# Arguments passed as follows:
  a1  in %rdi     (64 bits)
  a1p in %rsi     (64 bits)
  a2  in %edx     (32 bits)
  a2p in %rcx     (64 bits)
  a3  in %r8w     (16 bits)
  a3p in %r9      (64 bits)
  a4  at %rsp+8   (8  bits)
  a4p at %rsp+16  (64 bits)
proc:
  movq    16(%rsp), %rax  # Fetch a4p  (64 bits)
  addq    %rdi, (%rsi)    # *a1p += a1 (64 bits)
  addl    %edx, (%rcx)    # *a2p += a2 (32 bits)
  addw    %r8w, (%r9)     # *a3p += a3 (16 bits)
  movl    8(%rsp), %edx   # Fetch a4   (8  bits)
  addb    %dl, (%rax)     # *a4p += a4 (8  bits)
  ret

栈上的局部存储

有些时候，局部变量必须存放在内存中，常见的情况包括：

1. 寄存器不足够存放所有的本地数据。
2. 对一个局部变量使用地址运算符&，因此必须能够为它产生一个地址。
3. 某些局部变量是数组或结构，因此必须能够通过数组或结构引用被访问到。

寄存器中的局部存储空间

寄存器组是唯一被所有过程共享的资源。虽然在给定时刻只有一个过程是活动的，我们仍然必须确保当一个过程（调用者）调用另一个过程（被调用者）时，被调用者不会覆盖调用者稍后会使用的寄存器值。为此，x86-64 采用了一组统一的寄存器使用惯例，所有的过程（包括程序库）都必须遵循。

根据惯例，寄存器 %rbx、%rbp 和 %r12~%r15 被划分为被调用者保存寄存器。所有其他寄存器，除了栈指针寄存器，都分类为调用者保存寄存器。这就意味着任何函数都能修改它们（基于一种必须遵守的假设）。（前面的寄存器表有所有的说明）

保存方式可用寄存器，或者内存栈。

递归过程

递归调用一个函数本身与调用其他函数一样。栈规则提供了一种机制，每次函数调用都有它自己私有的状态信息存储空间。如果需要，它还可以提供局部变量的存储。栈分配和释放的规则很自然地就与函数调用-返回的顺序匹配。

C 代码：

long rfact(long n) {
  long result;
  if (n <= 1)
    result = 1;
  else
    result = n * rfact(n - 1);
  return result;
}

汇编代码：

# n in %rdi
rfact:
  pushq   %rbx         # Save %rbx
  movq    %rdi, %rbx   # Store n in callee-saved register
  movl    $1, %eax     # Set return value = 1
  cmpq    $1, %rdi     # Compare n:1
  jle     .L35         # If <=, goto done (return)
  leaq    -1(%rdi), %rdi  # Compare n-1
  call    rfact        # Call rfact(n-1)
  imulq   %rbx, %rax   # Multiply result by n
.L35:
  popq    %rbx  # Restore %rbx
  ret

数组、指针的分配和访问

x86-64 的内存引用指令可以用来简化数组访问。例如，假设 E 是一个 int 型的数组，而我们想计算E[i]，在此，E 的地址存放在寄存器%rdx中，而 i 存放在寄存器%rcx中。然后，指令：

movl  (%rdx, %rcx, 4), %eax

会得到第 i 个元素的地址，并将结果存放到寄存器 %eax 中。

嵌套的数组

要访问多维数组的元素，编译器会以数组起w为基地址，（可能需要经过伸缩的）偏移量作为索引，产生计算期望的元素的偏移量，然后使用某种 MOV 指令。通常来说，对一个T D[R][C]的数组，它的数组元素D[i][j]的内存地址为：

$$ & D\left[i \right]\left[ j \right] = x_D + L(C\cdot i + j) $$

考虑一个定义为 5x3 的整型数组 A。可以用下面的代码将数组元素 A[i][j] 复制到寄存器 %eax 中：

# A in %rdi, i in %rsi, and j in %rdx
leaq  (%rsi, %rsi, 2), %rax   # Compute 3i
leaq  (%rdi, %rax, 4), %rax   # Compute xA + 12i
movl  (%rax, %rdx, 4), %eax   # Read from M[xA + 12i + 4j]

多维数组 vs 多级数组

多维数组（multi-dimension array）：T[i][j]

int a[2][3] = { { 1,2,3 }, { 2,3,4 } }

多级数组（multi-level array）：T* [i]

int *a[2] = { { 1,2 }, { 1,2,3,4 } } // 任意长度

两者的区别：是否做了两次内存读。注意，Java 就是用多级数组的方式来表示多维数组。

定长数组

C 语言编译器能够优化定长多维数组上的操作代码。这里展示优化等级设置为-O1时 GCC 采用的一些优化。假设我们用如下方式将数据类型 fix_matrix 声明为 16x16 的整型数组：

#define N 16
typedef int fix_matrix[N][N]

/* Compute i, k of fixed matrix product */
/* 计算矩阵 A 和 B 乘积的元素 i，k，即 A 的行 i 和 B 的列 k 的内积 */
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;
}

GCC 产生的代码中进行了如下优化：

1. 生成一个指针，命名为Aptr，指向 A 的行 i 中连续的元素。
2. 生成一个指针，命名为Bptr，指向 B 的列 j 中连续的元素。
3. 生成一个指针，命名为Bend，当需要终止循环时，它会等于 Bptr 的值。

优化过的 C 代码：

/* Compute i, k of fixed matrix product */
int fix_prod_ele_opt(fix_matrix A, fix_matrix B, long i, long k) {
  int *Aptr = &A[i][0];
  int *Bptr = &B[0][k];
  int *Bend = &B[N][k];
  int result = 0;
  do {
    result += *Aptr * *Bptr;
    Aptr++;
    Bptr += N;
  } while (Bptr != Bend);
  return result;
}

变长数组

参考：p181，优化方法与定长数组类似。

异质的数据结构

参考：p183 & p186

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

内存越界引用和缓冲区溢出

/* Read input line and write it back */
void echo() {
  char buf[8];  /* way to small! */
  gets(buf);
  puts(buf);
}

对应的汇编代码：

echo:
  subq    %24, %rsp     # Allocate 24 bytes on stack
  movq    %rsp, %rdi    # Compute buf as %rsp
  call    gets          # Call gets
  movq    %rsp, %rdi    # Compute buf as %rsp
  call    puts          # Call puts
  addq    $24, %rsp     # Deallocate stack space
  ret

长一些的字符串会导致 gets 覆盖栈上存储的某些信息。随着字符串变长，下面的信息会被破坏：

输入的字符数量	附加的被破坏的状态
0 ~ 7	无
9 ~ 23	未被使用的栈空间
24 ~ 31	返回地址
32+	caller 中保存的状态

字符串到 23 个字符之前都没有严重的后果，但是超过以后，返回指针的值以及更多可能的保存状态会被破坏。如果存储的返回地址的值被破坏了，那么 ret 指令会导致程序跳到一个完全意想不到的位置。如果只看 C 代码，根本就不可能看出会有上面这些行为。

通常，使用 gets 或其它任何能导致存储溢出的函数，都是不好的编程习惯。不幸的是，很多常用的库函数，包括 strcpy、strcat 和 sprintf，都有一个属性——不需要告诉它们目标缓冲区的大小。

缓冲区溢出的一个更加致命的使用就是让程序执行它本来不愿意执行的函数。这是一种最常见的通过计算机网络攻击系统安全的方法。通常，输入给程序一个字符串，这个字符串包含一些可执行代码的字节编码，称为攻击代码（exploit code），另外，还有一些字节会用一个指向攻击代码的指针覆盖返回地址。那么，执行 ret 指令的效果就是跳转到攻击代码。

在一种攻击形式中，攻击代码会使用系统调用启动一个 shell 程序，给攻击者提供一组操作系统函数。在另一种攻击形式中，攻击代码会执行一些未授权的任务，修复对栈的破坏，然后第二次执行 ret 指令，（表面上）正常返回给调用者。

蠕虫和病毒都试图在计算机中传播它们自己的代码段。蠕虫（worm）可以自己运行，并且能够将自己等效副本传播到其他机器。病毒（virus）能将自己添加到包括操作系统在内的其他程序中，但它不能独立运行。两者是不同的，媒体有时会把应该叫做蠕虫的东西称为病毒。

对缓冲区溢出攻击

以下列举 Linux 上最新 GCC 版本所提供的一些机制。

栈随机化

为了在系统中插入攻击代码，攻击者既要插入代码，也要插入指向这段代码的指针，这个指针也是攻击字符串的一部分。产生这个指针需要知道这个字符串放置的栈地址。在过去，程序的栈地址非常容易预测。对于所有运行同样程序和操作系统版本的系统来说，在不同的机器之间，栈的位置是相当固定的。这种现象常被称为安全单一化（security monoculture）。

栈随机化的思想使得栈的位置在程序每次运行时都有变化。实现的方式是：程序开始时，在栈上分配一段 0 ~ n 字节之间的随机大小空间。程序不使用这段空间，但是它会导致程序每次执行时后续的栈位置发生了变化。当 n 很大的时候才能获得足够多的栈地址变化，但这也会导致浪费。

/* 确定栈地址的方法 */
int main() {
  long local;
  printf("local at %p\n", %local);
  return 0;
}

在 Linux 系统中，栈随机化已经成为了标准行为。它是更大的一类技术中的一种，这类技术成为地址空间布局随机化（Address-Space Layout Randomization），或者简称ASLR。采用它，每次运行时程序的不同部分，包括程序代码、库代码、栈、全局变量和堆数据，都会被加载到内存的不同区域。这就意味着在一台机器上运行一个程序，与在其他机器上运行同样的程序，它们的地址映射大相径庭。

然而，一个执著的攻击者总是能够用蛮力克服随机化，他可以反复地用不同的地址进行攻击。一种常见的把戏就是在实际的攻击代码前插入很长一段的nop（no operation）指令。执行这种指令除了对程序计数器加一，使之指向下一条指令之外，没有任何的效果。攻击者可以使程序经过这个序列，到达攻击代码。这个序列的术语是空操作雪橇（nop sled），意思是程序会「滑过」这个序列。

栈破坏检测

计算机的第二道防线是能够检测到何时栈已被破坏。最近的 GCC 版本在产生的代码中加入了一种栈保护者（stack protector）机制，来检测缓冲区越界。其思想是在栈帧中任何局部缓冲区与栈状态之间存储一个特殊的金丝雀值（canary，它们能在煤矿中察觉有毒气体），也称为哨兵值（guard value），是在程序每次运行时随机产生的。

在恢复寄存器状态和从函数返回之前，程序检查这个金丝雀值是否被函数的某个操作或者该函数调用的某个函数的某个操作改变了。如果是的，那么程序异常中止。

限制可执行代码区域

最后一招是消除攻击者向系统中插入可执行代码的能力。一种方法是限制哪些内存区域能够存放可执行代码。硬件支持多种形式的内存保护，能够指明用户程序和操作系统内核所允许的访问形式。

最近，AMD 为它的 64 位处理器的内存保护引入了NX（No-Execute，不执行）位，将读和执行访问模式分开，Intel 也跟进了。有了这个特性，栈可以被标记为可读和可写，但是不可执行，而检查页是否可执行由硬件来完成，效率上没有损失。

支持变长栈帧

为了管理变长栈帧，x86-64 代码使用寄存器%rbp作为帧指针（frame pointer），也称为基指针（base pointer）。此时，函数栈帧结构如下：

可以看到代码必须把 %rbp 以前的值保存到栈中，因为它是一个被调用者保存寄存器。然后在函数执行的整个过程中，都使得 %rbp 指向那个时刻栈的位置，然后用固定长度的局部变量相对于 %rbp 的偏移量来引用它们。

在函数的开始，代码建立栈帧，并为数组 p 分配空间。首先把 %rbp 的当前值压入栈中，将 %rbp 设置为指向当前的栈位置。然后，在栈上分配 16 个字节（如图）。

在函数的结尾，leave指令将帧指针恢复到它之前的值。这条指令不需要参数，等价于执行以下两条指令：

movq  %rbp, %rsp  # set %rsp back
popq  %rbp        # set %rbp back

在较早版本的 x86 代码（IA32）中，每个函数调用都使用了帧指针。而现在，只在栈帧长可变的情况下才使用。可以把使用帧指针的代码和不使用帧指针的代码混在一起，只要所有的函数都把 %rbp 当做被调用者保存寄存器来处理即可。

浮点代码

AVX 浮点体系结构允许数据存储在 16 个YMM寄存器中，它们的名字为%ymm0 ~ %ymm15。每个 YMM 寄存器都是 256 位（32 字节）。当对标量数据操作时，这些寄存器只保存浮点数，而且只使用低 32 位（对于 float）或 64 位（对于 double）。汇编代码用寄存器 SSE XMM 寄存器名字%xmm0 ~ %xmm15来引用它们，每个 XMM 寄存器都是对应的 YMM 寄存器的低 128 位（16 字节）。

浮点数传送

float float_mov(float v1, float *src, float *dst) {
  float v2 = *src;
  *dst = v1;
  return v2;
}

与它相关联的 x86-64 汇编代码为

# float float_mov(float v1, float *src, float *dst)
# v1 in %xmm0, src in %rdi, dst in %rsi
float_mov:
  vmovaps  %xmm0, %xmm1   # Copy v1
  vmovss   (%rdi), %xmm0  # Read v2 from src
  vmovss   %xmm1, (%rsi)  # Write v1 to dst
  ret                     # Return v2 in %xmm0

浮点数转换

第一个操作数读取来自于内存或一个通用目的寄存器。这里可以忽略第二个操作数，因为它的值只会影响结果的高位字节。而我们的目标必须是 XMM 寄存器。在最常见的使用场景中，第二个源目的操作数都是一样的，就像下面这条指令：

vcvtsi2sdq  %rax, %xmm1, %xmm1

这条指令从寄存器 %rax 读出一个长整数，把它转换成数据类型 double，并把结果存放进 XMM 寄存器 %xmm1 的低字节里。

最后，要在两种不同的浮点格式之间转换，GCC 的当前版本生成的代码需要单独说明。假设 %xmm0 低位 4 字节保存着一个单精度值，很容易就想到用下面这条指令把转换成一个双精度值，并将结果存储在寄存器 %xmm0 的低 8 字节。

vcvtss2sd  %xmm0, %xmm0, %xmm0

不过 GCC 实际生成的代码如下（原因参考 p207）：

vunpcklps  %xmm0, %xmm0, %xmm0
vcvtps2pd  %xmm0, %xmm0

对于双精度转换为单精度，GCC 会产生类似的代码：

vmovddup    %xmm0, %xmm0
vcvtpd2psx  %xmm0, %xmm0

浮点数运算

double funct(double a, float x, double b, int i) {
  return a * x - b / i;
}

x86-64 代码如下：

# double funct(double a, float x, double b, int i)
# a in %xmm0, x in %xmm1, b in %xmm2, i in %edi
funct:
  # The following two instructions convert x to double
  vunpcklps   %xmm1, %xmm1, %xmm1
  vcvtps2pd   %xmm1, %xmm1
  vmulsd      %xmm0, %xmm1, %xmm0  # Multiple a by x, xmm0 * xmm1
  vcvtsi2sd   %edi, %xmm1, %xmm1   # Convert i to double
  vdivsd      %xmm1, %xmm2, %xmm2  # Compute b / i, xmm2 / xmm1
  vsubsd      %xmm2, %xmm0, %xmm0  # Subtract from a * x, xmm0 - xmm2
  ret

浮点数常量

和整数运算操作不同，AVX 浮点操作不能以立即数作为操作数。相反，编译器必须为所有常量值分配和初始化存储空间。然后代码再把这些值从内存读入。如摄氏度到华氏度转换的函数：

double cel2fahr(double temp) {
  return 1.8 * temp + 32.0;
}

对应的汇编代码：

# temp in %xmm0
cel2fahr:
  vmulsd  .LC2(%rip), %xmm0, %xmm0    # Multiply by 1.8
  vaddsd  .LC3(%rip), %xmm0, %xmm0    # Add 32.0
  ret
.LC2:
  .long  3435973837    # Low-order of 1.8 (4 bytes)
  .long  1073532108    # High-order of 1.8
.LC3:
  .long  0             # Low-order of 32.0
  .long  1077936128    # High-order of 32.0

浮点数位级操作

浮点比较操作

条件码的设置条件如下：

顺序 $S_2 : S_1$	CF	ZF	PF
无序的	1	1	1
$S_2 < S_1$	1	0	0
$S_2 = S_1$	0	1	0
$S_2 > S_1$	0	0	0

当任以操作数为NaN时，就会出现无序的情况。可以通过奇偶标志位发现这种情况。通常jp（jump on parity）指令是条件跳转，条件就是浮点比较得到一个无序的结果。

IA32 的一些汇编代码

在看 CSE 351 视频的时候，课上首先采用了 IA32 进行讲解。IA32 和 x86-64 还是由一定差别的，所以还是记录一下 IA32 的几个程序。

1. 注意参数的获取方式

void swap(int *xp, int *yp) {
  int t0 = *xp;
  int t1 = *yp;
  *xp = t1;
  *yp = t0;
}

# %ecx - yp, %edx - xp, %eax - t1, %ebx - t0
movl  12(%ebp), %ecx   # ecx = yp
movl  8(%ebp), %edx    # edx = xp
movl  (%ecx), %eax     # eax = *yp (t1)
movl  (%edx), %ebx     # ebx = *xp (t0)
movl  %eax, (%edx)     # *xp = t1)
movl  %ebx, (%ecx)     # *yp = ebx

2. 全局变量的获取方式

int zip1 = 15123;
int zip2 = 98150;

void call_swap() {
  swap(&zip1, &zip2);
}

call_swap:
  # ...
  pushl  $zip2
  pushl  $zip1  # 而且注意推入的顺序，从右往左
  call   swap
  movl   %ebp, %esp   # 将 esp 指回 ebp（基址）
  popl   %ebp   # 注意这条指令是建立在上一条指令之上的，因为 popl 需要 esp 指向 ebp
  ret           # 此时因为 pop 了 old ebp，esp 指向 return address，ret 将 esp 的值给 PC