Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

What is the "stack" exactly?

I've read articles, tried comprehending it through my understanding, experience, and educated guessing of programming and computers, but I'm a bit perplexed here.

The "stack" is a region in RAM? Or is it some other space I'm uncertain of here?

The processor pushes bits through registers on to the stack in RAM, or do I have it wrong here?

Also, the processor moves the bits from the RAM to the register to "process" it, such as maybe a compare, arithmetic, etc.

But what actually can help understand, in some visual or verbal description or both, of how to implement the idea of a "stack" here?

Is the stack actually the same in terminology with a "machine stack" meaning it's in RAM?


I know what a software stack is. I know about LIFO, FIFO, etc. I just want to gain a better understanding of the assembly level stack, what it is, where it is, how exactly it works, etc...

share|improve this question

closed as unclear what you're asking by MichaelT, gnat, Bart van Ingen Schenau, World Engineer Apr 19 at 23:29

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question.If this question can be reworded to fit the rules in the help center, please edit the question.

2  
I see that you haven't marked any of the three good answers here as correct. Can you explain what you're confused about that's not answered here or in the relevant Wikipedia article? Additionally, any book on computer architecture, operating systems, or assembly language will explain all about the stack. If you're really planning on writing an operating system, you'll want to read at least one good book in each category. –  William Shakespeare Jan 23 '13 at 0:17

3 Answers 3

You do not state what processor your assembly is for, however the basic understanding will not change as they all do the same thing.

Virtually all computers have a small set of machine codes that provide support for basic stack operations. These are PUSH and POP and a stack pointer register (I'll call it SP)- that points to a location in memory. If supported, procedure calls (CALL) and returns (RET) use a stack by pushing and poping the return address. Hardware interrupts use a stack for saving return address and registers. Depending on the machine, there may be more than one stack pointer (e.g. One for Hardware interrupts, one for program flow and one for data).

The concept of a "Stack" is supported by the processor instructions, but is really something the processor knows little about. SP points to an address, PUSH stores and updates SP, POP updates SP and retrieves from the address. As programmers, we make those simple instructions into a "stack". Clever Assembly can make use of those instructions for other tasks (At the developers peril).

Most processors have other instructions for managing the stack and manipulating the stack pointer.

The stack operates by first setting SP to point to a RAM memory location. PUSH Decreases SP (by the size of the item) and then copies the item to the SP location. POP Copies the item from the location SP points to, then increases SP by the size of the item. Note: Typically Stacks grow from higher memory addresses down to lower memory addresses. There is not particular reason for this beyond historical choices - The stack sat at the upper memory locations, and the program at the lower locations. In the early days, you were out of memory when the stack and program memory collided, however, it made it easier to manage memory . This still happens on small micro computers. On more complex architecture, there is a memory management system that prevents this happening

Depending on the machine in use, the PUSH and POP instructions can move registers, memory locations etc of various sizes between the stack. Many processors have other registers that allow detection of stack overflow/underflow, use of multiple stacks etc.

share|improve this answer
    
x86 Intel architecture is the microarchitecture I'll be developing on. –  leslar Bonar Dec 18 '12 at 0:55

It's a reserved area of RAM that is accessed by an offset from a stack pointer. For example, consider a stack consisting of 5 words:

5 garbage
4 garbage
3 garbage
2 garbage
1 garbage

Before a function is called it has a stack pointer (SP) equal to 6. The function call instruction puts the return address on the stack and decrements the stack pointer, so now it looks like:

5 return address <-------- SP
4 garbage
3 garbage
2 garbage
1 garbage

If you want to allocate an integer on the stack, just decrement the stack pointer:

5 return address
4 local integer  <-------- SP
3 garbage
2 garbage
1 garbage

Now when my function needs to access my local integer, it uses the memory address of SP+0. If I call another function, it decrements the SP again, and I can allocate some storage again, like:

5 return address
4 local integer
3 return address for second function
2 local integer for second function
1 another local integer for second function   <-------- SP

Now, if I use the memory address SP+0, it is referring to the second function's local integer. Note that I'm now out of stack space, so any more operations will result in a stack overflow.

When I return, I just do it in reverse, add to the SP to deallocate the memory, then the return instruction reads the return address from the stack.

Note that the stacks of different architectures work slightly differently. On some the SP is decremented before pushing the return address and some after. Some automatically save registers on the stack in addition to just the return address, especially during an interrupt. On a PIC, for another example, the stack is completely isolated memory that only holds the return addresses and can't be used for variables. What's common is the LIFO allocation of memory.

share|improve this answer

Typically, the stack is a memory region.

It is possible to add data to the stack ("push"), or to retrieve it and take it out of the stack ("pop"). The last data added to the stack is the first to be retrieved.

PUSH 1
PUSH 2
PUSH 3
POP -> Result 3
PUSH 4
POP -> Result 4
POP -> Result 2
POP -> Result 1

The processor pushes bits through registers on to the stack in RAM, or do I have it wrong here?

Processors often have instructions to copy data from the registers to the stack and vice-versa.

In x86 assembly (32 bits):

MOV EAX, 20
PUSH EAX ; Adds 20 to the stack (32 bits, many of which are zero)
POP EBX ; EBX will have the value 20, and the stack will be restored to its former state

However, in most (all?) architectures, it is possible to obtain data from the stack without actually popping it.

In x86 (32 bits)

MOV EAX, [ESP+20] ; Will copy to EAX the contents of the stack 20 bytes before its current state

The "stack" is a region in RAM? Or is it some other space I'm uncertain of here?

You can think of it like that.

In modern architectures, there is something called the virtual memory which will be frequently, but not always, mapped to the physical memory (RAM). Ocasionally, when the physical memory runs out, this memory will be stored to disk.

The virtual memory is where the stack is usually placed.

However, the stack will also be accessed frequently, so it will often be in the processor cache too.

Fortunately, that is all abstracted away. As far as a program running in the machine knows, the stack is in the RAM. The OS typically takes care of the ugly details.

share|improve this answer
    
So you're saying that the stack is a hardware-region of the RAM, and the processors copies data, moves data, and accesses bits from it? You're NOT saying that the stack is NOT in the RAM, correct? –  leslar Bonar Dec 17 '12 at 22:40
    
confusing way to ask that, but yes, the stack is in RAM. –  bunglestink Dec 17 '12 at 22:48
    
@BigyellowBastion You can think of it like that, but things are more complicated than that. In many (most?) architectures, the stack is a region of virtual memory. It is possible for multiple stacks to coexist (e.g. one per thread), so the RAM may have multiple stacks. Technically, the RAM could be swapped to disk, so the RAM might not have all the stacks there. Also, the stack is very commonly accessed, so it'll usually be in the cache. But, as far as a program being executed is concerned, the stack is in the RAM. All else is usually abstracted away by the operating system. –  luiscubal Dec 17 '12 at 22:58
    
I'll just add my comment to the answer. –  luiscubal Dec 17 '12 at 22:59
    
So if I write my own operating system and DON'T implement virtual memory, will the stack be entirely in RAM? I plan to write a small bootloader and see where things go ... how would that work out as far as the stack goes? –  leslar Bonar Dec 18 '12 at 0:53

Not the answer you're looking for? Browse other questions tagged or ask your own question.