callstack究竟是如何工作的？

Question

我试图更深入地了解编程语言的低级操作是如何工作的,尤其是它们如何与OS/CPU交互.我可能已经在Stack Overflow上的每个堆栈/堆相关线程中阅读了每个答案,并且它们都很棒.但还有一件事我还没有完全理解.

在伪代码中考虑这个函数,这往往是有效的Rust代码;-)

fn foo() {
    let a = 1;
    let b = 2;
    let c = 3;
    let d = 4;

    // line X

    doSomething(a, b);
    doAnotherThing(c, d);
}

这就是我假设堆栈在X行上的样子:

Stack

a +-------------+
  | 1           | 
b +-------------+     
  | 2           |  
c +-------------+
  | 3           | 
d +-------------+     
  | 4           | 
  +-------------+ 

现在,我读到的关于堆栈如何工作的一切都是它严格遵守LIFO规则(后进先出).就像.NET,Java或任何其他编程语言中的堆栈数据类型一样.

但如果是这样,那么在X行之后会发生什么？显然,接下来我们需要的是使用a和b,但这意味着操作系统/ CPU(？)必须弹出d并c首先回到a和b.但是它会在脚下射击,因为它需要c并且d在下一行.

所以,我想知道幕后究竟发生了什么？

另一个相关问题.考虑我们传递对其他函数的引用,如下所示:

fn foo() {
    let a = 1;
    let b = 2;
    let c = 3;
    let d = 4;

    // line X

    doSomething(&a, &b);
    doAnotherThing(c, d);
}

从我所理解的东西,这将意味着在参数doSomething基本上指向像相同的内存地址a,并b在foo.但是,这意味着在我们开始a和b发生之前不会弹出堆栈.

这些2箱子让我觉得我还没有完全掌握如何准确堆栈的工作方式以及它严格遵循LIFO规则.

Answer 1

调用堆栈也可以称为帧堆栈.在LIFO原则之后堆叠
的东西不是局部变量,而是被调用函数的整个堆栈帧("调用").局部变量分别与所谓的函数序言和结尾中的那些帧一起推送和弹出.

在框架内部,变量的顺序是完全未指定的; 编译器适当地"重新排序"框架内局部变量的位置以优化它们的对齐,以便处理器可以尽快获取它们.关键的事实是变量相对于某个固定地址的偏移量在帧的整个生命周期内是恒定的 - 所以只需要一个锚地址,例如帧本身的地址,并使用该地址的偏移量来处理变量.这种锚地址实际上包含在所谓的基本或帧指针中,该指针存储在EBP寄存器中.另一方面,偏移在编译时清楚地知道,因此硬编码到机器代码中.

维基百科的这个图形显示了典型的调用堆栈结构如¹:

添加我们想要访问的变量的偏移量到帧指针中包含的地址,我们得到变量的地址.简而言之,代码只是通过基址指针的常量编译时偏移直接访问它们; 这是简单的指针算法.

例

#include <iostream>

int main()
{
    char c = std::cin.get();
    std::cout << c;
}

gcc.godbolt.org给了我们

main:
    pushq   %rbp
    movq    %rsp, %rbp
    subq    $16, %rsp

    movl    std::cin, %edi
    call    std::basic_istream<char, std::char_traits<char> >::get()
    movb    %al, -1(%rbp)
    movsbl  -1(%rbp), %eax
    movl    %eax, %esi
    movl    std::cout, %edi
    call    [... the insertion operator for char, long thing... ]

    movl    $0, %eax
    leave
    ret

..为main.我将代码分为三个小节.功能序言包括前三个操作:

• 基指针被压入堆栈.
• 堆栈指针保存在基指针中
• 减去堆栈指针以为局部变量腾出空间.

然后cin被移入EDI寄存器²并被get调用; 返回值在EAX中.

到现在为止还挺好.现在有趣的事情发生了:

由8位寄存器AL指定的EAX的低位字节被取出并存储在基指针之后的字节中:即-1(%rbp),基指针的偏移量为-1.这个字节是我们的变量c.偏移量为负,因为堆栈在x86上向下增长.下一个操作存储c在EAX中:EAX移动到ESI,cout移动到EDI,然后调用插入操作符cout并c作为参数.

最后,

• 返回值main存储在EAX:0中.这是因为隐式return语句.您可能也会看到xorl rax rax而不是movl.
• 离开并返回呼叫站点.leave正在简单地缩写这个结尾
  • 用基指针替换堆栈指针
  • 弹出基指针.

