xref: /illumos-gate/usr/src/lib/libmalloc/common/malloc.c (revision eb9a1df2aeb866bf1de4494433b6d7e5fa07b3ae)

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

#include <sys/types.h>

#ifndef debug
#define	NDEBUG
#endif

#include <stdlib.h>
#include <string.h>
#include <errno.h>
#include "assert.h"
#include "malloc.h"
#include "mallint.h"
#include <thread.h>
#include <pthread.h>
#include <synch.h>
#include <unistd.h>
#include <limits.h>

static mutex_t mlock = DEFAULTMUTEX;
static ssize_t freespace(struct holdblk *);
static void *malloc_unlocked(size_t, int);
static void *realloc_unlocked(void *, size_t);
static void free_unlocked(void *);
static void *morecore(size_t);

/*
 * use level memory allocater (malloc, free, realloc)
 *
 *	-malloc, free, realloc and mallopt form a memory allocator
 *	similar to malloc, free, and realloc.  The routines
 *	here are much faster than the original, with slightly worse
 *	space usage (a few percent difference on most input).  They
 *	do not have the property that data in freed blocks is left
 *	untouched until the space is reallocated.
 *
 *	-Memory is kept in the "arena", a singly linked list of blocks.
 *	These blocks are of 3 types.
 *		1. A free block.  This is a block not in use by the
 *		   user.  It has a 3 word header. (See description
 *		   of the free queue.)
 *		2. An allocated block.  This is a block the user has
 *		   requested.  It has only a 1 word header, pointing
 *		   to the next block of any sort.
 *		3. A permanently allocated block.  This covers space
 *		   aquired by the user directly through sbrk().  It
 *		   has a 1 word header, as does 2.
 *	Blocks of type 1 have the lower bit of the pointer to the
 *	nextblock = 0.  Blocks of type 2 and 3 have that bit set,
 *	to mark them busy.
 *
 *	-Unallocated blocks are kept on an unsorted doubly linked
 *	free list.
 *
 *	-Memory is allocated in blocks, with sizes specified by the
 *	user.  A circular first-fit startegy is used, with a roving
 *	head of the free queue, which prevents bunching of small
 *	blocks at the head of the queue.
 *
 *	-Compaction is performed at free time of any blocks immediately
 *	following the freed block.  The freed block will be combined
 *	with a preceding block during the search phase of malloc.
 *	Since a freed block is added at the front of the free queue,
 *	which is moved to the end of the queue if considered and
 *	rejected during the search, fragmentation only occurs if
 *	a block with a contiguious preceding block that is free is
 *	freed and reallocated on the next call to malloc.  The
 *	time savings of this strategy is judged to be worth the
 *	occasional waste of memory.
 *
 *	-Small blocks (of size < MAXSIZE)  are not allocated directly.
 *	A large "holding" block is allocated via a recursive call to
 *	malloc.  This block contains a header and ?????? small blocks.
 *	Holding blocks for a given size of small block (rounded to the
 *	nearest ALIGNSZ bytes) are kept on a queue with the property that any
 *	holding block with an unused small block is in front of any without.
 *	A list of free blocks is kept within the holding block.
 */

/*
 *	description of arena, free queue, holding blocks etc.
 *
 * New compiler and linker does not guarentee order of initialized data.
 * Define freeptr as arena[2-3] to guarentee it follows arena in memory.
 * Later code depends on this order.
 */

static struct header arena[4] = {
	    {0, 0, 0},
	    {0, 0, 0},
	    {0, 0, 0},
	    {0, 0, 0}
	};
				/*
				 * the second word is a minimal block to
				 * start the arena. The first is a busy
				 * block to be pointed to by the last block.
				 */

#define	freeptr (arena + 2)
				/* first and last entry in free list */
static struct header *arenaend;	/* ptr to block marking high end of arena */
static struct header *lastblk;	/* the highest block in the arena */
static struct holdblk **holdhead;   /* pointer to array of head pointers */
				    /* to holding block chains */
/*
 * In order to save time calculating indices, the array is 1 too
 * large, and the first element is unused
 *
 * Variables controlling algorithm, esp. how holding blocs are used
 */
static int numlblks = NUMLBLKS;
static int minhead = MINHEAD;
static int change = 0;	/* != 0, once param changes are no longer allowed */
static int fastct = FASTCT;
static unsigned int maxfast = MAXFAST;
/* number of small block sizes to map to one size */

static int grain = ALIGNSZ;

#ifdef debug
static int case1count = 0;

