注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

Tsecer的回音岛

Tsecer的博客

 
 
 

日志

 
 

从一次内存异常看常见动态内存管理方法  

2016-07-29 20:22:43|  分类: Glibc分析 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
一、问题的起因
问题的原型是对某一个数组,根据特定情况要修改数组元素的概率,然后根据概率从这组修改之后的数组中选择出一个元素返回给用户。这个逻辑并不复杂,特别是在使用C++标准库的vector情况下。前面描述了问题的原始模型,但是为了验证效果,这里使用更为简单的代码来模拟。下面的代码的运行结果只需要注意到一个现象,就是调用处使用函数刚返回的元素开始若干自己被修改,而且只发生在返回vector第一个元素的时候才出现这个问题。
tsecer@harry: cat vecelem.cpp 
#include <stdio.h>
#include <stdlib.h>
#include <sys/types.h>
#include <unistd.h>
#include <vector>

using namespace std;

#define  VSIZE 10
#define  ESIZE 100
typedef struct 
{
int arr[ESIZE];
} ELEM;

struct container
{
vector<ELEM> m_vecCont;
container()
{
        for (int i = 0; i < VSIZE; i++)
        {
                m_vecCont.push_back((ELEM){0});
        }
}
ELEM * GetElem(int &irand)
{
        vector<ELEM> vecCopy = m_vecCont;
        return & vecCopy[irand = rand() % VSIZE];
}
};

container g_cont;
int main()
{
        srand(getpid());
        for (int i = 0; i < VSIZE; i++)
        {
int iindex;
                ELEM *pe = g_cont.GetElem(iindex);
                if (pe->arr[0] != 0)
                {
                        printf("except index %d\n", iindex);
for (void ** paddr = (void**)&pe->arr; *paddr != NULL; paddr++)
{
printf("%p\t", *paddr);
}
printf("\n");
                        return -1;
                }
else
{
printf("index %d\n", iindex);
}
        }
        return 0;
}

tsecer@harry: g++ vecelem.cpp 
tsecer@harry: ./a.out 
index 5
index 1
except index 0
0x3367db87b8 0x3367db87b8
tsecer@harry: 
二、直观原因
其实这个代码写的的确有问题,一个明显的错误就是不应该返回局部变量给调用函数。而当时这样实现的原因主要有两个:一方面是由于对于给定的需求,这样是最直观的实现方法,写代码的时候并没有考虑太多;另一方面,返回的元素地址是vector对象从堆中动态分配的,直观上看单线程环境下这个动态内存在函数返回之后马上使用还不至于被再次分配出去。
如果对动态内存管理的基本原理稍有了解的话,直观上就可以感觉到造成这种现象的原因是动态内存管理模块写入了一些控制结构。对于动态内存的管理是一个基本的问题,在C语言出现之时就有个该问题。在《计算机程序设计艺术》的第一卷描述了动态内存管理的基本思路,大部分计算机教科书也会有提及该问题。从用户的角度来看,动态内存就是需要实现分配和释放两个基本功能,为了实现这些功能,动态库就需要添加一些管理结构。这些管理结构和用户内存的关系和inode与文件内容的关系一样,只是每个文件内容和它对应的inode在磁盘上的物理位置是隔离的,所有inode在磁盘格式化的时候就已经确定,并且放在专门的inode区(新的ext系列文件系统中的inode又按照不同的group聚集在一起),它们和用户可到的具体文件内容使用的扇区并不相邻。
其实除了内存的分配和释放之外,动态内存管理还有一个重要但是对用户不可见的功能——小内存的合并。一个长时间运行的程序,可能不断的分配/释放不同大小的内存块,如果不对用户释放的相邻内存块进行合并,那么程序运行一段时间之后可能动态内存已经严重碎片化,进而导致总空闲内存足够多但是无法分配大块内存。
现在直观上考虑一个最为朴素的动态内存管理结构:为了管理所有位置不连续的空闲内存块,就需要使用链表将它们管理起来。为了便于快速找到最近接用户申请大小的空间内存块,理想的方法是在动态内存被归还的时候,按照归还内存大小将它插入空闲内存链表中,这样在应用申请新的内存大小时就可以遍历该链表,找到第一个满足申请大小的空闲内存块,从链表上摘除,并返回给用户(当然,如果第一个空闲内存块比申请空间大,可能还要把剩余内存再次插入空闲列表)。
在用户释放动态内存时,需要知道释放空间的大小,以便将它插入空闲队列的合适位置(按照空间大小的顺序排序的明显好处就是分配时便于找到最佳适应大小,缺点就是排序本身可能会比较耗时)。
为了实现连续小内存的合并,在释放内存时还要知道被释放内存前后是否有空闲内存块,如果有的话进行空闲内存的合并,从而组成更大空闲内存块,以消除可能出现的内存碎片。
三、glibc的管理结构
glibc中对于动态内存的管理相关内容主要放在glibc-2.11\malloc\malloc.c文件中,该文件对于具体实现的相关数据结构在代码中有比较完善的注释,下面是它描述的主要结构
    An allocated chunk looks like this:


    chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |             Size of previous chunk, if allocated            | |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |             Size of chunk, in bytes                       |M|P|
      mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |             User data starts here...                          .
   .                                                               .
   .             (malloc_usable_size() bytes)                      .
   .                                                               |
nextchunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |             Size of chunk                                     |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
……
    Free chunks are stored in circular doubly-linked lists, and look like this:

    chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |             Size of previous chunk                            |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    `head:' |             Size of chunk, in bytes                         |P|
      mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |             Forward pointer to next chunk in list             |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |             Back pointer to previous chunk in list            |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |             Unused space (may be 0 bytes long)                .
   .                                                               .
   .                                                               |
nextchunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    `foot:' |             Size of chunk, in bytes                           |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
从这个结构上看,与前面所描述的朴素实现相比,多出了不少字段,其中有一些陌生的字段就是为了完成空闲内存块的合并。
四、合并时要考虑的问题
在释放内存合并时,不仅要考虑和该释放内存之前(逻辑地址)紧邻内存块的合并,还要考虑和之后紧邻内存块的合并,而这又要依赖于首先要知道自己(前后)紧邻内存块的基本信息:是否空闲,大小多少。对于前向内存,在"Size of chunk, in bytes                       |M|P|"结构的最低bit(P)表示了前向内存是否空闲,如果空闲,那么"Size of previous chunk, if allocated "表示了前向内存的大小,这样我们就解决了前向内存是否被空闲以及空闲大小的问题。
那么如何判断后向内存是否空闲呢?从上面的结构看,并没有一个类似的P标志位来表示后向内存是否空闲,虽然可以通过自己的地址+自己的大小来知道后向块的其实位置。从glibc的实现来看,解决这个问题的方法是通过查看下一个的下一个的P字段来判断。
五、Size of previous chunk与Size of chunk, in bytes 
从glibc自带的注释中对"Free chunks"的描述看,head和foot处的值相同,都写入了该chunk的大小,这个做法的意义是什么?其实head处的size是供该chunk使用的,它用来找到自己后续chuck的位置;而foot处的size是供后续chuck使用,用来找到前向chunk的位置。或者说foot处的size对于该chunk来说是只写的,而对于后续chuck来说是只读的,虽然foot处size本身的空间是后续chunk申请并拥有的。
六、glibc的优化
glibc动态内存的管理当然不是使用前面所说的有序单链表管理所有空间的做法(因为效率太低),而是进行了优化。比较重要的优化是使用了fastbin、normal bin、arena。
fastbin使用单项链表保存所有小于global_max_fast(缺省值为DEFAULT_MXFAST=(64 * SIZE_SZ / 4))的空闲块,这些列表中块的大小粒度为16字节(64位系统下),这意味着16——31字节的空闲块放在同一个fastbin中,32—47放入同一bin队列中,依次类推,直到(64 * SIZE_SZ / 4)。这样实现虽然空间可能有些浪费(最多15个字节),但是对于通常的小块内存分配会非常快,只需要从队列头中取出第一个元素即可,因为这个队列使用的是单项列表。
normal bin中的small并同样是以定长16字节为单位向上取整放入相同bin中,large则以更大的粒度划分bin,例如粒度为64、512、4096等,只是粒度越大,这些粒度的bin越少。例如粒度为64的bin为48个,粒度为512的20个等。
arena主要优化在多线程场景下。为了减少多线程同时malloc对于锁竞争导致的等待,希望不同的线程能够使用不同的arena(从而在获得该arena锁时不会产生等待),当然理想情况下就是每个线程都使用线程私有的arena结构,这样甚至可以完全不使用锁功能。但是这样的话在一些线程较多的应用中,arena的数目就会相应地非常多。所以这个地方再次进行了折中,对于一个应用中总共的arena数量进行了限制,组成一个thread和erena为nXm的关系,其中n是进程线程数,m是系统中cpu core的数量,这个值由函数__get_nprocs通过读取"/proc/stat"或者"/proc/cpuinfo"文件获得。
七、其它一些动态内存管理实现的对比
内核中对于动态内存的管理通常使用的是两种典型的管理方法,一种是定长结构也经典的slab分配器,一种是变长结构的slob分配器。 内核配置项中对于该配置项的说明为linux-2.6.17\init\Kconfig。也就是默认系统使用的是slab分配方法,注视中说明,SLOB相对更加简单,空间利用率更高,但是扩展性差,并且可能更容易出现内存碎片。感觉这个其实是定长分配和变长分配的典型特征注释。
1、slab的关键实现
这个选项只有在配置了EMBEDDED的时候才在内核配置时对用户可见
config SLAB
default y
bool "Use full SLAB allocator" if EMBEDDED
help
 Disabling this replaces the advanced SLAB allocator and
 kmalloc support with the drastically simpler SLOB allocator.
 SLOB is more space efficient but does not scale well and is
 more susceptible to fragmentation.
