C 内存管理 - 高并发内存池 - 《编程技术》

内存池的设计
STL的空间配置器
- 一级空间配置器
- 二级空间配置器
并发内存池
- 申请内存
- 释放内存
Reference

频繁的内存的申请和释放会造成内存碎片的问题（new delete），最终造成程序的性能降低。内存的池化技术就是为了减少内存频繁的申请和释放问题，从而降低内存碎片。

当程序运行的时间很长的时候，由于所申请的内存块的大小不定，频繁使用时会造成大量的内存碎片从而降低程序和操作系统的性能。

内存池的原理就是在程序开始时，提前申请一块大的内存用以专门程序内内存的申请和释放，并通过维护这块大的内存而提升内存的利用效率。

内存池则是在真正使用内存之前，先申请分配一大块内存（内存池）留作备用。当程序员申请内存时，从池中取出一块动态分配，当程序员释放时，将释放的内存放回到池内，再次申请，就可以从池里取出来使用，并尽量与周边的空闲内存块合并。若内存池不够时，则自动扩大内存池，从操作系统中申请更大的内存池。

内存的碎片分为内存的内碎片和外碎片。
内碎片是由于所申请的内存大于实际所使用的内存而早晨的内存碎片。
外碎片则是由于释放的内存由于存在不连续的情况，而导致无法有效的被利用而产生的碎片。

假设系统依次分配了16byte、8byte、16byte、4byte，还剩余8byte未分配。这时要分配一个24byte的空间，操作系统回收了一个上面的两个16byte，总的剩余空间有40byte，但是却不能分配出一个连续24byte的空间

内存的池化技术只能降低外碎片，而不能解决内碎片的问题。

内存池的设计

简单的内存池

一个简单的内存池，是通过一个链表来对这块大的内存进行管理，当需要申请一块内存时，通过指针来找到空余的符合申请的内存大小的空间，将起始地址的指针进行返回，当内存使用完毕的时候，在链表中进行释放，同时做好标记，并及时对内存进行重新的归并。
优点是：实现简单
缺点是：会花费较长的时间用于查找合适的内存大小，释放内存进行归并的操作性能消耗也较大。

定长内存分配器

将内存分成同样大小的空间，维护两个指针，分别指向空闲内存的位置openptr和应用中内存的位置closeptr，申请时，移动openptr，释放时，移动closeptr，当closeptr移动到末尾时，集中释放整块内存。
优点：简单粗暴，分配和释放的效率高，解决实际中特定场景下的问题有效。
缺点：功能单一，只能解决定长的内存需求，另外占着内存没有释放。

哈希映射的FreeList池

STL的空间配置器

STL中采用两级空间配置器，当申请的内存大于128字节时，采用一级空间配置器，直接调用系统的malloc（）完成内存的分配，当申请的内存小于128字节时，系统认为所申请的内存是小内存，采用二级空间配置器，从内存池中分配内存。

一级空间配置器

SGI以malloc来配置内存。当malloc()失败后，就调用oom_alloc()，如果客户端没有设置内存不足处理机制，则就直接抛出bad_alloc异常信息，或者直接终止程序。如果客户端设置了内存不足处理机制，则他就会一直调用 内存处理机制 ，企图在某次调用之后获得一块足够的内存。但是如果内存不足处理机制设计不好的话，存在死循环的危险。注意：” 内存不足处理机制 “是客户端的责任，设置”内存不足处理介质”也是客户端的责任。

