内存池调研与设计

2023-12-22 08:29:33

一 SGI内存池（STL内存池）

SGI内存池有两级配置器，第一级配置器其实就是执行系统内存分配函数，当内存需求没有被满足的时候会调用指定函数。它的重点在于二级配置器。

二级配置器分配策略：
1.当分配的区块大于128byte，移交第一级配置器。
2.分配的区块小于等于128byte,交给内存池管理。内存池维护16个空闲块链表，每个链表下面挂着的都是一样大小的内存块，如下图所示

这里所有空闲数据块
头部都可以解释为一个联合体：

union obj {
    union obj* free_list_link;
    char client_data[1];
}在这里插入代码片

所有空闲链表的free_list_link都指向下一个空闲数据块，而当返回数据块的时候，直接返回obj.client_data,其实就是返回了数据块的首地址（这一块没懂，直接返回obj的地址不就行了，搞个client_data是干嘛用的）。

1.1 内存分配

内存分配函数跟普通的malloc差不多：

static void * allocate(size_t n) {
    obj * __VOLATILE * my_free_list;
    obj * __RESTRICT result;
  
    if (n > (size_t) __MAX_BYTES)//大于128字节调用第一级配置器
    {
        return(malloc_alloc::allocate(n));
    }
    my_free_list = free_list + FREELIST_INDEX(n);//根据申请空间的大小寻找相应的空闲链表（16个空闲链表中的一个）
  
    result = *my_free_list;
    if (result == 0)//如果该空闲链表没有空闲的数据块
    {
        void *r = refill(ROUND_UP(n));//为该空闲链表填充新的空间
        return r;
    }
    *my_free_list = result -> free_list_link;//如果空闲链表中有空闲数据块，则取出一个，并把空闲链表的指针指向下一个数据块
    return result；
}

代码中写的很清楚，首先对n以8的倍数向上取整，假设N为70，取整到72，然后找到对应的下标72/8 - 1 = 8;如果此时链表头不为空（证明有空闲内存），将链表头移到下一个数据块，直接返回内存首地址。如果链表头为空，执行refill操作。refill稍后会详细介绍，在此先不提。

1.2 内存释放

内存释放跟内存申请相反，如果大于128BYTE，直接释放。如果小于等于128，返回给内存池，代码如下：

static void deallocate(void *p, size_t n)
{
    obj *q = (obj *)p;
    obj * __VOLATILE * my_free_list;
  
    if (n > (size_t) __MAX_BYTES)//如果空间大于128字节，采用普通的方法析构
    {
        malloc_alloc::deallocate(p, n);
        return;
    }
  
    my_free_list = free_list + FREELIST_INDEX(n);//否则将空间回收到相应空闲链表（由释放块的大小决定）中
    q -> free_list_link = *my_free_list;
    *my_free_list = q;
}

内存释放操作非常简单，这里注意到我们这边内存释放的时候会带着一个参数N，这跟我们常用的free不一样，因为我们free内存的时候其实操作系统帮我们把长度记下来了（本身使用了额外空间来记下，一般在我们指针前面的几个字节携带内存信息），这里SGI的内存池并没有使用额外的信息去存储内存信息，直接让申请内存的人保存这个信息（一般来说我们都会保存这个信息）。首先我们对N向上取整到8的倍数，计算出属于哪个池子，直接把这个内存块替换成原来的链表头。

1.3 refill操作

refill操作会尝试申请20个大小为N的块（有可能申请不到），返回一个大小为N的数据块的地址，并且会把其他块放到free_list。

static void* refill(size_t n){ 
    int nobjs = 20; // 默认分配20个区块
    char* chunk = chunk_alloc(n, nobjs); // 获得分配的内存空间
    obj* volatile * my_free_list;
    obj* result, *current_obj, *next_obj;
    // 如果只分配了一个区块，直接返回
    if (1 == nobjs) return chunk;
    // 否则将其他区块插入到free list
    my_free_list = free_list + FREELIST_INDEX(n);
    result = (obj*)chunk; // 从chunk中切分下一块
    *my_free_list = next_obj = (obj*)(chunk + n); // 将后面的区块插入到free list，n表示切割的大小
    for (int i = 1;; ++i){ // 切割内存块，并用指针相链，避免大量cookie产生
        current_obj = next_obj;
        next_obj = (obj*)((char*)next_obj + n); 
        if (nobjs - 1 == i){ // 最后一个指向空指针
            current_obj->free_list_link = 0;
            break;
        }
        current_obj->free_list_link = next_obj;
    }
    return result;
}

