Friday, February 07, 2003

Runtime Stack

The runtime stack is an implicit stack that is maintained automatically during program execution; we've alluded to this stack in previous lectures. The basic idea behind the stack is that everytime a function invocation takes place, a new stack frame (sometimes called an activation record) is pushed on the stack. Generally, the following information is pushed on the runtime stack during each function invocation (though different compilers may do things differently for efficiency and performance reasons):

• The return value. When the function has finished executing, the calling code must be able to retrieve the function's return value (if any). This value is typically left on the top of the stack after the function has finished.
• The return address. This is the address of the instruction that control is to return when the function has completed execution. Trashing the stack via a buffer overrun and modifying this return address is a common way to seriously compromise the security of a program.
• The function's parameters. Copies of the function's actual parameters are pushed on the stack.
• The function's (non-static) local variables are also pushed onto the stack. Generally speaking, the compiler automatically takes care of the storage attributes of these variables. As a result, these variables have auto storage.

Global variables

Some variables may be pushed on the runtime stack shortly after the program starts but before the main() function is actually called. Global variables (both static and non-static) are stored on the stack when the program starts. They are popped off the stack only after the program finishes. The lifetime of these variables extends over the lifetime of the entire program. static global variables have the same storage attributes as non-static global variables, but their linkage attributes are internal rather than external (i.e. functions in only one source module can access them). Global variables are initialized to zero.

Local static variables

Local static variables have storage (lifetime) attributes similar to global variables but with much more limited scope. Local static variables (like non-static local variables) can only be accessed inside the functions in which they are defined. static local variables are initialized when the function containing the variable is first executed. They do not get re-initialized each time the function containing them is executed. By default, static local variables are initialized to zero.

Like global variables, space is automatically allocated for local static variables at the very beginning of program execution. (i.e. a local static variable is not pushed onto the stack on each invocation of the function in which it resides). As a result, static local variables retain their values across subsequent invocations of the functions in which they reside. Recursive functions can use local static variables to reduce the amount of information that has to be pushed onto the stack on each invocation. This is particularly true if the value of the variable is constant over each invocation.

Local static variables cannot be used if the function is to be used in a multithreaded program. Some classic C library functions use static local variables (e.g. strtok()) and as a result would have to be made re-entrant if they are used in a multithreaded context.

Example

Consider the following (contrived) example:

#include <stdio.h>

int global = 1;

int func(int formal)
{
	static int	static_local;
	int		local = 0;

	++static_local;
	++local;
	return local * global * formal * static_local;
}

int
main()
{
	int	actual = 2;
	int	ret_value;
	
	ret_value = func(actual);
	++global;
	++actual;
	ret_value = func(actual);

	return 0;
}

Initially, the global variable and static local variable are pushed on the stack and initialized (either explicitly or implicitly). Note that space is made for static_local even though the function it resides in hasn't even been called yet. Also note that this variable is implicitly initialized to zero (unlike regular local variables, which must be initialized explicitly).

When the main() function is called room is allocated on the stack for main()'s return value and main()'s local variables are pushed on the stack:

Now, when we call func() for the first time, we make room on the stack for its return value and push the return address on the stack (in this case, the return address would be the address of the instruction that assigns the result of the function to the ret_value variable). Then we copy and push the function's formal parameter on the stack. Finally the function's local variable is pushed on the stack:

After performing the two preincrements, the runtime stack will have the following values:

When the return statement is executed, the stack frame is popped and control jumps to the return address on the stack, giving us:

The assignment of ret_value to the return value of the function is then performed by popping the return value off the stack. The global and actual variables are then incremented, giving us the stack:

We then call the function again, pushing the appropriate values and addresses on the stack as before.

Just prior to executing the return statement, the stack will look as follows:

Note that static_local had retained its value from the last invocation of the function. After we return from the function, the stack has the following values:

Again, ret_value is then assigned the return value of the function by popping the stack, main() then finishes by returning zero which is eventually returned to the operating system as the remainder of the runtime stack is deallocated.

Note that there are some simplifications made in the above example, but the general idea should be clear.

Dangling pointers

A dangling pointer is a pointer that points to a memory location that was once valid but is now bogus. For example, consider the following invalid C program:

int	*p;

void func1() 
{
	int	a = 0;
	p = &a;
}

void func2() 
{
	int	b = 1;
}

main()
{
	func1();
	printf ("%d\n", *p);
	func2();
	printf ("%d\n", *p);
}

The p pointer pointed to a location on the runtime stack that is no longer valid when func1() ends. When func2() executes, p (may) just happen to point to the part of the runtime stack now occupied by func2()'s local variable b.

Last modified: Fri Feb 7 15:32:54 2003