在执行此操作之后ret,已经有效地弹出了框架,尽管调用者仍然需要清理参数,因为我们正在使用cdecl调用约定.其他约定,例如stdcall,要求被调用者整理,例如通过传递字节量ret.

帧指针省略

也可以不使用基本/帧指针的偏移,而是使用堆栈指针(ESB).这使得EBP寄存器本来可以包含任意使用的帧指针值 - 但是它可以在某些机器上进行调试,并且对于某些函数将隐式关闭.在为只有少量寄存器(包括x86)的处理器进行编译时,它特别有用.

这种优化称为FPO(帧指针省略),由-fomit-frame-pointerGCC和-OyClang设置; 请注意,当且仅当调试仍然可行时,每个优化级别> 0隐式触发它,因为除此之外没有任何成本.有关详细信息,请参阅此处和此处.

¹正如评论中所指出的,帧指针可能意味着指向返回地址之后的地址.

²请注意,以R开头的寄存器是以E开头的寄存器的64位副本.EAX指定RAX的四个低位字节.为清楚起见,我使用了32位寄存器的名称.

Answer 2

因为很明显,接下来我们需要的是使用a和b,但这意味着OS/CPU(？)必须首先弹出d和c才能返回a和b.但是它会在脚下射击,因为它需要下一行中的c和d.

简而言之:

没有必要弹出参数.调用者传递foo给函数的参数doSomething和局部变量doSomething 都可以作为基指针的偏移量引用.
所以,

• 进行函数调用时,函数的参数在堆栈上被推送.基指针进一步引用这些参数.
• 当函数返回其调用者时,返回函数的参数使用LIFO方法从堆栈中弹出.

详细地:

规则是每个函数调用都会导致创建堆栈帧(最小值是要返回的地址).因此,如果funcA调用funcB和funcB调用,则将funcC三个堆栈帧设置在另一个堆栈帧之上.当函数返回时,其框架变为无效.一个表现良好的函数仅在其自己的堆栈帧上起作用,并且不会侵入另一个堆栈帧.换句话说,POPing被执行到顶部的堆栈帧(当从函数返回时).

问题中的堆栈由调用者设置foo.当doSomething和doAnotherThing被调用,那么他们建立了自己的堆栈.这个数字可以帮助你理解这个:

注意,要访问参数,函数体必须从存储返回地址的位置向下遍历(更高的地址),并且要访问局部变量,函数体必须遍历堆栈(较低的地址) )相对于存储返回地址的位置.事实上,典型的编译器生成的函数代码就是这样做的.编译器为此指定了一个名为EBP的寄存器(Base Pointer).另一个名称是帧指针.作为函数体的第一件事,编译器通常将当前EBP值推送到堆栈并将EBP设置为当前ESP.这意味着,一旦完成,在功能代码的任何部分,参数1是EBP + 8离开(每个调用者的EBP和返回地址4个字节),参数2是EBP + 12(十进制),局部变量是EBP-4n了.

.
.
.
[ebp - 4]  (1st local variable)
[ebp]      (old ebp value)
[ebp + 4]  (return address)
[ebp + 8]  (1st argument)
[ebp + 12] (2nd argument)
[ebp + 16] (3rd function argument) 

看看下面的C代码,用于形成函数的堆栈帧:

void MyFunction(int x, int y, int z)
{
     int a, int b, int c;
     ...
}

当来电者打电话时

MyFunction(10, 5, 2);  

将生成以下代码

^
| call _MyFunction  ; Equivalent to: 
|                   ; push eip + 2
|                   ; jmp _MyFunction
| push 2            ; Push first argument  
| push 5            ; Push second argument  
| push 10           ; Push third argument  

并且函数的汇编代码将是(在返回之前由被调用者设置)

^
| _MyFunction:
|  sub esp, 12 ; sizeof(a) + sizeof(b) + sizeof(c)
|  ;x = [ebp + 8], y = [ebp + 12], z = [ebp + 16]
|  ;a = [ebp - 4] = [esp + 8], b = [ebp - 8] = [esp + 4], c = [ebp - 12] =   [esp]
|  mov ebp, esp
|  push ebp

参考文献:

• 函数调用约定和堆栈.
• 帧指针和局部变量.
• x86反汇编/功能和堆栈帧.

Answer 3

与其他人一样,在超出范围之前,不需要弹出参数.

我将贴上Nick Parlante的"指针和记忆"中的一些例子.我认为情况比你想象的要简单一些.

这是代码:

void X() 
{
  int a = 1;
  int b = 2;

  // T1
  Y(a);

  // T3
  Y(b);

  // T5
}

