调用堆栈到底是如何工作的?

我试图更深入地了解编程语言的底层操作是如何工作的,尤其是它们是如何与操作系统/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 或任何其他编程语言。

But if that's the case, then what happens after line X? Because obviously, the next thing we need is to work with a and b, but that would mean that the OS/CPU (?) has to pop out d and c first to get back to a and b. But then it would shoot itself in the foot, because it needs c and d in the next line.

因此,我想知道 没错在幕后发生了什么?

另一个相关的问题,假设我们传递一个引用到另一个函数,如下所示:

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


// line X


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

从我的理解来看,这意味着 doSomething中的参数基本上指向相同的内存地址,如 foo中的 ab。但是这又意味着没有 弹出堆栈,直到我们到达 ABC1和 b发生。

Those two cases make me think that I haven't fully grasped how 没错 the stack works and how it strictly follows the LIFO rules.

36922 次浏览

调用堆栈也可以称为帧堆栈。
在 LIFO 原则之后的 堆积如山不是局部变量,而是被调用的函数的整个堆栈帧(“调用”)。在所谓的 功能序言功能序言结束语中,局部变量分别与这些帧一起被推送和弹出。

在框架内部,变量的顺序是完全未指定的; 编译器 “重新排序”局部变量在框架内的位置适当地优化它们的对齐方式,以便处理器能够尽快地获取它们。关键的事实是,在帧的整个生命周期中,变量相对于某个固定地址的偏移量是恒定的-所以它足以采取锚地址,例如,框架本身的地址,并与该地址的偏移量的变量。这样的锚地址实际上包含在存储在 EBP 寄存器中的所谓 baseframe pointer中。另一方面,偏移量在编译时清楚地知道,因此硬编码到机器代码中。

这张来自 维基百科的图表显示了典型的调用堆栈的结构类似于 1:

Picture of a stack

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

Example

#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

我把代码分成三个部分。 The function prologue consists of the first three operations:

  • 将基指针推送到堆栈上。
  • 堆栈指针保存在基指针中
  • 减去堆栈指针为局部变量腾出空间。

然后将 cin移动到 EDI register2,并调用 get; 返回值在 EAX 中。

到目前为止还不错,现在有趣的事情发生了:

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

终于,

  • main的返回值存储在 EAX: 0中,这是因为隐式的 return语句。 您还可能看到 xorl rax rax而不是 movl
  • 离开并返回到呼叫站点。 leave是这个尾声的缩写,并含蓄地
    • 将堆栈指针替换为基指针和
    • 弹出基指针。

在执行这个操作和 ret之后,框架已经被有效地弹出,尽管由于我们正在使用 cdecl 调用约定,调用方仍然需要清理参数。其他约定,例如 stdcall,要求被调用方进行整理,例如将字节数量传递给 ret

Frame Pointer Omission

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

这种优化被称为 FPO (帧指针省略) ,在 Clang 的海湾合作委员会和 -Oy中由 -fomit-frame-pointer设置,请注意,它是由每个 > 0的优化级别隐式触发的,当且仅当调试仍然可能,因为除此之外没有任何成本。 有关详细信息,请参阅 给你给你


正如注释中指出的那样,框架指针可能指向返回地址后面的地址。

2 注意,以 R 开头的寄存器是以 E. EAX 开头的寄存器的64位对应物,指定 RAX 的四个低阶字节。为了清楚起见,我用了32位寄存器的名字。

因为很明显,接下来我们需要使用 a 和 b 但这意味着 OS/CPU (?)必须先弹出 d 和 c 才能返回到 a 和 b。但这样的话,它就会伤到自己的脚,因为下一行需要 c 和 d。

In short:

没有必要打破这些论点。调用方 foo传递给函数 doSomething的参数和 doSomething都可以作为 < a href = “ https://stackoverflow./q/1395591/2455888”> < em > 基本指针 的偏移量引用中的局部变量。
那么,

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

详情如下:

规则是 每个函数调用都会创建一个堆栈帧(最小值是返回的地址)。因此,如果 funcA调用 funcB,而 funcB调用 funcC,就会在另一个堆栈帧之上设置三个堆栈帧。When a function returns, its frame becomes invalid.一个行为良好的函数只作用于它自己的堆栈框架,并且不侵入另一个堆栈框架。换句话说,POPing 被执行到顶部的堆栈帧(从函数返回时)。

