Call Stack

In computer science, a call stack is a stack data structure that stores information about the active subroutines of a computer program. This kind of stack is also known as an execution stack, program stack, control stack, run-time stack, or machine stack, and is often shortened to just "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.
To accomplish this, the address following the call instruction, the return address, is pushed onto the call stack with each call.

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 (recursive as a special case), hence the stack structure.

Description

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, pulls or pops the return address off the call stack and transfers control to that address.
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 subroutine's entry to the call stack is sometimes called "winding"; conversely, removing entries is "unwinding".

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 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.

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 (address) of the instruction at which the calling routine can later resume needs to be saved somewhere.

Using a stack to save the return address has important advantages over alternative calling conventions. One is that each task can have its own stack, and thus the subroutine can be reentrant, that is, can be active simultaneously for different tasks doing different things. Another benefit is that 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.

Structure

A call stack is composed of stack frames (also called activation records or activation frames). These are machine dependent and ABI-dependent data structures containing subroutine state information. This data is sometimes referred to as CFI (Call Frame Information). Each stack frame corresponds to a call to a subroutine which has not yet terminated with a return.

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. Furthermore, independently of this, architectures differ as to whether call stacks grow towards higher addresses or towards lower addresses.

The stack frame at the top of the stack is for the currently executing routine. The stack frame usually includes at least the following items (in push order):

  • the arguments (parameter values) passed to the routine (if any);
  • the return address back to the routine's caller
  • saved bp
  • space for the local variables of the routine (if any).

Stack and frame pointers

When stack frame sizes can differ, such as between different functions or between invocations of a particular function, popping a frame off the stack does not constitute a fixed decrement of the stack pointer. At function return, the stack pointer is instead restored to the frame pointer, the value of the stack pointer just before the function was called. Each stack frame contains a stack pointer to the top of the frame immediately below.
A frame pointer of a given invocation of a function is a copy of the stack pointer as it was before the function was invoked.

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.

Example

Great visualization how a cdelc (common calling convention) function call works:

results matching ""

    No results matching ""