home *** CD-ROM | disk | FTP | other *** search
/ Usenet 1994 October / usenetsourcesnewsgroupsinfomagicoctober1994disk2.iso / misc / volume5 / malloc.uport / malloc.c < prev    next >
C/C++ Source or Header  |  1989-02-03  |  13KB  |  514 lines
  1.  
  2. /*
  3.         Fast Malloc for Microport 286
  4.         Copyright (C) April 1988
  5.         Michael Grenier
  6.  
  7. Permission to redistribute for non-profit use is hereby granted.
  8. Please send bug fixes to mike@cimcor.mn.org
  9.  
  10. */
  11. #include <stdio.h>
  12. #include <memory.h>
  13.  
  14. /*  TUNABLE PARAMETERS */
  15.  
  16.  
  17. #define EPSILON        10  /* Blocks smaller than this number of words are not
  18.                 retained */
  19.  
  20.  
  21. /* DO NOT CHANGE! */
  22. #define ALLOCATED    1
  23. #define AVAILABLE    0
  24. #define MAX_BLOCK_SIZE 32744          /* maximum size block we can allocate -
  25.                         32768 - 4 * HEADER_SIZE  words */
  26. #define LLINK(x)    (page[x])    /* pointer to previous block in page */
  27. #define TAG(x)        (page[x+1])  /* set to 1 if allocated */
  28. #define SIZE(x)        (page[x+2])  /* Number of words in this block not counting header */
  29. #define RLINK(x)    (page[x+3])  /* pointer to next block */
  30. #define ETAG(x)        (page[x+SIZE(x)+4])  /* set to 1 if allocated */
  31. #define ULINK(x)    (page[x+SIZE(x)+5])  /* pointer to beginning of this block */
  32. #define AV(indx)    (av_list[indx])      /* pointer to block on free list with this page */
  33.  
  34. static char *xxcopyright="\n\n\nCopyright 1988 by Michael Grenier, all rights reserved\n\n";
  35.  
  36. char *sbrk();   /* needed Unix System calls */
  37. int    brk();
  38.  
  39. static unsigned av_list[62],   /* offset pointer to a free block with each page */
  40.      m_curindx=0,    /* Current page to allocate from */
  41.      free_indx=1;    /* Page to begin searching for a block in */
  42.  
  43. static int xxfunny[4]={23,56,12,23}; /* used to uniquely identify this binary should
  44.                 someone steal the start distributing binaries
  45.                 and delete the copyright */
  46.  
  47. #define HEADER_SIZE    6 /* words wasted per block */
  48. #define ALLOCATE_OFFSET 4 /* Offset in block where user process pointer points */
  49.  
  50. static long m_endds, m_first_endds; /* address of current and initial brk() value */
  51.  
  52.  
  53. /* Get starting address of this segment given segment number
  54.    starting with one as the first segment allocated
  55. */
  56. unsigned int *getpage(indx)
  57. unsigned indx;
  58. {
  59.     return (unsigned int *) ((m_first_endds + ((unsigned long)indx - 1L)
  60.          * 0x00080000L) & 0xFFFF0000L); /* adjust selector */
  61. }
  62.  
  63.  
  64.  
  65. /* can't use stock memcpy, memset as they don't handle a size
  66.     greater than 32K bytes */
  67.  
  68. void u_memset(ptr, value, size) /* in words */
  69. unsigned int *ptr, value, size;
  70. {
  71.     while (!size)
  72.     {
  73.         (*(ptr++)) = value;
  74.         size--;
  75.     }
  76. }
  77.  
  78. void u_memcpy(ptr1, ptr2, size) /* in words, should be written in asssembler ti use block moves */
  79. unsigned int *ptr1, *ptr2, size;
  80. {
  81.     while (!size)
  82.     {
  83.         (*(ptr1++)) = *(ptr2++);
  84.         size--;
  85.     }
  86. }
  87.  
  88.  
  89. /*
  90.     New_page() - allocate a new segment from Unix
  91.     This routine allocates a full 64K segment to be supplied to malloc
  92.     to be split up as appropiate
  93. */
  94. void new_page()
  95. {
  96.     unsigned temp, *page;
  97.     
  98.     if (m_curindx==0) /* First time so initialize a segment */
  99.     {
  100.         m_first_endds = (long) sbrk(0);  /* returns next segment value */
  101.         m_endds = m_first_endds + 65535L;
  102.     }
  103.     else
  104.         m_endds += 0x00080000L; /* add one to 80286 selector */
  105.  
  106.     brk((char *) m_endds);    /* allocates the new page (segment) */
  107.     
  108.     /* Now set up free list in segment. Allocate and tag busy two zero
  109.        length blocks on each end of page to simplify and speed up
  110.        allocation algorithm - see Sahni's notes. Also allocate a
  111.        zero length free segment and set AV to point to it.
  112.     */
  113.     
  114.     m_curindx++;  /* Update number of pages allocated */
  115.     page = getpage (m_curindx); /* set up to use macros */
  116.     
  117.     TAG(0)    = ALLOCATED;  /* allocate zero length block at start of page */
  118.     SIZE(0)    = 0;
  119.     ETAG(0)    = ALLOCATED;
  120.     ULINK(0)= 0;
  121.     
  122.  
  123.  
  124.     temp = 32768 - HEADER_SIZE;/* point to last possible block in page
  125.                       and allocate it also */
  126.                       
  127.     TAG(temp)   = ALLOCATED;
  128.     SIZE(temp)  = 0;
  129.     ETAG(temp)  = ALLOCATED;
  130.     ULINK(temp) = temp;
  131.  
  132.  
  133.  
  134.     temp = HEADER_SIZE; /* Now allocate a zero length free block that
  135.                    will never get allocated (because of its size) */
  136.  
  137.     TAG(temp)   = AVAILABLE;
  138.     SIZE(temp)  = 0;
  139.     LLINK(temp) = temp + HEADER_SIZE; /* point to next block (yet to be 
  140.                          created) which will be the actual
  141.                          free block */
  142.     ETAG(temp)  = AVAILABLE;
  143.     ULINK(temp) = temp;
  144.     RLINK(temp) = temp + HEADER_SIZE;
  145.     av_list[m_curindx] = temp;      /* point to first free block */
  146.     
  147.  
  148.     temp += HEADER_SIZE;  /* Finally, allocate the actual free block */
  149.     TAG(temp) = AVAILABLE;  /* mark as free */
  150.     SIZE(temp) = MAX_BLOCK_SIZE;
  151.     LLINK(temp) = HEADER_SIZE; /* point to previous free block */
  152.     RLINK(temp) = HEADER_SIZE;
  153.     ETAG(temp)  = AVAILABLE;
  154.     ULINK(temp) = temp;
  155. }
  156.  
  157. unsigned int get_offset(ptr)
  158. unsigned int *ptr; /* not char * because we want pointer math in words, not bytes */
  159. {
  160.     unsigned int temp = (((unsigned) ptr >>1) - ALLOCATE_OFFSET);
  161.     return temp;
  162. }
  163.  
  164.  
  165. void free_from_page(p, seqindx)
  166. unsigned int p, seqindx;
  167. {
  168.     unsigned int n, q, r, *page;
  169.     
  170.     /* point to true beginning of block */
  171.     
  172.     page = getpage(seqindx);
  173.  
  174.     if ((TAG(p) != ALLOCATED) || (ETAG(p) != ALLOCATED))
  175.     {
  176.         fprintf(stderr,"\n\rAttempt to free a pointer which was not allocated\n");
  177.         fprintf(stderr,"or had its control block information overwritten!\n");
  178.         abort();
  179.     }
  180.  
  181.     n = SIZE(p);
  182.  
  183.     if (((p==12) || (page[p-2]==ALLOCATED))
  184.        && (TAG(p+n+HEADER_SIZE)==ALLOCATED))
  185.     /* free this block but do not join with neighbors */
  186.     {
  187.         TAG(p)        = AVAILABLE;
  188.         ETAG(p)            = AVAILABLE;
  189.         ULINK(p)    = p;
  190.         LLINK(p)    = AV(seqindx);
  191.         RLINK(p)    = RLINK(AV(seqindx));
  192. /*        LLINK(RLINK(p)    = p;        Can't seem to nest macros */
  193.         page [ RLINK(p) ] = p;
  194.         RLINK(AV(seqindx))    = p;
  195.     }
  196.     else if ((p!=12) &&    /* Never join with first empty block as AV must point to something */
  197.         (page[p-2]==AVAILABLE) && 
  198.         ((TAG(p+n+HEADER_SIZE))==ALLOCATED))
  199.     /* join with left block */
  200.     {
  201.         q = page[p-1]; /* start of left block */
  202.         SIZE(q) = SIZE(q) + n + HEADER_SIZE;
  203.         ULINK(p) = q;
  204.         ETAG(p)  = AVAILABLE;
  205.         AV(seqindx) = q;     /* always leave AV pointing to possible full block */
  206.     }
  207.     else if (((p==12) || (page[p-2]==ALLOCATED)) &&
  208.         ((TAG(p+n+HEADER_SIZE))==AVAILABLE))
  209.     /* join with right block */
  210.     {
  211.         q = p + n + HEADER_SIZE; /* start of next block */
  212.         page[ page[q] + 3] = p;  /* RLINK(LLINK(q))=p  stupid macros...*/ 
  213.         page[page[q+3]]=p;   /*LLINK(RLINK(q)) = p; */
  214.         LLINK(p) = LLINK(q);
  215.         RLINK(p) = RLINK(q);
  216.         SIZE(p) = n + HEADER_SIZE + SIZE(q);
  217.         ULINK(p) = p;
  218.         TAG(p) = AVAILABLE;
  219.         AV(seqindx)=p; /* Can't have free list pointer pointing to 
  220.                     garbage! */
  221.     }
  222.     else 
  223.     {
  224.         /* join with both sides */
  225.         q = p + n + HEADER_SIZE; /* start of next block */
  226.         r = page[p - 1];      /* start of previous block */
  227.         RLINK(LLINK(q))=RLINK(q);
  228.         LLINK(RLINK(q))=LLINK(q);
  229.         SIZE(r)=SIZE(r) + (n + HEADER_SIZE) + SIZE(q) + HEADER_SIZE;
  230.         ULINK(r)=r;
  231.         AV(seqindx)=r; /* don't point to garbage */
  232.     }
  233. }
  234.  
  235.  
  236.  
  237. unsigned int *allocate_from_page(n, seqindx)
  238. unsigned int n, seqindx;
  239. {
  240.     unsigned int p, diff, *page;
  241.     page = getpage(seqindx);
  242.     p = AV(seqindx); /* point to first free block */
  243.     do
  244.     {    /* search for a free block, first fit */
  245.         if (SIZE(p) >= n)  /* allocate it */
  246.         {
  247.             diff=SIZE(p)-n;
  248.             if (diff < EPSILON) /* allocate whole block */
  249.             {
  250.                 RLINK(LLINK(p)) = RLINK(p);
  251.                 LLINK(RLINK(p)) = LLINK(p);
  252.                 TAG(p)  = ALLOCATED;
  253.                 ETAG(p) = ALLOCATED;
  254.                 AV(seqindx) = LLINK(p);
  255.                 return(page + p + ALLOCATE_OFFSET);
  256.             }
  257.             else
  258.             {    /* free lower portion of block */
  259.                 SIZE(p)  = diff - HEADER_SIZE; /* remaining free portion */
  260.                 ULINK(p) = p;
  261.                 ETAG(p)  = AVAILABLE;
  262.                 AV(seqindx) = p;
  263.                 
  264.                 /* allocate the rest of block */
  265.                 p += SIZE(p) + HEADER_SIZE; /* point to start of block */
  266.                 SIZE(p) = n;
  267.                 TAG(p)  = ALLOCATED;
  268.                 ETAG(p) = ALLOCATED;
  269.                 ULINK(p) = p;
  270.                 return (page + p + ALLOCATE_OFFSET);
  271.             }
  272.         }
  273.         p = RLINK(p); /* point to next free block */
  274.     } while (p != AV(seqindx));
  275.     return ((unsigned int *) 0);
  276. }
  277.  
  278.  
  279. void return_free_pages()
  280. {
  281.     unsigned i, *page; /* leave one page allocated because this
  282.             #*#*!& UNIX won't give you the intial brk value */
  283.     while ((m_curindx>1) && (page=getpage(m_curindx),
  284.             SIZE(AV(m_curindx)) == MAX_BLOCK_SIZE))
  285.     {
  286.         m_curindx--;
  287.         m_endds -= 0x00080000L; /* subtract one from selector */
  288.     };
  289.     brk( (char *) m_endds);
  290. }
  291.  
  292.  
  293. char *malloc(size)
  294. unsigned size;
  295. {
  296.     char *dummy;
  297.     int indx;
  298.  
  299.     if (m_curindx==0)
  300.         if (!new_page()) return((char *) 0); /* no more memory */
  301.     
  302.     /* calculate page address */
  303.  
  304.     indx=free_indx;
  305.     do
  306.     {
  307.         if ((dummy = (char *) allocate_from_page((size+1)>>1, indx))
  308.             !=NULL) 
  309.         {
  310.             free_indx=indx; /* to speed up allocating for next malloc */
  311.             return ((char *) dummy);
  312.         }            
  313.         indx++;
  314.         if (indx>m_curindx) indx=1;
  315.     } while (indx != free_indx);
  316.  
  317. /*  -- if we haven't returned yet, call brk for more memory and try again */
  318.  
  319.     if (!new_page()) return((char *) 0);
  320.     return((char *) allocate_from_page((size+1)>>1, m_curindx));
  321.     
  322. }
  323.  
  324.  
  325. char *calloc(nelem, elsize)
  326. unsigned nelem, elsize;
  327. {
  328.     char *dum;
  329.     register unsigned size;
  330.     size = nelem*elsize; /* in bytes, assume compiler word aligns structures */
  331.     if ((dum=malloc(size)) != NULL)   /* zero out the block */
  332.         u_memset( (int *) dum, 0, size>>1); /* set size words to 0 */
  333.     return dum;
  334. }
  335.  
  336.  
  337. void free(ptr)
  338. char *ptr;
  339. {
  340.     unsigned int indx;
  341.     long temp;
  342.  
  343.     temp = (long) ptr - m_first_endds;
  344.     indx = (temp >>19) + 1;        /* get selector for pointer */
  345.     free_from_page(get_offset((unsigned int *)ptr), indx);
  346.     return_free_pages();
  347. }
  348.  
  349.  
  350.  
  351. char *realloc( ptr, size)
  352. char *ptr;
  353. unsigned size;
  354. {
  355.     unsigned int seqindx, *page, rb, p, diff;
  356.     long temp;
  357.     char * ptrnew;
  358.  
  359.     if (size==0) 
  360.     {
  361.         free(ptr);
  362.         return (char *) NULL; 
  363.     }
  364.     
  365.     temp = (long) ptr - m_first_endds;
  366.     seqindx = (temp >>19) + 1;        /* get selector for pointer */
  367.     
  368.     page = getpage(seqindx);
  369.     p = get_offset((unsigned int *) ptr);
  370.     size = (size + 1) >>1;                /* bytes to words, round up */
  371.     diff =  SIZE(p) - size;     /* in words */
  372.     if (size <= SIZE(p)) /* words, reduce space */
  373.     {
  374.         unsigned int rbnew;
  375.  
  376.         if (diff<HEADER_SIZE)
  377.             return ptr;    /* if can't create a new free block then */
  378.                     /* waste the few bytes */
  379.             
  380.         SIZE(p) -= diff;        /* modify this block */
  381.         ULINK(p) =p;
  382.         ETAG(p)  = ALLOCATED;
  383.  
  384.         rbnew = p + HEADER_SIZE + SIZE(p); /* build new right block */
  385.         TAG(rbnew) = ALLOCATED;
  386.         SIZE(rbnew) = diff - HEADER_SIZE;
  387.         ETAG(rbnew) = ALLOCATED;
  388.         ULINK(rbnew) = rbnew;
  389.         free_from_page(rbnew, seqindx);
  390.         return(ptr);
  391.     }
  392.  
  393.     /* enlarging space */
  394.  
  395.     rb=p+SIZE(p)+HEADER_SIZE; /* see if space is available from next block*/
  396.     diff= -diff;
  397.     if ((TAG(rb)==AVAILABLE) && ((SIZE(rb)+1)>diff))
  398.     {    /* take from right block - save important info */
  399.         unsigned int lsave, rsave, ssave;
  400.         lsave=LLINK(rb);
  401.         rsave=RLINK(rb);
  402.         ssave=SIZE(rb);
  403.         SIZE(p)  = size;
  404.         ULINK(p) = p;
  405.         ETAG(p)  = ALLOCATED;
  406.         rb = p + SIZE(p) + HEADER_SIZE;
  407.         
  408.         /* fix right block */
  409.         
  410.         LLINK(rb) = lsave;
  411.         RLINK(rb) = rsave;
  412.         TAG(rb)   = AVAILABLE;
  413.         SIZE(rb)  = ssave - diff;
  414.         ETAG(rb)  = AVAILABLE; /* shouldn't have changed but ... */
  415.         ULINK(rb) = rb;
  416.         
  417.         /* fix neighbors on free list */
  418.         LLINK(RLINK(rb)) = rb;
  419.         RLINK(LLINK(rb)) = rb;
  420.         return ptr;
  421.     }
  422.     
  423.     /* Finally, if room wasn't availble, allocate new block and move stuff */
  424.     
  425.     ptrnew = malloc(size<<1);
  426.     u_memcpy((int *) ptr, (int *) ptrnew, SIZE(p));
  427.     free (ptr);
  428.     return ptrnew;
  429.         
  430. }
  431.  
  432.  
  433. char *tagit(i)
  434. unsigned int i;
  435. {
  436.     if (i==AVAILABLE)
  437.         return "AVAIL ";
  438.     if (i==ALLOCATED)
  439.         return "IN USE";
  440.     return "*BAD* ";
  441. }
  442.  
  443.  
  444. int dump_malloc()
  445. {
  446.     unsigned int indx, ptr, *page;
  447.     
  448.     if (m_curindx==0) 
  449.     {
  450.         fprintf(stderr,"\r\n No segments allocated\r\n");
  451.         return(1);
  452.     }
  453.     
  454.     for (indx=1; indx<=m_curindx; indx++)
  455.     {
  456.         fprintf(stderr,"\r\n Segment No. %d : \r\n",indx);
  457.         page=getpage(indx);
  458.         
  459.         ptr = 0; /* first block */
  460.         fprintf(stderr," Ptr      Block\r\n");
  461.         fprintf(stderr," Addr     offset       LLINK  TAG    SIZE    RLINK  ETAG    UPLINK\r\n\n");
  462.         while (ptr!=32768 /* last block */ )
  463.         {
  464.             fprintf(stderr,"%.8lx   %.5u      %.5u  %s  %.5u   %.5u  %s  %.5u \r\n",
  465.               page + ptr + ALLOCATE_OFFSET,
  466.               ptr, LLINK(ptr), tagit(TAG(ptr)), SIZE(ptr), RLINK(ptr), 
  467.                        tagit(ETAG(ptr)), ULINK(ptr));
  468.               
  469.             ptr += HEADER_SIZE+SIZE(ptr);
  470.             if (ptr<6) abort();
  471.         }
  472.         
  473.         fprintf(stderr," \r\n AV points to %u\r\n\n",AV(indx));
  474.     }
  475.     return(1);
  476. }    
  477.  
  478.  
  479. /* int check_malloc()
  480. {
  481.     char pointers[32762]; 
  482.     unsigned int first, cur, indx, *page;
  483.     
  484.     for (indx=1; indx<=m_curindx; indx++);
  485.     {
  486.         fprintf("\nChecking segment %d for LLINKS\n", indx);
  487.         for (cur==0; cur<32762; cur++)
  488.             pointers[cur]=0;
  489.         page=getpage(indx);
  490.         first=AV(indx);
  491.         cur=first;
  492.         while (pointers[cur]==0)
  493.         {
  494.             pointers[cur]=1;
  495.             cur=LLINK(cur);
  496.         }
  497.         if (cur != first)abort();
  498.         
  499.         fprintf("\nChecking segment %d for RLINKS\n", indx);
  500.         for (cur==0; cur<32760; cur++)
  501.             pointers[cur]=0;
  502.         page=getpage(indx);
  503.         first=AV(indx);
  504.         cur=first;
  505.         while (pointers[cur]==0)
  506.         {
  507.             pointers[cur]=1;
  508.             cur=RLINK(cur);
  509.         }
  510.         if (cur != first)abort();
  511.     }
  512. }
  513. */
  514.