OpenSolaris Launch

1 files changed, 906 insertions, 0 deletions

diff --git a/usr/src/lib/libc/port/gen/malloc.c b/usr/src/lib/libc/port/gen/malloc.c
new file mode 100644
index 0000000000..c23ae55335
--- /dev/null
+++ b/usr/src/lib/libc/port/gen/malloc.c
@@ -0,0 +1,906 @@
+/*
+ * CDDL HEADER START
+ *
+ * The contents of this file are subject to the terms of the
+ * Common Development and Distribution License, Version 1.0 only
+ * (the "License").  You may not use this file except in compliance
+ * with the License.
+ *
+ * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
+ * or http://www.opensolaris.org/os/licensing.
+ * See the License for the specific language governing permissions
+ * and limitations under the License.
+ *
+ * When distributing Covered Code, include this CDDL HEADER in each
+ * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
+ * If applicable, add the following below this CDDL HEADER, with the
+ * fields enclosed by brackets "[]" replaced with your own identifying
+ * information: Portions Copyright [yyyy] [name of copyright owner]
+ *
+ * CDDL HEADER END
+ */
+/*
+ * Copyright 2004 Sun Microsystems, Inc.  All rights reserved.
+ * Use is subject to license terms.
+ */
+
+#pragma ident	"%Z%%M%	%I%	%E% SMI"
+
+/*	Copyright (c) 1988 AT&T	*/
+/*	  All Rights Reserved  	*/
+
+
+/*
+ *	Memory management: malloc(), realloc(), free().
+ *
+ *	The following #-parameters may be redefined:
+ *	SEGMENTED: if defined, memory requests are assumed to be
+ *		non-contiguous across calls of GETCORE's.
+ *	GETCORE: a function to get more core memory. If not SEGMENTED,
+ *		GETCORE(0) is assumed to return the next available
+ *		address. Default is 'sbrk'.
+ *	ERRCORE: the error code as returned by GETCORE.
+ *		Default is (char *)(-1).
+ *	CORESIZE: a desired unit (measured in bytes) to be used
+ *		with GETCORE. Default is (1024*ALIGN).
+ *
+ *	This algorithm is based on a  best fit strategy with lists of
+ *	free elts maintained in a self-adjusting binary tree. Each list
+ *	contains all elts of the same size. The tree is ordered by size.
+ *	For results on self-adjusting trees, see the paper:
+ *		Self-Adjusting Binary Trees,
+ *		DD Sleator & RE Tarjan, JACM 1985.
+ *
+ *	The header of a block contains the size of the data part in bytes.
+ *	Since the size of a block is 0%4, the low two bits of the header
+ *	are free and used as follows:
+ *
+ *		BIT0:	1 for busy (block is in use), 0 for free.
+ *		BIT1:	if the block is busy, this bit is 1 if the
+ *			preceding block in contiguous memory is free.
+ *			Otherwise, it is always 0.
+ */
+
+#include "synonyms.h"
+#include "mallint.h"
+#include "mtlib.h"
+
+/*
+ * Some abusers of the system (notably java1.2) acquire __malloc_lock
+ * in order to prevent threads from holding it while they are being
+ * suspended via thr_suspend() or thr_suspend_allmutators().
+ * The new scheme of acquiring it via lmutex_lock() solves the same
+ * problem but causes these old programs to malfunction (acquiring
+ * a lock by both mutex_lock() and lmutex_lock() leads to fatal
+ * inconsistencies).  Therefore, we leave __malloc_lock as an external
+ * variable to satisfy these old programs, but we define a new lock,
+ * private to libc, to do the real locking: libc_malloc_lock
+ */
+mutex_t __malloc_lock = DEFAULTMUTEX;
+
+mutex_t libc_malloc_lock = DEFAULTMUTEX;
+
+static TREE	*Root,		/* root of the free tree */
+		*Bottom,	/* the last free chunk in the arena */
+		*_morecore(size_t);	/* function to get more core */
+
+static char	*Baddr;		/* current high address of the arena */
+static char	*Lfree;		/* last freed block with data intact */
+
+static void	t_delete(TREE *);
+static void	t_splay(TREE *);
+static void	realfree(void *);
+static void	cleanfree(void *);
+static void	*_malloc_unlocked(size_t);
+
+#define	FREESIZE (1<<5) /* size for preserving free blocks until next malloc */
+#define	FREEMASK FREESIZE-1
+
+static void *flist[FREESIZE];	/* list of blocks to be freed on next malloc */
+static int freeidx;		/* index of free blocks in flist % FREESIZE */
+
+/*
+ *	Allocation of small blocks
+ */
+static TREE	*List[MINSIZE/WORDSIZE-1]; /* lists of small blocks */
+
+static void *
+_smalloc(size_t size)
+{
+	TREE	*tp;
+	size_t	i;
+
+	ASSERT(size % WORDSIZE == 0);
+	/* want to return a unique pointer on malloc(0) */
+	if (size == 0)
+		size = WORDSIZE;
+
+	/* list to use */
+	i = size / WORDSIZE - 1;
+
+	if (List[i] == NULL) {
+		TREE *np;
+		int n;
+		/* number of blocks to get at one time */
+#define	NPS (WORDSIZE*8)
+		ASSERT((size + WORDSIZE) * NPS >= MINSIZE);
+
+		/* get NPS of these block types */
+		if ((List[i] = _malloc_unlocked((size + WORDSIZE) * NPS)) == 0)
+			return (0);
+
+		/* make them into a link list */
+		for (n = 0, np = List[i]; n < NPS; ++n) {
+			tp = np;
+			SIZE(tp) = size;
+			np = NEXT(tp);
+			AFTER(tp) = np;
+		}
+		AFTER(tp) = NULL;
+	}
+
+	/* allocate from the head of the queue */
+	tp = List[i];
+	List[i] = AFTER(tp);
+	SETBIT0(SIZE(tp));
+	return (DATA(tp));
+}
+
+void *
+malloc(size_t size)
+{
+	void *ret;
+
+	if (!primary_link_map) {
+		errno = ENOTSUP;
+		return (NULL);
+	}
+	assert_no_libc_locks_held();
+	lmutex_lock(&libc_malloc_lock);
+	ret = _malloc_unlocked(size);
+	lmutex_unlock(&libc_malloc_lock);
+	return (ret);
+}
+
+static void *
+_malloc_unlocked(size_t size)
+{
+	size_t	n;
+	TREE	*tp, *sp;
+	size_t	o_bit1;
+
+	COUNT(nmalloc);
+	ASSERT(WORDSIZE == ALIGN);
+
+	/* check for size that could overflow calculations */
+	if (size > MAX_MALLOC) {
+		errno = ENOMEM;
+		return (NULL);
+	}
+
+	/* make sure that size is 0 mod ALIGN */
+	ROUND(size);
+
+	/* see if the last free block can be used */
+	if (Lfree) {
+		sp = BLOCK(Lfree);
+		n = SIZE(sp);
+		CLRBITS01(n);
+		if (n == size) {
+			/*
+			 * exact match, use it as is
+			 */
+			freeidx = (freeidx + FREESIZE - 1) &
+				FREEMASK; /* 1 back */
+			flist[freeidx] = Lfree = NULL;
+			return (DATA(sp));
+		} else if (size >= MINSIZE && n > size) {
+			/*
+			 * got a big enough piece
+			 */
+			freeidx = (freeidx + FREESIZE - 1) &
+				FREEMASK; /* 1 back */
+			flist[freeidx] = Lfree = NULL;
+			o_bit1 = SIZE(sp) & BIT1;
+			SIZE(sp) = n;
+			goto leftover;
+		}
+	}
+	o_bit1 = 0;
+
+	/* perform free's of space since last malloc */
+	cleanfree(NULL);
+
+	/* small blocks */
+	if (size < MINSIZE)
+		return (_smalloc(size));
+
+	/* search for an elt of the right size */
+	sp = NULL;
+	n  = 0;
+	if (Root) {
+		tp = Root;
+		for (;;) {
+			/* branch left */
+			if (SIZE(tp) >= size) {
+				if (n == 0 || n >= SIZE(tp)) {
+					sp = tp;
+					n = SIZE(tp);
+				}
+				if (LEFT(tp))
+					tp = LEFT(tp);
+				else
+					break;
+			} else { /* branch right */
+				if (RIGHT(tp))
+					tp = RIGHT(tp);
+				else
+					break;
+			}
+		}
+
+		if (sp) {
+			t_delete(sp);
+		} else if (tp != Root) {
+			/* make the searched-to element the root */
+			t_splay(tp);
+			Root = tp;
+		}
+	}
+
+	/* if found none fitted in the tree */
+	if (!sp) {
+		if (Bottom && size <= SIZE(Bottom)) {
+			sp = Bottom;
+			CLRBITS01(SIZE(sp));
+		} else if ((sp = _morecore(size)) == NULL) /* no more memory */
+			return (NULL);
+	}
+
+	/* tell the forward neighbor that we're busy */
+	CLRBIT1(SIZE(NEXT(sp)));
+
+	ASSERT(ISBIT0(SIZE(NEXT(sp))));
+
+leftover:
+	/* if the leftover is enough for a new free piece */
+	if ((n = (SIZE(sp) - size)) >= MINSIZE + WORDSIZE) {
+		n -= WORDSIZE;
+		SIZE(sp) = size;
+		tp = NEXT(sp);
+		SIZE(tp) = n|BIT0;
+		realfree(DATA(tp));
+	} else if (BOTTOM(sp))
+		Bottom = NULL;
+
+	/* return the allocated space */
+	SIZE(sp) |= BIT0 | o_bit1;
+	return (DATA(sp));
+}
+
+
+/*
+ * realloc().
+ *
+ * If the block size is increasing, we try forward merging first.
+ * This is not best-fit but it avoids some data recopying.
+ */
+void *
+realloc(void *old, size_t size)
+{
+	TREE	*tp, *np;
+	size_t	ts;
+	char	*new;
+
+	if (!primary_link_map) {
+		errno = ENOTSUP;
+		return (NULL);
+	}
+
+	assert_no_libc_locks_held();
+	COUNT(nrealloc);
+
+	/* check for size that could overflow calculations */
+	if (size > MAX_MALLOC) {
+		errno = ENOMEM;
+		return (NULL);
+	}
+
+	/* pointer to the block */
+	lmutex_lock(&libc_malloc_lock);
+	if (old == NULL) {
+		new = _malloc_unlocked(size);
+		lmutex_unlock(&libc_malloc_lock);
+		return (new);
+	}
+
+	/* perform free's of space since last malloc */
+	cleanfree(old);
+
+	/* make sure that size is 0 mod ALIGN */
+	ROUND(size);
+
+	tp = BLOCK(old);
+	ts = SIZE(tp);
+
+	/* if the block was freed, data has been destroyed. */
+	if (!ISBIT0(ts)) {
+		lmutex_unlock(&libc_malloc_lock);
+		return (NULL);
+	}
+
+	/* nothing to do */
+	CLRBITS01(SIZE(tp));
+	if (size == SIZE(tp)) {
+		SIZE(tp) = ts;
+		lmutex_unlock(&libc_malloc_lock);
+		return (old);
+	}
+
+	/* special cases involving small blocks */
+	if (size < MINSIZE || SIZE(tp) < MINSIZE) {
+		/* free is size is zero */
+		if (size == 0) {
+			SETOLD01(SIZE(tp), ts);
+			_free_unlocked(old);
+			lmutex_unlock(&libc_malloc_lock);
+			return (NULL);
+		} else {
+			goto call_malloc;
+		}
+	}
+
+	/* block is increasing in size, try merging the next block */
+	if (size > SIZE(tp)) {
+		np = NEXT(tp);
+		if (!ISBIT0(SIZE(np))) {
+			ASSERT(SIZE(np) >= MINSIZE);
+			ASSERT(!ISBIT1(SIZE(np)));
+			SIZE(tp) += SIZE(np) + WORDSIZE;
+			if (np != Bottom)
+				t_delete(np);
+			else
+				Bottom = NULL;
+			CLRBIT1(SIZE(NEXT(np)));
+		}
+
+#ifndef SEGMENTED
+		/* not enough & at TRUE end of memory, try extending core */
+		if (size > SIZE(tp) && BOTTOM(tp) && GETCORE(0) == Baddr) {
+			Bottom = tp;
+			if ((tp = _morecore(size)) == NULL) {
+				tp = Bottom;
+				Bottom = NULL;
+				}
+		}
+#endif
+	}
+
+	/* got enough space to use */
+	if (size <= SIZE(tp)) {
+		size_t n;
+
+chop_big:
+		if ((n = (SIZE(tp) - size)) >= MINSIZE + WORDSIZE) {
+			n -= WORDSIZE;
+			SIZE(tp) = size;
+			np = NEXT(tp);
+			SIZE(np) = n|BIT0;
+			realfree(DATA(np));
+		} else if (BOTTOM(tp))
+			Bottom = NULL;
+
+		/* the previous block may be free */
+		SETOLD01(SIZE(tp), ts);
+		lmutex_unlock(&libc_malloc_lock);
+		return (old);
+	}
+
+	/* call malloc to get a new block */
+call_malloc:
+	SETOLD01(SIZE(tp), ts);
+	if ((new = _malloc_unlocked(size)) != NULL) {
+		CLRBITS01(ts);
+		if (ts > size)
+			ts = size;
+		MEMCOPY(new, old, ts);
+		_free_unlocked(old);
+		lmutex_unlock(&libc_malloc_lock);
+		return (new);
+	}
+
+	/*
+	 * Attempt special case recovery allocations since malloc() failed:
+	 *
+	 * 1. size <= SIZE(tp) < MINSIZE
+	 *	Simply return the existing block
+	 * 2. SIZE(tp) < size < MINSIZE
+	 *	malloc() may have failed to allocate the chunk of
+	 *	small blocks. Try asking for MINSIZE bytes.
+	 * 3. size < MINSIZE <= SIZE(tp)
+	 *	malloc() may have failed as with 2.  Change to
+	 *	MINSIZE allocation which is taken from the beginning
+	 *	of the current block.
+	 * 4. MINSIZE <= SIZE(tp) < size
+	 *	If the previous block is free and the combination of
+	 *	these two blocks has at least size bytes, then merge
+	 *	the two blocks copying the existing contents backwards.
+	 */
+	CLRBITS01(SIZE(tp));
+	if (SIZE(tp) < MINSIZE) {
+		if (size < SIZE(tp)) {			/* case 1. */
+			SETOLD01(SIZE(tp), ts);
+			lmutex_unlock(&libc_malloc_lock);
+			return (old);
+		} else if (size < MINSIZE) {		/* case 2. */
+			size = MINSIZE;
+			goto call_malloc;
+		}
+	} else if (size < MINSIZE) {			/* case 3. */
+		size = MINSIZE;
+		goto chop_big;
+	} else if (ISBIT1(ts) &&
+	    (SIZE(np = LAST(tp)) + SIZE(tp) + WORDSIZE) >= size) {
+		ASSERT(!ISBIT0(SIZE(np)));
+		t_delete(np);
+		SIZE(np) += SIZE(tp) + WORDSIZE;
+		/*
+		 * Since the copy may overlap, use memmove() if available.
+		 * Otherwise, copy by hand.
+		 */
+		(void) memmove(DATA(np), old, SIZE(tp));
+		old = DATA(np);
+		tp = np;
+		CLRBIT1(ts);
+		goto chop_big;
+	}
+	SETOLD01(SIZE(tp), ts);
+	lmutex_unlock(&libc_malloc_lock);
+	return (NULL);
+}
+
+
+/*
+ * realfree().
+ *
+ * Coalescing of adjacent free blocks is done first.
+ * Then, the new free block is leaf-inserted into the free tree
+ * without splaying. This strategy does not guarantee the amortized
+ * O(nlogn) behaviour for the insert/delete/find set of operations
+ * on the tree. In practice, however, free is much more infrequent
+ * than malloc/realloc and the tree searches performed by these
+ * functions adequately keep the tree in balance.
+ */
+static void
+realfree(void *old)
+{
+	TREE	*tp, *sp, *np;
+	size_t	ts, size;
+
+	COUNT(nfree);
+
+	/* pointer to the block */
+	tp = BLOCK(old);
+	ts = SIZE(tp);
+	if (!ISBIT0(ts))
+		return;
+	CLRBITS01(SIZE(tp));
+
+	/* small block, put it in the right linked list */
+	if (SIZE(tp) < MINSIZE) {
+		ASSERT(SIZE(tp) / WORDSIZE >= 1);
+		ts = SIZE(tp) / WORDSIZE - 1;
+		AFTER(tp) = List[ts];
+		List[ts] = tp;
+		return;
+	}
+
+	/* see if coalescing with next block is warranted */
+	np = NEXT(tp);
+	if (!ISBIT0(SIZE(np))) {
+		if (np != Bottom)
+			t_delete(np);
+		SIZE(tp) += SIZE(np) + WORDSIZE;
+	}
+
+	/* the same with the preceding block */
+	if (ISBIT1(ts)) {
+		np = LAST(tp);
+		ASSERT(!ISBIT0(SIZE(np)));
+		ASSERT(np != Bottom);
+		t_delete(np);
+		SIZE(np) += SIZE(tp) + WORDSIZE;
+		tp = np;
+	}
+
+	/* initialize tree info */
+	PARENT(tp) = LEFT(tp) = RIGHT(tp) = LINKFOR(tp) = NULL;
+
+	/* the last word of the block contains self's address */
+	*(SELFP(tp)) = tp;
+
+	/* set bottom block, or insert in the free tree */
+	if (BOTTOM(tp))
+		Bottom = tp;
+	else {
+		/* search for the place to insert */
+		if (Root) {
+			size = SIZE(tp);
+			np = Root;
+			for (;;) {
+				if (SIZE(np) > size) {
+					if (LEFT(np))
+						np = LEFT(np);
+					else {
+						LEFT(np) = tp;
+						PARENT(tp) = np;
+						break;
+					}
+				} else if (SIZE(np) < size) {
+					if (RIGHT(np))
+						np = RIGHT(np);
+					else {
+						RIGHT(np) = tp;
+						PARENT(tp) = np;
+						break;
+					}
+				} else {
+					if ((sp = PARENT(np)) != NULL) {
+						if (np == LEFT(sp))
+							LEFT(sp) = tp;
+						else
+							RIGHT(sp) = tp;
+						PARENT(tp) = sp;
+					} else
+						Root = tp;
+
+					/* insert to head of list */
+					if ((sp = LEFT(np)) != NULL)
+						PARENT(sp) = tp;
+					LEFT(tp) = sp;
+
+					if ((sp = RIGHT(np)) != NULL)
+						PARENT(sp) = tp;
+					RIGHT(tp) = sp;
+
+					/* doubly link list */
+					LINKFOR(tp) = np;
+					LINKBAK(np) = tp;
+					SETNOTREE(np);
+
+					break;
+				}
+			}
+		} else
+			Root = tp;
+	}
+
+	/* tell next block that this one is free */
+	SETBIT1(SIZE(NEXT(tp)));
+
+	ASSERT(ISBIT0(SIZE(NEXT(tp))));
+}
+
+/*
+ * Get more core. Gaps in memory are noted as busy blocks.
+ */
+static TREE *
+_morecore(size_t size)
+{
+	TREE	*tp;
+	ssize_t	n, offset;
+	char	*addr;
+	ssize_t	nsize;
+
+	/* compute new amount of memory to get */
+	tp = Bottom;
+	n = (ssize_t)size + 2 * WORDSIZE;
+	addr = GETCORE(0);
+
+	if (addr == ERRCORE)
+		return (NULL);
+
+	/* need to pad size out so that addr is aligned */
+	if ((((uintptr_t)addr) % ALIGN) != 0)
+		offset = ALIGN - (uintptr_t)addr % ALIGN;
+	else
+		offset = 0;
+
+#ifndef SEGMENTED
+	/* if not segmented memory, what we need may be smaller */
+	if (addr == Baddr) {
+		n -= WORDSIZE;
+		if (tp != NULL)
+			n -= SIZE(tp);
+	}
+#endif
+
+	/* get a multiple of CORESIZE */
+	n = ((n - 1) / CORESIZE + 1) * CORESIZE;
+	nsize = n + offset;
+
+	/* check if nsize request could overflow in GETCORE */
+	if ((size_t)nsize > MAX_MALLOC - (uintptr_t)addr) {
+		errno = ENOMEM;
+		return (NULL);
+	}
+
+	if ((size_t)nsize <= MAX_GETCORE) {
+		if (GETCORE(nsize) == ERRCORE)
+			return (NULL);
+	} else {
+		intptr_t	delta;
+		/*
+		 * the value required is too big for GETCORE() to deal with
+		 * in one go, so use GETCORE() at most 2 times instead.
+		 * Argument to GETCORE() must be multiple of ALIGN.
+		 * If not, GETCORE(-MAX_GETCORE) will not return brk point
+		 * to previous value, but will be ALIGN more.
+		 * This would leave a small hole.
+		 */
+		delta = MAX_GETCORE;
+		while (delta > 0) {
+			if (GETCORE(delta) == ERRCORE) {
+				if (addr != GETCORE(0))
+					(void) GETCORE(-MAX_GETCORE);
+				return (NULL);
+			}
+			nsize -= MAX_GETCORE;
+			delta = nsize;
+		}
+	}
+
+	/* contiguous memory */
+	if (addr == Baddr) {
+		ASSERT(offset == 0);
+		if (tp) {
+			addr = (char *)tp;
+			n += SIZE(tp) + 2 * WORDSIZE;
+		} else {
+			addr = Baddr - WORDSIZE;
+			n += WORDSIZE;
+		}
+	} else
+		addr += offset;
+
+	/* new bottom address */
+	Baddr = addr + n;
+
+	/* new bottom block */
+	tp = (TREE *)(uintptr_t)addr;
+	SIZE(tp) = n - 2 * WORDSIZE;
+	ASSERT((SIZE(tp) % ALIGN) == 0);
+
+	/* reserved the last word to head any noncontiguous memory */
+	SETBIT0(SIZE(NEXT(tp)));
+
+	/* non-contiguous memory, free old bottom block */
+	if (Bottom && Bottom != tp) {
+		SETBIT0(SIZE(Bottom));
+		realfree(DATA(Bottom));
+	}
+
+	return (tp);
+}
+
+
+/*
+ * Tree rotation functions (BU: bottom-up, TD: top-down)
+ */
+
+#define	LEFT1(x, y)		\
+			if ((RIGHT(x) = LEFT(y)) != NULL) PARENT(RIGHT(x)) = x;\
+			if ((PARENT(y) = PARENT(x)) != NULL)\
+				if (LEFT(PARENT(x)) == x) LEFT(PARENT(y)) = y;\
+				else RIGHT(PARENT(y)) = y;\
+			LEFT(y) = x; PARENT(x) = y
+
+#define	RIGHT1(x, y)		\
+			if ((LEFT(x) = RIGHT(y)) != NULL) PARENT(LEFT(x)) = x;\
+			if ((PARENT(y) = PARENT(x)) != NULL)\
+				if (LEFT(PARENT(x)) == x) LEFT(PARENT(y)) = y;\
+				else RIGHT(PARENT(y)) = y;\
+			RIGHT(y) = x; PARENT(x) = y
+
+#define	BULEFT2(x, y, z)	\
+			if ((RIGHT(x) = LEFT(y)) != NULL) PARENT(RIGHT(x)) = x;\
+			if ((RIGHT(y) = LEFT(z)) != NULL) PARENT(RIGHT(y)) = y;\
+			if ((PARENT(z) = PARENT(x)) != NULL)\
+				if (LEFT(PARENT(x)) == x) LEFT(PARENT(z)) = z;\
+				else RIGHT(PARENT(z)) = z;\
+			LEFT(z) = y; PARENT(y) = z; LEFT(y) = x; PARENT(x) = y
+
+#define	BURIGHT2(x, y, z)	\
+			if ((LEFT(x) = RIGHT(y)) != NULL) PARENT(LEFT(x)) = x;\
+			if ((LEFT(y) = RIGHT(z)) != NULL) PARENT(LEFT(y)) = y;\
+			if ((PARENT(z) = PARENT(x)) != NULL)\
+				if (LEFT(PARENT(x)) == x) LEFT(PARENT(z)) = z;\
+				else RIGHT(PARENT(z)) = z;\
+			RIGHT(z) = y; PARENT(y) = z; RIGHT(y) = x; PARENT(x) = y
+
+#define	TDLEFT2(x, y, z)	\
+			if ((RIGHT(y) = LEFT(z)) != NULL) PARENT(RIGHT(y)) = y;\
+			if ((PARENT(z) = PARENT(x)) != NULL)\
+				if (LEFT(PARENT(x)) == x) LEFT(PARENT(z)) = z;\
+				else RIGHT(PARENT(z)) = z;\
+			PARENT(x) = z; LEFT(z) = x;
+
+#define	TDRIGHT2(x, y, z)	\
+			if ((LEFT(y) = RIGHT(z)) != NULL) PARENT(LEFT(y)) = y;\
+			if ((PARENT(z) = PARENT(x)) != NULL)\
+				if (LEFT(PARENT(x)) == x) LEFT(PARENT(z)) = z;\
+				else RIGHT(PARENT(z)) = z;\
+			PARENT(x) = z; RIGHT(z) = x;
+
+/*
+ * Delete a tree element
+ */
+static void
+t_delete(TREE *op)
+{
+	TREE	*tp, *sp, *gp;
+
+	/* if this is a non-tree node */
+	if (ISNOTREE(op)) {
+		tp = LINKBAK(op);
+		if ((sp = LINKFOR(op)) != NULL)
+			LINKBAK(sp) = tp;
+		LINKFOR(tp) = sp;
+		return;
+	}
+
+	/* make op the root of the tree */
+	if (PARENT(op))
+		t_splay(op);
+
+	/* if this is the start of a list */
+	if ((tp = LINKFOR(op)) != NULL) {
+		PARENT(tp) = NULL;
+		if ((sp = LEFT(op)) != NULL)
+			PARENT(sp) = tp;
+		LEFT(tp) = sp;
+
+		if ((sp = RIGHT(op)) != NULL)
+			PARENT(sp) = tp;
+		RIGHT(tp) = sp;
+
+		Root = tp;
+		return;
+	}
+
+	/* if op has a non-null left subtree */
+	if ((tp = LEFT(op)) != NULL) {
+		PARENT(tp) = NULL;
+
+		if (RIGHT(op)) {
+			/* make the right-end of the left subtree its root */
+			while ((sp = RIGHT(tp)) != NULL) {
+				if ((gp = RIGHT(sp)) != NULL) {
+					TDLEFT2(tp, sp, gp);
+					tp = gp;
+				} else {
+					LEFT1(tp, sp);
+					tp = sp;
+				}
+			}
+
+			/* hook the right subtree of op to the above elt */
+			RIGHT(tp) = RIGHT(op);
+			PARENT(RIGHT(tp)) = tp;
+		}
+	} else if ((tp = RIGHT(op)) != NULL)	/* no left subtree */
+		PARENT(tp) = NULL;
+
+	Root = tp;
+}
+
+/*
+ * Bottom up splaying (simple version).
+ * The basic idea is to roughly cut in half the
+ * path from Root to tp and make tp the new root.
+ */
+static void
+t_splay(TREE *tp)
+{
+	TREE	*pp, *gp;
+
+	/* iterate until tp is the root */
+	while ((pp = PARENT(tp)) != NULL) {
+		/* grandparent of tp */
+		gp = PARENT(pp);
+
+		/* x is a left child */
+		if (LEFT(pp) == tp) {
+			if (gp && LEFT(gp) == pp) {
+				BURIGHT2(gp, pp, tp);
+			} else {
+				RIGHT1(pp, tp);
+			}
+		} else {
+			ASSERT(RIGHT(pp) == tp);
+			if (gp && RIGHT(gp) == pp) {
+				BULEFT2(gp, pp, tp);
+			} else {
+				LEFT1(pp, tp);
+			}
+		}
+	}
+}
+
+
+/*
+ *	free().
+ *	Performs a delayed free of the block pointed to
+ *	by old. The pointer to old is saved on a list, flist,
+ *	until the next malloc or realloc. At that time, all the
+ *	blocks pointed to in flist are actually freed via
+ *	realfree(). This allows the contents of free blocks to
+ *	remain undisturbed until the next malloc or realloc.
+ */
+void
+free(void *old)
+{
+	assert_no_libc_locks_held();
+	lmutex_lock(&libc_malloc_lock);
+	_free_unlocked(old);
+	lmutex_unlock(&libc_malloc_lock);
+}
+
+
+void
+_free_unlocked(void *old)
+{
+	int	i;
+
+	if (old == NULL || !primary_link_map)
+		return;
+
+	/*
+	 * Make sure the same data block is not freed twice.
+	 * 3 cases are checked.  It returns immediately if either
+	 * one of the conditions is true.
+	 *	1. Last freed.
+	 *	2. Not in use or freed already.
+	 *	3. In the free list.
+	 */
+	if (old == Lfree)
+		return;
+	if (!ISBIT0(SIZE(BLOCK(old))))
+		return;
+	for (i = 0; i < freeidx; i++)
+		if (old == flist[i])
+			return;
+
+	if (flist[freeidx] != NULL)
+		realfree(flist[freeidx]);
+	flist[freeidx] = Lfree = old;
+	freeidx = (freeidx + 1) & FREEMASK; /* one forward */
+}
+
+/*
+ * cleanfree() frees all the blocks pointed to be flist.
+ *
+ * realloc() should work if it is called with a pointer
+ * to a block that was freed since the last call to malloc() or
+ * realloc(). If cleanfree() is called from realloc(), ptr
+ * is set to the old block and that block should not be
+ * freed since it is actually being reallocated.
+ */
+static void
+cleanfree(void *ptr)
+{
+	char	**flp;
+
+	flp = (char **)&(flist[freeidx]);
+	for (;;) {
+		if (flp == (char **)&(flist[0]))
+			flp = (char **)&(flist[FREESIZE]);
+		if (*--flp == NULL)
+			break;
+		if (*flp != ptr)
+			realfree(*flp);
+		*flp = NULL;
+	}
+	freeidx = 0;
+	Lfree = NULL;
+}