高级内存管理

前言

说到内存管理，就得提到内存池,gc垃圾回收以及malloc底层实现。本篇主要剖析内存池，通过分析经典的memcached的内存池设计来了解了解内存池的内部实现和优劣点。

memcached概述

memcached是一种分布式高速缓存中间件，相比较redis是更早期的缓存中间件。它的内存池使用的是slab机制。这里使用的是1.6.16版本，源码文件是slab.c。

在讲slab机制前先来说说几个概念，以及后面的源码精简了下只保留和本主题有关的内容。

item

• item 是memcached存储的最小单元
• item 存储memcached里的key和value
• HashTable 和 LRU链表结构都依赖item来进行的

总之item就是我们使用memcached最基础的数据单元

代码如下：

typedef struct _stritem {
    /* Protected by LRU locks */
    struct _stritem *next;
    struct _stritem *prev;
    ...
    uint8_t         slabs_clsid;/* which slab class we're in */
    uint8_t         nkey;       /* key length, w/terminating null and padding */
    /* this odd type prevents type-punning issues when we do
     * the little shuffle to save space when not using CAS. */
    union {
        uint64_t cas;
        char end;
    } data[];
    /* if it_flags & ITEM_CAS we have 8 bytes CAS */
    /* then null-terminated key */
    /* then " flags length\r\n" (no terminating null) */
    /* then data with terminating \r\n (no terminating null; it's binary!) */
} item;

省略了和本主题无关的字段， 剩下的字段 next, prev 这个事链表的前后指针，slabs_clsid 是 slab class的 id表达该item在哪个slab class里面

slabclass 内存分配的数据结构

代码如下：

typedef struct {
    //当下可以存储的最大的item的大小
    unsigned int size;      /* sizes of items */
    //当下可以存的item的数量
    unsigned int perslab;   /* how many items per slab */

    //空闲的未使用的item链表
    void *slots;           /* list of item ptrs */
    //总共的空闲链表的item数量
    unsigned int sl_curr;   /* total free items in list */
    //已经分配了多少个item
    unsigned int slabs;     /* how many slabs were allocated for this class */

    //这个字段实际上可以理解成item指针的数组，每个数组元素的item指针都是指向一个item链表。记录之前分配给该slab的一个完整page(大小1Mb)
    void **slab_list;       /* array of slab pointers */
    //上面这个数组的大小
    unsigned int list_size; /* size of prev array */
} slabclass_t;

//总共64个slabclass
static slabclass_t slabclass[MAX_NUMBER_OF_SLAB_CLASSES];

• memcached会初始化64个slabclass_t结构。下标为0的特别说明一下这个是给-e参数指定文件。然后内存会按照page为单位预先分配到0的 slabclass_t里面，这里只是提一下，默认机制里不使用这玩意。
• 这里有个chunk的概念的，每个slabclass_t是存储一系列大小相同的chunk，然后每一个chunk里面存实际的item
• slabclass_t数组从1开始指定存储的chunk大小是96Byte，然后到下标63(如果能到chunk有最大值控制默认512KB)，依次乘以1.25（setting.factor 通过-f来修改），这里最后一个64下标直接存默认512KB（settings.slab_chunk_size_max）
• 每个slabclass只存小于等于它chunk的item,比如slabclass[1]是96Byte slabclass[2]是120Byte，那么100Byte的item就会分配在slabclass[2]里面。当然这里有内存浪费
• 每次分配给slabclass内存的时候是按照page（默认1mb）为单位整体分配给它的

接下来在画slabclass内存图之前，先来说明一下经典的内存池技术嵌入式指针。

图中要说明的是这个小的内存块，分配出去后就完全可以当做一个新的结构体使用,可以无视原来的指针字段。

最重要的字段就是slots用于挂载空闲链表。当有需要就从这里分配给应用。

源码分析

slabclass的初始化slabs_init

这里删减了一些大页预分配内存以及memcache设定内存文件用于热启动的一些机制代码，只保留最核心的内存池代码

/**
 * Determines the chunk sizes and initializes the slab class descriptors
 * accordingly.
 */
