What is the direction of stack growth in most modern systems?

Question

I am preparing some training materials in C and I want my examples to fit the typical stack model.

What direction does a C stack grow in Linux, Windows, Mac OSX (PPC and x86), Solaris, and most recent Unixes?

Medical

A why downwards version: #2036068 – Surber

Answer 1

Stack growth doesn't usually depend on the operating system itself, but on the processor it's running on. Solaris, for example, runs on x86 and SPARC. Mac OSX (as you mentioned) runs on PPC and x86. Linux runs on everything from my big honkin' System z at work to a puny little wristwatch.

If the CPU provides any kind of choice, the ABI / calling convention used by the OS specifies which choice you need to make if you want your code to call everyone else's code.

The processors and their direction are:

• x86: down.
• SPARC: selectable. The standard ABI uses down.
• PPC: down, I think.
• System z: in a linked list, I kid you not (but still down, at least for zLinux).
• ARM: selectable, but Thumb2 has compact encodings only for down (LDMIA = increment after, STMDB = decrement before).
• 6502: down (but only 256 bytes).
• RCA 1802A: any way you want, subject to SCRT implementation.
• PDP11: down.
• 8051: up.

---

Showing my age on those last few, the 1802 was the chip used to control the early shuttles (sensing if the doors were open, I suspect, based on the processing power it had :-) and my second computer, the COMX-35 (following my ZX80).

PDP11 details gleaned from here, 8051 details from here.

The SPARC architecture uses a sliding window register model. The architecturally visible details also include a circular buffer of register-windows that are valid and cached internally, with traps when that over/underflows. See here for details. As the SPARCv8 manual explains, SAVE and RESTORE instructions are like ADD instructions plus register-window rotation. Using a positive constant instead of the usual negative would give an upward-growing stack.

The afore-mentioned SCRT technique is another - the 1802 used some or it's sixteen 16-bit registers for SCRT (standard call and return technique). One was the program counter, you could use any register as the PC with the SEP Rn instruction. One was the stack pointer and two were set always to point to the SCRT code address, one for call, one for return. No register was treated in a special way. Keep in mind these details are from memory, they may not be totally correct.

For example, if R3 was the PC, R4 was the SCRT call address, R5 was the SCRT return address and R2 was the "stack" (quotes as it's implemented in software), SEP R4 would set R4 to be the PC and start running the SCRT call code.

It would then store R3 on the R2 "stack" (I think R6 was used for temp storage), adjusting it up or down, grab the two bytes following R3, load them into R3, then do SEP R3 and be running at the new address.

To return, it would SEP R5 which would pull the old address off the R2 stack, add two to it (to skip the address bytes of the call), load it into R3 and SEP R3 to start running the previous code.

Very hard to wrap your head around initially after all the 6502/6809/z80 stack-based code but still elegant in a bang-your-head-against-the-wall sort of way. Also one of the big selling features of the chip was a full suite of 16 16-bit registers, despite the fact you immediately lost 7 of those (5 for SCRT, two for DMA and interrupts from memory). Ahh, the triumph of marketing over reality :-)

System z is actually quite similar, using its R14 and R15 registers for call/return.

Tuchun

To add to the list, ARM can grow in either direction, but can be set to one or the other by a particular silicon implementation (or can be left selectable by software). The few I've dealt with have always been in grow-down mode. – Patsypatt

Wow, this is revelatory - I've always assumed it was down for every architecture. Linked lists! – Liebig

I think PPC is selectable, but it grows down on OS X (since the 68k that Mac ran on before had a downward stack.) – Margetts

PDP11 was downward, according to history.dcs.ed.ac.uk/archive/docs/psrthesis/psrthesis.html – Margetts

In the little bit of the ARM world I've seen so far (ARM7TDMI) the stack is entirely handled in software. Return addresses are stored in a register which is saved by software if needed, and pre-/post-increment/decrement instructions allow to put it and other stuff on the stack in either direction. – Dividend

@Dividend - you are right - my mistake. It's endianness used by the ARM that's selectable, but can be fixed one way or the other by the silicon OEM. – Patsypatt

PPC stack growth is compiler convention (stack pointer is just an ordinary register), but it's been down in every implementation I've ever seen. – Anthracoid

the 8051 micro-controller family grows up in the 128 byte "IDATA" portion of memory, and most local variables are compiled to use static locations in the larger external memory. – Phosphatase

One the HPPA, the stack grew up! Fairly rare among reasonably modern architectures. – Churning

For the curious, here is a good resource on how the stack works on z/OS: www-03.ibm.com/systems/resources/Stack+and+Heap.pdf – Hyperphagia

A Century for you :) – Shoemake

I am not sure what I make of the expression a stack grows downward (as opposed for example to it grows eastward). Does "downward" mean that the value of the stack pointer gets decreased with a push operation and increased with a pop operation? – Jointress

@René, in this context, downward means toward lower memory addresses. – Tuchun

Answer 2

