Sign in to follow this  
Nice Coder

The stack

Recommended Posts

I was thinking about stacks recently... i always seem to use them and yet i do not know how they work (i am working to rectify this). I have searched google with the keywords stack + work + computer i managed to get a "wiki" but it does not explain how the hardware deals with the stack. My question is: How is the stack implemented in hardware and/or software? Any information or google keywords would be very welcome, DENC

Share this post


Link to post
Share on other sites
You'll have to clarify what you mean. Are you talking about the call-stack (what's usually meant when you say "the stack"), or actual, discrete stack data structures (as in, "put the values in a stack")?

Share this post


Link to post
Share on other sites
the "call stack", if i remember correctly, is a memory address that is stored by a special register in the CPU. this address is used to allocate memory and pass arguments to functions. it's the same in basic functionality as the data structure stack, where the current address(pointer, element) is percieved of as the top and elements can be "pushed" on top of it or "popped" off the top. this idea works well for fast linear memory storage, that's why the "stack" was first designed and supported by CPU's (as opposed to lists).

though i use stacks in assembly and used them in college in theoretical programs, i have yet to find them helpfull in game programming. not to say they have no use, but i was interested in what you were using them for?

Share this post


Link to post
Share on other sites
Thank you for the replies,
I am mainly interested in the hardware that implements the stack because i do not know about that yet. (i am interested in nearly everything anything i do not know).

The main thing which made me think of the hardware of it is because i could not think of a way to implement the stack.

I am also interested in many other things in "modern" cpu's (like the cache), because it is not known to me how things like that work, and it bugs me to no end [lol].

Any keywords or information would be welcome,
DENC

Share this post


Link to post
Share on other sites
i wouldn't call stacks data structures, i would say its an abstract data type (ADT) because they can be implementated in number of ways, the concept is beyond a programming language.

As anist points out the stack in the context of hardware still has notion of the concept it just implementated differently

Share this post


Link to post
Share on other sites
How is a stack implemented in hardware?

Usually by having a register dedicated to being a pointer. A "stack pointer". Commonly called "SP", like program counters/execution pointers are called "PC"/"EP", respectively.

To 'push' a value; write the value to the address pointed at by the stack pointer, and then increment or decrement the pointer.
  (*SP) = V; SP--;

To 'pop' a value; decrement or increment the pointer (the opposite of what you did to 'push'), and then read the value at the address pointed to by the stack pointer.
  SP++; V = (*SP);

Most hardware stacks grow downwards; pushing a value decrements the stack pointer, moving from higher to lower memory as more items are added. IIRC, this was the practice in small and/or embedded systems where you'd have a moderate-sized chunk of memory at the low end of the address range, and a small chunk at the high end of the address range; the stack pointer would be initialized to point at the very top of the address space, and the stack would grow downwards. The program and data would be stored in the low end of the address range.

For example, on a 16-bit system, you might have an 8K ram chunk from 0x0000 to 0x2000, and a 1K ram chunk from 0xFC00 to 0xFFFF. SP would get initialized to 0xFFFF (for one-byte stack words), EP would get initialized to 0x0000, and execution would begin.

Share this post


Link to post
Share on other sites
This explanation is mainly x86 (Intel, AMD cpu) based, but here you go:

The hardware implementation of a stack is that the current place in the stack is stored by an special register (called the esp register, or extended stack pointer register).
Say the operating system allocates an area of memory from 0x0 to 0x1000, and puts the value 0x1000 into the esp register. Why 0x1000? The wierd thing is that on the x86 cpu, the stack grows downwards.
There are two opcodes for messing with the stack. 'PUSH' pushes a value onto the stack. It works like this:

- Minus the esp by the sizeof(value) - generally speaking 4 bytes/32bits
- Place the value at the new esp

'POP' pops a value from the stack to a value:

- Place the value at esp in value
- Plus the esp by the sizeof(value)

It's not a very dynamic data structure, you must have an area of allocated memory that nothing else will touch, otherwise there'll be trouble.

The CPU, when it comes across the call instruction, pushes eip (the extended instruction pointer register, the memory address of the current opcode) onto the stack, and any parameters that go with the function, and at the RET instruction, pops (usually) 4 bytes into the eip register so it can continue executing at the previous place.

This may be a bit advanced for you, so I suggest checking out the appendix of the NASM manual.

Share this post


Link to post
Share on other sites
Quote:
Original post by Nice Coder
Thank you for the replies,
I am mainly interested in the hardware that implements the stack because i do not know about that yet. (i am interested in nearly everything anything i do not know).

The main thing which made me think of the hardware of it is because i could not think of a way to implement the stack.


while you don't implement the hardware stack in any laguage, you use it in assembly and machine language. its a very simple concept here. there is one register (sp, for Stack Pointer) which contains a memory address of the top of the stack. calling "push" increments the address and places the value there, calling "pop" decrements the address. these are CPU instructions but you can manually manipulate the address as well.

