从零开始游戏开发——1.2 内存管理

　　软件项目中最为重要的内容之一就是内存管理，游戏开发尤为如此。一款游戏的运行需要占用大量内存资源，特别是移动设备在硬件受限的情况下，如果不能管理好内存，系统很快就会因为内存不足导致程序崩溃。内存管理中最为关心的两类问题是内存泄露和内存碎片问题。使用C++进行开发时，我们new出一个对象后很容易忘记释放这块内存而造成内存泄漏，即使我们记得每次都能释放到内存，在游戏中大量对象需要不断创建和销毁时，内存中会造成很多内存碎片，如下图中的灰色和红色部分是已经使用的内存，当红色部分内存被释放后，虽然我们还有足够的内存空间，但当需要申请像第一块灰色大小的内存时，就会导致内存分配失败。

　　为了最大效率的提升内存利用率，我们需要建立自己的内存管理方案。主要思路就是预先分配一块比较大的内存，之后的每次内存分配都是在空闲内存中分配可用空间。外部接口的定义了下面几个函数：

1 void *CreateMemoryZone(int size);
2 void DestroyMemoryZone(void *ptr);
3 void *Malloc(void *fromPtr, int size);
4 void Free(void *fromPtr, void *ptr);
5 void DebugPrint(void *ptr, const char *message);

最开始通过CreateMemoryZone预先分配一块固定大小的内存，之后每次通过Malloc和Free进行逻辑内存分配，最后DestroyMemoryZone释放整块内存，DebugPrint则帮助我们追踪内存的使用情况，帮助排查内存泄露等情况。我们通过链表的方式将空闲列表连接，定义了下面的数据结构：

 1 //内存块
 2 typedef struct memblock_s
 3 {
 4     int size;                       //包含头大小的当前内存块尺寸
 5     int tag;                        //当前内存块是否被使用标记
 6     struct memblock_s *next, *prev; //链连接的上一和下一空闲块
 7 } memblock_t;
 8 
 9 //放在内存末尾用于找到内存头信息
10 typedef struct
11 {
12     int size;
13 } memfooter_t;
14 
15 //内存区首地址
16 typedef struct
17 {
18     int size;               //总内存大小
19     int used;               //当前使用的内存大小
20     memblock_t *freeblock;  //第一块空闲内存块
21 } memzone_t;

CreateMemoryZone后 memzone_t信息存储于内存起始位置，标识了分配内存的总大小、已经使用的内存大小和指向第一块空闲内存的指针，初始情况下没有内存分配，memzone_t后紧接了一个未被分配的memblock_t结构，上一和下一空闲块指向自己，freeblock指向memzone_t的地址，内存释放时则直接调用DestroyMemoryZone，CreateMemoryZone和DestroyMemoryZone的代码如下：

 1 void *CreateMemoryZone(int size)
 2 {
 3     memzone_t *zone;
 4     memblock_t *block;
 5     zone = (memzone_t *)calloc(size, 1);
 6     if (!zone)
 7     {
 8         printf("InitMemory failed : %d", size);
 9         return 0;
10     }
11     zone->size = size;
12     zone->used = 0;
13     block = (memblock_t *)((char *)zone + sizeof(memzone_t));
14     block->next = block->prev = block;
15     block->size = size - sizeof(memzone_t);
16     block->tag = 0;
17     zone->freeblock = block;
18 
19     return zone;
20 }
21 
22 void DestroyMemoryZone(void *ptr)
23 {
24     if (ptr)
25         free(ptr);
26 }

游戏内分配使用的内存时，Malloc分别传入CreateMemoryZone返回的内存地址和需要的内存大小，具体代码如下：

 1 void *Malloc(void *fromPtr, int size)
 2 {
 3     int allocSize, extra;
 4     memblock_t *base, *new;
 5     memfooter_t *footer;
 6     memzone_t *zone = (memzone_t *)fromPtr;
 7 
 8     allocSize = size;
 9     size += sizeof(memblock_t) + sizeof(memfooter_t);
10     size = (size + 3) & ~3; //4字节对齐
11 
12     base = FindFreeMemory(zone, size);
13     if (!base)
14     {
15         printf("Malloc failed, memory not enough:%d/n", size);
16         return 0;
17     }
18 
19     extra = base->size - size;
20     if (extra > sizeof(memblock_t) + sizeof(memfooter_t)) //找到的内存剩余部分可以分割为另一个block
21     {
22         new = (memblock_t *)((char *)base + size);
23         if (base->next == base) //唯一空闲块
24             new->next = new->prev = new;
25         else
26         {
27             new->next = base->next;
28             new->prev = base->prev;
29         }
30         new->size = extra;
31         zone->freeblock = new;
32     }
33     else
34     {
35         if (base->next == base) //唯一内存被分配
36             zone->freeblock = 0;
37         else
38             zone->freeblock = base->next;
39     }
40 
41     base->size = size;
42 
43     footer = (memfooter_t *)((char *)base + size - sizeof(memfooter_t));
44     footer->size = size;
45 
46     base->tag = 1;
47     zone->used += size;
48 
49     return (void *)((char *)base + sizeof(memblock_t));
50 }

