[perl5.git] / malloc.c

/* $Header: malloc.c,v 3.0.1.1 89/10/26 23:15:05 lwall Locked $
 *
 * $Log:	malloc.c,v $
 * Revision 3.0.1.1  89/10/26  23:15:05  lwall
 * patch1: some declarations were missing from malloc.c
 * patch1: sparc machines had alignment problems in malloc.c
 * 
 * Revision 3.0  89/10/18  15:20:39  lwall
 * 3.0 baseline
 * 
 */

#ifndef lint
static char sccsid[] = "@(#)malloc.c	4.3 (Berkeley) 9/16/83";

#ifdef DEBUGGING
#define RCHECK
#endif
/*
 * 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-12) bytes long.
 * This is designed for use in a program that uses vast quantities of memory,
 * but bombs when it runs out. 
 */

#include "EXTERN.h"
#include "perl.h"

static findbucket(), morecore();

/* I don't much care whether these are defined in sys/types.h--LAW */

#define u_char unsigned char
#define u_int unsigned int
#define u_short unsigned short

/*
 * 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 and the size of the block fits
 * in two bytes, then the top two bytes hold the size of the requested block
 * plus the range checking words, and the header word MINUS ONE.
 */
union	overhead {
	union	overhead *ov_next;	/* when free */
#if defined (mips) || defined (sparc)
	double  strut;			/* alignment problems */
#endif
	struct {
		u_char	ovu_magic;	/* magic number */
		u_char	ovu_index;	/* bucket # */
#ifdef RCHECK
		u_short	ovu_size;	/* actual block size */
		u_int	ovu_rmagic;	/* range magic number */
#endif
	} ovu;
#define	ov_magic	ovu.ovu_magic
#define	ov_index	ovu.ovu_index
#define	ov_size		ovu.ovu_size
#define	ov_rmagic	ovu.ovu_rmagic
};

#define	MAGIC		0xff		/* magic # on accounting info */
#define OLDMAGIC	0x7f		/* same after a free() */
#define RMAGIC		0x55555555	/* magic # on range info */
#ifdef RCHECK
#define	RSLOP		sizeof (u_int)
#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();

#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

#ifdef debug
#define	ASSERT(p)   if (!(p)) botch("p"); else
static
botch(s)
	char *s;
{

	printf("assertion botched: %s\n", s);
	abort();
}
#else
#define	ASSERT(p)
#endif

char *
malloc(nbytes)
	register unsigned nbytes;
{
  	register union overhead *p;
  	register int bucket = 0;
  	register unsigned shiftr;

	/*
	 * Convert amount of memory requested into
	 * closest block size stored in hash buckets
	 * which satisfies request.  Account for
	 * space used per block for accounting.
	 */
  	nbytes += sizeof (union overhead) + RSLOP;
  	nbytes = (nbytes + 3) &~ 3; 
  	shiftr = (nbytes - 1) >> 2;
	/* apart from this loop, this is O(1) */
  	while (shiftr >>= 1)
  		bucket++;
	/*
	 * If nothing in hash bucket right now,
	 * request more memory from the system.
	 */
  	if (nextf[bucket] == NULL)    
  		morecore(bucket);
  	if ((p = (union overhead *)nextf[bucket]) == NULL)
  		return (NULL);
	/* remove from linked list */
	if (*((int*)p) > 0x10000000)
#ifndef I286
	    fprintf(stderr,"Corrupt malloc ptr 0x%x at 0x%x\n",*((int*)p),p);
#else
	    fprintf(stderr,"Corrupt malloc ptr 0x%lx at 0x%lx\n",*((int*)p),p);
#endif
  	nextf[bucket] = nextf[bucket]->ov_next;
	p->ov_magic = MAGIC;
	p->ov_index= bucket;
#ifdef MSTATS
  	nmalloc[bucket]++;
#endif
#ifdef RCHECK
	/*
	 * Record allocated size of block and
	 * bound space with magic numbers.
	 */
  	if (nbytes <= 0x10000)
		p->ov_size = nbytes - 1;
	p->ov_rmagic = RMAGIC;
  	*((u_int *)((caddr_t)p + nbytes - RSLOP)) = RMAGIC;
#endif
  	return ((char *)(p + 1));
}

