查看“Stack”的源代码

：''堆栈也可以引用[[：Category:Networking | Networking]]中的TCP/IP堆栈。 本文讨论体系结构中使用的数据结构和堆栈。''

[[Image:Stack.png|thumb|right|A normal stack, that grows upwards.]]

“堆栈”是一种数据结构。 您可以分别将元素推送到和从中弹出。 但是，与[[FIFO]]（先进先出）不同，从堆栈中弹出的元素是您最后推送的元素。 因此，堆栈也称为后进先出或FILO（先进先出）。

在[[：Category:X86 | X86架构]]和许多其他架构中，有一个用于代码执行的堆栈。 它用于在调用例程时存储返回指针，但也可以在其上存储临时数据和局部变量。


== 堆栈理论 ==

许多语言和体系结构都有一个可供使用的堆栈。 当返回值存储在上面时，堆栈帧的概念就出现了。 堆栈被划分为多个堆栈帧。 每个堆栈帧包含例程的本地/临时数据、参数和前一个例程（调用者）的返回值。

=== X86体系结构上的堆栈示例 ===

在X86体系结构上，堆栈向下增长。 堆栈帧具有关于调用约定的特定结构。 CDECL呼叫约定是使用最广泛的。 它很可能由编译器使用。 使用两个寄存器：

*“”“<tt>ESP</tt>：“””扩展堆栈指针。 包含“栈顶”地址的32位值（更准确地说是X86上的“栈底”）
*''<tt>EBP</tt>：''扩展基指针。 使用CDECL调用约定时定义当前堆栈帧的32位值。 它指向当前的本地数据。 它还可以访问例程参数。

在实现内核时要小心。 如果使用[[segmentation]]，则应将<tt>DS</tt>段配置为其基址与SS相同。 否则，在将指向局部变量的指针传递到函数中时，您可能会遇到问题，因为<tt>普通GPRs</tt>无法以您可能认为的方式访问堆栈。

下面是一个示例堆栈。 这些元素是保护模式下的4字节字：

内存地址：堆栈元素：

                +----------------------------+
0x105000      | Parameter 1 for routine 1  | \
+----------------------------+  |
0x104FFC      | First callers return addr. |   >  Stack frame 1
+----------------------------+  |
0x104FF8      | First callers EBP          | /
+----------------------------+
0x104FF4   +->| Parameter 2 for routine 2  | \  <-- Routine 1's EBP
|  +----------------------------+  |
0x104FF0   |  | Parameter 1 for routine 2  |  |
|  +----------------------------+  |
0x104FEC   |  | Return address, routine 1  |  |
|  +----------------------------+  |
0x104FE8   +--| EBP value for routine 1    |   >  Stack frame 2
+----------------------------+  |
0x104FE4   +->| Local data                 |  | <-- Routine 2's EBP
|  +----------------------------+  |
0x104FE0   |  | Local data                 |  |
|  +----------------------------+  |
0x104FDC   |  | Local data                 | /
|  +----------------------------+
0x104FD8   |  | Parameter 1 for routine 3  | \
|  +----------------------------+  |
0x104FD4   |  | Return address, routine 2  |  |
|  +----------------------------+   >  Stack frame 3
0x104FD0   +--| EBP value for routine 2    |  |
+----------------------------+  |
0x104FCC   +->| Local data                 | /  <-- Routine 3's EBP
|  +----------------------------+
0x104FC8   |  | Return address, routine 3  | \
|  +----------------------------+  |
0x104FC4   +--| EBP value for routine 3    |  |
+----------------------------+   >  Stack frame 4
0x104FC0      | Local data                 |  | <-- Current EBP
+----------------------------+  |
0x104FBC      | Local data                 | /
+----------------------------+
0x104FB8      |                            |    <-- Current ESP
\/\/\/\/\/\/\/\/\/\/\/\/\/\/

The CDECL calling convention is described here:

; Caller's responsibilities
* Push parameters in reverse order (last parameter pushed first)
* Perform the call
* Pop the parameters, use them, or simply increment ESP to remove them (stack clearing)
* The return value is stored in EAX

; Callee's responsibilities (callee is the routine being called)
* Store caller's EBP on the stack
* Save current ESP in EBP
* Code, storing local data on the stack
* For a fast exit load the old ESP from EBP, else pop local data elements
* Pop the old EBP and return &ndash; store return value in EAX

It looks like this in assembly (NASM):

SECTION .text

caller:

     ; ...
     
     ; Caller responsibilities:
     PUSH  3         ; push the parameters in reverse order
     PUSH  2
     CALL  callee    ; perform the call
     ADD   ESP, 8    ; stack cleaning (remove the 2 words)
     
     ; ... Use the return value in EAX ...


