What Exactly Is Program Stack's Growth Direction

what exactly is program stack's growth direction?

The book is not inconsistent; each drawing shows higher addresses at the top.

The first drawing illustrates a stack that grows downward. The caller pushes parameters onto the stack, then calls the new function. The act of calling pushes the return address onto the stack. The callee then pushes the current value of the base pointer onto the stack, copies the stack pointer into the base pointer, and decrements the stack pointer to make room for the callee's local variables.

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

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.

Does stack grow upward or downward?

The behavior of stack (growing up or growing down) depends on the application binary interface (ABI) and how the call stack (aka activation record) is organized.

Throughout its lifetime a program is bound to communicate with other programs like OS. ABI determines how a program can communicate with another program.

The stack for different architectures can grow the either way, but for an architecture it will be consistent. Please check this wiki link. But, the stack's growth is decided by the ABI of that architecture.

For example, if you take the MIPS ABI, the call stack is defined as below.

Let us consider that function 'fn1' calls 'fn2'. Now the stack frame as seen by 'fn2' is as follows:

direction of     |                                 |
  growth of      +---------------------------------+ 
   stack         | Parameters passed by fn1(caller)|
from higher addr.|                                 |
to lower addr.   | Direction of growth is opposite |
      |          |   to direction of stack growth  |
      |          +---------------------------------+ <-- SP on entry to fn2
      |          | Return address from fn2(callee) | 
      V          +---------------------------------+ 
                 | Callee saved registers being    | 
                 |   used in the callee function   | 
                 +---------------------------------+
                 | Local variables of fn2          |
                 |(Direction of growth of frame is |
                 | same as direction of growth of  |
                 |            stack)               |
                 +---------------------------------+ 
                 | Arguments to functions called   |
                 | by fn2                          |
                 +---------------------------------+ <- Current SP after stack 
                                                        frame is allocated

Now you can see the stack grows downward. So, if the variables are allocated to the local frame of the function, the variable's addresses actually grows downward. The compiler can decide on the order of variables for memory allocation. (In your case it can be either 'q' or 's' that is first allocated stack memory. But, generally the compiler does stack memory allocation as per the order of the declaration of the variables).

But in case of the arrays, the allocation has only single pointer and the memory needs to be allocated will be actually pointed by a single pointer. The memory needs to be contiguous for an array. So, though stack grows downward, for arrays the stack grows up.

stack growth direction

The stack may not grow up or down.

Each stack frame can potentially be allocated at random points inside the heap.

This is actually done in several OS to try and prevent stack smashing by malicious code.

The concept of a stack growing towards the heap is just an easy way to teach the concept of a stack (and of course early implementations did work this way as it was simple (no need to make something harder than you need when nobody is trying to break you)).

Why do stacks typically grow downwards?

As to the historic rationale, I can't say for certain (because I didn't design them). My thoughts on the matter are that early CPUs got their original program counter set to 0 and it was a natural desire to start the stack at the other end and grow downwards, since their code naturally grows upward.

As an aside, note that this setting of the program counter to 0 on reset is not the case for all early CPUs. For example, the Motorola 6809 would fetch the program counter from addresses 0xfffe/f so you could start running at an arbitrary location, depending on what was supplied at that address (usually, but by no means limited to, ROM).