/*
 * Allocate more memory to the indicated bucket.
 */
static
morecore(bucket)
	register int bucket;
{
  	register union overhead *op;
  	register int rnu;       /* 2^rnu bytes will be requested */
  	register int nblks;     /* become nblks blocks of the desired size */
	register int siz;

  	if (nextf[bucket])
  		return;
	/*
	 * Insure memory is allocated
	 * on a page boundary.  Should
	 * make getpageize call?
	 */
  	op = (union overhead *)sbrk(0);
#ifndef I286
  	if ((int)op & 0x3ff)
  		(void)sbrk(1024 - ((int)op & 0x3ff));
#else
	/* The sbrk(0) call on the I286 always returns the next segment */
#endif

#ifndef I286
	/* take 2k unless the block is bigger than that */
  	rnu = (bucket <= 8) ? 11 : bucket + 3;
#else
	/* take 16k unless the block is bigger than that 
	   (80286s like large segments!)		*/
  	rnu = (bucket <= 11) ? 14 : bucket + 3;
#endif
  	nblks = 1 << (rnu - (bucket + 3));  /* how many blocks to get */
  	if (rnu < bucket)
		rnu = bucket;
	op = (union overhead *)sbrk(1 << rnu);
	/* no more room! */
  	if ((int)op == -1)
  		return;
	/*
	 * Round up to minimum allocation size boundary
	 * and deduct from block count to reflect.
	 */
#ifndef I286
  	if ((int)op & 7) {
  		op = (union overhead *)(((int)op + 8) &~ 7);
  		nblks--;
  	}
#else
	/* Again, this should always be ok on an 80286 */
#endif
	/*
	 * Add new memory allocated to that on
	 * free list for this hash bucket.
	 */
  	nextf[bucket] = op;
  	siz = 1 << (bucket + 3);
  	while (--nblks > 0) {
		op->ov_next = (union overhead *)((caddr_t)op + siz);
		op = (union overhead *)((caddr_t)op + siz);
  	}
}

free(cp)
	char *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) {
		warn("%s free() ignored",
		    op->ov_magic == OLDMAGIC ? "Duplicate" : "Bad");
		return;				/* sanity */
	}
	op->ov_magic = OLDMAGIC;
#endif
#ifdef RCHECK
  	ASSERT(op->ov_rmagic == RMAGIC);
	if (op->ov_index <= 13)
		ASSERT(*(u_int *)((caddr_t)op + op->ov_size + 1 - RSLOP) == RMAGIC);
#endif
  	ASSERT(op->ov_index < NBUCKETS);
  	size = op->ov_index;
	op->ov_next = nextf[size];
  	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
 * ``reall_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 reall_srchlen = 4;	/* 4 should be plenty, -1 =>'s whole list */

char *
realloc(cp, nbytes)
	char *cp; 
	unsigned nbytes;
{   
  	register u_int onb;
	union overhead *op;
  	char *res;
	register int i;
	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 ``reall_srchlen'' items free'd.
		 * If all lookups fail, then assume the size of
		 * the memory block being realloc'd is the
		 * smallest possible.
		 */
		if ((i = findbucket(op, 1)) < 0 &&
		    (i = findbucket(op, reall_srchlen)) < 0)
			i = 0;
	}
	onb = (1 << (i + 3)) - sizeof (*op) - RSLOP;
	/* avoid the copy if same size block */
	if (was_alloced &&
	    nbytes <= onb && nbytes > (onb >> 1) - sizeof(*op) - RSLOP) {
#ifdef RCHECK
		/*
		 * Record new allocated size of block and
		 * bound space with magic numbers.
		 */
		if (op->ov_index <= 13) {
			/*
			 * Convert amount of memory requested into
			 * closest block size stored in hash buckets
			 * which satisfies request.  Account for
			 * space used per block for accounting.
			 */
			nbytes += sizeof (union overhead) + RSLOP;
			nbytes = (nbytes + 3) &~ 3; 
			op->ov_size = nbytes - 1;
			*((u_int *)((caddr_t)op + nbytes - RSLOP)) = RMAGIC;
		}
#endif
		return(cp);
	}
  	if ((res = malloc(nbytes)) == NULL)
  		return (NULL);
  	if (cp != res)			/* common optimization */
		(void)bcopy(cp, res, (int)((nbytes < onb) ? nbytes : onb));
  	if (was_alloced)
		free(cp);
  	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
