![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to malloc.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [Research Unix] / researchv9 / libc / gen|
Return to malloc.c CVS log | Up to [Research Unix] / researchv9 / libc / gen |
1.1 root 1: /* compile-time features
2: IALLOC use all blocks given to ialloc, otherwise ignore unordered blocks
3: MSTATS enable statistics
4: debug enable assertion checking
5: longdebug full arena checks at every transaction
6: */
7: #ifdef longdebug
8: #define debug 1
9: #endif
10: #ifdef debug
11: #include <stdio.h>
12: #define ASSERT(p) if(!(p))botch(__LINE__);else
13: static
14: botch(n)
15: {
16: fprintf(stderr,"bad arena, malloc.c line %d\n" ,n);
17: abort();
18: }
19: #else
20: #define ASSERT(p)
21: #endif
22:
23: /* C storage allocator
24: * circular first-fit strategy
25: * works with noncontiguous, but monotonically linked, arena
26: * each block is preceded by a ptr to the (pointer of)
27: * the next following block
28: * blocks are exact number of words long
29: * aligned to the data type requirements of ALIGN
30: * pointers to blocks must have BUSY bit 0
31: * bit in ptr is 1 for busy, 0 for idle
32: * gaps in arena are merely noted as busy blocks
33: * last block of arena is empty and
34: * has a pointer to first
35: * idle blocks are coalesced during space search
36: *
37: * a different implementation may need to redefine
38: * ALIGN, NALIGN, BLOCK, BUSY, INT
39: * where INT is integer type to which a pointer can be cast
40: */
41: #define INT int
42: #define ALIGN int
43: #define NALIGN 1
44: #define WORD sizeof(union store)
45: #define BLOCK 4096
46: #define BUSY 1
47: #define NULL 0
48: #define testbusy(p) ((INT)(p)&BUSY)
49: #define setbusy(p) (union store *)((INT)(p)|BUSY)
50: #define clearbusy(p) (union store *)((INT)(p)&~BUSY)
51:
52: union store {
53: union store *ptr;
54: ALIGN dummy[NALIGN];
55: int calloc; /*calloc clears an array of integers*/
56: };
57:
58: /* alloca should have type union store.
59: * The funny business gets it initialized without complaint*/
60: #define addr(a) (union store*)&a
61: static char *alloca = (char*)&alloca + BUSY; /* initial arena */
62: static union store *allocb = addr(alloca); /*arena base*/
63: static union store *allocc = addr(alloca); /*all prev blocks known busy*/
64: static union store *allocp = addr(alloca); /*search ptr*/
65: static union store *alloct = addr(alloca); /*top cell*/
66: static union store *allocx; /*for benefit of realloc*/
67: extern char *sbrk();
68:
69: /* a cache list of frequently-used sizes is maintained. From each
70: * cache entry hangs a chain of available blocks
71: * malloc(0) shuts off caching (to keep freed data clean)
72: */
73: #define CACHEMAX 50 /* largest block to be cached (in words) */
74: #define CACHESIZ 13 /* number of entries (prime) */
75:
76: static union store *cache[CACHESIZ];
77: static int cachemax = CACHEMAX;
78: static char *stdmalloc();
79:
80: #ifdef MSTATS
81: #define Mstats(e) e
82: static long nmalloc, nrealloc, nfree; /* call statistics */
83: static long walloc, wfree; /* space statistics */
84: static long chit, ccoll, cdrain, cavail; /* cache statistics */
85: #else
86: #define Mstats(e)
87: #endif
88:
89: char *
90: malloc(nbytes)
91: unsigned nbytes;
92: {
93: register union store *p;
94: register nw;
95: register union store **cp;
96:
97: nw = (nbytes+WORD+WORD-1)/WORD;
98: Mstats((nmalloc++, walloc += nw));
99: if(nw<cachemax) {
100: if(nw>=2) {
101: cp = &cache[nw%CACHESIZ];
102: p = *cp;
103: if(p && nw==clearbusy(p->ptr)-p) {
104: ASSERT(testbusy(p->ptr));
105: *cp = (++p)->ptr;
106: Mstats((chit++, cavail--));
107: return (char*)p;
108: }
109: } else {
110: draincache();
111: cachemax = 0;
112: }
113: }
114: return stdmalloc(nw);
115: }
116:
117: static char *
118: stdmalloc(nw)
119: register nw;
120: {
121: register union store *p, *q;
122: register temp;
123: ASSERT(allock(allocp));
124: for(; ; ) { /* done at most thrice */
125: p = allocp;
126: for(temp=0; ; ) {
127: if(!testbusy(p->ptr)) {
128: allocp = p;
129: while(!testbusy((q=p->ptr)->ptr)) {
130: ASSERT(q>p);
131: p->ptr = q->ptr;
132: }
133: if(q>=p+nw && p+nw>=p)
134: goto found;
135: }
136: q = p;
137: p = clearbusy(p->ptr);
138: if(p <= q) {
139: ASSERT(p==allocb&&q==alloct);
140: if(++temp>1)
141: break;
142: ASSERT(allock(allocc));
143: p = allocc;
144: }
145: }
146: p = (union store *)sbrk(0);
147: temp = ((nw+BLOCK/WORD)/(BLOCK/WORD))*(BLOCK/WORD);
148: do {
149: if(p+temp > p) { /*check wrap*/
150: q = (union store *)sbrk(temp*WORD);
151: if((INT)q != -1)
152: goto mextend;
153: }
154: temp -= (temp-nw)/2;
155: } while(temp-nw > 1);
156: if(draincache())
157: continue;
158: return(NULL);
159: mextend:
160: draincache();
161: ialloc((char *)q, (unsigned)temp*WORD);
162: }
163: found:
164: allocp += nw;
165: if(q>allocp) {
166: allocx = allocp->ptr;
167: allocp->ptr = p->ptr;
168: }
169: p->ptr = setbusy(allocp);
170: if(p<=allocc) {
171: ASSERT(p==allocc);
172: while(testbusy(allocc->ptr)
173: && (q=clearbusy(allocc->ptr))>allocc)
174: allocc = q;
175: }
176: return((char *)(p+1));
177: }
178:
179: free(ap)
180: char *ap;
181: {
182: register union store *p = (union store *)ap, *q;
183: register nw;
184: register union store **cp;
185:
186: if(p==NULL)
187: return;
188: --p;
189: ASSERT(allock(p));
190: ASSERT(testbusy(p->ptr));
191: ASSERT(!cached(p));
192: nw = clearbusy(p->ptr) - p;
193: Mstats((nfree++, wfree += nw));
194: ASSERT(nw>0);
195: if(nw<cachemax && nw>=2) {
196: cp = &cache[nw%CACHESIZ];
197: q = *cp;
198: if(!q || nw==clearbusy(q->ptr)-q) {
199: p[1].ptr = q;
200: *cp = p;
201: Mstats(cavail++);
202: return;
203: } else Mstats(q && ccoll++);
204: }
205: stdfree(p+1);
206: }
207:
208: /* freeing strategy tuned for LIFO allocation
209: */
210: static
211: stdfree(p)
212: register union store *p;
213: {
214: allocp = --p;
215: if(p < allocc)
216: allocc = p;
217: ASSERT(allock(allocp));
218: p->ptr = clearbusy(p->ptr);
219: ASSERT(p->ptr > allocp);
220: }
221:
222: static
223: draincache()
224: {
225: register union store **cp = cache+CACHESIZ;
226: register union store *q;
227: int anyfreed = 0;
228: while(--cp>=cache) {
229: while(q= *cp) {
230: ASSERT(testbusy(q->ptr));
231: ASSERT((clearbusy(q->ptr)-q)%CACHESIZ==cp-cache);
232: ASSERT(q>=allocb&&q<=alloct);
233: stdfree(++q);
234: anyfreed++;
235: *cp = q->ptr;
236: }
237: }
238: Mstats((cdrain+=anyfreed, cavail=0));
239: return anyfreed;
240: }
241:
242: /* ialloc(q, nbytes) inserts a block that did not come
243: * from malloc into the arena
244: *
245: * q points to new block
246: * r points to last of new block
247: * p points to last cell of arena before new block
248: * s points to first cell of arena after new block
249: */
250:
251: ialloc(qq, nbytes)
252: char *qq;
253: unsigned nbytes;
254: {
255: register union store *p, *q, *s;
256: union store *r;
257:
258: q = (union store *)qq;
259: r = q + (nbytes/WORD) - 1;
260: q->ptr = r;
261: if(q > alloct) {
262: p = alloct;
263: s = allocb;
264: alloct = r;
265: } else {
266: #ifdef IALLOC /* useful only in small address spaces */
267: for(p=allocb; ; p=s) {
268: s = clearbusy(p->ptr);
269: if(s==allocb)
270: break;
271: ASSERT(s>p);
272: if(s>r) {
273: if(p<q)
274: break;
275: else
276: ASSERT(p>r);
277: }
278: }
279: if(allocb > q)
280: allocb = q;
281: if(allocc > q)
282: allocc = q;
283: allocp = allocc;
284: #else
285: return;
286: #endif
287: }
288: p->ptr = q==p+1? q: setbusy(q);
289: r->ptr = s==r+1? s: setbusy(s);
290: while(testbusy(allocc->ptr))
291: allocc = clearbusy(allocc->ptr);
292: }
293:
294: /* realloc(p, nbytes) reallocates a block obtained from malloc()
295: * and freed since last call of malloc()
296: * to have new size nbytes, and old content
297: * returns new location, or 0 on failure
298: */
299:
300: char *
301: realloc(pp, nbytes)
302: char *pp;
303: unsigned nbytes;
304: {
305: register union store *p = (union store *)pp;
306: register union store *s, *t;
307: register union store *q;
308: register unsigned nw;
309: unsigned onw;
310:
311: Mstats(nrealloc++);
312: if(p==NULL)
313: return malloc(nbytes);
314: ASSERT(allock(p-1));
315: if(testbusy(p[-1].ptr))
316: stdfree(p);
317: onw = p[-1].ptr - p;
318: nw = (nbytes+WORD-1)/WORD;
319: q = (union store *)stdmalloc(nw+1);
320: if(q==NULL || q==p)
321: return((char *)q);
322: ASSERT(q<p||q>p[-1].ptr);
323: if(nw<onw) {
324: Mstats(wfree += onw-nw);
325: onw = nw;
326: } else Mstats(walloc += nw-onw);
327: for(s=p, t=q; onw--!=0; )
328: *t++ = *s++;
329: ASSERT(clearbusy(q[-1].ptr)-q==nw);
330: if(q<p && q+nw>=p)
331: (q+(q+nw-p))->ptr = allocx;
332: ASSERT(allock(q-1));
333: return((char *)q);
334: }
335:
336: #ifdef debug
337: static
338: allock(q)
339: union store *q;
340: {
341: #ifdef longdebug
342: register union store *p, *r;
343: register union store **cp;
344: int x, y;
345: for(cp=cache+CACHESIZ; --cp>=cache; ) {
346: if((p= *cp)==0)
347: continue;
348: x = clearbusy(p->ptr) - p;
349: ASSERT(x%CACHESIZ==cp-cache);
350: for( ; p; p = p[1].ptr) {
351: ASSERT(testbusy(p->ptr));
352: ASSERT(clearbusy(p->ptr)-p==x);
353: }
354: }
355: x = 0, y = 0;
356: p = allocb;
357: for( ; (r=clearbusy(p->ptr)) > p; p=r) {
358: if(p==allocc)
359: y++;
360: ASSERT(y||testbusy(p->ptr));
361: if(p==q)
362: x++;
363: }
364: ASSERT(r==allocb);
365: ASSERT(x==1||p==q);
366: ASSERT(y||p==allocc);
367: return(1);
368: #else
369: ASSERT((unsigned)q/WORD*WORD==(unsigned)q);
370: ASSERT(q>=allocb&&q<=alloct);
371: #endif
372: }
373: #endif
374:
375: mstats()
376: {
377: #ifdef MSTATS
378: #ifndef stderr
379: #include <stdio.h>
380: #endif
381: fprintf(stderr, "Malloc statistics, including overhead bytes\n");
382: fprintf(stderr, "Arena: bottom %ld, top %ld\n",
383: (long)clearbusy(alloca), (long)alloct);
384: fprintf(stderr, "Calls: malloc %ld, realloc %ld, free %ld\n",
385: nmalloc, nrealloc, nfree);
386: fprintf(stderr, "Bytes: allocated or extended %ld, ",
387: walloc*WORD);
388: fprintf(stderr, "freed or cut %ld\n", wfree*WORD);
389: fprintf(stderr,"Cache: hits %ld, collisions %ld, discards %ld, avail %ld\n",
390: chit, ccoll, cdrain, cavail);
391: #endif
392: }
393:
394: #ifdef debug
395: cached(p)
396: union store *p;
397: {
398: union store *q = cache[(clearbusy(p->ptr)-p)%CACHESIZ];
399: for( ; q; q=q[1].ptr)
400: ASSERT(p!=q);
401: return 0;
402: }
403: #endif
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.