xref: /illumos-gate/usr/src/cmd/sh/blok.c (revision d6b882a974afe4a3ab38793d5de10bae2e078d39)
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