恐怖C++之三

Malloc, Free. "I know what you did last summer".

int *p = (int *)malloc(sizeof(int));
...
free(p);

几乎每天都在写这样的代码，从堆中分配一块内存，使用后释放。可是 malloc 如何获得空闲内存， free 又如何知道该释放多大的内存？一定有东西记录了这些，但从来没有看到有关 malloc 和 free 实现细节的文章（不过也没有去专门找过，呵呵），只记得在 Lippman 和 Meyer 的书上都看到过 new 会在分配的内存的前面加入一个“参量”用来为 delete 提供信息，怀疑那个参量就是 malloc 生成的，没办法，找代码看看吧。

手头上相关的代码就只有 Microsoft CRT Source （随 VC6 提供，选装），其中的代码主要供程序员怀疑 CRT 时调试代码，大多数都是 debug 版的，不过对于上面的问题已经足够了。

堆操作的代码（release版）基本上集中在 HEAP.H 及 HEAP*.C 中。malloc 和 free 的 Release 版在 MALLOC.C 和 FREE.C 中实现。

首先来看看 HEAP.H 中的两个重要的数据结构：

/*
 * Heap block descriptor
 */
struct _block_descriptor {
    struct _block_descriptor *pnextdesc;    /* ptr to next descriptor */
    void *pblock;                           /* ptr to memory block */
};
#define _BLKDESC    struct _block_descriptor
#define _PBLKDESC   struct _block_descriptor *

/*
 * Heap descriptor
 */
struct _heap_desc_ {
    _PBLKDESC pfirstdesc;   /* pointer to first descriptor */
    _PBLKDESC proverdesc;   /* rover pointer */
    _PBLKDESC emptylist;    /* pointer to empty list */
    _BLKDESC  sentinel;     /* Sentinel block for end of heap list */
};
extern struct _heap_desc_ _heap_desc;

可以看到，这里将对内存分成块并用 LinkedList 管理，其中 _block_descriptor 为每个块的描述符，其记录了每块的内存地址（后面还可以看到其中还包括了 heap block 的状态信息），全局变量 _heap_desc 记录了链表头（pfirstdesc），链表尾块（sentinel），以及一个漂移指针（proverdesc）。

漂移指针对快速查找提供了重要支持。

在 HEAPINIT.C 中可以看到全局变量 _heap_desc 的初始值：

struct _heap_desc_ _heap_desc = {
    &_heap_desc.sentinel,   /* pfirstdesc */
    &_heap_desc.sentinel,   /* proverdesc */
    NULL,                   /* emptylist */
    NULL,                   /* sentinel.pnextdesc */
    NULL                    /* sentinel.pblock */
};

即在程序初始时堆大小为0，_heap_desc为一个单节点的链表，可以通过 HEAPADD.C 中的 _heapadd() 和 _heap_add_block() 函数来完成，运行中的 _heap_desc 如图：[a]http://www.wait4c.com/userfiles/9/2004070712265497125.gif[/a]

刚才提到 _block_descriptor 还要记录 heap 块的状态，可是在结构中并没有这样的 member 。HEAP.H 中定义了一个 _GRANULARITY 作为内存分配的基数，在这里值为4，就是说所有的内存分配操作尺寸都是4的倍数，于是 _block_descriptor 的成员 void *pblock 的最低两位便空闲出来（因为所分配的所有地址这两位都是0），程序就是利用这两位纪录块的状态。HEAP.H 中的 _IS_FREE, _SET_FREE 等宏就是对这两位操作。

找到了数据结构，现在可以研究一下 malloc 和 free 的算法实现了，在文件 MALLOC.C 中有几个重要函数 _malloc_base() _nh_malloc_base() _heap_alloc_base()。其中第一个便是 Release 版的 malloc 函数，她仅仅是调用了 _nh_malloc_base()，"nh"代表的是"new handle"，此函数处理堆分配失败时的回调函数，无非是循环调用（我记得 new handle 是 C++ 的机制，为什么会出现在这里？ M$C？）。
malloc 的算法由 _heap_alloc_base() 实作，简化程序如下：

/*
 * Does actual heap allocation
 */
