【CSAPP】笔记-Cp3-3-控制与过程数据存储

跳转指令jmp .L和jmp *e*会导致程序在执行时切换到另一个位置。前一种方式中，它的参数L是一个标示符，这个标示符类似于高级语言中的函数名，用于标示一段程序的开始，汇编中就是用这种方式来管理子程序的；后一种方式中，它的参数e是一个寄存器或者以寄存器为地址的(%eax)这种存储器的值，这些值将会给当做跳转地址。
还有一些跳转叫做条件跳转，它们是基本跳转语句的特化版本，比如je就是当ZF位为1时跳转之类的。它们也是高级语言条件语句的基础。

至于C语言的条件语句翻译成汇编，一般都是先开一个条件跳转语句，然后后面更上else的内容。

循环

循环语句在C中有do-while、while和for，太基础就不细说了。

do-while它们可以对应汇编中的goto和条件跳转指令的组合，像是：

loop:
    xxx
    je next
    goto loop

while和do-while类似，但它的判断放在loop段的开始，这允许产生零长度的循环：

loop:
    je next
    xxx
    goto loop

for一般等价于while形式，是另一种写法。但当和continue语句合作是可能有例外。详见习题24。

条件传送语句

条件传送语句是现代CPU都有的一条指令，它本质上是以下C代码的翻译：

int absdiff(int x, int y){
    return x < y ? y - x : x - y;
}

在汇编中，会先计算好y-x和x-y，然后通过一条cmovl指令（l表示小于）直接判断前面cmp的比较结果即条件码然后送走y-x或者x-y而不是通过条件跳转。这样做的效率一般会很高，这是由于CPU内部的流水线采用的分支预测机制。因为对于此指令，处理器只是读数据、检查条件码、然后更新或者不动目的寄存器，不会有额外的跳转。

当然这个指令并非时时有效，由于它要事先计算两个分支的结果，所以可能会造成无谓的计算浪费，也受编译器的影响。

switch指令

对应于C中的switch语句，当分支较多并且每个分支的条件间隔较小时，会生成一个跳转表，有个这个表，可以使得分支实现和复杂度无关，相对于经典的条件转移，利用查表的方式可以说复杂度都是固定的，是并行判断。

过程

过程调用将数据和控制进行跳转，而后又可以恢复现场继续执行刚才的操作。这是通过转移到控制和转移出控制实现的。

栈帧

栈帧实际上就是栈的一种应用，它是为单个过程所分配的栈，由存放于%ebp中的帧指针和存放于%esp中的栈指针控制。

转移控制

当一个过程被call指令调用时，首先将返回地址入栈，然后当前一些需要保护的局部变量什么的入栈，保护现场，随后跳转到被调用过程的首地址，调用结束后再使用leave指令做好准备，之后ret指令恢复现场并返回跳转前的地址继续。

调用控制中的寄存器分配是约定俗成的%eax、%edx和ecx被分配给被调用者，可以被覆盖，而%ebx、%esi和%edi则分配给调用者，再覆盖之前要先入栈以便恢复。

对于递归过程，编译器会将每次函数对自身的调用都视为调用一个其他的函数，本质上并无区别。

数组和结构体

数组是一种聚合数据类型，它在C中实现很简单，为T A[N]的形式，这段代码会在内存中分配N个数据类型T需要的内存空间，A作为一个标示符，是一个指向数组开头的指针，而A和下标的组合即可给这个指针加上偏移来访问数组内的任意数据。

比如定义数组char A[8]，首先分配8个字节的内存，然后将A指向这八个字节的开头，A[4]则构造A+4的指针，可以用其访问数组中的第四个数据。这在汇编中是movl (%edx, %ecx, 4), %eax。

本质上，我们使用A[i]相当于先得到元素A[i]的引用，然后用*A[i]来获得该地址的值。

嵌套数组

即多维数组，比如int A[5][5]，这和一般数组没什么两样，只不过在计算地址的时候会多一套工序，考虑你是在一个二维矩阵中取值就可以了，比如取值A[i][j]，那么地址就是A + 4(5i + j)。

