转载：Memcached源码分析之内存管理（1.3）

四 源码分析

memcached-1.2.8版本

4.1 do_slabs_newslab

前面说过每个 slabclass 都拥有一些 slab, 当所有 slab 都用完时, memcached 会给它分配一个新的 slab, do_slabs_newslab 就是做这个工作的.

//为每一个slab分配内存
static int do_slabs_newslab(const unsigned int id) {
    slabclass_t *p = &slabclass[id];
#ifdef ALLOW_SLABS_REASSIGN
    int len = POWER_BLOCK;
#else
    int len = p->size * p->perslab;
#endif
    char *ptr;

//分配内存
//在第一次分配slab内存时，执行memory_allocate()
    if ((mem_limit && mem_malloced + len > mem_limit && p->slabs > 0) ||
        (grow_slab_list(id) == 0) ||
        ((ptr = memory_allocate((size_t)len)) == 0))
    {
        //

        MEMCACHED_SLABS_SLABCLASS_ALLOCATE_FAILED(id);
        return 0;
    }

    memset(ptr, 0, (size_t)len);

//指向空闲的item
    p->end_page_ptr = ptr;
    p->end_page_free = p->perslab;

//slab_list指向的是当前class中分配的各个slab
    p->slab_list[p->slabs++] = ptr;
    mem_malloced += len;

    MEMCACHED_SLABS_SLABCLASS_ALLOCATE(id);
    return 1;
}

分配一个新的 slab, 必须把该 slab 的首地址安插在 slab_list 数组中, 所以先调用 grow_slab_list 来确保 slab_list数组有足够的容量, 如果容量不足, grow_slab_list 会对 slab_list 扩容. 然后调用 memory_allocate 分配 1M 的内存空间, memory_allocate 从预先分配的内存取下 1M 大小的空闲内存块,作为新的 slab. 最后调整 end_page_ptr, 新分配的 slab 全部都是空闲内存块, 所以 end_page_ptr 指向新 slab 的首地址.这个新 slab 的首地址也被安插在 slab_list 数组中.

4.2 do_slabs_alloc

这个函数从指定的 slabclass, 即 slabclass[id], 分配大小为 size 的内存块供申请者使用.分配的原则是, 优先从 slots 指向的空闲链表中分配, 空闲链表没有, 才从 slab 中分配一个空闲的 chunk.

/*@null@*/
//分配一个item
void *do_slabs_alloc(const size_t size, unsigned int id) {
    slabclass_t *p;
    void *ret = NULL;

//边界条件判断
    if (id < POWER_SMALLEST || id > power_largest) {
        MEMCACHED_SLABS_ALLOCATE_FAILED(size, 0);
        return NULL;
    }

//指向slab class
    p = &slabclass[id];
    assert(p->sl_curr == 0 || ((item *)p->slots[p->sl_curr - 1])->slabs_clsid == 0);

#ifdef USE_SYSTEM_MALLOC
    if (mem_limit && mem_malloced + size > mem_limit) {
        MEMCACHED_SLABS_ALLOCATE_FAILED(size, id);
        return 0;
    }
    mem_malloced += size;
    ret = malloc(size);
    MEMCACHED_SLABS_ALLOCATE(size, id, 0, ret);
    return ret;
#endif

    /* 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 */
       //当没有空间时，返回ret=NULL
    if (! (p->end_page_ptr != 0 || p->sl_curr != 0 ||
           do_slabs_newslab(id) != 0)) {
        /* We don't have more memory available */
        ret = NULL;
    } else if (p->sl_curr != 0) {
        /* return off our freelist */
        ret = p->slots[--p->sl_curr];
    } else {
    //从空闲的slab中分配一个item
        /* if we recently allocated a whole page, return from that */
        assert(p->end_page_ptr != NULL);
    //指向空闲slab
    ret = p->end_page_ptr;
        if (--p->end_page_free != 0) {
            p->end_page_ptr += p->size;
        } else {
            p->end_page_ptr = 0;
        }
    }

    if (ret) {
        MEMCACHED_SLABS_ALLOCATE(size, id, p->size, ret);
    } else {
        MEMCACHED_SLABS_ALLOCATE_FAILED(size, id);
    }

    return ret;
}

4.3 do_slabs_free

把 ptr 指向的 item 归还给 slabclass[id]。操作很简单, 把 ptr 指向的 item 挂在 slots 空闲链表的最前面。

//释放一个item
void do_slabs_free(void *ptr, const size_t size, unsigned int id) {
    slabclass_t *p;

    assert(((item *)ptr)->slabs_clsid == 0);
    assert(id >= POWER_SMALLEST && id <= power_largest);
    if (id < POWER_SMALLEST || id > power_largest)
        return;

    MEMCACHED_SLABS_FREE(size, id, ptr);
    p = &slabclass[id];

#ifdef USE_SYSTEM_MALLOC
    mem_malloced -= size;
    free(ptr);
    return;
#endif

    if (p->sl_curr == p->sl_total) { /* need more space on the free list */
        int new_size = (p->sl_total != 0) ? p->sl_total * 2 : 16; /* 16 is arbitrary */
        void **new_slots = realloc(p->slots, new_size * sizeof(void *));
        if (new_slots == 0)
            return;
        p->slots = new_slots;
        p->sl_total = new_size;
    }
    p->slots[p->sl_curr++] = ptr;
    return;
}

4.4 do_item_alloc

从 slab 系统分配一个空闲 item

/*@null@*/
//nkey------------key的大小
//nbytes----------value的大小

