Call stack
In computer science, a call stack is a stack data structure that stores information about the active subroutines and inline blocks of a computer program. This type of stack is also known as an execution stack, program stack, control stack, run-time stack, or machine stack, and is often shortened to simply the "stack". Although maintenance of the call stack is important for the proper functioning of most software, the details are normally hidden and automatic in high-level programming languages. Many computer instruction sets provide special instructions for manipulating stacks.
A call stack is 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. An active subroutine is one that has been called, but is yet to complete execution, after which control should be handed back to the point of call. Such activations of subroutines may be nested to any level, hence the stack structure. For example, if a subroutine
DrawSquare calls a subroutine DrawLine from four different places, DrawLine must know where to return when its execution completes. To accomplish this, the address following the instruction that jumps to DrawLine, the return address, is pushed onto the top of the call stack as part of each call.Description
Since the call stack is organized as a stack, the caller of a procedure, or the prologue of that procedure, pushes the return address onto the stack, and the called subroutine, when it finishes, pulls or pops the return address off the call stack and transfers control to that address; similarly, the prologue of an inline block pushes a stack frame and the epilog pops it. If a called subroutine calls on yet another subroutine, it will push another 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, generally causing the program to crash. Adding a block's or subroutine's entry to the call stack is sometimes called "winding", and removing entries "unwinding".There is usually exactly one call stack associated with a running program, although additional stacks may be created for signal handling or cooperative multitasking. Since there is only one in this important context, it can be referred to as the stack ; however, in the Forth programming language the data stack or parameter stack is accessed more explicitly than the call stack and is commonly referred to as the stack.
In high-level programming languages, the specifics of the call stack are usually hidden from the programmer. They are given access only to a set of functions, and not the memory on the stack itself. This is an example of abstraction. Most assembly languages, on the other hand, require programmers to be involved in manipulating the stack. The actual details of the stack in a programming language depend upon the compiler, operating system, and the available instruction set.
Functions of the call stack
As noted above, the primary purpose of a call stack is to store the return addresses. When a subroutine is called, the location of the instruction at which the calling routine can later resume must be saved somewhere. Using a stack to save the return address has important advantages over some alternative calling conventions, such as saving the return address before the beginning of the called subroutine or in some other fixed location. One is that each task can have its own stack, and thus the subroutine can be thread-safe, that is, able to be active simultaneously for different tasks doing different things. Another benefit is that by providing reentrancy, recursion is automatically supported. When a function calls itself recursively, a return address needs to be stored for each activation of the function so that it can later be used to return from the function activation. Stack structures provide this capability automatically.Depending on the language, operating system, and machine environment, a call stack may serve additional purposes, including, for example:
; Local data storage
; Parameter passing
; Evaluation stack
; Enclosing subroutine context
; Enclosed block context
; Other return state
The typical call stack is used for the return address, locals, and parameters. In some environments there may be more or fewer functions assigned to the call stack. In the Forth programming language, for example, ordinarily only the return address, counted loop parameters and indexes, and possibly local variables are stored on the call stack, although any data can be temporarily placed there using special return-stack handling code so long as the needs of calls and returns are respected; parameters are ordinarily stored on a separate data stack or parameter stack, typically called the stack in Forth terminology even though there is a call stack since it is usually accessed more explicitly. Some Forths also have a third stack for floating-point parameters.
Structure
A call stack is composed of stack frames. These are machine dependent and ABI-dependent data structures containing subroutine state information. Each stack frame corresponds to an invocation of a subroutine that has not yet completed with a return. The stack frame at the top of the stack is for the currently executing routine. For example, if a subroutine namedDrawLine is currently running, having been called by a subroutine DrawSquare, the top part of the call stack might be laid out like in the adjacent picture.A diagram like this can be drawn in either direction as long as the placement of the top, and so direction of stack growth, is understood. Architectures differ as to whether call stacks grow towards higher addresses or towards lower addresses, so the logic of any diagram is not dependent on this addressing choice by convention.
While it is actively executing, with its frame at the stack top, a routine can access the information within its frame as needed. The stack frame typically includes at least the following items :
- the arguments passed to the routine on the call stack ;
- the return address back to the routine's caller, if that is saved on the call stack rather than a register; and
- space for the local variables of the routine.
Stack and frame pointers
The locations of all other fields in the frame can be defined relative either to the top of the frame, as negative offsets of the stack pointer, or relative to the top of the frame below, as positive offsets of the frame pointer. The location of the frame pointer itself must inherently be defined as a negative offset of the stack pointer.
Storing the address to the caller's frame
In most 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, the stack frame ofDrawLine would have a memory location holding the frame pointer value that DrawSquare uses. The value is saved upon entry to the subroutine. Having such a field in a known location in the stack frame enables code to access each frame successively underneath the currently executing routine's frame, and also allows the routine to easily restore the frame pointer to the caller's frame, just before it returns.Lexically nested routines
Programming languages that support nested subroutines also have a field in the call frame that points to the stack frame of the latest activation of the procedure that most closely encapsulates the callee, i.e. the immediate scope of the callee. This is called an access link or static link and provides the routine access to the local data of its encapsulating routines at every nesting level. Some architectures, compilers, or optimization cases store one link for each enclosing level, so that deeply nested routines that access shallow data do not have to traverse several links; this strategy is often called a "display".Access links can be optimized away when an inner function does not access any local data in the encapsulation, as is the case with pure functions communicating only via arguments and return values, for example. Some historical computers, such as the Electrologica X8 and somewhat later the Burroughs large systems, had special "display registers" to support nested functions, while compilers for most modern machines simply reserve a few words on the stack for the pointers, as needed.