对于slab内存分配来说,关键的管理结构如下
struct array_cache {
unsigned int avail;
……
spinlock_t lock;
void *entry[0]; /*
* Must have this definition in here for the proper
* alignment of array_cache. Also simplifies accessing
* the entries.
* [0] is for gcc 2.95. It should really be [].
*/
}          
其中avail表示了可用空闲节点的数量,而entry则表示了存储了这些节点的首地址,也就是说如果avail的值为10,那么此时entry的前10个元素空闲,并且每个都指向一个空闲的可用节点地址。这样在分配和释放的时候效率都很高,例如分配的时候objp = ac->entry[--ac->avail]即可完成,而释放的时候alien->entry[alien->avail++] = objp;即可(当然这里的说明省略了锁,avail为零等细节)。
2、slob的关键实现
slob的实现代码注释中就说明了这个实现更类似于传统的C语言堆分配器("The core of SLOB is a traditional K&R style heap allocator"),也就是之前讨论的朴素实现方法,甚至更加简单。这个空闲链表是单向链表,并且不是按照空闲块的大小来排序,而是按照块的起始地址排序,这样作就可以在不使用额外省数据结构的情况下来完成前后空闲块的合并。事实上,一个这样的控制结构比C库的管理结构还要简单,在32系统下大小为8字节。
struct slob_block {
int units;
struct slob_block *next;
};
由于内存块按照起始地址排序,所以判断下一个块是否空闲的方法就是判断slob_block链表中下一个block的起始位置是否等于自己的起始位置加上units,对应代码中slob_free函数内if (b + b->units == cur->next)判断。这个slob.c的实现代码量较少,毫无意外,执行效率和空间利用率相对较低。
3、inode的分配
其实ext系列文件系统的inode分配也可以看作是定长分配的一种方法,它的实现更类似于slab的方法,因为每个inode节点在磁盘上占用的空间是相同的。但是inode的空闲列表的管理结构更加的紧密,关键的空闲节点(和非空闲)节点是通过位图来表示,这样理论上说一个空闲节点和非空闲节点使用一个bit就可以表示(而不是slab中使用的一个指针)。但是查找空闲节点的时候就需要从位图开始扫描,直到遇到一个空闲的位图。这样对于一个空闲节点非产少的系统来说,可能需要扫描很久才能找到一个空闲inode。为了解决这个问题,一个文件系统通常内部再区分了不同的group结构。本质上看,也是一种分治的思想。
八、回到开始的例子
现在看来,开始的问题就简单很多了。当内存被释放之后,此时glibc通过修改释放内存中的fd(forward)和bk(backward)指针来将该内存来添加到空闲内存链表中。对于vector结构来说,它真正存储数据的数组默认也是通过glibc动态内存管理,所以在函数返回时,vector局部变量的析构函数将动态内存归还给libc,libc在释放内存中存储了两个指针。这里最简单的教训就是当动态内存释放之后,它不仅不可写,也不再可读。

  评论这张
 
阅读(50)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017