这篇文章是csapp第七节的阅读笔记

0x00 运行时栈

过程（procedures）是一个非常重要的抽象，它隐藏了一部分实现细节，对外提供一个功能。

在程序中的任何地方都可以随时调用这个过程，得到结果后继续执行。

也叫函数（function）、方法（method）等（后面还是统一叫函数吧）。

函数P调用函数Q，需要考虑以下几点：

• 控制转移（Passing control）：程序的执行从函数P转移到函数Q，具体是通过设置PC寄存器的值为Q的地址；
• 数据传送（Passing data）：函数P需要向函数Q传送参数，函数Q需要向函数P传递执行结果；
• 申请与释放内存（Allocating and deallocating memory）：函数Q需要申请内存来存储局部变量，返回后需要释放。

为了实现函数的机制，需要使用栈。下面就是运行时栈的结构：

• 栈是向下增长的（栈顶在下）；
• 每个函数都有自己的stack frame，在被调用的时候就创建好了；
• 有的stack frame是固定大小的，有的是变动的；
• 当前执行函数的stack frame在栈顶。

0x01 控制转移

函数P调用函数Q涉及到控制转移。

首先函数P要知道到哪里去找函数Q；函数Q执行完了也要知道怎么回去继续执行函数P。

这涉及到PC计数器，就是当前执行指令的地址。

当函数P需要调用函数Q的时候，将函数Q的入口地址保存到PC里，这样下一个指令执行的时候就可以到函数Q了。

为了能够使函数Q返回找到函数P，需要保存函数P的下一条指令的地址。

这个地址保存在栈里。

这些工作就是指令call完成的。

反过来，函数Q返回时需要将栈里P的地址弹出来，然后放入PC中，这些由指令ret完成。

其中两个call指令和jmp类似，一个是直接调用，一个是间接调用。

这个过程如下图：

0x02 数据传送

数据传送涉及到函数P传参数到函数Q，以及函数Q返回结果给函数P。

参数传递可以通过寄存器来完成，一共有六个寄存器负责参数传递：

如果有更多的参数，那么存入栈中。存入栈中的参数大小需要补齐到8的倍数。

这样函数Q就可以通过寄存器和出栈得到所有的参数了。

函数Q执行结果存入%rax中。

一个C例子：

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;
}

编译后：

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                        ; Return

调用函数Q的时候，栈里的情况如下：

0x03 栈上的局部存储

函数在执行的时候，可能需要存放一些临时变量。

这些临时变量有两个地方可以存：栈和指针。

先看看临时变量放进栈里的情况。

在栈上申请空间只需要减少%rsp的值就可以了，看一个例子。

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;
}

函数swap_add交换两个由指针指示的数，然后返回这两个数的和。函数caller对两个局部变量arg1和arg2取址然后作为参数传递给函数swap_add，这时函数caller就需要将这两个局部变量保存起来了。下面是函数caller的编译结果：

caller:
    subq    $16, %rsp        ; Allocate 16 bytes for stack frame
    movq    $534, (%rsp)    ; Store 534 in arg1
    movq    $1057, 8(%rsp)    ; Store 1057 in arg2
    leaq    8(%rsp), %rsi    ; Compute &arg2 as second argument
    movq    %rsp, %rdi        ; Compute &arg1 as first argument
    call    swap_add        ; Call swap_add(&arg1, &arg2)
    movq    (%rsp), %rdx    ; Get arg1
    subq    8(%rsp), %rdx    ; Compute diff = arg1 - arg2
    imulq    %rdx, %rax        ; Compute sum * diff
    addq    %16, %rsp        ; Deallocate stack frame
    ret                        ; Return

通过简单减少%rsp的值就可以在栈上申请空间了，通过增加%rsp的值就可以释放空间。

0x04寄存器上的局部存储空间

寄存器是多个函数共享的，但是我们要保证，当调用者（caller）调用被调者（callee）时，callee不能覆盖caller在寄存器中保存使用的值。

寄存器%rbx，%rbp，%r12到%r15是callee saved寄存器，当函数P调用函数Q时，函数Q必须保持这些寄存器的值。

函数Q要么在执行过程中不改变这些寄存器的值，要么先保存这些值，使用完之后将原来的值填回去。

除了上面的那些寄存器，还有%rsp之外，其余的都是caller saved寄存器。

这意味着，这些寄存器的值可以被任何函数更改。

可以这样理解，函数P执行过程中，设置好了这些寄存器的值，然后调用函数Q，函数Q可以随意更改这些寄存器的值，在调用函数Q之前是函数P的责任来设置好这些寄存器的值。

例子：

long P(long x, long y) {
    long u = Q(y);
    long v = Q(x);
    return u + v;
}

函数P调用函数Q两次，在第一次调用中，函数P需要保存x的值以备后面使用；同样，在第二次调用的时候，需要保存Q(y)的值。

编译结果：

P:
    pushq %rbp             ; Save %rbp
    pushq %rbx             ; Save %rbx
    subq $8, %rsp         ; Align stack frame
    movq %rdi, %rbp     ; Save x
    movq %rsi, %rdi     ; Move y to first argument
    call Q                 ; Call Q(y)
    movq %rax, %rbx     ; Save result
    movq %rbp, %rdi     ; Move x to first argument
    call Q                 ; Call Q(x)
    addq %rbx, %rax     ; Add saved Q(y) to Q(x)
    addq $8, %rsp         ; Deallocate last part of stack
    popq %rbx             ; Restore %rbx
    popq %rbp             ;Restore %rbp
    ret

这里使用了两个callee saved寄存器，%rbp用来保存x的值，%rbx用来保存Q(y)的值。

函数首先需要将这两个寄存器中的值保存到栈中，当函数执行完的时候从栈中取出来放回到对应的寄存器中。

push的顺序刚好和pop相反。

0x05 递归过程

每一个函数在栈上都有自己的栈空间。

这样就可以执行共创中调用了。一个例子：

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

编译后：

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
    leaq -1(%rdi), %rdi  ; Compute n-1
    call rfact             ; Call rfact(n-1)
    imulq %rbx, %rax     ; Multiply result by n
.L35:                     ; done:
    popq %rbx             ; Restore %rbx
    ret                 ; Return

这里使用寄存器%rbx来保存n的值，不过需要先将%rbx里原来的值保存到寄存器中。

这样，当第9行调用rfact(n-1)返回的时候，返回的结果保存于%rax中，同时n的值在%rbx中。

这样两个值都有，就可以执行C程序中第6行的计算了。

这和别的函数调用没啥区别。