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