上面代码第9、10行可以看到，分配的内存需要加上首尾结构的大小，并进行了一次4字节内存对齐。12行的FindFreeMemory找到一块合适的内存，之后如果有剩余内存则分配新的memblock_t块，最后返回memblock_t后面的地址。FindFreeMemory遍历空闲内存块列表，找到最小满足内存分配的块返回，这里也可以找到第一个满足的内存块以提高查找速度，但会造成内部内存碎片。FindFreeMemory的代码比较简单如下：

 1 memblock_t *FindFreeMemory(memzone_t *zone, int size)
 2 {
 3     memblock_t *base = 0, *worker = 0;
 4     int minMeetSize = -1;
 5 
 6     if (size > zone->size - sizeof(memzone_t) - sizeof(memblock_t) - zone->used)
 7         return 0;
 8 
 9     worker = zone->freeblock;
10     if (!worker)
11         return 0;
12     do
13     {
14         if (worker->size >= size && (worker->size < minMeetSize || minMeetSize == -1))
15         {
16             base = worker;
17             minMeetSize = worker->size;
18         }
19     } while (worker != zone->freeblock);
20 
21     return base;
22 }

内存释放过程稍微有些复杂，内存释放后，需要对空闲的相邻内存块进行合并，代码如下：

 1 void Free(void *fromPtr, void *ptr)
 2 {
 3     memblock_t *base, *other, *first, *last;
 4     memfooter_t *baseFooter, *prevAdjacentFooter, *lastFooter;
 5     memzone_t *zone = (memzone_t *)fromPtr;
 6     int freeSize;
 7     int isMerged = 0;
 8 
 9     base = (memblock_t *)((char *)ptr - sizeof(memblock_t));
10     base->tag = 0;
11     freeSize = base->size;
12 
13     first = (memblock_t *)((char *)fromPtr + sizeof(memzone_t));
14     lastFooter = (memfooter_t *)((char *)fromPtr + zone->size - sizeof(memfooter_t));
15     last = (memblock_t *)((char *)fromPtr + zone->size - lastFooter->size);
16 
17     if (!zone->freeblock)
18     {
19         zone->freeblock = base->next = base->prev = base;
20         return;
21     }
22 
23     //检查相邻内存空闲则合并
24     if (base > first)
25     {
26         prevAdjacentFooter = (memfooter_t *)((char *)base - sizeof(memfooter_t));
27         other = (memblock_t *)((char *)base - prevAdjacentFooter->size);
28         if (other->tag == 0)
29         {
30             base = other;
31             base->size += freeSize;
32             isMerged = 1;
33         }
34     }
35 
36     if (base < last)
37     {
38         other = (memblock_t *)((char *)base + base->size);
39         if (other->tag == 0)
40         {
41             base->size += other->size;
42             base->next = other->next;
43             base->prev = other->prev;
44             base->prev->next = base;
45             base->next->prev = base;
46             if (other == zone->freeblock)
47             {
48                 zone->freeblock = base;
49             }
50             isMerged = 1;
51         }
52     }
53 
54     baseFooter = (memfooter_t *)((char *)base + base->size - sizeof(memfooter_t));
55     baseFooter->size = base->size;
56 
57     zone->used -= freeSize;
58 
59     if (!isMerged)
60     {
61         base->next = zone->freeblock->next;
62         base->prev = zone->freeblock;
63         zone->freeblock->next = base;
64         if (zone->freeblock->prev == zone->freeblock)
65             zone->freeblock->prev = base;
66     }
67 }

代码第17号判断如果当前没有空闲内存，则直接将freeblock指向当前释放的内存块。第24行到56行判断是否相邻内存块空闲，如果空闲则进行合并。最后在59行的时候，如果内存块没进行合并，则插入到空间列表中。至此，需要的内存管理函数就都有了，我们还增加了一个调试函数如下，实际使用时可按需修改：

 1 void DebugPrint(void *ptr, const char *message)
 2 {
 3     memzone_t *zone = (memzone_t *)ptr;
 4     memblock_t *block;
 5     printf("==========================================/n");
 6     printf("%s/n", message);
 7     printf("Zone Info(%p):/nSize: %d/nUsed:%d/n", zone, zone->size, zone->used);
 8     block = zone->freeblock;
 9     while (block)
10     {
11         printf("Free addr:%p, size:%d/n", block, block->size);
12         block = block->next;
13         if (block == zone->freeblock)
14             break;
15     }
16     printf("==========================================/n");
17 
18     printf("/n/r");
19 }

　　以上是全部的内存管理函数，在实际游戏中，需要根据对内存的实际需求进行初始大小的分配，如果开始的时候内存大小是无法确定的，也可以在Malloc内存时，动态管理内存大小

如果发现空间不足，则重新分配一块更大的内存zone，将当前的分配信息拷贝到新的内存zone下，而不是像现在这样直接返回错误。

{    memzone_t *zone;    memblock_t *block;    zone = (memzone_t *)calloc(size, 1);    if (!zone)        printf(“InitMemory failed : %d”, size);    zone->size = size;    zone->used = 0;    block = (memblock_t *)((char *)zone + sizeof(memzone_t));    block->next = block->prev = block;    block->size = size – sizeof(memzone_t);    block->tag = 0;    zone->freeblock = block;
    return zone;}