Confusion of the "stack" in Assembly-level programming [closed]

Question

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...

Answer 1

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.

Answer 2

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.

Answer 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.