memcached探索之item.h/item.c

4若

终于到了item的操作了，item是memcached数据管理的基本单位，也是hash, LRU等链表处理的基本单位。很核心的东西来。

一. 主要程序接口

item *do_item_alloc(char *key, const size_t nkey, const int flags, const rel_time_t exptime, const int nbytes);
void item_free(item *it);
bool item_size_ok(const size_t nkey, const int flags, const int nbytes);

int do_item_link(item *it);
void do_item_unlink(item *it);
void do_item_remove(item *it);
void do_item_update(item *it);
int do_item_replace(item *it, item *new_it);

char *do_item_cachedump(const unsigned int slabs_clsid, const unsigned int limit, unsigned int *bytes);

void do_item_flush_expired(void);

item *do_item_get(const char *key, const size_t nkey);
item *do_item_get_nocheck(const char *key, const size_t nkey);

二. 源代码注释和分析

1. 主要数据结构

#define ITEM_UPDATE_INTERVAL 60

#define LARGEST_ID POWER_LARGEST
typedef struct {
    unsigned int evicted;
    unsigned int evicted_nonzero;
    rel_time_t evicted_time;
    unsigned int reclaimed;
    unsigned int outofmemory;
    unsigned int tailrepairs;
} itemstats_t; //item的状态统计信息，这里就不分析了

static item *heads[LARGEST_ID]; //LRU链首指针,  每个classid一个LRU链
static item *tails[LARGEST_ID];    //LRU链尾指针，每个classid一个LRU链
static itemstats_t itemstats[LARGEST_ID];
static unsigned int sizes[LARGEST_ID];  //每个classid的LRU链的长度(item个数）

// item数据结构的定义(放在memcached.h中)
typedef struct _stritem {
    struct _stritem *next;  //next和prev是LRU链的双向链表指针
    struct _stritem *prev;
    struct _stritem *h_next;
    rel_time_t time;
    rel_time_t exptime;
    int nbytes;
    unsigned short refcount;
    uint8_t nsuffix;
    uint8_t it_flags;
    uint8_t slabs_clsid;
    uint8_t nkey;
    void * end[]; //方便item数据结构后面存储value_data




} item;
// item的三种flag: ITEM_SLABBED, ITEM_LINKED,ITEM_CAS


2. item_link_q 和 item_unlink_q (主要用于LRU链的管理)

//将item加入到对应classid的LRU链的head
oid item_link_q(item *it) {
    item **head, **tail;
    assert(it->slabs_clsid < LARGEST_ID);
    assert((it->it_flags & ITEM_SLABBED) == 0);

    head = &heads[it->slabs_clsid];
    tail = &tails[it->slabs_clsid];
    assert(it != *head);
    assert((*head && *tail) || (*head == 0 && *tail == 0));
    it->prev = 0; //双向链表的指针操作
    it->next = *head;
    if (it->next) it->next->prev = it;
    *head = it;
    if (*tail == 0) *tail = it;
    sizes[it->slabs_clsid]++; //LUR queue size++
    return;
}
//将item从对应classid的LRU链上移除
static void item_unlink_q(item *it) {
    item **head, **tail;
    assert(it->slabs_clsid < LARGEST_ID);
    head = &heads[it->slabs_clsid];
    tail = &tails[it->slabs_clsid];

    if (*head == it) {
        assert(it->prev == 0);
        *head = it->next;
    }
    if (*tail == it) {
        assert(it->next == 0);
        *tail = it->prev;
    }
    assert(it->next != it);
    assert(it->prev != it);

    if (it->next) it->next->prev = it->prev;
    if (it->prev) it->prev->next = it->next;
    sizes[it->slabs_clsid]--;
    return;
}

3. do_item_link 和 do_item_unlink,do_item_remove, do_item_update,do_item_replace等

//将item加入到hashtable并加入到对应classid的LRU链中。
int do_item_link(item *it) {
    MEMCACHED_ITEM_LINK(ITEM_key(it), it->nkey, it->nbytes);
    assert((it->it_flags & (ITEM_LINKED|ITEM_SLABBED)) == 0);
    it->it_flags |= ITEM_LINKED; //进入linked状态
    it->time = current_time;
    assoc_insert(it); //加入到hashtable

    STATS_LOCK(); //stat信息统计
    stats.curr_bytes += ITEM_ntotal(it);
    stats.curr_items += 1;
    stats.total_items += 1;
    STATS_UNLOCK();


    ITEM_set_cas(it, (settings.use_cas) ? get_cas_id() : 0);
    item_link_q(it); //加入到LUR链中
    return 1;
}

