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