Handle arbitrary numbers of shuffle descriptors

Allocate high memory out of the way to hold the shuffle descriptors,
and generate continuation descriptors as needed.

2 files changed, 147 insertions, 22 deletions

diff --git a/com32/lib/syslinux/movebits.c b/com32/lib/syslinux/movebits.c
index 6dd83b16..9ec2c8c4 100644
--- a/com32/lib/syslinux/movebits.c
+++ b/com32/lib/syslinux/movebits.c
@@ -80,6 +80,21 @@ new_movelist(addr_t dst, addr_t src, addr_t len)
   return ml;
 }
 
+static struct syslinux_movelist *
+dup_movelist(struct syslinux_movelist *src)
+{
+  struct syslinux_movelist *dst = NULL, **dstp = &dst, *ml;
+
+  while (src) {
+    ml = new_movelist(src->dst, src->src, src->len);
+    *dstp = ml;
+    dstp = &ml->next;
+    src = src->next;
+  }
+
+  return dst;
+}
+
 /*
  * Take a chunk, entirely confined in **parentptr, and split it off so that
  * it has its own structure.
@@ -118,7 +133,6 @@ split_movelist(addr_t start, addr_t len, struct syslinux_movelist **parentptr)
   return parentptr;
 }
 
-#if 0
 static void
 delete_movelist(struct syslinux_movelist **parentptr)
 {
@@ -126,7 +140,13 @@ delete_movelist(struct syslinux_movelist **parentptr)
   *parentptr = o->next;
   free(o);
 }
-#endif
+
+static void
+free_movelist(struct syslinux_movelist **parentptr)
+{
+  while (*parentptr)
+    delete_movelist(parentptr);
+}
 
 /*
  * Scan the freelist looking for a particular chunk of memory
@@ -235,10 +255,11 @@ tidy_freelist(struct syslinux_movelist **frags,
 
 int
 syslinux_compute_movelist(struct syslinux_movelist **moves,
-			  struct syslinux_movelist *frags,
+			  struct syslinux_movelist *ifrags,
 			  struct syslinux_memmap *memmap)
 {
   struct syslinux_memmap *mmap = NULL, *mm;
+  struct syslinux_movelist *frags = NULL;
   struct syslinux_movelist *mv, *space;
   struct syslinux_movelist *f, **fp, **ep;
   struct syslinux_movelist *o, **op;
@@ -260,6 +281,8 @@ syslinux_compute_movelist(struct syslinux_movelist **moves,
   if (!mmap)
     goto bail;
 
+  frags = dup_movelist(ifrags);
+
 #if DEBUG
   dprintf("Initial memory map:\n");
   syslinux_dump_memmap(stdout, mmap);
@@ -361,7 +384,7 @@ syslinux_compute_movelist(struct syslinux_movelist **moves,
       } else {
 	ep = free_area_max(&space);
 	if ( !ep )
-	  return -1;		/* Stuck! */
+	  goto bail;		/* Stuck! */
 	copydst = (*ep)->src;
 	copylen = (*ep)->len;
       }
@@ -403,7 +426,7 @@ syslinux_compute_movelist(struct syslinux_movelist **moves,
       }
       goto move_chunk;
     }
-    return -1;			/* Stuck! */
+    goto bail;			/* Stuck! */
 
   move_chunk:
     /* We're allowed to move the chunk into place now. */
@@ -441,6 +464,8 @@ syslinux_compute_movelist(struct syslinux_movelist **moves,
  bail:
   if (mmap)
     syslinux_free_memmap(mmap);
+  if (frags)
+    free_movelist(&frags);
   return rv;
 }
 
diff --git a/com32/lib/syslinux/shuffle.c b/com32/lib/syslinux/shuffle.c
index 26c89f98..3393f2a8 100644
--- a/com32/lib/syslinux/shuffle.c
+++ b/com32/lib/syslinux/shuffle.c
@@ -34,8 +34,10 @@
  */
 
 #include <stdlib.h>
+#include <string.h>
 #include <inttypes.h>
 #include <com32.h>
+#include <minmax.h>
 #include <syslinux/movebits.h>
 
 #ifndef DEBUG
@@ -52,55 +54,153 @@ struct shuffle_descriptor {
   uint32_t dst, src, len;
 };
 