void * __cdecl _heap_alloc_base (size_t size)
{
    _PBLKDESC pdesc;
    _PBLKDESC pdesc2;

    /* try to find a big enough free block */
    if ( (pdesc = _heap_search(size)) == NULL ) {
        if ( _heap_grow(size) != -1 ) {
            /* try finding a big enough free block again. the
             * success of the call to _heap_grow should guarantee it. */
            if ( (pdesc = _heap_search(size)) == NULL ) {
                /* something unexpected, and very bad */
                _heap_abort();
            }
        }
        else
            return NULL;
    }

    /* carve the block into two pieces (if necessary) */
    if ( _BLKSIZE(pdesc) != size ) {
        if ( (pdesc2 = _heap_split_block(pdesc, size)) != NULL )
            _SET_FREE(pdesc2);
    }

    _SET_INUSE(pdesc);
    _heap_desc.proverdesc = pdesc->pnextdesc;

    return( (void *)((char *)_ADDRESS(pdesc) + _HDRSIZE) );  /* NOTE! */
}

程序利用 _heap_search() 从刚才提到的 _heap_desc 中查找是否有足够大的空闲块，如果没有便利用 _heap_grow() 函数增加 heap 的尺寸。找到空闲块之后将其按照需要调整大小，并将其标示为使用状态。（_heap_search 和 _heap_split_block 的实现也非常有意思，有空再聊）

然后用宏 _ADDRESS 从块描述符中取得块地址，向下偏移 _HDRSIZE 然后返回。等等！为什么要向下偏移？ _HDRSIZE 是什么？

回到 HEAP.H 中找找，哈哈：

/*
 * Size of the header in a memory block. Note that we must have
 * sizeof(void *) <= _HDRSIZE so the header is big enough to hold a pointer
 * to the descriptor.
 */
#define _HDRSIZE    1 * _GRANULARITY

上面已经说过 _GRANULARITY，则 _HDRSIZE=4 。这就是我们要找的那个参量，怀疑被证明了一半。再查看 HEAPADD.C 中的块添加函数 _heap_add_block ，其中在添加一个新块的时总是将该块的最初4个字节赋予对应的块描述符的地址。在 HEAP.H 中定义的宏 _BACKPTR(addr) 可以经由 malloc 返回的地址取得相应的块描述符，从而得知分配的空间大小。另外在 HEAPSRCH.C 中的 _heap_search 函数也是以“需求内存大小+_HDRSIZE”为搜索尺寸的。

再看看 FREE.H 中 free 的实现代码：

pblock = (char *)pblock - _HDRSIZE;
pdesc = *(_PBLKDESC*)pblock;

_SET_FREE(pdesc);

这下明白了，malloc 总是分配超过要求大小4字节的内存，并将内存的最初4字节赋予内部的块描述符的地址，而将第5字节的内存地址返回供用户使用。当调用 free 时， free 从目标地址向上偏移4字节，取得内部的块描述符地址，进而取得块大小（_MEMSIZE），然后释放相应内存。

至此我们基本了解了heap管理的实现细节，其实后面还有很多，比如：在 block 的管理下面还有一层 _heap_region_ 用来管理 heap 的增长，这些还没有深究；还有 _heap_search 的相应算法，对于自己编写内存池、优化都是很重要的，至少应该看看；由上面 _heap_desc 的描述也可以想到 realloc 的实现不一定总是需要拷贝操作吧！：）

[ 2004-07-08 12:35:05 ApH 修改 ]

精华再现~~~怎麽沒有見著第一?

不管怎么样,先抢掉二楼

APH真是不简单,写了这么多辛苦了,什么时候混到读懂了,在看,先收藏着 :)

--------------------
我的签名不占地方吧?

就见你到处抢[em104][em104][em104][em104] -------------------- [em074][em074][em074][em074][em074][em074][em074][em074][em074][em074][em074][em074][em074]
[em074]趴在楼下的背上睡得呼呼的Zzzzzz............[em074]
[em074][em074][em074][em074][em074][em074][em074][em074][em074][em074][em074][em074][em074]

[a=http://home.itdrp.com/go2west/]感情欠费中
           爱情停机中
                       工作寻找中[/a]

c++都快忘光了  呵呵  复习中？？ -------------------- [email protected]

very cow, i got it~

不管怎么样,先抢掉二楼

APH真是不简单,写了这么多辛苦了,什么时候混到读懂了,在看,先收藏着 :) -------------------- 我的签名不占地方吧?