void Y(int p) 
{
  int q;
  q = p + 2;
  // T2 (first time through), T4 (second time through)
}

时间点T1, T2, etc.在代码中标记,当时的内存状态如图所示:

Answer 4

不同的处理器和语言使用一些不同的堆栈设计.8x86和68000上的两个传统模式称为Pascal调用约定和C调用约定; 除寄存器的名称外,每个约定在两个处理器中的处理方式相同.每个寄存器都使用两个寄存器来管理堆栈和相关变量,称为堆栈指针(SP或A7)和帧指针(BP或A6).

使用任一约定调用子例程时,在调用例程之前,任何参数都将被压入堆栈.然后,例程的代码将帧指针的当前值压入堆栈,将堆栈指针的当前值复制到帧指针,并从堆栈指针中减去局部变量[if any]使用的字节数.完成后,即使将其他数据压入堆栈,所有局部变量也将存储在堆栈指针中具有恒定负位移的变量中,并且调用者在堆栈上推送的所有参数都可以在帧指针的恒定正位移.

两个约定之间的区别在于它们处理从子例程退出的方式.在C约定中,返回函数将帧指针复制到堆栈指针[将其恢复到刚按下旧帧指针后的值],弹出旧帧指针值,然后执行返回.调用之前调用者在堆栈上推送的任何参数都将保留在那里.在Pascal约定中,在弹出旧的帧指针之后,处理器弹出函数返回地址,向栈指针添加调用者推送的参数的字节数,然后转到弹出的返回地址.在原始的68000上,必须使用3指令序列来删除调用者的参数; 原始版本之后的8x86和所有680x0处理器包含一个"ret N"[或680x0等效]指令,该指令在执行返回时将N添加到堆栈指针.

Pascal约定具有在调用者端保存一点代码的优点,因为调用者不必在函数调用之后更新堆栈指针.但是,它要求被调用的函数准确知道调用者将要放入堆栈的参数的字节数.在调用使用Pascal约定的函数之前,未能将适当数量的参数压入堆栈几乎可以确保导致崩溃.但是,这是因为每个被调用方法中的一些额外代码将在调用方法的位置保存代码.因此,大多数原始Macintosh工具箱例程都使用Pascal调用约定.

C调用约定的优点是允许例程接受可变数量的参数,并且即使例程不使用所有传递的参数也是健壮的(调用者将知道它推送了多少字节值的参数,以及因此能够清理它们).此外,在每次函数调用之后不必执行堆栈清理.如果一个例程按顺序调用四个函数,每个函数使用四个字节的参数,它可以 - 而不是ADD SP,4在每次调用后使用一个ADD SP,16函数,在最后一次调用后使用一个来清除所有四个调用的参数.

如今所描述的调用约定被认为有些陈旧.由于编译器在寄存器使用方面的效率更高,因此通常让方法接受寄存器中的一些参数,而不是要求所有参数都被压入堆栈; 如果一个方法可以使用寄存器来保存所有参数和局部变量,则不需要使用帧指针,因此不需要保存和恢复旧的指针.但是,在调用链接使用它们的库时,有时需要使用较旧的调用约定.

Answer 5

这里已经有一些非常好的答案。但是，如果您仍然担心堆栈的LIFO行为，可以将其视为框架堆栈，而不是变量堆栈。我的意思是，尽管一个函数可以访问不在堆栈顶部的变量，但它仍然只对堆栈顶部的项目起作用：单个堆栈框架。

当然，也有例外。整个调用链的局部变量仍然分配并可用。但是不会直接访问它们。相反，它们是通过引用（或通过指针，实际上只是语义上的不同）传递的。在这种情况下，可以访问堆栈框架的局部变量。但是即使在这种情况下，当前正在执行的功能仍然仅在其自身的本地数据上运行。它正在访问存储在其自己的堆栈帧中的引用，该引用可能是对堆中，静态内存中或堆栈下方的某些内容的引用。

这是堆栈抽象的一部分，它使函数可以按任何顺序调用，并允许递归。顶部堆栈框架是代码直接访问的唯一对象。可以间接访问其他任何内容（通过驻留在顶部堆栈框架中的指针）。

查看小程序的汇编可能会很有帮助，特别是如果您在没有优化的情况下进行编译。我认为您会看到函数中的所有内存访问都是通过与堆栈帧指针的偏移量发生的，这就是编译器将如何编写函数代码的方式。在通过引用传递的情况下，您将看到通过与堆栈帧指针有一定偏移量存储的指针的间接内存访问指令。