xref: /titanic_44/usr/src/lib/libc/port/gen/malloc.c (revision 7257d1b4d25bfac0c802847390e98a464fd787ac)
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
52333b8a2Sraf  * Common Development and Distribution License (the "License").
62333b8a2Sraf  * You may not use this file except in compliance with the License.
77c478bd9Sstevel@tonic-gate  *
87c478bd9Sstevel@tonic-gate  * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
97c478bd9Sstevel@tonic-gate  * or http://www.opensolaris.org/os/licensing.
107c478bd9Sstevel@tonic-gate  * See the License for the specific language governing permissions
117c478bd9Sstevel@tonic-gate  * and limitations under the License.
127c478bd9Sstevel@tonic-gate  *
137c478bd9Sstevel@tonic-gate  * When distributing Covered Code, include this CDDL HEADER in each
147c478bd9Sstevel@tonic-gate  * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
157c478bd9Sstevel@tonic-gate  * If applicable, add the following below this CDDL HEADER, with the
167c478bd9Sstevel@tonic-gate  * fields enclosed by brackets "[]" replaced with your own identifying
177c478bd9Sstevel@tonic-gate  * information: Portions Copyright [yyyy] [name of copyright owner]
187c478bd9Sstevel@tonic-gate  *
197c478bd9Sstevel@tonic-gate  * CDDL HEADER END
207c478bd9Sstevel@tonic-gate  */
212333b8a2Sraf 
227c478bd9Sstevel@tonic-gate /*
238cd45542Sraf  * Copyright 2008 Sun Microsystems, Inc.  All rights reserved.
247c478bd9Sstevel@tonic-gate  * Use is subject to license terms.
257c478bd9Sstevel@tonic-gate  */
267c478bd9Sstevel@tonic-gate 
277c478bd9Sstevel@tonic-gate /*	Copyright (c) 1988 AT&T	*/
287c478bd9Sstevel@tonic-gate /*	  All Rights Reserved  	*/
297c478bd9Sstevel@tonic-gate 
30*7257d1b4Sraf #pragma ident	"%Z%%M%	%I%	%E% SMI"
31*7257d1b4Sraf 
327c478bd9Sstevel@tonic-gate /*
337c478bd9Sstevel@tonic-gate  *	Memory management: malloc(), realloc(), free().
347c478bd9Sstevel@tonic-gate  *
357c478bd9Sstevel@tonic-gate  *	The following #-parameters may be redefined:
367c478bd9Sstevel@tonic-gate  *	SEGMENTED: if defined, memory requests are assumed to be
377c478bd9Sstevel@tonic-gate  *		non-contiguous across calls of GETCORE's.
387c478bd9Sstevel@tonic-gate  *	GETCORE: a function to get more core memory. If not SEGMENTED,
397c478bd9Sstevel@tonic-gate  *		GETCORE(0) is assumed to return the next available
407c478bd9Sstevel@tonic-gate  *		address. Default is 'sbrk'.
417c478bd9Sstevel@tonic-gate  *	ERRCORE: the error code as returned by GETCORE.
427c478bd9Sstevel@tonic-gate  *		Default is (char *)(-1).
437c478bd9Sstevel@tonic-gate  *	CORESIZE: a desired unit (measured in bytes) to be used
447c478bd9Sstevel@tonic-gate  *		with GETCORE. Default is (1024*ALIGN).
457c478bd9Sstevel@tonic-gate  *
467c478bd9Sstevel@tonic-gate  *	This algorithm is based on a  best fit strategy with lists of
477c478bd9Sstevel@tonic-gate  *	free elts maintained in a self-adjusting binary tree. Each list
487c478bd9Sstevel@tonic-gate  *	contains all elts of the same size. The tree is ordered by size.
497c478bd9Sstevel@tonic-gate  *	For results on self-adjusting trees, see the paper:
507c478bd9Sstevel@tonic-gate  *		Self-Adjusting Binary Trees,
517c478bd9Sstevel@tonic-gate  *		DD Sleator & RE Tarjan, JACM 1985.
527c478bd9Sstevel@tonic-gate  *
537c478bd9Sstevel@tonic-gate  *	The header of a block contains the size of the data part in bytes.
547c478bd9Sstevel@tonic-gate  *	Since the size of a block is 0%4, the low two bits of the header
557c478bd9Sstevel@tonic-gate  *	are free and used as follows:
567c478bd9Sstevel@tonic-gate  *
577c478bd9Sstevel@tonic-gate  *		BIT0:	1 for busy (block is in use), 0 for free.
587c478bd9Sstevel@tonic-gate  *		BIT1:	if the block is busy, this bit is 1 if the
597c478bd9Sstevel@tonic-gate  *			preceding block in contiguous memory is free.
607c478bd9Sstevel@tonic-gate  *			Otherwise, it is always 0.
617c478bd9Sstevel@tonic-gate  */
627c478bd9Sstevel@tonic-gate 
63*7257d1b4Sraf #include "lint.h"
647c478bd9Sstevel@tonic-gate #include "mallint.h"
657c478bd9Sstevel@tonic-gate #include "mtlib.h"
667c478bd9Sstevel@tonic-gate 
677c478bd9Sstevel@tonic-gate /*
687c478bd9Sstevel@tonic-gate  * Some abusers of the system (notably java1.2) acquire __malloc_lock
697c478bd9Sstevel@tonic-gate  * in order to prevent threads from holding it while they are being
707c478bd9Sstevel@tonic-gate  * suspended via thr_suspend() or thr_suspend_allmutators().
712333b8a2Sraf  * This never worked when alternate malloc() libraries were used
722333b8a2Sraf  * because they don't use __malloc_lock for their locking strategy.
732333b8a2Sraf  * We leave __malloc_lock as an external variable to satisfy these
742333b8a2Sraf  * old programs, but we define a new lock, private to libc, to do the
752333b8a2Sraf  * real locking: libc_malloc_lock.  This puts libc's malloc() package
762333b8a2Sraf  * on the same footing as all other malloc packages.
777c478bd9Sstevel@tonic-gate  */
787c478bd9Sstevel@tonic-gate mutex_t __malloc_lock = DEFAULTMUTEX;
797c478bd9Sstevel@tonic-gate mutex_t libc_malloc_lock = DEFAULTMUTEX;
807c478bd9Sstevel@tonic-gate 
817c478bd9Sstevel@tonic-gate static TREE	*Root,		/* root of the free tree */
827c478bd9Sstevel@tonic-gate 		*Bottom,	/* the last free chunk in the arena */
837c478bd9Sstevel@tonic-gate 		*_morecore(size_t);	/* function to get more core */
847c478bd9Sstevel@tonic-gate 
857c478bd9Sstevel@tonic-gate static char	*Baddr;		/* current high address of the arena */
867c478bd9Sstevel@tonic-gate static char	*Lfree;		/* last freed block with data intact */
877c478bd9Sstevel@tonic-gate 
887c478bd9Sstevel@tonic-gate static void	t_delete(TREE *);
897c478bd9Sstevel@tonic-gate static void	t_splay(TREE *);
907c478bd9Sstevel@tonic-gate static void	realfree(void *);
917c478bd9Sstevel@tonic-gate static void	cleanfree(void *);
927c478bd9Sstevel@tonic-gate static void	*_malloc_unlocked(size_t);
937c478bd9Sstevel@tonic-gate 
947c478bd9Sstevel@tonic-gate #define	FREESIZE (1<<5) /* size for preserving free blocks until next malloc */
957c478bd9Sstevel@tonic-gate #define	FREEMASK FREESIZE-1
967c478bd9Sstevel@tonic-gate 
977c478bd9Sstevel@tonic-gate static void *flist[FREESIZE];	/* list of blocks to be freed on next malloc */
987c478bd9Sstevel@tonic-gate static int freeidx;		/* index of free blocks in flist % FREESIZE */
997c478bd9Sstevel@tonic-gate 
1007c478bd9Sstevel@tonic-gate /*
1012333b8a2Sraf  * Interfaces used only by atfork_init() functions.
1022333b8a2Sraf  */
1032333b8a2Sraf void
malloc_locks(void)1042333b8a2Sraf malloc_locks(void)
1052333b8a2Sraf {
1068cd45542Sraf 	(void) mutex_lock(&libc_malloc_lock);
1072333b8a2Sraf }
1082333b8a2Sraf 
1092333b8a2Sraf void
malloc_unlocks(void)1102333b8a2Sraf malloc_unlocks(void)
1112333b8a2Sraf {
1128cd45542Sraf 	(void) mutex_unlock(&libc_malloc_lock);
1132333b8a2Sraf }
1142333b8a2Sraf 
1152333b8a2Sraf /*
1167c478bd9Sstevel@tonic-gate  *	Allocation of small blocks
1177c478bd9Sstevel@tonic-gate  */
1187c478bd9Sstevel@tonic-gate static TREE	*List[MINSIZE/WORDSIZE-1]; /* lists of small blocks */
1197c478bd9Sstevel@tonic-gate 
1207c478bd9Sstevel@tonic-gate static void *
_smalloc(size_t size)1217c478bd9Sstevel@tonic-gate _smalloc(size_t size)
1227c478bd9Sstevel@tonic-gate {
1237c478bd9Sstevel@tonic-gate 	TREE	*tp;
1247c478bd9Sstevel@tonic-gate 	size_t	i;
1257c478bd9Sstevel@tonic-gate 
1267c478bd9Sstevel@tonic-gate 	ASSERT(size % WORDSIZE == 0);
1277c478bd9Sstevel@tonic-gate 	/* want to return a unique pointer on malloc(0) */
1287c478bd9Sstevel@tonic-gate 	if (size == 0)
1297c478bd9Sstevel@tonic-gate 		size = WORDSIZE;
1307c478bd9Sstevel@tonic-gate 
1317c478bd9Sstevel@tonic-gate 	/* list to use */
1327c478bd9Sstevel@tonic-gate 	i = size / WORDSIZE - 1;
1337c478bd9Sstevel@tonic-gate 
1347c478bd9Sstevel@tonic-gate 	if (List[i] == NULL) {
1357c478bd9Sstevel@tonic-gate 		TREE *np;
1367c478bd9Sstevel@tonic-gate 		int n;
1377c478bd9Sstevel@tonic-gate 		/* number of blocks to get at one time */
1387c478bd9Sstevel@tonic-gate #define	NPS (WORDSIZE*8)
1397c478bd9Sstevel@tonic-gate 		ASSERT((size + WORDSIZE) * NPS >= MINSIZE);
1407c478bd9Sstevel@tonic-gate 
1417c478bd9Sstevel@tonic-gate 		/* get NPS of these block types */
1427c478bd9Sstevel@tonic-gate 		if ((List[i] = _malloc_unlocked((size + WORDSIZE) * NPS)) == 0)
1437c478bd9Sstevel@tonic-gate 			return (0);
1447c478bd9Sstevel@tonic-gate 
1457c478bd9Sstevel@tonic-gate 		/* make them into a link list */
1467c478bd9Sstevel@tonic-gate 		for (n = 0, np = List[i]; n < NPS; ++n) {
1477c478bd9Sstevel@tonic-gate 			tp = np;
1487c478bd9Sstevel@tonic-gate 			SIZE(tp) = size;
1497c478bd9Sstevel@tonic-gate 			np = NEXT(tp);
1507c478bd9Sstevel@tonic-gate 			AFTER(tp) = np;
1517c478bd9Sstevel@tonic-gate 		}
1527c478bd9Sstevel@tonic-gate 		AFTER(tp) = NULL;
1537c478bd9Sstevel@tonic-gate 	}
1547c478bd9Sstevel@tonic-gate 
1557c478bd9Sstevel@tonic-gate 	/* allocate from the head of the queue */
1567c478bd9Sstevel@tonic-gate 	tp = List[i];
1577c478bd9Sstevel@tonic-gate 	List[i] = AFTER(tp);
1587c478bd9Sstevel@tonic-gate 	SETBIT0(SIZE(tp));
1597c478bd9Sstevel@tonic-gate 	return (DATA(tp));
1607c478bd9Sstevel@tonic-gate }
1617c478bd9Sstevel@tonic-gate 
1627c478bd9Sstevel@tonic-gate void *
malloc(size_t size)1637c478bd9Sstevel@tonic-gate malloc(size_t size)
1647c478bd9Sstevel@tonic-gate {
1657c478bd9Sstevel@tonic-gate 	void *ret;
1667c478bd9Sstevel@tonic-gate 
1677c478bd9Sstevel@tonic-gate 	if (!primary_link_map) {
1687c478bd9Sstevel@tonic-gate 		errno = ENOTSUP;
1697c478bd9Sstevel@tonic-gate 		return (NULL);
1707c478bd9Sstevel@tonic-gate 	}
1717c478bd9Sstevel@tonic-gate 	assert_no_libc_locks_held();
1728cd45542Sraf 	(void) mutex_lock(&libc_malloc_lock);
1737c478bd9Sstevel@tonic-gate 	ret = _malloc_unlocked(size);
1748cd45542Sraf 	(void) mutex_unlock(&libc_malloc_lock);
1757c478bd9Sstevel@tonic-gate 	return (ret);
1767c478bd9Sstevel@tonic-gate }
1777c478bd9Sstevel@tonic-gate 
1787c478bd9Sstevel@tonic-gate static void *
_malloc_unlocked(size_t size)1797c478bd9Sstevel@tonic-gate _malloc_unlocked(size_t size)
1807c478bd9Sstevel@tonic-gate {
1817c478bd9Sstevel@tonic-gate 	size_t	n;
1827c478bd9Sstevel@tonic-gate 	TREE	*tp, *sp;
1837c478bd9Sstevel@tonic-gate 	size_t	o_bit1;
1847c478bd9Sstevel@tonic-gate 
1857c478bd9Sstevel@tonic-gate 	COUNT(nmalloc);
1867c478bd9Sstevel@tonic-gate 	ASSERT(WORDSIZE == ALIGN);
1877c478bd9Sstevel@tonic-gate 
1887c478bd9Sstevel@tonic-gate 	/* check for size that could overflow calculations */
1897c478bd9Sstevel@tonic-gate 	if (size > MAX_MALLOC) {
1907c478bd9Sstevel@tonic-gate 		errno = ENOMEM;
1917c478bd9Sstevel@tonic-gate 		return (NULL);
1927c478bd9Sstevel@tonic-gate 	}
1937c478bd9Sstevel@tonic-gate 
1947c478bd9Sstevel@tonic-gate 	/* make sure that size is 0 mod ALIGN */
1957c478bd9Sstevel@tonic-gate 	ROUND(size);
1967c478bd9Sstevel@tonic-gate 
1977c478bd9Sstevel@tonic-gate 	/* see if the last free block can be used */
1987c478bd9Sstevel@tonic-gate 	if (Lfree) {
1997c478bd9Sstevel@tonic-gate 		sp = BLOCK(Lfree);
2007c478bd9Sstevel@tonic-gate 		n = SIZE(sp);
2017c478bd9Sstevel@tonic-gate 		CLRBITS01(n);
2027c478bd9Sstevel@tonic-gate 		if (n == size) {
2037c478bd9Sstevel@tonic-gate 			/*
2047c478bd9Sstevel@tonic-gate 			 * exact match, use it as is
2057c478bd9Sstevel@tonic-gate 			 */
2067c478bd9Sstevel@tonic-gate 			freeidx = (freeidx + FREESIZE - 1) &
2077c478bd9Sstevel@tonic-gate 			    FREEMASK; /* 1 back */
2087c478bd9Sstevel@tonic-gate 			flist[freeidx] = Lfree = NULL;
2097c478bd9Sstevel@tonic-gate 			return (DATA(sp));
2107c478bd9Sstevel@tonic-gate 		} else if (size >= MINSIZE && n > size) {
2117c478bd9Sstevel@tonic-gate 			/*
2127c478bd9Sstevel@tonic-gate 			 * got a big enough piece
2137c478bd9Sstevel@tonic-gate 			 */
2147c478bd9Sstevel@tonic-gate 			freeidx = (freeidx + FREESIZE - 1) &
2157c478bd9Sstevel@tonic-gate 			    FREEMASK; /* 1 back */
2167c478bd9Sstevel@tonic-gate 			flist[freeidx] = Lfree = NULL;
2177c478bd9Sstevel@tonic-gate 			o_bit1 = SIZE(sp) & BIT1;
2187c478bd9Sstevel@tonic-gate 			SIZE(sp) = n;
2197c478bd9Sstevel@tonic-gate 			goto leftover;
2207c478bd9Sstevel@tonic-gate 		}
2217c478bd9Sstevel@tonic-gate 	}
2227c478bd9Sstevel@tonic-gate 	o_bit1 = 0;
2237c478bd9Sstevel@tonic-gate 
2247c478bd9Sstevel@tonic-gate 	/* perform free's of space since last malloc */
2257c478bd9Sstevel@tonic-gate 	cleanfree(NULL);
2267c478bd9Sstevel@tonic-gate 
2277c478bd9Sstevel@tonic-gate 	/* small blocks */
2287c478bd9Sstevel@tonic-gate 	if (size < MINSIZE)
2297c478bd9Sstevel@tonic-gate 		return (_smalloc(size));
2307c478bd9Sstevel@tonic-gate 
2317c478bd9Sstevel@tonic-gate 	/* search for an elt of the right size */
2327c478bd9Sstevel@tonic-gate 	sp = NULL;
2337c478bd9Sstevel@tonic-gate 	n  = 0;
2347c478bd9Sstevel@tonic-gate 	if (Root) {
2357c478bd9Sstevel@tonic-gate 		tp = Root;
2367c478bd9Sstevel@tonic-gate 		for (;;) {
2377c478bd9Sstevel@tonic-gate 			/* branch left */
2387c478bd9Sstevel@tonic-gate 			if (SIZE(tp) >= size) {
2397c478bd9Sstevel@tonic-gate 				if (n == 0 || n >= SIZE(tp)) {
2407c478bd9Sstevel@tonic-gate 					sp = tp;
2417c478bd9Sstevel@tonic-gate 					n = SIZE(tp);
2427c478bd9Sstevel@tonic-gate 				}
2437c478bd9Sstevel@tonic-gate 				if (LEFT(tp))
2447c478bd9Sstevel@tonic-gate 					tp = LEFT(tp);
2457c478bd9Sstevel@tonic-gate 				else
2467c478bd9Sstevel@tonic-gate 					break;
2477c478bd9Sstevel@tonic-gate 			} else { /* branch right */
2487c478bd9Sstevel@tonic-gate 				if (RIGHT(tp))
2497c478bd9Sstevel@tonic-gate 					tp = RIGHT(tp);
2507c478bd9Sstevel@tonic-gate 				else
2517c478bd9Sstevel@tonic-gate 					break;
2527c478bd9Sstevel@tonic-gate 			}
2537c478bd9Sstevel@tonic-gate 		}
2547c478bd9Sstevel@tonic-gate 
2557c478bd9Sstevel@tonic-gate 		if (sp) {
2567c478bd9Sstevel@tonic-gate 			t_delete(sp);
2577c478bd9Sstevel@tonic-gate 		} else if (tp != Root) {
2587c478bd9Sstevel@tonic-gate 			/* make the searched-to element the root */
2597c478bd9Sstevel@tonic-gate 			t_splay(tp);
2607c478bd9Sstevel@tonic-gate 			Root = tp;
2617c478bd9Sstevel@tonic-gate 		}
2627c478bd9Sstevel@tonic-gate 	}
2637c478bd9Sstevel@tonic-gate 
2647c478bd9Sstevel@tonic-gate 	/* if found none fitted in the tree */
2657c478bd9Sstevel@tonic-gate 	if (!sp) {
2667c478bd9Sstevel@tonic-gate 		if (Bottom && size <= SIZE(Bottom)) {
2677c478bd9Sstevel@tonic-gate 			sp = Bottom;
2687c478bd9Sstevel@tonic-gate 			CLRBITS01(SIZE(sp));
2697c478bd9Sstevel@tonic-gate 		} else if ((sp = _morecore(size)) == NULL) /* no more memory */
2707c478bd9Sstevel@tonic-gate 			return (NULL);
2717c478bd9Sstevel@tonic-gate 	}
2727c478bd9Sstevel@tonic-gate 
2737c478bd9Sstevel@tonic-gate 	/* tell the forward neighbor that we're busy */
2747c478bd9Sstevel@tonic-gate 	CLRBIT1(SIZE(NEXT(sp)));
2757c478bd9Sstevel@tonic-gate 
2767c478bd9Sstevel@tonic-gate 	ASSERT(ISBIT0(SIZE(NEXT(sp))));
2777c478bd9Sstevel@tonic-gate 
2787c478bd9Sstevel@tonic-gate leftover:
2797c478bd9Sstevel@tonic-gate 	/* if the leftover is enough for a new free piece */
2807c478bd9Sstevel@tonic-gate 	if ((n = (SIZE(sp) - size)) >= MINSIZE + WORDSIZE) {
2817c478bd9Sstevel@tonic-gate 		n -= WORDSIZE;
2827c478bd9Sstevel@tonic-gate 		SIZE(sp) = size;
2837c478bd9Sstevel@tonic-gate 		tp = NEXT(sp);
2847c478bd9Sstevel@tonic-gate 		SIZE(tp) = n|BIT0;
2857c478bd9Sstevel@tonic-gate 		realfree(DATA(tp));
2867c478bd9Sstevel@tonic-gate 	} else if (BOTTOM(sp))
2877c478bd9Sstevel@tonic-gate 		Bottom = NULL;
2887c478bd9Sstevel@tonic-gate 
2897c478bd9Sstevel@tonic-gate 	/* return the allocated space */
2907c478bd9Sstevel@tonic-gate 	SIZE(sp) |= BIT0 | o_bit1;
2917c478bd9Sstevel@tonic-gate 	return (DATA(sp));
2927c478bd9Sstevel@tonic-gate }
2937c478bd9Sstevel@tonic-gate 
2947c478bd9Sstevel@tonic-gate 
2957c478bd9Sstevel@tonic-gate /*
2967c478bd9Sstevel@tonic-gate  * realloc().
2977c478bd9Sstevel@tonic-gate  *
2987c478bd9Sstevel@tonic-gate  * If the block size is increasing, we try forward merging first.
2997c478bd9Sstevel@tonic-gate  * This is not best-fit but it avoids some data recopying.
3007c478bd9Sstevel@tonic-gate  */
3017c478bd9Sstevel@tonic-gate void *
realloc(void * old,size_t size)3027c478bd9Sstevel@tonic-gate realloc(void *old, size_t size)
3037c478bd9Sstevel@tonic-gate {
3047c478bd9Sstevel@tonic-gate 	TREE	*tp, *np;
3057c478bd9Sstevel@tonic-gate 	size_t	ts;
3067c478bd9Sstevel@tonic-gate 	char	*new;
3077c478bd9Sstevel@tonic-gate 
3087c478bd9Sstevel@tonic-gate 	if (!primary_link_map) {
3097c478bd9Sstevel@tonic-gate 		errno = ENOTSUP;
3107c478bd9Sstevel@tonic-gate 		return (NULL);
3117c478bd9Sstevel@tonic-gate 	}
3127c478bd9Sstevel@tonic-gate 
3137c478bd9Sstevel@tonic-gate 	assert_no_libc_locks_held();
3147c478bd9Sstevel@tonic-gate 	COUNT(nrealloc);
3157c478bd9Sstevel@tonic-gate 
3167c478bd9Sstevel@tonic-gate 	/* check for size that could overflow calculations */
3177c478bd9Sstevel@tonic-gate 	if (size > MAX_MALLOC) {
3187c478bd9Sstevel@tonic-gate 		errno = ENOMEM;
3197c478bd9Sstevel@tonic-gate 		return (NULL);
3207c478bd9Sstevel@tonic-gate 	}
3217c478bd9Sstevel@tonic-gate 
3227c478bd9Sstevel@tonic-gate 	/* pointer to the block */
3238cd45542Sraf 	(void) mutex_lock(&libc_malloc_lock);
3247c478bd9Sstevel@tonic-gate 	if (old == NULL) {
3257c478bd9Sstevel@tonic-gate 		new = _malloc_unlocked(size);
3268cd45542Sraf 		(void) mutex_unlock(&libc_malloc_lock);
3277c478bd9Sstevel@tonic-gate 		return (new);
3287c478bd9Sstevel@tonic-gate 	}
3297c478bd9Sstevel@tonic-gate 
3307c478bd9Sstevel@tonic-gate 	/* perform free's of space since last malloc */
3317c478bd9Sstevel@tonic-gate 	cleanfree(old);
3327c478bd9Sstevel@tonic-gate 
3337c478bd9Sstevel@tonic-gate 	/* make sure that size is 0 mod ALIGN */
3347c478bd9Sstevel@tonic-gate 	ROUND(size);
3357c478bd9Sstevel@tonic-gate 
3367c478bd9Sstevel@tonic-gate 	tp = BLOCK(old);
3377c478bd9Sstevel@tonic-gate 	ts = SIZE(tp);
3387c478bd9Sstevel@tonic-gate 
3397c478bd9Sstevel@tonic-gate 	/* if the block was freed, data has been destroyed. */
3407c478bd9Sstevel@tonic-gate 	if (!ISBIT0(ts)) {
3418cd45542Sraf 		(void) mutex_unlock(&libc_malloc_lock);
3427c478bd9Sstevel@tonic-gate 		return (NULL);
3437c478bd9Sstevel@tonic-gate 	}
3447c478bd9Sstevel@tonic-gate 
3457c478bd9Sstevel@tonic-gate 	/* nothing to do */
3467c478bd9Sstevel@tonic-gate 	CLRBITS01(SIZE(tp));
3477c478bd9Sstevel@tonic-gate 	if (size == SIZE(tp)) {
3487c478bd9Sstevel@tonic-gate 		SIZE(tp) = ts;
3498cd45542Sraf 		(void) mutex_unlock(&libc_malloc_lock);
3507c478bd9Sstevel@tonic-gate 		return (old);
3517c478bd9Sstevel@tonic-gate 	}
3527c478bd9Sstevel@tonic-gate 
3537c478bd9Sstevel@tonic-gate 	/* special cases involving small blocks */
3547c478bd9Sstevel@tonic-gate 	if (size < MINSIZE || SIZE(tp) < MINSIZE) {
3557c478bd9Sstevel@tonic-gate 		/* free is size is zero */
3567c478bd9Sstevel@tonic-gate 		if (size == 0) {
3577c478bd9Sstevel@tonic-gate 			SETOLD01(SIZE(tp), ts);
3587c478bd9Sstevel@tonic-gate 			_free_unlocked(old);
3598cd45542Sraf 			(void) mutex_unlock(&libc_malloc_lock);
3607c478bd9Sstevel@tonic-gate 			return (NULL);
3617c478bd9Sstevel@tonic-gate 		} else {
3627c478bd9Sstevel@tonic-gate 			goto call_malloc;
3637c478bd9Sstevel@tonic-gate 		}
3647c478bd9Sstevel@tonic-gate 	}
3657c478bd9Sstevel@tonic-gate 
3667c478bd9Sstevel@tonic-gate 	/* block is increasing in size, try merging the next block */
3677c478bd9Sstevel@tonic-gate 	if (size > SIZE(tp)) {
3687c478bd9Sstevel@tonic-gate 		np = NEXT(tp);
3697c478bd9Sstevel@tonic-gate 		if (!ISBIT0(SIZE(np))) {
3707c478bd9Sstevel@tonic-gate 			ASSERT(SIZE(np) >= MINSIZE);
3717c478bd9Sstevel@tonic-gate 			ASSERT(!ISBIT1(SIZE(np)));
3727c478bd9Sstevel@tonic-gate 			SIZE(tp) += SIZE(np) + WORDSIZE;
3737c478bd9Sstevel@tonic-gate 			if (np != Bottom)
3747c478bd9Sstevel@tonic-gate 				t_delete(np);
3757c478bd9Sstevel@tonic-gate 			else
3767c478bd9Sstevel@tonic-gate 				Bottom = NULL;
3777c478bd9Sstevel@tonic-gate 			CLRBIT1(SIZE(NEXT(np)));
3787c478bd9Sstevel@tonic-gate 		}
3797c478bd9Sstevel@tonic-gate 
3807c478bd9Sstevel@tonic-gate #ifndef SEGMENTED
3817c478bd9Sstevel@tonic-gate 		/* not enough & at TRUE end of memory, try extending core */
3827c478bd9Sstevel@tonic-gate 		if (size > SIZE(tp) && BOTTOM(tp) && GETCORE(0) == Baddr) {
3837c478bd9Sstevel@tonic-gate 			Bottom = tp;
3847c478bd9Sstevel@tonic-gate 			if ((tp = _morecore(size)) == NULL) {
3857c478bd9Sstevel@tonic-gate 				tp = Bottom;
3867c478bd9Sstevel@tonic-gate 				Bottom = NULL;
3877c478bd9Sstevel@tonic-gate 				}
3887c478bd9Sstevel@tonic-gate 		}
3897c478bd9Sstevel@tonic-gate #endif
3907c478bd9Sstevel@tonic-gate 	}
3917c478bd9Sstevel@tonic-gate 
3927c478bd9Sstevel@tonic-gate 	/* got enough space to use */
3937c478bd9Sstevel@tonic-gate 	if (size <= SIZE(tp)) {
3947c478bd9Sstevel@tonic-gate 		size_t n;
3957c478bd9Sstevel@tonic-gate 
3967c478bd9Sstevel@tonic-gate chop_big:
3977c478bd9Sstevel@tonic-gate 		if ((n = (SIZE(tp) - size)) >= MINSIZE + WORDSIZE) {
3987c478bd9Sstevel@tonic-gate 			n -= WORDSIZE;
3997c478bd9Sstevel@tonic-gate 			SIZE(tp) = size;
4007c478bd9Sstevel@tonic-gate 			np = NEXT(tp);
4017c478bd9Sstevel@tonic-gate 			SIZE(np) = n|BIT0;
4027c478bd9Sstevel@tonic-gate 			realfree(DATA(np));
4037c478bd9Sstevel@tonic-gate 		} else if (BOTTOM(tp))
4047c478bd9Sstevel@tonic-gate 			Bottom = NULL;
4057c478bd9Sstevel@tonic-gate 
4067c478bd9Sstevel@tonic-gate 		/* the previous block may be free */
4077c478bd9Sstevel@tonic-gate 		SETOLD01(SIZE(tp), ts);
4088cd45542Sraf 		(void) mutex_unlock(&libc_malloc_lock);
4097c478bd9Sstevel@tonic-gate 		return (old);
4107c478bd9Sstevel@tonic-gate 	}
4117c478bd9Sstevel@tonic-gate 
4127c478bd9Sstevel@tonic-gate 	/* call malloc to get a new block */
4137c478bd9Sstevel@tonic-gate call_malloc:
4147c478bd9Sstevel@tonic-gate 	SETOLD01(SIZE(tp), ts);
4157c478bd9Sstevel@tonic-gate 	if ((new = _malloc_unlocked(size)) != NULL) {
4167c478bd9Sstevel@tonic-gate 		CLRBITS01(ts);
4177c478bd9Sstevel@tonic-gate 		if (ts > size)
4187c478bd9Sstevel@tonic-gate 			ts = size;
4197c478bd9Sstevel@tonic-gate 		MEMCOPY(new, old, ts);
4207c478bd9Sstevel@tonic-gate 		_free_unlocked(old);
4218cd45542Sraf 		(void) mutex_unlock(&libc_malloc_lock);
4227c478bd9Sstevel@tonic-gate 		return (new);
4237c478bd9Sstevel@tonic-gate 	}
4247c478bd9Sstevel@tonic-gate 
4257c478bd9Sstevel@tonic-gate 	/*
4267c478bd9Sstevel@tonic-gate 	 * Attempt special case recovery allocations since malloc() failed:
4277c478bd9Sstevel@tonic-gate 	 *
4287c478bd9Sstevel@tonic-gate 	 * 1. size <= SIZE(tp) < MINSIZE
4297c478bd9Sstevel@tonic-gate 	 *	Simply return the existing block
4307c478bd9Sstevel@tonic-gate 	 * 2. SIZE(tp) < size < MINSIZE
4317c478bd9Sstevel@tonic-gate 	 *	malloc() may have failed to allocate the chunk of
4327c478bd9Sstevel@tonic-gate 	 *	small blocks. Try asking for MINSIZE bytes.
4337c478bd9Sstevel@tonic-gate 	 * 3. size < MINSIZE <= SIZE(tp)
4347c478bd9Sstevel@tonic-gate 	 *	malloc() may have failed as with 2.  Change to
4357c478bd9Sstevel@tonic-gate 	 *	MINSIZE allocation which is taken from the beginning
4367c478bd9Sstevel@tonic-gate 	 *	of the current block.
4377c478bd9Sstevel@tonic-gate 	 * 4. MINSIZE <= SIZE(tp) < size
4387c478bd9Sstevel@tonic-gate 	 *	If the previous block is free and the combination of
4397c478bd9Sstevel@tonic-gate 	 *	these two blocks has at least size bytes, then merge
4407c478bd9Sstevel@tonic-gate 	 *	the two blocks copying the existing contents backwards.
4417c478bd9Sstevel@tonic-gate 	 */
4427c478bd9Sstevel@tonic-gate 	CLRBITS01(SIZE(tp));
4437c478bd9Sstevel@tonic-gate 	if (SIZE(tp) < MINSIZE) {
4447c478bd9Sstevel@tonic-gate 		if (size < SIZE(tp)) {			/* case 1. */
4457c478bd9Sstevel@tonic-gate 			SETOLD01(SIZE(tp), ts);
4468cd45542Sraf 			(void) mutex_unlock(&libc_malloc_lock);
4477c478bd9Sstevel@tonic-gate 			return (old);
4487c478bd9Sstevel@tonic-gate 		} else if (size < MINSIZE) {		/* case 2. */
4497c478bd9Sstevel@tonic-gate 			size = MINSIZE;
4507c478bd9Sstevel@tonic-gate 			goto call_malloc;
4517c478bd9Sstevel@tonic-gate 		}
4527c478bd9Sstevel@tonic-gate 	} else if (size < MINSIZE) {			/* case 3. */
4537c478bd9Sstevel@tonic-gate 		size = MINSIZE;
4547c478bd9Sstevel@tonic-gate 		goto chop_big;
4557c478bd9Sstevel@tonic-gate 	} else if (ISBIT1(ts) &&
4567c478bd9Sstevel@tonic-gate 	    (SIZE(np = LAST(tp)) + SIZE(tp) + WORDSIZE) >= size) {
4577c478bd9Sstevel@tonic-gate 		ASSERT(!ISBIT0(SIZE(np)));
4587c478bd9Sstevel@tonic-gate 		t_delete(np);
4597c478bd9Sstevel@tonic-gate 		SIZE(np) += SIZE(tp) + WORDSIZE;
4607c478bd9Sstevel@tonic-gate 		/*
4617c478bd9Sstevel@tonic-gate 		 * Since the copy may overlap, use memmove() if available.
4627c478bd9Sstevel@tonic-gate 		 * Otherwise, copy by hand.
4637c478bd9Sstevel@tonic-gate 		 */
4647c478bd9Sstevel@tonic-gate 		(void) memmove(DATA(np), old, SIZE(tp));
4657c478bd9Sstevel@tonic-gate 		old = DATA(np);
4667c478bd9Sstevel@tonic-gate 		tp = np;
4677c478bd9Sstevel@tonic-gate 		CLRBIT1(ts);
4687c478bd9Sstevel@tonic-gate 		goto chop_big;
4697c478bd9Sstevel@tonic-gate 	}
4707c478bd9Sstevel@tonic-gate 	SETOLD01(SIZE(tp), ts);
4718cd45542Sraf 	(void) mutex_unlock(&libc_malloc_lock);
4727c478bd9Sstevel@tonic-gate 	return (NULL);
4737c478bd9Sstevel@tonic-gate }
4747c478bd9Sstevel@tonic-gate 
4757c478bd9Sstevel@tonic-gate 
4767c478bd9Sstevel@tonic-gate /*
4777c478bd9Sstevel@tonic-gate  * realfree().
4787c478bd9Sstevel@tonic-gate  *
4797c478bd9Sstevel@tonic-gate  * Coalescing of adjacent free blocks is done first.
4807c478bd9Sstevel@tonic-gate  * Then, the new free block is leaf-inserted into the free tree
4817c478bd9Sstevel@tonic-gate  * without splaying. This strategy does not guarantee the amortized
4827c478bd9Sstevel@tonic-gate  * O(nlogn) behaviour for the insert/delete/find set of operations
4837c478bd9Sstevel@tonic-gate  * on the tree. In practice, however, free is much more infrequent
4847c478bd9Sstevel@tonic-gate  * than malloc/realloc and the tree searches performed by these
4857c478bd9Sstevel@tonic-gate  * functions adequately keep the tree in balance.
4867c478bd9Sstevel@tonic-gate  */
4877c478bd9Sstevel@tonic-gate static void
realfree(void * old)4887c478bd9Sstevel@tonic-gate realfree(void *old)
4897c478bd9Sstevel@tonic-gate {
4907c478bd9Sstevel@tonic-gate 	TREE	*tp, *sp, *np;
4917c478bd9Sstevel@tonic-gate 	size_t	ts, size;
4927c478bd9Sstevel@tonic-gate 
4937c478bd9Sstevel@tonic-gate 	COUNT(nfree);
4947c478bd9Sstevel@tonic-gate 
4957c478bd9Sstevel@tonic-gate 	/* pointer to the block */
4967c478bd9Sstevel@tonic-gate 	tp = BLOCK(old);
4977c478bd9Sstevel@tonic-gate 	ts = SIZE(tp);
4987c478bd9Sstevel@tonic-gate 	if (!ISBIT0(ts))
4997c478bd9Sstevel@tonic-gate 		return;
5007c478bd9Sstevel@tonic-gate 	CLRBITS01(SIZE(tp));
5017c478bd9Sstevel@tonic-gate 
5027c478bd9Sstevel@tonic-gate 	/* small block, put it in the right linked list */
5037c478bd9Sstevel@tonic-gate 	if (SIZE(tp) < MINSIZE) {
5047c478bd9Sstevel@tonic-gate 		ASSERT(SIZE(tp) / WORDSIZE >= 1);
5057c478bd9Sstevel@tonic-gate 		ts = SIZE(tp) / WORDSIZE - 1;
5067c478bd9Sstevel@tonic-gate 		AFTER(tp) = List[ts];
5077c478bd9Sstevel@tonic-gate 		List[ts] = tp;
5087c478bd9Sstevel@tonic-gate 		return;
5097c478bd9Sstevel@tonic-gate 	}
5107c478bd9Sstevel@tonic-gate 
5117c478bd9Sstevel@tonic-gate 	/* see if coalescing with next block is warranted */
5127c478bd9Sstevel@tonic-gate 	np = NEXT(tp);
5137c478bd9Sstevel@tonic-gate 	if (!ISBIT0(SIZE(np))) {
5147c478bd9Sstevel@tonic-gate 		if (np != Bottom)
5157c478bd9Sstevel@tonic-gate 			t_delete(np);
5167c478bd9Sstevel@tonic-gate 		SIZE(tp) += SIZE(np) + WORDSIZE;
5177c478bd9Sstevel@tonic-gate 	}
5187c478bd9Sstevel@tonic-gate 
5197c478bd9Sstevel@tonic-gate 	/* the same with the preceding block */
5207c478bd9Sstevel@tonic-gate 	if (ISBIT1(ts)) {
5217c478bd9Sstevel@tonic-gate 		np = LAST(tp);
5227c478bd9Sstevel@tonic-gate 		ASSERT(!ISBIT0(SIZE(np)));
5237c478bd9Sstevel@tonic-gate 		ASSERT(np != Bottom);
5247c478bd9Sstevel@tonic-gate 		t_delete(np);
5257c478bd9Sstevel@tonic-gate 		SIZE(np) += SIZE(tp) + WORDSIZE;
5267c478bd9Sstevel@tonic-gate 		tp = np;
5277c478bd9Sstevel@tonic-gate 	}
5287c478bd9Sstevel@tonic-gate 
5297c478bd9Sstevel@tonic-gate 	/* initialize tree info */
5307c478bd9Sstevel@tonic-gate 	PARENT(tp) = LEFT(tp) = RIGHT(tp) = LINKFOR(tp) = NULL;
5317c478bd9Sstevel@tonic-gate 
5327c478bd9Sstevel@tonic-gate 	/* the last word of the block contains self's address */
5337c478bd9Sstevel@tonic-gate 	*(SELFP(tp)) = tp;
5347c478bd9Sstevel@tonic-gate 
5357c478bd9Sstevel@tonic-gate 	/* set bottom block, or insert in the free tree */
5367c478bd9Sstevel@tonic-gate 	if (BOTTOM(tp))
5377c478bd9Sstevel@tonic-gate 		Bottom = tp;
5387c478bd9Sstevel@tonic-gate 	else {
5397c478bd9Sstevel@tonic-gate 		/* search for the place to insert */
5407c478bd9Sstevel@tonic-gate 		if (Root) {
5417c478bd9Sstevel@tonic-gate 			size = SIZE(tp);
5427c478bd9Sstevel@tonic-gate 			np = Root;
5437c478bd9Sstevel@tonic-gate 			for (;;) {
5447c478bd9Sstevel@tonic-gate 				if (SIZE(np) > size) {
5457c478bd9Sstevel@tonic-gate 					if (LEFT(np))
5467c478bd9Sstevel@tonic-gate 						np = LEFT(np);
5477c478bd9Sstevel@tonic-gate 					else {
5487c478bd9Sstevel@tonic-gate 						LEFT(np) = tp;
5497c478bd9Sstevel@tonic-gate 						PARENT(tp) = np;
5507c478bd9Sstevel@tonic-gate 						break;
5517c478bd9Sstevel@tonic-gate 					}
5527c478bd9Sstevel@tonic-gate 				} else if (SIZE(np) < size) {
5537c478bd9Sstevel@tonic-gate 					if (RIGHT(np))
5547c478bd9Sstevel@tonic-gate 						np = RIGHT(np);
5557c478bd9Sstevel@tonic-gate 					else {
5567c478bd9Sstevel@tonic-gate 						RIGHT(np) = tp;
5577c478bd9Sstevel@tonic-gate 						PARENT(tp) = np;
5587c478bd9Sstevel@tonic-gate 						break;
5597c478bd9Sstevel@tonic-gate 					}
5607c478bd9Sstevel@tonic-gate 				} else {
5617c478bd9Sstevel@tonic-gate 					if ((sp = PARENT(np)) != NULL) {
5627c478bd9Sstevel@tonic-gate 						if (np == LEFT(sp))
5637c478bd9Sstevel@tonic-gate 							LEFT(sp) = tp;
5647c478bd9Sstevel@tonic-gate 						else
5657c478bd9Sstevel@tonic-gate 							RIGHT(sp) = tp;
5667c478bd9Sstevel@tonic-gate 						PARENT(tp) = sp;
5677c478bd9Sstevel@tonic-gate 					} else
5687c478bd9Sstevel@tonic-gate 						Root = tp;
5697c478bd9Sstevel@tonic-gate 
5707c478bd9Sstevel@tonic-gate 					/* insert to head of list */
5717c478bd9Sstevel@tonic-gate 					if ((sp = LEFT(np)) != NULL)
5727c478bd9Sstevel@tonic-gate 						PARENT(sp) = tp;
5737c478bd9Sstevel@tonic-gate 					LEFT(tp) = sp;
5747c478bd9Sstevel@tonic-gate 
5757c478bd9Sstevel@tonic-gate 					if ((sp = RIGHT(np)) != NULL)
5767c478bd9Sstevel@tonic-gate 						PARENT(sp) = tp;
5777c478bd9Sstevel@tonic-gate 					RIGHT(tp) = sp;
5787c478bd9Sstevel@tonic-gate 
5797c478bd9Sstevel@tonic-gate 					/* doubly link list */
5807c478bd9Sstevel@tonic-gate 					LINKFOR(tp) = np;
5817c478bd9Sstevel@tonic-gate 					LINKBAK(np) = tp;
5827c478bd9Sstevel@tonic-gate 					SETNOTREE(np);
5837c478bd9Sstevel@tonic-gate 
5847c478bd9Sstevel@tonic-gate 					break;
5857c478bd9Sstevel@tonic-gate 				}
5867c478bd9Sstevel@tonic-gate 			}
5877c478bd9Sstevel@tonic-gate 		} else
5887c478bd9Sstevel@tonic-gate 			Root = tp;
5897c478bd9Sstevel@tonic-gate 	}
5907c478bd9Sstevel@tonic-gate 
5917c478bd9Sstevel@tonic-gate 	/* tell next block that this one is free */
5927c478bd9Sstevel@tonic-gate 	SETBIT1(SIZE(NEXT(tp)));
5937c478bd9Sstevel@tonic-gate 
5947c478bd9Sstevel@tonic-gate 	ASSERT(ISBIT0(SIZE(NEXT(tp))));
5957c478bd9Sstevel@tonic-gate }
5967c478bd9Sstevel@tonic-gate 
5977c478bd9Sstevel@tonic-gate /*
5987c478bd9Sstevel@tonic-gate  * Get more core. Gaps in memory are noted as busy blocks.
5997c478bd9Sstevel@tonic-gate  */
6007c478bd9Sstevel@tonic-gate static TREE *
_morecore(size_t size)6017c478bd9Sstevel@tonic-gate _morecore(size_t size)
6027c478bd9Sstevel@tonic-gate {
6037c478bd9Sstevel@tonic-gate 	TREE	*tp;
6047c478bd9Sstevel@tonic-gate 	ssize_t	n, offset;
6057c478bd9Sstevel@tonic-gate 	char	*addr;
6067c478bd9Sstevel@tonic-gate 	ssize_t	nsize;
6077c478bd9Sstevel@tonic-gate 
6087c478bd9Sstevel@tonic-gate 	/* compute new amount of memory to get */
6097c478bd9Sstevel@tonic-gate 	tp = Bottom;
6107c478bd9Sstevel@tonic-gate 	n = (ssize_t)size + 2 * WORDSIZE;
6117c478bd9Sstevel@tonic-gate 	addr = GETCORE(0);
6127c478bd9Sstevel@tonic-gate 
6137c478bd9Sstevel@tonic-gate 	if (addr == ERRCORE)
6147c478bd9Sstevel@tonic-gate 		return (NULL);
6157c478bd9Sstevel@tonic-gate 
6167c478bd9Sstevel@tonic-gate 	/* need to pad size out so that addr is aligned */
6177c478bd9Sstevel@tonic-gate 	if ((((uintptr_t)addr) % ALIGN) != 0)
6187c478bd9Sstevel@tonic-gate 		offset = ALIGN - (uintptr_t)addr % ALIGN;
6197c478bd9Sstevel@tonic-gate 	else
6207c478bd9Sstevel@tonic-gate 		offset = 0;
6217c478bd9Sstevel@tonic-gate 
6227c478bd9Sstevel@tonic-gate #ifndef SEGMENTED
6237c478bd9Sstevel@tonic-gate 	/* if not segmented memory, what we need may be smaller */
6247c478bd9Sstevel@tonic-gate 	if (addr == Baddr) {
6257c478bd9Sstevel@tonic-gate 		n -= WORDSIZE;
6267c478bd9Sstevel@tonic-gate 		if (tp != NULL)
6277c478bd9Sstevel@tonic-gate 			n -= SIZE(tp);
6287c478bd9Sstevel@tonic-gate 	}
6297c478bd9Sstevel@tonic-gate #endif
6307c478bd9Sstevel@tonic-gate 
6317c478bd9Sstevel@tonic-gate 	/* get a multiple of CORESIZE */
6327c478bd9Sstevel@tonic-gate 	n = ((n - 1) / CORESIZE + 1) * CORESIZE;
6337c478bd9Sstevel@tonic-gate 	nsize = n + offset;
6347c478bd9Sstevel@tonic-gate 
6357c478bd9Sstevel@tonic-gate 	/* check if nsize request could overflow in GETCORE */
6367c478bd9Sstevel@tonic-gate 	if ((size_t)nsize > MAX_MALLOC - (uintptr_t)addr) {
6377c478bd9Sstevel@tonic-gate 		errno = ENOMEM;
6387c478bd9Sstevel@tonic-gate 		return (NULL);
6397c478bd9Sstevel@tonic-gate 	}
6407c478bd9Sstevel@tonic-gate 
6417c478bd9Sstevel@tonic-gate 	if ((size_t)nsize <= MAX_GETCORE) {
6427c478bd9Sstevel@tonic-gate 		if (GETCORE(nsize) == ERRCORE)
6437c478bd9Sstevel@tonic-gate 			return (NULL);
6447c478bd9Sstevel@tonic-gate 	} else {
6457c478bd9Sstevel@tonic-gate 		intptr_t	delta;
6467c478bd9Sstevel@tonic-gate 		/*
6477c478bd9Sstevel@tonic-gate 		 * the value required is too big for GETCORE() to deal with
6487c478bd9Sstevel@tonic-gate 		 * in one go, so use GETCORE() at most 2 times instead.
6497c478bd9Sstevel@tonic-gate 		 * Argument to GETCORE() must be multiple of ALIGN.
6507c478bd9Sstevel@tonic-gate 		 * If not, GETCORE(-MAX_GETCORE) will not return brk point
6517c478bd9Sstevel@tonic-gate 		 * to previous value, but will be ALIGN more.
6527c478bd9Sstevel@tonic-gate 		 * This would leave a small hole.
6537c478bd9Sstevel@tonic-gate 		 */
6547c478bd9Sstevel@tonic-gate 		delta = MAX_GETCORE;
6557c478bd9Sstevel@tonic-gate 		while (delta > 0) {
6567c478bd9Sstevel@tonic-gate 			if (GETCORE(delta) == ERRCORE) {
6577c478bd9Sstevel@tonic-gate 				if (addr != GETCORE(0))
6587c478bd9Sstevel@tonic-gate 					(void) GETCORE(-MAX_GETCORE);
6597c478bd9Sstevel@tonic-gate 				return (NULL);
6607c478bd9Sstevel@tonic-gate 			}
6617c478bd9Sstevel@tonic-gate 			nsize -= MAX_GETCORE;
6627c478bd9Sstevel@tonic-gate 			delta = nsize;
6637c478bd9Sstevel@tonic-gate 		}
6647c478bd9Sstevel@tonic-gate 	}
6657c478bd9Sstevel@tonic-gate 
6667c478bd9Sstevel@tonic-gate 	/* contiguous memory */
6677c478bd9Sstevel@tonic-gate 	if (addr == Baddr) {
6687c478bd9Sstevel@tonic-gate 		ASSERT(offset == 0);
6697c478bd9Sstevel@tonic-gate 		if (tp) {
6707c478bd9Sstevel@tonic-gate 			addr = (char *)tp;
6717c478bd9Sstevel@tonic-gate 			n += SIZE(tp) + 2 * WORDSIZE;
6727c478bd9Sstevel@tonic-gate 		} else {
6737c478bd9Sstevel@tonic-gate 			addr = Baddr - WORDSIZE;
6747c478bd9Sstevel@tonic-gate 			n += WORDSIZE;
6757c478bd9Sstevel@tonic-gate 		}
6767c478bd9Sstevel@tonic-gate 	} else
6777c478bd9Sstevel@tonic-gate 		addr += offset;
6787c478bd9Sstevel@tonic-gate 
6797c478bd9Sstevel@tonic-gate 	/* new bottom address */
6807c478bd9Sstevel@tonic-gate 	Baddr = addr + n;
6817c478bd9Sstevel@tonic-gate 
6827c478bd9Sstevel@tonic-gate 	/* new bottom block */
6837c478bd9Sstevel@tonic-gate 	tp = (TREE *)(uintptr_t)addr;
6847c478bd9Sstevel@tonic-gate 	SIZE(tp) = n - 2 * WORDSIZE;
6857c478bd9Sstevel@tonic-gate 	ASSERT((SIZE(tp) % ALIGN) == 0);
6867c478bd9Sstevel@tonic-gate 
6877c478bd9Sstevel@tonic-gate 	/* reserved the last word to head any noncontiguous memory */
6887c478bd9Sstevel@tonic-gate 	SETBIT0(SIZE(NEXT(tp)));
6897c478bd9Sstevel@tonic-gate 
6907c478bd9Sstevel@tonic-gate 	/* non-contiguous memory, free old bottom block */
6917c478bd9Sstevel@tonic-gate 	if (Bottom && Bottom != tp) {
6927c478bd9Sstevel@tonic-gate 		SETBIT0(SIZE(Bottom));
6937c478bd9Sstevel@tonic-gate 		realfree(DATA(Bottom));
6947c478bd9Sstevel@tonic-gate 	}
6957c478bd9Sstevel@tonic-gate 
6967c478bd9Sstevel@tonic-gate 	return (tp);
6977c478bd9Sstevel@tonic-gate }
6987c478bd9Sstevel@tonic-gate 
6997c478bd9Sstevel@tonic-gate 
7007c478bd9Sstevel@tonic-gate /*
7017c478bd9Sstevel@tonic-gate  * Tree rotation functions (BU: bottom-up, TD: top-down)
7027c478bd9Sstevel@tonic-gate  */
7037c478bd9Sstevel@tonic-gate 
7047c478bd9Sstevel@tonic-gate #define	LEFT1(x, y)		\
7057c478bd9Sstevel@tonic-gate 			if ((RIGHT(x) = LEFT(y)) != NULL) PARENT(RIGHT(x)) = x;\
7067c478bd9Sstevel@tonic-gate 			if ((PARENT(y) = PARENT(x)) != NULL)\
7077c478bd9Sstevel@tonic-gate 				if (LEFT(PARENT(x)) == x) LEFT(PARENT(y)) = y;\
7087c478bd9Sstevel@tonic-gate 				else RIGHT(PARENT(y)) = y;\
7097c478bd9Sstevel@tonic-gate 			LEFT(y) = x; PARENT(x) = y
7107c478bd9Sstevel@tonic-gate 
7117c478bd9Sstevel@tonic-gate #define	RIGHT1(x, y)		\
7127c478bd9Sstevel@tonic-gate 			if ((LEFT(x) = RIGHT(y)) != NULL) PARENT(LEFT(x)) = x;\
7137c478bd9Sstevel@tonic-gate 			if ((PARENT(y) = PARENT(x)) != NULL)\
7147c478bd9Sstevel@tonic-gate 				if (LEFT(PARENT(x)) == x) LEFT(PARENT(y)) = y;\
7157c478bd9Sstevel@tonic-gate 				else RIGHT(PARENT(y)) = y;\
7167c478bd9Sstevel@tonic-gate 			RIGHT(y) = x; PARENT(x) = y
7177c478bd9Sstevel@tonic-gate 
7187c478bd9Sstevel@tonic-gate #define	BULEFT2(x, y, z)	\
7197c478bd9Sstevel@tonic-gate 			if ((RIGHT(x) = LEFT(y)) != NULL) PARENT(RIGHT(x)) = x;\
7207c478bd9Sstevel@tonic-gate 			if ((RIGHT(y) = LEFT(z)) != NULL) PARENT(RIGHT(y)) = y;\
7217c478bd9Sstevel@tonic-gate 			if ((PARENT(z) = PARENT(x)) != NULL)\
7227c478bd9Sstevel@tonic-gate 				if (LEFT(PARENT(x)) == x) LEFT(PARENT(z)) = z;\
7237c478bd9Sstevel@tonic-gate 				else RIGHT(PARENT(z)) = z;\
7247c478bd9Sstevel@tonic-gate 			LEFT(z) = y; PARENT(y) = z; LEFT(y) = x; PARENT(x) = y
7257c478bd9Sstevel@tonic-gate 
7267c478bd9Sstevel@tonic-gate #define	BURIGHT2(x, y, z)	\
7277c478bd9Sstevel@tonic-gate 			if ((LEFT(x) = RIGHT(y)) != NULL) PARENT(LEFT(x)) = x;\
7287c478bd9Sstevel@tonic-gate 			if ((LEFT(y) = RIGHT(z)) != NULL) PARENT(LEFT(y)) = y;\
7297c478bd9Sstevel@tonic-gate 			if ((PARENT(z) = PARENT(x)) != NULL)\
7307c478bd9Sstevel@tonic-gate 				if (LEFT(PARENT(x)) == x) LEFT(PARENT(z)) = z;\
7317c478bd9Sstevel@tonic-gate 				else RIGHT(PARENT(z)) = z;\
7327c478bd9Sstevel@tonic-gate 			RIGHT(z) = y; PARENT(y) = z; RIGHT(y) = x; PARENT(x) = y
7337c478bd9Sstevel@tonic-gate 
7347c478bd9Sstevel@tonic-gate #define	TDLEFT2(x, y, z)	\
7357c478bd9Sstevel@tonic-gate 			if ((RIGHT(y) = LEFT(z)) != NULL) PARENT(RIGHT(y)) = y;\
7367c478bd9Sstevel@tonic-gate 			if ((PARENT(z) = PARENT(x)) != NULL)\
7377c478bd9Sstevel@tonic-gate 				if (LEFT(PARENT(x)) == x) LEFT(PARENT(z)) = z;\
7387c478bd9Sstevel@tonic-gate 				else RIGHT(PARENT(z)) = z;\
7397c478bd9Sstevel@tonic-gate 			PARENT(x) = z; LEFT(z) = x;
7407c478bd9Sstevel@tonic-gate 
7417c478bd9Sstevel@tonic-gate #define	TDRIGHT2(x, y, z)	\
7427c478bd9Sstevel@tonic-gate 			if ((LEFT(y) = RIGHT(z)) != NULL) PARENT(LEFT(y)) = y;\
7437c478bd9Sstevel@tonic-gate 			if ((PARENT(z) = PARENT(x)) != NULL)\
7447c478bd9Sstevel@tonic-gate 				if (LEFT(PARENT(x)) == x) LEFT(PARENT(z)) = z;\
7457c478bd9Sstevel@tonic-gate 				else RIGHT(PARENT(z)) = z;\
7467c478bd9Sstevel@tonic-gate 			PARENT(x) = z; RIGHT(z) = x;
7477c478bd9Sstevel@tonic-gate 
7487c478bd9Sstevel@tonic-gate /*
7497c478bd9Sstevel@tonic-gate  * Delete a tree element
7507c478bd9Sstevel@tonic-gate  */
7517c478bd9Sstevel@tonic-gate static void
t_delete(TREE * op)7527c478bd9Sstevel@tonic-gate t_delete(TREE *op)
7537c478bd9Sstevel@tonic-gate {
7547c478bd9Sstevel@tonic-gate 	TREE	*tp, *sp, *gp;
7557c478bd9Sstevel@tonic-gate 
7567c478bd9Sstevel@tonic-gate 	/* if this is a non-tree node */
7577c478bd9Sstevel@tonic-gate 	if (ISNOTREE(op)) {
7587c478bd9Sstevel@tonic-gate 		tp = LINKBAK(op);
7597c478bd9Sstevel@tonic-gate 		if ((sp = LINKFOR(op)) != NULL)
7607c478bd9Sstevel@tonic-gate 			LINKBAK(sp) = tp;
7617c478bd9Sstevel@tonic-gate 		LINKFOR(tp) = sp;
7627c478bd9Sstevel@tonic-gate 		return;
7637c478bd9Sstevel@tonic-gate 	}
7647c478bd9Sstevel@tonic-gate 
7657c478bd9Sstevel@tonic-gate 	/* make op the root of the tree */
7667c478bd9Sstevel@tonic-gate 	if (PARENT(op))
7677c478bd9Sstevel@tonic-gate 		t_splay(op);
7687c478bd9Sstevel@tonic-gate 
7697c478bd9Sstevel@tonic-gate 	/* if this is the start of a list */
7707c478bd9Sstevel@tonic-gate 	if ((tp = LINKFOR(op)) != NULL) {
7717c478bd9Sstevel@tonic-gate 		PARENT(tp) = NULL;
7727c478bd9Sstevel@tonic-gate 		if ((sp = LEFT(op)) != NULL)
7737c478bd9Sstevel@tonic-gate 			PARENT(sp) = tp;
7747c478bd9Sstevel@tonic-gate 		LEFT(tp) = sp;
7757c478bd9Sstevel@tonic-gate 
7767c478bd9Sstevel@tonic-gate 		if ((sp = RIGHT(op)) != NULL)
7777c478bd9Sstevel@tonic-gate 			PARENT(sp) = tp;
7787c478bd9Sstevel@tonic-gate 		RIGHT(tp) = sp;
7797c478bd9Sstevel@tonic-gate 
7807c478bd9Sstevel@tonic-gate 		Root = tp;
7817c478bd9Sstevel@tonic-gate 		return;
7827c478bd9Sstevel@tonic-gate 	}
7837c478bd9Sstevel@tonic-gate 
7847c478bd9Sstevel@tonic-gate 	/* if op has a non-null left subtree */
7857c478bd9Sstevel@tonic-gate 	if ((tp = LEFT(op)) != NULL) {
7867c478bd9Sstevel@tonic-gate 		PARENT(tp) = NULL;
7877c478bd9Sstevel@tonic-gate 
7887c478bd9Sstevel@tonic-gate 		if (RIGHT(op)) {
7897c478bd9Sstevel@tonic-gate 			/* make the right-end of the left subtree its root */
7907c478bd9Sstevel@tonic-gate 			while ((sp = RIGHT(tp)) != NULL) {
7917c478bd9Sstevel@tonic-gate 				if ((gp = RIGHT(sp)) != NULL) {
7927c478bd9Sstevel@tonic-gate 					TDLEFT2(tp, sp, gp);
7937c478bd9Sstevel@tonic-gate 					tp = gp;
7947c478bd9Sstevel@tonic-gate 				} else {
7957c478bd9Sstevel@tonic-gate 					LEFT1(tp, sp);
7967c478bd9Sstevel@tonic-gate 					tp = sp;
7977c478bd9Sstevel@tonic-gate 				}
7987c478bd9Sstevel@tonic-gate 			}
7997c478bd9Sstevel@tonic-gate 
8007c478bd9Sstevel@tonic-gate 			/* hook the right subtree of op to the above elt */
8017c478bd9Sstevel@tonic-gate 			RIGHT(tp) = RIGHT(op);
8027c478bd9Sstevel@tonic-gate 			PARENT(RIGHT(tp)) = tp;
8037c478bd9Sstevel@tonic-gate 		}
8047c478bd9Sstevel@tonic-gate 	} else if ((tp = RIGHT(op)) != NULL)	/* no left subtree */
8057c478bd9Sstevel@tonic-gate 		PARENT(tp) = NULL;
8067c478bd9Sstevel@tonic-gate 
8077c478bd9Sstevel@tonic-gate 	Root = tp;
8087c478bd9Sstevel@tonic-gate }
8097c478bd9Sstevel@tonic-gate 
8107c478bd9Sstevel@tonic-gate /*
8117c478bd9Sstevel@tonic-gate  * Bottom up splaying (simple version).
8127c478bd9Sstevel@tonic-gate  * The basic idea is to roughly cut in half the
8137c478bd9Sstevel@tonic-gate  * path from Root to tp and make tp the new root.
8147c478bd9Sstevel@tonic-gate  */
8157c478bd9Sstevel@tonic-gate static void
t_splay(TREE * tp)8167c478bd9Sstevel@tonic-gate t_splay(TREE *tp)
8177c478bd9Sstevel@tonic-gate {
8187c478bd9Sstevel@tonic-gate 	TREE	*pp, *gp;
8197c478bd9Sstevel@tonic-gate 
8207c478bd9Sstevel@tonic-gate 	/* iterate until tp is the root */
8217c478bd9Sstevel@tonic-gate 	while ((pp = PARENT(tp)) != NULL) {
8227c478bd9Sstevel@tonic-gate 		/* grandparent of tp */
8237c478bd9Sstevel@tonic-gate 		gp = PARENT(pp);
8247c478bd9Sstevel@tonic-gate 
8257c478bd9Sstevel@tonic-gate 		/* x is a left child */
8267c478bd9Sstevel@tonic-gate 		if (LEFT(pp) == tp) {
8277c478bd9Sstevel@tonic-gate 			if (gp && LEFT(gp) == pp) {
8287c478bd9Sstevel@tonic-gate 				BURIGHT2(gp, pp, tp);
8297c478bd9Sstevel@tonic-gate 			} else {
8307c478bd9Sstevel@tonic-gate 				RIGHT1(pp, tp);
8317c478bd9Sstevel@tonic-gate 			}
8327c478bd9Sstevel@tonic-gate 		} else {
8337c478bd9Sstevel@tonic-gate 			ASSERT(RIGHT(pp) == tp);
8347c478bd9Sstevel@tonic-gate 			if (gp && RIGHT(gp) == pp) {
8357c478bd9Sstevel@tonic-gate 				BULEFT2(gp, pp, tp);
8367c478bd9Sstevel@tonic-gate 			} else {
8377c478bd9Sstevel@tonic-gate 				LEFT1(pp, tp);
8387c478bd9Sstevel@tonic-gate 			}
8397c478bd9Sstevel@tonic-gate 		}
8407c478bd9Sstevel@tonic-gate 	}
8417c478bd9Sstevel@tonic-gate }
8427c478bd9Sstevel@tonic-gate 
8437c478bd9Sstevel@tonic-gate 
8447c478bd9Sstevel@tonic-gate /*
8457c478bd9Sstevel@tonic-gate  *	free().
8467c478bd9Sstevel@tonic-gate  *	Performs a delayed free of the block pointed to
8477c478bd9Sstevel@tonic-gate  *	by old. The pointer to old is saved on a list, flist,
8487c478bd9Sstevel@tonic-gate  *	until the next malloc or realloc. At that time, all the
8497c478bd9Sstevel@tonic-gate  *	blocks pointed to in flist are actually freed via
8507c478bd9Sstevel@tonic-gate  *	realfree(). This allows the contents of free blocks to
8517c478bd9Sstevel@tonic-gate  *	remain undisturbed until the next malloc or realloc.
8527c478bd9Sstevel@tonic-gate  */
8537c478bd9Sstevel@tonic-gate void
free(void * old)8547c478bd9Sstevel@tonic-gate free(void *old)
8557c478bd9Sstevel@tonic-gate {
8568cd45542Sraf 	if (!primary_link_map) {
8578cd45542Sraf 		errno = ENOTSUP;
8588cd45542Sraf 		return;
8598cd45542Sraf 	}
8607c478bd9Sstevel@tonic-gate 	assert_no_libc_locks_held();
8618cd45542Sraf 	(void) mutex_lock(&libc_malloc_lock);
8627c478bd9Sstevel@tonic-gate 	_free_unlocked(old);
8638cd45542Sraf 	(void) mutex_unlock(&libc_malloc_lock);
8647c478bd9Sstevel@tonic-gate }
8657c478bd9Sstevel@tonic-gate 
8667c478bd9Sstevel@tonic-gate 
8677c478bd9Sstevel@tonic-gate void
_free_unlocked(void * old)8687c478bd9Sstevel@tonic-gate _free_unlocked(void *old)
8697c478bd9Sstevel@tonic-gate {
8707c478bd9Sstevel@tonic-gate 	int	i;
8717c478bd9Sstevel@tonic-gate 
8728cd45542Sraf 	if (old == NULL)
8737c478bd9Sstevel@tonic-gate 		return;
8747c478bd9Sstevel@tonic-gate 
8757c478bd9Sstevel@tonic-gate 	/*
8767c478bd9Sstevel@tonic-gate 	 * Make sure the same data block is not freed twice.
8777c478bd9Sstevel@tonic-gate 	 * 3 cases are checked.  It returns immediately if either
8787c478bd9Sstevel@tonic-gate 	 * one of the conditions is true.
8797c478bd9Sstevel@tonic-gate 	 *	1. Last freed.
8807c478bd9Sstevel@tonic-gate 	 *	2. Not in use or freed already.
8817c478bd9Sstevel@tonic-gate 	 *	3. In the free list.
8827c478bd9Sstevel@tonic-gate 	 */
8837c478bd9Sstevel@tonic-gate 	if (old == Lfree)
8847c478bd9Sstevel@tonic-gate 		return;
8857c478bd9Sstevel@tonic-gate 	if (!ISBIT0(SIZE(BLOCK(old))))
8867c478bd9Sstevel@tonic-gate 		return;
8877c478bd9Sstevel@tonic-gate 	for (i = 0; i < freeidx; i++)
8887c478bd9Sstevel@tonic-gate 		if (old == flist[i])
8897c478bd9Sstevel@tonic-gate 			return;
8907c478bd9Sstevel@tonic-gate 
8917c478bd9Sstevel@tonic-gate 	if (flist[freeidx] != NULL)
8927c478bd9Sstevel@tonic-gate 		realfree(flist[freeidx]);
8937c478bd9Sstevel@tonic-gate 	flist[freeidx] = Lfree = old;
8947c478bd9Sstevel@tonic-gate 	freeidx = (freeidx + 1) & FREEMASK; /* one forward */
8957c478bd9Sstevel@tonic-gate }
8967c478bd9Sstevel@tonic-gate 
8977c478bd9Sstevel@tonic-gate /*
8987c478bd9Sstevel@tonic-gate  * cleanfree() frees all the blocks pointed to be flist.
8997c478bd9Sstevel@tonic-gate  *
9007c478bd9Sstevel@tonic-gate  * realloc() should work if it is called with a pointer
9017c478bd9Sstevel@tonic-gate  * to a block that was freed since the last call to malloc() or
9027c478bd9Sstevel@tonic-gate  * realloc(). If cleanfree() is called from realloc(), ptr
9037c478bd9Sstevel@tonic-gate  * is set to the old block and that block should not be
9047c478bd9Sstevel@tonic-gate  * freed since it is actually being reallocated.
9057c478bd9Sstevel@tonic-gate  */
9067c478bd9Sstevel@tonic-gate static void
cleanfree(void * ptr)9077c478bd9Sstevel@tonic-gate cleanfree(void *ptr)
9087c478bd9Sstevel@tonic-gate {
9097c478bd9Sstevel@tonic-gate 	char	**flp;
9107c478bd9Sstevel@tonic-gate 
9117c478bd9Sstevel@tonic-gate 	flp = (char **)&(flist[freeidx]);
9127c478bd9Sstevel@tonic-gate 	for (;;) {
9137c478bd9Sstevel@tonic-gate 		if (flp == (char **)&(flist[0]))
9147c478bd9Sstevel@tonic-gate 			flp = (char **)&(flist[FREESIZE]);
9157c478bd9Sstevel@tonic-gate 		if (*--flp == NULL)
9167c478bd9Sstevel@tonic-gate 			break;
9177c478bd9Sstevel@tonic-gate 		if (*flp != ptr)
9187c478bd9Sstevel@tonic-gate 			realfree(*flp);
9197c478bd9Sstevel@tonic-gate 		*flp = NULL;
9207c478bd9Sstevel@tonic-gate 	}
9217c478bd9Sstevel@tonic-gate 	freeidx = 0;
9227c478bd9Sstevel@tonic-gate 	Lfree = NULL;
9237c478bd9Sstevel@tonic-gate }
924