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 (the "License").
6 * You may not use this file except in compliance with the License.
7 *
8 * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
9 * or http://www.opensolaris.org/os/licensing.
10 * See the License for the specific language governing permissions
11 * and limitations under the License.
12 *
13 * When distributing Covered Code, include this CDDL HEADER in each
14 * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
15 * If applicable, add the following below this CDDL HEADER, with the
16 * fields enclosed by brackets "[]" replaced with your own identifying
17 * information: Portions Copyright [yyyy] [name of copyright owner]
18 *
19 * CDDL HEADER END
20 */
21
22 /*
23 * Copyright 2009 Sun Microsystems, Inc. All rights reserved.
24 * Use is subject to license terms.
25 */
26
27 /* Copyright (c) 1984, 1986, 1987, 1988, 1989 AT&T */
28 /* All Rights Reserved */
29
30 /*
31 * UNIX shell
32 */
33
34 #include "defs.h"
35
36
37 /*
38 * storage allocator
39 * (circular first fit strategy)
40 */
41
42 #define BUSY 01
43 #define busy(x) (Rcheat((x)->word) & BUSY)
44
45 unsigned brkincr = BRKINCR;
46 struct blk *blokp; /* current search pointer */
47 struct blk *bloktop; /* top of arena (last blok) */
48
49 unsigned char *brkbegin;
50 extern unsigned char *setbrk();
51
52 #ifdef DEBUG
53 /*
54 * If DEBUG is defined, the following testing will be performed:
55 * - chkbptr() checks the linkage of blocks by following links.
56 * Note that this makes shell really slow.
57 * - fill_pat() fills the memory block with pattern like umem does.
58 * The pattern used to fill the memory area is defined below.
59 */
60 #define PAT_MAGIC 0xfeedface
61 #define PAT_INIT 0xbaddcafe
62 #define PAT_FREE 0xdeadbeef
63
64 static void fill_pat(struct blk *, uint32_t);
65 static void chkbptr(struct blk *);
66 #endif
67
68 void *
alloc(size_t nbytes)69 alloc(size_t nbytes)
70 {
71 size_t rbytes = round(nbytes + ALIGNSIZ, ALIGNSIZ);
72
73 if (stakbot == 0) {
74 addblok((unsigned int)0);
75 }
76
77 for (;;) {
78 int c = 0;
79 struct blk *p = blokp;
80 struct blk *q;
81
82 do
83 {
84 if (!busy(p)) {
85 while (!busy(q = p->word))
86 p->word = q->word;
87 if ((char *)q - (char *)p >= rbytes) {
88 blokp = (struct blk *)
89 ((char *)p + rbytes);
90 if (q > blokp)
91 blokp->word = p->word;
92 p->word = (struct blk *)
93 (Rcheat(blokp) | BUSY);
94 #ifdef DEBUG
95 fill_pat(p, PAT_INIT);
96 #endif
97 return ((char *)(p + 1));
98 }
99 }
100 q = p;
101 p = (struct blk *)(Rcheat(p->word) & ~BUSY);
102 } while (p > q || (c++) == 0);
103 addblok(rbytes);
104 }
105 }
106
107 void
addblok(unsigned int reqd)108 addblok(unsigned int reqd)
109 {
110 if (stakbot == 0) {
111 brkbegin = setbrk(3 * BRKINCR);
112 /*
113 * setbrk() returns 8 byte aligned address
114 * but we could need larger align in future
115 */
116 brkbegin = (unsigned char *)round(brkbegin, ALIGNSIZ);
117 bloktop = (struct blk *)brkbegin;
118 }
119
120 if (stakbas != staktop) {
121 unsigned char *rndstak;
122 struct blk *blokstak;
123
124 if (staktop >= brkend)
125 growstak(staktop);
126 pushstak(0);
127 rndstak = (unsigned char *)round(staktop, ALIGNSIZ);
128 blokstak = (struct blk *)(stakbas) - 1;
129 blokstak->word = stakbsy;
130 stakbsy = blokstak;
131 bloktop->word = (struct blk *)(Rcheat(rndstak) | BUSY);
132 bloktop = (struct blk *)(rndstak);
133 }
134 reqd += brkincr;
135 reqd &= ~(brkincr - 1);
136 blokp = bloktop;
137 /*
138 * brkend points to the first invalid address.
139 * make sure bloktop is valid.
140 */
141 if ((unsigned char *)&bloktop->word >= brkend) {
142 if (setbrk((unsigned)((unsigned char *)
143 (&bloktop->word) - brkend + sizeof (struct blk))) ==
144 (unsigned char *)-1)
145 error(nospace);
146 }
147 bloktop = bloktop->word = (struct blk *)(Rcheat(bloktop) + reqd);
148 if ((unsigned char *)&bloktop->word >= brkend) {
149 if (setbrk((unsigned)((unsigned char *)
150 (&bloktop->word) - brkend + sizeof (struct blk))) ==
151 (unsigned char *)-1)
152 error(nospace);
153 }
154 bloktop->word = (struct blk *)(brkbegin + 1);
155 {
156 unsigned char *stakadr = (unsigned char *)
157 (bloktop + 2);
158 unsigned char *sp = stakadr;
159 if (reqd = (staktop-stakbot)) {
160 if (stakadr + reqd >= brkend)
161 growstak(stakadr + reqd);
162 while (reqd-- > 0)
163 *sp++ = *stakbot++;
164 sp--;
165 }
166 staktop = sp;
167 if (staktop >= brkend)
168 growstak(staktop);
169 stakbas = stakbot = stakadr;
170 }
171 }
172
173 void
free(ap)174 free(ap)
175 void *ap;
176 {
177 struct blk *p;
178
179 if ((p = (struct blk *)ap) && p < bloktop && p > (struct blk *)brkbegin)
180 {
181 #ifdef DEBUG
182 chkbptr(p);
183 #endif
184 --p;
185 p->word = (struct blk *)(Rcheat(p->word) & ~BUSY);
186 #ifdef DEBUG
187 fill_pat(p, PAT_FREE);
188 #endif
189 }
190
191
192 }
193
194
195 #ifdef DEBUG
196
197 static void
fill_pat(struct blk * ptr,uint32_t pat)198 fill_pat(struct blk *ptr, uint32_t pat)
199 {
200 uint32_t *ui, *eui;
201
202 *(uint32_t *)ptr->pad = PAT_MAGIC;
203 eui = (uint32_t *)(Rcheat(ptr->word) & ~BUSY);
204 for (ui = (uint32_t *)(ptr + 1); ui < eui; ui++)
205 *ui = pat;
206 }
207
208 static void
chkbptr(struct blk * ptr)209 chkbptr(struct blk *ptr)
210 {
211 int exf = 0;
212 struct blk *p = (struct blk *)brkbegin;
213 struct blk *q;
214 int us = 0, un = 0;
215
216 for (;;) {
217 q = (struct blk *)(Rcheat(p->word) & ~BUSY);
218
219 if (p+1 == ptr)
220 exf++;
221
222 if (q < (struct blk *)brkbegin || q > bloktop)
223 abort();
224
225 if (p == bloktop)
226 break;
227
228 if (busy(p))
229 us += q - p;
230 else
231 un += q - p;
232
233 if (p >= q)
234 abort();
235
236 p = q;
237 }
238 if (exf == 0)
239 abort();
240 }
241
242 static void
chkmem()243 chkmem()
244 {
245 struct blk *p = (struct blk *)brkbegin;
246 struct blk *q;
247 int us = 0, un = 0;
248
249 for (;;) {
250 q = (struct blk *)(Rcheat(p->word) & ~BUSY);
251
252 if (q < (struct blk *)brkbegin || q > bloktop)
253 abort();
254
255 if (p == bloktop)
256 break;
257
258 if (busy(p))
259 us += q - p;
260 else
261 un += q - p;
262
263 if (p >= q)
264 abort();
265
266 p = q;
267 }
268
269 prs("un/used/avail ");
270 prn(un);
271 blank();
272 prn(us);
273 blank();
274 prn((uintptr_t)bloktop - (uintptr_t)brkbegin - (un + us));
275 newline();
276
277 }
278
279 #endif
280
281 size_t
blklen(q)282 blklen(q)
283 char *q;
284 {
285 struct blk *pp = (struct blk *)q;
286 struct blk *p;
287
288 --pp;
289 p = (struct blk *)(Rcheat(pp->word) & ~BUSY);
290
291 return ((size_t)((long)p - (long)q));
292 }
293
294 /*
295 * This is a really hasty hack at putting realloc() in the shell, along
296 * with alloc() and free(). I really hate having to do things like this,
297 * hacking in something before I understand _why_ libcollate does any
298 * memory (re)allocation, let alone feel comfortable with this particular
299 * implementation of realloc, assuming it actually gets used by anything.
300 *
301 * I plan to revist this, for now this is just to get sh to compile so
302 * that xcu4 builds may be done and we get xcu4 on our desktops.
303 *
304 * Eric Brunner, 10/21/94
305 *
306 * Implemented a variation on the suggested fix in Trusted Solaris 2.5,
307 * then forward ported the fix into the mainline shell.
308 *
309 * 3/3/99
310 */
311 #ifdef __STDC__
312 void *
realloc(pp,nbytes)313 realloc(pp, nbytes)
314 void *pp;
315 size_t nbytes;
316 #else
317 char *
318 realloc(pp, nbytes)
319 char *pp;
320 size_t nbytes;
321 #endif
322 {
323 char *q;
324 size_t blen;
325
326 if (pp == NULL)
327 return (alloc(nbytes));
328 if ((nbytes == 0) && (pp != NULL))
329 free(pp);
330
331 blen = blklen(pp);
332
333 if (blen < nbytes) { /* need to grow */
334 q = alloc(nbytes);
335 memcpy(q, pp, blen);
336 free(pp);
337 return ((char *)q);
338 } else if (blen == nbytes) { /* do nothing */
339 return (pp);
340 } else { /* free excess */
341 q = alloc(nbytes);
342 memcpy(q, pp, nbytes);
343 free(pp);
344 return ((char *)q);
345 }
346
347 #ifdef undef
348 /*
349 * all of what follows is the _idea_ of what is going to be done
350 * getting the size of the block is a problem -- what follows
351 * is _not_ "real", since "sizeof" isn't going to tell me any
352 * thing usefull, probably have to travers the list to the next
353 * blk, then subtract ptr addrs ... and be careful not to leave
354 * holes.
355 */
356 p = (struct blk *)pp;
357 if (sizeof (p) < nbytes) { /* need to grow */
358 q = alloc(nbytes);
359 memcpy(q, pp, sizeof (p));
360 free(pp);
361 return ((char *)q);
362 } else if (sizeof (p) == nbytes) { /* do nothing */
363 return (pp);
364 } else { /* free excess */
365 q = alloc(nbytes);
366 memcpy(q, pp, nbytes);
367 free(pp);
368 return ((char *)q);
369 }
370 #endif
371 }
372