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. 13262136Sbrueffer * 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> 48110803Skan#include <stdarg.h> 49119255Simp#include <stddef.h> 50110803Skan#include <stdio.h> 5134192Sjdp#include <stdlib.h> 5234192Sjdp#include <string.h> 5334192Sjdp#include <unistd.h> 5434192Sjdp#include <sys/param.h> 5534192Sjdp#include <sys/mman.h> 56225152Skib#include "rtld_printf.h" 5734192Sjdp 5834192Sjdpstatic void morecore(); 5934192Sjdpstatic int findbucket(); 6034192Sjdp 6134192Sjdp/* 6234192Sjdp * Pre-allocate mmap'ed pages 6334192Sjdp */ 6434192Sjdp#define NPOOLPAGES (32*1024/pagesz) 6534192Sjdpstatic caddr_t pagepool_start, pagepool_end; 6634192Sjdpstatic int morepages(); 6734192Sjdp 6834192Sjdp/* 6934192Sjdp * The overhead on a block is at least 4 bytes. When free, this space 7034192Sjdp * contains a pointer to the next free block, and the bottom two bits must 7134192Sjdp * be zero. When in use, the first byte is set to MAGIC, and the second 7234192Sjdp * byte is the size index. The remaining bytes are for alignment. 7334192Sjdp * If range checking is enabled then a second word holds the size of the 7434192Sjdp * requested block, less 1, rounded up to a multiple of sizeof(RMAGIC). 7534192Sjdp * The order of elements is critical: ov_magic must overlay the low order 7634192Sjdp * bits of ov_next, and ov_magic can not be a valid ov_next bit pattern. 7734192Sjdp */ 7834192Sjdpunion overhead { 7934192Sjdp union overhead *ov_next; /* when free */ 8034192Sjdp struct { 8134192Sjdp u_char ovu_magic; /* magic number */ 8234192Sjdp u_char ovu_index; /* bucket # */ 8334192Sjdp#ifdef RCHECK 8434192Sjdp u_short ovu_rmagic; /* range magic number */ 8534192Sjdp u_int ovu_size; /* actual block size */ 8634192Sjdp#endif 8734192Sjdp } ovu; 8834192Sjdp#define ov_magic ovu.ovu_magic 8934192Sjdp#define ov_index ovu.ovu_index 9034192Sjdp#define ov_rmagic ovu.ovu_rmagic 9134192Sjdp#define ov_size ovu.ovu_size 9234192Sjdp}; 9334192Sjdp 9434192Sjdp#define MAGIC 0xef /* magic # on accounting info */ 9534192Sjdp#define RMAGIC 0x5555 /* magic # on range info */ 9634192Sjdp 9734192Sjdp#ifdef RCHECK 9834192Sjdp#define RSLOP sizeof (u_short) 9934192Sjdp#else 10034192Sjdp#define RSLOP 0 10134192Sjdp#endif 10234192Sjdp 10334192Sjdp/* 10434192Sjdp * nextf[i] is the pointer to the next free block of size 2^(i+3). The 10534192Sjdp * smallest allocatable block is 8 bytes. The overhead information 10634192Sjdp * precedes the data area returned to the user. 10734192Sjdp */ 10834192Sjdp#define NBUCKETS 30 10934192Sjdpstatic union overhead *nextf[NBUCKETS]; 11034192Sjdp 11134192Sjdpstatic int pagesz; /* page size */ 11234192Sjdpstatic int pagebucket; /* page size bucket */ 11334192Sjdp 11434192Sjdp#ifdef MSTATS 11534192Sjdp/* 11634192Sjdp * nmalloc[i] is the difference between the number of mallocs and frees 11734192Sjdp * for a given block size. 11834192Sjdp */ 11934192Sjdpstatic u_int nmalloc[NBUCKETS]; 12034192Sjdp#include <stdio.h> 12134192Sjdp#endif 12234192Sjdp 12334192Sjdp#if defined(MALLOC_DEBUG) || defined(RCHECK) 12434192Sjdp#define ASSERT(p) if (!(p)) botch("p") 12534192Sjdp#include <stdio.h> 12634192Sjdpstatic void 12734192Sjdpbotch(s) 12834192Sjdp char *s; 12934192Sjdp{ 13034192Sjdp fprintf(stderr, "\r\nassertion botched: %s\r\n", s); 13134192Sjdp (void) fflush(stderr); /* just in case user buffered it */ 13234192Sjdp abort(); 13334192Sjdp} 13434192Sjdp#else 13534192Sjdp#define ASSERT(p) 13634192Sjdp#endif 13734192Sjdp 13834192Sjdp/* Debugging stuff */ 139225152Skib#define TRACE() rtld_printf("TRACE %s:%d\n", __FILE__, __LINE__) 14034192Sjdp 141264346Salc/* 142264346Salc * The array of supported page sizes is provided by the user, i.e., the 143264346Salc * program that calls this storage allocator. That program must initialize 144264346Salc * the array before making its first call to allocate storage. The array 145264346Salc * must contain at least one page size. The page sizes must be stored in 146264346Salc * increasing order. 147264346Salc */ 148264346Salcextern size_t *pagesizes; 149211413Skib 15034192Sjdpvoid * 15134192Sjdpmalloc(nbytes) 15234192Sjdp size_t nbytes; 15334192Sjdp{ 15434192Sjdp register union overhead *op; 15538816Sdfr register int bucket; 15638816Sdfr register long n; 15734192Sjdp register unsigned amt; 15834192Sjdp 15934192Sjdp /* 16034192Sjdp * First time malloc is called, setup page size and 16134192Sjdp * align break pointer so all data will be page aligned. 16234192Sjdp */ 16334192Sjdp if (pagesz == 0) { 164264346Salc pagesz = n = pagesizes[0]; 16534192Sjdp if (morepages(NPOOLPAGES) == 0) 16634192Sjdp return NULL; 16734192Sjdp op = (union overhead *)(pagepool_start); 16838816Sdfr n = n - sizeof (*op) - ((long)op & (n - 1)); 16934192Sjdp if (n < 0) 17034192Sjdp n += pagesz; 17134192Sjdp if (n) { 17234192Sjdp pagepool_start += n; 17334192Sjdp } 17434192Sjdp bucket = 0; 17534192Sjdp amt = 8; 176114625Sobrien while ((unsigned)pagesz > amt) { 17734192Sjdp amt <<= 1; 17834192Sjdp bucket++; 17934192Sjdp } 18034192Sjdp pagebucket = bucket; 18134192Sjdp } 18234192Sjdp /* 18334192Sjdp * Convert amount of memory requested into closest block size 18434192Sjdp * stored in hash buckets which satisfies request. 18534192Sjdp * Account for space used per block for accounting. 18634192Sjdp */ 187114625Sobrien if (nbytes <= (unsigned long)(n = pagesz - sizeof (*op) - RSLOP)) { 18834192Sjdp#ifndef RCHECK 18934192Sjdp amt = 8; /* size of first bucket */ 19034192Sjdp bucket = 0; 19134192Sjdp#else 19234192Sjdp amt = 16; /* size of first bucket */ 19334192Sjdp bucket = 1; 19434192Sjdp#endif 19534192Sjdp n = -(sizeof (*op) + RSLOP); 19634192Sjdp } else { 19734192Sjdp amt = pagesz; 19834192Sjdp bucket = pagebucket; 19934192Sjdp } 20034192Sjdp while (nbytes > amt + n) { 20134192Sjdp amt <<= 1; 20234192Sjdp if (amt == 0) 20334192Sjdp return (NULL); 20434192Sjdp bucket++; 20534192Sjdp } 20634192Sjdp /* 20734192Sjdp * If nothing in hash bucket right now, 20834192Sjdp * request more memory from the system. 20934192Sjdp */ 21034192Sjdp if ((op = nextf[bucket]) == NULL) { 21134192Sjdp morecore(bucket); 21234192Sjdp if ((op = nextf[bucket]) == NULL) 21334192Sjdp return (NULL); 21434192Sjdp } 21534192Sjdp /* remove from linked list */ 21634192Sjdp nextf[bucket] = op->ov_next; 21734192Sjdp op->ov_magic = MAGIC; 21834192Sjdp op->ov_index = bucket; 21934192Sjdp#ifdef MSTATS 22034192Sjdp nmalloc[bucket]++; 22134192Sjdp#endif 22234192Sjdp#ifdef RCHECK 22334192Sjdp /* 22434192Sjdp * Record allocated size of block and 22534192Sjdp * bound space with magic numbers. 22634192Sjdp */ 227298292Spfg op->ov_size = roundup2(nbytes, RSLOP); 22834192Sjdp op->ov_rmagic = RMAGIC; 22934192Sjdp *(u_short *)((caddr_t)(op + 1) + op->ov_size) = RMAGIC; 23034192Sjdp#endif 23134192Sjdp return ((char *)(op + 1)); 23234192Sjdp} 23334192Sjdp 234154248Sjasonevoid * 235154248Sjasonecalloc(size_t num, size_t size) 236154248Sjasone{ 237154248Sjasone void *ret; 238154248Sjasone 239154248Sjasone if (size != 0 && (num * size) / size != num) { 240154248Sjasone /* size_t overflow. */ 241154248Sjasone return (NULL); 242154248Sjasone } 243154248Sjasone 244154248Sjasone if ((ret = malloc(num * size)) != NULL) 245154248Sjasone memset(ret, 0, num * size); 246154248Sjasone 247154248Sjasone return (ret); 248154248Sjasone} 249154248Sjasone 25034192Sjdp/* 25134192Sjdp * Allocate more memory to the indicated bucket. 25234192Sjdp */ 25334192Sjdpstatic void 25434192Sjdpmorecore(bucket) 25534192Sjdp int bucket; 25634192Sjdp{ 25734192Sjdp register union overhead *op; 25834192Sjdp register int sz; /* size of desired block */ 25934192Sjdp int amt; /* amount to allocate */ 26034192Sjdp int nblks; /* how many blocks we get */ 26134192Sjdp 26234192Sjdp /* 26334192Sjdp * sbrk_size <= 0 only for big, FLUFFY, requests (about 26434192Sjdp * 2^30 bytes on a VAX, I think) or for a negative arg. 26534192Sjdp */ 26634192Sjdp sz = 1 << (bucket + 3); 26734192Sjdp#ifdef MALLOC_DEBUG 26834192Sjdp ASSERT(sz > 0); 26934192Sjdp#else 27034192Sjdp if (sz <= 0) 27134192Sjdp return; 27234192Sjdp#endif 27334192Sjdp if (sz < pagesz) { 27434192Sjdp amt = pagesz; 27534192Sjdp nblks = amt / sz; 27634192Sjdp } else { 27734192Sjdp amt = sz + pagesz; 27834192Sjdp nblks = 1; 27934192Sjdp } 28034192Sjdp if (amt > pagepool_end - pagepool_start) 28134192Sjdp if (morepages(amt/pagesz + NPOOLPAGES) == 0) 28234192Sjdp return; 28334192Sjdp op = (union overhead *)pagepool_start; 28434192Sjdp pagepool_start += amt; 28534192Sjdp 28634192Sjdp /* 28734192Sjdp * Add new memory allocated to that on 28834192Sjdp * free list for this hash bucket. 28934192Sjdp */ 29034192Sjdp nextf[bucket] = op; 29134192Sjdp while (--nblks > 0) { 29234192Sjdp op->ov_next = (union overhead *)((caddr_t)op + sz); 29334192Sjdp op = (union overhead *)((caddr_t)op + sz); 29434192Sjdp } 29534192Sjdp} 29634192Sjdp 29734192Sjdpvoid 29834192Sjdpfree(cp) 29934192Sjdp void *cp; 30034192Sjdp{ 30134192Sjdp register int size; 30234192Sjdp register union overhead *op; 30334192Sjdp 30434192Sjdp if (cp == NULL) 30534192Sjdp return; 30634192Sjdp op = (union overhead *)((caddr_t)cp - sizeof (union overhead)); 30734192Sjdp#ifdef MALLOC_DEBUG 30834192Sjdp ASSERT(op->ov_magic == MAGIC); /* make sure it was in use */ 30934192Sjdp#else 31034192Sjdp if (op->ov_magic != MAGIC) 31134192Sjdp return; /* sanity */ 31234192Sjdp#endif 31334192Sjdp#ifdef RCHECK 31434192Sjdp ASSERT(op->ov_rmagic == RMAGIC); 31534192Sjdp ASSERT(*(u_short *)((caddr_t)(op + 1) + op->ov_size) == RMAGIC); 31634192Sjdp#endif 31734192Sjdp size = op->ov_index; 31834192Sjdp ASSERT(size < NBUCKETS); 31934192Sjdp op->ov_next = nextf[size]; /* also clobbers ov_magic */ 32034192Sjdp nextf[size] = op; 32134192Sjdp#ifdef MSTATS 32234192Sjdp nmalloc[size]--; 32334192Sjdp#endif 32434192Sjdp} 32534192Sjdp 32634192Sjdp/* 32734192Sjdp * When a program attempts "storage compaction" as mentioned in the 32834192Sjdp * old malloc man page, it realloc's an already freed block. Usually 32934192Sjdp * this is the last block it freed; occasionally it might be farther 33034192Sjdp * back. We have to search all the free lists for the block in order 331298897Spfg * to determine its bucket: 1st we make one pass through the lists 33234192Sjdp * checking only the first block in each; if that fails we search 33334192Sjdp * ``realloc_srchlen'' blocks in each list for a match (the variable 33434192Sjdp * is extern so the caller can modify it). If that fails we just copy 33534192Sjdp * however many bytes was given to realloc() and hope it's not huge. 33634192Sjdp */ 33734192Sjdpint realloc_srchlen = 4; /* 4 should be plenty, -1 =>'s whole list */ 33834192Sjdp 33934192Sjdpvoid * 34034192Sjdprealloc(cp, nbytes) 34134192Sjdp void *cp; 34234192Sjdp size_t nbytes; 34334192Sjdp{ 34434192Sjdp register u_int onb; 34534192Sjdp register int i; 34634192Sjdp union overhead *op; 34734192Sjdp char *res; 34834192Sjdp int was_alloced = 0; 34934192Sjdp 35034192Sjdp if (cp == NULL) 35134192Sjdp return (malloc(nbytes)); 35234192Sjdp op = (union overhead *)((caddr_t)cp - sizeof (union overhead)); 35334192Sjdp if (op->ov_magic == MAGIC) { 35434192Sjdp was_alloced++; 35534192Sjdp i = op->ov_index; 35634192Sjdp } else { 35734192Sjdp /* 35834192Sjdp * Already free, doing "compaction". 35934192Sjdp * 36034192Sjdp * Search for the old block of memory on the 36134192Sjdp * free list. First, check the most common 36234192Sjdp * case (last element free'd), then (this failing) 36334192Sjdp * the last ``realloc_srchlen'' items free'd. 36434192Sjdp * If all lookups fail, then assume the size of 36534192Sjdp * the memory block being realloc'd is the 36634192Sjdp * largest possible (so that all "nbytes" of new 36734192Sjdp * memory are copied into). Note that this could cause 36834192Sjdp * a memory fault if the old area was tiny, and the moon 36934192Sjdp * is gibbous. However, that is very unlikely. 37034192Sjdp */ 37134192Sjdp if ((i = findbucket(op, 1)) < 0 && 37234192Sjdp (i = findbucket(op, realloc_srchlen)) < 0) 37334192Sjdp i = NBUCKETS; 37434192Sjdp } 37534192Sjdp onb = 1 << (i + 3); 376114625Sobrien if (onb < (u_int)pagesz) 37734192Sjdp onb -= sizeof (*op) + RSLOP; 37834192Sjdp else 37934192Sjdp onb += pagesz - sizeof (*op) - RSLOP; 38034192Sjdp /* avoid the copy if same size block */ 38134192Sjdp if (was_alloced) { 38234192Sjdp if (i) { 38334192Sjdp i = 1 << (i + 2); 38434192Sjdp if (i < pagesz) 38534192Sjdp i -= sizeof (*op) + RSLOP; 38634192Sjdp else 38734192Sjdp i += pagesz - sizeof (*op) - RSLOP; 38834192Sjdp } 389114625Sobrien if (nbytes <= onb && nbytes > (size_t)i) { 39034192Sjdp#ifdef RCHECK 391298292Spfg op->ov_size = roundup2(nbytes, RSLOP); 39234192Sjdp *(u_short *)((caddr_t)(op + 1) + op->ov_size) = RMAGIC; 39334192Sjdp#endif 39434192Sjdp return(cp); 39534192Sjdp } else 39634192Sjdp free(cp); 39734192Sjdp } 39834192Sjdp if ((res = malloc(nbytes)) == NULL) 39934192Sjdp return (NULL); 40034192Sjdp if (cp != res) /* common optimization if "compacting" */ 40134192Sjdp bcopy(cp, res, (nbytes < onb) ? nbytes : onb); 40234192Sjdp return (res); 40334192Sjdp} 40434192Sjdp 40534192Sjdp/* 40634192Sjdp * Search ``srchlen'' elements of each free list for a block whose 40734192Sjdp * header starts at ``freep''. If srchlen is -1 search the whole list. 40834192Sjdp * Return bucket number, or -1 if not found. 40934192Sjdp */ 41034192Sjdpstatic int 41134192Sjdpfindbucket(freep, srchlen) 41234192Sjdp union overhead *freep; 41334192Sjdp int srchlen; 41434192Sjdp{ 41534192Sjdp register union overhead *p; 41634192Sjdp register int i, j; 41734192Sjdp 41834192Sjdp for (i = 0; i < NBUCKETS; i++) { 41934192Sjdp j = 0; 42034192Sjdp for (p = nextf[i]; p && j != srchlen; p = p->ov_next) { 42134192Sjdp if (p == freep) 42234192Sjdp return (i); 42334192Sjdp j++; 42434192Sjdp } 42534192Sjdp } 42634192Sjdp return (-1); 42734192Sjdp} 42834192Sjdp 42934192Sjdp#ifdef MSTATS 43034192Sjdp/* 43134192Sjdp * mstats - print out statistics about malloc 43234192Sjdp * 43334192Sjdp * Prints two lines of numbers, one showing the length of the free list 43434192Sjdp * for each size category, the second showing the number of mallocs - 43534192Sjdp * frees for each size category. 43634192Sjdp */ 43734192Sjdpmstats(s) 43834192Sjdp char *s; 43934192Sjdp{ 44034192Sjdp register int i, j; 44134192Sjdp register union overhead *p; 44234192Sjdp int totfree = 0, 44334192Sjdp totused = 0; 44434192Sjdp 44534192Sjdp fprintf(stderr, "Memory allocation statistics %s\nfree:\t", s); 44634192Sjdp for (i = 0; i < NBUCKETS; i++) { 44734192Sjdp for (j = 0, p = nextf[i]; p; p = p->ov_next, j++) 44834192Sjdp ; 44934192Sjdp fprintf(stderr, " %d", j); 45034192Sjdp totfree += j * (1 << (i + 3)); 45134192Sjdp } 45234192Sjdp fprintf(stderr, "\nused:\t"); 45334192Sjdp for (i = 0; i < NBUCKETS; i++) { 45434192Sjdp fprintf(stderr, " %d", nmalloc[i]); 45534192Sjdp totused += nmalloc[i] * (1 << (i + 3)); 45634192Sjdp } 45734192Sjdp fprintf(stderr, "\n\tTotal in use: %d, total free: %d\n", 45834192Sjdp totused, totfree); 45934192Sjdp} 46034192Sjdp#endif 46134192Sjdp 46234192Sjdp 46334192Sjdpstatic int 46434192Sjdpmorepages(n) 46534192Sjdpint n; 46634192Sjdp{ 46734192Sjdp int fd = -1; 46834192Sjdp int offset; 46934192Sjdp 47034192Sjdp if (pagepool_end - pagepool_start > pagesz) { 47134192Sjdp caddr_t addr = (caddr_t) 47238816Sdfr (((long)pagepool_start + pagesz - 1) & ~(pagesz - 1)); 47334192Sjdp if (munmap(addr, pagepool_end - addr) != 0) 474225152Skib rtld_fdprintf(STDERR_FILENO, "morepages: munmap %p", 475225152Skib addr); 47634192Sjdp } 47734192Sjdp 47838816Sdfr offset = (long)pagepool_start - ((long)pagepool_start & ~(pagesz - 1)); 47934192Sjdp 48034192Sjdp if ((pagepool_start = mmap(0, n * pagesz, 48134192Sjdp PROT_READ|PROT_WRITE, 48234192Sjdp MAP_ANON|MAP_COPY, fd, 0)) == (caddr_t)-1) { 483225152Skib rtld_printf("Cannot map anonymous memory\n"); 48434192Sjdp return 0; 48534192Sjdp } 48634192Sjdp pagepool_end = pagepool_start + n * pagesz; 48734192Sjdp pagepool_start += offset; 48834192Sjdp 48934192Sjdp return n; 49034192Sjdp} 491