static void
checkq(void)
{
	register struct header *p;

	p = &freeptr[0];

	/* check forward */
	/*CSTYLED*/
	while (p != &freeptr[1]) {
		p = p->nextfree;
		assert(p->prevfree->nextfree == p);
	}

	/* check backward */
	/*CSTYLED*/
	while (p != &freeptr[0]) {
		p = p->prevfree;
		assert(p->nextfree->prevfree == p);
	}
}
#endif


/*
 * malloc(nbytes) - give a user nbytes to use
 */

void *
malloc(size_t nbytes)
{
	void *ret;

	(void) mutex_lock(&mlock);
	ret = malloc_unlocked(nbytes, 0);
	(void) mutex_unlock(&mlock);
	return (ret);
}

/*
 * Use malloc_unlocked() to get the address to start with; Given this
 * address, find out the closest address that aligns with the request
 * and return that address after doing some house keeping (refer to the
 * ascii art below).
 */
void *
memalign(size_t alignment, size_t size)
{
	void *alloc_buf;
	struct header *hd;
	size_t alloc_size;
	uintptr_t fr;
	static int realloc;

	if (size == 0 || alignment == 0 ||
	    (alignment & (alignment - 1)) != 0) {
		return (NULL);
	}
	if (alignment <= ALIGNSZ)
		return (malloc(size));

	alloc_size = size + alignment;
	if (alloc_size < size) { /* overflow */
		return (NULL);
	}

	(void) mutex_lock(&mlock);
	alloc_buf = malloc_unlocked(alloc_size, 1);
	(void) mutex_unlock(&mlock);

	if (alloc_buf == NULL)
		return (NULL);
	fr = (uintptr_t)alloc_buf;

	fr = (fr + alignment - 1) / alignment * alignment;

	if (fr == (uintptr_t)alloc_buf)
		return (alloc_buf);

	if ((fr - (uintptr_t)alloc_buf) <= HEADSZ) {
		/*
		 * we hit an edge case, where the space ahead of aligned
		 * address is not sufficient to hold 'header' and hence we
		 * can't free it. So double the allocation request.
		 */
		realloc++;
		free(alloc_buf);
		alloc_size = size + alignment*2;
		if (alloc_size < size) {
			return (NULL);
		}

		(void) mutex_lock(&mlock);
		alloc_buf = malloc_unlocked(alloc_size, 1);
		(void) mutex_unlock(&mlock);

		if (alloc_buf == NULL)
			return (NULL);
		fr = (uintptr_t)alloc_buf;

		fr = (fr + alignment - 1) / alignment * alignment;
		if (fr == (uintptr_t)alloc_buf)
			return (alloc_buf);
		if ((fr - (uintptr_t)alloc_buf) <= HEADSZ) {
			fr = fr + alignment;
		}
	}

	/*
	 *	+-------+		+-------+
	 *  +---| <a>   |		| <a>   |--+
	 *  |   +-------+<--alloc_buf-->+-------+  |
	 *  |   |	|		|	|  |
	 *  |   |	|		|	|  |
	 *  |   |	|		|	|  |
	 *  |   |	|	 hd-->  +-------+  |
	 *  |   |	|	    +---|  <b>  |<-+
	 *  |   |	|	    |   +-------+<--- fr
	 *  |   |	|	    |   |	|
	 *  |   |	|	    |   |	|
	 *  |   |	|	    |   |	|
	 *  |   |	|	    |   |	|
	 *  |   |	|	    |   |	|
	 *  |   |	|	    |   |	|
	 *  |   +-------+	    |   +-------+
	 *  +-->|  next |	    +-->|  next |
	 *	+-------+		+-------+
	 *
	 */
	hd = (struct header *)((char *)fr - minhead);
	(void) mutex_lock(&mlock);
	hd->nextblk = ((struct header *)((char *)alloc_buf - minhead))->nextblk;
	((struct header *)((char *)alloc_buf - minhead))->nextblk = SETBUSY(hd);
	(void) mutex_unlock(&mlock);
	free(alloc_buf);
	CHECKQ
	return ((void *)fr);
}

void *
valloc(size_t size)
{
	static unsigned pagesize;
	if (size == 0)
		return (NULL);

	if (!pagesize)
		pagesize = sysconf(_SC_PAGESIZE);

	return (memalign(pagesize, size));
}

/*
 * malloc_unlocked(nbytes, nosmall) - Do the real work for malloc
 */

