confused about system stack

Hello everyone,


I am confused about the term "stack" which the system will use -- there are so many items we call them "stack". Suppose when we invoke a function, we will push the parameters and return address into a "stack", so that when the function returns, it can find the address to proceed correctly. Is it the same as a data structure "stack".

When we create a variable using malloc or new, we also say that it is allocated on "heap" other than on "stack", is heap also something like a stack in ternally (but has a different term)? And for local variables, when they are created, we say it is created on stack (for example, int i, j; ), it seems that each function has a separate stack?

Another confusing thing is thinking about stack and segment together, like the code segment, data segment of the program (which you can see when debugging your application), are the segments also some stacks (since when local variables are on code segment, we also say local variables are on stack, so I think maybe segment is implemented as stack)?

Besides the "stacks" I presented above, are there any other stacks which system will utilize?

Please forgive asking a simple question. :-)


regards,
George

When a program is compiled, the compiler goes and tallys up the total amount of static memory being allocated in the program. Things like regularly defined variables, string constants, objects, parameters in function calls and the return address are included in this tally. This is the amount of memory the executable takes up every time it's run. When you run the program, all this memory is pushed onto what's known as the "stack". It's an area of your system memory that holds all predefined data. I'm not positive, but from what I understand, this is usually in the low memory addresses of your system's memory. It should be noted, that when an application is compiled, data is not given a memory address, but simply an offset in memory from the beginning of the program's memory.

Beyond that is a reserved amount of memory for any kind of dynamic memory that may need to be allocated during the run-time of an application. This area is called the "heap". Any time you dynamically allocate memory (via malloc() or what have you), this memory is pushed onto the "heap". I'm not sure if there is any correlation between the way the memory "stack" and "heap" work and the way the data structure "stack" and "heap" work, but I wouldn't be surprised if there was.

That's about the gist of it. I'm pretty tired, so if I said anything wrong here, someone will surely correct me.

hmm,

I was always taught that an application's stack started at the very end of the available application RAM, and worked its way down into the dynamically available memory

Call stack
Stack (data structure)
Heap

>Is it the same as a data structure "stack".
Yes and no. It's a practical application of the stack data structure.

>is heap also something like a stack internally (but has a different term)?
No. A stack is a well defined data structure with strict behavioral rules. A heap is just a pool of memory that is organized in whatever way the memory manager feels is most efficient.

>it seems that each function has a separate stack?
Not really, though now you're getting pretty deep into implementation specifics. A generally accepted method is to use a single runtime stack. When a function in C is called, several things happen behind the scenes. Take the following C:

Code:

---

int foo ( int arg1, int arg2 )
{
  int temp = arg1 + arg2;
  /* Other things with temp */
  return temp;
}

int main ( void )
{
  foo ( 2, 4 );
  return 0;
}

---

When foo is called, 2 and 4 are pushed onto the runtime stack in reverse order. The runtime stack is basically just a block of unused memory somewhere in the memory allocated to the process. Each process has its own stack. The function is then called, where the address of the next instruction is pushed onto the stack as well and then the address of foo is jumped to. The stack would look like this after the call:

Code:

---

/* Push arg1 and arg2, then call foo */
-------------
|    ...    |
-------------
|  arg2    |
-------------
|  arg1    |
-------------
|Return Addr|
-------------

---

Inside foo, enough space is made on the same stack for temp and the calculations are made. It's basically like pushing an unknown value, which generally constitutes doing arithmetic on the stack pointer depending on which way the stack grows in memory:

Code:

---

-------------
|    ...    |
-------------
|  arg2    |
-------------
|  arg1    |
-------------
|Return Addr|
-------------
|  temp    |
-------------

---

Before returning, the stack is restored to its original state so that the next thing popped is the return address (usually by arithmetic). That address is jumped to, the arguments are popped, and execution proceeds. A low level assembly implementation would look something like this:

Code:

---

foo:

        ; Create a stack frame
        push        ebp
        mov        ebp,esp

        ; Allocate temp
        sub        esp,4

        ; temp = arg1 + arg2
        mov        eax,[ebp+8]
        add        eax,[ebp+12]
        mov        [ebp-4],eax

        ; Other things with temp

        ; Set the return value
        mov        eax,[ebp-4]

        ; Clean up the stack frame
        mov        esp,ebp
        pop        ebp

        ; Return
        jmp        [esp]

main:
        push        4
        push        2
        push        .next

        ; Call
        jmp        foo

    .next:

        ; Pop arg1, arg2, and the return addr
        add        esp,12

        ; return 0;
        mov        eax,0
        ret

---

The "create a stack frame" part is little more than saving the place on the stack where the return value is stored. But "create a stack frame" sounds cooler than "don't get lost and corrupt your stack, stupid!". :)

>Another confusing thing is thinking about stack and segment together
Don't do that. You'll confuse yourself unnecessarily. Stacks and segments are two completely different things.

>Please forgive asking a simple question. :-)
That's far from a simple question. :)