home *** CD-ROM | disk | FTP | other *** search
/ C/C++ Interactive Guide / c-cplusplus-interactive-guide.iso / c_ref / csource4 / 231_01 / newmal.c < prev    next >
Text File  |  1987-06-17  |  8KB  |  270 lines
  1. /*
  2. From gi!sytek!menlo70!hao!seismo!harpo!utah-cs!thomas Thu Dec 16 14:08:48 1982
  3. Subject: New malloc subroutine
  4. Newsgroups: net.sources
  5.  
  6. This malloc works much better in a VAX (paging) environment.  I doubt it would
  7. work very well on a PDP-11 (in fact, the copymem routine uses an asm, so it
  8. will work only on a VAX without modification).  Defining MSTATS causes
  9. some statistics to be kept, and the routine mstats(string) can be called
  10. to print them out.  Defining rcheck causes more careful checking to be done,
  11. may help find bugs in code (I haven't used it).  Note that the layout of
  12. the arena is QUITE different from the old malloc, so anything that depends
  13. on this will need to be rewritten.  I make no guarantees, and it's not my
  14. code to begin with (I asked the author, whose name I have forgotten now,
  15. for permission to redistribute).
  16.  
  17. -Spencer
  18. ================================================================
  19. */
  20. /* @(#)nmalloc.c 1 (Caltech) 2/21/82
  21.  *  This is a very fast storage allocator.  It allocates blocks of a small
  22.  *  number of different sizes, and keeps free lists of each size.  Blocks that
  23.  *  don't exactly fit are passed up to the next larger size.  In this
  24.  *  implementation, the available sizes are (2^n)-4 (or -12) bytes long.
  25.  *  This is designed for use in a program that uses vast quantities of memory,
  26.  *  but bombs when it runs out.  To make it a little better, it warns the
  27.  *  user when he starts to get near the end.
  28.  */
  29.  
  30. /* nextf[i] is the pointer to the next free block of size 2^(i+3).  The
  31.  * smallest allocatable block is 8 bytes.  The overhead information will
  32.  * go in the first int of the block, and the returned pointer will point
  33.  * to the second.
  34.  *
  35. #ifdef MSTATS
  36.  * nmalloc[i] is the difference between the number of mallocs and frees
  37.  * for a given block size.
  38. #endif MSTATS
  39.  */
  40.  
  41. static unsigned int *nextf[30];
  42.  
  43. #define MSTATS
  44. #ifdef MSTATS
  45. static unsigned int nmalloc[30];
  46. #include "stdio.h"
  47. #endif MSTATS
  48.  
  49. #include <sys/vlimit.h>     /* warn the user when near the end */
  50. #ifdef debug
  51. #define ASSERT(p)   if (!(p))botch("p"); else
  52. #else
  53. #define ASSERT(p)
  54. #endif
  55.  
  56. extern char etext;           /* end of the program */
  57. #define NULL 0
  58.  
  59. #ifdef rcheck
  60. #define MAGIC 0x55555555
  61. #endif
  62.  
  63. /*      The overhead on a block will be four bytes long.  When free, it will
  64.  *  contain a pointer to the next free block, and the bottom two bits must
  65.  *  be zero.  When in use, the first byte will be set to 0xFF, and the second
  66.  *  byte will be the size index.  The other two bytes are only used for
  67.  *  alignment.  If you are range checking, and the size of the block will fit
  68.  *  into two bytes, then the top two bytes hold the size of the requested block
  69.  *  plus the range checking words, and the header word MINUS ONE.
  70.  */
  71.  
  72. static *morecore(nu)    /* ask system for more memory */
  73. register int nu;        /* size index to get more of  */
  74. {   char *sbrk();
  75.     register unsigned int *cp;
  76.     register int rnu;       /* 2^rnu bytes will be requested */
  77.     register int nblks;     /* that becomes nblks blocks of the desired size */
  78.     register int siz;       /* size in ints, not bytes */
  79.     static int warnlevel=0;
  80.     register int used;
  81.  
  82.     if (nextf[nu]!=NULL)
  83.     return;
  84.  
  85.     siz=vlimit(LIM_DATA,-1);        /* find out how much we can get */
  86.     cp=((unsigned int *)sbrk(0));
  87.     used=(int)cp;
  88.     used-= (int)&etext;
  89.     switch (warnlevel){
  90.     case 0:
  91.     if (used>(siz/4)*3){
  92.         write(2,"warning: past 75% of memory limit\7\n",35);
  93.         warnlevel=1;}
  94.     break;
  95.     case 1:
  96.     if (used>(siz/20)*17){
  97.         write(2,"warning: past 85% of memory limit\7\n",35);
  98.         warnlevel=2;}
  99.     break;
  100.     case 2:
  101.     if (used>(siz/20)*19){
  102.         write(2,"warning: past 95% of memory limit\7\n",35);
  103.         warnlevel=3;}
  104.     break;
  105.     }       /* end of warning switch */
  106.     if ((((int)cp)&0x3ff) != 0)       /* land on 1K boundaries */
  107.     sbrk(1024-(((int)cp)&0x3ff));
  108.  
  109.     rnu=(nu<=8)?11:nu+3;    /* take 2k unless the block is bigger than that */
  110.     nblks=1<<(rnu-(nu+3));  /* how many blocks to get */
  111.     if (rnu<nu) rnu=nu;
  112.     if ((int)(cp=(unsigned int*)sbrk(1<<rnu)) == -1)      /* no more room! */
  113.     return;
  114.     if ((((int)cp) & 7)!=0){
  115.     cp=(unsigned int*)((((int)cp)+8)&~7);
  116.     nblks--;}
  117.     nextf[nu]=cp;
  118.     siz= 1<<(nu+1);
  119.     while (--nblks>0){
  120.     ((unsigned int**)cp)[0]= &cp[siz];
  121.     cp= (unsigned int*)&cp[siz];}
  122. }
  123.  
  124. char *malloc(nbytes)    /* get a block */
  125. register unsigned nbytes;
  126. {
  127.     register unsigned char *p;
  128.     register int nunits=0;
  129.     register unsigned shiftr;
  130.  
  131. #ifdef rcheck
  132.     nbytes+=12;     /* make sure the range checkers will fit */
  133. #else
  134.     nbytes+=4;      /* add on for the overhead */
  135. #endif
  136.     nbytes=(nbytes+3)&~3;       /* round up, but still measure in bytes */
  137.     shiftr=(nbytes-1)>>2;
  138.     while ((shiftr>>=1)!=0)     /* apart from this loop, this is O(1) */
  139.     nunits++;
  140.     if (nextf[nunits]==NULL)    /* needed block, nunits is the size index */
  141.     morecore(nunits);
  142.     if ((p=(unsigned char*)(nextf[nunits]))==NULL)
  143.     return(NULL);
  144.     nextf[nunits]= (unsigned int*)*nextf[nunits];
  145.     p[0]=0xff;
  146.     p[1]=nunits;
  147. #ifdef MSTATS
  148.     nmalloc[nunits]++;
  149. #endif MSTATS
  150. #ifdef rcheck
  151.     if (nbytes<=0x10000)
  152.     ((unsigned short*)p)[1]=(unsigned short)nbytes-1;
  153.     *((int*)(p+4))=MAGIC;
  154.     *((int*)(p+nbytes-4))=MAGIC;
  155.     return((char*)(p+8));
  156. #else
  157.     return((char*)(p+4));
  158. #endif
  159. }
  160.  
  161. free(ap)
  162. register unsigned char *ap;
  163. {   register int si;
  164.  
  165.     if (ap==NULL)
  166.     return;
  167. #ifdef rcheck
  168.     ap-=4;
  169.     ASSERT(*(int*)ap==MAGIC);
  170. #endif
  171.     ap-=4;                              /* point back to overhead word */
  172. #ifdef debug
  173.     ASSERT(ap[0]==0xff);                /* make sure it was in use */
  174. #else
  175.     if (ap[0]!=0xff)
  176.     return;
  177. #endif
  178. #ifdef rcheck
  179.     if (ap[1]<=13){
  180.     si=((unsigned short *)ap)[1]-11;  /* get the size of the data */
  181.     ASSERT(*((int*)(ap+si+8))==MAGIC);  /* check for overflow */
  182.     }
  183. #endif
  184.     ASSERT(ap[1]<=29);
  185.     si=ap[1];
  186.     *((unsigned int**)ap)=nextf[si];
  187.     nextf[si]=(unsigned int*)ap;
  188. #ifdef MSTATS
  189.     nmalloc[si]--;
  190. #endif MSTATS
  191. }
  192.  
  193. char *realloc(p, nbytes)
  194. register char *p; register unsigned nbytes;
  195. {   register char *res;
  196.     register unsigned int onb;
  197.  
  198.     if (p==NULL)
  199.     return(malloc(nbytes));
  200. #ifdef rcheck
  201.     if (p[-7]<13)
  202.     onb= ((unsigned short*)p)[-3]-11;  /* old number of data bytes only */
  203.     else
  204.     onb=(1<<(p[-7]+3))-12;
  205. #else
  206.     onb=(1<<(p[-3]+3))-4;
  207. #endif
  208.     if ((res=malloc(nbytes))==NULL)
  209.     return(NULL);
  210.     copymem((nbytes<onb)?nbytes:onb,p,res);
  211.     free(p);
  212.     return(res);
  213. }
  214.  
  215. copymem(n, from, to)
  216. int n;
  217. register char * from, * to;
  218. {
  219.     register int i;
  220.  
  221.     while (n > 0)
  222.     {
  223.     i = n > 65535L ? 65535L : n;
  224.     asm("    movc3    r9,(r11),(r10)");    /* glug! */
  225.     n -= i;
  226.     from += i;
  227.     to += i;
  228.     }
  229. }
  230.  
  231. #ifdef MSTATS
  232. /* ****************************************************************
  233.  * mstats - print out statistics about malloc
  234.  *
  235.  * Prints two lines of numbers, one showing the length of the free list
  236.  * for each size category, the second showing the number of mallocs -
  237.  * frees for each size category.
  238.  */
  239.  
  240. mstats(s)
  241. char *s;
  242. {
  243.     register int i, j;
  244.     register unsigned int * p;
  245.     int totfree = 0,
  246.         totused = 0;
  247.  
  248.     fprintf(stderr, "Memory allocation statistics %s\nfree:\t", s);
  249.     for (i=0; i<30; i++)
  250.     {
  251.     for (j=0, p=nextf[i]; p; p = (unsigned int *)*p, j++)
  252.         ;
  253.     fprintf(stderr, " %d", j);
  254.     totfree += j * (1 << (i+3));
  255.     }
  256.     fprintf(stderr, "\nused:\t");
  257.     for (i=0; i<30; i++)
  258.     {
  259.     fprintf(stderr, " %d", nmalloc[i]);
  260.     totused += nmalloc[i] * (1 << (i+3));
  261.     }
  262.     fprintf(stderr, "\n\tTotal in use: %d, total free: %d\n");
  263. }
  264. #else
  265. mstats()
  266. {                    /* dummy to keep people happy */
  267. }
  268. #endif
  269.  
  270.