com32/lib/syslinux/movebits.c

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