[PATCH 3/4] powerpc: Add simple memory allocator to bootwrapper

[PATCH 3/4] powerpc: Add simple memory allocator to bootwrapper

[Mark A. Greer]

Provide primitive malloc, free, and realloc functions for bootwrapper.

Signed-off-by: Mark A. Greer <mgreer@mvista.com>
---

 Makefile       |    2 
 simple_alloc.c |  131 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 2 files changed, 132 insertions(+), 1 deletion(-)
---

diff --git a/arch/powerpc/boot/Makefile b/arch/powerpc/boot/Makefile
index 9aad574..2def775 100644
--- a/arch/powerpc/boot/Makefile
+++ b/arch/powerpc/boot/Makefile
@@ -41,7 +41,7 @@ zliblinuxheader := zlib.h zconf.h zutil.
 		$(addprefix $(obj)/,$(zlibheader))
 
 src-wlib := string.S stdio.c main.c flatdevtree.c flatdevtree_misc.c ns16550.c \
-		serial.c div64.S util.S $(zlib)
+		serial.c simple_alloc.c div64.S util.S $(zlib)
 src-plat := of.c
 src-boot := crt0.S $(src-wlib) $(src-plat) empty.c
 
diff --git a/arch/powerpc/boot/simple_alloc.c b/arch/powerpc/boot/simple_alloc.c
new file mode 100644
index 0000000..d746906
--- /dev/null
+++ b/arch/powerpc/boot/simple_alloc.c
@@ -0,0 +1,131 @@
+/*
+ * Implement primitive realloc(3) functionality.
+ *
+ * Author: Mark A. Greer <mgreer@mvista.com>
+ *
+ * 2006 (c) MontaVista, Software, Inc.  This file is licensed under
+ * the terms of the GNU General Public License version 2.  This program
+ * is licensed "as is" without any warranty of any kind, whether express
+ * or implied.
+ */
+
+#include <stddef.h>
+#include "types.h"
+#include "page.h"
+#include "string.h"
+#include "ops.h"
+
+#define	ENTRY_BEEN_USED	0x01
+#define	ENTRY_IN_USE	0x02
+
+static struct alloc_info {
+	u32	flags;
+	u32	base;
+	u32	size;
+} *alloc_tbl;
+
+static u32 tbl_entries;
+static u32 alloc_min;
+static u32 space_left;
+
+/*
+ * First time an entry is used, its base and size are set.
+ * An entry can be freed and re-malloc'd but its base & size don't change.
+ * Should be smart enough for needs of bootwrapper.
+ */
+static void *simple_malloc(u32 size)
+{
+	u32 i;
+	struct alloc_info *p = alloc_tbl, *prevp = NULL;
+
+	if (size == 0)
+		goto err_out;
+
+	size = _ALIGN_UP(size, alloc_min);
+
+	for (i=0; i<tbl_entries; i++) {
+		if (!(p->flags & ENTRY_BEEN_USED)) { /* never been used */
+			if (size <= space_left) {
+				if (i > 0)
+					p->base = prevp->base + prevp->size;
+				p->size = size;
+				p->flags = ENTRY_BEEN_USED | ENTRY_IN_USE;
+				space_left -= size;
+				return (void *)p->base;
+			}
+			goto err_out; /* not enough space left */
+		}
+		/* reuse an entry keeping same base & size */
+		else if (!(p->flags & ENTRY_IN_USE) && (size <= p->size)) {
+			p->flags |= ENTRY_IN_USE;
+			return (void *)p->base;
+		}
+		prevp = p++;
+	}
+err_out:
+	return NULL;
+}
+
+static void simple_free(void *ptr)
+{
+	u32 i;
+	struct alloc_info *p = alloc_tbl;
+
+	for (i=0; i<tbl_entries; i++,p++) {
+		if (!(p->flags & ENTRY_BEEN_USED))
+			break;
+		else if ((p->flags & ENTRY_IN_USE) && (p->base == (u32)ptr)) {
+			p->flags &= ~ENTRY_IN_USE;
+			break;
+		}
+	}
+}
+
+/*
+ * Change size of area pointed to by 'ptr' to 'size'.
+ * If 'ptr' is NULL, then its a malloc().  If 'size' is 0, then its a free().
+ * 'ptr' must be NULL or a value previously returned by simple_realloc().
+ */
+static void *simple_realloc(void *ptr, unsigned long size)
+{
+	if (size == 0) {
+		simple_free(ptr);
+		return NULL;
+	}
+	else if (ptr == NULL)
+		return simple_malloc(size);
+	else {
+		simple_free(ptr);
+		return simple_malloc(size);
+	}
+}
+
+/*
+ * Returns addr of first byte after heap so caller can see if it took
+ * too much space.  If so, change args & try again.
+ */
+void *simple_alloc_init(char *base, u32 heap_size, u32 granularity,
+		u32 max_allocs)
+{
+	u32 heap_base, tbl_size;
+
+	heap_size = _ALIGN_UP(heap_size, granularity);
+	alloc_min = granularity;
+	tbl_entries = max_allocs;
+
+	tbl_size = tbl_entries * sizeof(struct alloc_info);
+
+	alloc_tbl = (struct alloc_info *)_ALIGN_UP((unsigned long)base, 8);
+	memset(alloc_tbl, 0, tbl_size);
+
+	heap_base = _ALIGN_UP((u32)alloc_tbl + tbl_size, alloc_min);
+
+	alloc_tbl[0].base = heap_base;
+	space_left = heap_size;
+
+	platform_ops.malloc = simple_malloc;
+	platform_ops.free = simple_free;
+	platform_ops.realloc = simple_realloc;
+
+	return (void *)(heap_base + heap_size);
+}

