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