Call Stack Internals (Part 1)


In this post, I will be discussing the internal working of a function call stack. The content will be divided into multiple posts for better understanding. Major focus will be on the following:

  • Creation of stack frames,
  • Saving/restoring registers to/from the stack.
  • Saving function local variables, arguments, and return address on the stack.
  • Usage and manipulation of stack specific registers — Stack pointer and Frame pointer.

The code examples presented are written and compiled on Linux systems running on 64bit x86 platform. But, the discussion will still give a generic understanding of the stack.

On x86 platforms, stack space allocated to the process grows downwards — higher to lower memory addresses.

If we take the following code example, the diagram below it shows how stack frames are created and removed from the stack during a typical call sequence.

int main()
{
  foo();
  bar();
}
void foo()
{
  // do something
  bar();
}
void bar()
{
  // do something
}

stack

The above diagram shows how the stack memory gets allocated and de-allocated as the execution of the above program proceeds and functions call each other. But, what is this stack frame ? What information does it contain ? How does it get created and manipulated ? Why is it even used ? The next section of the post will answer such questions.

A stack frame is a memory area used for storing information for a particular called function. A frame stores:

  • Arguments passed by the caller.
  • Local variables.
  • Return address to the caller.
  • Frame pointer for the previous frame (stack frame for the caller at a memory address higher than the current frame).
  • Exception handling information (if any).
  • Saved value of the CPU registers that the callee (called function) can’t modify freely, and thus they first need to be preserved on the stack.

A stack pointer is one of the general purpose registers (RSP) provided by x86. It contains a reference to the top of the stack. Please don’t forget that stack grows downwards, so top of the stack is at numerically lower address than other elements in the stack.

A frame pointer is also one of the general purpose registers (RBP) provided by x86. The value (address) stored in the frame pointer is used as an offset to access the local variables, arguments, return address stored in the stack frame of the function under execution.

Two basic instructions used to manipulate (grow and shrink) the stack are:

  • PUSH source – decrements the value of stack pointer and stores the “source” information at the top of stack.
  • POP dest – pops the value from the top of stack or loads the destination “dest” with the value from the top of stack and increments the stack pointer.

How a stack-frame is setup ? Let’s say function foo() calls function bar().

Before bar() is called. Stack frame setup operations performed by the caller :

  • Push the arguments of bar() on stack. Note that arguments are pushed in reverse order — right to left.
  • Push the return address (the current value in instruction-pointer (RIP) register) on stack.

After bar() is called. Stack frame setup operations performed by the callee :

  • Push the RBP register value on stack. This value is the frame pointer for bar()’s caller which is foo() and is commonly referred to as “old RBP”.
  • Move the current value of RSP register to RBP register. This new value of RBP is the frame pointer for callee or bar()’s stack frame.
  • Decrement RSP to create storage space for local variables and buffers.
  • Preserve registers on the stack.

So with the above information, a typical stack frame may look like:
stack1

Explanation –

  • After the function arguments and return address have been saved onto the stack, return address is at the top of the stack. Hence. at this moment, RSP points to this memory location.
  • We further decrement the RSP by pushing the RBP register value (previous frame pointer) onto the stack. RBP register value is at the top of stack implying RSP points to this location.
  • We now move the RSP value to RBP making both RSP and RBP point to the same location on stack. The RBP becomes the frame pointer for the current frame under concern.
  • RSP get further decremented as space for local variables, temporary buffers is allocated.
  • Finally, the callee may preserve some registers on stack which results in further growth of stack.

From the above diagram, we can observe that:

Following are at the positive offsets from the frame pointer.

  • Old frame pointer — RBP + 0b
  • Return address — RBP + 8b
  • Arguments — RBP + 16b onwards

Following are at the negative offsets from the frame pointer:

  • Local variables
  • Buffers
  • Callee saved registers.

I would like to conclude part1 here. In the next part, we will take a dig into the following:

  • Assembly level instructions performed to set-up the stack.
  • Stack cleanup.
  • Restoring of frame pointer and base pointer along with other registers.
  • Stack unwinding.
  • More diagrams with more code examples 🙂
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Blog at WordPress.com.

Up ↑

%d bloggers like this: