diff options
Diffstat (limited to 'com32')
-rw-r--r-- | com32/lib/syslinux/movebits.c | 302 |
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: |