[CSAPP-I] 过程（函数栈帧） C语句的机器级表示（gcc -S）

1 C和机器指令

1.1 电平和二进制

给计算机通电后，计算机内导通的器件“带电”。不同器件的“带电程度”可能不同。可能有些器件的某个输出端的电压为5V，有的器件的某个输出端电压为1V。

人若将计算机内带5V电压的输出端的状态视为“1”，带1V电压的输出端的状态视为“0”。那么，计算机内一连串的输出端就可以被人视为一连串的0或1的序列。这一串0或1（b_nb_n-1 … b₁ b₀）的序列可以被解释为整数（b_n*2ⁿ+ b_n-1*2^n-1 + … b₁*2¹ + b₀*2⁰）、字符（串）、汉字或图像数据等的编码或其它，并将它们显示出来。

将只有0,1两个数字存在的集合作一些规定得到二进制集。由于编码这个抽象东西的存在，所以说存在计算机中的数据（东西）都是二进制（0,1序列）。[紫色的东西都需要对其额外的了解]

1.2 汇编指令和机器指令

指令集体系结构（汇编指令集）代表了机器级程序的格式和行为，对机器级编程来说是一种很重要的抽象。用汇编编写的程序经过汇编编译器后被转换为机器指令（二进制），且汇编指令与机器代码一一对应。汇编指令时机器指令的助记符，便于人理解程序。

Figure 1. 汇编指令和机器指令

1.3 C和汇编指令

C是在指令集体系结构基础之上的再次抽象，以方便程序员以接近于Americans的日常思维习惯编程。CPU只能识别机器指令（二进制），必须要将用C编写的程序转换为机器指令，过程为：C--> 汇编 -->机器码。C源程序的C语句和汇编指令非一一对应的关系，所以在C转换为汇编时，能得到怎么样的汇编指令，依靠具体的转换策略。这些转换策略被包含在“C编译器”中。

Figure 2. C语句到汇编指令

由于可以用不同的汇编指令来实现C中同一条语句或者数据结构，所以针对相同的C代码，不同平台的编译器（一般，编译器可能针对某个特定的平台如windowsx86、Linux来编写）产生的汇编指令不一定相同（选取汇编指令来实现C语句的机制和优化能力）。

2 平台

2.1 硬件

Table 1. 硬件(ls cpu)

Architecture：	i686(Intel 80386)
Byte Order：	Little Endian

 

2.2 操作系统

Table 2. 操作系统类型

操作系统（cat /proc/version）	位数（uname -a）
Linux version 3.2.0-4-686-pae	i686（32bit）

 

2.3 编译器

Table 3. 编译器信息

编译器（gcc -v）

gcc (Debian 4.7.2-5) 4.7.2

gcc有不同级别的优化能力，-O1，-O2等级。本笔记不使用任何优化选项（不同优化级别得到的汇编指令不同）。

3 C代码

3.1 main.c

#include "sub_fun.h"

int main(void)
{
        if_else_fun(1, 2);
        return 0;
}

3.2 sub_fun.c

//-------------------------------Data in C ----------------------------------//
//Array's mechanism in assembly
void array_fun(int n)
{
	int a[n];
	int b[2][3];
	
	a[n - 1]	= 0;
	b[1][2]		= 1;

}


//Pointer's mechanism in assembly
void pointer_fun(void)
{
        int i           = 0;
        int j           = 2;
        int *p;
        int **pp;

        p       = &i;
        *p      += 1;

        pp      = &p;
        *pp     = &j;
        **pp    = 1;

}

//Struct's mechanism in assembly
void struct_fun(void)
{
        struct e{
                int     i;
                char    c;
                int     *p;
        }evar;

        evar.i  = 1;
        evar.c  = 'a';
        evar.p  = &evar.i;
}


//Union's mechanism in assembly
char union_fun(void)
{
        union e{
                char    c;
                float   f;
        }evar;

        evar.f  = 1.0f;
	return evar.c;
}
//-------------------------------Data in C ----------------------------------//


//-------------------------------Control in C ----------------------------------//
//IF-ELSE in data control flow
int if_else_fun(int x, int y)
{
        if (x >= y) {
                return x - y;
        }else {
                return y - x;
        }
}


//SWITCH-case
int switch_case_fun(int x)
{
        switch (x) {
                case 0:
                        x       = ~x;
                        break;
                case 1:
                        x       += 1;
                case 2:
                        x       += 1;
                        break;
                case 99:
                        x       += 10;
                        break;
                default:
                        x       = 1;
                        break;
        }
        return x;
}

//DO-WHILE
void do_while_fun(int n)
{
        do {
                n--;
        } while(n);
}

//WHILE
void while_fun(int n)
{
        while (n) {
               n--;
        }
}
//FOR
void for_fun(int n)
{
        int i;
        for (i = 0; i < n; ++i) {
                i++;
                i--;
        }
}
//-------------------------------Control in C ----------------------------------//

