Mary, Mary, quite contrary, how does your stackframe grow?

So there was a discussion on an internal mailing list yesterday, and Raymond popped in with the following quote:

The problem is that some people draw stacks growing downward (so "top of stack" is lowest) and others growing upward (so "top of stack" is highest).  The documentation here wants "top of stack" to be highest.  In other words, "higher" = "closer to the point the exception is raised".  The second interpretation is probably more common.

People also talk about a calling function being "higher" than a called function. This is directly in conflict the second interpretation above. Yet this terminology is also very common.

He brings up an interesting point.  Which way DO stacks grow?

On Intel processors, the PUSH EAX instruction is equivalent to:

SUB ESP, 4MOV [ESP], EAX

So on Intel processors, stacks grow down.  Whenever I’m writing calls stacks that’s the way I draw them – the caller is on top, the callee is on the bottom.  But other machines have stacks that grow UP, not DOWN.  For example, the Decsystem-20’s stack grows up (I first learned assembly language programming on the Dec-20 – it’s still my favorite instruction set).  So the fact that my stacks grow down is clearly not related to the language I first learned.  On the other hand, I spent many years writing exclusively in x86 assembly (from 1984 to 1989, more or less), so it may be that that’s what I’m familiar with.

Interestingly enough, it can be argued (pretty strongly) that stacks that grow down are a cause of security holes (or rather stacks that grow in a direction opposite of array accesses).  Since array accesses typically go up in memory, and stacks grow down, the area where they cross has huge amounts of potential.  If stacks grew up and arrays grew up, then it would be much harder (not impossible, mind you, but much harder) for easy coding mistakes to result in buffer overruns (wcscpy(stackbuffer, inputstring) isn’t as much a security hole if the return address is BELOW the stackbuffer instead of above the stackbuffer).  Unfortunately, it’s WAY too late for this behavior to change; to change this behavior would require a wholesale move away from x86 compatible platforms onto another platform, every existing application would break, etc.  And I’m sure that the Intel engineers who designed the 8080 had a good reason for making their stacks grow down – that was a decision made almost 30 years ago, back in a different era.

Oh, and btw.  There’s a related question to the stack question: How do your trees grow?  My trees (binary, n-ary, etc) are rooted at the top of the whiteboard and grow down.  Other people’s trees are rooted at the bottom of the whiteboard and grow up.  I don’t know if the two are related, but…

 

Edit: Raymond pointed out that the SUB comes first on the PUSH instruction :)