模拟函数递归调用压栈过程

微信扫一扫,分享到朋友圈

模拟函数递归调用压栈过程

操作系统版本

Linux e982ba054bfa 4.9.125-linuxkit x86_64 x86_64 x86_64 GNU/Linux

gcc version 6.4.0 运行与mac下的docker

执行代码

//递归函数调用实现斐波那契
int fib(int n)
{
if (n <= 2)
{
return 1;
}
else
{
return fib(n - 1) + fib(n - 2);
}
}
int main()
{
fib(4);
return 0;
}

编译

gcc fib.c -g -o fib //-g选项使目标文件fib包含程序的调试信息

开始

gdb fib
(gdb) start //拉起被调试程序,并执行至main函数的开始位置
Temporary breakpoint 1 at 0x40050f: file fib.c, line 14.
Starting program: /home/work/fib
Temporary breakpoint 1, main () at fib.c:14
14     fib(4);

查看当前栈层信息及rbp,rsp的值

(gdb) info f //打印出当前栈层的信息
Stack level 0, frame at 0x7fffffffe6e0:
rip = 0x40050f in main (fib.c:14); saved rip = 0x7ffff7a303d5
source language c.
Arglist at 0x7fffffffe6d0, args:
Locals at 0x7fffffffe6d0, Previous frame's sp is 0x7fffffffe6e0
Saved registers:
rbp at 0x7fffffffe6d0, rip at 0x7fffffffe6d8
(gdb) info registers rbp rsp //当前rbp rsp的值
rbp            0x7fffffffe6d0    0x7fffffffe6d0
rsp            0x7fffffffe6d0    0x7fffffffe6d0

查看当前函数的汇编信息,可以看到当前汇编指令执行到0x000000000040050f(貌似我的跟别人的好像不一样,具体可以以自己的为准),我这里已经执行完main的frame初始化了

Dump of assembler code for function main:
13    {
0x000000000040050b <+0>:    55    push   %rbp //将rbp寄存器的值压栈
0x000000000040050c <+1>:    48 89 e5    mov    %rsp,%rbp //将rsp寄存器的值赋给rbp寄存器,初始化当前函数的栈底
14     fib(4);
=> 0x000000000040050f <+4>:    bf 04 00 00 00    mov    $0x4,%edi
0x0000000000400514 <+9>:    e8 b4 ff ff ff    callq  0x4004cd <fib>
15     return 0;
0x0000000000400519 <+14>:    b8 00 00 00 00    mov    $0x0,%eax
16    }
0x000000000040051e <+19>:    5d    pop    %rbp
0x000000000040051f <+20>:    c3    retq
End of assembler dump.

在上面的代码可以看到接下来将要执行的两步分别是

  • 0x000000000040050f 把4付给edi寄存器
  • 0x0000000000400514 fib函数调用

好了执行一下

(gdb) si 2 //si是汇编级别的执行下一条,si 2 执行2条到fib中

查看一下当前寄存器及内存信息

(gdb) info registers rbp rsp edi
rbp            0x7fffffffe6d0    0x7fffffffe6d0
rsp            0x7fffffffe6c8    0x7fffffffe6c8
edi            0x4    4
(gdb) x/20x 0x7fffffffe6a0 //从0x7fffffffe6a0开始以16进制打印20条信息
0x7fffffffe6a0:    0x00000000    0x00000000    0x00000000    0x00000000
0x7fffffffe6b0:    0x00400520    0x00000000    0x004003e0    0x00000000
0x7fffffffe6c0:    0xffffe7b0    0x00007fff    0x00400519    0x00000000
0x7fffffffe6d0:    0x00000000    0x00000000    0xf7a303d5    0x00007fff
0x7fffffffe6e0:    0x00000000    0x00000000    0xffffe7b8    0x00007fff

可以看到现在寄存器edi的值是4,rsp的值是0x7fffffffe6c8,怎么变了呢?仔细看下面的内存信息在0x7fffffffe6c8到0x7fffffffe6d0之前压入了一个地址0x00400519往上翻翻是不是fib函数下一条要执行的汇编指令的地址呢。而rsp代表的是栈顶的地址,也就跟着扩容到了0x7fffffffe6c。接下来打印一下当前汇编指令,应该已经跳到fib函数内部了

(gdb) disassemble /rm
Dump of assembler code for function fib:
2    {
=> 0x00000000004004cd <+0>:    55    push   %rbp
0x00000000004004ce <+1>:    48 89 e5    mov    %rsp,%rbp
0x00000000004004d1 <+4>:    53    push   %rbx
0x00000000004004d2 <+5>:    48 83 ec 18    sub    $0x18,%rsp
0x00000000004004d6 <+9>:    89 7d ec    mov    %edi,-0x14(%rbp)
3     if (n <= 2)
0x00000000004004d9 <+12>:    83 7d ec 02    cmpl   $0x2,-0x14(%rbp)
0x00000000004004dd <+16>:    7f 07    jg     0x4004e6 <fib+25>
4     {
5      return 1;
0x00000000004004df <+18>:    b8 01 00 00 00    mov    $0x1,%eax
0x00000000004004e4 <+23>:    eb 1e    jmp    0x400504 <fib+55>
6     }
7     else
8     {
9      return fib(n - 1) + fib(n - 2);
0x00000000004004e6 <+25>:    8b 45 ec    mov    -0x14(%rbp),%eax
0x00000000004004e9 <+28>:    83 e8 01    sub    $0x1,%eax
0x00000000004004ec <+31>:    89 c7    mov    %eax,%edi
0x00000000004004ee <+33>:    e8 da ff ff ff    callq  0x4004cd <fib>
0x00000000004004f3 <+38>:    89 c3    mov    %eax,%ebx
0x00000000004004f5 <+40>:    8b 45 ec    mov    -0x14(%rbp),%eax
0x00000000004004f8 <+43>:    83 e8 02    sub    $0x2,%eax
0x00000000004004fb <+46>:    89 c7    mov    %eax,%edi
0x00000000004004fd <+48>:    e8 cb ff ff ff    callq  0x4004cd <fib>
0x0000000000400502 <+53>:    01 d8    add    %ebx,%eax
10     }
11    }
0x0000000000400504 <+55>:    48 83 c4 18    add    $0x18,%rsp
0x0000000000400508 <+59>:    5b    pop    %rbx
0x0000000000400509 <+60>:    5d    pop    %rbp
0x000000000040050a <+61>:    c3    retq
End of assembler dump.

接下来先进行fib的frame初始化,然后看一下当前寄存器的情况和内存信息

(gdb) si 2
(gdb) info registers rbp rsp edi
rbp            0x7fffffffe6c0    0x7fffffffe6c0
rsp            0x7fffffffe6c0    0x7fffffffe6c0
edi            0x4    4
(gdb) x/20x 0x7fffffffe6a0
0x7fffffffe6a0:    0x00000000    0x00000000    0x00000000    0x00000000
0x7fffffffe6b0:    0x00400520    0x00000000    0x004003e0    0x00000000
0x7fffffffe6c0:    0xffffe6d0    0x00007fff    0x00400519    0x00000000
0x7fffffffe6d0:    0x00000000    0x00000000    0xf7a303d5    0x00007fff
0x7fffffffe6e0:    0x00000000    0x00000000    0xffffe7b8    0x00007fff

可以看到edi的值没有变化,rbp和rsp的值都变成了0x7fffffffe6c0,仔细看下面的内存信息在0x7fffffffe6c0到0x7fffffffe6c8的位置压入了main的rbp的值0xffffe6d0,rsp跟着扩容,接下来把rsp的值赋给rbp。fib的frame初始化完成。

接下来在往下走三步

  • push %rbx //讲rbx寄存器的值压栈,rsp-8
  • sub $0x18,%rsp //rsp-0x18(24)
  • mov %edi,-0x14(%rbp) //把edi寄存器的值(4)放到距rbp寄存器存放的地址偏移-0x14(20)位的地方

打印一下寄存器和内存信息

