Larry Osterman's WebLog

Confessions of an Old Fogey
Blog - Title

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

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

  • Comments 19

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, 4
MOV [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 :)

 

  • Can stacks just go left-right and avoid the confusion completely?

    I strongly prefer trees growing down. For whiteboarding, having a root at the top with room to grow down is key. Nodes are more likely to be added to the bottom than the top.
  • Peter. If they go left-right, which is the top of the stack?
  • It's the end with the arrow marked 'TOP' ;-)

    I'll admit I've only ever used processors or platforms where the stack grows down (from higher-numbered addresses to lower ones). So far that's Z80, x86, 68k on a development board, and Windows CE running on x86, SH3 and ARM. In the latter case the CPU has support for growing stack either way because it doesn't have PUSH instructions, but by convention you use a stmdb instruction (store multiple, decrement before) to set up your stack frame in the prologue, and an ldmia (load multiple, increment after) to tear down the stack - and often you store the link register lr (r14) in the prologue and load it straight into pc to perform the return.

    I have the horrible feeling I use the term 'higher' interchangeably for meaning caller and callee - clearly the perfect representative sample.
  • Why grow down? Well, back in the day (8080's etc), everything is physical - no virtual memory. So, your physical memory is your total usable address space.

    Once your 'one time' memory allocations are out of the way, you basically have *two* different consumers of memory - heap and stack. But, there's no easy way to decide ahead of time which will be 'bigger'.

    The easiest way to ensure that the available memory can be easily shared and traded between the two is to have one grow up from bottom, and the other grow down from top. Flip a coin to decide which is which, and you end up with stacks that grow down.

    Today, of course, the point is entirely moot - although *a* stack has to be contiguous, programs run with more than one stack, and heaps can be fragmented. Virtual memory allows also you to place these things 'far apart' even if your physical memory wouyld not support it.
  • It's hard to gauge how much of a security benefit switching the stack direction would have. Essentially, it swaps the location between the caller and callee for where the buffer overflow is needed to perform an exploit. It may close a lot of existing holes but then open up new holes that are currently not exploitable. As we further vet code with our existing stack model the benefits of switching decline. We'd be moving from a model that is very well tested to a model that is theoretically more secure but little tested.
  • Thanks for the info M.
    And you're absolutely right Nicholas. I wasn't advocating the swap, as you pointed out, and as I mentioned, it doesn't make stack based exploits impossible, it just changes them.

    And it does nothing to stop vtable smashing, or other heap based exploits.
  • This of course also makes an assumption about how you draw memory on your white-board. Is the 0 address at the top or the bottom? By simply repositioning the '0' address, you can get stacks to visually grow up or down, regardless of which way the numbers are going.

    I have even seen poeple who insist on the stack growing down, and thus for architectures, where it doesn't, they simply move '0' to the top, so that down==add.
  • Just to my 2c.
    On IA64 stack do grow in both directions. CPU 'spills' registers in one direction and you use it from the other. (sorry for such non-technical info ;)
    So the arguments are over ;)
  • We want sequencial values to progress downward but positive vectors to point upward. Also, "real world" stacks almost always grow upward, since gravity and friction tend to make the bottom item hard to pop.

    The strangeness of little-endian results from a similar conflict: sequencial values should progress rightward, but increasingly significant digits should progress leftward.
  • I can think of one potential benefit to stacks growing downwards. If one register points to the lowest usable address (think SS) and another register contains a nonnegative value giving the offset to the current top of stack (think SP) then stack overflow can be detected automatically when SP is bumped downwards from 0. If stacks grow upwards then automatic detection is still possible (when SP is bumped upwards to 0, i.e. stack overflow == integral overflow) but then the value of SS and initial value of SP has to be fudged.

    There was some early IBM machine where index registers did negative indexing instead of positive indexing. Index registers were so difficult to use that IBM's compilers generated object code doing ordinary arithmetic for array indexing, totally ignoring the existence of index registers. This lesson was probably remembered for a while when deciding on such matters as not making stacks unnecessarily complicated.

    In modern times, playing games with SS and SP is not considered an insurmountable difficulty, so maybe the reason for stacks to still grow down is just tradition instead of difficulty.

    Regarding trees, Knuth mentions in one of his books that in the first edition he drew trees with the root at the bottom and leaves at the top, and lots of readers complained. In the second edition and in other subsequent volumes, he drew trees with the root at the top and leaves at the bottom, conforming to convention.
  • When I’m debugging assembly code, my stacks grow down so I can start at the top of the page and add a line when pushing.

    When I’m drawing trees, they either grow down (again, so I can add at the leaves), or right (think Explorer, or better yet, Norton Commander), depending on where I have more free space.

    On a related note, how do your bitmaps grow? Many would argue that it is natural for bitmaps to be ordered the same as text (in European terms — top-down and left-to-right). Others would say graph axes are usually directed left-to-right and bottom-up.

    So we end up with Windows where screen coordinates grow top-down and bitmap coordinates grow bottom-up (although there is some limited top-down bitmap support).
  • Centaur: Yes, and think about 1 more dimension: which coordinate system do you use? My head goes around every time I export data from 3DSMAX (right-handed coordinates) to DirectX (left-handed), while trying to match the data with a paper geographical map that has traditional geographical coordinates, which have the axes reversed, in order for the export not to be too simple... :-)

    (For the record: My stacks grow upwards (usually, but it depends also on the amount of free space on paper), trees have roots always on top.)
  • The bitmap confusion is an OS/2-ism. Windows inherited device-independent bitmaps from OS/2, where the default coordinate system had (0,0) at the bottom left.
  • My trees always start at the top and grow down... I really just draw it as I visualize it.
  • As mentioned previously, on IA64 stacks will grow in both directions; for anyone who is interested I have a related article on my blog which illustrates this point <a href="http://blogs.msdn.com/joshwil/archive/2004/04/12/111638.aspx">http://blogs.msdn.com/joshwil/archive/2004/04/12/111638.aspx</a>.
Page 1 of 2 (19 items) 12