Home > 程序/算法 > HeapAlloc内部算法

HeapAlloc内部算法

December 23rd, 2005 Leave a comment Go to comments

大家都知道在VC中使用new操作符时(如果没有重载的话),其内部实际上调用了标准的malloc,而根据工程设置中选择的运行库的不同(是否多线程,是否调试,是否Dll等)调用了不同的malloc版本,多线程版malloc内部使用了Win32的关键区,而调试版会额外多申请一些内存用来保存调试信息,这些直接看VC附带的crt源码就可以看到。所有版本的malloc的共同点是最后都调用了Win32的API函数HeapAlloc。

关于HeapAlloc的算法记得很多年前一个后来去了微软的大牛给我讲过,但当时我还是个菜鸟(现在没那么菜了)没记住,于是决定自己研究一下。方法是用HeapCreate自己建一个堆,用HeapAlloc从里面申请内存,同时用VC的内存查看盯着heap所在内存区看,观察Alloc和Free的时候内存都发生了哪些变化。其间从网上找到的这篇文档帮助比较大,节省了不少时间。

Heap头的结构基本没搞明白(也不需要太关心),只知道在偏移地址0x28的位置记录的是剩余空间大小(单位是8字节),然后从0x178开始是一个free list 表(数组),一共128个单元,每个单元的数组下标代表这个链上每个节点(free chunk)是多大(包括chunk header所占空间,单位是8字节)。所以记录的是0~1024(128×8)大小的free chunk链,每个单元是一个循环链表,Flink和Plink指针共占用8个字节。第0号单元比较特殊,它维护的是大小>=1k的chunk的list,按chunk大小升序排列。下图摘自前面提到的文档。

freelist

每个chunk,包括free chunk和已分配出去的chunk,都会带有一个8字节的header结构,如下图

chunkheader

chunk header之后就是chunk的用户数据区,用户数据区之后紧跟了8个值总是为0xab的字节,然后会有0~7个不用的字节用于8字节对齐,之后是8个总是为0的字节。用户数据区后面的这16~23字节就我观察到的始终没有变过,所以我也不知道是做什么用的。注意这里提到的size单位都是8字节,另外Previous chunk size不是指在free list中的previous,而是物理内存的前面一块的大小,这个值是在chunk回收时会用到,因为可能需要和前一个free chunk粘合,下面会提到。Unused bytes就是这个chunk中除了用户数据之外的字节数(就是header的8字节加上用户数据之后的16~23个字节)

如果这个chunk是free chunk(就是还没有被分配或者已经回收的chunk),在chunk header之后,也就是用户数据区中的前8个字节用来保存它在free list中的Next指针和Prev指针。之所以使用用户数据区,是因为当chunk被分配出去以后就已经不在free list中了,当然就无需再保存这两个指针。而且,从前面说过的chunk结构来看是一定能容下这两个指针的。

好了,数据结构清楚了,开始说算法。

先说Alloc算法:

根据用户提交的申请内存字节数,考虑chunk header等结构本身的内存开销,决定这个chunk需要多大size,把这个size除以8就得到在free list表里对应的下标(超过127就是0),从这个下标对应的free list开始往下标增大的方向找(超过127回到0,顺着0号free list找)也就是在所有free chunk中找到第一个size大等于要求值的chunk,如果找到大小正合适的chunk,那很好,把chunk从list中摘出来,把chunk header的flag字节的busy位置上,然后返回该chunk用户数据区的首地址,搞定。

如果一个都没找到就返回空指针(如果HeapAlloc给的option参数要求抛异常则抛异常)。

如果找到的free chunk比要求的size大,先把它从free list中摘出,然后把这个chunk分割成两部分,前面size那么大的形成一个chunk,剩下的部分形成一个碎片chunk(因为都是8字节对齐的,所以剩下的空间至少够一个chunk header)。前一个chunk当然就是分配给用户的chunk了,把header中的Self size设置一下,previous chunk size不会变。碎片chunk需要加回free list表,找到它所属的相应大小的free list。这里要注意的是碎片的self size和previous chunk size(就是给用户的chunk 的size)都要设置,并且碎片后面一个chunk(除非后面没了)的previous chunk size要设成碎片chunk的大小。最后把用户要求的chunk设置busy后返回数据区指针。

Free的算法。

Free的算法比较特殊的是内存的粘合,要释放一个chunk时,看看前后的chunk(根据自己的size和preivious chunk size很容易找到相应的chunk header)是不是free(判busy位)的,如果是则把它(们)和当前chunk粘合,具体粘合算法就不说了,无非是把前后的self size和previous chunk size改改。注意粘合前要先把被粘合的chunk从free list中摘除。我想就是这个粘合导致的free chunk从free list的摘除操作才导致free list需要双链结构(单链的话得从链头开始找太慢),如果象一般内存池那样不需要粘合的话,free list只要单链就够了,因为总是从链头添加和删除节点。最后粘合(或没有粘合)后得到的chunk根据大小被重新加入free list。

其它

一个heap刚被创建时,只有0号下标(也就是> 1K)的free list中有一个free chunk,包含了这个堆里所有可以被分配的内存。

开始提到的那个文档中提到一个 lookaside表,大致就是可以对于每种大小的free chunk都缓存几个在lookaside表中(而不会被粘合)这样能一定程度上加快速度,但是就我观察到的似乎没有用到这个算法(或者和堆的创建参数或者堆的大小有关?没有仔细研究)

下标为1,2,3的free list实际上永远不会被直接分配出去,因为一个有效(包含用户数据)的chunk至少会占用32个字节(size为4),这几个list保存的都是等待被粘合的碎片

以上是研究了两个晚上的结果,好多细节都没有深究。

Categories: 程序/算法 Tags: ,
  1. SiyangLiu
    May 30th, 2011 at 22:00 | #1

    不知道和DLMalloc区别大吗?
    如果使用lookaside的话,记得MSDN的说法是必须是一个单线程的堆。是有一个参数的。

    你也不上msn了,有一个技术问题问你:
    我粗略浏览了一下unreal2的代码,发现他的场景管理都是BSP。而且我搜索了一些文档,好像没看到有人说别的管理方式。但是U2根据官方文档说,也是支持室外场景的。如果是室外场景的话,大概意思是BSP+一个叫做什么区域表的概念。我的理解可能是分成几个区域,然后每个区域自己的BSP?又或者是BSP的变种。。总之不太清楚。

    问题就是室外场景,是不是使用四叉树会更好一些?至少我一直是这么理解的。。。。
    而且使用四叉树貌似可以动态加载?

    我的问题就是,u2都是大牛们做的,为啥他们只有BSP一种场景管理机制,是不是BSP也不一定比四叉树在室外场景管理上弱?还是u2就是为室内场景所设计,且要求各种碰撞,如果要做也只能做成八叉树,所以他们懒得做了?

    另外BSP在数据管理上优势强吗?譬如我想知道周围都有谁,因为网游可能更关心附近都有谁。
    改天上msn啊,我没有gtalk。。。。

  1. No trackbacks yet.

 

Spam Protection by WP-SpamFree