4 将C转换为汇编指令

在Linux shell命令行下“man gcc”了解关于gcc的用法。将sub_fun.c和main.c放在同一个目录下。

使用gcc编译器的-S参数来得到C源文件对应的汇编文件：

gcc  -S  sub_fun.c gcc  -S  main.c

经过此gcc编译器的-S后，会在当前目录生成sub_fun.s和main.s两个文件。它们分别是sub_fun.c和main.c对应的汇编代码。在汇编文件中，所有以'.'开头的行都是指导汇编器和链接器的命令。目前只关心C到汇编中的一个（gcc (Debian 4.7.2-5) 4.7.2）机制，所以只在汇编文件中保留了汇编指令。

4.1 过程

《Linux C 编程一站式学习》第18，19章也有关于“函数栈帧”的讲解，笔记有“一个C源文件到可执行文件 [反汇编-函数栈帧 编译 链接]”。在此，再笔记一下C语言中调用函数的过程。

IA32用程序栈来支持过程调用。机器用栈来传递过程参数、存储返回信息、保存寄存器用于以后恢复，以及本地存储。为单个过程分配的那部分栈称为栈帧。最顶端的栈帧以两个指针界定，寄存器%ebp为帧指针，而寄存器%esp为栈指针。[《CSAPP》2e  P.149]

以%ebp和%esp在程序中所描述的现象来理解这两个寄存器的作用。可在《汇编语言》—王爽一书中打基础。

(1) 查看%ss, %esp,%ebp的虚拟地址值

将sub_fun.c和main.c编译链接成可执行程序：

gcc  sub_fun.c  main.c  –g gdb  a.out

Figure3. 程序运行时%esp和%ebp的值

(2) 函数栈帧

Figure 3中所查得到的%ebp和%esp是在未执行main程序中的任何语句时的值，故，我们可以从main()函数调用子函数开始了解函数调用过程（无call main）。图中绿色部分表示标绿指令的功能：

Figure4. C主函数main的汇编代码

_start调用main函数执行时，会自动完成红框中的汇编指令（andl $-16,%esp保证栈空间为16的整数倍，此平台采用补码表示有符号数，-16的补码为0xfffffff0）：

Figure5. 进入main函数为main函数分配栈空间

完成main函数栈空间分配后，再执行main函数内的语句即调用if_else_fun函数：

Figure6. 为if_else函数传递参数

给子函数传递的参数保存在调用者的栈空间内。

Figure7. call if_else_fun函数的操作（main函数栈帧形成）

执行完call语句后（call指令将下一条指令的地址入栈，并跳到被调用过程的起始处），将转到if_else_fun函数内运行，同理，查看进入if_else_fun函数后的%esp和%ebp中的虚拟地址值：

Figure8. 进入子函数时%esp和%ebp值

从Figure 8可以看出，进入if_else_fun连续为if_else_fun分配栈空间，首先将%ebp寄存器入栈保存起来，然后再将%esp的值赋给%ebp，这个过程为下图红色方框内容：

Figure9. 进入if_else_fun

这个过程栈发生的变化为：

Figure10. 两个函数的栈帧

因为if_else_fun内没有其它数据，所以栈帧只有4个字节。当执行指令执行到Figure 10的.L7处时（其它指令会在“C语句实现机制”中分析），本程序的栈帧开始被回收。如下图所示：

Figure11. if_else_fun栈帧回收

Figure12. if_else_fun函数返回

ret指令从栈中弹出地址，并跳转到这个位置。此时，%eip的值为main函数中的return 0语句的地址。即Figure 4中第9行语句处（将整型的返回值给%eax）。然后再执行leave指令（相当于movl %ebp, %esp 加popl %ebp的功能）：

Figure13. main函数执行leave，main函数栈帧完全释放

执行完leave指令后，还要执行ret指令，正确跳到调用main函数的下一个语句处继续执行程序：

Figure14. main函数返回

关于函数栈帧，可以在看过像《汇编函数》—王爽这一类书后再根据《Linux C编程一站式学习》自己画画。

4.2 C语句实现机制

(1) 数组

array_fun函数内定义了一个定长数组，一个变长数组。此函数在gcc (Debian 4.7.2-5) 4.7.2下的汇编代码为：

Figure15. arrar_fun函数在gcc –O1级下对应的汇编指令

上图中1中的代码是在为array_fun函数开辟栈空间（不包括数组的栈空间）。%ebp - %esp = 56 bytes。

%ebp+ 8是父函数的栈空间，所以%ebp + 8是父函数传递给array_fun函数的实参数n。

2中的代码是在为变长数组int a[n]开辟空间，红线标注的语句让array_fun函数的栈空间得到扩展，其大小跟参数n有关。经过对%eax进行计算（保证内存对齐等）后，将%eax的值作为数组a[n]的起始地址，并把它保存在-16(%ebp)中。

