![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to alloc.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [CSRG BSD Unix] / 40BSD / cmd / oldcsh|
Return to alloc.c CVS log | Up to [CSRG BSD Unix] / 40BSD / cmd / oldcsh |
1.1 root 1: /* Copyright (c) 1979 Regents of the University of California */
2: #include "sh.local.h"
3: #ifdef debug
4: #define ASSERT(p) if(!(p))botch("p");else
5: botch(s)
6: char *s;
7: {
8: printf("assertion botched: %s\n",s);
9: chdir("/usr/bill/cshcore");
10: abort();
11: }
12: #else
13: #define ASSERT(p)
14: #endif
15:
16: /* avoid break bug */
17: #ifdef pdp11
18: #define GRANULE 64
19: #else
20: #define GRANULE 0
21: #endif
22: /* C storage allocator
23: * circular first-fit strategy
24: * works with noncontiguous, but monotonically linked, arena
25: * each block is preceded by a ptr to the (pointer of)
26: * the next following block
27: * blocks are exact number of words long
28: * aligned to the data type requirements of ALIGN
29: * pointers to blocks must have BUSY bit 0
30: * bit in ptr is 1 for busy, 0 for idle
31: * gaps in arena are merely noted as busy blocks
32: * last block of arena (pointed to by alloct) is empty and
33: * has a pointer to first
34: * idle blocks are coalesced during space search
35: *
36: * a different implementation may need to redefine
37: * ALIGN, NALIGN, BLOCK, BUSY, INT
38: * where INT is integer type to which a pointer can be cast
39: */
40: #define INT int
41: #define ALIGN int
42: #define NALIGN 1
43: #define WORD sizeof(union store)
44: #define BLOCK 1024 /* a multiple of WORD*/
45: #define BUSY 1
46: #define NULL 0
47: #define testbusy(p) ((INT)(p)&BUSY)
48: #define setbusy(p) (union store *)((INT)(p)|BUSY)
49: #define clearbusy(p) (union store *)((INT)(p)&~BUSY)
50:
51: union store { union store *ptr;
52: ALIGN dummy[NALIGN];
53: int calloc; /*calloc clears an array of integers*/
54: };
55:
56: static union store allocs[2]; /*initial arena*/
57: static union store *allocp; /*search ptr*/
58: static union store *alloct; /*arena top*/
59: static union store *allocx; /*for benefit of realloc*/
60: char *sbrk();
61:
62: char *
63: malloc(nbytes)
64: unsigned nbytes;
65: {
66: register union store *p, *q;
67: register nw;
68: static temp; /*coroutines assume no auto*/
69:
70: if(allocs[0].ptr==0) { /*first time*/
71: allocs[0].ptr = setbusy(&allocs[1]);
72: allocs[1].ptr = setbusy(&allocs[0]);
73: alloct = &allocs[1];
74: allocp = &allocs[0];
75: }
76: nw = (nbytes+WORD+WORD-1)/WORD;
77: ASSERT(allocp>=allocs && allocp<=alloct);
78: ASSERT(allock());
79: for(p=allocp; ; ) {
80: for(temp=0; ; ) {
81: if(!testbusy(p->ptr)) {
82: while(!testbusy((q=p->ptr)->ptr)) {
83: ASSERT(q>p&&q<alloct);
84: p->ptr = q->ptr;
85: }
86: if(q>=p+nw && p+nw>=p)
87: goto found;
88: }
89: q = p;
90: p = clearbusy(p->ptr);
91: if(p>q)
92: ASSERT(p<=alloct);
93: else if(q!=alloct || p!=allocs) {
94: ASSERT(q==alloct&&p==allocs);
95: return(NULL);
96: } else if(++temp>1)
97: break;
98: }
99: temp = ((nw+BLOCK/WORD)/(BLOCK/WORD))*(BLOCK/WORD);
100: q = (union store *)sbrk(0);
101: if(q+temp+GRANULE < q) {
102: return(NULL);
103: }
104: q = (union store *)sbrk(temp*WORD);
105: if((INT)q == -1) {
106: return(NULL);
107: }
108: ASSERT(q>alloct);
109: alloct->ptr = q;
110: if(q!=alloct+1)
111: alloct->ptr = setbusy(alloct->ptr);
112: alloct = q->ptr = q+temp-1;
113: alloct->ptr = setbusy(allocs);
114: }
115: found:
116: allocp = p + nw;
117: ASSERT(allocp<=alloct);
118: if(q>allocp) {
119: allocx = allocp->ptr;
120: allocp->ptr = p->ptr;
121: }
122: p->ptr = setbusy(allocp);
123: return((char *)(p+1));
124: }
125:
126: /* freeing strategy tuned for LIFO allocation
127: */
128: free(ap)
129: register char *ap;
130: {
131: register union store *p = (union store *)ap;
132:
133: ASSERT(p>clearbusy(allocs[1].ptr)&&p<=alloct);
134: ASSERT(allock());
135: allocp = --p;
136: /* ASSERT(testbusy(p->ptr)); */
137: p->ptr = clearbusy(p->ptr);
138: ASSERT(p->ptr > allocp && p->ptr <= alloct);
139: }
140:
141: /* realloc(p, nbytes) reallocates a block obtained from malloc()
142: * and freed since last call of malloc()
143: * to have new size nbytes, and old content
144: * returns new location, or 0 on failure
145: */
146:
147: char *
148: realloc(p, nbytes)
149: register union store *p;
150: unsigned nbytes;
151: {
152: register union store *q;
153: union store *s, *t;
154: register unsigned nw;
155: unsigned onw;
156:
157: if(testbusy(p[-1].ptr))
158: free((char *)p);
159: onw = p[-1].ptr - p;
160: q = (union store *)malloc(nbytes);
161: if(q==NULL || q==p)
162: return((char *)q);
163: s = p;
164: t = q;
165: nw = (nbytes+WORD-1)/WORD;
166: if(nw<onw)
167: onw = nw;
168: while(onw--!=0)
169: #ifdef V6
170: copy(t++, s++, sizeof (*t));
171: #else
172: *t++ = *s++;
173: #endif
174: if(q<p && q+nw>=p)
175: (q+(q+nw-p))->ptr = allocx;
176: return((char *)q);
177: }
178:
179: #ifdef debug
180: allock()
181: {
182: #ifdef longdebug
183: register union store *p;
184: int x;
185: x = 0;
186: for(p= &allocs[0]; clearbusy(p->ptr) > p; p=clearbusy(p->ptr)) {
187: if(p==allocp)
188: x++;
189: }
190: ASSERT(p==alloct);
191: return(x==1|p==allocp);
192: #else
193: return(1);
194: #endif
195: }
196: #endif
197:
198: #ifdef debug
199: showall(v)
200: char **v;
201: {
202: register union store *p, *q;
203: int used = 0, free = 0, i;
204:
205: for (p = clearbusy(allocs[1].ptr); p != alloct; p = q) {
206: q = clearbusy(p->ptr);
207: if (v[1])
208: printf("%6o %5d %s\n", p,
209: ((unsigned) q - (unsigned) p),
210: testbusy(p->ptr) ? "BUSY" : "FREE");
211: i = ((unsigned) q - (unsigned) p);
212: if (testbusy(p->ptr)) used += i; else free += i;
213: }
214: printf("%d used, %d free, %l end\n", used, free, clearbusy(alloct));
215: }
216: #endif
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.