Overview

When a program is started by the operating system, a fixed block of memory is allocated in system memory for the program stack.

The program stack is also known as the call stack.

Call Stack

The portion of the stack allocated for a single function call is called a stack frame.

The stack behaves like a Last In, First Out (LIFO) queue.

When a function is called, a new frame is pushed onto the stack.

When the function returns, the frame is popped from the stack.

The calling convention of a function determine what is pushed on the stack, and in what order.

The stack contains:

• The return address of the calling function (to resume execution of the program when a function returns).

• The values of certain CPU registers (to restore their values if they are overridden by a function call).

• The values of local variables (some local variables are stored in CPU registers).

The current position on the stack is determined by the stack pointer.

The direction in which the stack grows depends on the processor architecture.

In the Intel x86 architecture, the stack grows down.

Therefore, when memory is allocated on the stack (push), the stack pointer decreases; and when memory is freed from the stack (pop), the stack pointer increases.

Registers

The stack frame is managed by two CPU registers: the stack pointer and the base pointer.

The base pointer points to the bottom of the stack frame (BSP on Intel x86).

The stack pointer points to the top of the stack frame (ESP on Intel x86).

When a function is called, we need to save the current position on the stack, to allow the program to resume execution after the function returns.

When a function is about to be called:

• The base pointer register is pushed onto the stack.

• The stack pointer register is saved into the base pointer register.

pushl %ebp
movl %esp %ebp

When the current function returns:

• The stack pointer register is restored from the base pointer register.

• The base pointer register is popped from the stack.

• The function returns, and the execution resumes in the caller function.

movl %ebp, %esp
popl %ebp
ret

Allocation

It is possible for a program to allocate memory on the stack by changing the value of the stack register.

This is useful for allocating temporary memory efficiently, but the amount of free memory is very limited.

Languages

C and C++

Any type can be allocated on the stack as long as there is enough space.

Additional memory can be allocated on the stack using the _alloca function.

C#

Only value types can be allocated on the stack.

A ref struct can only be allocated on the stack.

A reference type can be allocated on the stack when it is allocated with stackalloc.