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

[PATCH 4/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>
---

This is a replacement patch for [PATCH 3/4]
---

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

diff --git a/arch/powerpc/boot/Makefile b/arch/powerpc/boot/Makefile
index ef1bec4..895e537 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..d6aa1b1
--- /dev/null
+++ b/arch/powerpc/boot/simple_alloc.c
@@ -0,0 +1,149 @@
+/*
+ * 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 struct alloc_info *simple_find_entry(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;
+		if ((p->flags & ENTRY_IN_USE) && (p->base == (u32)ptr))
+			return p;
+	}
+	return NULL;
+}
+
+static void simple_free(void *ptr)
+{
+	struct alloc_info *p = simple_find_entry(ptr);
+
+	if (p != NULL)
+		p->flags &= ~ENTRY_IN_USE;
+}
+
+/*
+ * 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)
+{
+	struct alloc_info *p;
+	void *new;
+
+	if (size == 0) {
+		simple_free(ptr);
+		return NULL;
+	}
+
+	if (ptr == NULL)
+		return simple_malloc(size);
+
+	p = simple_find_entry(ptr);
+	if (p == NULL) /* ptr not from simple_malloc/simple_realloc */
+		return NULL;
+	if (size <= p->size) /* fits in current block */
+		return ptr;
+
+	new = simple_malloc(size);
+	memcpy(new, ptr, p->size);
+	simple_free(ptr);
+	return new;
+}
+
+/*
+ * 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);
+}

[PATCH 0/4] powerpc: Next round of bootwrapper flat dt patches

[Mark A. Greer]

I'm resumitting the entire patch series because I messed up the
threading and made some changes to simple_alloc.

Mark
---

Hi,

This patch series is a respin of--and complete replacement for--the
bootwrapper reorg patches that I sent out a while back.  I also included
the flatdevtree.c file which is the latest version that Paul sent plus
changes that I've made.

The patches apply to powerpc.git commit id:

	ba00003aa83a61b615542dd66f5af8fb4a7cee1d

Paul, it would really help the rest of us if you would apply these patches
quickly.  There are several people waiting for this work but there are so
many versions of so many patches that no one knows what to use.  Plus, it
would get more people testing/debugging the flatdevtree code.

Summary of changes:
===================

more reorg patch
----------------
- This patch includes Paul's changes to zImage.lds.S which define
  _dtb_start & _dtb_end and a related patch for the wrapper script.
- I changed main.c:start() a little so that the call to ft_init() is
  done in platform_init().  I did this because of an interface change
  to ft_init which now require some platform knowledge.
- I added a realloc() call to dt_ops so it can be passed to ft_open.

flatdevtree patch
-----------------
- I did not debug all of the flatdevtree.c code.  I only debugged
  ft_find_device, ft_get_prop, ft_set_prop and their supporting routines.
- I added a phandle table (insided the cxt) to track phandles returned by
  ft_find_device().  Now the value returned by ft_find_device() is a phandle
  which is nothing more than an index into the phandle table.  The phandle
  table contains the address of the corresponding node.  When the flat dt
  is edited/moved, the node pointers in the phandle table are updated
  accordingly so no phandles kept by the caller become stale.
- I tested shrinking, and expanding an existing property but did not test
  adding a new property.
- I'm not sure of the usefulness of the genealogy stuff but I left it there
  in case Paul has plans for it.  I did not test ft_get_parent (the only user
  of genealogy).

simple_realloc patch
--------------------
- The flatdevtree code needs a realloc now so that is implemented in here.
- As the name implies, it is a simple allocator which uses a table to track
  what's been allocated.  simple_alloc_init() let's the caller set where
  the heap is, its size, the granularity of its allocations, and how many
  entries the table has.
- Once a slot in the table is used, its base & size are set.  This allows
  the code to be much simpler.

non-OF serial console patch
---------------------------
- I decided not to look for a /cpus/<some cpu>/64-bit property and instead
  get either 1 or 2 "32-bit things" from the uart's 'virtual-reg' property.
  If there is 1, its 32-bits; if its 2, its 64-bits.

Mark

[PATCH 4/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 |  147 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 2 files changed, 148 insertions(+), 1 deletion(-)
---

diff --git a/arch/powerpc/boot/Makefile b/arch/powerpc/boot/Makefile
index ef1bec4..895e537 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..478a381
--- /dev/null
+++ b/arch/powerpc/boot/simple_alloc.c
@@ -0,0 +1,147 @@
+/*
+ * 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 struct alloc_info *simple_find_entry(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;
+		if ((p->flags & ENTRY_IN_USE) && (p->base == (u32)ptr))
+			return p;
+	}
+	return NULL;
+}
+
+static void simple_free(void *ptr)
+{
+	struct alloc_info *p = simple_find_entry(ptr);
+
+	if (p != NULL)
+		p->flags &= ~ENTRY_IN_USE;
+}
+
+/*
+ * 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)
+{
+	struct alloc_info *p;
+	void *new;
+
+	if (size == 0) {
+		simple_free(ptr);
+		return NULL;
+	}
+
+	/* also malloc if ptr didn't come from simple_malloc/realloc */
+	if ((ptr == NULL) || ((p = simple_find_entry(ptr)) == NULL))
+		return simple_malloc(size);
+
+	if (size <= p->size) /* fits in current block */
+		return ptr;
+
+	new = simple_malloc(size);
+	memcpy(new, ptr, p->size);
+	simple_free(ptr);
+	return new;
+}
+
+/*
+ * 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);
+}

[PATCH] powerpc: change bad ptr handling in simple_alloc

[Mark A. Greer]

Some minor changes to simple_alloc.c:
 - Make simple_realloc return NULL if the ptr passed to it wasn't from a
   previous simple_malloc or simple_realloc.
 - Change tracking of base of unused memory.

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

 simple_alloc.c |   19 ++++++++++---------
 1 files changed, 10 insertions(+), 9 deletions(-)
---

diff --git a/arch/powerpc/boot/simple_alloc.c b/arch/powerpc/boot/simple_alloc.c
index 478a381..7cc3389 100644
--- a/arch/powerpc/boot/simple_alloc.c
+++ b/arch/powerpc/boot/simple_alloc.c
@@ -26,6 +26,7 @@ static struct alloc_info {
 
 static u32 tbl_entries;
 static u32 alloc_min;
+static u32 next_base;
 static u32 space_left;
 
 /*
@@ -36,20 +37,20 @@ static u32 space_left;
 static void *simple_malloc(u32 size)
 {
 	u32 i;
-	struct alloc_info *p = alloc_tbl, *prevp = NULL;
+	struct alloc_info *p = alloc_tbl;
 
 	if (size == 0)
 		goto err_out;
 
 	size = _ALIGN_UP(size, alloc_min);
 
-	for (i=0; i<tbl_entries; i++) {
+	for (i=0; i<tbl_entries; i++, p++)
 		if (!(p->flags & ENTRY_BEEN_USED)) { /* never been used */
 			if (size <= space_left) {
-				if (i > 0)
-					p->base = prevp->base + prevp->size;
+				p->base = next_base;
 				p->size = size;
 				p->flags = ENTRY_BEEN_USED | ENTRY_IN_USE;
+				next_base += size;
 				space_left -= size;
 				return (void *)p->base;
 			}
