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