#endif /* lint */
Commit	Line	Data
03a14243	1	/* $Header: malloc.c,v 3.0.1.1 89/10/26 23:15:05 lwall Locked $
8d063cd8 LW	2	*
8d063cd8 LW	3	* $Log: malloc.c,v $
03a14243 LW	4	* Revision 3.0.1.1 89/10/26 23:15:05 lwall
	5	* patch1: some declarations were missing from malloc.c
	6	* patch1: sparc machines had alignment problems in malloc.c
	7	*
a687059c LW	8	* Revision 3.0 89/10/18 15:20:39 lwall
a687059c LW	9	* 3.0 baseline
8d063cd8 LW	10	*
	11	*/
	12
	13	#ifndef lint
	14	static char sccsid[] = "@(#)malloc.c 4.3 (Berkeley) 9/16/83";
8d063cd8	15
a687059c	16	#ifdef DEBUGGING
8d063cd8	17	#define RCHECK
a687059c	18	#endif
8d063cd8 LW	19	/*
	20	* malloc.c (Caltech) 2/21/82
	21	* Chris Kingsley, kingsley@cit-20.
	22	*
	23	* This is a very fast storage allocator. It allocates blocks of a small
	24	* number of different sizes, and keeps free lists of each size. Blocks that
	25	* don't exactly fit are passed up to the next larger size. In this
	26	* implementation, the available sizes are 2^n-4 (or 2^n-12) bytes long.
	27	* This is designed for use in a program that uses vast quantities of memory,
	28	* but bombs when it runs out.
	29	*/
	30
135863df	31	#include "EXTERN.h"
135863df AB	32	#include "perl.h"
135863df AB	33
03a14243 LW	34	static findbucket(), morecore();
03a14243 LW	35
135863df AB	36	/* I don't much care whether these are defined in sys/types.h--LAW */
	37
	38	#define u_char unsigned char
	39	#define u_int unsigned int
	40	#define u_short unsigned short
8d063cd8	41
8d063cd8 LW	42	/*
	43	* The overhead on a block is at least 4 bytes. When free, this space
	44	* contains a pointer to the next free block, and the bottom two bits must
	45	* be zero. When in use, the first byte is set to MAGIC, and the second
	46	* byte is the size index. The remaining bytes are for alignment.
	47	* If range checking is enabled and the size of the block fits
	48	* in two bytes, then the top two bytes hold the size of the requested block
	49	* plus the range checking words, and the header word MINUS ONE.
	50	*/
	51	union overhead {
	52	union overhead ov_next; / when free */
03a14243	53	#if defined (mips) \|\| defined (sparc)
a687059c LW	54	double strut; /* alignment problems */
a687059c LW	55	#endif
8d063cd8 LW	56	struct {
	57	u_char ovu_magic; /* magic number */
	58	u_char ovu_index; /* bucket # */
	59	#ifdef RCHECK
	60	u_short ovu_size; /* actual block size */
	61	u_int ovu_rmagic; /* range magic number */
	62	#endif
	63	} ovu;
	64	#define ov_magic ovu.ovu_magic
	65	#define ov_index ovu.ovu_index
	66	#define ov_size ovu.ovu_size
	67	#define ov_rmagic ovu.ovu_rmagic
	68	};
	69
	70	#define MAGIC 0xff /* magic # on accounting info */