@@ -60,8 +61,6 @@ static void *simple_malloc(u32 size)
 			p->flags |= ENTRY_IN_USE;
 			return (void *)p->base;
 		}
-		prevp = p++;
-	}
 err_out:
 	return NULL;
 }
@@ -103,10 +102,12 @@ static void *simple_realloc(void *ptr, u
 		return NULL;
 	}
 
-	/* also malloc if ptr didn't come from simple_malloc/realloc */
-	if ((ptr == NULL) || ((p = simple_find_entry(ptr)) == NULL))
+	if (ptr == NULL)
 		return simple_malloc(size);
 
+	p = simple_find_entry(ptr);
+	if (p == NULL) /* ptr not from simple_malloc/simple_realloc */
+		return NULL;
 	if (size <= p->size) /* fits in current block */
 		return ptr;
 
@@ -136,7 +137,7 @@ void *simple_alloc_init(char *base, u32 
 
 	heap_base = _ALIGN_UP((u32)alloc_tbl + tbl_size, alloc_min);
 
-	alloc_tbl[0].base = heap_base;
+	next_base = heap_base;
 	space_left = heap_size;
 
 	platform_ops.malloc = simple_malloc;

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

[Mark A. Greer]

Resending patch that combines previous two patches with this subject.

Mark
---

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

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

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

diff --git a/arch/powerpc/boot/Makefile b/arch/powerpc/boot/Makefile
index ef1bec4..895e537 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..cfe3a75
--- /dev/null
+++ b/arch/powerpc/boot/simple_alloc.c
@@ -0,0 +1,149 @@
+/*
+ * 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 next_base;
+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;
+
+	if (size == 0)
+		goto err_out;
+
+	size = _ALIGN_UP(size, alloc_min);
+
+	for (i=0; i<tbl_entries; i++, p++)
+		if (!(p->flags & ENTRY_BEEN_USED)) { /* never been used */
+			if (size <= space_left) {
+				p->base = next_base;
+				p->size = size;
+				p->flags = ENTRY_BEEN_USED | ENTRY_IN_USE;
+				next_base += size;
+				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;
+		}
+err_out:
+	return NULL;
+}
+
+static struct alloc_info *simple_find_entry(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;
+		if ((p->flags & ENTRY_IN_USE) && (p->base == (u32)ptr))
+			return p;
+	}
+	return NULL;
+}
+
+static void simple_free(void *ptr)
+{
+	struct alloc_info *p = simple_find_entry(ptr);
+
+	if (p != NULL)
+		p->flags &= ~ENTRY_IN_USE;
+}
+
+/*
+ * 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 pointer to a non-freed area previously returned by
+ * simple_realloc() or simple_malloc().
+ */
+static void *simple_realloc(void *ptr, unsigned long size)
+{
+	struct alloc_info *p;
+	void *new;
+
+	if (size == 0) {
+		simple_free(ptr);
+		return NULL;
+	}
+
+	if (ptr == NULL)
+		return simple_malloc(size);
+
+	p = simple_find_entry(ptr);
+	if (p == NULL) /* ptr not from simple_malloc/simple_realloc */
+		return NULL;
+	if (size <= p->size) /* fits in current block */
+		return ptr;
+
+	new = simple_malloc(size);
+	memcpy(new, ptr, p->size);
+	simple_free(ptr);
+	return new;
+}
+
+/*
+ * 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);
+
+	next_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);
+}