gbadev.org forum archive

This is a read-only mirror of the content originally found on forum.gbadev.org (now offline), salvaged from Wayback machine copies. A new forum can be found here.

DS development > alloca()

#156682 - simonjhall - Mon May 12, 2008 7:12 pm

I discovered the amazingness that is alloca() recently - it's great! I can't believe I'd never used (nor heard of) this function before.
For those who don't know, it's used for creating variable-sized arrays on the stack, not the heap. When the function returns, the compiler automatically frees the memory. Useful on targets where you don't have a new or malloc.
_________________
Big thanks to everyone who donated for Quake2

#156690 - tepples - Mon May 12, 2008 8:35 pm


As I understand it, malloc() is ISO C, while alloca() is a BSD innovation. So wouldn't malloc() work on more systems than alloca()?
_________________
-- Where is he?
-- Who?
-- You know, the human.
-- I think he moved to Tilwick.

#156695 - simonjhall - Mon May 12, 2008 9:16 pm

Ah good stuff. From the disadvantages page I don't really follow: you don't get a clean error message? Does that mean that it doesn't return a NULL pointer if there's insufficient memory? I guess you just get a pointer into some place which looks stack-y but it may be further into the stack than you're allowed to go...

Also I don't get it how you can have a library emulation of the function - when a function finishes, how does the memory get freed? Does the compiler automatically call the appropriate memory free function?

And you're right, alloca seems to live in non-standard places. For instance on Visual C++ (.NET 2003 at least) it's in malloc.h but on the GCC I tried earlier it's in alloca.h (which then goes to __builtin_alloca()).

/ot: just watched Dispatches on Channel 4 all about anti-aging creams. One of the women inteviewed was named "Newby Hands" - wow. Just wow. Seriously.
_________________
Big thanks to everyone who donated for Quake2

#156698 - Quirky - Mon May 12, 2008 9:26 pm

As in "Get your Newby Hands off my code"?

Also alloca: nice! I hadn't heard of it before. The DS has a pretty small stack, so care must be taken there, right? Statically allocating big things on the stack tends to crap out in a very ugly way, I guess this would do the same.

#156701 - kusma - Mon May 12, 2008 10:19 pm

simon, first you must understand what alloca IS - it's a subtraction on the stack-pointer. Since you usually have no knowledge of where the stack ends (in theory it often doesn't), there's no way of checking that the memory isn't there.

On the other side, malloc() doesn't really return NULL when out of memory on modern computers (note: this does not include the NDS or the GBA) - it only does so when it runs out of address-room. Thank god for visualization.

The stack-pointer is usually pushed when entering a function, and popped when leaving. This means that there's no need to free any memory, since it's returned automatically.

And yes, alloca is a neat function, but I don't really find too many real usecases for it reality.

#156703 - DekuTree64 - Mon May 12, 2008 10:36 pm

kusma wrote:
The stack-pointer is usually pushed when entering a function, and popped when leaving. This means that there's no need to free any memory, since it's returned automatically.

Pushed onto what, itself? The allocation sizes or previous stack pointer would have to be kept track of somewhere. It would also affect how normal stack variables are accessed, since they normally use constant offsets from the stack pointer. Especially tricky in thumb code, where there are special instructions for stack-relative access, so you can't just copy the original stack to another register and use that.

Maybe I'll do some disassembly testing on it later to see what actually happens.
_________________
___________
The best optimization is to do nothing at all.
Therefore a fully optimized program doesn't exist.
-Deku

#156704 - simonjhall - Mon May 12, 2008 10:45 pm

kusma wrote:
simon, first you must understand what alloca IS - it's a subtraction on the stack-pointer. Since you usually have no knowledge of where the stack ends (in theory it often doesn't), there's no way of checking that the memory isn't there.
Yeah that's what I had thought!
Thing is though, compilers can add in run-time checking of the stack pointer (gcc has an -fstack-check option as well as -fstack-limit-* stuff) so I had imagined that somehow it'd pull a null pointer out if it ran out of room :-)