In C++ (adaptable to C) stack.cc:

static int
find_stack_direction ()
{
    static char *addr = 0;
    auto char dummy;
    if (addr == 0)
    {
        addr = &dummy;
        return find_stack_direction ();
    }
    else
    {
        return ((&dummy > addr) ? 1 : -1);
    }
}

Hyperesthesia

Wow, it's been a long time since I've seen the "auto" keyword. – Tuchun

(&dummy > addr) is undefined. The result of feeding two pointers to a relational operator is defined only if the two pointers point within the same array or structure. – Saxecoburggotha

Trying to investigate the layout of your own stack -- something which C/C++ don't specify at all -- is "unportable" to begin with, so I wouldn't really care about that. It looks like this function will only work correctly once, though. – Ingratiating

There's no need to use a static for this. Instead you could pass the address as an argument to a recursive call. – Intersection

plus, by using a static, if you call this more than once, the subsequent calls may fail... – Lobbyist

That last problem could presumably be fixed with something like addr = &dummy; int x = find_stack_dir(); addr = 0; return x; in the if case so that every invocation did the two-step recursion. Or only calling the function once and caching the result, assuming stack direction doesn't change midstream: that would be a weird architecture :-) – Tuchun

Unnecessarily too complex, non-reentrant, and UB-invoking. – Mapping

@PSkocik also it is the only code example in 10 years. Though it wasn't a great solution even 10 years ago. – Hyperesthesia

You can use std::less and remove auto in C++11. – Denigrate

Answer 3

Just a small addition to the other answers, which as far as I can see have not touched this point:

Having the stack grow downwards makes all addresses within the stack have a positive offset relative to the stack pointer. There's no need for negative offsets, as they would only point to unused stack space. This simplifies accessing stack locations when the processor supports stackpointer-relative addressing.

Many processors have instructions that allow accesses with a positive-only offset relative to some register. Those include many modern architectures, as well as some old ones. For example, the ARM Thumb ABI provides for stackpointer-relative accesses with a positive offset encoded within a single 16-bit instruction word.

If the stack grew upwards, all useful offsets relative to the stackpointer would be negative, which is less intuitive and less convenient. It also is at odds with other applications of register-relative addressing, for example for accessing fields of a struct.

Transcend

Answer 4

The advantage of growing down is in older systems the stack was typically at the top of memory. Programs typically filled memory starting from the bottom thus this sort of memory management minimized the need to measure and place the bottom of the stack somewhere sensible.

Volatile

Not an 'advantage', a tautology really. – Carencarena

Not a tautology. The point is to have two growing memory regions not interfering (unless memory full anyway), as @valenok pointed out. – Unnecessarily

Answer 5

Stack grows down on x86 (defined by the architecture, pop increments stack pointer, push decrements.)

Margetts

Answer 6

In MIPS and many modern RISC architectures (like PowerPC, RISC-V, SPARC...) there are no push and pop instructions. Those operations are explicitly done by manually adjusting the stack pointer then load/store the value relatively to the adjusted pointer. All registers (except the zero register) are general purpose so in theory any register can be a stack pointer, and the stack can grow in any direction the programmer wants

That said, the stack typically grows down on most architectures, probably to avoid the case when the stack and program data or heap data grows up and clash to each other. There's also the great addressing reasons mentioned sh-'s answer. Some examples: MIPS ABIs grows downwards and use $29 (A.K.A $sp) as the stack pointer, RISC-V ABI also grows downwards and use x2 as the stack pointer

In Intel 8051 the stack grows up, probably because the memory space is so tiny (128 bytes in original version) that there's no heap and you don't need to put the stack on top so that it'll be separated from the heap growing from bottom

You can find more information about the stack usage in various architectures in https://en.wikipedia.org/wiki/Calling_convention

See also

• Why does the stack grow downward?
• What are the advantages to having the stack grow downward?
• Why do stacks typically grow downwards?
• Does stack grow upward or downward?

Brutus

Answer 7

On most systems, stack grows down, and my article at https://gist.github.com/cpq/8598782 explains WHY it grows down. It is simple: how to layout two growing memory blocks (heap and stack) in a fixed chunk of memory? The best solution is to put them on the opposite ends and let grow towards each other.

Thesda

that gist seems to be dead now :( – Museum

@Museum - I can get to it – Ingres

Answer 8

It grows down because the memory allocated to the program has the "permanent data" i.e. code for the program itself at the bottom, then the heap in the middle. You need another fixed point from which to reference the stack, so that leaves you the top. This means the stack grows down, until it is potentially adjacent to objects on the heap.

Workingwoman

Answer 9

This macro should detect it at runtime without UB:

#define stk_grows_up_eh() stk_grows_up__(&(char){0})
_Bool stk_grows_up__(char *ParentsLocal);

__attribute((__noinline__))
_Bool stk_grows_up__(char *ParentsLocal) { 
    return (uintptr_t)ParentsLocal < (uintptr_t)&ParentsLocal;
}

Mapping