1*0Sstevel@tonic-gate /*
2*0Sstevel@tonic-gate * CDDL HEADER START
3*0Sstevel@tonic-gate *
4*0Sstevel@tonic-gate * The contents of this file are subject to the terms of the
5*0Sstevel@tonic-gate * Common Development and Distribution License, Version 1.0 only
6*0Sstevel@tonic-gate * (the "License"). You may not use this file except in compliance
7*0Sstevel@tonic-gate * with the License.
8*0Sstevel@tonic-gate *
9*0Sstevel@tonic-gate * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
10*0Sstevel@tonic-gate * or http://www.opensolaris.org/os/licensing.
11*0Sstevel@tonic-gate * See the License for the specific language governing permissions
12*0Sstevel@tonic-gate * and limitations under the License.
13*0Sstevel@tonic-gate *
14*0Sstevel@tonic-gate * When distributing Covered Code, include this CDDL HEADER in each
15*0Sstevel@tonic-gate * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
16*0Sstevel@tonic-gate * If applicable, add the following below this CDDL HEADER, with the
17*0Sstevel@tonic-gate * fields enclosed by brackets "[]" replaced with your own identifying
18*0Sstevel@tonic-gate * information: Portions Copyright [yyyy] [name of copyright owner]
19*0Sstevel@tonic-gate *
20*0Sstevel@tonic-gate * CDDL HEADER END
21*0Sstevel@tonic-gate */
22*0Sstevel@tonic-gate /* Copyright (c) 1984, 1986, 1987, 1988, 1989 AT&T */
23*0Sstevel@tonic-gate /* All Rights Reserved */
24*0Sstevel@tonic-gate
25*0Sstevel@tonic-gate
26*0Sstevel@tonic-gate #ident "%Z%%M% %I% %E% SMI" /* SVr4.0 1.3 */
27*0Sstevel@tonic-gate #ifdef debug
28*0Sstevel@tonic-gate #define ASSERT(p) if(!(p))botch("p");else
botch(s)29*0Sstevel@tonic-gate botch(s)
30*0Sstevel@tonic-gate char *s;
31*0Sstevel@tonic-gate {
32*0Sstevel@tonic-gate printf("assertion botched: %s\n",s);
33*0Sstevel@tonic-gate abort();
34*0Sstevel@tonic-gate }
35*0Sstevel@tonic-gate #else
36*0Sstevel@tonic-gate #define ASSERT(p)
37*0Sstevel@tonic-gate #endif
38*0Sstevel@tonic-gate
39*0Sstevel@tonic-gate /* C storage allocator
40*0Sstevel@tonic-gate * circular first-fit strategy
41*0Sstevel@tonic-gate * works with noncontiguous, but monotonically linked, arena
42*0Sstevel@tonic-gate * each block is preceded by a ptr to the (pointer of)
43*0Sstevel@tonic-gate * the next following block
44*0Sstevel@tonic-gate * blocks are exact number of words long
45*0Sstevel@tonic-gate * aligned to the data type requirements of ALIGN
46*0Sstevel@tonic-gate * pointers to blocks must have BUSY bit 0
47*0Sstevel@tonic-gate * bit in ptr is 1 for busy, 0 for idle
48*0Sstevel@tonic-gate * gaps in arena are merely noted as busy blocks
49*0Sstevel@tonic-gate * last block of arena is empty and
50*0Sstevel@tonic-gate * has a pointer to first
51*0Sstevel@tonic-gate * idle blocks are coalesced during space search
52*0Sstevel@tonic-gate *
53*0Sstevel@tonic-gate * a different implementation may need to redefine
54*0Sstevel@tonic-gate * ALIGN, NALIGN, BLOCK, BUSY, INT
55*0Sstevel@tonic-gate * where INT is integer type to which a pointer can be cast
56*0Sstevel@tonic-gate */
57*0Sstevel@tonic-gate #define INT int
58*0Sstevel@tonic-gate #define ALIGN int
59*0Sstevel@tonic-gate #define NALIGN 1
60*0Sstevel@tonic-gate #define WORD sizeof(union store)
61*0Sstevel@tonic-gate #define BLOCK 1024
62*0Sstevel@tonic-gate #define BUSY 1
63*0Sstevel@tonic-gate #define NULL 0
64*0Sstevel@tonic-gate #define testbusy(p) ((INT)(p)&BUSY)
65*0Sstevel@tonic-gate #define setbusy(p) (union store *)((INT)(p)|BUSY)
66*0Sstevel@tonic-gate #define clearbusy(p) (union store *)((INT)(p)&~BUSY)
67*0Sstevel@tonic-gate
68*0Sstevel@tonic-gate union store {
69*0Sstevel@tonic-gate union store *ptr;
70*0Sstevel@tonic-gate ALIGN dummy[NALIGN];
71*0Sstevel@tonic-gate int calloc; /*calloc clears an array of integers*/
72*0Sstevel@tonic-gate };
73*0Sstevel@tonic-gate
74*0Sstevel@tonic-gate static union store alloca; /* initial arena */
75*0Sstevel@tonic-gate static union store *allocb = &alloca; /*arena base*/
76*0Sstevel@tonic-gate static union store *allocp = &alloca; /*search ptr*/
77*0Sstevel@tonic-gate static union store *allocx; /*for benefit of realloc*/
78*0Sstevel@tonic-gate extern char *sbrk();
79*0Sstevel@tonic-gate
80*0Sstevel@tonic-gate char *
malloc(nbytes)81*0Sstevel@tonic-gate malloc(nbytes)
82*0Sstevel@tonic-gate unsigned nbytes;
83*0Sstevel@tonic-gate {
84*0Sstevel@tonic-gate register union store *p, *q;
85*0Sstevel@tonic-gate register nw;
86*0Sstevel@tonic-gate register temp;
87*0Sstevel@tonic-gate register union store *r = 0;
88*0Sstevel@tonic-gate
89*0Sstevel@tonic-gate nw = (nbytes+WORD+WORD-1)/WORD + 1; /*need one more than asked for*/
90*0Sstevel@tonic-gate ASSERT(allock(allocp));
91*0Sstevel@tonic-gate for(; ; ) { /* done at most twice */
92*0Sstevel@tonic-gate p = allocp;
93*0Sstevel@tonic-gate if(alloca.ptr!=0) /*C can't initialize union*/
94*0Sstevel@tonic-gate for(temp=0; ; ) {
95*0Sstevel@tonic-gate if(!testbusy(p->ptr)) {
96*0Sstevel@tonic-gate while(!testbusy((q=p->ptr)->ptr)) {
97*0Sstevel@tonic-gate ASSERT(q>p);
98*0Sstevel@tonic-gate p->ptr = q->ptr;
99*0Sstevel@tonic-gate allocp = p;
100*0Sstevel@tonic-gate }
101*0Sstevel@tonic-gate if(q>=p+nw && p+nw>=p)
102*0Sstevel@tonic-gate goto found;
103*0Sstevel@tonic-gate r = p;
104*0Sstevel@tonic-gate }
105*0Sstevel@tonic-gate q = p;
106*0Sstevel@tonic-gate p = clearbusy(p->ptr);
107*0Sstevel@tonic-gate if(p <= q) {
108*0Sstevel@tonic-gate ASSERT(p==allocb);
109*0Sstevel@tonic-gate if(p != allocb)
110*0Sstevel@tonic-gate return(NULL);
111*0Sstevel@tonic-gate if(++temp>1)
112*0Sstevel@tonic-gate break;
113*0Sstevel@tonic-gate }
114*0Sstevel@tonic-gate }
115*0Sstevel@tonic-gate temp = nw;
116*0Sstevel@tonic-gate p = (union store *)sbrk(0);
117*0Sstevel@tonic-gate if (r && !testbusy(r->ptr) && r->ptr + 1 == p)
118*0Sstevel@tonic-gate temp -= p - r - 1;
119*0Sstevel@tonic-gate temp = ((temp+BLOCK/WORD)/(BLOCK/WORD))*(BLOCK/WORD);
120*0Sstevel@tonic-gate if(p+temp <= p)
121*0Sstevel@tonic-gate return(NULL);
122*0Sstevel@tonic-gate for(; ; ) {
123*0Sstevel@tonic-gate q = (union store *)sbrk(temp*WORD);
124*0Sstevel@tonic-gate if((INT)q != -1)
125*0Sstevel@tonic-gate break;
126*0Sstevel@tonic-gate temp -= (temp-nw+1)/2;
127*0Sstevel@tonic-gate if(temp <= nw)
128*0Sstevel@tonic-gate return(NULL);
129*0Sstevel@tonic-gate }
130*0Sstevel@tonic-gate ialloc((char *)q, (unsigned)temp*WORD);
131*0Sstevel@tonic-gate }
132*0Sstevel@tonic-gate found:
133*0Sstevel@tonic-gate allocp = p + nw;
134*0Sstevel@tonic-gate if(q>allocp) {
135*0Sstevel@tonic-gate allocx = allocp->ptr;
136*0Sstevel@tonic-gate allocp->ptr = p->ptr;
137*0Sstevel@tonic-gate }
138*0Sstevel@tonic-gate p->ptr = setbusy(allocp);
139*0Sstevel@tonic-gate return((char *)(p+1));
140*0Sstevel@tonic-gate }
141*0Sstevel@tonic-gate
142*0Sstevel@tonic-gate /* freeing strategy tuned for LIFO allocation
143*0Sstevel@tonic-gate */
free(ap)144*0Sstevel@tonic-gate free(ap)
145*0Sstevel@tonic-gate char *ap;
146*0Sstevel@tonic-gate {
147*0Sstevel@tonic-gate register union store *p = (union store *)ap;
148*0Sstevel@tonic-gate
149*0Sstevel@tonic-gate allocp = --p;
150*0Sstevel@tonic-gate ASSERT(allock(allocp));
151*0Sstevel@tonic-gate ASSERT(testbusy(p->ptr));
152*0Sstevel@tonic-gate p->ptr = clearbusy(p->ptr);
153*0Sstevel@tonic-gate ASSERT(p->ptr > allocp);
154*0Sstevel@tonic-gate }
155*0Sstevel@tonic-gate
156*0Sstevel@tonic-gate /* ialloc(q, nbytes) inserts a block that did not come
157*0Sstevel@tonic-gate * from malloc into the arena
158*0Sstevel@tonic-gate *
159*0Sstevel@tonic-gate * q points to new block
160*0Sstevel@tonic-gate * r points to last of new block
161*0Sstevel@tonic-gate * p points to last cell of arena before new block
162*0Sstevel@tonic-gate * s points to first cell of arena after new block
163*0Sstevel@tonic-gate */
ialloc(qq,nbytes)164*0Sstevel@tonic-gate ialloc(qq, nbytes)
165*0Sstevel@tonic-gate char *qq;
166*0Sstevel@tonic-gate unsigned nbytes;
167*0Sstevel@tonic-gate {
168*0Sstevel@tonic-gate register union store *p, *q, *s;
169*0Sstevel@tonic-gate union store *r;
170*0Sstevel@tonic-gate
171*0Sstevel@tonic-gate q = (union store *)qq;
172*0Sstevel@tonic-gate r = q + (nbytes/WORD) - 1;
173*0Sstevel@tonic-gate q->ptr = r;
174*0Sstevel@tonic-gate if(alloca.ptr==0) /*C can't initialize union*/
175*0Sstevel@tonic-gate alloca.ptr = &alloca;
176*0Sstevel@tonic-gate for(p=allocb; ; p=s) {
177*0Sstevel@tonic-gate s = clearbusy(p->ptr);
178*0Sstevel@tonic-gate if(s==allocb)
179*0Sstevel@tonic-gate break;
180*0Sstevel@tonic-gate ASSERT(s>p);
181*0Sstevel@tonic-gate if(s>r) {
182*0Sstevel@tonic-gate if(p<q)
183*0Sstevel@tonic-gate break;
184*0Sstevel@tonic-gate else
185*0Sstevel@tonic-gate ASSERT(p>r);
186*0Sstevel@tonic-gate }
187*0Sstevel@tonic-gate }
188*0Sstevel@tonic-gate p->ptr = q==p+1? q: setbusy(q);
189*0Sstevel@tonic-gate r->ptr = s==r+1? s: setbusy(s);
190*0Sstevel@tonic-gate if(allocb > q)
191*0Sstevel@tonic-gate allocb = q;
192*0Sstevel@tonic-gate allocp = allocb;
193*0Sstevel@tonic-gate }
194*0Sstevel@tonic-gate
195*0Sstevel@tonic-gate /* realloc(p, nbytes) reallocates a block obtained from malloc()
196*0Sstevel@tonic-gate * and freed since last call of malloc()
197*0Sstevel@tonic-gate * to have new size nbytes, and old content
198*0Sstevel@tonic-gate * returns new location, or 0 on failure
199*0Sstevel@tonic-gate */
200*0Sstevel@tonic-gate
201*0Sstevel@tonic-gate char *
realloc(pp,nbytes)202*0Sstevel@tonic-gate realloc(pp, nbytes)
203*0Sstevel@tonic-gate char *pp;
204*0Sstevel@tonic-gate unsigned nbytes;
205*0Sstevel@tonic-gate {
206*0Sstevel@tonic-gate register union store *q;
207*0Sstevel@tonic-gate register union store *p = (union store *)pp;
208*0Sstevel@tonic-gate union store *s, *t;
209*0Sstevel@tonic-gate register unsigned nw;
210*0Sstevel@tonic-gate unsigned onw;
211*0Sstevel@tonic-gate
212*0Sstevel@tonic-gate ASSERT(allock(p-1));
213*0Sstevel@tonic-gate if(testbusy(p[-1].ptr))
214*0Sstevel@tonic-gate free((char *)p);
215*0Sstevel@tonic-gate onw = p[-1].ptr - p;
216*0Sstevel@tonic-gate q = (union store *)malloc(nbytes);
217*0Sstevel@tonic-gate if(q==NULL || q==p)
218*0Sstevel@tonic-gate return((char *)q);
219*0Sstevel@tonic-gate ASSERT(q<p||q>p[-1].ptr);
220*0Sstevel@tonic-gate s = p;
221*0Sstevel@tonic-gate t = q;
222*0Sstevel@tonic-gate nw = (nbytes+WORD-1)/WORD;
223*0Sstevel@tonic-gate if(nw<onw)
224*0Sstevel@tonic-gate onw = nw;
225*0Sstevel@tonic-gate while(onw--!=0)
226*0Sstevel@tonic-gate *t++ = *s++;
227*0Sstevel@tonic-gate ASSERT(clearbusy(q[-1].ptr)-q==nw);
228*0Sstevel@tonic-gate if(q<p && q+nw>=p)
229*0Sstevel@tonic-gate (q+(q+nw-p))->ptr = allocx;
230*0Sstevel@tonic-gate ASSERT(allock(q-1));
231*0Sstevel@tonic-gate return((char *)q);
232*0Sstevel@tonic-gate }
233*0Sstevel@tonic-gate
234*0Sstevel@tonic-gate #ifdef debug
235*0Sstevel@tonic-gate allock(q)
236*0Sstevel@tonic-gate union store *q;
237*0Sstevel@tonic-gate {
238*0Sstevel@tonic-gate #ifdef longdebug
239*0Sstevel@tonic-gate register union store *p, *r;
240*0Sstevel@tonic-gate int x;
241*0Sstevel@tonic-gate x = 0;
242*0Sstevel@tonic-gate p = allocb;
243*0Sstevel@tonic-gate if(alloca.ptr==0)
244*0Sstevel@tonic-gate return(1);
245*0Sstevel@tonic-gate for( ; (r=clearbusy(p->ptr)) > p; p=r) {
246*0Sstevel@tonic-gate if(p==q)
247*0Sstevel@tonic-gate x++;
248*0Sstevel@tonic-gate }
249*0Sstevel@tonic-gate return(r==allocb&(x==1|p==q));
250*0Sstevel@tonic-gate #else
251*0Sstevel@tonic-gate return(q>=allocb);
252*0Sstevel@tonic-gate #endif
253*0Sstevel@tonic-gate }
254*0Sstevel@tonic-gate #endif
255*0Sstevel@tonic-gate
256