![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to cmalloc.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [Research Unix] / researchv10no / cmd / trace|
Return to cmalloc.c CVS log | Up to [Research Unix] / researchv10no / cmd / trace |
1.1 root 1: #ifdef debug
2: #define ASSERT(p) if(!(p))botch("p");else
3: botch(s)
4: char *s;
5: {
6: printf("assertion botched: %s\n",s);
7: abort();
8: }
9: #else
10: #define ASSERT(p)
11: #endif
12:
13: /* C storage allocator
14: * circular first-fit strategy
15: * works with noncontiguous, but monotonically linked, arena
16: * each block is preceded by a ptr to the (pointer of)
17: * the next following block
18: * blocks are exact number of words long
19: * aligned to the data type requirements of ALIGN
20: * pointers to blocks must have BUSY bit 0
21: * bit in ptr is 1 for busy, 0 for idle
22: * gaps in arena are merely noted as busy blocks
23: * last block of arena is empty and
24: * has a pointer to first
25: * idle blocks are coalesced during space search
26: *
27: * a different implementation may need to redefine
28: * ALIGN, NALIGN, BLOCK, BUSY, INT
29: * where INT is integer type to which a pointer can be cast
30: */
31: #define INT int
32: #define ALIGN int
33: #define NALIGN 1
34: #define WORD sizeof(union store)
35: #define BLOCK 1024
36: #define BUSY 1
37: #define NULL 0
38: #define testbusy(p) ((INT)(p)&BUSY)
39: #define setbusy(p) (union store *)((INT)(p)|BUSY)
40: #define clearbusy(p) (union store *)((INT)(p)&~BUSY)
41:
42: union store {
43: union store *ptr;
44: ALIGN dummy[NALIGN];
45: int calloc; /*calloc clears an array of integers*/
46: };
47:
48: static union store alloca; /* initial arena */
49: static union store *allocb = &alloca; /*arena base*/
50: static union store *allocp = &alloca; /*search ptr*/
51: static union store *alloct = &alloca; /*arena top; for speedier ialloc*/
52: static union store allocx, allocy; /*for benefit of realloc*/
53: extern char *sbrk();
54:
55: /* a cache list of frequently-used sizes is maintained. From each
56: * cache entry hangs a chain of available blocks (marked busy
57: * to keep out of the first fit search)
58: */
59: #define CACHEMAX 100 /* largest block to be cached (in words) */
60: #ifndef pdp11
61: #define CACHESIZ 13 /* number of entries (prime) */
62: #else
63: #define CACHESIZ 0
64: #endif
65: static struct cache {
66: int size;
67: union store *chain;
68: } cache[CACHESIZ];
69:
70: char *
71: malloc(nbytes)
72: unsigned nbytes;
73: {
74: register union store *p, *q;
75: register nw;
76: register temp;
77: register struct cache *cp;
78:
79: ASSERT(allock(allocp)&1);
80: nw = (nbytes+WORD+WORD-1)/WORD;
81: if(CACHESIZ && nw<CACHEMAX && nw>2) { /* see note + below */
82: cp = cache + nw%CACHESIZ;
83: p = cp->chain;
84: if(p && nw==cp->size) {
85: cp->chain = p[1].ptr;
86: ASSERT(testbusy(p->ptr));
87: ASSERT(clearbusy(p->ptr)-p==nw);
88: return (char*)(p+1);
89: }
90: }
91: ASSERT(allock(allocp)&3);
92: for(; ; ) { /* done at most twice */
93: p = allocp;
94: if(alloca.ptr!=0) /*C can't initialize union*/
95: for(temp=0; ; ) {
96: if(!testbusy(p->ptr)) {
97: while(!testbusy((q=p->ptr)->ptr)) {
98: ASSERT(q>p);
99: p->ptr = q->ptr;
100: }
101: allocp = p;
102: if(q>=p+nw && p+nw>=p) /*room; no wrap*/
103: goto found;
104: }
105: q = p;
106: p = clearbusy(p->ptr);
107: if(p <= q) {
108: ASSERT(p==allocb);
109: if(++temp>1)
110: break;
111: }
112: }
113: temp = nw;
114: p = (union store *)sbrk(0);
115: q = allocp->ptr;
116: if(!testbusy(q) && q+1 == p)
117: temp -= p - allocp;
118: temp = ((temp+BLOCK/WORD)/(BLOCK/WORD))*(BLOCK/WORD);
119: if(p+temp <= p)
120: return(NULL);
121: for( ; ; ) {
122: register s;
123: q = (union store *)sbrk(temp*WORD);
124: if((INT)q != -1)
125: break;
126: for(cp=cache; cp<cache+CACHESIZ; cp++) {
127: for(p=cp->chain; p; p=p[1].ptr) {
128: ASSERT(testbusy(p->ptr));
129: p->ptr = clearbusy(p->ptr);
130: ASSERT(p->ptr-p==cp->size);
131: }
132: cp->chain = 0;
133: }
134: s = (temp-nw)/2;
135: if(s <= 0)
136: return(NULL);
137: temp -= s;
138: }
139: ialloc((char *)q, (unsigned)temp*WORD);
140: }
141: found:
142: q = p + nw;
143: if(p->ptr > q) {
144: allocx = *q;
145: q->ptr = p->ptr;
146: }
147: p->ptr = setbusy(q);
148: ASSERT(allock(allocp)&7);
149: return((char *)(p+1));
150: }
151: /* + note CACHESIZ is tested for conditional compilation; nw>2 assumes there's
152: * no point in caching smaller sizes (they are rarely used and always
153: * can be allocated) and protects against the old storage compaction trick:
154: * free(p); free(dummy);dummy=malloc(1);realloc(p)
155: * (otherwise free(dummy) would destroy allocy, which pertains to p)
156: */
157:
158: /* freeing strategy tuned for LIFO allocation
159: */
160: free(ap)
161: char *ap;
162: {
163: register union store *p = (union store *)ap, *q;
164: register nw;
165: register struct cache *cp;
166:
167: --p;
168: ASSERT(allock(p));
169: ASSERT(testbusy(p->ptr));
170: nw = clearbusy(p->ptr) - p;
171: ASSERT(nw>0);
172: if(CACHESIZ && nw<CACHEMAX && nw>2) {
173: cp = cache + nw%CACHESIZ;
174: if(nw != cp->size) {
175: q = cp->chain;
176: if(q) {
177: ASSERT(testbusy(q->ptr));
178: q->ptr = clearbusy(q->ptr);
179: ASSERT(q->ptr-q==cp->size);
180: cp->chain = q[1].ptr;
181: }
182: if(!q)
183: cp->size = nw;
184: else
185: goto nocache;
186: }
187: allocy = p[1];
188: p[1].ptr = cp->chain;
189: cp->chain = p;
190: ASSERT(allock(allocp)&017);
191: return;
192: }
193: nocache:
194: allocp = p;
195: p->ptr = clearbusy(p->ptr);
196: ASSERT(allock(allocp)&037);
197: ASSERT(p->ptr<=alloct);
198: }
199:
200: /* ialloc(q, nbytes) inserts a block that did not come
201: * from malloc into the arena
202: *
203: * q points to new block
204: * r points to last of new block
205: * p points to last cell of arena before new block
206: * s points to first cell of arena after new block
207: */
208: ialloc(qq, nbytes)
209: char *qq;
210: unsigned nbytes;
211: {
212: register union store *p, *q, *s;
213: union store *r;
214:
215: q = (union store *)qq;
216: r = q + (nbytes/WORD) - 1;
217: q->ptr = r;
218: if(alloca.ptr==0) /*C can't initialize union*/
219: alloca.ptr = &alloca;
220: if(q > alloct) {
221: p = alloct;
222: alloct = r;
223: } else
224: allocp = p = allocb;
225: for( ; ; p=s) {
226: s = clearbusy(p->ptr);
227: if(s==allocb)
228: break;
229: ASSERT(s>p);
230: if(s>r) {
231: if(p<q)
232: break;
233: else
234: ASSERT(p>r);
235: }
236: }
237: p->ptr = q==p+1? q: setbusy(q);
238: r->ptr = s==r+1? s: setbusy(s);
239: if(allocb > q)
240: allocp = allocb = q;
241: }
242:
243: /* realloc(p, nbytes) reallocates a block obtained from malloc()
244: * and freed since last call of malloc()
245: * to have new size nbytes, and old content
246: * returns new location, or 0 on failure
247: */
248:
249: char *
250: realloc(pp, nbytes)
251: char *pp;
252: unsigned nbytes;
253: {
254: register union store *q;
255: register union store *p = (union store *)pp;
256: register union store *s, *t;
257: register unsigned nw;
258: struct cache *cp;
259: unsigned onw;
260:
261: q = p-1;
262: ASSERT(allock(q));
263: if(testbusy(q->ptr)) {
264: allocp = q;
265: q->ptr = clearbusy(q->ptr);
266: if(CACHESIZ) {
267: nw = q->ptr - q;
268: cp = cache + nw%CACHESIZ;
269: if(cp->chain==q) {
270: ASSERT(cp->size==nw);
271: cp->chain = p->ptr; /*p->ptr==q[1].ptr*/
272: *p = allocy;
273: } else
274: ASSERT(notonchain(q,cp->chain));
275: }
276: }
277: onw = q->ptr - p;
278: q = (union store *)malloc(nbytes);
279: if(q==NULL || q==p)
280: return((char *)q);
281: ASSERT(q<p||q>p[-1].ptr);
282: s = p;
283: t = q;
284: nw = (nbytes+WORD-1)/WORD;
285: if(nw<onw)
286: onw = nw;
287: while(onw--!=0)
288: *t++ = *s++;
289: ASSERT(clearbusy(q[-1].ptr)-q==nw);
290: if(q<p && q+nw>=p)
291: q[q+nw-p] = allocx;
292: ASSERT(allock(q-1));
293: return((char *)q);
294: }
295:
296: #ifdef debug
297:
298: notonchain(p,q)
299: union store *p, *q;
300: {
301: for(;q; q=clearbusy(q->ptr))
302: if(q==p)
303: return 0;
304: return 1;
305: }
306:
307: allock(q)
308: union store *q;
309: {
310: #ifdef longdebug
311: register union store *p, *r;
312: int x;
313: for(x=0; x<CACHESIZ; x++) {
314: p = cache[x].chain;
315: if(p==0)
316: continue;
317: for( ; p; p=p[1].ptr) {
318: ASSERT(testbusy(p->ptr));
319: ASSERT(clearbusy(p->ptr)-p==cache[x].size);
320: }
321: }
322: x = 0;
323: p = allocb;
324: if(alloca.ptr==0)
325: return(1);
326: for( ; (r=clearbusy(p->ptr)) > p; p=r) {
327: if(p==q)
328: x++;
329: }
330: return(r==allocb&(x==1|p==q));
331: #else
332: return(q>=allocb);
333: #endif
334: }
335: #endif
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.