quake3(雷神之錘III)是ID software公司采用id Tech3技術(shù)開(kāi)發(fā)的一款第一人稱(chēng)射擊游戲织咧。網(wǎng)上有不少的源碼分析的文章了庄拇，其中不乏有寫(xiě)的很好的文章值得閱讀的宝泵。作為一個(gè)較早的開(kāi)源引擎，很多童鞋說(shuō)里面很多技術(shù)過(guò)時(shí)了另锋，誠(chéng)然待德，關(guān)于這點(diǎn)，因?yàn)榧夹g(shù)普通筹麸，故而不做評(píng)論活合。只是出于熱愛(ài)去閱讀罷了。
這篇主要分析quake3的內(nèi)存池技術(shù)物赶。只閱讀了小塊內(nèi)存處理部分的代碼白指，因此這里只分析這部分。大塊內(nèi)存的分配和管理是在代碼的Hunk部分酵紫，留待下次分析告嘲。
關(guān)于內(nèi)存池，網(wǎng)上也有很多相關(guān)的文章和算法奖地￠匣＃總結(jié)而言就是預(yù)分配內(nèi)存塊，然后根據(jù)需要從這個(gè)預(yù)分配的內(nèi)存塊查找到合適的大小的內(nèi)存参歹，返回給業(yè)務(wù)使用仰楚，使用完畢后，標(biāo)記內(nèi)存塊狀態(tài)為“回收”，以供下次使用僧界，而非真正釋放內(nèi)存侨嘀。
這樣做的好處就是
1.不會(huì)產(chǎn)生內(nèi)存碎片
2.比系統(tǒng)的分配（new/malloc）以及回收（delete/free）速度更快
3.內(nèi)存的heap-dump
4.泄漏檢測(cè)
所以想分析quake3的這塊內(nèi)存管理的內(nèi)容，是因?yàn)槠鋬?nèi)存池的設(shè)計(jì)思路雖說(shuō)都大同小異捂襟，但是卻兼顧了內(nèi)容使用率和速度咬腕，而且代碼簡(jiǎn)潔有力，思路明晰笆豁，不愧是卡馬克大神的作品郎汪。放到今天，依舊毫不遜色闯狱。該內(nèi)存池的特點(diǎn)就如同注釋里面說(shuō)的
There is never any space between memblocks, and there will never be two
contiguous free memblocks.
已分配出去的兩個(gè)內(nèi)存塊之間絕對(duì)不會(huì)有其他空間煞赢，絕對(duì)不會(huì)有兩個(gè)連續(xù)標(biāo)記空閑的內(nèi)存塊。
啰嗦了這么多哄孤，開(kāi)始上干貨吧照筑。
內(nèi)存塊結(jié)構(gòu)定義
#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;
以上三個(gè)結(jié)構(gòu)就是ZONE MEMORY ALLOCATION中使用的所有結(jié)構(gòu)了。
其中瘦陈，ZONEID用于標(biāo)記由內(nèi)存池分配的內(nèi)存塊凝危，即memblock_t結(jié)構(gòu)中的那個(gè)id，should be ZONEID晨逝。MINFRAGMENT表示最小的內(nèi)存塊大小蛾默，用于在分配之后，如果剩余的空間比這個(gè)大的話捉貌，就再分一個(gè)block出來(lái)支鸡。
zondebug_t結(jié)構(gòu)主要在DEBUG的時(shí)候使用，用于標(biāo)記請(qǐng)求分配的文件趁窃，行號(hào)牧挣，標(biāo)簽，大小信息醒陆，Dump的時(shí)候有用瀑构。
memblock_t結(jié)構(gòu)是每個(gè)具體的分配出去的內(nèi)存塊的Header。記錄了本次分配的大小以及前后block的地址刨摩，使用狀態(tài)寺晌。
memzone_t結(jié)構(gòu)負(fù)責(zé)管理內(nèi)存池的。記錄總分配大小码邻，使用情況折剃，內(nèi)存塊鏈表，下一個(gè)待檢查的block地址像屋。在每次分配和釋放的時(shí)候怕犁，這個(gè)rover都會(huì)動(dòng)態(tài)的去調(diào)整位置，然后下次分配就從rover的位置開(kāi)始，適度避免檢索部分出于“忙”狀態(tài)的block奏甫。
對(duì)外接口
quake3的小塊內(nèi)存通過(guò)ZONE MEMORY BLOCK的塊來(lái)實(shí)現(xiàn)分配和回收戈轿，提供對(duì)外的接口分別為
#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 );
其中分配內(nèi)存的函數(shù)有三個(gè)，對(duì)應(yīng)DEBUG模式和RELEASE模式阵子。釋放接口有兩個(gè)思杯，Z_Free用于釋放指定起始地址的內(nèi)存，Z_FreeTags釋放指定標(biāo)簽的內(nèi)存挠进。Z_AvailableMemory用于查詢(xún)當(dāng)前池內(nèi)可用內(nèi)存色乾。Z_LogHeap用于Dump內(nèi)存池的使用信息，包括例如哪個(gè)文件哪一行請(qǐng)求了多大的內(nèi)存领突，標(biāo)簽值等等信息暖璧。
分配和釋放
其他的還有一些小的函數(shù)就不逐一分析了，這里主要分析當(dāng)中的malloc和free部分君旦。也是這個(gè)內(nèi)存池的核心澎办。
首先看malloc
代碼我不全貼了，分析幾個(gè)關(guān)鍵點(diǎn)
/*
================
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;
...
// 這段是查找所有的內(nèi)存塊金砍，直到找到第一個(gè)滿足大小的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);
...
// 如果分配后局蚀，剩余的內(nèi)存大于最小內(nèi)存塊的劃分，就再分一個(gè)新的block出來(lái)（這樣可以保證浪費(fèi)會(huì)小于64字節(jié)）
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;
}
以上是內(nèi)存分配的基本內(nèi)容恕稠。
內(nèi)存釋放
/*
========================
Z_Free
========================
*/
void Z_Free( void *ptr ) {
memblock_t *block, *other;
memzone_t *zone;
...
// 總大小減去釋放的size琅绅，并且標(biāo)記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
// 這一塊就很關(guān)鍵了，釋放之后鹅巍，檢查該block的前一塊內(nèi)存以及后一塊內(nèi)存奉件，如果都是空閑的話，就合并內(nèi)存塊昆著。并且標(biāo)記了下一個(gè)檢索的位置
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的主要內(nèi)容了。
