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

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.

Such activations of subroutines may be nested to any level (recursive as a special case), hence the stack structure.

The actual details of the stack in a programming language depend upon the compiler, operating system, and the available instruction set.

Depending on the language, operating system, and machine environment, a call stack may serve additional purposes, including, for example:

These are machine dependent and ABI-dependent data structures containing subroutine state information.

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.

Some architectures, compilers, or optimization cases store one link for each enclosing level (not just the immediately enclosing), so that deeply nested routines that access shallow data do not have to traverse several links; this strategy is often called a "display".

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 (such as the ubiquitous x86) simply reserve a few words on the stack for the pointers, as needed.

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.

Under this approach, the size of the area is calculated by the compiler to be the largest needed by any called subroutine.

The actual call instruction, such as "branch and link", is then typically executed to transfer control to the code of the target subroutine.

The Scheme programming language allows arbitrary thunks to be executed in specified points on "unwinding" or "rewinding" of the control stack when a continuation is invoked.

Depending on how the program is written and compiled, the information on the stack can be used to determine intermediate values and function call traces.

This has been used to generate fine-grained automated tests,[4] and in cases like Ruby and Smalltalk, to implement first-class continuations.

As an example, the GNU Debugger (GDB) implements interactive inspection of the call stack of a running, but paused, C program.

[5] Taking regular-time samples of the call stack can be useful in profiling the performance of programs as, if a subroutine's address appears in the call stack sampling data many times, it is likely to act as a code bottleneck and should be inspected for performance problems.

In a language with free pointers or non-checked array writes (such as in C), the mixing of control flow data which affects the execution of code (the return addresses or the saved frame pointers) and simple program data (parameters or return values) in a call stack is a security risk, and is possibly exploitable through stack buffer overflows, which are the most common type of buffer overflow.

Various mitigations have been proposed, such as storing arrays in a completely separate location from the return stack, as is the case in the Forth programming language.