xref: /illumos-gate/usr/src/lib/libmalloc/common/malloc.c (revision 31c6d826a7f7a4ee7d83c8e99f25d82a4a248076)
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
54088bb40Sraf  * Common Development and Distribution License (the "License").
64088bb40Sraf  * 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  */
214088bb40Sraf 
221d530678Sraf /*
237257d1b4Sraf  * Copyright 2008 Sun Microsystems, Inc.  All rights reserved.
241d530678Sraf  * Use is subject to license terms.
251d530678Sraf  */
261d530678Sraf 
277c478bd9Sstevel@tonic-gate /*	Copyright (c) 1988 AT&T	*/
287c478bd9Sstevel@tonic-gate /*	  All Rights Reserved  	*/
297c478bd9Sstevel@tonic-gate 
307c478bd9Sstevel@tonic-gate #include <sys/types.h>
317c478bd9Sstevel@tonic-gate 
327c478bd9Sstevel@tonic-gate #ifndef debug
337c478bd9Sstevel@tonic-gate #define	NDEBUG
347c478bd9Sstevel@tonic-gate #endif
357c478bd9Sstevel@tonic-gate 
367c478bd9Sstevel@tonic-gate #include <stdlib.h>
377c478bd9Sstevel@tonic-gate #include <string.h>
38*31c6d826SRichard Lowe #include <errno.h>
397c478bd9Sstevel@tonic-gate #include "assert.h"
407c478bd9Sstevel@tonic-gate #include "malloc.h"
417c478bd9Sstevel@tonic-gate #include "mallint.h"
427c478bd9Sstevel@tonic-gate #include <thread.h>
431d530678Sraf #include <pthread.h>
447c478bd9Sstevel@tonic-gate #include <synch.h>
457c478bd9Sstevel@tonic-gate #include <unistd.h>
467c478bd9Sstevel@tonic-gate #include <limits.h>
477c478bd9Sstevel@tonic-gate 
487c478bd9Sstevel@tonic-gate static mutex_t mlock = DEFAULTMUTEX;
497c478bd9Sstevel@tonic-gate static ssize_t freespace(struct holdblk *);
507c478bd9Sstevel@tonic-gate static void *malloc_unlocked(size_t, int);
517c478bd9Sstevel@tonic-gate static void *realloc_unlocked(void *, size_t);
527c478bd9Sstevel@tonic-gate static void free_unlocked(void *);
537c478bd9Sstevel@tonic-gate static void *morecore(size_t);
547c478bd9Sstevel@tonic-gate 
557c478bd9Sstevel@tonic-gate /*
567c478bd9Sstevel@tonic-gate  * use level memory allocater (malloc, free, realloc)
577c478bd9Sstevel@tonic-gate  *
587c478bd9Sstevel@tonic-gate  *	-malloc, free, realloc and mallopt form a memory allocator
597c478bd9Sstevel@tonic-gate  *	similar to malloc, free, and realloc.  The routines
607c478bd9Sstevel@tonic-gate  *	here are much faster than the original, with slightly worse
617c478bd9Sstevel@tonic-gate  *	space usage (a few percent difference on most input).  They
627c478bd9Sstevel@tonic-gate  *	do not have the property that data in freed blocks is left
637c478bd9Sstevel@tonic-gate  *	untouched until the space is reallocated.
647c478bd9Sstevel@tonic-gate  *
657c478bd9Sstevel@tonic-gate  *	-Memory is kept in the "arena", a singly linked list of blocks.
667c478bd9Sstevel@tonic-gate  *	These blocks are of 3 types.
677c478bd9Sstevel@tonic-gate  *		1. A free block.  This is a block not in use by the
687c478bd9Sstevel@tonic-gate  *		   user.  It has a 3 word header. (See description
697c478bd9Sstevel@tonic-gate  *		   of the free queue.)
707c478bd9Sstevel@tonic-gate  *		2. An allocated block.  This is a block the user has
717c478bd9Sstevel@tonic-gate  *		   requested.  It has only a 1 word header, pointing
727c478bd9Sstevel@tonic-gate  *		   to the next block of any sort.
737c478bd9Sstevel@tonic-gate  *		3. A permanently allocated block.  This covers space
747c478bd9Sstevel@tonic-gate  *		   aquired by the user directly through sbrk().  It
757c478bd9Sstevel@tonic-gate  *		   has a 1 word header, as does 2.
767c478bd9Sstevel@tonic-gate  *	Blocks of type 1 have the lower bit of the pointer to the
777c478bd9Sstevel@tonic-gate  *	nextblock = 0.  Blocks of type 2 and 3 have that bit set,
787c478bd9Sstevel@tonic-gate  *	to mark them busy.
797c478bd9Sstevel@tonic-gate  *
807c478bd9Sstevel@tonic-gate  *	-Unallocated blocks are kept on an unsorted doubly linked
817c478bd9Sstevel@tonic-gate  *	free list.
827c478bd9Sstevel@tonic-gate  *
837c478bd9Sstevel@tonic-gate  *	-Memory is allocated in blocks, with sizes specified by the
847c478bd9Sstevel@tonic-gate  *	user.  A circular first-fit startegy is used, with a roving
857c478bd9Sstevel@tonic-gate  *	head of the free queue, which prevents bunching of small
867c478bd9Sstevel@tonic-gate  *	blocks at the head of the queue.
877c478bd9Sstevel@tonic-gate  *
887c478bd9Sstevel@tonic-gate  *	-Compaction is performed at free time of any blocks immediately
897c478bd9Sstevel@tonic-gate  *	following the freed block.  The freed block will be combined
907c478bd9Sstevel@tonic-gate  *	with a preceding block during the search phase of malloc.
917c478bd9Sstevel@tonic-gate  *	Since a freed block is added at the front of the free queue,
927c478bd9Sstevel@tonic-gate  *	which is moved to the end of the queue if considered and
937c478bd9Sstevel@tonic-gate  *	rejected during the search, fragmentation only occurs if
947c478bd9Sstevel@tonic-gate  *	a block with a contiguious preceding block that is free is
957c478bd9Sstevel@tonic-gate  *	freed and reallocated on the next call to malloc.  The
967c478bd9Sstevel@tonic-gate  *	time savings of this strategy is judged to be worth the
977c478bd9Sstevel@tonic-gate  *	occasional waste of memory.
987c478bd9Sstevel@tonic-gate  *
997c478bd9Sstevel@tonic-gate  *	-Small blocks (of size < MAXSIZE)  are not allocated directly.
1007c478bd9Sstevel@tonic-gate  *	A large "holding" block is allocated via a recursive call to
1017c478bd9Sstevel@tonic-gate  *	malloc.  This block contains a header and ?????? small blocks.
1027c478bd9Sstevel@tonic-gate  *	Holding blocks for a given size of small block (rounded to the
1037c478bd9Sstevel@tonic-gate  *	nearest ALIGNSZ bytes) are kept on a queue with the property that any
1047c478bd9Sstevel@tonic-gate  *	holding block with an unused small block is in front of any without.
1057c478bd9Sstevel@tonic-gate  *	A list of free blocks is kept within the holding block.
1067c478bd9Sstevel@tonic-gate  */
1077c478bd9Sstevel@tonic-gate 
1087c478bd9Sstevel@tonic-gate /*
1097c478bd9Sstevel@tonic-gate  *	description of arena, free queue, holding blocks etc.
1107c478bd9Sstevel@tonic-gate  *
1117c478bd9Sstevel@tonic-gate  * New compiler and linker does not guarentee order of initialized data.
1127c478bd9Sstevel@tonic-gate  * Define freeptr as arena[2-3] to guarentee it follows arena in memory.
1137c478bd9Sstevel@tonic-gate  * Later code depends on this order.
1147c478bd9Sstevel@tonic-gate  */
1157c478bd9Sstevel@tonic-gate 
1167c478bd9Sstevel@tonic-gate static struct header arena[4] = {
1177c478bd9Sstevel@tonic-gate 	    {0, 0, 0},
1187c478bd9Sstevel@tonic-gate 	    {0, 0, 0},
1197c478bd9Sstevel@tonic-gate 	    {0, 0, 0},
1207c478bd9Sstevel@tonic-gate 	    {0, 0, 0}
1217c478bd9Sstevel@tonic-gate 	};
1227c478bd9Sstevel@tonic-gate 				/*
1237c478bd9Sstevel@tonic-gate 				 * the second word is a minimal block to
1247c478bd9Sstevel@tonic-gate 				 * start the arena. The first is a busy
1257c478bd9Sstevel@tonic-gate 				 * block to be pointed to by the last block.
1267c478bd9Sstevel@tonic-gate 				 */
1277c478bd9Sstevel@tonic-gate 
1287c478bd9Sstevel@tonic-gate #define	freeptr (arena + 2)
1297c478bd9Sstevel@tonic-gate 				/* first and last entry in free list */
1307c478bd9Sstevel@tonic-gate static struct header *arenaend;	/* ptr to block marking high end of arena */
1317c478bd9Sstevel@tonic-gate static struct header *lastblk;	/* the highest block in the arena */
1327c478bd9Sstevel@tonic-gate static struct holdblk **holdhead;   /* pointer to array of head pointers */
1337c478bd9Sstevel@tonic-gate 				    /* to holding block chains */
1347c478bd9Sstevel@tonic-gate /*
1357c478bd9Sstevel@tonic-gate  * In order to save time calculating indices, the array is 1 too
1367c478bd9Sstevel@tonic-gate  * large, and the first element is unused
1377c478bd9Sstevel@tonic-gate  *
1387c478bd9Sstevel@tonic-gate  * Variables controlling algorithm, esp. how holding blocs are used
1397c478bd9Sstevel@tonic-gate  */
1407c478bd9Sstevel@tonic-gate static int numlblks = NUMLBLKS;
1417c478bd9Sstevel@tonic-gate static int minhead = MINHEAD;
1427c478bd9Sstevel@tonic-gate static int change = 0;	/* != 0, once param changes are no longer allowed */
1437c478bd9Sstevel@tonic-gate static int fastct = FASTCT;
1447c478bd9Sstevel@tonic-gate static unsigned int maxfast = MAXFAST;
1457c478bd9Sstevel@tonic-gate /* number of small block sizes to map to one size */
1467c478bd9Sstevel@tonic-gate 
1477c478bd9Sstevel@tonic-gate static int grain = ALIGNSZ;
1487c478bd9Sstevel@tonic-gate 
1497c478bd9Sstevel@tonic-gate #ifdef debug
1507c478bd9Sstevel@tonic-gate static int case1count = 0;
1517c478bd9Sstevel@tonic-gate 
1527c478bd9Sstevel@tonic-gate static void
1537c478bd9Sstevel@tonic-gate checkq(void)
1547c478bd9Sstevel@tonic-gate {
1557c478bd9Sstevel@tonic-gate 	register struct header *p;
1567c478bd9Sstevel@tonic-gate 
1577c478bd9Sstevel@tonic-gate 	p = &freeptr[0];
1587c478bd9Sstevel@tonic-gate 
1597c478bd9Sstevel@tonic-gate 	/* check forward */
1607c478bd9Sstevel@tonic-gate 	/*CSTYLED*/
1617c478bd9Sstevel@tonic-gate 	while (p != &freeptr[1]) {
1627c478bd9Sstevel@tonic-gate 		p = p->nextfree;
1637c478bd9Sstevel@tonic-gate 		assert(p->prevfree->nextfree == p);
1647c478bd9Sstevel@tonic-gate 	}
1657c478bd9Sstevel@tonic-gate 
1667c478bd9Sstevel@tonic-gate 	/* check backward */
1677c478bd9Sstevel@tonic-gate 	/*CSTYLED*/
1687c478bd9Sstevel@tonic-gate 	while (p != &freeptr[0]) {
1697c478bd9Sstevel@tonic-gate 		p = p->prevfree;
1707c478bd9Sstevel@tonic-gate 		assert(p->nextfree->prevfree == p);
1717c478bd9Sstevel@tonic-gate 	}
1727c478bd9Sstevel@tonic-gate }
1737c478bd9Sstevel@tonic-gate #endif
1747c478bd9Sstevel@tonic-gate 
1757c478bd9Sstevel@tonic-gate 
1767c478bd9Sstevel@tonic-gate /*
1777c478bd9Sstevel@tonic-gate  * malloc(nbytes) - give a user nbytes to use
1787c478bd9Sstevel@tonic-gate  */
1797c478bd9Sstevel@tonic-gate 
1807c478bd9Sstevel@tonic-gate void *
1817c478bd9Sstevel@tonic-gate malloc(size_t nbytes)
1827c478bd9Sstevel@tonic-gate {
1837c478bd9Sstevel@tonic-gate 	void *ret;
1847c478bd9Sstevel@tonic-gate 
1857c478bd9Sstevel@tonic-gate 	(void) mutex_lock(&mlock);
1867c478bd9Sstevel@tonic-gate 	ret = malloc_unlocked(nbytes, 0);
1877c478bd9Sstevel@tonic-gate 	(void) mutex_unlock(&mlock);
1887c478bd9Sstevel@tonic-gate 	return (ret);
1897c478bd9Sstevel@tonic-gate }
1907c478bd9Sstevel@tonic-gate 
1917c478bd9Sstevel@tonic-gate /*
1927c478bd9Sstevel@tonic-gate  * Use malloc_unlocked() to get the address to start with; Given this
1937c478bd9Sstevel@tonic-gate  * address, find out the closest address that aligns with the request
1947c478bd9Sstevel@tonic-gate  * and return that address after doing some house keeping (refer to the
1957c478bd9Sstevel@tonic-gate  * ascii art below).
1967c478bd9Sstevel@tonic-gate  */
1977c478bd9Sstevel@tonic-gate void *
1984088bb40Sraf memalign(size_t alignment, size_t size)
1997c478bd9Sstevel@tonic-gate {
2007c478bd9Sstevel@tonic-gate 	void *alloc_buf;
2017c478bd9Sstevel@tonic-gate 	struct header *hd;
2027c478bd9Sstevel@tonic-gate 	size_t alloc_size;
2037c478bd9Sstevel@tonic-gate 	uintptr_t fr;
2047c478bd9Sstevel@tonic-gate 	static int realloc;
2057c478bd9Sstevel@tonic-gate 
2067c478bd9Sstevel@tonic-gate 	if (size == 0 || alignment == 0 ||
2077257d1b4Sraf 	    (alignment & (alignment - 1)) != 0) {
2087c478bd9Sstevel@tonic-gate 		return (NULL);
2097c478bd9Sstevel@tonic-gate 	}
2107c478bd9Sstevel@tonic-gate 	if (alignment <= ALIGNSZ)
2117c478bd9Sstevel@tonic-gate 		return (malloc(size));
2127c478bd9Sstevel@tonic-gate 
2137c478bd9Sstevel@tonic-gate 	alloc_size = size + alignment;
2147c478bd9Sstevel@tonic-gate 	if (alloc_size < size) { /* overflow */
2157c478bd9Sstevel@tonic-gate 		return (NULL);
2167c478bd9Sstevel@tonic-gate 	}
2177c478bd9Sstevel@tonic-gate 
2187c478bd9Sstevel@tonic-gate 	(void) mutex_lock(&mlock);
2197c478bd9Sstevel@tonic-gate 	alloc_buf = malloc_unlocked(alloc_size, 1);
2207c478bd9Sstevel@tonic-gate 	(void) mutex_unlock(&mlock);
2217c478bd9Sstevel@tonic-gate 
2227c478bd9Sstevel@tonic-gate 	if (alloc_buf == NULL)
2237c478bd9Sstevel@tonic-gate 		return (NULL);
2247c478bd9Sstevel@tonic-gate 	fr = (uintptr_t)alloc_buf;
2257c478bd9Sstevel@tonic-gate 
2267c478bd9Sstevel@tonic-gate 	fr = (fr + alignment - 1) / alignment * alignment;
2277c478bd9Sstevel@tonic-gate 
2287c478bd9Sstevel@tonic-gate 	if (fr == (uintptr_t)alloc_buf)
2297c478bd9Sstevel@tonic-gate 		return (alloc_buf);
2307c478bd9Sstevel@tonic-gate 
2317c478bd9Sstevel@tonic-gate 	if ((fr - (uintptr_t)alloc_buf) <= HEADSZ) {
2327c478bd9Sstevel@tonic-gate 		/*
2337c478bd9Sstevel@tonic-gate 		 * we hit an edge case, where the space ahead of aligned
2347c478bd9Sstevel@tonic-gate 		 * address is not sufficient to hold 'header' and hence we
2357c478bd9Sstevel@tonic-gate 		 * can't free it. So double the allocation request.
2367c478bd9Sstevel@tonic-gate 		 */
2377c478bd9Sstevel@tonic-gate 		realloc++;
2387c478bd9Sstevel@tonic-gate 		free(alloc_buf);
2397c478bd9Sstevel@tonic-gate 		alloc_size = size + alignment*2;
2407c478bd9Sstevel@tonic-gate 		if (alloc_size < size) {
2417c478bd9Sstevel@tonic-gate 			return (NULL);
2427c478bd9Sstevel@tonic-gate 		}
2437c478bd9Sstevel@tonic-gate 
2447c478bd9Sstevel@tonic-gate 		(void) mutex_lock(&mlock);
2457c478bd9Sstevel@tonic-gate 		alloc_buf = malloc_unlocked(alloc_size, 1);
2467c478bd9Sstevel@tonic-gate 		(void) mutex_unlock(&mlock);
2477c478bd9Sstevel@tonic-gate 
2487c478bd9Sstevel@tonic-gate 		if (alloc_buf == NULL)
2497c478bd9Sstevel@tonic-gate 			return (NULL);
2507c478bd9Sstevel@tonic-gate 		fr = (uintptr_t)alloc_buf;
2517c478bd9Sstevel@tonic-gate 
2527c478bd9Sstevel@tonic-gate 		fr = (fr + alignment - 1) / alignment * alignment;
2537c478bd9Sstevel@tonic-gate 		if (fr == (uintptr_t)alloc_buf)
2547c478bd9Sstevel@tonic-gate 			return (alloc_buf);
2557c478bd9Sstevel@tonic-gate 		if ((fr - (uintptr_t)alloc_buf) <= HEADSZ) {
2567c478bd9Sstevel@tonic-gate 			fr = fr + alignment;
2577c478bd9Sstevel@tonic-gate 		}
2587c478bd9Sstevel@tonic-gate 	}
2597c478bd9Sstevel@tonic-gate 
2607c478bd9Sstevel@tonic-gate 	/*
2617c478bd9Sstevel@tonic-gate 	 *	+-------+		+-------+
2627c478bd9Sstevel@tonic-gate 	 *  +---| <a>   |		| <a>   |--+
2637c478bd9Sstevel@tonic-gate 	 *  |   +-------+<--alloc_buf-->+-------+  |
2647c478bd9Sstevel@tonic-gate 	 *  |   |	|		|	|  |
2657c478bd9Sstevel@tonic-gate 	 *  |   |	|		|	|  |
2667c478bd9Sstevel@tonic-gate 	 *  |   |	|		|	|  |
2677c478bd9Sstevel@tonic-gate 	 *  |   |	|	 hd-->  +-------+  |
2687c478bd9Sstevel@tonic-gate 	 *  |   |	|	    +---|  <b>  |<-+
2697c478bd9Sstevel@tonic-gate 	 *  |   |	|	    |   +-------+<--- fr
2707c478bd9Sstevel@tonic-gate 	 *  |   |	|	    |   |	|
2717c478bd9Sstevel@tonic-gate 	 *  |   |	|	    |   |	|
2727c478bd9Sstevel@tonic-gate 	 *  |   |	|	    |   |	|
2737c478bd9Sstevel@tonic-gate 	 *  |   |	|	    |   |	|
2747c478bd9Sstevel@tonic-gate 	 *  |   |	|	    |   |	|
2757c478bd9Sstevel@tonic-gate 	 *  |   |	|	    |   |	|
2767c478bd9Sstevel@tonic-gate 	 *  |   +-------+	    |   +-------+
2777c478bd9Sstevel@tonic-gate 	 *  +-->|  next |	    +-->|  next |
2787c478bd9Sstevel@tonic-gate 	 *	+-------+		+-------+
2797c478bd9Sstevel@tonic-gate 	 *
2807c478bd9Sstevel@tonic-gate 	 */
2817c478bd9Sstevel@tonic-gate 	hd = (struct header *)((char *)fr - minhead);
2827c478bd9Sstevel@tonic-gate 	(void) mutex_lock(&mlock);
2837c478bd9Sstevel@tonic-gate 	hd->nextblk = ((struct header *)((char *)alloc_buf - minhead))->nextblk;
2847c478bd9Sstevel@tonic-gate 	((struct header *)((char *)alloc_buf - minhead))->nextblk = SETBUSY(hd);
2857c478bd9Sstevel@tonic-gate 	(void) mutex_unlock(&mlock);
2867c478bd9Sstevel@tonic-gate 	free(alloc_buf);
2877c478bd9Sstevel@tonic-gate 	CHECKQ
2887c478bd9Sstevel@tonic-gate 	return ((void *)fr);
2897c478bd9Sstevel@tonic-gate }
2907c478bd9Sstevel@tonic-gate 
2917c478bd9Sstevel@tonic-gate void *
2924088bb40Sraf valloc(size_t size)
2937c478bd9Sstevel@tonic-gate {
2947c478bd9Sstevel@tonic-gate 	static unsigned pagesize;
2957c478bd9Sstevel@tonic-gate 	if (size == 0)
2967c478bd9Sstevel@tonic-gate 		return (NULL);
2977c478bd9Sstevel@tonic-gate 
2987c478bd9Sstevel@tonic-gate 	if (!pagesize)
2997c478bd9Sstevel@tonic-gate 		pagesize = sysconf(_SC_PAGESIZE);
3007c478bd9Sstevel@tonic-gate 
3017c478bd9Sstevel@tonic-gate 	return (memalign(pagesize, size));
3027c478bd9Sstevel@tonic-gate }
3037c478bd9Sstevel@tonic-gate 
3047c478bd9Sstevel@tonic-gate /*
3057c478bd9Sstevel@tonic-gate  * malloc_unlocked(nbytes, nosmall) - Do the real work for malloc
3067c478bd9Sstevel@tonic-gate  */
3077c478bd9Sstevel@tonic-gate 
3087c478bd9Sstevel@tonic-gate static void *
3097c478bd9Sstevel@tonic-gate malloc_unlocked(size_t nbytes, int nosmall)
3107c478bd9Sstevel@tonic-gate {
3117c478bd9Sstevel@tonic-gate 	struct header *blk;
3127c478bd9Sstevel@tonic-gate 	size_t nb;	/* size of entire block we need */
3137c478bd9Sstevel@tonic-gate 
3147c478bd9Sstevel@tonic-gate 	/* on first call, initialize */
3157c478bd9Sstevel@tonic-gate 	if (freeptr[0].nextfree == GROUND) {
3167c478bd9Sstevel@tonic-gate 		/* initialize arena */
3177c478bd9Sstevel@tonic-gate 		arena[1].nextblk = (struct header *)BUSY;
3187c478bd9Sstevel@tonic-gate 		arena[0].nextblk = (struct header *)BUSY;
3197c478bd9Sstevel@tonic-gate 		lastblk = arenaend = &(arena[1]);
3207c478bd9Sstevel@tonic-gate 		/* initialize free queue */
3217c478bd9Sstevel@tonic-gate 		freeptr[0].nextfree = &(freeptr[1]);
3227c478bd9Sstevel@tonic-gate 		freeptr[1].nextblk = &(arena[0]);
3237c478bd9Sstevel@tonic-gate 		freeptr[1].prevfree = &(freeptr[0]);
3247c478bd9Sstevel@tonic-gate 		/* mark that small blocks not init yet */
3257c478bd9Sstevel@tonic-gate 	}
3267c478bd9Sstevel@tonic-gate 	if (nbytes == 0)
3277c478bd9Sstevel@tonic-gate 		return (NULL);
3287c478bd9Sstevel@tonic-gate 
3297c478bd9Sstevel@tonic-gate 	if (nbytes <= maxfast && !nosmall) {
3307c478bd9Sstevel@tonic-gate 		/*
3317c478bd9Sstevel@tonic-gate 		 * We can allocate out of a holding block
3327c478bd9Sstevel@tonic-gate 		 */
3337c478bd9Sstevel@tonic-gate 		struct holdblk *holdblk; /* head of right sized queue */
3347c478bd9Sstevel@tonic-gate 		struct lblk *lblk;	 /* pointer to a little block */
3357c478bd9Sstevel@tonic-gate 		struct holdblk *newhold;
3367c478bd9Sstevel@tonic-gate 
3377c478bd9Sstevel@tonic-gate 		if (!change) {
3387c478bd9Sstevel@tonic-gate 			int i;
3397c478bd9Sstevel@tonic-gate 			/*
3407c478bd9Sstevel@tonic-gate 			 * This allocates space for hold block
3417c478bd9Sstevel@tonic-gate 			 * pointers by calling malloc recursively.
3427c478bd9Sstevel@tonic-gate 			 * Maxfast is temporarily set to 0, to
3437c478bd9Sstevel@tonic-gate 			 * avoid infinite recursion.  allocate
3447c478bd9Sstevel@tonic-gate 			 * space for an extra ptr so that an index
3457c478bd9Sstevel@tonic-gate 			 * is just ->blksz/grain, with the first
3467c478bd9Sstevel@tonic-gate 			 * ptr unused.
3477c478bd9Sstevel@tonic-gate 			 */
3487c478bd9Sstevel@tonic-gate 			change = 1;	/* change to algorithm params */
3497c478bd9Sstevel@tonic-gate 					/* no longer allowed */
3507c478bd9Sstevel@tonic-gate 			/*
3517c478bd9Sstevel@tonic-gate 			 * temporarily alter maxfast, to avoid
3527c478bd9Sstevel@tonic-gate 			 * infinite recursion
3537c478bd9Sstevel@tonic-gate 			 */
3547c478bd9Sstevel@tonic-gate 			maxfast = 0;
3557c478bd9Sstevel@tonic-gate 			holdhead = (struct holdblk **)
3567c478bd9Sstevel@tonic-gate 			    malloc_unlocked(sizeof (struct holdblk *) *
3577c478bd9Sstevel@tonic-gate 			    (fastct + 1), 0);
3587c478bd9Sstevel@tonic-gate 			if (holdhead == NULL)
3597c478bd9Sstevel@tonic-gate 				return (malloc_unlocked(nbytes, 0));
3607c478bd9Sstevel@tonic-gate 			for (i = 1; i <= fastct; i++) {
3617c478bd9Sstevel@tonic-gate 				holdhead[i] = HGROUND;
3627c478bd9Sstevel@tonic-gate 			}
3637c478bd9Sstevel@tonic-gate 			maxfast = fastct * grain;
3647c478bd9Sstevel@tonic-gate 		}
3657c478bd9Sstevel@tonic-gate 		/*
3667c478bd9Sstevel@tonic-gate 		 * Note that this uses the absolute min header size (MINHEAD)
3677c478bd9Sstevel@tonic-gate 		 * unlike the large block case which uses minhead
3687c478bd9Sstevel@tonic-gate 		 *
3697c478bd9Sstevel@tonic-gate 		 * round up to nearest multiple of grain
3707c478bd9Sstevel@tonic-gate 		 * code assumes grain is a multiple of MINHEAD
3717c478bd9Sstevel@tonic-gate 		 */
3727c478bd9Sstevel@tonic-gate 		/* round up to grain */
3737c478bd9Sstevel@tonic-gate 		nb = (nbytes + grain - 1) / grain * grain;
3747c478bd9Sstevel@tonic-gate 		holdblk = holdhead[nb / grain];
3757c478bd9Sstevel@tonic-gate 		nb = nb + MINHEAD;
3767c478bd9Sstevel@tonic-gate 		/*
3777c478bd9Sstevel@tonic-gate 		 * look for space in the holding block.  Blocks with
3787c478bd9Sstevel@tonic-gate 		 * space will be in front of those without
3797c478bd9Sstevel@tonic-gate 		 */
3807c478bd9Sstevel@tonic-gate 		if ((holdblk != HGROUND) && (holdblk->lfreeq != LGROUND))  {
3817c478bd9Sstevel@tonic-gate 			/* there is space */
3827c478bd9Sstevel@tonic-gate 			lblk = holdblk->lfreeq;
3837c478bd9Sstevel@tonic-gate 
3847c478bd9Sstevel@tonic-gate 			/*
3857c478bd9Sstevel@tonic-gate 			 * Now make lfreeq point to a free block.
3867c478bd9Sstevel@tonic-gate 			 * If lblk has been previously allocated and
3877c478bd9Sstevel@tonic-gate 			 * freed, it has a valid pointer to use.
3887c478bd9Sstevel@tonic-gate 			 * Otherwise, lblk is at the beginning of
3897c478bd9Sstevel@tonic-gate 			 * the unallocated blocks at the end of
3907c478bd9Sstevel@tonic-gate 			 * the holding block, so, if there is room, take
3917c478bd9Sstevel@tonic-gate 			 * the next space.  If not, mark holdblk full,
3927c478bd9Sstevel@tonic-gate 			 * and move holdblk to the end of the queue
3937c478bd9Sstevel@tonic-gate 			 */
3947c478bd9Sstevel@tonic-gate 			if (lblk < holdblk->unused) {
3957c478bd9Sstevel@tonic-gate 				/* move to next holdblk, if this one full */
3967c478bd9Sstevel@tonic-gate 				if ((holdblk->lfreeq =
3977c478bd9Sstevel@tonic-gate 				    CLRSMAL(lblk->header.nextfree)) ==
3987c478bd9Sstevel@tonic-gate 				    LGROUND) {
3997c478bd9Sstevel@tonic-gate 					holdhead[(nb-MINHEAD) / grain] =
4007c478bd9Sstevel@tonic-gate 					    holdblk->nexthblk;
4017c478bd9Sstevel@tonic-gate 				}
4027c478bd9Sstevel@tonic-gate 			} else if (((char *)holdblk->unused + nb) <
4037c478bd9Sstevel@tonic-gate 			    ((char *)holdblk + HOLDSZ(nb))) {
4047c478bd9Sstevel@tonic-gate 				holdblk->unused = (struct lblk *)
4057c478bd9Sstevel@tonic-gate 				    ((char *)holdblk->unused+nb);
4067c478bd9Sstevel@tonic-gate 				holdblk->lfreeq = holdblk->unused;
4077c478bd9Sstevel@tonic-gate 			} else {
4087c478bd9Sstevel@tonic-gate 				holdblk->unused = (struct lblk *)
4097c478bd9Sstevel@tonic-gate 				    ((char *)holdblk->unused+nb);
4107c478bd9Sstevel@tonic-gate 				holdblk->lfreeq = LGROUND;
4117c478bd9Sstevel@tonic-gate 				holdhead[(nb-MINHEAD)/grain] =
4127c478bd9Sstevel@tonic-gate 				    holdblk->nexthblk;
4137c478bd9Sstevel@tonic-gate 			}
4147c478bd9Sstevel@tonic-gate 			/* mark as busy and small */
4157c478bd9Sstevel@tonic-gate 			lblk->header.holder = (struct holdblk *)SETALL(holdblk);
4167c478bd9Sstevel@tonic-gate 		} else {
4177c478bd9Sstevel@tonic-gate 			/* we need a new holding block */
4187c478bd9Sstevel@tonic-gate 			newhold = (struct holdblk *)
4197c478bd9Sstevel@tonic-gate 			    malloc_unlocked(HOLDSZ(nb), 0);
4207c478bd9Sstevel@tonic-gate 			if ((char *)newhold == NULL) {
4217c478bd9Sstevel@tonic-gate 				return (NULL);
4227c478bd9Sstevel@tonic-gate 			}
4237c478bd9Sstevel@tonic-gate 			/* add to head of free queue */
4247c478bd9Sstevel@tonic-gate 			if (holdblk != HGROUND) {
4257c478bd9Sstevel@tonic-gate 				newhold->nexthblk = holdblk;
4267c478bd9Sstevel@tonic-gate 				newhold->prevhblk = holdblk->prevhblk;
4277c478bd9Sstevel@tonic-gate 				holdblk->prevhblk = newhold;
4287c478bd9Sstevel@tonic-gate 				newhold->prevhblk->nexthblk = newhold;
4297c478bd9Sstevel@tonic-gate 			} else {
4307c478bd9Sstevel@tonic-gate 				newhold->nexthblk = newhold->prevhblk = newhold;
4317c478bd9Sstevel@tonic-gate 			}
4327c478bd9Sstevel@tonic-gate 			holdhead[(nb-MINHEAD)/grain] = newhold;
4337c478bd9Sstevel@tonic-gate 			/* set up newhold */
4347c478bd9Sstevel@tonic-gate 			lblk = (struct lblk *)(newhold->space);
4357c478bd9Sstevel@tonic-gate 			newhold->lfreeq = newhold->unused =
4367c478bd9Sstevel@tonic-gate 			    (struct lblk *)((char *)newhold->space+nb);
4377c478bd9Sstevel@tonic-gate 			lblk->header.holder = (struct holdblk *)SETALL(newhold);
4387c478bd9Sstevel@tonic-gate 			newhold->blksz = nb-MINHEAD;
4397c478bd9Sstevel@tonic-gate 		}
4407c478bd9Sstevel@tonic-gate #ifdef debug
4417c478bd9Sstevel@tonic-gate 		assert(((struct holdblk *)CLRALL(lblk->header.holder))->blksz >=
4427c478bd9Sstevel@tonic-gate 		    nbytes);
4437c478bd9Sstevel@tonic-gate #endif /* debug */
4447c478bd9Sstevel@tonic-gate 		return ((char *)lblk + MINHEAD);
4457c478bd9Sstevel@tonic-gate 	} else {
4467c478bd9Sstevel@tonic-gate 		/*
4477c478bd9Sstevel@tonic-gate 		 * We need an ordinary block
4487c478bd9Sstevel@tonic-gate 		 */
4497c478bd9Sstevel@tonic-gate 		struct header *newblk;	/* used for creating a block */
4507c478bd9Sstevel@tonic-gate 
4517c478bd9Sstevel@tonic-gate 		/* get number of bytes we need */
4527c478bd9Sstevel@tonic-gate 		nb = nbytes + minhead;
4537c478bd9Sstevel@tonic-gate 		nb = (nb + ALIGNSZ - 1) / ALIGNSZ * ALIGNSZ;	/* align */
4547c478bd9Sstevel@tonic-gate 		nb = (nb > MINBLKSZ) ? nb : MINBLKSZ;
4557c478bd9Sstevel@tonic-gate 		/*
4567c478bd9Sstevel@tonic-gate 		 * see if there is a big enough block
4577c478bd9Sstevel@tonic-gate 		 * If none exists, you will get to freeptr[1].
4587c478bd9Sstevel@tonic-gate 		 * freeptr[1].next = &arena[0], so when you do the test,
4597c478bd9Sstevel@tonic-gate 		 * the result is a large positive number, since arena[0]
4607c478bd9Sstevel@tonic-gate 		 * comes before all blocks.  Arena[0] is marked busy so
4617c478bd9Sstevel@tonic-gate 		 * that it will not be compacted.  This kludge is for the
4627c478bd9Sstevel@tonic-gate 		 * sake of the almighty efficiency.
4637c478bd9Sstevel@tonic-gate 		 */
4647c478bd9Sstevel@tonic-gate 		/* check that a very large request won't cause an inf. loop */
4657c478bd9Sstevel@tonic-gate 
4667c478bd9Sstevel@tonic-gate 		if ((freeptr[1].nextblk-&(freeptr[1])) < nb) {
4677c478bd9Sstevel@tonic-gate 			return (NULL);
4687c478bd9Sstevel@tonic-gate 		} else {
4697c478bd9Sstevel@tonic-gate 			struct header *next;		/* following block */
4707c478bd9Sstevel@tonic-gate 			struct header *nextnext;	/* block after next */
4717c478bd9Sstevel@tonic-gate 
4727c478bd9Sstevel@tonic-gate 			blk = freeptr;
4737c478bd9Sstevel@tonic-gate 			do {
4747c478bd9Sstevel@tonic-gate 				blk = blk->nextfree;
4757c478bd9Sstevel@tonic-gate 				/* see if we can compact */
4767c478bd9Sstevel@tonic-gate 				next = blk->nextblk;
4777c478bd9Sstevel@tonic-gate 				if (!TESTBUSY(nextnext = next->nextblk)) {
4787c478bd9Sstevel@tonic-gate 					do {
4797c478bd9Sstevel@tonic-gate 						DELFREEQ(next);
4807c478bd9Sstevel@tonic-gate 						next = nextnext;
4817c478bd9Sstevel@tonic-gate 						nextnext = next->nextblk;
4827c478bd9Sstevel@tonic-gate 					} while (!TESTBUSY(nextnext));
4837c478bd9Sstevel@tonic-gate 					/*
4847c478bd9Sstevel@tonic-gate 					 * next will be at most == to lastblk,
4857c478bd9Sstevel@tonic-gate 					 * but I think the >= test is faster
4867c478bd9Sstevel@tonic-gate 					 */
4877c478bd9Sstevel@tonic-gate 					if (next >= arenaend)
4887c478bd9Sstevel@tonic-gate 						lastblk = blk;
4897c478bd9Sstevel@tonic-gate 					blk->nextblk = next;
4907c478bd9Sstevel@tonic-gate 				}
4917c478bd9Sstevel@tonic-gate 			} while (((char *)(next) - (char *)blk) < nb);
4927c478bd9Sstevel@tonic-gate 		}
4937c478bd9Sstevel@tonic-gate 		/*
4947c478bd9Sstevel@tonic-gate 		 * if we didn't find a block, get more memory
4957c478bd9Sstevel@tonic-gate 		 */
4967c478bd9Sstevel@tonic-gate 		if (blk == &(freeptr[1])) {
4977c478bd9Sstevel@tonic-gate 			/*
4987c478bd9Sstevel@tonic-gate 			 * careful coding could likely replace
4997c478bd9Sstevel@tonic-gate 			 * newend with arenaend
5007c478bd9Sstevel@tonic-gate 			 */
5017c478bd9Sstevel@tonic-gate 			struct header *newend;	/* new end of arena */
5027c478bd9Sstevel@tonic-gate 			ssize_t nget;	/* number of words to get */
5037c478bd9Sstevel@tonic-gate 
5047c478bd9Sstevel@tonic-gate 			/*
5057c478bd9Sstevel@tonic-gate 			 * Three cases - 1. There is space between arenaend
5067c478bd9Sstevel@tonic-gate 			 *		    and the break value that will become
5077c478bd9Sstevel@tonic-gate 			 *		    a permanently allocated block.
5087c478bd9Sstevel@tonic-gate 			 *		 2. Case 1 is not true, and the last
5097c478bd9Sstevel@tonic-gate 			 *		    block is allocated.
5107c478bd9Sstevel@tonic-gate 			 *		 3. Case 1 is not true, and the last
5117c478bd9Sstevel@tonic-gate 			 *		    block is free
5127c478bd9Sstevel@tonic-gate 			 */
5137c478bd9Sstevel@tonic-gate 			if ((newblk = (struct header *)sbrk(0)) !=
5147c478bd9Sstevel@tonic-gate 			    (struct header *)((char *)arenaend + HEADSZ)) {
5157c478bd9Sstevel@tonic-gate 				/* case 1 */
5167c478bd9Sstevel@tonic-gate #ifdef debug
5177c478bd9Sstevel@tonic-gate 				if (case1count++ > 0)
5187c478bd9Sstevel@tonic-gate 				    (void) write(2, "Case 1 hit more that once."
5197c478bd9Sstevel@tonic-gate 					" brk or sbrk?\n", 41);
5207c478bd9Sstevel@tonic-gate #endif
5217c478bd9Sstevel@tonic-gate 				/* get size to fetch */
5227c478bd9Sstevel@tonic-gate 				nget = nb + HEADSZ;
5237c478bd9Sstevel@tonic-gate 				/* round up to a block */
5247c478bd9Sstevel@tonic-gate 				nget = (nget + BLOCKSZ - 1)/BLOCKSZ * BLOCKSZ;
5257c478bd9Sstevel@tonic-gate 				assert((uintptr_t)newblk % ALIGNSZ == 0);
5267c478bd9Sstevel@tonic-gate 				/* get memory */
5277c478bd9Sstevel@tonic-gate 				if (morecore(nget) == (void *)-1)
5287c478bd9Sstevel@tonic-gate 					return (NULL);
5297c478bd9Sstevel@tonic-gate 				/* add to arena */
5307c478bd9Sstevel@tonic-gate 				newend = (struct header *)((char *)newblk + nget
5317c478bd9Sstevel@tonic-gate 				    - HEADSZ);
5327c478bd9Sstevel@tonic-gate 				assert((uintptr_t)newblk % ALIGNSZ == 0);
5337c478bd9Sstevel@tonic-gate 				newend->nextblk = SETBUSY(&(arena[1]));
5347c478bd9Sstevel@tonic-gate /* ???  newblk ?? */
5357c478bd9Sstevel@tonic-gate 				newblk->nextblk = newend;
5367c478bd9Sstevel@tonic-gate 
5377c478bd9Sstevel@tonic-gate 				/*
5387c478bd9Sstevel@tonic-gate 				 * space becomes a permanently allocated block.
5397c478bd9Sstevel@tonic-gate 				 * This is likely not mt-safe as lock is not
5407c478bd9Sstevel@tonic-gate 				 * shared with brk or sbrk
5417c478bd9Sstevel@tonic-gate 				 */
5427c478bd9Sstevel@tonic-gate 				arenaend->nextblk = SETBUSY(newblk);
5437c478bd9Sstevel@tonic-gate 				/* adjust other pointers */
5447c478bd9Sstevel@tonic-gate 				arenaend = newend;
5457c478bd9Sstevel@tonic-gate 				lastblk = newblk;
5467c478bd9Sstevel@tonic-gate 				blk = newblk;
5477c478bd9Sstevel@tonic-gate 			} else if (TESTBUSY(lastblk->nextblk)) {
5487c478bd9Sstevel@tonic-gate 				/* case 2 */
5497c478bd9Sstevel@tonic-gate 				nget = (nb + BLOCKSZ - 1) / BLOCKSZ * BLOCKSZ;
5507c478bd9Sstevel@tonic-gate 				if (morecore(nget) == (void *)-1)
5517c478bd9Sstevel@tonic-gate 					return (NULL);
5527c478bd9Sstevel@tonic-gate 				/* block must be word aligned */
5537c478bd9Sstevel@tonic-gate 				assert(((uintptr_t)newblk%ALIGNSZ) == 0);
5547c478bd9Sstevel@tonic-gate 				/*
5557c478bd9Sstevel@tonic-gate 				 * stub at old arenaend becomes first word
5567c478bd9Sstevel@tonic-gate 				 * in blk
5577c478bd9Sstevel@tonic-gate 				 */
5587c478bd9Sstevel@tonic-gate /* ???  	newblk = arenaend; */
5597c478bd9Sstevel@tonic-gate 
5607c478bd9Sstevel@tonic-gate 				newend =
5617c478bd9Sstevel@tonic-gate 				    (struct header *)((char *)arenaend+nget);
5627c478bd9Sstevel@tonic-gate 				newend->nextblk = SETBUSY(&(arena[1]));
5637c478bd9Sstevel@tonic-gate 				arenaend->nextblk = newend;
5647c478bd9Sstevel@tonic-gate 				lastblk = blk = arenaend;
5657c478bd9Sstevel@tonic-gate 				arenaend = newend;
5667c478bd9Sstevel@tonic-gate 			} else {
5677c478bd9Sstevel@tonic-gate 				/* case 3 */
5687c478bd9Sstevel@tonic-gate 				/*
5697c478bd9Sstevel@tonic-gate 				 * last block in arena is at end of memory and
5707c478bd9Sstevel@tonic-gate 				 * is free
5717c478bd9Sstevel@tonic-gate 				 */
5727c478bd9Sstevel@tonic-gate 				/* 1.7 had this backward without cast */
5737c478bd9Sstevel@tonic-gate 				nget = nb -
5747c478bd9Sstevel@tonic-gate 				    ((char *)arenaend - (char *)lastblk);
5757c478bd9Sstevel@tonic-gate 				nget = (nget + (BLOCKSZ - 1)) /
5767c478bd9Sstevel@tonic-gate 				    BLOCKSZ * BLOCKSZ;
5777c478bd9Sstevel@tonic-gate 				assert(((uintptr_t)newblk % ALIGNSZ) == 0);
5787c478bd9Sstevel@tonic-gate 				if (morecore(nget) == (void *)-1)
5797c478bd9Sstevel@tonic-gate 					return (NULL);
5807c478bd9Sstevel@tonic-gate 				/* combine with last block, put in arena */
5817c478bd9Sstevel@tonic-gate 				newend = (struct header *)
5827c478bd9Sstevel@tonic-gate 				    ((char *)arenaend + nget);
5837c478bd9Sstevel@tonic-gate 				arenaend = lastblk->nextblk = newend;
5847c478bd9Sstevel@tonic-gate 				newend->nextblk = SETBUSY(&(arena[1]));
5857c478bd9Sstevel@tonic-gate 				/* set which block to use */
5867c478bd9Sstevel@tonic-gate 				blk = lastblk;
5877c478bd9Sstevel@tonic-gate 				DELFREEQ(blk);
5887c478bd9Sstevel@tonic-gate 			}
5897c478bd9Sstevel@tonic-gate 		} else {
5907c478bd9Sstevel@tonic-gate 			struct header *nblk;	/* next block */
5917c478bd9Sstevel@tonic-gate 
5927c478bd9Sstevel@tonic-gate 			/* take block found of free queue */
5937c478bd9Sstevel@tonic-gate 			DELFREEQ(blk);
5947c478bd9Sstevel@tonic-gate 			/*
5957c478bd9Sstevel@tonic-gate 			 * make head of free queue immediately follow blk,
5967c478bd9Sstevel@tonic-gate 			 * unless blk was at the end of the queue
5977c478bd9Sstevel@tonic-gate 			 */
5987c478bd9Sstevel@tonic-gate 			nblk = blk->nextfree;
5997c478bd9Sstevel@tonic-gate 			if (nblk != &(freeptr[1])) {
6007c478bd9Sstevel@tonic-gate 				MOVEHEAD(nblk);
6017c478bd9Sstevel@tonic-gate 			}
6027c478bd9Sstevel@tonic-gate 		}
6037c478bd9Sstevel@tonic-gate 		/* blk now points to an adequate block */
6047c478bd9Sstevel@tonic-gate 		if (((char *)blk->nextblk - (char *)blk) - nb >= MINBLKSZ) {
6057c478bd9Sstevel@tonic-gate 			/* carve out the right size block */
6067c478bd9Sstevel@tonic-gate 			/* newblk will be the remainder */
6077c478bd9Sstevel@tonic-gate 			newblk = (struct header *)((char *)blk + nb);
6087c478bd9Sstevel@tonic-gate 			newblk->nextblk = blk->nextblk;
6097c478bd9Sstevel@tonic-gate 			/* mark the block busy */
6107c478bd9Sstevel@tonic-gate 			blk->nextblk = SETBUSY(newblk);
6117c478bd9Sstevel@tonic-gate 			ADDFREEQ(newblk);
6127c478bd9Sstevel@tonic-gate 			/* if blk was lastblk, make newblk lastblk */
6137c478bd9Sstevel@tonic-gate 			if (blk == lastblk)
6147c478bd9Sstevel@tonic-gate 				lastblk = newblk;
6157c478bd9Sstevel@tonic-gate 		} else {
6167c478bd9Sstevel@tonic-gate 			/* just mark the block busy */
6177c478bd9Sstevel@tonic-gate 			blk->nextblk = SETBUSY(blk->nextblk);
6187c478bd9Sstevel@tonic-gate 		}
6197c478bd9Sstevel@tonic-gate 	}
6207c478bd9Sstevel@tonic-gate 	CHECKQ
6217c478bd9Sstevel@tonic-gate 	assert((char *)CLRALL(blk->nextblk) -
6227c478bd9Sstevel@tonic-gate 	    ((char *)blk + minhead) >= nbytes);
6237c478bd9Sstevel@tonic-gate 	assert((char *)CLRALL(blk->nextblk) -
6247c478bd9Sstevel@tonic-gate 	    ((char *)blk + minhead) < nbytes + MINBLKSZ);
6257c478bd9Sstevel@tonic-gate 	return ((char *)blk + minhead);
6267c478bd9Sstevel@tonic-gate }
6277c478bd9Sstevel@tonic-gate 
6287c478bd9Sstevel@tonic-gate /*
6297c478bd9Sstevel@tonic-gate  * free(ptr) - free block that user thinks starts at ptr
6307c478bd9Sstevel@tonic-gate  *
6317c478bd9Sstevel@tonic-gate  *	input - ptr-1 contains the block header.
6327c478bd9Sstevel@tonic-gate  *		If the header points forward, we have a normal
6337c478bd9Sstevel@tonic-gate  *			block pointing to the next block
6347c478bd9Sstevel@tonic-gate  *		if the header points backward, we have a small
6357c478bd9Sstevel@tonic-gate  *			block from a holding block.
6367c478bd9Sstevel@tonic-gate  *		In both cases, the busy bit must be set
6377c478bd9Sstevel@tonic-gate  */
6387c478bd9Sstevel@tonic-gate 
6397c478bd9Sstevel@tonic-gate void
6407c478bd9Sstevel@tonic-gate free(void *ptr)
6417c478bd9Sstevel@tonic-gate {
6427c478bd9Sstevel@tonic-gate 	(void) mutex_lock(&mlock);
6437c478bd9Sstevel@tonic-gate 	free_unlocked(ptr);
6447c478bd9Sstevel@tonic-gate 	(void) mutex_unlock(&mlock);
6457c478bd9Sstevel@tonic-gate }
6467c478bd9Sstevel@tonic-gate 
6477c478bd9Sstevel@tonic-gate /*
6487c478bd9Sstevel@tonic-gate  * free_unlocked(ptr) - Do the real work for free()
6497c478bd9Sstevel@tonic-gate  */
6507c478bd9Sstevel@tonic-gate 
6517c478bd9Sstevel@tonic-gate void
6527c478bd9Sstevel@tonic-gate free_unlocked(void *ptr)
6537c478bd9Sstevel@tonic-gate {
6547c478bd9Sstevel@tonic-gate 	struct holdblk *holdblk;	/* block holding blk */
6557c478bd9Sstevel@tonic-gate 	struct holdblk *oldhead;	/* former head of the hold block */
6567c478bd9Sstevel@tonic-gate 					/* queue containing blk's holder */
6577c478bd9Sstevel@tonic-gate 
6587c478bd9Sstevel@tonic-gate 	if (ptr == NULL)
6597c478bd9Sstevel@tonic-gate 		return;
6607c478bd9Sstevel@tonic-gate 	if (TESTSMAL(((struct header *)((char *)ptr - MINHEAD))->nextblk)) {
6617c478bd9Sstevel@tonic-gate 		struct lblk	*lblk;	/* pointer to freed block */
6627c478bd9Sstevel@tonic-gate 		ssize_t		offset;	/* choice of header lists */
6637c478bd9Sstevel@tonic-gate 
6647c478bd9Sstevel@tonic-gate 		lblk = (struct lblk *)CLRBUSY((char *)ptr - MINHEAD);
6657c478bd9Sstevel@tonic-gate 		assert((struct header *)lblk < arenaend);
6667c478bd9Sstevel@tonic-gate 		assert((struct header *)lblk > arena);
6677c478bd9Sstevel@tonic-gate 		/* allow twits (e.g. awk) to free a block twice */
6687c478bd9Sstevel@tonic-gate 		holdblk = lblk->header.holder;
6697c478bd9Sstevel@tonic-gate 		if (!TESTBUSY(holdblk))
6707c478bd9Sstevel@tonic-gate 			return;
6717c478bd9Sstevel@tonic-gate 		holdblk = (struct holdblk *)CLRALL(holdblk);
6727c478bd9Sstevel@tonic-gate 		/* put lblk on its hold block's free list */
6737c478bd9Sstevel@tonic-gate 		lblk->header.nextfree = SETSMAL(holdblk->lfreeq);
6747c478bd9Sstevel@tonic-gate 		holdblk->lfreeq = lblk;
6757c478bd9Sstevel@tonic-gate 		/* move holdblk to head of queue, if its not already there */
6767c478bd9Sstevel@tonic-gate 		offset = holdblk->blksz / grain;
6777c478bd9Sstevel@tonic-gate 		oldhead = holdhead[offset];
6787c478bd9Sstevel@tonic-gate 		if (oldhead != holdblk) {
6797c478bd9Sstevel@tonic-gate 			/* first take out of current spot */
6807c478bd9Sstevel@tonic-gate 			holdhead[offset] = holdblk;
6817c478bd9Sstevel@tonic-gate 			holdblk->nexthblk->prevhblk = holdblk->prevhblk;
6827c478bd9Sstevel@tonic-gate 			holdblk->prevhblk->nexthblk = holdblk->nexthblk;
6837c478bd9Sstevel@tonic-gate 			/* now add at front */
6847c478bd9Sstevel@tonic-gate 			holdblk->nexthblk = oldhead;
6857c478bd9Sstevel@tonic-gate 			holdblk->prevhblk = oldhead->prevhblk;
6867c478bd9Sstevel@tonic-gate 			oldhead->prevhblk = holdblk;
6877c478bd9Sstevel@tonic-gate 			holdblk->prevhblk->nexthblk = holdblk;
6887c478bd9Sstevel@tonic-gate 		}
6897c478bd9Sstevel@tonic-gate 	} else {
6907c478bd9Sstevel@tonic-gate 		struct header *blk;	/* real start of block */
6917c478bd9Sstevel@tonic-gate 		struct header *next;	/* next = blk->nextblk */
6927c478bd9Sstevel@tonic-gate 		struct header *nextnext;	/* block after next */
6937c478bd9Sstevel@tonic-gate 
6947c478bd9Sstevel@tonic-gate 		blk = (struct header *)((char *)ptr - minhead);
6957c478bd9Sstevel@tonic-gate 		next = blk->nextblk;
6967c478bd9Sstevel@tonic-gate 		/* take care of twits (e.g. awk) who return blocks twice */
6977c478bd9Sstevel@tonic-gate 		if (!TESTBUSY(next))
6987c478bd9Sstevel@tonic-gate 			return;
6997c478bd9Sstevel@tonic-gate 		blk->nextblk = next = CLRBUSY(next);
7007c478bd9Sstevel@tonic-gate 		ADDFREEQ(blk);
7017c478bd9Sstevel@tonic-gate 		/* see if we can compact */
7027c478bd9Sstevel@tonic-gate 		if (!TESTBUSY(nextnext = next->nextblk)) {
7037c478bd9Sstevel@tonic-gate 			do {
7047c478bd9Sstevel@tonic-gate 				DELFREEQ(next);
7057c478bd9Sstevel@tonic-gate 				next = nextnext;
7067c478bd9Sstevel@tonic-gate 			} while (!TESTBUSY(nextnext = next->nextblk));
7077c478bd9Sstevel@tonic-gate 			if (next == arenaend) lastblk = blk;
7087c478bd9Sstevel@tonic-gate 			blk->nextblk = next;
7097c478bd9Sstevel@tonic-gate 		}
7107c478bd9Sstevel@tonic-gate 	}
7117c478bd9Sstevel@tonic-gate 	CHECKQ
7127c478bd9Sstevel@tonic-gate }
7137c478bd9Sstevel@tonic-gate 
7147c478bd9Sstevel@tonic-gate 
7157c478bd9Sstevel@tonic-gate /*
7167c478bd9Sstevel@tonic-gate  * realloc(ptr, size) - give the user a block of size "size", with
7177c478bd9Sstevel@tonic-gate  *			    the contents pointed to by ptr.  Free ptr.
7187c478bd9Sstevel@tonic-gate  */
7197c478bd9Sstevel@tonic-gate 
7207c478bd9Sstevel@tonic-gate void *
7217c478bd9Sstevel@tonic-gate realloc(void *ptr, size_t size)
7227c478bd9Sstevel@tonic-gate {
7237c478bd9Sstevel@tonic-gate 	void	*retval;
7247c478bd9Sstevel@tonic-gate 
7257c478bd9Sstevel@tonic-gate 	(void) mutex_lock(&mlock);
7267c478bd9Sstevel@tonic-gate 	retval = realloc_unlocked(ptr, size);
7277c478bd9Sstevel@tonic-gate 	(void) mutex_unlock(&mlock);
7287c478bd9Sstevel@tonic-gate 	return (retval);
7297c478bd9Sstevel@tonic-gate }
7307c478bd9Sstevel@tonic-gate 
7317c478bd9Sstevel@tonic-gate 
7327c478bd9Sstevel@tonic-gate /*
7337c478bd9Sstevel@tonic-gate  * realloc_unlocked(ptr) - Do the real work for realloc()
7347c478bd9Sstevel@tonic-gate  */
7357c478bd9Sstevel@tonic-gate 
7367c478bd9Sstevel@tonic-gate static void *
7377c478bd9Sstevel@tonic-gate realloc_unlocked(void *ptr, size_t size)
7387c478bd9Sstevel@tonic-gate {
7397c478bd9Sstevel@tonic-gate 	struct header *blk;	/* block ptr is contained in */
7407c478bd9Sstevel@tonic-gate 	size_t trusize;	/* block size as allocater sees it */
7417c478bd9Sstevel@tonic-gate 	char *newptr;			/* pointer to user's new block */
7427c478bd9Sstevel@tonic-gate 	size_t cpysize;	/* amount to copy */
7437c478bd9Sstevel@tonic-gate 	struct header *next;	/* block after blk */
7447c478bd9Sstevel@tonic-gate 
7457c478bd9Sstevel@tonic-gate 	if (ptr == NULL)
7467c478bd9Sstevel@tonic-gate 		return (malloc_unlocked(size, 0));
7477c478bd9Sstevel@tonic-gate 
7487c478bd9Sstevel@tonic-gate 	if (size == 0) {
7497c478bd9Sstevel@tonic-gate 		free_unlocked(ptr);
7507c478bd9Sstevel@tonic-gate 		return (NULL);
7517c478bd9Sstevel@tonic-gate 	}
7527c478bd9Sstevel@tonic-gate 
7537c478bd9Sstevel@tonic-gate 	if (TESTSMAL(((struct lblk *)((char *)ptr - MINHEAD))->
7547c478bd9Sstevel@tonic-gate 	    header.holder)) {
7557c478bd9Sstevel@tonic-gate 		/*
7567c478bd9Sstevel@tonic-gate 		 * we have a special small block which can't be expanded
7577c478bd9Sstevel@tonic-gate 		 *
7587c478bd9Sstevel@tonic-gate 		 * This makes the assumption that even if the user is
7597c478bd9Sstevel@tonic-gate 		 * reallocating a free block, malloc doesn't alter the contents
7607c478bd9Sstevel@tonic-gate 		 * of small blocks
7617c478bd9Sstevel@tonic-gate 		 */
7627c478bd9Sstevel@tonic-gate 		newptr = malloc_unlocked(size, 0);
7637c478bd9Sstevel@tonic-gate 		if (newptr == NULL)
7647c478bd9Sstevel@tonic-gate 			return (NULL);
7657c478bd9Sstevel@tonic-gate 		/* this isn't to save time--its to protect the twits */
7667c478bd9Sstevel@tonic-gate 		if ((char *)ptr != newptr) {
7677c478bd9Sstevel@tonic-gate 			struct lblk *lblk;
7687c478bd9Sstevel@tonic-gate 			lblk = (struct lblk *)((char *)ptr - MINHEAD);
7697c478bd9Sstevel@tonic-gate 			cpysize = ((struct holdblk *)
7707c478bd9Sstevel@tonic-gate 			    CLRALL(lblk->header.holder))->blksz;
7717c478bd9Sstevel@tonic-gate 			cpysize = (size > cpysize) ? cpysize : size;
7727c478bd9Sstevel@tonic-gate 			(void) memcpy(newptr, ptr, cpysize);
7737c478bd9Sstevel@tonic-gate 			free_unlocked(ptr);
7747c478bd9Sstevel@tonic-gate 		}
7757c478bd9Sstevel@tonic-gate 	} else {
7767c478bd9Sstevel@tonic-gate 		blk = (struct header *)((char *)ptr - minhead);
7777c478bd9Sstevel@tonic-gate 		next = blk->nextblk;
7787c478bd9Sstevel@tonic-gate 		/*
7797c478bd9Sstevel@tonic-gate 		 * deal with twits who reallocate free blocks
7807c478bd9Sstevel@tonic-gate 		 *
7817c478bd9Sstevel@tonic-gate 		 * if they haven't reset minblk via getopt, that's
7827c478bd9Sstevel@tonic-gate 		 * their problem
7837c478bd9Sstevel@tonic-gate 		 */
7847c478bd9Sstevel@tonic-gate 		if (!TESTBUSY(next)) {
7857c478bd9Sstevel@tonic-gate 			DELFREEQ(blk);
7867c478bd9Sstevel@tonic-gate 			blk->nextblk = SETBUSY(next);
7877c478bd9Sstevel@tonic-gate 		}
7887c478bd9Sstevel@tonic-gate 		next = CLRBUSY(next);
7897c478bd9Sstevel@tonic-gate 		/* make blk as big as possible */
7907c478bd9Sstevel@tonic-gate 		if (!TESTBUSY(next->nextblk)) {
7917c478bd9Sstevel@tonic-gate 			do {
7927c478bd9Sstevel@tonic-gate 				DELFREEQ(next);
7937c478bd9Sstevel@tonic-gate 				next = next->nextblk;
7947c478bd9Sstevel@tonic-gate 			} while (!TESTBUSY(next->nextblk));
7957c478bd9Sstevel@tonic-gate 			blk->nextblk = SETBUSY(next);
7967c478bd9Sstevel@tonic-gate 			if (next >= arenaend) lastblk = blk;
7977c478bd9Sstevel@tonic-gate 		}
7987c478bd9Sstevel@tonic-gate 		/* get size we really need */
7997c478bd9Sstevel@tonic-gate 		trusize = size+minhead;
8007c478bd9Sstevel@tonic-gate 		trusize = (trusize + ALIGNSZ - 1)/ALIGNSZ*ALIGNSZ;
8017c478bd9Sstevel@tonic-gate 		trusize = (trusize >= MINBLKSZ) ? trusize : MINBLKSZ;
8027c478bd9Sstevel@tonic-gate 		/* see if we have enough */
8037c478bd9Sstevel@tonic-gate 		/* this isn't really the copy size, but I need a register */
8047c478bd9Sstevel@tonic-gate 		cpysize = (char *)next - (char *)blk;
8057c478bd9Sstevel@tonic-gate 		if (cpysize >= trusize) {
8067c478bd9Sstevel@tonic-gate 			/* carve out the size we need */
8077c478bd9Sstevel@tonic-gate 			struct header *newblk;	/* remainder */
8087c478bd9Sstevel@tonic-gate 
8097c478bd9Sstevel@tonic-gate 			if (cpysize - trusize >= MINBLKSZ) {
8107c478bd9Sstevel@tonic-gate 				/*
8117c478bd9Sstevel@tonic-gate 				 * carve out the right size block
8127c478bd9Sstevel@tonic-gate 				 * newblk will be the remainder
8137c478bd9Sstevel@tonic-gate 				 */
8147c478bd9Sstevel@tonic-gate 				newblk = (struct header *)((char *)blk +
8157c478bd9Sstevel@tonic-gate 				    trusize);
8167c478bd9Sstevel@tonic-gate 				newblk->nextblk = next;
8177c478bd9Sstevel@tonic-gate 				blk->nextblk = SETBUSY(newblk);
8187c478bd9Sstevel@tonic-gate 				/* at this point, next is invalid */
8197c478bd9Sstevel@tonic-gate 				ADDFREEQ(newblk);
8207c478bd9Sstevel@tonic-gate 				/* if blk was lastblk, make newblk lastblk */
8217c478bd9Sstevel@tonic-gate 				if (blk == lastblk)
8227c478bd9Sstevel@tonic-gate 					lastblk = newblk;
8237c478bd9Sstevel@tonic-gate 			}
8247c478bd9Sstevel@tonic-gate 			newptr = ptr;
8257c478bd9Sstevel@tonic-gate 		} else {
8267c478bd9Sstevel@tonic-gate 			/* bite the bullet, and call malloc */
8277c478bd9Sstevel@tonic-gate 			cpysize = (size > cpysize) ? cpysize : size;
8287c478bd9Sstevel@tonic-gate 			newptr = malloc_unlocked(size, 0);
8297c478bd9Sstevel@tonic-gate 			if (newptr == NULL)
8307c478bd9Sstevel@tonic-gate 				return (NULL);
8317c478bd9Sstevel@tonic-gate 			(void) memcpy(newptr, ptr, cpysize);
8327c478bd9Sstevel@tonic-gate 			free_unlocked(ptr);
8337c478bd9Sstevel@tonic-gate 		}
8347c478bd9Sstevel@tonic-gate 	}
8357c478bd9Sstevel@tonic-gate 	return (newptr);
8367c478bd9Sstevel@tonic-gate }
8377c478bd9Sstevel@tonic-gate 
8387c478bd9Sstevel@tonic-gate 
8397c478bd9Sstevel@tonic-gate /*
8407c478bd9Sstevel@tonic-gate  * calloc - allocate and clear memory block
8417c478bd9Sstevel@tonic-gate  */
8427c478bd9Sstevel@tonic-gate 
8437c478bd9Sstevel@tonic-gate void *
8447c478bd9Sstevel@tonic-gate calloc(size_t num, size_t size)
8457c478bd9Sstevel@tonic-gate {
8467c478bd9Sstevel@tonic-gate 	char *mp;
847*31c6d826SRichard Lowe 	size_t total;
848*31c6d826SRichard Lowe 
849*31c6d826SRichard Lowe 	if (num == 0 || size == 0) {
850*31c6d826SRichard Lowe 		total = 0;
851*31c6d826SRichard Lowe 	} else {
852*31c6d826SRichard Lowe 		total = num * size;
853*31c6d826SRichard Lowe 
854*31c6d826SRichard Lowe 		/* check for overflow */
855*31c6d826SRichard Lowe 		if ((total / num) != size) {
856*31c6d826SRichard Lowe 			errno = ENOMEM;
857*31c6d826SRichard Lowe 			return (NULL);
858*31c6d826SRichard Lowe 		}
859*31c6d826SRichard Lowe 	}
8607c478bd9Sstevel@tonic-gate 
861*31c6d826SRichard Lowe 	mp = malloc(total);
8627c478bd9Sstevel@tonic-gate 	if (mp == NULL)
8637c478bd9Sstevel@tonic-gate 		return (NULL);
864*31c6d826SRichard Lowe 	(void) memset(mp, 0, total);
8657c478bd9Sstevel@tonic-gate 	return (mp);
8667c478bd9Sstevel@tonic-gate }
8677c478bd9Sstevel@tonic-gate 
8687c478bd9Sstevel@tonic-gate 
8697c478bd9Sstevel@tonic-gate /*
8707c478bd9Sstevel@tonic-gate  * Mallopt - set options for allocation
8717c478bd9Sstevel@tonic-gate  *
8727c478bd9Sstevel@tonic-gate  *	Mallopt provides for control over the allocation algorithm.
8737c478bd9Sstevel@tonic-gate  *	The cmds available are:
8747c478bd9Sstevel@tonic-gate  *
8757c478bd9Sstevel@tonic-gate  *	M_MXFAST Set maxfast to value.  Maxfast is the size of the
8767c478bd9Sstevel@tonic-gate  *		 largest small, quickly allocated block.  Maxfast
8777c478bd9Sstevel@tonic-gate  *		 may be set to 0 to disable fast allocation entirely.
8787c478bd9Sstevel@tonic-gate  *
8797c478bd9Sstevel@tonic-gate  *	M_NLBLKS Set numlblks to value.  Numlblks is the number of
8807c478bd9Sstevel@tonic-gate  *		 small blocks per holding block.  Value must be
8817c478bd9Sstevel@tonic-gate  *		 greater than 0.
8827c478bd9Sstevel@tonic-gate  *
8837c478bd9Sstevel@tonic-gate  *	M_GRAIN  Set grain to value.  The sizes of all blocks
8847c478bd9Sstevel@tonic-gate  *		 smaller than maxfast are considered to be rounded
8857c478bd9Sstevel@tonic-gate  *		 up to the nearest multiple of grain. The default
8867c478bd9Sstevel@tonic-gate  *		 value of grain is the smallest number of bytes
8877c478bd9Sstevel@tonic-gate  *		 which will allow alignment of any data type.    Grain
8887c478bd9Sstevel@tonic-gate  *		 will be rounded up to a multiple of its default,
8897c478bd9Sstevel@tonic-gate  *		 and maxsize will be rounded up to a multiple of
8907c478bd9Sstevel@tonic-gate  *		 grain.  Value must be greater than 0.
8917c478bd9Sstevel@tonic-gate  *
8927c478bd9Sstevel@tonic-gate  *	M_KEEP   Retain data in freed block until the next malloc,
8937c478bd9Sstevel@tonic-gate  *		 realloc, or calloc.  Value is ignored.
8947c478bd9Sstevel@tonic-gate  *		 This option is provided only for compatibility with
8957c478bd9Sstevel@tonic-gate  *		 the old version of malloc, and is not recommended.
8967c478bd9Sstevel@tonic-gate  *
8977c478bd9Sstevel@tonic-gate  *	returns - 0, upon successful completion
8987c478bd9Sstevel@tonic-gate  *		 1, if malloc has previously been called or
8997c478bd9Sstevel@tonic-gate  *		    if value or cmd have illegal values
9007c478bd9Sstevel@tonic-gate  */
9017c478bd9Sstevel@tonic-gate 
9027c478bd9Sstevel@tonic-gate int
9034088bb40Sraf mallopt(int cmd, int value)
9047c478bd9Sstevel@tonic-gate {
9057c478bd9Sstevel@tonic-gate 	/* disallow changes once a small block is allocated */
9067c478bd9Sstevel@tonic-gate 	(void) mutex_lock(&mlock);
9077c478bd9Sstevel@tonic-gate 	if (change) {
9087c478bd9Sstevel@tonic-gate 		(void) mutex_unlock(&mlock);
9097c478bd9Sstevel@tonic-gate 		return (1);
9107c478bd9Sstevel@tonic-gate 	}
9117c478bd9Sstevel@tonic-gate 	switch (cmd) {
9127c478bd9Sstevel@tonic-gate 	case M_MXFAST:
9137c478bd9Sstevel@tonic-gate 		if (value < 0) {
9147c478bd9Sstevel@tonic-gate 			(void) mutex_unlock(&mlock);
9157c478bd9Sstevel@tonic-gate 			return (1);
9167c478bd9Sstevel@tonic-gate 		}
9177c478bd9Sstevel@tonic-gate 		fastct = (value + grain - 1) / grain;
9187c478bd9Sstevel@tonic-gate 		maxfast = grain*fastct;
9197c478bd9Sstevel@tonic-gate 		break;
9207c478bd9Sstevel@tonic-gate 	case M_NLBLKS:
9217c478bd9Sstevel@tonic-gate 		if (value <= 1) {
9227c478bd9Sstevel@tonic-gate 			(void) mutex_unlock(&mlock);
9237c478bd9Sstevel@tonic-gate 			return (1);
9247c478bd9Sstevel@tonic-gate 		}
9257c478bd9Sstevel@tonic-gate 		numlblks = value;
9267c478bd9Sstevel@tonic-gate 		break;
9277c478bd9Sstevel@tonic-gate 	case M_GRAIN:
9287c478bd9Sstevel@tonic-gate 		if (value <= 0) {
9297c478bd9Sstevel@tonic-gate 			(void) mutex_unlock(&mlock);
9307c478bd9Sstevel@tonic-gate 			return (1);
9317c478bd9Sstevel@tonic-gate 		}
9327c478bd9Sstevel@tonic-gate 
9337c478bd9Sstevel@tonic-gate 		/* round grain up to a multiple of ALIGNSZ */
9347c478bd9Sstevel@tonic-gate 		grain = (value + ALIGNSZ - 1)/ALIGNSZ*ALIGNSZ;
9357c478bd9Sstevel@tonic-gate 
9367c478bd9Sstevel@tonic-gate 		/* reduce fastct appropriately */
9377c478bd9Sstevel@tonic-gate 		fastct = (maxfast + grain - 1) / grain;
9387c478bd9Sstevel@tonic-gate 		maxfast = grain * fastct;
9397c478bd9Sstevel@tonic-gate 		break;
9407c478bd9Sstevel@tonic-gate 	case M_KEEP:
9417c478bd9Sstevel@tonic-gate 		if (change && holdhead != NULL) {
9427257d1b4Sraf 			(void) mutex_unlock(&mlock);
9437c478bd9Sstevel@tonic-gate 			return (1);
9447c478bd9Sstevel@tonic-gate 		}
9457c478bd9Sstevel@tonic-gate 		minhead = HEADSZ;
9467c478bd9Sstevel@tonic-gate 		break;
9477c478bd9Sstevel@tonic-gate 	default:
9487c478bd9Sstevel@tonic-gate 		(void) mutex_unlock(&mlock);
9497c478bd9Sstevel@tonic-gate 		return (1);
9507c478bd9Sstevel@tonic-gate 	}
9517c478bd9Sstevel@tonic-gate 	(void) mutex_unlock(&mlock);
9527c478bd9Sstevel@tonic-gate 	return (0);
9537c478bd9Sstevel@tonic-gate }
9547c478bd9Sstevel@tonic-gate 
9557c478bd9Sstevel@tonic-gate /*
9567c478bd9Sstevel@tonic-gate  * mallinfo-provide information about space usage
9577c478bd9Sstevel@tonic-gate  *
9587c478bd9Sstevel@tonic-gate  *	input - max; mallinfo will return the size of the
9597c478bd9Sstevel@tonic-gate  *		largest block < max.
9607c478bd9Sstevel@tonic-gate  *
9617c478bd9Sstevel@tonic-gate  *	output - a structure containing a description of
9627c478bd9Sstevel@tonic-gate  *		 of space usage, defined in malloc.h
9637c478bd9Sstevel@tonic-gate  */
9647c478bd9Sstevel@tonic-gate 
9657c478bd9Sstevel@tonic-gate struct mallinfo
9664088bb40Sraf mallinfo(void)
9677c478bd9Sstevel@tonic-gate {
9687c478bd9Sstevel@tonic-gate 	struct header *blk, *next;	/* ptr to ordinary blocks */
9697c478bd9Sstevel@tonic-gate 	struct holdblk *hblk;		/* ptr to holding blocks */
9707c478bd9Sstevel@tonic-gate 	struct mallinfo inf;		/* return value */
9717c478bd9Sstevel@tonic-gate 	int	i;			/* the ubiquitous counter */
9727c478bd9Sstevel@tonic-gate 	ssize_t size;			/* size of a block */
9737c478bd9Sstevel@tonic-gate 	ssize_t fsp;			/* free space in 1 hold block */
9747c478bd9Sstevel@tonic-gate 
9757c478bd9Sstevel@tonic-gate 	(void) mutex_lock(&mlock);
9767c478bd9Sstevel@tonic-gate 	(void) memset(&inf, 0, sizeof (struct mallinfo));
9777c478bd9Sstevel@tonic-gate 	if (freeptr[0].nextfree == GROUND) {
9787c478bd9Sstevel@tonic-gate 		(void) mutex_unlock(&mlock);
9797c478bd9Sstevel@tonic-gate 		return (inf);
9807c478bd9Sstevel@tonic-gate 	}
9817c478bd9Sstevel@tonic-gate 	blk = CLRBUSY(arena[1].nextblk);
9827c478bd9Sstevel@tonic-gate 	/* return total space used */
9837c478bd9Sstevel@tonic-gate 	inf.arena = (char *)arenaend - (char *)blk;
9847c478bd9Sstevel@tonic-gate 
9857c478bd9Sstevel@tonic-gate 	/*
9867c478bd9Sstevel@tonic-gate 	 * loop through arena, counting # of blocks, and
9877c478bd9Sstevel@tonic-gate 	 * and space used by blocks
9887c478bd9Sstevel@tonic-gate 	 */
9897c478bd9Sstevel@tonic-gate 	next = CLRBUSY(blk->nextblk);
9907c478bd9Sstevel@tonic-gate 	while (next != &(arena[1])) {
9917c478bd9Sstevel@tonic-gate 		inf.ordblks++;
9927c478bd9Sstevel@tonic-gate 		size = (char *)next - (char *)blk;
9937c478bd9Sstevel@tonic-gate 		if (TESTBUSY(blk->nextblk)) {
9947c478bd9Sstevel@tonic-gate 			inf.uordblks += size;
9957c478bd9Sstevel@tonic-gate 			inf.keepcost += HEADSZ-MINHEAD;
9967c478bd9Sstevel@tonic-gate 		} else {
9977c478bd9Sstevel@tonic-gate 			inf.fordblks += size;
9987c478bd9Sstevel@tonic-gate 		}
9997c478bd9Sstevel@tonic-gate 		blk = next;
10007c478bd9Sstevel@tonic-gate 		next = CLRBUSY(blk->nextblk);
10017c478bd9Sstevel@tonic-gate 	}
10027c478bd9Sstevel@tonic-gate 
10037c478bd9Sstevel@tonic-gate 	/*
10047c478bd9Sstevel@tonic-gate 	 * if any holding block have been allocated
10057c478bd9Sstevel@tonic-gate 	 * then examine space in holding blks
10067c478bd9Sstevel@tonic-gate 	 */
10077c478bd9Sstevel@tonic-gate 	if (change && holdhead != NULL) {
10087c478bd9Sstevel@tonic-gate 		for (i = fastct; i > 0; i--) {	/* loop thru ea. chain */
10097c478bd9Sstevel@tonic-gate 			hblk = holdhead[i];
10107c478bd9Sstevel@tonic-gate 			/* do only if chain not empty */
10117c478bd9Sstevel@tonic-gate 			if (hblk != HGROUND) {
10127c478bd9Sstevel@tonic-gate 				size = hblk->blksz +
10137c478bd9Sstevel@tonic-gate 				    sizeof (struct lblk) - sizeof (int);
10147c478bd9Sstevel@tonic-gate 				do {	/* loop thru 1 hold blk chain */
10157c478bd9Sstevel@tonic-gate 					inf.hblks++;
10167c478bd9Sstevel@tonic-gate 					fsp = freespace(hblk);
10177c478bd9Sstevel@tonic-gate 					inf.fsmblks += fsp;
10187c478bd9Sstevel@tonic-gate 					inf.usmblks += numlblks*size - fsp;
10197c478bd9Sstevel@tonic-gate 					inf.smblks += numlblks;
10207c478bd9Sstevel@tonic-gate 					hblk = hblk->nexthblk;
10217c478bd9Sstevel@tonic-gate 				} while (hblk != holdhead[i]);
10227c478bd9Sstevel@tonic-gate 			}
10237c478bd9Sstevel@tonic-gate 		}
10247c478bd9Sstevel@tonic-gate 	}
10257c478bd9Sstevel@tonic-gate 	inf.hblkhd = (inf.smblks / numlblks) * sizeof (struct holdblk);
10267c478bd9Sstevel@tonic-gate 	/* holding block were counted in ordblks, so subtract off */
10277c478bd9Sstevel@tonic-gate 	inf.ordblks -= inf.hblks;
10287c478bd9Sstevel@tonic-gate 	inf.uordblks -= inf.hblkhd + inf.usmblks + inf.fsmblks;
10297c478bd9Sstevel@tonic-gate 	inf.keepcost -= inf.hblks*(HEADSZ - MINHEAD);
10307c478bd9Sstevel@tonic-gate 	(void) mutex_unlock(&mlock);
10317c478bd9Sstevel@tonic-gate 	return (inf);
10327c478bd9Sstevel@tonic-gate }
10337c478bd9Sstevel@tonic-gate 
10347c478bd9Sstevel@tonic-gate 
10357c478bd9Sstevel@tonic-gate /*
10367c478bd9Sstevel@tonic-gate  * freespace - calc. how much space is used in the free
10377c478bd9Sstevel@tonic-gate  *		    small blocks in a given holding block
10387c478bd9Sstevel@tonic-gate  *
10397c478bd9Sstevel@tonic-gate  *	input - hblk = given holding block
10407c478bd9Sstevel@tonic-gate  *
10417c478bd9Sstevel@tonic-gate  *	returns space used in free small blocks of hblk
10427c478bd9Sstevel@tonic-gate  */
10437c478bd9Sstevel@tonic-gate 
10447c478bd9Sstevel@tonic-gate static ssize_t
10457c478bd9Sstevel@tonic-gate freespace(struct holdblk *holdblk)
10467c478bd9Sstevel@tonic-gate {
10477c478bd9Sstevel@tonic-gate 	struct lblk *lblk;
10487c478bd9Sstevel@tonic-gate 	ssize_t space = 0;
10497c478bd9Sstevel@tonic-gate 	ssize_t size;
10507c478bd9Sstevel@tonic-gate 	struct lblk *unused;
10517c478bd9Sstevel@tonic-gate 
10527c478bd9Sstevel@tonic-gate 	lblk = CLRSMAL(holdblk->lfreeq);
10537c478bd9Sstevel@tonic-gate 	size = holdblk->blksz + sizeof (struct lblk) - sizeof (int);
10547c478bd9Sstevel@tonic-gate 	unused = CLRSMAL(holdblk->unused);
10557c478bd9Sstevel@tonic-gate 	/* follow free chain */
10567c478bd9Sstevel@tonic-gate 	while ((lblk != LGROUND) && (lblk != unused)) {
10577c478bd9Sstevel@tonic-gate 		space += size;
10587c478bd9Sstevel@tonic-gate 		lblk = CLRSMAL(lblk->header.nextfree);
10597c478bd9Sstevel@tonic-gate 	}
10607c478bd9Sstevel@tonic-gate 	space += ((char *)holdblk + HOLDSZ(size)) - (char *)unused;
10617c478bd9Sstevel@tonic-gate 	return (space);
10627c478bd9Sstevel@tonic-gate }
10637c478bd9Sstevel@tonic-gate 
10647c478bd9Sstevel@tonic-gate static void *
10657c478bd9Sstevel@tonic-gate morecore(size_t bytes)
10667c478bd9Sstevel@tonic-gate {
10677c478bd9Sstevel@tonic-gate 	void * ret;
10687c478bd9Sstevel@tonic-gate 
10697c478bd9Sstevel@tonic-gate 	if (bytes > LONG_MAX) {
10707c478bd9Sstevel@tonic-gate 		intptr_t wad;
10717c478bd9Sstevel@tonic-gate 		/*
10727c478bd9Sstevel@tonic-gate 		 * The request size is too big. We need to do this in
10737c478bd9Sstevel@tonic-gate 		 * chunks. Sbrk only takes an int for an arg.
10747c478bd9Sstevel@tonic-gate 		 */
10757c478bd9Sstevel@tonic-gate 		if (bytes == ULONG_MAX)
10767c478bd9Sstevel@tonic-gate 			return ((void *)-1);
10777c478bd9Sstevel@tonic-gate 
10787c478bd9Sstevel@tonic-gate 		ret = sbrk(0);
10797c478bd9Sstevel@tonic-gate 		wad = LONG_MAX;
10807c478bd9Sstevel@tonic-gate 		while (wad > 0) {
10817c478bd9Sstevel@tonic-gate 			if (sbrk(wad) == (void *)-1) {
10827c478bd9Sstevel@tonic-gate 				if (ret != sbrk(0))
10837c478bd9Sstevel@tonic-gate 					(void) sbrk(-LONG_MAX);
10847c478bd9Sstevel@tonic-gate 				return ((void *)-1);
10857c478bd9Sstevel@tonic-gate 			}
10867c478bd9Sstevel@tonic-gate 			bytes -= LONG_MAX;
10877c478bd9Sstevel@tonic-gate 			wad = bytes;
10887c478bd9Sstevel@tonic-gate 		}
10897c478bd9Sstevel@tonic-gate 	} else
10907c478bd9Sstevel@tonic-gate 		ret = sbrk(bytes);
10917c478bd9Sstevel@tonic-gate 
10927c478bd9Sstevel@tonic-gate 	return (ret);
10937c478bd9Sstevel@tonic-gate }
10947c478bd9Sstevel@tonic-gate 
10957c478bd9Sstevel@tonic-gate #ifdef debug
10967c478bd9Sstevel@tonic-gate int
10977c478bd9Sstevel@tonic-gate check_arena(void)
10987c478bd9Sstevel@tonic-gate {
10997c478bd9Sstevel@tonic-gate 	struct header *blk, *prev, *next;	/* ptr to ordinary blocks */
11007c478bd9Sstevel@tonic-gate 
11017c478bd9Sstevel@tonic-gate 	(void) mutex_lock(&mlock);
11027c478bd9Sstevel@tonic-gate 	if (freeptr[0].nextfree == GROUND) {
11037c478bd9Sstevel@tonic-gate 		(void) mutex_unlock(&mlock);
11047c478bd9Sstevel@tonic-gate 		return (-1);
11057c478bd9Sstevel@tonic-gate 	}
11067c478bd9Sstevel@tonic-gate 	blk = arena + 1;
11077c478bd9Sstevel@tonic-gate 
11087c478bd9Sstevel@tonic-gate 	/* loop through arena, checking */
11097c478bd9Sstevel@tonic-gate 	blk = (struct header *)CLRALL(blk->nextblk);
11107c478bd9Sstevel@tonic-gate 	next = (struct header *)CLRALL(blk->nextblk);
11117c478bd9Sstevel@tonic-gate 	while (next != arena + 1) {
11127c478bd9Sstevel@tonic-gate 		assert(blk >= arena + 1);
11137c478bd9Sstevel@tonic-gate 		assert(blk <= lastblk);
11147c478bd9Sstevel@tonic-gate 		assert(next >= blk + 1);
11157c478bd9Sstevel@tonic-gate 		assert(((uintptr_t)((struct header *)blk->nextblk) &
11167c478bd9Sstevel@tonic-gate 		    (4 | SMAL)) == 0);
11177c478bd9Sstevel@tonic-gate 
11187c478bd9Sstevel@tonic-gate 		if (TESTBUSY(blk->nextblk) == 0) {
11197c478bd9Sstevel@tonic-gate 			assert(blk->nextfree >= freeptr);
11207c478bd9Sstevel@tonic-gate 			assert(blk->prevfree >= freeptr);
11217c478bd9Sstevel@tonic-gate 			assert(blk->nextfree <= lastblk);
11227c478bd9Sstevel@tonic-gate 			assert(blk->prevfree <= lastblk);
11237c478bd9Sstevel@tonic-gate 			assert(((uintptr_t)((struct header *)blk->nextfree) &
11247c478bd9Sstevel@tonic-gate 			    7) == 0);
11257c478bd9Sstevel@tonic-gate 			assert(((uintptr_t)((struct header *)blk->prevfree) &
11267c478bd9Sstevel@tonic-gate 			    7) == 0 || blk->prevfree == freeptr);
11277c478bd9Sstevel@tonic-gate 		}
11287c478bd9Sstevel@tonic-gate 		blk = next;
11297c478bd9Sstevel@tonic-gate 		next = CLRBUSY(blk->nextblk);
11307c478bd9Sstevel@tonic-gate 	}
11317c478bd9Sstevel@tonic-gate 	(void) mutex_unlock(&mlock);
11327c478bd9Sstevel@tonic-gate 	return (0);
11337c478bd9Sstevel@tonic-gate }
11347c478bd9Sstevel@tonic-gate 
11357c478bd9Sstevel@tonic-gate #define	RSTALLOC	1
11367c478bd9Sstevel@tonic-gate #endif
11377c478bd9Sstevel@tonic-gate 
11387c478bd9Sstevel@tonic-gate #ifdef RSTALLOC
11397c478bd9Sstevel@tonic-gate /*
11407c478bd9Sstevel@tonic-gate  * rstalloc - reset alloc routines
11417c478bd9Sstevel@tonic-gate  *
11427c478bd9Sstevel@tonic-gate  *	description -	return allocated memory and reset
11437c478bd9Sstevel@tonic-gate  *			allocation pointers.
11447c478bd9Sstevel@tonic-gate  *
11457c478bd9Sstevel@tonic-gate  *	Warning - This is for debugging purposes only.
11467c478bd9Sstevel@tonic-gate  *		  It will return all memory allocated after
11477c478bd9Sstevel@tonic-gate  *		  the first call to malloc, even if some
11487c478bd9Sstevel@tonic-gate  *		  of it was fetched by a user's sbrk().
11497c478bd9Sstevel@tonic-gate  */
11507c478bd9Sstevel@tonic-gate 
11517c478bd9Sstevel@tonic-gate void
11527c478bd9Sstevel@tonic-gate rstalloc(void)
11537c478bd9Sstevel@tonic-gate {
11547c478bd9Sstevel@tonic-gate 	(void) mutex_lock(&mlock);
11557c478bd9Sstevel@tonic-gate 	minhead = MINHEAD;
11567c478bd9Sstevel@tonic-gate 	grain = ALIGNSZ;
11577c478bd9Sstevel@tonic-gate 	numlblks = NUMLBLKS;
11587c478bd9Sstevel@tonic-gate 	fastct = FASTCT;
11597c478bd9Sstevel@tonic-gate 	maxfast = MAXFAST;
11607c478bd9Sstevel@tonic-gate 	change = 0;
11617c478bd9Sstevel@tonic-gate 	if (freeptr[0].nextfree == GROUND) {
11627c478bd9Sstevel@tonic-gate 		(void) mutex_unlock(&mlock);
11637c478bd9Sstevel@tonic-gate 		return;
11647c478bd9Sstevel@tonic-gate 	}
11657c478bd9Sstevel@tonic-gate 	brk(CLRBUSY(arena[1].nextblk));
11667c478bd9Sstevel@tonic-gate 	freeptr[0].nextfree = GROUND;
11677c478bd9Sstevel@tonic-gate #ifdef debug
11687c478bd9Sstevel@tonic-gate 	case1count = 0;
11697c478bd9Sstevel@tonic-gate #endif
11707c478bd9Sstevel@tonic-gate 	(void) mutex_unlock(&mlock);
11717c478bd9Sstevel@tonic-gate }
11727c478bd9Sstevel@tonic-gate #endif	/* RSTALLOC */
11737c478bd9Sstevel@tonic-gate 
11747c478bd9Sstevel@tonic-gate /*
11757c478bd9Sstevel@tonic-gate  * cfree is an undocumented, obsolete function
11767c478bd9Sstevel@tonic-gate  */
11777c478bd9Sstevel@tonic-gate 
11784088bb40Sraf /* ARGSUSED1 */
11797c478bd9Sstevel@tonic-gate void
11804088bb40Sraf cfree(void *p, size_t num, size_t size)
11817c478bd9Sstevel@tonic-gate {
11827c478bd9Sstevel@tonic-gate 	free(p);
11837c478bd9Sstevel@tonic-gate }
11841d530678Sraf 
11851d530678Sraf static void
11861d530678Sraf malloc_prepare()
11871d530678Sraf {
11881d530678Sraf 	(void) mutex_lock(&mlock);
11891d530678Sraf }
11901d530678Sraf 
11911d530678Sraf static void
11921d530678Sraf malloc_release()
11931d530678Sraf {
11941d530678Sraf 	(void) mutex_unlock(&mlock);
11951d530678Sraf }
11961d530678Sraf 
11971d530678Sraf #pragma init(malloc_init)
11981d530678Sraf static void
11991d530678Sraf malloc_init(void)
12001d530678Sraf {
12011d530678Sraf 	(void) pthread_atfork(malloc_prepare, malloc_release, malloc_release);
12021d530678Sraf }
1203