machine-Level representation of programs csapp

发表于 | 更新于 | 分类于 | 评论数：

程序的机器级表示

Intel x86由来

Intel处理器俗称x86。Intel处理器系列有好几个名字，包括IA32，也就是"Intel 32位体系结构（Intel Architecture 32-bit）"，以及最新的Intel 64，即IA32的64位扩展，也称为x864-64。最常用的名字是"x86"，我们用它来代指整个系列，也反映了直到i486处理器命名的惯例。

程序编码

程序计数器(program counter)，通常称为PC，在x86-64中用%rip表示。

机器级代码

汇编代码格式

数据格式

因为是从16位体系结构扩展成32位的，Intel用术语字表示16位数据类型。用双字（double words）表示32位数据类型。用四字（quad words）表示64位数据类型。指针存储为8字节的四字。
以下是C语言类型在x86-64中的大小：
format
大多数GCC生成的汇编代码中都有一个字符的后缀，表明操作数的大小。比如数据传送指令的四个变种：
movb传送字节，movw传送字，movl传送双字，movq传送四字。后缀’l’表示双字，因为32位数被看成是长字（long word）。

信息访问

通用目的寄存器寄存器

一个x86-64的CPU提供了一组16个64位的通用目的寄存器，这些寄存器用来存储整数数据和指针（地址）。如下所示是这16个寄存器：
register
它们的名字都以%r开头，但是后面还跟着一些其他命名规则的名字，这是指令集历史演化造成的：

  1. 最初的8086有8个16位寄存器，即%ax到%bp；
  2. 扩展到IA32架构时，寄存器也扩展成32位寄存器，标号从%eax到%ebp
  3. 扩展到x86-64后，原来的8个寄存器扩展成64位，标号从%rax到%rbp，此外，还增加了8个新的寄存器，它们的名字是%r8到%r15。

指令可以对这16个寄存器中的数据进行操作。字节级指令可以访问最低的字节，16位操作可以访问最低的16个字节。32位操作可以访问最低的32个字节，64位操作可以访问整个寄存器。
当指令以寄存器为目标时，对于生成小于8字节结果的指令，寄存器剩下的值该怎么变，有两条规则：

  1. 生成1字节和2字节数字的指令会保持剩下的字节不变。
  2. 生成4字节数字的指令会把高位4个字节置为0。

操作数寻址指令

大多数指令都有一个或者多个操作数，指示执行一个操作中要使用的源数据之，以及放置结果的目的位置。x86-64支持三类操作数格式：立即数，寄存器和内存引用。如下图所示：
operand

  1. 立即数。 在ATT格式的汇编代码中，立即数的写法是$后面跟一个标准C表示的整数。如$-144, $0xFF。
  2. 寄存器。将寄存器集合看成一个数组R，用寄存器标识符作为索引，如R[%rax]。
  3. 内存引用。根据计算出来的地址访问某个内存位置，将内存看成一个很大的字节数组，用符号Mb[Addr]表示对存储在内存中的地址Addr开始的b个字节的引用，通常省略下标b。内存引用有不同的寻址方式，如上图所示，后面9种都为内存引用，对应不同的寻址方式。

数据传送指令

将数组从一个位置复制到另一个位置的指令叫做数据传送指令。为了方便，把不同的指令划分为指令类，每一类中的指令执行相同的操作，只不过操作数大小不同。

x86-64加了一条限制，传送指令的两个操作数不能都指向内存位置。

MOV类

MOV类包含四条指令：movb, movw, movl, movq。它们把数据从源位置复制到目的位置。
mov
MOV类指令的约束如下：

  1. 源操作数指定的值是一个立即数，存储在寄存器中或者内存中
  2. 目的操作数指定一个位置，要么是一个寄存器，要么是一个内存地址。
  3. x86-64加了一条限制，传送指令的两个操作数不能都指向内存位置。
  4. 大多数情况下，MOV指令只会更新目的操作数指定的那些寄存器字节或者内存位置。唯一的例外是movl指令以寄存器作为目的时，它会把寄存器的高位4字节设置为0，这里x86-32采用的惯例，任何为寄存器生成32位值的指令都会把该寄存器的高位部分置为0。
  5. movq和movabsq的区别。moveq指令只能以表示为32位补码的立即数作为源操作数，然后把这个值符号扩展得到64位的值，放到目的位置。而movabsq指令能以任意64位立即数值作为源操作数。

MOVZ和MOVS类

MOVZ和MOVS类在将较小的源值复制到较大的目的位置时使用，它们都将数据从源（寄存器或者内存中）复制到目的寄存器。MOVZ中的指令把目的位置中剩余的位置填充为0，而MOVS通过符号扩展进行填充。如下图所示。
movz
movs

  1. 每条指令名字的最后两个字符都是大小指示符：第一个字符指令源的大小，第二个字符指明目的的大小。注意在movz中，没有movzlq指令，这个指令不需要存在。因为，movl为寄存器生成32位值的指令时会把寄存器的高位部分置为0。
  2. cltq指令没有操作数，它总是以寄存器%eax作为源，%rax作为符号扩展结果的目的。它的效果与指令movslq %eax, %rax完全一致。

压入和弹出栈数据

push操作可以把数据压入栈中，pop操作删除数据。栈指针%rsp保存着栈顶元素的地址。
push_pop
pushq将一个四字值压入栈中，比如pushq %rsp相当于以下两条指令：

1
2
subq $8, %rsp
movq %rbp, (%rsp)

只不过pushq指令编码为1个字节，而上面两条指令编码为8个字节。
同理popq从栈中弹出一个四字，popq %rax相当于以下两条指令：

1
2
movq (%rsp), $rax
addq $8, %rsp

算术和逻辑操作

算术和逻辑操作可以分为四组，加载有效地址，一元操作，二元操作和移位。除了leaq外，所有的指令类都有四种不同大小数据类型的指令（字节，字，双字，四字）。它们的指令格式如下表所示：
alg_log

加载有效地址

加载有效地址(lead effective address)指令leaq其实就是movq指令的变形。它的指令形式是从内存读数据到寄存器，但是它根本没有使用到内存，这个指令并不是从指定的位置读入数据，而是将源数据的有效地址写入到目的操作数。
此外，leaq还可以进行简普通的算术操作。比如，如果寄存器%rdx的值为x，指令leaq 7(%rdx, %rdx, 4), %rax设置寄存器的值为5x+7。

一元和二元操作

一元操作的源操作数和目的操作数是一样的，这个操作数可以是一个寄存器，也可以是一个内存位置。
uni
二元操作的第二个操作数既是源操作数又是目的操作数。
binary

移位操作

最后一组操作是移位操作，它的操作数有两个，第一个是移位量，它可以是一个立即数，也可以是存放在单字节寄存器%cl中的一个数值，只允许以这个特定的寄存器为操作数。第二个操作数是要移位的数。
shift
移位操作分为算术移位和逻辑移位。而每种移位又可以分为左移和右移。算术左移和逻辑右移是一样的，都是用0来填充右面的位。而算术右移和逻辑右移不同，算术右移使用0填充左边，而逻辑左移使用最高位的符号位填充。

128位乘除法

两个64位有符号数或者无符号整数相乘得到的乘积需要128位，x86-64指令集对128位数的操作提供有限的支持。延续字，双字，四字，Intel把16字节（128位）的数叫做八字。如下所示：
oct_word

128位乘法

imulq指令有两种不同的形式。一种接受两个操作数，一种接受一个操作数。前面介绍的imulq是接受双操作数的指令，这里介绍的两个mulq和imulq是两条不同的单操作数乘法指令，计算两个64位值的128位乘积，一个是无符号乘法，一个是补码乘法。这两条指令都要求一个参数必须在寄存器%rax中，另一个作为指令的源操作数给出，乘积存放在寄存器%rdx（高64位）和%rax（低64位）中。

128位除法

除法是由单操作数指令提供的。有符号除法指令idivl将寄存器%rdx（高64位）和%rax（第64位）中的128位作为被除数，而除数作为指令的操作数给出。指令将商存放在%rax中，余数存储在%rdx中。
通常情况下来说，除法的被除数通常也是64位的，这个值应该存放在%rax中，而%rdx应该置为0或者是%rax的符号位。可以使用cqto指令完成将%rax置为%rax的符号位，这条指令不需要操作数，默认读出%rax的符号位，并将它复制到%rdx的所有位。如果是无符号64位除法，不能使用cqto，需要使用movl $0, %edx，为什么不是movq $0, %rdx，因为movl能自动的将%rdx的高位4个字节置为0。

控制

条件码

x86 CPU维护了四个条件码：

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

leaq指令不会改变任何条件码，因为它是用来进行地址计算的。所有上一节介绍的算术和逻辑指令都会设置条件码。

访问条件码

条件码不会直接被读取，通常是在使用CMP指令类或者TEST指令类设置条件码之后，通常的使用方法有三种：

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

CMP指令类和TEST指令类

CMP和TEST指令类只设置条件码而不改变任何寄存器。
除了CMP只设置条件码而不更新目的寄存器，CMP和SUB指令是一样的。
除了TEST只设置条件码而不改变目的寄存器的值，TEST指令类的行为和AND指令是一样的。
test_cmp

SET指令类

SET指令类根据条件码的某种组合，将一个字节设置为0或者1，不同的SET指令之间的区别就在于它们考虑的条件码的组合是什么，指令名字的后缀指明了它们所考虑的条件码的组合。
一条SET指令的目的操作数是低位单字节寄存器，或者一个字节的内存位置，SET指令将这个字节设置成0或者1。为了得到一个32位或者64位的结果，必须对高位清零。
set

跳转指令类

正常情况下，指令按照它们出现的顺序一条一条的执行。跳转指令会导致执行切换到程序中一个全新的位置。在汇编代码中，这些跳转的目的地通常用一个label指明。下面是两类不同的跳转指令：
jmp

  1. **无条件跳转指令。*汇编语言中，直接跳转是给出一个label作为跳转目标的；间接跳转是’'号后面跟一个操作数指示符，如jmp *%rax，是内存操作数格式的一种。jmp是无条件跳转，它可以是直接跳转，也可以是间接跳转。
  2. **条件跳转指令。**所有其他跳转指令都是有条件的，它们根据条件码的某种组合，进行跳转或者继续执行下一条指令，这些指令的名字和跳转指令的名字和设置条件是匹配的。条件跳转只能是直接跳转，不能是间接跳转。

跳转指令的编码

在汇编代码中，跳转目标用符号label书写。汇编器和链接器会产生跳转目标的适当编码。
跳转指令有几种不同的编码：

  1. 最常使用的是PC相对(PC-relative)，它们会将目标指令的地址与紧跟在跳转指令后面的那条指令的地址之间的差作为编码（目标指令地址-跳转指令下一条的地址），在使用的时候，把下一条指令的地址加上PC相对量就得到了目标指令的地址。这些地址偏移量可以编码为1,2或者4个字节。
  2. 第二种编码方式是给出绝对地址，用4个字节直接指定目标。

汇编器和链接器会选择适当的跳转目的编码。

条件控制实现条件分支

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

1
2
3
4
5
6
7
8
if(test-expr)
{
    then-statement
}
else
{
    else-statement
}

汇编实现通常如下所示（C语法表示）：

1
2
3
4
5
6
7
8
    t = test-expr;
    if(!t)
        goto false;
    then-statement;
    goto done;
false:
    else-statement
done:

汇编器会为then-statement和else-statement产生各自的代码块。即汇编器会插入条件和无条件分支，保证执行正确的代码块。　
还可以有另外一种实现：

1
2
3
4
5
6
7
8
    t = test-expr;
    if(t)
        goto true;
    else-statement
    goto done;
true:
    then-statement;
done:

条件传送实现条件分支

除了控制的条件转义，还有数据的条件转移。它只能用在部分情况下，但是如果可以使用的话，就比较简单。
下图列出了x86-64的一些条件传送指令：
cmov
考虑以下条件表达式：

1
v = test-expr? then-expr: else-expr;

如果使用条件控制编译，通常会得到如下形式：

1
2
3
4
5
6
7
    if(!test-expr)
        goto false;
    v= then-expr;
    goto done;
false:
    else-expr;
done:

条件传送和条件跳转的区别。而条件跳转必须预测test的结果提高流水线的效率，如果预测错了，效率会很低。比如处理器预测test-expr结果为真，就会只执行then-expr的部分，如果预测错了，即它就得重新计算else-expr的部分。
对于条件传送来说，处理器不预测test的结果，它对if-expr和else-expr中的片段都进行求值，然后再根据计算出来的两个结果，选择是否进行条件传送。
条件传送的问题，需要对if-expr和else-expr都进行求值，如果它们冲突了，就会产生错误。而且如果它们的计算量都很大的时候，就会产生大量浪费的计算。对于GCC来说，通常当它们都很容易计算时，才会使用条件传送。

循环

do-while循环

C语言的do-while语句如下：

1
2
3
do
    body-statement
    while(test-expr);

翻译成汇编语言（C语言形式）如下：

1
2
3
4
5
loop:
    body-statement
    t = test-expr;
    if(t)
        goto loop;

while循环