the same could be done using just an array and a pointer. the pointer would stop at it's first position, incrementing based on calls to push and storing the value, while pop just decrements the pointer. there is no need to erase values above the pointer, just assume that these values are garbage and will overwritten with any call to push.

after your through with a pointer, an array, and two function calls you may want to try to encapsulate this in a class. that part should come very easy if you know C++.

like i said though, i haven't found any really effective uses of a stack. i DID have an interview for a job where i was required to write one though. so, if being the nerd who gets the job counts: they can be helpfull.

Share this post


Link to post
Share on other sites
Thanks for the great replies!

ok... i think i've got it now...

Push just loads from a register to a spot in ram where sp points to. it then decrements sp.

Pop just loads a register from a spot in ram where sp points to. it then increments the sp.

Is this correct?

Yes, and i am thinking about designing another processor (i sort of designed one before; it was an 8 bit processor with no cmp or jump conditionals... (because at the time i didn't know how those were implemented!))

And a few more questions...
How does a stack work for a multi-tasking environment?

If i Push too mutch information for the stack to handle, where is the error thrown?

if i pop too many times (so that i'm trying to make sp<0), does the hardware automatically stop once sp reaches 0, if so how does it do that? if not then how does it send the error to the software (flags register?) and what would happen if two pops were attempted so that sp would be -2 if not corrected? How does it stop the stack corruption which would result if you tried something like:

pop eax
pop ebx
push eax
push ebx

Is that the right way to use push and pop?
Is the stack cached?

Does the stack use the hardware normally used for load and store?

Does the stack keep a "window" of the stack in Cpu memory and the rest in ram?

I'm just full of questions... :-)
Any information, answers to questions or google keywords would be very welcome,
DENC

Share this post


Link to post
Share on other sites
Quote:
Original post by Nice Coder
How does a stack work for a multi-tasking environment?

For a multitasking environment, there are multiple stacks. The scheduler takes over when it feels like, and swaps out the instruction pointer and the stack pointer so that another process can do stuff.

Quote:
If i Push too mutch information for the stack to handle, where is the error thrown?

if i pop too many times (so that i'm trying to make sp<0), does the hardware automatically stop once sp reaches 0, if so how does it do that? if not then how does it send the error to the software (flags register?) and what would happen if two pops were attempted so that sp would be -2 if not corrected? How does it stop the stack corruption which would result if you tried something like:

pop eax
pop ebx
push eax
push ebx
It depends on the architecture and the compiler; there's no easy answer. Most modern architectures will complain, since your program will be writing to memory it doesn't have permission for.

Quote:
Is the stack cached?

Does the stack use the hardware normally used for load and store?

Does the stack keep a "window" of the stack in Cpu memory and the rest in ram?
The stack is just like any other area of memory, and since it's used so much, the active portion of it will most likely stay in the L1 cache. Some processors may specifically cache the stack separately; I don't know of any offhand.

If you really want to learn about call stacks and stack pointers and caching and all that fun stuff, get a good textbook on operating systems. The two subjects are inextricably linked. And you'll learn more about process scheduling than you ever wanted to know (and trust me, process scheduling can be cool).

Share this post


Link to post
Share on other sites
@Sneftel

If there are multiple stacks, whats to stop too many pop's from moving from one stack to another, or a stack overflow moving to the next stack.

eg.
stack 1 0-1000
stack 2 1000-2000

now say your at the beginning of stack2 (sp = 1000), and you pop the stack. you end up being at the end of stack 1's space. what if by sucessive pushes and pop's, stack 2's sp is smaller then stack 1's sp? then stack 1's stack is corrupt...

How does the os prevent this?

Sneftel, you said that the processor would complain, how would it complain?
things like segmentation faults and other things like that, how are they caught?

If its used so much, then why doesn't it have its own cache? then when trying to do a load/store you can be chacking if its in eather cache in parellel...
Any help would be appriciated,
DENC

Share this post


Link to post
Share on other sites
Each process has it's own stack. Look into virtual memory, the fundamental concept of 32bit protected mode, on google. In virtual memory, each process has it's own address space, and there is no way (in theory), of overwriting another process's memory.

Share this post


Link to post
Share on other sites
Isn't virtual memory where the computer uses the hard disk as extra ram when it runs out?

How virtual memory works (found using google)

What does that have to do with protected mode?

"Protected mode aka flat mode, allows you to address all of memory as if it was a huge sequential array" Quoted From here

How does 32 bit protected mode stop me from changing my pointer to acess another programs stack/allocated ram? and what does it have to do with virtual memory?

Can you please explain more clearly what you are trying to say cloudnine?

From Nice coder.
Edit: Clarity

Share this post


Link to post
Share on other sites
Your notion of "Virtual memory" is wrong. That's not a criticism; most people's is. Here's what it really is.

Virtual memory is a way to give each process its own memory space. Let's say you had a system where programs expect their executable code to be located at the memory location 0x80000000. So when they start, they expect to be able to find executable code there. That's fine.

But what if you have TWO processes?? You can't put them BOTH at 0x80000000, can you? They'd fight to the death! O tempora, o mores!

The solution is, make each one think it's located at 0x80000000. Here's the deal. Between the processor and the memory (physically it is actually inside the CPU these days, but that's not strictly necessary) is something called the Memory Management Unit, or MMU. The MMU keeps track of which process is currently running, and what memory segments it THINKS it has access to. Then it maps those memory segments onto physical memory. So let's say process A has its executable code, which, remember, is located at the virtual address 0x80000000, but its physical address is actually 0x0012a000. When it tries to access location, say, 0x80000004, the MMU says "oookay *wink*" and returns the memory in location 0x0012a004.

Now, let's say that process B gets swapped in. The stack pointer and the instruction pointer are changed. The MMU state is also changed. So now virtual location 0x80000000 points to, say, physical location 0x03002000. Bingo! the two processes will never even see each other.

A few other concepts stem from this. First of all, if the memory segment allocated for the stack is 65536 bytes long, and the process tries to over- or under-run it, there'll be an error, since the location 0x7fffffff doesn't actually exist (i.e. it's not mapped to physical memory). And since there's no way for the program to access physical rather than virtual addresses, functionally there's no way for it to ever affect another process (at least, by overwriting its memory). The idea of swapping to disk stems from all of this, too: the MMU manager might decide to put some data to disk from physical memory, and remove its mapping from the MMU. Then, when the program actually tries to access that virtual memory, the MMU throws an error (because it doesn't have a listing for that virtual address) but the MMU manager intercepts that error, puts the data back from the disk to physical memory, gives the MMU the updated mapping, and tells the MMU to try again. This time, of course, it finds it just fine.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
my understanding was that virtual memory is using the swap file, which is what your search turned up, and that what you were really looking for [and what Sneftel dsescribed quite well] is virtual address space. Virtual memory and virtual address space are very different things, but like sneftel said, a lot of people get them confused.

Share this post


Link to post
Share on other sites
Sneftel - Thanks for the information!
i used google and a few keywords from your post and i came across these Two Wiki's

Very interesting!

But another question, how does this work with cacheing?
in a cache line, it reads ahead to help speed up consecutive entries. (at least thats as much as i know about it). with the MMU, when you are trying to read at say 9000 instead of 8FFF, 9000 would have been stored in a cache line. does the MMU stop the request before it gets to the cache?

Thank you for your information,
DENC

Share this post


Link to post
Share on other sites
Quote:
Original post by snk_kid
i wouldn't call stacks data structures, i would say its an abstract data type (ADT) because they can be implementated in number of ways, the concept is beyond a programming language.

As anist points out the stack in the context of hardware still has notion of the concept it just implementated differently


What's the difference between an ADT and a data structure? I see ADT as an obsolete term for data structure.

Share this post


Link to post
Share on other sites
An ADT is just a data structure abstractified. An ADT is an object whose behaviour can be exactly defined by the operations you can perform on it. There is a full definition, but that's the compact one I was taught. It's where you don't care how it works, merely that it does. Think Turing machines; you don't care how they work, as long as they work as specified.

Share this post


Link to post
Share on other sites
Quote:
Original post by Magmai Kai Holmlor
Quote:
Original post by snk_kid
i wouldn't call stacks data structures, i would say its an abstract data type (ADT) because they can be implementated in number of ways, the concept is beyond a programming language.

As anist points out the stack in the context of hardware still has notion of the concept it just implementated differently


What's the difference between an ADT and a data structure? I see ADT as an obsolete term for data structure.


it can be very subtle depending on what context & point of view you look at them, but there is a significant & distinct difference between the two.

a data structure has a specific representation, it's representation does not vary. Most common examples of data structures are arrays, linked-lists, hash tables, binary search trees etc. The key here is representation is the most significant.

an abstract data type (ADT) such as stack has no specific representation or makes no reference to one in its definition, it's representation can vary but it's operations are specific and they do not vary. The key here is representation is insignificant, operations are the most significant.

For stack you could use any of the above or other data structures to implemenat it, you could use an array or a linked-list it makes no difference except for various trade-offs you get depending on which representation you commit to. Usually there is one specific data structure that gives you an over-all good/average trade-offs for all the ADT's operations.

This is where the word "abstract" comes into play in ADTs, you abstract & encapsulate the variant which is the representation so clients only see the operations that do not vary, they can or someone else can easily use & pass around a stack with a particular representation that conforms to the requirements of the ADT with-out having to change client's code that much or at all.

So an ADT is really a higher level entity than a data structure and ADTs are usually implemenated with some kind of data structure. It doesn't mean that one is better than the other it just means there different.

There are alot of ways to write ADTs the traditional OO way in C++ is to write an interface or abstract base class (ABC) where sub-types with a specific representation derive and implement the interface.

A more modern way i've seen and is more efficent is STL's example of a stack type using templates, again it doesn't have a specific representation but can default to one that gives a good over-all trade-offs for all it's operations, its the container type deque. You can change stack's representation to use any data structure or ADT that implements the concept of sequence and the operations that stack expects.

I can see what your saying thou if you look at it from a different point of view it looks like a data structure.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this