enter image description here

The stack in your question is setup by caller foo. When doSomething and doAnotherThing are called, then they setup their own stack. The figure may help you to understand this:

enter image description here

请注意,要访问参数,函数体必须从存储返回地址的位置向下遍历(更高的地址) ,要访问本地变量,函数体必须相对于存储返回地址的位置向上遍历堆栈(更低的地址)。实际上,典型的编译器为函数生成的代码就是这样做的。编译器为此专用一个名为 EBP 的寄存器(基本指针)。另一个相同的名称是帧指针。作为函数体的第一步,编译器通常将当前 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);

the following code will be generated

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

and the assembly code for the function will be (set-up by callee before returning)

^
| _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
 


参考文献:

正如其他人指出的那样,在参数超出作用域之前,不需要弹出参数。

我将粘贴一些例子从“指针和记忆”尼克 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为单位标出 代码和当时的内存状态如图所示:

enter image description here

这里已经有一些很好的答案了。但是,如果您仍然关心堆栈的 LIFO 行为,那么可以将它看作是一个帧堆栈,而不是一个变量堆栈。我的意思是,尽管函数可以访问不在堆栈顶部的变量,但它仍然只能在堆栈顶部的 item上操作: 一个堆栈帧。

当然,也有例外。整个调用链的局部变量仍然是分配和可用的。但不能直接进入。相反,它们是通过引用传递的(或者通过指针传递的,这实际上只是语义上的不同)。在这种情况下,可以访问更低层的堆栈帧的局部变量。它访问存储在自己的堆栈帧中的引用,这个引用可能是对堆、静态内存中的某个内容的引用,也可能是对堆栈下方的某个内容的引用。

这是堆栈抽象的一部分,它使函数可以以任意顺序调用,并允许递归。顶部堆栈帧是代码直接访问的唯一对象。其他任何内容都是间接访问的(通过位于堆栈顶部框架中的指针)。

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

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

当使用任何一种约定调用子例程时,在调用该例程之前,任何参数都会被推送到堆栈上。然后,例程的代码将帧指针的当前值推送到堆栈上,将堆栈指针的当前值复制到帧指针,并从堆栈指针中减去局部变量(如果有的话)使用的字节数。一旦这样做了,即使额外的数据被推到堆栈上,所有的局部变量将被存储在变量中,与堆栈指针的负位移是恒定的,所有的参数被调用者推到堆栈上,可以访问在一个恒定的正位移从帧指针。

The difference between the two conventions lies in the way they handle an exit from subroutine. In the C convention, the returning function copies the frame pointer to the stack pointer [restoring it to the value it had just after the old frame pointer was pushed], pops the old frame pointer value, and performs a return. Any parameters the caller had pushed on the stack before the call will remain there. In the Pascal convention, after popping the old frame pointer, the processor pops the function return address, adds to the stack pointer the number of bytes of parameters pushed by the caller, and then goes to the popped return address. On the original 68000 it was necessary to use a 3-instruction sequence to remove the caller's parameters; the 8x86 and all 680x0 processors after the original included a "ret N" [or 680x0 equivalent] instruction which would add N to the stack pointer when performing a return.

Pascal 约定的优点是可以在调用方节省一点代码,因为调用方不必在函数调用后更新堆栈指针。但是,它要求被调用的函数确切地知道调用方将在堆栈上放置多少字节的参数。如果在调用使用 Pascal 约定的函数之前未能将适当数量的参数压入堆栈,几乎肯定会导致崩溃。但是,由于每个被调用方法中的一点额外代码将在调用方法的位置保存代码,因此这一点有所偏移。出于这个原因,大多数原始的 Macintosh 工具箱例程都使用了 Pascal 调用约定。

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

现在,所描述的调用约定被认为有些过时了。由于编译器在使用寄存器方面已经变得更加高效,所以通常方法都会接受寄存器中的一些参数,而不是要求所有的参数都被推送到堆栈上; 如果一个方法可以使用寄存器来保存所有的参数和局部变量,那么就不需要使用框架指针,因此也不需要保存和恢复旧的。尽管如此,在调用链接到使用它们的库时,有时还是有必要使用旧的调用约定。

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