378cc40b	71	#define OLDMAGIC 0x7f /* same after a free() */
8d063cd8 LW	72	#define RMAGIC 0x55555555 /* magic # on range info */
	73	#ifdef RCHECK
	74	#define RSLOP sizeof (u_int)
	75	#else
	76	#define RSLOP 0
	77	#endif
	78
	79	/*
	80	* nextf[i] is the pointer to the next free block of size 2^(i+3). The
	81	* smallest allocatable block is 8 bytes. The overhead information
	82	* precedes the data area returned to the user.
	83	*/
	84	#define NBUCKETS 30
	85	static union overhead *nextf[NBUCKETS];
	86	extern char *sbrk();
	87
	88	#ifdef MSTATS
	89	/*
	90	* nmalloc[i] is the difference between the number of mallocs and frees
	91	* for a given block size.
	92	*/
	93	static u_int nmalloc[NBUCKETS];
	94	#include <stdio.h>
	95	#endif
	96
	97	#ifdef debug
	98	#define ASSERT(p) if (!(p)) botch("p"); else
	99	static
	100	botch(s)
	101	char *s;
	102	{
	103
	104	printf("assertion botched: %s\n", s);
	105	abort();
	106	}
	107	#else
	108	#define ASSERT(p)
	109	#endif
	110
	111	char *
	112	malloc(nbytes)
	113	register unsigned nbytes;
	114	{
	115	register union overhead *p;
	116	register int bucket = 0;
	117	register unsigned shiftr;
	118
	119	/*
	120	* Convert amount of memory requested into
	121	* closest block size stored in hash buckets
	122	* which satisfies request. Account for
	123	* space used per block for accounting.
	124	*/
	125	nbytes += sizeof (union overhead) + RSLOP;
	126	nbytes = (nbytes + 3) &~ 3;
	127	shiftr = (nbytes - 1) >> 2;
	128	/* apart from this loop, this is O(1) */
	129	while (shiftr >>= 1)
	130	bucket++;
	131	/*
	132	* If nothing in hash bucket right now,
	133	* request more memory from the system.
	134	*/
	135	if (nextf[bucket] == NULL)
136	morecore(bucket);
137	if ((p = (union overhead *)nextf[bucket]) == NULL)
138	return (NULL);
139	/* remove from linked list */
140	if (((int)p) > 0x10000000)
a687059c	141	#ifndef I286
8d063cd8	142	fprintf(stderr,"Corrupt malloc ptr 0x%x at 0x%x\n",((int)p),p);
a687059c LW	143	#else
	144	fprintf(stderr,"Corrupt malloc ptr 0x%lx at 0x%lx\n",((int)p),p);
	145	#endif
8d063cd8 LW	146	nextf[bucket] = nextf[bucket]->ov_next;
	147	p->ov_magic = MAGIC;
	148	p->ov_index= bucket;
	149	#ifdef MSTATS
	150	nmalloc[bucket]++;
	151	#endif
	152	#ifdef RCHECK
	153	/*
	154	* Record allocated size of block and
	155	* bound space with magic numbers.
	156	*/
	157	if (nbytes <= 0x10000)
	158	p->ov_size = nbytes - 1;
	159	p->ov_rmagic = RMAGIC;
	160	((u_int )((caddr_t)p + nbytes - RSLOP)) = RMAGIC;
	161	#endif
	162	return ((char *)(p + 1));
	163	}
	164
	165	/*
	166	* Allocate more memory to the indicated bucket.
	167	*/
	168	static
	169	morecore(bucket)