while循环有两种方式，一种相当于在do-while的前面加一个goto语句直接跳转到do-while的test-expr部分，另一种相当于直接在do-while前再加一个执行一次的test-expr，进行第一次条件判断，其实都一样。
C语言的while语句如下：

1
2
while(test-expr)
    body-statement;

翻译成汇编语言（C语言形式）如下：

1
2
3
4
5
6
7
8
    goto ;
loop:
    body-statment

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

或者还可以用do-while表示while：

1
2
3
4
5
6
7
t = test-expr;
if(!t)
    goto done;
do
    body-statement
while(test-expr);
done:

翻译成汇编语言（C语言形式）如下：

1
2
3
4
5
6
7
8
9
t = test-expr
if(t)
    goto done;
loop:
    body-statement
    t = test-expr;
    if(t)
        goto loop;
done:

for循环

C语言for循环的形式如下：

1
2
for(init-expr; test-expr; update-expr)
    body-statement

C标准规定（除了含有continue语句的for循环），for循环的行为和下列while的行为是一样的：

1
2
3
4
5
6
7
8
init-expr;
while(test_expr)
{
    body-statement
    //if(i & 0x1)
    // continue;
    update-expr;
}

GCC为for循环产生的代码就是while循环两种中的一个，具体是哪一个取决于优化等级。
如果直接将含有continue语句的for循环修改成while语句，会陷入死循环，因为它无法执行update-expr操作，continue语句属于body-statement部分，可以看上面的代码块中的注释部分，所以需要额外使用goto语句使其跳转到update-expr部分。

switch语句

switch处理多种可能结果的测试，通过使用跳转表可以提高效率，使得执行switch语句的时间和switch的数量无关，一个跳转表可以线性时间跳转到任何一个switch分支。
如果忘了做一道题就OK了。

Procedures

Procedures（过程）是一种抽象，其实就是C/C++ 中的函数，Java的方法，还有子例程(subroutine)，处理函数(handler)等。
机器级的procedures，需要处理不同的属性，为了方便，假设过程P调用过程Q，过程Q执行完返回到过程P。这个过程包括下面一个或者多个部分：

  • 传递控制。进入过程Q的时候，PC(%rip)被设置为Q的代码的起始地址，并且将返回地址（调用指令后面的那条指令地址）压入栈中。返回过程P时，弹出返回地址，并将PC设置为返回地址。
  • 传递数据。过程P向过程Q提供一个或者多个参数，过程Q向过程P返回一个值。
  • 分配和释放内存。在过程Q开始时，可能需要为局部变量分配空间；而在过程Q返回时，需要释放这些空间。

运行时栈

