[unix-history] / lib / libc / stdlib / malloc.c

/*
 * Copyright (c) 1983 Regents of the University of California.
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 * 3. All advertising materials mentioning features or use of this software
 *    must display the following acknowledgement:
 *	This product includes software developed by the University of
 *	California, Berkeley and its contributors.
 * 4. Neither the name of the University nor the names of its contributors
 *    may be used to endorse or promote products derived from this software
 *    without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 * SUCH DAMAGE.
 */

#if defined(LIBC_SCCS) && !defined(lint)
static char sccsid[] = "@(#)malloc.c	5.11 (Berkeley) 2/23/91";
#endif /* LIBC_SCCS and not lint */

/*
 * malloc.c (Caltech) 2/21/82
 * Chris Kingsley, kingsley@cit-20.
 *
 * This is a very fast storage allocator.  It allocates blocks of a small 
 * number of different sizes, and keeps free lists of each size.  Blocks that
 * don't exactly fit are passed up to the next larger size.  In this 
 * implementation, the available sizes are 2^n-4 (or 2^n-10) bytes long.
 * This is designed for use in a virtual memory environment.
 */

#include <sys/types.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>

#define	NULL 0

static void morecore();
static int findbucket();

/*
 * The overhead on a block is at least 4 bytes.  When free, this space
 * contains a pointer to the next free block, and the bottom two bits must
 * be zero.  When in use, the first byte is set to MAGIC, and the second
 * byte is the size index.  The remaining bytes are for alignment.
 * If range checking is enabled then a second word holds the size of the
 * requested block, less 1, rounded up to a multiple of sizeof(RMAGIC).
 * The order of elements is critical: ov_magic must overlay the low order
 * bits of ov_next, and ov_magic can not be a valid ov_next bit pattern.
 */
union	overhead {
	union	overhead *ov_next;	/* when free */
	struct {
		u_char	ovu_magic;	/* magic number */
		u_char	ovu_index;	/* bucket # */
#ifdef RCHECK
		u_short	ovu_rmagic;	/* range magic number */
		u_int	ovu_size;	/* actual block size */
#endif
	} ovu;
#define	ov_magic	ovu.ovu_magic
#define	ov_index	ovu.ovu_index
#define	ov_rmagic	ovu.ovu_rmagic
#define	ov_size		ovu.ovu_size
};

#define	MAGIC		0xef		/* magic # on accounting info */
#define RMAGIC		0x5555		/* magic # on range info */

#ifdef RCHECK
#define	RSLOP		sizeof (u_short)
#else
#define	RSLOP		0
#endif

/*
 * nextf[i] is the pointer to the next free block of size 2^(i+3).  The
 * smallest allocatable block is 8 bytes.  The overhead information
 * precedes the data area returned to the user.
 */
#define	NBUCKETS 30
static	union overhead *nextf[NBUCKETS];
extern	char *sbrk();

static	int pagesz;			/* page size */
static	int pagebucket;			/* page size bucket */

#ifdef MSTATS
/*
 * nmalloc[i] is the difference between the number of mallocs and frees
 * for a given block size.
 */
static	u_int nmalloc[NBUCKETS];
#include <stdio.h>
#endif

#if defined(DEBUG) || defined(RCHECK)
#define	ASSERT(p)   if (!(p)) botch("p")
#include <stdio.h>
static
botch(s)
	char *s;
{
	fprintf(stderr, "\r\nassertion botched: %s\r\n", s);
 	(void) fflush(stderr);		/* just in case user buffered it */
	abort();
}
#else
#define	ASSERT(p)
#endif

