home *** CD-ROM | disk | FTP | other *** search
/ Celestin Apprentice 7 / Apprentice-Release7.iso / Source Code / C / Applications / Python 1.4 / Python 1.4 source / Mac / mwerks / malloc / malloc.c < prev    next >
Encoding:
C/C++ Source or Header  |  1996-10-24  |  11.2 KB  |  425 lines  |  [TEXT/CWIE]
  1. /*
  2.  * Attempt at a memory allocator for the Mac, Jack Jansen, CWI, 1995.
  3.  *
  4.  * Code adapted from BSD malloc, which is:
  5.  *
  6.  * Copyright (c) 1983 Regents of the University of California.
  7.  * All rights reserved.
  8.  *
  9.  * Redistribution and use in source and binary forms, with or without
  10.  * modification, are permitted provided that the following conditions
  11.  * are met:
  12.  * 1. Redistributions of source code must retain the above copyright
  13.  *    notice, this list of conditions and the following disclaimer.
  14.  * 2. Redistributions in binary form must reproduce the above copyright
  15.  *    notice, this list of conditions and the following disclaimer in the
  16.  *    documentation and/or other materials provided with the distribution.
  17.  * 3. All advertising materials mentioning features or use of this software
  18.  *    must display the following acknowledgement:
  19.  *    This product includes software developed by the University of
  20.  *    California, Berkeley and its contributors.
  21.  * 4. Neither the name of the University nor the names of its contributors
  22.  *    may be used to endorse or promote products derived from this software
  23.  *    without specific prior written permission.
  24.  *
  25.  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  26.  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  27.  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  28.  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  29.  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  30.  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  31.  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  32.  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  33.  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  34.  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  35.  * SUCH DAMAGE.
  36.  */
  37.  
  38. #if defined(LIBC_SCCS) && !defined(lint)
  39. /*static char *sccsid = "from: @(#)malloc.c    5.11 (Berkeley) 2/23/91";*/
  40. static char *rcsid = "$Id: malloc.c,v 1.5 1996/10/23 15:46:57 jack Exp $";
  41. #endif /* LIBC_SCCS and not lint */
  42.  
  43. /*
  44.  * malloc.c (Caltech) 2/21/82
  45.  * Chris Kingsley, kingsley@cit-20. Modified by Jack Jansen, CWI.
  46.  *
  47.  * This is a very fast storage allocator.  It allocates blocks of a small 
  48.  * number of different sizes, and keeps free lists of each size.  Blocks that
  49.  * don't exactly fit are passed up to the next larger size.
  50.  *
  51.  * Blocks over a certain size are directly allocated by calling NewPtr.
  52.  * 
  53.  */
  54.  
  55. #ifdef USE_MALLOC_DEBUG
  56. /* You may also selectively enable some of these (but some are interdependent) */
  57. #define DEBUG
  58. #define DEBUG2
  59. #define MSTATS
  60. #define RCHECK
  61. #define VCHECK
  62. #endif /* USE_MALLOC_DEBUG */
  63.  
  64. typedef unsigned char u_char;
  65. typedef unsigned long u_long;
  66. typedef unsigned int u_int;
  67. typedef unsigned short u_short;
  68. typedef u_long caddr_t;
  69.  
  70. #include <Memory.h>
  71. #include <stdlib.h>
  72. #include <string.h>
  73.  
  74. #define    NULL 0
  75.  
  76. static void morecore();
  77.  
  78. /*
  79.  * The overhead on a block is at least 4 bytes.  When free, this space
  80.  * contains a pointer to the next free block, and the bottom two bits must
  81.  * be zero.  When in use, the first byte is set to MAGIC, and the second
  82.  * byte is the size index.  The remaining bytes are for alignment.
  83.  * If range checking is enabled then a second word holds the size of the
  84.  * requested block, less 1, rounded up to a multiple of sizeof(RMAGIC).
  85.  * The order of elements is critical: ov_magic must overlay the low order
  86.  * bits of ov_next, and ov_magic can not be a valid ov_next bit pattern.
  87.  */
  88. union    overhead {
  89.     union    overhead *ov_next;    /* when free */
  90.     struct {
  91.         u_char    ovu_magic0;    /* magic number */
  92.         u_char    ovu_index;    /* bucket # */
  93.         u_char    ovu_unused;    /* unused */
  94.         u_char    ovu_magic1;    /* other magic number */
  95. #ifdef RCHECK
  96.         u_short    ovu_rmagic;    /* range magic number */
  97.         u_long    ovu_size;    /* actual block size */
  98. #endif
  99.     } ovu;
  100. #define    ov_magic0    ovu.ovu_magic0
  101. #define    ov_magic1    ovu.ovu_magic1
  102. #define    ov_index    ovu.ovu_index
  103. #define    ov_rmagic    ovu.ovu_rmagic
  104. #define    ov_size        ovu.ovu_size
  105. };
  106.  
  107. #define    MAGIC        0xef        /* magic # on accounting info */
  108. #define RMAGIC        0x5555        /* magic # on range info */
  109.  
  110. #ifdef RCHECK
  111. #define    RSLOP        sizeof (u_short)
  112. #else
  113. #define    RSLOP        0
  114. #endif
  115.  
  116. #define OVERHEAD (sizeof(union overhead) + RSLOP)
  117.  
  118. /*
  119.  * nextf[i] is the pointer to the next free block of size 2^(i+3).  The
  120.  * smallest allocatable block is 8 bytes.  The overhead information
  121.  * precedes the data area returned to the user.
  122.  */
  123. #define    NBUCKETS 11
  124. #define MAXMALLOC (1<<(NBUCKETS+2))
  125. static    union overhead *nextf[NBUCKETS];
  126.  
  127. #ifdef MSTATS
  128. /*
  129.  * nmalloc[i] is the difference between the number of mallocs and frees
  130.  * for a given block size.
  131.  */
  132. static    u_int nmalloc[NBUCKETS+1];
  133. #include <stdio.h>
  134. #endif
  135.  
  136. #if defined(DEBUG) || defined(RCHECK) || defined(DEBUG2)
  137. #define    ASSERT(p)   if (!(p)) botch(# p)
  138. #include <stdio.h>
  139. static
  140. botch(s)
  141.     char *s;
  142. {
  143.     fprintf(stderr, "\r\nmalloc assertion botched: %s\r\n", s);
  144.      (void) fflush(stderr);        /* just in case user buffered it */
  145.     abort();
  146. }
  147. #else
  148. #define    ASSERT(p)
  149. #endif
  150.  
  151. void *
  152. malloc(nbytes)
  153.     size_t nbytes;
  154. {
  155.       register union overhead *op;
  156.       register long bucket;
  157.     register unsigned amt;
  158.  
  159.     /*
  160.     ** First the simple case: we simple allocate big blocks directly
  161.     */
  162.     if ( nbytes + OVERHEAD >= MAXMALLOC ) {
  163.         op = (union overhead *)NewPtr(nbytes+OVERHEAD);
  164.         if ( op == NULL )
  165.             return NULL;
  166.         op->ov_magic0 = op->ov_magic1 = MAGIC;
  167.         op->ov_index = 0xff;
  168. #ifdef MSTATS
  169.           nmalloc[NBUCKETS]++;
  170. #endif
  171. #ifdef RCHECK
  172.         /*
  173.          * Record allocated size of block and
  174.          * bound space with magic numbers.
  175.          */
  176.         op->ov_size = (nbytes + RSLOP - 1) & ~(RSLOP - 1);
  177.         op->ov_rmagic = RMAGIC;
  178.           *(u_short *)((caddr_t)(op + 1) + op->ov_size) = RMAGIC;
  179. #endif
  180.         return (void *)(op+1);
  181.     }
  182.     /*
  183.      * Convert amount of memory requested into closest block size
  184.      * stored in hash buckets which satisfies request.
  185.      * Account for space used per block for accounting.
  186.      */
  187. #ifndef RCHECK
  188.     amt = 8;    /* size of first bucket */
  189.     bucket = 0;
  190. #else
  191.     amt = 16;    /* size of first bucket */
  192.     bucket = 1;
  193. #endif
  194.     while (nbytes + OVERHEAD > amt) {
  195.         amt <<= 1;
  196.         if (amt == 0)
  197.             return (NULL);
  198.         bucket++;
  199.     }
  200. #ifdef DEBUG2
  201.     ASSERT( bucket < NBUCKETS );
  202. #endif
  203.     /*
  204.      * If nothing in hash bucket right now,
  205.      * request more memory from the system.
  206.      */
  207.       if ((op = nextf[bucket]) == NULL) {
  208.           morecore(bucket);
  209.           if ((op = nextf[bucket]) == NULL)
  210.               return (NULL);
  211.     }
  212.     /* remove from linked list */
  213.       nextf[bucket] = op->ov_next;
  214.     op->ov_magic0 = op->ov_magic1 = MAGIC;
  215.     op->ov_index = bucket;
  216. #ifdef MSTATS
  217.       nmalloc[bucket]++;
  218. #endif
  219. #ifdef RCHECK
  220.     /*
  221.      * Record allocated size of block and
  222.      * bound space with magic numbers.
  223.      */
  224.     op->ov_size = (nbytes + RSLOP - 1) & ~(RSLOP - 1);
  225.     op->ov_rmagic = RMAGIC;
  226.       *(u_short *)((caddr_t)(op + 1) + op->ov_size) = RMAGIC;
  227. #endif
  228. #ifdef VCHECK
  229.     memset((char *)(op+1), 0x41, nbytes);
  230. #endif
  231.       return ((char *)(op + 1));
  232. }
  233.  
  234. /*
  235.  * Allocate more memory to the indicated bucket.
  236.  */
  237. static void
  238. morecore(bucket)
  239.     int bucket;
  240. {
  241.       register union overhead *op;
  242.     register long sz;        /* size of desired block */
  243.       long amt;            /* amount to allocate */
  244.       int nblks;            /* how many blocks we get */
  245.  
  246.     /*
  247.      * sbrk_size <= 0 only for big, FLUFFY, requests (about
  248.      * 2^30 bytes on a VAX, I think) or for a negative arg.
  249.      */
  250.     sz = 1 << (bucket + 3);
  251. #ifdef DEBUG2
  252.     ASSERT(sz > 0);
  253. #endif
  254.     amt = MAXMALLOC;
  255.     nblks = amt / sz;
  256. #ifdef DEBUG2
  257.     ASSERT(nblks*sz == amt);
  258. #endif
  259.     op = (union overhead *)NewPtr(amt);
  260.     /* no more room! */
  261.       if (op == NULL)
  262.           return;
  263.     /*
  264.      * Add new memory allocated to that on
  265.      * free list for this hash bucket.
  266.      */
  267.       nextf[bucket] = op;
  268.       while (--nblks > 0) {
  269.         op->ov_next = (union overhead *)((caddr_t)op + sz);
  270.         op = (union overhead *)((caddr_t)op + sz);
  271.       }
  272.       op->ov_next = (union overhead *)NULL;
  273. }
  274.  
  275. void
  276. free(cp)
  277.     void *cp;
  278. {   
  279.       register long size;
  280.     register union overhead *op;
  281.  
  282.       if (cp == NULL)
  283.           return;
  284.     op = (union overhead *)((caddr_t)cp - sizeof (union overhead));
  285. #ifdef DEBUG
  286.       ASSERT(op->ov_magic0 == MAGIC);        /* make sure it was in use */
  287.       ASSERT(op->ov_magic1 == MAGIC);
  288. #else
  289.     if (op->ov_magic0 != MAGIC || op->ov_magic1 != MAGIC)
  290.         return;                /* sanity */
  291. #endif
  292. #ifdef RCHECK
  293.       ASSERT(op->ov_rmagic == RMAGIC);
  294.     ASSERT(*(u_short *)((caddr_t)(op + 1) + op->ov_size) == RMAGIC);
  295. #endif
  296. #ifdef VCHECK
  297.     memset(cp, 43, op->ov_size);
  298. #endif
  299.       size = op->ov_index;
  300.       if ( size == 0xff ) {
  301. #ifdef MSTATS
  302.         nmalloc[NBUCKETS]--;
  303. #endif
  304.           DisposPtr((Ptr)op);
  305.           return;
  306.       }
  307.       ASSERT(size < NBUCKETS);
  308.     op->ov_next = nextf[size];    /* also clobbers ov_magic */
  309.       nextf[size] = op;
  310. #ifdef MSTATS
  311.       nmalloc[size]--;
  312. #endif
  313. }
  314.  
  315. void *
  316. realloc(cp, nbytes)
  317.     void *cp; 
  318.     size_t nbytes;
  319. {   
  320.     int i;
  321.     union overhead *op;
  322.     int expensive;
  323.     u_long maxsize;
  324.  
  325.       if (cp == NULL)
  326.           return (malloc(nbytes));
  327.     op = (union overhead *)((caddr_t)cp - sizeof (union overhead));
  328. #ifdef DEBUG
  329.       ASSERT(op->ov_magic0 == MAGIC);        /* make sure it was in use */
  330.       ASSERT(op->ov_magic1 == MAGIC);
  331. #else
  332.     if (op->ov_magic0 != MAGIC || op->ov_magic1 != MAGIC)
  333.         return NULL;                /* sanity */
  334. #endif
  335. #ifdef RCHECK
  336.       ASSERT(op->ov_rmagic == RMAGIC);
  337.     ASSERT(*(u_short *)((caddr_t)(op + 1) + op->ov_size) == RMAGIC);
  338. #endif
  339.     i = op->ov_index;
  340.     /*
  341.     ** First the malloc/copy cases
  342.     */
  343.     expensive = 0;
  344.     if ( i == 0xff ) {
  345.         /* Big block. See if it has to stay big */
  346.         if (nbytes+OVERHEAD > MAXMALLOC) {
  347.             /* Yup, try to resize it first */
  348.             SetPtrSize((Ptr)op, nbytes+OVERHEAD);
  349.             if ( MemError() == 0 ) {
  350. #ifdef RCHECK
  351.                 op->ov_size = (nbytes + RSLOP - 1) & ~(RSLOP - 1);
  352.                 *(u_short *)((caddr_t)(op + 1) + op->ov_size) = RMAGIC;
  353. #endif
  354.                 return cp;
  355.             }
  356.             /* Nope, failed. Take the long way */
  357.         }
  358.         maxsize = GetPtrSize((Ptr)op);
  359.         expensive = 1;
  360.     } else {
  361.         maxsize = 1 << (i+3);
  362.         if ( nbytes + OVERHEAD > maxsize )
  363.             expensive = 1;
  364.         else if ( i > 0 && nbytes + OVERHEAD < (maxsize/2) )
  365.             expensive = 1;
  366.     }
  367.     if ( expensive ) {
  368.         void *newp;
  369.         
  370.         newp = malloc(nbytes);
  371.         if ( newp == NULL ) {
  372.             return NULL;
  373.         }
  374.         maxsize -= OVERHEAD;
  375.         if ( maxsize < nbytes )
  376.             nbytes = maxsize;
  377.         memcpy(newp, cp, nbytes);
  378.         free(cp);
  379.         return newp;
  380.     }
  381.     /*
  382.     ** Ok, we don't have to copy, it fits as-is
  383.     */
  384. #ifdef RCHECK
  385.     op->ov_size = (nbytes + RSLOP - 1) & ~(RSLOP - 1);
  386.     *(u_short *)((caddr_t)(op + 1) + op->ov_size) = RMAGIC;
  387. #endif
  388.     return(cp);
  389. }
  390.  
  391.  
  392. #ifdef MSTATS
  393. /*
  394.  * mstats - print out statistics about malloc
  395.  * 
  396.  * Prints two lines of numbers, one showing the length of the free list
  397.  * for each size category, the second showing the number of mallocs -
  398.  * frees for each size category.
  399.  */
  400. mstats(s)
  401.     char *s;
  402. {
  403.       register int i, j;
  404.       register union overhead *p;
  405.       int totfree = 0,
  406.       totused = 0;
  407.  
  408.       fprintf(stderr, "Memory allocation statistics %s\nfree:\t", s);
  409.       for (i = 0; i < NBUCKETS; i++) {
  410.           for (j = 0, p = nextf[i]; p; p = p->ov_next, j++)
  411.               ;
  412.           fprintf(stderr, " %d", j);
  413.           totfree += j * (1 << (i + 3));
  414.       }
  415.       fprintf(stderr, "\nused:\t");
  416.       for (i = 0; i < NBUCKETS; i++) {
  417.           fprintf(stderr, " %d", nmalloc[i]);
  418.           totused += nmalloc[i] * (1 << (i + 3));
  419.       }
  420.       fprintf(stderr, "\n\tTotal small in use: %d, total free: %d\n",
  421.         totused, totfree);
  422.     fprintf(stderr, "\n\tNumber of big (>%d) blocks in use: %d\n", MAXMALLOC, nmalloc[NBUCKETS]);
  423. }
  424. #endif
  425.