static void *
malloc_unlocked(size_t nbytes, int nosmall)
{
	struct header *blk;
	size_t nb;	/* size of entire block we need */

	/* on first call, initialize */
	if (freeptr[0].nextfree == GROUND) {
		/* initialize arena */
		arena[1].nextblk = (struct header *)BUSY;
		arena[0].nextblk = (struct header *)BUSY;
		lastblk = arenaend = &(arena[1]);
		/* initialize free queue */
		freeptr[0].nextfree = &(freeptr[1]);
		freeptr[1].nextblk = &(arena[0]);
		freeptr[1].prevfree = &(freeptr[0]);
		/* mark that small blocks not init yet */
	}
	if (nbytes == 0)
		return (NULL);

	if (nbytes <= maxfast && !nosmall) {
		/*
		 * We can allocate out of a holding block
		 */
		struct holdblk *holdblk; /* head of right sized queue */
		struct lblk *lblk;	 /* pointer to a little block */
		struct holdblk *newhold;

		if (!change) {
			int i;
			/*
			 * This allocates space for hold block
			 * pointers by calling malloc recursively.
			 * Maxfast is temporarily set to 0, to
			 * avoid infinite recursion.  allocate
			 * space for an extra ptr so that an index
			 * is just ->blksz/grain, with the first
			 * ptr unused.
			 */
			change = 1;	/* change to algorithm params */
					/* no longer allowed */
			/*
			 * temporarily alter maxfast, to avoid
			 * infinite recursion
			 */
			maxfast = 0;
			holdhead = (struct holdblk **)
			    malloc_unlocked(sizeof (struct holdblk *) *
			    (fastct + 1), 0);
			if (holdhead == NULL)
				return (malloc_unlocked(nbytes, 0));
			for (i = 1; i <= fastct; i++) {
				holdhead[i] = HGROUND;
			}
			maxfast = fastct * grain;
		}
		/*
		 * Note that this uses the absolute min header size (MINHEAD)
		 * unlike the large block case which uses minhead
		 *
		 * round up to nearest multiple of grain
		 * code assumes grain is a multiple of MINHEAD
		 */
		/* round up to grain */
		nb = (nbytes + grain - 1) / grain * grain;
		holdblk = holdhead[nb / grain];
		nb = nb + MINHEAD;
		/*
		 * look for space in the holding block.  Blocks with
		 * space will be in front of those without
		 */
		if ((holdblk != HGROUND) && (holdblk->lfreeq != LGROUND))  {
			/* there is space */
			lblk = holdblk->lfreeq;

			/*
			 * Now make lfreeq point to a free block.
			 * If lblk has been previously allocated and
			 * freed, it has a valid pointer to use.
			 * Otherwise, lblk is at the beginning of
			 * the unallocated blocks at the end of
			 * the holding block, so, if there is room, take
			 * the next space.  If not, mark holdblk full,
			 * and move holdblk to the end of the queue
			 */
			if (lblk < holdblk->unused) {
				/* move to next holdblk, if this one full */
				if ((holdblk->lfreeq =
				    CLRSMAL(lblk->header.nextfree)) ==
				    LGROUND) {
					holdhead[(nb-MINHEAD) / grain] =
					    holdblk->nexthblk;
				}
			} else if (((char *)holdblk->unused + nb) <
			    ((char *)holdblk + HOLDSZ(nb))) {
				holdblk->unused = (struct lblk *)
				    ((char *)holdblk->unused+nb);
				holdblk->lfreeq = holdblk->unused;
			} else {
				holdblk->unused = (struct lblk *)
				    ((char *)holdblk->unused+nb);
				holdblk->lfreeq = LGROUND;
				holdhead[(nb-MINHEAD)/grain] =
				    holdblk->nexthblk;
			}
			/* mark as busy and small */
			lblk->header.holder = (struct holdblk *)SETALL(holdblk);
		} else {
			/* we need a new holding block */
			newhold = (struct holdblk *)
			    malloc_unlocked(HOLDSZ(nb), 0);
			if ((char *)newhold == NULL) {
				return (NULL);
			}
			/* add to head of free queue */
			if (holdblk != HGROUND) {
				newhold->nexthblk = holdblk;
				newhold->prevhblk = holdblk->prevhblk;
				holdblk->prevhblk = newhold;
				newhold->prevhblk->nexthblk = newhold;
			} else {
				newhold->nexthblk = newhold->prevhblk = newhold;
			}
			holdhead[(nb-MINHEAD)/grain] = newhold;
			/* set up newhold */
			lblk = (struct lblk *)(newhold->space);
			newhold->lfreeq = newhold->unused =
			    (struct lblk *)((char *)newhold->space+nb);
			lblk->header.holder = (struct holdblk *)SETALL(newhold);
			newhold->blksz = nb-MINHEAD;
		}
#ifdef debug
		assert(((struct holdblk *)CLRALL(lblk->header.holder))->blksz >=
		    nbytes);
#endif /* debug */
		return ((char *)lblk + MINHEAD);
	} else {
		/*
		 * We need an ordinary block
		 */
		struct header *newblk;	/* used for creating a block */

		/* get number of bytes we need */
		nb = nbytes + minhead;
		nb = (nb + ALIGNSZ - 1) / ALIGNSZ * ALIGNSZ;	/* align */
		nb = (nb > MINBLKSZ) ? nb : MINBLKSZ;
		/*
		 * see if there is a big enough block
		 * If none exists, you will get to freeptr[1].
		 * freeptr[1].next = &arena[0], so when you do the test,
		 * the result is a large positive number, since arena[0]
		 * comes before all blocks.  Arena[0] is marked busy so
		 * that it will not be compacted.  This kludge is for the
		 * sake of the almighty efficiency.
		 */
		/* check that a very large request won't cause an inf. loop */

		if ((freeptr[1].nextblk-&(freeptr[1])) < nb) {
			return (NULL);
		} else {
			struct header *next;		/* following block */
			struct header *nextnext;	/* block after next */

			blk = freeptr;
			do {
				blk = blk->nextfree;
				/* see if we can compact */
				next = blk->nextblk;
				if (!TESTBUSY(nextnext = next->nextblk)) {
					do {
						DELFREEQ(next);
						next = nextnext;
						nextnext = next->nextblk;
					} while (!TESTBUSY(nextnext));
					/*
					 * next will be at most == to lastblk,
					 * but I think the >= test is faster
					 */
					if (next >= arenaend)
						lastblk = blk;
					blk->nextblk = next;
				}
			} while (((char *)(next) - (char *)blk) < nb);
		}
		/*
		 * if we didn't find a block, get more memory
		 */
		if (blk == &(freeptr[1])) {
			/*
			 * careful coding could likely replace
			 * newend with arenaend
			 */
			struct header *newend;	/* new end of arena */
			ssize_t nget;	/* number of words to get */

			/*
			 * Three cases - 1. There is space between arenaend
			 *		    and the break value that will become
			 *		    a permanently allocated block.
			 *		 2. Case 1 is not true, and the last
			 *		    block is allocated.
			 *		 3. Case 1 is not true, and the last
			 *		    block is free
			 */
			if ((newblk = (struct header *)sbrk(0)) !=
			    (struct header *)((char *)arenaend + HEADSZ)) {
				/* case 1 */
#ifdef debug
				if (case1count++ > 0)
				    (void) write(2, "Case 1 hit more that once."
					" brk or sbrk?\n", 41);
#endif
				/* get size to fetch */
				nget = nb + HEADSZ;
				/* round up to a block */
				nget = (nget + BLOCKSZ - 1)/BLOCKSZ * BLOCKSZ;
				assert((uintptr_t)newblk % ALIGNSZ == 0);
				/* get memory */
				if (morecore(nget) == (void *)-1)
					return (NULL);
				/* add to arena */
				newend = (struct header *)((char *)newblk + nget
				    - HEADSZ);
				assert((uintptr_t)newblk % ALIGNSZ == 0);
				newend->nextblk = SETBUSY(&(arena[1]));
/* ???  newblk ?? */
				newblk->nextblk = newend;

				/*
				 * space becomes a permanently allocated block.
				 * This is likely not mt-safe as lock is not
				 * shared with brk or sbrk
				 */
				arenaend->nextblk = SETBUSY(newblk);
				/* adjust other pointers */
				arenaend = newend;
				lastblk = newblk;
				blk = newblk;
			} else if (TESTBUSY(lastblk->nextblk)) {
				/* case 2 */
				nget = (nb + BLOCKSZ - 1) / BLOCKSZ * BLOCKSZ;
				if (morecore(nget) == (void *)-1)
					return (NULL);
				/* block must be word aligned */
				assert(((uintptr_t)newblk%ALIGNSZ) == 0);
				/*
				 * stub at old arenaend becomes first word
				 * in blk
				 */
/* ???  	newblk = arenaend; */

				newend =
				    (struct header *)((char *)arenaend+nget);
				newend->nextblk = SETBUSY(&(arena[1]));
				arenaend->nextblk = newend;
				lastblk = blk = arenaend;
				arenaend = newend;
			} else {
				/* case 3 */
				/*
				 * last block in arena is at end of memory and
				 * is free
				 */
				/* 1.7 had this backward without cast */
				nget = nb -
				    ((char *)arenaend - (char *)lastblk);
				nget = (nget + (BLOCKSZ - 1)) /
				    BLOCKSZ * BLOCKSZ;
				assert(((uintptr_t)newblk % ALIGNSZ) == 0);
				if (morecore(nget) == (void *)-1)
					return (NULL);
				/* combine with last block, put in arena */
				newend = (struct header *)
				    ((char *)arenaend + nget);
				arenaend = lastblk->nextblk = newend;
				newend->nextblk = SETBUSY(&(arena[1]));
				/* set which block to use */
				blk = lastblk;
				DELFREEQ(blk);
			}
		} else {
			struct header *nblk;	/* next block */

			/* take block found of free queue */
			DELFREEQ(blk);
			/*
			 * make head of free queue immediately follow blk,
			 * unless blk was at the end of the queue
			 */
			nblk = blk->nextfree;
			if (nblk != &(freeptr[1])) {
				MOVEHEAD(nblk);
			}
		}
		/* blk now points to an adequate block */
		if (((char *)blk->nextblk - (char *)blk) - nb >= MINBLKSZ) {
			/* carve out the right size block */
			/* newblk will be the remainder */
			newblk = (struct header *)((char *)blk + nb);
			newblk->nextblk = blk->nextblk;
			/* mark the block busy */
			blk->nextblk = SETBUSY(newblk);
			ADDFREEQ(newblk);
			/* if blk was lastblk, make newblk lastblk */
			if (blk == lastblk)
				lastblk = newblk;
		} else {
			/* just mark the block busy */
			blk->nextblk = SETBUSY(blk->nextblk);
		}
	}
	CHECKQ
	assert((char *)CLRALL(blk->nextblk) -
	    ((char *)blk + minhead) >= nbytes);
	assert((char *)CLRALL(blk->nextblk) -
	    ((char *)blk + minhead) < nbytes + MINBLKSZ);
	return ((char *)blk + minhead);
}