a687059c	170	register int bucket;
8d063cd8 LW	171	{
	172	register union overhead *op;
	173	register int rnu; /* 2^rnu bytes will be requested */
	174	register int nblks; /* become nblks blocks of the desired size */
	175	register int siz;
	176
	177	if (nextf[bucket])
	178	return;
	179	/*
	180	* Insure memory is allocated
	181	* on a page boundary. Should
	182	* make getpageize call?
	183	*/
	184	op = (union overhead *)sbrk(0);
a687059c	185	#ifndef I286
8d063cd8	186	if ((int)op & 0x3ff)
a687059c LW	187	(void)sbrk(1024 - ((int)op & 0x3ff));
	188	#else
	189	/* The sbrk(0) call on the I286 always returns the next segment */
	190	#endif
	191
	192	#ifndef I286
8d063cd8 LW	193	/* take 2k unless the block is bigger than that */
8d063cd8 LW	194	rnu = (bucket <= 8) ? 11 : bucket + 3;
a687059c LW	195	#else
	196	/* take 16k unless the block is bigger than that
	197	(80286s like large segments!) */
	198	rnu = (bucket <= 11) ? 14 : bucket + 3;
	199	#endif
8d063cd8 LW	200	nblks = 1 << (rnu - (bucket + 3)); /* how many blocks to get */
	201	if (rnu < bucket)
	202	rnu = bucket;
	203	op = (union overhead *)sbrk(1 << rnu);
	204	/* no more room! */
	205	if ((int)op == -1)
	206	return;
	207	/*
	208	* Round up to minimum allocation size boundary
	209	* and deduct from block count to reflect.
	210	*/
a687059c	211	#ifndef I286
8d063cd8 LW	212	if ((int)op & 7) {
	213	op = (union overhead *)(((int)op + 8) &~ 7);
	214	nblks--;
	215	}
a687059c LW	216	#else
	217	/* Again, this should always be ok on an 80286 */
	218	#endif
8d063cd8 LW	219	/*
	220	* Add new memory allocated to that on
	221	* free list for this hash bucket.
	222	*/
	223	nextf[bucket] = op;
	224	siz = 1 << (bucket + 3);
	225	while (--nblks > 0) {
	226	op->ov_next = (union overhead *)((caddr_t)op + siz);
	227	op = (union overhead *)((caddr_t)op + siz);
	228	}
	229	}
	230
	231	free(cp)
	232	char *cp;
	233	{
	234	register int size;
	235	register union overhead *op;
	236
	237	if (cp == NULL)
	238	return;
	239	op = (union overhead *)((caddr_t)cp - sizeof (union overhead));
	240	#ifdef debug
	241	ASSERT(op->ov_magic == MAGIC); /* make sure it was in use */
	242	#else
378cc40b	243	if (op->ov_magic != MAGIC) {
a687059c	244	warn("%s free() ignored",
378cc40b	245	op->ov_magic == OLDMAGIC ? "Duplicate" : "Bad");
8d063cd8	246	return; /* sanity */
378cc40b LW	247	}
378cc40b LW	248	op->ov_magic = OLDMAGIC;
8d063cd8 LW	249	#endif
	250	#ifdef RCHECK
	251	ASSERT(op->ov_rmagic == RMAGIC);
	252	if (op->ov_index <= 13)
	253	ASSERT((u_int )((caddr_t)op + op->ov_size + 1 - RSLOP) == RMAGIC);
	254	#endif
	255	ASSERT(op->ov_index < NBUCKETS);
	256	size = op->ov_index;
	257	op->ov_next = nextf[size];
	258	nextf[size] = op;
	259	#ifdef MSTATS
	260	nmalloc[size]--;
	261	#endif
	262	}
	263
	264	/*
	265	* When a program attempts "storage compaction" as mentioned in the
	266	* old malloc man page, it realloc's an already freed block. Usually
	267	* this is the last block it freed; occasionally it might be farther
	268	* back. We have to search all the free lists for the block in order
	269	* to determine its bucket: 1st we make one pass thru the lists
	270	* checking only the first block in each; if that fails we search
378cc40b	271	* ``reall_srchlen'' blocks in each list for a match (the variable
8d063cd8 LW	272	* is extern so the caller can modify it). If that fails we just copy
	273	* however many bytes was given to realloc() and hope it's not huge.
	274	*/
