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.9 (Berkeley) 06/01/90"; 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 morecore(bucket) 184 int bucket; 185 { 186 register union overhead *op; 187 register int sz; /* size of desired block */ 188 int amt; /* amount to allocate */ 189 int nblks; /* how many blocks we get */ 190 191 /* 192 * sbrk_size <= 0 only for big, FLUFFY, requests (about 193 * 2^30 bytes on a VAX, I think) or for a negative arg. 194 */ 195 sz = 1 << (bucket + 3); 196 #ifdef DEBUG 197 ASSERT(sz > 0); 198 #else 199 if (sz <= 0) 200 return; 201 #endif 202 if (sz < pagesz) { 203 amt = pagesz; 204 nblks = amt / sz; 205 } else { 206 amt = sz + pagesz; 207 nblks = 1; 208 } 209 op = (union overhead *)sbrk(amt); 210 /* no more room! */ 211 if ((int)op == -1) 212 return; 213 /* 214 * Add new memory allocated to that on 215 * free list for this hash bucket. 216 */ 217 nextf[bucket] = op; 218 while (--nblks > 0) { 219 op->ov_next = (union overhead *)((caddr_t)op + sz); 220 op = (union overhead *)((caddr_t)op + sz); 221 } 222 } 223 224 free(cp) 225 char *cp; 226 { 227 register int size; 228 register union overhead *op; 229 230 if (cp == NULL) 231 return; 232 op = (union overhead *)((caddr_t)cp - sizeof (union overhead)); 233 #ifdef DEBUG 234 ASSERT(op->ov_magic == MAGIC); /* make sure it was in use */ 235 #else 236 if (op->ov_magic != MAGIC) 237 return; /* sanity */ 238 #endif 239 #ifdef RCHECK 240 ASSERT(op->ov_rmagic == RMAGIC); 241 ASSERT(*(u_short *)((caddr_t)(op + 1) + op->ov_size) == RMAGIC); 242 #endif 243 size = op->ov_index; 244 ASSERT(size < NBUCKETS); 245 op->ov_next = nextf[size]; /* also clobbers ov_magic */ 246 nextf[size] = op; 247 #ifdef MSTATS 248 nmalloc[size]--; 249 #endif 250 } 251 252 /* 253 * When a program attempts "storage compaction" as mentioned in the 254 * old malloc man page, it realloc's an already freed block. Usually 255 * this is the last block it freed; occasionally it might be farther 256 * back. We have to search all the free lists for the block in order 257 * to determine its bucket: 1st we make one pass thru the lists 258 * checking only the first block in each; if that fails we search 259 * ``realloc_srchlen'' blocks in each list for a match (the variable 260 * is extern so the caller can modify it). If that fails we just copy 261 * however many bytes was given to realloc() and hope it's not huge. 262 */ 263 int realloc_srchlen = 4; /* 4 should be plenty, -1 =>'s whole list */ 264 265 char * 266 realloc(cp, nbytes) 267 char *cp; 268 unsigned nbytes; 269 { 270 register u_int onb; 271 register int i; 272 union overhead *op; 273 char *res; 274 int was_alloced = 0; 275 276 if (cp == NULL) 277 return (malloc(nbytes)); 278 op = (union overhead *)((caddr_t)cp - sizeof (union overhead)); 279 if (op->ov_magic == MAGIC) { 280 was_alloced++; 281 i = op->ov_index; 282 } else { 283 /* 284 * Already free, doing "compaction". 285 * 286 * Search for the old block of memory on the 287 * free list. First, check the most common 288 * case (last element free'd), then (this failing) 289 * the last ``realloc_srchlen'' items free'd. 290 * If all lookups fail, then assume the size of 291 * the memory block being realloc'd is the 292 * largest possible (so that all "nbytes" of new 293 * memory are copied into). Note that this could cause 294 * a memory fault if the old area was tiny, and the moon 295 * is gibbous. However, that is very unlikely. 296 */ 297 if ((i = findbucket(op, 1)) < 0 && 298 (i = findbucket(op, realloc_srchlen)) < 0) 299 i = NBUCKETS; 300 } 301 onb = 1 << (i + 3); 302 if (onb < pagesz) 303 onb -= sizeof (*op) + RSLOP; 304 else 305 onb += pagesz - sizeof (*op) - RSLOP; 306 /* avoid the copy if same size block */ 307 if (was_alloced) { 308 if (i) { 309 i = 1 << (i + 2); 310 if (i < pagesz) 311 i -= sizeof (*op) + RSLOP; 312 else 313 i += pagesz - sizeof (*op) - RSLOP; 314 } 315 if (nbytes <= onb && nbytes > i) { 316 #ifdef RCHECK 317 op->ov_size = (nbytes + RSLOP - 1) & ~(RSLOP - 1); 318 *(u_short *)((caddr_t)(op + 1) + op->ov_size) = RMAGIC; 319 #endif 320 return(cp); 321 } else 322 free(cp); 323 } 324 if ((res = malloc(nbytes)) == NULL) 325 return (NULL); 326 if (cp != res) /* common optimization if "compacting" */ 327 bcopy(cp, res, (nbytes < onb) ? nbytes : onb); 328 return (res); 329 } 330 331 /* 332 * Search ``srchlen'' elements of each free list for a block whose 333 * header starts at ``freep''. If srchlen is -1 search the whole list. 334 * Return bucket number, or -1 if not found. 335 */ 336 static 337 findbucket(freep, srchlen) 338 union overhead *freep; 339 int srchlen; 340 { 341 register union overhead *p; 342 register int i, j; 343 344 for (i = 0; i < NBUCKETS; i++) { 345 j = 0; 346 for (p = nextf[i]; p && j != srchlen; p = p->ov_next) { 347 if (p == freep) 348 return (i); 349 j++; 350 } 351 } 352 return (-1); 353 } 354 355 #ifdef MSTATS 356 /* 357 * mstats - print out statistics about malloc 358 * 359 * Prints two lines of numbers, one showing the length of the free list 360 * for each size category, the second showing the number of mallocs - 361 * frees for each size category. 362 */ 363 mstats(s) 364 char *s; 365 { 366 register int i, j; 367 register union overhead *p; 368 int totfree = 0, 369 totused = 0; 370 371 fprintf(stderr, "Memory allocation statistics %s\nfree:\t", s); 372 for (i = 0; i < NBUCKETS; i++) { 373 for (j = 0, p = nextf[i]; p; p = p->ov_next, j++) 374 ; 375 fprintf(stderr, " %d", j); 376 totfree += j * (1 << (i + 3)); 377 } 378 fprintf(stderr, "\nused:\t"); 379 for (i = 0; i < NBUCKETS; i++) { 380 fprintf(stderr, " %d", nmalloc[i]); 381 totused += nmalloc[i] * (1 << (i + 3)); 382 } 383 fprintf(stderr, "\n\tTotal in use: %d, total free: %d\n", 384 totused, totfree); 385 } 386 #endif 387