1 /*- 2 * Copyright (c) 1983, 1991 The Regents of the University of California. 3 * All rights reserved. 4 * 5 * %sccs.include.redist.c% 6 */ 7 8 #ifndef lint 9 static char sccsid[] = "@(#)alloc.c 5.11 (Berkeley) 10/27/91"; 10 #endif /* not lint */ 11 12 /* 13 * tc.alloc.c from 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-12) bytes long. 20 * This is designed for use in a program that uses vast quantities of memory, 21 * but bombs when it runs out. 22 */ 23 24 #include <sys/types.h> 25 #include <unistd.h> 26 #include <string.h> 27 #if __STDC__ 28 # include <stdarg.h> 29 #else 30 # include <varargs.h> 31 #endif 32 33 #include "csh.h" 34 #include "extern.h" 35 36 char *memtop = NULL; /* PWP: top of current memory */ 37 char *membot = NULL; /* PWP: bottom of allocatable memory */ 38 39 #ifndef SYSMALLOC 40 41 #undef RCHECK 42 #undef DEBUG 43 44 45 #ifndef NULL 46 #define NULL 0 47 #endif 48 49 50 /* 51 * The overhead on a block is at least 4 bytes. When free, this space 52 * contains a pointer to the next free block, and the bottom two bits must 53 * be zero. When in use, the first byte is set to MAGIC, and the second 54 * byte is the size index. The remaining bytes are for alignment. 55 * If range checking is enabled and the size of the block fits 56 * in two bytes, then the top two bytes hold the size of the requested block 57 * plus the range checking words, and the header word MINUS ONE. 58 */ 59 60 #define ROUNDUP 7 61 62 #define ALIGN(a) (((a) + ROUNDUP) & ~ROUNDUP) 63 64 union overhead { 65 union overhead *ov_next; /* when free */ 66 struct { 67 u_char ovu_magic; /* magic number */ 68 u_char ovu_index; /* bucket # */ 69 #ifdef RCHECK 70 u_short ovu_size; /* actual block size */ 71 u_int ovu_rmagic; /* range magic number */ 72 #endif 73 } ovu; 74 #define ov_magic ovu.ovu_magic 75 #define ov_index ovu.ovu_index 76 #define ov_size ovu.ovu_size 77 #define ov_rmagic ovu.ovu_rmagic 78 }; 79 80 #define MAGIC 0xfd /* magic # on accounting info */ 81 #define RMAGIC 0x55555555 /* magic # on range info */ 82 #ifdef RCHECK 83 #define RSLOP sizeof (u_int) 84 #else 85 #define RSLOP 0 86 #endif 87 88 /* 89 * nextf[i] is the pointer to the next free block of size 2^(i+3). The 90 * smallest allocatable block is 8 bytes. The overhead information 91 * precedes the data area returned to the user. 92 */ 93 #define NBUCKETS 30 94 static union overhead *nextf[NBUCKETS]; 95 96 static int findbucket __P((union overhead *, int)); 97 static void morecore __P((int)); 98 99 /* 100 * nmalloc[i] is the difference between the number of mallocs and frees 101 * for a given block size. 102 */ 103 static u_int nmalloc[NBUCKETS]; 104 105 106 #ifdef DEBUG 107 #define CHECK(a, str, p) \ 108 if (a) { \ 109 (void) fprintfcsherr, (str, p); \ 110 (void) fprintf(csherr, "memtop = %lx membot = %lx.\n", memtop, membot);\ 111 abort(); \ 112 } \ 113 else 114 #else 115 #define CHECK(a, str, p) \ 116 if (a) { \ 117 (void) fprintf(csherr, str, p); \ 118 (void) fprintf(csherr, "memtop = %lx membot = %lx.\n", memtop, membot);\ 119 return; \ 120 } \ 121 else 122 #endif 123 124 ptr_t 125 malloc(nbytes) 126 register size_t nbytes; 127 { 128 #ifndef lint 129 register union overhead *p; 130 register int bucket = 0; 131 register unsigned shiftr; 132 133 /* 134 * Convert amount of memory requested into closest block size stored in 135 * hash buckets which satisfies request. Account for space used per block 136 * for accounting. 137 */ 138 nbytes = ALIGN(ALIGN(sizeof(union overhead)) + nbytes + RSLOP); 139 shiftr = (nbytes - 1) >> 2; 140 141 /* apart from this loop, this is O(1) */ 142 while (shiftr >>= 1) 143 bucket++; 144 /* 145 * If nothing in hash bucket right now, request more memory from the 146 * system. 147 */ 148 if (nextf[bucket] == NULL) 149 morecore(bucket); 150 if ((p = (union overhead *) nextf[bucket]) == NULL) { 151 child++; 152 #ifndef DEBUG 153 stderror(ERR_NOMEM); 154 #else 155 showall(); 156 (void) fprintf(csherr, "nbytes=%d: Out of memory\n", nbytes); 157 abort(); 158 #endif 159 /* fool lint */ 160 return ((ptr_t) 0); 161 } 162 /* remove from linked list */ 163 nextf[bucket] = nextf[bucket]->ov_next; 164 p->ov_magic = MAGIC; 165 p->ov_index = bucket; 166 nmalloc[bucket]++; 167 #ifdef RCHECK 168 /* 169 * Record allocated size of block and bound space with magic numbers. 170 */ 171 if (nbytes <= 0x10000) 172 p->ov_size = nbytes - 1; 173 p->ov_rmagic = RMAGIC; 174 *((u_int *) (((caddr_t) p) + nbytes - RSLOP)) = RMAGIC; 175 #endif 176 return ((ptr_t) (((caddr_t) p) + ALIGN(sizeof(union overhead)))); 177 #else 178 if (nbytes) 179 return ((ptr_t) 0); 180 else 181 return ((ptr_t) 0); 182 #endif /* !lint */ 183 } 184 185 #ifndef lint 186 /* 187 * Allocate more memory to the indicated bucket. 188 */ 189 static void 190 morecore(bucket) 191 register int bucket; 192 { 193 register union overhead *op; 194 register int rnu; /* 2^rnu bytes will be requested */ 195 register int nblks; /* become nblks blocks of the desired size */ 196 register int siz; 197 198 if (nextf[bucket]) 199 return; 200 /* 201 * Insure memory is allocated on a page boundary. Should make getpageize 202 * call? 203 */ 204 op = (union overhead *) sbrk(0); 205 memtop = (char *) op; 206 if (membot == NULL) 207 membot = memtop; 208 if ((int) op & 0x3ff) { 209 memtop = (char *) sbrk(1024 - ((int) op & 0x3ff)); 210 memtop += 1024 - ((int) op & 0x3ff); 211 } 212 213 /* take 2k unless the block is bigger than that */ 214 rnu = (bucket <= 8) ? 11 : bucket + 3; 215 nblks = 1 << (rnu - (bucket + 3)); /* how many blocks to get */ 216 memtop = (char *) sbrk(1 << rnu); /* PWP */ 217 op = (union overhead *) memtop; 218 memtop += 1 << rnu; 219 /* no more room! */ 220 if ((int) op == -1) 221 return; 222 /* 223 * Round up to minimum allocation size boundary and deduct from block count 224 * to reflect. 225 */ 226 if (((u_int) op) & ROUNDUP) { 227 op = (union overhead *) (((u_int) op + (ROUNDUP + 1)) & ~ROUNDUP); 228 nblks--; 229 } 230 /* 231 * Add new memory allocated to that on free list for this hash bucket. 232 */ 233 nextf[bucket] = op; 234 siz = 1 << (bucket + 3); 235 while (--nblks > 0) { 236 op->ov_next = (union overhead *) (((caddr_t) op) + siz); 237 op = (union overhead *) (((caddr_t) op) + siz); 238 } 239 op->ov_next = NULL; 240 } 241 242 #endif 243 244 void 245 free(cp) 246 ptr_t cp; 247 { 248 #ifndef lint 249 register int size; 250 register union overhead *op; 251 252 if (cp == NULL) 253 return; 254 CHECK(!memtop || !membot, "free(%lx) called before any allocations.", cp); 255 CHECK(cp > (ptr_t) memtop, "free(%lx) above top of memory.", cp); 256 CHECK(cp < (ptr_t) membot, "free(%lx) above top of memory.", cp); 257 op = (union overhead *) (((caddr_t) cp) - ALIGN(sizeof(union overhead))); 258 CHECK(op->ov_magic != MAGIC, "free(%lx) bad block.", cp); 259 260 #ifdef RCHECK 261 if (op->ov_index <= 13) 262 CHECK(*(u_int *) ((caddr_t) op + op->ov_size + 1 - RSLOP) != RMAGIC, 263 "free(%lx) bad range check.", cp); 264 #endif 265 CHECK(op->ov_index >= NBUCKETS, "free(%lx) bad block index.", cp); 266 size = op->ov_index; 267 op->ov_next = nextf[size]; 268 nextf[size] = op; 269 270 nmalloc[size]--; 271 272 #else 273 if (cp == NULL) 274 return; 275 #endif 276 } 277 278 ptr_t 279 calloc(i, j) 280 size_t i, j; 281 { 282 #ifndef lint 283 register char *cp, *scp; 284 285 i *= j; 286 scp = cp = (char *) xmalloc((size_t) i); 287 if (i != 0) 288 do 289 *cp++ = 0; 290 while (--i); 291 292 return (scp); 293 #else 294 if (i && j) 295 return ((ptr_t) 0); 296 else 297 return ((ptr_t) 0); 298 #endif 299 } 300 301 /* 302 * When a program attempts "storage compaction" as mentioned in the 303 * old malloc man page, it realloc's an already freed block. Usually 304 * this is the last block it freed; occasionally it might be farther 305 * back. We have to search all the free lists for the block in order 306 * to determine its bucket: 1st we make one pass thru the lists 307 * checking only the first block in each; if that fails we search 308 * ``realloc_srchlen'' blocks in each list for a match (the variable 309 * is extern so the caller can modify it). If that fails we just copy 310 * however many bytes was given to realloc() and hope it's not huge. 311 */ 312 #ifndef lint 313 int realloc_srchlen = 4; /* 4 should be plenty, -1 =>'s whole list */ 314 315 #endif /* lint */ 316 317 ptr_t 318 realloc(cp, nbytes) 319 ptr_t cp; 320 size_t nbytes; 321 { 322 #ifndef lint 323 register u_int onb; 324 union overhead *op; 325 char *res; 326 register int i; 327 int was_alloced = 0; 328 329 if (cp == NULL) 330 return (malloc(nbytes)); 331 op = (union overhead *) (((caddr_t) cp) - ALIGN(sizeof(union overhead))); 332 if (op->ov_magic == MAGIC) { 333 was_alloced++; 334 i = op->ov_index; 335 } 336 else 337 /* 338 * Already free, doing "compaction". 339 * 340 * Search for the old block of memory on the free list. First, check the 341 * most common case (last element free'd), then (this failing) the last 342 * ``realloc_srchlen'' items free'd. If all lookups fail, then assume 343 * the size of the memory block being realloc'd is the smallest 344 * possible. 345 */ 346 if ((i = findbucket(op, 1)) < 0 && 347 (i = findbucket(op, realloc_srchlen)) < 0) 348 i = 0; 349 350 onb = ALIGN(nbytes + ALIGN(sizeof(union overhead)) + RSLOP); 351 352 /* avoid the copy if same size block */ 353 if (was_alloced && (onb < (1 << (i + 3))) && (onb >= (1 << (i + 2)))) 354 return ((ptr_t) cp); 355 if ((res = malloc(nbytes)) == NULL) 356 return ((ptr_t) 0); 357 if (cp != res) /* common optimization */ 358 bcopy(cp, res, nbytes); 359 if (was_alloced) 360 free(cp); 361 return (res); 362 #else 363 if (cp && nbytes) 364 return ((ptr_t) 0); 365 else 366 return ((ptr_t) 0); 367 #endif /* !lint */ 368 } 369 370 371 372 #ifndef lint 373 /* 374 * Search ``srchlen'' elements of each free list for a block whose 375 * header starts at ``freep''. If srchlen is -1 search the whole list. 376 * Return bucket number, or -1 if not found. 377 */ 378 static int 379 findbucket(freep, srchlen) 380 union overhead *freep; 381 int srchlen; 382 { 383 register union overhead *p; 384 register int i, j; 385 386 for (i = 0; i < NBUCKETS; i++) { 387 j = 0; 388 for (p = nextf[i]; p && j != srchlen; p = p->ov_next) { 389 if (p == freep) 390 return (i); 391 j++; 392 } 393 } 394 return (-1); 395 } 396 397 #endif 398 399 400 #else /* SYSMALLOC */ 401 402 /** 403 ** ``Protected versions'' of malloc, realloc, calloc, and free 404 ** 405 ** On many systems: 406 ** 407 ** 1. malloc(0) is bad 408 ** 2. free(0) is bad 409 ** 3. realloc(0, n) is bad 410 ** 4. realloc(n, 0) is bad 411 ** 412 ** Also we call our error routine if we run out of memory. 413 **/ 414 char * 415 Malloc(n) 416 size_t n; 417 { 418 ptr_t ptr; 419 420 n = n ? n : 1; 421 422 if ((ptr = malloc(n)) == (ptr_t) 0) { 423 child++; 424 stderror(ERR_NOMEM); 425 } 426 return ((char *) ptr); 427 } 428 429 char * 430 Realloc(p, n) 431 ptr_t p; 432 size_t n; 433 { 434 ptr_t ptr; 435 436 n = n ? n : 1; 437 if ((ptr = (p ? realloc(p, n) : malloc(n))) == (ptr_t) 0) { 438 child++; 439 stderror(ERR_NOMEM); 440 } 441 return ((char *) ptr); 442 } 443 444 char * 445 Calloc(s, n) 446 size_t s, n; 447 { 448 char *sptr; 449 ptr_t ptr; 450 451 n *= s; 452 n = n ? n : 1; 453 if ((ptr = malloc(n)) == (ptr_t) 0) { 454 child++; 455 stderror(ERR_NOMEM); 456 } 457 458 sptr = (char *) ptr; 459 if (n != 0) 460 do 461 *sptr++ = 0; 462 while (--n); 463 464 return ((char *) ptr); 465 } 466 467 void 468 Free(p) 469 ptr_t p; 470 { 471 if (p) 472 free(p); 473 } 474 475 #endif /* SYSMALLOC */ 476 477 /* 478 * mstats - print out statistics about malloc 479 * 480 * Prints two lines of numbers, one showing the length of the free list 481 * for each size category, the second showing the number of mallocs - 482 * frees for each size category. 483 */ 484 void 485 /*ARGSUSED*/ 486 showall(v, t) 487 Char **v; 488 struct command *t; 489 { 490 #ifndef SYSMALLOC 491 register int i, j; 492 register union overhead *p; 493 int totfree = 0, totused = 0; 494 495 (void) fprintf(cshout, "csh current memory allocation:\nfree:\t"); 496 for (i = 0; i < NBUCKETS; i++) { 497 for (j = 0, p = nextf[i]; p; p = p->ov_next, j++); 498 (void) fprintf(cshout, " %4d", j); 499 totfree += j * (1 << (i + 3)); 500 } 501 (void) fprintf(cshout, "\nused:\t"); 502 for (i = 0; i < NBUCKETS; i++) { 503 (void) fprintf(cshout, "%4d", nmalloc[i]); 504 totused += nmalloc[i] * (1 << (i + 3)); 505 } 506 (void) fprintf(cshout, "\n\tTotal in use: %d, total free: %d\n", 507 totused, totfree); 508 (void) fprintf(cshout, 509 "\tAllocated memory from 0x%lx to 0x%lx. Real top at 0x%lx\n", 510 membot, memtop, (char *) sbrk(0)); 511 #else 512 (void) fprintf(cshout, "Allocated memory from 0x%lx to 0x%lx (%ld).\n", 513 membot, memtop = (char *) sbrk(0), memtop - membot); 514 #endif /* SYSMALLOC */ 515 } 516