软件项目中最为重要的内容之一就是内存管理,游戏开发尤为如此。一款游戏的运行需要占用大量内存资源,特别是移动设备在硬件受限的情况下,如果不能管理好内存,系统很快就会因为内存不足导致程序崩溃。内存管理中最为关心的两类问题是内存泄露和内存碎片问题。使用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:%dn", 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("%sn", message);
 7     printf("Zone Info(%p):nSize: %dnUsed:%dn", zone, zone->size, zone->used);
 8     block = zone->freeblock;
 9     while (block)
10     {
11         printf("Free addr:%p, size:%dn", block, block->size);
12         block = block->next;
13         if (block == zone->freeblock)
14             break;
15     }
16     printf("==========================================n");
17 
18     printf("nr");
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;}
内容来源于网络如有侵权请私信删除

文章来源: 博客园

原文链接: https://www.cnblogs.com/primarycode/p/16328487.html

你还没有登录,请先登录注册
  • 还没有人评论,欢迎说说您的想法!