在幕后,机器做到了:

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

Http://en.wikipedia.org/wiki/random-access_machine

下面是我为 Windows 上使用 Windows x64调用约定的 C + + 程序的调用堆栈创建的图表。它比谷歌图片版本更准确,更现代:

enter image description here

与上图的精确结构相对应,下面是在 Windows 7上的 notepad.exe x64调试,其中函数的第一条指令‘ current function’(因为我忘了它是什么函数)即将执行。

enter image description here

低地址和高地址被交换,因此堆栈在这个图中向上攀升(这是第一个图的垂直翻转,还要注意的是,数据被格式化为显示四字而不是字节,所以不能看到小的 endiism)。黑色是主空间; 蓝色是返回地址,它是调用函数或调用函数中的标签在调用后指令的偏移量; 橙色是对齐方式; 粉色是 rsp在函数开始之后指向的位置,或者更确切地说,是在调用之前(如果使用 alloca)。homespace_for_the_next_function+return_address值是 windows 上允许的最小帧,因为必须维护被调用函数开始处的16字节 rsp 对齐,它还包括8字节对齐,这样返回地址后指向第一个字节的 rsp将被对齐到16字节(因为在调用函数时 rsp保证被对齐到16字节,而 homespace+return_address = 40不能被16整除,所以你需要额外的8字节来确保在函数调用后 rsp被对齐)。因为这些函数不需要任何堆栈局部变量(因为它们可以优化为寄存器)或堆栈参数/返回值(因为它们适合寄存器) ,并且不使用任何其他字段,所以绿色的堆栈帧的大小都是 alignment+homespace+return_address

红色的函数行概述了被调用函数在逻辑上“拥有”+ 在调用约定中通过值读取/修改的内容,而不需要引用它(它可以修改在堆栈上传递的参数,这个参数太大,无法在 -Ofast 寄存器中传递) ,这是堆栈帧的经典概念。绿色帧标明了调用的结果和被调用函数的分配: 第一个绿色帧显示了 RtlUserThreadStart在函数调用期间实际分配的内容(从调用之前到执行下一个调用指令) ,并且从返回地址之前的第一个字节到函数序言分配的最后一个字节(如果使用 alloca 则更多)。RtlUserThreadStart将返回地址本身分配为 null,所以在序言中看到的是 sub rsp, 48h而不是 sub rsp, 40h,因为没有对 RtlUserThreadStart的调用,它只是在堆栈底部的 rip处开始执行。

Stack space that is needed by the function is assigned in the function prologue by decrementing the stack pointer.

例如,以下面的 C + + 和它编译成的 MASM (-O0)为例。

typedef struct _struc {int a;} struc, pstruc;
int func(){return 1;}
int square(_struc num) {
int a=1;
int b=2;
int c=3;
return func();
}
_DATA SEGMENT
_DATA ENDS


int func(void) PROC ; func
mov eax, 1
ret 0
int func(void) ENDP ; func


a$ = 32  //4 bytes from rsp+32 to rsp+35
b$ = 36
c$ = 40
num$ = 64


//masm shows stack locals and params relative to the address of rsp; the rsp address
//is the rsp in the main body of the function after the prolog and before the epilog


int square(_struc) PROC ; square
$LN3:
mov DWORD PTR [rsp+8], ecx
sub rsp, 56 ; 00000038H
mov DWORD PTR a$[rsp], 1
mov DWORD PTR b$[rsp], 2
mov DWORD PTR c$[rsp], 3
call int func(void) ; func
add rsp, 56 ; 00000038H
ret 0
int square(_struc) ENDP ; square

可以看到,当 call指令分配8字节的返回地址时,保留了56个字节,绿色栈帧的大小为64个字节。

56字节包括12字节的局部变量、32字节的主空间和12字节的对齐。

所有被调用寄存器的保存和存储寄存器参数都发生在序言之前,序言保留(使用 sub rsp, x指令)函数主体所需的堆栈空间。对齐处于 sub rsp, x指令保留的空间的最高地址,函数中的最终局部变量被分配到之后的下一个较低地址(在对原始数据类型本身的分配中,它从该分配的最低地址开始,按字节顺序向较高地址运行,因为它是小端) ,这样,函数中的第一个原始类型(数组单元格,变量等)位于堆栈的顶部,尽管局部变量可以按任意顺序分配。下图显示了上面的不同随机示例代码,它不调用任何函数(仍然使用 x64Windowscc) :

