home *** CD-ROM | disk | FTP | other *** search
/ ftp.freefriends.org / ftp.freefriends.org.tar / ftp.freefriends.org / arnold / Source / mush.rstevens.tar.gz / mush.tar / malloc.c < prev    next >
C/C++ Source or Header  |  1991-05-16  |  11KB  |  457 lines
  1. /*
  2.  * This is a slightly modified version of the malloc.c distributed with
  3.  * Larry Wall's perl 2.0 sources.  RCS and sccs information has been
  4.  * retained, but modified so that it will not actually affect checkin
  5.  * or checkout of this file if revision control is used for Mush.
  6.  *
  7.  * Other changes include:
  8.  *    Removal of the ASSERT macro and other code related to the
  9.  *    preprocessor definition "debug"
  10.  *
  11.  *    Replaced #include "perl.h" with #include "mush.h" (guess why)
  12.  *
  13.  *    Warning messages are now printed with the mush Debug macro,
  14.  *    that is, they are normally suppressed
  15.  *
  16.  *    Added a calloc() function, using mush's bzero()
  17.  *
  18.  * Also, the mush xfree() and free_vec() functions have been moved here.
  19.  */
  20.  
  21. #include "mush.h"
  22.  
  23. /*
  24.  * Compile this portion only if configured for INTERNAL_MALLOC
  25.  */
  26. #ifdef INTERNAL_MALLOC
  27. #ifdef SYSV
  28. #include <memory.h>
  29. #define bcopy(src,dst,len)    memcpy(dst,src,len)
  30. #endif /* SYSV */
  31. #define free xfree    /* rename free for mush purposes */
  32.  
  33. /* Begin modified perl malloc.c */
  34.  
  35. /* Header: malloc.c,v 2.0 88/06/05 00:09:16 root Exp
  36.  *
  37.  * Log:    malloc.c,v
  38.  * Revision 2.0  88/06/05  00:09:16  root
  39.  * Baseline version 2.0.
  40.  * 
  41.  */
  42.  
  43. #ifndef lint
  44. static char sccsid[] = "malloc.c    4.3 (Berkeley) 9/16/83";
  45. #endif /* !lint */
  46.  
  47. #define RCHECK
  48. /*
  49.  * malloc.c (Caltech) 2/21/82
  50.  * Chris Kingsley, kingsley@cit-20.
  51.  *
  52.  * This is a very fast storage allocator.  It allocates blocks of a small 
  53.  * number of different sizes, and keeps free lists of each size.  Blocks that
  54.  * don't exactly fit are passed up to the next larger size.  In this 
  55.  * implementation, the available sizes are 2^n-4 (or 2^n-12) bytes long.
  56.  * This is designed for use in a program that uses vast quantities of memory,
  57.  * but bombs when it runs out. 
  58.  */
  59.  
  60. /* I don't much care whether these are defined in sys/types.h--LAW */
  61.  
  62. #undef u_char
  63. #define u_char unsigned char
  64. #undef u_int
  65. #define u_int unsigned int
  66. #undef u_short
  67. #define u_short unsigned short
  68.  
  69. /*
  70.  * The overhead on a block is at least 4 bytes.  When free, this space
  71.  * contains a pointer to the next free block, and the bottom two bits must
  72.  * be zero.  When in use, the first byte is set to MAGIC, and the second
  73.  * byte is the size index.  The remaining bytes are for alignment.
  74.  * If range checking is enabled and the size of the block fits
  75.  * in two bytes, then the top two bytes hold the size of the requested block
  76.  * plus the range checking words, and the header word MINUS ONE.
  77.  */
  78. union    overhead {
  79.     union    overhead *ov_next;    /* when free */
  80.     struct {
  81.         u_char    ovu_magic;    /* magic number */
  82.         u_char    ovu_index;    /* bucket # */
  83. #ifdef RCHECK
  84.         u_short    ovu_size;    /* actual block size */
  85.         u_int    ovu_rmagic;    /* range magic number */
  86. #endif /* RCHECK */
  87.     } ovu;
  88. #define    ov_magic    ovu.ovu_magic
  89. #define    ov_index    ovu.ovu_index
  90. #define    ov_size        ovu.ovu_size
  91. #define    ov_rmagic    ovu.ovu_rmagic
  92. };
  93.  
  94. #define    MAGIC        0xff        /* magic # on accounting info */
  95. #define OLDMAGIC    0x7f        /* same after a free() */
  96. #define RMAGIC        0x55555555    /* magic # on range info */
  97. #ifdef RCHECK
  98. #define    RSLOP        sizeof (u_int)
  99. #else /* !RCHECK */
  100. #define    RSLOP        0
  101. #endif /* RCHECK */
  102.  
  103. /*
  104.  * nextf[i] is the pointer to the next free block of size 2^(i+3).  The
  105.  * smallest allocatable block is 8 bytes.  The overhead information
  106.  * precedes the data area returned to the user.
  107.  */
  108. #define    NBUCKETS 30
  109. static    union overhead *nextf[NBUCKETS];
  110. extern    char *sbrk();
  111.  
  112. #ifdef MSTATS
  113. /*
  114.  * nmalloc[i] is the difference between the number of mallocs and frees
  115.  * for a given block size.
  116.  */
  117. static    u_int nmalloc[NBUCKETS];
  118. #endif /* MSTATS */
  119.  
  120. char *
  121. malloc(nbytes)
  122.     register unsigned nbytes;
  123. {
  124.     register union overhead *p;
  125.     register int bucket = 0;
  126.     register unsigned shiftr;
  127.  
  128.     if (nbytes == 0)
  129.         return NULL;
  130.     /*
  131.      * Convert amount of memory requested into
  132.      * closest block size stored in hash buckets
  133.      * which satisfies request.  Account for
  134.      * space used per block for accounting.
  135.      */
  136.     nbytes += sizeof (union overhead) + RSLOP;
  137.     nbytes = (nbytes + 3) &~ 3; 
  138.     shiftr = (nbytes - 1) >> 2;
  139.     /* apart from this loop, this is O(1) */
  140.     while (shiftr >>= 1)
  141.         bucket++;
  142.     /*
  143.      * If nothing in hash bucket right now,
  144.      * request more memory from the system.
  145.      */
  146.     if (nextf[bucket] == (union overhead *)0)    
  147.         morecore(bucket);
  148.     if ((p = (union overhead *)nextf[bucket]) == (union overhead *)0)
  149.         return (NULL);
  150.     /* remove from linked list */
  151.     if (*((int*)p) > 0x10000000)
  152.         Debug("Corrupt malloc ptr 0x%x at 0x%x\n",*((int*)p),p);
  153.     nextf[bucket] = nextf[bucket]->ov_next;
  154.     p->ov_magic = MAGIC;
  155.     p->ov_index= bucket;
  156. #ifdef MSTATS
  157.     nmalloc[bucket]++;
  158. #endif /* MSTATS */
  159. #ifdef RCHECK
  160.     /*
  161.      * Record allocated size of block and
  162.      * bound space with magic numbers.
  163.      */
  164.     if (nbytes <= 0x10000)
  165.         p->ov_size = nbytes - 1;
  166.     p->ov_rmagic = RMAGIC;
  167.     *((u_int *)((caddr_t)p + nbytes - RSLOP)) = RMAGIC;
  168. #endif /* RCHECK */
  169.     return ((char *)(p + 1));
  170. }
  171.  
  172. /*
  173.  * Allocate more memory to the indicated bucket.
  174.  */
  175. static
  176. morecore(bucket)
  177.     register bucket;
  178. {
  179.     register union overhead *op;
  180.     register int rnu;       /* 2^rnu bytes will be requested */
  181.     register int nblks;     /* become nblks blocks of the desired size */
  182.     register int siz;
  183.  
  184.     if (nextf[bucket])
  185.         return;
  186.     /*
  187.      * Insure memory is allocated
  188.      * on a page boundary.  Should
  189.      * make getpageize call?
  190.      */
  191.     op = (union overhead *)sbrk(0);
  192.     if ((long)op & 0x3ff)
  193.         sbrk(1024 - ((long)op & 0x3ff));
  194.     /* take 2k unless the block is bigger than that */
  195.     rnu = (bucket <= 8) ? 11 : bucket + 3;
  196.     nblks = 1 << (rnu - (bucket + 3));  /* how many blocks to get */
  197.     if (rnu < bucket)
  198.         rnu = bucket;
  199.     op = (union overhead *)sbrk(1 << rnu);
  200.     /* no more room! */
  201.     if ((long)op == -1)
  202.         return;
  203.     /*
  204.      * Round up to minimum allocation size boundary
  205.      * and deduct from block count to reflect.
  206.      */
  207.     if ((long)op & 7) {
  208.         op = (union overhead *)(((long)op + 8) &~ 7);
  209.         nblks--;
  210.     }
  211.     /*
  212.      * Add new memory allocated to that on
  213.      * free list for this hash bucket.
  214.      */
  215.     nextf[bucket] = op;
  216.     siz = 1 << (bucket + 3);
  217.     while (--nblks > 0) {
  218.         op->ov_next = (union overhead *)((caddr_t)op + siz);
  219.         op = (union overhead *)((caddr_t)op + siz);
  220.     }
  221. }
  222.  
  223. void
  224. free(cp)
  225.     char *cp;
  226. {   
  227.     register int size;
  228.     register union overhead *op;
  229.  
  230.     if (cp == NULL || debug > 4)
  231.         return;
  232.     op = (union overhead *)((caddr_t)cp - sizeof (union overhead));
  233.     if (op->ov_magic != MAGIC) {
  234.         Debug("%s free() ignored\n",
  235.             op->ov_magic == OLDMAGIC ? "Duplicate" : "Bad");
  236.         return;                /* sanity */
  237.     }
  238.     op->ov_magic = OLDMAGIC;
  239. #ifdef RCHECK
  240.     if (op->ov_rmagic != RMAGIC) {
  241.         Debug("Range check failed, free() ignored\n");
  242.         return;
  243.     }
  244.     if (op->ov_index <= 13 &&
  245.         *(u_int *)((caddr_t)op + op->ov_size + 1 - RSLOP) != RMAGIC) {
  246.         Debug("Range check failed, free() ignored\n");
  247.         return;
  248.     }
  249. #endif /* RCHECK */
  250.     if (op->ov_index >= NBUCKETS)
  251.         return;
  252.     size = op->ov_index;
  253.     op->ov_next = nextf[size];
  254.     nextf[size] = op;
  255. #ifdef MSTATS
  256.     nmalloc[size]--;
  257. #endif /* MSTATS */
  258. }
  259.  
  260. /*
  261.  * When a program attempts "storage compaction" as mentioned in the
  262.  * old malloc man page, it realloc's an already freed block.  Usually
  263.  * this is the last block it freed; occasionally it might be farther
  264.  * back.  We have to search all the free lists for the block in order
  265.  * to determine its bucket: 1st we make one pass thru the lists
  266.  * checking only the first block in each; if that fails we search
  267.  * ``reall_srchlen'' blocks in each list for a match (the variable
  268.  * is extern so the caller can modify it).  If that fails we just copy
  269.  * however many bytes was given to realloc() and hope it's not huge.
  270.  */
  271. int reall_srchlen = 4;    /* 4 should be plenty, -1 =>'s whole list */
  272.  
  273. char *
  274. realloc(cp, nbytes)
  275.     char *cp;
  276.     unsigned nbytes;
  277. {   
  278.     register u_int onb;
  279.     union overhead *op;
  280.     char *res;
  281.     register int i;
  282.     int was_alloced = 0;
  283.  
  284.     if (cp == NULL)
  285.         return (malloc(nbytes));
  286.     op = (union overhead *)((caddr_t)cp - sizeof (union overhead));
  287.     if (op->ov_magic == MAGIC) {
  288.         was_alloced++;
  289.         i = op->ov_index;
  290.     } else {
  291.         /*
  292.          * Already free, doing "compaction".
  293.          *
  294.          * Search for the old block of memory on the
  295.          * free list.  First, check the most common
  296.          * case (last element free'd), then (this failing)
  297.          * the last ``reall_srchlen'' items free'd.
  298.          * If all lookups fail, then assume the size of
  299.          * the memory block being realloc'd is the
  300.          * smallest possible.
  301.          */
  302.         if ((i = findbucket(op, 1)) < 0 &&
  303.             (i = findbucket(op, reall_srchlen)) < 0)
  304.             i = 0;
  305.     }
  306.     onb = (1 << (i + 3)) - sizeof (*op) - RSLOP;
  307. #ifdef RCHECK
  308.     /* There's something wrong with the "onb" size computation, above,
  309.      * when RCHECK is defined.  If you see this comment and can figure
  310.      * out exactly how "onb" is being used here, let me know.  Bart.
  311.      */
  312.     if (was_alloced) {
  313.         free(cp);    /* Hack so there's some chance res == cp */
  314.         was_alloced = 0;
  315.     }
  316. #else /* RCHECK */
  317.     /* avoid the copy if same size block */
  318.     if (was_alloced &&
  319.         nbytes <= onb && nbytes > (onb >> 1) - sizeof(*op) - RSLOP)
  320.         return(cp);
  321. #endif /* RCHECK */
  322.     if ((res = malloc(nbytes)) == NULL)
  323.         return (NULL);
  324.     if (cp != res)            /* common optimization */
  325.         bcopy(cp, res, (nbytes < onb) ? nbytes : onb);
  326.     if (was_alloced)
  327.         free(cp);
  328.     return (res);
  329. }
  330.  
  331. /*
  332.  * Search ``srchlen'' elements of each free list for a block whose
  333.  * header starts at ``freep''.  If srchlen is -1 search the whole list.
  334.  * Return bucket number, or -1 if not found.
  335.  */
  336. static
  337. findbucket(freep, srchlen)
  338.     union overhead *freep;
  339.     int srchlen;
  340. {
  341.     register union overhead *p;
  342.     register int i, j;
  343.  
  344.     for (i = 0; i < NBUCKETS; i++) {
  345.         j = 0;
  346.         for (p = nextf[i]; p && j != srchlen; p = p->ov_next) {
  347.             if (p == freep)
  348.                 return (i);
  349.             j++;
  350.         }
  351.     }
  352.     return (-1);
  353. }
  354.  
  355. #ifdef MSTATS
  356. /*
  357.  * mstats - print out statistics about malloc
  358.  * 
  359.  * Prints two lines of numbers, one showing the length of the free list
  360.  * for each size category, the second showing the number of mallocs -
  361.  * frees for each size category.
  362.  */
  363. mstats(s)
  364.     char *s;
  365. {
  366.     register int i, j;
  367.     register union overhead *p;
  368.     int totfree = 0,
  369.     totused = 0;
  370.  
  371.     Debug("Memory allocation statistics %s\nfree:\t", s);
  372.     for (i = 0; i < NBUCKETS; i++) {
  373.         for (j = 0, p = nextf[i]; p; p = p->ov_next, j++)
  374.             ;
  375.         Debug(" %d", j);
  376.         totfree += j * (1 << (i + 3));
  377.     }
  378.     Debug("\nused:\t");
  379.     for (i = 0; i < NBUCKETS; i++) {
  380.         Debug( " %d", nmalloc[i]);
  381.         totused += nmalloc[i] * (1 << (i + 3));
  382.     }
  383.     Debug("\n\tTotal in use: %d, total free: %d\n",
  384.         totused, totfree);
  385. }
  386. #endif /* MSTATS */
  387.  
  388. /* End of modified perl malloc.c */
  389.  
  390. char *
  391. calloc(nitems, itemsz)
  392. u_int nitems, itemsz;
  393. {
  394.     char *cp;
  395.  
  396.     cp = malloc(nitems * itemsz);
  397.     bzero(cp, nitems * itemsz);
  398.     return cp;
  399. }
  400.  
  401. /* These are needed for curses and other external linkage */
  402.  
  403. #undef free
  404.  
  405. char *
  406. cfree(p, n, s)
  407. char *p;
  408. u_int n, s;
  409. {
  410.     xfree(p);
  411.     return NULL;
  412. }
  413.  
  414. char *
  415. free(p)
  416. char *p;
  417. {
  418.     xfree(p);
  419.     return NULL;
  420. }
  421.  
  422. #else /* INTERNAL_MALLOC */
  423.  
  424. char *stackbottom;    /* set first thing in main() */
  425.  
  426. void
  427. xfree(cp)
  428. char *cp;
  429. {
  430.     extern char end[];
  431.  
  432.     if (cp && cp >= end && cp < stackbottom && cp < (char *) &cp && debug < 5)
  433.     free(cp);
  434. }
  435.  
  436. #endif /* INTERNAL_MALLOC */
  437.  
  438. void
  439. free_elems(argv)
  440. char **argv;
  441. {
  442.     register int n;
  443.  
  444.     if (!argv)
  445.     return;
  446.     for (n = 0; argv[n]; n++)
  447.     xfree(argv[n]);
  448. }
  449.  
  450. void
  451. free_vec(argv)
  452. char **argv;
  453. {
  454.     free_elems(argv);
  455.     xfree((char *)argv);
  456. }
  457.