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的主要内容了。
