何为堆栈

堆Heap与栈Stack是两个不同的概念,在理解这两个概念时,需要放到具体的场景下,因为不同的场景下,堆与栈代表不同的含义.一般情况下有两层含义

程序内存布局的场景下,堆与栈表示两种内存管理方式
数据结构场景下,堆与栈表示两种常用的数据结构

内存管理方式的堆和栈

堆Heap

1. 堆由开发人员分配和释放,若开发人员不释放,程序结束的时候由OS回收,分配方式类似于链表.
2. 堆得内存增长方向由低地址到高地址,也称为向上增长.

栈Stack

1. 栈由操作系统自动分配释放,用于存放函数的参数值,局部变量等.
2. 函数中定义的局部变量按照先后顺序(具体的顺序根据编译器决定)依次压入栈中,也就是说相邻的变量的地址之间不会存在其他变量.
3. 栈的内存增长方向和堆相反,由高地址到低地址,也称为向下增长.

观察下面这段程序,我们可以设想一下变量的地址的大小:

#include <stdio.h>

int func(void)
{
    int a;
    int b;
    int c;
    printf("[func] &a = %p, &b = %p, &c = %p\n", &a, &b, &c);
}

int main(void)
{
    int a;
    int b;
    int c;
    printf("[main] &a = %p, &b = %p, &c = %p\n", &a, &b, &c);
    
    func();
    return 0;
}

猜测:

1. 如果按照栈是向下增长的情况,那么main函数以及func函数中的局部变量a,b,c的地址关系应该是: &a > &b > &c
2. main函数调用子函数func,那么func函数中的局部变量应该比main函数中的小, &func_a < &main_a, &func_b < &main_b, &func_c < &main_c

那么实际运行结果如何呢(linux下使用gcc编译的结果)

[main] &a = 0x7ffe3e3ddc2c, &b = 0x7ffe3e3ddc30, &c = 0x7ffe3e3ddc34
[func] &a = 0x7ffe3e3ddbfc, &b = 0x7ffe3e3ddc00, &c = 0x7ffe3e3ddc04

可以观察出两个结果:

1. 局部变量a,b,c的地址是&a < &b < &c.和我们想的栈是从高地址到地址的方式有出入.
2. 但是可以看到func函数中的局部变量地址比main中的局部变量地址小, &func_a < &main_a, &func_b < &main_b, &func_c < &main_c

从我们观察的结果得出,如果以函数整体来看,那么栈在linux下确实是从高地址到低地址来分配的.其实事实也是这样,但是为什么函数内的局部变量的地址不一样呢,这里就牵扯到了栈的增长方向与栈帧布局

这里说的栈是指函数调用栈,是以栈帧(stack frame)为单位的.
每一次函数调用都会在栈上分配一个新的栈帧,在这次函数调用结束时释放空间.
被调用的函数(callee)的栈帧相对于调用函数(caller)的栈帧反应了栈的增长方向;如果被调用的函数的栈帧比调用函数的栈帧在更低的地址,那么栈就是向下增长;反之向上增长.

而在一个栈帧内,局部变量是如何分配到栈帧里的(所谓的栈帧布局,stack frame layout),这完全是编译器的自由.
每个函数都是一个栈帧,栈的分配是按照这个来的,而栈帧里怎么分配完全看编译器.

在windows下栈与堆得增长方向是没有定义的.

那么我们其实可以写一个函数判断栈帧的增长方向,如下

int find_stack_direction(void)
{
    int var;//用于获取栈地址 
    static int *addr = NULL; //用于存放第一个var的地址.

    if (addr == NULL)
    {
        addr = &var;
        find_stack_direction();
    }
    else
    {
        printf("addr = %p, &var = %p\n", addr, &var);
        if (addr > &var)
        {
            printf("栈帧向下增长\n");
        }
        else
        {
            printf("栈帧向上增长\n");
        }
    }
}

int main(void)
{
    find_stack_direction();
    return 0;
}

运行结果如下

addr = 0x7ffe8ebf1604, &var = 0x7ffe8ebf15e4
栈帧向下增长

内存管理上堆栈的区别

堆与栈实际上是操作系统对进程占用的内存空间的两种管理方式,主要有如下几种区别:

• 管理方式不同:栈由操作系统自动分配释放,无需我们手动控制;堆的申请和释放工作由程序员控制,容易产生内存泄漏
• 空间大小不同:每个进程拥有的栈大小要远远小于堆大小.理论上,进程可申请的堆大小为虚拟内存大小,进程栈的大小 64bits 的 Windows 默认 1MB,64bits 的 Linux 默认 10MB
• 生长方向不同:堆的生长方向向上,内存地址由低到高;栈的生长方向向下,内存地址由高到低.
• 分配方式不同:堆都是动态分配的,没有静态分配的堆.栈有2种分配方式:静态分配和动态分配.静态分配是由操作系统完成的,比如局部变量的分配.动态分配由alloca()函数分配,但是栈的动态分配和堆是不同的,它的动态分配是由操作系统进行释放,无需我们手工实现.
• 分配效率不同:栈由操作系统自动分配,会在硬件层级对栈提供支持:分配专门的寄存器存放栈的地址,压栈出栈都有专门的指令执行,这就决定了栈的效率比较高.堆则是由C/C++提供的库函数或运算符来完成申请与管理,实现机制较为复杂,频繁的内存申请容易产生内存碎片.显然,堆的效率比栈要低得多.
• 存放内容不同:栈存放的内容,函数返回地址,相关参数,局部变量和寄存器内容等.当主函数调用另外一个函数的时候,要对当前函数执行断点进行保存,需要使用栈来实现,首先入栈的是主函数下一条语句的地址,即扩展指针寄存器的内容(EIP),然后是当前栈帧的底部地址,即扩展基址指针寄存器内容(EBP),再然后是被调函数的实参等,一般情况下是按照从右向左的顺序入栈,之后是被调函数的局部变量,注意静态变量是存放在数据段或者BSS段,是不入栈的.出栈的顺序正好相反,最终栈顶指向主函数下一条语句的地址,主程序又从该地址开始执行.堆,一般情况堆顶使用一个字节的空间来存放堆的大小,而堆中具体存放内容是由程序员来填充的.

数据结构上的堆和栈

堆Heap

堆是一种常用的树形结构,是一种特殊的完全二叉树,当且仅当满足所有节点的值总是不大于或不小于其父节点的值的完全二叉树被称之为堆.堆的这一特性称之为堆序性.因此,在一个堆中,根节点是最大(或最小)节点.如果根节点最小,称之为小顶堆(或小根堆),如果根节点最大,称之为大顶堆(或大根堆).堆的左右孩子没有大小的顺序.下面是一个小顶堆示例:

栈Stack

栈是一种运算受限的线性表,其限制是指只仅允许在表的一端进行插入和删除操作,这一端被称为栈顶(Top),相对地,把另一端称为栈底(Bottom).把新元素放到栈顶元素的上面,使之成为新的栈顶元素称作进栈,入栈或压栈(Push);把栈顶元素删除,使其相邻的元素成为新的栈顶元素称作出栈或退栈(Pop).这种受限的运算使栈拥有先进后出的特性(First-In/Last-Out),简称FILO.

堆栈分别存放了什么

• 堆:由程序员决定
• 栈:函数返回地址, 函数参数, 局部变量, 寄存器内容

以下面这个程序为例:

main()
{
    int b;//stack
    char s[] = "abc";//stack
    char *p2;//stack
    char *p3 = "123456";//123456\0在常量区, p3在stack上.
    p1 = (char *)malloc(10);//heap
    p2 = (char *)malloc(20);//heap
}

为什么栈向下增长

计算机内存分配了代码段(.text),初始化的数据段(.data),未初始化的数据段(.bss),堆空间(heap),栈空间(stack),命令行参数以及环境变量区域().

每一个可执行的C程序,从低地址到高地址依次是:text, data, bss, heap, stack,命令行参数以及环境变量,如下图:

程序计数器(program counter,简称pc)的缺省指向0地址,计算机开机后从程序计数器指向的地址开始执行程序,每执行完一条指令后,程序计算器自动加1.

因此很自然的,.text段从低地址区间开始加载,向高地址区间扩展.

heap从低地址向高地址拓展,做内存管理相对要简单些,为了避免栈空间和堆空间冲突,最大利用地址空间,很自然的,我们会选择把栈底设置在高地址区间,然后让栈向下增长.

• 优点
  stack从高地址向低地址扩展,这样栈空间的起始位置就能确定下来.动态的调整栈空间大小也不需要移动栈内的数据,如果是从低地址到高地址的扩展,结尾的地址是固定的,如果要扩大或缩小,则需要移动整个栈的数据.

并且这样设计可以使得堆和栈能够充分利用空闲的地址空间.如果栈向上涨的话,我们就必须得指定栈和堆的一个严格分界线,但这个分界线怎么确定呢?平均分?但是有的程序使用的堆空间比较多,而有的程序使用的栈空间比较多.

所以就可能出现这种情况:一个程序因为栈溢出而崩溃的时候,其实它还有大量闲置的堆空间呢,但是我们却无法使用这些闲置的堆空间.所以呢,最好的办法就是让堆和栈一个向上涨,一个向下涨,这样它们就可以最大程度地共用这块剩余的地址空间,达到利用率的最大化.

• 所有的栈都是向下增长吗?
  大部分CPU指令集设计了函数调用架构,定义了专用的调用/返回指令,并在指令中隐含规定栈的方向.

  • 主流1:向低地址扩展:x86,MIPS
  • 主流2:自由选择:Arm(但个别指令仅支持向低)
  • 罕见:向高地址扩展:PA-RISC,操作系统Multics
  • 非主流:System z,栈是个链表

  如果CPU同时支持向上和向下,例如arm,那么编译器需要指定程序的调用方向,一般还是选择向下.
  比较罕见的极端的案例是Multics操作系统,这是Unix的巨无霸前身,设计者刻意选用向高地址扩展,因为该架构有助于防御缓冲区溢出攻击.

参考文献

• 一文读懂堆与栈的区别
• 内存管理之栈（stack）