An overview of Stack

In this semester, I’ve a core subject named Computer Language Engineering,
which mainly focuses on the design of Compilers. But today, Prof.
SushasKurup M took a very good session on the stack structure, this
intended me to write a blog on “Stack”. Hope that you will enjoy it!!

A stack is a contiguous block of memory containing data. A register called
the stack pointer (SP) points to the top of the stack. The bottom of the
stack is at a fixed address. Its size is dynamically adjusted by the kernel
at run time. The CPU implements instructions to PUSH onto and POP off of the
stack.

The stack consists of logical stack frames that are pushed when calling a
function and popped when returning. A stack frame contains the parameters to
a function, its local variables, and the data necessary to recover the
previous stack frame, including the value of the instruction pointer at the
time of the function call.

Depending on the implementation the stack will either grow down (towards
lower memory addresses), or up. In our examples we’ll use a stack that grows
down. This is the way the stack grows on many computers including the Intel,
Motorola, SPARC and MIPS processors. The stack pointer (SP) is also
implementation dependent. It may point to the last address on the stack, or
to the next free available address after the stack. For our discussion we’ll
assume it points to the last address on the stack.

In addition to the stack pointer, which points to the top of the stack
(lowest numerical address), it is often convenient to have a frame pointer
(FP) which points to a fixed location within a frame. Some texts also refer
to it as a local base pointer (LB). In principle, local variables could be
referenced by giving their offsets from SP. However, as words are pushed onto
the stack and popped from the stack, these offsets change. Although in some
cases the compiler can keep track of the number of words on the stack and
thus correct the offsets, in some cases it cannot, and in all cases
considerable administration is required. Further more, on some machines, such
as Intel-based processors, accessing a variable at a known distance from SP
requires multiple instructions.

Consequently, many compilers use a second register, FP, for referencing
both local variables and parameters because their distances from FP do
not change with PUSHes and POPs. On Intel CPUs, BP (EBP) is used for this
purpose. On the Motorola CPU’s, any address register except A7 (the stack
pointer) will do. Because the way our stack grows, actual parameters have
positive offsets and local variables have negative offsets from FP.

The first thing a procedure must do when called is save the previous FP
(so it can be restored at procedure exit). Then it copies SP into FP to
create the new FP, and advances SP to reserve space for the local variables.
This code is called the procedure prolog. Upon procedure exit, the stack
must be cleaned up again, something called the procedure epilog. The Intel
ENTER and LEAVE instructions and the Motorola LINK and UNLINK instructions,
have been provided to do most of the procedure prolog and epilog work
efficiently.

Let us see what the stack looks like in a simple example:

Example1.c:

#include
void function(int a, int b, int c)
{
char buffer1[5];
char buffer2[10];
}

void main()
{
function(1,2,3);
}

To understand what the program does to call function() we compile it with
gcc using the -S switch to generate assembly code output:

 $ gcc -S -o example1.s example1.c

By looking at the assembly language output we see that the call to
function() is translated to:

pushl $2
pushl $1
call function

This pushes the 3 arguments to function backwards into the stack, and
calls function(). The instruction ‘call’ will push the instruction pointer
(IP) onto the stack. We’ll call the saved IP the return address (RET). The
first thing done in function is the procedure prolog:

pushl %ebp
movl %esp,%ebp
subl $20,%esp

This pushes EBP, the frame pointer, onto the stack. It then copies the
current SP onto EBP, making it the new FP pointer. We’ll call the saved FP
pointer SFP. It then allocates space for the local variables by subtracting
their size from SP.

We must remember that memory can only be addressed in multiples of the
word size. A word in our case is 4 bytes, or 32 bits. So our 5 byte buffer
is really going to take 8 bytes (2 words) of memory, and our 10 byte buffer
is going to take 12 bytes (3 words) of memory. That is why SP is being
subtracted by 20. With that in mind our stack looks like this when
function() is called (each space represents a byte):


bottom of top of
memory memory
buffer2 buffer1 sfp ret a b c
<------ [ ][ ][ ][ ][ ][ ][ ]

top of bottom of
stack stack

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