--- a/packages/redboot/current/ChangeLog
+++ b/packages/redboot/current/ChangeLog
@@ -1,3 +1,10 @@
+2003-12-05  Ian Campbell  <icampbell@arcom.com>
+
+	* src/decompress.c: Ensure that free'd blocks are returned to the
+	free pool and that adjacent free blocks are merged. Initialise the
+	pool in _zlib_init() so that things are initialised even when
+	gzip_init hasn't been called.
+
 2003-12-05  Gary Thomas  <gary@mlbassoc.com>
 
 	* src/io.c (_rb_gets_preloaded): ^A could have moved the cursor to

--- a/packages/redboot/current/src/decompress.c
+++ b/packages/redboot/current/src/decompress.c
@@ -63,15 +63,15 @@ static bool stream_end;
 
 //
 // Free memory [blocks] are stored as a linked list of "struct _block"
-// When free, 'size' is the size of the whole block
-// When allocated, 'size' is the allocation size
 // The 'magic' is kept to insure that the block being freed is reasonable
 //
+// One of either next or size might be removable, if a sentinal block
+// is placed at the end of the region at initialisation time.
 struct _block {
-    int            size;
-    long           magic;  // Must be __ZLIB_MAGIC__
+    int            size;   // always the total length of the block, including this header
+    long           magic;  // Must be __ZLIB_MAGIC__ if allocated and 0 if free
     struct _block *next;
-    struct _block *self;
+    struct _block *prev;
 };
 static struct _block *memlist;
 
@@ -92,6 +92,7 @@ static void *zlib_workspace;
 static void
 _zlib_init(void)
 {
+    struct _block *bp;
 #ifdef CYGOPT_REDBOOT_FIS_ZLIB_COMMON_BUFFER
     zlib_workspace = fis_zlib_common_buffer;
 #else
@@ -99,6 +100,14 @@ static void
     workspace_end -= ZLIB_COMPRESSION_OVERHEAD;
     zlib_workspace = workspace_end;
 #endif
+    bp = (struct _block *)zlib_workspace;
+    memlist = bp;
+    bp->next = bp->prev = 0;
+    bp->size = ZLIB_COMPRESSION_OVERHEAD; 
+    bp->magic = 0;
+#ifdef DEBUG_ZLIB_MALLOC
+    show_memlist(__FUNCTION__);
+#endif
 }
 
 RedBoot_init(_zlib_init, RedBoot_INIT_FIRST);
@@ -111,10 +120,13 @@ show_memlist(char *when)
     struct _block *bp = memlist;
 
     diag_printf("memory list after %s\n", when);
+    diag_printf("   --START--- --END----- --SIZE---- --PREV---- --NEXT---- TYPE-----\n");
     while (bp != (struct _block *)0) {
-        diag_printf("   %08p %5d %08p\n", bp, bp->size, bp->next);
+        diag_printf("   %08p-%08p 0x%08x %08p %08p %s\n", bp, (unsigned char *)bp+bp->size, 
+                    bp->size, bp->prev, bp->next, bp->magic == 0 ? "FREE" : "ALLOCATED" );
         bp = bp->next;
     }
+    diag_printf("\n");
 }
 #endif
 
