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