ViewVC Help
View File | Revision Log | Show Annotations | Download File | Root Listing
root/radiance/ray/src/common/malloc.c
(Generate patch)

Comparing ray/src/common/malloc.c (file contents):
Revision 1.13 by greg, Wed Jul 17 11:35:47 1991 UTC vs.
Revision 1.14 by greg, Mon Aug 26 10:12:24 1991 UTC

# Line 15 | Line 15 | static char SCCSid[] = "$SunId$ LBL";
15   *      call mscrounge() if sbrk fails.
16   * mscrounge() returns whatever free memory it can find to satisfy the
17   *      request along with the number of bytes (modified).
18 + * mcompact() takes the same arguments as mscrounge() (and is in fact
19 + *      called by mscrounge() under dire circumstances), but it uses
20 + *      memory compaction to return a larger block.  (MCOMP)
21   *
22   *      Greg Ward       Lawrence Berkeley Laboratory
23   */
# Line 23 | Line 26 | static char SCCSid[] = "$SunId$ LBL";
26  
27   #ifdef MSTATS
28   #include  <stdio.h>
29 + static unsigned b_nsbrked = 0;
30   static unsigned b_nalloced = 0;
31   static unsigned b_nfreed = 0;
32   static unsigned b_nscrounged = 0;
33 + static unsigned b_ncompacted = 0;
34   static unsigned m_nalloced = 0;
35   static unsigned m_nfreed = 0;
36   static unsigned m_nwasted = 0;
# Line 64 | Line 69 | static ALIGN   dummy_mem;
69  
70   #define DUMMYLOC        ((char *)&dummy_mem)
71  
72 + #ifdef  MCOMP                   /* memory compaction routines */
73 + static char     seedtab[1024];          /* seed for compaction table */
74  
75 + static struct mblk {
76 +        char            *ptr;   /* pointer to memory block */
77 +        unsigned        siz;    /* size of memory block */
78 + }       cptab = {seedtab, sizeof(seedtab)};
79 +
80 + #define mtab(mb)        ((struct mblk *)(mb)->ptr)
81 + #define mtablen(mb)     ((mb)->siz/sizeof(struct mblk))
82 +
83 +
84 + static int
85 + mbcmp(m1, m2)           /* compare memory block locations */
86 + register struct mblk    *m1, *m2;
87 + {
88 +                                /* put empty blocks at end */
89 +        if (m1->siz == 0)
90 +                return(m2->siz == 0 ? 0 : 1);
91 +        if (m2->siz == 0)
92 +                return(-1);
93 +                                /* otherwise, ascending order */
94 +        return(m1->ptr - m2->ptr);
95 + }
96 +
97 +
98 + int
99 + compactfree()           /* compact free lists (moving to table) */
100 + {
101 +        register struct mblk    *tp;
102 +        register int    bucket;
103 +        unsigned        n, bsiz, ncomp;
104 +                                /* fill table from free lists */
105 +        tp = mtab(&cptab); n = mtablen(&cptab);
106 +        bucket = NBUCKETS-1; bsiz = 1<<(NBUCKETS-1);
107 +        ncomp = 0;
108 +        for ( ; ; ) {
109 +                while (tp->siz) {       /* find empty slot */
110 +                        if (--n == 0)
111 +                                goto loopexit;
112 +                        tp++;
113 +                }
114 +                while (free_list[bucket] == NULL) {     /* find block */
115 +                        if (--bucket < FIRSTBUCKET)
116 +                                goto loopexit;
117 +                        bsiz >>= 1;
118 +                }
119 +                tp->ptr = (char *)free_list[bucket];
120 +                ncomp += (tp->siz = bsiz + sizeof(M_HEAD));
121 +                free_list[bucket] = free_list[bucket]->next;
122 +        }
123 + loopexit:
124 +        if (ncomp == 0)
125 +                return(0);              /* nothing new to compact */
126 + #ifdef MSTATS
127 +        b_ncompacted += ncomp;
128 + #endif
129 +        tp = mtab(&cptab); n = mtablen(&cptab);         /* sort table */
130 +        qsort((char *)tp, n, sizeof(struct mblk), mbcmp);
131 +        ncomp = 0;                                      /* collect blocks */
132 +        while (--n && tp[1].siz) {
133 +                if (tp[0].ptr + tp[0].siz == tp[1].ptr) {
134 +                        tp[1].ptr = tp[0].ptr;
135 +                        tp[1].siz += tp[0].siz;
136 +                        ncomp += tp[0].siz;
137 +                        tp[0].siz = 0;
138 +                }
139 +                tp++;
140 +        }
141 +        return(ncomp);
142 + }
143 +
144 +
145   char *
146 + mcompact(np)            /* compact free lists to satisfy request */
147 + unsigned        *np;
148 + {
149 +        struct mblk     *tab;
150 +        unsigned        tablen;
151 +        register struct mblk    *bp, *big;
152 +
153 +        for ( ; ; ) {
154 +                                        /* compact free lists */
155 +                compactfree();
156 +                                        /* find largest block */
157 +                tab = mtab(&cptab); tablen = mtablen(&cptab);
158 +                big = tab;
159 +                bp = tab + tablen;
160 +                while (--bp > tab)
161 +                        if (bp->siz > big->siz)
162 +                                big = bp;
163 +                if (big->siz >= *np) {          /* big enough? */
164 +                        *np = big->siz;
165 +                        big->siz = 0;           /* remove from table */
166 +                        return(big->ptr);       /* return it */
167 +                }
168 +                if (mtablen(big) < tablen+1) {
169 +                        *np = 0;                /* cannot grow table */
170 +                        return(NULL);           /* report failure */
171 +                }
172 +                                /* enlarge table, free old one */
173 +                mtab(big)[0].ptr = cptab.ptr;
174 +                mtab(big)[0].siz = cptab.siz;
175 +                cptab.ptr = big->ptr;
176 +                cptab.siz = big->siz;
177 +                big->siz = 0;                   /* clear and copy */
178 + #ifdef BSD
179 +                bcopy((char *)tab, (char *)(mtab(&cptab)+1),
180 +                                tablen*sizeof(struct mblk));
181 +                bzero((char *)(mtab(&cptab)+tablen+1),
182 +                        (mtablen(&cptab)-tablen-1)*sizeof(struct mblk));
183 + #else
184 +                (void)memcpy((char *)(mtab(&cptab)+1), (char *)tab,
185 +                                tablen*sizeof(struct mblk));
186 +                memset((char *)(mtab(&cptab)+tablen+1), 0,
187 +                        (mtablen(&cptab)-tablen-1)*sizeof(struct mblk));
188 + #endif
189 +        }                       /* next round */
190 + }
191 + #endif          /* MCOMP */
192 +
193 +
194 + char *
195   mscrounge(np)           /* search free lists to satisfy request */
196   register unsigned       *np;
197   {
# Line 84 | Line 210 | register unsigned      *np;
210   #endif
211                          return(p);
212                  }
213 + #ifdef MCOMP
214 +        return(mcompact(np));           /* try compaction */
215 + #else
216          *np = 0;
217          return(NULL);
218 + #endif
219   }
220  
221  
# Line 108 | Line 238 | register unsigned  n;
238                  bpos = sbrk(nrem);                      /* word aligned! */
239                  if ((int)bpos == -1)
240                          return(NULL);
241 + #ifdef MSTATS
242 +                b_nsbrked += nrem;
243 + #endif
244          }
245  
246          n = (n+(BYTES_WORD-1))&~(BYTES_WORD-1);         /* word align rqst. */
# Line 126 | Line 259 | register unsigned  n;
259                          if (p == NULL)                  /* we're really out */
260                                  return(NULL);
261                  }
262 + #ifdef MSTATS
263 +                else b_nsbrked += thisamnt;
264 + #endif
265                  if (p != bpos+nrem) {                   /* not an increment */
266                          bfree(bpos, nrem);              /* free what we have */
267                          bpos = p;
# Line 283 | Line 419 | FILE   *fp;
419          unsigned int    total = 0;
420  
421          fprintf(fp, "Memory statistics:\n");
422 +        fprintf(fp, "\tbmalloc: %d bytes from sbrk\n", b_nsbrked);
423          fprintf(fp, "\tbmalloc: %d bytes allocated\n", b_nalloced);
424          fprintf(fp, "\tbmalloc: %d bytes freed\n", b_nfreed);
425          fprintf(fp, "\tbmalloc: %d bytes scrounged\n", b_nscrounged);
426 +        fprintf(fp, "\tbmalloc: %d bytes compacted\n", b_ncompacted);
427          fprintf(fp, "\tmalloc: %d bytes allocated\n", m_nalloced);
428          fprintf(fp, "\tmalloc: %d bytes wasted (%.1f%%)\n", m_nwasted,
429                          100.0*m_nwasted/m_nalloced);

Diff Legend

– Removed lines
+ Added lines
< Changed lines
> Changed lines