/*
 * CDDL HEADER START
 *
 * The contents of this file are subject to the terms of the
 * Common Development and Distribution License (the "License").
 * You may not use this file except in compliance with the License.
 *
 * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
 * or http://www.opensolaris.org/os/licensing.
 * See the License for the specific language governing permissions
 * and limitations under the License.
 *
 * When distributing Covered Code, include this CDDL HEADER in each
 * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
 * If applicable, add the following below this CDDL HEADER, with the
 * fields enclosed by brackets "[]" replaced with your own identifying
 * information: Portions Copyright [yyyy] [name of copyright owner]
 *
 * CDDL HEADER END
 */

/*
 * Copyright 2009 Sun Microsystems, Inc.  All rights reserved.
 * Use is subject to license terms.
 */

/*	Copyright (c) 1984, 1986, 1987, 1988, 1989 AT&T	*/
/*	  All Rights Reserved  	*/

/*
 *	UNIX shell
 */

#include	"defs.h"


/*
 *	storage allocator
 *	(circular first fit strategy)
 */

#define	BUSY 01
#define	busy(x)	(Rcheat((x)->word) & BUSY)

unsigned	brkincr = BRKINCR;
struct blk *blokp;			/* current search pointer */
struct blk *bloktop;		/* top of arena (last blok) */

unsigned char		*brkbegin;
extern unsigned char		*setbrk();

#ifdef DEBUG
/*
 * If DEBUG is defined, the following testing will be performed:
 * - chkbptr() checks the linkage of blocks by following links.
 *   Note that this makes shell really slow.
 * - fill_pat() fills the memory block with pattern like umem does.
 *   The pattern used to fill the memory area is defined below.
 */
#define	PAT_MAGIC	0xfeedface
#define	PAT_INIT	0xbaddcafe
#define	PAT_FREE	0xdeadbeef

static void	fill_pat(struct blk *, uint32_t);
static void	chkbptr(struct blk *);
#endif

void *
alloc(size_t nbytes)
{
	size_t rbytes = round(nbytes + ALIGNSIZ, ALIGNSIZ);

	if (stakbot == 0) {
		addblok((unsigned int)0);
	}

	for (;;) {
		int	c = 0;
		struct blk *p = blokp;
		struct blk *q;

		do
		{
			if (!busy(p)) {
				while (!busy(q = p->word))
					p->word = q->word;
				if ((char *)q - (char *)p >= rbytes) {
					blokp = (struct blk *)
							((char *)p + rbytes);
					if (q > blokp)
						blokp->word = p->word;
					p->word = (struct blk *)
							(Rcheat(blokp) | BUSY);
#ifdef DEBUG
					fill_pat(p, PAT_INIT);
#endif
					return ((char *)(p + 1));
				}
			}
			q = p;
			p = (struct blk *)(Rcheat(p->word) & ~BUSY);
		} while (p > q || (c++) == 0);
		addblok(rbytes);
	}
}

void
addblok(unsigned int reqd)
{
	if (stakbot == 0) {
		brkbegin = setbrk(3 * BRKINCR);
		/*
		 * setbrk() returns 8 byte aligned address
		 * but we could need larger align in future
		 */
		brkbegin = (unsigned char *)round(brkbegin, ALIGNSIZ);
		bloktop = (struct blk *)brkbegin;
	}

	if (stakbas != staktop) {
		unsigned char *rndstak;
		struct blk *blokstak;

		if (staktop >= brkend)
			growstak(staktop);
		pushstak(0);
		rndstak = (unsigned char *)round(staktop, ALIGNSIZ);
		blokstak = (struct blk *)(stakbas) - 1;
		blokstak->word = stakbsy;
		stakbsy = blokstak;
		bloktop->word = (struct blk *)(Rcheat(rndstak) | BUSY);
		bloktop = (struct blk *)(rndstak);
	}
	reqd += brkincr;
	reqd &= ~(brkincr - 1);
	blokp = bloktop;
	/*
	 * brkend points to the first invalid address.
	 * make sure bloktop is valid.
	 */
	if ((unsigned char *)&bloktop->word >= brkend) {
		if (setbrk((unsigned)((unsigned char *)
		    (&bloktop->word) - brkend + sizeof (struct blk))) ==
		    (unsigned char *)-1)
			error(nospace);
	}
	bloktop = bloktop->word = (struct blk *)(Rcheat(bloktop) + reqd);
	if ((unsigned char *)&bloktop->word >= brkend) {
		if (setbrk((unsigned)((unsigned char *)
		    (&bloktop->word) - brkend + sizeof (struct blk))) ==
		    (unsigned char *)-1)
			error(nospace);
	}
	bloktop->word = (struct blk *)(brkbegin + 1);
	{
		unsigned char *stakadr = (unsigned char *)
							(bloktop + 2);
		unsigned char *sp = stakadr;
		if (reqd = (staktop-stakbot)) {
			if (stakadr + reqd >= brkend)
				growstak(stakadr + reqd);
			while (reqd-- > 0)
				*sp++ = *stakbot++;
			sp--;
		}
		staktop = sp;
		if (staktop >= brkend)
			growstak(staktop);
		stakbas = stakbot = stakadr;
	}
}

