永远也不完美的程序

不断学习,不断实践,不断的重构……

常用链接

统计

积分与排名

好友链接

最新评论

堆和栈(转)

堆(heap)和栈(stack)是C/C++编程不可避免会碰到的两个基本概念。首先,这两个概念都可以在讲数据结构的书中找到,他们都是基本的数据结构,虽然栈更为简单一些。在具体的C/C++编程框架中,这两个概念并不是并行的。对底层机器代码的研究可以揭示,栈是机器系统提供的数据结构,而堆则是C/C++函数库提供的。

具体地说,现代计算机(串行执行机制),都直接在代码底层支持栈的数据结构。这体现在,有专门的寄存器指向栈所在的地址,有专门的机器指令完成数据入栈出栈的操作。这种机制的特点是效率高,支持的数据有限,一般是整数,指针,浮点数等系统直接支持的数据类型,并不直接支持其他的数据结构。因为栈的这种特点,对栈的使用在程序中是非常频繁的。对子程序的调用就是直接利用栈完成的。机器的call指令里隐含了把返回地址推入栈,然后跳转至子程序地址的操作,而子程序中的ret指令则隐含从堆栈中弹出返回地址并跳转之的操作。C/C++中的自动变量是直接利用栈的例子,这也就是为什么当函数返回时,该函数的自动变量自动失效的原因。

和栈不同,堆的数据结构并不是由系统(无论是机器系统还是操作系统)支持的,而是由函数库提供的。基本的malloc/realloc/free函数维护了一套内部的堆数据结构。当程序使用这些函数去获得新的内存空间时,这套函数首先试图从内部堆中寻找可用的内存空间,如果没有可以使用的内存空间,则试图利用系统调用来动态增加程序数据段的内存大小,新分配得到的空间首先被组织进内部堆中去,然后再以适当的形式返回给调用者。当程序释放分配的内存空间时,这片内存空间被返回内部堆结构中,可能会被适当的处理(比如和其他空闲空间合并成更大的空闲空间),以更适合下一次内存分配申请。这套复杂的分配机制实际上相当于一个内存分配的缓冲池(Cache),使用这套机制有如下若干原因:

1. 系统调用可能不支持任意大小的内存分配。有些系统的系统调用只支持固定大小及其倍数的内存请求(按页分配);这样的话对于大量的小内存分类来说会造成浪费。

2. 系统调用申请内存可能是代价昂贵的。系统调用可能涉及用户态和核心态的转换。

3. 没有管理的内存分配在大量复杂内存的分配释放操作下很容易造成内存碎片。

堆和栈的对比

从以上知识可知,栈是系统提供的功能,特点是快速高效,缺点是有限制,数据不灵活;而栈是函数库提供的功能,特点是灵活方便,数据适应面广泛,但是效率有一定降低。栈是系统数据结构,对于进程/线程是唯一的;堆是函数库内部数据结构,不一定唯一。不同堆分配的内存无法互相操作。栈空间分静态分配和动态分配两种。静态分配是编译器完成的,比如自动变量(auto)的分配。动态分配由alloca函数完成。栈的动态分配无需释放(是自动的),也就没有释放函数。为可移植的程序起见,栈的动态分配操作是不被鼓励的!堆空间的分配总是动态的,虽然程序结束时所有的数据空间都会被释放回系统,但是精确的申请内存/释放内存匹配是良好程序的基本要素。





