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