com32/lib/syslinux/movebits.c

   1 /* ----------------------------------------------------------------------- *
   2  *
   3  *   Copyright 2007-2008 H. Peter Anvin - All Rights Reserved
   4  *   Copyright 2009 Intel Corporation; author: H. Peter Anvin
   5  *
   6  *   Permission is hereby granted, free of charge, to any person
   7  *   obtaining a copy of this software and associated documentation
   8  *   files (the "Software"), to deal in the Software without
   9  *   restriction, including without limitation the rights to use,
  10  *   copy, modify, merge, publish, distribute, sublicense, and/or
  11  *   sell copies of the Software, and to permit persons to whom
  12  *   the Software is furnished to do so, subject to the following
  13  *   conditions:
  14  *
  15  *   The above copyright notice and this permission notice shall
  16  *   be included in all copies or substantial portions of the Software.
  17  *
  18  *   THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
  19  *   EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
  20  *   OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
  21  *   NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
  22  *   HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
  23  *   WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
  24  *   FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
  25  *   OTHER DEALINGS IN THE SOFTWARE.
  26  *
  27  * ----------------------------------------------------------------------- */
  28
  29 /*
  30  * movebits.c
  31  *
  32  * Utility function to take a list of memory areas to shuffle and
  33  * convert it to a set of shuffle operations.
  34  *
  35  * Note: a lot of the functions in this file deal with "parent pointers",
  36  * which are pointers to a pointer to a list, or part of the list.
  37  * They can be pointers to a variable holding the list root pointer,
  38  * or pointers to a next field of a previous entry.
  39  */
  40
  41 #include <assert.h>
  42 #include <stdio.h>
  43 #include <errno.h>
  44 #include <stdlib.h>
  45 #include <inttypes.h>
  46 #include <setjmp.h>
  47 #include <minmax.h>
  48 #include <stdbool.h>
  49
  50 #include <syslinux/movebits.h>
  51 #include <dprintf.h>
  52
  53 static jmp_buf new_movelist_bail;
  54
  55 static struct syslinux_movelist *new_movelist(addr_t dst, addr_t src,
  56                                               addr_t len)
  57 {
  58     struct syslinux_movelist *ml = malloc(sizeof(struct syslinux_movelist));
  59
  60     if (!ml)
  61         longjmp(new_movelist_bail, 1);
  62
  63     ml->dst = dst;
  64     ml->src = src;
  65     ml->len = len;
  66     ml->next = NULL;
  67
  68     return ml;
  69 }
  70
  71 static struct syslinux_movelist *dup_movelist(struct syslinux_movelist *src)
  72 {
  73     struct syslinux_movelist *dst = NULL, **dstp = &dst, *ml;
  74
  75     while (src) {
  76         ml = new_movelist(src->dst, src->src, src->len);
  77         *dstp = ml;
  78         dstp = &ml->next;
  79         src = src->next;
  80     }
  81
  82     return dst;
  83 }
  84
  85 static void
  86 add_freelist(struct syslinux_memmap **mmap, addr_t start,
  87              addr_t len, enum syslinux_memmap_types type)
  88 {
  89     if (syslinux_add_memmap(mmap, start, len, type))
  90         longjmp(new_movelist_bail, 1);
  91 }
  92
  93 /*
  94  * Take a chunk, entirely confined in **parentptr, and split it off so that
  95  * it has its own structure.
  96  */
  97 static struct syslinux_movelist **split_movelist(addr_t start, addr_t len,
  98                                                  struct syslinux_movelist
  99                                                  **parentptr)
 100 {
 101     struct syslinux_movelist *m, *ml = *parentptr;
 102
 103     assert(start >= ml->src);
 104     assert(start < ml->src + ml->len);
 105
 106     /* Split off the beginning */
 107     if (start > ml->src) {
 108         addr_t l = start - ml->src;
 109
 110         m = new_movelist(ml->dst + l, start, ml->len - l);
 111         m->next = ml->next;
 112         ml->len = l;
 113         ml->next = m;
 114
 115         parentptr = &ml->next;
 116         ml = m;                 /* Continue processing the new node */
 117     }
 118
 119     /* Split off the end */
 120     if (ml->len > len) {
 121         addr_t l = ml->len - len;
 122
 123         m = new_movelist(ml->dst + len, ml->src + len, l);
 124         m->next = ml->next;
 125         ml->len = len;
 126         ml->next = m;
 127     }
 128
 129     return parentptr;
 130 }
 131
 132 static void delete_movelist(struct syslinux_movelist **parentptr)
 133 {
 134     struct syslinux_movelist *o = *parentptr;
 135     *parentptr = o->next;
 136     free(o);
 137 }
 138
 139 static void free_movelist(struct syslinux_movelist **parentptr)
 140 {
 141     while (*parentptr)
 142         delete_movelist(parentptr);
 143 }
 144
 145 /*
 146  * Scan the freelist looking for a particular chunk of memory
 147  */
 148 static const struct syslinux_memmap *is_free_zone(const struct syslinux_memmap
 149                                                   *list, addr_t start,
 150                                                   addr_t len)
 151 {
 152     dprintf("f: 0x%08x bytes at 0x%08x\n", len, start);
 153
 154     addr_t last, llast;
 155
 156     last = start + len - 1;
 157
 158     while (list->type != SMT_END) {
 159         llast = list->next->start - 1;
 160         if (list->start <= start) {
 161             if (llast >= last) {
 162                 /* Chunk has a single, well-defined type */
 163                 if (list->type == SMT_FREE) {
 164                     dprintf("F: 0x%08x bytes at 0x%08x\n",
 165                             list->next->start, list->start);
 166                     return list;        /* It's free */
 167                 }
 168                 return NULL;    /* Not free */
 169             } else if (llast >= start) {
 170                 return NULL;    /* Crosses region boundary */
 171             }
 172         }
 173         list = list->next;
 174     }
 175
 176     return NULL;                /* Internal error? */
 177 }
 178
 179 /*
 180  * Scan the freelist looking for the smallest chunk of memory which
 181  * can fit X bytes; returns the length of the block on success.
 182  */
 183 static addr_t free_area(const struct syslinux_memmap *mmap,
 184                         addr_t len, addr_t * start)
 185 {
 186     const struct syslinux_memmap *best = NULL;
 187     const struct syslinux_memmap *s;
 188     addr_t slen, best_len = -1;
 189
 190     for (s = mmap; s->type != SMT_END; s = s->next) {
 191         if (s->type != SMT_FREE)
 192             continue;
 193         slen = s->next->start - s->start;
 194         if (slen >= len) {
 195             if (!best || best_len > slen) {
 196                 best = s;
 197                 best_len = slen;
 198             }
 199         }
 200     }
 201
 202     if (best) {
 203         *start = best->start;
 204         return best_len;
 205     } else {
 206         return 0;
 207     }
 208 }
 209
 210 /*
 211  * Remove a chunk from the freelist
 212  */
 213 static void
 214 allocate_from(struct syslinux_memmap **mmap, addr_t start, addr_t len)
 215 {
 216     syslinux_add_memmap(mmap, start, len, SMT_ALLOC);
 217 }
 218
 219 /*
 220  * Find chunks of a movelist which are one-to-many (one source, multiple
 221  * destinations.)  Those chunks can get turned into post-shuffle copies,
 222  * to avoid confusing the shuffler.
 223  */
 224 static void shuffle_dealias(struct syslinux_movelist **fraglist,
 225                             struct syslinux_movelist **postcopy)
 226 {
 227     struct syslinux_movelist *mp, **mpp, *mx, *np;
 228     addr_t ps, pe, xs, xe, delta;
 229     bool advance;
 230
 231     dprintf("Before alias resolution:\n");
 232     syslinux_dump_movelist(*fraglist);
 233
 234     *postcopy = NULL;
 235
 236     /*
 237      * Note: as written, this is an O(n^2) algorithm; by producing a list
 238      * sorted by destination address we could reduce it to O(n log n).
 239      */
 240     mpp = fraglist;
 241     while ((mp = *mpp)) {
 242         dprintf("mp -> (%#x,%#x,%#x)\n", mp->dst, mp->src, mp->len);
 243         ps = mp->src;
 244         pe = mp->src + mp->len - 1;
 245         for (mx = *fraglist; mx != mp; mx = mx->next) {
 246             dprintf("mx -> (%#x,%#x,%#x)\n", mx->dst, mx->src, mx->len);
 247             /*
 248              * If there is any overlap between mx and mp, mp should be
 249              * modified and possibly split.
 250              */
 251             xs = mx->src;
 252             xe = mx->src + mx->len - 1;
 253
 254             dprintf("?: %#x..%#x (inside %#x..%#x)\n", ps, pe, xs, xe);
 255
 256             if (pe <= xs || ps >= xe)
 257                 continue;       /* No overlap */
 258
 259             advance = false;
 260             *mpp = mp->next;    /* Remove from list */
 261
 262             if (pe > xe) {
 263                 delta = pe - xe;
 264                 np = new_movelist(mp->dst + mp->len - delta,
 265                                   mp->src + mp->len - delta, delta);
 266                 mp->len -= delta;
 267                 pe = xe;
 268                 np->next = *mpp;
 269                 *mpp = np;
 270                 advance = true;
 271             }
 272             if (ps < xs) {
 273                 delta = xs - ps;
 274                 np = new_movelist(mp->dst, ps, delta);
 275                 mp->src += delta;
 276                 ps = mp->src;
 277                 mp->dst += delta;
 278                 mp->len -= delta;
 279                 np->next = *mpp;
 280                 *mpp = np;
 281                 advance = true;
 282             }
 283
 284             assert(ps >= xs && pe <= xe);
 285
 286             dprintf("Overlap: %#x..%#x (inside %#x..%#x)\n", ps, pe, xs, xe);
 287
 288             mp->src = mx->dst + (ps - xs);
 289             mp->next = *postcopy;
 290             *postcopy = mp;
 291
 292             mp = *mpp;
 293
 294             if (!advance)
 295                 goto restart;
 296         }
 297
 298         mpp = &mp->next;
 299 restart:
 300         ;
 301     }
 302
 303     dprintf("After alias resolution:\n");
 304     syslinux_dump_movelist(*fraglist);
 305     dprintf("Post-shuffle copies:\n");
 306     syslinux_dump_movelist(*postcopy);
 307 }
 308
 309 /*
 310  * The code to actually emit moving of a chunk into its final place.
 311  */
 312 static void
 313 move_chunk(struct syslinux_movelist ***moves,
 314            struct syslinux_memmap **mmap,
 315            struct syslinux_movelist **fp, addr_t copylen)
 316 {
 317     addr_t copydst, copysrc;
 318     addr_t freebase, freelen;
 319     addr_t needlen;
 320     int reverse;
 321     struct syslinux_movelist *f = *fp, *mv;
 322
 323     if (f->src < f->dst && (f->dst - f->src) < f->len) {
 324         /* "Shift up" type overlap */
 325         needlen = f->dst - f->src;
 326         reverse = 1;
 327     } else if (f->src > f->dst && (f->src - f->dst) < f->len) {
 328         /* "Shift down" type overlap */
 329         needlen = f->src - f->dst;
 330         reverse = 0;
 331     } else {
 332         needlen = f->len;
 333         reverse = 0;
 334     }
 335
 336     copydst = f->dst;
 337     copysrc = f->src;
 338
 339     dprintf("Q: copylen = 0x%08x, needlen = 0x%08x\n", copylen, needlen);
 340
 341     if (copylen < needlen) {
 342         if (reverse) {
 343             copydst += (f->len - copylen);
 344             copysrc += (f->len - copylen);
 345         }
 346
 347         dprintf("X: 0x%08x bytes at 0x%08x -> 0x%08x\n",
 348                 copylen, copysrc, copydst);
 349
 350         /* Didn't get all we wanted, so we have to split the chunk */
 351         fp = split_movelist(copysrc, copylen, fp);      /* Is this right? */
 352         f = *fp;
 353     }
 354
 355     mv = new_movelist(f->dst, f->src, f->len);
 356     dprintf("A: 0x%08x bytes at 0x%08x -> 0x%08x\n", mv->len, mv->src, mv->dst);
 357     **moves = mv;
 358     *moves = &mv->next;
 359
 360     /* Figure out what memory we just freed up */
 361     if (f->dst > f->src) {
 362         freebase = f->src;
 363         freelen = min(f->len, f->dst - f->src);
 364     } else if (f->src >= f->dst + f->len) {
 365         freebase = f->src;
 366         freelen = f->len;
 367     } else {
 368         freelen = f->src - f->dst;
 369         freebase = f->dst + f->len;
 370     }
 371
 372     dprintf("F: 0x%08x bytes at 0x%08x\n", freelen, freebase);
 373
 374     add_freelist(mmap, freebase, freelen, SMT_FREE);
 375
 376     delete_movelist(fp);
 377 }
 378
 379 /*
 380  * moves is computed from "frags" and "freemem".  "space" lists
 381  * free memory areas at our disposal, and is (src, cnt) only.
 382  */
 383 int
 384 syslinux_compute_movelist(struct syslinux_movelist **moves,
 385                           struct syslinux_movelist *ifrags,
 386                           struct syslinux_memmap *memmap)
 387 {
 388     struct syslinux_memmap *mmap = NULL;
 389     const struct syslinux_memmap *mm, *ep;
 390     struct syslinux_movelist *frags = NULL;
 391     struct syslinux_movelist *postcopy = NULL;
 392     struct syslinux_movelist *mv;
 393     struct syslinux_movelist *f, **fp;
 394     struct syslinux_movelist *o, **op;
 395     addr_t needbase, needlen, copysrc, copydst, copylen;
 396     addr_t avail;
 397     addr_t fstart, flen;
 398     addr_t cbyte;
 399     addr_t ep_len;
 400     int rv = -1;
 401     int reverse;
 402
 403     dprintf("entering syslinux_compute_movelist()...\n");
 404
 405     if (setjmp(new_movelist_bail)) {
 406 nomem:
 407         dprintf("Out of working memory!\n");
 408         goto bail;
 409     }
 410
 411     *moves = NULL;
 412
 413     /* Create our memory map.  Anything that is SMT_FREE or SMT_ZERO is
 414        fair game, but mark anything used by source material as SMT_ALLOC. */
 415     mmap = syslinux_init_memmap();
 416     if (!mmap)
 417         goto nomem;
 418
 419     frags = dup_movelist(ifrags);
 420
 421     /* Process one-to-many conditions */
 422     shuffle_dealias(&frags, &postcopy);
 423
 424     for (mm = memmap; mm->type != SMT_END; mm = mm->next)
 425         add_freelist(&mmap, mm->start, mm->next->start - mm->start,
 426                      mm->type == SMT_ZERO ? SMT_FREE : mm->type);
 427
 428     for (f = frags; f; f = f->next)
 429         add_freelist(&mmap, f->src, f->len, SMT_ALLOC);
 430
 431     /* As long as there are unprocessed fragments in the chain... */
 432     while ((fp = &frags, f = *fp)) {
 433
 434         dprintf("Current free list:\n");
 435         syslinux_dump_memmap(mmap);
 436         dprintf("Current frag list:\n");
 437         syslinux_dump_movelist(frags);
 438
 439         /* Scan for fragments which can be discarded without action. */
 440         if (f->src == f->dst) {
 441             delete_movelist(fp);
 442             continue;
 443         }
 444         op = &f->next;
 445         while ((o = *op)) {
 446             if (o->src == o->dst)
 447                 delete_movelist(op);
 448             else
 449                 op = &o->next;
 450         }
 451
 452         /* Scan for fragments which can be immediately moved
 453            to their final destination, if so handle them now */
 454         for (op = fp; (o = *op); op = &o->next) {
 455             if (o->src < o->dst && (o->dst - o->src) < o->len) {
 456                 /* "Shift up" type overlap */
 457                 needlen = o->dst - o->src;
 458                 needbase = o->dst + (o->len - needlen);
 459                 reverse = 1;
 460                 cbyte = o->dst + o->len - 1;
 461             } else if (o->src > o->dst && (o->src - o->dst) < o->len) {
 462                 /* "Shift down" type overlap */
 463                 needlen = o->src - o->dst;
 464                 needbase = o->dst;
 465                 reverse = 0;
 466                 cbyte = o->dst; /* "Critical byte" */
 467             } else {
 468                 needlen = o->len;
 469                 needbase = o->dst;
 470                 reverse = 0;
 471                 cbyte = o->dst; /* "Critical byte" */
 472             }
 473
 474             if (is_free_zone(mmap, needbase, needlen)) {
 475                 fp = op, f = o;
 476                 dprintf("!: 0x%08x bytes at 0x%08x -> 0x%08x\n",
 477                         f->len, f->src, f->dst);
 478                 copysrc = f->src;
 479                 copylen = needlen;
 480                 allocate_from(&mmap, needbase, copylen);
 481                 goto move_chunk;
 482             }
 483         }
 484
 485         /* Ok, bother.  Need to do real work at least with one chunk. */
 486
 487         dprintf("@: 0x%08x bytes at 0x%08x -> 0x%08x\n",
 488                 f->len, f->src, f->dst);
 489
 490         /* See if we can move this chunk into place by claiming
 491            the destination, or in the case of partial overlap, the
 492            missing portion. */
 493
 494         if (f->src < f->dst && (f->dst - f->src) < f->len) {
 495             /* "Shift up" type overlap */
 496             needlen = f->dst - f->src;
 497             needbase = f->dst + (f->len - needlen);
 498             reverse = 1;
 499             cbyte = f->dst + f->len - 1;
 500         } else if (f->src > f->dst && (f->src - f->dst) < f->len) {
 501             /* "Shift down" type overlap */
 502             needlen = f->src - f->dst;
 503             needbase = f->dst;
 504             reverse = 0;
 505             cbyte = f->dst;     /* "Critical byte" */
 506         } else {
 507             needlen = f->len;
 508             needbase = f->dst;
 509             reverse = 0;
 510             cbyte = f->dst;
 511         }
 512
 513         dprintf("need: base = 0x%08x, len = 0x%08x, "
 514                 "reverse = %d, cbyte = 0x%08x\n",
 515                 needbase, needlen, reverse, cbyte);
 516
 517         ep = is_free_zone(mmap, cbyte, 1);
 518         if (ep) {
 519             ep_len = ep->next->start - ep->start;
 520             if (reverse)
 521                 avail = needbase + needlen - ep->start;
 522             else
 523                 avail = ep_len - (needbase - ep->start);
 524         } else {
 525             avail = 0;
 526         }
 527
 528         if (avail) {
 529             /* We can move at least part of this chunk into place without
 530                further ado */
 531             dprintf("space: start 0x%08x, len 0x%08x, free 0x%08x\n",
 532                     ep->start, ep_len, avail);
 533             copylen = min(needlen, avail);
 534
 535             if (reverse)
 536                 allocate_from(&mmap, needbase + needlen - copylen, copylen);
 537             else
 538                 allocate_from(&mmap, needbase, copylen);
 539
 540             goto move_chunk;
 541         }
 542
 543         /* At this point, we need to evict something out of our space.
 544            Find the object occupying the critical byte of our target space,
 545            and move it out (the whole object if we can, otherwise a subset.)
 546            Then move a chunk of ourselves into place. */
 547         for (op = &f->next, o = *op; o; op = &o->next, o = *op) {
 548
 549             dprintf("O: 0x%08x bytes at 0x%08x -> 0x%08x\n",
 550                     o->len, o->src, o->dst);
 551
 552             if (!(o->src <= cbyte && o->src + o->len > cbyte))
 553                 continue;       /* Not what we're looking for... */
 554
 555             /* Find somewhere to put it... */
 556
 557             if (is_free_zone(mmap, o->dst, o->len)) {
 558                 /* Score!  We can move it into place directly... */
 559                 copydst = o->dst;
 560                 copysrc = o->src;
 561                 copylen = o->len;
 562             } else if (free_area(mmap, o->len, &fstart)) {
 563                 /* We can move the whole chunk */
 564                 copydst = fstart;
 565                 copysrc = o->src;
 566                 copylen = o->len;
 567             } else {
 568                 /* Well, copy as much as we can... */
 569                 if (syslinux_memmap_largest(mmap, SMT_FREE, &fstart, &flen)) {
 570                     dprintf("No free memory at all!\n");
 571                     goto bail;  /* Stuck! */
 572                 }
 573
 574                 /* Make sure we include the critical byte */
 575                 copydst = fstart;
 576                 if (reverse) {
 577                     copysrc = max(o->src, cbyte + 1 - flen);
 578                     copylen = cbyte + 1 - copysrc;
 579                 } else {
 580                     copysrc = cbyte;
 581                     copylen = min(flen, o->len - (cbyte - o->src));
 582                 }
 583             }
 584             allocate_from(&mmap, copydst, copylen);
 585
 586             if (copylen < o->len) {
 587                 op = split_movelist(copysrc, copylen, op);
 588                 o = *op;
 589             }
 590
 591             mv = new_movelist(copydst, copysrc, copylen);
 592             dprintf("C: 0x%08x bytes at 0x%08x -> 0x%08x\n",
 593                     mv->len, mv->src, mv->dst);
 594             *moves = mv;
 595             moves = &mv->next;
 596
 597             o->src = copydst;
 598
 599             if (copylen > needlen) {
 600                 /* We don't need all the memory we freed up.  Mark it free. */
 601                 if (copysrc < needbase) {
 602                     add_freelist(&mmap, copysrc, needbase - copysrc, SMT_FREE);
 603                     copylen -= (needbase - copysrc);
 604                 }
 605                 if (copylen > needlen) {
 606                     add_freelist(&mmap, copysrc + needlen, copylen - needlen,
 607                                  SMT_FREE);
 608                     copylen = needlen;
 609                 }
 610             }
 611             reverse = 0;
 612             goto move_chunk;
 613         }
 614         dprintf("Cannot find the chunk containing the critical byte\n");
 615         goto bail;              /* Stuck! */
 616
 617 move_chunk:
 618         move_chunk(&moves, &mmap, fp, copylen);
 619     }
 620
 621     /* Finally, append the postcopy chain to the end of the moves list */
 622     for (op = moves; (o = *op); op = &o->next) ;        /* Locate the end of the list */
 623     *op = postcopy;
 624     postcopy = NULL;
 625
 626     rv = 0;
 627 bail:
 628     if (mmap)
 629         syslinux_free_memmap(mmap);
 630     if (frags)
 631         free_movelist(&frags);
 632     if (postcopy)
 633         free_movelist(&postcopy);
 634     return rv;
 635 }
 636
 637 #ifdef TEST
 638
 639 #include <stdio.h>
 640
 641 int main(int argc, char *argv[])
 642 {
 643     FILE *f;
 644     unsigned long d, s, l;
 645     struct syslinux_movelist *frags;
 646     struct syslinux_movelist **fep = &frags;
 647     struct syslinux_movelist *mv, *moves;
 648     struct syslinux_memmap *memmap;
 649     char line[BUFSIZ];
 650
 651     (void)argc;
 652
 653     memmap = syslinux_init_memmap();
 654
 655     f = fopen(argv[1], "r");
 656     while (fgets(line, sizeof line, f) != NULL) {
 657         if (sscanf(line, "%lx %lx %lx", &s, &d, &l) == 3) {
 658             if (d) {
 659                 if (s == -1UL) {
 660                     syslinux_add_memmap(&memmap, d, l, SMT_ZERO);
 661                 } else {
 662                     mv = new_movelist(d, s, l);
 663                     *fep = mv;
 664                     fep = &mv->next;
 665                 }
 666             } else {
 667                 syslinux_add_memmap(&memmap, s, l, SMT_FREE);
 668             }
 669         }
 670     }
 671     fclose(f);
 672
 673     *fep = NULL;
 674
 675     dprintf("Input move list:\n");
 676     syslinux_dump_movelist(frags);
 677     dprintf("Input free list:\n");
 678     syslinux_dump_memmap(memmap);
 679
 680     if (syslinux_compute_movelist(&moves, frags, memmap)) {
 681         printf("Failed to compute a move sequence\n");
 682         return 1;
 683     } else {
 684         dprintf("Final move list:\n");
 685         syslinux_dump_movelist(stdout, moves);
 686         return 0;
 687     }
 688 }
 689
 690 #endif /* TEST */