/*
 * free(ptr) - free block that user thinks starts at ptr
 *
 *	input - ptr-1 contains the block header.
 *		If the header points forward, we have a normal
 *			block pointing to the next block
 *		if the header points backward, we have a small
 *			block from a holding block.
 *		In both cases, the busy bit must be set
 */

void
free(void *ptr)
{
	(void) mutex_lock(&mlock);
	free_unlocked(ptr);
	(void) mutex_unlock(&mlock);
}

/*
 * free_unlocked(ptr) - Do the real work for free()
 */

void
free_unlocked(void *ptr)
{
	struct holdblk *holdblk;	/* block holding blk */
	struct holdblk *oldhead;	/* former head of the hold block */
					/* queue containing blk's holder */

	if (ptr == NULL)
		return;
	if (TESTSMAL(((struct header *)((char *)ptr - MINHEAD))->nextblk)) {
		struct lblk	*lblk;	/* pointer to freed block */
		ssize_t		offset;	/* choice of header lists */

		lblk = (struct lblk *)CLRBUSY((char *)ptr - MINHEAD);
		assert((struct header *)lblk < arenaend);
		assert((struct header *)lblk > arena);
		/* allow twits (e.g. awk) to free a block twice */
		holdblk = lblk->header.holder;
		if (!TESTBUSY(holdblk))
			return;
		holdblk = (struct holdblk *)CLRALL(holdblk);
		/* put lblk on its hold block's free list */
		lblk->header.nextfree = SETSMAL(holdblk->lfreeq);
		holdblk->lfreeq = lblk;
		/* move holdblk to head of queue, if its not already there */
		offset = holdblk->blksz / grain;
		oldhead = holdhead[offset];
		if (oldhead != holdblk) {
			/* first take out of current spot */
			holdhead[offset] = holdblk;
			holdblk->nexthblk->prevhblk = holdblk->prevhblk;
			holdblk->prevhblk->nexthblk = holdblk->nexthblk;
			/* now add at front */
			holdblk->nexthblk = oldhead;
			holdblk->prevhblk = oldhead->prevhblk;
			oldhead->prevhblk = holdblk;
			holdblk->prevhblk->nexthblk = holdblk;
		}
	} else {
		struct header *blk;	/* real start of block */
		struct header *next;	/* next = blk->nextblk */
		struct header *nextnext;	/* block after next */

		blk = (struct header *)((char *)ptr - minhead);
		next = blk->nextblk;
		/* take care of twits (e.g. awk) who return blocks twice */
		if (!TESTBUSY(next))
			return;
		blk->nextblk = next = CLRBUSY(next);
		ADDFREEQ(blk);
		/* see if we can compact */
		if (!TESTBUSY(nextnext = next->nextblk)) {
			do {
				DELFREEQ(next);
				next = nextnext;
			} while (!TESTBUSY(nextnext = next->nextblk));
			if (next == arenaend) lastblk = blk;
			blk->nextblk = next;
		}
	}
	CHECKQ
}


