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 /*
 101  * Take a chunk, entirely confined in **parentptr, and split it off so that
 102  * it has its own structure.
 103  */
 104 static struct syslinux_movelist **
 105 split_movelist(addr_t start, addr_t len, struct syslinux_movelist **parentptr)
 106 {
 107   struct syslinux_movelist *m, *ml = *parentptr;
 108
 109   assert(start >= ml->src);
 110   assert(start < ml->src+ml->len);
 111
 112   /* Split off the beginning */
 113   if ( start > ml->src ) {
 114     addr_t l = start - ml->src;
 115
 116     m = new_movelist(ml->dst+l, start, ml->len-l);
 117     m->next = ml->next;
 118     ml->len = l;
 119     ml->next = m;
 120
 121     parentptr = &ml->next;
 122     ml = m;                     /* Continue processing the new node */
 123   }
 124
 125   /* Split off the end */
 126   if ( ml->len > len ) {
 127     addr_t l = ml->len - len;
 128
 129     m = new_movelist(ml->dst+len, ml->src+len, l);
 130     m->next = ml->next;
 131     ml->len = len;
 132     ml->next = m;
 133   }
 134
 135   return parentptr;
 136 }
 137
 138 static void
 139 delete_movelist(struct syslinux_movelist **parentptr)
 140 {
 141   struct syslinux_movelist *o = *parentptr;
 142   *parentptr = o->next;
 143   free(o);
 144 }
 145
 146 static void
 147 free_movelist(struct syslinux_movelist **parentptr)
 148 {
 149   while (*parentptr)
 150     delete_movelist(parentptr);
 151 }
 152
 153 /*
 154  * Scan the freelist looking for a particular chunk of memory
 155  */
 156 static struct syslinux_movelist **
 157 is_free_zone(addr_t start, addr_t len, struct syslinux_movelist **space)
 158 {
 159   struct syslinux_movelist *s;
 160
 161   while ( (s = *space) ) {
 162     if ( s->src <= start && s->src+s->len >= start+len )
 163       return space;
 164     space = &s->next;
 165   }
 166
 167   return NULL;
 168 }
 169
 170 /*
 171  * Scan the freelist looking for the smallest chunk of memory which
 172  * can fit X bytes
 173  */
 174 static struct syslinux_movelist **
 175 free_area(addr_t len, struct syslinux_movelist **space)
 176 {
 177   struct syslinux_movelist **best = NULL;
 178   struct syslinux_movelist *s;
 179
 180   while ( (s = *space) ) {
 181     if ( s->len >= len ) {
 182       if ( !best || (*best)->len > s->len )
 183         best = space;
 184     }
 185     space = &s->next;
 186   }
 187
 188   return best;
 189 }
 190
 191
 192 /*
 193  * Scan the freelist looking for the largest chunk of memory,
 194  * returns parent ptr
 195  */
 196 static struct syslinux_movelist **
 197 free_area_max(struct syslinux_movelist **space)
 198 {
 199   struct syslinux_movelist **best = NULL;
 200   struct syslinux_movelist *s;
 201
 202   while ( (s = *space) ) {
 203     if ( !best || s->len > (*best)->len )
 204       best = space;
 205     space = &s->next;
 206   }
 207
 208   return best;
 209 }
 210
 211 /*
 212  * Remove a chunk from the freelist
 213  */
 214 static void
 215 allocate_from(addr_t start, addr_t len, struct syslinux_movelist **parentptr)
 216 {
 217   struct syslinux_movelist *c = *parentptr;
 218
 219   assert(c->src <= start);
 220   assert(c->src+c->len >= start+len);
 221
 222   if ( c->src != start || c->len != len ) {
 223     parentptr = split_movelist(start, len, parentptr);
 224     c = *parentptr;
 225   }
 226
 227   *parentptr = c->next;
 228   free(c);
 229 }
 230
 231 #if 0
 232 /*
 233  * Remove any chunk from the freelist which is already
 234  * claimed by source data.  This somewhat frivolously
 235  * assumes that the fragments are either completely
 236  * covered by a free zone or not covered at all.
 237  */
 238 static void
 239 tidy_freelist(struct syslinux_movelist **frags,
 240               struct syslinux_movelist **space)
 241 {
 242   struct syslinux_movelist **sep;
 243   struct syslinux_movelist *f;
 244
 245   while ( (f = *frags) ) {
 246     if ( (sep = is_free_zone(f->src, f->len, space)) )
 247       allocate_from(f->src, f->len, sep);
 248     frags = &f->next;
 249   }
 250 }
 251 #endif
 252
 253 /*
 254  * moves is computed from "frags" and "freemem".  "space" lists
 255  * free memory areas at our disposal, and is (src, cnt) only.
 256  */
 257
 258 int
 259 syslinux_compute_movelist(struct syslinux_movelist **moves,
 260                           struct syslinux_movelist *ifrags,
 261                           struct syslinux_memmap *memmap)
 262 {
 263   struct syslinux_memmap *mmap = NULL, *mm;
 264   struct syslinux_movelist *frags = NULL;
 265   struct syslinux_movelist *mv, *space;
 266   struct syslinux_movelist *f, **fp, **ep;
 267   struct syslinux_movelist *o, **op;
 268   addr_t needbase, needlen, copysrc, copydst, copylen;
 269   addr_t freebase, freelen;
 270   addr_t mstart, avail;
 271   addr_t cbyte;
 272   int m_ok;
 273   int rv = -1;
 274   int reverse;
 275   int again;
 276
 277   dprintf("entering syslinux_compute_movelist()...\n");
 278
 279   if (setjmp(new_movelist_bail)) {
 280     dprintf("Out of working memory!\n");
 281     goto bail;
 282   }
 283
 284   *moves = NULL;
 285
 286   /* Mark any memory that's in use by source material busy in the memory map */
 287   mmap = syslinux_dup_memmap(memmap);
 288   if (!mmap)
 289     goto bail;
 290
 291   frags = dup_movelist(ifrags);
 292
 293 #if DEBUG
 294   dprintf("Initial memory map:\n");
 295   syslinux_dump_memmap(stdout, mmap);
 296 #endif
 297
 298   for (f = frags; f; f = f->next) {
 299     if (syslinux_add_memmap(&mmap, f->src, f->len, SMT_ALLOC)) {
 300       dprintf("Cannot generate free map\n");
 301       goto bail;
 302     }
 303   }
 304
 305 #if DEBUG
 306   dprintf("Adjusted memory map:\n");
 307   syslinux_dump_memmap(stdout, mmap);
 308 #endif
 309
 310   /* Compute the freelist in movelist format. */
 311   space = NULL;
 312   ep = &space;
 313   mstart = -1;
 314   m_ok = 0;
 315
 316   /* Yes, we really do want to run through the loop on SMT_END */
 317   for (mm = mmap; mm; mm = mm->next) {
 318     /* We can safely use to-be-zeroed memory as a scratch area. */
 319     if (mmap->type == SMT_FREE || mmap->type == SMT_ZERO) {
 320       if (!m_ok) {
 321         m_ok = 1;
 322         mstart = mmap->start;
 323       }
 324     } else {
 325       if (m_ok) {
 326         f = new_movelist(0, mstart, mmap->start - mstart);
 327         *ep = f;
 328         ep = &f->next;
 329         m_ok = 0;
 330       }
 331     }
 332
 333     mmap = mmap->next;
 334   }
 335
 336   do {
 337     again = 0;
 338
 339 #if DEBUG
 340     dprintf("Current free list:\n");
 341     syslinux_dump_movelist(stdout, space);
 342     dprintf("Current frag list:\n");
 343     syslinux_dump_movelist(stdout, frags);
 344 #endif
 345
 346     fp = &frags;
 347     while ( (f = *fp) ) {
 348       dprintf("@: 0x%08x bytes at 0x%08x -> 0x%08x\n",
 349               f->len, f->src, f->dst);
 350
 351       if ( f->src == f->dst ) {
 352         delete_movelist(fp);
 353         continue;
 354       }
 355
 356       /* See if we can move this chunk into place by claiming
 357          the destination, or in the case of partial overlap, the
 358          missing portion. */
 359
 360       needbase = f->dst;
 361       needlen  = f->len;
 362
 363       dprintf("need: base = 0x%08x, len = 0x%08x\n", needbase, needlen);
 364
 365       reverse = 0;
 366       cbyte = f->dst;           /* "Critical byte" */
 367       if ( f->src < f->dst && (f->dst - f->src) < f->len ) {
 368         /* "Shift up" type overlap */
 369         needlen  = f->dst - f->src;
 370         needbase = f->dst + (f->len - needlen);
 371         cbyte = f->dst + f->len - 1;
 372         reverse = 1;
 373       } else if ( f->src > f->dst && (f->src - f->dst) < f->len ) {
 374         /* "Shift down" type overlap */
 375         needbase = f->dst;
 376         needlen  = f->src - f->dst;
 377       }
 378
 379       dprintf("need: base = 0x%08x, len = 0x%08x, "
 380               "reverse = %d, cbyte = 0x%08x\n",
 381               needbase, needlen, reverse, cbyte);
 382
 383       ep = is_free_zone(cbyte, 1, &space);
 384       if (ep) {
 385         if (reverse)
 386           avail = needbase+needlen - (*ep)->src;
 387         else
 388           avail = (*ep)->len - (needbase - (*ep)->src);
 389       } else {
 390         avail = 0;
 391       }
 392
 393       if (avail) {
 394         /* We can move at least part of this chunk into place without
 395            further ado */
 396         dprintf("space: start 0x%08x, len 0x%08x, free 0x%08x\n",
 397                 (*ep)->src, (*ep)->len, avail);
 398         copylen = min(needlen, avail);
 399
 400         if (reverse)
 401           allocate_from(needbase+needlen-copylen, copylen, ep);
 402         else
 403           allocate_from(needbase, copylen, ep);
 404
 405         goto move_chunk;
 406       }
 407
 408       /* At this point, we need to evict something out of our space.
 409          Find the object occupying the critical byte of our target space,
 410          and move it out (the whole object if we can, otherwise a subset.)
 411          Then move a chunk of ourselves into place. */
 412       for ( op = &f->next, o = *op ; o ; op = &o->next, o = *op ) {
 413
 414         dprintf("O: 0x%08x bytes at 0x%08x -> 0x%08x\n",
 415                 o->len, o->src, o->dst);
 416
 417         if ( !(o->src <= cbyte && o->src+o->len > cbyte) )
 418           continue;             /* Not what we're looking for... */
 419
 420         /* Find somewhere to put it... */
 421
 422         if ( (ep = is_free_zone(o->dst, o->len, &space)) ) {
 423           /* Score!  We can move it into place directly... */
 424           copydst = o->dst;
 425           copylen = o->len;
 426         } else if ( (ep = free_area(o->len, &space)) ) {
 427           /* We can move the whole chunk */
 428           copydst = (*ep)->src;
 429           copylen = o->len;
 430         } else {
 431           /* Well, copy as much as we can... */
 432           ep = free_area_max(&space);
 433           if ( !ep ) {
 434             dprintf("No free memory at all!\n");
 435             goto bail;          /* Stuck! */
 436           }
 437
 438           /* Make sure we include the critical byte */
 439           copydst = (*ep)->src;
 440           if (reverse) {
 441             copysrc = max(o->src, cbyte+1 - (*ep)->len);
 442             copylen = cbyte+1 - copysrc;
 443           } else {
 444             copysrc = cbyte;
 445             copylen = min((*ep)->len, o->len - (cbyte-o->src));
 446           }
 447         }
 448         allocate_from(copydst, copylen, ep);
 449
 450         if ( copylen < o->len ) {
 451           op = split_movelist(copysrc, copylen, op);
 452           o = *op;
 453         }
 454
 455         mv = new_movelist(copydst, copysrc, copylen);
 456         dprintf("C: 0x%08x bytes at 0x%08x -> 0x%08x\n",
 457                 mv->len, mv->src, mv->dst);
 458         *moves = mv;
 459         moves = &mv->next;
 460
 461         o->src = copydst;
 462
 463         if ( copylen > needlen ) {
 464           /* We don't need all the memory we freed up.  Mark it free. */
 465           if ( copysrc < needbase ) {
 466             mv = new_movelist(0, copysrc, needbase-copysrc);
 467             mv->next = space;
 468             space = mv;
 469             copylen -= (needbase-copysrc);
 470           }
 471           if ( copylen > needlen ) {
 472             mv = new_movelist(0, copysrc+needlen, copylen-needlen);
 473             mv->next = space;
 474             space = mv;
 475             copylen = needlen;
 476           }
 477         }
 478         reverse = 0;
 479         goto move_chunk;
 480       }
 481       dprintf("Cannot find the chunk containing the critical byte\n");
 482       goto bail;                        /* Stuck! */
 483
 484     move_chunk:
 485       /* We're allowed to move the chunk into place now. */
 486
 487       copydst = f->dst;
 488       copysrc = f->src;
 489
 490       dprintf("Q: copylen = 0x%08x, needlen = 0x%08x\n", copylen, needlen);
 491
 492       if ( copylen < needlen ) {
 493         if (reverse) {
 494           copydst += (f->len-copylen);
 495           copysrc += (f->len-copylen);
 496         }
 497
 498         dprintf("X: 0x%08x bytes at 0x%08x -> 0x%08x\n",
 499                 copylen, copysrc, copydst);
 500
 501         /* Didn't get all we wanted, so we have to split the chunk */
 502         fp = split_movelist(copysrc, copylen, fp); /* Is this right? */
 503         f = *fp;
 504       }
 505
 506       mv = new_movelist(f->dst, f->src, f->len);
 507       dprintf("A: 0x%08x bytes at 0x%08x -> 0x%08x\n",
 508               mv->len, mv->src, mv->dst);
 509       *moves = mv;
 510       moves = &mv->next;
 511
 512       /* Figure out what memory we just freed up */
 513       if ( f->dst > f->src ) {
 514         freebase = f->src;
 515         freelen  = min(f->len, f->dst-f->src);
 516       } else if ( f->src >= f->dst+f->len ) {
 517         freebase = f->src;
 518         freelen  = f->len;
 519       } else {
 520         freelen  = f->src-f->dst;
 521         freebase = f->dst+f->len;
 522       }
 523
 524       dprintf("F: 0x%08x bytes at 0x%08x\n", freelen, freebase);
 525
 526       mv = new_movelist(0, freebase, freelen);
 527       mv->next = space;
 528       space = mv;
 529
 530       delete_movelist(fp);
 531       again = 1;                /* At least one chunk was moved */
 532     }
 533   } while (again);
 534
 535   rv = 0;
 536  bail:
 537   if (mmap)
 538     syslinux_free_memmap(mmap);
 539   if (frags)
 540     free_movelist(&frags);
 541   return rv;
 542 }
 543
 544 #ifdef TEST
 545
 546 #include <stdio.h>
 547
 548 int main(int argc, char *argv[])
 549 {
 550   FILE *f;
 551   unsigned long d, s, l;
 552   struct syslinux_movelist *frags;
 553   struct syslinux_movelist **fep = &frags;
 554   struct syslinux_movelist *space;
 555   struct syslinux_movelist **sep = &space;
 556   struct syslinux_movelist *mv, *moves;
 557
 558   f = fopen(argv[1], "r");
 559   while ( fscanf(f, "%lx %lx %lx", &d, &s, &l) == 3 ) {
 560     if ( d ) {
 561       mv = new_movelist(d, s, l);
 562       *fep = mv;
 563       fep = &mv->next;
 564     } else {
 565       mv = new_movelist(0, s, l);
 566       *sep = mv;
 567       sep = &mv->next;
 568     }
 569   }
 570   fclose(f);
 571
 572   if ( syslinux_compute_movelist(&moves, frags, space) ) {
 573     printf("Failed to compute a move sequence\n");
 574     return 1;
 575   } else {
 576     for ( mv = moves ; mv ; mv = mv->next ) {
 577       printf("0x%08x bytes at 0x%08x -> 0x%08x\n",
 578              mv->len, mv->src, mv->dst);
 579     }
 580     return 0;
 581   }
 582  }
 583
 584 #endif /* TEST */