void slabs_init(const size_t limit, const double factor, const bool prealloc, const uint32_t *slab_sizes, void *mem_base_external, bool reuse_mem) {
    int i = POWER_SMALLEST - 1;
    unsigned int size = sizeof(item) + settings.chunk_size;

    ...

    memset(slabclass, 0, sizeof(slabclass));

    while (++i < MAX_NUMBER_OF_SLAB_CLASSES-1) {
        if (slab_sizes != NULL) {
            if (slab_sizes[i-1] == 0)
                break;
            size = slab_sizes[i-1];
        } else if (size >= settings.slab_chunk_size_max / factor) {
            break;
        }
        //这里进行内存对齐
        /* Make sure items are always n-byte aligned */
        if (size % CHUNK_ALIGN_BYTES)
            size += CHUNK_ALIGN_BYTES - (size % CHUNK_ALIGN_BYTES);

        //每个slabclass存储最大的item大小
        slabclass[i].size = size;
        //每个slabclass可以一页有多少个item
        slabclass[i].perslab = settings.slab_page_size / slabclass[i].size;
        if (slab_sizes == NULL)
            size *= factor;
        if (settings.verbose > 1) {
            fprintf(stderr, "slab class %3d: chunk size %9u perslab %7u\n",
                    i, slabclass[i].size, slabclass[i].perslab);
        }
    }

    //处理最大的这个slabclass,size取最大size配置,默认是512KB,perslab为2
    power_largest = i;
    slabclass[power_largest].size = settings.slab_chunk_size_max;
    slabclass[power_largest].perslab = settings.slab_page_size / settings.slab_chunk_size_max;
    if (settings.verbose > 1) {
        fprintf(stderr, "slab class %3d: chunk size %9u perslab %7u\n",
                i, slabclass[i].size, slabclass[i].perslab);
    }

    ...
}

这里就是slab的初始化过程,从slabclass[1]一直遍历到最大power_largest，对每一个slabclass指定size和perslab,这里可以看到是可以外部自己指定slabclass大小（就是代码里slab_sizes参数）, 最大的size不能超过settings.slab_chunk_size_max，默认是512KB。

do_slabs_alloc 分配item

//分配一个slab
void *slabs_alloc(size_t size, unsigned int id,
        unsigned int flags) {
    void *ret;

    pthread_mutex_lock(&slabs_lock);
    //需要分配的size和 哪个slabclass id 就是slabclass数组下标，这两个值是对应的
    ret = do_slabs_alloc(size, id, flags);
    pthread_mutex_unlock(&slabs_lock);
    return ret;
}

static void *do_slabs_alloc(const size_t size, unsigned int id,
        unsigned int flags) {
    slabclass_t *p;
    void *ret = NULL;
    item *it = NULL;

    ...
    
    //获取指定的slabclass
    p = &slabclass[id];
    assert(p->sl_curr == 0 || (((item *)p->slots)->it_flags & ITEM_SLABBED));

    assert(size <= p->size);
    /* fail unless we have space at the end of a recently allocated page,
       we have something on our freelist, or we could allocate a new page */
    //sl_curr就是当前slabclass还有多少剩余chunk可以分配，后面flag判定是rebalance机制使用可以这里无视它。然后do_slabs_newslab进行分配
    if (p->sl_curr == 0 && flags != SLABS_ALLOC_NO_NEWPAGE) {
        do_slabs_newslab(id);
    }

    //从空余的slots链表上取下一个节点分配给应用
    if (p->sl_curr != 0) {
        /* return off our freelist */
        it = (item *)p->slots;
        p->slots = it->next;
        if (it->next) it->next->prev = 0;
        /* Kill flag and initialize refcount here for lock safety in slab
         * mover's freeness detection. */
        it->it_flags &= ~ITEM_SLABBED;
        it->refcount = 1;
        p->sl_curr--;
        ret = (void *)it;
    } else {
        ret = NULL;
    }

    ...
    return ret;
}

这个代码还是很清晰的。Memcached分配一个item会进行调用slabs_alloc。实现里会先检查对应的slabclass的空闲列表有没有chunk，有就进行分配，如果没有的话，会先进行调用do_slabs_newslab进行该slab分配。

do_slabs_newslab分配，先看代码

