Skip to contentSkip to conversation

Add TLSF heap allocator

PATCH In review Jan Kiszka 1 participant 1 message Oct 20, 2006

lore
Share & tools
lore

Jan Kiszka

author
#0 lore raw

PATCH 2/2 Add TLSF heap allocator

Based on previous split-up, the attached patch adds TLSF version 2.2.0 as an alternative heap allocator for Xenomai. It is currently limited to 32-bit platforms. It also does not yet implement extensible heap support, which may break on some PPC platforms (so far obviously the only user of this feature).

For now this allocator is intended as an experimental variant until the above issues are resolved and it is proven to work reliably across any Xenomai-enabled architecture.

---
 include/nucleus/heap.h      |    2 
 include/nucleus/tlsfalloc.h |   81 +++++++++
 ksrc/nucleus/Config.in      |    3 
 ksrc/nucleus/Kconfig        |   17 +
 ksrc/nucleus/Makefile       |    2 
 ksrc/nucleus/tlsfalloc.c    |  385 ++++++++++++++++++++++++++++++++++++++++++++
 6 files changed, 489 insertions(+), 1 deletion(-)
nucleus/tlsfalloc.h new file +81 -0
Index: include/nucleus/tlsfalloc.h
===================================================================
@@ -0,0 +1,81 @@
+/*
+ * Two Levels Segregate Fit memory allocator (TLSF)
+ * Version 2.2.0
+ *
+ * Written by Miguel Masmano Tello, adapted to Xenomai by Jan Kiszka
+ *
+ * Copyright (C) 2004,2005,2006 Miguel Masmano Tello <[email protected]>.
+ * Copyright (C) 2006 Jan Kiszka <[email protected]>.
+ *
+ * Xenomai is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published
+ * by the Free Software Foundation; either version 2 of the License,
+ * or (at your option) any later version.
+ *
+ * Xenomai is distributed in the hope that it will be useful, but
+ * WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with Xenomai; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
+ * 02111-1307, USA.
+ */
+
+#ifndef _XENO_NUCLEUS_TLSFALLOC_H
+#define _XENO_NUCLEUS_TLSFALLOC_H
+
+/* Some IMPORTANT TLSF parameters */
+#define MAX_FLI			30
+#define MAX_SLI			32
+#define MAX_LOG2_SLI		5
+#define MAX_SLI			32  /* MAX_SLI = 2^MAX_LOG2_SLI */
+
+#define FLI_OFFSET 6		/* tlsf structure just will manage blocks bigger \
+				   than 128 bytes */
+#define SMALL_BLOCK		128
+#define REAL_FLI		(MAX_FLI - FLI_OFFSET)
+
+#define XNHEAP_MINALIGNSZ	(1 << 4) /* i.e. 16 bytes */
+#define XNHEAP_MAXEXTSZ		(1 << MAX_FLI) /* i.e. 1Gb */
+
+#define xnheap_overhead(hsize,psize) \
+((sizeof(xnextent_t) + XNHEAP_MINALIGNSZ - 1) & ~(XNHEAP_MINALIGNSZ - 1))
+
+struct bhdr_struct;
+
+typedef struct free_ptr_struct {
+	struct bhdr_struct *prev;
+	struct bhdr_struct *next;
+} free_ptr_t;
+
+typedef struct bhdr_struct {
+	/* This pointer is just valid if the first bit of size is set */
+	struct bhdr_struct *prev_hdr;
+	/* The size is stored in bytes */
+	u32 size;	/* bit 0 indicates whether the block is used and
+			   bit 1 allows to know whether the previous block is free */
+	union {
+		struct free_ptr_struct free_ptr;
+		u8 buffer[sizeof(struct free_ptr_struct)];
+	} ptr;
+} bhdr_t;
+
+typedef struct tlsf_struct {
+	/* The first-level bitmap
+	   This array should have a size of REAL_FLI bits */
+	u32 fl_bitmap;
+
+	/* The second-level bitmap */
+	u32 sl_bitmap[REAL_FLI];
+
+	bhdr_t *matrix[REAL_FLI][MAX_SLI];
+} tlsf_t;
+
+typedef tlsf_t xnextend_priv_t;
+
+typedef struct xnheap_priv {
+} xnheap_priv_t;
+
+#endif /* !_XENO_NUCLEUS_TLSFALLOC_H */
nucleus/Kconfig renamed from nucleus/Kconfig.orig +17 -0
Index: ksrc/nucleus/Kconfig
===================================================================
@@ -133,6 +133,23 @@ choice
 
 config XENO_OPT_ALLOC_BSD
 	bool "BSD"