@@ -124,120 +136,90 @@ show_memlist(char *when)
 void 
 *zcalloc(void *opaque, unsigned int items, unsigned int size)
 {
-    voidpf res;
-    int len = (items*size);
+    voidpf res = 0;
+    int len = (items*size) + sizeof(struct _block);
     struct _block *bp = memlist;
-    struct _block *nbp, *pbp;
+    struct _block *nbp;
+
+#ifdef DEBUG_ZLIB_MALLOC
+    /* do this here because when int is called output is not setup yet */
+    static int first_alloc = 1;
+    if ( first_alloc ) {
+        show_memlist("initialization");
+        first_alloc = 0;
+    }
+#endif
 
     // Simple, first-fit algorithm
-    pbp = (struct _block *)0;
     while (bp) {
-        if (bp->size > len) {
-            nbp = (struct _block *)((char *)bp + len + sizeof(struct _block));
+        if (bp->magic == 0 && bp->size > len) {
+            nbp = (struct _block *)((char *)bp + len);
+            /* link new block into chain */
             nbp->next = bp->next;
+            bp->next = nbp;
+            nbp->prev = bp;
+            /* split size between the two blocks */
             nbp->size = bp->size - len;
-            if (pbp) {
-                pbp->next = nbp;
-            } else {
-                memlist = nbp;
-            }
-            res = bp;
+            bp->size = len;
+            /* mark the new block as free */
+            nbp->magic = 0;
+            /* mark allocated block as allocated */
+            bp->magic = __ZLIB_MAGIC__;
+            res = bp +1;
+            memset(res, 0, len - sizeof(struct _block));
             break;
         }
-        pbp = bp;
         bp = bp->next;
     }
-    if (bp) {
-        bp->size = len;
-        bp->magic = __ZLIB_MAGIC__;
-        bp->self = bp;
-        res = bp+1;
-        memset(res, 0, len);
-    } else {
-        res = 0;  // No memory left
-    }
 #ifdef DEBUG_ZLIB_MALLOC
-    diag_printf("%s(%d,%d) = %p\n", __FUNCTION__, items, size, res);
+    diag_printf("%s(0x%x,0x%x) = %p\n", __FUNCTION__, items, size, res);
     show_memlist(__FUNCTION__);
 #endif
+    if ( res == NULL )
+        diag_printf("zcalloc: failed to allocate 0x%x items of 0x%x bytes == 0x%x bytes\n", items, size, len);
     return res;
 }
 
 void 
 zcfree(void *opaque, void *ptr)
 {
-    struct _block *bp, *pbp, *nbp;
-    int size;
+    struct _block *bp;
 
     if (!ptr) return;  // Safety
     bp = (struct _block *)((char *)ptr - sizeof(struct _block));
-    if ((bp->magic != __ZLIB_MAGIC__) || (bp->self != bp)) {
+    if (bp->magic != __ZLIB_MAGIC__) {
         diag_printf("%s(%p) - invalid block\n", __FUNCTION__, ptr);
         return;
     }
-    size = bp->size;
+
+    /* mark as free */
+    bp->magic = 0;
+
 #ifdef DEBUG_ZLIB_MALLOC
-    diag_printf("%s(%p) = %d bytes\n", __FUNCTION__, ptr, size);
-#endif
-    // See if this block is adjacent to a free block
-    nbp = memlist;
-    pbp = (struct _block *)0;
-    while (nbp) {
-        if ((char *)bp+size+sizeof(struct _block) == (char *)nbp) {
-            // The block being freed fits just before
-            bp->next = nbp->next;
-            bp->size = nbp->size + size + sizeof(struct _block);
-#ifdef DEBUG_ZLIB_MALLOC
-            diag_printf("Free before\n");
+    diag_printf("%s(%p) = 0x%x bytes\n", __FUNCTION__, ptr, bp->size);
 #endif
-            if (pbp) {
-                pbp->next = bp;
-                // See if this new block and the previous one can
-                // be combined.
-                if ((char *)pbp+pbp->size == (char *)bp) {
-#ifdef DEBUG_ZLIB_MALLOC
-                    diag_printf("Collapse [before] - p: %p/%d/%p, n: %p/%d/%p\n",
-                                pbp, pbp->size, pbp->next,
-                                bp, bp->size, bp->next);
-#endif
-                    pbp->size += bp->size;
-                    pbp->next = bp->next;
-                }
-            } else {
-                memlist = bp;
-            }
+
+    bp = (struct _block *)((char *)ptr - sizeof(struct _block));
+    while(bp->next && bp->next->magic == 0) {
 #ifdef DEBUG_ZLIB_MALLOC
-            show_memlist(__FUNCTION__);
+        diag_printf("  merging %08p and %08p (after)\n", bp, bp->next);
 #endif
-            return;
-        } else
-        if ((char *)nbp+nbp->size == (char *)bp) {
-            // The block being freed fits just after
-            nbp->size += size + sizeof(struct _block);
-            // See if it will now collapse with the following block
-#ifdef DEBUG_ZLIB_MALLOC
-            diag_printf("Free after\n");
-#endif
-            if (nbp->next != (struct _block *)0) {
-                if ((char *)nbp+nbp->size == (char *)nbp->next) {
+        bp->size += bp->next->size;
+        bp->next = bp->next->next;
+    }
+
+    while(bp->prev && bp->prev->magic == 0) {
 #ifdef DEBUG_ZLIB_MALLOC
-                    diag_printf("Collapse [after] - p: %p/%d/%p, n: %p/%d/%p\n",
-                                nbp, nbp->size, nbp->next,
-                                nbp->next, nbp->next->size, nbp->next->next);
+        diag_printf("  merging %08p and %08p (before)\n", bp->prev, bp);
 #endif
-                    nbp->size += (nbp->next)->size;
-                    nbp->next = (nbp->next)->next;
-                }
-            }
+        bp->prev->size += bp->size;
+        bp->prev->next = bp->next;
+        bp = bp->prev;
+    }
+
 #ifdef DEBUG_ZLIB_MALLOC
-            show_memlist(__FUNCTION__);
+    show_memlist(__FUNCTION__);
 #endif
-            return;
-        } else {
-            pbp = nbp;
-            nbp = nbp->next;
-        }
-    }
 }
 
 //
@@ -252,7 +234,7 @@ gzip_init(_pipe_t* p)
 
     bp = (struct _block *)zlib_workspace;
     memlist = bp;
-    bp->next = 0;
+    bp->next = bp->prev = 0;
     bp->size = ZLIB_COMPRESSION_OVERHEAD;
     stream.zalloc = zcalloc;
     stream.zfree = zcfree;