void *
malloc(nbytes)
	size_t nbytes;
{
  	register union overhead *op;
  	register int bucket, n;
	register unsigned amt;

	/*
	 * First time malloc is called, setup page size and
	 * align break pointer so all data will be page aligned.
	 */
	if (pagesz == 0) {
		pagesz = n = getpagesize();
		op = (union overhead *)sbrk(0);
  		n = n - sizeof (*op) - ((int)op & (n - 1));
		if (n < 0)
			n += pagesz;
  		if (n) {
  			if (sbrk(n) == (char *)-1)
				return (NULL);
		}
		bucket = 0;
		amt = 8;
		while (pagesz > amt) {
			amt <<= 1;
			bucket++;
		}
		pagebucket = bucket;
	}
	/*
	 * Convert amount of memory requested into closest block size
	 * stored in hash buckets which satisfies request.
	 * Account for space used per block for accounting.
	 */
	if (nbytes <= (n = pagesz - sizeof (*op) - RSLOP)) {
#ifndef RCHECK
		amt = 8;	/* size of first bucket */
		bucket = 0;
#else
		amt = 16;	/* size of first bucket */
		bucket = 1;
#endif
		n = -(sizeof (*op) + RSLOP);
	} else {
		amt = pagesz;
		bucket = pagebucket;
	}
	while (nbytes > amt + n) {
		amt <<= 1;
		if (amt == 0)
			return (NULL);
		bucket++;
	}
	/*
	 * If nothing in hash bucket right now,
	 * request more memory from the system.
	 */
  	if ((op = nextf[bucket]) == NULL) {
  		morecore(bucket);
  		if ((op = nextf[bucket]) == NULL)
  			return (NULL);
	}
	/* remove from linked list */
  	nextf[bucket] = op->ov_next;
	op->ov_magic = MAGIC;
	op->ov_index = bucket;
#ifdef MSTATS
  	nmalloc[bucket]++;
#endif
#ifdef RCHECK
	/*
	 * Record allocated size of block and
	 * bound space with magic numbers.
	 */
	op->ov_size = (nbytes + RSLOP - 1) & ~(RSLOP - 1);
	op->ov_rmagic = RMAGIC;
  	*(u_short *)((caddr_t)(op + 1) + op->ov_size) = RMAGIC;
#endif
  	return ((char *)(op + 1));
}

/*
 * Allocate more memory to the indicated bucket.
 */
static void
morecore(bucket)
	int bucket;
{
  	register union overhead *op;
	register int sz;		/* size of desired block */
  	int amt;			/* amount to allocate */
  	int nblks;			/* how many blocks we get */

	/*
	 * sbrk_size <= 0 only for big, FLUFFY, requests (about
	 * 2^30 bytes on a VAX, I think) or for a negative arg.
	 */
	sz = 1 << (bucket + 3);
#ifdef DEBUG
	ASSERT(sz > 0);
#else
	if (sz <= 0)
		return;
#endif
	if (sz < pagesz) {
		amt = pagesz;
  		nblks = amt / sz;
	} else {
		amt = sz + pagesz;
		nblks = 1;
	}
	op = (union overhead *)sbrk(amt);
	/* no more room! */
  	if ((int)op == -1)
  		return;
	/*
	 * Add new memory allocated to that on
	 * free list for this hash bucket.
	 */
  	nextf[bucket] = op;
  	while (--nblks > 0) {
		op->ov_next = (union overhead *)((caddr_t)op + sz);
		op = (union overhead *)((caddr_t)op + sz);
  	}
}

void
free(cp)
	void *cp;
{   
  	register int size;
	register union overhead *op;

  	if (cp == NULL)
  		return;
	op = (union overhead *)((caddr_t)cp - sizeof (union overhead));
#ifdef DEBUG
  	ASSERT(op->ov_magic == MAGIC);		/* make sure it was in use */
#else
	if (op->ov_magic != MAGIC)
		return;				/* sanity */
#endif
#ifdef RCHECK
  	ASSERT(op->ov_rmagic == RMAGIC);
	ASSERT(*(u_short *)((caddr_t)(op + 1) + op->ov_size) == RMAGIC);
#endif
  	size = op->ov_index;
  	ASSERT(size < NBUCKETS);
	op->ov_next = nextf[size];	/* also clobbers ov_magic */
  	nextf[size] = op;
#ifdef MSTATS
  	nmalloc[size]--;
#endif
}

/*
 * When a program attempts "storage compaction" as mentioned in the
 * old malloc man page, it realloc's an already freed block.  Usually
 * this is the last block it freed; occasionally it might be farther
 * back.  We have to search all the free lists for the block in order
 * to determine its bucket: 1st we make one pass thru the lists
 * checking only the first block in each; if that fails we search
 * ``realloc_srchlen'' blocks in each list for a match (the variable
 * is extern so the caller can modify it).  If that fails we just copy
 * however many bytes was given to realloc() and hope it's not huge.
 */
int realloc_srchlen = 4;	/* 4 should be plenty, -1 =>'s whole list */

