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