代码中有一个申请内存的函数：chunk_alloc,这个函数申请空间策略如下：

（1）如果内存池空间大小满足大于等20*n,直接申请成功，返回首地址，更新内存池空闲空间首地址（这里的内存池跟上面说的二级内存池不一样，这是一片内存空间，free_list的空间都是从这划出去的）。

（2）如果内存池空间大小满足大于一个块，但是小于20个块，那么也算申请成功。假设N等于16，内存池大小为16*10+8，那么相当于申请了10个块，返回第一个块给用户，剩余九个挂在free_list[1]上。如果最多满足一个块大小，那么直接返回给用户，更新内存池首地址。

（3）如果内存池一个空间都不满足，进行下面几步操作：

先将内存池剩余的空间放到合适的free_list,比如我们申请块大小为32，但是内存池大小只有16，那么把这个16分配到free_list[1]。
然后直接调用malloc申请两倍大小的N*20 + heap_size >> 4,heap_size是上一次申请内存池的大小。
如果malloc失败，就会遍历free_list中所有大于N的块，找到最接近的一个，放入内存池，当成内存池用。比如N=32,就会遍历有没有40，48，56 …
（4）如果第三步也失败了，调用第一级配置器申请内存，其实第一级配置器也是调用malloc，但是加上了自定义的malloc函数调用失败的处理函数，并且会循环申请。申请步骤如下：

调用malloc分配空间，如果成功，直接返回
如果上一步失败，调用自定义的内存不足处理函数（如果没有处理函数，直接抛出异常）
调用完自定义处理函数，返回第一步继续申请内存。
详细代码如下：

template <bool threads, int inst>
char *
    __default_alloc_template<threads, inst>::chunk_alloc(size_t size, int& nobjs) { // 内存池内存分配函数
        char * result;                                                              // nobjs通过引用传递，方便更改实际申请的内存块个数
        size_t total_bytes = size * nobjs; // 内存需求大小
        size_t bytes_left = end_free - start_free; // 内存池剩余空间
    if (bytes_left >= total_bytes) { // 内存池剩余空间完全满足需求量    
        result = start_free;
        start_free += total_bytes;
        return result;
    } else if (bytes_left >= size) { // 内存池剩余空间不能完全满足需求量，但足够供应一个（含）以上的区块 
        nobjs = bytes_left/size; // 计算最多供应的区块数
        total_bytes = size * nobjs;
        result = start_free;
        start_free += total_bytes;
        return result;
    } else { // 内存池剩余空间连一个区块的大小都无法提供
        size_t bytes_to_get = 2 * total_bytes + ROUND_UP(heap_size >> 4); // 申请大小为需求的两倍，并加上附加量
        if (bytes_left > 0) {  // 利用剩余的内存，避免碎片
            obj * volatile * my_free_list = free_list + FREELIST_INDEX(bytes_left); // 找到适合该大小的free-list
            ((obj *)start_free) -> free_list_link = *my_free_list; // 调整free list，将内存池中的剩余空间加入指定的free-list
            *my_free_list = (obj *)start_free;
        }
        // 申请堆内空间，补充内存池
        start_free = (char *)malloc(bytes_to_get);
        if (0 == start_free) { // 申请失败
            int i;
            obj * volatile * my_free_list, *p;
            for (i=size; i <= __MAX_BYTES; i+=__ALIGN) { // 寻找其它free-list手上是否有空闲的内存
                my_free_list = free_list + FREELIST_INDEX(i);
                p = *my_free_list;
                if (0 != p) { // free list内有未用块
                    *my_free_list = p -> free_list_link; // 调整free list以释放未用区块
                    start_free = (char *)p;
                    end_free = start_free + i;
                    return chunk_alloc(size, nobjs);   // 递归调用自己，为了修正nobjs
                }
            }
            end_free = 0; // 无任何空闲内存，则调用第一级配置器
            start_free = (char *)malloc_alloc::allocate(bytes_to_get);
        }
        heap_size += bytes_to_get; // 每次申请大小累加，用于附加内存申请大小的计算
        end_free = start_free + bytes_to_get; // 修改内存池
        return chunk_alloc(size, nobjs);  // 递归调用自己，为了修正nobjs
    }
}

二 dlmalloc

2.1 全局变量malloc_state:

struct malloc_state { 
  binmap_t   smallmap; 
  mchunkptr  smallbins[(NSMALLBINS+1)*2]; 
   
