movebits: handle the case of an upward overlap move with obstacles

Handle the case of an upward move when there is something in the way.
This happens when loading an SDI image.

1 files changed, 187 insertions, 115 deletions

diff --git a/com32/lib/syslinux/movebits.c b/com32/lib/syslinux/movebits.c
index 9ec2c8c4..c9253396 100644
--- a/com32/lib/syslinux/movebits.c
+++ b/com32/lib/syslinux/movebits.c
@@ -46,10 +46,12 @@
 
 #include <syslinux/movebits.h>
 
-#ifdef TEST
-# define DEBUG 1
-#else
-# define DEBUG 0
+#ifndef DEBUG
+# ifdef TEST
+#  define DEBUG 1
+# else
+#  define DEBUG 0
+# endif
 #endif
 
 #if DEBUG
@@ -265,14 +267,19 @@ syslinux_compute_movelist(struct syslinux_movelist **moves,
   struct syslinux_movelist *o, **op;
   addr_t needbase, needlen, copysrc, copydst, copylen;
   addr_t freebase, freelen;
-  addr_t mstart;
+  addr_t mstart, avail;
+  addr_t cbyte;
   int m_ok;
   int rv = -1;
+  int reverse;
+  int again;
 
   dprintf("entering syslinux_compute_movelist()...\n");
 
-  if (setjmp(new_movelist_bail))
+  if (setjmp(new_movelist_bail)) {
+    dprintf("Out of working memory!\n");
     goto bail;
+  }
 
   *moves = NULL;
 
@@ -289,8 +296,10 @@ syslinux_compute_movelist(struct syslinux_movelist **moves,
 #endif
 
   for (f = frags; f; f = f->next) {
-    if (syslinux_add_memmap(&mmap, f->src, f->len, SMT_ALLOC))
+    if (syslinux_add_memmap(&mmap, f->src, f->len, SMT_ALLOC)) {
+      dprintf("Cannot generate free map\n");
       goto bail;
+    }
   }
 
 #if DEBUG
@@ -324,141 +333,204 @@ syslinux_compute_movelist(struct syslinux_movelist **moves,
     mmap = mmap->next;
   }
 
+  do {
+    again = 0;
+
 #if DEBUG
-  dprintf("Computed free list:\n");
-  syslinux_dump_movelist(stdout, space);
+    dprintf("Current free list:\n");
+    syslinux_dump_movelist(stdout, space);
+    dprintf("Current frag list:\n");
+    syslinux_dump_movelist(stdout, frags);
 #endif
 
-  for ( fp = &frags, f = *fp ; f ; fp = &f->next, f = *fp ) {
-    dprintf("@: 0x%08x bytes at 0x%08x -> 0x%08x\n",
-	    f->len, f->src, f->dst);
+    fp = &frags;
+    while ( (f = *fp) ) {
+      dprintf("@: 0x%08x bytes at 0x%08x -> 0x%08x\n",
+	      f->len, f->src, f->dst);
 
-    if ( f->src == f->dst ) {
-      //delete_movelist(fp);	/* Already in the right place! */
-      continue;
-    }
+      if ( f->src == f->dst ) {
+	delete_movelist(fp);
+	continue;
+      }
 
-    /* See if we can move this chunk into place by claiming
-       the destination, or in the case of partial overlap, the
-       missing portion. */
+      /* See if we can move this chunk into place by claiming
+	 the destination, or in the case of partial overlap, the
+	 missing portion. */
 
-    needbase = f->dst;
-    needlen  = f->len;
+      needbase = f->dst;
+      needlen  = f->len;
+
+      dprintf("need: base = 0x%08x, len = 0x%08x\n", needbase, needlen);
+
+      reverse = 0;
+      cbyte = f->dst;		/* "Critical byte" */
+      if ( f->src < f->dst && (f->dst - f->src) < f->len ) {
+	/* "Shift up" type overlap */
+	needlen  = f->dst - f->src;
+	needbase = f->dst + (f->len - needlen);
+	cbyte = f->dst + f->len - 1;
+	reverse = 1;
+      } else if ( f->src > f->dst && (f->src - f->dst) < f->len ) {
+	/* "Shift down" type overlap */
+	needbase = f->dst;
+	needlen  = f->src - f->dst;
+      }
 
-    dprintf("need: base = 0x%08x, len = 0x%08x\n", needbase, needlen);
+      dprintf("need: base = 0x%08x, len = 0x%08x, "
+	      "reverse = %d, cbyte = 0x%08x\n",
+	      needbase, needlen, reverse, cbyte);
 
-    if ( f->src < f->dst && (f->dst - f->src) < f->len ) {
-      /* "Shift up" type overlap */
-      needlen  = f->dst - f->src;
-      needbase = f->dst + (f->len - needlen);
-    } else if ( f->src > f->dst && (f->src - f->dst) < f->len ) {
-      /* "Shift down" type overlap */
-      needbase = f->dst;
-      needlen  = f->src - f->dst;
-    }
+      ep = is_free_zone(cbyte, 1, &space);
+      if (ep) {
+	if (reverse)
+	  avail = needbase+needlen - (*ep)->src;
+	else
+	  avail = (*ep)->len - (needbase - (*ep)->src);
+      } else {
+	avail = 0;
+      }
 
-    if ( (ep = is_free_zone(needbase, 1, &space)) ) {
-      /* We can move at least part of this chunk into place without further ado */
-      copylen = min(needlen, (*ep)->len);
-      allocate_from(needbase, copylen, ep);
-      goto move_chunk;
-    }
+      if (avail) {
+	/* We can move at least part of this chunk into place without
+	   further ado */
+	dprintf("space: start 0x%08x, len 0x%08x, free 0x%08x\n",
+		(*ep)->src, (*ep)->len, avail);
+	copylen = min(needlen, avail);
+
+	if (reverse)
+	  allocate_from(needbase+needlen-copylen, copylen, ep);
+	else
+	  allocate_from(needbase, copylen, ep);
+
+	goto move_chunk;
+      }
 
-    /* At this point, we need to evict something out of our space.
-       Find the object occupying the first byte of our target space,
-       and move it out (the whole object if we can, otherwise a subset.)
-       Then move a chunk of ourselves into place. */
-    for ( op = &f->next, o = *op ; o ; op = &o->next, o = *op ) {
+      /* At this point, we need to evict something out of our space.
+	 Find the object occupying the critical byte of our target space,
+	 and move it out (the whole object if we can, otherwise a subset.)
+	 Then move a chunk of ourselves into place. */
+      for ( op = &f->next, o = *op ; o ; op = &o->next, o = *op ) {
 
-	dprintf("O: 0x%08x bytes	at 0x%08x -> 0x%08x\n",
+	dprintf("O: 0x%08x bytes at 0x%08x -> 0x%08x\n",
 		o->len, o->src, o->dst);
 
-      if ( !(o->src <= needbase && o->src+o->len > needbase) )
-	continue;		/* Not what we're looking for... */
+	if ( !(o->src <= cbyte && o->src+o->len > cbyte) )
+	  continue;		/* Not what we're looking for... */
+
+	/* Find somewhere to put it... */
+
+	if ( (ep = is_free_zone(o->dst, o->len, &space)) ) {
+	  /* Score!  We can move it into place directly... */
+	  copydst = o->dst;
+	  copylen = o->len;
+	} else if ( (ep = free_area(o->len, &space)) ) {
+	  /* We can move the whole chunk */
+	  copydst = (*ep)->src;
+	  copylen = o->len;
+	} else {
+	  /* Well, copy as much as we can... */
+	  ep = free_area_max(&space);
+	  if ( !ep ) {
+	    dprintf("No free memory at all!\n");
+	    goto bail;		/* Stuck! */
+	  }
+
+	  /* Make sure we include the critical byte */
+	  copydst = (*ep)->src;
+	  if (reverse) {
+	    copysrc = max(o->src, cbyte+1 - (*ep)->len);
+	    copylen = cbyte+1 - copysrc;
+	  } else {
+	    copysrc = cbyte;
+	    copylen = min((*ep)->len, o->len - (cbyte-o->src));
+	  }
+	}
+	allocate_from(copydst, copylen, ep);
 
-      /* Find somewhere to put it... */
-      if ( (ep = free_area(o->len, &space)) ) {
-	/* We got what we wanted... */
-	copydst = (*ep)->src;
-	copylen = o->len;
-      } else {
-	ep = free_area_max(&space);
-	if ( !ep )
-	  goto bail;		/* Stuck! */
-	copydst = (*ep)->src;
-	copylen = (*ep)->len;
-      }
-      allocate_from(copydst, copylen, ep);
+	if ( copylen < o->len ) {
+	  op = split_movelist(copysrc, copylen, op);
+	  o = *op;
+	}
 
-      if ( copylen >= o->len - (needbase-o->src) ) {
-	copysrc = o->src + (o->len - copylen);
-      } else {
-	copysrc = o->src;
+	mv = new_movelist(copydst, copysrc, copylen);
+	dprintf("C: 0x%08x bytes at 0x%08x -> 0x%08x\n",
+		mv->len, mv->src, mv->dst);
+	*moves = mv;
+	moves = &mv->next;
+
+	o->src = copydst;
+
+	if ( copylen > needlen ) {
+	  /* We don't need all the memory we freed up.  Mark it free. */
+	  if ( copysrc < needbase ) {
+	    mv = new_movelist(0, copysrc, needbase-copysrc);
+	    mv->next = space;
+	    space = mv;
+	    copylen -= (needbase-copysrc);
+	  }
+	  if ( copylen > needlen ) {
+	    mv = new_movelist(0, copysrc+needlen, copylen-needlen);
+	    mv->next = space;
+	    space = mv;
+	    copylen = needlen;
+	  }
+	}
+	reverse = 0;
+	goto move_chunk;
       }
+      dprintf("Cannot find the chunk containing the critical byte\n");
+      goto bail;			/* Stuck! */
+
+    move_chunk:
+      /* We're allowed to move the chunk into place now. */
 
-      if ( copylen < o->len ) {
-	op = split_movelist(copysrc, copylen, op);
-	o = *op;
+      copydst = f->dst;
+      copysrc = f->src;
+
+      dprintf("Q: copylen = 0x%08x, needlen = 0x%08x\n", copylen, needlen);
+
+      if ( copylen < needlen ) {
+	if (reverse) {
+	  copydst += (f->len-copylen);
+	  copysrc += (f->len-copylen);
+	}
+      
+	dprintf("X: 0x%08x bytes at 0x%08x -> 0x%08x\n",
+		copylen, copysrc, copydst);
+
+	/* Didn't get all we wanted, so we have to split the chunk */
+	fp = split_movelist(copysrc, copylen, fp); /* Is this right? */
+	f = *fp;
       }
 
-      mv = new_movelist(copydst, copysrc, copylen);
-      dprintf("C: 0x%08x bytes at 0x%08x -> 0x%08x\n",
+      mv = new_movelist(f->dst, f->src, f->len);
+      dprintf("A: 0x%08x bytes at 0x%08x -> 0x%08x\n",
 	      mv->len, mv->src, mv->dst);
       *moves = mv;
       moves = &mv->next;
 
-      o->src = copydst;
-
-      if ( copylen > needlen ) {
-	/* We don't need all the memory we freed up.  Mark it free. */
-	if ( copysrc < needbase ) {
-	  mv = new_movelist(0, copysrc, needbase-copysrc);
-	  mv->next = space;
-	  space = mv;
-	  copylen -= (needbase-copysrc);
-	}
-	if ( copylen > needlen ) {
-	  mv = new_movelist(0, copysrc+needlen, copylen-needlen);
-	  mv->next = space;
-	  space = mv;
-	  copylen = needlen;
-	}
+      /* Figure out what memory we just freed up */
+      if ( f->dst > f->src ) {
+	freebase = f->src;
+	freelen  = min(f->len, f->dst-f->src);
+      } else if ( f->src >= f->dst+f->len ) {
+	freebase = f->src;
+	freelen  = f->len;
+      } else {
+	freelen  = f->src-f->dst;
+	freebase = f->dst+f->len;
       }
-      goto move_chunk;
-    }
-    goto bail;			/* Stuck! */
 
-  move_chunk:
-    /* We're allowed to move the chunk into place now. */
+      dprintf("F: 0x%08x bytes at 0x%08x\n", freelen, freebase);
 
-    if ( copylen < needlen ) {
-      /* Didn't get all we wanted, so we have to split the chunk */
-      fp = split_movelist(f->src, copylen+(needbase-f->dst), fp);
-      f = *fp;
+      mv = new_movelist(0, freebase, freelen);
+      mv->next = space;
+      space = mv;
+      
+      delete_movelist(fp);
+      again = 1;		/* At least one chunk was moved */
     }
-
-    mv = new_movelist(f->dst, f->src, f->len);
-    dprintf("A: 0x%08x bytes at 0x%08x -> 0x%08x\n",
-	    mv->len, mv->src, mv->dst);
-    *moves = mv;
-    moves = &mv->next;
-
-    /* Figure out what memory we just freed up */
-    if ( f->dst > f->src ) {
-      freebase = f->src;
-      freelen  = min(f->len, f->dst-f->src);
-    } else if ( f->src >= f->dst+f->len ) {
-      freebase = f->src;
-      freelen  = f->len;
-    } else {
-      freelen  = f->src-f->dst;
-      freebase = f->dst+f->len;
-    }
-
-    mv = new_movelist(0, freebase, freelen);
-    mv->next = space;
-    space = mv;
-  }
+  } while (again);
 
   rv = 0;
  bail: