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
45unsigned	brkincr = BRKINCR;
46struct blk *blokp;			/* current search pointer */
47struct blk *bloktop;		/* top of arena (last blok) */
48
49unsigned char		*brkbegin;
50extern 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
64static void	fill_pat(struct blk *, uint32_t);
65static void	chkbptr(struct blk *);
66#endif
67
68void *
69alloc(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
107void
108addblok(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
173void
174free(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
197static void
198fill_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
208static void
209chkbptr(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
242static void
243chkmem()
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
281size_t
282blklen(q)
283char *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__
312void *
313realloc(pp, nbytes)
314void *pp;
315size_t nbytes;
316#else
317char *
318realloc(pp, nbytes)
319char *pp;
320size_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