How are things stored in stack?

So I have been learning assembly and came to the topic of stack, storing local, static and global variable and stuff.

But I'm having a hard time imagining it in my head.

Bottom of memory but top of stack, :S whaa??

The thing that got me confused is, every time something gets push(ed) into stack, stack pointer gets subtracted. Shouldn't it add to it.

I mean I get the code, but its hard not still knowing what's really h开发者_开发知识库appening.

---

It is true that on many CPU architectures the stack pointer is decreased when something is pushed onto the stack. This is really an implementation detail of the CPU, but if you find that confusing you may try visualize the stack like it is done on this diagram:

_{(source: eventhelix.com)}

The memory addresses increase as you move down, but when you want to push something on top of the stack you place it on top of the diagram (at a lower address).

(The diagram can be found at EventHelix.com.)

---

The thing that got me confused is, every time something gets push(ed) into stack, stack pointer gets subtracted. Shouldn't it add to it.

It could be. That depend on whether the stack grows upwards or downwards.

Understand the stack

Stack grow direction

---

Think of it as of an implementation detail. On many architectures when you push something onto the stack the stack pointer gets subtracted so the stack grows downwards (to the smaller addresses). That's all.

---

The reason they do that because stack share the same memory chunk with heap. The heap grow from the top (low address) to bottom (higher address number) while stack grow from bottom (high address number) to the top (the lower).

This is done so that there is no need to predict the amount of memory twice (one for heap and another for stack).

00000000 HEAP----
00000001 ||||||||
00000002 vvvvvvvv

FFFFFFFD ^^^^^^^^
FFFFFFFE ||||||||
FFFFFFFF Stack

Hope this helps.

---

The reason for decrementing the SP, is simply that (*) the stack is added to "from the bottom" (with regards to the memory location). It would be a bit like if you had a "to do list". You'd start it at the top of the page, and rather than marking individual things off at random in the list (like we typically do), you'd only start and complete the job that is the furthest down the page.

The reason for this using the memory from the top (i.e. from the higher addresses) for the stack is that it allows another important memory store, the heap to grow in the other direction (at least, that is the case in some memory models). Continuing with the "to do list" analogy, now you'd be also writing another list, say a grocery list, from the bottom of the page. However, this list being the heap, you'd allow yourself you erase things from it at random places, as you walk through the store, as well as re-using the space left by some of the erased lines.

Now at the risk of adding more material for confusion, another important element of the stack management is the concept of a stack frame, which is a convenient way of storing the parameters to a function and the local variables, that correspond to the "overall context" of nested function calls.

(*) on many CPUs, that is. As Pierr pointed out, some CPUs work with a stack that move the SP "up" (increase it) when things are pushed upon it.

---

The stack grows down, the heap grows up, that way you don't have to decide how much for each. Actually, things are more complex than that now, but x86 and others have machine ops with that assumption built in. In any case, it doesn't matter, the machine adds ands subtracts equally well.

---

The "top" of the stack has nothing to do with how the stack is layed out in memory.

It's a data structure. The "stack" analogy is a conceptual model, the fact that it grows upward or downward in memory space is simply an implementation detail. Heck, the fact that it uses a continuous block of memory is merely an implementation detail; you can very well have a stack where the items are scattered all over the place, for instance, if you implement it as a linked list.

It's not even a real stack: consider for instance, that even though the text-book says it's a "last-in first-out", you can in reality change items in the middle of the stack.

What you need to implement a stack is:

• A way to point to each frame/element of the stack
• A way to point to the last inserted element of the stack (aka stack top)
• A way to get to the previous element
• A way to insert an element to the end/top
• A way to remove an element from the end/top, such that its previous element becomes the new last/top element.

How the memory layout looks like has nothing to do with any of it.