+/* Allocate descriptor memory in these chunks */
+#define DESC_BLOCK_SIZE	256
+
 int syslinux_prepare_shuffle(struct syslinux_movelist *fraglist,
 			     struct syslinux_memmap *memmap)
 {
   struct syslinux_movelist *moves = NULL, *mp;
-  struct syslinux_memmap *ml;
-  struct shuffle_descriptor *dp;
-  int np, rv = -1;
+  struct syslinux_memmap *rxmap = NULL, *ml;
+  struct shuffle_descriptor *dp, *dbuf;
+  int np, nb, rv = -1;
+  int desc_blocks;
+  addr_t desczone, descfree, descaddr, descoffs;
+  int nmoves, nzero;
+  struct shuffle_descriptor primaries[2];
+
+  /* Count the number of zero operations */
+  nzero = 0;
+  for (ml = memmap; ml->type != SMT_END; ml = ml->next) {
+    if (ml->type == SMT_ZERO)
+      nzero++;
+  }
 
-  if (syslinux_compute_movelist(&moves, fraglist, memmap))
+  rxmap = syslinux_dup_memmap(memmap);
+  for (mp = fraglist; mp; mp = mp->next) {
+    if (syslinux_add_memmap(&rxmap, mp->src, mp->len, SMT_ALLOC))
+      goto bail;
+  }
+    
+  if (syslinux_memmap_largest(rxmap, SMT_FREE, &desczone, &descfree))
     goto bail;
 
+  dprintf("desczone = 0x%08x, descfree = 0x%08x\n", desczone, descfree);
+
+  for (desc_blocks = (nzero+DESC_BLOCK_SIZE)/(DESC_BLOCK_SIZE-1) ; ;
+       desc_blocks++) {
+    addr_t descmem = desc_blocks*
+      sizeof(struct shuffle_descriptor)*DESC_BLOCK_SIZE;
+
+    if (descfree < descmem)
+      goto bail;		/* No memory block large enough */
+
+    descaddr = desczone + descfree - descmem;
+    if (syslinux_add_memmap(&rxmap, descaddr, descmem, SMT_ALLOC))
+      goto bail;
+
+#if DEBUG
+    syslinux_dump_movelist(stdout, fraglist);
+#endif
+
+    if (syslinux_compute_movelist(&moves, fraglist, rxmap))
+      goto bail;
+    
+    nmoves = 0;
+    for (mp = moves; mp; mp = mp->next)
+      nmoves++;
+
+    if ((nmoves+nzero) <= desc_blocks*(DESC_BLOCK_SIZE-1))
+      break;			/* Sufficient memory, yay */
+  }
+
 #if DEBUG
   dprintf("Final movelist:\n");
   syslinux_dump_movelist(stdout, moves);
 #endif
 
-  dp = __com32.cs_bounce;
-  np = 0;
+  syslinux_free_memmap(rxmap);
+  rxmap = NULL;
 
-  /* Copy the move sequence into the bounce buffer */
+  dbuf = malloc((nmoves+nzero+desc_blocks)*sizeof(struct shuffle_descriptor));
+  if (!dbuf)
+    goto bail;
+
+  descoffs = descaddr - (addr_t)dbuf;
+
+#if DEBUG
+  dprintf("nmoves = %d, nzero = %d, dbuf = %p, offs = 0x%08x\n",
+	  nmoves, nzero, dbuf, descoffs);
+#endif
+
+  /* Copy the move sequence into the descriptor buffer */
+  np = 0;
+  nb = 0;
+  dp = dbuf;
   for (mp = moves; mp; mp = mp->next) {
-    if (np >= 65536/12)
-      goto bail;		/* Way too many descriptors... */
+    if (nb == DESC_BLOCK_SIZE-1) {
+      dp->dst = -1;		/* Load new descriptors */
+      dp->src = (addr_t)(dp+1) + descoffs;
+      dp->len = sizeof(*dp)*min(nmoves, DESC_BLOCK_SIZE);
+      dprintf("[ %08x %08x %08x ]\n", dp->dst, dp->src, dp->len);
+      dp++; np++;
+      nb = 0;
+    }
 
     dp->dst = mp->dst;
     dp->src = mp->src;
     dp->len = mp->len;
-    dp++; np++;
+    dprintf("[ %08x %08x %08x ]\n", dp->dst, dp->src, dp->len);
+    dp++; np++; nb++;
   }
 
-  /* Copy any zeroing operations into the bounce buffer */
+  /* Copy bzero operations into the descriptor buffer */
   for (ml = memmap; ml->type != SMT_END; ml = ml->next) {
     if (ml->type == SMT_ZERO) {
-      if (np >= 65536/12)
-	goto bail;
-
+      if (nb == DESC_BLOCK_SIZE-1) {
+	dp->dst = (addr_t)-1;	/* Load new descriptors */
+	dp->src = (addr_t)(dp+1) + descoffs;
+	dp->len = sizeof(*dp)*min(nmoves, DESC_BLOCK_SIZE);
+	dprintf("[ %08x %08x %08x ]\n", dp->dst, dp->src, dp->len);
+	dp++; np++;
+	nb = 0;
+      }
+      
       dp->dst = ml->start;
-      dp->src = (addr_t)-1;	/* bzero this region */
+      dp->src = (addr_t)-1;	/* bzero region */
       dp->len = ml->next->start - ml->start;
-      dp++; np++;
+      dprintf("[ %08x %08x %08x ]\n", dp->dst, dp->src, dp->len);
+      dp++; np++; nb++;
     }
   }
 
-  rv = np;
+  /* Set up the primary descriptors in the bounce buffer.
+     The first one moves the descriptor list into its designated safe
+     zone, the second one loads the first descriptor block. */
+  dp = primaries;
+
+  dp->dst = descaddr;
+  dp->src = (addr_t)dbuf;
+  dp->len = np*sizeof(*dp);
+  dprintf("< %08x %08x %08x >\n", dp->dst, dp->src, dp->len);
+  dp++;
+
+  dp->dst = (addr_t)-1;
+  dp->src = descaddr;
+  dp->len = sizeof(*dp)*min(np, DESC_BLOCK_SIZE);
+  dprintf("< %08x %08x %08x >\n", dp->dst, dp->src, dp->len);
+  dp++;
+
+  memcpy(__com32.cs_bounce, primaries, 2*sizeof(*dp));
+
+  rv = 2;			/* Always two primaries */
 
  bail:
   /* This is safe only because free() doesn't use the bounce buffer!!!! */
   if (moves)
     syslinux_free_movelist(moves);
+  if (rxmap)
+    syslinux_free_memmap(rxmap);
 
   return rv;
 }