/*
 * realloc(ptr, size) - give the user a block of size "size", with
 *			    the contents pointed to by ptr.  Free ptr.
 */

void *
realloc(void *ptr, size_t size)
{
	void	*retval;

	(void) mutex_lock(&mlock);
	retval = realloc_unlocked(ptr, size);
	(void) mutex_unlock(&mlock);
	return (retval);
}


/*
 * realloc_unlocked(ptr) - Do the real work for realloc()
 */

static void *
realloc_unlocked(void *ptr, size_t size)
{
	struct header *blk;	/* block ptr is contained in */
	size_t trusize;	/* block size as allocater sees it */
	char *newptr;			/* pointer to user's new block */
	size_t cpysize;	/* amount to copy */
	struct header *next;	/* block after blk */

	if (ptr == NULL)
		return (malloc_unlocked(size, 0));

	if (size == 0) {
		free_unlocked(ptr);
		return (NULL);
	}

	if (TESTSMAL(((struct lblk *)((char *)ptr - MINHEAD))->
	    header.holder)) {
		/*
		 * we have a special small block which can't be expanded
		 *
		 * This makes the assumption that even if the user is
		 * reallocating a free block, malloc doesn't alter the contents
		 * of small blocks
		 */
		newptr = malloc_unlocked(size, 0);
		if (newptr == NULL)
			return (NULL);
		/* this isn't to save time--its to protect the twits */
		if ((char *)ptr != newptr) {
			struct lblk *lblk;
			lblk = (struct lblk *)((char *)ptr - MINHEAD);
			cpysize = ((struct holdblk *)
			    CLRALL(lblk->header.holder))->blksz;
			cpysize = (size > cpysize) ? cpysize : size;
			(void) memcpy(newptr, ptr, cpysize);
			free_unlocked(ptr);
		}
	} else {
		blk = (struct header *)((char *)ptr - minhead);
		next = blk->nextblk;
		/*
		 * deal with twits who reallocate free blocks
		 *
		 * if they haven't reset minblk via getopt, that's
		 * their problem
		 */
		if (!TESTBUSY(next)) {
			DELFREEQ(blk);
			blk->nextblk = SETBUSY(next);
		}
		next = CLRBUSY(next);
		/* make blk as big as possible */
		if (!TESTBUSY(next->nextblk)) {
			do {
				DELFREEQ(next);
				next = next->nextblk;
			} while (!TESTBUSY(next->nextblk));
			blk->nextblk = SETBUSY(next);
			if (next >= arenaend) lastblk = blk;
		}
		/* get size we really need */
		trusize = size+minhead;
		trusize = (trusize + ALIGNSZ - 1)/ALIGNSZ*ALIGNSZ;
		trusize = (trusize >= MINBLKSZ) ? trusize : MINBLKSZ;
		/* see if we have enough */
		/* this isn't really the copy size, but I need a register */
		cpysize = (char *)next - (char *)blk;
		if (cpysize >= trusize) {
			/* carve out the size we need */
			struct header *newblk;	/* remainder */

			if (cpysize - trusize >= MINBLKSZ) {
				/*
				 * carve out the right size block
				 * newblk will be the remainder
				 */
				newblk = (struct header *)((char *)blk +
				    trusize);
				newblk->nextblk = next;
				blk->nextblk = SETBUSY(newblk);
				/* at this point, next is invalid */
				ADDFREEQ(newblk);
				/* if blk was lastblk, make newblk lastblk */
				if (blk == lastblk)
					lastblk = newblk;
			}
			newptr = ptr;
		} else {
			/* bite the bullet, and call malloc */
			cpysize = (size > cpysize) ? cpysize : size;
			newptr = malloc_unlocked(size, 0);
			if (newptr == NULL)
				return (NULL);
			(void) memcpy(newptr, ptr, cpysize);
			free_unlocked(ptr);
		}
	}
	return (newptr);
}