  binmap_t   treemap; 
  tbinptr    treebins[NTREEBINS]; 
   
  mchunkptr  dv; 
  size_t     dvsize; 
   
  mchunkptr  top; 
  size_t     topsize; 
 char*      least_addr; 
  size_t     trim_check; 
   
  size_t     magic; 
  size_t     footprint; 
#if USE_MAX_ALLOWED_FOOTPRINT 
  size_t     max_allowed_footprint; 
#endif 
  size_t     max_footprint; 
  flag_t     mflags; 
#if USE_LOCKS 
  MLOCK_T    mutex; 
#endif /* USE_LOCKS */ 
  msegment   seg; 
};
 
static struct malloc_state _gm_;

这个结构体是dlmalloc的全局管理结构体。在讲这个结构体之前，先说一下dlmalloc的分配策略，跟大部分内存池一样，都是采取了分级管理的策略（按内存大小分级管理）。

这里假设平台为32位；

（1）16-256（实际上分配都是8的倍数）. 在这个范围里面属于小块，小chunck管理（后面会详细说），也就是上面结构体中的smallbins（分箱链表）, smallmap是位图，1表示有空闲块，0表示对应链表为空

（2）>256。在这个范围属于大块，由另一种数据结构管理（树跟链表),也就是结构体中的treebins,同时treemap是位图，1表示有空闲块，0表示对应链表为空

前面四个变量主要对应上面两种不同大小的内存块分配的结构体。后面四个变量含义如下：

dv,dvsize: dv是一个特殊的内存块，当找不到空闲并且合适的小内存块时，会优先分割dv这个内存块（这里有利于相近的申请位于连续的内存块上，对程序运行速度有帮助）。dvsize描述dv内存块大小。

top,topsize:top也是一个特殊的内存块。表示当前堆空间中最顶端的内存块，这个内存块不到迫不得已不会被使用。因为这个dlmalloc释放内存给操作系统的时候是从高地址到低地址收缩，也就是说如果top被占用，即使中间有大量的空闲内存也没办法被释放。

2.2 小块分配结构体malloc_chunk

struct malloc_chunk {
  size_t               prev_foot;  /* Size of previous chunk (if free).  */
  size_t               head;       /* Size and inuse bits. */
  struct malloc_chunk* fd;         /* double links -- used only if free. */
  struct malloc_chunk* bk;
};

直观的用图体会一下这个结构：

dlmalloc会存在连续几个块都是已经被使用，但是不会存在连续几个快都是空闲块，因为连续空闲块会被合并。
解释一下上面的这个结构体每个变量的含义：
prev_foot: 这个变量其实是对上一个malloc_chunk的描述，在不同的场景，它有不同的意义：
（1）当上一个chunk为空闲块的时候，它表示是空闲块的size。
（2）当上一个块不是空闲块，如果开了内存的额外安全校验，那么这个变量会用来做校验。
注：关于这一块，我看的两篇参考资料说法不完全相同，有如下两种说法：
如果没开校验，那么这个变量没有意义，直接可以作为用户可使用的内存(这种情况下图中所示的淡蓝色部分其实也可以作为用户申请的深蓝色内存块一起被使用)
这个变量的第零位可以表示当前这块chunk是否是通过mmap申请而来。
这两种说法在上一个块是空闲块的时候并不矛盾，因为是空闲块的时候表示上一个空闲块的大小，为8的整数倍，最后一位其实没起作用。但是当被用户使用时，如果这个块可以被用户使用，那么将没有空闲的位可以作为标志位。从计算上一个chunk的宏来看：#define prev_chunk§ ((mchunkptr)( ((char*)§) - (§->prev_foot) ))，并没有对prev_foot最低位做处理，如果最低位被额外用起来的话完整的公式应该是（(char*)§) - (§→prev_foot & ~1)）
head:这个变量是对当前这个chunk的描述：
（1）最直观的意义是描述当前chunk的大小，由于dlmalloc的大小至少也是8的整数倍，所以head的最后三个bit必然用不到，所以实际上head只有前面的位才表示当前的size（head & ~3），最后三个bit用来描述其他信息。
（2）第0个位表示前一个chunk是否在使用中，1表示使用，0为空闲
（3）第1个位表示当前chunk是否在使用中，1表示使用，0表示空闲
从上面两个变量可以看出，有了这俩变量，可以很容易确定上一个块的头指针以及状态，下一个块的头指针以及状态，这样就可以很方便的合并相邻的空闲块。
fd: 链表指针指向下一个相同大小的内存块（当内存被使用时指针所占用的空闲直接当成纯粹的内存使用）
bk: 链表指针指向上一个相同大小的内存块（当内存被使用时指针所占用的空闲直接当成纯粹的内存使用）
dlmalloc的小块内存管理方式与SGI相似，都是采用了分箱管理的策略。维护32个双向链表，他们分别是8，16，24，32，40 … 256。2.1中提到的malloc_state结构体保存了一个数组名为smallbins，就是保存了这些节点的头节点。如下图所示：

