堆栈(stack)又称为栈或堆叠,是计算机科学里最重要且最基础的数据结构之一,它按照FILO(First In Last Out,后进先出)的原则存储数据。
栈的相关概念:
下面是栈的示意图,从图中可以清楚的看到,不管是插入数据还是删除数据,都是在栈顶进行的,还有就是FILO原则,可以看到,如果你想取出B的值,那么你必须先要将B的上面的C取出,要取出C的值,就得取出C上面的值,以此类推。
从技术上说,栈就是CPU寄存器里的某个指针所指向的一片内存区域。这里所说的“某个指针”通常位于x86/x64平台的ESP寄存器/RSP寄存器,以及ARM平台的SP寄存器。
操作栈的最常见的指令时PUSH(压栈)和POP(弹栈)。PUSH指令会对ESP/RSP/SP寄存器的值进行减法运算,使之减去4(32位)或8(64位),然后将操作数写到上述寄存器里的指针所指向的内存中。
POP指令是PUSH指令的逆操作:它先从栈指针指向的内存中读取数据,用以备用(通常是写到其他寄存器里),然后再将栈指针的数值加上4或8.
下图演示了x86平台下的push指令和pop指令,指令push Z,首先ESP的值-4,然后将Z的值写入新的ESP所指的内存中,指令pop eax,先将Z的值存入EAX寄存器,然后进行ESP+4。指令POP EBX,首先将栈顶元素存入EBX,然后ESP+4。
下面通过一个例子说明,首先是push eax,此时eax的值为0x115fcc0,ESP的值为0x115fc68,栈顶的值为0x75936359
当push eax执行完之后结果如下图,此时ESP的值为0x115fc64(为原来ESP的值-4,注意多数栈是逆增长的,也就是向低地址增长),栈顶的值为0x115fcc0(EAX的值)
当pop ebx的指令执行完时,此时ebx的值为0x115fcc0(从栈顶弹出来的),ESP的值为0x115fc68(上一步ESP的值+4),此时之前的数据0x115fcc0依然在内存中(地址为0x115fc64的地方),只不过这个值不再是栈的一部分了,因为ESP指向的是栈顶。
栈帧也叫过程活动记录,是编译器用来实现过程/函数调用的一种数据结构。简言之,栈帧就是利用EBP(栈帧指针,请注意不是ESP)寄存器访问局部变量、参数、函数返回地址等的手段。
;栈帧结构
PUSH EBP ;函数开始(使用EBP前先把已有值保存到栈中)
MOV EBP, ESP ;保存当前ESP到EBP中
... ;函数体
;无论ESP值如何变化,EBP都保持不变,可以安全访问函数的局部变量、参数
MOV ESP, EBP ;将函数的起始地址返回到ESP中
POP EBP ;函数返回前弹出保存在栈中的值
RETN ;函数终止
每一次函数的调用,都会在调用栈(call stack)上维护一个独立的栈帧(stack frame)。每个独立的栈帧一般包括:
栈是从高地址向低地址延伸,一个函数的栈帧用EBP和ESP这两个寄存器来划定范围。EBP指向当前栈帧的底部,ESP始终指向栈帧的顶部。
EBP寄存器又被称为帧指针(Frame Pointer)
ESP寄存器又被称为栈指针(Stack Pointer)
一个很常见的活动记录示例如图所示