进程在内存中的影像.  
      我们假设现在有一个程序, 它的函数调用顺序如下.  
      main(...) -> func_1(...) -> func_2(...) -> func_3(...)  
      即: 主函数main调用函数func_1; 函数func_1调用函数func_2; 函数func_2调用函数func_3  

      当程序被操作系统调入内存运行, 其相对应的进程在内存中的影像如下图所示.  

        (内存高址)  
        +--------------------------------------+  
        |             ......                   |  ... 省略了一些我们不需要关心的区  
        +--------------------------------------+  
        |  env strings (环境变量字串)          | \  
        +--------------------------------------+  \  
        |  argv strings (命令行字串)           |   \  
        +--------------------------------------+    \  
        |  env pointers (环境变量指针)         |    SHELL的环境变量和命令行参数保存区  
        +--------------------------------------+    /  
        |  argv pointers (命令行参数指针)      |   /  
        +--------------------------------------+  /  
        |  argc (命令行参数个数)               | /  
        +--------------------------------------+  
        |            main 函数的栈帧           | \  
        +--------------------------------------+  \  
        |            func_1 函数的栈帧         |   \  
        +--------------------------------------+    \  
        |            func_2 函数的栈帧         |     \  
        +--------------------------------------+      \  
        |            func_3 函数的栈帧         |      Stack (栈)  
        +......................................+      /  
        |                                      |     /  
                      ......                        /  
        |                                      |   /  
        +......................................+  /  
        |            Heap (堆)                 | /  
        +--------------------------------------+  
        |        Uninitialised (BSS) data      |  非初始化数据(BSS)区  
        +--------------------------------------+  
        |        Initialised data              |  初始化数据区  
        +--------------------------------------+  
        |        Text                          |  文本区  
        +--------------------------------------+  
        (内存低址)  

        这里需要说明的是:  
        i)   随着函数调用层数的增加, 函数栈帧是一块块地向内存低地址方向延伸的.  
             随着进程中函数调用层数的减少, 即各函数调用的返回, 栈帧会一块块地  
             被遗弃而向内存的高址方向回缩.  
             各函数的栈帧大小随着函数的性质的不同而不等, 由函数的局部变量的数目决定.  
        ii)  进程对内存的动态申请是发生在Heap(堆)里的. 也就是说, 随着系统动态分  
             配给进程的内存数量的增加, Heap(堆)有可能向高址或低址延伸, 依赖于不  
             同CPU的实现. 但一般来说是向内存的高地址方向增长的.  
        iii) 在BSS数据或者Stack(栈)的增长耗尽了系统分配给进程的自由内存的情况下,  
             进程将会被阻塞, 重新被操作系统用更大的内存模块来调度运行.  
             (虽然和exploit没有关系, 但是知道一下还是有好处的)  
        iv)  函数的栈帧里包含了函数的参数(至于被调用函数的参数是放在调用函数的栈  
             帧还是被调用函数栈帧, 则依赖于不同系统的实现),  
             它的局部变量以及恢复调用该函数的函数的栈帧(也就是前一个栈帧)所需要的  
             数据, 其中包含了调用函数的下一条执行指令的地址.  
        v)   非初始化数据(BSS)区用于存放程序的静态变量, 这部分内存都是被初始化为零的.  
             初始化数据区用于存放可执行文件里的初始化数据.  
             这两个区统称为数据区.  
        vi)  Text(文本区)是个只读区, 任何尝试对该区的写操作会导致段违法出错. 文本区  
             是被多个运行该可执行文件的进程所共享的. 文本区存放了程序的代码.  

    2) 函数的栈帧.  
       函数调用时所建立的栈帧包含了下面的信息:  
       i)   函数的返回地址. 返回地址是存放在调用函数的栈帧还是被调用函数的栈帧里,  
            取决于不同系统的实现.  
       ii)  调用函数的栈帧信息, 即栈顶和栈底.  
       iii) 为函数的局部变量分配的空间  
       iv)  为被调用函数的参数分配的空间--取决于不同系统的实现.

posted on 2009-05-16 23:52 狂烂球 阅读(2509) 评论(4)  编辑 收藏 引用 所属分类: C++

评论

# re: 堆和栈(转) 2009-05-17 12:22 skyscribe

解释的很清楚哦,不错!

补充一点:
函数的参数可能是在寄存器上而不是在栈上。
gcc那个著名的优化选项-fomit-frame-pointer还可以把fp指针占用的寄存器空间给省略掉从而带来性能的提升。  回复  更多评论   

# re: 堆和栈(转) 2009-05-17 12:28 maomi

niubi, 学习了. thanks  回复  更多评论   

# re: 堆和栈(转)[未登录] 2009-05-18 00:17 zj

引用:堆的数据结构并不是由系统(无论是机器系统还是操作系统)支持的,而是由函数库提供的.
----------------------------------
应该是有系统提供的,操作系统几大组件,内存管理,文件管理。
不是系统提供内存管理系统调用,库函数只是空中楼阁,必定库函数也是封装了系统调用  回复  更多评论   

# re: 堆和栈(转) 2009-05-18 11:20 yb

@zj
没错,malloc,free之类的函数需要系统支持,这就是为什么不同的平台移植时往往要重写malloc, free。  回复  更多评论   


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理