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