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 #if defined(LIBC_SCCS) && !defined(lint)
33 /*static char *sccsid = "from: @(#)malloc.c 5.11 (Berkeley) 2/23/91";*/
34 static char *rcsid = "$FreeBSD$";
35 #endif /* LIBC_SCCS and not lint */
36
37 /*
38 * malloc.c (Caltech) 2/21/82
39 * Chris Kingsley, kingsley@cit-20.
40 *
41 * This is a very fast storage allocator. It allocates blocks of a small
42 * number of different sizes, and keeps free lists of each size. Blocks that
43 * don't exactly fit are passed up to the next larger size. In this
44 * implementation, the available sizes are 2^n-4 (or 2^n-10) bytes long.
45 * This is designed for use in a virtual memory environment.
46 */
47
48 #include <sys/param.h>
49 #include <sys/sysctl.h>
50 #include <sys/mman.h>
51 #include <errno.h>
52 #include <stdarg.h>
53 #include <stddef.h>
54 #include <string.h>
55 #include <unistd.h>
56 #include "rtld.h"
57 #include "rtld_printf.h"
58 #include "rtld_paths.h"
59
60 /*
61 * Pre-allocate mmap'ed pages
62 */
63 #define NPOOLPAGES (128*1024/pagesz)
64 static caddr_t pagepool_start, pagepool_end;
65
66 /*
67 * The overhead on a block is at least 4 bytes. When free, this space
68 * contains a pointer to the next free block, and the bottom two bits must
69 * be zero. When in use, the first byte is set to MAGIC, and the second
70 * byte is the size index. The remaining bytes are for alignment.
71 * If range checking is enabled then a second word holds the size of the
72 * requested block, less 1, rounded up to a multiple of sizeof(RMAGIC).
73 * The order of elements is critical: ov_magic must overlay the low order
74 * bits of ov_next, and ov_magic can not be a valid ov_next bit pattern.
75 */
76 union overhead {
77 union overhead *ov_next; /* when free */
78 struct {
79 u_char ovu_magic; /* magic number */
80 u_char ovu_index; /* bucket # */
81 } ovu;
82 #define ov_magic ovu.ovu_magic
83 #define ov_index ovu.ovu_index
84 };
85
86 static void morecore(int bucket);
87 static int morepages(int n);
88
89 #define MAGIC 0xef /* magic # on accounting info */
90
91 /*
92 * nextf[i] is the pointer to the next free block of size
93 * (FIRST_BUCKET_SIZE << i). The overhead information precedes the data
94 * area returned to the user.
95 */
96 #define FIRST_BUCKET_SIZE 8
97 #define NBUCKETS 30
98 static union overhead *nextf[NBUCKETS];
99
100 static int pagesz; /* page size */
101
102 /*
103 * The array of supported page sizes is provided by the user, i.e., the
104 * program that calls this storage allocator. That program must initialize
105 * the array before making its first call to allocate storage. The array
106 * must contain at least one page size. The page sizes must be stored in
107 * increasing order.
108 */
109
110 void *
__crt_malloc(size_t nbytes)111 __crt_malloc(size_t nbytes)
112 {
113 union overhead *op;
114 int bucket;
115 size_t amt;
116
117 /*
118 * First time malloc is called, setup page size.
119 */
120 if (pagesz == 0)
121 pagesz = pagesizes[0];
122 /*
123 * Convert amount of memory requested into closest block size
124 * stored in hash buckets which satisfies request.
125 * Account for space used per block for accounting.
126 */
127 amt = FIRST_BUCKET_SIZE;
128 bucket = 0;
129 while (nbytes > amt - sizeof(*op)) {
130 amt <<= 1;
131 bucket++;
132 if (amt == 0 || bucket >= NBUCKETS)
133 return (NULL);
134 }
135 /*
136 * If nothing in hash bucket right now,
137 * request more memory from the system.
138 */
139 if ((op = nextf[bucket]) == NULL) {
140 morecore(bucket);
141 if ((op = nextf[bucket]) == NULL)
142 return (NULL);
143 }
144 /* remove from linked list */
145 nextf[bucket] = op->ov_next;
146 op->ov_magic = MAGIC;
147 op->ov_index = bucket;
148 return ((char *)(op + 1));
149 }
150
151 void *
__crt_calloc(size_t num,size_t size)152 __crt_calloc(size_t num, size_t size)
153 {
154 void *ret;
155
156 if (size != 0 && (num * size) / size != num) {
157 /* size_t overflow. */
158 return (NULL);
159 }
160
161 if ((ret = __crt_malloc(num * size)) != NULL)
162 memset(ret, 0, num * size);
163
164 return (ret);
165 }
166
167 /*
168 * Allocate more memory to the indicated bucket.
169 */
170 static void
morecore(int bucket)171 morecore(int bucket)
172 {
173 union overhead *op;
174 int sz; /* size of desired block */
175 int amt; /* amount to allocate */
176 int nblks; /* how many blocks we get */
177
178 sz = FIRST_BUCKET_SIZE << bucket;
179 if (sz < pagesz) {
180 amt = pagesz;
181 nblks = amt / sz;
182 } else {
183 amt = sz;
184 nblks = 1;
185 }
186 if (amt > pagepool_end - pagepool_start)
187 if (morepages(amt / pagesz + NPOOLPAGES) == 0 &&
188 /* Retry with min required size */
189 morepages(amt / pagesz) == 0)
190 return;
191 op = (union overhead *)pagepool_start;
192 pagepool_start += amt;
193
194 /*
195 * Add new memory allocated to that on
196 * free list for this hash bucket.
197 */
198 nextf[bucket] = op;
199 while (--nblks > 0) {
200 op->ov_next = (union overhead *)((caddr_t)op + sz);
201 op = (union overhead *)((caddr_t)op + sz);
202 }
203 }
204
205 void
__crt_free(void * cp)206 __crt_free(void *cp)
207 {
208 int size;
209 union overhead *op;
210
211 if (cp == NULL)
212 return;
213 op = (union overhead *)((caddr_t)cp - sizeof (union overhead));
214 if (op->ov_magic != MAGIC)
215 return; /* sanity */
216 size = op->ov_index;
217 op->ov_next = nextf[size]; /* also clobbers ov_magic */
218 nextf[size] = op;
219 }
220
221 void *
__crt_realloc(void * cp,size_t nbytes)222 __crt_realloc(void *cp, size_t nbytes)
223 {
224 u_int onb;
225 int i;
226 union overhead *op;
227 char *res;
228
229 if (cp == NULL)
230 return (__crt_malloc(nbytes));
231 op = (union overhead *)((caddr_t)cp - sizeof (union overhead));
232 if (op->ov_magic != MAGIC)
233 return (NULL); /* Double-free or bad argument */
234 i = op->ov_index;
235 onb = 1 << (i + 3);
236 if (onb < (u_int)pagesz)
237 onb -= sizeof(*op);
238 else
239 onb += pagesz - sizeof(*op);
240 /* avoid the copy if same size block */
241 if (i != 0) {
242 i = 1 << (i + 2);
243 if (i < pagesz)
244 i -= sizeof(*op);
245 else
246 i += pagesz - sizeof(*op);
247 }
248 if (nbytes <= onb && nbytes > (size_t)i)
249 return (cp);
250 if ((res = __crt_malloc(nbytes)) == NULL)
251 return (NULL);
252 bcopy(cp, res, (nbytes < onb) ? nbytes : onb);
253 __crt_free(cp);
254 return (res);
255 }
256
257 static int
morepages(int n)258 morepages(int n)
259 {
260 caddr_t addr;
261 int offset;
262
263 if (pagepool_end - pagepool_start > pagesz) {
264 addr = roundup2(pagepool_start, pagesz);
265 if (munmap(addr, pagepool_end - addr) != 0) {
266 #ifdef IN_RTLD
267 rtld_fdprintf(STDERR_FILENO, _BASENAME_RTLD ": "
268 "morepages: cannot munmap %p: %s\n",
269 addr, rtld_strerror(errno));
270 #endif
271 }
272 }
273
274 offset = (uintptr_t)pagepool_start - rounddown2(
275 (uintptr_t)pagepool_start, pagesz);
276
277 addr = mmap(0, n * pagesz, PROT_READ | PROT_WRITE,
278 MAP_ANON | MAP_PRIVATE, -1, 0);
279 if (addr == MAP_FAILED) {
280 #ifdef IN_RTLD
281 rtld_fdprintf(STDERR_FILENO, _BASENAME_RTLD ": morepages: "
282 "cannot mmap anonymous memory: %s\n",
283 rtld_strerror(errno));
284 #endif
285 pagepool_start = pagepool_end = NULL;
286 return (0);
287 }
288 pagepool_start = addr;
289 pagepool_end = pagepool_start + n * pagesz;
290 pagepool_start += offset;
291
292 return (n);
293 }
294