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