这个callstack是如何工作的？

我试图深入了解编程语言的低级操作是如何工作的，特别是他们如何与OS / CPU进行交互。 我可能在堆栈溢出的每个堆栈/堆相关的线程中都读过每个答案，它们都很精彩。 但是还有一件事我还没完全理解。

在伪代码中考虑这个function，这往往是有效的锈代码;-) 

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或任何其他编程语言中的堆栈数据types一样。

但是如果是这样的话，那么在X行之后会发生什么呢？ 因为显然，接下来我们需要的是使用a和b ，但是这意味着OS / CPU（？）必须首先popupd和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中的参数基本上指向与foo a和b相同的内存地址。 但是，这又意味着在我们碰到a和b之前，没有popup堆栈 。

这两种情况让我觉得我还没有完全理解这个堆栈是如何工作的，以及它如何严格遵循LIFO规则。

调用堆栈也可以被称为帧堆栈。
在LIFO原理之后堆叠的东西不是局部variables，而是被调用函数的整个栈帧（“调用”） 。 局部variables分别在所谓的函数序言和结语中与这些帧一起被推送和popup。

在框架内，variables的顺序完全没有指定; 编译器对帧内局部variables的位置进行“重新sorting”，以便优化其alignment方式，使处理器能够尽可能快地获取它们。 关键的事实是， variables相对于某个固定地址的偏移量在整个帧的生命周期中是恒定的 – 因此只需要获得一个锚地址，比如帧本身的地址，然后使用该地址的偏移量variables。 这样的锚定地址实际上被包含在存储在EBP寄存器中的所谓的基本或帧指针中。 另一方面，偏移量在编译时很清楚，因此被硬编码到机器码中。

来自维基百科的这个graphics显示了典型的调用堆栈的结构，如1 ：

图片的堆栈

将我们要访问的variables的偏移量添加到帧指针中包含的地址，并获取variables的地址。 所以简单地说，代码只是通过从基址指针不断的编译时间偏移直接访问它们; 这是简单的指针算术。

例 

 #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 。 我把代码分成三个小节。 函数序言由前三个操作组成：

  • 基指针被压入堆栈。
  • 堆栈指针保存在基址指针中
  • 堆栈指针被减去以为本地variables腾出空间。

然后将cin移入EDI寄存器2并调用get ; 返回值在EAX中。

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

由8位寄存器AL指定的EAX的低位字节被取出并存储在基指针之后的字节中 ：即-1(%rbp) ，基指针的偏移量为-1 。 这个字节是我们的variablesc 。 偏移量为负值，因为x86上的堆栈向下增长。 接下来的操作将E存储在EAX中：将EAX移至ESI，将cout移至EDI，然后使用cout和c作为参数调用插入运算符。

最后，

  • main的返回值存储在EAX：0中。这是因为隐式return语句。 您可能还会看到xorl rax rax而不是movl 。
  • 离开并返回到呼叫站点。 leave是缩写这个结语和含蓄
    • 用基址指针replace堆栈指针
    • popup基指针。

在这个操作和ret执行之后，框架已经被有效地popup，尽pipe调用者仍然必须清理参数，因为我们使用的是cdecl调用约定。 其他约定，例如stdcall，要求被调用者整理，例如通过传递字节数来ret 。

帧指针省略

也可以不使用来自基本/帧指针的偏移量，而是使用来自堆栈指针（ESB）的偏移量。 这使得EBP寄存器可以包含可用于任意使用的帧指针值，但它可能会使某些机器上的debugging无法进行 ，并且对于某些函数将被隐式closures 。 编译只有几个寄存器的处理器时尤其有用，包括x86。

这种优化被称为FPO（帧指针省略），由GCC中的-fomit-frame-pointer和Clang中的-Oy ; 请注意，当且仅当仍然可以进行debugging时，才会由每个优化级别> 0隐式触发，因为除此之外，它没有任何成本。 欲了解更多信息，请看这里和这里 。

1正如在注释中指出的那样，帧指针大概意味着指向返回地址之后的地址。

2请注意，以R开始的寄存器是以E开头的那些寄存器的64位对应项。EAX指定RAX的四个低位字节。 为了清晰起见，我使用了32位寄存器的名称。

因为显然，接下来我们需要的是使用a和b，但这意味着OS / CPU（？）必须首先popupd和c才能返回到a和b。 但是，它会在脚下自行射击，因为它需要c和d在下一行。

简而言之：

没有必要popup这个论点。 调用者foo传递给函数doSomething和doSomething的局部variables的参数都可以被引用为基指针的偏移量 。
所以，

  • 当进行函数调用时，函数的参数在堆栈上被压入。 这些参数被基指针进一步引用。
  • 当函数返回给它的调用者时，返回函数的参数是使用LIFO方法从堆栈中popup的。

详细：

规则是每个函数调用都会创build一个栈帧 （最小的地址是返回的地址）。 所以，如果funcA调用funcB和funcB调用funcC ，那么三个堆栈帧将被设置为一个在另一个之上。 当函数返回时，其框架将变为无效 。 行为良好的function只能在自己的堆栈框架上运行，不能侵入他人的堆栈框架。 换句话说，POPing被执行到顶部的栈帧（当从函数返回时）。

在这里输入图像说明

你问题中的堆栈是由调用者foo设置的。 当doSomething和doAnotherThing被调用，然后他们build立自己的堆栈。 这个数字可能会帮助你理解这一点：

在这里输入图像说明

