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