关于内存的具体分配与释放较为复杂，放到下面再讲。

2.3 malloc_tree_chunk

对于大于256的内存由malloc_tree_malloc管理，结构体定义如下：

struct malloc_tree_chunk {
  /* The first four fields must be compatible with malloc_chunk */
  size_t                    prev_foot;
  size_t                    head;
  struct malloc_tree_chunk* fd;
  struct malloc_tree_chunk* bk;
  
  struct malloc_tree_chunk* child[2];
  struct malloc_tree_chunk* parent;
  bindex_t                  index;
};

malloc_tree_malloc前面四个变量与之前的的malloc_chunk结构相似，但是后面多了四个变量，左右子节点，以及父节点，还有分箱号

malloc_tree_malloc也是分箱管理，2.1中malloc_state结构体中的treebins[NTREEBINS]数组就是箱子数组，箱子个数为32。但是这里的箱子不再向上面的小块箱子一样每个箱子都是固定大小块的链表，而是一个区间大小的块的链表头的树。结构如下所示：

32个箱子负责的范围如下表（只画了24个）：

这里的树（两篇资料说的不一样），以第一个箱子为例，资料分别列出如下两种结构：

这里资料有说到原作者对树的形容：左边节点小于右边节点的值，并且左右子树也是相同的结构，当前节点不保证与两边子节点的大小关系。

博客作者将这个树称为类似于Trie树（字典树）结构，从图来看，明明是个区间树（转载自https://blog.csdn.net/weixin_34007886/article/details/91999395）

这个图感觉是一颗AVL树。。。

第一个图虽然画成了区间树，但是大致描述了工作原理，看看第一个图作者的分析如下：

看完上面这段话我才懂了为啥说这是一个类似于字典树的结构，下面画个图解释一下上面这段话：

比如搜索314， 314二进制表示为0b100111010,然后就是前缀匹配

插入的过程：
（1）如果当前的节点为空，那么直接将内存块放在该节点。
（2）如果节点不为空，且节点值等于要插入内存块大小，直接放入链表
（3）如果节点不为空，且节点值不等于插入内存块大小，按前缀匹配结果进入左子树或者右子树，再次进入循环，重复（1）（2）（3）

2.4 segment

段是对真正大块内存的描述，主要描述非连续分配的大内存（这个字段也是malloc_state的成员之一），结构如下：

struct malloc_segment {
  char*        base;             /* base address */
  size_t       size;             /* allocated size */
  struct malloc_segment* next;   /* ptr to next segment */
  flag_t       sflags;           /* mmap and extern flag */
};

字段base表示该segment段的起始地址，size表示该segment段的大小，sflags是一个标记字段（两个标记，一个用于标记该segment段是否为通过mmap申请，一个用于标记该segment段是否已经分配），而字段next用于指向下一个segment段，从而形成单链表结构。记录该单链表表头的变量同样定义在结构体malloc_state内。多个segment段是通过next形成单链表结构来组织管理的，dlmalloc也没有对它们做其它特别的索引处理，因此查找某一个segment段需要在该单链表内线性扫描查找，不过大多数情况下，segment段应该是非常少的，所以并不会造成多大的性能损失。

2.5 小内存块申请

