1 0 stevel /* 2 0 stevel * CDDL HEADER START 3 0 stevel * 4 0 stevel * The contents of this file are subject to the terms of the 5 2658 raf * Common Development and Distribution License (the "License"). 6 2658 raf * You may not use this file except in compliance with the License. 7 0 stevel * 8 0 stevel * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE 9 0 stevel * or http://www.opensolaris.org/os/licensing. 10 0 stevel * See the License for the specific language governing permissions 11 0 stevel * and limitations under the License. 12 0 stevel * 13 0 stevel * When distributing Covered Code, include this CDDL HEADER in each 14 0 stevel * file and include the License file at usr/src/OPENSOLARIS.LICENSE. 15 0 stevel * If applicable, add the following below this CDDL HEADER, with the 16 0 stevel * fields enclosed by brackets "[]" replaced with your own identifying 17 0 stevel * information: Portions Copyright [yyyy] [name of copyright owner] 18 0 stevel * 19 0 stevel * CDDL HEADER END 20 0 stevel */ 21 35 craigm 22 0 stevel /* 23 6812 raf * Copyright 2008 Sun Microsystems, Inc. All rights reserved. 24 35 craigm * Use is subject to license terms. 25 0 stevel */ 26 0 stevel 27 0 stevel /* Copyright (c) 1988 AT&T */ 28 0 stevel /* All Rights Reserved */ 29 0 stevel 30 35 craigm #pragma ident "%Z%%M% %I% %E% SMI" 31 0 stevel 32 0 stevel /* 33 0 stevel * Memory management: malloc(), realloc(), free(), memalign(). 34 0 stevel * 35 0 stevel * The following #-parameters may be redefined: 36 0 stevel * GETCORE: a function to get more core memory. 37 0 stevel * GETCORE(0) is assumed to return the next available 38 0 stevel * address. Default is 'sbrk'. 39 0 stevel * ERRCORE: the error code as returned by GETCORE. 40 0 stevel * Default is ((char *)(-1)). 41 0 stevel * CORESIZE: a desired unit (measured in bytes) to be used 42 0 stevel * with GETCORE. Default is (1024*ALIGN). 43 0 stevel * 44 0 stevel * This algorithm is based on a best fit strategy with lists of 45 0 stevel * free elts maintained in a self-adjusting binary tree. Each list 46 0 stevel * contains all elts of the same size. The tree is ordered by size. 47 0 stevel * For results on self-adjusting trees, see the paper: 48 0 stevel * Self-Adjusting Binary Trees, 49 0 stevel * DD Sleator & RE Tarjan, JACM 1985. 50 0 stevel * 51 0 stevel * The header of a block contains the size of the data part in bytes. 52 0 stevel * Since the size of a block is 0%4, the low two bits of the header 53 0 stevel * are free and used as follows: 54 0 stevel * 55 0 stevel * BIT0: 1 for busy (block is in use), 0 for free. 56 0 stevel * BIT1: if the block is busy, this bit is 1 if the 57 0 stevel * preceding block in contiguous memory is free. 58 0 stevel * Otherwise, it is always 0. 59 0 stevel */ 60 0 stevel 61 0 stevel #include "mallint.h" 62 0 stevel 63 0 stevel static mutex_t __watch_malloc_lock = DEFAULTMUTEX; 64 0 stevel 65 0 stevel static TREE *Root; /* root of the free tree */ 66 0 stevel static TREE *Bottom; /* the last free chunk in the arena */ 67 0 stevel static char *Baddr; /* current high address of the arena */ 68 0 stevel 69 0 stevel static void t_delete(TREE *); 70 0 stevel static void t_splay(TREE *); 71 0 stevel static void realfree(void *); 72 0 stevel static void *malloc_unlocked(size_t); 73 0 stevel static void free_unlocked(void *); 74 0 stevel static TREE *morecore(size_t); 75 0 stevel 76 0 stevel static void protect(TREE *); 77 0 stevel static void unprotect(TREE *); 78 0 stevel 79 0 stevel #define FREEPAT 0 80 0 stevel #define LIVEPAT 1 81 0 stevel 82 0 stevel /* 83 0 stevel * Patterns to be copied into freed blocks and allocated blocks. 84 0 stevel * 0xfeedbeef and 0xfeedface are invalid pointer values in all programs. 85 0 stevel */ 86 0 stevel static uint64_t patterns[2] = { 87 35 craigm 0xdeadbeefdeadbeefULL, /* pattern in a freed block */ 88 35 craigm 0xbaddcafebaddcafeULL /* pattern in an allocated block */ 89 0 stevel }; 90 0 stevel 91 0 stevel static void 92 0 stevel copy_pattern(int pat, TREE *tp) 93 0 stevel { 94 0 stevel uint64_t pattern = patterns[pat]; 95 0 stevel size_t sz = SIZE(tp) / sizeof (uint64_t); 96 0 stevel /* LINTED improper alignment */ 97 0 stevel uint64_t *datap = (uint64_t *)DATA(tp); 98 0 stevel 99 0 stevel while (sz--) 100 0 stevel *datap++ = pattern; 101 0 stevel } 102 0 stevel 103 0 stevel /* 104 0 stevel * Keep lists of small blocks, LIFO order. 105 0 stevel */ 106 0 stevel static TREE *List[MINSIZE/WORDSIZE-1]; 107 0 stevel static TREE *Last[MINSIZE/WORDSIZE-1]; 108 0 stevel 109 0 stevel /* number of blocks to get at one time */ 110 0 stevel #define NPS (WORDSIZE*8) 111 0 stevel 112 0 stevel static void * 113 0 stevel smalloc(size_t size) 114 0 stevel { 115 0 stevel TREE *tp; 116 0 stevel size_t i; 117 0 stevel 118 0 stevel ASSERT(size % WORDSIZE == 0); 119 0 stevel /* want to return a unique pointer on malloc(0) */ 120 0 stevel if (size == 0) 121 0 stevel size = WORDSIZE; 122 0 stevel 123 0 stevel /* list to use */ 124 0 stevel i = size / WORDSIZE - 1; 125 0 stevel 126 0 stevel if (List[i] == NULL) { 127 0 stevel TREE *np; 128 0 stevel int n; 129 0 stevel ASSERT((size + WORDSIZE) * NPS >= MINSIZE); 130 0 stevel 131 0 stevel /* get NPS of these block types */ 132 0 stevel if ((np = malloc_unlocked((size + WORDSIZE)*NPS)) == NULL) 133 0 stevel return (NULL); 134 0 stevel 135 0 stevel /* make them into a link list */ 136 0 stevel for (n = 0, List[i] = np; n < NPS; ++n) { 137 0 stevel tp = np; 138 0 stevel SIZE(tp) = size; 139 0 stevel copy_pattern(FREEPAT, tp); 140 0 stevel if (n == NPS - 1) { 141 0 stevel Last[i] = tp; 142 0 stevel np = NULL; 143 0 stevel } else { 144 0 stevel /* LINTED improper alignment */ 145 0 stevel np = NEXT(tp); 146 0 stevel } 147 0 stevel AFTER(tp) = np; 148 0 stevel protect(tp); 149 0 stevel } 150 0 stevel } 151 0 stevel 152 0 stevel /* allocate from the head of the queue */ 153 0 stevel tp = List[i]; 154 0 stevel unprotect(tp); 155 0 stevel if ((List[i] = AFTER(tp)) == NULL) 156 0 stevel Last[i] = NULL; 157 0 stevel copy_pattern(LIVEPAT, tp); 158 0 stevel SETBIT0(SIZE(tp)); 159 0 stevel protect(tp); 160 0 stevel return (DATA(tp)); 161 0 stevel } 162 0 stevel 163 0 stevel void * 164 0 stevel malloc(size_t size) 165 0 stevel { 166 0 stevel void *ret; 167 3866 raf (void) mutex_lock(&__watch_malloc_lock); 168 0 stevel ret = malloc_unlocked(size); 169 3866 raf (void) mutex_unlock(&__watch_malloc_lock); 170 0 stevel return (ret); 171 0 stevel } 172 0 stevel 173 0 stevel static void * 174 0 stevel malloc_unlocked(size_t size) 175 0 stevel { 176 0 stevel size_t n; 177 0 stevel TREE *tp, *sp, *tmp; 178 0 stevel 179 0 stevel COUNT(nmalloc); 180 0 stevel ASSERT(WORDSIZE == ALIGN); 181 0 stevel 182 0 stevel /* check for size that could overflow calculations */ 183 0 stevel if (size > MAX_MALLOC) { 184 0 stevel errno = ENOMEM; 185 0 stevel return (NULL); 186 0 stevel } 187 0 stevel /* make sure that size is 0 mod ALIGN */ 188 0 stevel ROUND(size); 189 0 stevel 190 0 stevel /* small blocks */ 191 0 stevel if (size < MINSIZE) 192 0 stevel return (smalloc(size)); 193 0 stevel 194 0 stevel /* search for an elt of the right size */ 195 0 stevel sp = NULL; 196 0 stevel n = 0; 197 0 stevel if (Root) { 198 0 stevel tp = Root; 199 0 stevel for (;;) { 200 0 stevel unprotect(tp); 201 0 stevel if (SIZE(tp) >= size) { /* branch left */ 202 0 stevel if (n == 0 || n >= SIZE(tp)) { 203 0 stevel sp = tp; 204 0 stevel n = SIZE(tp); 205 0 stevel } 206 0 stevel if ((tmp = LEFT(tp)) != NULL) { 207 0 stevel protect(tp); 208 0 stevel tp = tmp; 209 0 stevel } else { 210 0 stevel protect(tp); 211 0 stevel break; 212 0 stevel } 213 0 stevel } else { /* branch right */ 214 0 stevel if ((tmp = RIGHT(tp)) != NULL) { 215 0 stevel protect(tp); 216 0 stevel tp = tmp; 217 0 stevel } else { 218 0 stevel protect(tp); 219 0 stevel break; 220 0 stevel } 221 0 stevel } 222 0 stevel } 223 0 stevel 224 0 stevel if (sp) { 225 0 stevel unprotect(sp); 226 0 stevel t_delete(sp); 227 0 stevel } else if (tp != Root) { 228 0 stevel /* make the searched-to element the root */ 229 0 stevel unprotect(tp); 230 0 stevel t_splay(tp); 231 0 stevel protect(tp); 232 0 stevel Root = tp; 233 0 stevel } 234 0 stevel } 235 0 stevel 236 0 stevel /* if found none fitted in the tree */ 237 0 stevel if (sp == NULL) { 238 0 stevel if (Bottom) { 239 0 stevel unprotect(Bottom); 240 0 stevel if (size <= SIZE(Bottom)) { 241 0 stevel sp = Bottom; 242 0 stevel CLRBITS01(SIZE(sp)); 243 0 stevel } else { 244 0 stevel protect(Bottom); 245 0 stevel if ((sp = morecore(size)) == NULL) 246 0 stevel return (NULL); 247 0 stevel } 248 0 stevel } else { 249 0 stevel if ((sp = morecore(size)) == NULL) 250 0 stevel return (NULL); 251 0 stevel } 252 0 stevel } 253 0 stevel 254 0 stevel /* tell the forward neighbor that we're busy */ 255 0 stevel /* LINTED improper alignment */ 256 0 stevel tmp = NEXT(sp); 257 0 stevel unprotect(tmp); 258 0 stevel CLRBIT1(SIZE(tmp)); 259 0 stevel ASSERT(ISBIT0(SIZE(tmp))); 260 0 stevel protect(tmp); 261 0 stevel 262 0 stevel leftover: 263 0 stevel /* if the leftover is enough for a new free piece */ 264 0 stevel if ((n = (SIZE(sp) - size)) >= MINSIZE + WORDSIZE) { 265 0 stevel n -= WORDSIZE; 266 0 stevel SIZE(sp) = size; 267 0 stevel /* LINTED improper alignment */ 268 0 stevel tp = NEXT(sp); 269 0 stevel SIZE(tp) = n | BIT0; 270 0 stevel realfree(DATA(tp)); 271 0 stevel } else if (BOTTOM(sp)) 272 0 stevel Bottom = NULL; 273 0 stevel 274 0 stevel /* return the allocated space */ 275 0 stevel copy_pattern(LIVEPAT, sp); 276 0 stevel SIZE(sp) |= BIT0; 277 0 stevel protect(sp); 278 0 stevel return (DATA(sp)); 279 0 stevel } 280 0 stevel 281 0 stevel /* 282 0 stevel * realloc(). 283 0 stevel * If the block size is increasing, we try forward merging first. 284 0 stevel * This is not best-fit but it avoids some data recopying. 285 0 stevel */ 286 0 stevel void * 287 0 stevel realloc(void *old, size_t size) 288 0 stevel { 289 0 stevel TREE *tp, *np; 290 0 stevel size_t ts; 291 0 stevel char *new; 292 0 stevel 293 0 stevel COUNT(nrealloc); 294 0 stevel 295 0 stevel /* check for size that could overflow calculations */ 296 0 stevel if (size > MAX_MALLOC) { 297 0 stevel errno = ENOMEM; 298 0 stevel return (NULL); 299 0 stevel } 300 0 stevel 301 0 stevel /* pointer to the block */ 302 3866 raf (void) mutex_lock(&__watch_malloc_lock); 303 0 stevel if (old == NULL) { 304 0 stevel new = malloc_unlocked(size); 305 3866 raf (void) mutex_unlock(&__watch_malloc_lock); 306 0 stevel return (new); 307 0 stevel } 308 0 stevel 309 0 stevel /* make sure that size is 0 mod ALIGN */ 310 0 stevel ROUND(size); 311 0 stevel 312 0 stevel /* LINTED improper alignment */ 313 0 stevel tp = BLOCK(old); 314 0 stevel unprotect(tp); 315 0 stevel ts = SIZE(tp); 316 0 stevel 317 0 stevel /* if the block was freed, data has been destroyed. */ 318 0 stevel if (!ISBIT0(ts)) { 319 0 stevel /* XXX; complain here! */ 320 0 stevel protect(tp); 321 3866 raf (void) mutex_unlock(&__watch_malloc_lock); 322 0 stevel errno = EINVAL; 323 0 stevel return (NULL); 324 0 stevel } 325 0 stevel 326 0 stevel CLRBITS01(SIZE(tp)); 327 0 stevel if (size == SIZE(tp)) { /* nothing to do */ 328 0 stevel SIZE(tp) = ts; 329 0 stevel protect(tp); 330 3866 raf (void) mutex_unlock(&__watch_malloc_lock); 331 0 stevel return (old); 332 0 stevel } 333 0 stevel 334 0 stevel /* special cases involving small blocks */ 335 0 stevel if (size < MINSIZE || SIZE(tp) < MINSIZE) { 336 0 stevel if (size == 0) { 337 0 stevel SETOLD01(SIZE(tp), ts); 338 0 stevel free_unlocked(old); 339 3866 raf (void) mutex_unlock(&__watch_malloc_lock); 340 0 stevel return (NULL); 341 0 stevel } 342 0 stevel goto call_malloc; 343 0 stevel } 344 0 stevel 345 0 stevel /* block is increasing in size, try merging the next block */ 346 0 stevel if (size > SIZE(tp)) { 347 0 stevel /* LINTED improper alignment */ 348 0 stevel np = NEXT(tp); 349 0 stevel unprotect(np); 350 0 stevel if (ISBIT0(SIZE(np))) 351 0 stevel protect(np); 352 0 stevel else { 353 0 stevel TREE *tmp; 354 0 stevel ASSERT(SIZE(np) >= MINSIZE); 355 0 stevel ASSERT(!ISBIT1(SIZE(np))); 356 0 stevel SIZE(tp) += SIZE(np) + WORDSIZE; 357 0 stevel if (np != Bottom) 358 0 stevel t_delete(np); 359 0 stevel else 360 0 stevel Bottom = NULL; 361 0 stevel /* LINTED improper alignment */ 362 0 stevel tmp = NEXT(np); 363 0 stevel unprotect(tmp); 364 0 stevel CLRBIT1(SIZE(tmp)); 365 0 stevel protect(tmp); 366 0 stevel } 367 0 stevel 368 0 stevel /* not enough & at TRUE end of memory, try extending core */ 369 0 stevel if (size > SIZE(tp) && BOTTOM(tp) && GETCORE(0) == Baddr) { 370 0 stevel Bottom = tp; 371 0 stevel protect(Bottom); 372 0 stevel if ((tp = morecore(size)) == NULL) { 373 0 stevel tp = Bottom; 374 0 stevel Bottom = NULL; 375 0 stevel unprotect(tp); 376 0 stevel } 377 0 stevel } 378 0 stevel } 379 0 stevel 380 0 stevel /* got enough space to use */ 381 0 stevel if (size <= SIZE(tp)) { 382 0 stevel size_t n; 383 0 stevel chop_big: 384 0 stevel if ((n = (SIZE(tp) - size)) >= MINSIZE + WORDSIZE) { 385 0 stevel n -= WORDSIZE; 386 0 stevel SIZE(tp) = size; 387 0 stevel /* LINTED improper alignment */ 388 0 stevel np = NEXT(tp); 389 0 stevel SIZE(np) = n | BIT0; 390 0 stevel realfree(DATA(np)); 391 0 stevel } else if (BOTTOM(tp)) 392 0 stevel Bottom = NULL; 393 0 stevel 394 0 stevel /* the previous block may be free */ 395 0 stevel SETOLD01(SIZE(tp), ts); 396 0 stevel protect(tp); 397 3866 raf (void) mutex_unlock(&__watch_malloc_lock); 398 0 stevel return (old); 399 0 stevel } 400 0 stevel 401 0 stevel call_malloc: /* call malloc to get a new block */ 402 0 stevel SETOLD01(SIZE(tp), ts); 403 0 stevel if ((new = malloc_unlocked(size)) != NULL) { 404 0 stevel CLRBITS01(ts); 405 0 stevel if (ts > size) 406 0 stevel ts = size; 407 0 stevel (void) memcpy(new, old, ts); 408 0 stevel free_unlocked(old); 409 3866 raf (void) mutex_unlock(&__watch_malloc_lock); 410 0 stevel return (new); 411 0 stevel } 412 0 stevel 413 0 stevel /* 414 0 stevel * Attempt special case recovery allocations since malloc() failed: 415 0 stevel * 416 0 stevel * 1. size <= SIZE(tp) < MINSIZE 417 0 stevel * Simply return the existing block 418 0 stevel * 2. SIZE(tp) < size < MINSIZE 419 0 stevel * malloc() may have failed to allocate the chunk of 420 0 stevel * small blocks. Try asking for MINSIZE bytes. 421 0 stevel * 3. size < MINSIZE <= SIZE(tp) 422 0 stevel * malloc() may have failed as with 2. Change to 423 0 stevel * MINSIZE allocation which is taken from the beginning 424 0 stevel * of the current block. 425 0 stevel * 4. MINSIZE <= SIZE(tp) < size 426 0 stevel * If the previous block is free and the combination of 427 0 stevel * these two blocks has at least size bytes, then merge 428 0 stevel * the two blocks copying the existing contents backwards. 429 0 stevel */ 430 0 stevel CLRBITS01(SIZE(tp)); 431 0 stevel if (SIZE(tp) < MINSIZE) { 432 0 stevel if (size < SIZE(tp)) /* case 1. */ { 433 0 stevel SETOLD01(SIZE(tp), ts); 434 0 stevel protect(tp); 435 3866 raf (void) mutex_unlock(&__watch_malloc_lock); 436 0 stevel return (old); 437 0 stevel } else if (size < MINSIZE) /* case 2. */ { 438 0 stevel size = MINSIZE; 439 0 stevel goto call_malloc; 440 0 stevel } 441 0 stevel } else if (size < MINSIZE) /* case 3. */ { 442 0 stevel size = MINSIZE; 443 0 stevel goto chop_big; 444 0 stevel } else if (ISBIT1(ts)) { 445 0 stevel np = LAST(tp); 446 0 stevel unprotect(np); 447 0 stevel if ((SIZE(np) + SIZE(tp) + WORDSIZE) >= size) { 448 0 stevel ASSERT(!ISBIT0(SIZE(np))); 449 0 stevel t_delete(np); 450 0 stevel SIZE(np) += SIZE(tp) + WORDSIZE; 451 0 stevel /* 452 0 stevel * Since the copy may overlap, use memmove(). 453 0 stevel */ 454 0 stevel (void) memmove(DATA(np), old, SIZE(tp)); 455 0 stevel old = DATA(np); 456 0 stevel tp = np; 457 0 stevel CLRBIT1(ts); 458 0 stevel goto chop_big; 459 0 stevel } 460 0 stevel protect(np); 461 0 stevel } 462 0 stevel SETOLD01(SIZE(tp), ts); 463 0 stevel protect(tp); 464 3866 raf (void) mutex_unlock(&__watch_malloc_lock); 465 0 stevel /* malloc() sets errno */ 466 0 stevel return (NULL); 467 0 stevel } 468 0 stevel 469 0 stevel /* 470 0 stevel * realfree(). 471 0 stevel * Coalescing of adjacent free blocks is done first. 472 0 stevel * Then, the new free block is leaf-inserted into the free tree 473 0 stevel * without splaying. This strategy does not guarantee the amortized 474 0 stevel * O(nlogn) behaviour for the insert/delete/find set of operations 475 0 stevel * on the tree. In practice, however, free is much more infrequent 476 0 stevel * than malloc/realloc and the tree searches performed by these 477 0 stevel * functions adequately keep the tree in balance. 478 0 stevel */ 479 0 stevel static void 480 0 stevel realfree(void *old) 481 0 stevel { 482 0 stevel TREE *tp, *sp, *np, *tmp; 483 0 stevel size_t ts, size; 484 0 stevel 485 0 stevel COUNT(nfree); 486 0 stevel 487 0 stevel /* pointer to the block */ 488 0 stevel /* LINTED improper alignment */ 489 0 stevel tp = BLOCK(old); 490 0 stevel unprotect(tp); 491 0 stevel ts = SIZE(tp); 492 0 stevel if (!ISBIT0(ts)) { /* block is not busy; previously freed? */ 493 0 stevel protect(tp); /* force a watchpoint trap */ 494 0 stevel CLRBIT0(SIZE(tp)); 495 0 stevel return; 496 0 stevel } 497 0 stevel CLRBITS01(SIZE(tp)); 498 0 stevel copy_pattern(FREEPAT, tp); 499 0 stevel 500 0 stevel /* small block, return it to the tail of its queue */ 501 0 stevel if (SIZE(tp) < MINSIZE) { 502 0 stevel ASSERT(SIZE(tp) / WORDSIZE >= 1); 503 0 stevel ts = SIZE(tp) / WORDSIZE - 1; 504 0 stevel AFTER(tp) = NULL; 505 0 stevel protect(tp); 506 0 stevel if (List[ts] == NULL) { 507 0 stevel List[ts] = tp; 508 0 stevel Last[ts] = tp; 509 0 stevel } else { 510 0 stevel sp = Last[ts]; 511 0 stevel unprotect(sp); 512 0 stevel AFTER(sp) = tp; 513 0 stevel protect(sp); 514 0 stevel Last[ts] = tp; 515 0 stevel } 516 0 stevel return; 517 0 stevel } 518 0 stevel 519 0 stevel /* see if coalescing with next block is warranted */ 520 0 stevel /* LINTED improper alignment */ 521 0 stevel np = NEXT(tp); 522 0 stevel unprotect(np); 523 0 stevel if (ISBIT0(SIZE(np))) 524 0 stevel protect(np); 525 0 stevel else { 526 0 stevel if (np != Bottom) 527 0 stevel t_delete(np); 528 0 stevel SIZE(tp) += SIZE(np) + WORDSIZE; 529 0 stevel } 530 0 stevel 531 0 stevel /* the same with the preceding block */ 532 0 stevel if (ISBIT1(ts)) { 533 0 stevel np = LAST(tp); 534 0 stevel unprotect(np); 535 0 stevel ASSERT(!ISBIT0(SIZE(np))); 536 0 stevel ASSERT(np != Bottom); 537 0 stevel t_delete(np); 538 0 stevel SIZE(np) += SIZE(tp) + WORDSIZE; 539 0 stevel tp = np; 540 0 stevel } 541 0 stevel 542 0 stevel /* initialize tree info */ 543 0 stevel PARENT(tp) = LEFT(tp) = RIGHT(tp) = LINKFOR(tp) = NULL; 544 0 stevel 545 0 stevel /* set bottom block, or insert in the free tree */ 546 0 stevel if (BOTTOM(tp)) 547 0 stevel Bottom = tp; 548 0 stevel else { 549 0 stevel /* search for the place to insert */ 550 0 stevel if (Root) { 551 0 stevel size = SIZE(tp); 552 0 stevel np = Root; 553 0 stevel for (;;) { 554 0 stevel unprotect(np); 555 0 stevel if (SIZE(np) > size) { 556 0 stevel if ((tmp = LEFT(np)) != NULL) { 557 0 stevel protect(np); 558 0 stevel np = tmp; 559 0 stevel } else { 560 0 stevel LEFT(np) = tp; 561 0 stevel PARENT(tp) = np; 562 0 stevel protect(np); 563 0 stevel break; 564 0 stevel } 565 0 stevel } else if (SIZE(np) < size) { 566 0 stevel if ((tmp = RIGHT(np)) != NULL) { 567 0 stevel protect(np); 568 0 stevel np = tmp; 569 0 stevel } else { 570 0 stevel RIGHT(np) = tp; 571 0 stevel PARENT(tp) = np; 572 0 stevel protect(np); 573 0 stevel break; 574 0 stevel } 575 0 stevel } else { 576 0 stevel if ((sp = PARENT(np)) != NULL) { 577 0 stevel unprotect(sp); 578 0 stevel if (np == LEFT(sp)) 579 0 stevel LEFT(sp) = tp; 580 0 stevel else 581 0 stevel RIGHT(sp) = tp; 582 0 stevel PARENT(tp) = sp; 583 0 stevel protect(sp); 584 0 stevel } else 585 0 stevel Root = tp; 586 0 stevel 587 0 stevel /* insert to head of list */ 588 0 stevel if ((sp = LEFT(np)) != NULL) { 589 0 stevel unprotect(sp); 590 0 stevel PARENT(sp) = tp; 591 0 stevel protect(sp); 592 0 stevel } 593 0 stevel LEFT(tp) = sp; 594 0 stevel 595 0 stevel if ((sp = RIGHT(np)) != NULL) { 596 0 stevel unprotect(sp); 597 0 stevel PARENT(sp) = tp; 598 0 stevel protect(sp); 599 0 stevel } 600 0 stevel RIGHT(tp) = sp; 601 0 stevel 602 0 stevel /* doubly link list */ 603 0 stevel LINKFOR(tp) = np; 604 0 stevel LINKBAK(np) = tp; 605 0 stevel SETNOTREE(np); 606 0 stevel protect(np); 607 0 stevel 608 0 stevel break; 609 0 stevel } 610 0 stevel } 611 0 stevel } else { 612 0 stevel Root = tp; 613 0 stevel } 614 0 stevel } 615 0 stevel 616 0 stevel /* 617 0 stevel * Tell next block that this one is free. 618 0 stevel * The first WORD of the next block contains self's address. 619 0 stevel */ 620 0 stevel /* LINTED improper alignment */ 621 0 stevel tmp = NEXT(tp); 622 0 stevel unprotect(tmp); 623 0 stevel /* LINTED improper alignment */ 624 0 stevel *(SELFP(tp)) = tp; 625 0 stevel SETBIT1(SIZE(tmp)); 626 0 stevel ASSERT(ISBIT0(SIZE(tmp))); 627 0 stevel protect(tmp); 628 0 stevel protect(tp); 629 0 stevel } 630 0 stevel 631 0 stevel /* 632 0 stevel * Get more core. Gaps in memory are noted as busy blocks. 633 0 stevel */ 634 0 stevel static TREE * 635 0 stevel morecore(size_t size) 636 0 stevel { 637 0 stevel TREE *tp; 638 0 stevel size_t n, offset, requestsize; 639 0 stevel char *addr; 640 0 stevel 641 0 stevel /* compute new amount of memory to get */ 642 0 stevel tp = Bottom; 643 0 stevel n = size + 2 * WORDSIZE; 644 0 stevel addr = GETCORE(0); 645 0 stevel 646 0 stevel if (addr == ERRCORE) 647 0 stevel /* errno set by GETCORE sbrk */ 648 0 stevel return (NULL); 649 0 stevel 650 0 stevel /* need to pad size out so that addr is aligned */ 651 0 stevel if ((((size_t)addr) % ALIGN) != 0) 652 0 stevel offset = ALIGN - (size_t)addr % ALIGN; 653 0 stevel else 654 0 stevel offset = 0; 655 0 stevel 656 0 stevel if (tp) 657 0 stevel unprotect(tp); 658 0 stevel 659 0 stevel /* if not segmented memory, what we need may be smaller */ 660 0 stevel if (addr == Baddr) { 661 0 stevel n -= WORDSIZE; 662 0 stevel if (tp != NULL) 663 0 stevel n -= SIZE(tp); 664 0 stevel } 665 0 stevel 666 0 stevel /* get a multiple of CORESIZE */ 667 0 stevel n = ((n - 1) / CORESIZE + 1) * CORESIZE; 668 0 stevel requestsize = n + offset; 669 0 stevel 670 0 stevel /* check if nsize request could overflow in GETCORE */ 671 0 stevel if (requestsize > MAX_MALLOC - (size_t)addr) { 672 0 stevel if (tp) 673 0 stevel protect(tp); 674 0 stevel errno = ENOMEM; 675 0 stevel return (NULL); 676 0 stevel } 677 0 stevel 678 0 stevel if (requestsize > MAX_GETCORE) { 679 0 stevel intptr_t delta; 680 0 stevel /* 681 0 stevel * the value required is too big for GETCORE() to deal with 682 0 stevel * in one go, so use GETCORE() at most 2 times instead. 683 0 stevel * Argument to GETCORE() must be multiple of ALIGN. 684 0 stevel * If not, GETCORE(-MAX_GETCORE) will not return brk point 685 0 stevel * to previous value, but will be ALIGN more. 686 0 stevel * This would leave a small hole. 687 0 stevel */ 688 0 stevel delta = MAX_GETCORE; 689 0 stevel while (delta > 0) { 690 0 stevel if (GETCORE(delta) == ERRCORE) { 691 0 stevel if (tp) 692 0 stevel protect(tp); 693 0 stevel if (addr != GETCORE(0)) 694 0 stevel (void) GETCORE(-MAX_GETCORE); 695 0 stevel return (NULL); 696 0 stevel } 697 0 stevel requestsize -= MAX_GETCORE; 698 0 stevel delta = requestsize; 699 0 stevel } 700 0 stevel } else if (GETCORE(requestsize) == ERRCORE) { 701 0 stevel if (tp) 702 0 stevel protect(tp); 703 0 stevel return (NULL); 704 0 stevel } 705 0 stevel 706 0 stevel /* contiguous memory */ 707 0 stevel if (addr == Baddr) { 708 0 stevel ASSERT(offset == 0); 709 0 stevel if (tp) { 710 0 stevel addr = ((char *)tp); 711 0 stevel n += SIZE(tp) + 2 * WORDSIZE; 712 0 stevel } else { 713 0 stevel addr = Baddr - WORDSIZE; 714 0 stevel n += WORDSIZE; 715 0 stevel } 716 0 stevel } else { 717 0 stevel addr += offset; 718 0 stevel } 719 0 stevel 720 0 stevel /* new bottom address */ 721 0 stevel Baddr = addr + n; 722 0 stevel 723 0 stevel /* new bottom block */ 724 0 stevel /* LINTED improper alignment */ 725 0 stevel tp = ((TREE *)addr); 726 0 stevel SIZE(tp) = n - 2 * WORDSIZE; 727 0 stevel ASSERT((SIZE(tp) % ALIGN) == 0); 728 0 stevel 729 0 stevel /* reserved the last word to head any noncontiguous memory */ 730 0 stevel /* LINTED improper alignment */ 731 0 stevel SETBIT0(SIZE(NEXT(tp))); 732 0 stevel 733 0 stevel /* non-contiguous memory, free old bottom block */ 734 0 stevel if (Bottom && Bottom != tp) { 735 0 stevel SETBIT0(SIZE(Bottom)); 736 0 stevel realfree(DATA(Bottom)); 737 0 stevel } 738 0 stevel 739 0 stevel return (tp); 740 0 stevel } 741 0 stevel 742 0 stevel /* 743 0 stevel * Utility function to avoid protecting a tree node twice. 744 0 stevel * Return true if tp is in the NULL-terminated array of tree nodes. 745 0 stevel */ 746 0 stevel static int 747 0 stevel in_list(TREE *tp, TREE **npp) 748 0 stevel { 749 0 stevel TREE *sp; 750 0 stevel 751 0 stevel while ((sp = *npp++) != NULL) 752 0 stevel if (tp == sp) 753 0 stevel return (1); 754 0 stevel return (0); 755 0 stevel } 756 0 stevel 757 0 stevel /* 758 0 stevel * Tree rotation functions (BU: bottom-up, TD: top-down). 759 0 stevel * All functions are entered with the arguments unprotected. 760 0 stevel * They must return in the same condition, with all other elements 761 0 stevel * that have been unprotected during the operation re-protected. 762 0 stevel */ 763 0 stevel static void 764 0 stevel LEFT1(TREE *x, TREE *y) 765 0 stevel { 766 0 stevel TREE *node[3]; 767 0 stevel TREE **npp = node; 768 0 stevel TREE *tp; 769 0 stevel 770 0 stevel if ((RIGHT(x) = LEFT(y)) != NULL) { 771 0 stevel unprotect(*npp++ = RIGHT(x)); 772 0 stevel PARENT(RIGHT(x)) = x; 773 0 stevel } 774 0 stevel if ((PARENT(y) = PARENT(x)) != NULL) { 775 0 stevel unprotect(*npp++ = PARENT(x)); 776 0 stevel if (LEFT(PARENT(x)) == x) 777 0 stevel LEFT(PARENT(y)) = y; 778 0 stevel else 779 0 stevel RIGHT(PARENT(y)) = y; 780 0 stevel } 781 0 stevel LEFT(y) = x; 782 0 stevel PARENT(x) = y; 783 0 stevel 784 0 stevel *npp = NULL; 785 0 stevel npp = node; 786 0 stevel while ((tp = *npp++) != NULL) 787 0 stevel if (tp != x && tp != y && !in_list(tp, npp)) 788 0 stevel protect(tp); 789 0 stevel } 790 0 stevel 791 0 stevel static void 792 0 stevel RIGHT1(TREE *x, TREE *y) 793 0 stevel { 794 0 stevel TREE *node[3]; 795 0 stevel TREE **npp = node; 796 0 stevel TREE *tp; 797 0 stevel 798 0 stevel if ((LEFT(x) = RIGHT(y)) != NULL) { 799 0 stevel unprotect(*npp++ = LEFT(x)); 800 0 stevel PARENT(LEFT(x)) = x; 801 0 stevel } 802 0 stevel if ((PARENT(y) = PARENT(x)) != NULL) { 803 0 stevel unprotect(*npp++ = PARENT(x)); 804 0 stevel if (LEFT(PARENT(x)) == x) 805 0 stevel LEFT(PARENT(y)) = y; 806 0 stevel else 807 0 stevel RIGHT(PARENT(y)) = y; 808 0 stevel } 809 0 stevel RIGHT(y) = x; 810 0 stevel PARENT(x) = y; 811 0 stevel 812 0 stevel *npp = NULL; 813 0 stevel npp = node; 814 0 stevel while ((tp = *npp++) != NULL) 815 0 stevel if (tp != x && tp != y && !in_list(tp, npp)) 816 0 stevel protect(tp); 817 0 stevel } 818 0 stevel 819 0 stevel static void 820 0 stevel BULEFT2(TREE *x, TREE *y, TREE *z) 821 0 stevel { 822 0 stevel TREE *node[4]; 823 0 stevel TREE **npp = node; 824 0 stevel TREE *tp; 825 0 stevel 826 0 stevel if ((RIGHT(x) = LEFT(y)) != NULL) { 827 0 stevel unprotect(*npp++ = RIGHT(x)); 828 0 stevel PARENT(RIGHT(x)) = x; 829 0 stevel } 830 0 stevel if ((RIGHT(y) = LEFT(z)) != NULL) { 831 0 stevel unprotect(*npp++ = RIGHT(y)); 832 0 stevel PARENT(RIGHT(y)) = y; 833 0 stevel } 834 0 stevel if ((PARENT(z) = PARENT(x)) != NULL) { 835 0 stevel unprotect(*npp++ = PARENT(x)); 836 0 stevel if (LEFT(PARENT(x)) == x) 837 0 stevel LEFT(PARENT(z)) = z; 838 0 stevel else 839 0 stevel RIGHT(PARENT(z)) = z; 840 0 stevel } 841 0 stevel LEFT(z) = y; 842 0 stevel PARENT(y) = z; 843 0 stevel LEFT(y) = x; 844 0 stevel PARENT(x) = y; 845 0 stevel 846 0 stevel *npp = NULL; 847 0 stevel npp = node; 848 0 stevel while ((tp = *npp++) != NULL) 849 0 stevel if (tp != x && tp != y && tp != z && !in_list(tp, npp)) 850 0 stevel protect(tp); 851 0 stevel } 852 0 stevel 853 0 stevel static void 854 0 stevel BURIGHT2(TREE *x, TREE *y, TREE *z) 855 0 stevel { 856 0 stevel TREE *node[4]; 857 0 stevel TREE **npp = node; 858 0 stevel TREE *tp; 859 0 stevel 860 0 stevel if ((LEFT(x) = RIGHT(y)) != NULL) { 861 0 stevel unprotect(*npp++ = LEFT(x)); 862 0 stevel PARENT(LEFT(x)) = x; 863 0 stevel } 864 0 stevel if ((LEFT(y) = RIGHT(z)) != NULL) { 865 0 stevel unprotect(*npp++ = LEFT(y)); 866 0 stevel PARENT(LEFT(y)) = y; 867 0 stevel } 868 0 stevel if ((PARENT(z) = PARENT(x)) != NULL) { 869 0 stevel unprotect(*npp++ = PARENT(x)); 870 0 stevel if (LEFT(PARENT(x)) == x) 871 0 stevel LEFT(PARENT(z)) = z; 872 0 stevel else 873 0 stevel RIGHT(PARENT(z)) = z; 874 0 stevel } 875 0 stevel RIGHT(z) = y; 876 0 stevel PARENT(y) = z; 877 0 stevel RIGHT(y) = x; 878 0 stevel PARENT(x) = y; 879 0 stevel 880 0 stevel *npp = NULL; 881 0 stevel npp = node; 882 0 stevel while ((tp = *npp++) != NULL) 883 0 stevel if (tp != x && tp != y && tp != z && !in_list(tp, npp)) 884 0 stevel protect(tp); 885 0 stevel } 886 0 stevel 887 0 stevel static void 888 0 stevel TDLEFT2(TREE *x, TREE *y, TREE *z) 889 0 stevel { 890 0 stevel TREE *node[3]; 891 0 stevel TREE **npp = node; 892 0 stevel TREE *tp; 893 0 stevel 894 0 stevel if ((RIGHT(y) = LEFT(z)) != NULL) { 895 0 stevel unprotect(*npp++ = RIGHT(y)); 896 0 stevel PARENT(RIGHT(y)) = y; 897 0 stevel } 898 0 stevel if ((PARENT(z) = PARENT(x)) != NULL) { 899 0 stevel unprotect(*npp++ = PARENT(x)); 900 0 stevel if (LEFT(PARENT(x)) == x) 901 0 stevel LEFT(PARENT(z)) = z; 902 0 stevel else 903 0 stevel RIGHT(PARENT(z)) = z; 904 0 stevel } 905 0 stevel PARENT(x) = z; 906 0 stevel LEFT(z) = x; 907 0 stevel 908 0 stevel *npp = NULL; 909 0 stevel npp = node; 910 0 stevel while ((tp = *npp++) != NULL) 911 0 stevel if (tp != x && tp != y && tp != z && !in_list(tp, npp)) 912 0 stevel protect(tp); 913 0 stevel } 914 0 stevel 915 0 stevel #if 0 /* Not used, for now */ 916 0 stevel static void 917 0 stevel TDRIGHT2(TREE *x, TREE *y, TREE *z) 918 0 stevel { 919 0 stevel TREE *node[3]; 920 0 stevel TREE **npp = node; 921 0 stevel TREE *tp; 922 0 stevel 923 0 stevel if ((LEFT(y) = RIGHT(z)) != NULL) { 924 0 stevel unprotect(*npp++ = LEFT(y)); 925 0 stevel PARENT(LEFT(y)) = y; 926 0 stevel } 927 0 stevel if ((PARENT(z) = PARENT(x)) != NULL) { 928 0 stevel unprotect(*npp++ = PARENT(x)); 929 0 stevel if (LEFT(PARENT(x)) == x) 930 0 stevel LEFT(PARENT(z)) = z; 931 0 stevel else 932 0 stevel RIGHT(PARENT(z)) = z; 933 0 stevel } 934 0 stevel PARENT(x) = z; 935 0 stevel RIGHT(z) = x; 936 0 stevel 937 0 stevel *npp = NULL; 938 0 stevel npp = node; 939 0 stevel while ((tp = *npp++) != NULL) 940 0 stevel if (tp != x && tp != y && tp != z && !in_list(tp, npp)) 941 0 stevel protect(tp); 942 0 stevel } 943 0 stevel #endif 944 0 stevel 945 0 stevel /* 946 0 stevel * Delete a tree element 947 0 stevel */ 948 0 stevel static void 949 0 stevel t_delete(TREE *op) 950 0 stevel { 951 0 stevel TREE *tp, *sp, *gp; 952 0 stevel 953 0 stevel /* if this is a non-tree node */ 954 0 stevel if (ISNOTREE(op)) { 955 0 stevel tp = LINKBAK(op); 956 0 stevel unprotect(tp); 957 0 stevel if ((sp = LINKFOR(op)) != NULL) { 958 0 stevel unprotect(sp); 959 0 stevel LINKBAK(sp) = tp; 960 0 stevel protect(sp); 961 0 stevel } 962 0 stevel LINKFOR(tp) = sp; 963 0 stevel protect(tp); 964 0 stevel return; 965 0 stevel } 966 0 stevel 967 0 stevel /* make op the root of the tree */ 968 0 stevel if (PARENT(op)) 969 0 stevel t_splay(op); 970 0 stevel 971 0 stevel /* if this is the start of a list */ 972 0 stevel if ((tp = LINKFOR(op)) != NULL) { 973 0 stevel unprotect(tp); 974 0 stevel PARENT(tp) = NULL; 975 0 stevel if ((sp = LEFT(op)) != NULL) { 976 0 stevel unprotect(sp); 977 0 stevel PARENT(sp) = tp; 978 0 stevel protect(sp); 979 0 stevel } 980 0 stevel LEFT(tp) = sp; 981 0 stevel 982 0 stevel if ((sp = RIGHT(op)) != NULL) { 983 0 stevel unprotect(sp); 984 0 stevel PARENT(sp) = tp; 985 0 stevel protect(sp); 986 0 stevel } 987 0 stevel RIGHT(tp) = sp; 988 0 stevel 989 0 stevel Root = tp; 990 0 stevel protect(tp); 991 0 stevel return; 992 0 stevel } 993 0 stevel 994 0 stevel /* if op has a non-null left subtree */ 995 0 stevel if ((tp = LEFT(op)) != NULL) { 996 0 stevel unprotect(tp); 997 0 stevel PARENT(tp) = NULL; 998 0 stevel if (RIGHT(op)) { 999 0 stevel /* make the right-end of the left subtree its root */ 1000 0 stevel while ((sp = RIGHT(tp)) != NULL) { 1001 0 stevel unprotect(sp); 1002 0 stevel if ((gp = RIGHT(sp)) != NULL) { 1003 0 stevel unprotect(gp); 1004 0 stevel TDLEFT2(tp, sp, gp); 1005 0 stevel protect(sp); 1006 0 stevel protect(tp); 1007 0 stevel tp = gp; 1008 0 stevel } else { 1009 0 stevel LEFT1(tp, sp); 1010 0 stevel protect(tp); 1011 0 stevel tp = sp; 1012 0 stevel } 1013 0 stevel } 1014 0 stevel 1015 0 stevel /* hook the right subtree of op to the above elt */ 1016 0 stevel RIGHT(tp) = sp = RIGHT(op); 1017 0 stevel unprotect(sp); 1018 0 stevel PARENT(sp) = tp; 1019 0 stevel protect(sp); 1020 0 stevel } 1021 0 stevel protect(tp); 1022 0 stevel } else if ((tp = RIGHT(op)) != NULL) { /* no left subtree */ 1023 0 stevel unprotect(tp); 1024 0 stevel PARENT(tp) = NULL; 1025 0 stevel protect(tp); 1026 0 stevel } 1027 0 stevel 1028 0 stevel Root = tp; 1029 0 stevel } 1030 0 stevel 1031 0 stevel /* 1032 0 stevel * Bottom up splaying (simple version). 1033 0 stevel * The basic idea is to roughly cut in half the 1034 0 stevel * path from Root to tp and make tp the new root. 1035 0 stevel */ 1036 0 stevel static void 1037 0 stevel t_splay(TREE *tp) 1038 0 stevel { 1039 0 stevel TREE *pp, *gp; 1040 0 stevel 1041 0 stevel /* iterate until tp is the root */ 1042 0 stevel while ((pp = PARENT(tp)) != NULL) { 1043 0 stevel unprotect(pp); 1044 0 stevel /* grandparent of tp */ 1045 0 stevel gp = PARENT(pp); 1046 0 stevel if (gp) 1047 0 stevel unprotect(gp); 1048 0 stevel 1049 0 stevel /* x is a left child */ 1050 0 stevel if (LEFT(pp) == tp) { 1051 0 stevel if (gp && LEFT(gp) == pp) { 1052 0 stevel BURIGHT2(gp, pp, tp); 1053 0 stevel protect(gp); 1054 0 stevel } else { 1055 0 stevel if (gp) 1056 0 stevel protect(gp); 1057 0 stevel RIGHT1(pp, tp); 1058 0 stevel } 1059 0 stevel } else { 1060 0 stevel ASSERT(RIGHT(pp) == tp); 1061 0 stevel if (gp && RIGHT(gp) == pp) { 1062 0 stevel BULEFT2(gp, pp, tp); 1063 0 stevel protect(gp); 1064 0 stevel } else { 1065 0 stevel if (gp) 1066 0 stevel protect(gp); 1067 0 stevel LEFT1(pp, tp); 1068 0 stevel } 1069 0 stevel } 1070 0 stevel protect(pp); 1071 0 stevel unprotect(tp); /* just in case */ 1072 0 stevel } 1073 0 stevel } 1074 0 stevel 1075 0 stevel void 1076 0 stevel free(void *old) 1077 0 stevel { 1078 3866 raf (void) mutex_lock(&__watch_malloc_lock); 1079 0 stevel free_unlocked(old); 1080 3866 raf (void) mutex_unlock(&__watch_malloc_lock); 1081 0 stevel } 1082 0 stevel 1083 0 stevel 1084 0 stevel static void 1085 0 stevel free_unlocked(void *old) 1086 0 stevel { 1087 0 stevel if (old != NULL) 1088 0 stevel realfree(old); 1089 0 stevel } 1090 0 stevel 1091 0 stevel 1092 0 stevel /* 1093 0 stevel * memalign(align,nbytes) 1094 0 stevel * 1095 0 stevel * Description: 1096 0 stevel * Returns a block of specified size on a specified alignment boundary. 1097 0 stevel * 1098 0 stevel * Algorithm: 1099 0 stevel * Malloc enough to ensure that a block can be aligned correctly. 1100 0 stevel * Find the alignment point and return the fragments 1101 0 stevel * before and after the block. 1102 0 stevel * 1103 0 stevel * Errors: 1104 0 stevel * Returns NULL and sets errno as follows: 1105 0 stevel * [EINVAL] 1106 0 stevel * if nbytes = 0, 1107 0 stevel * or if alignment is misaligned, 1108 0 stevel * or if the heap has been detectably corrupted. 1109 0 stevel * [ENOMEM] 1110 0 stevel * if the requested memory could not be allocated. 1111 0 stevel */ 1112 0 stevel 1113 0 stevel #define misaligned(p) ((unsigned)(p) & 3) 1114 0 stevel /* 4-byte "word" alignment is considered ok in LP64 */ 1115 0 stevel #define nextblk(p, size) ((TREE *)((char *)(p) + (size))) 1116 0 stevel 1117 0 stevel void * 1118 2658 raf memalign(size_t align, size_t nbytes) 1119 0 stevel { 1120 0 stevel size_t reqsize; /* Num of bytes to get from malloc() */ 1121 0 stevel TREE *p; /* Ptr returned from malloc() */ 1122 0 stevel TREE *blk; /* For addressing fragment blocks */ 1123 0 stevel size_t blksize; /* Current (shrinking) block size */ 1124 0 stevel TREE *alignedp; /* Ptr to properly aligned boundary */ 1125 0 stevel TREE *aligned_blk; /* The block to be returned */ 1126 0 stevel size_t frag_size; /* size of fragments fore and aft */ 1127 0 stevel size_t x; 1128 0 stevel 1129 0 stevel /* 1130 0 stevel * check for valid size and alignment parameters 1131 0 stevel * MAX_ALIGN check prevents overflow in later calculation. 1132 0 stevel */ 1133 0 stevel if (nbytes == 0 || misaligned(align) || align == 0 || 1134 0 stevel align > MAX_ALIGN) { 1135 0 stevel errno = EINVAL; 1136 0 stevel return (NULL); 1137 0 stevel } 1138 0 stevel 1139 0 stevel /* 1140 0 stevel * Malloc enough memory to guarantee that the result can be 1141 0 stevel * aligned correctly. The worst case is when malloc returns 1142 0 stevel * a block so close to the next alignment boundary that a 1143 0 stevel * fragment of minimum size cannot be created. In order to 1144 0 stevel * make sure we can handle this, we need to force the 1145 0 stevel * alignment to be at least as large as the minimum frag size 1146 0 stevel * (MINSIZE + WORDSIZE). 1147 0 stevel */ 1148 0 stevel 1149 0 stevel /* check for size that could overflow ROUND calculation */ 1150 0 stevel if (nbytes > MAX_MALLOC) { 1151 0 stevel errno = ENOMEM; 1152 0 stevel return (NULL); 1153 0 stevel } 1154 0 stevel ROUND(nbytes); 1155 0 stevel if (nbytes < MINSIZE) 1156 0 stevel nbytes = MINSIZE; 1157 0 stevel ROUND(align); 1158 0 stevel while (align < MINSIZE + WORDSIZE) 1159 0 stevel align <<= 1; 1160 0 stevel reqsize = nbytes + align + (MINSIZE + WORDSIZE); 1161 0 stevel /* check for overflow */ 1162 0 stevel if (reqsize < nbytes) { 1163 0 stevel errno = ENOMEM; 1164 0 stevel return (NULL); 1165 0 stevel } 1166 0 stevel p = (TREE *) malloc(reqsize); 1167 0 stevel if (p == (TREE *) NULL) { 1168 0 stevel /* malloc sets errno */ 1169 0 stevel return (NULL); 1170 0 stevel } 1171 3866 raf (void) mutex_lock(&__watch_malloc_lock); 1172 0 stevel 1173 0 stevel /* 1174 0 stevel * get size of the entire block (overhead and all) 1175 0 stevel */ 1176 0 stevel /* LINTED improper alignment */ 1177 0 stevel blk = BLOCK(p); /* back up to get length word */ 1178 0 stevel unprotect(blk); 1179 0 stevel blksize = SIZE(blk); 1180 0 stevel CLRBITS01(blksize); 1181 0 stevel 1182 0 stevel /* 1183 0 stevel * locate the proper alignment boundary within the block. 1184 0 stevel */ 1185 0 stevel x = (size_t)p; 1186 0 stevel if (x % align != 0) 1187 0 stevel x += align - (x % align); 1188 0 stevel alignedp = (TREE *)x; 1189 0 stevel /* LINTED improper alignment */ 1190 0 stevel aligned_blk = BLOCK(alignedp); 1191 0 stevel 1192 0 stevel /* 1193 0 stevel * Check out the space to the left of the alignment 1194 0 stevel * boundary, and split off a fragment if necessary. 1195 0 stevel */ 1196 0 stevel frag_size = (size_t)aligned_blk - (size_t)blk; 1197 0 stevel if (frag_size != 0) { 1198 0 stevel /* 1199 0 stevel * Create a fragment to the left of the aligned block. 1200 0 stevel */ 1201 0 stevel if (frag_size < MINSIZE + WORDSIZE) { 1202 0 stevel /* 1203 0 stevel * Not enough space. So make the split 1204 0 stevel * at the other end of the alignment unit. 1205 0 stevel * We know this yields enough space, because 1206 0 stevel * we forced align >= MINSIZE + WORDSIZE above. 1207 0 stevel */ 1208 0 stevel frag_size += align; 1209 0 stevel /* LINTED improper alignment */ 1210 0 stevel aligned_blk = nextblk(aligned_blk, align); 1211 0 stevel } 1212 0 stevel blksize -= frag_size; 1213 0 stevel SIZE(aligned_blk) = blksize | BIT0; 1214 0 stevel frag_size -= WORDSIZE; 1215 0 stevel SIZE(blk) = frag_size | BIT0 | ISBIT1(SIZE(blk)); 1216 0 stevel free_unlocked(DATA(blk)); 1217 0 stevel /* 1218 0 stevel * free_unlocked(DATA(blk)) has the side-effect of calling 1219 0 stevel * protect() on the block following blk, that is, aligned_blk. 1220 0 stevel * We recover from this by unprotect()ing it here. 1221 0 stevel */ 1222 0 stevel unprotect(aligned_blk); 1223 0 stevel } 1224 0 stevel 1225 0 stevel /* 1226 0 stevel * Is there a (sufficiently large) fragment to the 1227 0 stevel * right of the aligned block? 1228 0 stevel */ 1229 0 stevel frag_size = blksize - nbytes; 1230 0 stevel if (frag_size >= MINSIZE + WORDSIZE) { 1231 0 stevel /* 1232 0 stevel * split and free a fragment on the right 1233 0 stevel */ 1234 0 stevel blksize = SIZE(aligned_blk); 1235 0 stevel SIZE(aligned_blk) = nbytes; 1236 0 stevel /* LINTED improper alignment */ 1237 0 stevel blk = NEXT(aligned_blk); 1238 0 stevel SETOLD01(SIZE(aligned_blk), blksize); 1239 0 stevel frag_size -= WORDSIZE; 1240 0 stevel SIZE(blk) = frag_size | BIT0; 1241 0 stevel free_unlocked(DATA(blk)); 1242 0 stevel } 1243 0 stevel copy_pattern(LIVEPAT, aligned_blk); 1244 0 stevel protect(aligned_blk); 1245 3866 raf (void) mutex_unlock(&__watch_malloc_lock); 1246 0 stevel return (DATA(aligned_blk)); 1247 0 stevel } 1248 0 stevel 1249 0 stevel void * 1250 2658 raf valloc(size_t size) 1251 0 stevel { 1252 0 stevel static unsigned pagesize; 1253 0 stevel if (!pagesize) 1254 0 stevel pagesize = _sysconf(_SC_PAGESIZE); 1255 0 stevel return (memalign(pagesize, size)); 1256 0 stevel } 1257 0 stevel 1258 0 stevel void * 1259 0 stevel calloc(size_t num, size_t size) 1260 0 stevel { 1261 0 stevel void *mp; 1262 0 stevel size_t total; 1263 0 stevel 1264 0 stevel total = num * size; 1265 0 stevel 1266 0 stevel /* check for overflow */ 1267 0 stevel if (num != 0 && total / num != size) { 1268 0 stevel errno = ENOMEM; 1269 0 stevel return (NULL); 1270 0 stevel } 1271 0 stevel if ((mp = malloc(total)) != NULL) 1272 0 stevel (void) memset(mp, 0, total); 1273 0 stevel return (mp); 1274 0 stevel } 1275 0 stevel 1276 0 stevel /* ARGSUSED1 */ 1277 0 stevel void 1278 2658 raf cfree(void *p, size_t num, size_t size) 1279 0 stevel { 1280 0 stevel free(p); 1281 0 stevel } 1282 0 stevel 1283 0 stevel typedef struct { 1284 0 stevel long cmd; 1285 0 stevel prwatch_t prwatch; 1286 0 stevel } ctl_t; 1287 0 stevel 1288 0 stevel static pid_t my_pid = 0; /* to check for whether we fork()d */ 1289 0 stevel static int dont_watch = 0; 1290 0 stevel static int do_stop = 0; 1291 0 stevel static int ctlfd = -1; 1292 0 stevel struct stat ctlstatb; 1293 0 stevel static int wflags = WA_WRITE; 1294 0 stevel 1295 0 stevel static void 1296 0 stevel init_watch() 1297 0 stevel { 1298 0 stevel char str[80]; 1299 0 stevel char *s; 1300 0 stevel 1301 0 stevel my_pid = getpid(); 1302 0 stevel 1303 0 stevel dont_watch = 1; 1304 0 stevel 1305 0 stevel if ((s = getenv("MALLOC_DEBUG")) == NULL) 1306 0 stevel return; 1307 0 stevel 1308 0 stevel s = strncpy(str, s, sizeof (str)); 1309 0 stevel while (s != NULL) { 1310 0 stevel char *e = strchr(s, ','); 1311 0 stevel if (e) 1312 0 stevel *e++ = '\0'; 1313 0 stevel if (strcmp(s, "STOP") == 0) 1314 0 stevel do_stop = 1; 1315 0 stevel else if (strcmp(s, "WATCH") == 0) 1316 0 stevel dont_watch = 0; 1317 0 stevel else if (strcmp(s, "RW") == 0) { 1318 0 stevel dont_watch = 0; 1319 0 stevel wflags = WA_READ|WA_WRITE; 1320 0 stevel } 1321 0 stevel s = e; 1322 0 stevel } 1323 0 stevel 1324 0 stevel if (dont_watch) 1325 0 stevel return; 1326 0 stevel 1327 0 stevel if ((ctlfd = open("/proc/self/ctl", O_WRONLY)) < 0 || 1328 0 stevel fstat(ctlfd, &ctlstatb) != 0) { 1329 0 stevel if (ctlfd >= 0) 1330 0 stevel (void) close(ctlfd); 1331 0 stevel ctlfd = -1; 1332 0 stevel dont_watch = 1; 1333 0 stevel return; 1334 0 stevel } 1335 0 stevel /* close-on-exec */ 1336 0 stevel (void) fcntl(ctlfd, F_SETFD, 1); 1337 0 stevel 1338 0 stevel if (do_stop) { 1339 0 stevel int pfd; 1340 0 stevel pstatus_t pstatus; 1341 0 stevel struct { 1342 0 stevel long cmd; 1343 0 stevel fltset_t fltset; 1344 0 stevel } ctl; 1345 0 stevel 1346 0 stevel /* 1347 0 stevel * Play together with some /proc controller 1348 0 stevel * that has set other stop-on-fault flags. 1349 0 stevel */ 1350 0 stevel premptyset(&ctl.fltset); 1351 0 stevel if ((pfd = open("/proc/self/status", O_RDONLY)) >= 0) { 1352 0 stevel if (read(pfd, &pstatus, sizeof (pstatus)) 1353 0 stevel == sizeof (pstatus)) 1354 0 stevel ctl.fltset = pstatus.pr_flttrace; 1355 0 stevel (void) close(pfd); 1356 0 stevel } 1357 0 stevel praddset(&ctl.fltset, FLTWATCH); 1358 0 stevel ctl.cmd = PCSFAULT; 1359 0 stevel (void) write(ctlfd, &ctl, sizeof (ctl)); 1360 0 stevel } 1361 0 stevel } 1362 0 stevel 1363 0 stevel static int 1364 0 stevel nowatch() 1365 0 stevel { 1366 0 stevel struct stat statb; 1367 0 stevel 1368 0 stevel if (dont_watch) 1369 0 stevel return (1); 1370 0 stevel if (ctlfd < 0) /* first time */ 1371 0 stevel init_watch(); 1372 0 stevel else if (fstat(ctlfd, &statb) != 0 || 1373 0 stevel statb.st_dev != ctlstatb.st_dev || 1374 0 stevel statb.st_ino != ctlstatb.st_ino) { 1375 0 stevel /* 1376 0 stevel * Someone closed our file descriptor. 1377 0 stevel * Just open another one. 1378 0 stevel */ 1379 0 stevel if ((ctlfd = open("/proc/self/ctl", O_WRONLY)) < 0 || 1380 0 stevel fstat(ctlfd, &ctlstatb) != 0) { 1381 0 stevel if (ctlfd >= 0) 1382 0 stevel (void) close(ctlfd); 1383 0 stevel ctlfd = -1; 1384 0 stevel dont_watch = 1; 1385 0 stevel return (1); 1386 0 stevel } 1387 0 stevel /* close-on-exec */ 1388 0 stevel (void) fcntl(ctlfd, F_SETFD, 1); 1389 0 stevel } 1390 0 stevel if (my_pid != getpid()) { 1391 0 stevel /* 1392 0 stevel * We fork()d since the last call to the allocator. 1393 0 stevel * watchpoints are not inherited across fork(). 1394 0 stevel * XXX: how to recover from this ??? 1395 0 stevel */ 1396 0 stevel dont_watch = 1; 1397 0 stevel (void) close(ctlfd); 1398 0 stevel ctlfd = -1; 1399 0 stevel } 1400 0 stevel return (dont_watch); 1401 0 stevel } 1402 0 stevel 1403 0 stevel static void 1404 0 stevel protect(TREE *tp) 1405 0 stevel { 1406 0 stevel ctl_t ctl; 1407 0 stevel size_t size, sz; 1408 0 stevel 1409 0 stevel if (nowatch()) 1410 0 stevel return; 1411 0 stevel if (tp == NULL || DATA(tp) == Baddr) 1412 0 stevel return; 1413 0 stevel 1414 0 stevel sz = size = SIZE(tp); 1415 0 stevel CLRBITS01(size); 1416 0 stevel if (size == 0) 1417 0 stevel return; 1418 0 stevel if (ISBIT0(sz)) /* block is busy, protect only the head */ 1419 0 stevel size = 0; 1420 0 stevel ctl.cmd = PCWATCH; 1421 0 stevel ctl.prwatch.pr_vaddr = (uintptr_t)tp; 1422 0 stevel ctl.prwatch.pr_size = size + WORDSIZE; 1423 0 stevel ctl.prwatch.pr_wflags = wflags; 1424 0 stevel (void) write(ctlfd, &ctl, sizeof (ctl)); 1425 0 stevel } 1426 0 stevel 1427 0 stevel static void 1428 0 stevel unprotect(TREE *tp) 1429 0 stevel { 1430 0 stevel ctl_t ctl; 1431 0 stevel 1432 0 stevel if (nowatch()) 1433 0 stevel return; 1434 0 stevel if (tp == NULL || DATA(tp) == Baddr) 1435 0 stevel return; 1436 0 stevel 1437 0 stevel ctl.cmd = PCWATCH; 1438 0 stevel ctl.prwatch.pr_vaddr = (uintptr_t)tp; 1439 0 stevel ctl.prwatch.pr_size = WORDSIZE; /* size is arbitrary */ 1440 0 stevel ctl.prwatch.pr_wflags = 0; /* clear the watched area */ 1441 0 stevel (void) write(ctlfd, &ctl, sizeof (ctl)); 1442 0 stevel } 1443 3866 raf 1444 3866 raf static void 1445 3866 raf malloc_prepare() 1446 3866 raf { 1447 3866 raf (void) mutex_lock(&__watch_malloc_lock); 1448 3866 raf } 1449 3866 raf 1450 3866 raf static void 1451 3866 raf malloc_release() 1452 3866 raf { 1453 3866 raf (void) mutex_unlock(&__watch_malloc_lock); 1454 3866 raf } 1455 3866 raf 1456 3866 raf #pragma init(malloc_init) 1457 3866 raf static void 1458 3866 raf malloc_init(void) 1459 3866 raf { 1460 3866 raf (void) pthread_atfork(malloc_prepare, malloc_release, malloc_release); 1461 3866 raf } 1462
Indexes created Sat Nov 28 14:09:03 UTC 2009
Terms of Use |
Privacy |
Trademarks |
Copyright Policy |
Site Guidelines |
Help
Your use of this web site or any of its content or software indicates your agreement to be bound by these Terms of Use.
Copyright © 1995-2008 Sun Microsystems, Inc.