关于c:模拟函数递归调用压栈过程

35次阅读

共计 11706 个字符，预计需要花费 30 分钟才能阅读完成。

操作系统版本

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 表示法

正文完
c
发表至： c#
2020-11-05
 0
关于c++:记录平时遇到的一些注意点
关于c:JIT原理简单介绍
程序一定要从main函数开始运行吗
关于c#:C-WinForm-线程间操作无效-从不是创建控件的线程访问它的解决办法