运行时栈

栈

C语言过程调用机制的一个关键特性在于使用了栈数据结构提供的后进先出的内存管理原则。在函数P调用函数Q中，当Q在执行时，P以及所有在向上追溯到P的调用链中的函数，都是暂时被挂起的。当Q运行时，它只需要为局部变量分配新的存储空间，或者设置到另一个函数的调用。另一方面，当Q返回时，任何它所分配的局部存储空间都可以被释放。因此，程序可以用栈来管理它的函数所需要的存储空间，栈和程序寄存器存放着传递控制和数据、分配内存所需要的信息。当P调用Q时，控制和数据信息添加到栈尾。当P返回时，这些信息会释放掉。

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

当x86-64函数需要的存储空间超出寄存器能够存放的大小时，就会在栈上分配空间。这个部分称为函数的栈帧(stack fram)。通用的栈帧结构如下图所示：
通用栈帧结构
当前正在执行的函数的帧总是在栈顶。当函数P调用函数Q时，会把返回地址压入栈中，指明当Q返回时，要从P的哪个位置继续执行。我们把这个返回地址当做P的栈帧的一部分，因为它存放的是与P相关的状态。Q的代码会扩展当前栈的边界，分配它的栈帧所需的空间。在这个空间中，它可以保存寄存器的值，分配局部变量空间，为它调用的过程设置参数。大多数函数的栈帧都是定长的，在函数的开始就分配好了。但是有些函数需要变长的帧，这个问题在后面讨论。通过寄存器，函数P可以传递最多6个整数值（也就是指针和整数），但是如果Q需要更多的参数，P可以在调用Q之前在自己的栈帧里存好这些参数。

为了提高空间和时间效率，x86-64函数只分配自己所需要的栈帧部分。例如，许多函数有6个或者更少的参数，那么所有的参数都可以通过寄存器传递。因此，上图中画出的某些栈帧部分可以省略。实际上，许多函数甚至根本不需要栈帧。当所有的局部变量都可以保存在寄存器中，而且该函数不会调用任何其他函数时，就可以这样处理。

转移控制

将控制从函数P转移到函数Q只需要简单的把程序计数器(PC)设置为Q的代码的起始位置。不过，当稍后从Q返回的时候，处理器必须记录好它需要继续P的执行的代码位置。在x86-64机器中，这个信息是用指令 call Q调用函数Q来记录的。该指令会把地址A压入栈中，并将PC设置为Q的起始地址。压入的地址A被称为返回地址，是紧跟在call指令后面的那条指令的地址。对应的指令ret会从栈中弹出地址A，并把PC设置为A。

下表给出的是call和ret指令的一般形式：

指令 描述
call Label 函数调用
call .Operand 函数调用
ret 从函数调用中返回

call指令有一个目标，即指明被调用过程起始的指令地址。同跳转一样，调用可以是直接的，也可以是间接的。在汇编代码中，直接调用的目标是一个标号，而间接调用的目标是*后面跟一个操作数指示符。

数据传送

当调用一个函数时，除了要把控制传递给它并在过程返回时再传递回来外，函数调用还可能包括把数据作为参数传递，而从函数返回还有可能包括返回一个值。x86-64中，大部分函数间的数据传送是通过寄存器实现的。例如，参数在寄存器%rdi、%rsi和其他寄存器中传递。当函数P调用函数Q时，P的代码必须首先把参数复制到适当的寄存器中。类似的，当Q返回到P时，P的代码可以访问寄存器%rax中的返回值。

x86-64中，可以通过寄存器最多传递6个整型（例如整数和指针）参数。寄存器的使用是有特殊顺序的，寄存器使用的名字取决于要传递的数据类型的大小。如下表所示的传递函数参数的寄存器：

操作数大小(位) 参数1 参数2 参数3 参数4 参数5 参数6
64 %rdi %rsi %rdx %rcx% %r8 %r9
32 %edi %esi %edx %ecx %r8d %r9d
16 %di %si %dx %cx %r8w %r9w
8 %dil %sil %dl %cl %r8b %r9b

如果一个函数有大于6个整型参数，超过6个的部分就要通过栈来传递。假设函数P调用函数Q，有n个整型参数，且n>6。那么P的代码分配的栈帧必须要能容纳7到n号参数的存储空间，如下图所示：
通用栈帧结构
要把参数1-6复制到对应的寄存器，把参数7-n放到栈上，而参数7位于栈顶。通过栈传递参数时，所有的数据大小都向8的倍数对齐。参数到位以后，程序就可以执行call指令将控制转移到函数Q了。函数Q可以通过寄存器访问参数，有必要的话也可以通过栈访问。相应的，如果Q也调用了某个有超过6个参数的函数，它也需要在自己的栈帧中为超出6个部分的参数分配空间，如上图中标号为”参数构造区“的区域所示。

参数传递示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
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;
}
//该函数有8个参数，包括字节数不同的整数(8,4,2,1)和不同类型的指针(每个都是8字节的)
//参数传递：
//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)   从内存读入4个字节
    addb %dl, (%rax)      ; *a4p += a4   (8  bits)   只用其中的低位一字节
    ret                   ; return

从上面的例子可以看到，前面6个参数通过寄存器传递，后面2个通过栈传递。作为过程调用的一部分，返回地址被压入栈中，因而这两个参数位于相对于栈指针距离为8和16的位置。

