[patch 1/6] sys_indirect RFC - fast sequential allocator

[patch 1/6] sys_indirect RFC - fast sequential allocator

[Davide Libenzi]

This file implements a fast, sequential allocator. Chunks of memory
are allocated in blocks of pages, and inside these blocks memory is
allocated is a sequential fashion. All the allocated memory is released
in one single sweep by freeing the backing pages. Indeed, there is not
an fsa_free() function to deallocate a single block. The user can provide
an initial allocation backing store, if needed, to avoid the alocator to
call page allocation functions for the first "in cache" allocations.
The FSA allocator provides no locking, so it is up to the caller serialize
fsa_alloc() calls if ever needed.



Signed-off-by: Davide Libenzi <davidel@xmailserver.org>


- Davide


---
 include/linux/fsalloc.h |   34 ++++++++++++++++
 lib/Makefile            |    2 
 lib/fsalloc.c           |  102 ++++++++++++++++++++++++++++++++++++++++++++++++
 3 files changed, 137 insertions(+), 1 deletion(-)

Index: linux-2.6.mod/lib/Makefile
===================================================================
--- linux-2.6.mod.orig/lib/Makefile	2007-06-29 12:12:42.000000000 -0700
+++ linux-2.6.mod/lib/Makefile	2007-06-29 12:12:45.000000000 -0700
@@ -5,7 +5,7 @@
 lib-y := ctype.o string.o vsprintf.o cmdline.o \
 	 rbtree.o radix-tree.o dump_stack.o \
 	 idr.o int_sqrt.o bitmap.o extable.o prio_tree.o \
-	 sha1.o irq_regs.o reciprocal_div.o
+	 sha1.o irq_regs.o reciprocal_div.o fsalloc.o
 
 lib-$(CONFIG_MMU) += ioremap.o
 lib-$(CONFIG_SMP) += cpumask.o
Index: linux-2.6.mod/include/linux/fsalloc.h
===================================================================
--- /dev/null	1970-01-01 00:00:00.000000000 +0000
+++ linux-2.6.mod/include/linux/fsalloc.h	2007-06-29 12:12:45.000000000 -0700
@@ -0,0 +1,34 @@
+/*
+ *  include/linux/fsalloc.h
+ *
+ *  Copyright (C) 2007  Davide Libenzi <davidel@xmailserver.org>
+ *
+ */
+
+#ifndef _LINUX_FSALLOC_H
+#define _LINUX_FSALLOC_H
+
+#ifdef __KERNEL__
+
+struct fsa_page {
+	struct fsa_page *next;
+	int order;
+	unsigned long avail;
+	void *data;
+};
+
+struct fsa_context {
+	struct fsa_page *first, *curr;
+	struct fsa_page cached;
+	int order;
+};
+
+void fsa_init(struct fsa_context *ator, void *buffer,
+	      unsigned long csize);
+void fsa_cleanup(struct fsa_context *ator);
+void *fsa_alloc(struct fsa_context *ator, unsigned long size);
+
+#endif /* __KERNEL__ */
+
+#endif /* _LINUX_FSALLOC_H */
+
Index: linux-2.6.mod/lib/fsalloc.c
===================================================================
--- /dev/null	1970-01-01 00:00:00.000000000 +0000
+++ linux-2.6.mod/lib/fsalloc.c	2007-06-29 12:12:45.000000000 -0700
@@ -0,0 +1,102 @@
+/*
+ *  lib/fsalloc.c
+ *
+ *  Copyright (C) 2007  Davide Libenzi <davidel@xmailserver.org>
+ *
+ *  This file implements a fast, sequential allocator. Chunks of memory
+ *  are allocated in blocks of pages, and inside these blocks memory is
+ *  allocated is a sequential fashion. All the allocated memory is released
+ *  in one single sweep by freeing the backing pages. Indeed, there is not
+ *  an fsa_free() function to deallocate a single block. The user can provide
+ *  an initial allocation backing store, if needed, to avoid the alocator to
+ *  call page allocation functions for the first "in cache" allocations.
+ *  The FSA allocator provides no locking, so it is up to the caller serialize
+ *  fsa_alloc() calls if ever needed.
+ */
+
+#include <linux/module.h>
+#include <linux/mm.h>
+#include <linux/mman.h>
+#include <linux/kernel.h>
+#include <linux/fsalloc.h>
+
+#define FSA_MEM_ALIGN	sizeof(unsigned long)
+#define FSA_FIT_FACTOR	8
+#define FSA_MIN_ORDER	1
+#define FSA_MAX_ORDER	8
+
+/**
+ * fsa_init - Initializes a grow-only allocator
+ *
+ * @ator:    [in] Pointer to the allocator structure
+ * @buffer:  [in] Pointer to a buffer to be used as initial cached buffer
+ *                for the allocator
+ * @csize:   [in] Size of @buffer or 0 in case @buffer is NULL
+ *
+ */
+void fsa_init(struct fsa_context *ator, void *buffer,
+	      unsigned long csize)
+{
+	ator->order = FSA_MIN_ORDER;
+	ator->cached.next = NULL;
+	ator->cached.order = -1;
+	ator->cached.avail = csize;
+	ator->cached.data = buffer;
+	ator->first = ator->curr = &ator->cached;
+}
+
+/**
+ * fsa_cleanup - Cleanups all the memory allocated by the grow-only allocator
+ *
+ * @ator:    [in] Pointer to the allocator structure
+ *
+ */
+void fsa_cleanup(struct fsa_context *ator)
+{
+	struct fsa_page *curr, *next;
+
+	for (next = ator->first; (curr = next) != NULL;) {
+		next = curr->next;
+		if (curr->order >= 0)
+			free_pages((unsigned long) curr, curr->order);
+	}
+}
+
+/**
+ * fsa_alloc - Allocated a buffer inside the grow-only allocator
+ *
+ * @ator:    [in] Pointer to the allocator structure
+ * @size:    [in] Size of the requested buffer
+ *
+ * Returns a pointer to the allocated buffer, or NULL in case of error.
+ */
+void *fsa_alloc(struct fsa_context *ator, unsigned long size)
+{
+	int order;
+	struct fsa_page *new;
+	void *data;
+
+	size = roundup(size, FSA_MEM_ALIGN);
+	if (unlikely(ator->curr->avail < size)) {
+		if (size >= (PAGE_SIZE << FSA_MAX_ORDER) - sizeof(struct fsa_page))
+			return NULL;
+		order = get_order(FSA_FIT_FACTOR * size + sizeof(struct fsa_page));
+		order = max(order, ator->order);
+		order = min(order, FSA_MAX_ORDER);
+		new = (struct fsa_page *) __get_free_pages(GFP_KERNEL, order);
+		if (!new)
+			return NULL;
+		ator->order = order;
+		new->order = order;
+		new->avail = (PAGE_SIZE << order) - sizeof(struct fsa_page);
+		new->data = (char *) new + sizeof(struct fsa_page);
+		new->next = NULL;
+		ator->curr->next = new;
+		ator->curr = new;
+	}
+	data = ator->curr->data;
+	ator->curr->data = data + size;
+	ator->curr->avail -= size;
+	return data;
+}
+