How does alloca() work on a memory level?-CodePudding

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.

CodePudding user response：

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.

CodePudding user response：

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
}

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

CodePudding user response：

Although alloca looks like a function from a syntax point of view, it can't be implemented as a normal function. 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.