小内存块是指小于256的内存块，申请过程如下：
（1）从malloc_chunk分配：找到内存块对应的箱子，如果当前箱子或者相邻大八个字节的箱子不为空，取走一块返回给用户。否则进入第二步
（2）从dv内存块分配（1.1malloc_state里的特殊成员）：如果dv(1.1malloc_state结构体的成员)内存块大于当前申请的内存，那么从dv内存块切割一块下来返回给用户，更新dv内存块指针以及大小。如果dv内存不够（那证明一定小于256），将dv内存块挂到格式的链表上，进入第三步
（3）从其他链表分配：遍历比当前箱子大至少16字节的所有链表，比如当前是128，那么遍历144，152，160… 找到最接近申请大小的内存块（也就是第一个不为空的箱子的内存块），分割成两块，一块交给用户，剩下的作为dv内存块（在第二步dv内存块被挂到合适的链表里去了，所以此时的dv内存块是空）。如果所有的箱子都没找到内存块，那么进入第四步。
（4）从tree bins分配：因为tree bins所有内存块都大于256，所以找出一个最小的内存块分割成两块，一块交给用户，剩下的用作dv内存块。如果tree bins也是空，那么进入第五步。
（5）从top内存块分配（1.1malloc_state里的特殊成员）：如果top内存块大于申请内存，则割一块返回，否则进入下一步。
（6）向内核申请。

2.6 大内存块申请

这里的大内存块指大于等于256.
（1）从tree bins里面申请：如果有正好这个大小的内存块（对齐之后的大小），直接从链表取出一个返回。如果没有，找一个最接近大小的，分成两部分，一部分返回给用户，一部分挂到malloc_chunk或者tree bins(看剩余大小是否超过256)
（2）从top分配：如果足够大，返回一块。否则进入下一步。
（3）从系统申请（这里如果申请的空间大于mmap界限，优先使用mmap申请，否则直接在当前内存上扩展（如果扩展失败，在mmap）, 如果不超过界限，优先使用扩展（失败后再mmap））

2.7 内存释放

内存释放的时候，不同属性大小的内存块会有不同处理，如果是由mmap映射的内存（非连续内存），直接释放。否则进入如下步骤：
（1）计算当前释放内存大小以及边界以及做一些检测，判断相邻内存是否是空闲内存，如果不是直接归还，插入链表。如果是，合并。然后进入下一步。
（2）被合并的块如果属于dv块，更新dv块大小。如果此时的被释放内存挨着top块，那么内存并入top并且把dv清零,并且当top块达到一定程度，会收缩，释放一部分。
（3）被合并的块不是特殊块，从链表摘除被合并的块，再将新的块插入链表合适的位置

三 TCMalloc

tcmalloc(thread cache malloc),从名字可以看出来，是一个针对线程进行优化的内存分配器。事实上也确实如此，TCmalloc在多线程场景小内存分配效率远远高于ptmalloc(glibc的内存分配器，很多实现跟dlmalloc相似)。tcmalloc的内存分配也是分级管理，下面分别介绍。

3.1 Front-end

(1) threadcache
threadcache是用于小内存分配，每个线程的小内存分配都会优先从threadcache里分配，这样就避免了使用锁做线程同步。因此在多线程场景内存分配会非常快。thread cache的结构跟SGI小内存分配方式非常像，也是分成若干不同的箱子，然后每个箱子下面都是以链表的方式挂着相同大小的内存块，而且这些内存块都没有头，只有指向下一个的指针（跟SGI一样，当内存被使用的时候，指针会被当成可用内存，这样就不会浪费）。但是它的箱子跟SGI不同地方在于，SGI箱子大小是等间隔增长（8byte）,tcmallo不是等间隔增长的，tcmalloc有60-80多个箱子，具体可配，先密后疏，越大的内存块之间间隔越大。具体可以看https://github.com/google/tcmalloc/blob/master/tcmalloc/size_classes.cc

(2) pre-CPU模式

这种模式下各个线程通过Restartable Sequences同步，这个函数是用汇编写的，如果线程在执行的过程中，CPU被抢占，下次运行的时候，会从函数头重新开始运行。

3.2 Middle-end

Middle-end负责为Front-end提供内存，将内存返还给Back-end。Middle-end包括Transfercache和Central free list
（1） Transfer cache
github说明文档上表示，当front-end,也就是前段缓存需要返还内存到中端（Middle-end）或者向中端申请内存的时候，首先会访问传输缓存（Transfer cache），传输缓存保存了一个指向空闲内存的指针数组，它可以快速的把object移动到这个数组，或者快速的从数组获取一个对象返还给前端。它的名字由来真是因为可以让内存块在两个不同的线程中快速流动。当传输缓存无法满足需求，才会访问Central free list。
Central free list申请跟释放比Transfer cache慢,下面会说.
Transfer cache 是一个指针数组:

这里展现的是单链表,实际上是数组的链表,应该也是数组分箱模式.否则顺着链表一个个遍历,效率实在谈不上高.slot定义如下:

（2）Central free list
CenterCache有多个Central free list,每个Central free list 由span组成的链表构成,每个span都会被分割成相同大小的object(这里Central free list 管理的都是同样大小的object).
Central free list可以由下图表示：

