TLDR : When we say that the stack grows downwards, we mean that we write to the stack starting from the highest memory address to the lowest memory address allocated for the stack and we read from the lowest to the highest memory address allocated.

Among the computer systems folks, it’s widely accepted that the stack grows downwards.

What does this mean?

Background

A running process has several regions in the memory: read-only data, code, texts etc. Some of these regions don’t change over time (once written by the process they remain like that until the process is complete). Others are dynamic (they expand and shrink) and we don’t know their size until we run the program. This dynamic section of memory includes both the heap and the stack.

An OS doesn’t know in advance whether stack or heap will be used predominantly. Therefore, an OS must layout these two memory regions in a way that guarantees maximum space for both.

One way of solving this (which is our focus here) is putting the program, and its related data at the lowest addresses, then putting the dynamic area growing up, and the bottom of the stack at the very top of the available memory (highest addresses).

This way, the limit on the size of the stack is equal to the total size of available memory - (the size of the program + heap).

$$Stack_{size} = Memory_{size} - (Program_{size} + Heap_{size})$$

Furthermore, while different architectures, design their stacks differently, Chapter 37 of Intel CS2 teaches us that Intel chose to grow the stack downhill to simplify indexing into the stack from the user’s program.

As we have seen above, this has two main advantages:

  1. Laying out the stack and the heap in opposite directions in memory ensures the maximum available space for each. In the case values written on the stack are overriding values written on the heap, we know we have run out of memory.
  2. If the stack grows downwards, all addresses within the stack will have a positive offset in relation to the stack pointer. Conversely, if the stack were to grow upwards, all practical offsets from the stack pointer would be negative.

Mental Model.

In-Memory Layout of a Program (Process) is commonly visualized as: RAM simple vis In this case, we see that the stack direction is literally pointing downwards. Alternatively, we could visualize it as: RAM alt vis While the above diagram could deceive us into thinking that the stack is growing upwards, its stack is still growing downwards. “Growing” the stack/heap simply means allocating memory from the stack/heap space for the program that requested it. To grow the stack downward, we simply mean we allocate space with the stackpointer advancing toward lower memory.

Visual Example.

Suppose we need to add int 4 into the stack.

First, we create space on the stack by subtracting 4 bytes from the stack pointer. Creating space We then write to this space we just created. Write content

Since it’s a stack, the stack pointer points to the latest added item in the stack, so reading it is easy. We simply read whatever value the stack pointer is pointing it to.

If we were to imagine a linear stack, it would look like this:

Linear stack simple vis

Reading the value at sp means we get 0x00000004, and once we are done with this value we free up this stack space by incrementing sp

Done reading The sp is pointing to the bottom of the stack meaning that we are done reading, and we have freed up the stack space. Even though it’s not rewritten yet, the stack pointer indicates that this space is available for overwriting.

Code example

To make this concrete, we are gonna read values from two registers, write them to the stack, erase the values from the registers, then restore the registers with values from the stack, all in risc-v assembly.

set up

.globl main
.text
main:
	# simple code that loads the address of the stack into a register, 
	# pushes two integers (4 and 5 for example) and 
	# then pops these integers again
	
    # load immediates
	addi t1, zero, 4
	addi t1, zero, 5

store 4 and 5 in the stack

    # store the integers

	# create space on the stack
	addi sp, sp, -4
	# store t1 in the stack
	sw t1, 0(sp)
	# create space on the stack
	addi sp, sp, -4
	# store t2 in the stack
	sw t2, 0(sp)

reset registers

    # rewrite registers t1, and t2
	addi t1, zero, 0
	addi t2, zero, 0

retrieve values from the stack

    # pop the ints from the stack
	lw t2, 0(sp)
	# increment sp
	addi sp, sp, 4
	# pop into t2
	lw t1, 0(sp)
	addi sp, sp, 4

full code

.globl main
.text
main:
	# simple code that loads the address of the stack into a register, 
	# pushes two integers (4 and 5 for example) and 
	# then pops these integers again
	# load immediates
	addi t1, zero, 4
	addi t2, zero, 5
	
	# store the integers
	# create space on the stack
	addi sp, sp, -4
	# store t1 in the stack
	sw t1, 0(sp)
	# create space on the stack
	addi sp, sp, -4
	# store t2 in the stack
	sw t2, 0(sp)
	
	# rewrite registers t1, and t2
	addi t1, zero, 0
	addi t2, zero, 0
	
	# pop the ints from the stack
	lw t2, 0(sp)
	# increment sp
	addi sp, sp, 4
	# pop into t2
	lw t1, 0(sp)
	addi sp, sp, 4