diff options
Diffstat (limited to 'contrib/syslinux-4.02/com32/lib/syslinux/movebits.c')
-rw-r--r-- | contrib/syslinux-4.02/com32/lib/syslinux/movebits.c | 710 |
1 files changed, 710 insertions, 0 deletions
diff --git a/contrib/syslinux-4.02/com32/lib/syslinux/movebits.c b/contrib/syslinux-4.02/com32/lib/syslinux/movebits.c new file mode 100644 index 0000000..bd5ce0e --- /dev/null +++ b/contrib/syslinux-4.02/com32/lib/syslinux/movebits.c @@ -0,0 +1,710 @@ +/* ----------------------------------------------------------------------- * + * + * Copyright 2007-2008 H. Peter Anvin - All Rights Reserved + * Copyright 2009 Intel Corporation; author: H. Peter Anvin + * + * Permission is hereby granted, free of charge, to any person + * obtaining a copy of this software and associated documentation + * files (the "Software"), to deal in the Software without + * restriction, including without limitation the rights to use, + * copy, modify, merge, publish, distribute, sublicense, and/or + * sell copies of the Software, and to permit persons to whom + * the Software is furnished to do so, subject to the following + * conditions: + * + * The above copyright notice and this permission notice shall + * be included in all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, + * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES + * OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND + * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT + * HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, + * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING + * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR + * OTHER DEALINGS IN THE SOFTWARE. + * + * ----------------------------------------------------------------------- */ + +/* + * movebits.c + * + * Utility function to take a list of memory areas to shuffle and + * convert it to a set of shuffle operations. + * + * Note: a lot of the functions in this file deal with "parent pointers", + * which are pointers to a pointer to a list, or part of the list. + * They can be pointers to a variable holding the list root pointer, + * or pointers to a next field of a previous entry. + */ + +#include <assert.h> +#include <stdio.h> +#include <errno.h> +#include <stdlib.h> +#include <inttypes.h> +#include <setjmp.h> +#include <minmax.h> +#include <stdbool.h> + +#include <syslinux/movebits.h> + +#ifndef DEBUG +# ifdef TEST +# define DEBUG 1 +# else +# define DEBUG 0 +# endif +#endif + +#if DEBUG +# include <stdio.h> +# define dprintf printf +#else +# define dprintf(...) ((void)0) +#endif + +static jmp_buf new_movelist_bail; + +static struct syslinux_movelist *new_movelist(addr_t dst, addr_t src, + addr_t len) +{ + struct syslinux_movelist *ml = malloc(sizeof(struct syslinux_movelist)); + + if (!ml) + longjmp(new_movelist_bail, 1); + + ml->dst = dst; + ml->src = src; + ml->len = len; + ml->next = NULL; + + 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; +} + +static void +add_freelist(struct syslinux_memmap **mmap, addr_t start, + addr_t len, enum syslinux_memmap_types type) +{ + if (syslinux_add_memmap(mmap, start, len, type)) + longjmp(new_movelist_bail, 1); +} + +/* + * Take a chunk, entirely confined in **parentptr, and split it off so that + * it has its own structure. + */ +static struct syslinux_movelist **split_movelist(addr_t start, addr_t len, + struct syslinux_movelist + **parentptr) +{ + struct syslinux_movelist *m, *ml = *parentptr; + + assert(start >= ml->src); + assert(start < ml->src + ml->len); + + /* Split off the beginning */ + if (start > ml->src) { + addr_t l = start - ml->src; + + m = new_movelist(ml->dst + l, start, ml->len - l); + m->next = ml->next; + ml->len = l; + ml->next = m; + + parentptr = &ml->next; + ml = m; /* Continue processing the new node */ + } + + /* Split off the end */ + if (ml->len > len) { + addr_t l = ml->len - len; + + m = new_movelist(ml->dst + len, ml->src + len, l); + m->next = ml->next; + ml->len = len; + ml->next = m; + } + + return parentptr; +} + +static void delete_movelist(struct syslinux_movelist **parentptr) +{ + struct syslinux_movelist *o = *parentptr; + *parentptr = o->next; + free(o); +} + +static void free_movelist(struct syslinux_movelist **parentptr) +{ + while (*parentptr) + delete_movelist(parentptr); +} + +/* + * Scan the freelist looking for a particular chunk of memory + */ +static const struct syslinux_memmap *is_free_zone(const struct syslinux_memmap + *list, addr_t start, + addr_t len) +{ + dprintf("f: 0x%08x bytes at 0x%08x\n", len, start); + + addr_t last, llast; + + last = start + len - 1; + + while (list->type != SMT_END) { + llast = list->next->start - 1; + if (list->start <= start) { + if (llast >= last) { + /* Chunk has a single, well-defined type */ + if (list->type == SMT_FREE) { + dprintf("F: 0x%08x bytes at 0x%08x\n", + list->next->start, list->start); + return list; /* It's free */ + } + return NULL; /* Not free */ + } else if (llast >= start) { + return NULL; /* Crosses region boundary */ + } + } + list = list->next; + } + + return NULL; /* Internal error? */ +} + +/* + * Scan the freelist looking for the smallest chunk of memory which + * can fit X bytes; returns the length of the block on success. + */ +static addr_t free_area(const struct syslinux_memmap *mmap, + addr_t len, addr_t * start) +{ + const struct syslinux_memmap *best = NULL; + const struct syslinux_memmap *s; + addr_t slen, best_len = -1; + + for (s = mmap; s->type != SMT_END; s = s->next) { + if (s->type != SMT_FREE) + continue; + slen = s->next->start - s->start; + if (slen >= len) { + if (!best || best_len > slen) { + best = s; + best_len = slen; + } + } + } + + if (best) { + *start = best->start; + return best_len; + } else { + return 0; + } +} + +/* + * Remove a chunk from the freelist + */ +static void +allocate_from(struct syslinux_memmap **mmap, addr_t start, addr_t len) +{ + syslinux_add_memmap(mmap, start, len, SMT_ALLOC); +} + +/* + * Find chunks of a movelist which are one-to-many (one source, multiple + * destinations.) Those chunks can get turned into post-shuffle copies, + * to avoid confusing the shuffler. + */ +static void shuffle_dealias(struct syslinux_movelist **fraglist, + struct syslinux_movelist **postcopy) +{ + struct syslinux_movelist *mp, **mpp, *mx, *np; + addr_t ps, pe, xs, xe, delta; + bool advance; + +#if DEBUG + dprintf("Before alias resolution:\n"); + syslinux_dump_movelist(stdout, *fraglist); +#endif + + *postcopy = NULL; + + /* + * Note: as written, this is an O(n^2) algorithm; by producing a list + * sorted by destination address we could reduce it to O(n log n). + */ + mpp = fraglist; + while ((mp = *mpp)) { + dprintf("mp -> (%#x,%#x,%#x)\n", mp->dst, mp->src, mp->len); + ps = mp->src; + pe = mp->src + mp->len - 1; + for (mx = *fraglist; mx != mp; mx = mx->next) { + dprintf("mx -> (%#x,%#x,%#x)\n", mx->dst, mx->src, mx->len); + /* + * If there is any overlap between mx and mp, mp should be + * modified and possibly split. + */ + xs = mx->src; + xe = mx->src + mx->len - 1; + + dprintf("?: %#x..%#x (inside %#x..%#x)\n", ps, pe, xs, xe); + + if (pe <= xs || ps >= xe) + continue; /* No overlap */ + + advance = false; + *mpp = mp->next; /* Remove from list */ + + if (pe > xe) { + delta = pe - xe; + np = new_movelist(mp->dst + mp->len - delta, + mp->src + mp->len - delta, delta); + mp->len -= delta; + pe = xe; + np->next = *mpp; + *mpp = np; + advance = true; + } + if (ps < xs) { + delta = xs - ps; + np = new_movelist(mp->dst, ps, delta); + mp->src += delta; + ps = mp->src; + mp->dst += delta; + mp->len -= delta; + np->next = *mpp; + *mpp = np; + advance = true; + } + + assert(ps >= xs && pe <= xe); + + dprintf("Overlap: %#x..%#x (inside %#x..%#x)\n", ps, pe, xs, xe); + + mp->src = mx->dst + (ps - xs); + mp->next = *postcopy; + *postcopy = mp; + + mp = *mpp; + + if (!advance) + goto restart; + } + + mpp = &mp->next; +restart: + ; + } + +#if DEBUG + dprintf("After alias resolution:\n"); + syslinux_dump_movelist(stdout, *fraglist); + dprintf("Post-shuffle copies:\n"); + syslinux_dump_movelist(stdout, *postcopy); +#endif +} + +/* + * The code to actually emit moving of a chunk into its final place. + */ +static void +move_chunk(struct syslinux_movelist ***moves, + struct syslinux_memmap **mmap, + struct syslinux_movelist **fp, addr_t copylen) +{ + addr_t copydst, copysrc; + addr_t freebase, freelen; + addr_t needlen; + int reverse; + struct syslinux_movelist *f = *fp, *mv; + + if (f->src < f->dst && (f->dst - f->src) < f->len) { + /* "Shift up" type overlap */ + needlen = f->dst - f->src; + reverse = 1; + } else if (f->src > f->dst && (f->src - f->dst) < f->len) { + /* "Shift down" type overlap */ + needlen = f->src - f->dst; + reverse = 0; + } else { + needlen = f->len; + reverse = 0; + } + + 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(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; + } + + dprintf("F: 0x%08x bytes at 0x%08x\n", freelen, freebase); + + add_freelist(mmap, freebase, freelen, SMT_FREE); + + delete_movelist(fp); +} + +/* + * moves is computed from "frags" and "freemem". "space" lists + * free memory areas at our disposal, and is (src, cnt) only. + */ +int +syslinux_compute_movelist(struct syslinux_movelist **moves, + struct syslinux_movelist *ifrags, + struct syslinux_memmap *memmap) +{ + struct syslinux_memmap *mmap = NULL; + const struct syslinux_memmap *mm, *ep; + struct syslinux_movelist *frags = NULL; + struct syslinux_movelist *postcopy = NULL; + struct syslinux_movelist *mv; + struct syslinux_movelist *f, **fp; + struct syslinux_movelist *o, **op; + addr_t needbase, needlen, copysrc, copydst, copylen; + addr_t avail; + addr_t fstart, flen; + addr_t cbyte; + addr_t ep_len; + int rv = -1; + int reverse; + + dprintf("entering syslinux_compute_movelist()...\n"); + + if (setjmp(new_movelist_bail)) { +nomem: + dprintf("Out of working memory!\n"); + goto bail; + } + + *moves = NULL; + + /* Create our memory map. Anything that is SMT_FREE or SMT_ZERO is + fair game, but mark anything used by source material as SMT_ALLOC. */ + mmap = syslinux_init_memmap(); + if (!mmap) + goto nomem; + + frags = dup_movelist(ifrags); + + /* Process one-to-many conditions */ + shuffle_dealias(&frags, &postcopy); + + for (mm = memmap; mm->type != SMT_END; mm = mm->next) + add_freelist(&mmap, mm->start, mm->next->start - mm->start, + mm->type == SMT_ZERO ? SMT_FREE : mm->type); + + for (f = frags; f; f = f->next) + add_freelist(&mmap, f->src, f->len, SMT_ALLOC); + + /* As long as there are unprocessed fragments in the chain... */ + while ((fp = &frags, f = *fp)) { + +#if DEBUG + dprintf("Current free list:\n"); + syslinux_dump_memmap(stdout, mmap); + dprintf("Current frag list:\n"); + syslinux_dump_movelist(stdout, frags); +#endif + + /* Scan for fragments which can be discarded without action. */ + if (f->src == f->dst) { + delete_movelist(fp); + continue; + } + op = &f->next; + while ((o = *op)) { + if (o->src == o->dst) + delete_movelist(op); + else + op = &o->next; + } + + /* Scan for fragments which can be immediately moved + to their final destination, if so handle them now */ + for (op = fp; (o = *op); op = &o->next) { + if (o->src < o->dst && (o->dst - o->src) < o->len) { + /* "Shift up" type overlap */ + needlen = o->dst - o->src; + needbase = o->dst + (o->len - needlen); + reverse = 1; + cbyte = o->dst + o->len - 1; + } else if (o->src > o->dst && (o->src - o->dst) < o->len) { + /* "Shift down" type overlap */ + needlen = o->src - o->dst; + needbase = o->dst; + reverse = 0; + cbyte = o->dst; /* "Critical byte" */ + } else { + needlen = o->len; + needbase = o->dst; + reverse = 0; + cbyte = o->dst; /* "Critical byte" */ + } + + if (is_free_zone(mmap, needbase, needlen)) { + fp = op, f = o; + dprintf("!: 0x%08x bytes at 0x%08x -> 0x%08x\n", + f->len, f->src, f->dst); + copysrc = f->src; + copylen = needlen; + allocate_from(&mmap, needbase, copylen); + goto move_chunk; + } + } + + /* Ok, bother. Need to do real work at least with one chunk. */ + + dprintf("@: 0x%08x bytes at 0x%08x -> 0x%08x\n", + f->len, f->src, f->dst); + + /* See if we can move this chunk into place by claiming + the destination, or in the case of partial overlap, the + missing portion. */ + + 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); + reverse = 1; + cbyte = f->dst + f->len - 1; + } else if (f->src > f->dst && (f->src - f->dst) < f->len) { + /* "Shift down" type overlap */ + needlen = f->src - f->dst; + needbase = f->dst; + reverse = 0; + cbyte = f->dst; /* "Critical byte" */ + } else { + needlen = f->len; + needbase = f->dst; + reverse = 0; + cbyte = f->dst; + } + + dprintf("need: base = 0x%08x, len = 0x%08x, " + "reverse = %d, cbyte = 0x%08x\n", + needbase, needlen, reverse, cbyte); + + ep = is_free_zone(mmap, cbyte, 1); + if (ep) { + ep_len = ep->next->start - ep->start; + if (reverse) + avail = needbase + needlen - ep->start; + else + avail = ep_len - (needbase - ep->start); + } else { + avail = 0; + } + + 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->start, ep_len, avail); + copylen = min(needlen, avail); + + if (reverse) + allocate_from(&mmap, needbase + needlen - copylen, copylen); + else + allocate_from(&mmap, needbase, copylen); + + goto move_chunk; + } + + /* 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", + o->len, o->src, o->dst); + + if (!(o->src <= cbyte && o->src + o->len > cbyte)) + continue; /* Not what we're looking for... */ + + /* Find somewhere to put it... */ + + if (is_free_zone(mmap, o->dst, o->len)) { + /* Score! We can move it into place directly... */ + copydst = o->dst; + copysrc = o->src; + copylen = o->len; + } else if (free_area(mmap, o->len, &fstart)) { + /* We can move the whole chunk */ + copydst = fstart; + copysrc = o->src; + copylen = o->len; + } else { + /* Well, copy as much as we can... */ + if (syslinux_memmap_largest(mmap, SMT_FREE, &fstart, &flen)) { + dprintf("No free memory at all!\n"); + goto bail; /* Stuck! */ + } + + /* Make sure we include the critical byte */ + copydst = fstart; + if (reverse) { + copysrc = max(o->src, cbyte + 1 - flen); + copylen = cbyte + 1 - copysrc; + } else { + copysrc = cbyte; + copylen = min(flen, o->len - (cbyte - o->src)); + } + } + allocate_from(&mmap, copydst, copylen); + + if (copylen < o->len) { + op = split_movelist(copysrc, copylen, op); + o = *op; + } + + 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) { + add_freelist(&mmap, copysrc, needbase - copysrc, SMT_FREE); + copylen -= (needbase - copysrc); + } + if (copylen > needlen) { + add_freelist(&mmap, copysrc + needlen, copylen - needlen, + SMT_FREE); + copylen = needlen; + } + } + reverse = 0; + goto move_chunk; + } + dprintf("Cannot find the chunk containing the critical byte\n"); + goto bail; /* Stuck! */ + +move_chunk: + move_chunk(&moves, &mmap, fp, copylen); + } + + /* Finally, append the postcopy chain to the end of the moves list */ + for (op = moves; (o = *op); op = &o->next) ; /* Locate the end of the list */ + *op = postcopy; + postcopy = NULL; + + rv = 0; +bail: + if (mmap) + syslinux_free_memmap(mmap); + if (frags) + free_movelist(&frags); + if (postcopy) + free_movelist(&postcopy); + return rv; +} + +#ifdef TEST + +#include <stdio.h> + +int main(int argc, char *argv[]) +{ + FILE *f; + unsigned long d, s, l; + struct syslinux_movelist *frags; + struct syslinux_movelist **fep = &frags; + struct syslinux_movelist *mv, *moves; + struct syslinux_memmap *memmap; + char line[BUFSIZ]; + + (void)argc; + + memmap = syslinux_init_memmap(); + + f = fopen(argv[1], "r"); + while (fgets(line, sizeof line, f) != NULL) { + if (sscanf(line, "%lx %lx %lx", &s, &d, &l) == 3) { + if (d) { + if (s == -1UL) { + syslinux_add_memmap(&memmap, d, l, SMT_ZERO); + } else { + mv = new_movelist(d, s, l); + *fep = mv; + fep = &mv->next; + } + } else { + syslinux_add_memmap(&memmap, s, l, SMT_FREE); + } + } + } + fclose(f); + + *fep = NULL; + + printf("Input move list:\n"); + syslinux_dump_movelist(stdout, frags); + printf("Input free list:\n"); + syslinux_dump_memmap(stdout, memmap); + + if (syslinux_compute_movelist(&moves, frags, memmap)) { + printf("Failed to compute a move sequence\n"); + return 1; + } else { + printf("Final move list:\n"); + syslinux_dump_movelist(stdout, moves); + return 0; + } +} + +#endif /* TEST */ |