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