How does alloca() work on a memory level?

Question

I'm trying to figure out how alloca() actually works on a memory level. From the linux man page:

The alloca() function allocates size bytes of space in the stack frame of the caller. This temporary space is automatically freed when the function that called alloca() returns to its caller.

Does this mean alloca() will forward the stack pointer by n bytes? Or where exactly is the newly created memory allocated?

And isn't this exactly the same as variable length arrays?

I know the implementation details are probably left to the OS and stuff. But I want to know how in general this is accomplished.

Answer 1

Yes, alloca is functionally equivalent to a local variable length array, i.e. this:

int arr[n];

and this:

int *arr = alloca(n * sizeof(int));

both allocate space for n elements of type int on the stack. The only differences between arr in each case is that 1) one is an actual array and the other is a pointer to the first element of an array, and 2) the array's lifetime ends with its enclosing scope, while the alloca memory's lifetime ends when the function returns. In both cases the array resides on the stack.

As an example, given the following code:

#include <stdio.h>
#include <alloca.h>

void foo(int n)
{
    int a[n];
    int *b=alloca(n*sizeof(int));
    int c[n];
    printf("&a=%p, b=%p, &c=%p\n", (void *)a, (void *)b, (void *)c);
}

int main()
{
    foo(5);
    return 0;
}

When I run this I get:

&a=0x7ffc03af4370, b=0x7ffc03af4340, &c=0x7ffc03af4320

Which shows that the the memory returned from alloca sits between the memory for the two VLAs.

VLAs first appeared in the C standard in C99, but alloca was around well before that. The Linux man page states:

CONFORMING TO

This function is not in POSIX.1-2001.

There is evidence that the alloca() function appeared in 32V, PWB, PWB.2, 3BSD, and 4BSD. There is a man page for it in 4.3BSD. Linux uses the GNU version.

BSD 3 dates back to the late 70's, so alloca was an early nonstandardized attempt at VLAs before they were added to the standard.

Today, unless you're using a compiler that doesn't support VLAs (such as MSVC), there's really no reason to use this function since VLAs are now a standardized way to get the same functionality.

Answer 2

The other answer precisely describes mechanics of VLAs and alloca().

However, there is significant functional difference between alloca() and automatic VLA. The lifetime of the objects.

In case of alloca() the lifetime ends when the function returns. For VLAs the object is released when the containing block ends.

char *a;
int n = 10;
{
  char A[n];
  a = A;
}
// a is no longer valid

{
  a = alloca(n);
}
// is still valid

As result, it is possible to easily exhaust the stack in the loop while it is not possible to do it with VLAs.

for (...) {
  char *x = alloca(1000);
  // x is leaking with each iteration consuming stack
}

vs

for (...) {
  int n = 1000;
  char x[n];
  // x is released
}

Answer 3

Although alloca looks like a function from a syntax point of view, it can't be implemented as a normal function in a modern programming environment*. It must be regarded as a compiler feature with a function-like interface.

Traditionally C compilers maintained two pointer registers, a "stack pointer" and a "frame pointer" (or base pointer). The stack pointer delimits the current extent of the stack. The frame pointer saved the value of the stack pointer on entry to the function and is used to access local variables and to restore the stack pointer on function exit.

Nowadays most compilers do not use a frame pointer by default in normal functions. Modern debug/exception information formats have rendered it unnessacery, but they still understand what it is and can use it where needed.

In particular for functions with alloca or variable length arrays using a frame pointer allows the function to keep track of the location of it's stack frame while dynamically modifying the stack pointer to accomodate the variable length array.

For example I built the following code at O1 for arm

#include <alloca.h>
int bar(void * baz);
void foo(int a) {
    bar(alloca(a));
}

and got (comments mine)

foo(int):
  push {fp, lr}     @ save existing link register and frame pointer
  add fp, sp, #4    @ establish frame pointer for this function
  add r0, r0, #7    @ add 7 to a ...
  bic r0, r0, #7    @ ... and clear the bottom 3 bits, thus rounding a up to the next multiple of 8 for stack alignment 
  sub sp, sp, r0    @ allocate the space on the stack
  mov r0, sp        @ make r0 point to the newly allocated space
  bl bar            @ call bar with the allocated space
  sub sp, fp, #4    @ restore stack pointer and frame pointer 
  pop {fp, pc}      @ restore frame pointer to value at function entry and return.

And yes alloca and variable length arrays are very similar (though as another answer points out not exactly the same). alloca seems to be the older of the two constructoins.

---

* With a sufficiently dumb/predictable compiler it is posible to implement alloca as a function in assembler. Specifically the compiler needs to.

• Consistently create a frame pointer for all functions.
• Consistently use the frame pointer rather than the stack pointer to reference local varaibles.
• Consistently use the stack pointer rather than the frame pointer when setting up parameters for calls to functions.

This is apparently how it was first implemented ( https://www.tuhs.org/cgi-bin/utree.pl?file=32V/usr/src/libc/sys/alloca.s ).

I guess it's possible one could also have the actual implementation as an assembler function, but have a special case in the compiler that made it go into dumb/predictable mode when it saw alloca, I don't know if any compiler vendors did that.

Answer 4

alloca allocates memory which is automatically freed when the function which called alloca returns. That is, memory allocated with alloca is local to a particular function's ``stack frame'' or context.

alloca cannot be written portably, and is difficult to implement on machines without a conventional stack. Its use is problematical (and the obvious implementation on a stack-based machine fails) when its return value is passed directly to another function, as in

fgets(alloca(100), 100, stdin)

You are asking for trouble if you use it anywhere that doesn't fit this description. You are likely to run into trouble if you use alloca() in any of these places, because there might be something on the stack at the point alloca() is called:

• Inside a loop.
• Inside any block that begins with local variables, except the outermost block of a function, especially if the allocated memory is used after exiting this block.
• Using any expression more complicated than a pointer variable on the left hand side of an assignment, including one element of an array of pointers.
• Where the return value of alloca() is used as a function argument.
• In any context where the value of the = operator is used, such as

if ((pointer_variable = alloca(sizeof(struct something))) == NULL) { .... }

And I expect that someone will call me on even THAT highly restrictive limitation not being conservative enough for the code generated by some compilers. Now, if it's done as a compiler builtin, you might manage to get around the problems.

Once I finally got that alloca() function figured out, it worked reasonably well - as I recall, the primary use for it was in a Bison parser. That 128 bytes wasted per invocation combined with a fixed stack size could be a nuisance. Why didn't I just use GCC? Because this was an attempt to port GCC, initially using cross-compilers, to a machine that turned out to barely have enough memory to compile GCC (1.35 or so) natively. When GCC 2 came out, it turned out to be enough of a memory that natively compiling itself was out of the question.