xref: /illumos-gate/usr/src/cmd/sh/blok.c (revision d6b882a9)
17c478bd9Sstevel@tonic-gate /*
27c478bd9Sstevel@tonic-gate  * CDDL HEADER START
37c478bd9Sstevel@tonic-gate  *
47c478bd9Sstevel@tonic-gate  * The contents of this file are subject to the terms of the
50b46ffbaSmj  * Common Development and Distribution License (the "License").
60b46ffbaSmj  * You may not use this file except in compliance with the License.
77c478bd9Sstevel@tonic-gate  *
87c478bd9Sstevel@tonic-gate  * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
97c478bd9Sstevel@tonic-gate  * or http://www.opensolaris.org/os/licensing.
107c478bd9Sstevel@tonic-gate  * See the License for the specific language governing permissions
117c478bd9Sstevel@tonic-gate  * and limitations under the License.
127c478bd9Sstevel@tonic-gate  *
137c478bd9Sstevel@tonic-gate  * When distributing Covered Code, include this CDDL HEADER in each
147c478bd9Sstevel@tonic-gate  * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
157c478bd9Sstevel@tonic-gate  * If applicable, add the following below this CDDL HEADER, with the
167c478bd9Sstevel@tonic-gate  * fields enclosed by brackets "[]" replaced with your own identifying
177c478bd9Sstevel@tonic-gate  * information: Portions Copyright [yyyy] [name of copyright owner]
187c478bd9Sstevel@tonic-gate  *
197c478bd9Sstevel@tonic-gate  * CDDL HEADER END
207c478bd9Sstevel@tonic-gate  */
227c478bd9Sstevel@tonic-gate /*
23*d6b882a9SNobutomo Nakano  * Copyright 2009 Sun Microsystems, Inc.  All rights reserved.
24965005c8Schin  * Use is subject to license terms.
257c478bd9Sstevel@tonic-gate  */
277c478bd9Sstevel@tonic-gate /*	Copyright (c) 1984, 1986, 1987, 1988, 1989 AT&T	*/
287c478bd9Sstevel@tonic-gate /*	  All Rights Reserved  	*/
307c478bd9Sstevel@tonic-gate /*
317c478bd9Sstevel@tonic-gate  *	UNIX shell
327c478bd9Sstevel@tonic-gate  */
347c478bd9Sstevel@tonic-gate #include	"defs.h"
377c478bd9Sstevel@tonic-gate /*
387c478bd9Sstevel@tonic-gate  *	storage allocator
397c478bd9Sstevel@tonic-gate  *	(circular first fit strategy)
407c478bd9Sstevel@tonic-gate  */
427c478bd9Sstevel@tonic-gate #define	BUSY 01
437c478bd9Sstevel@tonic-gate #define	busy(x)	(Rcheat((x)->word) & BUSY)
457c478bd9Sstevel@tonic-gate unsigned	brkincr = BRKINCR;
467c478bd9Sstevel@tonic-gate struct blk *blokp;			/* current search pointer */
477c478bd9Sstevel@tonic-gate struct blk *bloktop;		/* top of arena (last blok) */
497c478bd9Sstevel@tonic-gate unsigned char		*brkbegin;
50*d6b882a9SNobutomo Nakano extern unsigned char		*setbrk();
52*d6b882a9SNobutomo Nakano #ifdef DEBUG
53*d6b882a9SNobutomo Nakano /*
54*d6b882a9SNobutomo Nakano  * If DEBUG is defined, the following testing will be performed:
55*d6b882a9SNobutomo Nakano  * - chkbptr() checks the linkage of blocks by following links.
56*d6b882a9SNobutomo Nakano  *   Note that this makes shell really slow.
57*d6b882a9SNobutomo Nakano  * - fill_pat() fills the memory block with pattern like umem does.
58*d6b882a9SNobutomo Nakano  *   The pattern used to fill the memory area is defined below.
59*d6b882a9SNobutomo Nakano  */
60*d6b882a9SNobutomo Nakano #define	PAT_MAGIC	0xfeedface
61*d6b882a9SNobutomo Nakano #define	PAT_INIT	0xbaddcafe
62*d6b882a9SNobutomo Nakano #define	PAT_FREE	0xdeadbeef
64*d6b882a9SNobutomo Nakano static void	fill_pat(struct blk *, uint32_t);
65*d6b882a9SNobutomo Nakano static void	chkbptr(struct blk *);
667c478bd9Sstevel@tonic-gate #endif
67*d6b882a9SNobutomo Nakano 
68*d6b882a9SNobutomo Nakano void *
alloc(size_t nbytes)69*d6b882a9SNobutomo Nakano alloc(size_t nbytes)
707c478bd9Sstevel@tonic-gate {
71*d6b882a9SNobutomo Nakano 	size_t rbytes = round(nbytes + ALIGNSIZ, ALIGNSIZ);
737c478bd9Sstevel@tonic-gate 	if (stakbot == 0) {
74*d6b882a9SNobutomo Nakano 		addblok((unsigned int)0);
757c478bd9Sstevel@tonic-gate 	}
77*d6b882a9SNobutomo Nakano 	for (;;) {
787c478bd9Sstevel@tonic-gate 		int	c = 0;
79965005c8Schin 		struct blk *p = blokp;
80965005c8Schin 		struct blk *q;
827c478bd9Sstevel@tonic-gate 		do
837c478bd9Sstevel@tonic-gate 		{
84*d6b882a9SNobutomo Nakano 			if (!busy(p)) {
857c478bd9Sstevel@tonic-gate 				while (!busy(q = p->word))
867c478bd9Sstevel@tonic-gate 					p->word = q->word;
87*d6b882a9SNobutomo Nakano 				if ((char *)q - (char *)p >= rbytes) {
887c478bd9Sstevel@tonic-gate 					blokp = (struct blk *)
897c478bd9Sstevel@tonic-gate 							((char *)p + rbytes);
907c478bd9Sstevel@tonic-gate 					if (q > blokp)
917c478bd9Sstevel@tonic-gate 						blokp->word = p->word;
927c478bd9Sstevel@tonic-gate 					p->word = (struct blk *)
937c478bd9Sstevel@tonic-gate 							(Rcheat(blokp) | BUSY);
94*d6b882a9SNobutomo Nakano #ifdef DEBUG
95*d6b882a9SNobutomo Nakano 					fill_pat(p, PAT_INIT);
96*d6b882a9SNobutomo Nakano #endif
977c478bd9Sstevel@tonic-gate 					return ((char *)(p + 1));
987c478bd9Sstevel@tonic-gate 				}
997c478bd9Sstevel@tonic-gate 			}
1007c478bd9Sstevel@tonic-gate 			q = p;
1017c478bd9Sstevel@tonic-gate 			p = (struct blk *)(Rcheat(p->word) & ~BUSY);
1027c478bd9Sstevel@tonic-gate 		} while (p > q || (c++) == 0);
1037c478bd9Sstevel@tonic-gate 		addblok(rbytes);
1047c478bd9Sstevel@tonic-gate 	}
1057c478bd9Sstevel@tonic-gate }
107965005c8Schin void
addblok(unsigned int reqd)108965005c8Schin addblok(unsigned int reqd)
1097c478bd9Sstevel@tonic-gate {
110db397771Schin 	if (stakbot == 0) {
1117c478bd9Sstevel@tonic-gate 		brkbegin = setbrk(3 * BRKINCR);
1120b46ffbaSmj 		/*
1130b46ffbaSmj 		 * setbrk() returns 8 byte aligned address
1140b46ffbaSmj 		 * but we could need larger align in future
1150b46ffbaSmj 		 */
1160b46ffbaSmj 		brkbegin = (unsigned char *)round(brkbegin, ALIGNSIZ);
1177c478bd9Sstevel@tonic-gate 		bloktop = (struct blk *)brkbegin;
1187c478bd9Sstevel@tonic-gate 	}
120db397771Schin 	if (stakbas != staktop) {
121965005c8Schin 		unsigned char *rndstak;
122965005c8Schin 		struct blk *blokstak;
1247c478bd9Sstevel@tonic-gate 		if (staktop >= brkend)
1257c478bd9Sstevel@tonic-gate 			growstak(staktop);
1267c478bd9Sstevel@tonic-gate 		pushstak(0);
1270b46ffbaSmj 		rndstak = (unsigned char *)round(staktop, ALIGNSIZ);
1287c478bd9Sstevel@tonic-gate 		blokstak = (struct blk *)(stakbas) - 1;
1297c478bd9Sstevel@tonic-gate 		blokstak->word = stakbsy;
1307c478bd9Sstevel@tonic-gate 		stakbsy = blokstak;
1317c478bd9Sstevel@tonic-gate 		bloktop->word = (struct blk *)(Rcheat(rndstak) | BUSY);
1327c478bd9Sstevel@tonic-gate 		bloktop = (struct blk *)(rndstak);
1337c478bd9Sstevel@tonic-gate 	}
1347c478bd9Sstevel@tonic-gate 	reqd += brkincr;
1357c478bd9Sstevel@tonic-gate 	reqd &= ~(brkincr - 1);
1367c478bd9Sstevel@tonic-gate 	blokp = bloktop;
1377c478bd9Sstevel@tonic-gate 	/*
1387c478bd9Sstevel@tonic-gate 	 * brkend points to the first invalid address.
1397c478bd9Sstevel@tonic-gate 	 * make sure bloktop is valid.
1407c478bd9Sstevel@tonic-gate 	 */
141db397771Schin 	if ((unsigned char *)&bloktop->word >= brkend) {
1427c478bd9Sstevel@tonic-gate 		if (setbrk((unsigned)((unsigned char *)
1437c478bd9Sstevel@tonic-gate 		    (&bloktop->word) - brkend + sizeof (struct blk))) ==
1447c478bd9Sstevel@tonic-gate 		    (unsigned char *)-1)
1457c478bd9Sstevel@tonic-gate 			error(nospace);
1467c478bd9Sstevel@tonic-gate 	}
1477c478bd9Sstevel@tonic-gate 	bloktop = bloktop->word = (struct blk *)(Rcheat(bloktop) + reqd);
148db397771Schin 	if ((unsigned char *)&bloktop->word >= brkend) {
1497c478bd9Sstevel@tonic-gate 		if (setbrk((unsigned)((unsigned char *)
1507c478bd9Sstevel@tonic-gate 		    (&bloktop->word) - brkend + sizeof (struct blk))) ==
1517c478bd9Sstevel@tonic-gate 		    (unsigned char *)-1)
1527c478bd9Sstevel@tonic-gate 			error(nospace);
1537c478bd9Sstevel@tonic-gate 	}
1547c478bd9Sstevel@tonic-gate 	bloktop->word = (struct blk *)(brkbegin + 1);
1557c478bd9Sstevel@tonic-gate 	{
156965005c8Schin 		unsigned char *stakadr = (unsigned char *)
1577c478bd9Sstevel@tonic-gate 							(bloktop + 2);
158965005c8Schin 		unsigned char *sp = stakadr;
159db397771Schin 		if (reqd = (staktop-stakbot)) {
1607c478bd9Sstevel@tonic-gate 			if (stakadr + reqd >= brkend)
1617c478bd9Sstevel@tonic-gate 				growstak(stakadr + reqd);
1627c478bd9Sstevel@tonic-gate 			while (reqd-- > 0)
1637c478bd9Sstevel@tonic-gate 				*sp++ = *stakbot++;
1647c478bd9Sstevel@tonic-gate 			sp--;
1657c478bd9Sstevel@tonic-gate 		}
1667c478bd9Sstevel@tonic-gate 		staktop = sp;
1677c478bd9Sstevel@tonic-gate 		if (staktop >= brkend)
1687c478bd9Sstevel@tonic-gate 			growstak(staktop);
1697c478bd9Sstevel@tonic-gate 		stakbas = stakbot = stakadr;
1707c478bd9Sstevel@tonic-gate 	}
1717c478bd9Sstevel@tonic-gate }
1737c478bd9Sstevel@tonic-gate void
free(ap)1747c478bd9Sstevel@tonic-gate free(ap)
1757c478bd9Sstevel@tonic-gate 	void *ap;
1767c478bd9Sstevel@tonic-gate {
177965005c8Schin 	struct blk *p;
1797c478bd9Sstevel@tonic-gate 	if ((p = (struct blk *)ap) && p < bloktop && p > (struct blk *)brkbegin)
1807c478bd9Sstevel@tonic-gate 	{
1817c478bd9Sstevel@tonic-gate #ifdef DEBUG
1827c478bd9Sstevel@tonic-gate 		chkbptr(p);
1837c478bd9Sstevel@tonic-gate #endif
1847c478bd9Sstevel@tonic-gate 		--p;
1857c478bd9Sstevel@tonic-gate 		p->word = (struct blk *)(Rcheat(p->word) & ~BUSY);
186*d6b882a9SNobutomo Nakano #ifdef DEBUG
187*d6b882a9SNobutomo Nakano 		fill_pat(p, PAT_FREE);
188*d6b882a9SNobutomo Nakano #endif
1897c478bd9Sstevel@tonic-gate 	}
1927c478bd9Sstevel@tonic-gate }
1957c478bd9Sstevel@tonic-gate #ifdef DEBUG
197*d6b882a9SNobutomo Nakano static void
fill_pat(struct blk * ptr,uint32_t pat)198*d6b882a9SNobutomo Nakano fill_pat(struct blk *ptr, uint32_t pat)
199*d6b882a9SNobutomo Nakano {
200*d6b882a9SNobutomo Nakano 	uint32_t *ui, *eui;
201*d6b882a9SNobutomo Nakano 
202*d6b882a9SNobutomo Nakano 	*(uint32_t *)ptr->pad = PAT_MAGIC;
203*d6b882a9SNobutomo Nakano 	eui = (uint32_t *)(Rcheat(ptr->word) & ~BUSY);
204*d6b882a9SNobutomo Nakano 	for (ui = (uint32_t *)(ptr + 1); ui < eui; ui++)
205*d6b882a9SNobutomo Nakano 		*ui = pat;
206*d6b882a9SNobutomo Nakano }
207*d6b882a9SNobutomo Nakano 
208*d6b882a9SNobutomo Nakano static void
chkbptr(struct blk * ptr)209*d6b882a9SNobutomo Nakano chkbptr(struct blk *ptr)
2107c478bd9Sstevel@tonic-gate {
2117c478bd9Sstevel@tonic-gate 	int	exf = 0;
212965005c8Schin 	struct blk *p = (struct blk *)brkbegin;
213965005c8Schin 	struct blk *q;
2147c478bd9Sstevel@tonic-gate 	int	us = 0, un = 0;
216*d6b882a9SNobutomo Nakano 	for (;;) {
2177c478bd9Sstevel@tonic-gate 		q = (struct blk *)(Rcheat(p->word) & ~BUSY);
2197c478bd9Sstevel@tonic-gate 		if (p+1 == ptr)
2207c478bd9Sstevel@tonic-gate 			exf++;
2227c478bd9Sstevel@tonic-gate 		if (q < (struct blk *)brkbegin || q > bloktop)
223*d6b882a9SNobutomo Nakano 			abort();
2257c478bd9Sstevel@tonic-gate 		if (p == bloktop)
2267c478bd9Sstevel@tonic-gate 			break;
2287c478bd9Sstevel@tonic-gate 		if (busy(p))
2297c478bd9Sstevel@tonic-gate 			us += q - p;
2307c478bd9Sstevel@tonic-gate 		else
2317c478bd9Sstevel@tonic-gate 			un += q - p;
2337c478bd9Sstevel@tonic-gate 		if (p >= q)
234*d6b882a9SNobutomo Nakano 			abort();
2367c478bd9Sstevel@tonic-gate 		p = q;
2377c478bd9Sstevel@tonic-gate 	}
2387c478bd9Sstevel@tonic-gate 	if (exf == 0)
239*d6b882a9SNobutomo Nakano 		abort();
2407c478bd9Sstevel@tonic-gate }
242*d6b882a9SNobutomo Nakano static void
chkmem()2437c478bd9Sstevel@tonic-gate chkmem()
2447c478bd9Sstevel@tonic-gate {
245965005c8Schin 	struct blk *p = (struct blk *)brkbegin;
246965005c8Schin 	struct blk *q;
2477c478bd9Sstevel@tonic-gate 	int	us = 0, un = 0;
2497c478bd9Sstevel@tonic-gate 	for (;;) {
2507c478bd9Sstevel@tonic-gate 		q = (struct blk *)(Rcheat(p->word) & ~BUSY);
2527c478bd9Sstevel@tonic-gate 		if (q < (struct blk *)brkbegin || q > bloktop)
253*d6b882a9SNobutomo Nakano 			abort();
2557c478bd9Sstevel@tonic-gate 		if (p == bloktop)
2567c478bd9Sstevel@tonic-gate 			break;
2587c478bd9Sstevel@tonic-gate 		if (busy(p))
2597c478bd9Sstevel@tonic-gate 			us += q - p;
2607c478bd9Sstevel@tonic-gate 		else
2617c478bd9Sstevel@tonic-gate 			un += q - p;
2637c478bd9Sstevel@tonic-gate 		if (p >= q)
264*d6b882a9SNobutomo Nakano 			abort();
2667c478bd9Sstevel@tonic-gate 		p = q;
2677c478bd9Sstevel@tonic-gate 	}
2697c478bd9Sstevel@tonic-gate 	prs("un/used/avail ");
2707c478bd9Sstevel@tonic-gate 	prn(un);
2717c478bd9Sstevel@tonic-gate 	blank();
2727c478bd9Sstevel@tonic-gate 	prn(us);
2737c478bd9Sstevel@tonic-gate 	blank();
274*d6b882a9SNobutomo Nakano 	prn((uintptr_t)bloktop - (uintptr_t)brkbegin - (un + us));
2757c478bd9Sstevel@tonic-gate 	newline();
2777c478bd9Sstevel@tonic-gate }
2797c478bd9Sstevel@tonic-gate #endif
2817c478bd9Sstevel@tonic-gate size_t
blklen(q)2827c478bd9Sstevel@tonic-gate blklen(q)
2837c478bd9Sstevel@tonic-gate char *q;
2847c478bd9Sstevel@tonic-gate {
285965005c8Schin 	struct blk *pp = (struct blk *)q;
286965005c8Schin 	struct blk *p;
2887c478bd9Sstevel@tonic-gate 	--pp;
2897c478bd9Sstevel@tonic-gate 	p = (struct blk *)(Rcheat(pp->word) & ~BUSY);
2917c478bd9Sstevel@tonic-gate 	return ((size_t)((long)p - (long)q));
2927c478bd9Sstevel@tonic-gate }
2947c478bd9Sstevel@tonic-gate /*
2957c478bd9Sstevel@tonic-gate  * This is a really hasty hack at putting realloc() in the shell, along
2967c478bd9Sstevel@tonic-gate  * with alloc() and free(). I really hate having to do things like this,
2977c478bd9Sstevel@tonic-gate  * hacking in something before I understand _why_ libcollate does any
2987c478bd9Sstevel@tonic-gate  * memory (re)allocation, let alone feel comfortable with this particular
2997c478bd9Sstevel@tonic-gate  * implementation of realloc, assuming it actually gets used by anything.
3007c478bd9Sstevel@tonic-gate  *
3017c478bd9Sstevel@tonic-gate  * I plan to revist this, for now this is just to get sh to compile so
3027c478bd9Sstevel@tonic-gate  * that xcu4 builds may be done and we get xcu4 on our desktops.
3037c478bd9Sstevel@tonic-gate  *
3047c478bd9Sstevel@tonic-gate  * Eric Brunner, 10/21/94
3057c478bd9Sstevel@tonic-gate  *
3067c478bd9Sstevel@tonic-gate  * Implemented a variation on the suggested fix in Trusted Solaris 2.5,
3077c478bd9Sstevel@tonic-gate  * then forward ported the fix into the mainline shell.
3087c478bd9Sstevel@tonic-gate  *
3097c478bd9Sstevel@tonic-gate  * 3/3/99
3107c478bd9Sstevel@tonic-gate  */
3117c478bd9Sstevel@tonic-gate #ifdef __STDC__
3127c478bd9Sstevel@tonic-gate void *
realloc(pp,nbytes)3137c478bd9Sstevel@tonic-gate realloc(pp, nbytes)
3147c478bd9Sstevel@tonic-gate void *pp;
3157c478bd9Sstevel@tonic-gate size_t nbytes;
3167c478bd9Sstevel@tonic-gate #else
3177c478bd9Sstevel@tonic-gate char *
3187c478bd9Sstevel@tonic-gate realloc(pp, nbytes)
3197c478bd9Sstevel@tonic-gate char *pp;
3207c478bd9Sstevel@tonic-gate size_t nbytes;
3217c478bd9Sstevel@tonic-gate #endif
3227c478bd9Sstevel@tonic-gate {
3237c478bd9Sstevel@tonic-gate 	char *q;
3247c478bd9Sstevel@tonic-gate 	size_t blen;
3267c478bd9Sstevel@tonic-gate 	if (pp == NULL)
3277c478bd9Sstevel@tonic-gate 		return (alloc(nbytes));
3287c478bd9Sstevel@tonic-gate 	if ((nbytes == 0) && (pp != NULL))
3297c478bd9Sstevel@tonic-gate 		free(pp);
3317c478bd9Sstevel@tonic-gate 	blen = blklen(pp);
3337c478bd9Sstevel@tonic-gate 	if (blen < nbytes) {		/* need to grow */
3347c478bd9Sstevel@tonic-gate 		q = alloc(nbytes);
3357c478bd9Sstevel@tonic-gate 		memcpy(q, pp, blen);
3367c478bd9Sstevel@tonic-gate 		free(pp);
3377c478bd9Sstevel@tonic-gate 		return ((char *)q);
3387c478bd9Sstevel@tonic-gate 	} else if (blen == nbytes) {	/* do nothing */
3397c478bd9Sstevel@tonic-gate 		return (pp);
3407c478bd9Sstevel@tonic-gate 	} else {			/* free excess */
3417c478bd9Sstevel@tonic-gate 		q = alloc(nbytes);
3427c478bd9Sstevel@tonic-gate 		memcpy(q, pp, nbytes);
3437c478bd9Sstevel@tonic-gate 		free(pp);
3447c478bd9Sstevel@tonic-gate 		return ((char *)q);
3457c478bd9Sstevel@tonic-gate 	}
3477c478bd9Sstevel@tonic-gate #ifdef undef
3487c478bd9Sstevel@tonic-gate 	/*
3497c478bd9Sstevel@tonic-gate 	 * all of what follows is the _idea_ of what is going to be done
3507c478bd9Sstevel@tonic-gate 	 * getting the size of the block is a problem -- what follows
3517c478bd9Sstevel@tonic-gate 	 * is _not_ "real", since "sizeof" isn't going to tell me any
3527c478bd9Sstevel@tonic-gate 	 * thing usefull, probably have to travers the list to the next
3537c478bd9Sstevel@tonic-gate 	 * blk, then subtract ptr addrs ... and be careful not to leave
3547c478bd9Sstevel@tonic-gate 	 * holes.
3557c478bd9Sstevel@tonic-gate 	 */
3567c478bd9Sstevel@tonic-gate 	p = (struct blk *)pp;
3577c478bd9Sstevel@tonic-gate 	if (sizeof (p) < nbytes) {			/* need to grow */
3587c478bd9Sstevel@tonic-gate 		q = alloc(nbytes);
3597c478bd9Sstevel@tonic-gate 		memcpy(q, pp, sizeof (p));
3607c478bd9Sstevel@tonic-gate 		free(pp);
3617c478bd9Sstevel@tonic-gate 		return ((char *)q);
3627c478bd9Sstevel@tonic-gate 	} else if (sizeof (p) == nbytes) {		/* do nothing */
3637c478bd9Sstevel@tonic-gate 		return (pp);
3647c478bd9Sstevel@tonic-gate 	} else {					/* free excess */
3657c478bd9Sstevel@tonic-gate 		q = alloc(nbytes);
3667c478bd9Sstevel@tonic-gate 		memcpy(q, pp, nbytes);
3677c478bd9Sstevel@tonic-gate 		free(pp);
3687c478bd9Sstevel@tonic-gate 		return ((char *)q);
3697c478bd9Sstevel@tonic-gate 	}
3707c478bd9Sstevel@tonic-gate #endif
3717c478bd9Sstevel@tonic-gate }