Stack Layout

Figure above shows a typical stack layout with only one stack frame. Everything in the diagram looks quite self explanatory except three new terms Frame Pointer, Stack Pointer
Old EBP. Let us tackle these three aliens one by one.

Stack Pointer and ESP: ESP is a special purpose register on the CPU which always contains the address of the last data item pushed on to the stack. In figure 2 it is pointing to local3. Every time a new data item is pushed on to the value in stack pointer register is decreased by the size of the data item to show the current top of the stack. Similarly every time a data item is popped out of the stack the value in ESP is increased by the size of the data item to show the current top of the stack.


Frame Pointer and EBP: EBP is another special purpose register on CPU.Every time a function is called the value of EBP is pushed on to the stack just after the arguments and the return address. Once the value EBP is pushed to the stack, definitely stack pointer will move to reflect the new current top of the stack. This new current top is copied into the EBP register. So the EBP also known as frame pointer register points to the previous value of EBP (or say the value of EBP before entering the called function or Caller ‘s EBP) stored on the stack.

This gives us a mechanism to traverse within a frame on the stack. If you want to know
The return address of a function from stack you have to use Frame pointer of that function and not the stack pointer because it is dynamic and keeps changing.In this case if you want to know the return address.You have to read the data item just below the location where old EBP or caller’s EBP is saved.


So return address will be EBP + 4



So the flow of making a stack frame for a function starts with caller pushing the arguments passed to the called function followed by return address of the called function.
These two things are done internally as part of the X 86 Call instructions.


After this the control goes to the called function.

The called function will always start by first pushing the EBP and then updating it with new ESP.

PUSH EBP

MOV EBP, ESP



Return Address and EIP: We have been talking bout pushing the return address of the called function on to stack. You also learnt that pushing the arguments passed and the return address is done as a part of the X 86 Call instructions. But where does the call instruction get the return address from?? The answer is from EIP .EIP is again a
Special purpose register on the CPU which always points to the next instruction to be executed. So when function1 calls function2 the control goes to
Call Function2 (arg1,arg2).
At this point EIP contains the address of next instruction to be executed after the Call completes. So Call instruction pushes the value of EIP on stack just after pushing the arguments.

Let us stack it up!!!

Today I plan to stack up this 'dormant for a while' blog with some wisdom bytes stacked up in my tiny brain about (yes, you guessed it right) Stack.

So here we go ........

Stack
A stack is an abstract data structure based on the principle of Last in First out (LIFO).
It has two basic operations: push and pop.

Push adds a given data item to the top of the stack leaving previous items below.
Pop removes and returns the current top data item of the stack.

Stack oriented program flow

Stack is a ubiquitous data structure in the world of programming. It is used for a variety of purposes including reversing a string, implementing search techniques and most importantly for deciding program flow and run time memory management by almost all the modern programming languages. Let us now explore how programming languages use stack for dictating program flow.

A computer program is nothing but a set of instructions to the CPU which when executed in a particular sequence performs some useful task. The bigger the task the longer will be the list of instructions to be executed by the CPU. What do you do when you have to evaluate a big expression: {(x+y)-z} * r .You divide the expression into parts and evaluate each part one at a time like this:

Add X+Y first and then subtract Z from the sum and then multiply the result with r.

So you divided the problem into manageable parts and worked on each part separately.
Similarly to write a program for a very complex task you should first divide the task into simpler tasks and then write the code for each simple task. The piece of code for each simple task here is called a function. Each function after performing its designated task delivers the results through a return value. These functions work together to accomplish the actual task for which the program was written.

Now the question is how these functions work together. Here is the answer:

Every program has a function called main function at which the program execution starts. As you know each function has a designated task which it has to accomplish and deliver the results via its return value. The designated task of main function in any program is to accomplish the actual goal of the program in this case to evaluate the expression {(x+y)-z} * r and return the result of expression. Now we have divided the task into subtasks:

Task 1: add x, y

Task 2: Subtract z from sum of x and y .For that it should first know the sum. The Sum has been calculated in task 1 .So it should request task 1 to give it the sum.

Task 3: Multiply the result of task 2 with r. So taks 3 should somehow get the result of task 2.

Form above it is clear that if you want to divide your program into functions there should be a means for functions to communicate.

A function requesting another function to do a subtask on its behalf is called calling a function.

When a function calls another function to perform a subtask it also provides the data on which subtask need to be performed in the form of parameters or arguments. The called function in turn delivers the results in the form of its return value.

So now we know that functions in a program communicate by calling function passing the parameters or arguments to the called function. Now there should be a place in memory for called function to keep the arguments passed before it work on it.

Further a function code consists of other statements interlaced with function calls.So once the called function is done with its subtask the program flow should come back to the calling function and proceed from the statement next to function call.For that it should know the address of next instruction in memory.

For all this every program creates a stack called call stack for itself near the high addresses of Process Address Space. As and when functions are called their argument values, return addresses and local variables(except static variables) are pushed on to the stack and retained there as long as the function is running. All this information pushed onto stack is called a stack frame.Once the function completes its subtask its stack frame is popped out from stack and control is returned to the return address retrieved from the stack frame.

Process Address Space

This post is not great stuff or a treasure trove of hidden secrets but the very basic things which can help you write a better User mode Application on Windows with fewer access violations.There is a lot of difference between being able to write the code that works and the code that works without throwing the disdainful access violations.Writing bug free code on windows is an art which requires the knowledge of the memory in which your application resides.


Porting your user mode code on Windows is like sending your child to a boarding school in a distant place, you better enquire about the place and send your child equipped with all it takes to survive in a foreign land.Just like the inmates of a day boarding are expected to take care of themselves Windows expects your brain child, your code to take care of itself failing which it faces the wrath of the warden, the Memory Manager.

So let us start by knowing the place, the memory allotted to the application also called the Process Address Space and how it is organised.


Each user mode process in Windows gets a Virtual Address Space of 2GB for its private use. The tiny picture you see on the right side shows how that 2GB of space is organised into segments and what does each segment contain.

Fixed Size Segments: The Text and Data segments are fixed in size and their size is decided by the size of the program to be run. The Text Segment contains the code or instructions for the CPU to execute. The fixed size data segment contains the global and Static Local Variables used in the program. These regions are generally marked read only and can not be modified by other segments.


Point to ponder: What should happen when you try to write into one of the memory locations of Code or Data segment?
Well, Windows (Operating System) being a good master and savior of these guarded (marked as Read only) territories should throw a memory access violation and stops you from going any further by terminating the offending process.
So now you know where those vicious Access Violation messages come from?


Dynamic Size Segments: Stack and heap segment both are dynamic in size. Heap grows upwards in memory (from low addresses to high addresses) and Stack grown downward (From High Addresses to Low Addresses).