请注意， 为了访问参数，函数体将不得不从存储返回地址的位置向下遍历（更高地址），并访问局部variables，函数体将不得不遍历堆栈（低地址）相对于存储返回地址的位置 。 实际上，典型的编译器为该函数生成的代码将完成此操作。 编译器为这个（Base Pointer）指定了一个名为EBP的寄存器。 另一个相同的名称是帧指针。 作为函数体的第一件事，编译器通常将当前的EBP值压入堆栈，并将EBP设置为当前的ESP。 这意味着，一旦完成，在函数代码的任何部分，参数1都是EBP + 8（每个调用者的EBP和返回地址都是4个字节），参数2是EBP + 12（十进制），局部variables是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

参考文献：

  • 函数调用约定和堆栈 。
  • 帧指针和局部variables 。
  • x86反汇编/函数和堆栈框架 。

像其他人指出的那样，没有必要popup参数，直到它们超出范围。

我会贴一些Nick Parlante的“Pointers and Memory”的例子。 我认为情况比你想象的要简单一些。

这是代码： 

 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 。 被标记在代码中，并且当时的内存状态显示在图中：

在这里输入图像说明

不同的处理器和语言使用一些不同的堆栈devise。 在8×86和68000上的两种传统模式称为Pascal调用约定和C调用约定; 每个约定在两个处理器中都以相同的方式处理，除了寄存器的名称。 每个使用两个寄存器来pipe理堆栈和相关的variables，称为堆栈指针（SP或A7）和帧指针（BP或A6）。

当使用任一惯例调用子程序时，在调用例程之前，将任何参数压入堆栈。 例程的代码然后将帧指针的当前值压入栈中，将栈指针的当前值复制到帧指针，并从栈指针中减去局部variables使用的字节数[如果有的话]。 一旦完成，即使将附加数据压入堆栈，所有局部variables也将存储在堆栈指针的常数负移位的variables中，并且由调用者在堆栈上压入的所有参数都可以在来自帧指针的恒定正向位移。

这两个约定之间的区别在于它们处理子程序退出的方式。 在C惯例中，返回函数将帧指针复制到堆栈指针[将其恢复到刚刚按下旧帧指针后的值]，popup旧的帧指针值并执行返回。 在呼叫之前，主叫方在堆栈上的任何参数都将保留在那里。 在Pascal惯例中，popup旧的帧指针后，处理器popup函数返回地址，向堆栈指针添加由调用者推送的参数的字节数，然后进入popup的返回地址。 在原来的68000上，有必要使用3指令序列来删除调用者的参数; 原来的8×86和全部680×0处理器包含了一个“ret N”[或680×0等效]指令，在执行返回时将会把N加到堆栈指针。

Pascal惯例的优点是在调用方保存了一些代码，因为调用者不必在函数调用后更新堆栈指针。 但是，它要求被调用的函数确切地知道调用者要将多less字节的参数放入堆栈。 在调用使用Pascal约定的函数之前，无法将正确数目的参数推入堆栈几乎可以确保导致崩溃。 然而，这被抵消了，因为每个被调用的方法中的一些额外的代码会将代码保存在调用该方法的地方。 出于这个原因，大多数原始的Macintosh工具箱例程都使用了Pascal调用约定。

C调用约定的优点是允许例程接受可变数量的参数，即使例程没有使用所有传递的参数也是健壮的（调用者将知道它推送的参数有多less字节，将因此能够清理它们）。 而且，每次函数调用后都不需要执行堆栈清理。 如果一个例程按顺序调用了四个函数，每个函数使用了四个字节的参数，那么在每次调用之后，可以使用一个ADD SP,16来代替使用ADD SP,4全部四个电话。

现在所描述的调用惯例被认为是过时的了。 由于编译器在寄存器使用上变得更有效率，所以方法接受寄存器中的一些参数是很常见的，而不是要求所有参数都被压入栈中。 如果一个方法可以使用寄存器来保存所有的参数和局部variables，则不需要使用帧指针，因此不需要保存和恢复旧指针。 尽pipe如此，在调用链接使用它们的库时，有时还需要使用较早的调用约定。

这里已经有一些非常好的答案。 但是，如果您仍然关心堆栈的LIFO行为，请将其视为一堆框架，而不是一堆variables。 我的意思是说，尽pipe一个函数可以访问不在堆栈顶部的variables，但它仍然只在堆栈顶部的项目上运行：一个堆栈框架。

当然，这也有例外。 整个调用链的本地variables仍然是可用的。 但是他们不会被直接访问。 相反，它们是通过引用传递的（或者通过指针来实现的，这实际上只是在语义上不同）。 在这种情况下，可以进一步访问堆栈帧的局部variables。 但即使在这种情况下，当前正在执行的函数仍然只能在自己的本地数据上运行。 它正在访问一个存储在自己堆栈框架中的引用，这个引用可能是堆中某些东西的引用，静态存储器中或堆栈下的引用。

这是堆栈抽象的一部分，使得函数可以按任意顺序调用，并允许recursion。 顶层堆栈框架是代码直接访问的唯一对象。 其他任何东西都是间接访问的（通过位于顶层栈帧的指针）。

看看你的小程序的汇编可能是有益的，特别是如果你编译没有优化。 我想你会看到，函数中的所有内存访问都是通过堆栈帧指针的偏移量来实现的，这就是编译器如何编写函数的代码。 在通过引用传递的情况下，通过存储在距栈帧指针的某个偏移处的指针，可以看到间接存储器访问指令。

调用堆栈实际上不是一个堆栈数据结构。 在幕后，我们使用的计算机是随机访问机器体系结构的实现。 所以，a和b可以直接访问。

在幕后，机器会：

  • 得到“a”等于读取堆栈顶下的第四个元素的值。
  • 得到“b”等于读取堆栈顶下的第三个元素的值。

http://en.wikipedia.org/wiki/Random-access_machine

    Interesting Posts

    操作系统如何“制造”？

    3D数组如何存储在C？