Alloca implementation

Alloca implementation

How does one implement alloca() using inline x86 assembler in languages like D, C, and C++? I want to create a slightly modified version of it, but first I need to know how the standard version is implemented. Reading the disassembly from compilers doesn't help because they perform so many optimizations, and I just want the canonical form.

Edit: I guess the hard part is that I want this to have normal function call syntax, i.e. using a naked function or something, make it look like the normal alloca().

Edit # 2: Ah, what the heck, you can assume that we're not omitting the frame pointer.

Answer by Paul Betts for Alloca implementation

Alloca is easy, you just move the stack pointer up; then generate all the read/writes to point to this new block

sub esp, 4  

Answer by Brian Knoblauch for Alloca implementation

I recommend the "enter" instruction. Available on 286 and newer processors (may have been available on the 186 as well, I can't remember offhand, but those weren't widely available anyways).

Answer by newgre for Alloca implementation

alloca is directly implemented in assembly code. That's because you cannot control stack layout directly from high level languages.

Also note that most implementation will perform some additional optimization like aligning the stack for performance reasons. The standard way of allocating stack space on X86 looks like this:

sub esp, XXX  

Whereas XXX is the number of bytes to allcoate

Edit:
If you want to look at the implementation (and you're using MSVC) see alloca16.asm and chkstk.asm.
The code in the first file basically aligns the desired allocation size to a 16 byte boundary. Code in the 2nd file actually walks all pages which would belong to the new stack area and touches them. This will possibly trigger PAGE_GAURD exceptions which are used by the OS to grow the stack.

Answer by Michael Burr for Alloca implementation

It would be tricky to do this - in fact, unless you have enough control over the compiler's code generation it cannot be done entirely safely. Your routine would have to manipulate the stack, such that when it returned everything was cleaned, but the stack pointer remained in such a position that the block of memory remained in that place.

The problem is that unless you can inform the compiler that the stack pointer is has been modified across your function call, it may well decide that it can continue to refer to other locals (or whatever) through the stack pointer - but the offsets will be incorrect.

Answer by Evan Teran for Alloca implementation

implementing alloca actually requires compiler assistance. A few people here are saying it's as easy as:

sub esp,   

which is unfortunately only half of the picture. Yes that would "allocate space on the stack" but there are a couple of gotchas.

1. if the compiler had emitted code which references other variables relative to esp instead of ebp (typical if you compile with no frame pointer). Then those references need to be adjusted. Even with frame pointers, compilers do this sometimes.

2. more importantly, by definition, space allocated with alloca must be "freed" when the function exits.

The big one is point #2. Because you need the compiler to emit code to symmetrically add to esp at every exit point of the function.

The most likely case is the compiler offers some intrinsics which allow library writers to ask the compiler for the help needed.

EDIT:

In fact, in glibc (GNU's implementation of libc). The implementation of alloca is simply this:

#ifdef  __GNUC__  # define __alloca(size) __builtin_alloca (size)