过程是怎么实现的. 过程在不同的语言中的表现形式不同, 比如函数, 方法等.但其底层都有一些共同的特性, 假设过程P调用过程Q:
- 传递控制: 进入Q的时候, 程序计数器的地址很显然要被设置成Q的起始指令所在的内存. 在返回的时候,则需要将程序计数器设置为P调用Q的指令之后的那条指令的地址.
- 传递数据: P要将参数传递给Q, Q要想办法把结果返回给P
- 分配和释放内存:Q在开始执行之前,要为其分配空间; 执行结束之后,必须释放空间
运行时栈
如果过程需要的存储空间超过了寄存器的大小,就会在栈上分配空间. 分配的部分叫做这个过程的栈帧(Stack Frame). 一般不超过6个的参数都可以通过寄存器传递.
超过的部分则保存在调用者的栈帧中.此外在调用的时候,栈帧最下边是一个返回地址, 指示当返回的时候到哪里去继续执行.
所有的参数都可以保存在寄存器中或者通过寄存器传递, 则就不会需要栈帧.
看到这里虽然还没有具体看后边的流程, 但终于从理论上彻底明白了栈帧, 还有变量作用域的问题. 当前栈帧里找不到, 如果之前有定义, 肯定是到上边的栈帧中去寻找.
转移控制
先是两个指令, 就是调用和返回指令:
call Label or *Operand, 可以跟标号或者操作数. 执行callq指令的时候, 会在当前栈里压入callq之后那条指令的地址.
然后将PC设置成Q的第一条指令.ret, 返回指令. 从前边已经知道, 如果过程返回值, 那个值就会放在%rax寄存器当中. ret指令还一个作用是会把callq之后
那条指令的地址从栈里弹出, 然后把程序计数器设置成这条指令的地址.
X86-64里这两条指令也可以写成callq和retq.
练习 3.32
| 指令 | 当时状态(指令执行前) | ||||||||
|---|---|---|---|---|---|---|---|---|---|
| 标号 | PC | 指令 | %rdi | %rsi | %rax | %rsp | * %rsp | 描述 | |
| M1 | 0x400560 | callq | %rdi | – | – | 0x7fffffffe820 | _ | 调用 first(10) | |
| F1 | 0x400548 | lea | 10 | – | – | 0x7fffffffe812 | 0x400565 | callq将之后标号地址压入栈中,设置程序计数器为跳转地址 | |
| F2 | 0x40054C | sub | 10 | 11 | – | 0x7fffffffe812 | 0x400565 | lea指令执行完毕, %rsi被更新 | |
| F3 | 0x400550 | callq | 9 | 11 | – | 0x7fffffffe812 | 0x400565 | sub指令执行完毕,又到调用新函数的地方,将标号地址压入栈中, 设置程序计数器为跳转地址 | |
| L1 | 0x400540 | mov | 9 | 11 | – | 0x7fffffffe804 | 0x400555 | callq指令执行完毕 | |
| L2 | 0x400543 | imul | 9 | 11 | 9 | 0x7fffffffe804 | 0x400555 | mov将%rdi 复制到 %rax之后的状态 | |
| L3 | 0x400547 | retq | 9 | 11 | 99 | 0x7fffffffe804 | 0x400555 | %rax = %rax * %rsi, 得到结果99 | |
| F4 | 0x400555 | repz retq | 9 | 11 | 99 | 0x7fffffffe812 | 0x400555 | 从L3返回 | |
| M2 | 0x400565 | mov | 9 | 11 | 99 | 0x7fffffffe820 | – | 从F4返回到main程序 | |
感谢下边朋友的回复, 这里移动是正确的, 把十六进制看成十进制了……
数据传送 – 寄存器传参规则
刚才的转移控制看完了. 但是刚才的函数之间互相传递参数和返回值, 全部是通过寄存器. 更多的参数还可以通过栈. 来详细看看.
首先是通过寄存器传递参数(注意直到浮点的部分之前, 都是讲的传递整型参数或者指针), 在参数小于等于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 |
如果过程P要向Q传递超过n>6个参数, 注意, 要在P的栈帧上分配n-6的空间用来保存参数.
在P调用Q之前, 按照上边的规则, 将 1-6 号参数复制到相应的寄存器, 把 剩下的 n – 6个参数, 倒序依次压入栈中, 也就是说第7个参数位于栈顶.
在通过栈传递数据时, 所有的大小都对齐到8的倍数. 上边的所有参数都到位之后, 就可以执行 callq 转移控制. 此时的栈顶更新为callq的 下一条指令的地址.
控制权移交给Q的指令后, Q 可以通过寄存器访问 1-6 号参数, 7-n 号参数, 则可以通过栈来访问.
如果Q调用其他过程, 也超过 6 个参数,也需要在自己的栈帧中分配空间. 为超出的参数分配的空间, 叫做参数构造区.
换成数字来说, 在callq进入Q的指令之后那一瞬间, %rsp指向callq下一条指令的地址, %rsp+8 就是第7个参数, %rsp+16 就是第8个参数, 依次类推.即使一个参数的数据类型小于64位, 也是占据8个字节的空间. 从低位开始排布
练习题 3.33 逻辑推理
由于代码的 return 里返回的是6, 所以可以知道 a 和 b 两个数一个是 4 位长, 一个是 2 位长. 而两个指针必定是8位长度.
假如a 是 4 位长度, 则一开始扩展%edi符号实际上操作的是a, 那么之后把a加到(%rdx)上边,说明 %rdx中是u. 对应的, sil中是b, %rcx中是v.
假如b 是 4 位长度, 则一开始扩展%edi符号实际上操作的是b, 那么之后把b加到(%rdx)上边,说明 %rdx中是v. 对应的, sil中是a, %rcx中是u.
然后看指令, 第一个addq是64字节, 则指针指向的数也是64字节. 第二个addb是加一个字节, 所以指针是 char * 类型.
两种情况如下:
| %rdi | %rsi | %rdx | %rcx |
|---|---|---|---|
| a int | b short | u long * | v char * |
| b int | a short | v long * | u char * |
数据传送 – 局部存储
这样就解决了参数传递的问题, 还有一个问题就是在过程Q中的计算所需的局部数据, 超出了寄存器的存储能力, 这些局部数据, 也会被放置在Q的栈帧中.
在当前过程运行结束之后, 指令会将栈指针向上移动, 栈指针将向上移动过所有局部变量和参数构造区, 也就是将这些空间全部释放.
实际上目前为止, 就看过了局部变量和参数构造区().局部构造变量相比参数构造区, 是当前调用者自己使用, 所以更靠近栈的底部. 在栈结构里, 还有一块被保存的寄存器. 这块是什么玩意呢.
答案就是, 当前过程Q必须向调用者P保证, 有一些寄存器的内容, 在从Q返回的时候, 与P调用Q的那时候, 值不变. 因为在调用Q结束之后, 仅仅只有%rax返回值得到更新, 而P要继续使用的那些寄存器, 不能够发生变化.
这些寄存器, 就被称作被调用者保存寄存器. 这个名字我实在觉得有些拗口, 应该叫做被调用者保证寄存器还好理解一些, 相当于P对Q说, 现在把计算机交给你了, 但是这几个寄存器, 交给你的时候是什么样子, 必须原封不动的交回来. 其他的随便你.
被调用者必须保证的寄存器是 %rbx, %rbp 和 %r12 – %r15. callq 进入Q的时候, 和ret的时候, 这些寄存器值必须不变, 至于过程中间怎么玩弄这些寄存器, P是不管的.
所以对于Q来说, 要保持这些寄存器的值有两种办法, 一种是压根就不去改动其中的值, 只复制其中的值到自己的栈帧中来使用; 还一种方法就是我先把所有的被调用者保存寄存器的值都保存了, 然后该用哪个用哪个, 在ret之前, 一一还原好, 外加%rax一起还给P完事.
有了被调用者保存寄存器, 自然有调用者保存寄存器, 除了上边的那些寄存器以及栈指针%rsp寄存器之外, 剩下的都是调用者保存寄存器, 也就是对于P来说, 在调用Q的时候, 这些寄存器就交给你Q随便玩, 里边的东西我都已经保存好了, 你玩坏也没有关系, 等你调用结束之后, 我不依赖其中的数据, 而是我自己保存的数据.
现在就可以知道了, 栈帧图的最上边那块被保存的寄存器, 其实就是当前程序要使用到的调用者保存寄存器的内容. 其实本质上, 我觉得这个东西和局部变量也是同一回事情, 都是由当前过程自己使用的. 而参数构造区, 还会由另外一个过程来使用甚至过程的子过程来使用.
读到这里, 基本上就会明白, 函数传值为什么是一个局部变量, 就是因为当前过程要使用的参数, 都要从父过程的栈帧里复制出来使用, 不能直接修改父过程的栈帧. 不管传过来的是指针还是整数, 用完之后栈指针一回弹, 一切皆成空.
这里自己再把CSAPP的例子过一遍, 免得回来看的时候还要在想:
long P(long x, long y) {
long u = Q(y);
long v = Q(x);
return u + v;
}
对应的汇编代码和分析如下:
P:
pushq %rbp 保存%rbp的值, 这里注意, 既然%rbp是被调用者保存寄存器, P这个过程本身, 必须向调用者保证不会改变其中的值, 所以要把寄存器的值入栈. 同样,Q过程也必须保证这两个寄存器在P交给Q之前和之后不能变.
pushq %rbx 和上边一行一样, 这两个寄存器都是被调用者保存寄存器. 这两行也说明, P过程采取的是在过程中操作这两个寄存器, 返回的时候还原其中值的方法.
subq $8, %rsp 栈指针减8个字节, 这8个字节是用来装本地变量, 也就是第一次调用Q的结果u
movq %rdi, %rbp 开始使用%rbp寄存器了, 把参数 x 的值复制到其中
moveq %rsi, %rdi 把参数 y 的值复制到 %rdi 中, 因为马上要调用 Q(y), 必须保证放置第一个参数的寄存器 %rdi 中的值是y
callq Q 调用Q, 此时参数1寄存器%rdi中的值是y. 注意, 调用Q之前的被调用者保存寄存器 %rbp 现在是 x, %rbx除了被保存, 没有用过. 在Q返回的时候, 这两个寄存器的值不会变化. 所以可以放心的把 x 放入其中留着之后用.
moveq %rax, %rbx Q调用完毕, 把Q的返回值放入被调用者寄存器 %rbx 中. 这里使用了第二个被调用者保存寄存器 %rbx.
moveq %rbp, %rdi 把 x 复制到1号参数寄存器, 很显然准备调用 Q(x)了
callq Q 此时看一下被调用者保存寄存器, %rbp 依然是 x, %rbx 中是 Q(y)的结果, 很放心, 因为Q返回时不会改变其中的值.
addq %rbx, %rax 此时的%rax中是Q(x), %rbx 中是 Q(y), 指令执行完毕之后, %rax 中是 Q(y) + Q(x), P的返回值已经准备完毕了, 但是此时不能直接返回, 需要做返回准备工作.
addq $8, %rsp 把栈指针+8, 这里我其实没有发现为何要将之前的栈指针先减8, 然后再+8. 因为全程没有用到过栈传递数据, 而调用压栈会自动更新%rsp. 这可能是一种要求吧.
popq %rbx 把栈中的%rbx中的值还原, %rbx 后入栈, 要先弹出
popq %rbp 还原%rbp的值.
ret 准备工作已经做好, 所有的被调用者保存寄存器都恢复到过程开始的阶段, 栈指针也全部复原, 之后就可以返回了.
练习题 3.34 根据汇编代码回答问题
long P(long x)
x in %rdi
P:
pushq %r15
pushq %r14
pushq %r13
pushq %r12
pushq %rbp
pushq %rbx 一直到这里, 保存了所有6个被调用者保存寄存器
subq $24, %rsp 栈上分配24字节局部存储空间
movq %rdi, %rbx 保存 x 的值 到 %rbx 寄存器
leaq 1(%rdi), %r15 x + 1 -> %r15
leaq 2(%rdi), %r14 x + 2 -> %r14
leaq 3(%rdi), %r13 x + 3 -> %r13
leaq 4(%rdi), %r12 x + 4 -> %r12
leaq 5(%rdi), %rbp x + 5 -> %rbp 上边这6行, 在P过程里把所有的被调用者保存器都用了一遍
leaq 6(%rdi), %rax x + 6 -> %rax
mov %rax, (%rsp) 把 x + 6 的结果放入栈中
leaq 7(%rdi), %rdx x + 7 -> %rdx
movq %rdx, 8(%rsp) 把 x + 7 的结果放入栈+8的位置里
movl $0, %eax %rax清零, 为进入Q做准备
call Q 进入Q
通过分析可以回答问题:
- 可以看到, x 到 x+5都被存放在被调用者寄存器中. 而这些寄存器原来的值, 都被放在栈区中的被保存的寄存器区域中.
- 局部变量为 x+6 和 x+7, 分别被保存在栈和栈+8的位置.
- 因为所有的局部值可能超过被调用者保存寄存器的总大小. 这个例子中一共有8个局部值, 用光了6个, 只能有2个保存在栈上.
数据传送 – 递归
其实上边把一个过程的栈区的三部分都看完了, 先是被保存的寄存器区域, 然后是超过被调用者保存寄存器存储能力的局部变量, 然后是为了其他调用进行的参数构造区.
这里我的理解是把局部变量使用的栈和寄存器部分统一起来看做所有的局部变量区域.这样可以发现, 每一个过程的栈区, 都保留了需要还原给上一个栈的局部变量, 自己的局部变量, 交给下一个过程的参数这样一些内容.
再抽象一下的话, 其实就是保存了一个自己过程的状态, 或者是私有信息, 不会和其他过程有冲突. 这样就可以让过程调用过程, 过程再调用过程, 一直这样下去.
所以不管过程调用自己, 还是调用一个其他的过程, 所谓的自己与否, 只是名字和代码是不是相同, 但在底层, 都是彼此独立不相关的过程.
自己再来分析一下书里的递归算阶乘的例子:
long rfact(long n){
long result;
if (n <= 1) {
result = 1;
} else result = n * rfact(n - 1);
return result;
}
这个递归函数很简单, 关键要理解调用的时候发生了什么:
long rfact(long n)
n in %rdi
rfact:
pushq %rbx 将被调用者寄存器%rbx中的值保存起来, 这个值是什么呢
movq %rdi, %rbx 保存n
movl $1, %eax %rax中放入1
cmpq %1, %rdi 比较 n : 1
jle .L35 如果n<=1 跳转 L35 标号
leaq -1(%rdi), %rdi n = n - 1, %rdi 此时减少1, 同时也是1号参数位置
call rfact 调用 rfact(n-1)
imulq %rbx, %rax 用 %rbx中的 n 乘以 %rax中的 rfact(n-1)的值
.L35:
popq %rbx 还原%rbx
ret 此时%eax中是1, 直接就可以返回1
前边的问题, %rbx 中的值是什么, 如果我们在main函数中调用rfact(3), 一开始%rbx的值我们是不知道的, 由于程序要使用%rbx, 所以必须保存一下, 假设这个值叫U.
之后rfact(3)相关内容进入系统, 此时先把U保存到了rfact(3)的栈区中, 然后在%rbx中存了3, 之后使用%rdi= n-1来调用rfact(2).
rfact(2)一开始的时候, %rbx中的值是3, 会把3保存到栈区, 然后把%rbx中存了2, 之后去调用rfact(1).
rfact(1)一开始的时候, %rbx中的值是2, 会把2保存到栈区, 然后在%rbx中存了1, 之后去判断n<=1, 结果发现成立, 就把%rbx中的值还原成2, 然后返回1.
此时控制权交给rfact(2)调用后的语句, 此时%rbx中的值是2, 2乘以rfact(1)返回的1, 结果是2, 然后还原%rbx 为 栈区中的3, 之后返回2.
控制权又交回给rfact(3)调用后的语句, 此时%rbx中的值是3, 3乘以rfact(2)的返回值2, 结果是6, 然后返回给main函数, 同时把栈区中的U还原到%rbx中.整个调用链就结束了.
可以看到,通过被调用者保存寄存器, 每一个过程在调用结束的时候, 都可以将自己的状态复原到调用之前, 仅仅继续使用%rax返回的值来继续进行运算.
练习3.35 根据汇编代码补充C函数
long rfun(unsigned long x){
if(______){
return ______;
}
unsigned long nx = ______;
long rv = rfun(nx);
return ______;
}
汇编代码分析如下:
long rfun(unsigned long x)
x in %rdi
rfun:
pushq %rbx 保存被调用者保存寄存器 %rbx 的值到栈区. 这说明程序中要使用 %rbx 来保存当前状态
movq %rdi, %rbx 在%rbx中保存了 x 的值, 说明每个过程中需要用到每次传入的参数
movl %0, %eax %rax 置0, 要想到在testq或者comp之前设置 %rax, 可能是某种条件下的返回值就是0
testq %rdi, %rdi 测试参数 x
je .L2 如果 x = 0, 跳转到 L2 标号
shrq $2, %rdi 逻辑右移两位, 相当于 x = x >> 2
callq rfun 调用rfun(x/4)
addq %rbx, %rax 此时%rbx中是初始参数 x 的值, 这句就是把返回值设置为 x + rfun(x>>2)
.L2
popq %rbx 还原%rbx的值
ret 此时返回0.
可见这是一个递归函数, 每次测试 x>>2 是否等于=0, 如果等于就返回0, 不等于就返回 x + rfun(x>>2). 补完后的代码如下:
long rfun(unsigned long x){
if(x==0){
return 0;
}
unsigned long nx = x>>2;
long rv = rfun(nx);
return x + rv;
}
过程的抽象是最初的抽象, 高层语言抽象出对象,ADT等概念千变万化, 底层一直是以过程的方式运作的.
练习3.22那里，不是向下移动了2字节哦，是0x20-0x18=0x8，还是8个字节的返回地址。
对, 十六进制….