From: Liu Yuan <tailai.ly at taobao.com> This allocator is on top of malloc/free pair and it is just faster for object storage, because it preallocate space and the allocation/deallocation just need some simple pointer calcalations. The chunk size for object is from 16 bytes to 128k bytes. No technical limit to chunk size, they are just macros. Usage: id = slabs_clsid(object size); # this will preallocate a slab sized by object size. object_ptr = slabs_alloc(id); slabs_free(object_ptr, id); This code is based on the slabs.c in project Memcached. Signed-off-by: Liu Yuan <tailai.ly at taobao.com> --- sheep/sheep.c | 2 + sheep/slabs.c | 239 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++ sheep/slabs.h | 21 +++++ 3 files changed, 262 insertions(+), 0 deletions(-) create mode 100644 sheep/slabs.c create mode 100644 sheep/slabs.h diff --git a/sheep/sheep.c b/sheep/sheep.c index 94b4a9e..9f42fd1 100644 --- a/sheep/sheep.c +++ b/sheep/sheep.c @@ -21,6 +21,7 @@ #include <sys/syslog.h> #include "sheep_priv.h" +#include "slabs.h" #define EPOLL_SIZE 4096 #define DEFAULT_OBJECT_DIR "/tmp" @@ -180,6 +181,7 @@ int main(int argc, char **argv) if (ret) exit(1); + slabs_init(64*1024*1024, 1.15); ret = init_store(dir); if (ret) exit(1); diff --git a/sheep/slabs.c b/sheep/slabs.c new file mode 100644 index 0000000..6f429f1 --- /dev/null +++ b/sheep/slabs.c @@ -0,0 +1,239 @@ +/* +Copyright (c) 2011 Taobao.com, Inc. + +Liu Yuan <namei.unix at gmail.com> + +GPLv2 Licensed. + +Based on the code slabs.[ch] from Memcached +http://memcached.org/ + +Copyright (c) 2003, Danga Interactive, Inc. +All rights reserved. + +Redistribution and use in source and binary forms, with or without +modification, are permitted provided that the following conditions are +met: + + * Redistributions of source code must retain the above copyright +notice, this list of conditions and the following disclaimer. + + * Redistributions in binary form must reproduce the above +copyright notice, this list of conditions and the following disclaimer +in the documentation and/or other materials provided with the +distribution. + + * Neither the name of the Danga Interactive nor the names of its +contributors may be used to endorse or promote products derived from +this software without specific prior written permission. + +THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS +"AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT +LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR +A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT +OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, +SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT +LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, +DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY +THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT +(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE +OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. +*/ +#include <stdlib.h> +#include <stdio.h> +#include <pthread.h> +#include <sys/types.h> +#include <stdint.h> + +#include "slabs.h" +#include "logger.h" +#include "util.h" + +struct slab_class { + unsigned int size; /* size of item */ + unsigned int nr_perslab; /* how many items per slab */ + + void **freed_slots; /* array of items freed */ + unsigned int total_free; /* size of previous array */ + unsigned int free; + + void *last_slab_ptr; /* pointer to next free item, or 0 to ask for new slab */ + unsigned int last_slab_free; /* number of items remaining at end of last alloced slab */ + + void **slab_slots; /* array of slab pointers */ + unsigned int total_slots; /* size of slots array */ + unsigned int alloc; +}; + +/* Slab sizing definitions. */ +#define POWER_SMALLEST 0 +#define POWER_LARGEST 200 +#define CHUNK_ALIGN_BYTES 8 +#define MAX_NUMBER_OF_SLAB_CLASSES (POWER_LARGEST) + +static struct slab_class slab_classes[MAX_NUMBER_OF_SLAB_CLASSES]; +static size_t mem_limit = 0; +static size_t mem_malloced = 0; +static int power_largest; + +/* N.B. So the smallest item will occupy 16 bytes and the biggest one + * up to 128k, that is, one slab. + */ +static int min_chunk_size = 16; +static int max_chunk_size = 4096 * 32; + +static pthread_mutex_t slabs_lock = PTHREAD_MUTEX_INITIALIZER; + +static int try_grow_slab_slots(const unsigned int id) +{ + struct slab_class *p = &slab_classes[id]; + + if (p->alloc == p->total_slots) { + size_t new_size = (p->total_slots != 0) ? p->total_slots * 2 : 16; + void *new_slots = xrealloc(p->slab_slots, new_size * sizeof(void *)); + + p->total_slots = new_size; + p->slab_slots = new_slots; + return 1; + } + return 0; +} + +int slabs_clsid(const size_t size) +{ + int ret = POWER_SMALLEST; + + if (size == 0) + return -1; + + while (ret <= power_largest && size > slab_classes[ret].size) { + if (ret > power_largest) + return -1; + ret++; + } + try_grow_slab_slots(ret); + return ret; +} + +void slabs_init(const size_t limit, const double factor) +{ + int i = POWER_SMALLEST; + unsigned int size = min_chunk_size; + + mem_limit = limit; + + while (i < POWER_LARGEST && size <= max_chunk_size) { + if (size % CHUNK_ALIGN_BYTES) + size += CHUNK_ALIGN_BYTES - (size % CHUNK_ALIGN_BYTES); + + slab_classes[i].size = size; + slab_classes[i].nr_perslab = max_chunk_size / size; + if (max_chunk_size / size == 1) { + slab_classes[i].size = max_chunk_size; + dprintf("slab class %3d: chunk size %9u nr_perslab %7u\n", + i, slab_classes[i].size, slab_classes[i].nr_perslab); + power_largest = i; + return; + } + + dprintf("slab class %3d: chunk size %9u nr_perslab %7u\n", + i, slab_classes[i].size, slab_classes[i].nr_perslab); + size *= factor; + power_largest = i; + i++; + } +} + +static int alloc_last_slab(const unsigned int id) +{ + struct slab_class *p = &slab_classes[id]; + size_t len = p->size * p->nr_perslab; + char *ptr; + + if (mem_limit && mem_malloced + len > mem_limit && p->alloc > 0) { + /* FIXME: reclaim freed slots */ + eprintf("slab: out of memory limit\n"); + return 0; + } + + if (try_grow_slab_slots(id) < 0) + return 0; + + ptr = xzalloc(len); + p->last_slab_ptr = ptr; + p->last_slab_free = p->nr_perslab; + + p->slab_slots[p->alloc++] = ptr; + mem_malloced += len; + + return 1; +} + +static void *do_slabs_alloc(unsigned int id) +{ + struct slab_class *p; + void *ret = NULL; + + if (id < POWER_SMALLEST || id > power_largest) + goto out; + + p = &slab_classes[id]; + + if (p->free != 0) { + p->free--; + ret = p->freed_slots[p->free]; + } else { + if (!p->last_slab_ptr) + if (!alloc_last_slab(id)) + goto out; + + ret = p->last_slab_ptr; + p->last_slab_free--; + if (p->last_slab_free > 0) { + p->last_slab_ptr = ((char *)p->last_slab_ptr) + p->size; + } else { + p->last_slab_ptr = 0; + } + + } +out: + return ret; +} + +static void do_slabs_free(void *ptr, unsigned int id) +{ + struct slab_class *p; + + if (id < POWER_SMALLEST || id > power_largest) + return; + + p = &slab_classes[id]; + + /* Grow or init ... */ + if (p->free == p->total_free) { + int new_size = (p->total_free != 0) ? p->total_free * 2 : 16; /* 16 is arbitrary */ + void **new_slots = xrealloc(p->freed_slots, new_size * sizeof(void *)); + + p->freed_slots = new_slots; + p->total_free = new_size; + } + + p->freed_slots[p->free++] = ptr; + + return; +} + +void *slabs_alloc(unsigned int id) { + void *ret; + + pthread_mutex_lock(&slabs_lock); + ret = do_slabs_alloc(id); + pthread_mutex_unlock(&slabs_lock); + return ret; +} + +void slabs_free(void *ptr, unsigned int id) { + pthread_mutex_lock(&slabs_lock); + do_slabs_free(ptr, id); + pthread_mutex_unlock(&slabs_lock); +} diff --git a/sheep/slabs.h b/sheep/slabs.h new file mode 100644 index 0000000..ada2209 --- /dev/null +++ b/sheep/slabs.h @@ -0,0 +1,21 @@ +#ifndef SLABS_H +#define SLABS_H + +/* Init the subsystem. 1st argument is the limit on no. of bytes to allocate, + * 0 if no limit. 2nd argument is the growth factor; each slab will use a chunk + * size equal to the previous slab's chunk size times this factor. + */ +void slabs_init(const size_t limit, const double factor); + +/* + * Given object size, return id to use when allocating/freeing memory for object + * -1 means error: can't store such a large object + */ + +int slabs_clsid(const size_t size); + +void *slabs_alloc(unsigned int id); + +void slabs_free(void *ptr, unsigned int id); + +#endif -- 1.7.8.rc3 |