定长和变长数组

定长数组是指大小在编译期就能就确定的的数组，而变长数组则不然，可能会在运行时动态改变。对于前者，尤其是多维的情况下，在编译的时候可以将其地址计算优化为常数乘法，而后者不但不能事先分配内存，必须在需要的时候才动态运算和分配，并且在取值时也要动态使用乘法来计算，所以性能会有所下降。

结构

C中的结构struct声明创建一个数据类型，将可能不同类型的对象聚合到一个对象，不同的对象用名字来引用。它本质上是方便编程的，因为对于数据本身而言，其在内存上是不变的，结构仅仅是改变去解释他们的方式，每个名字对应一个偏移，而这个偏移用于计算地址，比如：

struct S{
    int i;
    char c;
    short s;
}

S总共占据7个字节，如果其首地址为0，则S.i地址为0，S.c为4，S.s为5。

由于结构的存在，我们可以非常方便得管理聚合型数据，合理利用它也可以免除数据类型转换、新建内存的开销。

结构中的对象也可以是指针，这可以用于仿造OOP，比如将指针指向一个函数。

联合

联合union和struct不同，它用于用不同的类型去解释相同的数据，联合中所有部分的地址偏移都是一致的，它们只是用不同的方式去解释一段数据。比如：

union U{
    int i;
    char c;
    double d;
}

U会占据8字节，即double的长度，其中i、c、d的地址偏移都是0。

数据对齐

数据对齐对于提高存储器读写性能很关键，原则来讲，如果一个类型占用字节数是K，那么其地址应当是K的倍数。这就要求short类型的地址最低位为0而int型为00。对于Windows系统，对齐非常严格按照上述规则执行，而对于unix，8字节只需对齐4字节。
由于SSE指令要求存储器地址是16的倍数，所以栈帧的长度都是16的整数倍。

存储器越界引用和缓冲区溢出

缓冲区溢出是一个问题，比如在存储一个字符串时，如果没有分配足够的空间，便会发生溢出。发生溢出时，会错误覆盖栈帧中寄存器的值，这会导致被保存的现场不可恢复、代码无法正确返回等等，可能受到严重的攻击。比如库函数gets、strcpy等都有这个问题。好一点的方法是使用他们的具有限制最大长度的替代函数fgets等。

这种错误常被用于网络攻击，比如给字符串内巧妙加入一些可执行代码的字节编码，然后让其溢出，覆盖返回地址，这样就可以执行攻击代码。

对抗

对抗溢出攻击有几种方式。其中一种是栈随机化，它给程序端之前分配一些随机的、不使用的空闲空间，来是的程序的实际地址发生偏移，这样可以让程序字段的地址不可预测，是的攻击程序对地址的把握困难，这可以消除一部分影响。栈随机化被扩展后是地址空间布局随机化(ASLR)，除了栈之外，全局变量、堆等都要随机化。

另一种方法是栈破坏检测，也就是在栈帧的局部缓冲区与栈状态之间存储一个哨兵，被称为栈保护者，程序运行中不断检测它，当其被改变，即破坏时便会识别出被入侵。

还有一种就是限制可执行区域，即限定代码可以存储在什么区域。

习题

13

A. l为32位，比较为对补码的小于，所以为int。
B. w为16位，比较对补码，所以为short。
C. b为8位，比较对无符号数，所以为uchar。
D. l为32位，比较是不等于或非零操作，所以为int活uint。

14

和13类似。

15

A. 0x8048291 + (0x05 = 5)
B. 0x8048359 + (0xe7 = -25) C. 0x8048391 - (0x12 = 18)
D. 0x80482c4 + (0xffffffe0 = -32)
E. 0x8049ffc的小端是0xfc9f0408

16

A. 不想写goto，略过。
B. 本质上是吧p && a > 0拆分为了两部分来实现。

17

A. 简单，略过。
B. 两种方法等价，但是!t这种判断在没有else的状况下可以节省代码量，和if (!x) return;一样。

18

