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