4

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

leslar Bonar
  • 53
  • 3
    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. – Caleb Jan 23 '13 at 00:17
  • https://dl.acm.org/citation.cfm?id=2716018#.W5zV9yqRi-c.twitter – firo Sep 15 '18 at 10:36

3 Answers3

11

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.

luiscubal
  • 1,537
  • 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
  • 1
    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 00:53
  • And also, the architecture need not have any involvement or say in whether or not the software writer implements it. So technically, wouldn't whether or not the stack is stored on a storage medium or is all just physical RAM entirely depend on the programmer, not necessarily whether or not the architecture allows such an operation? An OS doesn't have to have virtual memory. – leslar Bonar Dec 18 '12 at 01:02
  • @BigyellowBastion, in a hypertheoretical sense you could use the disk drive or a paper tape or M&Ms in pigeonholes to implement the system stack, but that would require you to build your own hardware. If you are using commodity PC hardware it's unlikely to be possible. You do realize that there are no simple assembly instructions for writing to disk don't you? You are going to have to write moderately complex functions to read and write from the disk and those are going to be a lot easier if they use a stack in RAM. – Charles E. Grant Dec 18 '12 at 03:13
  • I fail to see your debate here ... sure Assembly is not the best for everything, but that's not the question(s) I was asking, and not the answers I was looking for. – leslar Bonar Dec 18 '12 at 03:34
  • @BigyellowBastion If you are in a mode that does not support virtual memory (such as x86's real mode, which is what I believe bootloaders use), then the stack will be in the RAM (the "physical memory"), at the memory region you tell it to be. Usually, you'll tell the processor what that region is by changing the values of the SP(or ESP) and SS registers. – luiscubal Dec 18 '12 at 14:12
  • But say I don't implement virtual memory at all in my system ... that would mean that, given the full use of actual RAM, I would access the stack in RAM only, which would probably simplify the OS. – leslar Bonar Dec 18 '12 at 17:13
  • @BigyellowBastion If you don't implement virtual memory, then the stack is indeed an actual physical memory (RAM) region. Note that the RAM does not have any "special support" for stacks. The "stack" is merely a processor/program concept. – luiscubal Dec 18 '12 at 17:27
  • So how would the stack be in the RAM if the RAM has no "special support" for it? – leslar Bonar Dec 18 '12 at 21:51
  • @BigyellowBastion When you write char c[1024];, the RAM has no "special support" for that. It's treated like any other memory. So is the stack. Technically you could do char c[1024]; and then set the stack pointer register to be the end of that array (I say "end" and not "beginning" because the stack grows downwards, so PUSH reduces the value of the SP register), and then the stack would be that array. When you are writing a bootloader or a kernel, the stack is where you tell the processor it is. All you should do is ensure that memory region is not used for anything else. – luiscubal Dec 18 '12 at 23:07
5

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.

Karl Bielefeldt
  • 147,435
5

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.

mattnz
  • 21,362