Re: [PATCH 3/4] powerpc: Add simple memory allocator to bootwrapper

[David Gibson]

On Mon, Oct 09, 2006 at 11:12:46PM -0700, Mark A. Greer wrote:
> Provide primitive malloc, free, and realloc functions for bootwrapper.

[snip]
> +/*
> + * Change size of area pointed to by 'ptr' to 'size'.
> + * If 'ptr' is NULL, then its a malloc().  If 'size' is 0, then its a free().
> + * 'ptr' must be NULL or a value previously returned by simple_realloc().
> + */
> +static void *simple_realloc(void *ptr, unsigned long size)
> +{
> +	if (size == 0) {
> +		simple_free(ptr);
> +		return NULL;
> +	}
> +	else if (ptr == NULL)
> +		return simple_malloc(size);
> +	else {
> +		simple_free(ptr);
> +		return simple_malloc(size);
> +	}
> +}

Um.. the above is clearly broken, it will throw away the data in a
realloc()ed block.

-- 
David Gibson			| I'll have my music baroque, and my code
david AT gibson.dropbear.id.au	| minimalist, thank you.  NOT _the_ _other_
				| _way_ _around_!
http://www.ozlabs.org/~dgibson

Re: [PATCH 3/4] powerpc: Add simple memory allocator to bootwrapper

[Josh Boyer]

On Mon, 2006-10-09 at 23:12 -0700, Mark A. Greer wrote:
> Provide primitive malloc, free, and realloc functions for bootwrapper.

The order is a bit off here.  This should be patch 4/4, as the Makefile
needs the ns16550.c changes introduced by "[PATCH 4/4] powerpc: Add
non-OF serial console support", which should be patch 3/4.

josh

Re: [PATCH 3/4] powerpc: Add simple memory allocator to bootwrapper

[Mark A. Greer]

On Tue, Oct 10, 2006 at 04:25:38PM +1000, David Gibson wrote:
> On Mon, Oct 09, 2006 at 11:12:46PM -0700, Mark A. Greer wrote:
> > Provide primitive malloc, free, and realloc functions for bootwrapper.
> 
> [snip]
> > +/*
> > + * Change size of area pointed to by 'ptr' to 'size'.
> > + * If 'ptr' is NULL, then its a malloc().  If 'size' is 0, then its a free().
> > + * 'ptr' must be NULL or a value previously returned by simple_realloc().
> > + */
> > +static void *simple_realloc(void *ptr, unsigned long size)
> > +{
> > +	if (size == 0) {
> > +		simple_free(ptr);
> > +		return NULL;
> > +	}
> > +	else if (ptr == NULL)
> > +		return simple_malloc(size);
> > +	else {
> > +		simple_free(ptr);
> > +		return simple_malloc(size);
> > +	}
> > +}
> 
> Um.. the above is clearly broken, it will throw away the data in a
> realloc()ed block.

Yes, too much of a hurry, I guess.  I'll fix.

Mark

Re: [PATCH 3/4] powerpc: Add simple memory allocator to bootwrapper

[Mark A. Greer]

On Tue, Oct 10, 2006 at 07:51:08AM -0500, Josh Boyer wrote:
> On Mon, 2006-10-09 at 23:12 -0700, Mark A. Greer wrote:
> > Provide primitive malloc, free, and realloc functions for bootwrapper.
> 
> The order is a bit off here.  This should be patch 4/4, as the Makefile
> needs the ns16550.c changes introduced by "[PATCH 4/4] powerpc: Add
> non-OF serial console support", which should be patch 3/4.

Oops, I switched the order at the last minute.  I'll switch back.

Mark