/*
 * calloc - allocate and clear memory block
 */

void *
calloc(size_t num, size_t size)
{
	char *mp;
	size_t total;

	if (num == 0 || size == 0) {
		total = 0;
	} else {
		total = num * size;

		/* check for overflow */
		if ((total / num) != size) {
			errno = ENOMEM;
			return (NULL);
		}
	}

	mp = malloc(total);
	if (mp == NULL)
		return (NULL);
	(void) memset(mp, 0, total);
	return (mp);
}


/*
 * Mallopt - set options for allocation
 *
 *	Mallopt provides for control over the allocation algorithm.
 *	The cmds available are:
 *
 *	M_MXFAST Set maxfast to value.  Maxfast is the size of the
 *		 largest small, quickly allocated block.  Maxfast
 *		 may be set to 0 to disable fast allocation entirely.
 *
 *	M_NLBLKS Set numlblks to value.  Numlblks is the number of
 *		 small blocks per holding block.  Value must be
 *		 greater than 0.
 *
 *	M_GRAIN  Set grain to value.  The sizes of all blocks
 *		 smaller than maxfast are considered to be rounded
 *		 up to the nearest multiple of grain. The default
 *		 value of grain is the smallest number of bytes
 *		 which will allow alignment of any data type.    Grain
 *		 will be rounded up to a multiple of its default,
 *		 and maxsize will be rounded up to a multiple of
 *		 grain.  Value must be greater than 0.
 *
 *	M_KEEP   Retain data in freed block until the next malloc,
 *		 realloc, or calloc.  Value is ignored.
 *		 This option is provided only for compatibility with
 *		 the old version of malloc, and is not recommended.
 *
 *	returns - 0, upon successful completion
 *		 1, if malloc has previously been called or
 *		    if value or cmd have illegal values
 */