在讲这个图之前，先说tcmalloc的两个概念:

第一个是“page”，也就是页的概念，每一个页大小是固定的4kb(或者8kb),上面thread cache的小对象都是从页里面分裂出来的.
第二个是"span", 每一个span都是一个或者多个连续的page组成.

Central free list中有两个链表,一个是nonempty链表,一个是empty链表,empty链表挂着的是完全没有空闲块的span.当内存申请时,通过refcount发现当前的span对象已经全部被分配完了,将span移入empty,当内存释放时,将span移回noempty.
从图中可以看到绿色部分是链表结构体对象,object指向一串object对象(都是相同大小的),refcount引用当前span的对象的个数.每个绿色部分都代表span对象,上面挂着由这个span分裂出来的object.

3.3 Back-end

Back-end负责以下工作:

管理大量未使用内存
当没有合适内存可使用时,负责从操作系统申请内存
当空闲内存过多,归还空闲内存给操作系统
这里有两种内存管理.
一种是Legacy Pageheap,由一串不同大小的span组成,如图:

它们是可以分裂的,比如假设现在只有128page大小的链表不为空,申请4个page,那么摘下一个128page的span,分裂成4跟124,然后4page大小返回给用户,124挂到124page对应的链表.在释放span的时候,相邻的span也是可以合并的,这个后面会提到.PageHeap有两个两个freelist，一个事normal，一个是return，以区别活跃跟不活跃的内存。PageHeap并不会直接将内存还给系统，而是攒够一批还给系统。在PageHeap里多余的内存会进入return链表，跟normal隔离，这样normal链表总是优先被使用。内核在内存不够的时候，优先将return链表的内存swap掉（啥意思）。当span进入return链表，tcmalloc做了一个附加操作，madvise(MADV_DONTNEED),试图告诉内核这些内存已经不用了.

