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