schwartz@swatsun.uucp (Scott Schwartz) (06/06/88)
In article <8017@brl-smoke.ARPA> gwyn@brl.arpa (Doug Gwyn (VLD/VMB) <gwyn>) writes: >For a limited class of applications, alloca() can be useful. >However, I don't use it myself. My applications all use a more >disciplined approach to memory allocation. One nice C extension that gcc provides is variable sized automatic arrays. I.e. foo(s) int s; { int a[s]; } I think this obviates the need for alloca() in most (all?) cases. Too late to get it in ansi, I suppose. -- Scott Schwartz, schwartz@swarthmore.edu, psuvax1!vu-vlsi!swatsun!schwartz
karl@haddock.ISC.COM (Karl Heuer) (06/06/88)
In article <1874@thebes.UUCP> schwartz@thebes.UUCP (Scott Schwartz) writes: >[gcc allows "foo(s) int s; { int a[s]; ... }".] >I think this obviates the need for alloca() in most (all?) cases. >Too late to get it in ansi, I suppose. Yes, I'm sure it's much too late to get it into ANSI C-88, if indeed it ever had a chance. But this is exactly the right way to get it into C-99 (or whenever __STDC__==2 comes out): by including it as a nonconforming extension in popular compilers, the ramifications ought to be well-understood by then. Karl W. Z. Heuer (ima!haddock!karl or karl@haddock.isc.com), The Walking Lint Followups to comp.lang.c.
ted%nmsu.csnet@relay.cs.net (06/10/88)
With respect to alloca,
From: Neil Webber <nw@palladium.uucp>
.
I believe that the real solution to this class of problem lies in
the constructor/destructor model of C++ and other such languages.
But isn't the following idiom for co-routines useful? (and how would it
be done with c++ constructors, without alloca)?
#include <stdio.h>
#include <setjmp.h>
/* set up a continuation with some free stack space */
#define cospawn(jb,fun,space) {if (_setjmp(jb)) fun();else alloca(space);}
/* transfer from one co-routine to another, saving our context */
#define cojmp(us,them) {if (!_setjmp(us)) _longjmp(them,1);}
jmp_buf A,B,C;
main()
{
int i;
void printa();
void printb();
cospawn(A,printa,1000);
cospawn(B,printb,1000);
for (i=0;i<5;i++) {
cojmp(C,A); /* transfer to A */
printf("c\n"); /* note the return */
cojmp(C,A);
printf("C\n");
}
}
/* print an 'a', transfer to B, then print an 'A' and transfer to B */
void printa(them)
continuation them;
{
while (1) {
printf("a ");fflush(stdout);
cojmp(A,B);
printf("A ");fflush(stdout);
cojmp(A,B);
}
}
/* print an 'b', transfer to C, then print an 'B' and transfer to C */
void printb(them)
continuation them;
{
while (1) {
printf("b ");fflush(stdout);
cojmp(B,C);
printf("B ");fflush(stdout);
cojmp(B,C);
}
}
It is of course possible to do the same by using malloc and munging on
the contents of the jmp_buf, but many implementations get very
paranoid when they suddenly find their stack pointer in the middle of
the heap. Another alternative is for main() to allocate separate
stacks as local variables of type char []. This still requires
munging the jmp_buf. All techniques which require changing the
jmp_buf need to know which direction the stack grows, and something
about whether a push involves pre or post de(in)crement. This idiom
has the advantage of not depending on the structure of a jmp_buf, nor
does it depend on the detailed operation of alloca (only on the
correct operation).chris@mimsy.UUCP (Chris Torek) (06/10/88)
In article <16126@brl-adm.ARPA> ted%nmsu.csnet@relay.cs.net writes:
[alloca + setjmp/longjmp for coroutines]
longjmp is not suitable for coroutines because it is valid for longjmp
to attempt to unwind the stack in order to find the corresponding
setjmp, and it is therefore legal for longjmp to abort if it is
attempting to jump the `wrong way' on the stack.
--
In-Real-Life: Chris Torek, Univ of MD Comp Sci Dept (+1 301 454 7163)
Domain: chris@mimsy.umd.edu Path: uunet!mimsy!chrisdjones@megatest.UUCP (Dave Jones) (06/11/88)
From article <11902@mimsy.UUCP>, by chris@mimsy.UUCP (Chris Torek): > In article <16126@brl-adm.ARPA> ted%nmsu.csnet@relay.cs.net writes: > [alloca + setjmp/longjmp for coroutines] > > longjmp is not suitable for coroutines because it is valid for longjmp > to attempt to unwind the stack in order to find the corresponding > setjmp, and it is therefore legal for longjmp to abort if it is > attempting to jump the `wrong way' on the stack. > -- > In-Real-Life: Chris Torek, Univ of MD Comp Sci Dept (+1 301 454 7163) > Domain: chris@mimsy.umd.edu Path: uunet!mimsy!chris I'm no C wizard -- BSD4.2 and Sun3-OS are the only C's I've ever used -- but it seems to me that longjmp is the most suitable technique going, by default. What else is there? You could use [abuse?] sigvec and kill. But if you use separate stacks of fixed sizes, they can overflow with disastrous consequences. And -- correct me if I'm wrong -- more systems have setjmp/longjmp/alloca than have sigvec and kill. Or you could use a smattering of assembler. But, it will certainly run on more kinds of machines if written in C than it would if written in assembler. And to answer your objection about unwinding the stack, you can see to it that the stack is restored _before_ you do the longjmp, so the longjmp can "unwind" as it pleases. I recently wrote a little discrete-event-simulator using setjmp/longjmp/alloca to do lightweight processes. We hope to run it on both Sun3s and IBM PCs. Haven't tried it on the PCs yet, so I don't know if it works there or not. Do I have a surprise in store for me? Here's what I did. The main simulator loop calls alloca(1) to find the bottom of the part of the stack that lightweight processes will be using. It squirrels that address away in the variable {stack_bottom}. To start a process initially, it just calls the process's procedure. Then the simulator and the process trade setjmp/longjmp cycles through a couple of jmpbufs. Well, you'll see. Is there some gotcha that will break this code on some systems? If so, is there a better [more machine independent] way? /*********************************************************************** ** Run the simulation, stopping after some number of ticks, unless ** all processes exit, or some process calls PSim_stop() first. ***********************************************************************/ unsigned long PSim_run(obj, ticks) Simulation* obj; unsigned long ticks; { obj->stack_bottom = (char*)alloca(1); obj->stop_time += ticks; while(!obj->quit) { /* Get a busy process from the busy-queue */ obj->active = (Process*) PQ_pop(&obj->busy); /* If all processes are finished, or are waiting on ** a semaphore, we are blocked, and must exit the simulation. */ if(obj->active==0) goto end_simulation; { register Process *active = obj->active; /* Update the time to the time of the active process */ obj->time = active->busy_until; if( obj->time >= obj->stop_time) goto end_simulation; if(setjmp(active->suspend) == 0) if(active->stack_save == 0) /* Process has not yet started. Call its start-procedure. */ active->return_value = (*(active->start))(obj); else { /* Process has been suspended, and will now be restarted. */ /* allocate the restarting process's stack. */ alloca( active->stack_size ); /* restore it */ bcopy( active->stack_save, active->stack_real, active->stack_size); sfree(active->stack_save); active->stack_save = 0; /* restart the process */ longjmp(active->restart, 1); } } } end_simulation: cleanup(obj); return obj->time; } static suspend_active_proc(obj) register Simulation* obj; { char* stack_top = (char*)alloca(1); long size = abs(obj->stack_bottom - stack_top); register Process* active = obj->active; active->stack_save = (char*)smalloc(size); active->stack_real = min(stack_top, obj->stack_bottom); active->stack_size = size; if(setjmp(active->restart) == 0) { /* copy the stack and return to the simulator. */ bcopy( active->stack_real, active->stack_save, size); longjmp(active->suspend, 1); } }
chris@mimsy.UUCP (Chris Torek) (06/11/88)
Put it this way: If you have a stack or an emulation of a stack (as
required by recursive functions), and if `alloca' is a compiler
builtin, the concept can be implemented. Hence alloca can be *made*
portable to any C compiler, if only by fiat (declare that henceforth
`alloca' is a keyword or is otherwise reserved).
Now the problem becomes one of convincing compiler writers that
alloca (possibly by some other name) is worth adding as a reserved
word, or (on some systems) simply writing it in assembly (either as
a routine or with `inline assembly').
Note that alloca is not a panacea, and that it can largely be simulated
with dynamically sized arrays, as in
int n = get_n();
{
char like_alloca[n];
...
}
These are not identical concepts, but they are interrelated. Whether
one is `more important' or `more useful' than another I will not venture
to say.
--
In-Real-Life: Chris Torek, Univ of MD Comp Sci Dept (+1 301 454 7163)
Domain: chris@mimsy.umd.edu Path: uunet!mimsy!chrishenry@utzoo.uucp (Henry Spencer) (06/14/88)
> I'm no C wizard... but it seems to me that longjmp is the most suitable > technique going, by default... What else is there? You could use [abuse?] > sigvec and kill... In the same way that you're abusing longjmp, you mean? The fact is, there is -->**NO**<-- portable way to accomplish what you're trying to do. None. Coroutines simply cannot be done without some degree of cooperation from the language or the compiler. C doesn't cooperate on the language level, so you're stuck. Yes, you can write code that will more-or-less work, so long as the compiler doesn't spring any surprises on you. Portable it isn't. That being the case, the proper approach is to admit defeat, study your compiler carefully, and write twenty lines of assembler to do things right. -- Man is the best computer we can | Henry Spencer @ U of Toronto Zoology put aboard a spacecraft. --Von Braun | {ihnp4,decvax,uunet!mnetor}!utzoo!henry
mouse@mcgill-vision.UUCP (der Mouse) (06/18/88)
In article <16100@brl-adm.ARPA>, rbj@icst-cmr.arpa (Root Boy Jim) writes: [Other attributions are Neil Webber <nw@palladium.uucp> and ted%nmsu.csnet@relay.cs.net, but it's not clear who wrote what.] > 2) function calling conventions -- unless alloca() is > built into the C compiler it has to implemented as > a C callable function, not an inline stack adjustment. > It's hard to figure out exactly what you mean here. I would imagine that he means more or less what he said. If alloca() is not specially known to the compiler (ie, "built in"), it will compile into a call to a function. It therefore can't be an inline stack adjustment. That's all. (The function called will wind up adjusting the stack, yes, but that's not "inline".) der Mouse uucp: mouse@mcgill-vision.uucp arpa: mouse@larry.mcrcim.mcgill.edu
gallen@apollo.uucp (Gary Allen) (06/20/88)
In article <1169@mcgill-vision.UUCP> mouse@mcgill-vision.UUCP (der Mouse) writes: >In article <16100@brl-adm.ARPA>, rbj@icst-cmr.arpa (Root Boy Jim) writes: >[Other attributions are Neil Webber <nw@palladium.uucp> and >ted%nmsu.csnet@relay.cs.net, but it's not clear who wrote what.] >> 2) function calling conventions -- unless alloca() is >> built into the C compiler it has to implemented as >> a C callable function, not an inline stack adjustment. >> It's hard to figure out exactly what you mean here. > >I would imagine that he means more or less what he said. If alloca() >is not specially known to the compiler (ie, "built in"), it will >compile into a call to a function. It therefore can't be an inline >stack adjustment. That's all. (The function called will wind up >adjusting the stack, yes, but that's not "inline".) Not necessarily. If your C compiler supports the 'asm' statement, it is possible to implement 'alloca' as a macro to adjust the stack pointer and then jam its contents into a register variable. It obviously ain't pretty and it obviously ain't portable, but it does work. Gary Allen Apollo Computer Chelmsford, MA {decvax,umix,yale}!apollo!gallen "I don't need life, I'm high on drugs."
gwyn@smoke.BRL.MIL (Doug Gwyn) (04/22/89)
In article <15945@rpp386.Dallas.TX.US> jfh@rpp386.Dallas.TX.US (John F. Haugh II) writes: >In article <1883@thor.acc.stolaf.edu> mike@mike@stolaf.edu writes: >>To repeat: alloca is EVIL. >It doesn't have to be. You appear to have missed the previous discussion. alloca() simply cannot be reasonably provided in some C environments. If your application depends on alloca(), you have limited its portability. There is no situation I know of when use of alloca() is necessary.
les@chinet.chi.il.us (Leslie Mikesell) (04/22/89)
In article <10090@smoke.BRL.MIL> gwyn@brl.arpa (Doug Gwyn) writes: >>>To repeat: alloca is EVIL. >>It doesn't have to be. >You appear to have missed the previous discussion. >alloca() simply cannot be reasonably provided in some C environments. >If your application depends on alloca(), you have limited its portability. >There is no situation I know of when use of alloca() is necessary. Likewise there is no situation where the use of local variables is necessary. There are two situations which are helped by the use of alloca(): 1) dividing the dynamically allocated space into reasonably sized chunks to reduce the time malloc() and free() need to search their lists, and 2) providing the ability to longjmp() out of a function (or just return) with the no longer needed memory automatically released (just like local variables). In addition to this, alloca() is conceptually the same as using local variables, malloc() is conceptually the same as using global varibles and the same arguments for the use of each should apply. Consider that if you longjmp() out of a function that no longer needs its malloc()'ed memory you *must* have stashed a global pointer in order to free it. Now, why can't the machines that can dynamically allocate space off the stack have an ordinary alloca() and those that can't provide a fake one which uses malloc() but tags the blocks such that calling alloca() or malloc() again will automatically free() any blocks alloca()'ed from a function that is no longer active? This would at least provide the conceptual advantages if not the efficiency. Les Mikesell
gwyn@smoke.BRL.MIL (Doug Gwyn) (04/23/89)
In article <8261@chinet.chi.il.us> les@chinet.chi.il.us (Leslie Mikesell) writes: >Now, why can't the machines that can dynamically allocate space off the >stack have an ordinary alloca() and those that can't provide a fake one >which uses malloc() but tags the blocks such that calling alloca() or >malloc() again will automatically free() any blocks alloca()'ed from >a function that is no longer active? That's indeed more or less how my alloca() emulation works, but there are numerous practical details that have to be taken care of, and such an emulation simply cannot do the "right thing" under all circumstances. Having gone through the exercise, I can assure you that alloca() is not a good idea in C as it exists. Some similar functionality might be useful in a new programming language design (not C). In writing many hundreds of thousands of lines of C source code, I've never felt a strong enough need for alloca() to cause me to use it. Normally when I dynamically allocate storage, it needs to hang around after the scope of the function in which it was allocated terminates. When it doesn't, normally automatic variables suffice. The few remaining instances aren't a great deal of trouble and I use malloc()/free() for those.
ka@june.cs.washington.edu (Kenneth Almquist) (04/24/89)
les@chinet.chi.il.us (Leslie Mikesell) writes: > There are two situations which are helped by the use of alloca(): > 1) dividing the dynamically allocated space into reasonably sized chunks > to reduce the time malloc() and free() need to search their lists, and > 2) providing the ability to longjmp() out of a function (or just return) > with the no longer needed memory automatically released (just like local > variables). Ash uses a memory allocator with stack-like semantics: struct stackmark smark; /* stack mark saves stack location */ setstackmark(&smark); /* smark = stack pointer */ for (;;) { ... p = stalloc(n); /* allocate space off stack */ ... } /* now free everything allocated by the stalloc calls */ popstackmark(&smark); /* stack pointer = smark */ This is more flexible than alloca because routines can return blocks allocated via stalloc. It solves the problems you mention. (It deals with problem 1 by allocating reasonably large blocks from malloc and doling them out in smaller pieces.) Its main advantage is that it can be implemented reliably on any machine that can support C. Ash will appear in comp.sources.unix next week if you want to steal the code. Kenneth Almquist
kjones@talos.UUCP (Kyle Jones) (04/24/89)
In article <1883@thor.acc.stolaf.edu> mike@mike@stolaf.edu writes: > I'm the author of GNU grep, and I firmly believe that alloca is Evil. > Don't use it in new programs! Why not? So compiler vendors can stop supporting it? Alloca is a very useful function to have on systems that can support it. I believe that it is useful enough that it should be demanded on all systems capable of supporting it. For the others, I can cobble a replacement that uses malloc and put wrappers around setjmp and longjmp calls to free this memory. I've done this before, it's not hard. But using a the alloca where available is a big win in terms of time taken to allocate the memory and programming ease when cleaning up after a longjmp. Why throw alloca away on systems that can support it? It's a simple idea, stupefyingly easy to implement on stack-based machines, and makes a certain class of programming tasks easier.
jfh@rpp386.Dallas.TX.US (John F. Haugh II) (04/24/89)
In article <10090@smoke.BRL.MIL> gwyn@brl.arpa (Doug Gwyn) writes: >There is no situation I know of when use of alloca() is necessary. What about the situations when the use of an automatic variable is necessary? -- John F. Haugh II +-Quote of the Week:------------------- VoiceNet: (214) 250-3311 Data: -6272 | "When everyone else complies InterNet: jfh@rpp386.Dallas.TX.US | I will too ..." UucpNet : <backbone>!killer!rpp386!jfh +------------------- -- Doug Davis --
flee@shire.cs.psu.edu (Felix Lee) (04/25/89)
Are there uses of alloca() that can't be handled by variable-length
automatic arrays:
{ int n = 10; { char s[n]; } }
which are allowed by GNU cc?
Are there architectures that will not allow you to implement this?
--
Felix Lee flee@shire.cs.psu.edu *!psuvax1!shire!fleejdc@naucse.UUCP (John Campbell) (04/27/89)
From article <11344@tekecs.GWD.TEK.COM>, by andrew@frip.wv.tek.com (Andrew Klossner): >> Are there architectures that will not allow you to implement this? (alloca) > No, with compiler assist you can always implement it; but its > complexity can approach that of marking all mallocs and teaching the > compiler (and longjmp) to call un_malloc_temporaries on each procedure > return. Ah, but that's the rub. What if you already have your compiler. In other words, what if you know of some nice useful software that *someone* sprinkled alloca's in AND you have some silly vendor supplied C compiler. In one case (at least) you'll have to write a stack manipulator (not in 'C') and even compile without optimizing. Often, it turns out, you'll find (with the vendor's compiler) that you're better off rewriting the offending section in order to turn optimize back on. I don't remember alloca() making it to the ANSI standard library. I hereby request that only those who write *useless* code use alloca()! :-) -- John Campbell ...!arizona!naucse!jdc CAMPBELL@NAUVAX.bitnet unix? Sure send me a dozen, all different colors.
dag@per2.UUCP (Daniel A. Glasser) (04/29/89)
In article <1381@naucse.UUCP>, jdc@naucse.UUCP (John Campbell) writes: > I don't remember alloca() making it to the ANSI standard library. I hereby > request that only those who write *useless* code use alloca()! :-) Here here! The standard does not have alloca() anywhere in it. The rationale document does mention the omission in 4.10.3 -- (quoted without permission) Some implementations provide a function (often called alloca) which allocates the requested object from automatic storage; the object is automatically freed when the calling function exits. _S_u_c_h _a _f_u_n_c_t_i_o_n _i_s _n_o_t _e_f_f_i_c_i_e_n_t_l_y _i_m_p_l_e_m_e_n_t_a_b_l_e _i_n _a _v_a_r_i_e_t_y _o_f _e_n_v_i_r_o_n_m_e_n_t_s_, _s_o _i_t _w_a_s _n_o_t _a_d_o_p_t_e_d _i_n _t_h_e _S_t_a_n_d_a_r_d. -- _____________________________________________________________________________ Daniel A. Glasser One of those things that goes uwvax!per2!dag "BUMP!!!(ouch)" in the night. ---Persoft, Inc.---------465 Science Drive-------Madison, WI 53711-----------
scs@adam.pika.mit.edu (Steve Summit) (04/29/89)
In article <8261@chinet.chi.il.us> les@chinet.chi.il.us (Leslie Mikesell) writes: %In article <10090@smoke.BRL.MIL> gwyn@brl.arpa (Doug Gwyn) writes: %>[earlier posters wrote:] %>>>To repeat: alloca is EVIL. %>>It doesn't have to be. %>There is no situation I know of when use of alloca() is necessary. %There are two situations which are helped by the use of alloca(): %... %2) providing the ability to longjmp() out of a function (or just return) %with the no longer needed memory automatically released longjmp is evil.
gwyn@smoke.BRL.MIL (Doug Gwyn) (04/29/89)
In article <10939@bloom-beacon.MIT.EDU> scs@adam.pika.mit.edu (Steve Summit) writes: >longjmp is evil. Well, at least it's worse than "goto". Some people have found reasonable (albeit obscure) uses for longjmp. I don't use it myself.
les@chinet.chi.il.us (Leslie Mikesell) (05/02/89)
In article <10177@smoke.BRL.MIL> gwyn@brl.arpa (Doug Gwyn) writes: >>longjmp is evil. >Well, at least it's worse than "goto". >Some people have found reasonable (albeit obscure) uses for longjmp. >I don't use it myself. Here is a use: A print spooler output process accepts commands to print files on a pipe from its parent (the scheduler). An interactive control program can cause the scheduler to send signals to the output process. One signal causes the current job to be restarted from the beginning, another causes the current job to be discarded and the next command to be read from the input pipe. There are many sub-functions involved in the output process. Using longjmp() out of the signal handler allows rapid response from anywhere in the program doing only the clean-up needed for the current state. Is there any other way to handle a situation like this? Testing a global variable set in the signal handler at all the appropriate places would add quite a bit of overhead. Les Mikesell
jdickson@spanza.jpl.nasa.gov (Jeff Dickson) (05/04/89)
I agree with Root Boy. I use alloca() exclusively on Sun O.S. 4.0 to set aside a large chunk of space in which to do my own memory allocation -deallocation out of. I first tried to use malloc/free, but had chronic prob- lems with it. It wasn't so much that those calls failed, it was that they failed and/or caused other unexplainable problems when they were called many times a second. My code doesn't use much memory, but it does do many allocations and deallocations per second. I have found however, that I can do essentially the same thing as alloca() by declaring a large automatic array of character. In that respect, it isn't totally necessary that I use alloca(). I really don't understand what the big fuss over alloca() is. So what that it does some weird things to the code. At least IT works. But then again, my code may not use it in the insane sense that others are refering to. My code does not call it often. In fact, I largely call it in the beginning of the process. jdickson@zook.jpl.nasa.gov
clive@ixi.UUCP (Clive) (05/05/89)
I don't know where all this alloca stuff came from, but BCPL had a
nice function (I forget the name, but let's call it stack_malloc for now)
which called another function with an array of specified size on
the stack - thus when you left this function (*however* you did,
including longjumps), the array went away.
Translating to C, the definition would be something like:
int stack_malloc (f, n)
int (*f) (/* char [], int */);
int n;
{
/* The body of this function is equivalent to the
(illegal) code:
char a [n]; /* This is illegal */
return (*f) (a, n);
}
[BCPL was typeless - it was much less painful]
The library code for this would do something like:
(assume args in r1 and r2, and ascending stack)
r3 = r1
r1 = sp
sp += r2
block copy the stack frame at fp (the one generated
by the call) up by r2
fp += r2
/* the 'sp just before call' field in the frame is unaltered */
jump @r3
I forget the return sequence used on this system, but this had the
right effect - the array was effectively in the caller's stack frame,
but when they returned, the sp had dropped down past it.
--
Clive D.W. Feather clive@ixi.uucp
IXI Limited ...!mcvax!ukc!acorn!ixi!clive (untested)
+44 223 462 131