aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
-rw-r--r--com32/lib/syslinux/movebits.c302
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: