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