typedef void(*MALLOCALLOC)();           //将void (*)()   重命名成MALLOCALLOC
template<int inst>
class _MallocAllocTemplate
{
private:
       static void* _OomMalloc(size_t);       //malloc失败的时候调用的函数
       static MALLOCALLOC _MallocAllocOomHandler;         //函数指针，内存不足的时候的处理机制
public:
       static void* _Allocate(size_t n)                        //分配空间n个字节的空间
       {
              void *result=0;
              result = malloc(n);
              if (0 == result)                    //若果malloc失败，则就调OOM_malloc
                     _OomMalloc(n);
              return result;
       }
       static void _DeAllocate(void *p)                //释放这块空间
       {
              free(p);
       }
       static MALLOCALLOC _SetMallocHandler(MALLOCALLOC f)    //这是一个函数，参数是一个函数指针，返回值也是一个函数指针
       {
              MALLOCALLOC old = _MallocAllocOomHandler;
              _MallocAllocOomHandler = f;              //将内存分配失败的句柄设置为f(让它指向一个内存失败了，让系统去释放其他地方空间的函数)
              return old;
       }
};
template<int inst>
void(* _MallocAllocTemplate<inst>::_MallocAllocOomHandler)()=0;    //默认不设置内存不足处理机制
template<int inst>
void* _MallocAllocTemplate<inst>::_OomMalloc(size_t n)
{
       MALLOCALLOC _MyMallocHandler;     //定义一个函数指针
       void *result;               
       while (1)
       {
              _MyMallocHandler = _MallocAllocOomHandler;
              if (0 == _MyMallocHandler)                  //没有设置内存不足处理机制
                     throw std::bad_alloc();                  //则抛出异常
              (*_MyMallocHandler)();                 //调用内存不足处理的函数，申请释放其他地方的内存
              if (result = malloc(n))                //重新申请内存
                     break;
       }
       return result;                              //申请成功时，则返回这块内存的地址
}
typedef _MallocAllocTemplate<0> malloc_alloc;

二级空间配置器

二级空间配置器在分配的时候都是以8的倍数对齐。也就是说二级配置器会将任何小块内存的需求上调到8的倍数处(例如：要7个字节，会给你分配8个字节。要9个字节，会给你16个字节),尽管这样做有内碎片的问题，但是对于我们管理来说却简单了不少。因为这样的话只要维护16个free_list就可以了，free_list这16个结点分别管理大小为8,16,24,32,40,48,56,64,72,80,88,86,96,104,112,120,128字节大小的内存块就行了。

自由链表的结构类型

union _Obj
{
    union _Obj* _M_free_list_link;
    char _M_client_data[1];    /* The client sees this.*/
};

采用union的方式使得一物可以二用

