| lists.openwall.net | lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC | |
|
Open Source and information security mailing list archives
| ||
|
Date: Fri, 29 Jun 2007 14:48:52 -0700
From: Davide Libenzi <davidel@...ilserver.org>
To: Linux Kernel Mailing List <linux-kernel@...r.kernel.org>
Cc: Andrew Morton <akpm@...ux-foundation.org>,
Linus Torvalds <torvalds@...ux-foundation.org>,
Ulrich Drepper <drepper@...il.com>, Ingo Molnar <mingo@...e.hu>
Subject: [patch 1/6] sys_indirect RFC - fast sequential allocator
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@...ilserver.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@...ilserver.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@...ilserver.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;
+}
+
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
Powered by blists - more mailing lists