A call stack is often used for several related purposes, but the main reason for having one is to keep track of the point to which each active subroutine should return control when it finishes executing. (The active subroutines are those which have been called but have not yet completed execution by returning.) If, for example, a subroutine
DrawSquare calls a subroutine
DrawLine from four different places, the code of
DrawLine must have a way of knowing where to return. This is typically done by code for each call within
DrawSquare putting the address of the instruction after the particular call statement (the "return address") onto the call stack.
Since the call stack is organized as a stack, the caller pushes the return address onto the stack, and the called subroutine, when it finishes, pops the return address off the call stack (and transfers control to that address). If a called subroutine calls on to yet another subroutine, it will push its return address onto the call stack, and so on, with the information stacking up and unstacking as the program dictates. If the pushing consumes all of the space allocated for the call stack, an error called a stack overflow occurs. Adding a subroutine's entry to the call stack is sometimes called winding; conversely, removing entries is unwinding.
There is usually exactly one call stack associated with a running program (or more accurately, with each task or thread of a process), although additional stacks may be created for signal handling or cooperative multitasking (as with setcontext). Since there is only one in this important context, it can be referred to as the stack (implicitly, "of the task").
In high-level programming languages, the specifics of the call stack are usually hidden from the programmer. They are given access only to the list of functions, and not the memory on the stack itself. Most assembly languages, on the other hand, require programmers to be involved with manipulating the stack. The actual details of the stack in a programming language depend upon the compiler, operating system, and the available instruction set.
A call stack may serve additional functions, depending on the language, operating system, and machine environment. Among them can be:
The typical call stack is used for the return address, locals, and parameters (known as a call frame). In some environments there may be more or fewer functions assigned to the call stack. In the Forth programming language, for example, only the return address and local variables are stored on the call stack (which in that environment is named the return stack); parameters are stored on a separate data stack. Most Forths also have a third stack for floating point parameters.
DrawLineis currently running, having just been called by a subroutine
DrawSquare, the top part of the call stack might be laid out like this (where the stack is growing towards the top):
The stack frame at the top of the stack is for the currently executing routine. In the most common approach the stack frame includes space for the local variables of the routine, the return address back to the routine's caller, and the parameter values passed into the routine. The stack is often accessed via a register called the stack pointer, which also serves to indicate the current top of the stack. Alternatively, memory within the frame may be accessed via a separate register, often termed the frame pointer, which typically points to some fixed point in the frame structure, such as the location for the return address.
Stack frames are not all the same size. Different subroutines have differing numbers of parameters, so that part of the stack frame will be different for different subroutines, although usually fixed across all activations of a particular subroutine. Similarly, the amount of space needed for local variables will be different for different subroutines. In fact, some languages support dynamic allocations of memory for local variables on the stack, in which case the size of the locals area will vary from activation to activation of a subroutine, and is not known when the subroutine is compiled. In the latter case, access via a frame pointer, rather than via the stack pointer, is usually necessary since the offsets from the stack top to values such as the return address would not be known at compile time.
In many systems a stack frame has a field to contain the previous value of the frame pointer register, the value it had while the caller was executing. For example, in the diagram above, the stack frame of
DrawLine would have a memory location holding the frame pointer value that
DrawSquare uses. The value is saved upon entry to the subroutine and restored for the return. Having such a field in a known location in the stack frame allows code to access each frame successively underneath the currently executing routine's frame.
Programming languages that support nested subroutines have a field in the call frame that points to the call frame of the outer routine that invoked the inner (nested) routine. This is sometimes called a display. This pointer provides the inner routine (as well as any other inner routines it may invoke) access to the parameters and local variables of the outer invoking routine. A few computers, such as the Burroughs large systems, have special "display registers" to support such nested functions.
For some purposes, the stack frame of a subroutine and that of its caller can be considered to overlap, the overlap consisting of the area where the parameters are passed from the caller to the callee. In some environments, the caller pushes each argument onto the stack, thus extending its stack frame, then invokes the callee. In other environments, the caller has a preallocated area at the top of its stack frame to hold the arguments it supplies to other subroutines it calls. This area is sometimes termed the outgoing arguments area or callout area. Under this approach, the size of the area is calculated by the compiler to be the largest needed by any called subroutine.
The prologue will commonly save the return address left in a register by the call instruction by pushing the value onto the call stack. Similarly, the current stack pointer and/or frame pointer values may be pushed. Alternatively, some instruction set architectures automatically provide comparable functionality as part of the action of the call instruction itself, and in such an environment the prologue need not do this.
If frame pointers are being used, the prologue will typically set the new value of the frame pointer register from the stack pointer. Space on the stack for local variables can then be allocated by incrementally changing the stack pointer.
The Forth programming language allows explicit winding of the call stack (called there the "return stack"). The Scheme programming language allows the winding of special frames on the stack through a "dynamic wind".
Some languages (such as Pascal) allow a global goto statement to transfer control out of a nested function and into a previously invoked outer function. This operation requires the stack to be unwound, removing as many stack frames as necessary to restore the proper context to transfer control to the target statement within the enclosing outer function. Such transfers of control are generally used only for error handling.
Other languages (such as Object Pascal) provide exception handling, which also requires unwinding of the stack. The stack frame of a function contains one or more entries specifying exception handlers. When an exception is thrown, the stack is unwound until an exception handler is found that is prepared to handle (catch) the exception. Common Lisp allows control of what happens when the stack is unwound by using the
unwind-protect special operator.
When applying a continuation, the stack is unwound and then rewound with the stack of the continuation. This is not the only way to implement continuations; for example, using multiple, explicit stacks, application of a continuation can simply activate its stack and wind a value to be passed.