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

9 files changed, 1772 insertions, 0 deletions

diff --git a/firmware/malloc/Makefile b/firmware/malloc/Makefile
new file mode 100644
index 0000000..d4c6436
--- /dev/null
+++ b/firmware/malloc/Makefile
@@ -0,0 +1,40 @@
+#             __________               __   ___.
+#   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.
+#
+
+TARGET = libdmalloc.a
+
+LIBOBJS = dmalloc.o bmalloc.o bysize.o
+
+# define this to talk a lot in runtime
+# -DDEBUG_VERBOSE 
+CFLAGS = -g -Wall -DDEBUG
+CC = gcc
+AR = ar
+
+LDFLAGS = -L. -ldmalloc
+
+all: $(TARGET)
+
+clean:
+	rm -f core *~ $(TARGET) $(LIBOBJS)
+
+$(TARGET): $(LIBOBJS)
+	$(AR) ruv $(TARGET) $(LIBOBJS)
+
+bmalloc.o: bmalloc.c bysize.h
+bysize.o: bysize.c
+dmalloc.o: dmalloc.c
diff --git a/firmware/malloc/README b/firmware/malloc/README
new file mode 100644
index 0000000..336bd57
--- /dev/null
+++ b/firmware/malloc/README
@@ -0,0 +1,21 @@
+Package: dbestfit - a dynamic best-fit memory allocator
+Date:	 1996 - 2002
+Version: 3.3
+Author:	 Daniel Stenberg <daniel@haxx.se>
+License: MIT originally, files in the Rockbox project are GPL licensed.
+
+ I wrote the dmalloc part for small allocation sizes to improve the behavior
+of the built-in (first-fit) allocator found in pSOS, during late 1996 and
+spring 1997.
+
+ I wrote the bmalloc part (best-fit with optional splay-tree sorting) just for
+the fun of it and to see how good malloc() implementation I could make. The
+quality of my implementation is still left to be judged in real-world tests.
+
+TODO:
+ * Remove the final not-so-very-nice loop in dmalloc.c that checks for a block
+   with free fragments (when the list gets longer too much time might be spent
+   in that loop).
+
+ * Make a separate application that samples the memory usage of a program
+   and is capable of replaying it (in order to test properly).
diff --git a/firmware/malloc/THOUGHTS b/firmware/malloc/THOUGHTS
new file mode 100644
index 0000000..2751736
--- /dev/null
+++ b/firmware/malloc/THOUGHTS
@@ -0,0 +1,170 @@
+		    ====================================
+		    Memory Allocation Algorithm Theories
+		    ====================================
+
+GOAL
+  It is intended to be a 100% working memory allocation system. It should be
+  capable of replacing an ordinary Operating System's own routines. It should
+  work good in a multitasking, shared memory, non-virtual memory environment
+  without clogging the memory. Primary aimed for small machines, CPUs and
+  memory amounts.
+
+  I use a best-fit algorithm with a slight overhead in order to increase speed
+  a lot. It should remain scalable and work good with very large amount of
+  memory and free/used memory blocks too.
+
+TERMINOLOGY
+
+  FRAGMENT - small identically sized parts of a larger BLOCK, they are _not_
+             allocated when traversed in lists etc 
+  BLOCK    - large memory area, if used for FRAGMENTS, they are linked in a
+	     lists. One list for each FRAGMENT size supported.
+  TOP      - head struct that holds information about and points to a chain
+	     of BLOCKS for a particular FRAGMENT size.
+  CHUNK    - a contiguous area of free memory
+
+MEMORY SYSTEM
+
+  We split the system in two parts. One part allocates small memory amounts
+  and one part allocates large memory amounts, but all allocations are done
+  "through" the small-part-system. There is an option to use only the small
+  system (and thus use the OS for large blocks) or the complete package.
+
+##############################################################################
+ SMALL SIZE ALLOCATIONS
+##############################################################################
+
+  Keywords for this system is 'Deferred Coalescing' and 'quick lists'.
+
+  ALLOC
+
+  * Small allocations are "aligned" upwards to a set of preset sizes. In the
+    current implementation I use 20, 28, 52, 116, 312, 580, 1016, 2032 bytes.
+    Memory allocations of these sizes are referred to as FRAGMENTS.
+    (The reason for these specific sizes is the requirement that they must be
+    32-bit aligned and fit as good as possible within 4064 bytes.)
+
+  * Allocations larger than 2032 will get a BLOCK for that allocation only.
+
+  * Each of these sizes has it's own TOP. When a FRAGMENT is requested, a
+    larger BLOCK will be allocated and divided into many FRAGMENTS (all of the
+    same size). TOP points to a list with BLOCKS that contains FRAGMENTS of
+    the same size. Each BLOCK has a 'number of free FRAGMENTS' counter and so
+    has each TOP (for the entire chain).
+
+  * A BLOCK is around 4064 bytes plus the size of the information header. This
+    size is adjusted to make the allocation of the big block not require more
+    than 4096 bytes. (This might not be so easy to be sure of, if you don't
+    know how the big-block system works, but the BMALLOC system uses an
+    extra header of 12 bytes and the header for the FRAGMENT BLOCK is 20 bytes
+    in a general 32-bit environment.)
+
+  * In case the allocation of a BLOCK fails when a FRAGMENT is required, the
+    next size of FRAGMENTS will be checked for a free FRAGMENT. First when the
+    larger size lists have been tested without success it will fail for real.
+
+  FREE
+
+  * When FRAGMENTS are freed so that a BLOCK becomes non-used, it is returned
+    to the system.
+
+  * FREEing a fragment adds the buffer in a LIFO-order. That means that the
+    next request for a fragment from the same list, the last freed buffer will
+    be returned first.
+
+  REALLOC
+
+  * REALLOCATION of a FRAGMENT does first check if the new size would fit
+    within the same FRAGMENT and if it would use the same FRAGMENT size. If it
+    does and would, the same pointer is returned.
+
+  OVERHEAD
+
+   Yes, there is an overhead on small allocations (internal fragmentation).
+  Yet, I do believe that small allocations more often than larger ones are
+  used dynamically. I believe that a large overhead is not a big problem if it
+  remains only for a while. The big gain is with the extreme speed we can GET
+  and RETURN small allocations. This has yet to be proven. I am open to other
+  systems of dealing with the small ones, but I don`t believe in using the
+  same system for all sizes of allocations.
+
+  IMPROVEMENT
+
+   An addition to the above described algorithm is the `save-empty-BLOCKS-a-
+  while-afterwards`. It will be used when the last used FRAGMENT within a
+  BLOCK is freed. The BLOCK will then not get returned to the system until "a
+  few more" FRAGMENTS have been freed in case the last [few] freed FRAGMENTS
+  are allocated yet again (and thus prevent the huge overhead of making
+  FRAGMENTS in a BLOCK). The "only" drawback of such a SEBAWA concept is
+  that it would mean an even bigger overhead...
+
+  HEADERS (in allocated data)
+
+    FRAGMENTS - 32-bit pointer to its parent BLOCK (lowest bit must be 0)
+    BLOCK     - 32-bit size (lowest bit must be 1 to separate this from
+		FRAGMENTS)
+
+##############################################################################
+ LARGER ALLOCATIONS
+##############################################################################
+
+  If the requested size is larger than the largest FRAGMENT size supported,
+  the allocation will be made for this memory area alone, or if a BLOCK is
+  allocated to fit lots of FRAGMENTS a large block is also desired.
+
+  * We add memory to the "system" with the add_pool() function call. It
+    specifies the start and size of the new block of memory that will be
+    used in this memory allocation system. Several add_pool() calls are
+    supported and they may or may not add contiguous memory.
+
+  * Make all blocks get allocated aligned to BLOCKSIZE (sometimes referred to
+    as 'grain size'), 64 bytes in my implementation. Reports tell us there is
+    no real gain in increasing the size of the align.
+
+  * We link *all* pieces of memory (AREAS), free or not free. We keep the list
+    in address order and thus when a FREE() occurs we know instantly if there
+    are FREE CHUNKS wall-to-wall. No list "travels" needed. Requires some
+    extra space in every allocated BLOCK. Still needs to put the new CHUNK in
+    the right place in size-sorted list/tree. All memory areas, allocated or
+    not, contain the following header:
+    - size of this memory area (31 bits)
+    - FREE status (1 bit)
+    - pointer to the next AREA closest in memory (32 bits)
+    - pointer to the prev AREA closest in memory (32 bits)
+    (Totally 12 bytes)
+
+  * Sort all FREE CHUNKS in size-order. We use a SPLAY TREE algorithm for
+    maximum speed. Data/structs used for the size-sorting functions are kept
+    in an abstraction layer away from this since it is really not changing
+    anything (except executing speed).
+
+  ALLOC (RSIZE - requested size, aligned properly)
+
+  * Fetch a CHUNK that RSIZE fits within. If the found CHUNK is larger than
+    RSIZE, split it and return the RSIZE to the caller. Link the new CHUNK
+    into the list/tree.
+
+  FREE (AREA - piece of memory that is returned to the system)
+
+  * Since the allocated BLOCK has kept its link-pointers, we can without
+    checking any list instantly see if there are any FREE CHUNKS that are
+    wall-to-wall with the AREA (both sides). If the AREA *is* wall-to-wall
+    with one or two CHUNKS that or they are unlinked from the lists, enlarged
+    and re-linked into the lists.
+
+  REALLOC
+ 
+  * There IS NO realloc() of large blocks, they are performed in the previous
+    layer (dmalloc).
+
+
+##############################################################################
+ FURTHER READING
+##############################################################################
+ 
+ * "Dynamic Storage Allocation: A Survey and Critical Review" (Paul R. Wilson,
+   Mark S. Johnstone, Michael Neely, David Boles)
+   ftp://ftp.cs.utexas.edu/pub/garbage/allocsrv.ps
+
+ * "A Memory Allocator" (Doug Lea)
+   http://g.oswego.edu/dl/html/malloc.html
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
+
+}
+
diff --git a/firmware/malloc/bmalloc.h b/firmware/malloc/bmalloc.h
new file mode 100644
index 0000000..b97236d
--- /dev/null
+++ b/firmware/malloc/bmalloc.h
@@ -0,0 +1,24 @@
+/***************************************************************************
+ *             __________               __   ___.
+ *   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.
+ *
+ ****************************************************************************/
+int bmalloc_add_pool(void *start, size_t size);
+void bmalloc_status(void);
+
+void *bmalloc(size_t size);
+void bfree(void *ptr);
+
diff --git a/firmware/malloc/bysize.c b/firmware/malloc/bysize.c
new file mode 100644
index 0000000..c8e2759
--- /dev/null
+++ b/firmware/malloc/bysize.c
@@ -0,0 +1,451 @@
+/***************************************************************************
+ *             __________               __   ___.
+ *   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.
+ *
+ ****************************************************************************/
+/*****************************************************************************
+ *
+ * Size-sorted list/tree functions.
+ *
+ * Author:  Daniel Stenberg
+ * Date:    March 7, 1997
+ * Version: 2.0
+ * Email:   daniel@haxx.se
+ *
+ * v2.0
+ * - Added SPLAY TREE functionality.
+ * 
+ * Adds and removes CHUNKS from a list or tree.
+ *
+ ****************************************************************************/
+
+#include <stdio.h>
+#include <stdlib.h>
+
+#define SPLAY /* we use the splay version as that is much faster when the
+                 amount of blocks grow */
+
+#ifndef TRUE
+#define TRUE 1
+#endif
+#ifndef FALSE
+#define FALSE 0
+#endif
+
+#ifndef SPLAY /* these routines are for the non-splay version */
+
+struct ChunkInfo {
+  struct ChunkInfo *larger;
+  struct ChunkInfo *smaller;
+  size_t size;
+};
+
+/* the CHUNK list anchor */
+struct ChunkInfo *chunkHead=NULL;
+
+/***********************************************************************
+
+  findchunkbysize()
+
+  Find the chunk that is smaller than the input size. Returns
+  NULL if none is.
+
+  **********************************************************************/
+
+static struct ChunkInfo *findchunkbysize(size_t size)
+{
+  struct ChunkInfo *test = chunkHead;
+  struct ChunkInfo *smaller = NULL;
+  while(test && (test->size < size)) {
+    smaller = test;
+    test = test->larger;
+  }
+  return smaller;
+}
+
+/***********************************************************************
+  
+  remove_chunksize()
+
+  Remove the chunk from the size-sorted list.
+  ***********************************************************************/
+
+void bmalloc_remove_chunksize(void *data)
+{
+  struct ChunkInfo *chunk = (struct ChunkInfo *)data;
+  if(chunk->smaller)
+    chunk->smaller->larger = chunk->larger;
+  else {
+    /* if this has no smaller, this is the head */
+    chunkHead = chunk->larger; /* new head */
+  }
+  if(chunk->larger)
+    chunk->larger->smaller = chunk->smaller;
+}
+
+void bmalloc_insert_bysize(char *data, size_t size)
+{
+  struct ChunkInfo *newchunk = (struct ChunkInfo *)data;
+  struct ChunkInfo *chunk = findchunkbysize ( size );
+
+  newchunk->size = size;
+
+  if(chunk) {
+    /* 'chunk' is smaller than size, append the new chunk ahead of this */
+    newchunk->smaller = chunk;
+    newchunk->larger = chunk->larger;
+    if(chunk->larger)
+      chunk->larger->smaller = newchunk;
+    chunk->larger = newchunk;
+  }
+  else {
+    /* smallest CHUNK around, append first in the list */
+    newchunk->larger = chunkHead;
+    newchunk->smaller = NULL;
+
+    if(chunkHead)
+      chunkHead->smaller = newchunk;
+    chunkHead = newchunk;
+  }
+}
+
+char *bmalloc_obtainbysize( size_t size)
+{
+  struct ChunkInfo *chunk = findchunkbysize( size );
+
+  if(!chunk) {
+    if(size <= (chunkHead->size))
+      /* there is no smaller CHUNK, use the first one (if we fit within that)
+       */
+      chunk = chunkHead;
+  }
+  else
+    /* we're on the last CHUNK that is smaller than requested, step onto
+       the bigger one */
+    chunk = chunk->larger;
+
+  if(chunk) {
+    bmalloc_remove_chunksize( chunk ); /* unlink size-wise */
+    return (char *)chunk;
+  }
+  else
+    return NULL;
+}
+
+void bmalloc_print_sizes(void)
+{
+  struct ChunkInfo *chunk = chunkHead;
+  printf("List of CHUNKS (in size order):\n");
+#if 1
+  while(chunk) {
+    printf("  START %p END %p SIZE %d\n",
+	   chunk, (char *)chunk+chunk->size, chunk->size);
+    chunk = chunk->larger;
+  }
+#endif
+  printf("End of CHUNKS:\n");
+}
+
+#else /* Here follows all routines dealing with the SPLAY TREES */
+
+typedef struct tree_node Tree;
+struct tree_node {
+  Tree *smaller; /* smaller node */
+  Tree *larger;  /* larger node */
+  Tree *same;    /* points to a node with identical key */
+  int key;       /* the "sort" key */
+};
+
+Tree *chunkHead = NULL; /* the root */
+
+#define compare(i,j) ((i)-(j))
+
+/* Set this to a key value that will *NEVER* appear otherwise */
+#define KEY_NOTUSED -1
+
+/*
+ * Splay using the key i (which may or may not be in the tree.) The starting
+ * root is t. Weight fields are maintained.
+ */
+static
+Tree * splay (int i, Tree *t)
+{
+  Tree N, *l, *r, *y;
+  int comp;
+    
+  if (t == NULL)
+    return t;
+  N.smaller = N.larger = NULL;
+  l = r = &N;
+
+  for (;;) {
+    comp = compare(i, t->key);
+    if (comp < 0) {
+      if (t->smaller == NULL)
+	break;
+      if (compare(i, t->smaller->key) < 0) {
+	y = t->smaller;                           /* rotate smaller */
+	t->smaller = y->larger;
+	y->larger = t;
+
+	t = y;
+	if (t->smaller == NULL)
+	  break;
+      }
+      r->smaller = t;                               /* link smaller */
+      r = t;
+      t = t->smaller;
+    }
+    else if (comp > 0) {
+      if (t->larger == NULL)
+	break;
+      if (compare(i, t->larger->key) > 0) {
+	y = t->larger;                          /* rotate larger */
+	t->larger = y->smaller;
+	y->smaller = t;
+	t = y;
+	if (t->larger == NULL)
+	  break;
+      }
+      l->larger = t;                              /* link larger */
+      l = t;
+      t = t->larger;
+    }
+    else {
+      break;
+    }
+  }
+
+  l->larger = r->smaller = NULL;
+
+  l->larger = t->smaller;                                /* assemble */
+  r->smaller = t->larger;
+  t->smaller = N.larger;
+  t->larger = N.smaller;
+
+  return t;
+}
+
+/* Insert key i into the tree t.  Return a pointer to the resulting tree or
+   NULL if something went wrong. */
+static
+Tree *insert(int i, Tree *t, Tree *new)
+{
+  if (new == NULL) {
+    return t;
+  }
+
+  if (t != NULL) {
+    t = splay(i,t);
+    if (compare(i, t->key)==0) {
+      /* it already exists one of this size */
+
+      new->same = t;
+      new->key = i;
+      new->smaller = t->smaller;
+      new->larger = t->larger;
+
+      t->smaller = new;
+      t->key = KEY_NOTUSED;
+
+      return new; /* new root node */
+    }
+  }
+
+  if (t == NULL) {
+    new->smaller = new->larger = NULL;
+  }
+  else if (compare(i, t->key) < 0) {
+    new->smaller = t->smaller;
+    new->larger = t;
+    t->smaller = NULL;
+  }
+  else {
+    new->larger = t->larger;
+    new->smaller = t;
+    t->larger = NULL;
+  }
+  new->key = i;
+
+  new->same = NULL; /* no identical node (yet) */
+
+  return new;
+}
+
+/* Finds and deletes the best-fit node from the tree. Return a pointer to the
+   resulting tree.  best-fit means the smallest node that fits the requested
+   size. */
+static
+Tree *removebestfit(int i, Tree *t, Tree **removed)
+{
+  Tree *x;
+
+  if (t==NULL)
+    return NULL;
+  t = splay(i,t);
+  if(compare(i, t->key) > 0) {
+    /* too small node, try the larger chain */
+    if(t->larger)
+      t=splay(t->larger->key, t);
+    else {
+      /* fail */
+      *removed = NULL;
+      return t;
+    }
+  }
+
+  if (compare(i, t->key) <= 0) {               /* found it */
+
+    /* FIRST! Check if there is a list with identical sizes */
+    x = t->same;
+    if(x) {
+      /* there is, pick one from the list */
+
+      /* 'x' is the new root node */
+
+      x->key = t->key;
+      x->larger = t->larger;
+      x->smaller = t->smaller;
+      *removed = t;
+      return x; /* new root */
+    }
+
+    if (t->smaller == NULL) {
+      x = t->larger;
+    }
+    else {
+      x = splay(i, t->smaller);
+      x->larger = t->larger;
+    }
+    *removed = t;
+
+    return x;
+  }
+  else {
+    *removed = NULL; /* no match */
+    return t;        /* It wasn't there */
+  }
+}
+
+
+/* Deletes the node we point out from the tree if it's there. Return a pointer
+   to the resulting tree.  */
+static
+Tree *removebyaddr(Tree *t, Tree *remove)
+{
+  Tree *x;
+
+  if (!t || !remove)
+    return NULL;
+
+  if(KEY_NOTUSED == remove->key) {
+    /* just unlink ourselves nice and quickly: */
+    remove->smaller->same = remove->same;
+    if(remove->same)
+      remove->same->smaller = remove->smaller;
+    /* voila, we're done! */
+    return t;
+  }
+
+  t = splay(remove->key,t);
+
+  /* Check if there is a list with identical sizes */
+
+  x = t->same;
+  if(x) {
+    /* 'x' is the new root node */
+
+    x->key = t->key;
+    x->larger = t->larger;
+    x->smaller = t->smaller;
+      
+    return x; /* new root */
+  }
+
+  /* Remove the actualy root node: */
+
+  if (t->smaller == NULL) {
+    x = t->larger;
+  }
+  else {
+    x = splay(remove->key, t->smaller);
+    x->larger = t->larger;
+  }
+
+  return x;
+}
+
+#ifdef DEBUG
+static
+int printtree(Tree * t, int d, char output)
+{
+  int distance=0;
+  Tree *node;
+  int i;
+  if (t == NULL)
+    return 0;
+  distance += printtree(t->larger, d+1, output);
+  for (i=0; i<d; i++)
+    if(output)
+      printf("  ");
+
+  if(output) {
+    printf("%d[%d]", t->key, i);
+  }
+  
+  for(node = t->same; node; node = node->same) {
+    distance += i; /* this has the same "virtual" distance */
+
+    if(output)
+      printf(" [+]");
+  }
+  if(output)
+    puts("");
+
+  distance += i;
+  distance += printtree(t->smaller, d+1, output);
+  return distance;
+}
+#endif
+
+/* Here follow the look-alike interface so that the tree-function names are
+   the same as the list-ones to enable easy interchange */
+
+void bmalloc_remove_chunksize(void *data)
+{
+  chunkHead = removebyaddr(chunkHead, data);
+}
+
+void bmalloc_insert_bysize(char *data, size_t size)
+{
+  chunkHead = insert(size, chunkHead, (Tree *)data);
+}
+
+char *bmalloc_obtainbysize( size_t size)
+{
+  Tree *receive;
+  chunkHead = removebestfit(size, chunkHead, &receive);
+  return (char *)receive;
+}
+
+#ifdef DEBUG
+void bmalloc_print_sizes(void)
+{
+  printtree(chunkHead, 0, 1);
+}
+#endif
+
+#endif
diff --git a/firmware/malloc/bysize.h b/firmware/malloc/bysize.h
new file mode 100644
index 0000000..c462132
--- /dev/null
+++ b/firmware/malloc/bysize.h
@@ -0,0 +1,24 @@
+/***************************************************************************
+ *             __________               __   ___.
+ *   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.
+ *
+ ****************************************************************************/
+void bmalloc_remove_chunksize(void *data);
+void bmalloc_insert_bysize(char *data, size_t size);
+char *bmalloc_obtainbysize( size_t size);
+#ifdef DEBUG
+void bmalloc_print_sizes(void);
+#endif
diff --git a/firmware/malloc/dmalloc.c b/firmware/malloc/dmalloc.c
new file mode 100644
index 0000000..cfb2508
--- /dev/null
+++ b/firmware/malloc/dmalloc.c
@@ -0,0 +1,623 @@
+/***************************************************************************
+ *             __________               __   ___.
+ *   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.
+ *
+ ****************************************************************************/
+/*****************************************************************************
+ *
+ * Dynamic small-blocks Memory Allocation
+ *
+ * Author:  Daniel Stenberg <daniel@haxx.se>
+ *
+ * Read THOUGHTS for theories and details on the implementation.
+ *
+ *****************************************************************************/
+
+#include <stdio.h>
+#include <string.h> /* memcpy */
+
+#ifdef DEBUG
+#include <stdarg.h>
+#endif
+
+#ifdef PSOS
+#include <psos.h>
+#define SEMAPHORE /* the PSOS routines use semaphore protection */
+#else
+#include <stdlib.h> /* makes the PSOS complain on the 'size_t' typedef */
+#endif
+
+#define BMALLOC /* we use our own big-malloc system */
+
+#ifdef BMALLOC
+#include "bmalloc.h"
+#endif
+
+/* Each TOP takes care of a chain of BLOCKS */
+struct MemTop {
+  struct MemBlock *chain; /* pointer to the BLOCK chain */
+  long nfree;             /* total number of free FRAGMENTS in the chain */
+  short nmax;             /* total number of FRAGMENTS in this kind of BLOCK */
+  size_t fragsize;        /* the size of each FRAGMENT */
+
+#ifdef SEMAPHORE /* if we're protecting the list with SEMAPHORES */
+  long semaphore_id;      /* semaphore used to lock this particular list */
+#endif
+
+};
+
+/* Each BLOCK takes care of an amount of FRAGMENTS */
+struct MemBlock {
+  struct MemTop *top;     /* our TOP struct */
+  struct MemBlock *next;  /* next BLOCK */
+  struct MemBlock *prev;  /* prev BLOCK */
+  
+  struct MemFrag *first;  /* the first free FRAGMENT in this block */
+
+  short nfree;            /* number of free FRAGMENTS in this BLOCK */
+};
+
+/* This is the data kept in all _free_ FRAGMENTS */
+struct MemFrag {
+  struct MemFrag *next;   /* next free FRAGMENT */
+  struct MemFrag *prev;   /* prev free FRAGMENT */
+};
+
+/* This is the data kept in all _allocated_ FRAGMENTS and BLOCKS. We add this
+   to the allocation size first thing in the ALLOC function to make room for
+   this smoothly. */
+
+struct MemInfo {
+  void *block;
+  /* which BLOCK is our father, if BLOCK_BIT is set it means this is a
+     stand-alone, large allocation and then the rest of the bits should be
+     treated as the size of the block */
+#define BLOCK_BIT 1
+};
+
+/* ---------------------------------------------------------------------- */
+/*                                 Defines                                */
+/* ---------------------------------------------------------------------- */
+
+#ifdef DEBUG_VERBOSE
+#define MEMINCR(addr,x) memchange(addr, x)
+#define MEMDECR(addr,x) memchange(addr,-(x))
+#else
+#define MEMINCR(a,x)
+#define MEMDECR(a,x)
+#endif
+
+/* The low level functions used to get memory from the OS and to return memory
+   to the OS, we may also define a stub that does the actual allocation and
+   free, these are the defined function names used in the dmalloc system
+   anyway: */
+#ifdef PSOS
+
+#ifdef DEBUG
+#define DMEM_OSALLOCMEM(size,pointer,type) pointer=(type)dbgmalloc(size)
+#define DMEM_OSFREEMEM(x) dbgfree(x)
+#else
+#define DMEM_OSALLOCMEM(size,pointer,type) rn_getseg(0,size,RN_NOWAIT,0,(void **)&pointer)
+/* Similar, but this returns the memory */
+#define DMEM_OSFREEMEM(x) rn_retseg(0, x)
+#endif
+
+/* Argument: <id> */
+#define SEMAPHOREOBTAIN(x) sm_p(x, SM_WAIT, 0)
+/* Argument: <id> */
+#define SEMAPHORERETURN(x) sm_v(x)
+/* Argument: <name> <id-variable name> */
+#define SEMAPHORECREATE(x,y) sm_create(x, 1, SM_FIFO, (ULONG *)&(y))
+
+#else
+#ifdef BMALLOC /* use our own big-memory-allocation system */
+#define DMEM_OSALLOCMEM(size,pointer,type) pointer=(type)bmalloc(size)
+#define DMEM_OSFREEMEM(x) bfree(x)
+#elif DEBUG
+#define DMEM_OSALLOCMEM(size,pointer,type) pointer=(type)dbgmalloc(size)
+#define DMEM_OSFREEMEM(x) dbgfree(x)
+#else
+#define DMEM_OSALLOCMEM(size,pointer,type) pointer=(type)malloc(size)
+#define DMEM_OSFREEMEM(x) free(x)
+#endif
+#endif
+
+
+/* the largest memory allocation that is made a FRAGMENT: (grab the highest
+   number from the list below) */
+#define DMEM_LARGESTSIZE 2032
+
+/* The total size of a BLOCK used for FRAGMENTS
+   In order to make this use only *1* even alignment from the big-block-
+   allocation-system (possible the bmalloc() system also written by me)
+   we need to subtract the [maximum] struct sizes that could get added all
+   the way through to the grab from the memory. */
+#define DMEM_BLOCKSIZE 4064 /* (4096 - sizeof(struct MemBlock) - 12) */
+
+/* Since the blocksize isn't an even 2^X story anymore, we make a table with
+   the FRAGMENT sizes and amounts that fills up a BLOCK nicely */
+
+/* a little 'bc' script that helps us maximize the usage:
+   - for 32-bit aligned addresses (SPARC crashes otherwise):
+   for(i=20; i<2040; i+=4) { a=4064/i; if(a*i >= 4060) { {i;} } }
+
+   I try to approximate a double of each size, starting with ~20. We don't do
+   ODD sizes since several CPU flavours dump core when accessing such
+   addresses. We try to do 32-bit aligned to make ALL kinds of CPUs to remain
+   happy with us.
+   */
+
+const static short qinfo[]= {
+  20, 28, 52, 116, 312, 580, 1016, 2032
+};
+
+#define MIN(x,y) ((x)<(y)?(x):(y))
+
+/* ---------------------------------------------------------------------- */
+/*                                 Globals                                */
+/* ---------------------------------------------------------------------- */
+
+/* keeper of the chain of BLOCKS */
+static struct MemTop top[ sizeof(qinfo)/sizeof(qinfo[0]) ];
+
+/* ---------------------------------------------------------------------- */
+/*                          Start of the real code                        */
+/* ---------------------------------------------------------------------- */
+
+#ifdef DEBUG
+/************
+ * A few functions that are verbose and tells us about the current status
+ * of the dmalloc system
+ ***********/
+
+void dmalloc_status(void)
+{
+  int i;
+  int used;
+  int num;
+  int totalfree=0;
+  struct MemBlock *block;
+  for(i=0; i<sizeof(qinfo)/sizeof(qinfo[0]);i++) {
+    block = top[i].chain;
+    used = 0;
+    num = 0;
+    while(block) {
+      used += top[i].nmax-block->nfree;
+      num++;
+      block = block->next;
+    }
+    printf("Q %d (FRAG %4d), USED %4d FREE %4ld (SIZE %4ld) BLOCKS %d\n",
+	   i, top[i].fragsize, used, top[i].nfree,
+	   top[i].nfree*top[i].fragsize, num);
+    totalfree += top[i].nfree*top[i].fragsize;
+  }
+  printf("Total unused memory stolen by dmalloc: %d\n", totalfree);
+}
+#endif
+
+#ifdef DEBUG_VERBOSE
+static void dmalloc_failed(size_t size)
+{
+  printf("*** " __FILE__ " Couldn't allocate %d bytes\n", size);
+  dmalloc_status();
+}
+#else
+#define dmalloc_failed(x)
+#endif
+
+#ifdef DEBUG_VERBOSE
+
+#define DBG(x) syslog x
+
+void syslog(char *fmt, ...)
+{
+  va_list ap;
+  va_start(ap, fmt);
+  vfprintf(stdout, fmt, ap);
+  va_end(ap);
+}
+
+void memchange(void *a, int x)
+{
+  static int memory=0;
+  static int count=0;
+  static int max=0;
+  if(memory > max)
+    max = memory;
+  memory += x;
+  DBG(("%d. PTR %p / %d TOTAL %d MAX %d\n", ++count, a, x, memory, max));
+}
+#else
+#define DBG(x)
+#endif
+
+/****************************************************************************
+ *
+ * FragBlock()
+ *
+ * This function makes FRAGMENTS of the BLOCK sent as argument.
+ *
+ ***************************************************************************/
+
+static void FragBlock(char *memp, int size)
+{
+  struct MemFrag *frag=(struct MemFrag *)memp;
+  struct MemFrag *prev=NULL; /* no previous in the first round */
+  int count=0;
+  while((count+size) <= DMEM_BLOCKSIZE) {
+    frag->next = (struct MemFrag *)((char *)frag + size);
+    frag->prev = prev;
+    prev = frag;
+    (char *)frag += size;
+    count += size;
+  }
+  prev->next = NULL; /* the last one has no next struct */
+}
+
+/***************************************************************************
+ *
+ * dmalloc_initialize();
+ *
+ * Call before the first dmalloc(). Inits a few memory things.
+ *
+ **************************************************************************/
+void dmalloc_initialize(void)
+{
+  int i;
+  /* Setup the nmax and fragsize fields of the top structs */
+  for(i=0; i< sizeof(qinfo)/sizeof(qinfo[0]); i++) {
+    top[i].fragsize = qinfo[i];
+    top[i].nmax = DMEM_BLOCKSIZE/qinfo[i];
+
+#ifdef PSOS
+    /* for some reason, these aren't nulled from start: */
+    top[i].chain = NULL; /* no BLOCKS */
+    top[i].nfree = 0;    /* no FRAGMENTS */
+#endif
+#ifdef SEMAPHORE
+    {
+      char name[7];
+      sprintf(name, "MEM%d", i);
+      SEMAPHORECREATE(name, top[i].semaphore_id);
+      /* doesn't matter if it failed, we continue anyway ;-( */
+    }
+#endif
+  }
+}
+
+/****************************************************************************
+ *
+ * fragfromblock()
+ *
+ * This should return a fragment from the block and mark it as used
+ * accordingly.
+ *
+ ***************************************************************************/
+
+static void *fragfromblock(struct MemBlock *block)
+{
+  /* make frag point to the first free FRAGMENT */
+  struct MemFrag *frag = block->first;
+  struct MemInfo *mem = (struct MemInfo *)frag;
+
+  /*
+   * Remove the FRAGMENT from the list and decrease the free counters.
+   */
+  block->first = frag->next; /* new first free FRAGMENT */
+
+  block->nfree--; /* BLOCK counter */
+  block->top->nfree--; /* TOP counter */
+      
+  /* heal the FRAGMENT list */
+  if(frag->prev) {
+    frag->prev->next = frag->next;
+  }
+  if(frag->next) {
+    frag->next->prev = frag->prev;
+  }
+  mem->block = block; /* no block bit set here */
+    
+  return ((char *)mem)+sizeof(struct MemInfo);
+}
+
+/***************************************************************************
+ *
+ * dmalloc()
+ *
+ * This needs no explanation. A malloc() look-alike.
+ *
+ **************************************************************************/
+
+void *dmalloc(size_t size)
+{
+  void *mem;
+
+  DBG(("dmalloc(%d)\n", size));
+
+  /* First, we make room for the space needed in every allocation */
+  size += sizeof(struct MemInfo);
+
+  if(size < DMEM_LARGESTSIZE) {
+    /* get a FRAGMENT */
+
+    struct MemBlock *block=NULL; /* SAFE */
+    struct MemBlock *newblock=NULL; /* SAFE */
+    struct MemTop *memtop=NULL; /* SAFE */
+
+    /* Determine which queue to use */
+    int queue;
+    for(queue=0; size > qinfo[queue]; queue++)
+      ;
+    do {
+      /* This is the head master of our chain: */
+      memtop = &top[queue];
+
+      DBG(("Top info: CHAIN %p FREE %d MAX %d FRAGSIZE %d\n",
+	   memtop->chain,
+	   memtop->nfree,
+	   memtop->nmax,
+	   memtop->fragsize));
+
+#ifdef SEMAPHORE
+      if(SEMAPHOREOBTAIN(memtop->semaphore_id))
+	return NULL; /* failed somehow */
+#endif
+
+      /* get the first BLOCK in the chain */
+      block = memtop->chain;
+
+      /* check if we have a free FRAGMENT */
+      if(memtop->nfree) {
+	/* there exists a free FRAGMENT in this chain */
+
+	/* I WANT THIS LOOP OUT OF HERE! */
+
+	/* search for the free FRAGMENT */
+	while(!block->nfree)
+	  block = block->next; /* check next BLOCK */
+
+	/*
+	 * Now 'block' is the first BLOCK with a free FRAGMENT
+	 */
+
+	mem = fragfromblock(block);
+      
+      }
+      else {
+	/* we do *not* have a free FRAGMENT but need to get us a new BLOCK */
+
+	DMEM_OSALLOCMEM(DMEM_BLOCKSIZE + sizeof(struct MemBlock),
+			newblock,
+			struct MemBlock *);
+	if(!newblock) {
+	  if(++queue < sizeof(qinfo)/sizeof(qinfo[0])) {
+	    /* There are queues for bigger FRAGMENTS that we should check
+	       before we fail this for real */
+#ifdef DEBUG_VERBOSE
+	    printf("*** " __FILE__ " Trying a bigger Q: %d\n", queue);
+#endif
+	    mem = NULL;
+	  }
+	  else {
+	    dmalloc_failed(size- sizeof(struct MemInfo));
+	    return NULL; /* not enough memory */
+	  }
+	}
+	else {
+	  /* allocation of big BLOCK was successful */
+
+	  MEMINCR(newblock, DMEM_BLOCKSIZE + sizeof(struct MemBlock));
+
+	  memtop->chain = newblock; /* attach this BLOCK to the chain */
+	  newblock->next = block;   /* point to the previous first BLOCK */
+	  if(block)
+	    block->prev = newblock; /* point back on this new BLOCK */
+	  newblock->prev = NULL;    /* no previous */
+	  newblock->top  = memtop;  /* our head master */
+	
+	  /* point to the new first FRAGMENT */
+	  newblock->first = (struct MemFrag *)
+	    ((char *)newblock+sizeof(struct MemBlock));
+
+	  /* create FRAGMENTS of the BLOCK: */
+	  FragBlock((char *)newblock->first, memtop->fragsize);
+
+	  /* fix the nfree counters */
+	  newblock->nfree = memtop->nmax;
+	  memtop->nfree += memtop->nmax;
+
+	  /* get a FRAGMENT from the BLOCK */
+	  mem = fragfromblock(newblock);
+	}
+      }
+#ifdef SEMAPHORE
+      SEMAPHORERETURN(memtop->semaphore_id); /* let it go */
+#endif
+    } while(NULL == mem); /* if we should retry a larger FRAGMENT */
+  }
+  else {
+    /* get a stand-alone BLOCK */
+    struct MemInfo *meminfo;
+
+    if(size&1)
+      /* don't leave this with an odd size since we'll use that bit for
+	 information */
+      size++;
+
+    DMEM_OSALLOCMEM(size, meminfo, struct MemInfo *);
+
+    if(meminfo) {
+      MEMINCR(meminfo, size);
+      meminfo->block = (void *)(size|BLOCK_BIT);
+      mem = (char *)meminfo + sizeof(struct MemInfo);
+    }
+    else {
+      dmalloc_failed(size);
+      mem = NULL;
+    }
+  }
+  return (void *)mem;
+}
+
+/***************************************************************************
+ *
+ * dfree()
+ *
+ * This needs no explanation. A free() look-alike.
+ *
+ **************************************************************************/
+
+void dfree(void *memp)
+{
+  struct MemInfo *meminfo = (struct MemInfo *)
+    ((char *)memp- sizeof(struct MemInfo));
+
+  DBG(("dfree(%p)\n", memp));
+
+  if(!((size_t)meminfo->block&BLOCK_BIT)) {
+    /* this is a FRAGMENT we have to deal with */
+
+    struct MemBlock *block=meminfo->block;
+    struct MemTop *memtop = block->top;
+
+#ifdef SEMAPHORE
+    SEMAPHOREOBTAIN(memtop->semaphore_id);
+#endif
+
+    /* increase counters */
+    block->nfree++;
+    memtop->nfree++;
+
+    /* is this BLOCK completely empty now? */
+    if(block->nfree == memtop->nmax) {
+      /* yes, return the BLOCK to the system */
+      if(block->prev)
+        block->prev->next = block->next;
+      else
+	memtop->chain = block->next;
+      if(block->next)
+        block->next->prev = block->prev;
+
+      memtop->nfree -= memtop->nmax; /* total counter subtraction */
+      MEMDECR(block, DMEM_BLOCKSIZE + sizeof(struct MemBlock));
+      DMEM_OSFREEMEM((void *)block); /* return the whole block */
+    }
+    else {
+      /* there are still used FRAGMENTS in the BLOCK, link this one
+         into the chain of free ones */
+      struct MemFrag *frag = (struct MemFrag *)meminfo;
+      frag->prev = NULL;
+      frag->next = block->first;
+      if(block->first)
+	block->first->prev = frag;
+      block->first = frag;
+    }
+#ifdef SEMAPHORE
+    SEMAPHORERETURN(memtop->semaphore_id);
+#endif
+  }
+  else {
+    /* big stand-alone block, just give it back to the OS: */
+    MEMDECR(meminfo->block, (size_t)meminfo->block&~BLOCK_BIT); /* clean BLOCK_BIT */
+    DMEM_OSFREEMEM((void *)meminfo);
+  }
+}
+
+/***************************************************************************
+ *
+ * drealloc()
+ *
+ * This needs no explanation. A realloc() look-alike.
+ *
+ **************************************************************************/
+
+void *drealloc(char *ptr, size_t size)
+{
+  struct MemInfo *meminfo = (struct MemInfo *)
+    ((char *)ptr- sizeof(struct MemInfo));
+  /*
+   * ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
+   * NOTE: the ->size field of the meminfo will now contain the MemInfo
+   * struct size too!
+   * ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
+   */
+  void *mem=NULL; /* SAFE */
+  size_t prevsize;
+
+  /* NOTE that this is only valid if BLOCK_BIT isn't set: */
+  struct MemBlock *block;
+
+  DBG(("drealloc(%p, %d)\n", ptr, size));
+
+  if(NULL == ptr)
+    return dmalloc( size );
+
+  block = meminfo->block;
+
+  if(!((size_t)meminfo->block&BLOCK_BIT) &&
+     (size + sizeof(struct MemInfo) <
+      (prevsize = block->top->fragsize) )) {
+    /* This is a FRAGMENT and new size is possible to retain within the same
+       FRAGMENT */
+    if((prevsize > qinfo[0]) &&
+       /* this is not the smallest memory Q */
+       (size < (block->top-1)->fragsize))
+      /* this fits in a smaller Q */
+      ;
+    else
+      mem = ptr; /* Just return the same pointer as we got in. */
+  }
+  if(!mem) {
+    /* This is a stand-alone BLOCK or a realloc that no longer fits within
+       the same FRAGMENT */
+
+    if((size_t)meminfo->block&BLOCK_BIT) {
+      prevsize = ((size_t)meminfo->block&~BLOCK_BIT) -
+	sizeof(struct MemInfo);
+    }
+    else
+      prevsize -= sizeof(struct MemInfo);
+
+    /* No tricks involved here, just grab a new bite of memory, copy the data
+     * from the old place and free the old memory again. */
+    mem = dmalloc(size);
+    if(mem) {
+      memcpy(mem, ptr, MIN(size, prevsize) );
+      dfree(ptr);
+    }
+  }
+  return mem;
+}
+
+/***************************************************************************
+ *
+ * dcalloc()
+ *
+ * This needs no explanation. A calloc() look-alike.
+ *
+ **************************************************************************/
+/* Allocate an array of NMEMB elements each SIZE bytes long.
+   The entire array is initialized to zeros.  */
+void *
+dcalloc (size_t nmemb, size_t size)
+{
+  void *result = dmalloc (nmemb * size);
+
+  if (result != NULL)
+    memset (result, 0, nmemb * size);
+
+  return result;
+}
diff --git a/firmware/malloc/dmalloc.h b/firmware/malloc/dmalloc.h
new file mode 100644
index 0000000..a4e0ab4
--- /dev/null
+++ b/firmware/malloc/dmalloc.h
@@ -0,0 +1,35 @@
+/***************************************************************************
+ *             __________               __   ___.
+ *   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.
+ *
+ ****************************************************************************/
+
+void *dmalloc(size_t);
+void dfree(void *);
+void *drealloc(void *, size_t);
+
+#define malloc(x)    dmalloc(x)
+#define free(x)      dfree(x)
+#define realloc(x,y) drealloc(x,y)
+#define calloc(x,y)  dcalloc(x,y)
+
+
+/* use this to intialize the internals of the dmalloc engine */
+void dmalloc_initialize(void);
+
+#ifdef DEBUG
+void dmalloc_status(void);
+#endif