int
mallopt(int cmd, int value)
{
	/* disallow changes once a small block is allocated */
	(void) mutex_lock(&mlock);
	if (change) {
		(void) mutex_unlock(&mlock);
		return (1);
	}
	switch (cmd) {
	case M_MXFAST:
		if (value < 0) {
			(void) mutex_unlock(&mlock);
			return (1);
		}
		fastct = (value + grain - 1) / grain;
		maxfast = grain*fastct;
		break;
	case M_NLBLKS:
		if (value <= 1) {
			(void) mutex_unlock(&mlock);
			return (1);
		}
		numlblks = value;
		break;
	case M_GRAIN:
		if (value <= 0) {
			(void) mutex_unlock(&mlock);
			return (1);
		}

		/* round grain up to a multiple of ALIGNSZ */
		grain = (value + ALIGNSZ - 1)/ALIGNSZ*ALIGNSZ;

		/* reduce fastct appropriately */
		fastct = (maxfast + grain - 1) / grain;
		maxfast = grain * fastct;
		break;
	case M_KEEP:
		if (change && holdhead != NULL) {
			(void) mutex_unlock(&mlock);
			return (1);
		}
		minhead = HEADSZ;
		break;
	default:
		(void) mutex_unlock(&mlock);
		return (1);
	}
	(void) mutex_unlock(&mlock);
	return (0);
}

/*
 * mallinfo-provide information about space usage
 *
 *	input - max; mallinfo will return the size of the
 *		largest block < max.
 *
 *	output - a structure containing a description of
 *		 of space usage, defined in malloc.h
 */

struct mallinfo
mallinfo(void)
{
	struct header *blk, *next;	/* ptr to ordinary blocks */
	struct holdblk *hblk;		/* ptr to holding blocks */
	struct mallinfo inf;		/* return value */
	int	i;			/* the ubiquitous counter */
	ssize_t size;			/* size of a block */
	ssize_t fsp;			/* free space in 1 hold block */

	(void) mutex_lock(&mlock);
	(void) memset(&inf, 0, sizeof (struct mallinfo));
	if (freeptr[0].nextfree == GROUND) {
		(void) mutex_unlock(&mlock);
		return (inf);
	}
	blk = CLRBUSY(arena[1].nextblk);
	/* return total space used */
	inf.arena = (char *)arenaend - (char *)blk;

	/*
	 * loop through arena, counting # of blocks, and
	 * and space used by blocks
	 */
	next = CLRBUSY(blk->nextblk);
	while (next != &(arena[1])) {
		inf.ordblks++;
		size = (char *)next - (char *)blk;
		if (TESTBUSY(blk->nextblk)) {
			inf.uordblks += size;
			inf.keepcost += HEADSZ-MINHEAD;
		} else {
			inf.fordblks += size;
		}
		blk = next;
		next = CLRBUSY(blk->nextblk);
	}

	/*
	 * if any holding block have been allocated
	 * then examine space in holding blks
	 */
	if (change && holdhead != NULL) {
		for (i = fastct; i > 0; i--) {	/* loop thru ea. chain */
			hblk = holdhead[i];
			/* do only if chain not empty */
			if (hblk != HGROUND) {
				size = hblk->blksz +
				    sizeof (struct lblk) - sizeof (int);
				do {	/* loop thru 1 hold blk chain */
					inf.hblks++;
					fsp = freespace(hblk);
					inf.fsmblks += fsp;
					inf.usmblks += numlblks*size - fsp;
					inf.smblks += numlblks;
					hblk = hblk->nexthblk;
				} while (hblk != holdhead[i]);
			}
		}
	}
	inf.hblkhd = (inf.smblks / numlblks) * sizeof (struct holdblk);
	/* holding block were counted in ordblks, so subtract off */
	inf.ordblks -= inf.hblks;
	inf.uordblks -= inf.hblkhd + inf.usmblks + inf.fsmblks;
	inf.keepcost -= inf.hblks*(HEADSZ - MINHEAD);
	(void) mutex_unlock(&mlock);
	return (inf);
}


