1 /*- 2 * Copyright (c) 1983 Regents of the University of California. 3 * All rights reserved. 4 * 5 * Redistribution and use in source and binary forms, with or without 6 * modification, are permitted provided that the following conditions 7 * are met: 8 * 1. Redistributions of source code must retain the above copyright 9 * notice, this list of conditions and the following disclaimer. 10 * 2. Redistributions in binary form must reproduce the above copyright 11 * notice, this list of conditions and the following disclaimer in the 12 * documentation and/or other materials provided with the distribution. 13 * 3. Neither the name of the University nor the names of its contributors 14 * may be used to endorse or promote products derived from this software 15 * without specific prior written permission. 16 * 17 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 18 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 19 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 20 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 21 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 22 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 23 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 24 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 25 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 26 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 27 * SUCH DAMAGE. 28 */ 29 30 /* 31 * malloc.c (Caltech) 2/21/82 32 * Chris Kingsley, kingsley@cit-20. 33 * 34 * This is a very fast storage allocator. It allocates blocks of a small 35 * number of different sizes, and keeps free lists of each size. Blocks that 36 * don't exactly fit are passed up to the next larger size. In this 37 * implementation, the available sizes are 2^n-4 (or 2^n-10) bytes long. 38 * This is designed for use in a virtual memory environment. 39 */ 40 41 #include <sys/types.h> 42 #include <paths.h> 43 #include <stdarg.h> 44 #include <stdio.h> 45 #include <stdlib.h> 46 #include <string.h> 47 #include <unistd.h> 48 #include <sys/param.h> 49 #include <sys/mman.h> 50 #include "rtld_printf.h" 51 52 static void morecore(); 53 static int findbucket(); 54 55 /* 56 * Pre-allocate mmap'ed pages 57 */ 58 #define NPOOLPAGES (32*1024/pagesz) 59 static caddr_t pagepool_start, pagepool_end; 60 static int morepages(); 61 62 /* 63 * The overhead on a block is at least 4 bytes. When free, this space 64 * contains a pointer to the next free block, and the bottom two bits must 65 * be zero. When in use, the first byte is set to MAGIC, and the second 66 * byte is the size index. The remaining bytes are for alignment. 67 * If range checking is enabled then a second word holds the size of the 68 * requested block, less 1, rounded up to a multiple of sizeof(RMAGIC). 69 * The order of elements is critical: ov_magic must overlay the low order 70 * bits of ov_next, and ov_magic can not be a valid ov_next bit pattern. 71 */ 72 union overhead { 73 union overhead *ov_next; /* when free */ 74 struct { 75 u_char ovu_magic; /* magic number */ 76 u_char ovu_index; /* bucket # */ 77 #ifdef RCHECK 78 u_short ovu_rmagic; /* range magic number */ 79 u_int ovu_size; /* actual block size */ 80 #endif 81 } ovu; 82 #define ov_magic ovu.ovu_magic 83 #define ov_index ovu.ovu_index 84 #define ov_rmagic ovu.ovu_rmagic 85 #define ov_size ovu.ovu_size 86 }; 87 88 #define MAGIC 0xef /* magic # on accounting info */ 89 #define RMAGIC 0x5555 /* magic # on range info */ 90 91 #ifdef RCHECK 92 #define RSLOP sizeof (u_short) 93 #else 94 #define RSLOP 0 95 #endif 96 97 /* 98 * nextf[i] is the pointer to the next free block of size 2^(i+3). The 99 * smallest allocatable block is 8 bytes. The overhead information 100 * precedes the data area returned to the user. 101 */ 102 #define NBUCKETS 30 103 static union overhead *nextf[NBUCKETS]; 104 105 static int pagesz; /* page size */ 106 static int pagebucket; /* page size bucket */ 107 108 #ifdef MSTATS 109 /* 110 * nmalloc[i] is the difference between the number of mallocs and frees 111 * for a given block size. 112 */ 113 static u_int nmalloc[NBUCKETS]; 114 #include <stdio.h> 115 #endif 116 117 #if defined(MALLOC_DEBUG) || defined(RCHECK) 118 #define ASSERT(p) if (!(p)) botch("p") 119 #include <stdio.h> 120 static void 121 botch(char *s) 122 { 123 fprintf(stderr, "\r\nassertion botched: %s\r\n", s); 124 (void) fflush(stderr); /* just in case user buffered it */ 125 abort(); 126 } 127 #else 128 #define ASSERT(p) 129 #endif 130 131 /* Debugging stuff */ 132 #define TRACE() rtld_printf("TRACE %s:%d\n", __FILE__, __LINE__) 133 134 void * 135 malloc(size_t nbytes) 136 { 137 union overhead *op; 138 int bucket; 139 long n; 140 size_t amt; 141 142 /* 143 * First time malloc is called, setup page size and 144 * align break pointer so all data will be page aligned. 145 */ 146 if (pagesz == 0) { 147 pagesz = n = getpagesize(); 148 if (morepages(NPOOLPAGES) == 0) 149 return NULL; 150 op = (union overhead *)(pagepool_start); 151 n = n - sizeof (*op) - ((long)op & (n - 1)); 152 if (n < 0) 153 n += pagesz; 154 if (n) { 155 pagepool_start += n; 156 } 157 bucket = 0; 158 amt = 8; 159 while ((size_t)pagesz > amt) { 160 amt <<= 1; 161 bucket++; 162 } 163 pagebucket = bucket; 164 } 165 /* 166 * Convert amount of memory requested into closest block size 167 * stored in hash buckets which satisfies request. 168 * Account for space used per block for accounting. 169 */ 170 if (nbytes <= (unsigned long)(n = pagesz - sizeof (*op) - RSLOP)) { 171 #ifndef RCHECK 172 amt = 8; /* size of first bucket */ 173 bucket = 0; 174 #else 175 amt = 16; /* size of first bucket */ 176 bucket = 1; 177 #endif 178 n = -(sizeof (*op) + RSLOP); 179 } else { 180 amt = (size_t)pagesz; 181 bucket = pagebucket; 182 } 183 while (nbytes > amt + n) { 184 amt <<= 1; 185 if (amt == 0) 186 return (NULL); 187 bucket++; 188 } 189 /* 190 * If nothing in hash bucket right now, 191 * request more memory from the system. 192 */ 193 if ((op = nextf[bucket]) == NULL) { 194 morecore(bucket); 195 if ((op = nextf[bucket]) == NULL) 196 return (NULL); 197 } 198 /* remove from linked list */ 199 nextf[bucket] = op->ov_next; 200 op->ov_magic = MAGIC; 201 op->ov_index = bucket; 202 #ifdef MSTATS 203 nmalloc[bucket]++; 204 #endif 205 #ifdef RCHECK 206 /* 207 * Record allocated size of block and 208 * bound space with magic numbers. 209 */ 210 op->ov_size = roundup2(nbytes, RSLOP); 211 op->ov_rmagic = RMAGIC; 212 *(u_short *)((caddr_t)(op + 1) + op->ov_size) = RMAGIC; 213 #endif 214 return ((char *)(op + 1)); 215 } 216 217 /* 218 * Used by rtld.c, if we don't override it here the calloc from 219 * libc may try to pull in the malloc/realloc/free from libc too. 220 */ 221 void * 222 calloc(size_t num, size_t size) 223 { 224 void *p; 225 226 size *= num; 227 if ((p = malloc(size)) != NULL) 228 bzero(p, size); 229 return(p); 230 } 231 232 /* 233 * Allocate more memory to the indicated bucket. 234 */ 235 static void 236 morecore(int bucket) 237 { 238 union overhead *op; 239 size_t sz; /* size of desired block */ 240 size_t amt; /* amount to allocate */ 241 int nblks; /* how many blocks we get */ 242 243 /* 244 * sbrk_size <= 0 only for big, FLUFFY, requests (about 245 * 2^30 bytes on a VAX, I think) or for a negative arg. 246 */ 247 sz = 1LU << (bucket + 3); 248 #ifdef MALLOC_DEBUG 249 ASSERT(sz > 0); 250 #else 251 if (sz == 0) 252 return; 253 #endif 254 if (sz < pagesz) { 255 amt = pagesz; 256 nblks = amt / sz; 257 } else { 258 amt = sz + pagesz; 259 nblks = 1; 260 } 261 if (amt > pagepool_end - pagepool_start) 262 if (morepages(amt/pagesz + NPOOLPAGES) == 0) 263 return; 264 op = (union overhead *)pagepool_start; 265 pagepool_start += amt; 266 267 /* 268 * Add new memory allocated to that on 269 * free list for this hash bucket. 270 */ 271 nextf[bucket] = op; 272 while (--nblks > 0) { 273 op->ov_next = (union overhead *)((caddr_t)op + sz); 274 op = (union overhead *)((caddr_t)op + sz); 275 } 276 } 277 278 void 279 free(void *cp) 280 { 281 int size; 282 union overhead *op; 283 284 if (cp == NULL) 285 return; 286 op = (union overhead *)((caddr_t)cp - sizeof (union overhead)); 287 #ifdef MALLOC_DEBUG 288 ASSERT(op->ov_magic == MAGIC); /* make sure it was in use */ 289 #else 290 if (op->ov_magic != MAGIC) 291 return; /* sanity */ 292 #endif 293 #ifdef RCHECK 294 ASSERT(op->ov_rmagic == RMAGIC); 295 ASSERT(*(u_short *)((caddr_t)(op + 1) + op->ov_size) == RMAGIC); 296 #endif 297 size = op->ov_index; 298 ASSERT(size < NBUCKETS); 299 op->ov_next = nextf[size]; /* also clobbers ov_magic */ 300 nextf[size] = op; 301 #ifdef MSTATS 302 nmalloc[size]--; 303 #endif 304 } 305 306 /* 307 * When a program attempts "storage compaction" as mentioned in the 308 * old malloc man page, it realloc's an already freed block. Usually 309 * this is the last block it freed; occasionally it might be farther 310 * back. We have to search all the free lists for the block in order 311 * to determine its bucket: 1st we make one pass thru the lists 312 * checking only the first block in each; if that fails we search 313 * ``realloc_srchlen'' blocks in each list for a match (the variable 314 * is extern so the caller can modify it). If that fails we just copy 315 * however many bytes was given to realloc() and hope it's not huge. 316 */ 317 int realloc_srchlen = 4; /* 4 should be plenty, -1 =>'s whole list */ 318 319 void * 320 realloc(void *cp, size_t nbytes) 321 { 322 size_t onb; 323 int i; 324 union overhead *op; 325 char *res; 326 int was_alloced = 0; 327 328 if (cp == NULL) 329 return (malloc(nbytes)); 330 op = (union overhead *)((caddr_t)cp - sizeof (union overhead)); 331 if (op->ov_magic == MAGIC) { 332 was_alloced++; 333 i = op->ov_index; 334 } else { 335 /* 336 * Already free, doing "compaction". 337 * 338 * Search for the old block of memory on the 339 * free list. First, check the most common 340 * case (last element free'd), then (this failing) 341 * the last ``realloc_srchlen'' items free'd. 342 * If all lookups fail, then assume the size of 343 * the memory block being realloc'd is the 344 * largest possible (so that all "nbytes" of new 345 * memory are copied into). Note that this could cause 346 * a memory fault if the old area was tiny, and the moon 347 * is gibbous. However, that is very unlikely. 348 */ 349 if ((i = findbucket(op, 1)) < 0 && 350 (i = findbucket(op, realloc_srchlen)) < 0) 351 i = NBUCKETS; 352 } 353 onb = 1LU << (i + 3); 354 if (onb < (u_int)pagesz) 355 onb -= sizeof (*op) + RSLOP; 356 else 357 onb += pagesz - sizeof (*op) - RSLOP; 358 /* avoid the copy if same size block */ 359 if (was_alloced) { 360 if (i) { 361 i = 1LU << (i + 2); 362 if (i < pagesz) 363 i -= sizeof (*op) + RSLOP; 364 else 365 i += pagesz - sizeof (*op) - RSLOP; 366 } 367 if (nbytes <= onb && nbytes > (size_t)i) { 368 #ifdef RCHECK 369 op->ov_size = roundup2(nbytes, RSLOP); 370 *(u_short *)((caddr_t)(op + 1) + op->ov_size) = RMAGIC; 371 #endif 372 return(cp); 373 } else 374 free(cp); 375 } 376 if ((res = malloc(nbytes)) == NULL) 377 return (NULL); 378 if (cp != res) /* common optimization if "compacting" */ 379 bcopy(cp, res, (nbytes < onb) ? nbytes : onb); 380 return (res); 381 } 382 383 /* 384 * Search ``srchlen'' elements of each free list for a block whose 385 * header starts at ``freep''. If srchlen is -1 search the whole list. 386 * Return bucket number, or -1 if not found. 387 */ 388 static int 389 findbucket(union overhead *freep, int srchlen) 390 { 391 union overhead *p; 392 int i, j; 393 394 for (i = 0; i < NBUCKETS; i++) { 395 j = 0; 396 for (p = nextf[i]; p && j != srchlen; p = p->ov_next) { 397 if (p == freep) 398 return (i); 399 j++; 400 } 401 } 402 return (-1); 403 } 404 405 #ifdef MSTATS 406 /* 407 * mstats - print out statistics about malloc 408 * 409 * Prints two lines of numbers, one showing the length of the free list 410 * for each size category, the second showing the number of mallocs - 411 * frees for each size category. 412 */ 413 void 414 mstats(char *s) 415 { 416 int i, j; 417 union overhead *p; 418 size_t totfree, totused; 419 420 totfree = 0; 421 totused = 0; 422 423 fprintf(stderr, "Memory allocation statistics %s\nfree:\t", s); 424 for (i = 0; i < NBUCKETS; i++) { 425 for (j = 0, p = nextf[i]; p; p = p->ov_next, j++) 426 ; 427 fprintf(stderr, " %d", j); 428 totfree += j * (1LU << (i + 3)); 429 } 430 fprintf(stderr, "\nused:\t"); 431 for (i = 0; i < NBUCKETS; i++) { 432 fprintf(stderr, " %d", nmalloc[i]); 433 totused += nmalloc[i] * (1LU << (i + 3)); 434 } 435 fprintf(stderr, "\n\tTotal in use: %zd, total free: %zd\n", 436 totused, totfree); 437 } 438 #endif 439 440 441 static int 442 morepages(int n) 443 { 444 int fd = -1; 445 int offset; 446 447 if (pagepool_end - pagepool_start > pagesz) { 448 caddr_t addr = (caddr_t) 449 roundup2((long)pagepool_start, pagesz); 450 if (munmap(addr, pagepool_end - addr) != 0) 451 rtld_fdprintf(STDERR_FILENO, "morepages: munmap %p", 452 addr); 453 } 454 455 offset = (long)pagepool_start - rounddown2((long)pagepool_start, pagesz); 456 457 if ((pagepool_start = mmap(0, n * pagesz, 458 PROT_READ|PROT_WRITE, 459 MAP_ANON|MAP_COPY, fd, 0)) == (caddr_t)-1) { 460 rtld_printf("Cannot map anonymous memory\n"); 461 return 0; 462 } 463 pagepool_end = pagepool_start + n * pagesz; 464 pagepool_start += offset; 465 466 return n; 467 } 468