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