contrib/tcsh/tc.alloc.c

   1 /* $Header: /src/pub/tcsh/tc.alloc.c,v 3.36 2002/03/08 17:36:47 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("$Id: tc.alloc.c,v 3.36 2002/03/08 17:36:47 christos Exp $")
  44
  45 static char   *memtop = NULL;           /* PWP: top of current memory */
  46 static char   *membot = NULL;           /* PWP: bottom of allocatable memory */
  47
  48 int dont_free = 0;
  49
  50 #if defined(_VMS_POSIX) || defined(_AMIGA_MEMORY)
  51 # define NO_SBRK
  52 #endif
  53
  54 #ifdef WINNT_NATIVE
  55 # define malloc         fmalloc
  56 # define free           ffree
  57 # define calloc         fcalloc
  58 # define realloc        frealloc
  59 #endif /* WINNT_NATIVE */
  60
  61 #ifndef SYSMALLOC
  62
  63 #undef RCHECK
  64 #undef DEBUG
  65
  66 #ifdef SX
  67 extern void* sbrk();
  68 #endif
  69 /*
  70  * Lots of os routines are busted and try to free invalid pointers.
  71  * Although our free routine is smart enough and it will pick bad
  72  * pointers most of the time, in cases where we know we are going to get
  73  * a bad pointer, we'd rather leak.
  74  */
  75
  76 #ifndef NULL
  77 #define NULL 0
  78 #endif
  79
  80 typedef unsigned char U_char;   /* we don't really have signed chars */
  81 typedef unsigned int U_int;
  82 typedef unsigned short U_short;
  83 typedef unsigned long U_long;
  84
  85
  86 /*
  87  * The overhead on a block is at least 4 bytes.  When free, this space
  88  * contains a pointer to the next free block, and the bottom two bits must
  89  * be zero.  When in use, the first byte is set to MAGIC, and the second
  90  * byte is the size index.  The remaining bytes are for alignment.
  91  * If range checking is enabled and the size of the block fits
  92  * in two bytes, then the top two bytes hold the size of the requested block
  93  * plus the range checking words, and the header word MINUS ONE.
  94  */
  95
  96
  97 #define MEMALIGN(a) (((a) + ROUNDUP) & ~ROUNDUP)
  98
  99 union overhead {
 100     union overhead *ov_next;    /* when free */
 101     struct {
 102         U_char  ovu_magic;      /* magic number */
 103         U_char  ovu_index;      /* bucket # */
 104 #ifdef RCHECK
 105         U_short ovu_size;       /* actual block size */
 106         U_int   ovu_rmagic;     /* range magic number */
 107 #endif
 108     }       ovu;
 109 #define ov_magic        ovu.ovu_magic
 110 #define ov_index        ovu.ovu_index
 111 #define ov_size         ovu.ovu_size
 112 #define ov_rmagic       ovu.ovu_rmagic
 113 };
 114
 115 #define MAGIC           0xfd    /* magic # on accounting info */
 116 #define RMAGIC          0x55555555      /* magic # on range info */
 117 #ifdef RCHECK
 118 #define RSLOP           sizeof (U_int)
 119 #else
 120 #define RSLOP           0
 121 #endif
 122
 123
 124 #define ROUNDUP 7
 125
 126 /*
 127  * nextf[i] is the pointer to the next free block of size 2^(i+3).  The
 128  * smallest allocatable block is 8 bytes.  The overhead information
 129  * precedes the data area returned to the user.
 130  */
 131 #define NBUCKETS ((sizeof(long) << 3) - 3)
 132 static union overhead *nextf[NBUCKETS] IZERO_STRUCT;
 133
 134 /*
 135  * nmalloc[i] is the difference between the number of mallocs and frees
 136  * for a given block size.
 137  */
 138 static U_int nmalloc[NBUCKETS] IZERO_STRUCT;
 139
 140 #ifndef lint
 141 static  int     findbucket      __P((union overhead *, int));
 142 static  void    morecore        __P((int));
 143 #endif
 144
 145
 146 #ifdef DEBUG
 147 # define CHECK(a, str, p) \
 148     if (a) { \
 149         xprintf(str, p);        \
 150         xprintf(" (memtop = %lx membot = %lx)\n", memtop, membot);      \
 151         abort(); \
 152     }
 153 #else
 154 # define CHECK(a, str, p) \
 155     if (a) { \
 156         xprintf(str, p);        \
 157         xprintf(" (memtop = %lx membot = %lx)\n", memtop, membot);      \
 158         return; \
 159     }
 160 #endif
 161
 162 memalign_t
 163 malloc(nbytes)
 164     register size_t nbytes;
 165 {
 166 #ifndef lint
 167     register union overhead *p;
 168     register int bucket = 0;
 169     register unsigned shiftr;
 170
 171     /*
 172      * Convert amount of memory requested into closest block size stored in
 173      * hash buckets which satisfies request.  Account for space used per block
 174      * for accounting.
 175      */
 176 #ifdef SUNOS4
 177     /*
 178      * SunOS localtime() overwrites the 9th byte on an 8 byte malloc()....
 179      * so we get one more...
 180      * From Michael Schroeder: This is not true. It depends on the
 181      * timezone string. In Europe it can overwrite the 13th byte on a
 182      * 12 byte malloc.
 183      * So we punt and we always allocate an extra byte.
 184      */
 185     nbytes++;
 186 #endif
 187
 188     nbytes = MEMALIGN(MEMALIGN(sizeof(union overhead)) + nbytes + RSLOP);
 189     shiftr = (nbytes - 1) >> 2;
 190
 191     /* apart from this loop, this is O(1) */
 192     while ((shiftr >>= 1) != 0)
 193         bucket++;
 194     /*
 195      * If nothing in hash bucket right now, request more memory from the
 196      * system.
 197      */
 198     if (nextf[bucket] == NULL)
 199         morecore(bucket);
 200     if ((p = (union overhead *) nextf[bucket]) == NULL) {
 201         child++;
 202 #ifndef DEBUG
 203         stderror(ERR_NOMEM);
 204 #else
 205         showall(NULL, NULL);
 206         xprintf(CGETS(19, 1, "nbytes=%d: Out of memory\n"), nbytes);
 207         abort();
 208 #endif
 209         /* fool lint */
 210         return ((memalign_t) 0);
 211     }
 212     /* remove from linked list */
 213     nextf[bucket] = nextf[bucket]->ov_next;
 214     p->ov_magic = MAGIC;
 215     p->ov_index = bucket;
 216     nmalloc[bucket]++;
 217 #ifdef RCHECK
 218     /*
 219      * Record allocated size of block and bound space with magic numbers.
 220      */
 221     p->ov_size = (p->ov_index <= 13) ? nbytes - 1 : 0;
 222     p->ov_rmagic = RMAGIC;
 223     *((U_int *) (((caddr_t) p) + nbytes - RSLOP)) = RMAGIC;
 224 #endif
 225     return ((memalign_t) (((caddr_t) p) + MEMALIGN(sizeof(union overhead))));
 226 #else
 227     if (nbytes)
 228         return ((memalign_t) 0);
 229     else
 230         return ((memalign_t) 0);
 231 #endif /* !lint */
 232 }
 233
 234 #ifndef lint
 235 /*
 236  * Allocate more memory to the indicated bucket.
 237  */
 238 static void
 239 morecore(bucket)
 240     register int bucket;
 241 {
 242     register union overhead *op;
 243     register int rnu;           /* 2^rnu bytes will be requested */
 244     register int nblks;         /* become nblks blocks of the desired size */
 245     register int siz;
 246
 247     if (nextf[bucket])
 248         return;
 249     /*
 250      * Insure memory is allocated on a page boundary.  Should make getpageize
 251      * call?
 252      */
 253     op = (union overhead *) sbrk(0);
 254     memtop = (char *) op;
 255     if (membot == NULL)
 256         membot = memtop;
 257     if ((long) op & 0x3ff) {
 258         memtop = (char *) sbrk((int) (1024 - ((long) op & 0x3ff)));
 259         memtop += (long) (1024 - ((long) op & 0x3ff));
 260     }
 261
 262     /* take 2k unless the block is bigger than that */
 263     rnu = (bucket <= 8) ? 11 : bucket + 3;
 264     nblks = 1 << (rnu - (bucket + 3));  /* how many blocks to get */
 265     memtop = (char *) sbrk(1 << rnu);   /* PWP */
 266     op = (union overhead *) memtop;
 267     /* no more room! */
 268     if ((long) op == -1)
 269         return;
 270     memtop += (long) (1 << rnu);
 271     /*
 272      * Round up to minimum allocation size boundary and deduct from block count
 273      * to reflect.
 274      */
 275     if (((U_long) op) & ROUNDUP) {
 276         op = (union overhead *) (((U_long) op + (ROUNDUP + 1)) & ~ROUNDUP);
 277         nblks--;
 278     }
 279     /*
 280      * Add new memory allocated to that on free list for this hash bucket.
 281      */
 282     nextf[bucket] = op;
 283     siz = 1 << (bucket + 3);
 284     while (--nblks > 0) {
 285         op->ov_next = (union overhead *) (((caddr_t) op) + siz);
 286         op = (union overhead *) (((caddr_t) op) + siz);
 287     }
 288     op->ov_next = NULL;
 289 }
 290
 291 #endif
 292
 293 void
 294 free(cp)
 295     ptr_t   cp;
 296 {
 297 #ifndef lint
 298     register int size;
 299     register union overhead *op;
 300
 301     /*
 302      * the don't free flag is there so that we avoid os bugs in routines
 303      * that free invalid pointers!
 304      */
 305     if (cp == NULL || dont_free)
 306         return;
 307     CHECK(!memtop || !membot,
 308           CGETS(19, 2, "free(%lx) called before any allocations."), cp);
 309     CHECK(cp > (ptr_t) memtop,
 310           CGETS(19, 3, "free(%lx) above top of memory."), cp);
 311     CHECK(cp < (ptr_t) membot,
 312           CGETS(19, 4, "free(%lx) below bottom of memory."), cp);
 313     op = (union overhead *) (((caddr_t) cp) - MEMALIGN(sizeof(union overhead)));
 314     CHECK(op->ov_magic != MAGIC,
 315           CGETS(19, 5, "free(%lx) bad block."), cp);
 316
 317 #ifdef RCHECK
 318     if (op->ov_index <= 13)
 319         CHECK(*(U_int *) ((caddr_t) op + op->ov_size + 1 - RSLOP) != RMAGIC,
 320               CGETS(19, 6, "free(%lx) bad range check."), cp);
 321 #endif
 322     CHECK(op->ov_index >= NBUCKETS,
 323           CGETS(19, 7, "free(%lx) bad block index."), cp);
 324     size = op->ov_index;
 325     op->ov_next = nextf[size];
 326     nextf[size] = op;
 327
 328     nmalloc[size]--;
 329
 330 #else
 331     if (cp == NULL)
 332         return;
 333 #endif
 334 }
 335
 336 memalign_t
 337 calloc(i, j)
 338     size_t  i, j;
 339 {
 340 #ifndef lint
 341     register char *cp, *scp;
 342
 343     i *= j;
 344     scp = cp = (char *) xmalloc((size_t) i);
 345     if (i != 0)
 346         do
 347             *cp++ = 0;
 348         while (--i);
 349
 350     return ((memalign_t) scp);
 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(cp, nbytes)
 377     ptr_t   cp;
 378     size_t  nbytes;
 379 {
 380 #ifndef lint
 381     register U_int onb;
 382     union overhead *op;
 383     ptr_t res;
 384     register int i;
 385     int     was_alloced = 0;
 386
 387     if (cp == NULL)
 388         return (malloc(nbytes));
 389     op = (union overhead *) (((caddr_t) cp) - MEMALIGN(sizeof(union overhead)));
 390     if (op->ov_magic == MAGIC) {
 391         was_alloced++;
 392         i = op->ov_index;
 393     }
 394     else
 395         /*
 396          * Already free, doing "compaction".
 397          *
 398          * Search for the old block of memory on the free list.  First, check the
 399          * most common case (last element free'd), then (this failing) the last
 400          * ``realloc_srchlen'' items free'd. If all lookups fail, then assume
 401          * the size of the memory block being realloc'd is the smallest
 402          * possible.
 403          */
 404         if ((i = findbucket(op, 1)) < 0 &&
 405             (i = findbucket(op, realloc_srchlen)) < 0)
 406             i = 0;
 407
 408     onb = MEMALIGN(nbytes + MEMALIGN(sizeof(union overhead)) + RSLOP);
 409
 410     /* avoid the copy if same size block */
 411     if (was_alloced && (onb <= (U_int) (1 << (i + 3))) &&
 412         (onb > (U_int) (1 << (i + 2)))) {
 413 #ifdef RCHECK
 414         /* JMR: formerly this wasn't updated ! */
 415         nbytes = MEMALIGN(MEMALIGN(sizeof(union overhead))+nbytes+RSLOP);
 416         *((U_int *) (((caddr_t) op) + nbytes - RSLOP)) = RMAGIC;
 417         op->ov_rmagic = RMAGIC;
 418         op->ov_size = (op->ov_index <= 13) ? nbytes - 1 : 0;
 419 #endif
 420         return ((memalign_t) cp);
 421     }
 422     if ((res = malloc(nbytes)) == NULL)
 423         return ((memalign_t) NULL);
 424     if (cp != res) {            /* common optimization */
 425         /*
 426          * christos: this used to copy nbytes! It should copy the
 427          * smaller of the old and new size
 428          */
 429         onb = (1 << (i + 3)) - MEMALIGN(sizeof(union overhead)) - RSLOP;
 430         (void) memmove((ptr_t) res, (ptr_t) cp,
 431                        (size_t) (onb < nbytes ? onb : nbytes));
 432     }
 433     if (was_alloced)
 434         free(cp);
 435     return ((memalign_t) res);
 436 #else
 437     if (cp && nbytes)
 438         return ((memalign_t) 0);
 439     else
 440         return ((memalign_t) 0);
 441 #endif /* !lint */
 442 }
 443
 444
 445
 446 #ifndef lint
 447 /*
 448  * Search ``srchlen'' elements of each free list for a block whose
 449  * header starts at ``freep''.  If srchlen is -1 search the whole list.
 450  * Return bucket number, or -1 if not found.
 451  */
 452 static int
 453 findbucket(freep, srchlen)
 454     union overhead *freep;
 455     int     srchlen;
 456 {
 457     register union overhead *p;
 458     register int i, j;
 459
 460     for (i = 0; i < NBUCKETS; i++) {
 461         j = 0;
 462         for (p = nextf[i]; p && j != srchlen; p = p->ov_next) {
 463             if (p == freep)
 464                 return (i);
 465             j++;
 466         }
 467     }
 468     return (-1);
 469 }
 470
 471 #endif
 472
 473
 474 #else                           /* SYSMALLOC */
 475
 476 /**
 477  ** ``Protected versions'' of malloc, realloc, calloc, and free
 478  **
 479  ** On many systems:
 480  **
 481  ** 1. malloc(0) is bad
 482  ** 2. free(0) is bad
 483  ** 3. realloc(0, n) is bad
 484  ** 4. realloc(n, 0) is bad
 485  **
 486  ** Also we call our error routine if we run out of memory.
 487  **/
 488 memalign_t
 489 smalloc(n)
 490     size_t  n;
 491 {
 492     ptr_t   ptr;
 493
 494     n = n ? n : 1;
 495
 496 #ifndef NO_SBRK
 497     if (membot == NULL)
 498         membot = (char*) sbrk(0);
 499 #endif /* !NO_SBRK */
 500
 501     if ((ptr = malloc(n)) == (ptr_t) 0) {
 502         child++;
 503         stderror(ERR_NOMEM);
 504     }
 505 #ifdef NO_SBRK
 506     if (memtop < ((char *) ptr) + n)
 507         memtop = ((char *) ptr) + n;
 508     if (membot == NULL)
 509         membot = (char*) ptr;
 510 #endif /* NO_SBRK */
 511     return ((memalign_t) ptr);
 512 }
 513
 514 memalign_t
 515 srealloc(p, n)
 516     ptr_t   p;
 517     size_t  n;
 518 {
 519     ptr_t   ptr;
 520
 521     n = n ? n : 1;
 522
 523 #ifndef NO_SBRK
 524     if (membot == NULL)
 525         membot = (char*) sbrk(0);
 526 #endif /* NO_SBRK */
 527
 528     if ((ptr = (p ? realloc(p, n) : malloc(n))) == (ptr_t) 0) {
 529         child++;
 530         stderror(ERR_NOMEM);
 531     }
 532 #ifdef NO_SBRK
 533     if (memtop < ((char *) ptr) + n)
 534         memtop = ((char *) ptr) + n;
 535     if (membot == NULL)
 536         membot = (char*) ptr;
 537 #endif /* NO_SBRK */
 538     return ((memalign_t) ptr);
 539 }
 540
 541 memalign_t
 542 scalloc(s, n)
 543     size_t  s, n;
 544 {
 545     char   *sptr;
 546     ptr_t   ptr;
 547
 548     n *= s;
 549     n = n ? n : 1;
 550
 551 #ifndef NO_SBRK
 552     if (membot == NULL)
 553         membot = (char*) sbrk(0);
 554 #endif /* NO_SBRK */
 555
 556     if ((ptr = malloc(n)) == (ptr_t) 0) {
 557         child++;
 558         stderror(ERR_NOMEM);
 559     }
 560
 561     sptr = (char *) ptr;
 562     if (n != 0)
 563         do
 564             *sptr++ = 0;
 565         while (--n);
 566
 567 #ifdef NO_SBRK
 568     if (memtop < ((char *) ptr) + n)
 569         memtop = ((char *) ptr) + n;
 570     if (membot == NULL)
 571         membot = (char*) ptr;
 572 #endif /* NO_SBRK */
 573
 574     return ((memalign_t) ptr);
 575 }
 576
 577 void
 578 sfree(p)
 579     ptr_t   p;
 580 {
 581     if (p && !dont_free)
 582         free(p);
 583 }
 584
 585 #endif /* SYSMALLOC */
 586
 587 /*
 588  * mstats - print out statistics about malloc
 589  *
 590  * Prints two lines of numbers, one showing the length of the free list
 591  * for each size category, the second showing the number of mallocs -
 592  * frees for each size category.
 593  */
 594 /*ARGSUSED*/
 595 void
 596 showall(v, c)
 597     Char **v;
 598     struct command *c;
 599 {
 600 #ifndef SYSMALLOC
 601     register int i, j;
 602     register union overhead *p;
 603     int     totfree = 0, totused = 0;
 604
 605     xprintf(CGETS(19, 8, "%s current memory allocation:\nfree:\t"), progname);
 606     for (i = 0; i < NBUCKETS; i++) {
 607         for (j = 0, p = nextf[i]; p; p = p->ov_next, j++)
 608             continue;
 609         xprintf(" %4d", j);
 610         totfree += j * (1 << (i + 3));
 611     }
 612     xprintf(CGETS(19, 9, "\nused:\t"));
 613     for (i = 0; i < NBUCKETS; i++) {
 614         xprintf(" %4u", nmalloc[i]);
 615         totused += nmalloc[i] * (1 << (i + 3));
 616     }
 617     xprintf(CGETS(19, 10, "\n\tTotal in use: %d, total free: %d\n"),
 618             totused, totfree);
 619     xprintf(CGETS(19, 11,
 620             "\tAllocated memory from 0x%lx to 0x%lx.  Real top at 0x%lx\n"),
 621             (unsigned long) membot, (unsigned long) memtop,
 622             (unsigned long) sbrk(0));
 623 #else
 624 #ifndef NO_SBRK
 625     memtop = (char *) sbrk(0);
 626 #endif /* !NO_SBRK */
 627     xprintf(CGETS(19, 12, "Allocated memory from 0x%lx to 0x%lx (%ld).\n"),
 628             (unsigned long) membot, (unsigned long) memtop,
 629             (unsigned long) (memtop - membot));
 630 #endif /* SYSMALLOC */
 631     USE(c);
 632     USE(v);
 633 }