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