1 /* 2 * Copyright (c) 1983 Regents of the University of California. 3 * All rights reserved. 4 * 5 * Redistribution and use in source and binary forms, with or without 6 * modification, are permitted provided that the following conditions 7 * are met: 8 * 1. Redistributions of source code must retain the above copyright 9 * notice, this list of conditions and the following disclaimer. 10 * 2. Redistributions in binary form must reproduce the above copyright 11 * notice, this list of conditions and the following disclaimer in the 12 * documentation and/or other materials provided with the distribution. 13 * 3. All advertising materials mentioning features or use of this software 14 * must display the following acknowledgement: 15 * This product includes software developed by the University of 16 * California, Berkeley and its contributors. 17 * 4. Neither the name of the University nor the names of its contributors 18 * may be used to endorse or promote products derived from this software 19 * without specific prior written permission. 20 * 21 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 22 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 23 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 24 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 25 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 26 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 27 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 28 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 29 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 30 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 31 * SUCH DAMAGE. 32 */ 33 34 #if defined(LIBC_SCCS) && !defined(lint) 35 /*static char *sccsid = "from: @(#)malloc.c 5.11 (Berkeley) 2/23/91";*/ 36 static char *rcsid = "$Id: malloc.c,v 1.3 1993/08/26 00:48:03 jtc Exp $"; 37 #endif /* LIBC_SCCS and not lint */ 38 39 /* 40 * malloc.c (Caltech) 2/21/82 41 * Chris Kingsley, kingsley@cit-20. 42 * 43 * This is a very fast storage allocator. It allocates blocks of a small 44 * number of different sizes, and keeps free lists of each size. Blocks that 45 * don't exactly fit are passed up to the next larger size. In this 46 * implementation, the available sizes are 2^n-4 (or 2^n-10) bytes long. 47 * This is designed for use in a virtual memory environment. 48 */ 49 50 #include <sys/types.h> 51 #include <stdlib.h> 52 #include <string.h> 53 #include <unistd.h> 54 55 #define NULL 0 56 57 static void morecore(); 58 static int findbucket(); 59 60 /* 61 * The overhead on a block is at least 4 bytes. When free, this space 62 * contains a pointer to the next free block, and the bottom two bits must 63 * be zero. When in use, the first byte is set to MAGIC, and the second 64 * byte is the size index. The remaining bytes are for alignment. 65 * If range checking is enabled then a second word holds the size of the 66 * requested block, less 1, rounded up to a multiple of sizeof(RMAGIC). 67 * The order of elements is critical: ov_magic must overlay the low order 68 * bits of ov_next, and ov_magic can not be a valid ov_next bit pattern. 69 */ 70 union overhead { 71 union overhead *ov_next; /* when free */ 72 struct { 73 u_char ovu_magic; /* magic number */ 74 u_char ovu_index; /* bucket # */ 75 #ifdef RCHECK 76 u_short ovu_rmagic; /* range magic number */ 77 u_int ovu_size; /* actual block size */ 78 #endif 79 } ovu; 80 #define ov_magic ovu.ovu_magic 81 #define ov_index ovu.ovu_index 82 #define ov_rmagic ovu.ovu_rmagic 83 #define ov_size ovu.ovu_size 84 }; 85 86 #define MAGIC 0xef /* magic # on accounting info */ 87 #define RMAGIC 0x5555 /* magic # on range info */ 88 89 #ifdef RCHECK 90 #define RSLOP sizeof (u_short) 91 #else 92 #define RSLOP 0 93 #endif 94 95 /* 96 * nextf[i] is the pointer to the next free block of size 2^(i+3). The 97 * smallest allocatable block is 8 bytes. The overhead information 98 * precedes the data area returned to the user. 99 */ 100 #define NBUCKETS 30 101 static union overhead *nextf[NBUCKETS]; 102 extern char *sbrk(); 103 104 static int pagesz; /* page size */ 105 static int pagebucket; /* page size bucket */ 106 107 #ifdef MSTATS 108 /* 109 * nmalloc[i] is the difference between the number of mallocs and frees 110 * for a given block size. 111 */ 112 static u_int nmalloc[NBUCKETS]; 113 #include <stdio.h> 114 #endif 115 116 #if defined(DEBUG) || defined(RCHECK) 117 #define ASSERT(p) if (!(p)) botch("p") 118 #include <stdio.h> 119 static 120 botch(s) 121 char *s; 122 { 123 fprintf(stderr, "\r\nassertion botched: %s\r\n", s); 124 (void) fflush(stderr); /* just in case user buffered it */ 125 abort(); 126 } 127 #else 128 #define ASSERT(p) 129 #endif 130 131 void * 132 malloc(nbytes) 133 size_t nbytes; 134 { 135 register union overhead *op; 136 register int bucket, n; 137 register unsigned amt; 138 139 /* 140 * First time malloc is called, setup page size and 141 * align break pointer so all data will be page aligned. 142 */ 143 if (pagesz == 0) { 144 pagesz = n = getpagesize(); 145 op = (union overhead *)sbrk(0); 146 n = n - sizeof (*op) - ((int)op & (n - 1)); 147 if (n < 0) 148 n += pagesz; 149 if (n) { 150 if (sbrk(n) == (char *)-1) 151 return (NULL); 152 } 153 bucket = 0; 154 amt = 8; 155 while (pagesz > amt) { 156 amt <<= 1; 157 bucket++; 158 } 159 pagebucket = bucket; 160 } 161 /* 162 * Convert amount of memory requested into closest block size 163 * stored in hash buckets which satisfies request. 164 * Account for space used per block for accounting. 165 */ 166 if (nbytes <= (n = pagesz - sizeof (*op) - RSLOP)) { 167 #ifndef RCHECK 168 amt = 8; /* size of first bucket */ 169 bucket = 0; 170 #else 171 amt = 16; /* size of first bucket */ 172 bucket = 1; 173 #endif 174 n = -(sizeof (*op) + RSLOP); 175 } else { 176 amt = pagesz; 177 bucket = pagebucket; 178 } 179 while (nbytes > amt + n) { 180 amt <<= 1; 181 if (amt == 0) 182 return (NULL); 183 bucket++; 184 } 185 /* 186 * If nothing in hash bucket right now, 187 * request more memory from the system. 188 */ 189 if ((op = nextf[bucket]) == NULL) { 190 morecore(bucket); 191 if ((op = nextf[bucket]) == NULL) 192 return (NULL); 193 } 194 /* remove from linked list */ 195 nextf[bucket] = op->ov_next; 196 op->ov_magic = MAGIC; 197 op->ov_index = bucket; 198 #ifdef MSTATS 199 nmalloc[bucket]++; 200 #endif 201 #ifdef RCHECK 202 /* 203 * Record allocated size of block and 204 * bound space with magic numbers. 205 */ 206 op->ov_size = (nbytes + RSLOP - 1) & ~(RSLOP - 1); 207 op->ov_rmagic = RMAGIC; 208 *(u_short *)((caddr_t)(op + 1) + op->ov_size) = RMAGIC; 209 #endif 210 return ((char *)(op + 1)); 211 } 212 213 /* 214 * Allocate more memory to the indicated bucket. 215 */ 216 static void 217 morecore(bucket) 218 int bucket; 219 { 220 register union overhead *op; 221 register int sz; /* size of desired block */ 222 int amt; /* amount to allocate */ 223 int nblks; /* how many blocks we get */ 224 225 /* 226 * sbrk_size <= 0 only for big, FLUFFY, requests (about 227 * 2^30 bytes on a VAX, I think) or for a negative arg. 228 */ 229 sz = 1 << (bucket + 3); 230 #ifdef DEBUG 231 ASSERT(sz > 0); 232 #else 233 if (sz <= 0) 234 return; 235 #endif 236 if (sz < pagesz) { 237 amt = pagesz; 238 nblks = amt / sz; 239 } else { 240 amt = sz + pagesz; 241 nblks = 1; 242 } 243 op = (union overhead *)sbrk(amt); 244 /* no more room! */ 245 if ((int)op == -1) 246 return; 247 /* 248 * Add new memory allocated to that on 249 * free list for this hash bucket. 250 */ 251 nextf[bucket] = op; 252 while (--nblks > 0) { 253 op->ov_next = (union overhead *)((caddr_t)op + sz); 254 op = (union overhead *)((caddr_t)op + sz); 255 } 256 } 257 258 void 259 free(cp) 260 void *cp; 261 { 262 register int size; 263 register union overhead *op; 264 265 if (cp == NULL) 266 return; 267 op = (union overhead *)((caddr_t)cp - sizeof (union overhead)); 268 #ifdef DEBUG 269 ASSERT(op->ov_magic == MAGIC); /* make sure it was in use */ 270 #else 271 if (op->ov_magic != MAGIC) 272 return; /* sanity */ 273 #endif 274 #ifdef RCHECK 275 ASSERT(op->ov_rmagic == RMAGIC); 276 ASSERT(*(u_short *)((caddr_t)(op + 1) + op->ov_size) == RMAGIC); 277 #endif 278 size = op->ov_index; 279 ASSERT(size < NBUCKETS); 280 op->ov_next = nextf[size]; /* also clobbers ov_magic */ 281 nextf[size] = op; 282 #ifdef MSTATS 283 nmalloc[size]--; 284 #endif 285 } 286 287 /* 288 * When a program attempts "storage compaction" as mentioned in the 289 * old malloc man page, it realloc's an already freed block. Usually 290 * this is the last block it freed; occasionally it might be farther 291 * back. We have to search all the free lists for the block in order 292 * to determine its bucket: 1st we make one pass thru the lists 293 * checking only the first block in each; if that fails we search 294 * ``realloc_srchlen'' blocks in each list for a match (the variable 295 * is extern so the caller can modify it). If that fails we just copy 296 * however many bytes was given to realloc() and hope it's not huge. 297 */ 298 int realloc_srchlen = 4; /* 4 should be plenty, -1 =>'s whole list */ 299 300 void * 301 realloc(cp, nbytes) 302 void *cp; 303 size_t nbytes; 304 { 305 register u_int onb; 306 register int i; 307 union overhead *op; 308 char *res; 309 int was_alloced = 0; 310 311 if (cp == NULL) 312 return (malloc(nbytes)); 313 op = (union overhead *)((caddr_t)cp - sizeof (union overhead)); 314 if (op->ov_magic == MAGIC) { 315 was_alloced++; 316 i = op->ov_index; 317 } else { 318 /* 319 * Already free, doing "compaction". 320 * 321 * Search for the old block of memory on the 322 * free list. First, check the most common 323 * case (last element free'd), then (this failing) 324 * the last ``realloc_srchlen'' items free'd. 325 * If all lookups fail, then assume the size of 326 * the memory block being realloc'd is the 327 * largest possible (so that all "nbytes" of new 328 * memory are copied into). Note that this could cause 329 * a memory fault if the old area was tiny, and the moon 330 * is gibbous. However, that is very unlikely. 331 */ 332 if ((i = findbucket(op, 1)) < 0 && 333 (i = findbucket(op, realloc_srchlen)) < 0) 334 i = NBUCKETS; 335 } 336 onb = 1 << (i + 3); 337 if (onb < pagesz) 338 onb -= sizeof (*op) + RSLOP; 339 else 340 onb += pagesz - sizeof (*op) - RSLOP; 341 /* avoid the copy if same size block */ 342 if (was_alloced) { 343 if (i) { 344 i = 1 << (i + 2); 345 if (i < pagesz) 346 i -= sizeof (*op) + RSLOP; 347 else 348 i += pagesz - sizeof (*op) - RSLOP; 349 } 350 if (nbytes <= onb && nbytes > i) { 351 #ifdef RCHECK 352 op->ov_size = (nbytes + RSLOP - 1) & ~(RSLOP - 1); 353 *(u_short *)((caddr_t)(op + 1) + op->ov_size) = RMAGIC; 354 #endif 355 return(cp); 356 } else 357 free(cp); 358 } 359 if ((res = malloc(nbytes)) == NULL) 360 return (NULL); 361 if (cp != res) /* common optimization if "compacting" */ 362 bcopy(cp, res, (nbytes < onb) ? nbytes : onb); 363 return (res); 364 } 365 366 /* 367 * Search ``srchlen'' elements of each free list for a block whose 368 * header starts at ``freep''. If srchlen is -1 search the whole list. 369 * Return bucket number, or -1 if not found. 370 */ 371 static 372 findbucket(freep, srchlen) 373 union overhead *freep; 374 int srchlen; 375 { 376 register union overhead *p; 377 register int i, j; 378 379 for (i = 0; i < NBUCKETS; i++) { 380 j = 0; 381 for (p = nextf[i]; p && j != srchlen; p = p->ov_next) { 382 if (p == freep) 383 return (i); 384 j++; 385 } 386 } 387 return (-1); 388 } 389 390 #ifdef MSTATS 391 /* 392 * mstats - print out statistics about malloc 393 * 394 * Prints two lines of numbers, one showing the length of the free list 395 * for each size category, the second showing the number of mallocs - 396 * frees for each size category. 397 */ 398 mstats(s) 399 char *s; 400 { 401 register int i, j; 402 register union overhead *p; 403 int totfree = 0, 404 totused = 0; 405 406 fprintf(stderr, "Memory allocation statistics %s\nfree:\t", s); 407 for (i = 0; i < NBUCKETS; i++) { 408 for (j = 0, p = nextf[i]; p; p = p->ov_next, j++) 409 ; 410 fprintf(stderr, " %d", j); 411 totfree += j * (1 << (i + 3)); 412 } 413 fprintf(stderr, "\nused:\t"); 414 for (i = 0; i < NBUCKETS; i++) { 415 fprintf(stderr, " %d", nmalloc[i]); 416 totused += nmalloc[i] * (1 << (i + 3)); 417 } 418 fprintf(stderr, "\n\tTotal in use: %d, total free: %d\n", 419 totused, totfree); 420 } 421 #endif 422