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