+	help
+
+	The is an enhanced version of the BSD memory allocator. Details
+	on the algorithm can be found in "Design of a General Purpose
+	Memory Allocator for the 4.3BSD Unix Kernel" by Marshall K.
+	McKusick and Michael J. Karels (USENIX 1988). Xenomai adds
+	support for extendible heaps to this model.
+
+config XENO_OPT_ALLOC_TLSF
+	bool "TLSF"
+	depends on !IA64
+	help
+
+	The TLSF heap allocator has strict O(1) complexity and keeps
+	overhead and fragmentation low. So far it is only available for
+	32-bit platforms. For more details on TLSF see
+	http://rtportal.upv.es/rtmalloc/allocators/tlsf/index.shtml.
 
 endchoice
 
nucleus/tlsfalloc.c new file +385 -0

385 lines not on this page · raw message

nucleus/Config.in renamed from nucleus/Config.in.orig +2 -1
Index: ksrc/nucleus/Config.in
===================================================================
@@ -27,7 +27,8 @@ if [ "$CONFIG_XENO_OPT_NUCLEUS" != "n" ]
 		int 'Number of registry slots' CONFIG_XENO_OPT_REGISTRY_NRSLOTS 512
 	fi
 	choice 'Heap allocator'						\
-		"BSD			CONFIG_XENO_OPT_ALLOC_BSD	BSD
+		"BSD			CONFIG_XENO_OPT_ALLOC_BSD	\
+		 TLSF			CONFIG_XENO_OPT_ALLOC_TLSF"	BSD
 	int 'Size of the system heap (Kb)' CONFIG_XENO_OPT_SYS_HEAPSZ 128
 	bool 'Interrupt shield support' CONFIG_XENO_OPT_ISHIELD
 	bool 'Optimize as pipeline head' CONFIG_XENO_OPT_PIPELINE_HEAD
nucleus/Makefile renamed from nucleus/Makefile.orig +2 -0
Index: ksrc/nucleus/Makefile
===================================================================
@@ -13,6 +13,7 @@ xeno_nucleus-$(CONFIG_XENO_OPT_PIPE) += 
 xeno_nucleus-$(CONFIG_XENO_OPT_REGISTRY) += registry.o
 
 xeno_nucleus-$(CONFIG_XENO_OPT_ALLOC_BSD) += bsdalloc.o
+xeno_nucleus-$(CONFIG_XENO_OPT_ALLOC_TLSF) += tlsfalloc.o
 
 xeno_nucleus-$(CONFIG_LTT) += ltt.o
 
@@ -35,6 +36,7 @@ opt_objs-$(CONFIG_XENO_OPT_PERVASIVE) +=
 opt_objs-$(CONFIG_XENO_OPT_PIPE) += pipe.o
 opt_objs-$(CONFIG_XENO_OPT_REGISTRY) += registry.o
 opt_objs-$(CONFIG_XENO_OPT_ALLOC_BSD) += bsdalloc.o
+opt_objs-$(CONFIG_XENO_OPT_ALLOC_TLSF) += tlsfalloc.o
 opt_objs-$(CONFIG_LTT) += ltt.o
 
 xeno_nucleus-objs += $(opt_objs-y)
nucleus/heap.h renamed from nucleus/heap.h.orig +2 -0
Index: include/nucleus/heap.h
===================================================================
@@ -46,6 +46,8 @@
 
 #if defined(CONFIG_XENO_OPT_ALLOC_BSD)
 #include <nucleus/bsdalloc.h>
+#elif defined(CONFIG_XENO_OPT_ALLOC_TLSF)
+#include <nucleus/tlsfalloc.h>
 #endif /* allocator selection */
 
 typedef struct xnextent {