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