《风魂》引擎之内存池学习

《风魂》里使用的是块固定大小的带内存泄露检查的内存池，下面具体说：
1  从总体上说，内存池对小内存块和大内存区分处理，而所谓大小则可以根据程序需求。像引擎里则以256字节为标准，小于256字节的为小内存块，大于256字节的为大内存块。大内存块直接向系统申请，小内存块再以8字节为单位分为不同的大小：8，16，24…到256，总共有256/8 = 32种大小的chunk。chunk是我们直接进行操作的对象。chunk除了需要保存自定义的数据之外，同时还需要保存chunk大小的信息，这样子删除chunk时候才可以将其归还给内存池；若在需要检查内存泄露的情况下，还要保存文件名，文件行数等等信息。

2  我们操作的对象都是针对chunk的进行的，因此在内存池中，chunk是以链表组织起来的，每个chunk都链接到下一个的chunk。“空闲列表”用来保存已经被分配的待使用的chunk，如果被使用了，chunk就从链表中移走。引擎里有32种不同大小的chunk，也就是32个链表保存在一个数组里。当chunk归还内存池时，则根据chunk本身的大小信息找到对应的列表插入。因为同个列表的chunk直接并无差异，不管申请还是归还直接对表头进行操作即可。

3  “总列表”是用来记录每次向系统申请的内存指针和大小，也就是每次当空闲列表为空时申请内存时，除了更新空闲列表本身，也同时要加入总列表中。这样子总列表就保存了所有内存池向系统申请的内存，只需对它进行删除就可以将去内存池所有内存归还系统。同时，由于总列表保存所有的chunk，而空闲列表保存着当前可以使用的chunk，那么程序最后结束时，内存泄露chunk = 总列表chunk - 空闲列表chunk。

4 大内存chunk则直接对系统内存进行操作，同样使用链表保存大内存chunk。申请时向系统申请并且加入链表，释放时归还系统并且从链表取出。最后链表剩下的chunk就是内存泄露了。
 
接下来看下《风魂》里的小内存chunk

代码

struct memory_cookie {
#ifdef _DEBUG
   const char *file;           //文件名 
   unsigned line;              //文件行数 
   unsigned id;                //全局id 
#endif
   size_t size;                //chunk大小 
   union {
      memory_cookie *next;     //下一链表节点 
      unsigned char data[1];   //数据区 
   };
}; 

上面说过，chunk必须除了保存自定义的数据，还需要记录chunk本身的大小，还有下一个chunk指针。在debug模式下，同时还记录了文件名，行数，一个id（全局累加），这些信息用于提供内存泄露检查的，所以只在debug模式下需要。注意next指针和data是采用union的方式组合在一起，下面再说它的作用。

struct cookie {
#ifdef _DEBUG
      cookie *prev;
      cookie *next;
      const char *file;
      unsigned line;
      unsigned id;
#endif
      size_t size;
};
 

这是引擎里的大内存chunk，跟小内存chunk有所不同。因为大内存chunk的申请和归还都是针对系统的，因此只有在需要检查内存泄露的情况下才将其放入链表，以双链表的形式可以提高链表操作的效率。
有了chunk的信息，看下我们申请的内存大小是如何转化成chunk的。在此内存池中，当我们创建一个对象，比如T *p = new T，那么需要申请的内存是sizeof(T)。而实际上chunk的大小 = sizeof(T) + sizeof(memory_cookie) - sizeof(memory_cookie *)。这里之所以还要减去sizeof(memory_cookie *)，是因为上面提过的里面的next*指针和data共享数据。当chunk在空闲列表中未被使用时，需要用next链接下一个chunk，data数据为空。而当chunk被取出使用时，next指针不需要被使用。当chunk归还内存池时，根据size大小找到相应的空闲链表插入，此次data数据已无用，next重新使用。
 
接下来根据得到的chunk大小，进行8字节对齐计算（如何计算，可以看字节对齐计算），这样求的的才能在空闲列表中找到对应大小的块链表。接着判断对齐后的chunk的大小，有两种情况：
1.如果小于最大的小内存块，即256字节，则从对应的空闲列表去除头节点chunk，并返回chunk->data进行使用。
2.如果大于256字节，则以大内存块处理。此时重新根据sizeof(T) + sizeof(cookie)，并且以8字节对齐后，求的的就是大内存块的chunk。向系统申请内存，同时返回chunk->data使用。

以下用伪代码说明从内存池申请和删除chunk的过程:

代码

WMalloc(int size)   //申请的大小
{
   size = size + sizeof(memory_cookie) - sizeof(memory_cookie *) //计算小内存chunk
   size = Align(size)    //８字节对齐
   if (size > 256)
   {
       chunk = free_list[size/8].GetHeadNode()
       填充chunk信息
   }
   else
   {
      size = size + sizeof(cookie)
      size = Align(size)
      chunk = malloc(size)  //向系统申请
      填充chunk信息
   }
   return chunk->data;
}

WDelete(void *p) //删除
{
   memory_cookie *chunk=reinterpret_cast<memory_cookie*>(reinterpret_cast<char*>(p)-
   if (chunk ->size > 256)  //
   {
      修改chunk链表信息
      free(chunk)
   }
   else
   {
      free_list[chunk ->size /8].InsertHeadNode(chunk)
   }
}