(gdb) si 3
(gdb) info registers rbp rsp edi rbx
rbp            0x7fffffffe6c0    0x7fffffffe6c0
rsp            0x7fffffffe6a0    0x7fffffffe6a0
edi            0x4    4
rbx            0x0    0
(gdb) x/20x 0x7fffffffe6a0
0x7fffffffe6a0:    0x00000000    0x00000000    0x00000000    0x00000004
0x7fffffffe6b0:    0x00400520    0x00000000    0x00000000    0x00000000
0x7fffffffe6c0:    0xffffe6d0    0x00007fff    0x00400519    0x00000000
0x7fffffffe6d0:    0x00000000    0x00000000    0xf7a303d5    0x00007fff
0x7fffffffe6e0:    0x00000000    0x00000000    0xffffe7b8    0x00007fff

在往下走

  • cmpl $0x2,-0x14(%rbp) //2和-0x14(%rbp)的值(4)相减,大于等于0执行下一条否则执行jg指令,这里显然不符合
  • jg 0x4004e6 <fib+25> //这个就是要跳转的地方了,
return fib(n - 1) + fib(n - 2);
=> 0x00000000004004e6 <+25>:    8b 45 ec    mov    -0x14(%rbp),%eax
0x00000000004004e9 <+28>:    83 e8 01    sub    $0x1,%eax
0x00000000004004ec <+31>:    89 c7    mov    %eax,%edi
0x00000000004004ee <+33>:    e8 da ff ff ff    callq  0x4004cd <fib>
0x00000000004004f3 <+38>:    89 c3    mov    %eax,%ebx
0x00000000004004f5 <+40>:    8b 45 ec    mov    -0x14(%rbp),%eax
0x00000000004004f8 <+43>:    83 e8 02    sub    $0x2,%eax
0x00000000004004fb <+46>:    89 c7    mov    %eax,%edi
0x00000000004004fd <+48>:    e8 cb ff ff ff    callq  0x4004cd <fib>
0x0000000000400502 <+53>:    01 d8    add    %ebx,%eax
  • mov -0x14(%rbp),%eax //把-0x14(%rbp)的值(4)赋给eax寄存器
  • sub $0x1,%eax //eax的值-1
  • mov %eax,%edi //把eax的值赋给edi
  • callq 0x4004cd <fib> //调用fib函数,注意这个地址跟之前的一样

再查看一下寄存器信息和内存信息

(gdb) info registers rbp rsp edi rbx eax
rbp            0x7fffffffe6c0    0x7fffffffe6c0
rsp            0x7fffffffe698    0x7fffffffe698
edi            0x3    3
rbx            0x0    0
eax            0x3    3
(gdb) x/20x 0x7fffffffe690
0x7fffffffe690:    0x00000001    0x00000000    0x004004f3    0x00000000
0x7fffffffe6a0:    0x00000000    0x00000000    0x00000000    0x00000004
0x7fffffffe6b0:    0x00400520    0x00000000    0x00000000    0x00000000
0x7fffffffe6c0:    0xffffe6d0    0x00007fff    0x00400519    0x00000000
0x7fffffffe6d0:    0x00000000    0x00000000    0xf7a303d5    0x00007fff

可以看到当前edi,eax的值是3,在0x7fffffffe698到0x7fffffffe6a0之间压入了这次函数调用的下一条指令地址,当前rsp是0x7fffffffe698。

查看汇编指令信息之后发现跟之前基本一样,初始化frame之后,当前寄存器和内存信息如下

(gdb) info registers rbp rsp edi rbx eax
rbp            0x7fffffffe690    0x7fffffffe690
rsp            0x7fffffffe690    0x7fffffffe690
edi            0x3    3
rbx            0x0    0
eax            0x3    3
(gdb) x/20x 0x7fffffffe690
0x7fffffffe690:    0xffffe6c0    0x00007fff    0x004004f3    0x00000000
0x7fffffffe6a0:    0x00000000    0x00000000    0x00000000    0x00000004
0x7fffffffe6b0:    0x00400520    0x00000000    0x00000000    0x00000000
0x7fffffffe6c0:    0xffffe6d0    0x00007fff    0x00400519    0x00000000
0x7fffffffe6d0:    0x00000000    0x00000000    0xf7a303d5    0x00007fff

跟上面一样,将之前的rbp压栈,同步rsp信息至rbp,接下来继续上面的三步打印一下寄存器和内存信息

(gdb) info registers rbp rsp edi rbx eax
rbp            0x7fffffffe690    0x7fffffffe690
rsp            0x7fffffffe670    0x7fffffffe670
edi            0x3    3
rbx            0x0    0
eax            0x3    3
(gdb) x/20x 0x7fffffffe660
0x7fffffffe660:    0x00000000    0x00000000    0x00000000    0x00000000
0x7fffffffe670:    0x00000000    0x00000000    0x00000000    0x00000003
0x7fffffffe680:    0x00000000    0x00000000    0x00000000    0x00000000
0x7fffffffe690:    0xffffe6c0    0x00007fff    0x004004f3    0x00000000
0x7fffffffe6a0:    0x00000000    0x00000000    0x00000000    0x00000004

将3压入0x7fffffffe678到0x7fffffffe680之间,当前rsp = rsp – push rbx (8) – 0x18 = 0x7fffffffe670。

继续往下走显然3也不满足条件,继续上面的步骤

  • mov -0x14(%rbp),%eax //把-0x14(%rbp)的值(3)赋给eax寄存器
  • sub $0x1,%eax //eax的值-1
  • mov %eax,%edi //把eax的值赋给edi
  • callq 0x4004cd <fib> //调用fib函数

查看一下寄存器信息和内存信息

(gdb) info registers rbp rsp edi rbx eax
rbp            0x7fffffffe690    0x7fffffffe690
rsp            0x7fffffffe668    0x7fffffffe668
edi            0x2    2
rbx            0x0    0
eax            0x2    2
(gdb) x/20x 0x7fffffffe660
0x7fffffffe660:    0x00000000    0x00000000    0x004004f3    0x00000000
0x7fffffffe670:    0x00000000    0x00000000    0x00000000    0x00000003
0x7fffffffe680:    0x00000000    0x00000000    0x00000000    0x00000000
0x7fffffffe690:    0xffffe6c0    0x00007fff    0x004004f3    0x00000000
0x7fffffffe6a0:    0x00000000    0x00000000    0x00000000    0x00000004

同样将0x004004f3压栈,rsp-8

初始化frame和参数之后查询寄存器信息和内存信息

(gdb) info registers rbp rsp edi rbx eax
rbp            0x7fffffffe660    0x7fffffffe660
rsp            0x7fffffffe640    0x7fffffffe640
edi            0x2    2
rbx            0x0    0
eax            0x2    2
(gdb) x/20x 0x7fffffffe640
0x7fffffffe640:    0x00000002    0x00000000    0x00000000    0x00000002
0x7fffffffe650:    0x00000000    0x00000000    0x00000000    0x00000000
0x7fffffffe660:    0xffffe690    0x00007fff    0x004004f3    0x00000000
0x7fffffffe670:    0x00000000    0x00000000    0x00000000    0x00000003
0x7fffffffe680:    0x00000000    0x00000000    0x00000000    0x00000000

符合预期,继续往下走,2-2显然满足条件

return 1; => 0x00000000004004df <+18>: b8 01 00 00 00 mov $0x1,%eax 0x00000000004004e4 <+23>: eb 1e jmp 0x400504 <fib+55>

  • mov $0x1,%eax //把1赋给eax寄存器
  • jmp 0x400504 <fib+55> //跳转

=> 0x0000000000400504 <+55>: 48 83 c4 18 add $0x18,%rsp 0x0000000000400508 <+59>: 5b pop %rbx 0x0000000000400509 <+60>: 5d pop %rbp 0x000000000040050a <+61>: c3 retq

  • add $0x18,%rsp //rsp+0x18(24) = 0x7fffffffe658
  • pop %rbx // rsp+8 = 0x7fffffffe660
  • pop %rbp //rbp = 0xffffe690 ; rsp + 8 = 0x7fffffffe668
  • retq // rsp + 8 = 0x7fffffffe670 ,跳转到0x004004f3

