home *** CD-ROM | disk | FTP | other *** search
/ Games of Daze / Infomagic - Games of Daze (Summer 1995) (Disc 1 of 2).iso / djgpp / libsrc / c / lib / malloc.c < prev    next >
Encoding:
C/C++ Source or Header  |  1994-07-27  |  11.0 KB  |  412 lines
  1. /*
  2.  * Copyright (c) 1983 Regents of the University of California.
  3.  * All rights reserved.
  4.  *
  5.  * Redistribution and use in source and binary forms are permitted
  6.  * provided that: (1) source distributions retain this entire copyright
  7.  * notice and comment, and (2) distributions including binaries display
  8.  * the following acknowledgement:  ``This product includes software
  9.  * developed by the University of California, Berkeley and its contributors''
  10.  * in the documentation or other materials provided with the distribution
  11.  * and in all advertising materials mentioning features or use of this
  12.  * software. Neither the name of the University nor the names of its
  13.  * contributors may be used to endorse or promote products derived
  14.  * from this software without specific prior written permission.
  15.  * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR
  16.  * IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED
  17.  * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
  18.  */
  19.  
  20. #if defined(LIBC_SCCS) && !defined(lint)
  21. static char sccsid[] = "@(#)malloc.c    5.9 (Berkeley) 6/1/90";
  22. #endif /* LIBC_SCCS and not lint */
  23.  
  24. /*
  25.  * malloc.c (Caltech) 2/21/82
  26.  * Chris Kingsley, kingsley@cit-20.
  27.  *
  28.  * This is a very fast storage allocator.  It allocates blocks of a small 
  29.  * number of different sizes, and keeps free lists of each size.  Blocks that
  30.  * don't exactly fit are passed up to the next larger size.  In this 
  31.  * implementation, the available sizes are 2^n-4 (or 2^n-10) bytes long.
  32.  * This is designed for use in a virtual memory environment.
  33.  */
  34.  
  35. #include <sys/types.h>
  36.  
  37. #define    NULL 0
  38.  
  39. /*
  40.  * The overhead on a block is at least 4 bytes.  When free, this space
  41.  * contains a pointer to the next free block, and the bottom two bits must
  42.  * be zero.  When in use, the first byte is set to MAGIC, and the second
  43.  * byte is the size index.  The remaining bytes are for alignment.
  44.  * If range checking is enabled then a second word holds the size of the
  45.  * requested block, less 1, rounded up to a multiple of sizeof(RMAGIC).
  46.  * The order of elements is critical: ov_magic must overlay the low order
  47.  * bits of ov_next, and ov_magic can not be a valid ov_next bit pattern.
  48.  */
  49. union    overhead {
  50.     union    overhead *ov_next;    /* when free */
  51.     struct {
  52.         u_char    ovu_magic;    /* magic number */
  53.         u_char    ovu_index;    /* bucket # */
  54. #ifdef RCHECK
  55.         u_short    ovu_rmagic;    /* range magic number */
  56.         u_int    ovu_size;    /* actual block size */
  57. #endif
  58.     } ovu;
  59. #define    ov_magic    ovu.ovu_magic
  60. #define    ov_index    ovu.ovu_index
  61. #define    ov_rmagic    ovu.ovu_rmagic
  62. #define    ov_size        ovu.ovu_size
  63. };
  64.  
  65. #define    MAGIC        0xef        /* magic # on accounting info */
  66. #define RMAGIC        0x5555        /* magic # on range info */
  67.  
  68. #ifdef RCHECK
  69. #define    RSLOP        sizeof (u_short)
  70. #else
  71. #define    RSLOP        0
  72. #endif
  73.  
  74. /*
  75.  * nextf[i] is the pointer to the next free block of size 2^(i+3).  The
  76.  * smallest allocatable block is 8 bytes.  The overhead information
  77.  * precedes the data area returned to the user.
  78.  */
  79. #define    NBUCKETS 30
  80. static    union overhead *nextf[NBUCKETS];
  81. extern    char *sbrk();
  82.  
  83. static    int pagesz;            /* page size */
  84. static    int pagebucket;            /* page size bucket */
  85.  
  86. #ifdef MSTATS
  87. /*
  88.  * nmalloc[i] is the difference between the number of mallocs and frees
  89.  * for a given block size.
  90.  */
  91. static    u_int nmalloc[NBUCKETS];
  92. #include <stdio.h>
  93. #endif
  94.  
  95. #if defined(DEBUG) || defined(RCHECK)
  96. #define    ASSERT(p)   if (!(p)) botch(#p)
  97. #include <stdio.h>
  98. static
  99. botch(s)
  100.     char *s;
  101. {
  102.     fprintf(stderr, "\r\nassertion botched: %s\r\n", s);
  103.      (void) fflush(stderr);        /* just in case user buffered it */
  104.     *((int *)-1) = 0; /* force fault; abort will probably fail if malloc's dead */
  105.     abort();
  106. }
  107. #else
  108. #define    ASSERT(p)
  109. #endif
  110.  
  111. char *
  112. malloc(nbytes)
  113.     unsigned nbytes;
  114. {
  115.       register union overhead *op;
  116.       register int bucket, n;
  117.     register unsigned amt;
  118.  
  119.     /*
  120.      * First time malloc is called, setup page size and
  121.      * align break pointer so all data will be page aligned.
  122.      */
  123.     if (pagesz == 0) {
  124.         pagesz = n = getpagesize();
  125.         op = (union overhead *)sbrk(0);
  126.           n = n - sizeof (*op) - ((int)op & (n - 1));
  127.         if (n < 0)
  128.             n += pagesz;
  129.           if (n) {
  130.               if (sbrk(n) == (char *)-1)
  131.                 return (NULL);
  132.         }
  133.         bucket = 0;
  134.         amt = 8;
  135.         while (pagesz > amt) {
  136.             amt <<= 1;
  137.             bucket++;
  138.         }
  139.         pagebucket = bucket;
  140.     }
  141.     /*
  142.      * Convert amount of memory requested into closest block size
  143.      * stored in hash buckets which satisfies request.
  144.      * Account for space used per block for accounting.
  145.      */
  146.     if (nbytes <= (n = pagesz - sizeof (*op) - RSLOP)) {
  147. #ifndef RCHECK
  148.         amt = 8;    /* size of first bucket */
  149.         bucket = 0;
  150. #else
  151.         amt = 16;    /* size of first bucket */
  152.         bucket = 1;
  153. #endif
  154.         n = -(sizeof (*op) + RSLOP);
  155.     } else {
  156.         amt = pagesz;
  157.         bucket = pagebucket;
  158.     }
  159.     while (nbytes > amt + n) {
  160.         amt <<= 1;
  161.         if (amt == 0)
  162.             return (NULL);
  163.         bucket++;
  164.     }
  165.     /*
  166.      * If nothing in hash bucket right now,
  167.      * request more memory from the system.
  168.      */
  169.       if ((op = nextf[bucket]) == NULL) {
  170.           morecore(bucket);
  171.           if ((op = nextf[bucket]) == NULL)
  172.               return (NULL);
  173.     }
  174.     /* remove from linked list */
  175.       nextf[bucket] = op->ov_next;
  176.     op->ov_magic = MAGIC;
  177.     op->ov_index = bucket;
  178. #ifdef MSTATS
  179.       nmalloc[bucket]++;
  180. #endif
  181. #ifdef RCHECK
  182.     /*
  183.      * Record allocated size of block and
  184.      * bound space with magic numbers.
  185.      */
  186.     op->ov_size = (nbytes + RSLOP - 1) & ~(RSLOP - 1);
  187.     op->ov_rmagic = RMAGIC;
  188.       *(u_short *)((caddr_t)(op + 1) + op->ov_size) = RMAGIC;
  189. #endif
  190.       return ((char *)(op + 1));
  191. }
  192.  
  193. char *
  194. calloc(size,nelem) /* added by DJ Delorie */
  195. unsigned size;
  196. unsigned nelem;
  197. {
  198.   char *rv = malloc(size*nelem);
  199.   if (rv)
  200.     bzero(rv, size*nelem);
  201.   return rv;
  202. }
  203.  
  204. /*
  205.  * Allocate more memory to the indicated bucket.
  206.  */
  207. morecore(bucket)
  208.     int bucket;
  209. {
  210.       register union overhead *op;
  211.     register int sz;        /* size of desired block */
  212.       int amt;            /* amount to allocate */
  213.       int nblks;            /* how many blocks we get */
  214.  
  215.     /*
  216.      * sbrk_size <= 0 only for big, FLUFFY, requests (about
  217.      * 2^30 bytes on a VAX, I think) or for a negative arg.
  218.      */
  219.     sz = 1 << (bucket + 3);
  220. #ifdef DEBUG
  221.     ASSERT(sz > 0);
  222. #else
  223.     if (sz <= 0)
  224.         return;
  225. #endif
  226.     if (sz < pagesz) {
  227.         amt = pagesz;
  228.           nblks = amt / sz;
  229.     } else {
  230.         amt = sz + pagesz;
  231.         nblks = 1;
  232.     }
  233.     op = (union overhead *)sbrk(amt);
  234.     /* no more room! */
  235.       if ((int)op == -1)
  236.           return;
  237.     /*
  238.      * Add new memory allocated to that on
  239.      * free list for this hash bucket.
  240.      */
  241.       nextf[bucket] = op;
  242.       while (--nblks > 0) {
  243.         op->ov_next = (union overhead *)((caddr_t)op + sz);
  244.         op = (union overhead *)((caddr_t)op + sz);
  245.       }
  246.     op->ov_next = 0;
  247. }
  248.  
  249. free(cp)
  250.     char *cp;
  251. {   
  252.       register int size;
  253.     register union overhead *op;
  254.  
  255.       if (cp == NULL)
  256.           return;
  257.     op = (union overhead *)((caddr_t)cp - sizeof (union overhead));
  258. #ifdef DEBUG
  259.       ASSERT(op->ov_magic == MAGIC);        /* make sure it was in use */
  260. #else
  261.     if (op->ov_magic != MAGIC)
  262.         return;                /* sanity */
  263. #endif
  264. #ifdef RCHECK
  265.       ASSERT(op->ov_rmagic == RMAGIC);
  266.     ASSERT(*(u_short *)((caddr_t)(op + 1) + op->ov_size) == RMAGIC);
  267. #endif
  268.       size = op->ov_index;
  269.       ASSERT(size < NBUCKETS);
  270.     op->ov_next = nextf[size];    /* also clobbers ov_magic */
  271.       nextf[size] = op;
  272. #ifdef MSTATS
  273.       nmalloc[size]--;
  274. #endif
  275. }
  276.  
  277. /*
  278.  * When a program attempts "storage compaction" as mentioned in the
  279.  * old malloc man page, it realloc's an already freed block.  Usually
  280.  * this is the last block it freed; occasionally it might be farther
  281.  * back.  We have to search all the free lists for the block in order
  282.  * to determine its bucket: 1st we make one pass thru the lists
  283.  * checking only the first block in each; if that fails we search
  284.  * ``realloc_srchlen'' blocks in each list for a match (the variable
  285.  * is extern so the caller can modify it).  If that fails we just copy
  286.  * however many bytes was given to realloc() and hope it's not huge.
  287.  */
  288. int realloc_srchlen = 4;    /* 4 should be plenty, -1 =>'s whole list */
  289.  
  290. char *
  291. realloc(cp, nbytes)
  292.     char *cp; 
  293.     unsigned nbytes;
  294. {   
  295.       register u_int onb;
  296.     register int i;
  297.     union overhead *op;
  298.       char *res;
  299.     int was_alloced = 0;
  300.  
  301.       if (cp == NULL)
  302.           return (malloc(nbytes));
  303.     op = (union overhead *)((caddr_t)cp - sizeof (union overhead));
  304.     if (op->ov_magic == MAGIC) {
  305.         was_alloced++;
  306.         i = op->ov_index;
  307.     } else {
  308.         /*
  309.          * Already free, doing "compaction".
  310.          *
  311.          * Search for the old block of memory on the
  312.          * free list.  First, check the most common
  313.          * case (last element free'd), then (this failing)
  314.          * the last ``realloc_srchlen'' items free'd.
  315.          * If all lookups fail, then assume the size of
  316.          * the memory block being realloc'd is the
  317.          * largest possible (so that all "nbytes" of new
  318.          * memory are copied into).  Note that this could cause
  319.          * a memory fault if the old area was tiny, and the moon
  320.          * is gibbous.  However, that is very unlikely.
  321.          */
  322.         if ((i = findbucket(op, 1)) < 0 &&
  323.             (i = findbucket(op, realloc_srchlen)) < 0)
  324.             i = NBUCKETS;
  325.     }
  326.     onb = 1 << (i + 3);
  327.     if (onb < pagesz)
  328.         onb -= sizeof (*op) + RSLOP;
  329.     else
  330.         onb += pagesz - sizeof (*op) - RSLOP;
  331.     /* avoid the copy if same size block */
  332.     if (was_alloced) {
  333.         if (i) {
  334.             i = 1 << (i + 2);
  335.             if (i < pagesz)
  336.                 i -= sizeof (*op) + RSLOP;
  337.             else
  338.                 i += pagesz - sizeof (*op) - RSLOP;
  339.         }
  340.         if (nbytes <= onb && nbytes > i) {
  341. #ifdef RCHECK
  342.             op->ov_size = (nbytes + RSLOP - 1) & ~(RSLOP - 1);
  343.             *(u_short *)((caddr_t)(op + 1) + op->ov_size) = RMAGIC;
  344. #endif
  345.             return(cp);
  346.         } else
  347.             free(cp);
  348.     }
  349.       if ((res = malloc(nbytes)) == NULL)
  350.           return (NULL);
  351.       if (cp != res)        /* common optimization if "compacting" */
  352.         bcopy(cp, res, (nbytes < onb) ? nbytes : onb);
  353.       return (res);
  354. }
  355.  
  356. /*
  357.  * Search ``srchlen'' elements of each free list for a block whose
  358.  * header starts at ``freep''.  If srchlen is -1 search the whole list.
  359.  * Return bucket number, or -1 if not found.
  360.  */
  361. static
  362. findbucket(freep, srchlen)
  363.     union overhead *freep;
  364.     int srchlen;
  365. {
  366.     register union overhead *p;
  367.     register int i, j;
  368.  
  369.     for (i = 0; i < NBUCKETS; i++) {
  370.         j = 0;
  371.         for (p = nextf[i]; p && j != srchlen; p = p->ov_next) {
  372.             if (p == freep)
  373.                 return (i);
  374.             j++;
  375.         }
  376.     }
  377.     return (-1);
  378. }
  379.  
  380. #ifdef MSTATS
  381. /*
  382.  * mstats - print out statistics about malloc
  383.  * 
  384.  * Prints two lines of numbers, one showing the length of the free list
  385.  * for each size category, the second showing the number of mallocs -
  386.  * frees for each size category.
  387.  */
  388. mstats(s)
  389.     char *s;
  390. {
  391.       register int i, j;
  392.       register union overhead *p;
  393.       int totfree = 0,
  394.       totused = 0;
  395.  
  396.       fprintf(stderr, "Memory allocation statistics %s\nfree:\t", s);
  397.       for (i = 0; i < NBUCKETS; i++) {
  398.           for (j = 0, p = nextf[i]; p; p = p->ov_next, j++)
  399.               ;
  400.           fprintf(stderr, " %d", j);
  401.           totfree += j * (1 << (i + 3));
  402.       }
  403.       fprintf(stderr, "\nused:\t");
  404.       for (i = 0; i < NBUCKETS; i++) {
  405.           fprintf(stderr, " %d", nmalloc[i]);
  406.           totused += nmalloc[i] * (1 << (i + 3));
  407.       }
  408.       fprintf(stderr, "\n\tTotal in use: %d, total free: %d\n",
  409.         totused, totfree);
  410. }
  411. #endif
  412.