/*
 * freespace - calc. how much space is used in the free
 *		    small blocks in a given holding block
 *
 *	input - hblk = given holding block
 *
 *	returns space used in free small blocks of hblk
 */

static ssize_t
freespace(struct holdblk *holdblk)
{
	struct lblk *lblk;
	ssize_t space = 0;
	ssize_t size;
	struct lblk *unused;

	lblk = CLRSMAL(holdblk->lfreeq);
	size = holdblk->blksz + sizeof (struct lblk) - sizeof (int);
	unused = CLRSMAL(holdblk->unused);
	/* follow free chain */
	while ((lblk != LGROUND) && (lblk != unused)) {
		space += size;
		lblk = CLRSMAL(lblk->header.nextfree);
	}
	space += ((char *)holdblk + HOLDSZ(size)) - (char *)unused;
	return (space);
}

static void *
morecore(size_t bytes)
{
	void * ret;

	if (bytes > LONG_MAX) {
		intptr_t wad;
		/*
		 * The request size is too big. We need to do this in
		 * chunks. Sbrk only takes an int for an arg.
		 */
		if (bytes == ULONG_MAX)
			return ((void *)-1);

		ret = sbrk(0);
		wad = LONG_MAX;
		while (wad > 0) {
			if (sbrk(wad) == (void *)-1) {
				if (ret != sbrk(0))
					(void) sbrk(-LONG_MAX);
				return ((void *)-1);
			}
			bytes -= LONG_MAX;
			wad = bytes;
		}
	} else
		ret = sbrk(bytes);

	return (ret);
}

#ifdef debug
int
check_arena(void)
{
	struct header *blk, *prev, *next;	/* ptr to ordinary blocks */

	(void) mutex_lock(&mlock);
	if (freeptr[0].nextfree == GROUND) {
		(void) mutex_unlock(&mlock);
		return (-1);
	}
	blk = arena + 1;

	/* loop through arena, checking */
	blk = (struct header *)CLRALL(blk->nextblk);
	next = (struct header *)CLRALL(blk->nextblk);
	while (next != arena + 1) {
		assert(blk >= arena + 1);
		assert(blk <= lastblk);
		assert(next >= blk + 1);
		assert(((uintptr_t)((struct header *)blk->nextblk) &
		    (4 | SMAL)) == 0);

		if (TESTBUSY(blk->nextblk) == 0) {
			assert(blk->nextfree >= freeptr);
			assert(blk->prevfree >= freeptr);
			assert(blk->nextfree <= lastblk);
			assert(blk->prevfree <= lastblk);
			assert(((uintptr_t)((struct header *)blk->nextfree) &
			    7) == 0);
			assert(((uintptr_t)((struct header *)blk->prevfree) &
			    7) == 0 || blk->prevfree == freeptr);
		}
		blk = next;
		next = CLRBUSY(blk->nextblk);
	}
	(void) mutex_unlock(&mlock);
	return (0);
}

#define	RSTALLOC	1
#endif

#ifdef RSTALLOC
/*
 * rstalloc - reset alloc routines
 *
 *	description -	return allocated memory and reset
 *			allocation pointers.
 *
 *	Warning - This is for debugging purposes only.
 *		  It will return all memory allocated after
 *		  the first call to malloc, even if some
 *		  of it was fetched by a user's sbrk().
 */

void
rstalloc(void)
{
	(void) mutex_lock(&mlock);
	minhead = MINHEAD;
	grain = ALIGNSZ;
	numlblks = NUMLBLKS;
	fastct = FASTCT;
	maxfast = MAXFAST;
	change = 0;
	if (freeptr[0].nextfree == GROUND) {
		(void) mutex_unlock(&mlock);
		return;
	}
	brk(CLRBUSY(arena[1].nextblk));
	freeptr[0].nextfree = GROUND;
#ifdef debug
	case1count = 0;
#endif
	(void) mutex_unlock(&mlock);
}
#endif	/* RSTALLOC */

/*
 * cfree is an undocumented, obsolete function
 */

/* ARGSUSED1 */
void
cfree(void *p, size_t num, size_t size)
{
	free(p);
}

static void
malloc_prepare()
{
	(void) mutex_lock(&mlock);
}

static void
malloc_release()
{
	(void) mutex_unlock(&mlock);
}

#pragma init(malloc_init)
static void
malloc_init(void)
{
	(void) pthread_atfork(malloc_prepare, malloc_release, malloc_release);
}