在查看下信息

(gdb) info registers rbp rsp edi rbx eax
rbp            0x7fffffffe690    0x7fffffffe690
rsp            0x7fffffffe670    0x7fffffffe670
edi            0x2    2
rbx            0x1    0
eax            0x1    1
(gdb) x/20x 0x7fffffffe640
0x7fffffffe640:    0x00000002    0x00000000    0x00000000    0x00000002
0x7fffffffe650:    0x00000000    0x00000000    0x00000000    0x00000000
0x7fffffffe660:    0xffffe690    0x00007fff    0x004004f3    0x00000000
0x7fffffffe670:    0x00000000    0x00000000    0x00000000    0x00000003
0x7fffffffe680:    0x00000000    0x00000000    0x00000000    0x00000000

跳回来,记得这个fib(3)那个

=> 0x00000000004004f3 <+38>:    89 c3    mov    %eax,%ebx
0x00000000004004f5 <+40>:    8b 45 ec    mov    -0x14(%rbp),%eax
0x00000000004004f8 <+43>:    83 e8 02    sub    $0x2,%eax
0x00000000004004fb <+46>:    89 c7    mov    %eax,%edi
0x00000000004004fd <+48>:    e8 cb ff ff ff    callq  0x4004cd <fib>
0x0000000000400502 <+53>:    01 d8    add    %ebx,%eax
  • mov %eax,%ebx //eax的值赋给ebx
  • mov -0x14(%rbp),%eax //-0x14(%rbp)位置的值赋给eax
  • sub $0x2,%eax//eax(3)-2
  • mov %eax,%edi //eax赋给edi
  • callq 0x4004cd <fib> //调用函数(又来了)

对照一下内存信息

(gdb) x/20x 0x7fffffffe660
0x7fffffffe660:    0xffffe690    0x00007fff    0x00400502    0x00000000
0x7fffffffe670:    0x00000000    0x00000000    0x00000000    0x00000003
0x7fffffffe680:    0x00000000    0x00000000    0x00000000    0x00000000
0x7fffffffe690:    0xffffe6c0    0x00007fff    0x004004f3    0x00000000
0x7fffffffe6a0:    0x00000000    0x00000000    0x00000000    0x00000004

开始新一轮的调用,把下一条指令地址0x00400502压栈。rsp-8,初始化frame和参数之后查询寄存器信息和内存信息

(gdb) info registers rbp rsp edi rbx eax
rbp            0x7fffffffe660    0x7fffffffe660
rsp            0x7fffffffe640    0x7fffffffe640
edi            0x1    1
rbx            0x1    1
eax            0x1    1
(gdb) x/20x 0x7fffffffe640
0x7fffffffe640:    0x00000002    0x00000000    0x00000000    0x00000001
0x7fffffffe650:    0x00000000    0x00000000    0x00000001    0x00000000
0x7fffffffe660:    0xffffe690    0x00007fff    0x00400502    0x00000000
0x7fffffffe670:    0x00000000    0x00000000    0x00000000    0x00000003
0x7fffffffe680:    0x00000000    0x00000000    0x00000000    0x00000000
  • push %rbx //rbx的值压栈 这次有值了 1, rsp-8
  • sub $0x18,%rsp //rsp-0x18(24)
  • mov %edi,-0x14(%rbp) //edi的值赋给-0x14(%rbp)

继续往下走,1-2显然满足条件

return 1;
=> 0x00000000004004df <+18>:    b8 01 00 00 00    mov    $0x1,%eax
0x00000000004004e4 <+23>:    eb 1e    jmp    0x400504 <fib+55>
  • mov $0x1,%eax //把1赋给eax寄存器
  • jmp 0x400504 <fib+55> //跳转
