jsq@ut-sally.UUCP (John Quarterman) (08/01/85)
----------------------------------------------------------------------
Date: Wed, 31 Jul 85 13:14:10 edt
From: Arnold Robbins <gatech!arnold>
Subject: Storage allocators
To: cbosgd!std-c, ut-sally!std-unix
Keywords: stack allocation, standardizing undocumented features
Unix has long had an undocumented routine alloca(), which allocates
storage off the stack. This storage then goes away when the function
returns.
I would like to see this documented in the Unix standard under development,
and also included in the new ANSI C standard. I would suggest that
the name get changed to something like salloc() [stack alloc], with
semantics similar to malloc (returned storage probably initialized to
garbage), only the storage is temporary, not permanent.
I think that cross posting to both groups is appropriate, 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.
------------------------------
Discussions-Of: UNIX standards, particularly the IEEE P1003 draft standard.
Submissions-To: ut-sally!std-unix or std-unix@ut-sally.ARPA
Comments-To: ut-sally!std-unix-request or std-unix-request@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)jsq@ut-sally.UUCP (John Quarterman) (08/04/85)
----------------------------------------------------------------------
Date: Fri, 2 Aug 85 17:37:19 EDT
From: Doug Gwyn <gwyn@BRL.ARPA>
To: arnold%gatech.uucp@BRL-TGR.ARPA
Cc: std-unix@UT-SALLY.ARPA, std-c%cbosgd.uucp@BRL-TGR.ARPA
Subject: Re: alloca()
No! It is not always possible to implement alloca(). Neither Gould
nor I could make it work on UTX-32. We very definitely do not need
this sort of critter in any standards!
(It also adds no functionality and encourages sloppy coding practice.)
------------------------------
Discussions-Of: UNIX standards, particularly the IEEE P1003 draft standard.
Submissions-To: ut-sally!std-unix or std-unix@ut-sally.ARPA
Comments-To: ut-sally!std-unix-request or std-unix-request@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)jsq@ut-sally.UUCP (John Quarterman) (08/05/85)
----------------------------------------------------------------------
Date: Mon, 5 Aug 85 10:04:43 edt
From: Arnold Robbins <gatech!arnold>
To: gwyn@brl.arpa
Subject: Re: alloca()
Cc: cbosgd!std-c, ut-sally!std-unix
Well, I just sort of liked the idea of using storage on the stack. It
is really nice for dynamic arrays. I'll agree that it can lead to poor
coding practices. The Gould must have a very interesting architecture
if alloca wouldn't work on it.
Arnold
------------------------------
Discussions-Of: UNIX standards, particularly the IEEE P1003 draft standard.
Submissions-To: ut-sally!std-unix or std-unix@ut-sally.ARPA
Comments-To: ut-sally!std-unix-request or std-unix-request@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)jsq@ut-sally.UUCP (John Quarterman) (08/05/85)
----------------------------------------------------------------------
From: seismo!BBN-LABS-B.ARPA!dan
To: ut-sally!BBN-LABS-B.ARPA!std-unix
Subject: Re: Storage allocators
Date: 05 Aug 85 12:30:18 EDT (Mon)
Much as I like alloca() in theory, I have to agree with Doug Gwyn that it is
not always implementable--at least, if you are starting with the runtime
environment already designed. Alloca() is a LANGUAGE feature, not a library
feature; it just happens that on many UNIX machines it is possible to add it to
the library and slip it past the compiler as long as you don't try to use it
too hard. On many systems, if you do
routine_with_args(arg1, arg2, arg3, ..., alloca(100), argN,...);
the alloca() will screw things up completely because the arguments before and
after it were pushed on the stack--that is, are SP-relative--and alloca() has
munged the SP. Sufficiently complex expressions can also cause this problem.
Unless alloca() is known to the compiler it usually cannot be implemented
correctly.
However, I don't understand Doug's comment about it encouraging sloppy
programming practice. Alloca() provides the programmer with the ability to
declare automatic variables whose size is determined at runtime rather than
compile time; thus the size can reflect the size of input data, which is GOOD
programming practice. If the makers of UNIX had had alloca() when they did
execvp(), they would not have (a) relied on the existence of array[-1], or (b)
assumed that there would not be more than 200 values in the array (as different
versions of that library routine did). I don't think anyone would argue that
the use of alloca here would have resulted in sloppier code! The only
alternative, if you want to be a good programmer, is to use malloc(), which is
relatively slow and quite clumsy. I have never subscribed to the point of view
that not having to explicitly allocate and free each variable is "sloppy
programming practice"; that's what auto vars are, after all.
Dan Franklin
------------------------------
Discussions-Of: UNIX standards, particularly the IEEE P1003 draft standard.
Submissions-To: ut-sally!std-unix or std-unix@ut-sally.ARPA
Comments-To: ut-sally!std-unix-request or std-unix-request@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)jsq@ut-sally.UUCP (John Quarterman) (08/07/85)
---------------------------------------------------------------------- Date: Tue, 6 Aug 85 01:11:53 PDT From: seismo!sun!guy (Guy Harris) To: cbosgd!std-c, ut-sally!std-unix Subject: Re: Storage allocators > Unix has long had an undocumented routine alloca(), which allocates > storage off the stack. This storage then goes away when the function > returns. *Some* UNIXes have had it. It was a PWB/UNIX invention, and wiggled its way into 4.xBSD; I don't remember it being in V7. > ...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. If you said "I know that there are no machines which can't do 'alloca'", I'd be more in favor of this proposal. C supports variables on the stack, but that merely requires that you can allocate a stack frame on procedure entry, not that you can extend a stack frame during the execution of a procedure. I would not be willing to say that all machines with C implementations can do that. >From the standpoint of UNIX, it's not clear that it's something that's been there for a long time in *all* UNIXes. Guy Harris ------------------------------ Discussions-Of: UNIX standards, particularly the IEEE P1003 draft standard. Submissions-To: ut-sally!std-unix or std-unix@ut-sally.ARPA Comments-To: ut-sally!std-unix-request or std-unix-request@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)
jsq@ut-sally.UUCP (John Quarterman) (08/11/85)
From: John Quarterman (moderator) <std-unix-request@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@ut-sally.UUCP> References: <2561@ut-sally.UUCP> <2579@ut-sally.UUCP> <2590@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@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@ut-sally.ARPA Comments-To: ut-sally!std-unix-request or std-unix-request@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)
jsq@ut-sally.UUCP (John Quarterman) (08/14/85)
----------------------------------------------------------------------
Date: Tue, 13 Aug 85 11:38:32 edt
From: seismo!allegra!phri!roy (Roy Smith)
To: ut-sally!std-unix
Subject: Storage allocation
Cc: roy
I'm not sure if it is really germane to the issue at hand, but I
recently (yesterday) submitted to mod.sources a little package to handle
run time memory allocation for multi-dimensional arrays. You might want to
take a look at it.
Is it reasonable to include such a functionality in a Unix
standard? I don't know if memory allocators should be considered part of
the C language, or part of the Unix OS, but given the fuss that went on
recently (in net.unix-wizards?) about the issue, it seems that it should be
addressed somewhere. Of course, my implementation isn't necessarily the
best one (or even a good one), but I think the idea is sound.
Roy Smith <allegra!phri!roy>
System Administrator, Public Health Research Institute
455 First Avenue, New York, NY 10016
------------------------------
Discussions-Of: UNIX standards, particularly the IEEE P1003 draft standard.
Submissions-To: ut-sally!std-unix or std-unix@ut-sally.ARPA
Comments-To: ut-sally!std-unix-request or std-unix-request@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)