int test(int x, int y){
    int val = x;
    if(x < -3){
        if(x > y)
            val = x * y;
        else
            val = x + y；
    }
    else if(x > 2){
        val = x - y;
    }
    return val;
}

19

A. 这是一个数学问题， $n! \le 2^{32} - 1$ 即可。
B. $n! \le 2^{63} - 1$ 。

20

寄存器	初始值
%eax	x
%ecx	y
%edx	n

B. do的是body，while后的是test，前者对应.L2中的addl、imull、subl，后者则是testl、jle、cmpl、jl。
C. 略过。

21

A. 这是a+b的结果。
剩下的题略过。

22

基础，略过。

23

基础，略过。

此函数的目的在于将传入参数x进行按位镜像。

24

A. 会导致无限循环。
B. 很简单，在body之前加上判断跳转回loop。

25

概率题，套上面公式可得 $T_MP = (31 - 16)*2 = 30$ 个周期，错误时需要46个周期。

26

\运算符，本质上是为了解决负数情况下的偏置问题。

27

int test(int x, int y){
    int val = 4 * x;
    if(y > 0){
        if(x < y){
            val = x - y;
        }
        else{
            val = x ^ y;
        }
    }
    else if(y < -2){
        val = x + y;
    }
    return val;
}

28

略过。

29

int switcher(int a, int b, int c){
    int answerl
    switch(a){
        case 5:
            c = b ^ 15;
        case 0:
            answer = c + 112;
            break;
        case 2:
        case 7:
            answer = (c + b) << 2;
            break;
        case 4:
            answer = a;
            break;
        default:
            answer = b;
    }
    return answer;
}

30

A. 被设置为pop指令的地址。
B. 这不是一个过程调用，他没有ret，控制和指令顺序一致，返回值从栈中弹出。
C. 这是IA32将PC的值放到整数寄存器中唯一的方法。

31

除了必须被保存的三个寄存器之外，其他寄存器随意被被更改，不会影响调用者的行为。

32

int fun(short c, char d, int *p, int x)

33

略过。这道题主要让我们明白编译器会分配大量不会使用的空间，这可能是为了数据对齐。

34

A. %ebx保存x的值，所以它可以被用于计算表达式结果。
B.

int rfun(unsigned x){
    if(x == 0){
        return 0;
    }
    unsigned nx = x >> 1;
    int rv = rfun(nx);
    return (x & 0x01) + rv; 
}

C. 它计算x中所有位的和。

35

GCC为long double分配12个字节。
指针类型固定占用4个字节。

数组	元素大小	整个数组大小	起始位置	元素i
short S[7]	2	14	$x_S$	$x_S+2i$
short *T[3]	4	12	$x_T$	$x_T+4i$
short **U[6]	4	24	$x_U$	$x_U+i$
long double V[8]	12	96	$x_Y$	$x_Y+12i$
long double *W[4]	4	16	$x_W$	$x_W+4i$

36

表达式	类型	值	汇编代码
S+1	short *	$x_S+2$	leal 2(%edx), %eax
S[3]	short	$M[x_S+6]$	movw 6(%edx), %ax
&S[i]	short *	$x_S+2i$	leal (%edx, %ecx, 2), %eax
S[4*i+1]	short	$[x_S+8i+2]$	movw 2(%edx, %ecx, 8), %ax
S+i-5	short *	$[x_S+2i-10]$	leal -10(%edx, %ecx, 2), %eax

37

M = 5, N = 7

38

详见代码。

这样的写法对特定的规则优化，能够消除乘法，提高效率。

39

A. 0，4，8，16
B. 24个字节
C.

void sp_init(struct prob *sp){
    sp -> s.x = sp -> s.y;
    sp -> p = $(sp -> s.x);
    sp -> next = sp;
}

40

略过。

41

A. 4字节对齐。
B. 4字节对齐。
C. 2字节对齐。
D. 4字节对齐。
E. 4字节对齐。

看基本类型里最大的K。

42

A. 基础，略过。
B. 4字节对齐。
C. 按照字节大小降序排列即可，最终总和是32。

点击查看评论