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$"; 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 142211413Skibextern int pagesize; 143211413Skib 144211413Skibstatic int 145211413Skibrtld_getpagesize(void) 146211413Skib{ 147211413Skib int mib[2]; 148211413Skib size_t size; 149211413Skib 150211413Skib if (pagesize != 0) 151211413Skib return (pagesize); 152211413Skib 153211413Skib mib[0] = CTL_HW; 154211413Skib mib[1] = HW_PAGESIZE; 155211413Skib size = sizeof(pagesize); 156211413Skib if (sysctl(mib, 2, &pagesize, &size, NULL, 0) == -1) 157211413Skib return (-1); 158211413Skib return (pagesize); 159211413Skib 160211413Skib} 161211413Skib 16234192Sjdpvoid * 16334192Sjdpmalloc(nbytes) 16434192Sjdp size_t nbytes; 16534192Sjdp{ 16634192Sjdp register union overhead *op; 16738816Sdfr register int bucket; 16838816Sdfr register long n; 16934192Sjdp register unsigned amt; 17034192Sjdp 17134192Sjdp /* 17234192Sjdp * First time malloc is called, setup page size and 17334192Sjdp * align break pointer so all data will be page aligned. 17434192Sjdp */ 17534192Sjdp if (pagesz == 0) { 176211413Skib pagesz = n = rtld_getpagesize(); 17734192Sjdp if (morepages(NPOOLPAGES) == 0) 17834192Sjdp return NULL; 17934192Sjdp op = (union overhead *)(pagepool_start); 18038816Sdfr n = n - sizeof (*op) - ((long)op & (n - 1)); 18134192Sjdp if (n < 0) 18234192Sjdp n += pagesz; 18334192Sjdp if (n) { 18434192Sjdp pagepool_start += n; 18534192Sjdp } 18634192Sjdp bucket = 0; 18734192Sjdp amt = 8; 188114625Sobrien while ((unsigned)pagesz > amt) { 18934192Sjdp amt <<= 1; 19034192Sjdp bucket++; 19134192Sjdp } 19234192Sjdp pagebucket = bucket; 19334192Sjdp } 19434192Sjdp /* 19534192Sjdp * Convert amount of memory requested into closest block size 19634192Sjdp * stored in hash buckets which satisfies request. 19734192Sjdp * Account for space used per block for accounting. 19834192Sjdp */ 199114625Sobrien if (nbytes <= (unsigned long)(n = pagesz - sizeof (*op) - RSLOP)) { 20034192Sjdp#ifndef RCHECK 20134192Sjdp amt = 8; /* size of first bucket */ 20234192Sjdp bucket = 0; 20334192Sjdp#else 20434192Sjdp amt = 16; /* size of first bucket */ 20534192Sjdp bucket = 1; 20634192Sjdp#endif 20734192Sjdp n = -(sizeof (*op) + RSLOP); 20834192Sjdp } else { 20934192Sjdp amt = pagesz; 21034192Sjdp bucket = pagebucket; 21134192Sjdp } 21234192Sjdp while (nbytes > amt + n) { 21334192Sjdp amt <<= 1; 21434192Sjdp if (amt == 0) 21534192Sjdp return (NULL); 21634192Sjdp bucket++; 21734192Sjdp } 21834192Sjdp /* 21934192Sjdp * If nothing in hash bucket right now, 22034192Sjdp * request more memory from the system. 22134192Sjdp */ 22234192Sjdp if ((op = nextf[bucket]) == NULL) { 22334192Sjdp morecore(bucket); 22434192Sjdp if ((op = nextf[bucket]) == NULL) 22534192Sjdp return (NULL); 22634192Sjdp } 22734192Sjdp /* remove from linked list */ 22834192Sjdp nextf[bucket] = op->ov_next; 22934192Sjdp op->ov_magic = MAGIC; 23034192Sjdp op->ov_index = bucket; 23134192Sjdp#ifdef MSTATS 23234192Sjdp nmalloc[bucket]++; 23334192Sjdp#endif 23434192Sjdp#ifdef RCHECK 23534192Sjdp /* 23634192Sjdp * Record allocated size of block and 23734192Sjdp * bound space with magic numbers. 23834192Sjdp */ 23934192Sjdp op->ov_size = (nbytes + RSLOP - 1) & ~(RSLOP - 1); 24034192Sjdp op->ov_rmagic = RMAGIC; 24134192Sjdp *(u_short *)((caddr_t)(op + 1) + op->ov_size) = RMAGIC; 24234192Sjdp#endif 24334192Sjdp return ((char *)(op + 1)); 24434192Sjdp} 24534192Sjdp 246154248Sjasonevoid * 247154248Sjasonecalloc(size_t num, size_t size) 248154248Sjasone{ 249154248Sjasone void *ret; 250154248Sjasone 251154248Sjasone if (size != 0 && (num * size) / size != num) { 252154248Sjasone /* size_t overflow. */ 253154248Sjasone return (NULL); 254154248Sjasone } 255154248Sjasone 256154248Sjasone if ((ret = malloc(num * size)) != NULL) 257154248Sjasone memset(ret, 0, num * size); 258154248Sjasone 259154248Sjasone return (ret); 260154248Sjasone} 261154248Sjasone 26234192Sjdp/* 26334192Sjdp * Allocate more memory to the indicated bucket. 26434192Sjdp */ 26534192Sjdpstatic void 26634192Sjdpmorecore(bucket) 26734192Sjdp int bucket; 26834192Sjdp{ 26934192Sjdp register union overhead *op; 27034192Sjdp register int sz; /* size of desired block */ 27134192Sjdp int amt; /* amount to allocate */ 27234192Sjdp int nblks; /* how many blocks we get */ 27334192Sjdp 27434192Sjdp /* 27534192Sjdp * sbrk_size <= 0 only for big, FLUFFY, requests (about 27634192Sjdp * 2^30 bytes on a VAX, I think) or for a negative arg. 27734192Sjdp */ 27834192Sjdp sz = 1 << (bucket + 3); 27934192Sjdp#ifdef MALLOC_DEBUG 28034192Sjdp ASSERT(sz > 0); 28134192Sjdp#else 28234192Sjdp if (sz <= 0) 28334192Sjdp return; 28434192Sjdp#endif 28534192Sjdp if (sz < pagesz) { 28634192Sjdp amt = pagesz; 28734192Sjdp nblks = amt / sz; 28834192Sjdp } else { 28934192Sjdp amt = sz + pagesz; 29034192Sjdp nblks = 1; 29134192Sjdp } 29234192Sjdp if (amt > pagepool_end - pagepool_start) 29334192Sjdp if (morepages(amt/pagesz + NPOOLPAGES) == 0) 29434192Sjdp return; 29534192Sjdp op = (union overhead *)pagepool_start; 29634192Sjdp pagepool_start += amt; 29734192Sjdp 29834192Sjdp /* 29934192Sjdp * Add new memory allocated to that on 30034192Sjdp * free list for this hash bucket. 30134192Sjdp */ 30234192Sjdp nextf[bucket] = op; 30334192Sjdp while (--nblks > 0) { 30434192Sjdp op->ov_next = (union overhead *)((caddr_t)op + sz); 30534192Sjdp op = (union overhead *)((caddr_t)op + sz); 30634192Sjdp } 30734192Sjdp} 30834192Sjdp 30934192Sjdpvoid 31034192Sjdpfree(cp) 31134192Sjdp void *cp; 31234192Sjdp{ 31334192Sjdp register int size; 31434192Sjdp register union overhead *op; 31534192Sjdp 31634192Sjdp if (cp == NULL) 31734192Sjdp return; 31834192Sjdp op = (union overhead *)((caddr_t)cp - sizeof (union overhead)); 31934192Sjdp#ifdef MALLOC_DEBUG 32034192Sjdp ASSERT(op->ov_magic == MAGIC); /* make sure it was in use */ 32134192Sjdp#else 32234192Sjdp if (op->ov_magic != MAGIC) 32334192Sjdp return; /* sanity */ 32434192Sjdp#endif 32534192Sjdp#ifdef RCHECK 32634192Sjdp ASSERT(op->ov_rmagic == RMAGIC); 32734192Sjdp ASSERT(*(u_short *)((caddr_t)(op + 1) + op->ov_size) == RMAGIC); 32834192Sjdp#endif 32934192Sjdp size = op->ov_index; 33034192Sjdp ASSERT(size < NBUCKETS); 33134192Sjdp op->ov_next = nextf[size]; /* also clobbers ov_magic */ 33234192Sjdp nextf[size] = op; 33334192Sjdp#ifdef MSTATS 33434192Sjdp nmalloc[size]--; 33534192Sjdp#endif 33634192Sjdp} 33734192Sjdp 33834192Sjdp/* 33934192Sjdp * When a program attempts "storage compaction" as mentioned in the 34034192Sjdp * old malloc man page, it realloc's an already freed block. Usually 34134192Sjdp * this is the last block it freed; occasionally it might be farther 34234192Sjdp * back. We have to search all the free lists for the block in order 34334192Sjdp * to determine its bucket: 1st we make one pass thru the lists 34434192Sjdp * checking only the first block in each; if that fails we search 34534192Sjdp * ``realloc_srchlen'' blocks in each list for a match (the variable 34634192Sjdp * is extern so the caller can modify it). If that fails we just copy 34734192Sjdp * however many bytes was given to realloc() and hope it's not huge. 34834192Sjdp */ 34934192Sjdpint realloc_srchlen = 4; /* 4 should be plenty, -1 =>'s whole list */ 35034192Sjdp 35134192Sjdpvoid * 35234192Sjdprealloc(cp, nbytes) 35334192Sjdp void *cp; 35434192Sjdp size_t nbytes; 35534192Sjdp{ 35634192Sjdp register u_int onb; 35734192Sjdp register int i; 35834192Sjdp union overhead *op; 35934192Sjdp char *res; 36034192Sjdp int was_alloced = 0; 36134192Sjdp 36234192Sjdp if (cp == NULL) 36334192Sjdp return (malloc(nbytes)); 36434192Sjdp op = (union overhead *)((caddr_t)cp - sizeof (union overhead)); 36534192Sjdp if (op->ov_magic == MAGIC) { 36634192Sjdp was_alloced++; 36734192Sjdp i = op->ov_index; 36834192Sjdp } else { 36934192Sjdp /* 37034192Sjdp * Already free, doing "compaction". 37134192Sjdp * 37234192Sjdp * Search for the old block of memory on the 37334192Sjdp * free list. First, check the most common 37434192Sjdp * case (last element free'd), then (this failing) 37534192Sjdp * the last ``realloc_srchlen'' items free'd. 37634192Sjdp * If all lookups fail, then assume the size of 37734192Sjdp * the memory block being realloc'd is the 37834192Sjdp * largest possible (so that all "nbytes" of new 37934192Sjdp * memory are copied into). Note that this could cause 38034192Sjdp * a memory fault if the old area was tiny, and the moon 38134192Sjdp * is gibbous. However, that is very unlikely. 38234192Sjdp */ 38334192Sjdp if ((i = findbucket(op, 1)) < 0 && 38434192Sjdp (i = findbucket(op, realloc_srchlen)) < 0) 38534192Sjdp i = NBUCKETS; 38634192Sjdp } 38734192Sjdp onb = 1 << (i + 3); 388114625Sobrien if (onb < (u_int)pagesz) 38934192Sjdp onb -= sizeof (*op) + RSLOP; 39034192Sjdp else 39134192Sjdp onb += pagesz - sizeof (*op) - RSLOP; 39234192Sjdp /* avoid the copy if same size block */ 39334192Sjdp if (was_alloced) { 39434192Sjdp if (i) { 39534192Sjdp i = 1 << (i + 2); 39634192Sjdp if (i < pagesz) 39734192Sjdp i -= sizeof (*op) + RSLOP; 39834192Sjdp else 39934192Sjdp i += pagesz - sizeof (*op) - RSLOP; 40034192Sjdp } 401114625Sobrien if (nbytes <= onb && nbytes > (size_t)i) { 40234192Sjdp#ifdef RCHECK 40334192Sjdp op->ov_size = (nbytes + RSLOP - 1) & ~(RSLOP - 1); 40434192Sjdp *(u_short *)((caddr_t)(op + 1) + op->ov_size) = RMAGIC; 40534192Sjdp#endif 40634192Sjdp return(cp); 40734192Sjdp } else 40834192Sjdp free(cp); 40934192Sjdp } 41034192Sjdp if ((res = malloc(nbytes)) == NULL) 41134192Sjdp return (NULL); 41234192Sjdp if (cp != res) /* common optimization if "compacting" */ 41334192Sjdp bcopy(cp, res, (nbytes < onb) ? nbytes : onb); 41434192Sjdp return (res); 41534192Sjdp} 41634192Sjdp 41734192Sjdp/* 41834192Sjdp * Search ``srchlen'' elements of each free list for a block whose 41934192Sjdp * header starts at ``freep''. If srchlen is -1 search the whole list. 42034192Sjdp * Return bucket number, or -1 if not found. 42134192Sjdp */ 42234192Sjdpstatic int 42334192Sjdpfindbucket(freep, srchlen) 42434192Sjdp union overhead *freep; 42534192Sjdp int srchlen; 42634192Sjdp{ 42734192Sjdp register union overhead *p; 42834192Sjdp register int i, j; 42934192Sjdp 43034192Sjdp for (i = 0; i < NBUCKETS; i++) { 43134192Sjdp j = 0; 43234192Sjdp for (p = nextf[i]; p && j != srchlen; p = p->ov_next) { 43334192Sjdp if (p == freep) 43434192Sjdp return (i); 43534192Sjdp j++; 43634192Sjdp } 43734192Sjdp } 43834192Sjdp return (-1); 43934192Sjdp} 44034192Sjdp 44134192Sjdp#ifdef MSTATS 44234192Sjdp/* 44334192Sjdp * mstats - print out statistics about malloc 44434192Sjdp * 44534192Sjdp * Prints two lines of numbers, one showing the length of the free list 44634192Sjdp * for each size category, the second showing the number of mallocs - 44734192Sjdp * frees for each size category. 44834192Sjdp */ 44934192Sjdpmstats(s) 45034192Sjdp char *s; 45134192Sjdp{ 45234192Sjdp register int i, j; 45334192Sjdp register union overhead *p; 45434192Sjdp int totfree = 0, 45534192Sjdp totused = 0; 45634192Sjdp 45734192Sjdp fprintf(stderr, "Memory allocation statistics %s\nfree:\t", s); 45834192Sjdp for (i = 0; i < NBUCKETS; i++) { 45934192Sjdp for (j = 0, p = nextf[i]; p; p = p->ov_next, j++) 46034192Sjdp ; 46134192Sjdp fprintf(stderr, " %d", j); 46234192Sjdp totfree += j * (1 << (i + 3)); 46334192Sjdp } 46434192Sjdp fprintf(stderr, "\nused:\t"); 46534192Sjdp for (i = 0; i < NBUCKETS; i++) { 46634192Sjdp fprintf(stderr, " %d", nmalloc[i]); 46734192Sjdp totused += nmalloc[i] * (1 << (i + 3)); 46834192Sjdp } 46934192Sjdp fprintf(stderr, "\n\tTotal in use: %d, total free: %d\n", 47034192Sjdp totused, totfree); 47134192Sjdp} 47234192Sjdp#endif 47334192Sjdp 47434192Sjdp 47534192Sjdpstatic int 47634192Sjdpmorepages(n) 47734192Sjdpint n; 47834192Sjdp{ 47934192Sjdp int fd = -1; 48034192Sjdp int offset; 48134192Sjdp 48234192Sjdp if (pagepool_end - pagepool_start > pagesz) { 48334192Sjdp caddr_t addr = (caddr_t) 48438816Sdfr (((long)pagepool_start + pagesz - 1) & ~(pagesz - 1)); 48534192Sjdp if (munmap(addr, pagepool_end - addr) != 0) 486225152Skib rtld_fdprintf(STDERR_FILENO, "morepages: munmap %p", 487225152Skib addr); 48834192Sjdp } 48934192Sjdp 49038816Sdfr offset = (long)pagepool_start - ((long)pagepool_start & ~(pagesz - 1)); 49134192Sjdp 49234192Sjdp if ((pagepool_start = mmap(0, n * pagesz, 49334192Sjdp PROT_READ|PROT_WRITE, 49434192Sjdp MAP_ANON|MAP_COPY, fd, 0)) == (caddr_t)-1) { 495225152Skib rtld_printf("Cannot map anonymous memory\n"); 49634192Sjdp return 0; 49734192Sjdp } 49834192Sjdp pagepool_end = pagepool_start + n * pagesz; 49934192Sjdp pagepool_start += offset; 50034192Sjdp 50134192Sjdp return n; 50234192Sjdp} 503