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 = "from: @(#)malloc.c	5.11 (Berkeley) 2/23/91";*/
36static char *rcsid = "$FreeBSD$";
37#endif /* LIBC_SCCS and not lint */
38
39/*
40 * malloc.c (Caltech) 2/21/82
41 * Chris Kingsley, kingsley@cit-20.
42 *
43 * This is a very fast storage allocator.  It allocates blocks of a small
44 * number of different sizes, and keeps free lists of each size.  Blocks that
45 * don't exactly fit are passed up to the next larger size.  In this
46 * implementation, the available sizes are 2^n-4 (or 2^n-10) bytes long.
47 * This is designed for use in a virtual memory environment.
48 */
49
50#include <sys/types.h>
51#include <sys/sysctl.h>
52#include <paths.h>
53#include <stdarg.h>
54#include <stddef.h>
55#include <stdio.h>
56#include <stdlib.h>
57#include <string.h>
58#include <unistd.h>
59#include <sys/param.h>
60#include <sys/mman.h>
61#include "rtld_printf.h"
62
63static void morecore();
64static int findbucket();
65
66/*
67 * Pre-allocate mmap'ed pages
68 */
69#define	NPOOLPAGES	(32*1024/pagesz)
70static caddr_t		pagepool_start, pagepool_end;
71static int		morepages();
72
73/*
74 * The overhead on a block is at least 4 bytes.  When free, this space
75 * contains a pointer to the next free block, and the bottom two bits must
76 * be zero.  When in use, the first byte is set to MAGIC, and the second
77 * byte is the size index.  The remaining bytes are for alignment.
78 * If range checking is enabled then a second word holds the size of the
79 * requested block, less 1, rounded up to a multiple of sizeof(RMAGIC).
80 * The order of elements is critical: ov_magic must overlay the low order
81 * bits of ov_next, and ov_magic can not be a valid ov_next bit pattern.
82 */
83union	overhead {
84	union	overhead *ov_next;	/* when free */
85	struct {
86		u_char	ovu_magic;	/* magic number */
87		u_char	ovu_index;	/* bucket # */
88#ifdef RCHECK
89		u_short	ovu_rmagic;	/* range magic number */
90		u_int	ovu_size;	/* actual block size */
91#endif
92	} ovu;
93#define	ov_magic	ovu.ovu_magic
94#define	ov_index	ovu.ovu_index
95#define	ov_rmagic	ovu.ovu_rmagic
96#define	ov_size		ovu.ovu_size
97};
98
99#define	MAGIC		0xef		/* magic # on accounting info */
100#define RMAGIC		0x5555		/* magic # on range info */
101
102#ifdef RCHECK
103#define	RSLOP		sizeof (u_short)
104#else
105#define	RSLOP		0
106#endif
107
108/*
109 * nextf[i] is the pointer to the next free block of size 2^(i+3).  The
110 * smallest allocatable block is 8 bytes.  The overhead information
111 * precedes the data area returned to the user.
112 */
113#define	NBUCKETS 30
114static	union overhead *nextf[NBUCKETS];
115
116static	int pagesz;			/* page size */
117static	int pagebucket;			/* page size bucket */
118
119#ifdef MSTATS
120/*
121 * nmalloc[i] is the difference between the number of mallocs and frees
122 * for a given block size.
123 */
124static	u_int nmalloc[NBUCKETS];
125#include <stdio.h>
126#endif
127
128#if defined(MALLOC_DEBUG) || defined(RCHECK)
129#define	ASSERT(p)   if (!(p)) botch("p")
130#include <stdio.h>
131static void
132botch(s)
133	char *s;
134{
135	fprintf(stderr, "\r\nassertion botched: %s\r\n", s);
136 	(void) fflush(stderr);		/* just in case user buffered it */
137	abort();
138}
139#else
140#define	ASSERT(p)
141#endif
142
143/* Debugging stuff */
144#define TRACE()	rtld_printf("TRACE %s:%d\n", __FILE__, __LINE__)
145
146extern int pagesize;
147
148static int
149rtld_getpagesize(void)
150{
151	int mib[2];
152	size_t size;
153
154	if (pagesize != 0)
155		return (pagesize);
156
157	mib[0] = CTL_HW;
158	mib[1] = HW_PAGESIZE;
159	size = sizeof(pagesize);
160	if (sysctl(mib, 2, &pagesize, &size, NULL, 0) == -1)
161		return (-1);
162	return (pagesize);
163
164}
165
166void *
167malloc(nbytes)
168	size_t nbytes;
169{
170  	register union overhead *op;
171  	register int bucket;
172	register long n;
173	register unsigned amt;
174
175	/*
176	 * First time malloc is called, setup page size and
177	 * align break pointer so all data will be page aligned.
178	 */
179	if (pagesz == 0) {
180		pagesz = n = rtld_getpagesize();
181		if (morepages(NPOOLPAGES) == 0)
182			return NULL;
183		op = (union overhead *)(pagepool_start);
184  		n = n - sizeof (*op) - ((long)op & (n - 1));
185		if (n < 0)
186			n += pagesz;
187  		if (n) {
188			pagepool_start += n;
189		}
190		bucket = 0;
191		amt = 8;
192		while ((unsigned)pagesz > amt) {
193			amt <<= 1;
194			bucket++;
195		}
196		pagebucket = bucket;
197	}
198	/*
199	 * Convert amount of memory requested into closest block size
200	 * stored in hash buckets which satisfies request.
201	 * Account for space used per block for accounting.
202	 */
203	if (nbytes <= (unsigned long)(n = pagesz - sizeof (*op) - RSLOP)) {
204#ifndef RCHECK
205		amt = 8;	/* size of first bucket */
206		bucket = 0;
207#else
208		amt = 16;	/* size of first bucket */
209		bucket = 1;
210#endif
211		n = -(sizeof (*op) + RSLOP);
212	} else {
213		amt = pagesz;
214		bucket = pagebucket;
215	}
216	while (nbytes > amt + n) {
217		amt <<= 1;
218		if (amt == 0)
219			return (NULL);
220		bucket++;
221	}
222	/*
223	 * If nothing in hash bucket right now,
224	 * request more memory from the system.
225	 */
226  	if ((op = nextf[bucket]) == NULL) {
227  		morecore(bucket);
228  		if ((op = nextf[bucket]) == NULL)
229  			return (NULL);
230	}
231	/* remove from linked list */
232  	nextf[bucket] = op->ov_next;
233	op->ov_magic = MAGIC;
234	op->ov_index = bucket;
235#ifdef MSTATS
236  	nmalloc[bucket]++;
237#endif
238#ifdef RCHECK
239	/*
240	 * Record allocated size of block and
241	 * bound space with magic numbers.
242	 */
243	op->ov_size = (nbytes + RSLOP - 1) & ~(RSLOP - 1);
244	op->ov_rmagic = RMAGIC;
245  	*(u_short *)((caddr_t)(op + 1) + op->ov_size) = RMAGIC;
246#endif
247  	return ((char *)(op + 1));
248}
249
250void *
251calloc(size_t num, size_t size)
252{
253	void *ret;
254
255	if (size != 0 && (num * size) / size != num) {
256		/* size_t overflow. */
257		return (NULL);
258	}
259
260	if ((ret = malloc(num * size)) != NULL)
261		memset(ret, 0, num * size);
262
263	return (ret);
264}
265
266/*
267 * Allocate more memory to the indicated bucket.
268 */
269static void
270morecore(bucket)
271	int bucket;
272{
273  	register union overhead *op;
274	register int sz;		/* size of desired block */
275  	int amt;			/* amount to allocate */
276  	int nblks;			/* how many blocks we get */
277
278	/*
279	 * sbrk_size <= 0 only for big, FLUFFY, requests (about
280	 * 2^30 bytes on a VAX, I think) or for a negative arg.
281	 */
282	sz = 1 << (bucket + 3);
283#ifdef MALLOC_DEBUG
284	ASSERT(sz > 0);
285#else
286	if (sz <= 0)
287		return;
288#endif
289	if (sz < pagesz) {
290		amt = pagesz;
291  		nblks = amt / sz;
292	} else {
293		amt = sz + pagesz;
294		nblks = 1;
295	}
296	if (amt > pagepool_end - pagepool_start)
297		if (morepages(amt/pagesz + NPOOLPAGES) == 0)
298			return;
299	op = (union overhead *)pagepool_start;
300	pagepool_start += amt;
301
302	/*
303	 * Add new memory allocated to that on
304	 * free list for this hash bucket.
305	 */
306  	nextf[bucket] = op;
307  	while (--nblks > 0) {
308		op->ov_next = (union overhead *)((caddr_t)op + sz);
309		op = (union overhead *)((caddr_t)op + sz);
310  	}
311}
312
313void
314free(cp)
315	void *cp;
316{
317  	register int size;
318	register union overhead *op;
319
320  	if (cp == NULL)
321  		return;
322	op = (union overhead *)((caddr_t)cp - sizeof (union overhead));
323#ifdef MALLOC_DEBUG
324  	ASSERT(op->ov_magic == MAGIC);		/* make sure it was in use */
325#else
326	if (op->ov_magic != MAGIC)
327		return;				/* sanity */
328#endif
329#ifdef RCHECK
330  	ASSERT(op->ov_rmagic == RMAGIC);
331	ASSERT(*(u_short *)((caddr_t)(op + 1) + op->ov_size) == RMAGIC);
332#endif
333  	size = op->ov_index;
334  	ASSERT(size < NBUCKETS);
335	op->ov_next = nextf[size];	/* also clobbers ov_magic */
336  	nextf[size] = op;
337#ifdef MSTATS
338  	nmalloc[size]--;
339#endif
340}
341
342/*
343 * When a program attempts "storage compaction" as mentioned in the
344 * old malloc man page, it realloc's an already freed block.  Usually
345 * this is the last block it freed; occasionally it might be farther
346 * back.  We have to search all the free lists for the block in order
347 * to determine its bucket: 1st we make one pass thru the lists
348 * checking only the first block in each; if that fails we search
349 * ``realloc_srchlen'' blocks in each list for a match (the variable
350 * is extern so the caller can modify it).  If that fails we just copy
351 * however many bytes was given to realloc() and hope it's not huge.
352 */
353int realloc_srchlen = 4;	/* 4 should be plenty, -1 =>'s whole list */
354
355void *
356realloc(cp, nbytes)
357	void *cp;
358	size_t nbytes;
359{
360  	register u_int onb;
361	register int i;
362	union overhead *op;
363  	char *res;
364	int was_alloced = 0;
365
366  	if (cp == NULL)
367  		return (malloc(nbytes));
368	op = (union overhead *)((caddr_t)cp - sizeof (union overhead));
369	if (op->ov_magic == MAGIC) {
370		was_alloced++;
371		i = op->ov_index;
372	} else {
373		/*
374		 * Already free, doing "compaction".
375		 *
376		 * Search for the old block of memory on the
377		 * free list.  First, check the most common
378		 * case (last element free'd), then (this failing)
379		 * the last ``realloc_srchlen'' items free'd.
380		 * If all lookups fail, then assume the size of
381		 * the memory block being realloc'd is the
382		 * largest possible (so that all "nbytes" of new
383		 * memory are copied into).  Note that this could cause
384		 * a memory fault if the old area was tiny, and the moon
385		 * is gibbous.  However, that is very unlikely.
386		 */
387		if ((i = findbucket(op, 1)) < 0 &&
388		    (i = findbucket(op, realloc_srchlen)) < 0)
389			i = NBUCKETS;
390	}
391	onb = 1 << (i + 3);
392	if (onb < (u_int)pagesz)
393		onb -= sizeof (*op) + RSLOP;
394	else
395		onb += pagesz - sizeof (*op) - RSLOP;
396	/* avoid the copy if same size block */
397	if (was_alloced) {
398		if (i) {
399			i = 1 << (i + 2);
400			if (i < pagesz)
401				i -= sizeof (*op) + RSLOP;
402			else
403				i += pagesz - sizeof (*op) - RSLOP;
404		}
405		if (nbytes <= onb && nbytes > (size_t)i) {
406#ifdef RCHECK
407			op->ov_size = (nbytes + RSLOP - 1) & ~(RSLOP - 1);
408			*(u_short *)((caddr_t)(op + 1) + op->ov_size) = RMAGIC;
409#endif
410			return(cp);
411		} else
412			free(cp);
413	}
414  	if ((res = malloc(nbytes)) == NULL)
415  		return (NULL);
416  	if (cp != res)		/* common optimization if "compacting" */
417		bcopy(cp, res, (nbytes < onb) ? nbytes : onb);
418  	return (res);
419}
420
421/*
422 * Search ``srchlen'' elements of each free list for a block whose
423 * header starts at ``freep''.  If srchlen is -1 search the whole list.
424 * Return bucket number, or -1 if not found.
425 */
426static int
427findbucket(freep, srchlen)
428	union overhead *freep;
429	int srchlen;
430{
431	register union overhead *p;
432	register int i, j;
433
434	for (i = 0; i < NBUCKETS; i++) {
435		j = 0;
436		for (p = nextf[i]; p && j != srchlen; p = p->ov_next) {
437			if (p == freep)
438				return (i);
439			j++;
440		}
441	}
442	return (-1);
443}
444
445#ifdef MSTATS
446/*
447 * mstats - print out statistics about malloc
448 *
449 * Prints two lines of numbers, one showing the length of the free list
450 * for each size category, the second showing the number of mallocs -
451 * frees for each size category.
452 */
453mstats(s)
454	char *s;
455{
456  	register int i, j;
457  	register union overhead *p;
458  	int totfree = 0,
459  	totused = 0;
460
461  	fprintf(stderr, "Memory allocation statistics %s\nfree:\t", s);
462  	for (i = 0; i < NBUCKETS; i++) {
463  		for (j = 0, p = nextf[i]; p; p = p->ov_next, j++)
464  			;
465  		fprintf(stderr, " %d", j);
466  		totfree += j * (1 << (i + 3));
467  	}
468  	fprintf(stderr, "\nused:\t");
469  	for (i = 0; i < NBUCKETS; i++) {
470  		fprintf(stderr, " %d", nmalloc[i]);
471  		totused += nmalloc[i] * (1 << (i + 3));
472  	}
473  	fprintf(stderr, "\n\tTotal in use: %d, total free: %d\n",
474	    totused, totfree);
475}
476#endif
477
478
479static int
480morepages(n)
481int	n;
482{
483	int	fd = -1;
484	int	offset;
485
486	if (pagepool_end - pagepool_start > pagesz) {
487		caddr_t	addr = (caddr_t)
488			(((long)pagepool_start + pagesz - 1) & ~(pagesz - 1));
489		if (munmap(addr, pagepool_end - addr) != 0)
490			rtld_fdprintf(STDERR_FILENO, "morepages: munmap %p",
491			    addr);
492	}
493
494	offset = (long)pagepool_start - ((long)pagepool_start & ~(pagesz - 1));
495
496	if ((pagepool_start = mmap(0, n * pagesz,
497			PROT_READ|PROT_WRITE,
498			MAP_ANON|MAP_COPY, fd, 0)) == (caddr_t)-1) {
499		rtld_printf("Cannot map anonymous memory\n");
500		return 0;
501	}
502	pagepool_end = pagepool_start + n * pagesz;
503	pagepool_start += offset;
504
505	return n;
506}
507