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 <[email protected]>
- 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 <[email protected]>
+ *
+ */
+
+#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 <[email protected]>
+ *
+ * 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;
+}
+
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
[Index of Archives]
[Kernel Newbies]
[Netfilter]
[Bugtraq]
[Photo]
[Stuff]
[Gimp]
[Yosemite News]
[MIPS Linux]
[ARM Linux]
[Linux Security]
[Linux RAID]
[Video 4 Linux]
[Linux for the blind]
[Linux Resources]