//将item从hashtable和LRU链中移除。是do_item_link的逆操作
void do_item_unlink(item *it) {
    MEMCACHED_ITEM_UNLINK(ITEM_key(it), it->nkey, 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();
        assoc_delete(ITEM_key(it), it->nkey);
        item_unlink_q(it);
        if (it->refcount == 0) item_free(it);
    }
}
//移除item
void do_item_remove(item *it) {
    MEMCACHED_ITEM_REMOVE(ITEM_key(it), it->nkey, it->nbytes);
    assert((it->it_flags & ITEM_SLABBED) == 0);
    if (it->refcount != 0) { //有别人在引用
        it->refcount--;
        DEBUG_REFCNT(it, '-');
    }
    if (it->refcount == 0 && (it->it_flags & ITEM_LINKED) == 0) {
        item_free(it); //释放item,接下来分析
    }
}
//更新一个item的最后访问时间，不过需要在一段时间之后
void do_item_update(item *it) {
    MEMCACHED_ITEM_UPDATE(ITEM_key(it), it->nkey, it->nbytes);
    if (it->time < current_time - ITEM_UPDATE_INTERVAL) {
        assert((it->it_flags & ITEM_SLABBED) == 0);
        if ((it->it_flags & ITEM_LINKED) != 0) {
            item_unlink_q(it);
            it->time = current_time;
            item_link_q(it);
        }
    }
}
//将item用new_item代替
int do_item_replace(item *it, item *new_it) { //
    MEMCACHED_ITEM_REPLACE(ITEM_key(it), it->nkey, it->nbytes,
                           ITEM_key(new_it), new_it->nkey, new_it->nbytes);
    assert((it->it_flags & ITEM_SLABBED) == 0);

    do_item_unlink(it);
    return do_item_link(new_it);
}

4. do_item_alloc (分配item) 和 item_free （释放item）


//由这里可以推出item的存储格式:item struct + key+1 + suffix +value + '\r\n'
static size_t item_make_header(const uint8_t nkey, const int flags, const int nbytes,
                     char *suffix, uint8_t *nsuffix) {
     //nbytes-2=value length
    *nsuffix = (uint8_t) snprintf(suffix, 40, " %d %d\r\n", flags, nbytes - 2);
    return sizeof(item) + nkey + *nsuffix + nbytes;
  }

