home *** CD-ROM | disk | FTP | other *** search
/ Stars of Shareware: Raytrace & Morphing / SOS-RAYTRACE.ISO / programm / source / radsrc22 / src / rt / malloc.c < prev    next >
Encoding:
C/C++ Source or Header  |  1992-10-08  |  11.0 KB  |  454 lines
  1. /* Copyright (c) 1992 Regents of the University of California */
  2.  
  3. #ifndef lint
  4. static char SCCSid[] = "@(#)malloc.c 2.8 10/8/92 LBL";
  5. #endif
  6.  
  7. /*
  8.  * Fast malloc for memory hogs and VM environments.
  9.  * Performs a minimum of searching through free lists.
  10.  * malloc(), realloc() and free() use buckets
  11.  *    containing blocks in powers of two, similar to CIT routines.
  12.  * bfree() puts memory from any source into malloc free lists.
  13.  * bmalloc() doesn't keep track of free lists -- it's usually
  14.  *    just a buffered call to sbrk(2).  However, bmalloc will
  15.  *    call mscrounge() if sbrk fails.
  16.  * mscrounge() returns whatever free memory it can find to satisfy the
  17.  *    request along with the number of bytes (modified).
  18.  * mcompact() takes the same arguments as mscrounge() (and is in fact
  19.  *    called by mscrounge() under dire circumstances), but it uses
  20.  *    memory compaction to return a larger block.  (MCOMP)
  21.  *
  22.  *    Greg Ward    Lawrence Berkeley Laboratory
  23.  */
  24.  
  25. #include  <errno.h>
  26.  
  27. #ifndef  BSD
  28. #define  bcopy(s,d,n)        (void)memcpy(d,s,n)
  29. #define  bzero(d,n)        (void)memset(d,0,n)
  30. extern char  *memcpy(), *memset();
  31. #endif
  32.  
  33. #ifdef MSTATS
  34. #include  <stdio.h>
  35. static unsigned    b_nsbrked = 0;
  36. static unsigned    b_nalloced = 0;
  37. static unsigned    b_nfreed = 0;
  38. static unsigned    b_nscrounged = 0;
  39. static unsigned b_ncompacted = 0;
  40. static unsigned    m_nalloced = 0;
  41. static unsigned    m_nfreed = 0;
  42. static unsigned    m_nwasted = 0;
  43. #else
  44. #define  NULL        0
  45. #endif
  46.  
  47. #ifndef ALIGN
  48. #define  ALIGN        int            /* align type */
  49. #endif
  50. #define  BYTES_WORD    sizeof(ALIGN)
  51.  
  52. #ifndef  MAXINCR
  53. #define  MAXINCR    (1<<16)            /* largest sbrk(2) increment */
  54. #endif
  55.                     /* malloc free lists */
  56. typedef union m_head {
  57.     union m_head    *next;
  58.     struct {
  59.         short        magic;
  60.         short        bucket;
  61.     }    a;
  62.     ALIGN        dummy;
  63. } M_HEAD;
  64.  
  65. #define MAGIC        0x1a2        /* magic number for allocated memory */
  66.  
  67. #define FIRSTBUCKET    3
  68. #define NBUCKETS    30
  69.  
  70. static M_HEAD    *free_list[NBUCKETS];
  71.  
  72. static ALIGN    dummy_mem;
  73.  
  74. static char    *memlim[2];
  75.  
  76. #define DUMMYLOC    ((char *)&dummy_mem)
  77.  
  78. #define BADPTR(p)    ((p) < memlim[0] | (p) >= memlim[1])
  79.  
  80. #ifdef  MCOMP            /* memory compaction routines */
  81. static char    seedtab[1024];        /* seed for compaction table */
  82.  
  83. static struct mblk {
  84.     char        *ptr;    /* pointer to memory block */
  85.     unsigned    siz;    /* size of memory block */
  86. }    cptab = {seedtab, sizeof(seedtab)};
  87.  
  88. #define mtab(mb)    ((struct mblk *)(mb)->ptr)
  89. #define mtablen(mb)    ((mb)->siz/sizeof(struct mblk))
  90.  
  91.  
  92. static int
  93. mbcmp(m1, m2)        /* compare memory block locations */
  94. register struct mblk    *m1, *m2;
  95. {
  96.                 /* put empty blocks at end */
  97.     if (m1->siz == 0)
  98.         return(m2->siz == 0 ? 0 : 1);
  99.     if (m2->siz == 0)
  100.         return(-1);
  101.                 /* otherwise, ascending order */
  102.     return(m1->ptr - m2->ptr);
  103. }
  104.  
  105.  
  106. int
  107. compactfree()        /* compact free lists (moving to table) */
  108. {
  109.     register struct mblk    *tp;
  110.     register int    bucket;
  111.     unsigned    n, bsiz, ncomp;
  112.                 /* fill table from free lists */
  113.     tp = mtab(&cptab); n = mtablen(&cptab);
  114.     bucket = NBUCKETS-1; bsiz = 1<<(NBUCKETS-1);
  115.     ncomp = 0;
  116.     for ( ; ; ) {
  117.         while (tp->siz) {    /* find empty slot */
  118.             if (--n == 0)
  119.                 goto loopexit;
  120.             tp++;
  121.         }
  122.         while (free_list[bucket] == NULL) {    /* find block */
  123.             if (--bucket < FIRSTBUCKET)
  124.                 goto loopexit;
  125.             bsiz >>= 1;
  126.         }
  127.         tp->ptr = (char *)free_list[bucket];
  128.         ncomp += (tp->siz = bsiz + sizeof(M_HEAD));
  129.         free_list[bucket] = free_list[bucket]->next;
  130.     }
  131. loopexit:
  132.     if (ncomp == 0)
  133.         return(0);        /* nothing new to compact */
  134. #ifdef MSTATS
  135.     b_ncompacted += ncomp;
  136. #endif
  137.     tp = mtab(&cptab); n = mtablen(&cptab);        /* sort table */
  138.     qsort((char *)tp, n, sizeof(struct mblk), mbcmp);
  139.     ncomp = 0;                    /* collect blocks */
  140.     while (--n && tp[1].siz) {
  141.         if (tp[0].ptr + tp[0].siz == tp[1].ptr) {
  142.             tp[1].ptr = tp[0].ptr;
  143.             tp[1].siz += tp[0].siz;
  144.             ncomp += tp[0].siz;
  145.             tp[0].siz = 0;
  146.         }
  147.         tp++;
  148.     }
  149.     return(ncomp);
  150. }
  151.  
  152.  
  153. char *
  154. mcompact(np)        /* compact free lists to satisfy request */
  155. unsigned    *np;
  156. {
  157.     struct mblk    *tab;
  158.     unsigned    tablen;
  159.     register struct mblk    *bp, *big;
  160.  
  161.     for ( ; ; ) {
  162.                     /* compact free lists */
  163.         compactfree();
  164.                     /* find largest block */
  165.         tab = mtab(&cptab); tablen = mtablen(&cptab);
  166.         big = tab;
  167.         bp = tab + tablen;
  168.         while (--bp > tab)
  169.             if (bp->siz > big->siz)
  170.                 big = bp;
  171.         if (big->siz >= *np) {        /* big enough? */
  172.             *np = big->siz;
  173.             big->siz = 0;        /* remove from table */
  174.             return(big->ptr);    /* return it */
  175.         }
  176.         if (mtablen(big) <= tablen) {
  177.             *np = 0;        /* cannot grow table */
  178.             return(NULL);        /* report failure */
  179.         }
  180.                 /* enlarge table, free old one */
  181.         mtab(big)[0].ptr = cptab.ptr;
  182.         mtab(big)[0].siz = cptab.siz;
  183.         cptab.ptr = big->ptr;
  184.         cptab.siz = big->siz;
  185.         big->siz = 0;            /* clear and copy */
  186.         bcopy((char *)tab, (char *)(mtab(&cptab)+1),
  187.                 tablen*sizeof(struct mblk));
  188.         bzero((char *)(mtab(&cptab)+tablen+1),
  189.             (mtablen(&cptab)-tablen-1)*sizeof(struct mblk));
  190.     }            /* next round */
  191. }
  192. #endif        /* MCOMP */
  193.  
  194.  
  195. char *
  196. mscrounge(np)        /* search free lists to satisfy request */
  197. register unsigned    *np;
  198. {
  199.     char    *p;
  200.     register int    bucket;
  201.     register unsigned    bsiz;
  202.  
  203.     for (bucket = FIRSTBUCKET, bsiz = 1<<FIRSTBUCKET;
  204.             bucket < NBUCKETS; bucket++, bsiz <<= 1)
  205.         if (free_list[bucket] != NULL && bsiz+sizeof(M_HEAD) >= *np) {
  206.             *np = bsiz+sizeof(M_HEAD);
  207.             p = (char *)free_list[bucket];
  208.             free_list[bucket] = free_list[bucket]->next;
  209. #ifdef MSTATS
  210.             b_nscrounged += *np;
  211. #endif
  212.             return(p);
  213.         }
  214. #ifdef MCOMP
  215.     return(mcompact(np));        /* try compaction */
  216. #else
  217.     *np = 0;
  218.     return(NULL);
  219. #endif
  220. }
  221.  
  222.  
  223. char *
  224. bmalloc(n)        /* allocate a block of n bytes, sans header */
  225. register unsigned  n;
  226. {
  227.     extern char  *sbrk();
  228.     static unsigned  pagesz = 0;
  229.     static unsigned  amnt;
  230.     static char  *bpos;
  231.     static unsigned  nrem;
  232.     unsigned  thisamnt;
  233.     register char    *p;
  234.  
  235.     if (pagesz == 0) {                /* initialize */
  236.         pagesz = amnt = getpagesize();
  237.         nrem = (int)sbrk(0);            /* page align break */
  238.         nrem = pagesz - (nrem&(pagesz-1));
  239.         bpos = sbrk(nrem);
  240.         if ((int)bpos == -1)
  241.             return(NULL);
  242. #ifdef MSTATS
  243.         b_nsbrked += nrem;
  244. #endif
  245.         bpos += nrem & (BYTES_WORD-1);        /* align pointer */
  246.         nrem &= ~(BYTES_WORD-1);
  247.         memlim[0] = bpos;
  248.         memlim[1] = bpos + nrem;
  249.     }
  250.  
  251.     n = (n+(BYTES_WORD-1))&~(BYTES_WORD-1);        /* word align rqst. */
  252.  
  253.     if (n > nrem) {                    /* need more core */
  254.     tryagain:
  255.         if (n > amnt) {                /* big chunk */
  256.             thisamnt = (n+(pagesz-1))&~(pagesz-1);
  257.             if (thisamnt <= MAXINCR)    /* increase amnt */
  258.                 amnt = thisamnt;
  259.         } else
  260.             thisamnt = amnt;
  261.         p = sbrk(thisamnt);
  262.         if ((int)p == -1) {            /* uh-oh, ENOMEM */
  263.             errno = 0;            /* call cavalry */
  264.             if (thisamnt >= n+pagesz) {
  265.                 amnt = pagesz;        /* minimize request */
  266.                 goto tryagain;
  267.             }
  268.             thisamnt = n;
  269.             p = mscrounge(&thisamnt);    /* search free lists */
  270.             if (p == NULL) {        /* we're really out */
  271.                 errno = ENOMEM;
  272.                 return(NULL);
  273.             }
  274.         }
  275. #ifdef MSTATS
  276.         else b_nsbrked += thisamnt;
  277. #endif
  278.         if (p != bpos+nrem) {            /* not an increment */
  279.             bfree(bpos, nrem);        /* free what we have */
  280.             bpos = p;
  281.             nrem = thisamnt;
  282.         } else                    /* otherwise tack on */
  283.             nrem += thisamnt;
  284.         if (bpos < memlim[0])
  285.             memlim[0] = bpos;
  286.         if (bpos + nrem > memlim[1])
  287.             memlim[1] = bpos + nrem;
  288.     }
  289.     p = bpos;
  290.     bpos += n;                    /* advance */
  291.     nrem -= n;
  292. #ifdef MSTATS
  293.     b_nalloced += n;
  294. #endif
  295.     return(p);
  296. }
  297.  
  298.  
  299. bfree(p, n)            /* free n bytes of random memory */
  300. register char  *p;
  301. register unsigned  n;
  302. {
  303.     register int    bucket;
  304.     register unsigned    bsiz;
  305.  
  306.     if (n < 1<<FIRSTBUCKET)
  307.         return;
  308. #ifdef MSTATS
  309.     b_nfreed += n;
  310. #endif
  311.                     /* align pointer */
  312.     bsiz = BYTES_WORD - ((unsigned)p&(BYTES_WORD-1));
  313.     if (bsiz < BYTES_WORD) {
  314.         p += bsiz;
  315.         n -= bsiz;
  316.     }
  317.     if (p < memlim[0])
  318.         memlim[0] = p;
  319.     if (p + n > memlim[1])
  320.         memlim[1] = p + n;
  321.                     /* fill big buckets first */
  322.     for (bucket = NBUCKETS-1, bsiz = 1<<(NBUCKETS-1);
  323.             bucket >= FIRSTBUCKET; bucket--, bsiz >>= 1)
  324.         if (n >= bsiz+sizeof(M_HEAD)) {
  325.             ((M_HEAD *)p)->next = free_list[bucket];
  326.             free_list[bucket] = (M_HEAD *)p;
  327.             p += bsiz+sizeof(M_HEAD);
  328.             n -= bsiz+sizeof(M_HEAD);
  329.         }
  330. }
  331.  
  332.  
  333. char *
  334. malloc(n)            /* allocate n bytes of memory */
  335. unsigned    n;
  336. {
  337.     register M_HEAD    *mp;
  338.     register int    bucket;
  339.     register unsigned    bsiz;
  340.                     /* don't return NULL on 0 request */
  341.     if (n == 0)
  342.         return(DUMMYLOC);
  343.                     /* find first bucket that fits */
  344.     for (bucket = FIRSTBUCKET, bsiz = 1<<FIRSTBUCKET;
  345.             bucket < NBUCKETS; bucket++, bsiz <<= 1)
  346.         if (bsiz >= n)
  347.             break;
  348.     if (bucket >= NBUCKETS) {
  349.         errno = EINVAL;
  350.         return(NULL);
  351.     }
  352.     if (free_list[bucket] == NULL) {    /* need more core */
  353.         mp = (M_HEAD *)bmalloc(bsiz+sizeof(M_HEAD));
  354.         if (mp == NULL)
  355.             return(NULL);
  356.     } else {                /* got it */
  357.         mp = free_list[bucket];
  358.         free_list[bucket] = mp->next;
  359.     }
  360. #ifdef MSTATS
  361.     m_nalloced += bsiz + sizeof(M_HEAD);
  362.     m_nwasted += bsiz + sizeof(M_HEAD) - n;
  363. #endif
  364.     mp->a.magic = MAGIC;            /* tag block */
  365.     mp->a.bucket = bucket;
  366.     return((char *)(mp+1));
  367. }
  368.  
  369.  
  370. char *
  371. realloc(op, n)            /* reallocate memory using malloc() */
  372. register char    *op;
  373. unsigned    n;
  374. {
  375.     char    *p;
  376.     register unsigned    on;
  377.                     /* get old size */
  378.     if (op != DUMMYLOC && !BADPTR(op) &&
  379.             ((M_HEAD *)op-1)->a.magic == MAGIC)
  380.         on = 1 << ((M_HEAD *)op-1)->a.bucket;
  381.     else
  382.         on = 0;
  383.     if (n <= on && (n > on>>1 || on == 1<<FIRSTBUCKET))
  384.         return(op);        /* same bucket */
  385.     if ((p = malloc(n)) == NULL)
  386.         return(n<=on ? op : NULL);
  387.     if (on) {
  388.         bcopy(op, p, n>on ? on : n);
  389.         free(op);
  390.     }
  391.     return(p);
  392. }
  393.  
  394.  
  395. free(p)            /* free memory allocated by malloc */
  396. char    *p;
  397. {
  398.     register M_HEAD    *mp;
  399.     register int    bucket;
  400.  
  401.     if (p == DUMMYLOC)
  402.         return(1);
  403.     if (BADPTR(p))
  404.         goto invalid;
  405.     mp = (M_HEAD *)p - 1;
  406.     if (mp->a.magic != MAGIC)        /* sanity check */
  407.         goto invalid;
  408.     bucket = mp->a.bucket;
  409.     if (bucket < FIRSTBUCKET | bucket >= NBUCKETS)
  410.         goto invalid;
  411.     mp->next = free_list[bucket];
  412.     free_list[bucket] = mp;
  413. #ifdef MSTATS
  414.     m_nfreed += (1 << bucket) + sizeof(M_HEAD);
  415. #endif
  416.     return(1);
  417. invalid:
  418.     errno = EINVAL;
  419.     return(0);
  420. }
  421.  
  422.  
  423. #ifdef MSTATS
  424. printmemstats(fp)        /* print memory statistics to stream */
  425. FILE    *fp;
  426. {
  427.     register int    i;
  428.     int    n;
  429.     register M_HEAD    *mp;
  430.     unsigned int    total = 0;
  431.  
  432.     fprintf(fp, "Memory statistics:\n");
  433.     fprintf(fp, "\tbmalloc: %d bytes from sbrk\n", b_nsbrked);
  434.     fprintf(fp, "\tbmalloc: %d bytes allocated\n", b_nalloced);
  435.     fprintf(fp, "\tbmalloc: %d bytes freed\n", b_nfreed);
  436.     fprintf(fp, "\tbmalloc: %d bytes scrounged\n", b_nscrounged);
  437.     fprintf(fp, "\tbmalloc: %d bytes compacted\n", b_ncompacted);
  438.     fprintf(fp, "\tmalloc: %d bytes allocated\n", m_nalloced);
  439.     fprintf(fp, "\tmalloc: %d bytes wasted (%.1f%%)\n", m_nwasted,
  440.             100.0*m_nwasted/m_nalloced);
  441.     fprintf(fp, "\tmalloc: %d bytes freed\n", m_nfreed);
  442.     for (i = NBUCKETS-1; i >= FIRSTBUCKET; i--) {
  443.         n = 0;
  444.         for (mp = free_list[i]; mp != NULL; mp = mp->next)
  445.             n++;
  446.         if (n) {
  447.             fprintf(fp, "\t%d * %u\n", n, 1<<i);
  448.             total += n * ((1<<i) + sizeof(M_HEAD));
  449.         }
  450.     }
  451.     fprintf(fp, "\t %u total bytes in free list\n", total);
  452. }
  453. #endif
  454.