void
free(ap)
	void *ap;
{
	struct blk *p;

	if ((p = (struct blk *)ap) && p < bloktop && p > (struct blk *)brkbegin)
	{
#ifdef DEBUG
		chkbptr(p);
#endif
		--p;
		p->word = (struct blk *)(Rcheat(p->word) & ~BUSY);
#ifdef DEBUG
		fill_pat(p, PAT_FREE);
#endif
	}


}


#ifdef DEBUG

static void
fill_pat(struct blk *ptr, uint32_t pat)
{
	uint32_t *ui, *eui;

	*(uint32_t *)ptr->pad = PAT_MAGIC;
	eui = (uint32_t *)(Rcheat(ptr->word) & ~BUSY);
	for (ui = (uint32_t *)(ptr + 1); ui < eui; ui++)
		*ui = pat;
}

static void
chkbptr(struct blk *ptr)
{
	int	exf = 0;
	struct blk *p = (struct blk *)brkbegin;
	struct blk *q;
	int	us = 0, un = 0;

	for (;;) {
		q = (struct blk *)(Rcheat(p->word) & ~BUSY);

		if (p+1 == ptr)
			exf++;

		if (q < (struct blk *)brkbegin || q > bloktop)
			abort();

		if (p == bloktop)
			break;

		if (busy(p))
			us += q - p;
		else
			un += q - p;

		if (p >= q)
			abort();

		p = q;
	}
	if (exf == 0)
		abort();
}

static void
chkmem()
{
	struct blk *p = (struct blk *)brkbegin;
	struct blk *q;
	int	us = 0, un = 0;

	for (;;) {
		q = (struct blk *)(Rcheat(p->word) & ~BUSY);

		if (q < (struct blk *)brkbegin || q > bloktop)
			abort();

		if (p == bloktop)
			break;

		if (busy(p))
			us += q - p;
		else
			un += q - p;

		if (p >= q)
			abort();

		p = q;
	}

	prs("un/used/avail ");
	prn(un);
	blank();
	prn(us);
	blank();
	prn((uintptr_t)bloktop - (uintptr_t)brkbegin - (un + us));
	newline();

}

#endif

size_t
blklen(q)
char *q;
{
	struct blk *pp = (struct blk *)q;
	struct blk *p;

	--pp;
	p = (struct blk *)(Rcheat(pp->word) & ~BUSY);

	return ((size_t)((long)p - (long)q));
}

/*
 * This is a really hasty hack at putting realloc() in the shell, along
 * with alloc() and free(). I really hate having to do things like this,
 * hacking in something before I understand _why_ libcollate does any
 * memory (re)allocation, let alone feel comfortable with this particular
 * implementation of realloc, assuming it actually gets used by anything.
 *
 * I plan to revist this, for now this is just to get sh to compile so
 * that xcu4 builds may be done and we get xcu4 on our desktops.
 *
 * Eric Brunner, 10/21/94
 *
 * Implemented a variation on the suggested fix in Trusted Solaris 2.5,
 * then forward ported the fix into the mainline shell.
 *
 * 3/3/99
 */
#ifdef __STDC__
void *
realloc(pp, nbytes)
void *pp;
size_t nbytes;
#else
char *
realloc(pp, nbytes)
char *pp;
size_t nbytes;
#endif
{
	char *q;
	size_t blen;

	if (pp == NULL)
		return (alloc(nbytes));
	if ((nbytes == 0) && (pp != NULL))
		free(pp);

	blen = blklen(pp);

	if (blen < nbytes) {		/* need to grow */
		q = alloc(nbytes);
		memcpy(q, pp, blen);
		free(pp);
		return ((char *)q);
	} else if (blen == nbytes) {	/* do nothing */
		return (pp);
	} else {			/* free excess */
		q = alloc(nbytes);
		memcpy(q, pp, nbytes);
		free(pp);
		return ((char *)q);
	}

#ifdef undef
	/*
	 * all of what follows is the _idea_ of what is going to be done
	 * getting the size of the block is a problem -- what follows
	 * is _not_ "real", since "sizeof" isn't going to tell me any
	 * thing usefull, probably have to travers the list to the next
	 * blk, then subtract ptr addrs ... and be careful not to leave
	 * holes.
	 */
	p = (struct blk *)pp;
	if (sizeof (p) < nbytes) {			/* need to grow */
		q = alloc(nbytes);
		memcpy(q, pp, sizeof (p));
		free(pp);
		return ((char *)q);
	} else if (sizeof (p) == nbytes) {		/* do nothing */
		return (pp);
	} else {					/* free excess */
		q = alloc(nbytes);
		memcpy(q, pp, nbytes);
		free(pp);
		return ((char *)q);
	}
#endif
}