quake3引擎之内存池（一）

quake3(雷神之锤III)是ID software公司采用id Tech3技术开发的一款第一人称射击游戏。网上有不少的源码分析的文章了，其中不乏有写的很好的文章值得阅读的。作为一个较早的开源引擎，很多童鞋说里面很多技术过时了，诚然，关于这点，因为技术普通，故而不做评论。只是出于热爱去阅读罢了。

这篇主要分析quake3的内存池技术。只阅读了小块内存处理部分的代码，因此这里只分析这部分。大块内存的分配和管理是在代码的Hunk部分，留待下次分析。
关于内存池，网上也有很多相关的文章和算法。总结而言就是预分配内存块，然后根据需要从这个预分配的内存块查找到合适的大小的内存，返回给业务使用，使用完毕后，标记内存块状态为“回收”，以供下次使用，而非真正释放内存。
这样做的好处就是
1.不会产生内存碎片
2.比系统的分配（new/malloc）以及回收（delete/free）速度更快
3.内存的heap-dump
4.泄漏检测

所以想分析quake3的这块内存管理的内容，是因为其内存池的设计思路虽说都大同小异，但是却兼顾了内容使用率和速度，而且代码简洁有力，思路明晰，不愧是卡马克大神的作品。放到今天，依旧毫不逊色。该内存池的特点就如同注释里面说的

There is never any space between memblocks, and there will never be two
contiguous free memblocks.

已分配出去的两个内存块之间绝对不会有其他空间，绝对不会有两个连续标记空闲的内存块。

啰嗦了这么多，开始上干货吧。

内存块结构定义

#define ZONEID  0x1d4a11
#define MINFRAGMENT 64

typedef struct zonedebug_s {
    char *label;
    char *file;
    int line;
    int allocSize;
} zonedebug_t;

typedef struct memblock_s {
    int     size;           // including the header and possibly tiny fragments
    int     tag;            // a tag of 0 is a free block
    struct memblock_s       *next, *prev;
    int     id;             // should be ZONEID
#ifdef ZONE_DEBUG
    zonedebug_t d;
#endif
} memblock_t;

typedef struct {
    int     size;           // total bytes malloced, including header
    int     used;           // total bytes used
    memblock_t  blocklist;  // start / end cap for linked list
    memblock_t  *rover;
} memzone_t;

以上三个结构就是ZONE MEMORY ALLOCATION中使用的所有结构了。
其中，ZONEID用于标记由内存池分配的内存块，即memblock_t结构中的那个id，should be ZONEID。MINFRAGMENT表示最小的内存块大小，用于在分配之后，如果剩余的空间比这个大的话，就再分一个block出来。
zondebug_t结构主要在DEBUG的时候使用，用于标记请求分配的文件，行号，标签，大小信息，Dump的时候有用。
memblock_t结构是每个具体的分配出去的内存块的Header。记录了本次分配的大小以及前后block的地址，使用状态。
memzone_t结构负责管理内存池的。记录总分配大小，使用情况，内存块链表，下一个待检查的block地址。在每次分配和释放的时候，这个rover都会动态的去调整位置，然后下次分配就从rover的位置开始，适度避免检索部分出于“忙”状态的block。

对外接口

quake3的小块内存通过ZONE MEMORY BLOCK的块来实现分配和回收，提供对外的接口分别为

#ifdef ZONE_DEBUG
#define Z_TagMalloc(size, tag)          Z_TagMallocDebug(size, tag, #size, __FILE__, __LINE__)
#define Z_Malloc(size)                  Z_MallocDebug(size, #size, __FILE__, __LINE__)
#define S_Malloc(size)                  S_MallocDebug(size, #size, __FILE__, __LINE__)
void *Z_TagMallocDebug( int size, int tag, char *label, char *file, int line ); // NOT 0 filled memory
void *Z_MallocDebug( int size, char *label, char *file, int line );         // returns 0 filled memory
void *S_MallocDebug( int size, char *label, char *file, int line );         // returns 0 filled memory
#else
void *Z_TagMalloc( int size, int tag ); // NOT 0 filled memory
void *Z_Malloc( int size );         // returns 0 filled memory
void *S_Malloc( int size );         // NOT 0 filled memory only for small allocations
#endif
void Z_Free( void *ptr );
void Z_FreeTags( int tag );
int Z_AvailableMemory( void );
void Z_LogHeap( void );

其中分配内存的函数有三个，对应DEBUG模式和RELEASE模式。释放接口有两个，Z_Free用于释放指定起始地址的内存，Z_FreeTags释放指定标签的内存。Z_AvailableMemory用于查询当前池内可用内存。Z_LogHeap用于Dump内存池的使用信息，包括例如哪个文件哪一行请求了多大的内存，标签值等等信息。

分配和释放

其他的还有一些小的函数就不逐一分析了，这里主要分析当中的malloc和free部分。也是这个内存池的核心。
首先看malloc
代码我不全贴了，分析几个关键点

/*
================
Z_TagMalloc
================
*/
#ifdef ZONE_DEBUG
void *Z_TagMallocDebug( int size, int tag, char *label, char *file, int line ) {
#else
void *Z_TagMalloc( int size, int tag ) {
#endif
    int     extra, allocSize;
    memblock_t  *start, *rover, *new, *base;
    memzone_t *zone;
    ...
    // 这段是查找所有的内存块，直到找到第一个满足大小的block用作分配
    do {
        if (rover == start) {
#ifdef ZONE_DEBUG
            Z_LogHeap();
#endif
            // scaned all the way around the list
            Com_Error( ERR_FATAL, "Z_Malloc: failed on allocation of %i bytes from the %s zone",
                                size, zone == smallzone ? "small" : "main");
            return NULL;
        }
        if (rover->tag) {
            base = rover = rover->next;
        } else {
            rover = rover->next;
        }
    } while (base->tag || base->size < size);
    ...
    // 如果分配后，剩余的内存大于最小内存块的划分，就再分一个新的block出来（这样可以保证浪费会小于64字节）
    extra = base->size - size;
    if (extra > MINFRAGMENT) {
        // there will be a free fragment after the allocated block
        new = (memblock_t *) ((byte *)base + size );
        new->size = extra;
        new->tag = 0;           // free block
        new->prev = base;
        new->id = ZONEID;
        new->next = base->next;
        new->next->prev = new;
        base->next = new;
        base->size = size;
    }

以上是内存分配的基本内容。

内存释放

/*
========================
Z_Free
========================
*/
void Z_Free( void *ptr ) {
    memblock_t  *block, *other;
    memzone_t *zone;
    ...
    // 总大小减去释放的size，并且标记block空闲
    zone->used -= block->size;
    // set the block to something that should cause problems
    // if it is referenced...
    Com_Memset( ptr, 0xaa, block->size - sizeof( *block ) );

    block->tag = 0;     // mark as free
    // 这一块就很关键了，释放之后，检查该block的前一块内存以及后一块内存，如果都是空闲的话，就合并内存块。并且标记了下一个检索的位置
     other = block->prev;
    if (!other->tag) {
        // merge with previous free block
        other->size += block->size;
        other->next = block->next;
        other->next->prev = other;
        if (block == zone->rover) {
            zone->rover = other;
        }
        block = other;
    }

    zone->rover = block;

    other = block->next;
    if ( !other->tag ) {
        // merge the next free block onto the end
        block->size += other->size;
        block->next = other->next;
        block->next->prev = block;
        if (other == zone->rover) {
            zone->rover = block;
        }
    }

以上就是quake3中zone memory allocation的主要内容了。