[Sheepdog] [PATCH 3/5] sheep: add a slab allocator

Liu Yuan namei.unix at gmail.com
Tue Nov 15 04:16:44 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/slabs.c |  239 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 sheep/slabs.h |   21 +++++
 2 files changed, 260 insertions(+), 0 deletions(-)
 create mode 100644 sheep/slabs.c
 create mode 100644 sheep/slabs.h

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.6.1




More information about the sheepdog mailing list