com32/libutil/movebits.c

   1 #include <assert.h>
   2 #include <stdio.h>
   3 #include <errno.h>
   4 #include <stdlib.h>
   5 #include <inttypes.h>
   6 #include <setjmp.h>
   7
   8 #include "movebits.h"
   9
  10 #ifdef TEST
  11 # define dprintf printf
  12 #else
  13 # define dprintf(...) ((void)0)
  14 #endif
  15
  16 #define min(x,y) ((x) < (y) ? (x) : (y))
  17 #define max(x,y) ((x) > (y) ? (x) : (y))
  18
  19 /*
  20  * Public utility function
  21  *
  22  * Creates a movelist consisting of only one element, and
  23  * if parent == NULL insert into the movelist chain immediately after
  24  * the parent element.
  25  */
  26 struct movelist *
  27 make_movelist(struct movelist *pptr, uintptr_t dst, uintptr_t src, uintptr_t len)
  28 {
  29   struct movelist *ml = malloc(sizeof(struct movelist));
  30
  31   if ( !ml )
  32     return NULL;
  33
  34   ml->dst = dst;
  35   ml->src = src;
  36   ml->len = len;
  37   ml->next = pptr ? pptr->next : NULL;
  38
  39   if ( pptr )
  40     pptr->next = ml;
  41
  42   return ml;
  43 }
  44
  45 /*
  46  * Public utility function
  47  *
  48  * Convert a movelist into a linear array of struct move_descriptors
  49  */
  50 size_t
  51 linearize_movelist(struct move_descriptor **d, struct movelist *m)
  52 {
  53   size_t n;
  54   struct movelist *mm;
  55   struct move_descriptor *l;
  56
  57   /* Count the length of the list */
  58   n = 0;
  59   for ( mm = m ; mm ; mm = mm->next )
  60     n++;
  61
  62   *d = l = malloc(n * sizeof(struct move_descriptor));
  63   if ( !l )
  64     return (size_t)-1;
  65
  66   while ( m ) {
  67     l->dst = m->dst;
  68     l->src = m->src;
  69     l->len = m->len;
  70     l++;
  71     mm = m;
  72     m = m->next;
  73     free(mm);
  74   }
  75
  76   return n;
  77 }
  78
  79
  80 static jmp_buf new_movelist_bail;
  81
  82 static struct movelist *
  83 new_movelist(uintptr_t dst, uintptr_t src, uintptr_t len)
  84 {
  85   struct movelist *ml = malloc(sizeof(struct movelist));
  86
  87   if ( !ml )
  88     longjmp(new_movelist_bail, 1);
  89
  90   ml->dst = dst;
  91   ml->src = src;
  92   ml->len = len;
  93   ml->next = NULL;
  94
  95   return ml;
  96 }
  97
  98 static struct movelist **
  99 split_movelist(uintptr_t start, uintptr_t len, struct movelist **parentptr)
 100 {
 101   struct 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     uintptr_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   if ( ml->len > len ) {
 120     uintptr_t l = ml->len - len;
 121
 122     m = new_movelist(ml->dst+len, ml->src+len, l);
 123     m->next = ml->next;
 124     ml->len = len;
 125     ml->next = m;
 126   }
 127
 128   return parentptr;
 129 }
 130
 131 #if 0
 132 static void
 133 delete_movelist(struct movelist **parentptr)
 134 {
 135   struct movelist *o = *parentptr;
 136   *parentptr = o->next;
 137   free(o);
 138 }
 139 #endif
 140
 141 /*
 142  * Scan the freelist looking for a particular chunk of memory
 143  */
 144 static struct movelist **
 145 is_free_zone(uintptr_t start, uintptr_t len, struct movelist **space)
 146 {
 147   struct movelist *s;
 148
 149   while ( (s = *space) ) {
 150     if ( s->src <= start && s->src+s->len >= start+len )
 151       return space;
 152     space = &s->next;
 153   }
 154
 155   return NULL;
 156 }
 157
 158 /*
 159  * Scan the freelist looking for the smallest chunk of memory which
 160  * can fit X bytes
 161  */
 162 static struct movelist **
 163 free_area(uintptr_t len, struct movelist **space)
 164 {
 165   struct movelist **best = NULL;
 166   struct movelist *s;
 167
 168   while ( (s = *space) ) {
 169     if ( s->len >= len ) {
 170       if ( !best || (*best)->len > s->len )
 171         best = space;
 172     }
 173     space = &s->next;
 174   }
 175
 176   return best;
 177 }
 178
 179
 180 /*
 181  * Scan the freelist looking for the largest chunk of memory, returns parent ptr
 182  */
 183 static struct movelist **
 184 free_area_max(struct movelist **space)
 185 {
 186   struct movelist **best = NULL;
 187   struct movelist *s;
 188
 189   while ( (s = *space) ) {
 190     if ( !best || s->len > (*best)->len )
 191       best = space;
 192     space = &s->next;
 193   }
 194
 195   return best;
 196 }
 197
 198 /*
 199  * Remove a chunk from the freelist
 200  */
 201 static void
 202 allocate_from(uintptr_t start, uintptr_t len, struct movelist **parentptr)
 203 {
 204   struct movelist *c = *parentptr;
 205
 206   assert(c->src <= start);
 207   assert(c->src+c->len >= start+len);
 208
 209   if ( c->src != start || c->len != len ) {
 210     parentptr = split_movelist(start, len, parentptr);
 211     c = *parentptr;
 212   }
 213
 214   *parentptr = c->next;
 215   free(c);
 216 }
 217
 218 /*
 219  * Remove any chunk from the freelist which is already
 220  * claimed by source data.  This somewhat frivolously
 221  * assumes that the fragments are either completely
 222  * covered by a free zone or not covered at all.
 223  */
 224 static void
 225 tidy_freelist(struct movelist **frags, struct movelist **space)
 226 {
 227   struct movelist **sep;
 228   struct movelist *f;
 229
 230   while ( (f = *frags) ) {
 231     if ( (sep = is_free_zone(f->src, f->len, space)) )
 232       allocate_from(f->src, f->len, sep);
 233     frags = &f->next;
 234   }
 235 }
 236
 237 /*
 238  * moves is computed from "frags" and "freemem".  "space" lists
 239  * free memory areas at our disposal, and is (src, cnt) only.
 240  */
 241
 242 int
 243 compute_movelist(struct movelist **moves, struct movelist *frags,
 244                  struct movelist *space)
 245 {
 246   struct movelist *mv;
 247   struct movelist *f, **fp, **ep;
 248   struct movelist *o, **op;
 249   uintptr_t needbase, needlen, copysrc, copydst, copylen;
 250   uintptr_t freebase, freelen;
 251
 252   *moves = NULL;
 253
 254   if ( setjmp(new_movelist_bail) )
 255     return -1;                  /* malloc() failed */
 256
 257   tidy_freelist(&frags, &space);
 258
 259   for ( fp = &frags, f = *fp ; f ; fp = &f->next, f = *fp ) {
 260     dprintf("@: 0x%08x bytes at 0x%08x -> 0x%08x\n",
 261             f->len, f->src, f->dst);
 262
 263     if ( f->src == f->dst ) {
 264       //delete_movelist(fp);    /* Already in the right place! */
 265       continue;
 266     }
 267
 268     /* See if we can move this chunk into place by claiming
 269        the destination, or in the case of partial overlap, the
 270        missing portion. */
 271
 272     needbase = f->dst;
 273     needlen  = f->len;
 274
 275     dprintf("need: base = 0x%08x, len = 0x%08x\n", needbase, needlen);
 276
 277     if ( f->src < f->dst && (f->dst - f->src) < f->len ) {
 278       /* "Shift up" type overlap */
 279       needlen  = f->dst - f->src;
 280       needbase = f->dst + (f->len - needlen);
 281     } else if ( f->src > f->dst && (f->src - f->dst) < f->len ) {
 282       /* "Shift down" type overlap */
 283       needbase = f->dst;
 284       needlen  = f->src - f->dst;
 285     }
 286
 287     if ( (ep = is_free_zone(needbase, 1, &space)) ) {
 288       /* We can move at least part of this chunk into place without further ado */
 289       copylen = min(needlen, (*ep)->len);
 290       allocate_from(needbase, copylen, ep);
 291       goto move_chunk;
 292     }
 293
 294     /* At this point, we need to evict something out of our space.
 295        Find the object occupying the first byte of our target space,
 296        and move it out (the whole object if we can, otherwise a subset.)
 297        Then move a chunk of ourselves into place. */
 298     for ( op = &f->next, o = *op ; o ; op = &o->next, o = *op ) {
 299
 300         dprintf("O: 0x%08x bytes        at 0x%08x -> 0x%08x\n",
 301                 o->len, o->src, o->dst);
 302
 303       if ( !(o->src <= needbase && o->src+o->len > needbase) )
 304         continue;               /* Not what we're looking for... */
 305
 306       /* Find somewhere to put it... */
 307       if ( (ep = free_area(o->len, &space)) ) {
 308         /* We got what we wanted... */
 309         copydst = (*ep)->src;
 310         copylen = o->len;
 311       } else {
 312         ep = free_area_max(&space);
 313         if ( !ep )
 314           return -1;            /* Stuck! */
 315         copydst = (*ep)->src;
 316         copylen = (*ep)->len;
 317       }
 318       allocate_from(copydst, copylen, ep);
 319
 320       if ( copylen >= o->len - (needbase-o->src) ) {
 321         copysrc = o->src + (o->len - copylen);
 322       } else {
 323         copysrc = o->src;
 324       }
 325
 326       if ( copylen < o->len ) {
 327         op = split_movelist(copysrc, copylen, op);
 328         o = *op;
 329       }
 330
 331       mv = new_movelist(copydst, copysrc, copylen);
 332       dprintf("C: 0x%08x bytes at 0x%08x -> 0x%08x\n",
 333               mv->len, mv->src, mv->dst);
 334       *moves = mv;
 335       moves = &mv->next;
 336
 337       o->src = copydst;
 338
 339       if ( copylen > needlen ) {
 340         /* We don't need all the memory we freed up.  Mark it free. */
 341         if ( copysrc < needbase ) {
 342           mv = new_movelist(0, copysrc, needbase-copysrc);
 343           mv->next = space;
 344           space = mv;
 345           copylen -= (needbase-copysrc);
 346         }
 347         if ( copylen > needlen ) {
 348           mv = new_movelist(0, copysrc+needlen, copylen-needlen);
 349           mv->next = space;
 350           space = mv;
 351           copylen = needlen;
 352         }
 353       }
 354       goto move_chunk;
 355     }
 356     return -1;                  /* Stuck! */
 357
 358   move_chunk:
 359     /* We're allowed to move the chunk into place now. */
 360
 361     if ( copylen < needlen ) {
 362       /* Didn't get all we wanted, so we have to split the chunk */
 363       fp = split_movelist(f->src, copylen+(needbase-f->dst), fp);
 364       f = *fp;
 365     }
 366
 367     mv = new_movelist(f->dst, f->src, f->len);
 368     dprintf("A: 0x%08x bytes at 0x%08x -> 0x%08x\n",
 369             mv->len, mv->src, mv->dst);
 370     *moves = mv;
 371     moves = &mv->next;
 372
 373     /* Figure out what memory we just freed up */
 374     if ( f->dst > f->src ) {
 375       freebase = f->src;
 376       freelen  = min(f->len, f->dst-f->src);
 377     } else if ( f->src >= f->dst+f->len ) {
 378       freebase = f->src;
 379       freelen  = f->len;
 380     } else {
 381       freelen  = f->src-f->dst;
 382       freebase = f->dst+f->len;
 383     }
 384
 385     mv = new_movelist(0, freebase, freelen);
 386     mv->next = space;
 387     space = mv;
 388   }
 389
 390   return 0;
 391 }
 392
 393 #ifdef TEST
 394
 395 #include <stdio.h>
 396
 397 int main(int argc, char *argv[])
 398 {
 399   FILE *f;
 400   unsigned long d, s, l;
 401   struct movelist *frags;
 402   struct movelist **fep = &frags;
 403   struct movelist *space;
 404   struct movelist **sep = &space;
 405   struct movelist *mv, *moves;
 406
 407   f = fopen(argv[1], "r");
 408   while ( fscanf(f, "%lx %lx %lx", &d, &s, &l) == 3 ) {
 409     if ( d ) {
 410       mv = new_movelist(d, s, l);
 411       *fep = mv;
 412       fep = &mv->next;
 413     } else {
 414       mv = new_movelist(0, s, l);
 415       *sep = mv;
 416       sep = &mv->next;
 417     }
 418   }
 419   fclose(f);
 420
 421   if ( compute_movelist(&moves, frags, space) ) {
 422     printf("Failed to compute a move sequence\n");
 423     return 1;
 424   } else {
 425     for ( mv = moves ; mv ; mv = mv->next ) {
 426       printf("0x%08x bytes at 0x%08x -> 0x%08x\n",
 427              mv->len, mv->src, mv->dst);
 428     }
 429     return 0;
 430   }
 431 }
 432
 433 #endif /* TEST */