还有一种是超大内存管理,hugepage(通常大于2M,感兴趣可以看GitHub文档: https://google.github.io/tcmalloc/temeraire.html)

3.4 内存申请

小内存申请:

对齐size,找到threadcache中对应的链表,如果满足条件,返回.否则进入下一步
尝试在CentralCache的transfer cache分配batch_size(不同大小batch_size不同,详细可见:https://github.com/google/tcmalloc/blob/master/tcmalloc/size_classes.cc) 个object,如果成功一个返回给用户,其他的加到threadcache.
尝试在size_class对应Central free list 尽量分配batch_size个object(不满足batch_size个也没关系只要大于等于一个就行),如果成功返回一个给用户,剩余挂到thread cache.否则进入下一步
向PageHeap申请一个span.对应的class_size申请的span应该包含多少个连续的page是预先设置好的,拿到span后拆分成N个object
- PageHeap先从npage大小对应的链表中查找空闲span(先normal 后return),如果失败进入下一步
- 在更大的npage中寻找,也就是上面我说的分裂.如果失败进入下一步
- 向内核申请可能大于npage大小的内存.返回所需内存,剩余放回链表

大内存申请:
第一步就是直接向pageheap申请.后面流程与小内存一致

3.5 内存释放

每个object都可以通过地址找到自己属于哪个span(通过基数树,后面再说),而每个span分裂出来的object都是固定大小的object,所以可以通过span知道所释放的内存大小是多少.如果class_size为0,那么代表指针所指向的事大块内存.
1.小内存释放:

将内存插入到thread cache对应class_size的链表(front-end)
如果链表长度超过阈值或者thread_cache大小超过阈值,触发回收机制.(middle-end)
object被回收到对应的CentralFreeList上(前面说过,每个CentralFreeList里的所有object都是一样大的,也就是CentralFreeList是跟class_size一一对应的),如果object数量达到bach_size并且Transfercache没有满,那么优先放入Transfercache.否则回收到CentralFreeList对应的span链表.(每个object对应唯一的span,可以通过基数树查找)
如果span下面的object都被回收了(refcount为0,代表没有人引用他了),进一步将其释放到PageHeap(back-end)
- 如果基数树上找到span并且发现此span之前或者之后的span也是空闲并且处于normal链表执行合并操作
- 否则将span回收到return链上,并且继续合并都在return链上的span
大块内存:
大块内存直接就是一个span,对比小块而言少了查询span的操作.直接进入middle-end释放,之后跟小块相同
上面一直说object可以直接找到所属span,那么是怎么找到的呢.首先span是由page组成的,span有第一个page的信息以及包含多少个page,由于每个page大小是固定的,都是4k的整数倍,所以通过object地址很容易确定pageID。tcmalloc有一个pagemap记录着pageID到span的映射如下图：

这是官方的图,这么看可能有些懵圈.再放一张博客老哥（https://blog.csdn.net/zwleagle/article/details/45113303）发的图跟解释,可能会懂一些.

其实大意就是整个操作系统可分配的地址是64位,最高16位不用,假设每个页8k(13位),那么最多存在2的35次方个8K页
转换到32操作系统，4K页面（32位用的是两级基数树），更好分析，32位操作系统最多有（2^32/212）2^{20个4K的页。先以最简单的例子举例，假设基数树只有一级，那么退化成数组，那么这个数组大小为2}20次方,数组的序号就是对应的页表ID。所以现在不妨用两级基数树来考虑（RadixTree, 字典树变种https://zh.wikipedia.org/wiki/%E5%9F%BA%E6%95%B0%E6%A0%91）

现在看上面的图,假设我们将2^20个page映射到二级基数树中,第一个数组大小为1024,数组index为N的格子对应着pageID范围为[index1024 , index1024 + 1024)的页面.其实就是用了两级映射,用一个数组或者hash表可以达到同样的效果,但是用多级数组来映射有两个好处:

比直接用一个数组节省内存.因为二级数组是实时new出来的,做个简单的假设,假设目前所有的页ID都在1-1024*3范围内，那么就只会有前三个格子指针被真的new出来了，后面格子的指针全为空。
hash表无法快速定位旁边的span是否可以跟当前span合并.因为span不一定是连续的.但是当前这个结构可以,比如现在归还了page2,向左右两个page查看,发现左边的page1指针不为空且不是同一个span,这代表左边的span地址跟当前的page2所属的span地址连续,那么就可以在两个span都空闲的情况下合并span.
注:其实我觉得hash表加排序set也可以快速实现这个功能,不过hash表在数量较大的情况下冲突太严重.

注:tcmalloc回收阈值，以及每次内存不足分配的数量还有很多细节以及策略,篇幅有限,不作细表,有兴趣可以看参考资料

四 Jemalloc

TODO

五音频数据内存池设计

5.1 内存池设计需要关注的点

通过前面的内存池的调研，我们知道内存池的使用需要注意以下几个点：

怎么样避免内存碎片
怎么样尽可能少的使用额外内存去记录内存信息
快速申请内存，并且合理利用局部性原理（相邻时间申请的内存尽可能处于相邻地址，尤其是小块内存）
快速归还内存，并且在归还的同时需不需要合并相邻的空闲内存
当内存使用率很低时（池子中被使用的内存远小于池子中的空闲内存），需不需要归还给操作系统，怎么快速归还

5.2 音频数据内存池的需求

音视频数据相对而言都是比较大的块，并且大小相对固定（比如webrtc中音频基本都是10ms的倍数,采样率也只有16k,32k,44.1k,48k这几种）,所以我们这边学习SGI的内存设计方式基本可用，不过SGI没有合理的归还机制，因为它的内存池都是小块内存，但是我们这边内存都是大块，如果使用率很低的时候没有及时归还，会造成很大的浪费，因此我们在SGI的基础上要设计一个合理的归还机制。
首先一个大体的设计层次如下：只有两层。

一级内存池由一块一块的超大块内存组成，当申请的大小超过kSecondAllocateArrSize个block大小直接走一级内存池（block是申请的最小单位，比如音频可以设置为16K * sizeof(int16) * 10ms / 1000 = 320）。
当申请内存小于kSecondAllocateArrSize个block，走二级内存池，二级内存池类似于SGI的二级内存池，分箱管理。

这里定义几个结构体用来管理内存池,记录内存池状态:

constexpr size_t kMinBlockSize = 160; // block最小值
constexpr size_t kSecondAllocateArrSize = 10; //二级配置器的向量长度
constexpr size_t kMinPercentForFree = 40; // 使用率低于40,尝试释放空闲大内存块给系统;
constexpr size_t kApplyCountOfBlock = 10; // 当二级配置器向一级配置器申请内存时,一次申请10个block大小的内存挂到箱子里
 
 
struct PrimaryAllocate {
  // 当前内存指向的地址
  void* head;
  // 当前内存空闲块的首地址
  void* top_ptr;
  // 当前大块内存大小
  size_t size;
  // 当前大块内存有多少被使用了
  size_t in_use;
};
struct SecondAllocate {
  // 当前内存的大小,最后三位模仿dlmalloc,最低位代表是否是大块内存,倒数第二位代表是否在被使用
  size_t size;
  SecondAllocate* front;
  SecondAllocate* next;
};
 
struct MemoryState {
  // 申请的所有内存的大小
  size_t all_memory_size;
  //当前有多少内存在使用中
  size_t in_use_size;
  // 一级分配器管理的内存
  std::vector<PrimaryAllocate> primary_allocate;
  // 如果一级内存中某大块内存全部被归还到内存池,那块内存会被放入到这个数组里
  std::vector<PrimaryAllocate> empty_allocate;
  // 二级分配器管理的内存
  SecondAllocate* second_allocate_arr[kSecondAllocateArrSize];
};

5.3 内存申请过程

大块内存申请
遍历第一级配置器,如果有一块大块内存剩余可分配满足条件,直接分配. 否则进入下一步(这个地方是否可以找最接近的一块,可以避免碎片)
看空闲列表是否有空闲大内存,如果有且符合条件,直接拿出来使用,否则进入下一步
向系统申请一个大片内存(具体申请大小的策略待补充)
小块内存申请
如果二级配置器对应大小有满足条件的块,直接返回,否则进入下一步
在第一级配置器尽可能寻找kApplyCountOfBlock个块大小的内存(尽可能是指至少一个,跟SGI策略差不多)，否则进入下一步
在相邻的箱子里找到第一个大于的块，分割挂到当前申请大小对应的箱子，然后返回块。如果还不满足条件，进入下一步
向系统申请大片内存，再回到第二步分配。

5.4 内存释放过程

更新归还内存的信息，如果发现当前所在大片内存已经全部被释放，二级配置器中属于当前大片内存的block全部移除，将整个大内存移到空闲列表
如果发现当前内存使用率低于设定阈值，看空闲列表是否有内存，释放一部分（具体释放多少 TODO 策略）
是否需要根据当前大块的信息合并相邻块，更新空闲头指针（跟dlmalloc的top有点像，只不过这边是当前大块的top,还是说在当需要申请大块内存的时候,再按需收缩top）.

六参考资料

https://blog.csdn.net/a987073381/article/details/52245795 SGI
https://zhuanlan.zhihu.com/p/280706845 SGI
https://blog.csdn.net/weixin_34007886/article/details/91999395 dlmalloc
http://blog.sina.com.cn/s/blog_5674d18801019x0f.html dlmalloc
https://github.com/google/tcmalloc/blob/master/docs/design.md tcmalloc
https://zhuanlan.zhihu.com/p/29216091 tcmalloc
https://blog.csdn.net/weixin_40486544/article/details/108271451 tcmalloc
https://www.cnblogs.com/cobbliu/articles/10854226.html tcmalloc
https://blog.csdn.net/zwleagle/article/details/45113303 tcmalloc

码农公寓

内存池调研与设计

目录

一 SGI内存池（STL内存池）

1.1 内存分配

1.2 内存释放

1.3 refill操作

二 dlmalloc

2.1 全局变量malloc_state:

2.2 小块分配结构体malloc_chunk

2.3 malloc_tree_chunk

2.4 segment

2.5 小内存块申请

2.6 大内存块申请

2.7 内存释放

三 TCMalloc

3.1 Front-end

3.2 Middle-end

3.3 Back-end

3.4 内存申请

3.5 内存释放

四 Jemalloc

五音频数据内存池设计

5.1 内存池设计需要关注的点

5.2 音频数据内存池的需求

5.3 内存申请过程

5.4 内存释放过程

六参考资料

码农公寓

目录

一 SGI内存池（STL内存池）

1.1 内存分配

1.2 内存释放

1.3 refill操作

二 dlmalloc

2.1 全局变量malloc_state:

2.2 小块分配结构体malloc_chunk

2.3 malloc_tree_chunk

2.4 segment

2.5 小内存块申请

2.6 大内存块申请

2.7 内存释放

三 TCMalloc

3.1 Front-end

3.2 Middle-end

3.3 Back-end

3.4 内存申请

3.5 内存释放

四 Jemalloc

五 音频数据内存池设计

5.1 内存池设计需要关注的点

5.2 音频数据内存池的需求

5.3 内存申请过程

5.4 内存释放过程

六 参考资料

相关文章

五音频数据内存池设计

六参考资料