134192Sjdp/*- 234192Sjdp * Copyright (c) 1983 Regents of the University of California. 334192Sjdp * All rights reserved. 434192Sjdp * 534192Sjdp * Redistribution and use in source and binary forms, with or without 634192Sjdp * modification, are permitted provided that the following conditions 734192Sjdp * are met: 834192Sjdp * 1. Redistributions of source code must retain the above copyright 934192Sjdp * notice, this list of conditions and the following disclaimer. 1034192Sjdp * 2. Redistributions in binary form must reproduce the above copyright 1134192Sjdp * notice, this list of conditions and the following disclaimer in the 1234192Sjdp * documentation and/or other materials provided with the distribution. 13262435Sbrueffer * 3. Neither the name of the University nor the names of its contributors 1434192Sjdp * may be used to endorse or promote products derived from this software 1534192Sjdp * without specific prior written permission. 1634192Sjdp * 1734192Sjdp * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 1834192Sjdp * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 1934192Sjdp * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 2034192Sjdp * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 2134192Sjdp * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 2234192Sjdp * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 2334192Sjdp * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 2434192Sjdp * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 2534192Sjdp * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 2634192Sjdp * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 2734192Sjdp * SUCH DAMAGE. 2834192Sjdp */ 2934192Sjdp 3034192Sjdp#if defined(LIBC_SCCS) && !defined(lint) 3134192Sjdp/*static char *sccsid = "from: @(#)malloc.c 5.11 (Berkeley) 2/23/91";*/ 3250476Speterstatic char *rcsid = "$FreeBSD: releng/10.2/libexec/rtld-elf/malloc.c 281452 2015-04-12 06:43:13Z kib $"; 3334192Sjdp#endif /* LIBC_SCCS and not lint */ 3434192Sjdp 3534192Sjdp/* 3634192Sjdp * malloc.c (Caltech) 2/21/82 3734192Sjdp * Chris Kingsley, kingsley@cit-20. 3834192Sjdp * 3934192Sjdp * This is a very fast storage allocator. It allocates blocks of a small 4034192Sjdp * number of different sizes, and keeps free lists of each size. Blocks that 4134192Sjdp * don't exactly fit are passed up to the next larger size. In this 4234192Sjdp * implementation, the available sizes are 2^n-4 (or 2^n-10) bytes long. 4334192Sjdp * This is designed for use in a virtual memory environment. 4434192Sjdp */ 4534192Sjdp 4634192Sjdp#include <sys/types.h> 47211413Skib#include <sys/sysctl.h> 4869793Sobrien#include <paths.h> 49110803Skan#include <stdarg.h> 50119255Simp#include <stddef.h> 51110803Skan#include <stdio.h> 5234192Sjdp#include <stdlib.h> 5334192Sjdp#include <string.h> 5434192Sjdp#include <unistd.h> 5534192Sjdp#include <sys/param.h> 5634192Sjdp#include <sys/mman.h> 57225152Skib#include "rtld_printf.h" 5834192Sjdp 5934192Sjdpstatic void morecore(); 6034192Sjdpstatic int findbucket(); 6134192Sjdp 6234192Sjdp/* 6334192Sjdp * Pre-allocate mmap'ed pages 6434192Sjdp */ 6534192Sjdp#define NPOOLPAGES (32*1024/pagesz) 6634192Sjdpstatic caddr_t pagepool_start, pagepool_end; 6734192Sjdpstatic int morepages(); 6834192Sjdp 6934192Sjdp/* 7034192Sjdp * The overhead on a block is at least 4 bytes. When free, this space 7134192Sjdp * contains a pointer to the next free block, and the bottom two bits must 7234192Sjdp * be zero. When in use, the first byte is set to MAGIC, and the second 7334192Sjdp * byte is the size index. The remaining bytes are for alignment. 7434192Sjdp * If range checking is enabled then a second word holds the size of the 7534192Sjdp * requested block, less 1, rounded up to a multiple of sizeof(RMAGIC). 7634192Sjdp * The order of elements is critical: ov_magic must overlay the low order 7734192Sjdp * bits of ov_next, and ov_magic can not be a valid ov_next bit pattern. 7834192Sjdp */ 7934192Sjdpunion overhead { 8034192Sjdp union overhead *ov_next; /* when free */ 8134192Sjdp struct { 8234192Sjdp u_char ovu_magic; /* magic number */ 8334192Sjdp u_char ovu_index; /* bucket # */ 8434192Sjdp#ifdef RCHECK 8534192Sjdp u_short ovu_rmagic; /* range magic number */ 8634192Sjdp u_int ovu_size; /* actual block size */ 8734192Sjdp#endif 8834192Sjdp } ovu; 8934192Sjdp#define ov_magic ovu.ovu_magic 9034192Sjdp#define ov_index ovu.ovu_index 9134192Sjdp#define ov_rmagic ovu.ovu_rmagic 9234192Sjdp#define ov_size ovu.ovu_size 9334192Sjdp}; 9434192Sjdp 9534192Sjdp#define MAGIC 0xef /* magic # on accounting info */ 9634192Sjdp#define RMAGIC 0x5555 /* magic # on range info */ 9734192Sjdp 9834192Sjdp#ifdef RCHECK 9934192Sjdp#define RSLOP sizeof (u_short) 10034192Sjdp#else 10134192Sjdp#define RSLOP 0 10234192Sjdp#endif 10334192Sjdp 10434192Sjdp/* 10534192Sjdp * nextf[i] is the pointer to the next free block of size 2^(i+3). The 10634192Sjdp * smallest allocatable block is 8 bytes. The overhead information 10734192Sjdp * precedes the data area returned to the user. 10834192Sjdp */ 10934192Sjdp#define NBUCKETS 30 11034192Sjdpstatic union overhead *nextf[NBUCKETS]; 11134192Sjdp 11234192Sjdpstatic int pagesz; /* page size */ 11334192Sjdpstatic int pagebucket; /* page size bucket */ 11434192Sjdp 11534192Sjdp#ifdef MSTATS 11634192Sjdp/* 11734192Sjdp * nmalloc[i] is the difference between the number of mallocs and frees 11834192Sjdp * for a given block size. 11934192Sjdp */ 12034192Sjdpstatic u_int nmalloc[NBUCKETS]; 12134192Sjdp#include <stdio.h> 12234192Sjdp#endif 12334192Sjdp 12434192Sjdp#if defined(MALLOC_DEBUG) || defined(RCHECK) 12534192Sjdp#define ASSERT(p) if (!(p)) botch("p") 12634192Sjdp#include <stdio.h> 12734192Sjdpstatic void 12834192Sjdpbotch(s) 12934192Sjdp char *s; 13034192Sjdp{ 13134192Sjdp fprintf(stderr, "\r\nassertion botched: %s\r\n", s); 13234192Sjdp (void) fflush(stderr); /* just in case user buffered it */ 13334192Sjdp abort(); 13434192Sjdp} 13534192Sjdp#else 13634192Sjdp#define ASSERT(p) 13734192Sjdp#endif 13834192Sjdp 13934192Sjdp/* Debugging stuff */ 140225152Skib#define TRACE() rtld_printf("TRACE %s:%d\n", __FILE__, __LINE__) 14134192Sjdp 142281452Skib/* 143281452Skib * The array of supported page sizes is provided by the user, i.e., the 144281452Skib * program that calls this storage allocator. That program must initialize 145281452Skib * the array before making its first call to allocate storage. The array 146281452Skib * must contain at least one page size. The page sizes must be stored in 147281452Skib * increasing order. 148281452Skib */ 149281452Skibextern size_t *pagesizes; 150211413Skib 15134192Sjdpvoid * 15234192Sjdpmalloc(nbytes) 15334192Sjdp size_t nbytes; 15434192Sjdp{ 15534192Sjdp register union overhead *op; 15638816Sdfr register int bucket; 15738816Sdfr register long n; 15834192Sjdp register unsigned amt; 15934192Sjdp 16034192Sjdp /* 16134192Sjdp * First time malloc is called, setup page size and 16234192Sjdp * align break pointer so all data will be page aligned. 16334192Sjdp */ 16434192Sjdp if (pagesz == 0) { 165281452Skib pagesz = n = pagesizes[0]; 16634192Sjdp if (morepages(NPOOLPAGES) == 0) 16734192Sjdp return NULL; 16834192Sjdp op = (union overhead *)(pagepool_start); 16938816Sdfr n = n - sizeof (*op) - ((long)op & (n - 1)); 17034192Sjdp if (n < 0) 17134192Sjdp n += pagesz; 17234192Sjdp if (n) { 17334192Sjdp pagepool_start += n; 17434192Sjdp } 17534192Sjdp bucket = 0; 17634192Sjdp amt = 8; 177114625Sobrien while ((unsigned)pagesz > amt) { 17834192Sjdp amt <<= 1; 17934192Sjdp bucket++; 18034192Sjdp } 18134192Sjdp pagebucket = bucket; 18234192Sjdp } 18334192Sjdp /* 18434192Sjdp * Convert amount of memory requested into closest block size 18534192Sjdp * stored in hash buckets which satisfies request. 18634192Sjdp * Account for space used per block for accounting. 18734192Sjdp */ 188114625Sobrien if (nbytes <= (unsigned long)(n = pagesz - sizeof (*op) - RSLOP)) { 18934192Sjdp#ifndef RCHECK 19034192Sjdp amt = 8; /* size of first bucket */ 19134192Sjdp bucket = 0; 19234192Sjdp#else 19334192Sjdp amt = 16; /* size of first bucket */ 19434192Sjdp bucket = 1; 19534192Sjdp#endif 19634192Sjdp n = -(sizeof (*op) + RSLOP); 19734192Sjdp } else { 19834192Sjdp amt = pagesz; 19934192Sjdp bucket = pagebucket; 20034192Sjdp } 20134192Sjdp while (nbytes > amt + n) { 20234192Sjdp amt <<= 1; 20334192Sjdp if (amt == 0) 20434192Sjdp return (NULL); 20534192Sjdp bucket++; 20634192Sjdp } 20734192Sjdp /* 20834192Sjdp * If nothing in hash bucket right now, 20934192Sjdp * request more memory from the system. 21034192Sjdp */ 21134192Sjdp if ((op = nextf[bucket]) == NULL) { 21234192Sjdp morecore(bucket); 21334192Sjdp if ((op = nextf[bucket]) == NULL) 21434192Sjdp return (NULL); 21534192Sjdp } 21634192Sjdp /* remove from linked list */ 21734192Sjdp nextf[bucket] = op->ov_next; 21834192Sjdp op->ov_magic = MAGIC; 21934192Sjdp op->ov_index = bucket; 22034192Sjdp#ifdef MSTATS 22134192Sjdp nmalloc[bucket]++; 22234192Sjdp#endif 22334192Sjdp#ifdef RCHECK 22434192Sjdp /* 22534192Sjdp * Record allocated size of block and 22634192Sjdp * bound space with magic numbers. 22734192Sjdp */ 22834192Sjdp op->ov_size = (nbytes + RSLOP - 1) & ~(RSLOP - 1); 22934192Sjdp op->ov_rmagic = RMAGIC; 23034192Sjdp *(u_short *)((caddr_t)(op + 1) + op->ov_size) = RMAGIC; 23134192Sjdp#endif 23234192Sjdp return ((char *)(op + 1)); 23334192Sjdp} 23434192Sjdp 235154248Sjasonevoid * 236154248Sjasonecalloc(size_t num, size_t size) 237154248Sjasone{ 238154248Sjasone void *ret; 239154248Sjasone 240154248Sjasone if (size != 0 && (num * size) / size != num) { 241154248Sjasone /* size_t overflow. */ 242154248Sjasone return (NULL); 243154248Sjasone } 244154248Sjasone 245154248Sjasone if ((ret = malloc(num * size)) != NULL) 246154248Sjasone memset(ret, 0, num * size); 247154248Sjasone 248154248Sjasone return (ret); 249154248Sjasone} 250154248Sjasone 25134192Sjdp/* 25234192Sjdp * Allocate more memory to the indicated bucket. 25334192Sjdp */ 25434192Sjdpstatic void 25534192Sjdpmorecore(bucket) 25634192Sjdp int bucket; 25734192Sjdp{ 25834192Sjdp register union overhead *op; 25934192Sjdp register int sz; /* size of desired block */ 26034192Sjdp int amt; /* amount to allocate */ 26134192Sjdp int nblks; /* how many blocks we get */ 26234192Sjdp 26334192Sjdp /* 26434192Sjdp * sbrk_size <= 0 only for big, FLUFFY, requests (about 26534192Sjdp * 2^30 bytes on a VAX, I think) or for a negative arg. 26634192Sjdp */ 26734192Sjdp sz = 1 << (bucket + 3); 26834192Sjdp#ifdef MALLOC_DEBUG 26934192Sjdp ASSERT(sz > 0); 27034192Sjdp#else 27134192Sjdp if (sz <= 0) 27234192Sjdp return; 27334192Sjdp#endif 27434192Sjdp if (sz < pagesz) { 27534192Sjdp amt = pagesz; 27634192Sjdp nblks = amt / sz; 27734192Sjdp } else { 27834192Sjdp amt = sz + pagesz; 27934192Sjdp nblks = 1; 28034192Sjdp } 28134192Sjdp if (amt > pagepool_end - pagepool_start) 28234192Sjdp if (morepages(amt/pagesz + NPOOLPAGES) == 0) 28334192Sjdp return; 28434192Sjdp op = (union overhead *)pagepool_start; 28534192Sjdp pagepool_start += amt; 28634192Sjdp 28734192Sjdp /* 28834192Sjdp * Add new memory allocated to that on 28934192Sjdp * free list for this hash bucket. 29034192Sjdp */ 29134192Sjdp nextf[bucket] = op; 29234192Sjdp while (--nblks > 0) { 29334192Sjdp op->ov_next = (union overhead *)((caddr_t)op + sz); 29434192Sjdp op = (union overhead *)((caddr_t)op + sz); 29534192Sjdp } 29634192Sjdp} 29734192Sjdp 29834192Sjdpvoid 29934192Sjdpfree(cp) 30034192Sjdp void *cp; 30134192Sjdp{ 30234192Sjdp register int size; 30334192Sjdp register union overhead *op; 30434192Sjdp 30534192Sjdp if (cp == NULL) 30634192Sjdp return; 30734192Sjdp op = (union overhead *)((caddr_t)cp - sizeof (union overhead)); 30834192Sjdp#ifdef MALLOC_DEBUG 30934192Sjdp ASSERT(op->ov_magic == MAGIC); /* make sure it was in use */ 31034192Sjdp#else 31134192Sjdp if (op->ov_magic != MAGIC) 31234192Sjdp return; /* sanity */ 31334192Sjdp#endif 31434192Sjdp#ifdef RCHECK 31534192Sjdp ASSERT(op->ov_rmagic == RMAGIC); 31634192Sjdp ASSERT(*(u_short *)((caddr_t)(op + 1) + op->ov_size) == RMAGIC); 31734192Sjdp#endif 31834192Sjdp size = op->ov_index; 31934192Sjdp ASSERT(size < NBUCKETS); 32034192Sjdp op->ov_next = nextf[size]; /* also clobbers ov_magic */ 32134192Sjdp nextf[size] = op; 32234192Sjdp#ifdef MSTATS 32334192Sjdp nmalloc[size]--; 32434192Sjdp#endif 32534192Sjdp} 32634192Sjdp 32734192Sjdp/* 32834192Sjdp * When a program attempts "storage compaction" as mentioned in the 32934192Sjdp * old malloc man page, it realloc's an already freed block. Usually 33034192Sjdp * this is the last block it freed; occasionally it might be farther 33134192Sjdp * back. We have to search all the free lists for the block in order 33234192Sjdp * to determine its bucket: 1st we make one pass thru the lists 33334192Sjdp * checking only the first block in each; if that fails we search 33434192Sjdp * ``realloc_srchlen'' blocks in each list for a match (the variable 33534192Sjdp * is extern so the caller can modify it). If that fails we just copy 33634192Sjdp * however many bytes was given to realloc() and hope it's not huge. 33734192Sjdp */ 33834192Sjdpint realloc_srchlen = 4; /* 4 should be plenty, -1 =>'s whole list */ 33934192Sjdp 34034192Sjdpvoid * 34134192Sjdprealloc(cp, nbytes) 34234192Sjdp void *cp; 34334192Sjdp size_t nbytes; 34434192Sjdp{ 34534192Sjdp register u_int onb; 34634192Sjdp register int i; 34734192Sjdp union overhead *op; 34834192Sjdp char *res; 34934192Sjdp int was_alloced = 0; 35034192Sjdp 35134192Sjdp if (cp == NULL) 35234192Sjdp return (malloc(nbytes)); 35334192Sjdp op = (union overhead *)((caddr_t)cp - sizeof (union overhead)); 35434192Sjdp if (op->ov_magic == MAGIC) { 35534192Sjdp was_alloced++; 35634192Sjdp i = op->ov_index; 35734192Sjdp } else { 35834192Sjdp /* 35934192Sjdp * Already free, doing "compaction". 36034192Sjdp * 36134192Sjdp * Search for the old block of memory on the 36234192Sjdp * free list. First, check the most common 36334192Sjdp * case (last element free'd), then (this failing) 36434192Sjdp * the last ``realloc_srchlen'' items free'd. 36534192Sjdp * If all lookups fail, then assume the size of 36634192Sjdp * the memory block being realloc'd is the 36734192Sjdp * largest possible (so that all "nbytes" of new 36834192Sjdp * memory are copied into). Note that this could cause 36934192Sjdp * a memory fault if the old area was tiny, and the moon 37034192Sjdp * is gibbous. However, that is very unlikely. 37134192Sjdp */ 37234192Sjdp if ((i = findbucket(op, 1)) < 0 && 37334192Sjdp (i = findbucket(op, realloc_srchlen)) < 0) 37434192Sjdp i = NBUCKETS; 37534192Sjdp } 37634192Sjdp onb = 1 << (i + 3); 377114625Sobrien if (onb < (u_int)pagesz) 37834192Sjdp onb -= sizeof (*op) + RSLOP; 37934192Sjdp else 38034192Sjdp onb += pagesz - sizeof (*op) - RSLOP; 38134192Sjdp /* avoid the copy if same size block */ 38234192Sjdp if (was_alloced) { 38334192Sjdp if (i) { 38434192Sjdp i = 1 << (i + 2); 38534192Sjdp if (i < pagesz) 38634192Sjdp i -= sizeof (*op) + RSLOP; 38734192Sjdp else 38834192Sjdp i += pagesz - sizeof (*op) - RSLOP; 38934192Sjdp } 390114625Sobrien if (nbytes <= onb && nbytes > (size_t)i) { 39134192Sjdp#ifdef RCHECK 39234192Sjdp op->ov_size = (nbytes + RSLOP - 1) & ~(RSLOP - 1); 39334192Sjdp *(u_short *)((caddr_t)(op + 1) + op->ov_size) = RMAGIC; 39434192Sjdp#endif 39534192Sjdp return(cp); 39634192Sjdp } else 39734192Sjdp free(cp); 39834192Sjdp } 39934192Sjdp if ((res = malloc(nbytes)) == NULL) 40034192Sjdp return (NULL); 40134192Sjdp if (cp != res) /* common optimization if "compacting" */ 40234192Sjdp bcopy(cp, res, (nbytes < onb) ? nbytes : onb); 40334192Sjdp return (res); 40434192Sjdp} 40534192Sjdp 40634192Sjdp/* 40734192Sjdp * Search ``srchlen'' elements of each free list for a block whose 40834192Sjdp * header starts at ``freep''. If srchlen is -1 search the whole list. 40934192Sjdp * Return bucket number, or -1 if not found. 41034192Sjdp */ 41134192Sjdpstatic int 41234192Sjdpfindbucket(freep, srchlen) 41334192Sjdp union overhead *freep; 41434192Sjdp int srchlen; 41534192Sjdp{ 41634192Sjdp register union overhead *p; 41734192Sjdp register int i, j; 41834192Sjdp 41934192Sjdp for (i = 0; i < NBUCKETS; i++) { 42034192Sjdp j = 0; 42134192Sjdp for (p = nextf[i]; p && j != srchlen; p = p->ov_next) { 42234192Sjdp if (p == freep) 42334192Sjdp return (i); 42434192Sjdp j++; 42534192Sjdp } 42634192Sjdp } 42734192Sjdp return (-1); 42834192Sjdp} 42934192Sjdp 43034192Sjdp#ifdef MSTATS 43134192Sjdp/* 43234192Sjdp * mstats - print out statistics about malloc 43334192Sjdp * 43434192Sjdp * Prints two lines of numbers, one showing the length of the free list 43534192Sjdp * for each size category, the second showing the number of mallocs - 43634192Sjdp * frees for each size category. 43734192Sjdp */ 43834192Sjdpmstats(s) 43934192Sjdp char *s; 44034192Sjdp{ 44134192Sjdp register int i, j; 44234192Sjdp register union overhead *p; 44334192Sjdp int totfree = 0, 44434192Sjdp totused = 0; 44534192Sjdp 44634192Sjdp fprintf(stderr, "Memory allocation statistics %s\nfree:\t", s); 44734192Sjdp for (i = 0; i < NBUCKETS; i++) { 44834192Sjdp for (j = 0, p = nextf[i]; p; p = p->ov_next, j++) 44934192Sjdp ; 45034192Sjdp fprintf(stderr, " %d", j); 45134192Sjdp totfree += j * (1 << (i + 3)); 45234192Sjdp } 45334192Sjdp fprintf(stderr, "\nused:\t"); 45434192Sjdp for (i = 0; i < NBUCKETS; i++) { 45534192Sjdp fprintf(stderr, " %d", nmalloc[i]); 45634192Sjdp totused += nmalloc[i] * (1 << (i + 3)); 45734192Sjdp } 45834192Sjdp fprintf(stderr, "\n\tTotal in use: %d, total free: %d\n", 45934192Sjdp totused, totfree); 46034192Sjdp} 46134192Sjdp#endif 46234192Sjdp 46334192Sjdp 46434192Sjdpstatic int 46534192Sjdpmorepages(n) 46634192Sjdpint n; 46734192Sjdp{ 46834192Sjdp int fd = -1; 46934192Sjdp int offset; 47034192Sjdp 47134192Sjdp if (pagepool_end - pagepool_start > pagesz) { 47234192Sjdp caddr_t addr = (caddr_t) 47338816Sdfr (((long)pagepool_start + pagesz - 1) & ~(pagesz - 1)); 47434192Sjdp if (munmap(addr, pagepool_end - addr) != 0) 475225152Skib rtld_fdprintf(STDERR_FILENO, "morepages: munmap %p", 476225152Skib addr); 47734192Sjdp } 47834192Sjdp 47938816Sdfr offset = (long)pagepool_start - ((long)pagepool_start & ~(pagesz - 1)); 48034192Sjdp 48134192Sjdp if ((pagepool_start = mmap(0, n * pagesz, 48234192Sjdp PROT_READ|PROT_WRITE, 48334192Sjdp MAP_ANON|MAP_COPY, fd, 0)) == (caddr_t)-1) { 484225152Skib rtld_printf("Cannot map anonymous memory\n"); 48534192Sjdp return 0; 48634192Sjdp } 48734192Sjdp pagepool_end = pagepool_start + n * pagesz; 48834192Sjdp pagepool_start += offset; 48934192Sjdp 49034192Sjdp return n; 49134192Sjdp} 492