3中的代码是在计算a[n-1]的下标值n – 1，并将其保存在%edx中。

4中的代码是在给指定的数组元素赋值：movl $0, (%eax, %edx, 4)这是访问数组元素的机器级指令，代表访问数组元素的过程，表示给地址为4 * %edx + %eax的内存赋值为1，%eax就是数组a的起始地址值，4 * %edx为相对数组起始地址的偏移值；编译器发现只对数组b[2][3]的b[1][2]进行访问，干脆将整个数组优化为b[1][2]这个整型变量，将其保存在-20(%ebp)中。

然后回收给变长数组a分配的栈空间（movl %ecx, %esp），恢复%ebx的值（但从这个程序看，此句也显得多余），再返回到父函数中。

在array_fun函数的过程大概为下图所示：

Figure16. array_fun运行时的栈帧

传递给子函数实参的地址在父函数栈帧内，子函数内的局部变量在运行时分配在子函数栈帧内。

(2) 指针

pointer_fun的C代码和汇编代码如下：

Figure17. 实现C语言指针的机制

根据汇编代码，首先找到在pointer_fun内各变量的栈地址：

Figure18. pointer_fun局部变量的栈地址

求栈地址用“leal指令”；求栈地址内的内容用“()”。“指针”其实就是地址。间接引用指针就是将该指针放在一个寄存器中，然后在存储器引用中使用这个寄存器。

(3) 结构体

struct_fun的C代码和汇编源码如下：

Figure 19. struct_fun结构体实现机制

struct_fun的栈空间情况如下：

Figure20. struct_fun函数的栈空间分配

其中，evar.c是char类型变量，本只占一个字节，但因“内存对齐”的缘故，会空三个字节不用（内存间隙，上图灰色部分）。

(4) 联合

使用联合的函数union_fun的C代码和汇编代码如下：

Figure21. union实现机制

其中.LC0的内容为：

1065353216的十六进制表示为0x3f800000，它是IEEE浮点标准下1.0的编码。

movzbl指令将做了零扩展的字节传送到双字中。evar.f共占4个字节，evar.c占这四个字节中的一个字节（最高（大端）或最低字节（小端））。

(5) if-else（数据控制流）

使用if-else语句的函数if_else_fun的C代码和汇编指令如下：

Figure22. if-else实现机制

此版本的gcc编译器采用条件跳转指令（jl）和无条件跳转指令(jmp)来实现C语句的if-else分支。测试数据值，然后根据测试的结果来改变控制流或者数据流的方式是gcc实现控制的主要策略。见（6）条件数据传输中gcc采用的另一种策略。

(6) switch-case

sub_fun.c中switch_fun函数使用了switch-case语句，其C代码和对应的汇编指令如下（gcc无指定优化级别的情况下没有使用跳转表机制来实现switch-case）：

Figure23. switch-case实现机制

(7) do-while

Figure24. do-while实现机制

(8) while

Figure25. while实现机制

实现while时，将其转化为do-while，然后按照do-while的实现机制实现。

(9) for

Figure26. for实现机制

实现for循环时，也是先将其转化为do-while，然后按照do-while的实现机制实现。

5 总结

5.1 定长数组和变长数组

变长数组必须使用乘法来对下标伸展n倍，不能用一系列的移位和加法（对n未知）。乘法在一些处理器中会导致严重的性能处罚，但在这种情况下不可避免。

5.2 数组和指针访问过程区别（汇编指令层）

访问数组元素a[i]的过程为：

• 取a的值：movl %esp, %eax；
• 取i：movl  -4(%ebp), %ebx;
• 读a[i]：movl ( %eax, %ebx, sizeof(a[0]) ),%ecx。

访问指针元素p[i]的过程为：

•  取p内的值：movl  -8(%ebp), %eax；
• 取i：movl  -4(%ebp), %ebx;
• 读p[i]：movl( %eax, %ebx, sizeof(a[0]) ), %ecx。

其中，a存在%esp中，i存在-4(%ebp)中，p存在-8(%ebp)中，sizeof(a[0])表数组类型大小。

5.3 数据控制和条件控制

现在的处理器支持条件传送指令，实现分支的的策略就有了两种：数据转移和条件转移。

因为现代处理器采用流水线技术（可读《大话处理器》），所以数据转移比条件转移要好（当分支中的各表达式都容易计算时）。即使许多分支预测错误的开销会超过更复杂的计算，但gcc还是会使用条件控制转移。

5.4 栈空间分配策略

gcc坚持x86编程指导方针，也就是一个函数使用的所有栈空间必须是16的整数倍（4.2中为函数分配的栈都是16的整数倍）。

[2015.01.13–01.19]

Read 《CSAPP》 Note Over.