Moved the malloc system into the firmware/malloc/ directory, removed the

implementation files from the test/malloc/ directory, leaving only test
files there.

Added headers, corrected a few minor documenational errors.


git-svn-id: svn://svn.rockbox.org/rockbox/trunk@571 a1c6a512-1295-4272-9138-f99709370657

1 files changed, 384 insertions, 0 deletions

diff --git a/firmware/malloc/bmalloc.c b/firmware/malloc/bmalloc.c
new file mode 100644
index 0000000..c83bd09
--- /dev/null
+++ b/firmware/malloc/bmalloc.c
@@ -0,0 +1,384 @@
+/***************************************************************************
+ *             __________               __   ___.
+ *   Open      \______   \ ____   ____ |  | _\_ |__   _______  ___
+ *   Source     |       _//  _ \_/ ___\|  |/ /| __ \ /  _ \  \/  /
+ *   Jukebox    |    |   (  <_> )  \___|    < | \_\ (  <_> > <  <
+ *   Firmware   |____|_  /\____/ \___  >__|_ \|___  /\____/__/\_ \
+ *                     \/            \/     \/    \/            \/
+ * $Id$
+ *
+ * Copyright (C) 2002 by Daniel Stenberg
+ *
+ * All files in this archive are subject to the GNU General Public License.
+ * See the file COPYING in the source tree root for full license agreement.
+ *
+ * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY
+ * KIND, either express or implied.
+ *
+ ****************************************************************************/
+/*****************************************************************************
+ *
+ * Big (best-fit) Memory Allocation
+ *
+ * Author:  Daniel Stenberg <daniel@haxx.se>
+ *
+ * Read THOUGHTS for theories and details on implementation.
+ * 
+ ****************************************************************************/
+
+#include <stdio.h>
+#include <stdlib.h>
+
+#include "bysize.h"
+
+#ifndef TRUE
+#define TRUE 1
+#endif
+#ifndef FALSE
+#define FALSE 0
+#endif
+
+/* #define DEBUG */
+
+#define BMEM_ALIGN 64 /* resolution */ 
+
+#define BMEMERR_TOOSMALL -1
+
+/* this struct will be stored in all CHUNKS and AREAS */
+struct BlockInfo {
+  struct BlockInfo *lower;  /* previous block in memory (lower address) */
+  struct BlockInfo *higher; /* next block in memory (higher address) */
+  unsigned long info;       /* 31 bits size: 1 bit free boolean */
+#define INFO_FREE 1
+#define INFO_SIZE (~ INFO_FREE) /* inverted FREE bit pattern */
+
+  /* FREE+SIZE Could be written to use ordinary bitfields if using a smart
+     (like gcc) compiler in a manner like:
+     int size:31;
+     int free:1;
+
+     The 'higher' pointer COULD be removed completely if the size is used as
+     an index to the higher one. This would then REQUIRE the entire memory
+     pool to be contiguous and it needs a 'terminating' "node" or an extra
+     flag that informs about the end of the list.
+     */
+};
+
+/* the BLOCK list should be sorted in a lower to higher address order */
+struct BlockInfo *blockHead=NULL; /* nothing from the start */
+
+void bmalloc_status(void);
+
+
+/***********************************************************************
+ * 
+ * remove_block()
+ *
+ * Remove the block from the address-sorted list.
+ *
+ ***********************************************************************/
+
+static
+void remove_block(struct BlockInfo *block)
+{
+  if(block->lower)
+    block->lower->higher = block->higher;
+  else
+    blockHead = block->higher;
+  if(block->higher)
+    block->higher->lower = block->lower;
+}
+
+/****************************************************************************
+ *
+ * add_blocktolists()
+ *
+ * Adds the specified block at the specified place in the address-sorted
+ * list and at the appropriate place in the size-sorted.
+ *
+ ***************************************************************************/
+static
+void add_blocktolists(struct BlockInfo *block,
+		      struct BlockInfo *newblock,
+		      size_t newsize)
+{
+  struct BlockInfo *temp; /* temporary storage variable */
+  if(block) {
+    /* `block' is now a lower address than 'newblock' */
+
+    /*
+     * Check if the new CHUNK is wall-to-wall with the lower addressed
+     * one (if *that* is free)
+     */
+    if(block->info&INFO_FREE) {
+      if((char *)block + (block->info&INFO_SIZE) == (char *)newblock) {
+	/* yes sir, this is our lower address neighbour, enlarge that one
+	   pick it out from the list and recursively add that chunk and
+	   then we escape */
+
+	/* remove from size-sorted list: */
+	bmalloc_remove_chunksize((char*)block+sizeof(struct BlockInfo));
+
+	block->info += newsize; /* newsize is an even number and thus the FREE
+				   bit is untouched */
+
+	remove_block(block); /* unlink the block address-wise */
+
+	/* recursively check our lower friend(s) */
+	add_blocktolists(block->lower, block, block->info&INFO_SIZE);
+	return;
+      }
+    }
+
+    temp = block->higher;
+
+    block->higher = newblock;
+    newblock->lower = block;
+    newblock->higher = temp;
+  }
+  else {
+    /* this block should preceed the heading one */
+    temp = blockHead;
+
+    /* check if this is our higher addressed neighbour */
+    if((char *)newblock + newsize == (char *)temp) {
+
+      /* yes, we are wall-to-wall with the higher CHUNK */
+      if(temp->info&INFO_FREE) {
+	/* and the neighbour is even free, remove that one and enlarge
+	   ourselves, call add_blocktolists() recursively and then escape */
+
+	remove_block(temp); /* unlink 'temp' from list */
+
+	/* remove from size-sorted list: */
+	bmalloc_remove_chunksize((char*)temp+sizeof(struct BlockInfo) );
+
+	/* add the upper block's size on ourselves */
+	newsize += temp->info&INFO_SIZE;
+
+	/* add the new, bigger block */
+	add_blocktolists(block, newblock, newsize);
+	return;
+      }
+    }
+
+    blockHead = newblock;
+    newblock->higher = temp;
+    newblock->lower  = NULL; /* there is no lower one */
+  }
+
+  newblock->info = newsize | INFO_FREE; /* we do assume size isn't using the
+					   FREE bit */
+  bmalloc_insert_bysize((char *)newblock+sizeof(struct BlockInfo), newsize);
+}
+
+/***********************************************************************
+ *
+ * findblockbyaddr()
+ *
+ * Find the block that is just before the input block in memory. Returns NULL
+ * if none is.
+ *
+ ***********************************************************************/
+
+static
+struct BlockInfo *findblockbyaddr(struct BlockInfo *block)
+{
+  struct BlockInfo *test = blockHead;
+  struct BlockInfo *lower = NULL;
+  
+  while(test && (test < block)) {
+    lower = test;
+    test = test->higher;
+  }
+  return lower;
+}
+
+/***********************************************************************
+ *
+ * bmalloc_add_pool()
+ * 
+ * This function should be the absolutely first function to call. It sets up
+ * the memory bounds of the [first] CHUNK(s). It is possible to call this
+ * function several times to add more CHUNKs to the pool of free memory. This
+ * allows the bmalloc system to deal with non-contigous memory areas.
+ *
+ * Returns non-zero if an error occured. The memory was not added then.
+ *
+ ***********************************************************************/
+
+int bmalloc_add_pool(void *start,
+                     size_t size)
+{
+  struct BlockInfo *newblock = (struct BlockInfo *)start;
+  struct BlockInfo *block;
+
+  if(size < BMEM_ALIGN)
+    return BMEMERR_TOOSMALL;
+
+  block = findblockbyaddr( newblock );
+  /* `block' is now a lower address than 'newblock' or NULL */
+
+  if(size&1)
+    size--; /* only add even sizes */
+
+  add_blocktolists(block, newblock, size);
+
+  return 0;
+}
+
+
+#ifdef DEBUG_VERBOSE
+static void bmalloc_failed(size_t size)
+{
+  printf("*** " __FILE__ " Couldn't allocate %d bytes\n", size);
+  bmalloc_status();
+}
+#else
+#define bmalloc_failed(x)
+#endif
+
+void bmalloc_status()
+{
+  struct BlockInfo *block = blockHead;
+  long mem_free = 0;
+  long mem_used = 0;
+#if 1
+  printf("List of BLOCKS (in address order):\n");
+  while(block) {
+    printf("  START %p END %p SIZE %ld FLAG %s\n",
+	   block,
+           (char *)block+(block->info&INFO_SIZE),
+           block->info&INFO_SIZE,
+	   (block->info&INFO_FREE)?"free":"used");
+    if(block->info&INFO_FREE)
+      mem_free += block->info&INFO_SIZE;
+    else
+      mem_used += block->info&INFO_SIZE;
+    block = block->higher;
+  }
+  printf(" Used mem: %ld , free mem: %ld (total %ld)\n",
+         mem_used, mem_free, mem_used + mem_free);
+#endif
+  bmalloc_print_sizes();
+}
+
+void *bmalloc(size_t size)
+{
+  void *mem;
+
+#ifdef DEBUG_VERBOSE
+  {
+    static int count=0;
+    int realsize = size + sizeof(struct BlockInfo);
+    if(realsize%4096)
+      realsize = ((size / BMEM_ALIGN)+1) * BMEM_ALIGN;
+    printf("%d bmalloc(%d) [%d]\n", count++, size, realsize);
+  }
+#endif
+
+  size += sizeof(struct BlockInfo); /* add memory for our header */
+
+  if(size&(BMEM_ALIGN-1)) /* a lot faster than %BMEM_ALIGN but this MUST be
+			     changed if the BLOCKSIZE is not 2^X ! */
+    size = ((size / BMEM_ALIGN)+1) * BMEM_ALIGN; /* align like this */
+
+  /* get a CHUNK from the list with this size */
+  mem = bmalloc_obtainbysize ( size );
+  if(mem) {
+    /* the memory block we have got is the "best-fit" and it is already
+       un-linked from the free list */
+
+    /* now do the math to get the proper block pointer */
+    struct BlockInfo *block= (struct BlockInfo *)
+      ((char *)mem - sizeof(struct BlockInfo));
+
+    block->info &= ~INFO_FREE;
+    /* not free anymore */
+
+    if( size != (block->info&INFO_SIZE)) {
+      /* split this chunk into two pieces and return the one that fits us */
+      size_t othersize = (block->info&INFO_SIZE) - size;
+
+      if(othersize > BMEM_ALIGN) { 
+	/* prevent losing small pieces of memory due to weird alignments
+	   of the memory pool */
+
+	block->info = size;  /* set new size (leave FREE bit cleared) */
+      
+	/* Add the new chunk to the lists: */
+	add_blocktolists(block->lower,
+			 (struct BlockInfo *)((char *)block + size),
+			 othersize );
+      }
+    }
+    
+    /* Return the memory our parent may use: */
+    return (char *)block+sizeof(struct BlockInfo);
+  }
+  else {
+    bmalloc_failed(size);
+    return NULL; /* can't find any memory, fail hard */
+  }
+
+#ifdef DEBUG_VERBOSE
+  bmalloc_status();
+#endif
+  return mem;
+}
+
+void bfree(void *ptr)
+{
+  struct BlockInfo *block = (struct BlockInfo *)
+    ((char *)ptr - sizeof(struct BlockInfo));
+  size_t size;
+
+  /* setup our initial higher and lower pointers */
+  struct BlockInfo *lower = block->lower;
+  struct BlockInfo *higher = block->higher;
+
+#ifdef DEBUG_VERBOSE
+  static int freecount=0;
+  printf("%d bfree(%p)\n", freecount++, ptr);
+#endif
+  /* bind together lower addressed FREE CHUNKS */
+  if(lower && (lower->info&INFO_FREE) &&
+     ((char *)lower + (lower->info&INFO_SIZE) == (char *)block)) {
+    size = block->info&INFO_SIZE;      /* original size */
+    
+    /* remove from size-link: */
+    bmalloc_remove_chunksize((char *)lower+sizeof(struct BlockInfo));
+
+    remove_block(block);              /* unlink from address list */
+    block = lower;                    /* new base area pointer */
+    block->info += size;              /* append the new size (the FREE bit
+					 will remain untouched) */
+
+    lower = lower->lower;             /* new lower pointer */
+  }
+  /* bind together higher addressed FREE CHUNKS */
+  if(higher && (higher->info&INFO_FREE) &&
+     ((char *)block + (block->info&INFO_SIZE) == (char *)higher)) { 
+    /* append higher size, the FREE bit won't be affected */
+    block->info += (higher->info&INFO_SIZE);
+    
+    /* unlink from size list: */
+    bmalloc_remove_chunksize(higher+sizeof(struct BlockInfo));
+    remove_block(higher);             /* unlink from address list */
+    higher = higher->higher;          /* the new higher link */
+    block->higher = higher;           /* new higher link */
+  }
+  block->info &= ~INFO_FREE;   /* consider this FREE! */
+
+  block->lower = lower;
+  block->higher = higher;
+
+  bmalloc_insert_bysize((char *)block+sizeof(struct BlockInfo),
+                        block->info&INFO_SIZE);
+
+#ifdef DEBUG_VERBOSE
+  bmalloc_status();
+#endif
+
+}
+