1/* -*- Mode: C; tab-width: 4; c-basic-offset: 4; indent-tabs-mode: nil -*- */
2/*
3 * Slabs memory allocation, based on powers-of-N. Slabs are up to 1MB in size
4 * and are divided into chunks. The chunk sizes start off at the size of the
5 * "item" structure plus space for a small key and value. They increase by
6 * a multiplier factor from there, up to half the maximum slab size. The last
7 * slab size is always 1MB, since that's the maximum item size allowed by the
8 * memcached protocol.
9 */
10#include "config.h"
11
12#include <fcntl.h>
13#include <errno.h>
14#include <stdlib.h>
15#include <stdio.h>
16#include <string.h>
17#include <inttypes.h>
18#include <stdarg.h>
19
20#include "default_engine.h"
21
22/*
23 * Forward Declarations
24 */
25static int do_slabs_newslab(struct default_engine *engine, const unsigned int id);
26static void *memory_allocate(struct default_engine *engine, size_t size);
27
28#ifndef DONT_PREALLOC_SLABS
29/* Preallocate as many slab pages as possible (called from slabs_init)
30   on start-up, so users don't get confused out-of-memory errors when
31   they do have free (in-slab) space, but no space to make new slabs.
32   if maxslabs is 18 (POWER_LARGEST - POWER_SMALLEST + 1), then all
33   slab types can be made.  if max memory is less than 18 MB, only the
34   smaller ones will be made.  */
35static void slabs_preallocate (const unsigned int maxslabs);
36#endif
37
38/*
39 * Figures out which slab class (chunk size) is required to store an item of
40 * a given size.
41 *
42 * Given object size, return id to use when allocating/freeing memory for object
43 * 0 means error: can't store such a large object
44 */
45
46unsigned int slabs_clsid(struct default_engine *engine, const size_t size) {
47    int res = POWER_SMALLEST;
48
49    if (size == 0)
50        return 0;
51    while (size > engine->slabs.slabclass[res].size)
52        if (res++ == engine->slabs.power_largest)     /* won't fit in the biggest slab */
53            return 0;
54    return res;
55}
56
57static void *my_allocate(struct default_engine *e, size_t size) {
58    void *ptr;
59    /* Is threre room? */
60    if (e->slabs.allocs.next == e->slabs.allocs.size) {
61        size_t n = e->slabs.allocs.size + 1024;
62        void *p = realloc(e->slabs.allocs.ptrs, n * sizeof(void*));
63        if (p == NULL) {
64            return NULL;
65        }
66        e->slabs.allocs.ptrs = p;
67        e->slabs.allocs.size = n;
68    }
69
70    ptr = malloc(size);
71    if (ptr != NULL) {
72        e->slabs.allocs.ptrs[e->slabs.allocs.next++] = ptr;
73
74    }
75    return ptr;
76}
77
78/**
79 * Determines the chunk sizes and initializes the slab class descriptors
80 * accordingly.
81 */
82ENGINE_ERROR_CODE slabs_init(struct default_engine *engine,
83                             const size_t limit,
84                             const double factor,
85                             const bool prealloc) {
86    int i = POWER_SMALLEST - 1;
87    unsigned int size = sizeof(hash_item) + (unsigned int)engine->config.chunk_size;
88
89    engine->slabs.mem_limit = limit;
90
91    if (prealloc) {
92        /* Allocate everything in a big chunk with malloc */
93        engine->slabs.mem_base = my_allocate(engine, engine->slabs.mem_limit);
94        if (engine->slabs.mem_base != NULL) {
95            engine->slabs.mem_current = engine->slabs.mem_base;
96            engine->slabs.mem_avail = engine->slabs.mem_limit;
97        } else {
98            return ENGINE_ENOMEM;
99        }
100    }
101
102    memset(engine->slabs.slabclass, 0, sizeof(engine->slabs.slabclass));
103
104    while (++i < POWER_LARGEST && size <= engine->config.item_size_max / factor) {
105        /* Make sure items are always n-byte aligned */
106        if (size % CHUNK_ALIGN_BYTES)
107            size += CHUNK_ALIGN_BYTES - (size % CHUNK_ALIGN_BYTES);
108
109        engine->slabs.slabclass[i].size = size;
110        engine->slabs.slabclass[i].perslab = (unsigned int)engine->config.item_size_max / engine->slabs.slabclass[i].size;
111        size = (unsigned int)(size * factor);
112        if (engine->config.verbose > 1) {
113            EXTENSION_LOGGER_DESCRIPTOR *logger;
114            logger = (void*)engine->server.extension->get_extension(EXTENSION_LOGGER);
115            logger->log(EXTENSION_LOG_INFO, NULL,
116                        "slab class %3d: chunk size %9u perslab %7u\n",
117                        i, engine->slabs.slabclass[i].size,
118                        engine->slabs.slabclass[i].perslab);
119        }
120    }
121
122    engine->slabs.power_largest = i;
123    engine->slabs.slabclass[engine->slabs.power_largest].size = (unsigned int)engine->config.item_size_max;
124    engine->slabs.slabclass[engine->slabs.power_largest].perslab = 1;
125    if (engine->config.verbose > 1) {
126        EXTENSION_LOGGER_DESCRIPTOR *logger;
127        logger = (void*)engine->server.extension->get_extension(EXTENSION_LOGGER);
128        logger->log(EXTENSION_LOG_INFO, NULL,
129                    "slab class %3d: chunk size %9u perslab %7u\n",
130                    i, engine->slabs.slabclass[i].size,
131                    engine->slabs.slabclass[i].perslab);
132    }
133
134    /* for the test suite:  faking of how much we've already malloc'd */
135    {
136        char *t_initial_malloc = getenv("T_MEMD_INITIAL_MALLOC");
137        if (t_initial_malloc) {
138            engine->slabs.mem_malloced = (size_t)atol(t_initial_malloc);
139        }
140
141    }
142
143#ifndef DONT_PREALLOC_SLABS
144    {
145        char *pre_alloc = getenv("T_MEMD_SLABS_ALLOC");
146
147        if (pre_alloc == NULL || atoi(pre_alloc) != 0) {
148            slabs_preallocate(power_largest);
149        }
150    }
151#endif
152
153    return ENGINE_SUCCESS;
154}
155
156#ifndef DONT_PREALLOC_SLABS
157static void slabs_preallocate (const unsigned int maxslabs) {
158    int i;
159    unsigned int prealloc = 0;
160
161    /* pre-allocate a 1MB slab in every size class so people don't get
162       confused by non-intuitive "SERVER_ERROR out of memory"
163       messages.  this is the most common question on the mailing
164       list.  if you really don't want this, you can rebuild without
165       these three lines.  */
166
167    for (i = POWER_SMALLEST; i <= POWER_LARGEST; i++) {
168        if (++prealloc > maxslabs)
169            return;
170        do_slabs_newslab(i);
171    }
172
173}
174#endif
175
176static int grow_slab_list (struct default_engine *engine, const unsigned int id) {
177    slabclass_t *p = &engine->slabs.slabclass[id];
178    if (p->slabs == p->list_size) {
179        unsigned int new_size =  (p->list_size != 0) ? p->list_size * 2 : 16;
180        void *new_list = realloc(p->slab_list, new_size * sizeof(void *));
181        if (new_list == 0) return 0;
182        p->list_size = new_size;
183        p->slab_list = new_list;
184    }
185    return 1;
186}
187
188static int do_slabs_newslab(struct default_engine *engine, const unsigned int id) {
189    slabclass_t *p = &engine->slabs.slabclass[id];
190    int len = p->size * p->perslab;
191    char *ptr;
192
193    if ((engine->slabs.mem_limit && engine->slabs.mem_malloced + len > engine->slabs.mem_limit && p->slabs > 0) ||
194        (grow_slab_list(engine, id) == 0) ||
195        ((ptr = memory_allocate(engine, (size_t)len)) == 0)) {
196
197        MEMCACHED_SLABS_SLABCLASS_ALLOCATE_FAILED(id);
198        return 0;
199    }
200
201    memset(ptr, 0, (size_t)len);
202    p->end_page_ptr = ptr;
203    p->end_page_free = p->perslab;
204
205    p->slab_list[p->slabs++] = ptr;
206    engine->slabs.mem_malloced += len;
207    MEMCACHED_SLABS_SLABCLASS_ALLOCATE(id);
208
209    return 1;
210}
211
212/*@null@*/
213static void *do_slabs_alloc(struct default_engine *engine, const size_t size, unsigned int id) {
214    slabclass_t *p;
215    void *ret = NULL;
216
217    if (id < POWER_SMALLEST || id > engine->slabs.power_largest) {
218        MEMCACHED_SLABS_ALLOCATE_FAILED(size, 0);
219        return NULL;
220    }
221
222    p = &engine->slabs.slabclass[id];
223
224#ifdef USE_SYSTEM_MALLOC
225    if (engine->slabs.mem_limit && engine->slabs.mem_malloced + size > engine->slabs.mem_limit) {
226        MEMCACHED_SLABS_ALLOCATE_FAILED(size, id);
227        return 0;
228    }
229    engine->slabs.mem_malloced += size;
230    ret = malloc(size);
231    MEMCACHED_SLABS_ALLOCATE(size, id, 0, ret);
232    return ret;
233#endif
234
235    /* fail unless we have space at the end of a recently allocated page,
236       we have something on our freelist, or we could allocate a new page */
237    if (! (p->end_page_ptr != 0 || p->sl_curr != 0 ||
238           do_slabs_newslab(engine, id) != 0)) {
239        /* We don't have more memory available */
240        ret = NULL;
241    } else if (p->sl_curr != 0) {
242        /* return off our freelist */
243        ret = p->slots[--p->sl_curr];
244    } else {
245        /* if we recently allocated a whole page, return from that */
246        cb_assert(p->end_page_ptr != NULL);
247        ret = p->end_page_ptr;
248        if (--p->end_page_free != 0) {
249            p->end_page_ptr = ((unsigned char *)p->end_page_ptr) + p->size;
250        } else {
251            p->end_page_ptr = 0;
252        }
253    }
254
255    if (ret) {
256        p->requested += size;
257        MEMCACHED_SLABS_ALLOCATE(size, id, p->size, ret);
258    } else {
259        MEMCACHED_SLABS_ALLOCATE_FAILED(size, id);
260    }
261
262    return ret;
263}
264
265static void do_slabs_free(struct default_engine *engine, void *ptr, const size_t size, unsigned int id) {
266    slabclass_t *p;
267
268    if (id < POWER_SMALLEST || id > engine->slabs.power_largest)
269        return;
270
271    MEMCACHED_SLABS_FREE(size, id, ptr);
272    p = &engine->slabs.slabclass[id];
273
274#ifdef USE_SYSTEM_MALLOC
275    engine->slabs.mem_malloced -= size;
276    free(ptr);
277    return;
278#endif
279
280    if (p->sl_curr == p->sl_total) { /* need more space on the free list */
281        int new_size = (p->sl_total != 0) ? p->sl_total * 2 : 16;  /* 16 is arbitrary */
282        void **new_slots = realloc(p->slots, new_size * sizeof(void *));
283        if (new_slots == 0)
284            return;
285        p->slots = new_slots;
286        p->sl_total = new_size;
287    }
288    p->slots[p->sl_curr++] = ptr;
289    p->requested -= size;
290    return;
291}
292
293void add_statistics(const void *cookie, ADD_STAT add_stats,
294                    const char* prefix, int num, const char *key,
295                    const char *fmt, ...) {
296    char name[80], val[80];
297    int klen = 0, vlen;
298    va_list ap;
299
300    cb_assert(cookie);
301    cb_assert(add_stats);
302    cb_assert(key);
303
304    va_start(ap, fmt);
305    vlen = vsnprintf(val, sizeof(val) - 1, fmt, ap);
306    va_end(ap);
307
308    if (prefix != NULL) {
309        klen = snprintf(name, sizeof(name), "%s:", prefix);
310    }
311
312    if (num != -1) {
313        klen += snprintf(name + klen, sizeof(name) - klen, "%d:", num);
314    }
315
316    klen += snprintf(name + klen, sizeof(name) - klen, "%s", key);
317
318    add_stats(name, klen, val, vlen, cookie);
319}
320
321/*@null@*/
322static void do_slabs_stats(struct default_engine *engine, ADD_STAT add_stats, const void *cookie) {
323    unsigned int i, total;
324    /* Get the per-thread stats which contain some interesting aggregates */
325#ifdef FUTURE
326    struct conn *conn = (struct conn*)cookie;
327    struct thread_stats thread_stats;
328    threadlocal_stats_aggregate(c, &thread_stats);
329#endif
330
331    total = 0;
332    for(i = POWER_SMALLEST; i <= engine->slabs.power_largest; i++) {
333        slabclass_t *p = &engine->slabs.slabclass[i];
334        if (p->slabs != 0) {
335            uint32_t perslab, slabs;
336            slabs = p->slabs;
337            perslab = p->perslab;
338
339            add_statistics(cookie, add_stats, NULL, i, "chunk_size", "%u",
340                           p->size);
341            add_statistics(cookie, add_stats, NULL, i, "chunks_per_page", "%u",
342                           perslab);
343            add_statistics(cookie, add_stats, NULL, i, "total_pages", "%u",
344                           slabs);
345            add_statistics(cookie, add_stats, NULL, i, "total_chunks", "%u",
346                           slabs * perslab);
347            add_statistics(cookie, add_stats, NULL, i, "used_chunks", "%u",
348                           slabs*perslab - p->sl_curr - p->end_page_free);
349            add_statistics(cookie, add_stats, NULL, i, "free_chunks", "%u",
350                           p->sl_curr);
351            add_statistics(cookie, add_stats, NULL, i, "free_chunks_end", "%u",
352                           p->end_page_free);
353            add_statistics(cookie, add_stats, NULL, i, "mem_requested", "%"PRIu64,
354                           (uint64_t)p->requested);
355#ifdef FUTURE
356            add_statistics(cookie, add_stats, NULL, i, "get_hits", "%"PRIu64,
357                           thread_stats.slab_stats[i].get_hits);
358            add_statistics(cookie, add_stats, NULL, i, "cmd_set", "%"PRIu64,
359                           thread_stats.slab_stats[i].set_cmds);
360            add_statistics(cookie, add_stats, NULL, i, "delete_hits", "%"PRIu64,
361                           thread_stats.slab_stats[i].delete_hits);
362            add_statistics(cookie, add_stats, NULL, i, "cas_hits", "%"PRIu64,
363                           thread_stats.slab_stats[i].cas_hits);
364            add_statistics(cookie, add_stats, NULL, i, "cas_badval", "%"PRIu64,
365                           thread_stats.slab_stats[i].cas_badval);
366#endif
367            total++;
368        }
369    }
370
371    /* add overall slab stats and append terminator */
372
373    add_statistics(cookie, add_stats, NULL, -1, "active_slabs", "%d", total);
374    add_statistics(cookie, add_stats, NULL, -1, "total_malloced", "%"PRIu64,
375                   (uint64_t)engine->slabs.mem_malloced);
376}
377
378static void *memory_allocate(struct default_engine *engine, size_t size) {
379    void *ret;
380
381    if (engine->slabs.mem_base == NULL) {
382        /* We are not using a preallocated large memory chunk */
383        ret = my_allocate(engine, size);
384    } else {
385        ret = engine->slabs.mem_current;
386
387        if (size > engine->slabs.mem_avail) {
388            return NULL;
389        }
390
391        /* mem_current pointer _must_ be aligned!!! */
392        if (size % CHUNK_ALIGN_BYTES) {
393            size += CHUNK_ALIGN_BYTES - (size % CHUNK_ALIGN_BYTES);
394        }
395
396        engine->slabs.mem_current = ((char*)engine->slabs.mem_current) + size;
397        if (size < engine->slabs.mem_avail) {
398            engine->slabs.mem_avail -= size;
399        } else {
400            engine->slabs.mem_avail = 0;
401        }
402    }
403
404    return ret;
405}
406
407void *slabs_alloc(struct default_engine *engine, size_t size, unsigned int id) {
408    void *ret;
409
410    cb_mutex_enter(&engine->slabs.lock);
411    ret = do_slabs_alloc(engine, size, id);
412    cb_mutex_exit(&engine->slabs.lock);
413    return ret;
414}
415
416void slabs_free(struct default_engine *engine, void *ptr, size_t size, unsigned int id) {
417    cb_mutex_enter(&engine->slabs.lock);
418    do_slabs_free(engine, ptr, size, id);
419    cb_mutex_exit(&engine->slabs.lock);
420}
421
422void slabs_stats(struct default_engine *engine, ADD_STAT add_stats, const void *c) {
423    cb_mutex_enter(&engine->slabs.lock);
424    do_slabs_stats(engine, add_stats, c);
425    cb_mutex_exit(&engine->slabs.lock);
426}
427
428void slabs_adjust_mem_requested(struct default_engine *engine, unsigned int id, size_t old, size_t ntotal)
429{
430    slabclass_t *p;
431    cb_mutex_enter(&engine->slabs.lock);
432    if (id < POWER_SMALLEST || id > engine->slabs.power_largest) {
433        EXTENSION_LOGGER_DESCRIPTOR *logger;
434        logger = (void*)engine->server.extension->get_extension(EXTENSION_LOGGER);
435        logger->log(EXTENSION_LOG_WARNING, NULL,
436                    "Internal error! Invalid slab class\n");
437        abort();
438    }
439
440    p = &engine->slabs.slabclass[id];
441    p->requested = p->requested - old + ntotal;
442    cb_mutex_exit(&engine->slabs.lock);
443}
444
445void slabs_destroy(struct default_engine *e)
446{
447    /* Release the allocated backing store */
448    size_t ii;
449    unsigned int jj;
450
451    for (ii = 0; ii < e->slabs.allocs.next; ++ii) {
452        free(e->slabs.allocs.ptrs[ii]);
453    }
454    free(e->slabs.allocs.ptrs);
455
456    /* Release the freelists */
457    for (jj = POWER_SMALLEST; jj <= e->slabs.power_largest; jj++) {
458        slabclass_t *p = &e->slabs.slabclass[jj];
459        free(p->slots);
460        free(p->slab_list);
461    }
462}
463