xref: /csrg-svn/lib/libc/stdlib/malloc.c (revision 35329)
121347Sdist /*
225177Smckusick  * Copyright (c) 1983 Regents of the University of California.
3*35329Sbostic  * All rights reserved.
4*35329Sbostic  *
5*35329Sbostic  * Redistribution and use in source and binary forms are permitted
6*35329Sbostic  * provided that the above copyright notice and this paragraph are
7*35329Sbostic  * duplicated in all such forms and that any documentation,
8*35329Sbostic  * advertising materials, and other materials related to such
9*35329Sbostic  * distribution and use acknowledge that the software was developed
10*35329Sbostic  * by the University of California, Berkeley.  The name of the
11*35329Sbostic  * University may not be used to endorse or promote products derived
12*35329Sbostic  * from this software without specific prior written permission.
13*35329Sbostic  * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR
14*35329Sbostic  * IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED
15*35329Sbostic  * WARRANTIES OF MERCHANTIBILITY AND FITNESS FOR A PARTICULAR PURPOSE.
1621347Sdist  */
1721347Sdist 
1826569Sdonn #if defined(LIBC_SCCS) && !defined(lint)
19*35329Sbostic static char sccsid[] = "@(#)malloc.c	5.7 (Berkeley) 08/04/88";
20*35329Sbostic #endif /* LIBC_SCCS and not lint */
2114953Skarels 
2214953Skarels /*
2314953Skarels  * malloc.c (Caltech) 2/21/82
2414953Skarels  * Chris Kingsley, kingsley@cit-20.
2514953Skarels  *
2614953Skarels  * This is a very fast storage allocator.  It allocates blocks of a small
2714953Skarels  * number of different sizes, and keeps free lists of each size.  Blocks that
2814953Skarels  * don't exactly fit are passed up to the next larger size.  In this
2926410Slepreau  * implementation, the available sizes are 2^n-4 (or 2^n-10) bytes long.
3026410Slepreau  * This is designed for use in a virtual memory environment.
3114953Skarels  */
3214953Skarels 
3314953Skarels #include <sys/types.h>
3414953Skarels 
3514953Skarels #define	NULL 0
3614953Skarels 
3714953Skarels /*
3814953Skarels  * The overhead on a block is at least 4 bytes.  When free, this space
3914953Skarels  * contains a pointer to the next free block, and the bottom two bits must
4014953Skarels  * be zero.  When in use, the first byte is set to MAGIC, and the second
4114953Skarels  * byte is the size index.  The remaining bytes are for alignment.
4226410Slepreau  * If range checking is enabled then a second word holds the size of the
4326410Slepreau  * requested block, less 1, rounded up to a multiple of sizeof(RMAGIC).
4426410Slepreau  * The order of elements is critical: ov_magic must overlay the low order
4526410Slepreau  * bits of ov_next, and ov_magic can not be a valid ov_next bit pattern.
4614953Skarels  */
4714953Skarels union	overhead {
4814953Skarels 	union	overhead *ov_next;	/* when free */
4914953Skarels 	struct {
5014953Skarels 		u_char	ovu_magic;	/* magic number */
5114953Skarels 		u_char	ovu_index;	/* bucket # */
5226410Slepreau #ifdef RCHECK
5326410Slepreau 		u_short	ovu_rmagic;	/* range magic number */
5417333Sralph 		u_int	ovu_size;	/* actual block size */
5514953Skarels #endif
5614953Skarels 	} ovu;
5714953Skarels #define	ov_magic	ovu.ovu_magic
5814953Skarels #define	ov_index	ovu.ovu_index
5917333Sralph #define	ov_rmagic	ovu.ovu_rmagic
6014953Skarels #define	ov_size		ovu.ovu_size
6114953Skarels };
6214953Skarels 
6317333Sralph #define	MAGIC		0xef		/* magic # on accounting info */
6417333Sralph #define RMAGIC		0x5555		/* magic # on range info */
6517333Sralph 
6614953Skarels #ifdef RCHECK
6717333Sralph #define	RSLOP		sizeof (u_short)
6814953Skarels #else
6914953Skarels #define	RSLOP		0
7014953Skarels #endif
7114953Skarels 
7214953Skarels /*
7314953Skarels  * nextf[i] is the pointer to the next free block of size 2^(i+3).  The
7414953Skarels  * smallest allocatable block is 8 bytes.  The overhead information
7514953Skarels  * precedes the data area returned to the user.
7614953Skarels  */
7714953Skarels #define	NBUCKETS 30
7814953Skarels static	union overhead *nextf[NBUCKETS];
7914953Skarels extern	char *sbrk();
8014953Skarels 
8117333Sralph static	int pagesz;			/* page size */
8217333Sralph static	int pagebucket;			/* page size bucket */
8317333Sralph 
8414953Skarels #ifdef MSTATS
8514953Skarels /*
8614953Skarels  * nmalloc[i] is the difference between the number of mallocs and frees
8714953Skarels  * for a given block size.
8814953Skarels  */
8914953Skarels static	u_int nmalloc[NBUCKETS];
9014953Skarels #include <stdio.h>
9114953Skarels #endif
9214953Skarels 
9325799Slepreau #if defined(DEBUG) || defined(RCHECK)
9417333Sralph #define	ASSERT(p)   if (!(p)) botch("p")
9525799Slepreau #include <stdio.h>
9614953Skarels static
9713259Sroot botch(s)
9815003Ssam 	char *s;
9913259Sroot {
10025799Slepreau 	fprintf(stderr, "\r\nassertion botched: %s\r\n", s);
10125799Slepreau  	(void) fflush(stderr);		/* just in case user buffered it */
10213259Sroot 	abort();
10313259Sroot }
10413259Sroot #else
10514953Skarels #define	ASSERT(p)
10613259Sroot #endif
10713259Sroot 
10813259Sroot char *
10913259Sroot malloc(nbytes)
11017333Sralph 	unsigned nbytes;
11113259Sroot {
11217333Sralph   	register union overhead *op;
11317333Sralph   	register int bucket;
11417333Sralph 	register unsigned amt, n;
11513259Sroot 
11614953Skarels 	/*
11717333Sralph 	 * First time malloc is called, setup page size and
11817333Sralph 	 * align break pointer so all data will be page aligned.
11914953Skarels 	 */
12017333Sralph 	if (pagesz == 0) {
12117333Sralph 		pagesz = n = getpagesize();
12217333Sralph 		op = (union overhead *)sbrk(0);
12317333Sralph   		n = n - sizeof (*op) - ((int)op & (n - 1));
12417333Sralph 		if (n < 0)
12517333Sralph 			n += pagesz;
12617333Sralph   		if (n) {
12717333Sralph   			if (sbrk(n) == (char *)-1)
12817333Sralph 				return (NULL);
12917333Sralph 		}
13017333Sralph 		bucket = 0;
13117333Sralph 		amt = 8;
13217333Sralph 		while (pagesz > amt) {
13317333Sralph 			amt <<= 1;
13417333Sralph 			bucket++;
13517333Sralph 		}
13617333Sralph 		pagebucket = bucket;
13717333Sralph 	}
13814953Skarels 	/*
13917333Sralph 	 * Convert amount of memory requested into closest block size
14017333Sralph 	 * stored in hash buckets which satisfies request.
14117333Sralph 	 * Account for space used per block for accounting.
14217333Sralph 	 */
14317333Sralph 	if (nbytes <= (n = pagesz - sizeof (*op) - RSLOP)) {
14417333Sralph #ifndef RCHECK
14517333Sralph 		amt = 8;	/* size of first bucket */
14617333Sralph 		bucket = 0;
14717333Sralph #else
14817333Sralph 		amt = 16;	/* size of first bucket */
14917333Sralph 		bucket = 1;
15017333Sralph #endif
15117333Sralph 		n = -(sizeof (*op) + RSLOP);
15217333Sralph 	} else {
15317333Sralph 		amt = pagesz;
15417333Sralph 		bucket = pagebucket;
15517333Sralph 	}
15617333Sralph 	while (nbytes > amt + n) {
15717333Sralph 		amt <<= 1;
15825793Smckusick 		if (amt == 0)
15925793Smckusick 			return (NULL);
16017333Sralph 		bucket++;
16117333Sralph 	}
16217333Sralph 	/*
16314953Skarels 	 * If nothing in hash bucket right now,
16414953Skarels 	 * request more memory from the system.
16514953Skarels 	 */
16617333Sralph   	if ((op = nextf[bucket]) == NULL) {
16714953Skarels   		morecore(bucket);
16817333Sralph   		if ((op = nextf[bucket]) == NULL)
16917333Sralph   			return (NULL);
17017333Sralph 	}
17114953Skarels 	/* remove from linked list */
17217333Sralph   	nextf[bucket] = op->ov_next;
17317333Sralph 	op->ov_magic = MAGIC;
17417333Sralph 	op->ov_index = bucket;
17514953Skarels #ifdef MSTATS
17614953Skarels   	nmalloc[bucket]++;
17714953Skarels #endif
17814953Skarels #ifdef RCHECK
17914953Skarels 	/*
18014953Skarels 	 * Record allocated size of block and
18114953Skarels 	 * bound space with magic numbers.
18214953Skarels 	 */
18317438Sralph 	op->ov_size = (nbytes + RSLOP - 1) & ~(RSLOP - 1);
18417333Sralph 	op->ov_rmagic = RMAGIC;
18517438Sralph   	*(u_short *)((caddr_t)(op + 1) + op->ov_size) = RMAGIC;
18614953Skarels #endif
18717333Sralph   	return ((char *)(op + 1));
18813259Sroot }
18913259Sroot 
19014953Skarels /*
19114953Skarels  * Allocate more memory to the indicated bucket.
19214953Skarels  */
19314953Skarels morecore(bucket)
19417333Sralph 	int bucket;
19513259Sroot {
19614953Skarels   	register union overhead *op;
19717333Sralph 	register int sz;		/* size of desired block */
19825793Smckusick   	int amt;			/* amount to allocate */
19925793Smckusick   	int nblks;			/* how many blocks we get */
20013259Sroot 
20125793Smckusick 	/*
20225793Smckusick 	 * sbrk_size <= 0 only for big, FLUFFY, requests (about
20325793Smckusick 	 * 2^30 bytes on a VAX, I think) or for a negative arg.
20425793Smckusick 	 */
20517333Sralph 	sz = 1 << (bucket + 3);
20626410Slepreau #ifdef DEBUG
20726410Slepreau 	ASSERT(sz > 0);
20826410Slepreau #else
20925793Smckusick 	if (sz <= 0)
21025793Smckusick 		return;
21126410Slepreau #endif
21217333Sralph 	if (sz < pagesz) {
21317333Sralph 		amt = pagesz;
21417333Sralph   		nblks = amt / sz;
21517333Sralph 	} else {
21617333Sralph 		amt = sz + pagesz;
21717333Sralph 		nblks = 1;
21817333Sralph 	}
21917333Sralph 	op = (union overhead *)sbrk(amt);
22014953Skarels 	/* no more room! */
22114953Skarels   	if ((int)op == -1)
22214953Skarels   		return;
22314953Skarels 	/*
22414953Skarels 	 * Add new memory allocated to that on
22514953Skarels 	 * free list for this hash bucket.
22614953Skarels 	 */
22714953Skarels   	nextf[bucket] = op;
22814953Skarels   	while (--nblks > 0) {
22917333Sralph 		op->ov_next = (union overhead *)((caddr_t)op + sz);
23017333Sralph 		op = (union overhead *)((caddr_t)op + sz);
23114953Skarels   	}
23213259Sroot }
23313259Sroot 
23414953Skarels free(cp)
23514953Skarels 	char *cp;
23614953Skarels {
23714953Skarels   	register int size;
23814953Skarels 	register union overhead *op;
23913259Sroot 
24014953Skarels   	if (cp == NULL)
24114953Skarels   		return;
24214953Skarels 	op = (union overhead *)((caddr_t)cp - sizeof (union overhead));
24317333Sralph #ifdef DEBUG
24414953Skarels   	ASSERT(op->ov_magic == MAGIC);		/* make sure it was in use */
24514953Skarels #else
24614953Skarels 	if (op->ov_magic != MAGIC)
24714953Skarels 		return;				/* sanity */
24814953Skarels #endif
24914953Skarels #ifdef RCHECK
25014953Skarels   	ASSERT(op->ov_rmagic == RMAGIC);
25117333Sralph 	ASSERT(*(u_short *)((caddr_t)(op + 1) + op->ov_size) == RMAGIC);
25214953Skarels #endif
25314953Skarels   	size = op->ov_index;
25417333Sralph   	ASSERT(size < NBUCKETS);
25526410Slepreau 	op->ov_next = nextf[size];	/* also clobbers ov_magic */
25614953Skarels   	nextf[size] = op;
25714953Skarels #ifdef MSTATS
25814953Skarels   	nmalloc[size]--;
25914953Skarels #endif
26014953Skarels }
26114953Skarels 
26214953Skarels /*
26314953Skarels  * When a program attempts "storage compaction" as mentioned in the
26414953Skarels  * old malloc man page, it realloc's an already freed block.  Usually
26514953Skarels  * this is the last block it freed; occasionally it might be farther
26614953Skarels  * back.  We have to search all the free lists for the block in order
26714953Skarels  * to determine its bucket: 1st we make one pass thru the lists
26814953Skarels  * checking only the first block in each; if that fails we search
26914953Skarels  * ``realloc_srchlen'' blocks in each list for a match (the variable
27014953Skarels  * is extern so the caller can modify it).  If that fails we just copy
27114953Skarels  * however many bytes was given to realloc() and hope it's not huge.
27214953Skarels  */
27315003Ssam int realloc_srchlen = 4;	/* 4 should be plenty, -1 =>'s whole list */
27414953Skarels 
27513259Sroot char *
27614953Skarels realloc(cp, nbytes)
27714953Skarels 	char *cp;
27814953Skarels 	unsigned nbytes;
27914953Skarels {
28017333Sralph   	register u_int onb, i;
28114953Skarels 	union overhead *op;
28214953Skarels   	char *res;
28314953Skarels 	int was_alloced = 0;
28414953Skarels 
28514953Skarels   	if (cp == NULL)
28614953Skarels   		return (malloc(nbytes));
28714953Skarels 	op = (union overhead *)((caddr_t)cp - sizeof (union overhead));
28814953Skarels 	if (op->ov_magic == MAGIC) {
28914953Skarels 		was_alloced++;
29014953Skarels 		i = op->ov_index;
29115003Ssam 	} else {
29215003Ssam 		/*
29315003Ssam 		 * Already free, doing "compaction".
29415003Ssam 		 *
29515003Ssam 		 * Search for the old block of memory on the
29615003Ssam 		 * free list.  First, check the most common
29715003Ssam 		 * case (last element free'd), then (this failing)
29815003Ssam 		 * the last ``realloc_srchlen'' items free'd.
29915003Ssam 		 * If all lookups fail, then assume the size of
30015003Ssam 		 * the memory block being realloc'd is the
30125799Slepreau 		 * largest possible (so that all "nbytes" of new
30225799Slepreau 		 * memory are copied into).  Note that this could cause
30325799Slepreau 		 * a memory fault if the old area was tiny, and the moon
30425799Slepreau 		 * is gibbous.  However, that is very unlikely.
30515003Ssam 		 */
30614953Skarels 		if ((i = findbucket(op, 1)) < 0 &&
30714953Skarels 		    (i = findbucket(op, realloc_srchlen)) < 0)
30825799Slepreau 			i = NBUCKETS;
30914953Skarels 	}
31017333Sralph 	onb = 1 << (i + 3);
31117333Sralph 	if (onb < pagesz)
31217333Sralph 		onb -= sizeof (*op) + RSLOP;
31317333Sralph 	else
31417333Sralph 		onb += pagesz - sizeof (*op) - RSLOP;
31515003Ssam 	/* avoid the copy if same size block */
31617333Sralph 	if (was_alloced) {
31717333Sralph 		if (i) {
31817333Sralph 			i = 1 << (i + 2);
31917333Sralph 			if (i < pagesz)
32017333Sralph 				i -= sizeof (*op) + RSLOP;
32117333Sralph 			else
32217333Sralph 				i += pagesz - sizeof (*op) - RSLOP;
32317333Sralph 		}
32417333Sralph 		if (nbytes <= onb && nbytes > i) {
32517332Sralph #ifdef RCHECK
32617438Sralph 			op->ov_size = (nbytes + RSLOP - 1) & ~(RSLOP - 1);
32717333Sralph 			*(u_short *)((caddr_t)(op + 1) + op->ov_size) = RMAGIC;
32817332Sralph #endif
32917333Sralph 			return(cp);
33017333Sralph 		} else
33117333Sralph 			free(cp);
33217332Sralph 	}
33314953Skarels   	if ((res = malloc(nbytes)) == NULL)
33414953Skarels   		return (NULL);
33525799Slepreau   	if (cp != res)		/* common optimization if "compacting" */
33614953Skarels 		bcopy(cp, res, (nbytes < onb) ? nbytes : onb);
33714953Skarels   	return (res);
33814953Skarels }
33914953Skarels 
34014953Skarels /*
34114953Skarels  * Search ``srchlen'' elements of each free list for a block whose
34214953Skarels  * header starts at ``freep''.  If srchlen is -1 search the whole list.
34314953Skarels  * Return bucket number, or -1 if not found.
34414953Skarels  */
34514953Skarels static
34614953Skarels findbucket(freep, srchlen)
34715003Ssam 	union overhead *freep;
34815003Ssam 	int srchlen;
34913259Sroot {
35014953Skarels 	register union overhead *p;
35114953Skarels 	register int i, j;
35213259Sroot 
35315003Ssam 	for (i = 0; i < NBUCKETS; i++) {
35415003Ssam 		j = 0;
35515003Ssam 		for (p = nextf[i]; p && j != srchlen; p = p->ov_next) {
35614953Skarels 			if (p == freep)
35714953Skarels 				return (i);
35815003Ssam 			j++;
35915003Ssam 		}
36015003Ssam 	}
36114953Skarels 	return (-1);
36213259Sroot }
36313259Sroot 
36414953Skarels #ifdef MSTATS
36514953Skarels /*
36614953Skarels  * mstats - print out statistics about malloc
36714953Skarels  *
36814953Skarels  * Prints two lines of numbers, one showing the length of the free list
36914953Skarels  * for each size category, the second showing the number of mallocs -
37014953Skarels  * frees for each size category.
37114953Skarels  */
37214953Skarels mstats(s)
37314953Skarels 	char *s;
37413259Sroot {
37514953Skarels   	register int i, j;
37614953Skarels   	register union overhead *p;
37714953Skarels   	int totfree = 0,
37814953Skarels   	totused = 0;
37914953Skarels 
38014953Skarels   	fprintf(stderr, "Memory allocation statistics %s\nfree:\t", s);
38114953Skarels   	for (i = 0; i < NBUCKETS; i++) {
38214953Skarels   		for (j = 0, p = nextf[i]; p; p = p->ov_next, j++)
38314953Skarels   			;
38414953Skarels   		fprintf(stderr, " %d", j);
38514953Skarels   		totfree += j * (1 << (i + 3));
38614953Skarels   	}
38714953Skarels   	fprintf(stderr, "\nused:\t");
38814953Skarels   	for (i = 0; i < NBUCKETS; i++) {
38914953Skarels   		fprintf(stderr, " %d", nmalloc[i]);
39014953Skarels   		totused += nmalloc[i] * (1 << (i + 3));
39114953Skarels   	}
39215003Ssam   	fprintf(stderr, "\n\tTotal in use: %d, total free: %d\n",
39315003Ssam 	    totused, totfree);
39413259Sroot }
39513259Sroot #endif
396