As you say though, it may not be too useful. However I'll see if I can find some use for it on my baby at work though...

@DekuTree64
I found this gem of a function in the awesome book "See MIPS run" and it implemented the function through a combination of two pointers/registers, sp and fp. Normal usage of the stack would just use sp but when you drop a variable-sized stack frame into the mix (via alloca) it'd use the two registers to do work within the function.

I don't have the book with me so can't divulge further.
(God knows what happens on x86)

EDIT: so what DOES happen with compilers that don't support alloca() and it's done through a library that (presumably) uses malloc()?
_________________
Big thanks to everyone who donated for Quake2

#156705 - kusma - Mon May 12, 2008 10:48 pm

DekuTree64 wrote:

Pushed onto what, itself? The allocation sizes or previous stack pointer would have to be kept track of somewhere.

Uhm, good point (I'm quite tired - packing to a company trip (UK) tomorrow morning). What happens with the stack is that a value is subtracted (not pushed, silly me) from the stack to make room for any variables allocated there, and added back again once the function returns. Now, exactly what happens with dynamically allocated stack-space, I'm not entirely sure of (and I suspect it varies among implementations), but I suspect a hidden variable is constructed (most likely on the stack itself), initialized to zero, and added to inside alloca(). Dead code elimination and/or constant folding will make sure that it doesn't cost anything in functions that does not use alloca.

#156722 - Dwedit - Tue May 13, 2008 9:18 am

I bet some abuse of setjump and longjump could simulate destruction of alloca'ed memory in C.
edit: no it can't... Gotta stop posting at 3:21 AM...
_________________
"We are merely sprites that dance at the beck and call of our button pressing overlord."

#156801 - tepples - Wed May 14, 2008 12:32 am

simonjhall wrote:
Also I don't get it how you can have a library emulation of the function - when a function finishes, how does the memory get freed? Does the compiler automatically call the appropriate memory free function?

Bison approximates it something like this:
  1. Detect where on the stack the alloca() was called.
  2. Collect garbage: free() all alloca()tions that were done with a stack taller than this one.
  3. malloc() the memory.
  4. Keep track of the allocated block along with where on the stack this alloca() was performed.

kusma wrote:
Since you usually have no knowledge of where the stack ends (in theory it often doesn't), there's no way of checking that the memory isn't there.

In many cases, the linker emits a symbol indicating the start of the section intended as the stack. Couldn't alloca() have been designed to compare the stack pointer to this address? I would bet that some implementations do, as simonjhall hinted with the comment about -fstack-check.

kusma wrote:
On the other side, malloc() doesn't really return NULL when out of memory on modern computers (note: this does not include the NDS or the GBA) - it only does so when it runs out of address-room.

Even worse, sometimes it succeeds and then your program crashes when it tries to write to the memory (see "Moral #2" on this page).

DekuTree64 wrote:
It would also affect how normal stack variables are accessed, since they normally use constant offsets from the stack pointer.

Apparently, functions that call alloca() need to use a separate register to hold the old stack pointer, called the "frame pointer".

It appears that alloca() is designed to fit into the C mindset, which has no built-in concept of destructors. It gets much tricker with non-POD types in C++ because you have to make sure that a class's constructor and destructor (or struct's conclassor and declassor[1]) get called somehow.


[1] Pun.
_________________
-- Where is he?
-- Who?
-- You know, the human.
-- I think he moved to Tilwick.

#156822 - simonjhall - Wed May 14, 2008 7:47 am

tepples wrote:
[1] Pun.
LOL - I got it at least.
_________________
Big thanks to everyone who donated for Quake2

#156828 - keldon - Wed May 14, 2008 12:17 pm

Close ...

Code:
#define kalloca(varname,type) \
    char varname ## _alloca [sizeof(type)]; \
   type &varname = *(type*) varname ## _alloca

int main (void)
{
   typedef int myarray[10];
   
   kalloca (myvar, myarray);
   
   return 0;
}