1 /* $Header: /p/tcsh/cvsroot/tcsh/tc.alloc.c,v 3.46 2006/03/02 18:46:44 christos Exp $ */ 2 /* 3 * tc.alloc.c (Caltech) 2/21/82 4 * Chris Kingsley, kingsley@cit-20. 5 * 6 * This is a very fast storage allocator. It allocates blocks of a small 7 * number of different sizes, and keeps free lists of each size. Blocks that 8 * don't exactly fit are passed up to the next larger size. In this 9 * implementation, the available sizes are 2^n-4 (or 2^n-12) bytes long. 10 * This is designed for use in a program that uses vast quantities of memory, 11 * but bombs when it runs out. 12 */ 13 /*- 14 * Copyright (c) 1980, 1991 The Regents of the University of California. 15 * All rights reserved. 16 * 17 * Redistribution and use in source and binary forms, with or without 18 * modification, are permitted provided that the following conditions 19 * are met: 20 * 1. Redistributions of source code must retain the above copyright 21 * notice, this list of conditions and the following disclaimer. 22 * 2. Redistributions in binary form must reproduce the above copyright 23 * notice, this list of conditions and the following disclaimer in the 24 * documentation and/or other materials provided with the distribution. 25 * 3. Neither the name of the University nor the names of its contributors 26 * may be used to endorse or promote products derived from this software 27 * without specific prior written permission. 28 * 29 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 30 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 31 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 32 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 33 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 34 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 35 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 36 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 37 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 38 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 39 * SUCH DAMAGE. 40 */ 41 #include "sh.h" 42 43 RCSID("$tcsh: tc.alloc.c,v 3.46 2006/03/02 18:46:44 christos Exp $") 44 45 #define RCHECK 46 #define DEBUG 47 48 static char *memtop = NULL; /* PWP: top of current memory */ 49 static char *membot = NULL; /* PWP: bottom of allocatable memory */ 50 51 int dont_free = 0; 52 53 #ifdef WINNT_NATIVE 54 # define malloc fmalloc 55 # define free ffree 56 # define calloc fcalloc 57 # define realloc frealloc 58 #endif /* WINNT_NATIVE */ 59 60 #if !defined(DEBUG) || defined(SYSMALLOC) 61 static void 62 out_of_memory (void) 63 { 64 static const char msg[] = "Out of memory\n"; 65 66 write(didfds ? 2 : SHDIAG, msg, strlen(msg)); 67 _exit(1); 68 } 69 #endif 70 71 #ifndef SYSMALLOC 72 73 #ifdef SX 74 extern void* sbrk(); 75 #endif 76 /* 77 * Lots of os routines are busted and try to free invalid pointers. 78 * Although our free routine is smart enough and it will pick bad 79 * pointers most of the time, in cases where we know we are going to get 80 * a bad pointer, we'd rather leak. 81 */ 82 83 #ifndef NULL 84 #define NULL 0 85 #endif 86 87 typedef unsigned char U_char; /* we don't really have signed chars */ 88 typedef unsigned int U_int; 89 typedef unsigned short U_short; 90 typedef unsigned long U_long; 91 92 93 /* 94 * The overhead on a block is at least 4 bytes. When free, this space 95 * contains a pointer to the next free block, and the bottom two bits must 96 * be zero. When in use, the first byte is set to MAGIC, and the second 97 * byte is the size index. The remaining bytes are for alignment. 98 * If range checking is enabled and the size of the block fits 99 * in two bytes, then the top two bytes hold the size of the requested block 100 * plus the range checking words, and the header word MINUS ONE. 101 */ 102 103 104 #define MEMALIGN(a) (((a) + ROUNDUP) & ~ROUNDUP) 105 106 union overhead { 107 union overhead *ov_next; /* when free */ 108 struct { 109 U_char ovu_magic; /* magic number */ 110 U_char ovu_index; /* bucket # */ 111 #ifdef RCHECK 112 U_short ovu_size; /* actual block size */ 113 U_int ovu_rmagic; /* range magic number */ 114 #endif 115 } ovu; 116 #define ov_magic ovu.ovu_magic 117 #define ov_index ovu.ovu_index 118 #define ov_size ovu.ovu_size 119 #define ov_rmagic ovu.ovu_rmagic 120 }; 121 122 #define MAGIC 0xfd /* magic # on accounting info */ 123 #define RMAGIC 0x55555555 /* magic # on range info */ 124 #ifdef RCHECK 125 #define RSLOP sizeof (U_int) 126 #else 127 #define RSLOP 0 128 #endif 129 130 131 #define ROUNDUP 7 132 133 /* 134 * nextf[i] is the pointer to the next free block of size 2^(i+3). The 135 * smallest allocatable block is 8 bytes. The overhead information 136 * precedes the data area returned to the user. 137 */ 138 #define NBUCKETS ((sizeof(long) << 3) - 3) 139 static union overhead *nextf[NBUCKETS] IZERO_STRUCT; 140 141 /* 142 * nmalloc[i] is the difference between the number of mallocs and frees 143 * for a given block size. 144 */ 145 static U_int nmalloc[NBUCKETS] IZERO_STRUCT; 146 147 #ifndef lint 148 static int findbucket (union overhead *, int); 149 static void morecore (int); 150 #endif 151 152 153 #ifdef DEBUG 154 # define CHECK(a, str, p) \ 155 if (a) { \ 156 xprintf(str, p); \ 157 xprintf(" (memtop = %p membot = %p)\n", memtop, membot); \ 158 abort(); \ 159 } 160 #else 161 # define CHECK(a, str, p) \ 162 if (a) { \ 163 xprintf(str, p); \ 164 xprintf(" (memtop = %p membot = %p)\n", memtop, membot); \ 165 return; \ 166 } 167 #endif 168 169 memalign_t 170 malloc(size_t nbytes) 171 { 172 #ifndef lint 173 union overhead *p; 174 int bucket = 0; 175 unsigned shiftr; 176 177 /* 178 * Convert amount of memory requested into closest block size stored in 179 * hash buckets which satisfies request. Account for space used per block 180 * for accounting. 181 */ 182 #ifdef SUNOS4 183 /* 184 * SunOS localtime() overwrites the 9th byte on an 8 byte malloc().... 185 * so we get one more... 186 * From Michael Schroeder: This is not true. It depends on the 187 * timezone string. In Europe it can overwrite the 13th byte on a 188 * 12 byte malloc. 189 * So we punt and we always allocate an extra byte. 190 */ 191 nbytes++; 192 #endif 193 194 nbytes = MEMALIGN(MEMALIGN(sizeof(union overhead)) + nbytes + RSLOP); 195 shiftr = (nbytes - 1) >> 2; 196 197 /* apart from this loop, this is O(1) */ 198 while ((shiftr >>= 1) != 0) 199 bucket++; 200 /* 201 * If nothing in hash bucket right now, request more memory from the 202 * system. 203 */ 204 if (nextf[bucket] == NULL) 205 morecore(bucket); 206 if ((p = nextf[bucket]) == NULL) { 207 child++; 208 #ifndef DEBUG 209 out_of_memory(); 210 #else 211 showall(NULL, NULL); 212 xprintf(CGETS(19, 1, "nbytes=%zu: Out of memory\n"), nbytes); 213 abort(); 214 #endif 215 /* fool lint */ 216 return ((memalign_t) 0); 217 } 218 /* remove from linked list */ 219 nextf[bucket] = nextf[bucket]->ov_next; 220 p->ov_magic = MAGIC; 221 p->ov_index = bucket; 222 nmalloc[bucket]++; 223 #ifdef RCHECK 224 /* 225 * Record allocated size of block and bound space with magic numbers. 226 */ 227 p->ov_size = (p->ov_index <= 13) ? nbytes - 1 : 0; 228 p->ov_rmagic = RMAGIC; 229 *((U_int *) (((caddr_t) p) + nbytes - RSLOP)) = RMAGIC; 230 #endif 231 return ((memalign_t) (((caddr_t) p) + MEMALIGN(sizeof(union overhead)))); 232 #else 233 if (nbytes) 234 return ((memalign_t) 0); 235 else 236 return ((memalign_t) 0); 237 #endif /* !lint */ 238 } 239 240 #ifndef lint 241 /* 242 * Allocate more memory to the indicated bucket. 243 */ 244 static void 245 morecore(int bucket) 246 { 247 union overhead *op; 248 int rnu; /* 2^rnu bytes will be requested */ 249 int nblks; /* become nblks blocks of the desired size */ 250 int siz; 251 252 if (nextf[bucket]) 253 return; 254 /* 255 * Insure memory is allocated on a page boundary. Should make getpageize 256 * call? 257 */ 258 op = (union overhead *) sbrk(0); 259 memtop = (char *) op; 260 if (membot == NULL) 261 membot = memtop; 262 if ((long) op & 0x3ff) { 263 memtop = sbrk((int) (1024 - ((long) op & 0x3ff))); 264 memtop += (long) (1024 - ((long) op & 0x3ff)); 265 } 266 267 /* take 2k unless the block is bigger than that */ 268 rnu = (bucket <= 8) ? 11 : bucket + 3; 269 nblks = 1 << (rnu - (bucket + 3)); /* how many blocks to get */ 270 memtop = sbrk(1 << rnu); /* PWP */ 271 op = (union overhead *) memtop; 272 /* no more room! */ 273 if ((long) op == -1) 274 return; 275 memtop += (long) (1 << rnu); 276 /* 277 * Round up to minimum allocation size boundary and deduct from block count 278 * to reflect. 279 */ 280 if (((U_long) op) & ROUNDUP) { 281 op = (union overhead *) (((U_long) op + (ROUNDUP + 1)) & ~ROUNDUP); 282 nblks--; 283 } 284 /* 285 * Add new memory allocated to that on free list for this hash bucket. 286 */ 287 nextf[bucket] = op; 288 siz = 1 << (bucket + 3); 289 while (--nblks > 0) { 290 op->ov_next = (union overhead *) (((caddr_t) op) + siz); 291 op = (union overhead *) (((caddr_t) op) + siz); 292 } 293 op->ov_next = NULL; 294 } 295 296 #endif 297 298 void 299 free(ptr_t cp) 300 { 301 #ifndef lint 302 int size; 303 union overhead *op; 304 305 /* 306 * the don't free flag is there so that we avoid os bugs in routines 307 * that free invalid pointers! 308 */ 309 if (cp == NULL || dont_free) 310 return; 311 CHECK(!memtop || !membot, 312 CGETS(19, 2, "free(%p) called before any allocations."), cp); 313 CHECK(cp > (ptr_t) memtop, 314 CGETS(19, 3, "free(%p) above top of memory."), cp); 315 CHECK(cp < (ptr_t) membot, 316 CGETS(19, 4, "free(%p) below bottom of memory."), cp); 317 op = (union overhead *) (((caddr_t) cp) - MEMALIGN(sizeof(union overhead))); 318 CHECK(op->ov_magic != MAGIC, 319 CGETS(19, 5, "free(%p) bad block."), cp); 320 321 #ifdef RCHECK 322 if (op->ov_index <= 13) 323 CHECK(*(U_int *) ((caddr_t) op + op->ov_size + 1 - RSLOP) != RMAGIC, 324 CGETS(19, 6, "free(%p) bad range check."), cp); 325 #endif 326 CHECK(op->ov_index >= NBUCKETS, 327 CGETS(19, 7, "free(%p) bad block index."), cp); 328 size = op->ov_index; 329 op->ov_next = nextf[size]; 330 nextf[size] = op; 331 332 nmalloc[size]--; 333 334 #else 335 if (cp == NULL) 336 return; 337 #endif 338 } 339 340 memalign_t 341 calloc(size_t i, size_t j) 342 { 343 #ifndef lint 344 char *cp; 345 346 i *= j; 347 cp = xmalloc(i); 348 memset(cp, 0, i); 349 350 return ((memalign_t) cp); 351 #else 352 if (i && j) 353 return ((memalign_t) 0); 354 else 355 return ((memalign_t) 0); 356 #endif 357 } 358 359 /* 360 * When a program attempts "storage compaction" as mentioned in the 361 * old malloc man page, it realloc's an already freed block. Usually 362 * this is the last block it freed; occasionally it might be farther 363 * back. We have to search all the free lists for the block in order 364 * to determine its bucket: 1st we make one pass thru the lists 365 * checking only the first block in each; if that fails we search 366 * ``realloc_srchlen'' blocks in each list for a match (the variable 367 * is extern so the caller can modify it). If that fails we just copy 368 * however many bytes was given to realloc() and hope it's not huge. 369 */ 370 #ifndef lint 371 /* 4 should be plenty, -1 =>'s whole list */ 372 static int realloc_srchlen = 4; 373 #endif /* lint */ 374 375 memalign_t 376 realloc(ptr_t cp, size_t nbytes) 377 { 378 #ifndef lint 379 U_int onb; 380 union overhead *op; 381 ptr_t res; 382 int i; 383 int was_alloced = 0; 384 385 if (cp == NULL) 386 return (malloc(nbytes)); 387 op = (union overhead *) (((caddr_t) cp) - MEMALIGN(sizeof(union overhead))); 388 if (op->ov_magic == MAGIC) { 389 was_alloced++; 390 i = op->ov_index; 391 } 392 else 393 /* 394 * Already free, doing "compaction". 395 * 396 * Search for the old block of memory on the free list. First, check the 397 * most common case (last element free'd), then (this failing) the last 398 * ``realloc_srchlen'' items free'd. If all lookups fail, then assume 399 * the size of the memory block being realloc'd is the smallest 400 * possible. 401 */ 402 if ((i = findbucket(op, 1)) < 0 && 403 (i = findbucket(op, realloc_srchlen)) < 0) 404 i = 0; 405 406 onb = MEMALIGN(nbytes + MEMALIGN(sizeof(union overhead)) + RSLOP); 407 408 /* avoid the copy if same size block */ 409 if (was_alloced && (onb <= (U_int) (1 << (i + 3))) && 410 (onb > (U_int) (1 << (i + 2)))) { 411 #ifdef RCHECK 412 /* JMR: formerly this wasn't updated ! */ 413 nbytes = MEMALIGN(MEMALIGN(sizeof(union overhead))+nbytes+RSLOP); 414 *((U_int *) (((caddr_t) op) + nbytes - RSLOP)) = RMAGIC; 415 op->ov_rmagic = RMAGIC; 416 op->ov_size = (op->ov_index <= 13) ? nbytes - 1 : 0; 417 #endif 418 return ((memalign_t) cp); 419 } 420 if ((res = malloc(nbytes)) == NULL) 421 return ((memalign_t) NULL); 422 if (cp != res) { /* common optimization */ 423 /* 424 * christos: this used to copy nbytes! It should copy the 425 * smaller of the old and new size 426 */ 427 onb = (1 << (i + 3)) - MEMALIGN(sizeof(union overhead)) - RSLOP; 428 (void) memmove(res, cp, onb < nbytes ? onb : nbytes); 429 } 430 if (was_alloced) 431 free(cp); 432 return ((memalign_t) res); 433 #else 434 if (cp && nbytes) 435 return ((memalign_t) 0); 436 else 437 return ((memalign_t) 0); 438 #endif /* !lint */ 439 } 440 441 442 443 #ifndef lint 444 /* 445 * Search ``srchlen'' elements of each free list for a block whose 446 * header starts at ``freep''. If srchlen is -1 search the whole list. 447 * Return bucket number, or -1 if not found. 448 */ 449 static int 450 findbucket(union overhead *freep, int srchlen) 451 { 452 union overhead *p; 453 size_t i; 454 int j; 455 456 for (i = 0; i < NBUCKETS; i++) { 457 j = 0; 458 for (p = nextf[i]; p && j != srchlen; p = p->ov_next) { 459 if (p == freep) 460 return (i); 461 j++; 462 } 463 } 464 return (-1); 465 } 466 467 #endif 468 469 470 #else /* SYSMALLOC */ 471 472 /** 473 ** ``Protected versions'' of malloc, realloc, calloc, and free 474 ** 475 ** On many systems: 476 ** 477 ** 1. malloc(0) is bad 478 ** 2. free(0) is bad 479 ** 3. realloc(0, n) is bad 480 ** 4. realloc(n, 0) is bad 481 ** 482 ** Also we call our error routine if we run out of memory. 483 **/ 484 memalign_t 485 smalloc(size_t n) 486 { 487 ptr_t ptr; 488 489 n = n ? n : 1; 490 491 #ifdef HAVE_SBRK 492 if (membot == NULL) 493 membot = sbrk(0); 494 #endif /* HAVE_SBRK */ 495 496 if ((ptr = malloc(n)) == NULL) 497 out_of_memory(); 498 #ifndef HAVE_SBRK 499 if (memtop < ((char *) ptr) + n) 500 memtop = ((char *) ptr) + n; 501 if (membot == NULL) 502 membot = ptr; 503 #endif /* !HAVE_SBRK */ 504 return ((memalign_t) ptr); 505 } 506 507 memalign_t 508 srealloc(ptr_t p, size_t n) 509 { 510 ptr_t ptr; 511 512 n = n ? n : 1; 513 514 #ifdef HAVE_SBRK 515 if (membot == NULL) 516 membot = sbrk(0); 517 #endif /* HAVE_SBRK */ 518 519 if ((ptr = (p ? realloc(p, n) : malloc(n))) == NULL) 520 out_of_memory(); 521 #ifndef HAVE_SBRK 522 if (memtop < ((char *) ptr) + n) 523 memtop = ((char *) ptr) + n; 524 if (membot == NULL) 525 membot = ptr; 526 #endif /* !HAVE_SBRK */ 527 return ((memalign_t) ptr); 528 } 529 530 memalign_t 531 scalloc(size_t s, size_t n) 532 { 533 ptr_t ptr; 534 535 n *= s; 536 n = n ? n : 1; 537 538 #ifdef HAVE_SBRK 539 if (membot == NULL) 540 membot = sbrk(0); 541 #endif /* HAVE_SBRK */ 542 543 if ((ptr = malloc(n)) == NULL) 544 out_of_memory(); 545 546 memset (ptr, 0, n); 547 548 #ifndef HAVE_SBRK 549 if (memtop < ((char *) ptr) + n) 550 memtop = ((char *) ptr) + n; 551 if (membot == NULL) 552 membot = ptr; 553 #endif /* !HAVE_SBRK */ 554 555 return ((memalign_t) ptr); 556 } 557 558 void 559 sfree(ptr_t p) 560 { 561 if (p && !dont_free) 562 free(p); 563 } 564 565 #endif /* SYSMALLOC */ 566 567 /* 568 * mstats - print out statistics about malloc 569 * 570 * Prints two lines of numbers, one showing the length of the free list 571 * for each size category, the second showing the number of mallocs - 572 * frees for each size category. 573 */ 574 /*ARGSUSED*/ 575 void 576 showall(Char **v, struct command *c) 577 { 578 #ifndef SYSMALLOC 579 size_t i, j; 580 union overhead *p; 581 int totfree = 0, totused = 0; 582 583 xprintf(CGETS(19, 8, "%s current memory allocation:\nfree:\t"), progname); 584 for (i = 0; i < NBUCKETS; i++) { 585 for (j = 0, p = nextf[i]; p; p = p->ov_next, j++) 586 continue; 587 xprintf(" %4zd", j); 588 totfree += j * (1 << (i + 3)); 589 } 590 xprintf(CGETS(19, 9, "\nused:\t")); 591 for (i = 0; i < NBUCKETS; i++) { 592 xprintf(" %4d", nmalloc[i]); 593 totused += nmalloc[i] * (1 << (i + 3)); 594 } 595 xprintf(CGETS(19, 10, "\n\tTotal in use: %d, total free: %d\n"), 596 totused, totfree); 597 xprintf(CGETS(19, 11, 598 "\tAllocated memory from 0x%lx to 0x%lx. Real top at 0x%lx\n"), 599 (unsigned long) membot, (unsigned long) memtop, 600 (unsigned long) sbrk(0)); 601 #else 602 #ifdef HAVE_SBRK 603 memtop = sbrk(0); 604 #endif /* HAVE_SBRK */ 605 xprintf(CGETS(19, 12, "Allocated memory from 0x%lx to 0x%lx (%ld).\n"), 606 (unsigned long) membot, (unsigned long) memtop, 607 (unsigned long) (memtop - membot)); 608 #endif /* SYSMALLOC */ 609 USE(c); 610 USE(v); 611 } 612