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