One of the first things some historical systems would do would be to scan memory from the top until it found a location that would read back the same value written, so that it would know the actual RAM installed (e.g., a z80 with 64K address space didn't necessarily have 64K or RAM, in fact 64K would have been massive in my early days). Once it found the top actual address, it would set the stack pointer appropriately and could then start calling subroutines. This scanning would generally be done by the CPU running code in ROM as part of start-up.

With regard to the stacks growth, not all of them grow downwards, see this answer for details.

Confusion about stack growth and addressing

essentially there are 3 types of memory you use in programming: static, dynamic/heap and stack.

Static memory is pre-allocated by the compiler and consist of the constants and variables declared statically in your program.

Heap is the memory which you can freely allocate and release

Stack is the memory which gets allocated for all local variables declared in a function. This is important because every time you call the function a new memory for its variables is allocated. So, that every call to a function will assure that it has its own unique copy of the variables. And every time you return from the function the memory gets freed.

It absolutely does not matter how the stack is managed as soon as it follows the above rules. It is convenient however to have program memory to be allocated in the lower address space and grow up, and the stack to start from a top memory space and grow down. Most systems implement this scheme.

In general there is a stack pointer register/variable which points so the current stack address. when a function gets called it decrease this address by the number of bytes it needs for its variables. when it calls the next function, this new one will start with the new pointer already decreased by the caller. When the function returns it restores the pointer which it started from.

There could be different schemes but as far as I know, mips and i86 follow this one.

And essentially there is only one virtual memory space in the program. This is up to the operating system and/or compiler how to use it. The compiler will split the memory in the logical regions for its own use and handle them, hopefully, according to the calling conventions defined in the platform documents.

So, in our example, v and i are allocated on the function stack. cout is static. every new int allocate space in heap. v is not a simple variable but a struct which contains fields which it needs to manage the list. it needs space for all these internals. So, every push_back modifies those fields to point to the allocated 'int' in some way. push_back() and back() are function calls and allocate their own stacks for internal variables to not interfere with the top function.

Why does the stack address grow towards decreasing memory addresses?

First, it's platform dependent. In some architectures, stack is allocated from the bottom of the address space and grows upwards.

Assuming an architecture like x86 that stack grown downwards from the top of address space, the idea is pretty simple:

===============     Highest Address (e.g. 0xFFFF)
|             |
|    STACK    |
|             |
|-------------|  <- Stack Pointer   (e.g. 0xEEEE)
|             |
.     ...     .
|             |
|-------------|  <- Heap Pointer    (e.g. 0x2222)
|             |
|    HEAP     |
|             |
===============     Lowest Address  (e.g. 0x0000)

To grow stack, you'd decrease the stack pointer:

===============     Highest Address (e.g. 0xFFFF)
|             |
|    STACK    |
|             |
|.............|  <- Old Stack Pointer (e.g. 0xEEEE)
|             |
| Newly       |
| allocated   |
|-------------|  <- New Stack Pointer (e.g. 0xAAAA)
.     ...     .
|             |
|-------------|  <- Heap Pointer      (e.g. 0x2222)
|             |
|    HEAP     |
|             |
===============     Lowest Address    (e.g. 0x0000)

As you can see, to grow stack, we have decreased the stack pointer from 0xEEEE to 0xAAAA, whereas to grow heap, you have to increase the heap pointer.

Obviously, this is a simplification of memory layout. The actual executable, data section, ... is also loaded in memory. Besides, threads have their own stack space.

You may ask, why should stack grow downwards. Well, as I said before, some architectures do the reverse, making heap grow downwards and stack grow upwards. It makes sense to put stack and heap on opposite sides as it prevents overlap and allows both areas to grow freely as long as you have enough address space available.

Another valid question could be: Isn't the program supposed to decrease/increase the stack pointer itself? How can an architecture impose one over the other to the programmer? Why it's not so program dependent as it's architecture dependent?
While you can pretty much fight the architecture and somehow get away your stack in the opposite direction, some instructions, notably call and ret that modify the stack pointer directly are going to assume another direction, making a mess.

Who selects the ARM stack direction?

Ultimately it's the designers of the operating system who choose which direction the stack grows in.

If you want to create your own stack, and not rely on the one given to you by the OS, you can use whatever type of stack you choose. However, if you want to use the OS stack, you have no choice but to accept what the OS gives you.

The first OS that ran on ARM was Arthur, written by Acorn Computers. Arthur uses a growing-downwards stack, quite possibly because the developers who wrote Arthur were used to the stack on the 6502, which also grows downwards. (Arthur didn't last long, and was quickly replaced by RISC OS.)

There is a version of ARM Linux that runs on Acorn hardware - I still have a version of it on my 1995 Acorn Risc PC. I know that that version of the ARM Linux kernel makes calls into RISC OS for various purposes, so it has to use growing-downwards stacks as well. Other operating system developers quite probably followed the lead set by Acorn and/or the ARMLinux developers.

As for iOS, it appears to use a growing-downwards stack (the STMFD instructions here suggest that). I suspect the same is true for Android and Windows RT, but I haven't been able to verify this.

What Exactly Is Program Stack's Growth Direction