Understanding The Memcached Source Code - Slab III

slab allocator (I, II, III - this article) is the core module of the cache system, which largely determines how efficient the bottleneck resource, memory, can be utilized. The other 3 parts, namely,

LRU algorithm (I , II , III) for entry expiration; and an

event driven model (I , II , III) based on libevent; and the

consistent hash (not complete) for data distribution,

are built around it.

Last time we saw the memory allocating process, which further formulates slabs and the derivative “free lists” (a.k.a., slots). This time we will examine how to take advantage of the established data structures to “slab allocate / release” memory chunks which will be used to store items.

Slab alloc

Firstly, we look at

do_slabs_alloc

which is opposite to the discussed do_slabs_free.

Note that the “public” interface of do_slabs_alloc is slabs_alloc which is basically a thread-safe wrapper that locks the core data structures manipulated by the Memcached instance that is configured as multithreaded.

void *slabs_alloc(size_t size, unsigned int id, unsigned int *total_chunks,
        unsigned int flags) {
    void *ret;

    pthread_mutex_lock(&slabs_lock);
    ret = do_slabs_alloc(size, id, total_chunks, flags);
    pthread_mutex_unlock(&slabs_lock);
    return ret;
}

slabs_alloc@slabs.c

...
        case 't':
            settings.num_threads = atoi(optarg);
            if (settings.num_threads <= 0) {
                fprintf(stderr, "Number of threads must be greater than 0\n");
                return 1;
            }
            /* There're other problems when you get above 64 threads.
             * In the future we should portably detect # of cores for the
             * default.
             */
            if (settings.num_threads > 64) {
                fprintf(stderr, "WARNING: Setting a high number of worker"
                                "threads is not recommended.\n"
                                " Set this value to the number of cores in"
                                " your machine or less.\n");
            }
            break;
...

main@memcached.c:5572

static void *do_slabs_alloc(const size_t size, unsigned int id, unsigned int *total_chunks,
        unsigned int flags) {
    slabclass_t *p;
    void *ret = NULL;
    item *it = NULL;
...
    p = &slabclass[id]; // scr: ----------------------------------------> 1)
...
    if (total_chunks != NULL) {
        *total_chunks = p->slabs * p->perslab; // scr: -----------------> 2)
    }
    /* 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 */
    if (p->sl_curr == 0 && flags != SLABS_ALLOC_NO_NEWPAGE) { // scr: --> *)
        do_slabs_newslab(id); // scr: ----------------------------------> 3)
    }

    if (p->sl_curr != 0) {
        /* return off our freelist */
        it = (item *)p->slots; // scr: ---------------------------------> 4)
        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; // scr: -------------------------> 5)
        it->refcount = 1;
        p->sl_curr--;
        ret = (void *)it; // scr: --------------------------------------> 6)
    } else {
        ret = NULL;
    }

...
    return ret;
}

do_slabs_alloc@slabs.c

1) For item allocation, id indicates the slab class that suits the requested item size best. In other words, id is selected using the actual item size, the process of which will be discussed very soon.

2) total_chunks is the parameter that outputs the total number of memory chunks (entries in the free list) available for the slab class. if (total_chunks != NULL) suggests that the argument is optional.

*) As the name indicates, SLABS_ALLOC_NO_NEWPAGE (flags) prevents this method to allocate new slab when there is no memory chunk available. This option is not used in the normal path of item allocation, hence is ignored for now.

3) When there is no free memory chunk, allocate a new slab. Here p->sl_curr indicates the number of available chunks, whose value decreases each time this method got called (in step 5 below).

Conversely, this field is increased in do_slabs_free. Note that new slab has also been covered from here.

4) Remove the front element (f) from the free list, and set it to it.

In do_slabs_free, an element is added to the front of the free list.

5) Clear the ITEM_SLABBED for the chuck (f), set its reference count to 1, and reduce p->sl_curr by 1.

Likewise, this flag is set in do_slabs_free.

6) Return (f).

Next, we look at the process of determining the id based on item size, the workhorse method of which is

slabs_clsid

unsigned int slabs_clsid(const size_t size) {
    int res = POWER_SMALLEST;

    if (size == 0)
        return 0;
    while (size > slabclass[res].size)
        if (res++ == power_largest)     /* won't fit in the biggest slab */
            return 0;
    return res;
}

do_slabs_alloc@slabs.c

slabs_clsid consists mainly of a while loop that linear search the possible smallest slab class that can contain the requested size. This method is called from do_item_alloc before slabs_alloc. We will discuss do_item_alloc in the following post.

item *do_item_alloc(char *key, const size_t nkey, const unsigned int flags,
                    const rel_time_t exptime, const int nbytes,
                    const uint32_t cur_hv) {
...
    unsigned int id = slabs_clsid(ntotal);
    if (id == 0)
        return 0;
...
        it = slabs_alloc(ntotal, id, &total_chunks, 0);
...

do_item_alloc@items.c