378cc40b	275	int reall_srchlen = 4; /* 4 should be plenty, -1 =>'s whole list */
8d063cd8 LW	276
	277	char *
	278	realloc(cp, nbytes)
	279	char *cp;
	280	unsigned nbytes;
	281	{
	282	register u_int onb;
	283	union overhead *op;
	284	char *res;
	285	register int i;
	286	int was_alloced = 0;
	287
	288	if (cp == NULL)
	289	return (malloc(nbytes));
	290	op = (union overhead *)((caddr_t)cp - sizeof (union overhead));
	291	if (op->ov_magic == MAGIC) {
	292	was_alloced++;
	293	i = op->ov_index;
	294	} else {
	295	/*
	296	* Already free, doing "compaction".
	297	*
	298	* Search for the old block of memory on the
	299	* free list. First, check the most common
	300	* case (last element free'd), then (this failing)
378cc40b	301	* the last ``reall_srchlen'' items free'd.
8d063cd8 LW	302	* If all lookups fail, then assume the size of
	303	* the memory block being realloc'd is the
	304	* smallest possible.
	305	*/
	306	if ((i = findbucket(op, 1)) < 0 &&
378cc40b	307	(i = findbucket(op, reall_srchlen)) < 0)
8d063cd8 LW	308	i = 0;
	309	}
	310	onb = (1 << (i + 3)) - sizeof (*op) - RSLOP;
	311	/* avoid the copy if same size block */
	312	if (was_alloced &&
a687059c LW	313	nbytes <= onb && nbytes > (onb >> 1) - sizeof(*op) - RSLOP) {
	314	#ifdef RCHECK
	315	/*
	316	* Record new allocated size of block and
	317	* bound space with magic numbers.
	318	*/
	319	if (op->ov_index <= 13) {
	320	/*
	321	* Convert amount of memory requested into
	322	* closest block size stored in hash buckets
	323	* which satisfies request. Account for
	324	* space used per block for accounting.
	325	*/
	326	nbytes += sizeof (union overhead) + RSLOP;
	327	nbytes = (nbytes + 3) &~ 3;
	328	op->ov_size = nbytes - 1;
	329	((u_int )((caddr_t)op + nbytes - RSLOP)) = RMAGIC;
	330	}
	331	#endif
8d063cd8	332	return(cp);
a687059c	333	}
8d063cd8 LW	334	if ((res = malloc(nbytes)) == NULL)
	335	return (NULL);
	336	if (cp != res) /* common optimization */
a687059c	337	(void)bcopy(cp, res, (int)((nbytes < onb) ? nbytes : onb));
8d063cd8 LW	338	if (was_alloced)
	339	free(cp);
	340	return (res);
	341	}
	342
	343	/*
	344	* Search ``srchlen'' elements of each free list for a block whose
	345	* header starts at ``freep''. If srchlen is -1 search the whole list.
	346	* Return bucket number, or -1 if not found.
	347	*/
	348	static
	349	findbucket(freep, srchlen)
	350	union overhead *freep;
	351	int srchlen;
	352	{
	353	register union overhead *p;
	354	register int i, j;
	355
	356	for (i = 0; i < NBUCKETS; i++) {
	357	j = 0;
	358	for (p = nextf[i]; p && j != srchlen; p = p->ov_next) {
	359	if (p == freep)
	360	return (i);
	361	j++;
	362	}
	363	}
	364	return (-1);
	365	}
	366
	367	#ifdef MSTATS
	368	/*
	369	* mstats - print out statistics about malloc
	370	*
	371	* Prints two lines of numbers, one showing the length of the free list
	372	* for each size category, the second showing the number of mallocs -
	373	* frees for each size category.
	374	*/
	375	mstats(s)
	376	char *s;
	377	{
	378	register int i, j;
	379	register union overhead *p;
	380	int totfree = 0,
	381	totused = 0;
	382
	383	fprintf(stderr, "Memory allocation statistics %s\nfree:\t", s);
	384	for (i = 0; i < NBUCKETS; i++) {
	385	for (j = 0, p = nextf[i]; p; p = p->ov_next, j++)
	386	;
	387	fprintf(stderr, " %d", j);
	388	totfree += j * (1 << (i + 3));
	389	}
	390	fprintf(stderr, "\nused:\t");
	391	for (i = 0; i < NBUCKETS; i++) {
	392	fprintf(stderr, " %d", nmalloc[i]);
	393	totused += nmalloc[i] * (1 << (i + 3));
	394	}
	395	fprintf(stderr, "\n\tTotal in use: %d, total free: %d\n",
	396	totused, totfree);
	397	}
	398	#endif
a687059c	399	#endif /* lint */