C语言函数（过程）调用使用了栈管理内存。如下所示：
stack_frame
栈从高地址向低地址增长，寄存器%rsp存放栈指针，指向栈顶元素。将栈指针减少一个适当的量可以在栈上分配空间，增加栈指针可以释放空间。
当一个函数需要的存储空间超出寄存器能够存放的大小时，就会在栈上分配空间，这部分空间称为栈帧，当前正在执行的函数的栈帧总是在栈顶。栈帧中可以存放返回地址，寄存器参变量，局部变量，向它调用的函数传递的参数等(函数通过寄存器最多可以传递6个整数，多余的哪些参数就需要通过栈帧传递）。
并不是所有的函数都有栈帧的所有部分，甚至很多函数其实不需要栈帧。比如函数的参数少于6个时，所有的参数都可以通过寄存器传递，这个时候不需要存放参数的那部分。当所有的局部变量都可以存放在寄存器中，并且该函数不会调用其他函数时，就不会创建栈帧（这个函数称为叶子过程）。

调用函数P的栈帧
参数1-n
返回地址
当前被调用函数的栈帧
保存的寄存器地址
局部变量
参数构造区

转移控制

转移控制完成的任务是函数调用和函数返回，通过call和ret指令实现这两个任务。
call由调用函数（caller）执行，call指令会将它的下一条指令的地址压入栈中，这个地址叫做返回地址，并设置PC为被调用函数的起始地址。
ret指令由被调用函数（callee）执行，从栈中将返回地址弹出，并设置PC为返回地址。

传递参数

函数可能需要传递参数，并且可能有返回值。x86-64中可以通过6个寄存器传递参数：
register_parameters
超过6个的需要使用寄存器传递，假设调用函数需要传递n个整数参数给被调用函数，需要在栈帧中分配第7-n个参数的空间，参数7位于调用函数(caller)栈帧的底部，也是栈顶（因为还没有调用callee，所以也就没有它的栈帧）。
通过栈传递参数时，需要使用8字节对齐（32位的机器）。

栈上的局部数据

当满足以下情况时：

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

如果需要分配空间，先通过减少栈指针分配空间，然后在ret前增加栈指针回收空间。

寄存器存储局部数据

寄存器是唯一被所有函数（过程）共享的资源。为了保证函数调用发生时，被调用函数不会覆盖调用函数(caller)中的寄存器值，x86-64采用了一组统一的寄存器使用惯例，所有的函数都必须遵循：
%rbx, %rbp和%r12到%r15，是被调用者负责保存的寄存器，callee需要确保这些寄存器中的值在返回caller时不会改变，callee可以不使用这些寄存器，或者将它们的值存放在栈中，等到返回时将它们的值弹出。所有其他除了%rsp的寄存器都被划分为调用者保存寄存器，所以如果一个函数使用到了这些寄存器，在它调用其他函数之前，最好把它们的值存好，因为调用函数很有可能会修改它们。

递归调用

递归调用的过程就是不断的创建栈帧的过程，这个过程确保每个函数之间不会相互干扰，正常工作（没有stackoverflow）。

数组

CSAPP中介绍的是C语言中数组的寻址：一维数组和和多维数组，变长数组的寻址。GCC在对数组的操作过程中，一般会把数组元素寻址中的乘法改成加法，提高效率。

声明一个数组并没有介绍，其实就是在函数的栈帧上分配空间或者存放在全局区。

结构和联合（union）

结构体的寻址和联合的寻址，注意对齐就行，没啥特别的吧。

对于大多数x86-64指令来说，无论对齐不对齐，对结果的正确与否都没啥影响，但是Intel还是建议对齐提高性能。对齐的原则是任何K字节的基本对象的地址都必须是K(K通常是2, 4或者8)的倍数。在汇编中，使用.align 8可以指定8字节对齐。
但是另一方面，如果数据没有对齐，某些型号的Intel和AMD处理器对于部分实现多媒体操作的SSE指令，无法正确执行，这些指令对16字节数据块进行操作，在SSE单元和内存之间传送指令的数据的指令要求内存地址必须是16的倍数。任何以不满足对齐要求的地址来访问内存都会导致程序异常。
因此，任何针对x86-64的编译器和运行时系统都必须保证分配用来保存可能会被SSE寄存器读或写的数据结构的内存，都必须满足16字节对齐。这个要求有以下两个后果：

  1. 任何内存分配函数(malloc, calloc或者realloc)生成的块的起始地址都必须是16的倍数；
  2. 大多数函数的栈帧的边界都需要是16字节的倍数。

最近的x86-64处理器实现了AVX多媒体指令，除了提供SSE指令的超集，支持AVX的指令没有强制性的对齐要求。

机器级控制和数据的交互

指针

没啥新东西。

GDB

GDB是GNU的调试器，可以用来调试C, C++和机器级程序等。下面是一些常见的调试机器级程序的选项：
gdb

数组越界和缓冲区溢出

局部变量和状态信息（返回地址和保存的寄存器值）都存放在栈中，由于C语言不对数组引用进行边界检查，这两种情况同时发生时，就可能造成缓冲区溢出。当输入超过了分配的缓冲区数组大小时，就可能会造成严重的后果，比如覆盖掉返回地址或者保存的寄存器值等等。
缓冲区溢出可能会导致网络攻击，比如输入中包含恶意代码，用指向恶意代码的指针覆盖返回地址，执行ret指令跳转到了恶意代码存放的位置。还有其他攻击的形式等等。

解决缓冲区溢出

有三种方式可以用于解决缓冲区溢出问题：

  1. 栈随机化。让栈的位置在程序每次运行时都有变化。
  2. 栈破坏检测。
  3. 限制可执行代码区域。

变长栈帧

对于拥有变长数组的函数来说，它的栈帧不是固定的，这个时候需要使用%rbp(base pointer)而不是%rsp作为栈指针进行管理。

浮点运算

浮点指令的发展，从SIMD到MMX，到SSE，以及最新的AVX，AVX2。这些指令都管理寄存器组中的数据，这些寄存器组在MMX中称为MM寄存器，SSE中称为XMM寄存器，AVX中称为YMM寄存器。MM是64位的，XMM是128位的，YMM是256位的。
浮点数拥有一套自己的操作：

  1. 浮点传送和转换指令；
  2. 浮点数的算术运算指令；
  3. 浮点数的位运算指令；
  4. 浮点数的比较运算指令。

参考文献

1.《CSAPP》