Does a stack allocate more space if needed or does it overflow?

Question

For x86 assembly, let's say we have a stack like so

The stack has 2 words allocated for the 2 local variables it has. But what if you forcibly push a third local variable to the stack. Does the ESP move upwards to make room for the variable or does the variable override the ESP?

Answer 1

See @Eric's answer for most of the details.

Not only are some OSes lazy about actually mapping the whole reserved stack region to physical pages right away, some don't even logically map it at all. e.g. on Linux the size of the stack mapping in /proc/self/maps is smaller than the ulimit -s value. But touching memory in that region will cause the kernel to extend the mapping (up to that size limit), even if it's far below the end of the current mapping.

This is separate from the usual lazy mapping where all pages of a newly allocated mmap(MAP_ANONYMOUS) region are copy-on-write mapped to the same physical page (of all zeros). So reading new pages can give you a TLB miss (to walk the page table for that virtual address) and an L1D cache hit (because the physical address is the same for all the still-written pages)¹.

On other OSes (like Windows I think), you can't go too far in one jump; the kernel's page-fault handler will only map new stack memory for you if the access is within a couple pages of the lowest-address page that's currently mapped. (It may also check that ESP / RSP is below the faulting address). If either of these checks fail, the page-fault results in an exception for your program, rather than being handled by silently mapping that page and re-running the load or store instruction.

This means that allocating space for a large array on the stack has to probe the stack every page or so, on OSes that require it. Microsoft's documentation for their visual studio compiler has some info on the details: the /Gs option defaults to /Gs4096: probe at least once every 4k when growing the stack by a large amount, or for a variable-sized array that could be that big.

A "probe" is nothing special, just a load or store to a stack address to trigger the page fault if the page wasn't allocated yet, so the stack grows one page at a time instead of faulting.

---

Footnote:

1. malloc and calloc use mmap, and calloc knows about mmap giving it zeroed pages, so it doesn't redo the zeroing when it got fresh memory from the kernel.

   But C++ std::vector is too dumb (in gcc and clang, with libc++ or libstdc++), and does dirty all the new memory itself even for large allocations where new ultimately calls mmap. C++'s replaceable-new means that compilers / libraries could only optimize this with -fwhole-program or link-time optimization, but in theory it's possible. Since in practice it doesn't happen, use a custom allocator or avoid std::vector if this behaviour is useful (e.g. a large sparse allocation where you only write part of it).

Answer 2

With x86, instructions that “push” data to the stack also modify the stack pointer (%esp in this case) to mark the new top of stack. Instructions that “pop” data modify the stack pointer in the opposite direction.

On machines without special push and pop instructions, the program must first modify the stack pointer and then store data to the stack.

Generally, a large area is reserved for the stack. The stack pointer merely marks the portion that is currently in use. A program is free to move the stack pointer up and down as it needs to.

The area reserved for the stack may depend on the operating system and/or the developer tools. For example, on macOS with Apple’s developer tools, the default stack size is eight mebibytes and may be changed with the “-stack_size size” switch to the linker (the ld command). (This is for the main stack. A program that uses multiple threads has an additional stack for each created thread. The stack size for these is set separately.)

Although a large area of virtual address space is reserved for the stack, an operating system might not map it all to physical memory as soon as a program starts. An operating system might map just a portion of it and then map more portions as the stack grows into the area.

Typically, some portion of virtual address space beyond the stack is kept unmapped, so that attempts to access it will cause exceptions. The address space pages in this area are called guard pages. Thus, if a program grows the stack beyond the reserved area and tries to write a value to the unmapped guard page, an exception will occur, and the system will report a stack overflow.

Nothing prevents a program from writing into the area reserved for the stack but slightly beyond the stack pointer. This would be a bug, but it generally is not detected by hardware. Furthermore, a program that does this may operate normally for a while; it can store data to this area and load it back as expected. However, there are additional things happening in your process that you are normally unaware of. For example, a signal may be delivered to your process. When this happens, the system interrupts regular processing of your program, pushes new data onto the stack, and calls a signal handler routine. When the routine returns, the data is removed from the stack, and your program resumes normal execution. However, if your program had stored data beyond the stack pointer, that data is now gone, since it was overwritten by the data for the signal handler. Thus, a program that stores data beyond the stack pointer may seem to work most of the time but fail on rare circumstances when a signal arrives at the wrong moment.

(On some systems, the safe area of stack is actually a fixed distance beyond the address in the stack pointer, instead of exactly at that address. This extra safe space may be called a “red zone.”)