/*

 * CDDL HEADER START

 *

 * The contents of this file are subject to the terms of the

 * Common Development and Distribution License (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 2008 Sun Microsystems, Inc.  All rights reserved.

 * Use is subject to license terms.

 */

/*	Copyright (c) 1988 AT&T	*/

/*	  All Rights Reserved  	*/

#pragma ident	"%Z%%M%	%I%	%E% SMI"

/*

 *	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 "lint.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().

 * This never worked when alternate malloc() libraries were used

 * because they don't use __malloc_lock for their locking strategy.

 * 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.  This puts libc's malloc() package

 * on the same footing as all other malloc packages.

 */

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 */

/*

 * Interfaces used only by atfork_init() functions.

 */

void

malloc_locks(void)

{

	(void) mutex_lock(&libc_malloc_lock);

}

void

malloc_unlocks(void)

{

	(void) mutex_unlock(&libc_malloc_lock);

}

/*

 *	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();

	(void) mutex_lock(&libc_malloc_lock);

	ret = _malloc_unlocked(size);

	(void) mutex_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 */

	(void) mutex_lock(&libc_malloc_lock);

	if (old == NULL) {

		new = _malloc_unlocked(size);

		(void) mutex_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)) {

		(void) mutex_unlock(&libc_malloc_lock);

		return (NULL);

	}

	/* nothing to do */

	CLRBITS01(SIZE(tp));

	if (size == SIZE(tp)) {

		SIZE(tp) = ts;

		(void) mutex_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);

			(void) mutex_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);

		(void) mutex_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);

		(void) mutex_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);

			(void) mutex_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);

	(void) mutex_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);