//分配一个item空间
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 = NULL;
    char suffix[40];
    size_t ntotal = item_make_header(nkey + 1, flags, nbytes, suffix, &nsuffix);
    if (settings.use_cas) {
        ntotal += sizeof(uint64_t);
    }
    unsigned int id = slabs_clsid(ntotal); //寻找合适的slabclass
    if (id == 0)
        return 0;

    int tries = 50;
    item *search; //首先从LRU链尾开始，寻找一个过期的item, 最多尝试50次
    for (search = tails[id];tries > 0 && search != NULL; tries--, search=search->prev) {
        if (search->refcount == 0 &&
            (search->exptime != 0 && search->exptime < current_time)) {
            it = search;

            STATS_LOCK();
            stats.reclaimed++;
            STATS_UNLOCK();
            itemstats[id].reclaimed++;
            it->refcount = 1;
            do_item_unlink(it); //将寻找到的item移除

            it->slabs_clsid = 0;
            it->refcount = 0;
            break;
        }
    }

    if (it == NULL && (it = slabs_alloc(ntotal, id)) == NULL) {

        tries = 50; //没有找到过期item并分配chunk失败，则进行LRU淘汰一个item

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

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

        for (search = tails[id]; tries > 0 && search != NULL; tries--, search=search->prev) {
            if (search->refcount == 0) {
                if (search->exptime == 0 || search->exptime > current_time) {
                    itemstats[id].evicted++;
                    itemstats[id].evicted_time = current_time - search->time;
                    if (search->exptime != 0)
                        itemstats[id].evicted_nonzero++;
                    STATS_LOCK();
                    stats.evictions++;
                    STATS_UNLOCK();
                } else {
                    itemstats[id].reclaimed++;
                    STATS_LOCK();
                    stats.reclaimed++;
                    STATS_UNLOCK();
                }
                do_item_unlink(search);
                break;
            }
        }
        it = slabs_alloc(ntotal, id); //LRU淘汰没有找到，再尝试一次内存分配。。。
        if (it == 0) {
            itemstats[id].outofmemory++;

            tries = 50; //分配失败，再尝试一次LRU淘汰
            for (search = tails[id]; tries > 0 && search != NULL; tries--, search=search->prev) {
                if (search->refcount != 0 && search->time + TAIL_REPAIR_TIME < current_time) {
                    itemstats[id].tailrepairs++;
                    search->refcount = 0;
                    do_item_unlink(search);
                    break;
                }
            }
            it = slabs_alloc(ntotal, id); //最后一次chunk分配
            if (it == 0) {
                return NULL;
            }
        }
    }

    assert(it->slabs_clsid == 0); //标志已经找到item时 slabs_clsid=0
    it->slabs_clsid = id;

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

    it->next = it->prev = it->h_next = 0;
    it->refcount = 1;
    DEBUG_REFCNT(it, '*');
    it->it_flags = settings.use_cas ? ITEM_CAS : 0;
    it->nkey = nkey;
    it->nbytes = nbytes;
    memcpy(ITEM_key(it), key, nkey); //存放key string
    it->exptime = exptime;
    memcpy(ITEM_suffix(it), suffix, (size_t)nsuffix); //存放suffix
    it->nsuffix = nsuffix;
    return it;  //注意：这里并没有存放value string, 要等到调用函数来memcpy
}

//释放item
void item_free(item *it) {
    size_t ntotal = ITEM_ntotal(it);
    unsigned int clsid;
    assert((it->it_flags & ITEM_LINKED) == 0); //非LINKED状态才能free
    assert(it != heads[it->slabs_clsid]);
    assert(it != tails[it->slabs_clsid]);
    assert(it->refcount == 0);


    clsid = it->slabs_clsid;
    it->slabs_clsid = 0;
    it->it_flags |= ITEM_SLABBED; //标志归还内存到slab,唯一 一次使用 ITEM_SLABBED
    DEBUG_REFCNT(it, 'F');
    slabs_free(it, ntotal, clsid); //是否slab memory
}

bool item_size_ok(const size_t nkey, const int flags, const int nbytes) {
    char prefix[40];
    uint8_t nsuffix;

    return slabs_clsid(item_make_header(nkey + 1, flags, nbytes,
                                        prefix, &nsuffix)) != 0;
}


5. do_item_get


//这个函数写的比较乱，这里精简了一下，现在看起来简单多来吧

item *do_item_get(const char *key, const size_t nkey) {
    item *it = assoc_find(key, nkey);
    int was_found = 0;

    if (it != NULL && settings.oldest_live != 0 && settings.oldest_live <= current_time &&
        it->time <= settings.oldest_live) {
        do_item_unlink(it);
        it = NULL;
    }

    if (it != NULL && it->exptime != 0 && it->exptime <= current_time) {
        do_item_unlink(it);
        it = NULL;
    }

    if (it != NULL) {
        it->refcount++;
        DEBUG_REFCNT(it, '+');
    }

    return it;
}


item *do_item_get_nocheck(const char *key, const size_t nkey) {
    item *it = assoc_find(key, nkey);
    if (it) {
        it->refcount++;
        DEBUG_REFCNT(it, '+');
    }
    return it;
}

//注意下oldest_live定义：

void do_item_flush_expired(void) {
    int i;
    item *iter, *next;
    if (settings.oldest_live == 0)
        return;
    for (i = 0; i < LARGEST_ID; i++) { //两次循环

        for (iter = heads[i]; iter != NULL; iter = next) {
            if (iter->time >= settings.oldest_live) {
                next = iter->next;
                if ((iter->it_flags & ITEM_SLABBED) == 0) { //没被释放才需要unlink
                    do_item_unlink(iter);
                }
            } else {

                break;
            }
        }
    }
}