Why does `alloca` not check if it can allocate memory?

Question

Why does alloca not check if it can allocate memory?

From man 3 alloca:

If the allocation causes stack overflow, program behavior is undefined. … There is no error indication if the stack frame cannot be extended.

Why alloca does not / can not check if it can allocate more memory?

The way I understand it alloca allocates memory on stack while (s)brk allocates memory on the heap. From https://en.wikipedia.org/wiki/Data_segment#Heap :

The heap area is managed by malloc, calloc, realloc, and free, which may use the brk and sbrk system calls to adjust its size

From man 3 alloca:

The alloca() function allocates size bytes of space in the stack frame of the caller.

And the stack and heap are growing in the converging directions, as shown in this Wikipedia graph:

(The above image is from Wikimedia Commons by Dougct released under CC BY-SA 3.0)

Now both alloca and (s)brk return a pointer to the beginning of the newly allocated memory, which implies they must both know where does the stack / heap end at the current moment. Indeed, from man 2 sbrk:

Calling sbrk() with an increment of 0 can be used to find the current location of the program break.

So, they way I understand it, checking if alloca can allocate the required memory essentially boils down to checking if there is enough space between the current end of the stack and the current end of the heap. If allocating the required memory on the stack would make the stack reach the heap, then allocation fails; otherwise, it succeeds.

So, why can't such a code be used to check if alloca can allocate memory?

void *safe_alloca(size_t size)
{
    if(alloca(0) - sbrk(0) < size) {
        errno = ENOMEM;
        return (void *)-1;
    } else {
        return alloca(size);
    }
}

This is even more confusing for me since apparently (s)brk can do such checks. From man 2 sbrk:

brk() sets the end of the data segment to the value specified by addr, when that value is reasonable, the system has enough memory, and the process does not exceed its maximum data size (see setrlimit(2)).

So if (s)brk can do such checks, then why can't alloca?

Answer 1

alloca is a non-standard compiler intrinsic whose selling point is that it compiles to extremely lightweight code, possibly even a single instruction. It basically does the operation performed at the beginning of every function with local variables - move the stack pointer register by the specified amount and return the new value. Unlike sbrk, alloca is entirely in userspace and has no way of knowing how much stack is left available.

The image of stack growing towards the heap is a useful mental model for learning the basics of memory management, but it is not really accurate on modern systems:

• As cmaster explained in his answer, the stack size will be primarily limited by the limit enforced by the kernel, not by the stack literally colliding into the heap, especially on a 64-bit system.
• In a multi-threaded processes, there is not one stack, but one for each thread, and they clearly cannot all grow towards the heap.
• The heap itself is not contiguous. Modern malloc implementations use multiple arenas to improve concurrent performance, and offload large allocations to anonymous mmap, ensuring that free returns them to the OS. The latter are also outside the single-arena "heap" as traditionally depicted.

It is possible to imagine a version of alloca that queries this information from the OS and returns a proper error condition, but then its performance edge would be lost, quite possibly even compared to malloc (which only occasionally needs to go to the OS to grab more memory for the process, and usually works in user-space).

Answer 2

The picture is a bit outdated: On a modern system, the heap memory regions and the memory region that contains the call stack are entirely separate entities, and they are very far apart on a 64 bit system. The concept of the memory break was designed for systems with small address spaces.

As such, the limitation for the stack space is not that it may grow into the top of the heap, the limitation is that the kernel may not have any memory left to back it. Or the kernel may decide that your stack has grown too much (some limit is reached), and thus shoots down your process.

Your process grows the stack simply by decrementing the stack pointer, and storing some data there. If that memory access is currently not mapped into your address space, the hardware immediately signals this condition to the OS kernel, which checks where the failed memory access occurred, and if that is just below the stack memory region, it will immediately expand that memory mapping, map a new page of memory there, and give control back to your process to retry its memory access. The process does not see any of this. It just sees that its access to stack memory succeeded.

alloca() does not deviate from this in any way: You ask it to allocate some memory on the stack, and it does so by decrementing the stack pointer accordingly. However, if your allocation is so large that the OS does not see memory accesses to it as valid stack memory accesses, it will (likely and hopefully) kill your process with a SEGFAULT. However, since the behavior is undefined, anything may happen.