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 uint16_t ovu_index; /* bucket # */ 79 uint8_t ovu_magic; /* magic number */ 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 #define AMAGIC 0xdf /* magic # for aligned alloc */ 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 LOW_BITS 3 97 #define FIRST_BUCKET_SIZE (1U << LOW_BITS) 98 #define NBUCKETS 30 99 static union overhead *nextf[NBUCKETS]; 100 101 static int pagesz; /* page size */ 102 103 /* 104 * The array of supported page sizes is provided by the user, i.e., the 105 * program that calls this storage allocator. That program must initialize 106 * the array before making its first call to allocate storage. The array 107 * must contain at least one page size. The page sizes must be stored in 108 * increasing order. 109 */ 110 111 static void * 112 cp2op(void *cp) 113 { 114 return (((caddr_t)cp - sizeof(union overhead))); 115 } 116 117 void * 118 __crt_malloc(size_t nbytes) 119 { 120 union overhead *op; 121 int bucket; 122 size_t amt; 123 124 /* 125 * First time malloc is called, setup page size. 126 */ 127 if (pagesz == 0) 128 pagesz = pagesizes[0]; 129 /* 130 * Convert amount of memory requested into closest block size 131 * stored in hash buckets which satisfies request. 132 * Account for space used per block for accounting. 133 */ 134 amt = FIRST_BUCKET_SIZE; 135 bucket = 0; 136 while (nbytes > amt - sizeof(*op)) { 137 amt <<= 1; 138 bucket++; 139 if (amt == 0 || bucket >= NBUCKETS) 140 return (NULL); 141 } 142 /* 143 * If nothing in hash bucket right now, 144 * request more memory from the system. 145 */ 146 if ((op = nextf[bucket]) == NULL) { 147 morecore(bucket); 148 if ((op = nextf[bucket]) == NULL) 149 return (NULL); 150 } 151 /* remove from linked list */ 152 nextf[bucket] = op->ov_next; 153 op->ov_magic = MAGIC; 154 op->ov_index = bucket; 155 return ((char *)(op + 1)); 156 } 157 158 void * 159 __crt_calloc(size_t num, size_t size) 160 { 161 void *ret; 162 163 if (size != 0 && (num * size) / size != num) { 164 /* size_t overflow. */ 165 return (NULL); 166 } 167 168 if ((ret = __crt_malloc(num * size)) != NULL) 169 memset(ret, 0, num * size); 170 171 return (ret); 172 } 173 174 void * 175 __crt_aligned_alloc_offset(size_t align, size_t size, size_t offset) 176 { 177 void *mem, *ov; 178 union overhead ov1; 179 uintptr_t x; 180 181 if (align < FIRST_BUCKET_SIZE) 182 align = FIRST_BUCKET_SIZE; 183 offset &= align - 1; 184 mem = __crt_malloc(size + align + offset + sizeof(union overhead)); 185 if (mem == NULL) 186 return (NULL); 187 x = roundup2((uintptr_t)mem + sizeof(union overhead), align); 188 x += offset; 189 ov = cp2op((void *)x); 190 ov1.ov_magic = AMAGIC; 191 ov1.ov_index = x - (uintptr_t)mem - sizeof(union overhead); 192 memcpy(ov, &ov1, sizeof(ov1)); 193 return ((void *)x); 194 } 195 196 /* 197 * Allocate more memory to the indicated bucket. 198 */ 199 static void 200 morecore(int bucket) 201 { 202 union overhead *op; 203 int sz; /* size of desired block */ 204 int amt; /* amount to allocate */ 205 int nblks; /* how many blocks we get */ 206 207 sz = FIRST_BUCKET_SIZE << bucket; 208 if (sz < pagesz) { 209 amt = pagesz; 210 nblks = amt / sz; 211 } else { 212 amt = sz; 213 nblks = 1; 214 } 215 if (amt > pagepool_end - pagepool_start) 216 if (morepages(amt / pagesz + NPOOLPAGES) == 0 && 217 /* Retry with min required size */ 218 morepages(amt / pagesz) == 0) 219 return; 220 op = (union overhead *)pagepool_start; 221 pagepool_start += amt; 222 223 /* 224 * Add new memory allocated to that on 225 * free list for this hash bucket. 226 */ 227 nextf[bucket] = op; 228 while (--nblks > 0) { 229 op->ov_next = (union overhead *)((caddr_t)op + sz); 230 op = (union overhead *)((caddr_t)op + sz); 231 } 232 } 233 234 void 235 __crt_free(void *cp) 236 { 237 union overhead *op, op1; 238 void *opx; 239 int size; 240 241 if (cp == NULL) 242 return; 243 opx = cp2op(cp); 244 memcpy(&op1, opx, sizeof(op1)); 245 op = op1.ov_magic == AMAGIC ? (void *)((caddr_t)cp - op1.ov_index) : 246 opx; 247 if (op->ov_magic != MAGIC) 248 return; /* sanity */ 249 size = op->ov_index; 250 op->ov_next = nextf[size]; /* also clobbers ov_magic */ 251 nextf[size] = op; 252 } 253 254 void * 255 __crt_realloc(void *cp, size_t nbytes) 256 { 257 u_int onb; 258 int i; 259 union overhead *op; 260 char *res; 261 262 if (cp == NULL) 263 return (__crt_malloc(nbytes)); 264 op = cp2op(cp); 265 if (op->ov_magic != MAGIC) 266 return (NULL); /* Double-free or bad argument */ 267 i = op->ov_index; 268 onb = 1 << (i + 3); 269 if (onb < (u_int)pagesz) 270 onb -= sizeof(*op); 271 else 272 onb += pagesz - sizeof(*op); 273 /* avoid the copy if same size block */ 274 if (i != 0) { 275 i = 1 << (i + 2); 276 if (i < pagesz) 277 i -= sizeof(*op); 278 else 279 i += pagesz - sizeof(*op); 280 } 281 if (nbytes <= onb && nbytes > (size_t)i) 282 return (cp); 283 if ((res = __crt_malloc(nbytes)) == NULL) 284 return (NULL); 285 bcopy(cp, res, (nbytes < onb) ? nbytes : onb); 286 __crt_free(cp); 287 return (res); 288 } 289 290 static int 291 morepages(int n) 292 { 293 caddr_t addr; 294 int offset; 295 296 if (pagepool_end - pagepool_start > pagesz) { 297 addr = roundup2(pagepool_start, pagesz); 298 if (munmap(addr, pagepool_end - addr) != 0) { 299 #ifdef IN_RTLD 300 rtld_fdprintf(STDERR_FILENO, _BASENAME_RTLD ": " 301 "morepages: cannot munmap %p: %s\n", 302 addr, rtld_strerror(errno)); 303 #endif 304 } 305 } 306 307 offset = (uintptr_t)pagepool_start - rounddown2( 308 (uintptr_t)pagepool_start, pagesz); 309 310 addr = mmap(0, n * pagesz, PROT_READ | PROT_WRITE, 311 MAP_ANON | MAP_PRIVATE, -1, 0); 312 if (addr == MAP_FAILED) { 313 #ifdef IN_RTLD 314 rtld_fdprintf(STDERR_FILENO, _BASENAME_RTLD ": morepages: " 315 "cannot mmap anonymous memory: %s\n", 316 rtld_strerror(errno)); 317 #endif 318 pagepool_start = pagepool_end = NULL; 319 return (0); 320 } 321 pagepool_start = addr; 322 pagepool_end = pagepool_start + n * pagesz; 323 pagepool_start += offset; 324 325 return (n); 326 } 327