enum { _ALIGN = 8 };              //按照基准值8的倍数进行内存操作（小型区块的上调边界）
enum { _MAXBYTES = 128 };        //自由链表中最大的块的大小是128（小型区块的上限）
enum { _NFREELISTS = 16 };       //自由链表的长度，等于_MAXBYTES/_ALIGN（free-list的个数）
//第一个参数用于多线程环境，第二参数完全没有派上用场
template <bool threads, int inst>  //非模板类型参数
class _DefaultAllocTemplate
{
       union _Obj                      //自由链表结点的类型
       {
              _Obj* _freeListLink;         //指向自由链表结点的指针
              char _clientData[1];          //this client sees
       };
private:
       static char* _startFree;             //内存池的头指针
       static char* _endFree;               //内存池的尾指针
       static size_t _heapSize;              //记录内存池已经向系统申请了多大的内存
       static _Obj* volatile _freeList[_NFREELISTS];    //自由链表
private:
       static size_t _GetFreeListIndex(size_t bytes)   //得到这个字节对应在自由链表中应取的位置
       {
              return (bytes +(size_t) _ALIGN - 1) / (size_t)_ALIGN - 1;     
       }
       static size_t _GetRoundUp(size_t bytes)        //对这个字节向上取成8的倍数
       {
              return (bytes + (size_t)_ALIGN - 1)&(~(_ALIGN-1));     //将n向上取成8的倍数
       }
       static void* _Refill(size_t n);          //在自由链表中申请内存,n表示要的内存的大小
       static char* _chunkAlloc(size_t size,int& nobjs);    //在内存池中申请内存nobjs个对象，每个对象size个大小
public:
       static void* Allocate(size_t n);      //n要大于0
       static void DeAllocate(void *p,size_t n);        //n要不等于0

具体的实现

num { _ALIGN = 8 };              //按照基准值8的倍数进行内存操作
enum { _MAXBYTES = 128 };        //自由链表中最大的块的大小是128
enum { _NFREELISTS = 16 };       //自由链表的长度，等于_MAXBYTES/_ALIGN
template <bool threads, int inst>  //非模板类型参数
class _DefaultAllocTemplate
{
       union _Obj                      //自由链表结点的类型
       {
              _Obj* _freeListLink;         //指向自由链表结点的指针
              char _clientData[1];          //this client sees
       };
private:
       static char* _startFree;             //内存池的头指针
       static char* _endFree;               //内存池的尾指针
       static size_t _heapSize;              //记录内存池已经向系统申请了多大的内存
       static _Obj* volatile _freeList[_NFREELISTS];    //自由链表
private:
       static size_t _GetFreeListIndex(size_t bytes)   //得到这个字节对应在自由链表中应取的位置
       {
              return (bytes +(size_t) _ALIGN - 1) / (size_t)_ALIGN - 1;     
       }
       static size_t _GetRoundUp(size_t bytes)        //对这个字节向上取成8的倍数
       {
              return (bytes + (size_t)_ALIGN - 1)&(~(_ALIGN-1));     //将n向上取成8的倍数
       }
       static void* _Refill(size_t n);          //在自由链表中申请内存,n表示要的内存的大小
       static char* _chunkAlloc(size_t size,int& nobjs);    //在内存池中申请内存nobjs个对象，每个对象size个大小
public:
       static void* Allocate(size_t n);      //n要大于0
       static void DeAllocate(void *p,size_t n);        //n要不等于0
};
template<bool threads,int inst>
char* _DefaultAllocTemplate<threads,inst>::_startFree = 0;        //内存池的头指针
template<bool threads, int inst>
char* _DefaultAllocTemplate<threads, inst>::_endFree=0;           //内存池的尾指针
template<bool threads, int inst>
size_t _DefaultAllocTemplate<threads, inst>::_heapSize = 0;              //记录内存池已经向系统申请了多大的内存
template<bool threads, int inst>
typename _DefaultAllocTemplate<threads, inst>::_Obj* volatile      //前面加typename表示后面是个类型
_DefaultAllocTemplate<threads, inst>::_freeList[_NFREELISTS] = {0};    //自由链表
template<bool threads, int inst>
void* _DefaultAllocTemplate<threads, inst>::Allocate(size_t n)    //分配空间
{
       void *ret;
       //先判断要分配的空间大小是不是大于128个字节
       if (n>_MAXBYTES)      //大于_MAXBYTES个字节则认为是大块内存，直接调用一级空间配置器
       {
              ret = malloc_alloc::_Allocate(n);
       }
       else       //否则就去自由链表中找
       {
              _Obj* volatile *myFreeList = _freeList+_GetFreeListIndex(n);  //让myFreeList指向自由链表中n向上取8的整数倍
              _Obj* result = *myFreeList;
              if (result == 0)  //这个结点下面没有挂内存，则就要去内存池中申请
              {
                     ret = _Refill(_GetRoundUp(n));      //到内存池中申请
              }
              else            //已经在自由链表上找到了内存
              {
                     *myFreeList= result->_freeListLink;      //把第二块空间的地址放到自由链表上
                     ret = result;
              }
       }
       return ret;
}
template<bool threads, int inst>
void _DefaultAllocTemplate<threads, inst>::DeAllocate(void *p, size_t n)   //回收空间
{
       //先判断这个字节的大小
       if (n > _MAXBYTES)  //如果n大于自由链表中结点所能挂的最大内存块，则就直接调用一级指针的释放函数
       {
              malloc_alloc::_DeAllocate(p);
       }
       else        //将这块内存回收到自由链表中
       {
              _Obj* q = (_Obj*)p;
              _Obj* volatile *myFreeList = _freeList + _GetFreeListIndex(n);
              q->_freeListLink = *myFreeList;
              *myFreeList = q;
       }
}
template<bool threads,int inst>
void* _DefaultAllocTemplate<threads, inst>::_Refill(size_t n)     //n表示要申请的字节个数
{
       int nobjs = 20;           //向内存池申请的时候一次性申请20个
       char* chunk = _chunkAlloc(n,nobjs);    //因为现在链表中没有，所以要想内存池中申请，多余的再挂到自由链表下面
       if (1 == nobjs)          //只分配到了一个对象
       {
              return chunk;
       }
       _Obj* ret = (_Obj*)chunk;                  //将申请的第一个对象作为返回值
       _Obj* volatile *myFreeList = _freeList+ _GetFreeListIndex(n);
       *myFreeList =(_Obj*)(chunk+n);             //将第二个对象的地址放到自由链表中
       _Obj* cur= *myFreeList;
       _Obj* next=0;
       cur->_freeListLink = 0;
       for (int i = 2; i < nobjs; ++i)             //将剩下的块挂到自由链表上
       {
              next= (_Obj*)(chunk + n*i);
              cur->_freeListLink = next;
              cur = next;
       }
       cur->_freeListLink = 0;
       return ret;
}
template<bool threads, int inst>
char* _DefaultAllocTemplate<threads, inst>::_chunkAlloc(size_t size, int& nobjs)  //向系统中申请内存
{
       char* result = 0;
       size_t totalBytes = size*nobjs;        //总共请求的内存大小
       size_t leftBytes = _endFree - _startFree;      //内存池剩余的大小
       if (leftBytes>=totalBytes)     //如果剩余的大小大于等于申请的大小，则返回这个这内存
       {
              result = _startFree;
              _startFree += totalBytes;
              return result;
       }
       else if (leftBytes>size)         //如果剩余的内存足够分配一个size,
       {
              nobjs=(int)(leftBytes/size);
              result = _startFree;
              _startFree +=(nobjs*size);
              return result;
       }
       else            //内存池中的内存已经不够一个size了
       {
              size_t NewBytes = 2 * totalBytes+_GetRoundUp(_heapSize>>4);       //内存池要开辟的新的容量
              if (leftBytes >0)  //剩余的内存挂到自由链表上
              {
                     _Obj* volatile *myFreeList = _freeList + _GetFreeListIndex(leftBytes);
                     ((_Obj*)_startFree)->_freeListLink = *myFreeList;
                     *myFreeList = (_Obj*)_startFree;
              }
              //开辟新的内存
              _startFree = (char*)malloc(NewBytes);
              if (0 == _startFree)                   //如果开辟失败
              {
                     //如果开辟失败的话，则表明系统已经没有内存了，这时候我们就要到自由链表中找一块比n还大的内存块，如果还没有的话，那就掉一级空间配置器
                     for (size_t i = size; i <(size_t)_MAXBYTES;i+=(size_t)_ALIGN)
                     {
                           _Obj* volatile *myFreeList = _freeList + _GetFreeListIndex(i);
                           _Obj* p =*myFreeList;
                           if (NULL != p)       //在自由链表找到一块内存块
                           {
                                  _startFree =(char*)p;                  
                                  //将这个内存块摘下来给内存池
                                  *myFreeList = p->_freeListLink;
                                  _endFree = _startFree + i;
                                  return _chunkAlloc(size, nobjs);  //内存池开辟好的话，就再调一次chunk分配内存
                           }
                     }
                     //要是再找不到的话，就调一级空间配置器，其中有内存不足处理机制,要是还不行的话，他会自动抛出异常
                     _endFree = NULL;
                     _startFree=(char*)malloc_alloc::_Allocate(NewBytes);
              }      
              //开辟成功的，就更新heapSize(记录总共向系统申请了多少内存),，更新_endFree
              _heapSize += NewBytes;
              _endFree = _startFree + NewBytes;
              return _chunkAlloc(size, nobjs);             //内存池开辟好的话，就再调一次chunk分配内存
       }
}
typedef _DefaultAllocTemplate<0,0>  default_alloc；

在空间配置器中所有的函数和变量都是静态的，所以他们在程序结束的时候才会被释放发。二级空间配置器中没有将申请的内存还给操作系统，只是将他们挂在自由链表上。所以说只有当你的程序结束了之后才会将开辟的内存还给操作系统。

由于它没有将内存还给操作系统，所以就会出现二种极端的情况。
- 假如我不断的开辟小块内存，最后将整个heap上的内存都挂在了自由链表上，但是都没有用这些空间，再想要开辟一个大块内存的话会开辟失败。
- 再比如我不断的开辟char,最后将整个heap内存全挂在了自由链表的第一个结点的后面，这时候我再想开辟一个16个字节的内存，也会失败。

总的来说上面的情况只是小概率情况。如果非得想办法解决的话，我想的是：针对第一条我们可以引入释放二级空间配置器的方法，但是这个释放比较麻烦。针对第二条我们可以合并自由链表上的连续的小的内存块。

二级空间配置器会造成内碎片问题，极端的情况下一直申请char，则就会浪费7/8的空间。但是整体来说，空间配置器的性能还是蛮高的。

并发内存池

设计成三层结构
第一层是Thread Cache。每一个Thread都有自己单独的Thread Cache，线程在这里申请不需要加锁。
第二层是Central Cache。这里是所有线程共享。Thread Cache是按需要从Central Cache中获取对象，它就要起着平衡多个线程按需调度的作用，既可以将内存对象分配给Thread Cache来的每个线程，又可以将线程归还回来的内存进行管理。Central Cache是存在竞争的，所以在这里取内存对象的时候是需要加锁的，但是锁的力度可以控制得很小。
第三层是Page Cache，存储的是以页为单位存储及分配的，Central Cache没有内存对象(Span)时，从Page cache分配出一定数量的Page，并切割成定长大小的小块内存，分配给Central Cache。Page Cache会回收Central Cache满足条件的Span(使用计数为0)对象，并且合并相邻的页，组成更大的页，缓解内存碎片的问题。

为了避免加锁带来的效率，在Thread Cache中使用（tls）thread local storage保存每个线程本地的Thread Cache的指针，这样Thread Cache在申请释放内存是不需要锁的。因为每一个线程都拥有了自己唯一的一个全局变量。

ThreadCache.h

#pragma once

#include "Common.h"

class ThreadCache
{
private:
    Freelist _freelist[NLISTS];//自由链表

public:
    //申请和释放内存对象
    void* Allocate(size_t size);
    void Deallocate(void* ptr, size_t size);

    //从中心缓存获取对象
    void* FetchFromCentralCache(size_t index, size_t size);

    //释放对象时，链表过长时，回收内存回到中心堆
    void ListTooLong(Freelist* list, size_t size);
};

//静态的，不是所有可见
//每个线程有个自己的指针, 用(_declspec (thread))，我们在使用时，每次来都是自己的，就不用加锁了
//每个线程都有自己的tlslist
_declspec (thread) static ThreadCache* tlslist = nullptr;

申请内存

当内存申请size<=64k时在Thread Cache中申请内存，计算size在自由链表中的位置，如果自由链表中有内存对象时，直接从FistList[i]中Pop一下对象，时间复杂度是O(1)，且没有锁竞争。
当FreeList[i]中没有对象时，则批量从Central Cache中获取一定数量的对象，插入到自由链表并返回一个对象。

释放内存
当释放内存小于64k时将内存释放回Thread Cache，计算size在自由链表中的位置，将对象Push到FreeList[i].
当链表的长度过长，也就是超过一次向中心缓存分配的内存块数目时则回收一部分内存对象到Central Cache。

Reference

https://blog.csdn.net/LF_2016/article/details/53511648
https://blog.csdn.net/qq_41562665/article/details/90546750