1*0Sstevel@tonic-gate /* 2*0Sstevel@tonic-gate * Copyright 2004 Sun Microsystems, Inc. All rights reserved. 3*0Sstevel@tonic-gate * Use is subject to license terms. 4*0Sstevel@tonic-gate */ 5*0Sstevel@tonic-gate 6*0Sstevel@tonic-gate #pragma ident "%Z%%M% %I% %E% SMI" 7*0Sstevel@tonic-gate /* 8*0Sstevel@tonic-gate * wizard:/space/4.3reno/usr/src/lib/libc/stdlib/malloc.c 9*0Sstevel@tonic-gate * Copyright (c) 1983 Regents of the University of California. 10*0Sstevel@tonic-gate * All rights reserved. 11*0Sstevel@tonic-gate * 12*0Sstevel@tonic-gate * Redistribution and use in source and binary forms are permitted 13*0Sstevel@tonic-gate * provided that: (1) source distributions retain this entire copyright 14*0Sstevel@tonic-gate * notice and comment, and (2) distributions including binaries display 15*0Sstevel@tonic-gate * the following acknowledgement: ``This product includes software 16*0Sstevel@tonic-gate * developed by the University of California, Berkeley and its contributors'' 17*0Sstevel@tonic-gate * in the documentation or other materials provided with the distribution 18*0Sstevel@tonic-gate * and in all advertising materials mentioning features or use of this 19*0Sstevel@tonic-gate * software. Neither the name of the University nor the names of its 20*0Sstevel@tonic-gate * contributors may be used to endorse or promote products derived 21*0Sstevel@tonic-gate * from this software without specific prior written permission. 22*0Sstevel@tonic-gate * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR 23*0Sstevel@tonic-gate * IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED 24*0Sstevel@tonic-gate * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. 25*0Sstevel@tonic-gate */ 26*0Sstevel@tonic-gate 27*0Sstevel@tonic-gate /* 28*0Sstevel@tonic-gate * malloc.c (Caltech) 2/21/82 29*0Sstevel@tonic-gate * Chris Kingsley, kingsley@cit-20. 30*0Sstevel@tonic-gate * 31*0Sstevel@tonic-gate * This is a very fast storage allocator. It allocates blocks of a small 32*0Sstevel@tonic-gate * number of different sizes, and keeps free lists of each size. Blocks that 33*0Sstevel@tonic-gate * don't exactly fit are passed up to the next larger size. In this 34*0Sstevel@tonic-gate * implementation, the available sizes are 2^n-4 bytes long (ILP32) 35*0Sstevel@tonic-gate * or 2^n-8 bytes long (LP64). 36*0Sstevel@tonic-gate */ 37*0Sstevel@tonic-gate 38*0Sstevel@tonic-gate /*LINTLIBRARY*/ 39*0Sstevel@tonic-gate #include <sys/types.h> 40*0Sstevel@tonic-gate #include <stdlib.h> 41*0Sstevel@tonic-gate #include <unistd.h> 42*0Sstevel@tonic-gate #include <string.h> 43*0Sstevel@tonic-gate #include <limits.h> 44*0Sstevel@tonic-gate 45*0Sstevel@tonic-gate /* 46*0Sstevel@tonic-gate * The overhead on a block is at least 4 bytes. When free, this space 47*0Sstevel@tonic-gate * contains a pointer to the next free block, and the bottom two bits must 48*0Sstevel@tonic-gate * be zero. When in use, the first byte is set to MAGIC, and the second 49*0Sstevel@tonic-gate * byte is the size index. The remaining bytes are for alignment. 50*0Sstevel@tonic-gate * The order of elements is critical: ov_magic must overlay the low order 51*0Sstevel@tonic-gate * bits of ov_next, and ov_magic can not be a valid ov_next bit pattern. 52*0Sstevel@tonic-gate * Overhead is 4 bytes for ILP32, 8 bytes for LP64 53*0Sstevel@tonic-gate */ 54*0Sstevel@tonic-gate union overhead { 55*0Sstevel@tonic-gate union overhead *ov_next; /* when free */ 56*0Sstevel@tonic-gate struct { 57*0Sstevel@tonic-gate #if defined(_LITTLE_ENDIAN) 58*0Sstevel@tonic-gate uchar_t ovu_magic; /* magic number */ 59*0Sstevel@tonic-gate uchar_t ovu_index; /* bucket # */ 60*0Sstevel@tonic-gate uchar_t ovu_pad[sizeof (union overhead *) - 2]; 61*0Sstevel@tonic-gate #elif defined(_BIG_ENDIAN) 62*0Sstevel@tonic-gate uchar_t ovu_pad[sizeof (union overhead *) - 2]; 63*0Sstevel@tonic-gate uchar_t ovu_index; /* bucket # */ 64*0Sstevel@tonic-gate uchar_t ovu_magic; /* magic number */ 65*0Sstevel@tonic-gate #else 66*0Sstevel@tonic-gate #error "Endianness is not defined" 67*0Sstevel@tonic-gate #endif 68*0Sstevel@tonic-gate } ovu; 69*0Sstevel@tonic-gate }; 70*0Sstevel@tonic-gate 71*0Sstevel@tonic-gate #define ov_magic ovu.ovu_magic 72*0Sstevel@tonic-gate #define ov_index ovu.ovu_index 73*0Sstevel@tonic-gate 74*0Sstevel@tonic-gate #define MAGIC 0xef /* magic # on accounting info */ 75*0Sstevel@tonic-gate 76*0Sstevel@tonic-gate /* 77*0Sstevel@tonic-gate * nextf[i] is the pointer to the next free block of size 2^(i+EXP). 78*0Sstevel@tonic-gate * The smallest allocatable block is 8 bytes (ILP32) or 16 bytes (LP64). 79*0Sstevel@tonic-gate * The overhead information precedes the data area returned to the user. 80*0Sstevel@tonic-gate */ 81*0Sstevel@tonic-gate #ifdef _LP64 82*0Sstevel@tonic-gate #define EXP 4 83*0Sstevel@tonic-gate #define NBUCKETS 60 84*0Sstevel@tonic-gate #else 85*0Sstevel@tonic-gate #define EXP 3 86*0Sstevel@tonic-gate #define NBUCKETS 29 87*0Sstevel@tonic-gate #endif 88*0Sstevel@tonic-gate static union overhead *nextf[NBUCKETS]; 89*0Sstevel@tonic-gate 90*0Sstevel@tonic-gate static int pagesz; /* page size */ 91*0Sstevel@tonic-gate static long sbrk_adjust; /* in case sbrk() does alignment */ 92*0Sstevel@tonic-gate static int pagebucket; /* page size bucket */ 93*0Sstevel@tonic-gate static void morecore(int); 94*0Sstevel@tonic-gate static int findbucket(union overhead *, int); 95*0Sstevel@tonic-gate 96*0Sstevel@tonic-gate void * 97*0Sstevel@tonic-gate malloc(size_t nbytes) 98*0Sstevel@tonic-gate { 99*0Sstevel@tonic-gate union overhead *op; 100*0Sstevel@tonic-gate int bucket; 101*0Sstevel@tonic-gate ssize_t n; 102*0Sstevel@tonic-gate size_t amt; 103*0Sstevel@tonic-gate 104*0Sstevel@tonic-gate /* 105*0Sstevel@tonic-gate * First time malloc is called, setup page size and 106*0Sstevel@tonic-gate * align break pointer so all data will be page aligned. 107*0Sstevel@tonic-gate */ 108*0Sstevel@tonic-gate if (pagesz == 0) { 109*0Sstevel@tonic-gate pagesz = getpagesize(); 110*0Sstevel@tonic-gate op = sbrk(0); 111*0Sstevel@tonic-gate n = pagesz - sizeof (*op) - ((uintptr_t)op & (pagesz - 1)); 112*0Sstevel@tonic-gate if (n < 0) 113*0Sstevel@tonic-gate n += pagesz; 114*0Sstevel@tonic-gate if (n) { 115*0Sstevel@tonic-gate if (sbrk(n) == (void *)-1) 116*0Sstevel@tonic-gate return (NULL); 117*0Sstevel@tonic-gate /* 118*0Sstevel@tonic-gate * We were careful to arrange that 119*0Sstevel@tonic-gate * sbrk(0) + sizeof (union overhead) 120*0Sstevel@tonic-gate * should end up on a page boundary. 121*0Sstevel@tonic-gate * If the underlying sbrk() performs alignment 122*0Sstevel@tonic-gate * then this is false. We compute the adjustment. 123*0Sstevel@tonic-gate */ 124*0Sstevel@tonic-gate op = sbrk(0); 125*0Sstevel@tonic-gate sbrk_adjust = (uintptr_t)(op + 1) & (pagesz - 1); 126*0Sstevel@tonic-gate } else { 127*0Sstevel@tonic-gate sbrk_adjust = 0; 128*0Sstevel@tonic-gate } 129*0Sstevel@tonic-gate bucket = 0; 130*0Sstevel@tonic-gate amt = (1UL << EXP); 131*0Sstevel@tonic-gate while (pagesz > amt) { 132*0Sstevel@tonic-gate amt <<= 1; 133*0Sstevel@tonic-gate bucket++; 134*0Sstevel@tonic-gate } 135*0Sstevel@tonic-gate pagebucket = bucket; 136*0Sstevel@tonic-gate } 137*0Sstevel@tonic-gate /* 138*0Sstevel@tonic-gate * Convert amount of memory requested into closest block size 139*0Sstevel@tonic-gate * stored in hash buckets which satisfies request. 140*0Sstevel@tonic-gate * Account for space used per block for accounting. 141*0Sstevel@tonic-gate */ 142*0Sstevel@tonic-gate if (nbytes <= (n = pagesz - sizeof (*op))) { 143*0Sstevel@tonic-gate amt = (1UL << EXP); /* size of first bucket */ 144*0Sstevel@tonic-gate bucket = 0; 145*0Sstevel@tonic-gate n = -(ssize_t)(sizeof (*op)); 146*0Sstevel@tonic-gate } else { 147*0Sstevel@tonic-gate amt = pagesz; 148*0Sstevel@tonic-gate bucket = pagebucket; 149*0Sstevel@tonic-gate } 150*0Sstevel@tonic-gate while (nbytes > amt + n) { 151*0Sstevel@tonic-gate amt <<= 1; 152*0Sstevel@tonic-gate if (amt == 0) 153*0Sstevel@tonic-gate return (NULL); 154*0Sstevel@tonic-gate bucket++; 155*0Sstevel@tonic-gate } 156*0Sstevel@tonic-gate /* 157*0Sstevel@tonic-gate * If nothing in hash bucket right now, 158*0Sstevel@tonic-gate * request more memory from the system. 159*0Sstevel@tonic-gate */ 160*0Sstevel@tonic-gate if ((op = nextf[bucket]) == NULL) { 161*0Sstevel@tonic-gate morecore(bucket); 162*0Sstevel@tonic-gate if ((op = nextf[bucket]) == NULL) 163*0Sstevel@tonic-gate return (NULL); 164*0Sstevel@tonic-gate } 165*0Sstevel@tonic-gate /* remove from linked list */ 166*0Sstevel@tonic-gate nextf[bucket] = op->ov_next; 167*0Sstevel@tonic-gate op->ov_magic = MAGIC; 168*0Sstevel@tonic-gate op->ov_index = (uchar_t)bucket; 169*0Sstevel@tonic-gate return (op + 1); 170*0Sstevel@tonic-gate } 171*0Sstevel@tonic-gate 172*0Sstevel@tonic-gate /* 173*0Sstevel@tonic-gate * Allocate more memory to the indicated bucket. 174*0Sstevel@tonic-gate */ 175*0Sstevel@tonic-gate static void 176*0Sstevel@tonic-gate morecore(int bucket) 177*0Sstevel@tonic-gate { 178*0Sstevel@tonic-gate union overhead *op; 179*0Sstevel@tonic-gate size_t sz; /* size of desired block */ 180*0Sstevel@tonic-gate ssize_t amt; /* amount to allocate */ 181*0Sstevel@tonic-gate long nblks; /* how many blocks we get */ 182*0Sstevel@tonic-gate 183*0Sstevel@tonic-gate sz = 1UL << (bucket + EXP); 184*0Sstevel@tonic-gate if (sz == 0) 185*0Sstevel@tonic-gate return; 186*0Sstevel@tonic-gate if (sz < pagesz) { 187*0Sstevel@tonic-gate amt = pagesz; 188*0Sstevel@tonic-gate nblks = amt / sz; 189*0Sstevel@tonic-gate } else { 190*0Sstevel@tonic-gate amt = sz + pagesz; 191*0Sstevel@tonic-gate nblks = 1; 192*0Sstevel@tonic-gate } 193*0Sstevel@tonic-gate if (amt <= 0) 194*0Sstevel@tonic-gate return; 195*0Sstevel@tonic-gate if (amt > LONG_MAX) { 196*0Sstevel@tonic-gate intptr_t delta; 197*0Sstevel@tonic-gate /* 198*0Sstevel@tonic-gate * the value required is too big for sbrk() to deal with 199*0Sstevel@tonic-gate * in one go, so use sbrk() at most 2 times instead. 200*0Sstevel@tonic-gate */ 201*0Sstevel@tonic-gate op = sbrk(0); 202*0Sstevel@tonic-gate delta = LONG_MAX; 203*0Sstevel@tonic-gate while (delta > 0) { 204*0Sstevel@tonic-gate if (sbrk(delta) == (void *)-1) { 205*0Sstevel@tonic-gate if (op != sbrk(0)) 206*0Sstevel@tonic-gate (void) sbrk(-LONG_MAX); 207*0Sstevel@tonic-gate return; 208*0Sstevel@tonic-gate } 209*0Sstevel@tonic-gate amt -= LONG_MAX; 210*0Sstevel@tonic-gate delta = amt; 211*0Sstevel@tonic-gate } 212*0Sstevel@tonic-gate } 213*0Sstevel@tonic-gate else 214*0Sstevel@tonic-gate op = sbrk(amt); 215*0Sstevel@tonic-gate /* no more room! */ 216*0Sstevel@tonic-gate if (op == (union overhead *)-1) 217*0Sstevel@tonic-gate return; 218*0Sstevel@tonic-gate /* LINTED improper alignment */ 219*0Sstevel@tonic-gate op = (union overhead *)((caddr_t)op - sbrk_adjust); 220*0Sstevel@tonic-gate /* 221*0Sstevel@tonic-gate * Add new memory allocated to that on 222*0Sstevel@tonic-gate * free list for this hash bucket. 223*0Sstevel@tonic-gate */ 224*0Sstevel@tonic-gate nextf[bucket] = op; 225*0Sstevel@tonic-gate while (--nblks > 0) { 226*0Sstevel@tonic-gate /* LINTED improper alignment */ 227*0Sstevel@tonic-gate op->ov_next = (union overhead *)((caddr_t)op + sz); 228*0Sstevel@tonic-gate /* LINTED improper alignment */ 229*0Sstevel@tonic-gate op = (union overhead *)((caddr_t)op + sz); 230*0Sstevel@tonic-gate } 231*0Sstevel@tonic-gate } 232*0Sstevel@tonic-gate 233*0Sstevel@tonic-gate void 234*0Sstevel@tonic-gate free(void *cp) 235*0Sstevel@tonic-gate { 236*0Sstevel@tonic-gate int size; 237*0Sstevel@tonic-gate union overhead *op; 238*0Sstevel@tonic-gate 239*0Sstevel@tonic-gate if (cp == NULL) 240*0Sstevel@tonic-gate return; 241*0Sstevel@tonic-gate /* LINTED improper alignment */ 242*0Sstevel@tonic-gate op = (union overhead *)((caddr_t)cp - sizeof (union overhead)); 243*0Sstevel@tonic-gate if (op->ov_magic != MAGIC) 244*0Sstevel@tonic-gate return; /* previously freed? */ 245*0Sstevel@tonic-gate size = op->ov_index; 246*0Sstevel@tonic-gate op->ov_next = nextf[size]; /* also clobbers ov_magic */ 247*0Sstevel@tonic-gate nextf[size] = op; 248*0Sstevel@tonic-gate } 249*0Sstevel@tonic-gate 250*0Sstevel@tonic-gate /* 251*0Sstevel@tonic-gate * When a program attempts "storage compaction" as mentioned in the 252*0Sstevel@tonic-gate * old malloc man page, it realloc's an already freed block. Usually 253*0Sstevel@tonic-gate * this is the last block it freed; occasionally it might be farther 254*0Sstevel@tonic-gate * back. We have to search all the free lists for the block in order 255*0Sstevel@tonic-gate * to determine its bucket: 1st we make one pass thru the lists 256*0Sstevel@tonic-gate * checking only the first block in each; if that fails we search 257*0Sstevel@tonic-gate * ``realloc_srchlen'' blocks in each list for a match (the variable 258*0Sstevel@tonic-gate * is extern so the caller can modify it). If that fails we just copy 259*0Sstevel@tonic-gate * however many bytes was given to realloc() and hope it's not huge. 260*0Sstevel@tonic-gate */ 261*0Sstevel@tonic-gate int realloc_srchlen = 4; /* 4 should be plenty, -1 =>'s whole list */ 262*0Sstevel@tonic-gate 263*0Sstevel@tonic-gate void * 264*0Sstevel@tonic-gate realloc(void *cp, size_t nbytes) 265*0Sstevel@tonic-gate { 266*0Sstevel@tonic-gate size_t onb; 267*0Sstevel@tonic-gate int i; 268*0Sstevel@tonic-gate union overhead *op; 269*0Sstevel@tonic-gate char *res; 270*0Sstevel@tonic-gate int was_alloced = 0; 271*0Sstevel@tonic-gate 272*0Sstevel@tonic-gate if (cp == NULL) 273*0Sstevel@tonic-gate return (malloc(nbytes)); 274*0Sstevel@tonic-gate /* LINTED improper alignment */ 275*0Sstevel@tonic-gate op = (union overhead *)((caddr_t)cp - sizeof (union overhead)); 276*0Sstevel@tonic-gate if (op->ov_magic == MAGIC) { 277*0Sstevel@tonic-gate was_alloced++; 278*0Sstevel@tonic-gate i = op->ov_index; 279*0Sstevel@tonic-gate } else { 280*0Sstevel@tonic-gate /* 281*0Sstevel@tonic-gate * Already free, doing "compaction". 282*0Sstevel@tonic-gate * 283*0Sstevel@tonic-gate * Search for the old block of memory on the 284*0Sstevel@tonic-gate * free list. First, check the most common 285*0Sstevel@tonic-gate * case (last element free'd), then (this failing) 286*0Sstevel@tonic-gate * the last ``realloc_srchlen'' items free'd. 287*0Sstevel@tonic-gate * If all lookups fail, then just malloc() the 288*0Sstevel@tonic-gate * space and copy the size of the new space. 289*0Sstevel@tonic-gate */ 290*0Sstevel@tonic-gate if ((i = findbucket(op, 1)) < 0 && 291*0Sstevel@tonic-gate (i = findbucket(op, realloc_srchlen)) < 0) { 292*0Sstevel@tonic-gate if ((res = malloc(nbytes)) != NULL) 293*0Sstevel@tonic-gate (void) memmove(res, cp, nbytes); 294*0Sstevel@tonic-gate return (res); 295*0Sstevel@tonic-gate } 296*0Sstevel@tonic-gate } 297*0Sstevel@tonic-gate onb = 1UL << (i + EXP); 298*0Sstevel@tonic-gate if (onb < pagesz) 299*0Sstevel@tonic-gate onb -= sizeof (*op); 300*0Sstevel@tonic-gate else 301*0Sstevel@tonic-gate onb += pagesz - sizeof (*op); 302*0Sstevel@tonic-gate /* avoid the copy if same size block */ 303*0Sstevel@tonic-gate if (was_alloced) { 304*0Sstevel@tonic-gate size_t sz = 0; 305*0Sstevel@tonic-gate if (i) { 306*0Sstevel@tonic-gate sz = 1UL << (i + EXP - 1); 307*0Sstevel@tonic-gate if (sz < pagesz) 308*0Sstevel@tonic-gate sz -= sizeof (*op); 309*0Sstevel@tonic-gate else 310*0Sstevel@tonic-gate sz += pagesz - sizeof (*op); 311*0Sstevel@tonic-gate } 312*0Sstevel@tonic-gate if (nbytes <= onb && nbytes > sz) { 313*0Sstevel@tonic-gate return (cp); 314*0Sstevel@tonic-gate } else 315*0Sstevel@tonic-gate free(cp); 316*0Sstevel@tonic-gate } 317*0Sstevel@tonic-gate if ((res = malloc(nbytes)) == NULL) 318*0Sstevel@tonic-gate return (NULL); 319*0Sstevel@tonic-gate if (cp != res) /* common optimization if "compacting" */ 320*0Sstevel@tonic-gate (void) memmove(res, cp, (nbytes < onb) ? nbytes : onb); 321*0Sstevel@tonic-gate return (res); 322*0Sstevel@tonic-gate } 323*0Sstevel@tonic-gate 324*0Sstevel@tonic-gate /* 325*0Sstevel@tonic-gate * Search ``srchlen'' elements of each free list for a block whose 326*0Sstevel@tonic-gate * header starts at ``freep''. If srchlen is -1 search the whole list. 327*0Sstevel@tonic-gate * Return bucket number, or -1 if not found. 328*0Sstevel@tonic-gate */ 329*0Sstevel@tonic-gate static int 330*0Sstevel@tonic-gate findbucket(union overhead *freep, int srchlen) 331*0Sstevel@tonic-gate { 332*0Sstevel@tonic-gate union overhead *p; 333*0Sstevel@tonic-gate int i, j; 334*0Sstevel@tonic-gate 335*0Sstevel@tonic-gate for (i = 0; i < NBUCKETS; i++) { 336*0Sstevel@tonic-gate j = 0; 337*0Sstevel@tonic-gate for (p = nextf[i]; p && j != srchlen; p = p->ov_next) { 338*0Sstevel@tonic-gate if (p == freep) 339*0Sstevel@tonic-gate return (i); 340*0Sstevel@tonic-gate j++; 341*0Sstevel@tonic-gate } 342*0Sstevel@tonic-gate } 343*0Sstevel@tonic-gate return (-1); 344*0Sstevel@tonic-gate } 345