17c478bd9Sstevel@tonic-gate /* 27c478bd9Sstevel@tonic-gate * CDDL HEADER START 37c478bd9Sstevel@tonic-gate * 47c478bd9Sstevel@tonic-gate * The contents of this file are subject to the terms of the 57c478bd9Sstevel@tonic-gate * Common Development and Distribution License, Version 1.0 only 67c478bd9Sstevel@tonic-gate * (the "License"). You may not use this file except in compliance 77c478bd9Sstevel@tonic-gate * with the License. 87c478bd9Sstevel@tonic-gate * 97c478bd9Sstevel@tonic-gate * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE 107c478bd9Sstevel@tonic-gate * or http://www.opensolaris.org/os/licensing. 117c478bd9Sstevel@tonic-gate * See the License for the specific language governing permissions 127c478bd9Sstevel@tonic-gate * and limitations under the License. 137c478bd9Sstevel@tonic-gate * 147c478bd9Sstevel@tonic-gate * When distributing Covered Code, include this CDDL HEADER in each 157c478bd9Sstevel@tonic-gate * file and include the License file at usr/src/OPENSOLARIS.LICENSE. 167c478bd9Sstevel@tonic-gate * If applicable, add the following below this CDDL HEADER, with the 177c478bd9Sstevel@tonic-gate * fields enclosed by brackets "[]" replaced with your own identifying 187c478bd9Sstevel@tonic-gate * information: Portions Copyright [yyyy] [name of copyright owner] 197c478bd9Sstevel@tonic-gate * 207c478bd9Sstevel@tonic-gate * CDDL HEADER END 217c478bd9Sstevel@tonic-gate */ 22*78b6ed60Scraigm 237c478bd9Sstevel@tonic-gate /* 24*78b6ed60Scraigm * Copyright 2001 Sun Microsystems, Inc. All rights reserved. 25*78b6ed60Scraigm * Use is subject to license terms. 267c478bd9Sstevel@tonic-gate */ 277c478bd9Sstevel@tonic-gate 287c478bd9Sstevel@tonic-gate /* Copyright (c) 1988 AT&T */ 297c478bd9Sstevel@tonic-gate /* All Rights Reserved */ 307c478bd9Sstevel@tonic-gate 31*78b6ed60Scraigm #pragma ident "%Z%%M% %I% %E% SMI" 327c478bd9Sstevel@tonic-gate 337c478bd9Sstevel@tonic-gate /* 347c478bd9Sstevel@tonic-gate * Memory management: malloc(), realloc(), free(), memalign(). 357c478bd9Sstevel@tonic-gate * 367c478bd9Sstevel@tonic-gate * The following #-parameters may be redefined: 377c478bd9Sstevel@tonic-gate * GETCORE: a function to get more core memory. 387c478bd9Sstevel@tonic-gate * GETCORE(0) is assumed to return the next available 397c478bd9Sstevel@tonic-gate * address. Default is 'sbrk'. 407c478bd9Sstevel@tonic-gate * ERRCORE: the error code as returned by GETCORE. 417c478bd9Sstevel@tonic-gate * Default is ((char *)(-1)). 427c478bd9Sstevel@tonic-gate * CORESIZE: a desired unit (measured in bytes) to be used 437c478bd9Sstevel@tonic-gate * with GETCORE. Default is (1024*ALIGN). 447c478bd9Sstevel@tonic-gate * 457c478bd9Sstevel@tonic-gate * This algorithm is based on a best fit strategy with lists of 467c478bd9Sstevel@tonic-gate * free elts maintained in a self-adjusting binary tree. Each list 477c478bd9Sstevel@tonic-gate * contains all elts of the same size. The tree is ordered by size. 487c478bd9Sstevel@tonic-gate * For results on self-adjusting trees, see the paper: 497c478bd9Sstevel@tonic-gate * Self-Adjusting Binary Trees, 507c478bd9Sstevel@tonic-gate * DD Sleator & RE Tarjan, JACM 1985. 517c478bd9Sstevel@tonic-gate * 527c478bd9Sstevel@tonic-gate * The header of a block contains the size of the data part in bytes. 537c478bd9Sstevel@tonic-gate * Since the size of a block is 0%4, the low two bits of the header 547c478bd9Sstevel@tonic-gate * are free and used as follows: 557c478bd9Sstevel@tonic-gate * 567c478bd9Sstevel@tonic-gate * BIT0: 1 for busy (block is in use), 0 for free. 577c478bd9Sstevel@tonic-gate * BIT1: if the block is busy, this bit is 1 if the 587c478bd9Sstevel@tonic-gate * preceding block in contiguous memory is free. 597c478bd9Sstevel@tonic-gate * Otherwise, it is always 0. 607c478bd9Sstevel@tonic-gate */ 617c478bd9Sstevel@tonic-gate 627c478bd9Sstevel@tonic-gate #include "mallint.h" 637c478bd9Sstevel@tonic-gate 647c478bd9Sstevel@tonic-gate static mutex_t __watch_malloc_lock = DEFAULTMUTEX; 657c478bd9Sstevel@tonic-gate 667c478bd9Sstevel@tonic-gate static TREE *Root; /* root of the free tree */ 677c478bd9Sstevel@tonic-gate static TREE *Bottom; /* the last free chunk in the arena */ 687c478bd9Sstevel@tonic-gate static char *Baddr; /* current high address of the arena */ 697c478bd9Sstevel@tonic-gate 707c478bd9Sstevel@tonic-gate static void t_delete(TREE *); 717c478bd9Sstevel@tonic-gate static void t_splay(TREE *); 727c478bd9Sstevel@tonic-gate static void realfree(void *); 737c478bd9Sstevel@tonic-gate static void *malloc_unlocked(size_t); 747c478bd9Sstevel@tonic-gate static void free_unlocked(void *); 757c478bd9Sstevel@tonic-gate static TREE *morecore(size_t); 767c478bd9Sstevel@tonic-gate 777c478bd9Sstevel@tonic-gate static void protect(TREE *); 787c478bd9Sstevel@tonic-gate static void unprotect(TREE *); 797c478bd9Sstevel@tonic-gate 807c478bd9Sstevel@tonic-gate #define FREEPAT 0 817c478bd9Sstevel@tonic-gate #define LIVEPAT 1 827c478bd9Sstevel@tonic-gate 837c478bd9Sstevel@tonic-gate /* 847c478bd9Sstevel@tonic-gate * Patterns to be copied into freed blocks and allocated blocks. 857c478bd9Sstevel@tonic-gate * 0xfeedbeef and 0xfeedface are invalid pointer values in all programs. 867c478bd9Sstevel@tonic-gate */ 877c478bd9Sstevel@tonic-gate static uint64_t patterns[2] = { 88*78b6ed60Scraigm 0xdeadbeefdeadbeefULL, /* pattern in a freed block */ 89*78b6ed60Scraigm 0xbaddcafebaddcafeULL /* pattern in an allocated block */ 907c478bd9Sstevel@tonic-gate }; 917c478bd9Sstevel@tonic-gate 927c478bd9Sstevel@tonic-gate static void 937c478bd9Sstevel@tonic-gate copy_pattern(int pat, TREE *tp) 947c478bd9Sstevel@tonic-gate { 957c478bd9Sstevel@tonic-gate uint64_t pattern = patterns[pat]; 967c478bd9Sstevel@tonic-gate size_t sz = SIZE(tp) / sizeof (uint64_t); 977c478bd9Sstevel@tonic-gate /* LINTED improper alignment */ 987c478bd9Sstevel@tonic-gate uint64_t *datap = (uint64_t *)DATA(tp); 997c478bd9Sstevel@tonic-gate 1007c478bd9Sstevel@tonic-gate while (sz--) 1017c478bd9Sstevel@tonic-gate *datap++ = pattern; 1027c478bd9Sstevel@tonic-gate } 1037c478bd9Sstevel@tonic-gate 1047c478bd9Sstevel@tonic-gate /* 1057c478bd9Sstevel@tonic-gate * Keep lists of small blocks, LIFO order. 1067c478bd9Sstevel@tonic-gate */ 1077c478bd9Sstevel@tonic-gate static TREE *List[MINSIZE/WORDSIZE-1]; 1087c478bd9Sstevel@tonic-gate static TREE *Last[MINSIZE/WORDSIZE-1]; 1097c478bd9Sstevel@tonic-gate 1107c478bd9Sstevel@tonic-gate /* number of blocks to get at one time */ 1117c478bd9Sstevel@tonic-gate #define NPS (WORDSIZE*8) 1127c478bd9Sstevel@tonic-gate 1137c478bd9Sstevel@tonic-gate static void * 1147c478bd9Sstevel@tonic-gate smalloc(size_t size) 1157c478bd9Sstevel@tonic-gate { 1167c478bd9Sstevel@tonic-gate TREE *tp; 1177c478bd9Sstevel@tonic-gate size_t i; 1187c478bd9Sstevel@tonic-gate 1197c478bd9Sstevel@tonic-gate ASSERT(size % WORDSIZE == 0); 1207c478bd9Sstevel@tonic-gate /* want to return a unique pointer on malloc(0) */ 1217c478bd9Sstevel@tonic-gate if (size == 0) 1227c478bd9Sstevel@tonic-gate size = WORDSIZE; 1237c478bd9Sstevel@tonic-gate 1247c478bd9Sstevel@tonic-gate /* list to use */ 1257c478bd9Sstevel@tonic-gate i = size / WORDSIZE - 1; 1267c478bd9Sstevel@tonic-gate 1277c478bd9Sstevel@tonic-gate if (List[i] == NULL) { 1287c478bd9Sstevel@tonic-gate TREE *np; 1297c478bd9Sstevel@tonic-gate int n; 1307c478bd9Sstevel@tonic-gate ASSERT((size + WORDSIZE) * NPS >= MINSIZE); 1317c478bd9Sstevel@tonic-gate 1327c478bd9Sstevel@tonic-gate /* get NPS of these block types */ 1337c478bd9Sstevel@tonic-gate if ((np = malloc_unlocked((size + WORDSIZE)*NPS)) == NULL) 1347c478bd9Sstevel@tonic-gate return (NULL); 1357c478bd9Sstevel@tonic-gate 1367c478bd9Sstevel@tonic-gate /* make them into a link list */ 1377c478bd9Sstevel@tonic-gate for (n = 0, List[i] = np; n < NPS; ++n) { 1387c478bd9Sstevel@tonic-gate tp = np; 1397c478bd9Sstevel@tonic-gate SIZE(tp) = size; 1407c478bd9Sstevel@tonic-gate copy_pattern(FREEPAT, tp); 1417c478bd9Sstevel@tonic-gate if (n == NPS - 1) { 1427c478bd9Sstevel@tonic-gate Last[i] = tp; 1437c478bd9Sstevel@tonic-gate np = NULL; 1447c478bd9Sstevel@tonic-gate } else { 1457c478bd9Sstevel@tonic-gate /* LINTED improper alignment */ 1467c478bd9Sstevel@tonic-gate np = NEXT(tp); 1477c478bd9Sstevel@tonic-gate } 1487c478bd9Sstevel@tonic-gate AFTER(tp) = np; 1497c478bd9Sstevel@tonic-gate protect(tp); 1507c478bd9Sstevel@tonic-gate } 1517c478bd9Sstevel@tonic-gate } 1527c478bd9Sstevel@tonic-gate 1537c478bd9Sstevel@tonic-gate /* allocate from the head of the queue */ 1547c478bd9Sstevel@tonic-gate tp = List[i]; 1557c478bd9Sstevel@tonic-gate unprotect(tp); 1567c478bd9Sstevel@tonic-gate if ((List[i] = AFTER(tp)) == NULL) 1577c478bd9Sstevel@tonic-gate Last[i] = NULL; 1587c478bd9Sstevel@tonic-gate copy_pattern(LIVEPAT, tp); 1597c478bd9Sstevel@tonic-gate SETBIT0(SIZE(tp)); 1607c478bd9Sstevel@tonic-gate protect(tp); 1617c478bd9Sstevel@tonic-gate return (DATA(tp)); 1627c478bd9Sstevel@tonic-gate } 1637c478bd9Sstevel@tonic-gate 1647c478bd9Sstevel@tonic-gate void * 1657c478bd9Sstevel@tonic-gate malloc(size_t size) 1667c478bd9Sstevel@tonic-gate { 1677c478bd9Sstevel@tonic-gate void *ret; 1687c478bd9Sstevel@tonic-gate _mutex_lock(&__watch_malloc_lock); 1697c478bd9Sstevel@tonic-gate ret = malloc_unlocked(size); 1707c478bd9Sstevel@tonic-gate _mutex_unlock(&__watch_malloc_lock); 1717c478bd9Sstevel@tonic-gate return (ret); 1727c478bd9Sstevel@tonic-gate } 1737c478bd9Sstevel@tonic-gate 1747c478bd9Sstevel@tonic-gate static void * 1757c478bd9Sstevel@tonic-gate malloc_unlocked(size_t size) 1767c478bd9Sstevel@tonic-gate { 1777c478bd9Sstevel@tonic-gate size_t n; 1787c478bd9Sstevel@tonic-gate TREE *tp, *sp, *tmp; 1797c478bd9Sstevel@tonic-gate 1807c478bd9Sstevel@tonic-gate COUNT(nmalloc); 1817c478bd9Sstevel@tonic-gate ASSERT(WORDSIZE == ALIGN); 1827c478bd9Sstevel@tonic-gate 1837c478bd9Sstevel@tonic-gate /* check for size that could overflow calculations */ 1847c478bd9Sstevel@tonic-gate if (size > MAX_MALLOC) { 1857c478bd9Sstevel@tonic-gate errno = ENOMEM; 1867c478bd9Sstevel@tonic-gate return (NULL); 1877c478bd9Sstevel@tonic-gate } 1887c478bd9Sstevel@tonic-gate /* make sure that size is 0 mod ALIGN */ 1897c478bd9Sstevel@tonic-gate ROUND(size); 1907c478bd9Sstevel@tonic-gate 1917c478bd9Sstevel@tonic-gate /* small blocks */ 1927c478bd9Sstevel@tonic-gate if (size < MINSIZE) 1937c478bd9Sstevel@tonic-gate return (smalloc(size)); 1947c478bd9Sstevel@tonic-gate 1957c478bd9Sstevel@tonic-gate /* search for an elt of the right size */ 1967c478bd9Sstevel@tonic-gate sp = NULL; 1977c478bd9Sstevel@tonic-gate n = 0; 1987c478bd9Sstevel@tonic-gate if (Root) { 1997c478bd9Sstevel@tonic-gate tp = Root; 2007c478bd9Sstevel@tonic-gate for (;;) { 2017c478bd9Sstevel@tonic-gate unprotect(tp); 2027c478bd9Sstevel@tonic-gate if (SIZE(tp) >= size) { /* branch left */ 2037c478bd9Sstevel@tonic-gate if (n == 0 || n >= SIZE(tp)) { 2047c478bd9Sstevel@tonic-gate sp = tp; 2057c478bd9Sstevel@tonic-gate n = SIZE(tp); 2067c478bd9Sstevel@tonic-gate } 2077c478bd9Sstevel@tonic-gate if ((tmp = LEFT(tp)) != NULL) { 2087c478bd9Sstevel@tonic-gate protect(tp); 2097c478bd9Sstevel@tonic-gate tp = tmp; 2107c478bd9Sstevel@tonic-gate } else { 2117c478bd9Sstevel@tonic-gate protect(tp); 2127c478bd9Sstevel@tonic-gate break; 2137c478bd9Sstevel@tonic-gate } 2147c478bd9Sstevel@tonic-gate } else { /* branch right */ 2157c478bd9Sstevel@tonic-gate if ((tmp = RIGHT(tp)) != NULL) { 2167c478bd9Sstevel@tonic-gate protect(tp); 2177c478bd9Sstevel@tonic-gate tp = tmp; 2187c478bd9Sstevel@tonic-gate } else { 2197c478bd9Sstevel@tonic-gate protect(tp); 2207c478bd9Sstevel@tonic-gate break; 2217c478bd9Sstevel@tonic-gate } 2227c478bd9Sstevel@tonic-gate } 2237c478bd9Sstevel@tonic-gate } 2247c478bd9Sstevel@tonic-gate 2257c478bd9Sstevel@tonic-gate if (sp) { 2267c478bd9Sstevel@tonic-gate unprotect(sp); 2277c478bd9Sstevel@tonic-gate t_delete(sp); 2287c478bd9Sstevel@tonic-gate } else if (tp != Root) { 2297c478bd9Sstevel@tonic-gate /* make the searched-to element the root */ 2307c478bd9Sstevel@tonic-gate unprotect(tp); 2317c478bd9Sstevel@tonic-gate t_splay(tp); 2327c478bd9Sstevel@tonic-gate protect(tp); 2337c478bd9Sstevel@tonic-gate Root = tp; 2347c478bd9Sstevel@tonic-gate } 2357c478bd9Sstevel@tonic-gate } 2367c478bd9Sstevel@tonic-gate 2377c478bd9Sstevel@tonic-gate /* if found none fitted in the tree */ 2387c478bd9Sstevel@tonic-gate if (sp == NULL) { 2397c478bd9Sstevel@tonic-gate if (Bottom) { 2407c478bd9Sstevel@tonic-gate unprotect(Bottom); 2417c478bd9Sstevel@tonic-gate if (size <= SIZE(Bottom)) { 2427c478bd9Sstevel@tonic-gate sp = Bottom; 2437c478bd9Sstevel@tonic-gate CLRBITS01(SIZE(sp)); 2447c478bd9Sstevel@tonic-gate } else { 2457c478bd9Sstevel@tonic-gate protect(Bottom); 2467c478bd9Sstevel@tonic-gate if ((sp = morecore(size)) == NULL) 2477c478bd9Sstevel@tonic-gate return (NULL); 2487c478bd9Sstevel@tonic-gate } 2497c478bd9Sstevel@tonic-gate } else { 2507c478bd9Sstevel@tonic-gate if ((sp = morecore(size)) == NULL) 2517c478bd9Sstevel@tonic-gate return (NULL); 2527c478bd9Sstevel@tonic-gate } 2537c478bd9Sstevel@tonic-gate } 2547c478bd9Sstevel@tonic-gate 2557c478bd9Sstevel@tonic-gate /* tell the forward neighbor that we're busy */ 2567c478bd9Sstevel@tonic-gate /* LINTED improper alignment */ 2577c478bd9Sstevel@tonic-gate tmp = NEXT(sp); 2587c478bd9Sstevel@tonic-gate unprotect(tmp); 2597c478bd9Sstevel@tonic-gate CLRBIT1(SIZE(tmp)); 2607c478bd9Sstevel@tonic-gate ASSERT(ISBIT0(SIZE(tmp))); 2617c478bd9Sstevel@tonic-gate protect(tmp); 2627c478bd9Sstevel@tonic-gate 2637c478bd9Sstevel@tonic-gate leftover: 2647c478bd9Sstevel@tonic-gate /* if the leftover is enough for a new free piece */ 2657c478bd9Sstevel@tonic-gate if ((n = (SIZE(sp) - size)) >= MINSIZE + WORDSIZE) { 2667c478bd9Sstevel@tonic-gate n -= WORDSIZE; 2677c478bd9Sstevel@tonic-gate SIZE(sp) = size; 2687c478bd9Sstevel@tonic-gate /* LINTED improper alignment */ 2697c478bd9Sstevel@tonic-gate tp = NEXT(sp); 2707c478bd9Sstevel@tonic-gate SIZE(tp) = n | BIT0; 2717c478bd9Sstevel@tonic-gate realfree(DATA(tp)); 2727c478bd9Sstevel@tonic-gate } else if (BOTTOM(sp)) 2737c478bd9Sstevel@tonic-gate Bottom = NULL; 2747c478bd9Sstevel@tonic-gate 2757c478bd9Sstevel@tonic-gate /* return the allocated space */ 2767c478bd9Sstevel@tonic-gate copy_pattern(LIVEPAT, sp); 2777c478bd9Sstevel@tonic-gate SIZE(sp) |= BIT0; 2787c478bd9Sstevel@tonic-gate protect(sp); 2797c478bd9Sstevel@tonic-gate return (DATA(sp)); 2807c478bd9Sstevel@tonic-gate } 2817c478bd9Sstevel@tonic-gate 2827c478bd9Sstevel@tonic-gate /* 2837c478bd9Sstevel@tonic-gate * realloc(). 2847c478bd9Sstevel@tonic-gate * If the block size is increasing, we try forward merging first. 2857c478bd9Sstevel@tonic-gate * This is not best-fit but it avoids some data recopying. 2867c478bd9Sstevel@tonic-gate */ 2877c478bd9Sstevel@tonic-gate void * 2887c478bd9Sstevel@tonic-gate realloc(void *old, size_t size) 2897c478bd9Sstevel@tonic-gate { 2907c478bd9Sstevel@tonic-gate TREE *tp, *np; 2917c478bd9Sstevel@tonic-gate size_t ts; 2927c478bd9Sstevel@tonic-gate char *new; 2937c478bd9Sstevel@tonic-gate 2947c478bd9Sstevel@tonic-gate COUNT(nrealloc); 2957c478bd9Sstevel@tonic-gate 2967c478bd9Sstevel@tonic-gate /* check for size that could overflow calculations */ 2977c478bd9Sstevel@tonic-gate if (size > MAX_MALLOC) { 2987c478bd9Sstevel@tonic-gate errno = ENOMEM; 2997c478bd9Sstevel@tonic-gate return (NULL); 3007c478bd9Sstevel@tonic-gate } 3017c478bd9Sstevel@tonic-gate 3027c478bd9Sstevel@tonic-gate /* pointer to the block */ 3037c478bd9Sstevel@tonic-gate _mutex_lock(&__watch_malloc_lock); 3047c478bd9Sstevel@tonic-gate if (old == NULL) { 3057c478bd9Sstevel@tonic-gate new = malloc_unlocked(size); 3067c478bd9Sstevel@tonic-gate _mutex_unlock(&__watch_malloc_lock); 3077c478bd9Sstevel@tonic-gate return (new); 3087c478bd9Sstevel@tonic-gate } 3097c478bd9Sstevel@tonic-gate 3107c478bd9Sstevel@tonic-gate /* make sure that size is 0 mod ALIGN */ 3117c478bd9Sstevel@tonic-gate ROUND(size); 3127c478bd9Sstevel@tonic-gate 3137c478bd9Sstevel@tonic-gate /* LINTED improper alignment */ 3147c478bd9Sstevel@tonic-gate tp = BLOCK(old); 3157c478bd9Sstevel@tonic-gate unprotect(tp); 3167c478bd9Sstevel@tonic-gate ts = SIZE(tp); 3177c478bd9Sstevel@tonic-gate 3187c478bd9Sstevel@tonic-gate /* if the block was freed, data has been destroyed. */ 3197c478bd9Sstevel@tonic-gate if (!ISBIT0(ts)) { 3207c478bd9Sstevel@tonic-gate /* XXX; complain here! */ 3217c478bd9Sstevel@tonic-gate protect(tp); 3227c478bd9Sstevel@tonic-gate _mutex_unlock(&__watch_malloc_lock); 3237c478bd9Sstevel@tonic-gate errno = EINVAL; 3247c478bd9Sstevel@tonic-gate return (NULL); 3257c478bd9Sstevel@tonic-gate } 3267c478bd9Sstevel@tonic-gate 3277c478bd9Sstevel@tonic-gate CLRBITS01(SIZE(tp)); 3287c478bd9Sstevel@tonic-gate if (size == SIZE(tp)) { /* nothing to do */ 3297c478bd9Sstevel@tonic-gate SIZE(tp) = ts; 3307c478bd9Sstevel@tonic-gate protect(tp); 3317c478bd9Sstevel@tonic-gate _mutex_unlock(&__watch_malloc_lock); 3327c478bd9Sstevel@tonic-gate return (old); 3337c478bd9Sstevel@tonic-gate } 3347c478bd9Sstevel@tonic-gate 3357c478bd9Sstevel@tonic-gate /* special cases involving small blocks */ 3367c478bd9Sstevel@tonic-gate if (size < MINSIZE || SIZE(tp) < MINSIZE) { 3377c478bd9Sstevel@tonic-gate if (size == 0) { 3387c478bd9Sstevel@tonic-gate SETOLD01(SIZE(tp), ts); 3397c478bd9Sstevel@tonic-gate free_unlocked(old); 3407c478bd9Sstevel@tonic-gate _mutex_unlock(&__watch_malloc_lock); 3417c478bd9Sstevel@tonic-gate return (NULL); 3427c478bd9Sstevel@tonic-gate } 3437c478bd9Sstevel@tonic-gate goto call_malloc; 3447c478bd9Sstevel@tonic-gate } 3457c478bd9Sstevel@tonic-gate 3467c478bd9Sstevel@tonic-gate /* block is increasing in size, try merging the next block */ 3477c478bd9Sstevel@tonic-gate if (size > SIZE(tp)) { 3487c478bd9Sstevel@tonic-gate /* LINTED improper alignment */ 3497c478bd9Sstevel@tonic-gate np = NEXT(tp); 3507c478bd9Sstevel@tonic-gate unprotect(np); 3517c478bd9Sstevel@tonic-gate if (ISBIT0(SIZE(np))) 3527c478bd9Sstevel@tonic-gate protect(np); 3537c478bd9Sstevel@tonic-gate else { 3547c478bd9Sstevel@tonic-gate TREE *tmp; 3557c478bd9Sstevel@tonic-gate ASSERT(SIZE(np) >= MINSIZE); 3567c478bd9Sstevel@tonic-gate ASSERT(!ISBIT1(SIZE(np))); 3577c478bd9Sstevel@tonic-gate SIZE(tp) += SIZE(np) + WORDSIZE; 3587c478bd9Sstevel@tonic-gate if (np != Bottom) 3597c478bd9Sstevel@tonic-gate t_delete(np); 3607c478bd9Sstevel@tonic-gate else 3617c478bd9Sstevel@tonic-gate Bottom = NULL; 3627c478bd9Sstevel@tonic-gate /* LINTED improper alignment */ 3637c478bd9Sstevel@tonic-gate tmp = NEXT(np); 3647c478bd9Sstevel@tonic-gate unprotect(tmp); 3657c478bd9Sstevel@tonic-gate CLRBIT1(SIZE(tmp)); 3667c478bd9Sstevel@tonic-gate protect(tmp); 3677c478bd9Sstevel@tonic-gate } 3687c478bd9Sstevel@tonic-gate 3697c478bd9Sstevel@tonic-gate /* not enough & at TRUE end of memory, try extending core */ 3707c478bd9Sstevel@tonic-gate if (size > SIZE(tp) && BOTTOM(tp) && GETCORE(0) == Baddr) { 3717c478bd9Sstevel@tonic-gate Bottom = tp; 3727c478bd9Sstevel@tonic-gate protect(Bottom); 3737c478bd9Sstevel@tonic-gate if ((tp = morecore(size)) == NULL) { 3747c478bd9Sstevel@tonic-gate tp = Bottom; 3757c478bd9Sstevel@tonic-gate Bottom = NULL; 3767c478bd9Sstevel@tonic-gate unprotect(tp); 3777c478bd9Sstevel@tonic-gate } 3787c478bd9Sstevel@tonic-gate } 3797c478bd9Sstevel@tonic-gate } 3807c478bd9Sstevel@tonic-gate 3817c478bd9Sstevel@tonic-gate /* got enough space to use */ 3827c478bd9Sstevel@tonic-gate if (size <= SIZE(tp)) { 3837c478bd9Sstevel@tonic-gate size_t n; 3847c478bd9Sstevel@tonic-gate chop_big: 3857c478bd9Sstevel@tonic-gate if ((n = (SIZE(tp) - size)) >= MINSIZE + WORDSIZE) { 3867c478bd9Sstevel@tonic-gate n -= WORDSIZE; 3877c478bd9Sstevel@tonic-gate SIZE(tp) = size; 3887c478bd9Sstevel@tonic-gate /* LINTED improper alignment */ 3897c478bd9Sstevel@tonic-gate np = NEXT(tp); 3907c478bd9Sstevel@tonic-gate SIZE(np) = n | BIT0; 3917c478bd9Sstevel@tonic-gate realfree(DATA(np)); 3927c478bd9Sstevel@tonic-gate } else if (BOTTOM(tp)) 3937c478bd9Sstevel@tonic-gate Bottom = NULL; 3947c478bd9Sstevel@tonic-gate 3957c478bd9Sstevel@tonic-gate /* the previous block may be free */ 3967c478bd9Sstevel@tonic-gate SETOLD01(SIZE(tp), ts); 3977c478bd9Sstevel@tonic-gate protect(tp); 3987c478bd9Sstevel@tonic-gate _mutex_unlock(&__watch_malloc_lock); 3997c478bd9Sstevel@tonic-gate return (old); 4007c478bd9Sstevel@tonic-gate } 4017c478bd9Sstevel@tonic-gate 4027c478bd9Sstevel@tonic-gate call_malloc: /* call malloc to get a new block */ 4037c478bd9Sstevel@tonic-gate SETOLD01(SIZE(tp), ts); 4047c478bd9Sstevel@tonic-gate if ((new = malloc_unlocked(size)) != NULL) { 4057c478bd9Sstevel@tonic-gate CLRBITS01(ts); 4067c478bd9Sstevel@tonic-gate if (ts > size) 4077c478bd9Sstevel@tonic-gate ts = size; 4087c478bd9Sstevel@tonic-gate (void) memcpy(new, old, ts); 4097c478bd9Sstevel@tonic-gate free_unlocked(old); 4107c478bd9Sstevel@tonic-gate _mutex_unlock(&__watch_malloc_lock); 4117c478bd9Sstevel@tonic-gate return (new); 4127c478bd9Sstevel@tonic-gate } 4137c478bd9Sstevel@tonic-gate 4147c478bd9Sstevel@tonic-gate /* 4157c478bd9Sstevel@tonic-gate * Attempt special case recovery allocations since malloc() failed: 4167c478bd9Sstevel@tonic-gate * 4177c478bd9Sstevel@tonic-gate * 1. size <= SIZE(tp) < MINSIZE 4187c478bd9Sstevel@tonic-gate * Simply return the existing block 4197c478bd9Sstevel@tonic-gate * 2. SIZE(tp) < size < MINSIZE 4207c478bd9Sstevel@tonic-gate * malloc() may have failed to allocate the chunk of 4217c478bd9Sstevel@tonic-gate * small blocks. Try asking for MINSIZE bytes. 4227c478bd9Sstevel@tonic-gate * 3. size < MINSIZE <= SIZE(tp) 4237c478bd9Sstevel@tonic-gate * malloc() may have failed as with 2. Change to 4247c478bd9Sstevel@tonic-gate * MINSIZE allocation which is taken from the beginning 4257c478bd9Sstevel@tonic-gate * of the current block. 4267c478bd9Sstevel@tonic-gate * 4. MINSIZE <= SIZE(tp) < size 4277c478bd9Sstevel@tonic-gate * If the previous block is free and the combination of 4287c478bd9Sstevel@tonic-gate * these two blocks has at least size bytes, then merge 4297c478bd9Sstevel@tonic-gate * the two blocks copying the existing contents backwards. 4307c478bd9Sstevel@tonic-gate */ 4317c478bd9Sstevel@tonic-gate CLRBITS01(SIZE(tp)); 4327c478bd9Sstevel@tonic-gate if (SIZE(tp) < MINSIZE) { 4337c478bd9Sstevel@tonic-gate if (size < SIZE(tp)) /* case 1. */ { 4347c478bd9Sstevel@tonic-gate SETOLD01(SIZE(tp), ts); 4357c478bd9Sstevel@tonic-gate protect(tp); 4367c478bd9Sstevel@tonic-gate _mutex_unlock(&__watch_malloc_lock); 4377c478bd9Sstevel@tonic-gate return (old); 4387c478bd9Sstevel@tonic-gate } else if (size < MINSIZE) /* case 2. */ { 4397c478bd9Sstevel@tonic-gate size = MINSIZE; 4407c478bd9Sstevel@tonic-gate goto call_malloc; 4417c478bd9Sstevel@tonic-gate } 4427c478bd9Sstevel@tonic-gate } else if (size < MINSIZE) /* case 3. */ { 4437c478bd9Sstevel@tonic-gate size = MINSIZE; 4447c478bd9Sstevel@tonic-gate goto chop_big; 4457c478bd9Sstevel@tonic-gate } else if (ISBIT1(ts)) { 4467c478bd9Sstevel@tonic-gate np = LAST(tp); 4477c478bd9Sstevel@tonic-gate unprotect(np); 4487c478bd9Sstevel@tonic-gate if ((SIZE(np) + SIZE(tp) + WORDSIZE) >= size) { 4497c478bd9Sstevel@tonic-gate ASSERT(!ISBIT0(SIZE(np))); 4507c478bd9Sstevel@tonic-gate t_delete(np); 4517c478bd9Sstevel@tonic-gate SIZE(np) += SIZE(tp) + WORDSIZE; 4527c478bd9Sstevel@tonic-gate /* 4537c478bd9Sstevel@tonic-gate * Since the copy may overlap, use memmove(). 4547c478bd9Sstevel@tonic-gate */ 4557c478bd9Sstevel@tonic-gate (void) memmove(DATA(np), old, SIZE(tp)); 4567c478bd9Sstevel@tonic-gate old = DATA(np); 4577c478bd9Sstevel@tonic-gate tp = np; 4587c478bd9Sstevel@tonic-gate CLRBIT1(ts); 4597c478bd9Sstevel@tonic-gate goto chop_big; 4607c478bd9Sstevel@tonic-gate } 4617c478bd9Sstevel@tonic-gate protect(np); 4627c478bd9Sstevel@tonic-gate } 4637c478bd9Sstevel@tonic-gate SETOLD01(SIZE(tp), ts); 4647c478bd9Sstevel@tonic-gate protect(tp); 4657c478bd9Sstevel@tonic-gate _mutex_unlock(&__watch_malloc_lock); 4667c478bd9Sstevel@tonic-gate /* malloc() sets errno */ 4677c478bd9Sstevel@tonic-gate return (NULL); 4687c478bd9Sstevel@tonic-gate } 4697c478bd9Sstevel@tonic-gate 4707c478bd9Sstevel@tonic-gate /* 4717c478bd9Sstevel@tonic-gate * realfree(). 4727c478bd9Sstevel@tonic-gate * Coalescing of adjacent free blocks is done first. 4737c478bd9Sstevel@tonic-gate * Then, the new free block is leaf-inserted into the free tree 4747c478bd9Sstevel@tonic-gate * without splaying. This strategy does not guarantee the amortized 4757c478bd9Sstevel@tonic-gate * O(nlogn) behaviour for the insert/delete/find set of operations 4767c478bd9Sstevel@tonic-gate * on the tree. In practice, however, free is much more infrequent 4777c478bd9Sstevel@tonic-gate * than malloc/realloc and the tree searches performed by these 4787c478bd9Sstevel@tonic-gate * functions adequately keep the tree in balance. 4797c478bd9Sstevel@tonic-gate */ 4807c478bd9Sstevel@tonic-gate static void 4817c478bd9Sstevel@tonic-gate realfree(void *old) 4827c478bd9Sstevel@tonic-gate { 4837c478bd9Sstevel@tonic-gate TREE *tp, *sp, *np, *tmp; 4847c478bd9Sstevel@tonic-gate size_t ts, size; 4857c478bd9Sstevel@tonic-gate 4867c478bd9Sstevel@tonic-gate COUNT(nfree); 4877c478bd9Sstevel@tonic-gate 4887c478bd9Sstevel@tonic-gate /* pointer to the block */ 4897c478bd9Sstevel@tonic-gate /* LINTED improper alignment */ 4907c478bd9Sstevel@tonic-gate tp = BLOCK(old); 4917c478bd9Sstevel@tonic-gate unprotect(tp); 4927c478bd9Sstevel@tonic-gate ts = SIZE(tp); 4937c478bd9Sstevel@tonic-gate if (!ISBIT0(ts)) { /* block is not busy; previously freed? */ 4947c478bd9Sstevel@tonic-gate protect(tp); /* force a watchpoint trap */ 4957c478bd9Sstevel@tonic-gate CLRBIT0(SIZE(tp)); 4967c478bd9Sstevel@tonic-gate return; 4977c478bd9Sstevel@tonic-gate } 4987c478bd9Sstevel@tonic-gate CLRBITS01(SIZE(tp)); 4997c478bd9Sstevel@tonic-gate copy_pattern(FREEPAT, tp); 5007c478bd9Sstevel@tonic-gate 5017c478bd9Sstevel@tonic-gate /* small block, return it to the tail of its queue */ 5027c478bd9Sstevel@tonic-gate if (SIZE(tp) < MINSIZE) { 5037c478bd9Sstevel@tonic-gate ASSERT(SIZE(tp) / WORDSIZE >= 1); 5047c478bd9Sstevel@tonic-gate ts = SIZE(tp) / WORDSIZE - 1; 5057c478bd9Sstevel@tonic-gate AFTER(tp) = NULL; 5067c478bd9Sstevel@tonic-gate protect(tp); 5077c478bd9Sstevel@tonic-gate if (List[ts] == NULL) { 5087c478bd9Sstevel@tonic-gate List[ts] = tp; 5097c478bd9Sstevel@tonic-gate Last[ts] = tp; 5107c478bd9Sstevel@tonic-gate } else { 5117c478bd9Sstevel@tonic-gate sp = Last[ts]; 5127c478bd9Sstevel@tonic-gate unprotect(sp); 5137c478bd9Sstevel@tonic-gate AFTER(sp) = tp; 5147c478bd9Sstevel@tonic-gate protect(sp); 5157c478bd9Sstevel@tonic-gate Last[ts] = tp; 5167c478bd9Sstevel@tonic-gate } 5177c478bd9Sstevel@tonic-gate return; 5187c478bd9Sstevel@tonic-gate } 5197c478bd9Sstevel@tonic-gate 5207c478bd9Sstevel@tonic-gate /* see if coalescing with next block is warranted */ 5217c478bd9Sstevel@tonic-gate /* LINTED improper alignment */ 5227c478bd9Sstevel@tonic-gate np = NEXT(tp); 5237c478bd9Sstevel@tonic-gate unprotect(np); 5247c478bd9Sstevel@tonic-gate if (ISBIT0(SIZE(np))) 5257c478bd9Sstevel@tonic-gate protect(np); 5267c478bd9Sstevel@tonic-gate else { 5277c478bd9Sstevel@tonic-gate if (np != Bottom) 5287c478bd9Sstevel@tonic-gate t_delete(np); 5297c478bd9Sstevel@tonic-gate SIZE(tp) += SIZE(np) + WORDSIZE; 5307c478bd9Sstevel@tonic-gate } 5317c478bd9Sstevel@tonic-gate 5327c478bd9Sstevel@tonic-gate /* the same with the preceding block */ 5337c478bd9Sstevel@tonic-gate if (ISBIT1(ts)) { 5347c478bd9Sstevel@tonic-gate np = LAST(tp); 5357c478bd9Sstevel@tonic-gate unprotect(np); 5367c478bd9Sstevel@tonic-gate ASSERT(!ISBIT0(SIZE(np))); 5377c478bd9Sstevel@tonic-gate ASSERT(np != Bottom); 5387c478bd9Sstevel@tonic-gate t_delete(np); 5397c478bd9Sstevel@tonic-gate SIZE(np) += SIZE(tp) + WORDSIZE; 5407c478bd9Sstevel@tonic-gate tp = np; 5417c478bd9Sstevel@tonic-gate } 5427c478bd9Sstevel@tonic-gate 5437c478bd9Sstevel@tonic-gate /* initialize tree info */ 5447c478bd9Sstevel@tonic-gate PARENT(tp) = LEFT(tp) = RIGHT(tp) = LINKFOR(tp) = NULL; 5457c478bd9Sstevel@tonic-gate 5467c478bd9Sstevel@tonic-gate /* set bottom block, or insert in the free tree */ 5477c478bd9Sstevel@tonic-gate if (BOTTOM(tp)) 5487c478bd9Sstevel@tonic-gate Bottom = tp; 5497c478bd9Sstevel@tonic-gate else { 5507c478bd9Sstevel@tonic-gate /* search for the place to insert */ 5517c478bd9Sstevel@tonic-gate if (Root) { 5527c478bd9Sstevel@tonic-gate size = SIZE(tp); 5537c478bd9Sstevel@tonic-gate np = Root; 5547c478bd9Sstevel@tonic-gate for (;;) { 5557c478bd9Sstevel@tonic-gate unprotect(np); 5567c478bd9Sstevel@tonic-gate if (SIZE(np) > size) { 5577c478bd9Sstevel@tonic-gate if ((tmp = LEFT(np)) != NULL) { 5587c478bd9Sstevel@tonic-gate protect(np); 5597c478bd9Sstevel@tonic-gate np = tmp; 5607c478bd9Sstevel@tonic-gate } else { 5617c478bd9Sstevel@tonic-gate LEFT(np) = tp; 5627c478bd9Sstevel@tonic-gate PARENT(tp) = np; 5637c478bd9Sstevel@tonic-gate protect(np); 5647c478bd9Sstevel@tonic-gate break; 5657c478bd9Sstevel@tonic-gate } 5667c478bd9Sstevel@tonic-gate } else if (SIZE(np) < size) { 5677c478bd9Sstevel@tonic-gate if ((tmp = RIGHT(np)) != NULL) { 5687c478bd9Sstevel@tonic-gate protect(np); 5697c478bd9Sstevel@tonic-gate np = tmp; 5707c478bd9Sstevel@tonic-gate } else { 5717c478bd9Sstevel@tonic-gate RIGHT(np) = tp; 5727c478bd9Sstevel@tonic-gate PARENT(tp) = np; 5737c478bd9Sstevel@tonic-gate protect(np); 5747c478bd9Sstevel@tonic-gate break; 5757c478bd9Sstevel@tonic-gate } 5767c478bd9Sstevel@tonic-gate } else { 5777c478bd9Sstevel@tonic-gate if ((sp = PARENT(np)) != NULL) { 5787c478bd9Sstevel@tonic-gate unprotect(sp); 5797c478bd9Sstevel@tonic-gate if (np == LEFT(sp)) 5807c478bd9Sstevel@tonic-gate LEFT(sp) = tp; 5817c478bd9Sstevel@tonic-gate else 5827c478bd9Sstevel@tonic-gate RIGHT(sp) = tp; 5837c478bd9Sstevel@tonic-gate PARENT(tp) = sp; 5847c478bd9Sstevel@tonic-gate protect(sp); 5857c478bd9Sstevel@tonic-gate } else 5867c478bd9Sstevel@tonic-gate Root = tp; 5877c478bd9Sstevel@tonic-gate 5887c478bd9Sstevel@tonic-gate /* insert to head of list */ 5897c478bd9Sstevel@tonic-gate if ((sp = LEFT(np)) != NULL) { 5907c478bd9Sstevel@tonic-gate unprotect(sp); 5917c478bd9Sstevel@tonic-gate PARENT(sp) = tp; 5927c478bd9Sstevel@tonic-gate protect(sp); 5937c478bd9Sstevel@tonic-gate } 5947c478bd9Sstevel@tonic-gate LEFT(tp) = sp; 5957c478bd9Sstevel@tonic-gate 5967c478bd9Sstevel@tonic-gate if ((sp = RIGHT(np)) != NULL) { 5977c478bd9Sstevel@tonic-gate unprotect(sp); 5987c478bd9Sstevel@tonic-gate PARENT(sp) = tp; 5997c478bd9Sstevel@tonic-gate protect(sp); 6007c478bd9Sstevel@tonic-gate } 6017c478bd9Sstevel@tonic-gate RIGHT(tp) = sp; 6027c478bd9Sstevel@tonic-gate 6037c478bd9Sstevel@tonic-gate /* doubly link list */ 6047c478bd9Sstevel@tonic-gate LINKFOR(tp) = np; 6057c478bd9Sstevel@tonic-gate LINKBAK(np) = tp; 6067c478bd9Sstevel@tonic-gate SETNOTREE(np); 6077c478bd9Sstevel@tonic-gate protect(np); 6087c478bd9Sstevel@tonic-gate 6097c478bd9Sstevel@tonic-gate break; 6107c478bd9Sstevel@tonic-gate } 6117c478bd9Sstevel@tonic-gate } 6127c478bd9Sstevel@tonic-gate } else { 6137c478bd9Sstevel@tonic-gate Root = tp; 6147c478bd9Sstevel@tonic-gate } 6157c478bd9Sstevel@tonic-gate } 6167c478bd9Sstevel@tonic-gate 6177c478bd9Sstevel@tonic-gate /* 6187c478bd9Sstevel@tonic-gate * Tell next block that this one is free. 6197c478bd9Sstevel@tonic-gate * The first WORD of the next block contains self's address. 6207c478bd9Sstevel@tonic-gate */ 6217c478bd9Sstevel@tonic-gate /* LINTED improper alignment */ 6227c478bd9Sstevel@tonic-gate tmp = NEXT(tp); 6237c478bd9Sstevel@tonic-gate unprotect(tmp); 6247c478bd9Sstevel@tonic-gate /* LINTED improper alignment */ 6257c478bd9Sstevel@tonic-gate *(SELFP(tp)) = tp; 6267c478bd9Sstevel@tonic-gate SETBIT1(SIZE(tmp)); 6277c478bd9Sstevel@tonic-gate ASSERT(ISBIT0(SIZE(tmp))); 6287c478bd9Sstevel@tonic-gate protect(tmp); 6297c478bd9Sstevel@tonic-gate protect(tp); 6307c478bd9Sstevel@tonic-gate } 6317c478bd9Sstevel@tonic-gate 6327c478bd9Sstevel@tonic-gate /* 6337c478bd9Sstevel@tonic-gate * Get more core. Gaps in memory are noted as busy blocks. 6347c478bd9Sstevel@tonic-gate */ 6357c478bd9Sstevel@tonic-gate static TREE * 6367c478bd9Sstevel@tonic-gate morecore(size_t size) 6377c478bd9Sstevel@tonic-gate { 6387c478bd9Sstevel@tonic-gate TREE *tp; 6397c478bd9Sstevel@tonic-gate size_t n, offset, requestsize; 6407c478bd9Sstevel@tonic-gate char *addr; 6417c478bd9Sstevel@tonic-gate 6427c478bd9Sstevel@tonic-gate /* compute new amount of memory to get */ 6437c478bd9Sstevel@tonic-gate tp = Bottom; 6447c478bd9Sstevel@tonic-gate n = size + 2 * WORDSIZE; 6457c478bd9Sstevel@tonic-gate addr = GETCORE(0); 6467c478bd9Sstevel@tonic-gate 6477c478bd9Sstevel@tonic-gate if (addr == ERRCORE) 6487c478bd9Sstevel@tonic-gate /* errno set by GETCORE sbrk */ 6497c478bd9Sstevel@tonic-gate return (NULL); 6507c478bd9Sstevel@tonic-gate 6517c478bd9Sstevel@tonic-gate /* need to pad size out so that addr is aligned */ 6527c478bd9Sstevel@tonic-gate if ((((size_t)addr) % ALIGN) != 0) 6537c478bd9Sstevel@tonic-gate offset = ALIGN - (size_t)addr % ALIGN; 6547c478bd9Sstevel@tonic-gate else 6557c478bd9Sstevel@tonic-gate offset = 0; 6567c478bd9Sstevel@tonic-gate 6577c478bd9Sstevel@tonic-gate if (tp) 6587c478bd9Sstevel@tonic-gate unprotect(tp); 6597c478bd9Sstevel@tonic-gate 6607c478bd9Sstevel@tonic-gate /* if not segmented memory, what we need may be smaller */ 6617c478bd9Sstevel@tonic-gate if (addr == Baddr) { 6627c478bd9Sstevel@tonic-gate n -= WORDSIZE; 6637c478bd9Sstevel@tonic-gate if (tp != NULL) 6647c478bd9Sstevel@tonic-gate n -= SIZE(tp); 6657c478bd9Sstevel@tonic-gate } 6667c478bd9Sstevel@tonic-gate 6677c478bd9Sstevel@tonic-gate /* get a multiple of CORESIZE */ 6687c478bd9Sstevel@tonic-gate n = ((n - 1) / CORESIZE + 1) * CORESIZE; 6697c478bd9Sstevel@tonic-gate requestsize = n + offset; 6707c478bd9Sstevel@tonic-gate 6717c478bd9Sstevel@tonic-gate /* check if nsize request could overflow in GETCORE */ 6727c478bd9Sstevel@tonic-gate if (requestsize > MAX_MALLOC - (size_t)addr) { 6737c478bd9Sstevel@tonic-gate if (tp) 6747c478bd9Sstevel@tonic-gate protect(tp); 6757c478bd9Sstevel@tonic-gate errno = ENOMEM; 6767c478bd9Sstevel@tonic-gate return (NULL); 6777c478bd9Sstevel@tonic-gate } 6787c478bd9Sstevel@tonic-gate 6797c478bd9Sstevel@tonic-gate if (requestsize > MAX_GETCORE) { 6807c478bd9Sstevel@tonic-gate intptr_t delta; 6817c478bd9Sstevel@tonic-gate /* 6827c478bd9Sstevel@tonic-gate * the value required is too big for GETCORE() to deal with 6837c478bd9Sstevel@tonic-gate * in one go, so use GETCORE() at most 2 times instead. 6847c478bd9Sstevel@tonic-gate * Argument to GETCORE() must be multiple of ALIGN. 6857c478bd9Sstevel@tonic-gate * If not, GETCORE(-MAX_GETCORE) will not return brk point 6867c478bd9Sstevel@tonic-gate * to previous value, but will be ALIGN more. 6877c478bd9Sstevel@tonic-gate * This would leave a small hole. 6887c478bd9Sstevel@tonic-gate */ 6897c478bd9Sstevel@tonic-gate delta = MAX_GETCORE; 6907c478bd9Sstevel@tonic-gate while (delta > 0) { 6917c478bd9Sstevel@tonic-gate if (GETCORE(delta) == ERRCORE) { 6927c478bd9Sstevel@tonic-gate if (tp) 6937c478bd9Sstevel@tonic-gate protect(tp); 6947c478bd9Sstevel@tonic-gate if (addr != GETCORE(0)) 6957c478bd9Sstevel@tonic-gate (void) GETCORE(-MAX_GETCORE); 6967c478bd9Sstevel@tonic-gate return (NULL); 6977c478bd9Sstevel@tonic-gate } 6987c478bd9Sstevel@tonic-gate requestsize -= MAX_GETCORE; 6997c478bd9Sstevel@tonic-gate delta = requestsize; 7007c478bd9Sstevel@tonic-gate } 7017c478bd9Sstevel@tonic-gate } else if (GETCORE(requestsize) == ERRCORE) { 7027c478bd9Sstevel@tonic-gate if (tp) 7037c478bd9Sstevel@tonic-gate protect(tp); 7047c478bd9Sstevel@tonic-gate return (NULL); 7057c478bd9Sstevel@tonic-gate } 7067c478bd9Sstevel@tonic-gate 7077c478bd9Sstevel@tonic-gate /* contiguous memory */ 7087c478bd9Sstevel@tonic-gate if (addr == Baddr) { 7097c478bd9Sstevel@tonic-gate ASSERT(offset == 0); 7107c478bd9Sstevel@tonic-gate if (tp) { 7117c478bd9Sstevel@tonic-gate addr = ((char *)tp); 7127c478bd9Sstevel@tonic-gate n += SIZE(tp) + 2 * WORDSIZE; 7137c478bd9Sstevel@tonic-gate } else { 7147c478bd9Sstevel@tonic-gate addr = Baddr - WORDSIZE; 7157c478bd9Sstevel@tonic-gate n += WORDSIZE; 7167c478bd9Sstevel@tonic-gate } 7177c478bd9Sstevel@tonic-gate } else { 7187c478bd9Sstevel@tonic-gate addr += offset; 7197c478bd9Sstevel@tonic-gate } 7207c478bd9Sstevel@tonic-gate 7217c478bd9Sstevel@tonic-gate /* new bottom address */ 7227c478bd9Sstevel@tonic-gate Baddr = addr + n; 7237c478bd9Sstevel@tonic-gate 7247c478bd9Sstevel@tonic-gate /* new bottom block */ 7257c478bd9Sstevel@tonic-gate /* LINTED improper alignment */ 7267c478bd9Sstevel@tonic-gate tp = ((TREE *)addr); 7277c478bd9Sstevel@tonic-gate SIZE(tp) = n - 2 * WORDSIZE; 7287c478bd9Sstevel@tonic-gate ASSERT((SIZE(tp) % ALIGN) == 0); 7297c478bd9Sstevel@tonic-gate 7307c478bd9Sstevel@tonic-gate /* reserved the last word to head any noncontiguous memory */ 7317c478bd9Sstevel@tonic-gate /* LINTED improper alignment */ 7327c478bd9Sstevel@tonic-gate SETBIT0(SIZE(NEXT(tp))); 7337c478bd9Sstevel@tonic-gate 7347c478bd9Sstevel@tonic-gate /* non-contiguous memory, free old bottom block */ 7357c478bd9Sstevel@tonic-gate if (Bottom && Bottom != tp) { 7367c478bd9Sstevel@tonic-gate SETBIT0(SIZE(Bottom)); 7377c478bd9Sstevel@tonic-gate realfree(DATA(Bottom)); 7387c478bd9Sstevel@tonic-gate } 7397c478bd9Sstevel@tonic-gate 7407c478bd9Sstevel@tonic-gate return (tp); 7417c478bd9Sstevel@tonic-gate } 7427c478bd9Sstevel@tonic-gate 7437c478bd9Sstevel@tonic-gate /* 7447c478bd9Sstevel@tonic-gate * Utility function to avoid protecting a tree node twice. 7457c478bd9Sstevel@tonic-gate * Return true if tp is in the NULL-terminated array of tree nodes. 7467c478bd9Sstevel@tonic-gate */ 7477c478bd9Sstevel@tonic-gate static int 7487c478bd9Sstevel@tonic-gate in_list(TREE *tp, TREE **npp) 7497c478bd9Sstevel@tonic-gate { 7507c478bd9Sstevel@tonic-gate TREE *sp; 7517c478bd9Sstevel@tonic-gate 7527c478bd9Sstevel@tonic-gate while ((sp = *npp++) != NULL) 7537c478bd9Sstevel@tonic-gate if (tp == sp) 7547c478bd9Sstevel@tonic-gate return (1); 7557c478bd9Sstevel@tonic-gate return (0); 7567c478bd9Sstevel@tonic-gate } 7577c478bd9Sstevel@tonic-gate 7587c478bd9Sstevel@tonic-gate /* 7597c478bd9Sstevel@tonic-gate * Tree rotation functions (BU: bottom-up, TD: top-down). 7607c478bd9Sstevel@tonic-gate * All functions are entered with the arguments unprotected. 7617c478bd9Sstevel@tonic-gate * They must return in the same condition, with all other elements 7627c478bd9Sstevel@tonic-gate * that have been unprotected during the operation re-protected. 7637c478bd9Sstevel@tonic-gate */ 7647c478bd9Sstevel@tonic-gate static void 7657c478bd9Sstevel@tonic-gate LEFT1(TREE *x, TREE *y) 7667c478bd9Sstevel@tonic-gate { 7677c478bd9Sstevel@tonic-gate TREE *node[3]; 7687c478bd9Sstevel@tonic-gate TREE **npp = node; 7697c478bd9Sstevel@tonic-gate TREE *tp; 7707c478bd9Sstevel@tonic-gate 7717c478bd9Sstevel@tonic-gate if ((RIGHT(x) = LEFT(y)) != NULL) { 7727c478bd9Sstevel@tonic-gate unprotect(*npp++ = RIGHT(x)); 7737c478bd9Sstevel@tonic-gate PARENT(RIGHT(x)) = x; 7747c478bd9Sstevel@tonic-gate } 7757c478bd9Sstevel@tonic-gate if ((PARENT(y) = PARENT(x)) != NULL) { 7767c478bd9Sstevel@tonic-gate unprotect(*npp++ = PARENT(x)); 7777c478bd9Sstevel@tonic-gate if (LEFT(PARENT(x)) == x) 7787c478bd9Sstevel@tonic-gate LEFT(PARENT(y)) = y; 7797c478bd9Sstevel@tonic-gate else 7807c478bd9Sstevel@tonic-gate RIGHT(PARENT(y)) = y; 7817c478bd9Sstevel@tonic-gate } 7827c478bd9Sstevel@tonic-gate LEFT(y) = x; 7837c478bd9Sstevel@tonic-gate PARENT(x) = y; 7847c478bd9Sstevel@tonic-gate 7857c478bd9Sstevel@tonic-gate *npp = NULL; 7867c478bd9Sstevel@tonic-gate npp = node; 7877c478bd9Sstevel@tonic-gate while ((tp = *npp++) != NULL) 7887c478bd9Sstevel@tonic-gate if (tp != x && tp != y && !in_list(tp, npp)) 7897c478bd9Sstevel@tonic-gate protect(tp); 7907c478bd9Sstevel@tonic-gate } 7917c478bd9Sstevel@tonic-gate 7927c478bd9Sstevel@tonic-gate static void 7937c478bd9Sstevel@tonic-gate RIGHT1(TREE *x, TREE *y) 7947c478bd9Sstevel@tonic-gate { 7957c478bd9Sstevel@tonic-gate TREE *node[3]; 7967c478bd9Sstevel@tonic-gate TREE **npp = node; 7977c478bd9Sstevel@tonic-gate TREE *tp; 7987c478bd9Sstevel@tonic-gate 7997c478bd9Sstevel@tonic-gate if ((LEFT(x) = RIGHT(y)) != NULL) { 8007c478bd9Sstevel@tonic-gate unprotect(*npp++ = LEFT(x)); 8017c478bd9Sstevel@tonic-gate PARENT(LEFT(x)) = x; 8027c478bd9Sstevel@tonic-gate } 8037c478bd9Sstevel@tonic-gate if ((PARENT(y) = PARENT(x)) != NULL) { 8047c478bd9Sstevel@tonic-gate unprotect(*npp++ = PARENT(x)); 8057c478bd9Sstevel@tonic-gate if (LEFT(PARENT(x)) == x) 8067c478bd9Sstevel@tonic-gate LEFT(PARENT(y)) = y; 8077c478bd9Sstevel@tonic-gate else 8087c478bd9Sstevel@tonic-gate RIGHT(PARENT(y)) = y; 8097c478bd9Sstevel@tonic-gate } 8107c478bd9Sstevel@tonic-gate RIGHT(y) = x; 8117c478bd9Sstevel@tonic-gate PARENT(x) = y; 8127c478bd9Sstevel@tonic-gate 8137c478bd9Sstevel@tonic-gate *npp = NULL; 8147c478bd9Sstevel@tonic-gate npp = node; 8157c478bd9Sstevel@tonic-gate while ((tp = *npp++) != NULL) 8167c478bd9Sstevel@tonic-gate if (tp != x && tp != y && !in_list(tp, npp)) 8177c478bd9Sstevel@tonic-gate protect(tp); 8187c478bd9Sstevel@tonic-gate } 8197c478bd9Sstevel@tonic-gate 8207c478bd9Sstevel@tonic-gate static void 8217c478bd9Sstevel@tonic-gate BULEFT2(TREE *x, TREE *y, TREE *z) 8227c478bd9Sstevel@tonic-gate { 8237c478bd9Sstevel@tonic-gate TREE *node[4]; 8247c478bd9Sstevel@tonic-gate TREE **npp = node; 8257c478bd9Sstevel@tonic-gate TREE *tp; 8267c478bd9Sstevel@tonic-gate 8277c478bd9Sstevel@tonic-gate if ((RIGHT(x) = LEFT(y)) != NULL) { 8287c478bd9Sstevel@tonic-gate unprotect(*npp++ = RIGHT(x)); 8297c478bd9Sstevel@tonic-gate PARENT(RIGHT(x)) = x; 8307c478bd9Sstevel@tonic-gate } 8317c478bd9Sstevel@tonic-gate if ((RIGHT(y) = LEFT(z)) != NULL) { 8327c478bd9Sstevel@tonic-gate unprotect(*npp++ = RIGHT(y)); 8337c478bd9Sstevel@tonic-gate PARENT(RIGHT(y)) = y; 8347c478bd9Sstevel@tonic-gate } 8357c478bd9Sstevel@tonic-gate if ((PARENT(z) = PARENT(x)) != NULL) { 8367c478bd9Sstevel@tonic-gate unprotect(*npp++ = PARENT(x)); 8377c478bd9Sstevel@tonic-gate if (LEFT(PARENT(x)) == x) 8387c478bd9Sstevel@tonic-gate LEFT(PARENT(z)) = z; 8397c478bd9Sstevel@tonic-gate else 8407c478bd9Sstevel@tonic-gate RIGHT(PARENT(z)) = z; 8417c478bd9Sstevel@tonic-gate } 8427c478bd9Sstevel@tonic-gate LEFT(z) = y; 8437c478bd9Sstevel@tonic-gate PARENT(y) = z; 8447c478bd9Sstevel@tonic-gate LEFT(y) = x; 8457c478bd9Sstevel@tonic-gate PARENT(x) = y; 8467c478bd9Sstevel@tonic-gate 8477c478bd9Sstevel@tonic-gate *npp = NULL; 8487c478bd9Sstevel@tonic-gate npp = node; 8497c478bd9Sstevel@tonic-gate while ((tp = *npp++) != NULL) 8507c478bd9Sstevel@tonic-gate if (tp != x && tp != y && tp != z && !in_list(tp, npp)) 8517c478bd9Sstevel@tonic-gate protect(tp); 8527c478bd9Sstevel@tonic-gate } 8537c478bd9Sstevel@tonic-gate 8547c478bd9Sstevel@tonic-gate static void 8557c478bd9Sstevel@tonic-gate BURIGHT2(TREE *x, TREE *y, TREE *z) 8567c478bd9Sstevel@tonic-gate { 8577c478bd9Sstevel@tonic-gate TREE *node[4]; 8587c478bd9Sstevel@tonic-gate TREE **npp = node; 8597c478bd9Sstevel@tonic-gate TREE *tp; 8607c478bd9Sstevel@tonic-gate 8617c478bd9Sstevel@tonic-gate if ((LEFT(x) = RIGHT(y)) != NULL) { 8627c478bd9Sstevel@tonic-gate unprotect(*npp++ = LEFT(x)); 8637c478bd9Sstevel@tonic-gate PARENT(LEFT(x)) = x; 8647c478bd9Sstevel@tonic-gate } 8657c478bd9Sstevel@tonic-gate if ((LEFT(y) = RIGHT(z)) != NULL) { 8667c478bd9Sstevel@tonic-gate unprotect(*npp++ = LEFT(y)); 8677c478bd9Sstevel@tonic-gate PARENT(LEFT(y)) = y; 8687c478bd9Sstevel@tonic-gate } 8697c478bd9Sstevel@tonic-gate if ((PARENT(z) = PARENT(x)) != NULL) { 8707c478bd9Sstevel@tonic-gate unprotect(*npp++ = PARENT(x)); 8717c478bd9Sstevel@tonic-gate if (LEFT(PARENT(x)) == x) 8727c478bd9Sstevel@tonic-gate LEFT(PARENT(z)) = z; 8737c478bd9Sstevel@tonic-gate else 8747c478bd9Sstevel@tonic-gate RIGHT(PARENT(z)) = z; 8757c478bd9Sstevel@tonic-gate } 8767c478bd9Sstevel@tonic-gate RIGHT(z) = y; 8777c478bd9Sstevel@tonic-gate PARENT(y) = z; 8787c478bd9Sstevel@tonic-gate RIGHT(y) = x; 8797c478bd9Sstevel@tonic-gate PARENT(x) = y; 8807c478bd9Sstevel@tonic-gate 8817c478bd9Sstevel@tonic-gate *npp = NULL; 8827c478bd9Sstevel@tonic-gate npp = node; 8837c478bd9Sstevel@tonic-gate while ((tp = *npp++) != NULL) 8847c478bd9Sstevel@tonic-gate if (tp != x && tp != y && tp != z && !in_list(tp, npp)) 8857c478bd9Sstevel@tonic-gate protect(tp); 8867c478bd9Sstevel@tonic-gate } 8877c478bd9Sstevel@tonic-gate 8887c478bd9Sstevel@tonic-gate static void 8897c478bd9Sstevel@tonic-gate TDLEFT2(TREE *x, TREE *y, TREE *z) 8907c478bd9Sstevel@tonic-gate { 8917c478bd9Sstevel@tonic-gate TREE *node[3]; 8927c478bd9Sstevel@tonic-gate TREE **npp = node; 8937c478bd9Sstevel@tonic-gate TREE *tp; 8947c478bd9Sstevel@tonic-gate 8957c478bd9Sstevel@tonic-gate if ((RIGHT(y) = LEFT(z)) != NULL) { 8967c478bd9Sstevel@tonic-gate unprotect(*npp++ = RIGHT(y)); 8977c478bd9Sstevel@tonic-gate PARENT(RIGHT(y)) = y; 8987c478bd9Sstevel@tonic-gate } 8997c478bd9Sstevel@tonic-gate if ((PARENT(z) = PARENT(x)) != NULL) { 9007c478bd9Sstevel@tonic-gate unprotect(*npp++ = PARENT(x)); 9017c478bd9Sstevel@tonic-gate if (LEFT(PARENT(x)) == x) 9027c478bd9Sstevel@tonic-gate LEFT(PARENT(z)) = z; 9037c478bd9Sstevel@tonic-gate else 9047c478bd9Sstevel@tonic-gate RIGHT(PARENT(z)) = z; 9057c478bd9Sstevel@tonic-gate } 9067c478bd9Sstevel@tonic-gate PARENT(x) = z; 9077c478bd9Sstevel@tonic-gate LEFT(z) = x; 9087c478bd9Sstevel@tonic-gate 9097c478bd9Sstevel@tonic-gate *npp = NULL; 9107c478bd9Sstevel@tonic-gate npp = node; 9117c478bd9Sstevel@tonic-gate while ((tp = *npp++) != NULL) 9127c478bd9Sstevel@tonic-gate if (tp != x && tp != y && tp != z && !in_list(tp, npp)) 9137c478bd9Sstevel@tonic-gate protect(tp); 9147c478bd9Sstevel@tonic-gate } 9157c478bd9Sstevel@tonic-gate 9167c478bd9Sstevel@tonic-gate #if 0 /* Not used, for now */ 9177c478bd9Sstevel@tonic-gate static void 9187c478bd9Sstevel@tonic-gate TDRIGHT2(TREE *x, TREE *y, TREE *z) 9197c478bd9Sstevel@tonic-gate { 9207c478bd9Sstevel@tonic-gate TREE *node[3]; 9217c478bd9Sstevel@tonic-gate TREE **npp = node; 9227c478bd9Sstevel@tonic-gate TREE *tp; 9237c478bd9Sstevel@tonic-gate 9247c478bd9Sstevel@tonic-gate if ((LEFT(y) = RIGHT(z)) != NULL) { 9257c478bd9Sstevel@tonic-gate unprotect(*npp++ = LEFT(y)); 9267c478bd9Sstevel@tonic-gate PARENT(LEFT(y)) = y; 9277c478bd9Sstevel@tonic-gate } 9287c478bd9Sstevel@tonic-gate if ((PARENT(z) = PARENT(x)) != NULL) { 9297c478bd9Sstevel@tonic-gate unprotect(*npp++ = PARENT(x)); 9307c478bd9Sstevel@tonic-gate if (LEFT(PARENT(x)) == x) 9317c478bd9Sstevel@tonic-gate LEFT(PARENT(z)) = z; 9327c478bd9Sstevel@tonic-gate else 9337c478bd9Sstevel@tonic-gate RIGHT(PARENT(z)) = z; 9347c478bd9Sstevel@tonic-gate } 9357c478bd9Sstevel@tonic-gate PARENT(x) = z; 9367c478bd9Sstevel@tonic-gate RIGHT(z) = x; 9377c478bd9Sstevel@tonic-gate 9387c478bd9Sstevel@tonic-gate *npp = NULL; 9397c478bd9Sstevel@tonic-gate npp = node; 9407c478bd9Sstevel@tonic-gate while ((tp = *npp++) != NULL) 9417c478bd9Sstevel@tonic-gate if (tp != x && tp != y && tp != z && !in_list(tp, npp)) 9427c478bd9Sstevel@tonic-gate protect(tp); 9437c478bd9Sstevel@tonic-gate } 9447c478bd9Sstevel@tonic-gate #endif 9457c478bd9Sstevel@tonic-gate 9467c478bd9Sstevel@tonic-gate /* 9477c478bd9Sstevel@tonic-gate * Delete a tree element 9487c478bd9Sstevel@tonic-gate */ 9497c478bd9Sstevel@tonic-gate static void 9507c478bd9Sstevel@tonic-gate t_delete(TREE *op) 9517c478bd9Sstevel@tonic-gate { 9527c478bd9Sstevel@tonic-gate TREE *tp, *sp, *gp; 9537c478bd9Sstevel@tonic-gate 9547c478bd9Sstevel@tonic-gate /* if this is a non-tree node */ 9557c478bd9Sstevel@tonic-gate if (ISNOTREE(op)) { 9567c478bd9Sstevel@tonic-gate tp = LINKBAK(op); 9577c478bd9Sstevel@tonic-gate unprotect(tp); 9587c478bd9Sstevel@tonic-gate if ((sp = LINKFOR(op)) != NULL) { 9597c478bd9Sstevel@tonic-gate unprotect(sp); 9607c478bd9Sstevel@tonic-gate LINKBAK(sp) = tp; 9617c478bd9Sstevel@tonic-gate protect(sp); 9627c478bd9Sstevel@tonic-gate } 9637c478bd9Sstevel@tonic-gate LINKFOR(tp) = sp; 9647c478bd9Sstevel@tonic-gate protect(tp); 9657c478bd9Sstevel@tonic-gate return; 9667c478bd9Sstevel@tonic-gate } 9677c478bd9Sstevel@tonic-gate 9687c478bd9Sstevel@tonic-gate /* make op the root of the tree */ 9697c478bd9Sstevel@tonic-gate if (PARENT(op)) 9707c478bd9Sstevel@tonic-gate t_splay(op); 9717c478bd9Sstevel@tonic-gate 9727c478bd9Sstevel@tonic-gate /* if this is the start of a list */ 9737c478bd9Sstevel@tonic-gate if ((tp = LINKFOR(op)) != NULL) { 9747c478bd9Sstevel@tonic-gate unprotect(tp); 9757c478bd9Sstevel@tonic-gate PARENT(tp) = NULL; 9767c478bd9Sstevel@tonic-gate if ((sp = LEFT(op)) != NULL) { 9777c478bd9Sstevel@tonic-gate unprotect(sp); 9787c478bd9Sstevel@tonic-gate PARENT(sp) = tp; 9797c478bd9Sstevel@tonic-gate protect(sp); 9807c478bd9Sstevel@tonic-gate } 9817c478bd9Sstevel@tonic-gate LEFT(tp) = sp; 9827c478bd9Sstevel@tonic-gate 9837c478bd9Sstevel@tonic-gate if ((sp = RIGHT(op)) != NULL) { 9847c478bd9Sstevel@tonic-gate unprotect(sp); 9857c478bd9Sstevel@tonic-gate PARENT(sp) = tp; 9867c478bd9Sstevel@tonic-gate protect(sp); 9877c478bd9Sstevel@tonic-gate } 9887c478bd9Sstevel@tonic-gate RIGHT(tp) = sp; 9897c478bd9Sstevel@tonic-gate 9907c478bd9Sstevel@tonic-gate Root = tp; 9917c478bd9Sstevel@tonic-gate protect(tp); 9927c478bd9Sstevel@tonic-gate return; 9937c478bd9Sstevel@tonic-gate } 9947c478bd9Sstevel@tonic-gate 9957c478bd9Sstevel@tonic-gate /* if op has a non-null left subtree */ 9967c478bd9Sstevel@tonic-gate if ((tp = LEFT(op)) != NULL) { 9977c478bd9Sstevel@tonic-gate unprotect(tp); 9987c478bd9Sstevel@tonic-gate PARENT(tp) = NULL; 9997c478bd9Sstevel@tonic-gate if (RIGHT(op)) { 10007c478bd9Sstevel@tonic-gate /* make the right-end of the left subtree its root */ 10017c478bd9Sstevel@tonic-gate while ((sp = RIGHT(tp)) != NULL) { 10027c478bd9Sstevel@tonic-gate unprotect(sp); 10037c478bd9Sstevel@tonic-gate if ((gp = RIGHT(sp)) != NULL) { 10047c478bd9Sstevel@tonic-gate unprotect(gp); 10057c478bd9Sstevel@tonic-gate TDLEFT2(tp, sp, gp); 10067c478bd9Sstevel@tonic-gate protect(sp); 10077c478bd9Sstevel@tonic-gate protect(tp); 10087c478bd9Sstevel@tonic-gate tp = gp; 10097c478bd9Sstevel@tonic-gate } else { 10107c478bd9Sstevel@tonic-gate LEFT1(tp, sp); 10117c478bd9Sstevel@tonic-gate protect(tp); 10127c478bd9Sstevel@tonic-gate tp = sp; 10137c478bd9Sstevel@tonic-gate } 10147c478bd9Sstevel@tonic-gate } 10157c478bd9Sstevel@tonic-gate 10167c478bd9Sstevel@tonic-gate /* hook the right subtree of op to the above elt */ 10177c478bd9Sstevel@tonic-gate RIGHT(tp) = sp = RIGHT(op); 10187c478bd9Sstevel@tonic-gate unprotect(sp); 10197c478bd9Sstevel@tonic-gate PARENT(sp) = tp; 10207c478bd9Sstevel@tonic-gate protect(sp); 10217c478bd9Sstevel@tonic-gate } 10227c478bd9Sstevel@tonic-gate protect(tp); 10237c478bd9Sstevel@tonic-gate } else if ((tp = RIGHT(op)) != NULL) { /* no left subtree */ 10247c478bd9Sstevel@tonic-gate unprotect(tp); 10257c478bd9Sstevel@tonic-gate PARENT(tp) = NULL; 10267c478bd9Sstevel@tonic-gate protect(tp); 10277c478bd9Sstevel@tonic-gate } 10287c478bd9Sstevel@tonic-gate 10297c478bd9Sstevel@tonic-gate Root = tp; 10307c478bd9Sstevel@tonic-gate } 10317c478bd9Sstevel@tonic-gate 10327c478bd9Sstevel@tonic-gate /* 10337c478bd9Sstevel@tonic-gate * Bottom up splaying (simple version). 10347c478bd9Sstevel@tonic-gate * The basic idea is to roughly cut in half the 10357c478bd9Sstevel@tonic-gate * path from Root to tp and make tp the new root. 10367c478bd9Sstevel@tonic-gate */ 10377c478bd9Sstevel@tonic-gate static void 10387c478bd9Sstevel@tonic-gate t_splay(TREE *tp) 10397c478bd9Sstevel@tonic-gate { 10407c478bd9Sstevel@tonic-gate TREE *pp, *gp; 10417c478bd9Sstevel@tonic-gate 10427c478bd9Sstevel@tonic-gate /* iterate until tp is the root */ 10437c478bd9Sstevel@tonic-gate while ((pp = PARENT(tp)) != NULL) { 10447c478bd9Sstevel@tonic-gate unprotect(pp); 10457c478bd9Sstevel@tonic-gate /* grandparent of tp */ 10467c478bd9Sstevel@tonic-gate gp = PARENT(pp); 10477c478bd9Sstevel@tonic-gate if (gp) 10487c478bd9Sstevel@tonic-gate unprotect(gp); 10497c478bd9Sstevel@tonic-gate 10507c478bd9Sstevel@tonic-gate /* x is a left child */ 10517c478bd9Sstevel@tonic-gate if (LEFT(pp) == tp) { 10527c478bd9Sstevel@tonic-gate if (gp && LEFT(gp) == pp) { 10537c478bd9Sstevel@tonic-gate BURIGHT2(gp, pp, tp); 10547c478bd9Sstevel@tonic-gate protect(gp); 10557c478bd9Sstevel@tonic-gate } else { 10567c478bd9Sstevel@tonic-gate if (gp) 10577c478bd9Sstevel@tonic-gate protect(gp); 10587c478bd9Sstevel@tonic-gate RIGHT1(pp, tp); 10597c478bd9Sstevel@tonic-gate } 10607c478bd9Sstevel@tonic-gate } else { 10617c478bd9Sstevel@tonic-gate ASSERT(RIGHT(pp) == tp); 10627c478bd9Sstevel@tonic-gate if (gp && RIGHT(gp) == pp) { 10637c478bd9Sstevel@tonic-gate BULEFT2(gp, pp, tp); 10647c478bd9Sstevel@tonic-gate protect(gp); 10657c478bd9Sstevel@tonic-gate } else { 10667c478bd9Sstevel@tonic-gate if (gp) 10677c478bd9Sstevel@tonic-gate protect(gp); 10687c478bd9Sstevel@tonic-gate LEFT1(pp, tp); 10697c478bd9Sstevel@tonic-gate } 10707c478bd9Sstevel@tonic-gate } 10717c478bd9Sstevel@tonic-gate protect(pp); 10727c478bd9Sstevel@tonic-gate unprotect(tp); /* just in case */ 10737c478bd9Sstevel@tonic-gate } 10747c478bd9Sstevel@tonic-gate } 10757c478bd9Sstevel@tonic-gate 10767c478bd9Sstevel@tonic-gate void 10777c478bd9Sstevel@tonic-gate free(void *old) 10787c478bd9Sstevel@tonic-gate { 10797c478bd9Sstevel@tonic-gate _mutex_lock(&__watch_malloc_lock); 10807c478bd9Sstevel@tonic-gate free_unlocked(old); 10817c478bd9Sstevel@tonic-gate _mutex_unlock(&__watch_malloc_lock); 10827c478bd9Sstevel@tonic-gate } 10837c478bd9Sstevel@tonic-gate 10847c478bd9Sstevel@tonic-gate 10857c478bd9Sstevel@tonic-gate static void 10867c478bd9Sstevel@tonic-gate free_unlocked(void *old) 10877c478bd9Sstevel@tonic-gate { 10887c478bd9Sstevel@tonic-gate if (old != NULL) 10897c478bd9Sstevel@tonic-gate realfree(old); 10907c478bd9Sstevel@tonic-gate } 10917c478bd9Sstevel@tonic-gate 10927c478bd9Sstevel@tonic-gate 10937c478bd9Sstevel@tonic-gate /* 10947c478bd9Sstevel@tonic-gate * memalign(align,nbytes) 10957c478bd9Sstevel@tonic-gate * 10967c478bd9Sstevel@tonic-gate * Description: 10977c478bd9Sstevel@tonic-gate * Returns a block of specified size on a specified alignment boundary. 10987c478bd9Sstevel@tonic-gate * 10997c478bd9Sstevel@tonic-gate * Algorithm: 11007c478bd9Sstevel@tonic-gate * Malloc enough to ensure that a block can be aligned correctly. 11017c478bd9Sstevel@tonic-gate * Find the alignment point and return the fragments 11027c478bd9Sstevel@tonic-gate * before and after the block. 11037c478bd9Sstevel@tonic-gate * 11047c478bd9Sstevel@tonic-gate * Errors: 11057c478bd9Sstevel@tonic-gate * Returns NULL and sets errno as follows: 11067c478bd9Sstevel@tonic-gate * [EINVAL] 11077c478bd9Sstevel@tonic-gate * if nbytes = 0, 11087c478bd9Sstevel@tonic-gate * or if alignment is misaligned, 11097c478bd9Sstevel@tonic-gate * or if the heap has been detectably corrupted. 11107c478bd9Sstevel@tonic-gate * [ENOMEM] 11117c478bd9Sstevel@tonic-gate * if the requested memory could not be allocated. 11127c478bd9Sstevel@tonic-gate */ 11137c478bd9Sstevel@tonic-gate 11147c478bd9Sstevel@tonic-gate #pragma weak memalign = _memalign 11157c478bd9Sstevel@tonic-gate 11167c478bd9Sstevel@tonic-gate #define misaligned(p) ((unsigned)(p) & 3) 11177c478bd9Sstevel@tonic-gate /* 4-byte "word" alignment is considered ok in LP64 */ 11187c478bd9Sstevel@tonic-gate #define nextblk(p, size) ((TREE *)((char *)(p) + (size))) 11197c478bd9Sstevel@tonic-gate 11207c478bd9Sstevel@tonic-gate void * 11217c478bd9Sstevel@tonic-gate _memalign(size_t align, size_t nbytes) 11227c478bd9Sstevel@tonic-gate { 11237c478bd9Sstevel@tonic-gate size_t reqsize; /* Num of bytes to get from malloc() */ 11247c478bd9Sstevel@tonic-gate TREE *p; /* Ptr returned from malloc() */ 11257c478bd9Sstevel@tonic-gate TREE *blk; /* For addressing fragment blocks */ 11267c478bd9Sstevel@tonic-gate size_t blksize; /* Current (shrinking) block size */ 11277c478bd9Sstevel@tonic-gate TREE *alignedp; /* Ptr to properly aligned boundary */ 11287c478bd9Sstevel@tonic-gate TREE *aligned_blk; /* The block to be returned */ 11297c478bd9Sstevel@tonic-gate size_t frag_size; /* size of fragments fore and aft */ 11307c478bd9Sstevel@tonic-gate size_t x; 11317c478bd9Sstevel@tonic-gate 11327c478bd9Sstevel@tonic-gate /* 11337c478bd9Sstevel@tonic-gate * check for valid size and alignment parameters 11347c478bd9Sstevel@tonic-gate * MAX_ALIGN check prevents overflow in later calculation. 11357c478bd9Sstevel@tonic-gate */ 11367c478bd9Sstevel@tonic-gate if (nbytes == 0 || misaligned(align) || align == 0 || 11377c478bd9Sstevel@tonic-gate align > MAX_ALIGN) { 11387c478bd9Sstevel@tonic-gate errno = EINVAL; 11397c478bd9Sstevel@tonic-gate return (NULL); 11407c478bd9Sstevel@tonic-gate } 11417c478bd9Sstevel@tonic-gate 11427c478bd9Sstevel@tonic-gate /* 11437c478bd9Sstevel@tonic-gate * Malloc enough memory to guarantee that the result can be 11447c478bd9Sstevel@tonic-gate * aligned correctly. The worst case is when malloc returns 11457c478bd9Sstevel@tonic-gate * a block so close to the next alignment boundary that a 11467c478bd9Sstevel@tonic-gate * fragment of minimum size cannot be created. In order to 11477c478bd9Sstevel@tonic-gate * make sure we can handle this, we need to force the 11487c478bd9Sstevel@tonic-gate * alignment to be at least as large as the minimum frag size 11497c478bd9Sstevel@tonic-gate * (MINSIZE + WORDSIZE). 11507c478bd9Sstevel@tonic-gate */ 11517c478bd9Sstevel@tonic-gate 11527c478bd9Sstevel@tonic-gate /* check for size that could overflow ROUND calculation */ 11537c478bd9Sstevel@tonic-gate if (nbytes > MAX_MALLOC) { 11547c478bd9Sstevel@tonic-gate errno = ENOMEM; 11557c478bd9Sstevel@tonic-gate return (NULL); 11567c478bd9Sstevel@tonic-gate } 11577c478bd9Sstevel@tonic-gate ROUND(nbytes); 11587c478bd9Sstevel@tonic-gate if (nbytes < MINSIZE) 11597c478bd9Sstevel@tonic-gate nbytes = MINSIZE; 11607c478bd9Sstevel@tonic-gate ROUND(align); 11617c478bd9Sstevel@tonic-gate while (align < MINSIZE + WORDSIZE) 11627c478bd9Sstevel@tonic-gate align <<= 1; 11637c478bd9Sstevel@tonic-gate reqsize = nbytes + align + (MINSIZE + WORDSIZE); 11647c478bd9Sstevel@tonic-gate /* check for overflow */ 11657c478bd9Sstevel@tonic-gate if (reqsize < nbytes) { 11667c478bd9Sstevel@tonic-gate errno = ENOMEM; 11677c478bd9Sstevel@tonic-gate return (NULL); 11687c478bd9Sstevel@tonic-gate } 11697c478bd9Sstevel@tonic-gate p = (TREE *) malloc(reqsize); 11707c478bd9Sstevel@tonic-gate if (p == (TREE *) NULL) { 11717c478bd9Sstevel@tonic-gate /* malloc sets errno */ 11727c478bd9Sstevel@tonic-gate return (NULL); 11737c478bd9Sstevel@tonic-gate } 11747c478bd9Sstevel@tonic-gate _mutex_lock(&__watch_malloc_lock); 11757c478bd9Sstevel@tonic-gate 11767c478bd9Sstevel@tonic-gate /* 11777c478bd9Sstevel@tonic-gate * get size of the entire block (overhead and all) 11787c478bd9Sstevel@tonic-gate */ 11797c478bd9Sstevel@tonic-gate /* LINTED improper alignment */ 11807c478bd9Sstevel@tonic-gate blk = BLOCK(p); /* back up to get length word */ 11817c478bd9Sstevel@tonic-gate unprotect(blk); 11827c478bd9Sstevel@tonic-gate blksize = SIZE(blk); 11837c478bd9Sstevel@tonic-gate CLRBITS01(blksize); 11847c478bd9Sstevel@tonic-gate 11857c478bd9Sstevel@tonic-gate /* 11867c478bd9Sstevel@tonic-gate * locate the proper alignment boundary within the block. 11877c478bd9Sstevel@tonic-gate */ 11887c478bd9Sstevel@tonic-gate x = (size_t)p; 11897c478bd9Sstevel@tonic-gate if (x % align != 0) 11907c478bd9Sstevel@tonic-gate x += align - (x % align); 11917c478bd9Sstevel@tonic-gate alignedp = (TREE *)x; 11927c478bd9Sstevel@tonic-gate /* LINTED improper alignment */ 11937c478bd9Sstevel@tonic-gate aligned_blk = BLOCK(alignedp); 11947c478bd9Sstevel@tonic-gate 11957c478bd9Sstevel@tonic-gate /* 11967c478bd9Sstevel@tonic-gate * Check out the space to the left of the alignment 11977c478bd9Sstevel@tonic-gate * boundary, and split off a fragment if necessary. 11987c478bd9Sstevel@tonic-gate */ 11997c478bd9Sstevel@tonic-gate frag_size = (size_t)aligned_blk - (size_t)blk; 12007c478bd9Sstevel@tonic-gate if (frag_size != 0) { 12017c478bd9Sstevel@tonic-gate /* 12027c478bd9Sstevel@tonic-gate * Create a fragment to the left of the aligned block. 12037c478bd9Sstevel@tonic-gate */ 12047c478bd9Sstevel@tonic-gate if (frag_size < MINSIZE + WORDSIZE) { 12057c478bd9Sstevel@tonic-gate /* 12067c478bd9Sstevel@tonic-gate * Not enough space. So make the split 12077c478bd9Sstevel@tonic-gate * at the other end of the alignment unit. 12087c478bd9Sstevel@tonic-gate * We know this yields enough space, because 12097c478bd9Sstevel@tonic-gate * we forced align >= MINSIZE + WORDSIZE above. 12107c478bd9Sstevel@tonic-gate */ 12117c478bd9Sstevel@tonic-gate frag_size += align; 12127c478bd9Sstevel@tonic-gate /* LINTED improper alignment */ 12137c478bd9Sstevel@tonic-gate aligned_blk = nextblk(aligned_blk, align); 12147c478bd9Sstevel@tonic-gate } 12157c478bd9Sstevel@tonic-gate blksize -= frag_size; 12167c478bd9Sstevel@tonic-gate SIZE(aligned_blk) = blksize | BIT0; 12177c478bd9Sstevel@tonic-gate frag_size -= WORDSIZE; 12187c478bd9Sstevel@tonic-gate SIZE(blk) = frag_size | BIT0 | ISBIT1(SIZE(blk)); 12197c478bd9Sstevel@tonic-gate free_unlocked(DATA(blk)); 12207c478bd9Sstevel@tonic-gate /* 12217c478bd9Sstevel@tonic-gate * free_unlocked(DATA(blk)) has the side-effect of calling 12227c478bd9Sstevel@tonic-gate * protect() on the block following blk, that is, aligned_blk. 12237c478bd9Sstevel@tonic-gate * We recover from this by unprotect()ing it here. 12247c478bd9Sstevel@tonic-gate */ 12257c478bd9Sstevel@tonic-gate unprotect(aligned_blk); 12267c478bd9Sstevel@tonic-gate } 12277c478bd9Sstevel@tonic-gate 12287c478bd9Sstevel@tonic-gate /* 12297c478bd9Sstevel@tonic-gate * Is there a (sufficiently large) fragment to the 12307c478bd9Sstevel@tonic-gate * right of the aligned block? 12317c478bd9Sstevel@tonic-gate */ 12327c478bd9Sstevel@tonic-gate frag_size = blksize - nbytes; 12337c478bd9Sstevel@tonic-gate if (frag_size >= MINSIZE + WORDSIZE) { 12347c478bd9Sstevel@tonic-gate /* 12357c478bd9Sstevel@tonic-gate * split and free a fragment on the right 12367c478bd9Sstevel@tonic-gate */ 12377c478bd9Sstevel@tonic-gate blksize = SIZE(aligned_blk); 12387c478bd9Sstevel@tonic-gate SIZE(aligned_blk) = nbytes; 12397c478bd9Sstevel@tonic-gate /* LINTED improper alignment */ 12407c478bd9Sstevel@tonic-gate blk = NEXT(aligned_blk); 12417c478bd9Sstevel@tonic-gate SETOLD01(SIZE(aligned_blk), blksize); 12427c478bd9Sstevel@tonic-gate frag_size -= WORDSIZE; 12437c478bd9Sstevel@tonic-gate SIZE(blk) = frag_size | BIT0; 12447c478bd9Sstevel@tonic-gate free_unlocked(DATA(blk)); 12457c478bd9Sstevel@tonic-gate } 12467c478bd9Sstevel@tonic-gate copy_pattern(LIVEPAT, aligned_blk); 12477c478bd9Sstevel@tonic-gate protect(aligned_blk); 12487c478bd9Sstevel@tonic-gate _mutex_unlock(&__watch_malloc_lock); 12497c478bd9Sstevel@tonic-gate return (DATA(aligned_blk)); 12507c478bd9Sstevel@tonic-gate } 12517c478bd9Sstevel@tonic-gate 12527c478bd9Sstevel@tonic-gate #pragma weak valloc = _valloc 12537c478bd9Sstevel@tonic-gate 12547c478bd9Sstevel@tonic-gate void * 12557c478bd9Sstevel@tonic-gate _valloc(size_t size) 12567c478bd9Sstevel@tonic-gate { 12577c478bd9Sstevel@tonic-gate static unsigned pagesize; 12587c478bd9Sstevel@tonic-gate if (!pagesize) 12597c478bd9Sstevel@tonic-gate pagesize = _sysconf(_SC_PAGESIZE); 12607c478bd9Sstevel@tonic-gate return (memalign(pagesize, size)); 12617c478bd9Sstevel@tonic-gate } 12627c478bd9Sstevel@tonic-gate 12637c478bd9Sstevel@tonic-gate /* 12647c478bd9Sstevel@tonic-gate * libc does not define a weak calloc as _calloc 12657c478bd9Sstevel@tonic-gate */ 12667c478bd9Sstevel@tonic-gate void * 12677c478bd9Sstevel@tonic-gate calloc(size_t num, size_t size) 12687c478bd9Sstevel@tonic-gate { 12697c478bd9Sstevel@tonic-gate void *mp; 12707c478bd9Sstevel@tonic-gate size_t total; 12717c478bd9Sstevel@tonic-gate 12727c478bd9Sstevel@tonic-gate total = num * size; 12737c478bd9Sstevel@tonic-gate 12747c478bd9Sstevel@tonic-gate /* check for overflow */ 12757c478bd9Sstevel@tonic-gate if (num != 0 && total / num != size) { 12767c478bd9Sstevel@tonic-gate errno = ENOMEM; 12777c478bd9Sstevel@tonic-gate return (NULL); 12787c478bd9Sstevel@tonic-gate } 12797c478bd9Sstevel@tonic-gate if ((mp = malloc(total)) != NULL) 12807c478bd9Sstevel@tonic-gate (void) memset(mp, 0, total); 12817c478bd9Sstevel@tonic-gate return (mp); 12827c478bd9Sstevel@tonic-gate } 12837c478bd9Sstevel@tonic-gate 12847c478bd9Sstevel@tonic-gate #pragma weak cfree = _cfree 12857c478bd9Sstevel@tonic-gate 12867c478bd9Sstevel@tonic-gate /* ARGSUSED1 */ 12877c478bd9Sstevel@tonic-gate void 12887c478bd9Sstevel@tonic-gate _cfree(void *p, size_t num, size_t size) 12897c478bd9Sstevel@tonic-gate { 12907c478bd9Sstevel@tonic-gate free(p); 12917c478bd9Sstevel@tonic-gate } 12927c478bd9Sstevel@tonic-gate 12937c478bd9Sstevel@tonic-gate /* 12947c478bd9Sstevel@tonic-gate * mallopt -- Do nothing 12957c478bd9Sstevel@tonic-gate */ 12967c478bd9Sstevel@tonic-gate 12977c478bd9Sstevel@tonic-gate #pragma weak mallopt = _mallopt 12987c478bd9Sstevel@tonic-gate 12997c478bd9Sstevel@tonic-gate /* ARGSUSED */ 13007c478bd9Sstevel@tonic-gate int 13017c478bd9Sstevel@tonic-gate _mallopt(int cmd, int value) 13027c478bd9Sstevel@tonic-gate { 13037c478bd9Sstevel@tonic-gate return (0); 13047c478bd9Sstevel@tonic-gate } 13057c478bd9Sstevel@tonic-gate 13067c478bd9Sstevel@tonic-gate /* 13077c478bd9Sstevel@tonic-gate * mallinfo -- Do nothing 13087c478bd9Sstevel@tonic-gate */ 13097c478bd9Sstevel@tonic-gate 13107c478bd9Sstevel@tonic-gate #pragma weak mallinfo = _mallinfo 13117c478bd9Sstevel@tonic-gate 13127c478bd9Sstevel@tonic-gate struct mallinfo 13137c478bd9Sstevel@tonic-gate _mallinfo() 13147c478bd9Sstevel@tonic-gate { 13157c478bd9Sstevel@tonic-gate static struct mallinfo __mallinfo; 13167c478bd9Sstevel@tonic-gate 13177c478bd9Sstevel@tonic-gate return (__mallinfo); 13187c478bd9Sstevel@tonic-gate } 13197c478bd9Sstevel@tonic-gate 13207c478bd9Sstevel@tonic-gate 13217c478bd9Sstevel@tonic-gate typedef struct { 13227c478bd9Sstevel@tonic-gate long cmd; 13237c478bd9Sstevel@tonic-gate prwatch_t prwatch; 13247c478bd9Sstevel@tonic-gate } ctl_t; 13257c478bd9Sstevel@tonic-gate 13267c478bd9Sstevel@tonic-gate static pid_t my_pid = 0; /* to check for whether we fork()d */ 13277c478bd9Sstevel@tonic-gate static int dont_watch = 0; 13287c478bd9Sstevel@tonic-gate static int do_stop = 0; 13297c478bd9Sstevel@tonic-gate static int ctlfd = -1; 13307c478bd9Sstevel@tonic-gate struct stat ctlstatb; 13317c478bd9Sstevel@tonic-gate static int wflags = WA_WRITE; 13327c478bd9Sstevel@tonic-gate 13337c478bd9Sstevel@tonic-gate static void 13347c478bd9Sstevel@tonic-gate init_watch() 13357c478bd9Sstevel@tonic-gate { 13367c478bd9Sstevel@tonic-gate char str[80]; 13377c478bd9Sstevel@tonic-gate char *s; 13387c478bd9Sstevel@tonic-gate 13397c478bd9Sstevel@tonic-gate my_pid = getpid(); 13407c478bd9Sstevel@tonic-gate 13417c478bd9Sstevel@tonic-gate dont_watch = 1; 13427c478bd9Sstevel@tonic-gate 13437c478bd9Sstevel@tonic-gate if ((s = getenv("MALLOC_DEBUG")) == NULL) 13447c478bd9Sstevel@tonic-gate return; 13457c478bd9Sstevel@tonic-gate 13467c478bd9Sstevel@tonic-gate s = strncpy(str, s, sizeof (str)); 13477c478bd9Sstevel@tonic-gate while (s != NULL) { 13487c478bd9Sstevel@tonic-gate char *e = strchr(s, ','); 13497c478bd9Sstevel@tonic-gate if (e) 13507c478bd9Sstevel@tonic-gate *e++ = '\0'; 13517c478bd9Sstevel@tonic-gate if (strcmp(s, "STOP") == 0) 13527c478bd9Sstevel@tonic-gate do_stop = 1; 13537c478bd9Sstevel@tonic-gate else if (strcmp(s, "WATCH") == 0) 13547c478bd9Sstevel@tonic-gate dont_watch = 0; 13557c478bd9Sstevel@tonic-gate else if (strcmp(s, "RW") == 0) { 13567c478bd9Sstevel@tonic-gate dont_watch = 0; 13577c478bd9Sstevel@tonic-gate wflags = WA_READ|WA_WRITE; 13587c478bd9Sstevel@tonic-gate } 13597c478bd9Sstevel@tonic-gate s = e; 13607c478bd9Sstevel@tonic-gate } 13617c478bd9Sstevel@tonic-gate 13627c478bd9Sstevel@tonic-gate if (dont_watch) 13637c478bd9Sstevel@tonic-gate return; 13647c478bd9Sstevel@tonic-gate 13657c478bd9Sstevel@tonic-gate if ((ctlfd = open("/proc/self/ctl", O_WRONLY)) < 0 || 13667c478bd9Sstevel@tonic-gate fstat(ctlfd, &ctlstatb) != 0) { 13677c478bd9Sstevel@tonic-gate if (ctlfd >= 0) 13687c478bd9Sstevel@tonic-gate (void) close(ctlfd); 13697c478bd9Sstevel@tonic-gate ctlfd = -1; 13707c478bd9Sstevel@tonic-gate dont_watch = 1; 13717c478bd9Sstevel@tonic-gate return; 13727c478bd9Sstevel@tonic-gate } 13737c478bd9Sstevel@tonic-gate /* close-on-exec */ 13747c478bd9Sstevel@tonic-gate (void) fcntl(ctlfd, F_SETFD, 1); 13757c478bd9Sstevel@tonic-gate 13767c478bd9Sstevel@tonic-gate if (do_stop) { 13777c478bd9Sstevel@tonic-gate int pfd; 13787c478bd9Sstevel@tonic-gate pstatus_t pstatus; 13797c478bd9Sstevel@tonic-gate struct { 13807c478bd9Sstevel@tonic-gate long cmd; 13817c478bd9Sstevel@tonic-gate fltset_t fltset; 13827c478bd9Sstevel@tonic-gate } ctl; 13837c478bd9Sstevel@tonic-gate 13847c478bd9Sstevel@tonic-gate /* 13857c478bd9Sstevel@tonic-gate * Play together with some /proc controller 13867c478bd9Sstevel@tonic-gate * that has set other stop-on-fault flags. 13877c478bd9Sstevel@tonic-gate */ 13887c478bd9Sstevel@tonic-gate premptyset(&ctl.fltset); 13897c478bd9Sstevel@tonic-gate if ((pfd = open("/proc/self/status", O_RDONLY)) >= 0) { 13907c478bd9Sstevel@tonic-gate if (read(pfd, &pstatus, sizeof (pstatus)) 13917c478bd9Sstevel@tonic-gate == sizeof (pstatus)) 13927c478bd9Sstevel@tonic-gate ctl.fltset = pstatus.pr_flttrace; 13937c478bd9Sstevel@tonic-gate (void) close(pfd); 13947c478bd9Sstevel@tonic-gate } 13957c478bd9Sstevel@tonic-gate praddset(&ctl.fltset, FLTWATCH); 13967c478bd9Sstevel@tonic-gate ctl.cmd = PCSFAULT; 13977c478bd9Sstevel@tonic-gate (void) write(ctlfd, &ctl, sizeof (ctl)); 13987c478bd9Sstevel@tonic-gate } 13997c478bd9Sstevel@tonic-gate } 14007c478bd9Sstevel@tonic-gate 14017c478bd9Sstevel@tonic-gate static int 14027c478bd9Sstevel@tonic-gate nowatch() 14037c478bd9Sstevel@tonic-gate { 14047c478bd9Sstevel@tonic-gate struct stat statb; 14057c478bd9Sstevel@tonic-gate 14067c478bd9Sstevel@tonic-gate if (dont_watch) 14077c478bd9Sstevel@tonic-gate return (1); 14087c478bd9Sstevel@tonic-gate if (ctlfd < 0) /* first time */ 14097c478bd9Sstevel@tonic-gate init_watch(); 14107c478bd9Sstevel@tonic-gate else if (fstat(ctlfd, &statb) != 0 || 14117c478bd9Sstevel@tonic-gate statb.st_dev != ctlstatb.st_dev || 14127c478bd9Sstevel@tonic-gate statb.st_ino != ctlstatb.st_ino) { 14137c478bd9Sstevel@tonic-gate /* 14147c478bd9Sstevel@tonic-gate * Someone closed our file descriptor. 14157c478bd9Sstevel@tonic-gate * Just open another one. 14167c478bd9Sstevel@tonic-gate */ 14177c478bd9Sstevel@tonic-gate if ((ctlfd = open("/proc/self/ctl", O_WRONLY)) < 0 || 14187c478bd9Sstevel@tonic-gate fstat(ctlfd, &ctlstatb) != 0) { 14197c478bd9Sstevel@tonic-gate if (ctlfd >= 0) 14207c478bd9Sstevel@tonic-gate (void) close(ctlfd); 14217c478bd9Sstevel@tonic-gate ctlfd = -1; 14227c478bd9Sstevel@tonic-gate dont_watch = 1; 14237c478bd9Sstevel@tonic-gate return (1); 14247c478bd9Sstevel@tonic-gate } 14257c478bd9Sstevel@tonic-gate /* close-on-exec */ 14267c478bd9Sstevel@tonic-gate (void) fcntl(ctlfd, F_SETFD, 1); 14277c478bd9Sstevel@tonic-gate } 14287c478bd9Sstevel@tonic-gate if (my_pid != getpid()) { 14297c478bd9Sstevel@tonic-gate /* 14307c478bd9Sstevel@tonic-gate * We fork()d since the last call to the allocator. 14317c478bd9Sstevel@tonic-gate * watchpoints are not inherited across fork(). 14327c478bd9Sstevel@tonic-gate * XXX: how to recover from this ??? 14337c478bd9Sstevel@tonic-gate */ 14347c478bd9Sstevel@tonic-gate dont_watch = 1; 14357c478bd9Sstevel@tonic-gate (void) close(ctlfd); 14367c478bd9Sstevel@tonic-gate ctlfd = -1; 14377c478bd9Sstevel@tonic-gate } 14387c478bd9Sstevel@tonic-gate return (dont_watch); 14397c478bd9Sstevel@tonic-gate } 14407c478bd9Sstevel@tonic-gate 14417c478bd9Sstevel@tonic-gate static void 14427c478bd9Sstevel@tonic-gate protect(TREE *tp) 14437c478bd9Sstevel@tonic-gate { 14447c478bd9Sstevel@tonic-gate ctl_t ctl; 14457c478bd9Sstevel@tonic-gate size_t size, sz; 14467c478bd9Sstevel@tonic-gate 14477c478bd9Sstevel@tonic-gate if (nowatch()) 14487c478bd9Sstevel@tonic-gate return; 14497c478bd9Sstevel@tonic-gate if (tp == NULL || DATA(tp) == Baddr) 14507c478bd9Sstevel@tonic-gate return; 14517c478bd9Sstevel@tonic-gate 14527c478bd9Sstevel@tonic-gate sz = size = SIZE(tp); 14537c478bd9Sstevel@tonic-gate CLRBITS01(size); 14547c478bd9Sstevel@tonic-gate if (size == 0) 14557c478bd9Sstevel@tonic-gate return; 14567c478bd9Sstevel@tonic-gate if (ISBIT0(sz)) /* block is busy, protect only the head */ 14577c478bd9Sstevel@tonic-gate size = 0; 14587c478bd9Sstevel@tonic-gate ctl.cmd = PCWATCH; 14597c478bd9Sstevel@tonic-gate ctl.prwatch.pr_vaddr = (uintptr_t)tp; 14607c478bd9Sstevel@tonic-gate ctl.prwatch.pr_size = size + WORDSIZE; 14617c478bd9Sstevel@tonic-gate ctl.prwatch.pr_wflags = wflags; 14627c478bd9Sstevel@tonic-gate (void) write(ctlfd, &ctl, sizeof (ctl)); 14637c478bd9Sstevel@tonic-gate } 14647c478bd9Sstevel@tonic-gate 14657c478bd9Sstevel@tonic-gate static void 14667c478bd9Sstevel@tonic-gate unprotect(TREE *tp) 14677c478bd9Sstevel@tonic-gate { 14687c478bd9Sstevel@tonic-gate ctl_t ctl; 14697c478bd9Sstevel@tonic-gate 14707c478bd9Sstevel@tonic-gate if (nowatch()) 14717c478bd9Sstevel@tonic-gate return; 14727c478bd9Sstevel@tonic-gate if (tp == NULL || DATA(tp) == Baddr) 14737c478bd9Sstevel@tonic-gate return; 14747c478bd9Sstevel@tonic-gate 14757c478bd9Sstevel@tonic-gate ctl.cmd = PCWATCH; 14767c478bd9Sstevel@tonic-gate ctl.prwatch.pr_vaddr = (uintptr_t)tp; 14777c478bd9Sstevel@tonic-gate ctl.prwatch.pr_size = WORDSIZE; /* size is arbitrary */ 14787c478bd9Sstevel@tonic-gate ctl.prwatch.pr_wflags = 0; /* clear the watched area */ 14797c478bd9Sstevel@tonic-gate (void) write(ctlfd, &ctl, sizeof (ctl)); 14807c478bd9Sstevel@tonic-gate } 1481