内存、栈、堆

标签：OS

内存、栈、堆的一点小总结

• 程序的内存布局
  【前言】在32位系统中，大家可能认为我们可以用一个32位的指针访问任意内存地址。如下：

    int *p = (int *)0x12345678;
  ++*p;

    但事实上用户可以直接读取的内存大小是达不到4GB的。大多数操作系统都会将其中的一部分分配给内核使用，应用程序是无法直接访问这一段内存的，这部分被称为内核空间。Linux默认将高地址的1GB空间分配给内核；win默认下将高地址的2GB分配给内核，但是也可以人为配置成1GB。（前面已介绍）
    但是处理上述的内核空间之外的用户空间中也有一些特殊的空间有特殊的用处，而应用程序能用的内存空间是如下的几个“默认区域”：

  • 栈
      用于维护函数调用的上下文，离开了栈，函数的调用就没办法实现了。栈通常在用户更高的地址空间处分配，通常有数兆字节的大小。

  • 堆
      堆用来容纳应用程序动态分配的内存区域，当程序使用malloc或new的时候就是得到来自堆中的内存。堆统称在栈的下方（低地址方向，但是，不是紧邻的）。堆一般比栈要更大一点，一般会达到几十甚至是数百兆字节。

  • 可执行文件映像
      顾名思义，这里存储着可执行文件在内存里的映像。装载器在装载的时候会将可执行文件读取或者映射到这里。

  • 保留区
      是对内存中受到保护而禁止访问的内存区域的总称。这个区域大家应该都比较熟悉，比如，大多数操作系统中，极小的地址区域都是不允许访问的，如NULL。
      相关的内存布局如下：
    
      上图中还有一个区域，“动态链接库映射区”，这个区域用于映射装载的动态链接库。比如，如果可执行文件依赖于其他的共享库，那么系统就会为他从0x40000000开始的地址分配相应的空间，并将该共享库载入到该空间（动态链接共享对象的内存地址分配）。
      【注意】栈向低地址增长；堆向高地址增长。当栈或者堆的现有大小不够用的时候，它将按照图中的增长方向扩大自身的尺寸，直到预留的空间（unused）被用完。
      【补充】在Linux或者是win内存中，有些地址是始终不能读写的，例如0地址，当指针指向这些地址的时候，就会出现“段错误（segment fault）”。造成这种情况的两种最普遍的原因：
      1.程序员将指针初始化为NULL，但是没有赋予合理的初值就开始使用。
      2.程序员没有初始化栈上的指针，指针的值一般是随机数，之后就开始使用该指针。

• 栈

  • 在经典的操作系统中，栈总是向下（低地址）增长的。

  • “堆栈帧”或“活动记录”
      栈保存一个函数调用所需要的维护信息，常被称为堆栈帧或者是活动记录，堆栈帧一般包括：
    （1）函数的返回地址和参数；
    （2）临时变量：包括函数的非静态局部变量以及编译器生成的其他局部变量；
    （3）保存的上下文：包括在函数调用前后保持不变的寄存器。

  • 栈中有两个重要的寄存器：esp和ebp
    （1）esp
      该寄存器标明栈顶，在栈上压入数据会导致esp减小，反之esp增大。再者，减小esp的值等于在栈上开辟空间，而增大esp的值等效于在栈上回收空间。
      esp不仅仅指向栈的顶部，同时也就意味着指向当前整个函数活动记录的顶部（见下图）。
    （2）ebp
      ebp寄存器指向函数活动记录的一个固定位置。ebp寄存器又被称为帧指针。如下：
    
      ebp具体的固定位置如上图所示。如图，（注意栈向低地址增长）ebp之前是该函数的返回地址，再之前是压入栈中的参数。而ebp指向的数据是调用该函数之前的ebp的值，保存旧的ebp的值的原因是，函数返回时，可以通过读取该值恢复到调用之前的ebp的值（回到之前指向的位置）。

• 调用惯例

  • 概念
      函数的调用方和被调用方对于函数如何调用需要有一个明确的约定（比如参数入栈的顺序等）。这样的约定就被称为调用惯例。

  • 调用惯例一般包括：
    （1）函数参数的传递顺序和方式。可以有很多方式，最常见的就是通过栈传递，参数入栈的顺序要事先由调用惯例确定；有些调用惯例为了提升性能还会选择用寄存器进行参数传递。
    （2）栈的维护方式。参数入栈后，函数体会被调用，参数使用的时候会被弹出的，可以是函数调用方进行参数的弹出或者是由函数本身进行参数的弹出。
    （3）名字修饰的策略。C语言实际上存在多种调用惯例，一般默认的（没有显示指定的情况下）是cdecl（不同的编辑器写法有别）：
    int _cdecl foo(int n, float m);

  • foo函数布局
    具体如下图所示：
    
      当foo函数返回的时候，程序会首先使用pop恢复保存在栈中的寄存器，然后从栈里取出返回地址，并返回至调用方，调用方再调整esp将堆栈恢复。下面给出一个具体的多级调用栈的布局：
    
    