在汇编代码中，我们可以看到根据操作数的大小，使用了add指令的不同版本：long使用addq，int使用addl，short使用addw，而char使用addb。

栈上的局部存储

一些函数运行时不需要超出寄存器大小的本地存储区域，而另外一些函数局部数据必须放在内存中，常见的情况包括：

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

一般来说，函数通过减小指针在栈上分配空间。分配的结果作为栈帧的一部分，标号为”局部变量“。

示例1：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
//交换指针xp和yp的值，并返回这两个值的和。
long swap_add(long *xp, long *yp){
    long x = *xp;
    long y = *yp;
    *xp = y;
    *yp = x;
    return x + y;
}

long caller(){
    long arg1 = 534;
    long arg2 = 1057;
    long sum = swap_add(&arg1,&arg2);
    long diff = arg1 - arg2;
    return sum * diff;
}

caller生成的汇编代码：
1    caller:
2        subq  $16, %rsp      ; allocate 16 bytes for stack frame
3        movq  $534, (%rsp)   ; store 534 in arg1
4        movq  $1057, 8(%rsp) ; store 1057 in arg2
5        leaq  8(%rsp), %rsi  ; compute &arg2 as second argument
6        movq  %rsp, %rdi     ; compute &arg1 as first argument
7        call  swap_add       ; call swap_add(&arg1,&arg2)
8        movq  (%rsp), %rdx   ; get arg1
9        subq  8(%rsp), %rdx  ; compute diff = arg1 -arg2
10       imulq %rdx, %rax     ; compute sum * diff
11       addq  $16, %rsp      ; deallocate stack frame
12       ret                  ;  return

从上面的例子可以看到：
1.caller代码开始的时候把栈指针减掉了16；实际上这就是在栈上分配了16个字节。
2.局部变量arg1和arg2存放在栈帧中相对于栈指针的偏移量为0和8（汇编第3-4行）。
3.当对swap_add的调用完成后，caller的代码会从栈上取出这两个值，计算它们的差（汇编第8-9行），再乘以swap_add在寄存器%rax中返回的值（汇编第10行）。
4.最后，该函数把栈指针加16，释放栈帧（第11行）。

通过这个例子可以看到，运行时栈提供了一种简单的、在需要时分配、函数完成时释放局部存储的机制。

寄存器中的局部存储空间

寄存器组是唯一被所有过程共享的资源。虽然在给定时刻只有一个函数是活动的，我们仍然必须确保当一个函数调用另外一个函数时，被调用者不会覆盖调用者稍后会使用的寄存器值。

为此，x86-64采用了一组统一的寄存器使用惯例，所有的函数包括程序库都必须遵循。

根据惯例，寄存器%rbx、%rbp和%r12-%r15被划分为被调用者保存寄存器。当函数P调用函数Q时，Q必须保存这些寄存器的值，保证它们的值在Q返回到P时与Q被调用时是一样的。

过程Q保存一个寄存器的值不变，要么就是根本不去改变它，要么就是把原始值压入栈中，改变寄存器的值，然后在返回前从栈中弹出旧值。压入寄存器的值会在栈帧中创建标号为”保存的寄存器“的一部分。

有了这条惯例，P的代码就能安全的把值存在被调用者保存寄存器中，调用Q，然后继续使用寄存器中的值，不必担心值被破坏。

所有其他的寄存器，除了栈指针%rsp，都分类为调用者保存寄存器。者就意味着任何函数都能修改它们。可以这样来理解”调用者保存“这个名字：函数P在某个此类寄存器中有局部数据，然后调用函数Q。因为Q可以随意修改这个寄存器，所以在调用之前首先保存好这个数据是P(调用者)的责任。

示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
long P(long x, long y){
    long u = Q(y);
    long v = Q(x);
    return u + v;
}

汇编代码：
； x in %rdi , y in %rsi
1    P:
2        pushq   %rbp       ; save %rbp
3        pushq   %rbx       ; save %rbx
4        subq    $8, %rsp   ; align stack frame
5        movq    %rdi, %rbp ; save x
6        movq    %rsi, %rdi ; move y to first argument
7        call    Q          ; call Q(y)
8        movq    %rax, %rbx ; save result
9        movq    %rbp, %rdi ; move x to first argument
10       call    Q          ; call Q(x)
11       addq    %rbx, %rax ; add saved Q(y) to Q(x)
12       addq    $8, %rsp   ; deallocated last part of stack
13       popq    %rbx       ; restore %rbx
14       popq    %rbp       ; restore %rbp
15       ret

从上面的例子可以看到：
1.函数P两次调用Q，在第一次调用中，必须保存x的值以备后面使用。
2.类似的，在第二次调用中，也必须保存Q(y)的值。
3.汇编代码使用了两个被调用者保存寄存器：%rbp保存x，%rbx保存Q(y)的值。
4.在函数的开头，把这两个寄存器的值保存到栈中（汇编第2-3行）。
5.在第一次调用Q之前，把参数x复制到%rbp（汇编第5行）。
6.在第二次调用Q之前，把Q(y)结果复制到%rbx （汇编第8行）
7.在函数的结尾，把%rbx、%rbp从栈中弹出，恢复这两个被调用者保护寄存器的值。注意它们的弹出顺序与压入顺序相反，说明了栈的后进先出规则。