1 /* 2 * CDDL HEADER START 3 * 4 * The contents of this file are subject to the terms of the 5 * Common Development and Distribution License, Version 1.0 only 6 * (the "License"). You may not use this file except in compliance 7 * with the License. 8 * 9 * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE 10 * or http://www.opensolaris.org/os/licensing. 11 * See the License for the specific language governing permissions 12 * and limitations under the License. 13 * 14 * When distributing Covered Code, include this CDDL HEADER in each 15 * file and include the License file at usr/src/OPENSOLARIS.LICENSE. 16 * If applicable, add the following below this CDDL HEADER, with the 17 * fields enclosed by brackets "[]" replaced with your own identifying 18 * information: Portions Copyright [yyyy] [name of copyright owner] 19 * 20 * CDDL HEADER END 21 */ 22 #pragma ident "%Z%%M% %I% %E% SMI" 23 24 /* 25 * Copyright (c) 1986 by Sun Microsystems, Inc. 26 */ 27 28 /* 29 * file: malloc.c 30 * description: 31 * Yet another memory allocator, this one based on a method 32 * described in C.J. Stephenson, "Fast Fits" 33 * 34 * The basic data structure is a "Cartesian" binary tree, in which 35 * nodes are ordered by ascending addresses (thus minimizing free 36 * list insertion time) and block sizes decrease with depth in the 37 * tree (thus minimizing search time for a block of a given size). 38 * 39 * In other words: for any node s, let D(s) denote the set of 40 * descendents of s; for all x in D(left(s)) and all y in 41 * D(right(s)), we have: 42 * 43 * a. addr(x) < addr(s) < addr(y) 44 * b. len(x) <= len(s) >= len(y) 45 */ 46 47 #include "mallint.h" 48 #include <errno.h> 49 50 /* system interface */ 51 52 extern char *sbrk(); 53 extern int getpagesize(); 54 extern abort(); 55 extern int errno; 56 57 static int nbpg = 0; /* set by calling getpagesize() */ 58 static bool morecore(); /* get more memory into free space */ 59 60 #ifdef S5EMUL 61 #define ptr_t void * /* ANSI C says these are voids */ 62 #define free_t void /* ANSI says void free(ptr_t ptr) */ 63 #define free_return(x) return 64 #else 65 #define ptr_t char * /* BSD still (4.3) wants char*'s */ 66 #define free_t int /* BSD says int free(ptr_t ptr) */ 67 #define free_return(x) return(x) 68 #endif 69 70 /* SystemV-compatible information structure */ 71 #define INIT_MXFAST 0 72 #define INIT_NLBLKS 100 73 #define INIT_GRAIN ALIGNSIZ 74 75 struct mallinfo __mallinfo = { 76 0,0,0,0,0,0,0,0,0,0, /* basic info */ 77 INIT_MXFAST, INIT_NLBLKS, INIT_GRAIN, /* mallopt options */ 78 0,0,0 79 }; 80 81 /* heap data structures */ 82 83 Freehdr _root = NIL; /* root of free space list */ 84 char *_lbound = NULL; /* lower bound of heap */ 85 char *_ubound = NULL; /* upper bound of heap */ 86 87 /* free header list management */ 88 89 static Freehdr getfreehdr(); 90 static putfreehdr(); 91 static Freehdr freehdrptr = NIL; /* ptr to block of available headers */ 92 static int nfreehdrs = 0; /* # of headers in current block */ 93 static Freehdr freehdrlist = NIL; /* List of available headers */ 94 95 /* error checking */ 96 static error(); /* sets errno; prints msg and aborts if DEBUG is on */ 97 98 #ifdef DEBUG /* >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> */ 99 100 int malloc_debug(/*level*/); 101 int malloc_verify(); 102 static int debug_level = 1; 103 104 /* 105 * A block with a negative size, a size that is not a multiple 106 * of ALIGNSIZ, a size greater than the current extent of the 107 * heap, or a size which extends beyond the end of the heap is 108 * considered bad. 109 */ 110 111 #define badblksize(p,size)\ 112 ( (size) < SMALLEST_BLK \ 113 || (size) & (ALIGNSIZ-1) \ 114 || (size) > heapsize() \ 115 || ((char*)(p))+(size) > _ubound ) 116 117 #else !DEBUG ================================================= 118 119 #define malloc_debug(level) 0 120 #define malloc_verify() 1 121 #define debug_level 0 122 #define badblksize(p,size) 0 123 124 #endif !DEBUG <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<< 125 126 127 /* 128 * insert (newblk, len) 129 * Inserts a new node in the free space tree, placing it 130 * in the correct position with respect to the existing nodes. 131 * 132 * algorithm: 133 * Starting from the root, a binary search is made for the new 134 * node. If this search were allowed to continue, it would 135 * eventually fail (since there cannot already be a node at the 136 * given address); but in fact it stops when it reaches a node in 137 * the tree which has a length less than that of the new node (or 138 * when it reaches a null tree pointer). 139 * 140 * The new node is then inserted at the root of the subtree for 141 * which the shorter node forms the old root (or in place of the 142 * null pointer). 143 */ 144 145 static 146 insert(newblk, len) 147 register Dblk newblk; /* Ptr to the block to insert */ 148 register uint len; /* Length of new node */ 149 { 150 register Freehdr *fpp; /* Address of ptr to subtree */ 151 register Freehdr x; 152 register Freehdr *left_hook; /* Temp for insertion */ 153 register Freehdr *right_hook; /* Temp for insertion */ 154 register Freehdr newhdr; 155 156 /* 157 * check for bad block size. 158 */ 159 if ( badblksize(newblk,len) ) { 160 error("insert: bad block size (%d) at %#x\n", len, newblk); 161 return; 162 } 163 164 /* 165 * Search for the first node which has a weight less 166 * than that of the new node; this will be the 167 * point at which we insert the new node. 168 */ 169 fpp = &_root; 170 x = *fpp; 171 while (weight(x) >= len) { 172 if (newblk < x->block) 173 fpp = &x->left; 174 else 175 fpp = &x->right; 176 x = *fpp; 177 } 178 179 /* 180 * Perform root insertion. The variable x traces a path through 181 * the fpp, and with the help of left_hook and right_hook, 182 * rewrites all links that cross the territory occupied 183 * by newblk. 184 */ 185 186 if ((newhdr = getfreehdr()) == NIL) { 187 /* Error message returned by getfreehdr() */ 188 return; 189 } 190 *fpp = newhdr; 191 192 newhdr->left = NIL; 193 newhdr->right = NIL; 194 newhdr->block = newblk; 195 newhdr->size = len; 196 197 /* 198 * set length word in the block for consistency with the header. 199 */ 200 201 newblk->size = len; 202 203 left_hook = &newhdr->left; 204 right_hook = &newhdr->right; 205 206 while (x != NIL) { 207 /* 208 * Remark: 209 * The name 'left_hook' is somewhat confusing, since 210 * it is always set to the address of a .right link 211 * field. However, its value is always an address 212 * below (i.e., to the left of) newblk. Similarly 213 * for right_hook. The values of left_hook and 214 * right_hook converge toward the value of newblk, 215 * as in a classical binary search. 216 */ 217 if (x->block < newblk) { 218 /* 219 * rewrite link crossing from the left 220 */ 221 *left_hook = x; 222 left_hook = &x->right; 223 x = x->right; 224 } else { 225 /* 226 * rewrite link crossing from the right 227 */ 228 *right_hook = x; 229 right_hook = &x->left; 230 x = x->left; 231 } /*else*/ 232 } /*while*/ 233 234 *left_hook = *right_hook = NIL; /* clear remaining hooks */ 235 236 } /*insert*/ 237 238 239 /* 240 * delete(p) 241 * deletes a node from a cartesian tree. p is the address of 242 * a pointer to the node which is to be deleted. 243 * 244 * algorithm: 245 * The left and right branches of the node to be deleted define two 246 * subtrees which are to be merged and attached in place of the 247 * deleted node. Each node on the inside edges of these two 248 * subtrees is examined and longer nodes are placed above the 249 * shorter ones. 250 * 251 * On entry: 252 * *p is assumed to be non-null. 253 */ 254 static 255 delete(p) 256 register Freehdr *p; 257 { 258 register Freehdr x; 259 register Freehdr left_branch; /* left subtree of deleted node */ 260 register Freehdr right_branch; /* right subtree of deleted node */ 261 register uint left_weight; 262 register uint right_weight; 263 264 x = *p; 265 left_branch = x->left; 266 left_weight = weight(left_branch); 267 right_branch = x->right; 268 right_weight = weight(right_branch); 269 270 while (left_branch != right_branch) { 271 /* 272 * iterate until left branch and right branch are 273 * both NIL. 274 */ 275 if ( left_weight >= right_weight ) { 276 /* 277 * promote the left branch 278 */ 279 if (left_branch != NIL) { 280 if (left_weight == 0) { 281 /* zero-length block */ 282 error("blocksize=0 at %#x\n", 283 (int)left_branch->block->data); 284 break; 285 } 286 *p = left_branch; 287 p = &left_branch->right; 288 left_branch = *p; 289 left_weight = weight(left_branch); 290 } 291 } else { 292 /* 293 * promote the right branch 294 */ 295 if (right_branch != NIL) { 296 if (right_weight == 0) { 297 /* zero-length block */ 298 error("blocksize=0 at %#x\n", 299 (int)right_branch->block->data); 300 break; 301 } 302 *p = right_branch; 303 p = &right_branch->left; 304 right_branch = *p; 305 right_weight = weight(right_branch); 306 } 307 }/*else*/ 308 }/*while*/ 309 *p = NIL; 310 putfreehdr(x); 311 } /*delete*/ 312 313 314 /* 315 * demote(p) 316 * Demotes a node in a cartesian tree, if necessary, to establish 317 * the required vertical ordering. 318 * 319 * algorithm: 320 * The left and right subtrees of the node to be demoted are to 321 * be partially merged and attached in place of the demoted node. 322 * The nodes on the inside edges of these two subtrees are 323 * examined and the longer nodes are placed above the shorter 324 * ones, until a node is reached which has a length no greater 325 * than that of the node being demoted (or until a null pointer 326 * is reached). The node is then attached at this point, and 327 * the remaining subtrees (if any) become its descendants. 328 * 329 * on entry: 330 * a. All the nodes in the tree, including the one to be demoted, 331 * must be correctly ordered horizontally; 332 * b. All the nodes except the one to be demoted must also be 333 * correctly positioned vertically. The node to be demoted 334 * may be already correctly positioned vertically, or it may 335 * have a length which is less than that of one or both of 336 * its progeny. 337 * c. *p is non-null 338 */ 339 340 static 341 demote(p) 342 register Freehdr *p; 343 { 344 register Freehdr x; /* addr of node to be demoted */ 345 register Freehdr left_branch; 346 register Freehdr right_branch; 347 register uint left_weight; 348 register uint right_weight; 349 register uint x_weight; 350 351 x = *p; 352 x_weight = weight(x); 353 left_branch = x->left; 354 right_branch = x->right; 355 left_weight = weight(left_branch); 356 right_weight = weight(right_branch); 357 358 while (left_weight > x_weight || right_weight > x_weight) { 359 /* 360 * select a descendant branch for promotion 361 */ 362 if (left_weight >= right_weight) { 363 /* 364 * promote the left branch 365 */ 366 *p = left_branch; 367 p = &left_branch->right; 368 left_branch = *p; 369 left_weight = weight(left_branch); 370 } else { 371 /* 372 * promote the right branch 373 */ 374 *p = right_branch; 375 p = &right_branch->left; 376 right_branch = *p; 377 right_weight = weight(right_branch); 378 } /*else*/ 379 } /*while*/ 380 381 *p = x; /* attach demoted node here */ 382 x->left = left_branch; 383 x->right = right_branch; 384 385 } /*demote*/ 386 387 388 /* 389 * char* 390 * malloc(nbytes) 391 * Allocates a block of length specified in bytes. If nbytes is 392 * zero, a valid pointer (that should not be dereferenced) is returned. 393 * 394 * algorithm: 395 * The freelist is searched by descending the tree from the root 396 * so that at each decision point the "better fitting" branch node 397 * is chosen (i.e., the shorter one, if it is long enough, or 398 * the longer one, otherwise). The descent stops when both 399 * branch nodes are too short. 400 * 401 * function result: 402 * Malloc returns a pointer to the allocated block. A null 403 * pointer indicates an error. 404 * 405 * diagnostics: 406 * 407 * ENOMEM: storage could not be allocated. 408 * 409 * EINVAL: either the argument was invalid, or the heap was found 410 * to be in an inconsistent state. More detailed information may 411 * be obtained by enabling range checks (cf., malloc_debug()). 412 * 413 * Note: In this implementation, each allocated block includes a 414 * length word, which occurs before the address seen by the caller. 415 * Allocation requests are rounded up to a multiple of wordsize. 416 */ 417 418 ptr_t 419 malloc(nbytes) 420 register uint nbytes; 421 { 422 register Freehdr allocp; /* ptr to node to be allocated */ 423 register Freehdr *fpp; /* for tree modifications */ 424 register Freehdr left_branch; 425 register Freehdr right_branch; 426 register uint left_weight; 427 register uint right_weight; 428 Dblk retblk; /* block returned to the user */ 429 430 /* 431 * if rigorous checking was requested, do it. 432 */ 433 if (debug_level >= 2) { 434 malloc_verify(); 435 } 436 437 /* 438 * add the size of a length word to the request, and 439 * guarantee at least one word of usable data. 440 */ 441 nbytes += ALIGNSIZ; 442 if (nbytes < SMALLEST_BLK) { 443 nbytes = SMALLEST_BLK; 444 } else { 445 nbytes = roundup(nbytes, ALIGNSIZ); 446 } 447 448 /* 449 * ensure that at least one block is big enough to satisfy 450 * the request. 451 */ 452 453 if (weight(_root) < nbytes) { 454 /* 455 * the largest block is not enough. 456 */ 457 if(!morecore(nbytes)) 458 return 0; 459 } 460 461 /* 462 * search down through the tree until a suitable block is 463 * found. At each decision point, select the better 464 * fitting node. 465 */ 466 467 fpp = &_root; 468 allocp = *fpp; 469 left_branch = allocp->left; 470 right_branch = allocp->right; 471 left_weight = weight(left_branch); 472 right_weight = weight(right_branch); 473 474 while (left_weight >= nbytes || right_weight >= nbytes) { 475 if (left_weight <= right_weight) { 476 if (left_weight >= nbytes) { 477 fpp = &allocp->left; 478 allocp = left_branch; 479 } else { 480 fpp = &allocp->right; 481 allocp = right_branch; 482 } 483 } else { 484 if (right_weight >= nbytes) { 485 fpp = &allocp->right; 486 allocp = right_branch; 487 } else { 488 fpp = &allocp->left; 489 allocp = left_branch; 490 } 491 } 492 left_branch = allocp->left; 493 right_branch = allocp->right; 494 left_weight = weight(left_branch); 495 right_weight = weight(right_branch); 496 } /*while*/ 497 498 /* 499 * allocate storage from the selected node. 500 */ 501 502 if (allocp->size - nbytes <= SMALLEST_BLK) { 503 /* 504 * not big enough to split; must leave at least 505 * a dblk's worth of space. 506 */ 507 retblk = allocp->block; 508 delete(fpp); 509 } else { 510 511 /* 512 * Split the selected block n bytes from the top. The 513 * n bytes at the top are returned to the caller; the 514 * remainder of the block goes back to free space. 515 */ 516 register Dblk nblk; 517 518 retblk = allocp->block; 519 nblk = nextblk(retblk, nbytes); /* ^next block */ 520 nblk->size = allocp->size = retblk->size - nbytes; 521 __mallinfo.ordblks++; /* count fragments */ 522 523 /* 524 * Change the selected node to point at the newly split 525 * block, and move the node to its proper place in 526 * the free space list. 527 */ 528 allocp->block = nblk; 529 demote(fpp); 530 531 /* 532 * set the length field of the allocated block; we need 533 * this because free() does not specify a length. 534 */ 535 retblk->size = nbytes; 536 } 537 /* maintain statistics */ 538 __mallinfo.uordbytes += retblk->size; /* bytes allocated */ 539 __mallinfo.allocated++; /* frags allocated */ 540 if (nbytes < __mallinfo.mxfast) 541 __mallinfo.smblks++; /* kludge to pass the SVVS */ 542 543 return((ptr_t)retblk->data); 544 545 } /*malloc*/ 546 547 /* 548 * free(p) 549 * return a block to the free space tree. 550 * 551 * algorithm: 552 * Starting at the root, search for and coalesce free blocks 553 * adjacent to one given. When the appropriate place in the 554 * tree is found, insert the given block. 555 * 556 * Some sanity checks to avoid total confusion in the tree. 557 * If the block has already been freed, return. 558 * If the ptr is not from the sbrk'ed space, return. 559 * If the block size is invalid, return. 560 */ 561 free_t 562 free(ptr) 563 ptr_t ptr; 564 { 565 register uint nbytes; /* Size of node to be released */ 566 register Freehdr *fpp; /* For deletion from free list */ 567 register Freehdr neighbor; /* Node to be coalesced */ 568 register Dblk neighbor_blk; /* Ptr to potential neighbor */ 569 register uint neighbor_size; /* Size of potential neighbor */ 570 register Dblk oldblk; /* Ptr to block to be freed */ 571 572 /* 573 * if rigorous checking was requested, do it. 574 */ 575 if (debug_level >= 2) { 576 malloc_verify(); 577 } 578 579 /* 580 * Check the address of the old block. 581 */ 582 if ( misaligned(ptr) ) { 583 error("free: illegal address (%#x)\n", ptr); 584 free_return(0); 585 } 586 587 /* 588 * Freeing something that wasn't allocated isn't 589 * exactly kosher, but fclose() does it routinely. 590 */ 591 if( ptr < (ptr_t)_lbound || ptr > (ptr_t)_ubound ) { 592 errno = EINVAL; 593 free_return(0); 594 } 595 596 /* 597 * Get node length by backing up by the size of a header. 598 * Check for a valid length. It must be a positive 599 * multiple of ALIGNSIZ, at least as large as SMALLEST_BLK, 600 * no larger than the extent of the heap, and must not 601 * extend beyond the end of the heap. 602 */ 603 oldblk = (Dblk)((char*)ptr - ALIGNSIZ); 604 nbytes = oldblk->size; 605 if (badblksize(oldblk,nbytes)) { 606 error("free: bad block size (%d) at %#x\n", 607 (int)nbytes, (int)oldblk ); 608 free_return(0); 609 } 610 611 /* maintain statistics */ 612 __mallinfo.uordbytes -= nbytes; /* bytes allocated */ 613 __mallinfo.allocated--; /* frags allocated */ 614 615 /* 616 * Search the tree for the correct insertion point for this 617 * node, coalescing adjacent free blocks along the way. 618 */ 619 fpp = &_root; 620 neighbor = *fpp; 621 while (neighbor != NIL) { 622 neighbor_blk = neighbor->block; 623 neighbor_size = neighbor->size; 624 if (oldblk < neighbor_blk) { 625 Dblk nblk = nextblk(oldblk,nbytes); 626 if (nblk == neighbor_blk) { 627 /* 628 * Absorb and delete right neighbor 629 */ 630 nbytes += neighbor_size; 631 __mallinfo.ordblks--; 632 delete(fpp); 633 } else if (nblk > neighbor_blk) { 634 /* 635 * The block being freed overlaps 636 * another block in the tree. This 637 * is bad news. Return to avoid 638 * further fouling up the the tree. 639 */ 640 error("free: blocks %#x, %#x overlap\n", 641 (int)oldblk, (int)neighbor_blk); 642 free_return(0); 643 } else { 644 /* 645 * Search to the left 646 */ 647 fpp = &neighbor->left; 648 } 649 } else if (oldblk > neighbor_blk) { 650 Dblk nblk = nextblk(neighbor_blk, neighbor_size); 651 if (nblk == oldblk) { 652 /* 653 * Absorb and delete left neighbor 654 */ 655 oldblk = neighbor_blk; 656 nbytes += neighbor_size; 657 __mallinfo.ordblks--; 658 delete(fpp); 659 } else if (nblk > oldblk) { 660 /* 661 * This block has already been freed 662 */ 663 error("free: block %#x was already free\n", 664 (int)ptr); 665 free_return(0); 666 } else { 667 /* 668 * search to the right 669 */ 670 fpp = &neighbor->right; 671 } 672 } else { 673 /* 674 * This block has already been freed 675 * as "oldblk == neighbor_blk" 676 */ 677 error("free: block %#x was already free\n", (int)ptr); 678 free_return(0); 679 } /*else*/ 680 681 /* 682 * Note that this depends on a side effect of 683 * delete(fpp) in order to terminate the loop! 684 */ 685 neighbor = *fpp; 686 687 } /*while*/ 688 689 /* 690 * Insert the new node into the free space tree 691 */ 692 insert( oldblk, nbytes ); 693 free_return(1); 694 695 } /*free*/ 696 697 698 /* 699 * char* 700 * shrink(oldblk, oldsize, newsize) 701 * Decreases the size of an old block to a new size. 702 * Returns the remainder to free space. Returns the 703 * truncated block to the caller. 704 */ 705 706 static char * 707 shrink(oldblk, oldsize, newsize) 708 register Dblk oldblk; 709 register uint oldsize, newsize; 710 { 711 register Dblk remainder; 712 if (oldsize - newsize >= SMALLEST_BLK) { 713 /* 714 * Block is to be contracted. Split the old block 715 * and return the remainder to free space. 716 */ 717 remainder = nextblk(oldblk, newsize); 718 remainder->size = oldsize - newsize; 719 oldblk->size = newsize; 720 721 /* maintain statistics */ 722 __mallinfo.ordblks++; /* count fragments */ 723 __mallinfo.allocated++; /* negate effect of free() */ 724 725 free(remainder->data); 726 } 727 return(oldblk->data); 728 } 729 730 731 /* 732 * char* 733 * realloc(ptr, nbytes) 734 * 735 * Reallocate an old block with a new size, returning the old block 736 * if possible. The block returned is guaranteed to preserve the 737 * contents of the old block up to min(size(old block), newsize). 738 * 739 * For backwards compatibility, ptr is allowed to reference 740 * a block freed since the LAST call of malloc(). Thus the old 741 * block may be busy, free, or may even be nested within a free 742 * block. 743 * 744 * Some old programs have been known to do things like the following, 745 * which is guaranteed not to work: 746 * 747 * free(ptr); 748 * free(dummy); 749 * dummy = malloc(1); 750 * ptr = realloc(ptr,nbytes); 751 * 752 * This atrocity was found in the source for diff(1). 753 */ 754 ptr_t 755 realloc(ptr, nbytes) 756 ptr_t ptr; 757 uint nbytes; 758 { 759 register Freehdr *fpp; 760 register Freehdr fp; 761 register Dblk oldblk; 762 register Dblk freeblk; 763 register Dblk oldneighbor; 764 register uint oldsize; 765 register uint newsize; 766 register uint oldneighborsize; 767 768 /* 769 * Add SVR4 semantics for OS 5.x so /usr/lib librarys 770 * work correctly when running in BCP mode 771 */ 772 if (ptr == NULL) { 773 return (malloc(nbytes)); 774 } 775 776 /* 777 * if rigorous checking was requested, do it. 778 */ 779 if (debug_level >= 2) { 780 malloc_verify(); 781 } 782 783 /* 784 * Check the address of the old block. 785 */ 786 if ( misaligned(ptr) || 787 ptr < (ptr_t)_lbound || 788 ptr > (ptr_t)_ubound ) { 789 error("realloc: illegal address (%#x)\n", ptr); 790 return(NULL); 791 } 792 793 /* 794 * check location and size of the old block and its 795 * neighboring block to the right. If the old block is 796 * at end of memory, the neighboring block is undefined. 797 */ 798 oldblk = (Dblk)((char*)ptr - ALIGNSIZ); 799 oldsize = oldblk->size; 800 if (badblksize(oldblk,oldsize)) { 801 error("realloc: bad block size (%d) at %#x\n", 802 oldsize, oldblk); 803 return(NULL); 804 } 805 oldneighbor = nextblk(oldblk,oldsize); 806 807 /* *** tree search code pulled into separate subroutine *** */ 808 if (reclaim(oldblk, oldsize, 1) == -1) { 809 return(NULL); /* internal error */ 810 } 811 812 /* 813 * At this point, we can guarantee that oldblk is out of free 814 * space. What we do next depends on a comparison of the size 815 * of the old block and the requested new block size. To do 816 * this, first round up the new size request. 817 */ 818 newsize = nbytes + ALIGNSIZ; /* add size of a length word */ 819 if (newsize < SMALLEST_BLK) { 820 newsize = SMALLEST_BLK; 821 } else { 822 newsize = roundup(newsize, ALIGNSIZ); 823 } 824 825 /* 826 * Next, examine the size of the old block, and compare it 827 * with the requested new size. 828 */ 829 830 if (oldsize >= newsize) { 831 /* 832 * Block is to be made smaller. 833 */ 834 return(shrink(oldblk, oldsize, newsize)); 835 } 836 837 /* 838 * Block is to be expanded. Look for adjacent free memory. 839 */ 840 if ( oldneighbor < (Dblk)_ubound ) { 841 /* 842 * Search for the adjacent block in the free 843 * space tree. Note that the tree may have been 844 * modified in the earlier loop. 845 */ 846 fpp = &_root; 847 fp = *fpp; 848 oldneighborsize = oldneighbor->size; 849 if ( badblksize(oldneighbor, oldneighborsize) ) { 850 error("realloc: bad blocksize(%d) at %#x\n", 851 oldneighborsize, oldneighbor); 852 return(NULL); 853 } 854 while ( weight(fp) >= oldneighborsize ) { 855 freeblk = fp->block; 856 if (oldneighbor < freeblk) { 857 /* 858 * search to the left 859 */ 860 fpp = &(fp->left); 861 fp = *fpp; 862 } 863 else if (oldneighbor > freeblk) { 864 /* 865 * search to the right 866 */ 867 fpp = &(fp->right); 868 fp = *fpp; 869 } 870 else { /* oldneighbor == freeblk */ 871 /* 872 * neighboring block is free; is it big enough? 873 */ 874 if (oldsize + oldneighborsize >= newsize) { 875 /* 876 * Big enough. Delete freeblk, join 877 * oldblk to neighbor, return newsize 878 * bytes to the caller, and return the 879 * remainder to free storage. 880 */ 881 delete(fpp); 882 883 /* maintain statistics */ 884 __mallinfo.ordblks--; 885 __mallinfo.uordbytes += oldneighborsize; 886 887 oldsize += oldneighborsize; 888 oldblk->size = oldsize; 889 return(shrink(oldblk, oldsize, newsize)); 890 } else { 891 /* 892 * Not big enough. Stop looking for a 893 * free lunch. 894 */ 895 break; 896 } /*else*/ 897 } /*else*/ 898 }/*while*/ 899 } /*if*/ 900 901 /* 902 * At this point, we know there is no free space in which to 903 * expand. Malloc a new block, copy the old block to the new, 904 * and free the old block, IN THAT ORDER. 905 */ 906 ptr = malloc(nbytes); 907 if (ptr != NULL) { 908 bcopy(oldblk->data, ptr, oldsize-ALIGNSIZ); 909 free(oldblk->data); 910 } 911 return(ptr); 912 913 } /* realloc */ 914 915 916 /* 917 * *** The following code was pulled out of realloc() *** 918 * 919 * int 920 * reclaim(oldblk, oldsize, flag) 921 * If a block containing 'oldsize' bytes from 'oldblk' 922 * is in the free list, remove it from the free list. 923 * 'oldblk' and 'oldsize' are assumed to include the free block header. 924 * 925 * Returns 1 if block was successfully removed. 926 * Returns 0 if block was not in free list. 927 * Returns -1 if block spans a free/allocated boundary (error() called 928 * if 'flag' == 1). 929 */ 930 static int 931 reclaim(oldblk, oldsize, flag) 932 register Dblk oldblk; 933 uint oldsize; 934 int flag; 935 { 936 register Dblk oldneighbor; 937 register Freehdr *fpp; 938 register Freehdr fp; 939 register Dblk freeblk; 940 register uint size; 941 942 /* 943 * Search the free space list for a node describing oldblk, 944 * or a node describing a block containing oldblk. Assuming 945 * the size of blocks decreases monotonically with depth in 946 * the tree, the loop may terminate as soon as a block smaller 947 * than oldblk is encountered. 948 */ 949 950 oldneighbor = nextblk(oldblk, oldsize); 951 952 fpp = &_root; 953 fp = *fpp; 954 while ( (size = weight(fp)) >= oldsize ) { 955 freeblk = fp->block; 956 if (badblksize(freeblk,size)) { 957 error("realloc: bad block size (%d) at %#x\n", 958 size, freeblk); 959 return(-1); 960 } 961 if ( oldblk == freeblk ) { 962 /* 963 * |<-- freeblk ... 964 * _________________________________ 965 * |<-- oldblk ... 966 * --------------------------------- 967 * Found oldblk in the free space tree; delete it. 968 */ 969 delete(fpp); 970 971 /* maintain statistics */ 972 __mallinfo.uordbytes += oldsize; 973 __mallinfo.allocated++; 974 return(1); 975 } 976 else if (oldblk < freeblk) { 977 /* 978 * |<-- freeblk ... 979 * _________________________________ 980 * |<--oldblk ... 981 * --------------------------------- 982 * Search to the left for oldblk 983 */ 984 fpp = &fp->left; 985 fp = *fpp; 986 } 987 else { 988 /* 989 * |<-- freeblk ... 990 * _________________________________ 991 * | |<--oldblk--->|<--oldneighbor 992 * --------------------------------- 993 * oldblk is somewhere to the right of freeblk. 994 * Check to see if it lies within freeblk. 995 */ 996 register Dblk freeneighbor; 997 freeneighbor = nextblk(freeblk, freeblk->size); 998 if (oldblk >= freeneighbor) { 999 /* 1000 * |<-- freeblk--->|<--- freeneighbor ... 1001 * _________________________________ 1002 * | |<--oldblk--->| 1003 * --------------------------------- 1004 * no such luck; search to the right. 1005 */ 1006 fpp = &fp->right; 1007 fp = *fpp; 1008 } 1009 else { 1010 /* 1011 * freeblk < oldblk < freeneighbor; 1012 * i.e., oldblk begins within freeblk. 1013 */ 1014 if (oldneighbor > freeneighbor) { 1015 /* 1016 * |<-- freeblk--->|<--- freeneighbor 1017 * _________________________________ 1018 * | |<--oldblk--->|<--oldneighbor 1019 * --------------------------------- 1020 * oldblk straddles a block boundary! 1021 */ 1022 if (flag) { 1023 error("realloc: block %#x straddles free block boundary\n", oldblk); 1024 } 1025 return(-1); 1026 } 1027 else if ( oldneighbor == freeneighbor ) { 1028 /* 1029 * |<-------- freeblk------------->| 1030 * _________________________________ 1031 * | |<--oldblk--->| 1032 * --------------------------------- 1033 * Oldblk is on the right end of 1034 * freeblk. Delete freeblk, split 1035 * into two fragments, and return 1036 * the one on the left to free space. 1037 */ 1038 delete(fpp); 1039 1040 /* maintain statistics */ 1041 __mallinfo.ordblks++; 1042 __mallinfo.uordbytes += oldsize; 1043 __mallinfo.allocated += 2; 1044 1045 freeblk->size -= oldsize; 1046 free(freeblk->data); 1047 return(1); 1048 } 1049 else { 1050 /* 1051 * |<-------- freeblk------------->| 1052 * _________________________________ 1053 * | |oldblk | oldneighbor | 1054 * --------------------------------- 1055 * Oldblk is in the middle of freeblk. 1056 * Delete freeblk, split into three 1057 * fragments, and return the ones on 1058 * the ends to free space. 1059 */ 1060 delete(fpp); 1061 1062 /* maintain statistics */ 1063 __mallinfo.ordblks += 2; 1064 __mallinfo.uordbytes += freeblk->size; 1065 __mallinfo.allocated += 3; 1066 1067 /* 1068 * split the left fragment by 1069 * subtracting the size of oldblk 1070 * and oldblk's neighbor 1071 */ 1072 freeblk->size -= 1073 ( (char*)freeneighbor 1074 - (char*)oldblk ); 1075 /* 1076 * split the right fragment by 1077 * setting oldblk's neighbor's size 1078 */ 1079 oldneighbor->size = 1080 (char*)freeneighbor 1081 - (char*)oldneighbor; 1082 /* 1083 * return the fragments to free space 1084 */ 1085 free(freeblk->data); 1086 free(oldneighbor->data); 1087 return(1); 1088 } /*else*/ 1089 } /*else*/ 1090 } /* else */ 1091 } /*while*/ 1092 1093 return(0); /* free block not found */ 1094 } 1095 1096 /* 1097 * bool 1098 * morecore(nbytes) 1099 * Add a block of at least nbytes from end-of-memory to the 1100 * free space tree. 1101 * 1102 * return value: 1103 * true if at least n bytes can be allocated 1104 * false otherwise 1105 * 1106 * remarks: 1107 * 1108 * -- free space (delimited by the extern variable _ubound) is 1109 * extended by an amount determined by rounding nbytes up to 1110 * a multiple of the system page size. 1111 * 1112 * -- The lower bound of the heap is determined the first time 1113 * this routine is entered. It does NOT necessarily begin at 1114 * the end of static data space, since startup code (e.g., for 1115 * profiling) may have invoked sbrk() before we got here. 1116 */ 1117 1118 static bool 1119 morecore(nbytes) 1120 uint nbytes; 1121 { 1122 Dblk p; 1123 Freehdr newhdr; 1124 1125 if (nbpg == 0) { 1126 nbpg = getpagesize(); 1127 /* hack to avoid fragmenting the heap with the first 1128 freehdr page */ 1129 if ((newhdr = getfreehdr()) == NIL) { 1130 /* Error message returned by getfreehdr() */ 1131 return(false); 1132 } 1133 (void)putfreehdr(newhdr); 1134 } 1135 nbytes = roundup(nbytes, nbpg); 1136 p = (Dblk) sbrk((int)nbytes); 1137 if (p == (Dblk) -1) { 1138 if (errno == EAGAIN) errno = ENOMEM; 1139 return(false); /* errno = ENOMEM */ 1140 } 1141 if (_lbound == NULL) /* set _lbound the first time through */ 1142 _lbound = (char*) p; 1143 _ubound = (char *) p + nbytes; 1144 p->size = nbytes; 1145 1146 /* maintain statistics */ 1147 __mallinfo.arena = _ubound - _lbound; 1148 __mallinfo.uordbytes += nbytes; 1149 __mallinfo.ordblks++; 1150 __mallinfo.allocated++; 1151 1152 free(p->data); 1153 return(true); 1154 1155 } /*morecore*/ 1156 1157 1158 /* 1159 * Get a free block header from the free header list. 1160 * When the list is empty, allocate an array of headers. 1161 * When the array is empty, allocate another one. 1162 * When we can't allocate another array, we're in deep weeds. 1163 */ 1164 static Freehdr 1165 getfreehdr() 1166 { 1167 Freehdr r; 1168 register Dblk blk; 1169 register uint size; 1170 1171 if (freehdrlist != NIL) { 1172 r = freehdrlist; 1173 freehdrlist = freehdrlist->left; 1174 return(r); 1175 } 1176 if (nfreehdrs <= 0) { 1177 size = NFREE_HDRS*sizeof(struct freehdr) + ALIGNSIZ; 1178 blk = (Dblk) sbrk(size); 1179 if ((int)blk == -1) { 1180 malloc_debug(1); 1181 error("getfreehdr: out of memory"); 1182 if (errno == EAGAIN) errno = ENOMEM; 1183 return(NIL); 1184 } 1185 if (_lbound == NULL) /* set _lbound on first allocation */ 1186 _lbound = (char*)blk; 1187 blk->size = size; 1188 freehdrptr = (Freehdr)blk->data; 1189 nfreehdrs = NFREE_HDRS; 1190 _ubound = (char*) nextblk(blk,size); 1191 1192 /* maintain statistics */ 1193 __mallinfo.arena = _ubound - _lbound; 1194 __mallinfo.treeoverhead += size; 1195 } 1196 nfreehdrs--; 1197 return(freehdrptr++); 1198 } 1199 1200 /* 1201 * Free a free block header 1202 * Add it to the list of available headers. 1203 */ 1204 static 1205 putfreehdr(p) 1206 Freehdr p; 1207 { 1208 p->left = freehdrlist; 1209 freehdrlist = p; 1210 } 1211 1212 1213 #ifndef DEBUG /* >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> */ 1214 1215 /* 1216 * stubs for error handling and diagnosis routines. These are what 1217 * you get in the standard C library; for non-placebo diagnostics 1218 * load /usr/lib/malloc.debug.o with your program. 1219 */ 1220 /*ARGSUSED*/ 1221 static 1222 error(fmt, arg1, arg2, arg3) 1223 char *fmt; 1224 int arg1, arg2, arg3; 1225 { 1226 errno = EINVAL; 1227 } 1228 1229 #endif !DEBUG <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<< 1230 1231 1232 #ifdef DEBUG /* >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> */ 1233 1234 /* 1235 * malloc_debug(level) 1236 * 1237 * description: 1238 * 1239 * Controls the level of error diagnosis and consistency checking 1240 * done by malloc() and free(). level is interpreted as follows: 1241 * 1242 * 0: malloc() and free() return 0 if error detected in arguments 1243 * (errno is set to EINVAL) 1244 * 1: malloc() and free() abort if errors detected in arguments 1245 * 2: same as 1, but scan entire heap for errors on every call 1246 * to malloc() or free() 1247 * 1248 * function result: 1249 * returns the previous level of error reporting. 1250 */ 1251 int 1252 malloc_debug(level) 1253 int level; 1254 { 1255 int old_level; 1256 old_level = debug_level; 1257 debug_level = level; 1258 return old_level; 1259 } 1260 1261 /* 1262 * check a free space tree pointer. Should be in 1263 * the static free pool or somewhere in the heap. 1264 */ 1265 1266 #define chkblk(p)\ 1267 if ( misaligned(p)\ 1268 || ((Dblk)(p) < (Dblk)_lbound || (Dblk)(p) > (Dblk)_ubound)){\ 1269 blkerror(p);\ 1270 return 0;\ 1271 } 1272 1273 #define chkhdr(p) chkblk(p) 1274 1275 static blkerror(p) 1276 Freehdr p; 1277 { 1278 error("Illegal block address (%#x)\n", (p)); 1279 } 1280 1281 /* 1282 * cartesian(p) 1283 * returns 1 if free space tree p satisfies internal consistency 1284 * checks. 1285 */ 1286 1287 static int 1288 cartesian(p) 1289 register Freehdr p; 1290 { 1291 register Freehdr probe; 1292 register Dblk db,pdb; 1293 1294 if (p == NIL) /* no tree to test */ 1295 return 1; 1296 /* 1297 * check that root has a data block 1298 */ 1299 chkhdr(p); 1300 pdb = p->block; 1301 chkblk(pdb); 1302 1303 /* 1304 * check that the child blocks are no larger than the parent block. 1305 */ 1306 probe = p->left; 1307 if (probe != NIL) { 1308 chkhdr(probe); 1309 db = probe->block; 1310 chkblk(db); 1311 if (probe->size > p->size) /* child larger than parent */ 1312 return 0; 1313 } 1314 probe = p->right; 1315 if (probe != NIL) { 1316 chkhdr(probe); 1317 db = probe->block; 1318 chkblk(db); 1319 if (probe->size > p->size) /* child larger than parent */ 1320 return 0; 1321 } 1322 /* 1323 * test data addresses in the left subtree, 1324 * starting at the left subroot and probing to 1325 * the right. All data addresses must be < p->block. 1326 */ 1327 probe = p->left; 1328 while (probe != NIL) { 1329 chkhdr(probe); 1330 db = probe->block; 1331 chkblk(db); 1332 if ( nextblk(db, probe->size) >= pdb ) /* overlap */ 1333 return 0; 1334 probe = probe->right; 1335 } 1336 /* 1337 * test data addresses in the right subtree, 1338 * starting at the right subroot and probing to 1339 * the left. All addresses must be > nextblk(p->block). 1340 */ 1341 pdb = nextblk(pdb, p->size); 1342 probe = p->right; 1343 while (probe != NIL) { 1344 chkhdr(probe); 1345 db = probe->block; 1346 chkblk(db); 1347 if (db == NULL || db <= pdb) /* overlap */ 1348 return 0; 1349 probe = probe->left; 1350 } 1351 return (cartesian(p->left) && cartesian(p->right)); 1352 } 1353 1354 /* 1355 * malloc_verify() 1356 * 1357 * This is a verification routine. It walks through all blocks 1358 * in the heap (both free and busy) and checks for bad blocks. 1359 * malloc_verify returns 1 if the heap contains no detectably bad 1360 * blocks; otherwise it returns 0. 1361 */ 1362 1363 int 1364 malloc_verify() 1365 { 1366 register int maxsize; 1367 register int hdrsize; 1368 register int size; 1369 register Dblk p; 1370 uint lb,ub; 1371 1372 extern char end[]; 1373 1374 if (_lbound == NULL) /* no allocation yet */ 1375 return 1; 1376 1377 /* 1378 * first check heap bounds pointers 1379 */ 1380 lb = (uint)end; 1381 ub = (uint)sbrk(0); 1382 1383 if ((uint)_lbound < lb || (uint)_lbound > ub) { 1384 error("malloc_verify: illegal heap lower bound (%#x)\n", 1385 _lbound); 1386 return 0; 1387 } 1388 if ((uint)_ubound < lb || (uint)_ubound > ub) { 1389 error("malloc_verify: illegal heap upper bound (%#x)\n", 1390 _ubound); 1391 return 0; 1392 } 1393 maxsize = heapsize(); 1394 p = (Dblk)_lbound; 1395 while (p < (Dblk) _ubound) { 1396 size = p->size; 1397 if ( (size) < SMALLEST_BLK 1398 || (size) & (ALIGNSIZ-1) 1399 || (size) > heapsize() 1400 || ((char*)(p))+(size) > _ubound ) { 1401 error("malloc_verify: bad block size (%d) at %#x\n", 1402 size, p); 1403 return(0); /* Badness */ 1404 } 1405 p = nextblk(p, size); 1406 } 1407 if (p > (Dblk) _ubound) { 1408 error("malloc_verify: heap corrupted\n"); 1409 return(0); 1410 } 1411 if (!cartesian(_root)){ 1412 error("malloc_verify: free space tree corrupted\n"); 1413 return(0); 1414 } 1415 return(1); 1416 } 1417 1418 /* 1419 * The following is a kludge to avoid dependency on stdio, which 1420 * uses malloc() and free(), one of which probably got us here in 1421 * the first place. 1422 */ 1423 1424 #define putchar(c) (*buf++ = (c)) 1425 extern int fileno(); /*bletch*/ 1426 #define stderr 2 /*bletch*/ 1427 #define LBUFSIZ 256 1428 1429 static char stderrbuf[LBUFSIZ]; 1430 1431 /*VARARGS2*/ 1432 static 1433 sprintf( string, fmt, x1, x2, x3 ) 1434 char *string; 1435 register char *fmt; 1436 uint x1,x2,x3; 1437 { 1438 register char *buf = string; 1439 uint *argp = &x1; 1440 register char c; 1441 1442 while ( c = *fmt++ ) { 1443 if (c != '%') { 1444 putchar(c); 1445 } else { 1446 /* 1447 * print formatted argument 1448 */ 1449 register uint x; 1450 unsigned short radix; 1451 char prbuf[12]; 1452 register char *cp; 1453 1454 x = *argp++; 1455 1456 switch( c = *fmt++ ) { 1457 case 'd': 1458 radix = 10; 1459 if ((int)x < 0) { 1460 putchar('-'); 1461 x = (unsigned)(-(int)x); 1462 } 1463 break; 1464 case '#': 1465 c = *fmt++; 1466 if (c == 'x') { 1467 putchar('0'); 1468 putchar(c); 1469 } 1470 /*FALL THROUGH*/ 1471 case 'x': 1472 radix = 16; 1473 break; 1474 default: 1475 putchar(c); 1476 continue; 1477 } /*switch*/ 1478 1479 cp = prbuf; 1480 do { 1481 *cp++ = "0123456789abcdef"[x%radix]; 1482 x /= radix; 1483 } while(x); 1484 do { 1485 putchar(*--cp); 1486 } while(cp > prbuf); 1487 }/*if*/ 1488 } /*while*/ 1489 1490 putchar('\0'); 1491 return(buf - string); 1492 1493 } /*sprintf*/ 1494 1495 /* 1496 * Error routine. 1497 * If debug_level == 0, does nothing except set errno = EINVAL. 1498 * Otherwise, prints an error message to stderr and generates a 1499 * core image. 1500 */ 1501 1502 /*VARARGS1*/ 1503 static 1504 error(fmt, arg1, arg2, arg3) 1505 char *fmt; 1506 int arg1, arg2, arg3; 1507 { 1508 static n = 0; /* prevents infinite recursion when using stdio */ 1509 register int nbytes; 1510 1511 errno = EINVAL; 1512 if (debug_level == 0) 1513 return; 1514 if (!n++) { 1515 nbytes = sprintf(stderrbuf, fmt, arg1, arg2, arg3); 1516 stderrbuf[nbytes++] = '\n'; 1517 stderrbuf[nbytes] = '\0'; 1518 write(fileno(stderr), stderrbuf, nbytes); 1519 } 1520 abort(); 1521 } 1522 1523 #endif DEBUG <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<< 1524