I'm assuming that you know what the data structure known as a stack is. A lot of my discussion is going to maybe be inaccurate, and it probably will be DOS/Intel-specific... and the syntax I made up.
The stack and heap both reside in RAM. The heap is at the bottom, the stack is at the top. Here's a picture....
Code:
[] <- This is the top of memory
[] <-Every block above the sp is reserved
[] <-Every block above the sp is reserved
[] <-Every block above the sp is reserved
[] <- sp (stack pointer) points here
[] <- below
[]
[] <- this is a memory block.
[]
[] <- Everything here is your heap
[] <- Some might be reserved, some might not, but it tries to
[] <- keep low so it doesn't collide with sp
[]
[] <- I think your program resides here
Now, let's say that you want to push an item on the stack, you just decrement sp, and voila, your stack is now 1 block bigger. If your stack hits reserved memory in the heap, then your program go bye bye. The stack is nice because it's extremely easy to allocate / deallocate memory for it like this. Handling memory on the heap is a lot more complicated (see the K&R implementation of malloc). Raising sp (and thus removing a block from the stack) is called popping. Lowering sp (and this adding a block to the stack) is called pushing. When you push, you can also choose a value for the new block in the stack at the same time.
Now, what goes on the stack, and what goes on the heap?
Code:
char global;
char aglobal[100];
int main (void)
{
char * s;
int a;
char c;
int array[100];
a = 2;
// Beh, let's just do nothing.
char = doNothing (a);
return 0;
}
void * doNothing (int passedVal)
{
void * result;
int b = 2;
passedVal = passedVal + b;
result = malloc (52);
return result;
}
Let's just run down the lines. First, you have your global data. These are the first things to go into your program's heap. They go at the bottom. It's hard to allocate and deallocate memory on the fly, but since your program is going to have them in memory the whole time, it just has to allocate it once at the beginning and deallocate it once at the end, which is easy to do. Also, there isn't really any way to have the entire program be able to access something on the stack, since our point of reference on the stack is always moving.
So we have global and aglobal. The first takes one byte, the latter takes 100 bytes, both go on the bottom of the heap.
char * s;
int a;
char c;
int array[100];
Okay, now this is 409 bytes worth of local variables we've got here (each int and pointer takes 4 bytes), and we don't have to initialize any of them... hurray. This memory we allocate on the stack, and it's easy to do...
sp -= 409
That was easy enough no? s is on the top, a is next, c comes next, then the 100 ints. So, when we refer to each of these, your computer does it like this...
#define s (sp + 405)
#define a (sp + 401)
#define c (sp + 400)
#define array (sp)
Next, we assign the value of 2 to a....
*(a) = 2
or equivalently...
*(sp + 401) = 2
Or in english, move the value 2 into the memory pointed at by sp+401.
Next we call a function. This is kinda tricky. We need to somehow get a from main to doNothing, get result from doNothing back to main, and there's a bit of CPU information that needs saved. First, we put a on the stack.
sp -= 4
*sp = *(a + 4)
Notice we have to take the change of sp into account, since a is referenced relative to sp. Everything on the stack is referenced relative to sp.
Next, we need memory where result (a pointer, and thus it takes 4 bytes) will be. Again, we use the stack..
sp-= 4
We don't have anything to put in there though.
Finally, we have some machine stuff to put in there. What exactly this entails depends, but the most important bit of information is it pushes a pointer to the current location in your program. This is possible because your program is loaded in memory, so we can have a pointer to it. When we call the function, we jump to another point in the program, so we need this information to know where to go back to when we're done in the function.
I'm going to assume that we have to store 8 bytes of information for this stuff...
sp -= 8
*sp = *CPUarea
goto doNothing
---- Notice how you can skip the following section, and ignore the mechanics of the function, just like in C. You can also understand how this function works without having to look at the caller.
Now we're in doNothing. First let's make some space for result and b....
sp -= 8
#define result (sp + 4)
#define b (sp)
We don't really know much anything about who called us, although we do know information about the stack....
Code:
For the sake of space, each block represents 4 bytes...
[] <- passedVal
[] <- returnVal
[] <- CPU stuff
[] <- address of caller
[] <- result
[] <- b (sp)
The parts that interest us are passedVal and result, so...
#define passedVal (sp + 20)
#define returnVal (sp + 16)
So, let's do the math.
*b = 2
*passedVal = *passedVal + *b
Now we have a call to malloc, which is kinda tricky. It reserves memory on the heap, but we let the operating system handle this.
*result = (get address of memory allocated on heap)
Finally, we get to the return statement. This has two parts. First, we have to take the value we want to return and put it in returnVal...
*returnVal = *result
Now we have to actually return. First, we scrap the local variables...
sp += 8 // frees b and result
Then we load CPU information off the stack...
*CPUarea = *sp
----- Stop skipping here.
Now the CPU is looking back at the main function, at the point after goto doNothing. It's our job to get the stack back to normal...
First, let's scrap the information the CPU needed for the jump
sp += 8
Next on the stack is the space we allocated for the result. We have to put it into s...
*s = *sp
sp += 4
Finally we have to get rid of the copy of a we made.
sp += 4
Apparantly the function changed the value of the copy we made of a, but that doesn't have any effect on us, since it wasn't actually able to access a, just the copy we put on the stack.
Now sp is back to where we expect it to be, at the bottom of our local variables. We can resume execution.
Then we hit return. Since it's a return from main, it's quite unique, and not something I am going to discuss.
You don't really have any choice over when you use the stack and when you use the heap. Local variables use the stack, and global variables use the heap. malloc() also uses the heap, but since it does so during the program's execution, it's a fairly slow operation.
Some things I wasn't quite accurate about in the above discussion...
1) The size of the stack is not neccisarily 'however so long as you don't hit something in the heap', although in some cases it is.
2) Technically, the address that is pushed on the stack is not that of the calling function. Instead, that gets put into a register, and whatever was in the register before gets pushed onto the stack.
What's important is that, every time you call a function, even if that function has no return value and accepts no arguments, something will have to be put on the stack.
Your C programs really should be blind to the fact that there's even a stack and a heap. In fact, your compiler very well may change how it deals with memory on a program-by-program basis for optimization sake (it might even not store some variables in memory, instead using registers which are extremely fast).