void *
realloc(cp, nbytes)
	void *cp; 
	size_t nbytes;
{   
  	register u_int onb;
	register int i;
	union overhead *op;
  	char *res;
	int was_alloced = 0;

  	if (cp == NULL)
  		return (malloc(nbytes));
	op = (union overhead *)((caddr_t)cp - sizeof (union overhead));
	if (op->ov_magic == MAGIC) {
		was_alloced++;
		i = op->ov_index;
	} else {
		/*
		 * Already free, doing "compaction".
		 *
		 * Search for the old block of memory on the
		 * free list.  First, check the most common
		 * case (last element free'd), then (this failing)
		 * the last ``realloc_srchlen'' items free'd.
		 * If all lookups fail, then assume the size of
		 * the memory block being realloc'd is the
		 * largest possible (so that all "nbytes" of new
		 * memory are copied into).  Note that this could cause
		 * a memory fault if the old area was tiny, and the moon
		 * is gibbous.  However, that is very unlikely.
		 */
		if ((i = findbucket(op, 1)) < 0 &&
		    (i = findbucket(op, realloc_srchlen)) < 0)
			i = NBUCKETS;
	}
	onb = 1 << (i + 3);
	if (onb < pagesz)
		onb -= sizeof (*op) + RSLOP;
	else
		onb += pagesz - sizeof (*op) - RSLOP;
	/* avoid the copy if same size block */
	if (was_alloced) {
		if (i) {
			i = 1 << (i + 2);
			if (i < pagesz)
				i -= sizeof (*op) + RSLOP;
			else
				i += pagesz - sizeof (*op) - RSLOP;
		}
		if (nbytes <= onb && nbytes > i) {
#ifdef RCHECK
			op->ov_size = (nbytes + RSLOP - 1) & ~(RSLOP - 1);
			*(u_short *)((caddr_t)(op + 1) + op->ov_size) = RMAGIC;
#endif
			return(cp);
		} else
			free(cp);
	}
  	if ((res = malloc(nbytes)) == NULL)
  		return (NULL);
  	if (cp != res)		/* common optimization if "compacting" */
		bcopy(cp, res, (nbytes < onb) ? nbytes : onb);
  	return (res);
}

/*
 * Search ``srchlen'' elements of each free list for a block whose
 * header starts at ``freep''.  If srchlen is -1 search the whole list.
 * Return bucket number, or -1 if not found.
 */
static
findbucket(freep, srchlen)
	union overhead *freep;
	int srchlen;
{
	register union overhead *p;
	register int i, j;

	for (i = 0; i < NBUCKETS; i++) {
		j = 0;
		for (p = nextf[i]; p && j != srchlen; p = p->ov_next) {
			if (p == freep)
				return (i);
			j++;
		}
	}
	return (-1);
}

#ifdef MSTATS
/*
 * mstats - print out statistics about malloc
 * 
 * Prints two lines of numbers, one showing the length of the free list
 * for each size category, the second showing the number of mallocs -
 * frees for each size category.
 */
