Path: utzoo!utgpu!news-server.csri.toronto.edu!bonnie.concordia.ca!thunder.mcrcim.mcgill.edu!snorkelwacker.mit.edu!mit-eddie!uw-beaver!zephyr.ens.tek.com!tektronix!sequent!mntgfx!caeco!vixen!ronbo
From: ronbo@vixen.uucp (Ron Hitchens)
Newsgroups: comp.sys.amiga.programmer
Subject: Re: AmigaGCC stack hogging
Message-ID: <390@vixen.uucp>
Date: 3 Feb 91 08:26:56 GMT
References: <1882f287.ARN1979@moria.UUCP> <1991Jan14.212254.9779@csun.edu> <18887df5.ARN1ad7@moria.UUCP> <1991Jan17.141218.19953@zorch.SF-Bay.ORG> <JKH.91Jan29040442@bambam.pcs.com>
Reply-To: ronbo@vixen.UUCP (Ron Hitchens)
Organization: Sleepless Software
Lines: 138

>>Maybe I'm missing the point here.  The _purpose_ of alloca() is to
>>allow extremely low overhead grabbing and releasing of extremely
>>.. [etc etc]
>>Why replace it by putting back something that installs the very same
>>problems alloca() was trying to solve, ...
>>
>>If the gnu code is doing inappropriate things with alloca() replace the
>>calls with malloc() calls explicitly.  Otherwise you are just creating
>
>ARGH! NO! NO!
>
>I'm afraid you _are_ missing the point, Kent.  While you're right in
>saying that the primary purpose of alloca() is to provide low overhead
>you-don't-need-to-worry-about-freeing-it-afterwards allocation of
>memory, just replacing the calls to alloca() with malloc() IS NOT a
>good solution to the problem! Unless you then take the time to track
>the memory so allocated and explicitly free() it at the appropriate
>time, you've just introduced a memory leak. 

    I've been thinking about this problem since it came up in this group
and I think I may have a good compromise solution.

    The "problem", for those who may be unclear on what it is, is that
the gcc compiler makes extensive use of the alloca() function which means
that it requires a huge stack in order to run without crashing on the Amiga.
The alloca() function allocates memory, similar to the more common malloc()
function, but it allocates the memory from the top of the stack rather than
from the general memory pool.  This usually means it is quite fast, but
more importantly it means that the allocated memory automatically disappears
when the function from which it was called exits.  Now, this works fine and
dandy on a unix system which can detect stack overruns, via an MMU, and
transparently grow the stack as needed.  Unfortunately the Amiga cannot
grow the stack for a task once it has started, so therefore gcc's heavy use
of alloca() means humungous amounts of stack space must be used when running
gcc to guard against the worst possible case.

    On the Amiga, we'd like to move all these alloca() calls off the stack,
but preserve the automatic-free behaviour to avoid having to rewrite huge
chunks of the compiler to do memory tracking.  Well, I think I have a way
to do that, which is possible because gcc is so configurable.

    In order to have alloca()'ed memory automatically disappear at function
exit it either needs to be incorporated into the current stack frame, as it
commonly is on unix, or you need some sort of hook that can reliably be
called whenever the function exits.  Such a hook exists in gcc, the config
headers for gcc allow you to define function prologue and epilogue code
that is generated at the beginning and end of every function.  It seems to
me that this is the place to hook in an alloca()-like scheme which actually
does malloc()-like allocations.

    It should be fairly simple to do with some code like the following:


typedef struct
	struct MinNode	node;		/* node struct for chaining */
	short		level;		/* nesting level when alloced */
	short		pad;		/* maintain longword alignment */
} AllocaNode;

static struct List	alloca_list = {		/* stack of malloc'ed blocks */
	(struct Node *) &alloca_list.lh_Tail, NULL,
	(struct Node *) &alloca_list.lh_Head, 0, 0
};

static int		alloca_level = 0;

/*	Called at function entry, increments current nesting level */
void
push_alloca (void)
{
	alloca_level++;
}

/*	Called at function exit, zaps blocks malloc'ed at current level */
void
pop_alloca (void)
{
	AllocaNode	*node;

	while ((node = (AllocaNode *) RemHead (&alloca_list)) != NULL) {
		if (node->level < alloca_level) {
			/* alloced below this level, put it back */
			AddHead (&alloca_list, (struct Node *) node);
			break;
		}
		free (node);
	}

	alloca_level--;
}

/*	Alternate alloca, mallocs and flags blocks with current nest level */
void *
alloca (size_t size)
{
	AllocaNode	*node = malloc (size + sizeof (AllocaNode));

	if (node == NULL) {
		return (NULL);
	}

	node->level = alloca_level;
	AddHead (&alloca_list, (struct Node *) node);

	node++;			/* bump past AllocaNode header */

	return (node);
}


    This code is not tested, I just now typed it in, but should be mostly
right.  The way it would work is this: when every function is entered it
would call push_alloca() to increment the current notion of the nesting
level for alloca's purposes.  When the function exits it would call
pop_alloca() which will free all the memory blocks that have been malloc'ed
at that level, then decrement the nesting level.  The alternate version
of alloca() will use malloc() to allocate the requested amount of space plus
a small header for a list node and a field to indicate what the nesting
level was at the time it was allocated, for unwinding the allocation stack.

    The calls to push_alloca() and pop_alloca() would be automatically 
generated as part of the FUNCTION_PROLOGUE and FUNCTION_EPILOGUE macros
which are defined in the tm.h header file in gcc, preferably conditional
on a run-time switch.

    This example code is in C, but if implemented would probably be done
in assembler for efficency.  The call to push_alloc() could even be replaced
by an inline add if the nesting variable is made global.  You could
probably get a performance increase by using AllocMem() rather than malloc,
but you'd have a memory leak if the program didn't exit by returning from
main() (ie by calling exit()).  Also, setjmp/longjmp would cause problems.

    Anyway, that's my suggestion for a workaround for gcc's stack gluttony.
Others are welcome to build on it.  Personally, I generally run a version
of gcc on my Sun which cross-compiles for the Amiga, so it doesn't present
much of a problem for me.

-- 
Ron Hitchens    /-O-O   | ronbo@vixen.uucp			- Smart uucp
  Sleepless     C  >    | ...!cs.utah.edu!caeco!vixen!ronbo	- Stupid uucp
    Software       ~    | hitchens@cs.utexas.edu		- Internet
"To be is to do" -Socrates  "To do is to be" -Sartre  "Do be do be do" -Sinatra