enter image description here

如果删除对 func()的调用,它只保留24字节,即12字节的局部变量和12字节的对齐。对齐位于框架的开始。当一个函数通过递减 rsp将某些内容推送到堆栈或在堆栈上保留空间时,无论是否调用另一个函数,rsp都需要对齐。如果堆栈空间的分配可以优化出来,没有 homespace+return_addreess是必需的,因为函数没有发出调用,那么将不会有对齐要求,因为 rsp不会改变。如果堆栈将与它需要分配的局部变量(如果调用,则为 + homespace+return_address)对齐16,那么它也不需要对齐,实际上它将需要分配给16字节边界的空间四舍五入。

rbp is not used on the x64 Windows calling convention unless alloca is used.

On gcc 32 bit cdecl and 64 bit system V calling conventions, rbp is used, and the new rbp points to the first byte after the old rbp (only if compiling using -O0, because it is saved to the stack on -O0, otherwise, rbp will point to the first byte after the return address). On these calling conventions, if compiling using -O0, it will, after callee saved registers, store register parameters to the stack, and this will be relative to rbp and part of the stack reservation done by the rsp decrement. Data within the stack reservation done by the rsp decrement is accessed relative rbp rather than rsp, unlike Windows x64 cc. On the Windows x64 calling convention, it stores parameters that were passed to it in registers to the homespace that was assigned for it if it is a varargs function or compiling using -O0. If it is not a varargs function then on rbp3, it will not write them to the homespace but the homespace will still be provided to it by the calling function, this means that it actually accesses those variables from the register rather from the homespace location on the stack after it stores it there, unlike rbp4 (which saves them to the homespace and then accesses them through the stack and not the registers).

如果一个函数调用放置在前一个图表所表示的函数中,堆栈现在看起来就像这样,在被调用函数的序言开始之前(Windows x64 cc) :

enter image description here

Orange 表示被调用方可以自由排列的部分(当然,数组和结构保持连续,并且朝着更高的地址前进,每个元素都是小端点) ,所以它可以以任意顺序放置变量和返回值分配,并且它在 rcx中传递返回值分配的指针,当被调用方所调用的函数的返回类型无法在 rax中传递时,它要写入返回值分配的指针。在 -O0上,如果返回值不能在 rax中传递,那么还会创建一个匿名变量(以及返回值空间和它被赋给的任何变量,因此可以有结构的3个副本)。-Ofast不能优化返回值空间,因为它是按值返回的,但是如果没有使用返回值,它会优化匿名返回变量,或者直接赋值给返回值被赋值的变量,而不创建匿名变量,所以 -Ofast有2/1个拷贝,-O0有3/2个拷贝(返回值被赋值给变量/返回值没有被赋值给变量)。蓝色表示被调用方必须按照被调用方调用约定的确切顺序提供的部分(参数必须按照这个顺序,这样函数签名中从左到右的第一个堆栈参数就位于堆栈的顶部,这与 cdecl (32位 cc)对堆栈参数的排序方式相同。然而,被调用方的对齐可以在任何位置,尽管我只在本地寄存器和被调用方推入寄存器之间看到过它。

If the function calls multiple functions, the call is in the same place on the stack for all the different possible callsites in the function, this is because the prologue caters for the whole function, including all calls it makes, and the parameters and homespace for any called function is always at the end of the allocation made in the prologue.

It turns out that C/C++ Microsoft calling convention only passes a struct in the registers if it fits into one register, otherwise it copies the local / anonymous variable and passes a pointer to it in the first available register. On gcc C/C++, if the struct does not fit in the first 2 parameter registers then it's passed on the stack and a pointer to it is not passed because the callee knows where it is due to the calling convention.

无论数组的大小如何,数组都是通过引用传递的。因此,如果你需要使用 rcx作为返回值分配的指针,那么如果第一个参数是一个数组,指针将在 rdx中传递,这将是一个指向正在传递的局部变量的指针。在这种情况下,它不需要将其作为参数复制到堆栈中,因为它不是通过值传递的。但是,如果没有可用的寄存器来传递指针,则通过引用在堆栈上传递指针。