home *** CD-ROM | disk | FTP | other *** search
/ APDL Public Domain 1 / APDL_PD1A.iso / program / language / perl / Source / C / Malloc < prev    next >
Encoding:
Text File  |  1991-02-09  |  10.7 KB  |  414 lines
  1. /* $Header: malloc.c,v 3.0.1.5 91/01/11 18:09:52 lwall Locked $
  2.  *
  3.  * $Log:    malloc.c,v $
  4.  * Revision 3.0.1.5  91/01/11  18:09:52  lwall
  5.  * patch42: Configure now checks alignment requirements
  6.  * 
  7.  * Revision 3.0.1.4  90/11/13  15:23:45  lwall
  8.  * patch41: added hp malloc union overhead strut (that sounds very blue collar)
  9.  * 
  10.  * Revision 3.0.1.3  90/10/16  15:27:47  lwall
  11.  * patch29: various portability fixes
  12.  * 
  13.  * Revision 3.0.1.2  89/11/11  04:36:37  lwall
  14.  * patch2: malloc pointer corruption check made more portable
  15.  * 
  16.  * Revision 3.0.1.1  89/10/26  23:15:05  lwall
  17.  * patch1: some declarations were missing from malloc.c
  18.  * patch1: sparc machines had alignment problems in malloc.c
  19.  * 
  20.  * Revision 3.0  89/10/18  15:20:39  lwall
  21.  * 3.0 baseline
  22.  * 
  23.  */
  24.  
  25. #ifndef lint
  26. static char sccsid[] = "@(#)malloc.c    4.3 (Berkeley) 9/16/83";
  27.  
  28. #ifdef DEBUGGING
  29. #define RCHECK
  30. #endif
  31. /*
  32.  * malloc.c (Caltech) 2/21/82
  33.  * Chris Kingsley, kingsley@cit-20.
  34.  *
  35.  * This is a very fast storage allocator.  It allocates blocks of a small 
  36.  * number of different sizes, and keeps free lists of each size.  Blocks that
  37.  * don't exactly fit are passed up to the next larger size.  In this 
  38.  * implementation, the available sizes are 2^n-4 (or 2^n-12) bytes long.
  39.  * This is designed for use in a program that uses vast quantities of memory,
  40.  * but bombs when it runs out. 
  41.  */
  42.  
  43. #include "EXTERN.h"
  44. #include "perl.h"
  45.  
  46. static findbucket(), morecore();
  47.  
  48. /* I don't much care whether these are defined in sys/types.h--LAW */
  49.  
  50. #define u_char unsigned char
  51. #define u_int unsigned int
  52. #define u_short unsigned short
  53.  
  54. /*
  55.  * The overhead on a block is at least 4 bytes.  When free, this space
  56.  * contains a pointer to the next free block, and the bottom two bits must
  57.  * be zero.  When in use, the first byte is set to MAGIC, and the second
  58.  * byte is the size index.  The remaining bytes are for alignment.
  59.  * If range checking is enabled and the size of the block fits
  60.  * in two bytes, then the top two bytes hold the size of the requested block
  61.  * plus the range checking words, and the header word MINUS ONE.
  62.  */
  63. union    overhead {
  64.     union    overhead *ov_next;    /* when free */
  65. #if ALIGNBYTES > 4
  66.     double    strut;            /* alignment problems */
  67. #endif
  68.     struct {
  69.         u_char    ovu_magic;    /* magic number */
  70.         u_char    ovu_index;    /* bucket # */
  71. #ifdef RCHECK
  72.         u_short    ovu_size;    /* actual block size */
  73.         u_int    ovu_rmagic;    /* range magic number */
  74. #endif
  75.     } ovu;
  76. #define    ov_magic    ovu.ovu_magic
  77. #define    ov_index    ovu.ovu_index
  78. #define    ov_size        ovu.ovu_size
  79. #define    ov_rmagic    ovu.ovu_rmagic
  80. };
  81.  
  82. #define    MAGIC        0xff        /* magic # on accounting info */
  83. #define OLDMAGIC    0x7f        /* same after a free() */
  84. #define RMAGIC        0x55555555    /* magic # on range info */
  85. #ifdef RCHECK
  86. #define    RSLOP        sizeof (u_int)
  87. #else
  88. #define    RSLOP        0
  89. #endif
  90.  
  91. /*
  92.  * nextf[i] is the pointer to the next free block of size 2^(i+3).  The
  93.  * smallest allocatable block is 8 bytes.  The overhead information
  94.  * precedes the data area returned to the user.
  95.  */
  96. #define    NBUCKETS 30
  97. static    union overhead *nextf[NBUCKETS];
  98. extern    char *sbrk();
  99.  
  100. #ifdef MSTATS
  101. /*
  102.  * nmalloc[i] is the difference between the number of mallocs and frees
  103.  * for a given block size.
  104.  */
  105. static    u_int nmalloc[NBUCKETS];
  106. #include <stdio.h>
  107. #endif
  108.  
  109. #ifdef debug
  110. #define    ASSERT(p)   if (!(p)) botch("p"); else
  111. static
  112. botch(s)
  113.     char *s;
  114. {
  115.  
  116.     printf("assertion botched: %s\n", s);
  117.     abort();
  118. }
  119. #else
  120. #define    ASSERT(p)
  121. #endif
  122.  
  123. char *
  124. malloc(nbytes)
  125.     register unsigned nbytes;
  126. {
  127.       register union overhead *p;
  128.       register int bucket = 0;
  129.       register unsigned shiftr;
  130.  
  131.     /*
  132.      * Convert amount of memory requested into
  133.      * closest block size stored in hash buckets
  134.      * which satisfies request.  Account for
  135.      * space used per block for accounting.
  136.      */
  137.       nbytes += sizeof (union overhead) + RSLOP;
  138.       nbytes = (nbytes + 3) &~ 3; 
  139.       shiftr = (nbytes - 1) >> 2;
  140.     /* apart from this loop, this is O(1) */
  141.       while (shiftr >>= 1)
  142.           bucket++;
  143.     /*
  144.      * If nothing in hash bucket right now,
  145.      * request more memory from the system.
  146.      */
  147.       if (nextf[bucket] == NULL)    
  148.           morecore(bucket);
  149.       if ((p = (union overhead *)nextf[bucket]) == NULL)
  150.           return (NULL);
  151.     /* remove from linked list */
  152. #ifdef RCHECK
  153.     if (*((int*)p) & (sizeof(union overhead) - 1))
  154. #ifndef I286
  155.         fprintf(stderr,"Corrupt malloc ptr 0x%x at 0x%x\n",*((int*)p),p);
  156. #else
  157.         fprintf(stderr,"Corrupt malloc ptr 0x%lx at 0x%lx\n",*((int*)p),p);
  158. #endif
  159. #endif
  160.       nextf[bucket] = p->ov_next;
  161.     p->ov_magic = MAGIC;
  162.     p->ov_index= bucket;
  163. #ifdef MSTATS
  164.       nmalloc[bucket]++;
  165. #endif
  166. #ifdef RCHECK
  167.     /*
  168.      * Record allocated size of block and
  169.      * bound space with magic numbers.
  170.      */
  171.       if (nbytes <= 0x10000)
  172.         p->ov_size = nbytes - 1;
  173.     p->ov_rmagic = RMAGIC;
  174.       *((u_int *)((caddr_t)p + nbytes - RSLOP)) = RMAGIC;
  175. #endif
  176.       return ((char *)(p + 1));
  177. }
  178.  
  179. /*
  180.  * Allocate more memory to the indicated bucket.
  181.  */
  182. static
  183. morecore(bucket)
  184.     register int bucket;
  185. {
  186.       register union overhead *op;
  187.       register int rnu;       /* 2^rnu bytes will be requested */
  188.       register int nblks;     /* become nblks blocks of the desired size */
  189.     register int siz;
  190.  
  191.       if (nextf[bucket])
  192.           return;
  193.     /*
  194.      * Insure memory is allocated
  195.      * on a page boundary.  Should
  196.      * make getpageize call?
  197.      */
  198.       op = (union overhead *)sbrk(0);
  199. #ifndef I286
  200.       if ((int)op & 0x3ff)
  201.           (void)sbrk(1024 - ((int)op & 0x3ff));
  202. #else
  203.     /* The sbrk(0) call on the I286 always returns the next segment */
  204. #endif
  205.  
  206. #ifndef I286
  207.     /* take 2k unless the block is bigger than that */
  208.       rnu = (bucket <= 8) ? 11 : bucket + 3;
  209. #else
  210.     /* take 16k unless the block is bigger than that 
  211.        (80286s like large segments!)        */
  212.       rnu = (bucket <= 11) ? 14 : bucket + 3;
  213. #endif
  214.       nblks = 1 << (rnu - (bucket + 3));  /* how many blocks to get */
  215.       if (rnu < bucket)
  216.         rnu = bucket;
  217.     op = (union overhead *)sbrk(1 << rnu);
  218.     /* no more room! */
  219.       if ((int)op == -1)
  220.           return;
  221.     /*
  222.      * Round up to minimum allocation size boundary
  223.      * and deduct from block count to reflect.
  224.      */
  225. #ifndef I286
  226.       if ((int)op & 7) {
  227.           op = (union overhead *)(((int)op + 8) &~ 7);
  228.           nblks--;
  229.       }
  230. #else
  231.     /* Again, this should always be ok on an 80286 */
  232. #endif
  233.     /*
  234.      * Add new memory allocated to that on
  235.      * free list for this hash bucket.
  236.      */
  237.       nextf[bucket] = op;
  238.       siz = 1 << (bucket + 3);
  239.       while (--nblks > 0) {
  240.         op->ov_next = (union overhead *)((caddr_t)op + siz);
  241.         op = (union overhead *)((caddr_t)op + siz);
  242.       }
  243. }
  244.  
  245. free(cp)
  246.     char *cp;
  247. {   
  248.       register int size;
  249.     register union overhead *op;
  250.  
  251.       if (cp == NULL)
  252.           return;
  253.     op = (union overhead *)((caddr_t)cp - sizeof (union overhead));
  254. #ifdef debug
  255.       ASSERT(op->ov_magic == MAGIC);        /* make sure it was in use */
  256. #else
  257.     if (op->ov_magic != MAGIC) {
  258.         warn("%s free() ignored",
  259.             op->ov_magic == OLDMAGIC ? "Duplicate" : "Bad");
  260.         return;                /* sanity */
  261.     }
  262.     op->ov_magic = OLDMAGIC;
  263. #endif
  264. #ifdef RCHECK
  265.       ASSERT(op->ov_rmagic == RMAGIC);
  266.     if (op->ov_index <= 13)
  267.         ASSERT(*(u_int *)((caddr_t)op + op->ov_size + 1 - RSLOP) == RMAGIC);
  268. #endif
  269.       ASSERT(op->ov_index < NBUCKETS);
  270.       size = op->ov_index;
  271.     op->ov_next = nextf[size];
  272.       nextf[size] = op;
  273. #ifdef MSTATS
  274.       nmalloc[size]--;
  275. #endif
  276. }
  277.  
  278. /*
  279.  * When a program attempts "storage compaction" as mentioned in the
  280.  * old malloc man page, it realloc's an already freed block.  Usually
  281.  * this is the last block it freed; occasionally it might be farther
  282.  * back.  We have to search all the free lists for the block in order
  283.  * to determine its bucket: 1st we make one pass thru the lists
  284.  * checking only the first block in each; if that fails we search
  285.  * ``reall_srchlen'' blocks in each list for a match (the variable
  286.  * is extern so the caller can modify it).  If that fails we just copy
  287.  * however many bytes was given to realloc() and hope it's not huge.
  288.  */
  289. int reall_srchlen = 4;    /* 4 should be plenty, -1 =>'s whole list */
  290.  
  291. char *
  292. realloc(cp, nbytes)
  293.     char *cp; 
  294.     unsigned nbytes;
  295. {   
  296.       register u_int onb;
  297.     union overhead *op;
  298.       char *res;
  299.     register int i;
  300.     int was_alloced = 0;
  301.  
  302.       if (cp == NULL)
  303.           return (malloc(nbytes));
  304.     op = (union overhead *)((caddr_t)cp - sizeof (union overhead));
  305.     if (op->ov_magic == MAGIC) {
  306.         was_alloced++;
  307.         i = op->ov_index;
  308.     } else {
  309.         /*
  310.          * Already free, doing "compaction".
  311.          *
  312.          * Search for the old block of memory on the
  313.          * free list.  First, check the most common
  314.          * case (last element free'd), then (this failing)
  315.          * the last ``reall_srchlen'' items free'd.
  316.          * If all lookups fail, then assume the size of
  317.          * the memory block being realloc'd is the
  318.          * smallest possible.
  319.          */
  320.         if ((i = findbucket(op, 1)) < 0 &&
  321.             (i = findbucket(op, reall_srchlen)) < 0)
  322.             i = 0;
  323.     }
  324.     onb = (1 << (i + 3)) - sizeof (*op) - RSLOP;
  325.     /* avoid the copy if same size block */
  326.     if (was_alloced &&
  327.         nbytes <= onb && nbytes > (onb >> 1) - sizeof(*op) - RSLOP) {
  328. #ifdef RCHECK
  329.         /*
  330.          * Record new allocated size of block and
  331.          * bound space with magic numbers.
  332.          */
  333.         if (op->ov_index <= 13) {
  334.             /*
  335.              * Convert amount of memory requested into
  336.              * closest block size stored in hash buckets
  337.              * which satisfies request.  Account for
  338.              * space used per block for accounting.
  339.              */
  340.             nbytes += sizeof (union overhead) + RSLOP;
  341.             nbytes = (nbytes + 3) &~ 3; 
  342.             op->ov_size = nbytes - 1;
  343.             *((u_int *)((caddr_t)op + nbytes - RSLOP)) = RMAGIC;
  344.         }
  345. #endif
  346.         return(cp);
  347.     }
  348.       if ((res = malloc(nbytes)) == NULL)
  349.           return (NULL);
  350.       if (cp != res)            /* common optimization */
  351.         (void)bcopy(cp, res, (int)((nbytes < onb) ? nbytes : onb));
  352.       if (was_alloced)
  353.         free(cp);
  354.       return (res);
  355. }
  356.  
  357. /*
  358.  * Search ``srchlen'' elements of each free list for a block whose
  359.  * header starts at ``freep''.  If srchlen is -1 search the whole list.
  360.  * Return bucket number, or -1 if not found.
  361.  */
  362. static
  363. findbucket(freep, srchlen)
  364.     union overhead *freep;
  365.     int srchlen;
  366. {
  367.     register union overhead *p;
  368.     register int i, j;
  369.  
  370.     for (i = 0; i < NBUCKETS; i++) {
  371.         j = 0;
  372.         for (p = nextf[i]; p && j != srchlen; p = p->ov_next) {
  373.             if (p == freep)
  374.                 return (i);
  375.             j++;
  376.         }
  377.     }
  378.     return (-1);
  379. }
  380.  
  381. #ifdef MSTATS
  382. /*
  383.  * mstats - print out statistics about malloc
  384.  * 
  385.  * Prints two lines of numbers, one showing the length of the free list
  386.  * for each size category, the second showing the number of mallocs -
  387.  * frees for each size category.
  388.  */
  389. mstats(s)
  390.     char *s;
  391. {
  392.       register int i, j;
  393.       register union overhead *p;
  394.       int totfree = 0,
  395.       totused = 0;
  396.  
  397.       fprintf(stderr, "Memory allocation statistics %s\nfree:\t", s);
  398.       for (i = 0; i < NBUCKETS; i++) {
  399.           for (j = 0, p = nextf[i]; p; p = p->ov_next, j++)
  400.               ;
  401.           fprintf(stderr, " %d", j);
  402.           totfree += j * (1 << (i + 3));
  403.       }
  404.       fprintf(stderr, "\nused:\t");
  405.       for (i = 0; i < NBUCKETS; i++) {
  406.           fprintf(stderr, " %d", nmalloc[i]);
  407.           totused += nmalloc[i] * (1 << (i + 3));
  408.       }
  409.       fprintf(stderr, "\n\tTotal in use: %d, total free: %d\n",
  410.         totused, totfree);
  411. }
  412. #endif
  413. #endif /* lint */
  414.