=> 0x0000000000400504 <+55>:    48 83 c4 18    add    $0x18,%rsp
0x0000000000400508 <+59>:    5b    pop    %rbx
0x0000000000400509 <+60>:    5d    pop    %rbp
0x000000000040050a <+61>:    c3    retq
  • add $0x18,%rsp //rsp+0x18(24) = 0x7fffffffe658
  • pop %rbx // rsp+8 = 0x7fffffffe660
  • pop %rbp //rbp = 0xffffe690 ; rsp + 8 = 0x7fffffffe668
  • retq // rsp + 8 = 0x7fffffffe670 ,跳转到0x00400502

在查看下信息

(gdb) x/20x 0x7fffffffe640
0x7fffffffe640:    0x00000002    0x00000000    0x00000000    0x00000001
0x7fffffffe650:    0x00000000    0x00000000    0x00000001    0x00000000
0x7fffffffe660:    0xffffe690    0x00007fff    0x00400502    0x00000000
0x7fffffffe670:    0x00000000    0x00000000    0x00000000    0x00000003
0x7fffffffe680:    0x00000000    0x00000000    0x00000000    0x00000000

回来继续往下走

0x0000000000400502 <+53>:    01 d8    add    %ebx,%eax
10     }
11    }
0x0000000000400504 <+55>:    48 83 c4 18    add    $0x18,%rsp
0x0000000000400508 <+59>:    5b    pop    %rbx
0x0000000000400509 <+60>:    5d    pop    %rbp
0x000000000040050a <+61>:    c3    retq
  • add %ebx,%eax // eax(2) = ebx(1)+eax(1)
  • add $0x18,%rsp //rsp+0x18= 0x7fffffffe658
  • pop %rbx //rsp+8 ,rbx=0
  • pop %rbp //rsp+8,rbp=0xffffe690
  • retq //rsp+8 ,跳转0x00400502

查看信息

(gdb) x/20x 0x7fffffffe640
0x7fffffffe640:    0x00000002    0x00000000    0x00000000    0x00000001
0x7fffffffe650:    0x00000000    0x00000000    0x00000001    0x00000000
0x7fffffffe660:    0xffffe690    0x00007fff    0x00400502    0x00000000
0x7fffffffe670:    0x00000000    0x00000000    0x00000000    0x00000003
0x7fffffffe680:    0x00000000    0x00000000    0x00000000    0x00000000

后面流程基本一样就不在往下写了。

总结一下

  1. 栈是 FILO
    (first in last out),先进后出。main函数先进栈,所以最后出来。
  2. %ESP – 堆栈指针
  3. 这个32位寄存器由多个CPU指令(PUSH,POP,CALL和RET等)隐式操作,它总是指向堆栈上使用的最后一个元素(不是第一个自由元素)
  4. “堆栈顶部”是一个占用位置,而不是一个空闲位置,并且位于最低内存地址。
  5. %EBP – 基准指针
  6. 该32位寄存器用于引用当前堆栈帧中的所有函数参数和局部变量。与%esp寄存器不同,基本指针仅被显式操作。这有时被称为“帧指针”。
  7. %EIP – 指令指针
  8. 它保存要执行的下一个CPU指令的地址,并作为CALL 指令的一部分保存到堆栈中。同样,任何“跳转”指令都会直接修改%EIP。
  9. 英特尔汇编程序世界中的每个人都使用Intel表示法,但GNU C编译器使用他们称之为“AT&T语法”的向后兼容性。这对我们来说似乎是一个非常愚蠢的想法,但这是生活中的事实。两种符号之间存在较小的符号差异,但到目前为止最令人讨厌的是AT&T语法会反转源和目标操作数。要将立即值4移动到EAX寄存器:原文地址: http://www.unixwiz.net/techtips/win32-callconv-asm.html
mov $ 4,%eax // AT&T表示法 mov eax,4 // Intel表示法

微信扫一扫,分享到朋友圈

模拟函数递归调用压栈过程

财富管理品牌全新升级 富途大象财富布局全球资产配置

上一篇

不懂就问:SQL 语句中 Where 条件后 写上1=1 是什么意思

下一篇

你也可能喜欢

模拟函数递归调用压栈过程

长按储存图像,分享给朋友