callee:

     ; Callee responsibilities:
     PUSH  EBP       ; store caller's EBP
     MOV   EBP, ESP  ; save current stack pointer in EBP
     
     ; ... Code, store return value in EAX ...
     
     ; Callee responsibilities:
     MOV   ESP, EBP  ; remove an unknown number of local data elements
     POP   EBP       ; restore caller's EBP
     RET             ; return

The GCC compiler does all this automatically, but if you have to call C/C++ methods from assembly or reverse, you have to know the convention. Now look at one stack frame (the callee's):

+-------------------------+
| Parameter 3             |
+-------------------------+
| Parameter 2             |
+-------------------------+
| Parameter 1             |
+-------------------------+
| Caller's return address |
+-------------------------+
| Caller's EBP value      |
+-------------------------+
| Local variable          | <-- Current EBP
+-------------------------+
| Local variable          |
+-------------------------+
| Local variable          |
+-------------------------+
| Temporary data          |
+-------------------------+
| Temporary data          |
+-------------------------+
|                         | <-- Current ESP
+-------------------------+

Using <tt>EBP</tt> the callee can access both parameters and local variables:

MOV  EAX, <nowiki>[[EBP + 12]]</nowiki>  ; Load parameter 1 into EAX

MOV  EAX, <nowiki>[[EBP + 16]]</nowiki>  ; Load parameter 2

MOV  EAX, <nowiki>[[EBP + 4 * EBX + 12]]</nowiki>  ; Load parameter EBX (0-indexed)

MOV  EAX, <nowiki>[[EBP]]</nowiki>       ; Load local variable 1

MOV  EAX, <nowiki>[[EBP - 4]]</nowiki>   ; Load local variable 2

X86还有其他调用约定。举几个例子：Pascal调用约定、fastcall约定、stdcall。 更多关于维基百科的信息，请参阅下面的链接。

=== 设置堆栈 ===

创建内核时，必须手动设置堆栈。 

如果从实模式转到保护模式，还必须设置堆栈。 这是因为<tt>SS</tt>段可能会发生变化，因此受保护模式下的<tt>ESP</tt>不会指向与实际模式下的<tt>SP</tt>相同的位置。 如果您在实模式和保护模式之间切换很多，那么它们可以共享堆栈。 你必须自己找到一个聪明的解决方案。 这是可以做到的。

在保护模式下，只需将新指针值移动到<tt>ESP</tt>寄存器中即可设置堆栈：

MOV ESP，0x105000；设置堆栈指针

记住，它是向下生长的。 您可以在内核的<tt>中为它分配空间。BSS</tt>部分，如果它包含一个：

SECTION .text

set_up_stack:

     MOV  ESP, stack_end  ; Set the stack pointer

SECTION .bss

stack_begin:
RESB 4096  ; Reserve 4 KiB stack space
stack_end:

如果您的内核是由[[Multiboot]]兼容的引导加载程序引导的，比如[[GRUB]]，则会向您提供一个内存映射。 您可以通过查找适当大小的空闲内存块来设置堆栈。 您只需确保在设置堆栈指针时不会覆盖任何重要数据或代码。

=== 安全 ===

堆栈很容易使用，但有一个问题。 没有“结束”，所以它容易受到缓冲区溢出攻击的变化。 攻击者推送的元素超过堆栈所能容纳的数量，因此元素被推送到堆栈内存之外，从而覆盖代码，然后攻击者可以执行这些代码。

在X86保护模式下，可以通过仅为堆栈分配[[GDT | GDT描述符]]来解决此问题，该描述符定义了堆栈的边界。

== 堆栈跟踪 ==

调试时，通常会显示堆栈跟踪，这很有帮助。 [[Stack Trace]]介绍了如何实现这一点，并使用上面的堆栈布局为X86 CDECL提供了示例代码。

== 展开堆栈 ==

展开堆栈很复杂。它是在使用异常时完成的，比如在[[C++]]中。它是在抛出异常时执行的。展开堆栈的目的是调用堆栈帧的本地对象的析构函数，并移除堆栈帧，直到找到合适的平台。着陆台是最好的选择。。catch块在C++或java中。catch块必须与异常匹配，即RuntimeException对象不能作为String对象捕获。

退绕算法取决于体系结构。 通常，该算法在语言运行库中提供。 当使用GCC和C++时，它在与应用程序链接的LIbSuc++库中定义。 但是，在创建内核时不会发生这种情况。 libsupc++库也过于臃肿，无法在内核空间中使用。

== 另见 ==

=== 文章 ===
[[Stack Trace]] - Trace the called functions from the stack

=== 线程 ===

=== 外部链接 ===

* [[wikipedia:x86 calling conventions| x86 calling conventions]] on Wikipedia.
* [[wikipedia:Stack (data structure)| Stack (data structure)]] on Wikipedia.

[[Category:OS theory]]