美文网首页
quake3引擎之内存池(一)

quake3引擎之内存池(一)

作者: ZerLon51 | 来源:发表于2017-06-03 21:51 被阅读0次

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

    相关文章

      网友评论

          本文标题:quake3引擎之内存池(一)

          本文链接:https://www.haomeiwen.com/subject/adipfxtx.html