Page 1 of 1

Everything You Needed To Know About The Stack But Daren't Ask Rate Topic: -----

#1 Martyn.Rae  Icon User is offline

  • The programming dinosaur
  • member icon

Reputation: 540
  • View blog
  • Posts: 1,406
  • Joined: 22-August 09

Posted 07 May 2011 - 03:33 PM

*
POPULAR

Everything You Needed To Know About The Stack But Daren't Ask

Introduction

The stack is a mysterious area of a program that not many developers really understand. This tutorial provides a deeper insight into how the stack is actually used by a program. For the purpose of this tutorial, I am assuming a 32-bit environment.

So What Is The Stack?

Let's begin by looking at a piece of C/C++ code.

    int foo() {
        return foobar;
    }

    int fooey() {
        int retval = foo();
        return retval + 1;
    }



We have a function called fooey which simply calls the function foo and assigns the return value to an integer called retval. A value of 1 is added to retval and the result returned to whoever called fooey (I appreciate this is nonsensical code, but it will serve our purpose adequately).

When fooey calls the function foo, the processor needs to know where to return to and this is where the stack comes into play. Associated with the stack is a stack pointer which always points to the current stack address. (On the x86 processor, this is the esp register).

Just before the program counter is set to the first executable instruction in the function foo, a value of 4 is subtracted from the current stack pointer and the address of the instruction following the call to foo is placed into that location. When the function foo returns, the current stack pointer is used to retrieve the return address from the stack and that is placed into the program counter, then a value of 4 is added to the current stack pointer.

Function Calls and Parameters

Lets now modify the code example above to include a single parameter as follows:

    int foo(int foo_param) {
        return foobar * foo_param;
    }

    int fooey() {
        int retval = foo(10);
        return retval + 1;
    }



What happens now, is before the call to foo is made, a value of 4 is subtracted from the current stack address and the value of our parameter is placed into that location. Then a value of 4 is subtracted from the current stack address and address of the instruction following the call to foo is placed into that location. We now have:

---> return address to caller
     the parameter 10



Within the function foo itself, the parameter foo_param is accessible by using the current stack pointer plus four bytes.

When the function foo returns, the current stack pointer is used to retrieve the return address from the stack and that is placed into the program counter, then a value of 4 is added to the current stack pointer. We now have a bit of a problem, in that the parameter is left on the stack.

Who Cleans Up Parameters On The Return From A Call?

If you are not already familiar with calling conventions in C/C++, please read up on the __cdecl and the __stdcall calling conventions.

The function foo is by default taken as __cdecl, so upon return from that function, the caller (i.e. fooey must clean up the stack by simply adding 4 to the current stack pointer. If the function foo had been declared as:


    int __stdcall foo(int foo_param) {
        return foobar * foo_param;
    }



then the stack would be cleaned up by adding an additional 4 to the current stack pointer before returning to the caller.

Local Function Variables

Variables that are local to a function are also placed onto the stack and this is where another problem lies. Let's continue our example from above, and add a local variable called fooit.

    int foo(int foo_param) {
        int fooit = foo_param;
        return foobar * fooit;
    }

    int fooey() {
        int retval = foo(10);
        return retval + 1;
    }



If we subtract 4 from the current stack pointer and use this as the address of fooit, then the parameter foo_param changes it's location to being the current stack pointer plus eight bytes. Now whilst it is possible for a compiler to keep track of how far away parameters are away from the current stack pointer, so it generates code correctly, this is rather tedious. Instead, we use a system called stack framing.

Introducing The Stack Frame

Stack framing is a mechanism whereby each function has a prolog and an epilog that is automatically generated by the compiler for all C/C++ functions (unless declared __naked).

For the x86 processor, the prolog code generated by the compiler simply subtracts a value of 4 from the stack pointer, saves a register known as the ebp register into that stack pointer location, then moves the current stack pointer address into the ebp register. Let's now subtract 4 from our current stack pointer, which is the space needed for our fooit variable. We now use the current ebp pointer to access our parameter, it is plus 8 bytes from the address held in that register and our local variable is accessed using the current ebp register minus 4 bytes.

Current stack pointer ---> ebp-4 | Location of fooit  |
Current ebp pointer   ---> ebp   | Old ebp register   |
                           ebp+4 | foo return address |
                           ebp+8 | parameter value 10 |



When foo returns, the current stack pointer is set from the current ebp pointer, the ebp pointer is set to the contents of the memory location pointed to by the current stack pointer and 4 then added to the current stack pointer. Using this stack frame mechanism, it does not matter what the state of the current stack pointer is, we can always return back to the calling routine. This is known as unwinding the stack, and is the method used when a function throws an exception condition.

This post has been edited by Martyn.Rae: 07 May 2011 - 03:33 PM


Is This A Good Question/Topic? 6
  • +

Replies To: Everything You Needed To Know About The Stack But Daren't Ask

#2 DXDenton  Icon User is offline

  • New D.I.C Head

Reputation: 1
  • View blog
  • Posts: 10
  • Joined: 28-April 10

Posted 10 May 2011 - 02:40 PM

    int foo() {
        return foobar;
    }

    int fooey() {
        int retval = foo();
        return retval + 1;
    }





Just before the program counter is set to the first executable instruction in the function foo, a value of 4 is subtracted from the current stack pointer and the address of the instruction following the call to foo is placed into that location. When the function foo returns, the current stack pointer is used to retrieve the return address from the stack and that is placed into the program counter, then a value of 4 is added to the current stack pointer.
____________________

So if the stack points to address 8A8AB4B4 it will be decremented to 8A8AB4B0 before executing foo. Why? Why is a value of 4 subtracted/added to the current stack address pointer when calling or returning from a function?
Was This Post Helpful? 0
  • +
  • -

#3 DXDenton  Icon User is offline

  • New D.I.C Head

Reputation: 1
  • View blog
  • Posts: 10
  • Joined: 28-April 10

Posted 10 May 2011 - 04:12 PM

View PostDXDenton, on 10 May 2011 - 04:40 PM, said:

    int foo() {
        return foobar;
    }

    int fooey() {
        int retval = foo();
        return retval + 1;
    }





Just before the program counter is set to the first executable instruction in the function foo, a value of 4 is subtracted from the current stack pointer and the address of the instruction following the call to foo is placed into that location. When the function foo returns, the current stack pointer is used to retrieve the return address from the stack and that is placed into the program counter, then a value of 4 is added to the current stack pointer.
____________________

So if the stack points to address 8A8AB4B4 it will be decremented to 8A8AB4B0 before executing foo. Why? Why is a value of 4 subtracted/added to the current stack address pointer when calling or returning from a function?


Ahh...I think I answered my own question. The stack is byte addressed, so decrementing by 4 = 32-bits. Why did I assume 32-bit addresses?

This post has been edited by DXDenton: 10 May 2011 - 04:12 PM

Was This Post Helpful? 0
  • +
  • -

#4 DXDenton  Icon User is offline

  • New D.I.C Head

Reputation: 1
  • View blog
  • Posts: 10
  • Joined: 28-April 10

Posted 10 May 2011 - 04:44 PM

Local Function Variables

Quote

Variables that are local to a function are also placed onto the stack and this is where another problem lies. Let's continue our example from above...


What is the state of the stack at this point in the example?

Is it the same as below?

1	---> return address to caller
2	     the parameter 10


Was This Post Helpful? 0
  • +
  • -

Page 1 of 1