Storage allocators

[John Quarterman]

From: John Quarterman (moderator) <std-unix-request at ut-sally>
Topic: Storage allocaters (alloca)

----------------------------------------------------------------------

From: ihnp4!hcr!hcrvx1!hugh
Date: 8 Aug 85 11:37:25 CDT (Thu)
To: hcr!ihnp4!ut-sally!std-unix
Subject: Re: Storage allocators

> ...since C supports variables on the stack, so I doubt that there are many
> machines which can't do alloca(), and for Unix, it comes down to
> documenting something that has been there for a long time.

alloca(), when implemented behind the back of a compiler is dangerous,
as described earlier ("f(..., alloca(...), ...)").  It also has a
potential performance penalty on EVERY function, not just those that use
it: with alloca, the system is forced to have a distinct frame pointer
and stack pointer.  Without the possibility of alloca, a frame pointer
is not needed (the activation record can be accessed by
known-at-compile-time offsets from the stack pointer).  Using two
registers instead of one could cause a noticeable increase in function
prologue/epilogue time.

I agree that the functionality of alloca() is useful, but it is not
sanely handled as a library routine.  ALGOL-60 got this right;
too bad its descendants didn't.

It appears that the C standard will give the compiler license to "know"
about library routines specified in the standard (and no others!).  Thus
the compiler would be able to treat alloca specially if it were included
in the standard.  Such a compiler might need an extra pass to be able to
avoid using a frame-pointer, and it would have to be able to generate
code both with and without a frame-pointer.  Even generating correct code
is tricky.  Perhaps, if alloca is standardized, it should be restricted
to certain usages, just as setjmp has been.

My hope is that alloca could be eliminated.  But even though it is
undocumented, there may be too many programs using it now.  Does anyone
know?

Perhaps this discussion should be in mod.std.c, not mod.std.unix.  I
hope that I have convinced you that this is a compiler/language issue,
not an isolated library issue.

[ The article that started the discussion was cross-posted to the two
newsgroups.  It's not clear that it still belongs in mod.std.unix,
but since it's involved UNIX history and implementation, I've seen
no reason to discourage it.  C library issues in general do more 
properly belong in mod.std.c, though.  -mod ]

------------------------------

From: ihnp4!tektronix!hammer.TEK!steveh (Stephen Hemminger)
To: tektronix!ihnp4!seismo!ut-sally!jsq
Date: Fri, 9 Aug 85 09:14:33 PDT
Subject: Re: Storage allocators
In-Reply-To: <2592 at ut-sally.UUCP>
References: <2561 at ut-sally.UUCP> <2579 at ut-sally.UUCP> <2590 at ut-sally.UUCP>

On the Tek NS32000 computers we have to fudge to get alloca() to work, but
I think the same technique might work on other computers.

The stack frame looks like:
	sp ->  ...
	      saved registers (0 ... 8)
	      local vars
	fp -> old fp
	      args

The kludge we implemented for alloca was to allocate 32 bytes (8 regs)
more of storage and copy the top 32 bytes.  Unless the machine has
a huge number of registers, this technique should allow alloca on
any machine!

				|--|		|--|
  [I'd rather be skiing]	| /|		| /|
			    .	|/ |		|/ |
			       .|--|		|--|
				| .|		|  |
	Stephen Hemminger	|  |.		|  |
	(steveh at hammer.TEK)	    .
				   .
				 .
		 	       .

[ I've broken my rule of asking for explicit permission to post things
mailed to my personal address, since this one was an obvious submission. -mod ]

------------------------------

Discussions-Of: UNIX standards, particularly the IEEE P1003 draft standard.
Submissions-To:	ut-sally!std-unix	or std-unix at ut-sally.ARPA
Comments-To: ut-sally!std-unix-request	or std-unix-request at ut-sally.ARPA
UUCP-Routes: {ihnp4,seismo,harvard,gatech}!ut-sally!std-unix
Archives-In: ~ftp/pub/mod.std.unix on ut-sally.ARPA (soon sally.UTEXAS.EDU)