[Sheepdog] [PATCH v3 03/12] sheep: add a slab allocator
Liu Yuan
namei.unix at gmail.com
Fri Dec 23 15:39:21 CET 2011
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
More information about the sheepdog
mailing list