mstats(s)
	char *s;
{
  	register int i, j;
  	register union overhead *p;
  	int totfree = 0,
  	totused = 0;

  	fprintf(stderr, "Memory allocation statistics %s\nfree:\t", s);
  	for (i = 0; i < NBUCKETS; i++) {
  		for (j = 0, p = nextf[i]; p; p = p->ov_next, j++)
  			;
  		fprintf(stderr, " %d", j);
  		totfree += j * (1 << (i + 3));
  	}
  	fprintf(stderr, "\nused:\t");
  	for (i = 0; i < NBUCKETS; i++) {
  		fprintf(stderr, " %d", nmalloc[i]);
  		totused += nmalloc[i] * (1 << (i + 3));
  	}
  	fprintf(stderr, "\n\tTotal in use: %d, total free: %d\n",
	    totused, totfree);
}
#endif
Commit	Line	Data
15637ed4 RG	1	/*
	2	* Copyright (c) 1983 Regents of the University of California.
	3	* All rights reserved.
	4	*
	5	* Redistribution and use in source and binary forms, with or without
	6	* modification, are permitted provided that the following conditions
	7	* are met:
	8	* 1. Redistributions of source code must retain the above copyright
	9	* notice, this list of conditions and the following disclaimer.
	10	* 2. Redistributions in binary form must reproduce the above copyright
	11	* notice, this list of conditions and the following disclaimer in the
	12	* documentation and/or other materials provided with the distribution.
	13	* 3. All advertising materials mentioning features or use of this software
	14	* must display the following acknowledgement:
	15	* This product includes software developed by the University of
	16	* California, Berkeley and its contributors.
	17	* 4. Neither the name of the University nor the names of its contributors
	18	* may be used to endorse or promote products derived from this software
	19	* without specific prior written permission.
	20	*
	21	* THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
	22	* ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
	23	* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
	24	* ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
	25	* FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
	26	* DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
	27	* OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
	28	* HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
	29	* LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
	30	* OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
	31	* SUCH DAMAGE.
	32	*/
	33
	34	#if defined(LIBC_SCCS) && !defined(lint)
	35	static char sccsid[] = "@(#)malloc.c 5.11 (Berkeley) 2/23/91";
	36	#endif /* LIBC_SCCS and not lint */
	37
	38	/*
	39	* malloc.c (Caltech) 2/21/82
	40	* Chris Kingsley, kingsley@cit-20.
	41	*
	42	* This is a very fast storage allocator. It allocates blocks of a small
	43	* number of different sizes, and keeps free lists of each size. Blocks that
	44	* don't exactly fit are passed up to the next larger size. In this
	45	* implementation, the available sizes are 2^n-4 (or 2^n-10) bytes long.
	46	* This is designed for use in a virtual memory environment.
	47	*/
	48
	49	#include <sys/types.h>
	50	#include <stdlib.h>
	51	#include <string.h>
	52	#include <unistd.h>
	53
	54	#define NULL 0
	55
	56	static void morecore();
	57	static int findbucket();
	58
	59	/*
	60	* The overhead on a block is at least 4 bytes. When free, this space
	61	* contains a pointer to the next free block, and the bottom two bits must
	62	* be zero. When in use, the first byte is set to MAGIC, and the second
	63	* byte is the size index. The remaining bytes are for alignment.
	64	* If range checking is enabled then a second word holds the size of the
65	* requested block, less 1, rounded up to a multiple of sizeof(RMAGIC).
66	* The order of elements is critical: ov_magic must overlay the low order
67	* bits of ov_next, and ov_magic can not be a valid ov_next bit pattern.
68	*/
69	union overhead {
70	union overhead ov_next; / when free */
71	struct {
72	u_char ovu_magic; /* magic number */
73	u_char ovu_index; /* bucket # */
74	#ifdef RCHECK
75	u_short ovu_rmagic; /* range magic number */
76	u_int ovu_size; /* actual block size */
77	#endif
78	} ovu;
79	#define ov_magic ovu.ovu_magic
80	#define ov_index ovu.ovu_index
81	#define ov_rmagic ovu.ovu_rmagic
82	#define ov_size ovu.ovu_size
83	};
84
85	#define MAGIC 0xef /* magic # on accounting info */
86	#define RMAGIC 0x5555 /* magic # on range info */
87
88	#ifdef RCHECK
89	#define RSLOP sizeof (u_short)
90	#else
91	#define RSLOP 0
92	#endif
93
94	/*
95	* nextf[i] is the pointer to the next free block of size 2^(i+3). The
96	* smallest allocatable block is 8 bytes. The overhead information
97	* precedes the data area returned to the user.
98	*/
99	#define NBUCKETS 30
100	static union overhead *nextf[NBUCKETS];
101	extern char *sbrk();
102
103	static int pagesz; /* page size */
104	static int pagebucket; /* page size bucket */
105
106	#ifdef MSTATS
107	/*
108	* nmalloc[i] is the difference between the number of mallocs and frees
109	* for a given block size.
110	*/
111	static u_int nmalloc[NBUCKETS];
112	#include <stdio.h>
113	#endif
114
115	#if defined(DEBUG) \|\| defined(RCHECK)
116	#define ASSERT(p) if (!(p)) botch("p")
117	#include <stdio.h>
118	static
119	botch(s)
120	char *s;
121	{
122	fprintf(stderr, "\r\nassertion botched: %s\r\n", s);
123	(void) fflush(stderr); /* just in case user buffered it */
124	abort();
125	}
126	#else
127	#define ASSERT(p)
128	#endif
129
130	void *
131	malloc(nbytes)
132	size_t nbytes;
133	{
134	register union overhead *op;
135	register int bucket, n;
136	register unsigned amt;
137
138	/*
139	* First time malloc is called, setup page size and
140	* align break pointer so all data will be page aligned.
141	*/
142	if (pagesz == 0) {
143	pagesz = n = getpagesize();
144	op = (union overhead *)sbrk(0);
145	n = n - sizeof (*op) - ((int)op & (n - 1));
146	if (n < 0)
147	n += pagesz;
148	if (n) {
149	if (sbrk(n) == (char *)-1)
150	return (NULL);
151	}
152	bucket = 0;
153	amt = 8;
154	while (pagesz > amt) {
155	amt <<= 1;
156	bucket++;
157	}
158	pagebucket = bucket;
159	}
160	/*
161	* Convert amount of memory requested into closest block size
162	* stored in hash buckets which satisfies request.
163	* Account for space used per block for accounting.
164	*/
165	if (nbytes <= (n = pagesz - sizeof (*op) - RSLOP)) {
166	#ifndef RCHECK
167	amt = 8; /* size of first bucket */
168	bucket = 0;
169	#else
170	amt = 16; /* size of first bucket */
171	bucket = 1;
172	#endif
173	n = -(sizeof (*op) + RSLOP);
174	} else {
175	amt = pagesz;
176	bucket = pagebucket;
177	}
178	while (nbytes > amt + n) {
179	amt <<= 1;
180	if (amt == 0)
181	return (NULL);
182	bucket++;
183	}
184	/*
185	* If nothing in hash bucket right now,
186	* request more memory from the system.
187	*/
188	if ((op = nextf[bucket]) == NULL) {
189	morecore(bucket);
190	if ((op = nextf[bucket]) == NULL)
191	return (NULL);
192	}
193	/* remove from linked list */
194	nextf[bucket] = op->ov_next;
195	op->ov_magic = MAGIC;
196	op->ov_index = bucket;
197	#ifdef MSTATS
198	nmalloc[bucket]++;
199	#endif
200	#ifdef RCHECK
201	/*
202	* Record allocated size of block and
203	* bound space with magic numbers.
204	*/
205	op->ov_size = (nbytes + RSLOP - 1) & ~(RSLOP - 1);
206	op->ov_rmagic = RMAGIC;
207	(u_short )((caddr_t)(op + 1) + op->ov_size) = RMAGIC;
208	#endif
209	return ((char *)(op + 1));
210	}
211
212	/*
213	* Allocate more memory to the indicated bucket.
214	*/
215	static void
216	morecore(bucket)
217	int bucket;
218	{
219	register union overhead *op;
220	register int sz; /* size of desired block */
221	int amt; /* amount to allocate */
222	int nblks; /* how many blocks we get */
223
224	/*
225	* sbrk_size <= 0 only for big, FLUFFY, requests (about
226	* 2^30 bytes on a VAX, I think) or for a negative arg.
227	*/
228	sz = 1 << (bucket + 3);
229	#ifdef DEBUG
230	ASSERT(sz > 0);
231	#else
232	if (sz <= 0)
233	return;
234	#endif
235	if (sz < pagesz) {
236	amt = pagesz;
237	nblks = amt / sz;
238	} else {
239	amt = sz + pagesz;
240	nblks = 1;
241	}
242	op = (union overhead *)sbrk(amt);
243	/* no more room! */
244	if ((int)op == -1)
245	return;
246	/*
247	* Add new memory allocated to that on
248	* free list for this hash bucket.
249	*/
250	nextf[bucket] = op;
251	while (--nblks > 0) {
252	op->ov_next = (union overhead *)((caddr_t)op + sz);
253	op = (union overhead *)((caddr_t)op + sz);
254	}
255	}
256
257	void
258	free(cp)
259	void *cp;
260	{
261	register int size;
262	register union overhead *op;
263
264	if (cp == NULL)
265	return;
266	op = (union overhead *)((caddr_t)cp - sizeof (union overhead));
267	#ifdef DEBUG
268	ASSERT(op->ov_magic == MAGIC); /* make sure it was in use */
269	#else
270	if (op->ov_magic != MAGIC)
271	return; /* sanity */
272	#endif
273	#ifdef RCHECK
274	ASSERT(op->ov_rmagic == RMAGIC);
275	ASSERT((u_short )((caddr_t)(op + 1) + op->ov_size) == RMAGIC);
276	#endif
277	size = op->ov_index;
278	ASSERT(size < NBUCKETS);
279	op->ov_next = nextf[size]; /* also clobbers ov_magic */
280	nextf[size] = op;
281	#ifdef MSTATS
282	nmalloc[size]--;
283	#endif
284	}
285
286	/*
287	* When a program attempts "storage compaction" as mentioned in the
288	* old malloc man page, it realloc's an already freed block. Usually
289	* this is the last block it freed; occasionally it might be farther
290	* back. We have to search all the free lists for the block in order
291	* to determine its bucket: 1st we make one pass thru the lists
292	* checking only the first block in each; if that fails we search
293	* ``realloc_srchlen'' blocks in each list for a match (the variable
294	* is extern so the caller can modify it). If that fails we just copy
295	* however many bytes was given to realloc() and hope it's not huge.
296	*/
297	int realloc_srchlen = 4; /* 4 should be plenty, -1 =>'s whole list */
298
299	void *
300	realloc(cp, nbytes)
301	void *cp;
302	size_t nbytes;
303	{
304	register u_int onb;
305	register int i;
306	union overhead *op;
307	char *res;
308	int was_alloced = 0;
309
310	if (cp == NULL)
311	return (malloc(nbytes));
312	op = (union overhead *)((caddr_t)cp - sizeof (union overhead));
313	if (op->ov_magic == MAGIC) {
314	was_alloced++;
315	i = op->ov_index;
316	} else {
317	/*
318	* Already free, doing "compaction".
319	*
320	* Search for the old block of memory on the
321	* free list. First, check the most common
322	* case (last element free'd), then (this failing)
323	* the last ``realloc_srchlen'' items free'd.
324	* If all lookups fail, then assume the size of
325	* the memory block being realloc'd is the
326	* largest possible (so that all "nbytes" of new
327	* memory are copied into). Note that this could cause
328	* a memory fault if the old area was tiny, and the moon
329	* is gibbous. However, that is very unlikely.
330	*/
331	if ((i = findbucket(op, 1)) < 0 &&
332	(i = findbucket(op, realloc_srchlen)) < 0)
333	i = NBUCKETS;
334	}
335	onb = 1 << (i + 3);
336	if (onb < pagesz)
337	onb -= sizeof (*op) + RSLOP;
338	else
339	onb += pagesz - sizeof (*op) - RSLOP;
340	/* avoid the copy if same size block */
341	if (was_alloced) {
342	if (i) {
343	i = 1 << (i + 2);
344	if (i < pagesz)
345	i -= sizeof (*op) + RSLOP;
346	else
347	i += pagesz - sizeof (*op) - RSLOP;
348	}
349	if (nbytes <= onb && nbytes > i) {
350	#ifdef RCHECK
351	op->ov_size = (nbytes + RSLOP - 1) & ~(RSLOP - 1);
352	(u_short )((caddr_t)(op + 1) + op->ov_size) = RMAGIC;
353	#endif
354	return(cp);
355	} else
356	free(cp);
357	}
358	if ((res = malloc(nbytes)) == NULL)
359	return (NULL);
360	if (cp != res) /* common optimization if "compacting" */
361	bcopy(cp, res, (nbytes < onb) ? nbytes : onb);
362	return (res);
363	}
364
365	/*
366	* Search ``srchlen'' elements of each free list for a block whose
367	* header starts at ``freep''. If srchlen is -1 search the whole list.
368	* Return bucket number, or -1 if not found.
369	*/
370	static
371	findbucket(freep, srchlen)
372	union overhead *freep;
373	int srchlen;
374	{
375	register union overhead *p;
376	register int i, j;
377
378	for (i = 0; i < NBUCKETS; i++) {
379	j = 0;
380	for (p = nextf[i]; p && j != srchlen; p = p->ov_next) {
381	if (p == freep)
382	return (i);
383	j++;
384	}
385	}
386	return (-1);
387	}
388
389	#ifdef MSTATS
390	/*
391	* mstats - print out statistics about malloc
392	*
393	* Prints two lines of numbers, one showing the length of the free list
394	* for each size category, the second showing the number of mallocs -
395	* frees for each size category.
396	*/
397	mstats(s)
398	char *s;
399	{
400	register int i, j;
401	register union overhead *p;
402	int totfree = 0,
403	totused = 0;
404
405	fprintf(stderr, "Memory allocation statistics %s\nfree:\t", s);
406	for (i = 0; i < NBUCKETS; i++) {
407	for (j = 0, p = nextf[i]; p; p = p->ov_next, j++)
408	;
409	fprintf(stderr, " %d", j);
410	totfree += j * (1 << (i + 3));
411	}
412	fprintf(stderr, "\nused:\t");
413	for (i = 0; i < NBUCKETS; i++) {
414	fprintf(stderr, " %d", nmalloc[i]);
415	totused += nmalloc[i] * (1 << (i + 3));
416	}
417	fprintf(stderr, "\n\tTotal in use: %d, total free: %d\n",
418	totused, totfree);
419	}
420	#endif