xref: /freebsd/libexec/rtld-elf/rtld_malloc.c (revision bc7e86106d428c7da328ad7fc9d4cb5f7f303e0e)
1d49ca25dSKonstantin Belousov /*-
2d49ca25dSKonstantin Belousov  * SPDX-License-Identifier: BSD-3-Clause
3d49ca25dSKonstantin Belousov  *
4d49ca25dSKonstantin Belousov  * Copyright (c) 1983 Regents of the University of California.
5d49ca25dSKonstantin Belousov  * All rights reserved.
6d49ca25dSKonstantin Belousov  *
7d49ca25dSKonstantin Belousov  * Redistribution and use in source and binary forms, with or without
8d49ca25dSKonstantin Belousov  * modification, are permitted provided that the following conditions
9d49ca25dSKonstantin Belousov  * are met:
10d49ca25dSKonstantin Belousov  * 1. Redistributions of source code must retain the above copyright
11d49ca25dSKonstantin Belousov  *    notice, this list of conditions and the following disclaimer.
12d49ca25dSKonstantin Belousov  * 2. Redistributions in binary form must reproduce the above copyright
13d49ca25dSKonstantin Belousov  *    notice, this list of conditions and the following disclaimer in the
14d49ca25dSKonstantin Belousov  *    documentation and/or other materials provided with the distribution.
15d49ca25dSKonstantin Belousov  * 3. Neither the name of the University nor the names of its contributors
16d49ca25dSKonstantin Belousov  *    may be used to endorse or promote products derived from this software
17d49ca25dSKonstantin Belousov  *    without specific prior written permission.
18d49ca25dSKonstantin Belousov  *
19d49ca25dSKonstantin Belousov  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
20d49ca25dSKonstantin Belousov  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
21d49ca25dSKonstantin Belousov  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
22d49ca25dSKonstantin Belousov  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
23d49ca25dSKonstantin Belousov  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
24d49ca25dSKonstantin Belousov  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
25d49ca25dSKonstantin Belousov  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
26d49ca25dSKonstantin Belousov  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
27d49ca25dSKonstantin Belousov  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
28d49ca25dSKonstantin Belousov  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
29d49ca25dSKonstantin Belousov  * SUCH DAMAGE.
30d49ca25dSKonstantin Belousov  */
31d49ca25dSKonstantin Belousov 
32d49ca25dSKonstantin Belousov #if defined(LIBC_SCCS) && !defined(lint)
33d49ca25dSKonstantin Belousov /*static char *sccsid = "from: @(#)malloc.c	5.11 (Berkeley) 2/23/91";*/
34d49ca25dSKonstantin Belousov static char *rcsid = "$FreeBSD$";
35d49ca25dSKonstantin Belousov #endif /* LIBC_SCCS and not lint */
36d49ca25dSKonstantin Belousov 
37d49ca25dSKonstantin Belousov /*
38d49ca25dSKonstantin Belousov  * malloc.c (Caltech) 2/21/82
39d49ca25dSKonstantin Belousov  * Chris Kingsley, kingsley@cit-20.
40d49ca25dSKonstantin Belousov  *
41d49ca25dSKonstantin Belousov  * This is a very fast storage allocator.  It allocates blocks of a small
42d49ca25dSKonstantin Belousov  * number of different sizes, and keeps free lists of each size.  Blocks that
43d49ca25dSKonstantin Belousov  * don't exactly fit are passed up to the next larger size.  In this
44d49ca25dSKonstantin Belousov  * implementation, the available sizes are 2^n-4 (or 2^n-10) bytes long.
45d49ca25dSKonstantin Belousov  * This is designed for use in a virtual memory environment.
46d49ca25dSKonstantin Belousov  */
47d49ca25dSKonstantin Belousov 
485cac2021SKonstantin Belousov #include <sys/param.h>
49d49ca25dSKonstantin Belousov #include <sys/sysctl.h>
505cac2021SKonstantin Belousov #include <sys/mman.h>
51d49ca25dSKonstantin Belousov #include <errno.h>
52d49ca25dSKonstantin Belousov #include <stdarg.h>
53d49ca25dSKonstantin Belousov #include <stddef.h>
54d49ca25dSKonstantin Belousov #include <string.h>
55d49ca25dSKonstantin Belousov #include <unistd.h>
56*bc7e8610SKonstantin Belousov #ifdef IN_RTLD
57d49ca25dSKonstantin Belousov #include "rtld.h"
58d49ca25dSKonstantin Belousov #include "rtld_printf.h"
5933dba3bbSKonstantin Belousov #include "rtld_paths.h"
60*bc7e8610SKonstantin Belousov #endif
61cf6dbdd1SKonstantin Belousov #include "rtld_malloc.h"
62d49ca25dSKonstantin Belousov 
63d49ca25dSKonstantin Belousov /*
64d49ca25dSKonstantin Belousov  * Pre-allocate mmap'ed pages
65d49ca25dSKonstantin Belousov  */
66d49ca25dSKonstantin Belousov #define	NPOOLPAGES	(128*1024/pagesz)
67d49ca25dSKonstantin Belousov static caddr_t		pagepool_start, pagepool_end;
68d49ca25dSKonstantin Belousov 
69d49ca25dSKonstantin Belousov /*
70d49ca25dSKonstantin Belousov  * The overhead on a block is at least 4 bytes.  When free, this space
71d49ca25dSKonstantin Belousov  * contains a pointer to the next free block, and the bottom two bits must
72d49ca25dSKonstantin Belousov  * be zero.  When in use, the first byte is set to MAGIC, and the second
73d49ca25dSKonstantin Belousov  * byte is the size index.  The remaining bytes are for alignment.
74d49ca25dSKonstantin Belousov  */
75d49ca25dSKonstantin Belousov union	overhead {
76d49ca25dSKonstantin Belousov 	union	overhead *ov_next;	/* when free */
77d49ca25dSKonstantin Belousov 	struct {
78d49ca25dSKonstantin Belousov 		u_char	ovu_magic;	/* magic number */
79d49ca25dSKonstantin Belousov 		u_char	ovu_index;	/* bucket # */
80d49ca25dSKonstantin Belousov 	} ovu;
81d49ca25dSKonstantin Belousov #define	ov_magic	ovu.ovu_magic
82d49ca25dSKonstantin Belousov #define	ov_index	ovu.ovu_index
83d49ca25dSKonstantin Belousov };
84d49ca25dSKonstantin Belousov 
85d49ca25dSKonstantin Belousov static void morecore(int bucket);
86d49ca25dSKonstantin Belousov static int morepages(int n);
87d49ca25dSKonstantin Belousov 
88d49ca25dSKonstantin Belousov #define	MAGIC		0xef		/* magic # on accounting info */
89d49ca25dSKonstantin Belousov 
90d49ca25dSKonstantin Belousov /*
9138915409SBrooks Davis  * nextf[i] is the pointer to the next free block of size
9238915409SBrooks Davis  * (FIRST_BUCKET_SIZE << i).  The overhead information precedes the data
9338915409SBrooks Davis  * area returned to the user.
94d49ca25dSKonstantin Belousov  */
9538915409SBrooks Davis #define	FIRST_BUCKET_SIZE	8
96d49ca25dSKonstantin Belousov #define	NBUCKETS 30
97d49ca25dSKonstantin Belousov static	union overhead *nextf[NBUCKETS];
98d49ca25dSKonstantin Belousov 
99d49ca25dSKonstantin Belousov static	int pagesz;			/* page size */
100d49ca25dSKonstantin Belousov 
101d49ca25dSKonstantin Belousov /*
102d49ca25dSKonstantin Belousov  * The array of supported page sizes is provided by the user, i.e., the
103d49ca25dSKonstantin Belousov  * program that calls this storage allocator.  That program must initialize
104d49ca25dSKonstantin Belousov  * the array before making its first call to allocate storage.  The array
105d49ca25dSKonstantin Belousov  * must contain at least one page size.  The page sizes must be stored in
106d49ca25dSKonstantin Belousov  * increasing order.
107d49ca25dSKonstantin Belousov  */
108d49ca25dSKonstantin Belousov 
109d49ca25dSKonstantin Belousov void *
110d49ca25dSKonstantin Belousov __crt_malloc(size_t nbytes)
111d49ca25dSKonstantin Belousov {
112d49ca25dSKonstantin Belousov 	union overhead *op;
113d49ca25dSKonstantin Belousov 	int bucket;
114d49ca25dSKonstantin Belousov 	size_t amt;
115d49ca25dSKonstantin Belousov 
116d49ca25dSKonstantin Belousov 	/*
11738915409SBrooks Davis 	 * First time malloc is called, setup page size.
118d49ca25dSKonstantin Belousov 	 */
11938915409SBrooks Davis 	if (pagesz == 0)
12038915409SBrooks Davis 		pagesz = pagesizes[0];
121d49ca25dSKonstantin Belousov 	/*
122d49ca25dSKonstantin Belousov 	 * Convert amount of memory requested into closest block size
123d49ca25dSKonstantin Belousov 	 * stored in hash buckets which satisfies request.
124d49ca25dSKonstantin Belousov 	 * Account for space used per block for accounting.
125d49ca25dSKonstantin Belousov 	 */
12638915409SBrooks Davis 	amt = FIRST_BUCKET_SIZE;
127d49ca25dSKonstantin Belousov 	bucket = 0;
12838915409SBrooks Davis 	while (nbytes > amt - sizeof(*op)) {
129d49ca25dSKonstantin Belousov 		amt <<= 1;
130d49ca25dSKonstantin Belousov 		bucket++;
13138915409SBrooks Davis 		if (amt == 0 || bucket >= NBUCKETS)
13238915409SBrooks Davis 			return (NULL);
133d49ca25dSKonstantin Belousov 	}
134d49ca25dSKonstantin Belousov 	/*
135d49ca25dSKonstantin Belousov 	 * If nothing in hash bucket right now,
136d49ca25dSKonstantin Belousov 	 * request more memory from the system.
137d49ca25dSKonstantin Belousov 	 */
138d49ca25dSKonstantin Belousov   	if ((op = nextf[bucket]) == NULL) {
139d49ca25dSKonstantin Belousov   		morecore(bucket);
140d49ca25dSKonstantin Belousov   		if ((op = nextf[bucket]) == NULL)
141d49ca25dSKonstantin Belousov   			return (NULL);
142d49ca25dSKonstantin Belousov 	}
143d49ca25dSKonstantin Belousov 	/* remove from linked list */
144d49ca25dSKonstantin Belousov   	nextf[bucket] = op->ov_next;
145d49ca25dSKonstantin Belousov 	op->ov_magic = MAGIC;
146d49ca25dSKonstantin Belousov 	op->ov_index = bucket;
147d49ca25dSKonstantin Belousov   	return ((char *)(op + 1));
148d49ca25dSKonstantin Belousov }
149d49ca25dSKonstantin Belousov 
150d49ca25dSKonstantin Belousov void *
151d49ca25dSKonstantin Belousov __crt_calloc(size_t num, size_t size)
152d49ca25dSKonstantin Belousov {
153d49ca25dSKonstantin Belousov 	void *ret;
154d49ca25dSKonstantin Belousov 
155d49ca25dSKonstantin Belousov 	if (size != 0 && (num * size) / size != num) {
156d49ca25dSKonstantin Belousov 		/* size_t overflow. */
157d49ca25dSKonstantin Belousov 		return (NULL);
158d49ca25dSKonstantin Belousov 	}
159d49ca25dSKonstantin Belousov 
160d49ca25dSKonstantin Belousov 	if ((ret = __crt_malloc(num * size)) != NULL)
161d49ca25dSKonstantin Belousov 		memset(ret, 0, num * size);
162d49ca25dSKonstantin Belousov 
163d49ca25dSKonstantin Belousov 	return (ret);
164d49ca25dSKonstantin Belousov }
165d49ca25dSKonstantin Belousov 
166d49ca25dSKonstantin Belousov /*
167d49ca25dSKonstantin Belousov  * Allocate more memory to the indicated bucket.
168d49ca25dSKonstantin Belousov  */
169d49ca25dSKonstantin Belousov static void
170d49ca25dSKonstantin Belousov morecore(int bucket)
171d49ca25dSKonstantin Belousov {
172d49ca25dSKonstantin Belousov 	union overhead *op;
173d49ca25dSKonstantin Belousov 	int sz;		/* size of desired block */
174d49ca25dSKonstantin Belousov   	int amt;			/* amount to allocate */
175d49ca25dSKonstantin Belousov   	int nblks;			/* how many blocks we get */
176d49ca25dSKonstantin Belousov 
17738915409SBrooks Davis 	sz = FIRST_BUCKET_SIZE << bucket;
178d49ca25dSKonstantin Belousov 	if (sz < pagesz) {
179d49ca25dSKonstantin Belousov 		amt = pagesz;
180d49ca25dSKonstantin Belousov   		nblks = amt / sz;
181d49ca25dSKonstantin Belousov 	} else {
18238915409SBrooks Davis 		amt = sz;
183d49ca25dSKonstantin Belousov 		nblks = 1;
184d49ca25dSKonstantin Belousov 	}
185d49ca25dSKonstantin Belousov 	if (amt > pagepool_end - pagepool_start)
18619e008e7SKonstantin Belousov 		if (morepages(amt / pagesz + NPOOLPAGES) == 0 &&
18719e008e7SKonstantin Belousov 		    /* Retry with min required size */
18819e008e7SKonstantin Belousov 		    morepages(amt / pagesz) == 0)
189d49ca25dSKonstantin Belousov 			return;
190d49ca25dSKonstantin Belousov 	op = (union overhead *)pagepool_start;
191d49ca25dSKonstantin Belousov 	pagepool_start += amt;
192d49ca25dSKonstantin Belousov 
193d49ca25dSKonstantin Belousov 	/*
194d49ca25dSKonstantin Belousov 	 * Add new memory allocated to that on
195d49ca25dSKonstantin Belousov 	 * free list for this hash bucket.
196d49ca25dSKonstantin Belousov 	 */
197d49ca25dSKonstantin Belousov   	nextf[bucket] = op;
198d49ca25dSKonstantin Belousov   	while (--nblks > 0) {
199d49ca25dSKonstantin Belousov 		op->ov_next = (union overhead *)((caddr_t)op + sz);
200d49ca25dSKonstantin Belousov 		op = (union overhead *)((caddr_t)op + sz);
201d49ca25dSKonstantin Belousov   	}
202d49ca25dSKonstantin Belousov }
203d49ca25dSKonstantin Belousov 
204d49ca25dSKonstantin Belousov void
205d49ca25dSKonstantin Belousov __crt_free(void *cp)
206d49ca25dSKonstantin Belousov {
207d49ca25dSKonstantin Belousov 	int size;
208d49ca25dSKonstantin Belousov 	union overhead *op;
209d49ca25dSKonstantin Belousov 
210d49ca25dSKonstantin Belousov   	if (cp == NULL)
211d49ca25dSKonstantin Belousov   		return;
212d49ca25dSKonstantin Belousov 	op = (union overhead *)((caddr_t)cp - sizeof (union overhead));
213d49ca25dSKonstantin Belousov 	if (op->ov_magic != MAGIC)
214d49ca25dSKonstantin Belousov 		return;				/* sanity */
215d49ca25dSKonstantin Belousov   	size = op->ov_index;
216d49ca25dSKonstantin Belousov 	op->ov_next = nextf[size];	/* also clobbers ov_magic */
217d49ca25dSKonstantin Belousov   	nextf[size] = op;
218d49ca25dSKonstantin Belousov }
219d49ca25dSKonstantin Belousov 
220d49ca25dSKonstantin Belousov void *
221d49ca25dSKonstantin Belousov __crt_realloc(void *cp, size_t nbytes)
222d49ca25dSKonstantin Belousov {
223d49ca25dSKonstantin Belousov 	u_int onb;
224d49ca25dSKonstantin Belousov 	int i;
225d49ca25dSKonstantin Belousov 	union overhead *op;
226d49ca25dSKonstantin Belousov   	char *res;
227d49ca25dSKonstantin Belousov 
228d49ca25dSKonstantin Belousov   	if (cp == NULL)
229d49ca25dSKonstantin Belousov 		return (__crt_malloc(nbytes));
230d49ca25dSKonstantin Belousov 	op = (union overhead *)((caddr_t)cp - sizeof (union overhead));
23198ab7906SBrooks Davis 	if (op->ov_magic != MAGIC)
23298ab7906SBrooks Davis 		return (NULL);	/* Double-free or bad argument */
233d49ca25dSKonstantin Belousov 	i = op->ov_index;
234d49ca25dSKonstantin Belousov 	onb = 1 << (i + 3);
235d49ca25dSKonstantin Belousov 	if (onb < (u_int)pagesz)
2365cac2021SKonstantin Belousov 		onb -= sizeof(*op);
237d49ca25dSKonstantin Belousov 	else
2385cac2021SKonstantin Belousov 		onb += pagesz - sizeof(*op);
239d49ca25dSKonstantin Belousov 	/* avoid the copy if same size block */
24098ab7906SBrooks Davis 	if (i != 0) {
241d49ca25dSKonstantin Belousov 		i = 1 << (i + 2);
242d49ca25dSKonstantin Belousov 		if (i < pagesz)
2435cac2021SKonstantin Belousov 			i -= sizeof(*op);
244d49ca25dSKonstantin Belousov 		else
2455cac2021SKonstantin Belousov 			i += pagesz - sizeof(*op);
246d49ca25dSKonstantin Belousov 	}
2475cac2021SKonstantin Belousov 	if (nbytes <= onb && nbytes > (size_t)i)
248d49ca25dSKonstantin Belousov 		return (cp);
249d49ca25dSKonstantin Belousov   	if ((res = __crt_malloc(nbytes)) == NULL)
250d49ca25dSKonstantin Belousov 		return (NULL);
251d49ca25dSKonstantin Belousov 	bcopy(cp, res, (nbytes < onb) ? nbytes : onb);
25298ab7906SBrooks Davis 	__crt_free(cp);
253d49ca25dSKonstantin Belousov   	return (res);
254d49ca25dSKonstantin Belousov }
255d49ca25dSKonstantin Belousov 
256d49ca25dSKonstantin Belousov static int
257d49ca25dSKonstantin Belousov morepages(int n)
258d49ca25dSKonstantin Belousov {
2593cac4083SKonstantin Belousov 	caddr_t	addr;
260d49ca25dSKonstantin Belousov 	int offset;
261d49ca25dSKonstantin Belousov 
262d49ca25dSKonstantin Belousov 	if (pagepool_end - pagepool_start > pagesz) {
2630b72d296SKonstantin Belousov 		addr = roundup2(pagepool_start, pagesz);
264d49ca25dSKonstantin Belousov 		if (munmap(addr, pagepool_end - addr) != 0) {
265d49ca25dSKonstantin Belousov #ifdef IN_RTLD
266d49ca25dSKonstantin Belousov 			rtld_fdprintf(STDERR_FILENO, _BASENAME_RTLD ": "
267d49ca25dSKonstantin Belousov 			    "morepages: cannot munmap %p: %s\n",
268d49ca25dSKonstantin Belousov 			    addr, rtld_strerror(errno));
269d49ca25dSKonstantin Belousov #endif
270d49ca25dSKonstantin Belousov 		}
271d49ca25dSKonstantin Belousov 	}
272d49ca25dSKonstantin Belousov 
2730b72d296SKonstantin Belousov 	offset = (uintptr_t)pagepool_start - rounddown2(
2740b72d296SKonstantin Belousov 	    (uintptr_t)pagepool_start, pagesz);
275d49ca25dSKonstantin Belousov 
27673dddffcSKonstantin Belousov 	addr = mmap(0, n * pagesz, PROT_READ | PROT_WRITE,
2773cac4083SKonstantin Belousov 	    MAP_ANON | MAP_PRIVATE, -1, 0);
27873dddffcSKonstantin Belousov 	if (addr == MAP_FAILED) {
279d49ca25dSKonstantin Belousov #ifdef IN_RTLD
280d49ca25dSKonstantin Belousov 		rtld_fdprintf(STDERR_FILENO, _BASENAME_RTLD ": morepages: "
281d49ca25dSKonstantin Belousov 		    "cannot mmap anonymous memory: %s\n",
282d49ca25dSKonstantin Belousov 		    rtld_strerror(errno));
283d49ca25dSKonstantin Belousov #endif
28473dddffcSKonstantin Belousov 		pagepool_start = pagepool_end = NULL;
2853cac4083SKonstantin Belousov 		return (0);
286d49ca25dSKonstantin Belousov 	}
28773dddffcSKonstantin Belousov 	pagepool_start = addr;
288d49ca25dSKonstantin Belousov 	pagepool_end = pagepool_start + n * pagesz;
289d49ca25dSKonstantin Belousov 	pagepool_start += offset;
290d49ca25dSKonstantin Belousov 
2913cac4083SKonstantin Belousov 	return (n);
292d49ca25dSKonstantin Belousov }
293