item *do_item_alloc(char *key, const size_t nkey, const int flags, const rel_time_t exptime, const int nbytes) {
    uint8_t nsuffix;
    item *it;
    char suffix[40];

//得到该item的大小=sizeof(item) + nkey + *nsuffix + nbytes;
    size_t ntotal = item_make_header(nkey + 1, flags, nbytes, suffix, &nsuffix);

//slabs_clsid：返回size大小对应的slabclass索引
    unsigned int id = slabs_clsid(ntotal);
    if (id == 0)
        return 0;

//从slabclass[id]中分配一个size大小的trunk
    it = slabs_alloc(ntotal, id);
//当没有空闲的item时，进行LRU计算
    if (it == 0) {
        int tries = 50;
        item *search;

        /* If requested to not push old items out of cache when memory runs out,
         * we're out of luck at this point...
         */

        if (settings.evict_to_free == 0) {
            itemstats[id].outofmemory++;
            return NULL;
        }

        /*
         * try to get one off the right LRU
         * don't necessariuly unlink the tail because it may be locked: refcount>0
         * search up from tail an item with refcount==0 and unlink it; give up after 50
         * tries
         */

        if (tails[id] == 0) {
            itemstats[id].outofmemory++;
            return NULL;
        }

        for (search = tails[id]; tries > 0 && search != NULL; tries--, search=search->prev) {
            //当发现一个item 当前没有被使用(引用计数refcount 为0) ，
            //且其 生存时间已经为0 或生存时间大于现在时间，
            //就果断的把它释放掉。并再次调slabs_alloc()
            if (search->refcount == 0) {
                if (search->exptime == 0 || search->exptime > current_time) {
                    itemstats[id].evicted++;
                    itemstats[id].evicted_time = current_time - search->time;
                    STATS_LOCK();
                    stats.evictions++;
                    STATS_UNLOCK();
                }
                do_item_unlink(search);
                break;
            }
        }
        it = slabs_alloc(ntotal, id);
        if (it == 0) {
            itemstats[id].outofmemory++;
            /* Last ditch effort. There is a very rare bug which causes
             * refcount leaks. We've fixed most of them, but it still happens,
             * and it may happen in the future.
             * We can reasonably assume no item can stay locked for more than
             * three hours, so if we find one in the tail which is that old,
             * free it anyway.
             */
            tries = 50;
            for (search = tails[id]; tries > 0 && search != NULL; tries--, search=search->prev) {
                if (search->refcount != 0 && search->time + 10800 < current_time) {
                    itemstats[id].tailrepairs++;
                    search->refcount = 0;
                    do_item_unlink(search);
                    break;
                }
            }
            it = slabs_alloc(ntotal, id);
            if (it == 0) {
                return NULL;
            }
        }
    }

    assert(it->slabs_clsid == 0);

    it->slabs_clsid = id;

    assert(it != heads[it->slabs_clsid]);

    it->next = it->prev = it->h_next = 0;
    it->refcount = 1; /* the caller will have a reference */
    DEBUG_REFCNT(it, '*');
    it->it_flags = 0;
    it->nkey = nkey;
    it->nbytes = nbytes;
    strcpy(ITEM_key(it), key);
    it->exptime = exptime;
    memcpy(ITEM_suffix(it), suffix, (size_t)nsuffix);
    it->nsuffix = nsuffix;
    return it;
}

4.5 do_item_link

形成了一个完成的 item 后, 就要把它放入两个数据结构中, 一是 memcached 的哈希表, memcached 运行过程中只有一个哈希表, 二是 item 所在的 slabclass 的 LRU 队列.如 图6 所示, 每个 slabclass 都有一个 LRU 队列。

//形成了一个完成的 item 后, 就要把它放入两个数据结构中
//一是 memcached 的哈希表,
//二是 item 所在的 slabclass 的 LRU 队列

int do_item_link(item *it) {
    MEMCACHED_ITEM_LINK(ITEM_key(it), it->nbytes);
    assert((it->it_flags & (ITEM_LINKED|ITEM_SLABBED)) == 0);
    assert(it->nbytes < (1024 * 1024)); /* 1MB max size */
    it->it_flags |= ITEM_LINKED;
    it->time = current_time;

    //加入到hashtable中
    assoc_insert(it);

    STATS_LOCK();
    stats.curr_bytes += ITEM_ntotal(it);
    stats.curr_items += 1;
    stats.total_items += 1;
    STATS_UNLOCK();

    /* Allocate a new CAS ID on link. */
    it->cas_id = get_cas_id();

//加入到LRU队列中
//新元素放入到头部，旧的放入到尾部。
    item_link_q(it);

    return 1;
}

4.6 do_item_unlink

do_item_unlink 与 do_item_unlink 做的工作相反, 把 item 从哈希表和 LRU 队列中删除,而且还释放掉 item 所占的内存 (其实只是把 item 放到空闲链表中).

void do_item_unlink(item *it) {
    MEMCACHED_ITEM_UNLINK(ITEM_key(it), it->nbytes);
    if ((it->it_flags & ITEM_LINKED) != 0) {
        it->it_flags &= ~ITEM_LINKED;
        STATS_LOCK();
        stats.curr_bytes -= ITEM_ntotal(it);
        stats.curr_items -= 1;
        STATS_UNLOCK();
//从hashtable中删除
        assoc_delete(ITEM_key(it), it->nkey);
//从LRU队列中删除
        item_unlink_q(it);
        if (it->refcount == 0) item_free(it);
    }
}

4.7 item_get

根据 key 找对应的 item, 为了加快查找速度, memcached 使用一个哈希表对 key 和 item 所在的内存地址做映射. item_get 直接从哈希表中查找就可以了, 当然找到了还要检查 item 是否超时. 超时了的 item将从哈希表和 LRU 队列中删除掉。

item *item_get(const char *key, const size_t nkey) {
    return item_get_notedeleted(key, nkey, 0);
}