com32/lib/syslinux/movebits.c

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