Stack frame
In computer science, a stack frame is a trivial memory management strategy that supports recursive subroutines. Programs which utilize a stack frame build a stack which grows with each function invocation, and which contains space for actual parameters, local variables, temporary locations, and information about the calling context. Typically, a stack frame is built using primitive stack manipulation instructions that are available on many modern processors. Stack frames are usually implemented automatically by the language's compiler.
Principles of Operation
To use a stack frame, a program keeps two pointers, often called the Stack Pointer (SP), and the Frame (FP) or Base Pointer (BP). SP always points to the "top" of the stack, and FP always points to the "top" of the frame. Additionally, the processor also maintains a program counter (PC) which points to the next instruction to be executed. Then, whenever a function call takes place, the following steps take place in roughly this order:
- The caller saves local variables and temporaries, by pushing them onto the stack.
- The caller pushes the callee's actual parameters onto the stack.
- The caller branches to the callee, pushing PC onto the stack (on most architectures, this is a single instruction called CALL). When on the stack, the saved PC is called the return address.
- The callee pushes the value of FP onto the stack.
- The callee copies SP to FP.
- The callee adjusts SP, creating storage locations for local variables and local temporaries on the stack.
Steps 4--6 above are referred to as the function prologue, since they are the beginning of every function.
Within the body of the callee function, formal parameters and local variables can all be accessed at an address relative to the frame pointer. Because of this, a function may recurse, and automatically create a different storage location for each of its local variables.
Upon exit from the function, those steps are performed in reverse:
- The callee restores SP, and in doing so destroys the storage locations reserved for locals and temporaries.
- The callee restores FP, and in doing so returns to the previous frame.
- The callee branches back to caller by popping PC off of the stack (on most architectures, this is a single instruction called RETURN).
- The caller removes the actual parameters from the stack.
- The caller resotres local variables and temporaries, by popping them from the stack.
Steps 1--3 are referred to as the function epilogue, since they are at the end of every function.
Depending on the Application Binary Interface (ABI) of the particular architecture and platform, these steps may be performed in slightly different order. For instance, some systems will save temporaries in two groups---those saved by the caller, and those by the callee. Similarly, on some platforms, the program counter may be saved onto a different stack. Many other variants are possible.
Another notable variant of the stack frame is the use of canary values to thwart buffer overflow attacks.
Limitations
Stack frames are not the most efficient way to manage short-lived values, such as formal parameters, local variables, and intermediate computations. On architectures that support it, it is faster to store these in registers than in memory locations. Unfortunately, this approach is often limited by separate compilation.
Stack frames assume that the lifetime of variables is delimited by the function which declares them, which is to say that after a function has returned, its local variables no longer exist. This is not the case for languages which support closures. For instance, in the C programming language,
int *badFunction(void)
{
int localVar = 4;
return &localVar;
}
Can produce undefined results, since it returns a pointer to a memory location that will be reused by other functions. After a few function calls, it is unlikely that the return value will point to the integer 4. It may seem like other high-level languages, such as Java programming language Java or C#, allow this, but they do not; their local variables are actually pointers to objects, and so one can return the object, but cannot return a pointer to the local variable.
However, some languages, such as Ruby or Standard ML support closures. In Ruby, this example
def goodFcn()
i = 4
return Proc { return i }
end
Returns a closure that can access the local variable i, even after goodFcn() has terminated. As a result, languages such as these must employ more memory management infrastructure than a stack frame.
Security and "Stack Smashing" Attacks
Main Article: buffer overflow attack
A stack smashing attack is a special case of a buffer overflow attack. Stack smashing attacks take advantage of the stack frame by assuming two things:
- Both program data (variables) and control flow information (saved program counter) are stored on the stack, and
- The stack grows from high memory addresses towards low memory addresses (this is the case on many, if not most, architectures). In other words, when data is copied to sequential, increasing addresses, it will eventuall reach control flow information on the stack.
Because of this, it is sometimes possible to craft a special input which will trick a poorly written program into voluntarily overwriting its control flow information, thus taking control of the executing program. This is of particular importance in machines which provide services over a network.