static int do_slabs_newslab(const unsigned int id) {
    slabclass_t *p = &slabclass[id];
    slabclass_t *g = &slabclass[SLAB_GLOBAL_PAGE_POOL];
    
    //这里默认是使用pagesize (1MB), 另外一种选项可以节省点内存，简单提一下，一个是内存进行Rebalance机制(这个主要是进行slabclass可以把分配给自己不用的页置换给别人)另一个是允许chunk（这个是让一个item可以突破单个chunk大小限制）下不允许这样，
    int len = (settings.slab_reassign || settings.slab_chunk_size_max != settings.slab_page_size)
        ? settings.slab_page_size
        : p->size * p->perslab;
    char *ptr;

    ...

    //grow_slab_list 是扩充slabclass里面的slab_list
    //get_page_from_global_pool是从 slabclass[0]里取page
    //memory_allocate通常行为就是调用系统的malloc申请一页的内存，当然开启其他机制的时候有变化这里就不细说了
    if ((grow_slab_list(id) == 0) ||
        (((ptr = get_page_from_global_pool()) == NULL) &&
        ((ptr = memory_allocate((size_t)len)) == 0))) {

        ...
        return 0;
    }

    // Always wipe the memory at this stage: in restart mode the mmap memory
    // could be unused, yet still full of data. Better for usability if we're
    // wiping memory as it's being pulled out of the global pool instead of
    // blocking startup all at once.
    memset(ptr, 0, (size_t)len);
    //把申请到的该页，改造成内存链表挂载到该slabclass的slot空闲链表上面
    split_slab_page_into_freelist(ptr, id);

    //用slab_list记录下，目前的主要的slab机制里用不到这个东西，它主要是用于rebalance。
    p->slab_list[p->slabs++] = ptr;
    ...

    return 1;
}

static void split_slab_page_into_freelist(char *ptr, const unsigned int id) {
    slabclass_t *p = &slabclass[id];
    int x;
    //遍历该slabclass一个page所有的chunk，把它们全部挂载到slot上面
    for (x = 0; x < p->perslab; x++) {
        do_slabs_free(ptr, 0, id);
        ptr += p->size;
    }
}

static void do_slabs_free(void *ptr, const size_t size, unsigned int id) {
    slabclass_t *p;
    item *it;

    ...
    
    p = &slabclass[id];

    it = (item *)ptr;
    if ((it->it_flags & ITEM_CHUNKED) == 0) {
        it->it_flags = ITEM_SLABBED;
        it->slabs_clsid = id;
        it->prev = 0;
        it->next = p->slots;
        if (it->next) it->next->prev = it;
        p->slots = it;

        p->sl_curr++;
    } else {
      ...
    }
    return;
}

do_slabs_newslab所做事情

• 申请1个page的内存
• 重置内存值
• 把申请到的page进行嵌入式链表化处理，然后挂载到该slabclass slots上面
• 修改相应的值 slab_list

slabs_free释放一个item

//传入item指针ptr, size和slabclass的id 进行chunk释放
void slabs_free(void *ptr, size_t size, unsigned int id) {
    pthread_mutex_lock(&slabs_lock);
    do_slabs_free(ptr, size, id);
    pthread_mutex_unlock(&slabs_lock);
}


static void do_slabs_free(void *ptr, const size_t size, unsigned int id) {
    slabclass_t *p;
    item *it;

    ...
    //找到对应的slabclass
    p = &slabclass[id];

    it = (item *)ptr;
    if ((it->it_flags & ITEM_CHUNKED) == 0) {
        //回收到slots链表
        it->it_flags = ITEM_SLABBED;
        it->slabs_clsid = id;
        it->prev = 0;
        it->next = p->slots;
        if (it->next) it->next->prev = it;
        p->slots = it;

        p->sl_curr++;
    } else {
        ...
    }
    return;
}

释放item，主要做的事情

• 找到slabclass
• 该item插入到该slabclass的slots链表上
• 进行slabclass相应值sl_cur修改

slabclass在回收内存的时候只是回收到自己的slab机制里，并不会调用free把它还给操作系统。考虑这样一个场景比如我一直使用slabclass[1]的内存。然后用满了然后全部删除，这时候内存全部还给slabclass[1]，但是我想放入一个大的item就会没法分配(因为slabclass大的想要申请page没有了)

这里memcached提供了内存页重分配机制处理。memcached是把不怎么使用的slabclass i 里的页重分配给 slabclass j,然后一页整体划过去，上面的已经存在的数据需要进行处理。内部也有机制判别啥时候i划给j。这里只是提一下，有兴趣可以看看slab.c 里面的slab_rebalance_thread

总结

memcached的内存机制

优点：

• 速度极快，我们可以看到分配时候直接取slot上面的chunk即可。基本不需要经过系统级malloc调用。尤其是开启预分配large page时候，抢占式开始就申请完整的内存。后面无需任何malloc
• 效率高，避免了内存碎片产生，这套算法避免了在整块内存里进行不规则切割，会把连续的内存切的稀碎导致申请要去寻找合适的位置。这里分配好就固定下来了就直接使用，回收后不会在进行复杂的重新调整避免了碎片

缺点：

• 浪费内存， 这里是以chunk为单位的。并不会以item的size就行恰好的分配。会有内存的浪费
• 使用了就抢占了，不能把内存还给操作系统给其他应用使用。

写在最后，欢迎有任何建议和想法或者指出哪里写的不足的地方的童鞋联系我~~~