• 函数返回值传递

  • 如果返回值的可以用4个字节表达，我们经常讲返回值保存在eax寄存器里面。返回后，函数的调用方将读取eax寄存器中的值即可。
  • 对于返回4~8字节对象的情况，几乎所有的调用惯例都采用eax和edx联合返回的方式进行的。

  • 超过8字节的返回值（大致思路）：
    先看一段代码：

    
    #include<stdio.h>
    
    typedef struct big_thing
    {
    　　char buf[128];
    }big_thing;
    
    big_thing return_test()
    {
    　　big_thing b;
    　　b.buf[0] = 0;
    　　return b;
    }
    
    int main()
    {
    　　big_thing n = return_test();
    　　return 0;
    }

  • 大致解读

    • 首先main函数在栈上额外开辟一片空间，并将这块空间的一部分作为传递返回值的临时对象，这里称为temp；
    • 将temp对象的地址作为隐藏参数传递给return_test函数；
    • return_test函数将数据拷贝给temp对象，并将temp的地址用eax传出；
    • return_test函数返回后，main函数将eax指向的temp对象的内容拷贝给了n。

  返回值传递流程如下：
  
  【注意】结果返回值对象会被拷贝两次，所以不到万不得已不要返回大尺寸的对象。

• 堆

  • 简介
      堆是一块巨大的内存空间，常常占用整个虚拟空间的绝大部分。在这片空间里，程序可以请求一块连续内存，并自由使用，这块内存在程序主动放弃之前都会一直保存。

  • malloc的实现
      不能采用系统调用的方式，开销较大；较好的做法是程序向操作系统申请一块适合大小的堆空间，然后由程序自己管理这块空间，具体来讲，管理着堆空间分配的往往是程序的运行库。
      运行库相当于向操作系统”批发“了一块较大的堆空间，之后”零售“给程序使用，如全部售完或者程序有大量的内存需求，再根据实际情况向操作系统“进货”。

  • Linux进程堆管理
      提供两种堆分配方式，即两个系统调用：brk()系统调用；mmap()系统调用。

    • brk()
      该函数的C语言声明如下：
      int brk(void *end_data_segment)
        该函数申请堆的方式是：设置进程的数据段的结束地址，即可以扩大或者是缩小数据段（Linux下数据段和BSS段合称数据段）。如果我们将数据段的结束地址向高地质移动（数据段变小），那么扩大的那部分空间常常用来作为堆空间。

    • mmap()
        该函数的作用是向操作系统申请一段虚拟空间，这块虚拟地址空间可以映射到某个文件，当它不进行映射的时候，我么又称这块空间为匿名空间，匿名空间就可以用来作为堆空间。
        glibc的malloc函数是这样处理用户的空间请求的：
        （1）对于小于128kb的请求，它会在现有的堆空间里面，按照堆空间分配算法为其分配一块地址并返回；
        （2）对于大于128kb的请求，它会使用mmap()函数为它分配一块匿名空间。使用mmap()函数实现malloc的代码如下：

      void *malloc(size_t  nbytes)
      {
      　   void *ret = mmap(0,nbytes,PROT_READ | PROT_WRTIE, MAP_PRIVATE | MAP_ANONYMOUS,0,0);
      　   if(ret == MAP_FAILED)
      　　      return 0;
      　   return ret;
      }

    【需要注意的是】mmap()函数和VirtualAloc()类似，他们都是虚拟空间的申请函数，它们申请的空间的实际地址和大小必须是系统页的大小的整数倍。

• 堆分配算法

  • 空闲链表法

    • 简介
        该方法将堆中的各个空闲块按照链表的方式连接起来，当用户请求一块空间的时候，可以遍历整个链表，直到找到合适大小的块并将它拆分，当用户释放空间的时候将他合并到空闲链表中。

    • 结构
        在堆里的每一个空闲空间的开头（或结尾）有一个头（header），头结构里面有两个指针prev和next，如下图：
      

    • 操作过程
        首先在空闲链表查找足够容纳请求大小的一个空闲块，然后将这个块分为两部分，一部分是程序请求的空间，另一部分是剩余的空闲空间。
      【注意】当采用空闲链表的方式时需要释放空闲空间的时候，有一个简单的解决方法：当用户请求k个字节的时候，我们实际分配k+4个字节，这四个字节用来存储该分配的大小。

  • 位图

    • 核心思想
        将整个堆划分为大量的大小相等的“块”。当用户请求的时候，总是分配整数个块的空间给用户。分配的块中，第一个块我们称为已分配区域的头（Head），其余的称为已分配区域的主体（Body）。我们使用整数数组来记录块的使用情况，由于每个块只有头/主体/空闲三种状态，因此可以使用两个bit位来表示一个块。

    • 举例
        假设堆的大小为1MB，那么我们让一个块大小为128字节，则总的块数：8k/(32/2)=512个int来存储，。这有512个int的数组就是一个位图，其中每两个bit位代表一个块。

    • 优点
      （1）速度快。由于整个堆的空闲信息都存储在一个数组内，因此访问该数据的时候cache容易命中。
      （2）稳定性好。为避免用户越界读写破坏数据，我们只需简单地备份一下位图即可。而且即使部分数据被破坏，也不会导致整个堆无法工作。
      （3）块不需要额外信息，易于管理

    • 缺点
      （1）分配内存的时候容易产生碎片。例如，分配300字节时，实际上分配了3个块即384个字节，这样就浪费了84个字节（128*3，按照整数个块进行分配）。
      （2）如果堆很大但是设定的块很小（这样可以减少碎片的数量），但同时也会导致位图的规模很大，可能会失去cache命中率高的优势，同时也会浪费一定的空间。针对这种情况，我们可以使用多级位图（不再介绍）。

  • 对象池

    • 使用情况
        被分配的大小是较为固定的几个值。

    • 大致思路
        如果每次分配的空间大小都一样，那么就可以按照这个每次请求分配的大小作为一个单位，把整个堆空间划分为大量的小块，每次请求的时候只需要找到一个小块就可以了。

    • 管理
        对象池的管理方法可以是空闲链表或者是位图。

  • 实际应用
      实际的应用中，堆的分配算法其实是采取多种算法的复合。