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 unnecessary, 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 accommodate 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 from 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

The most important difference between alloca and VLAs is the failure case. The following code:

int f(int n) {
    int array[n];
    return array == 0;
}
int g(int n) {
    int *array = alloca(n);
    return array == 0;
}

The VLA has no possibility of detecting an allocation failure; which is a very un-C thing to impose on a language construct. Alloca() is thus much better designed.