handmade.network » Wiki » Stack

Abstract

The stack is a thread-local (i.e. each thread has its own) block of memory that is used to temporarily store data. Data can be pushed (added) to and popped (removed) from the stack. Only the most recently pushed data can be popped from the stack (last in, first out). Because of its usefulness with regards to the programming of subroutines, many processors feature built-in support for a stack.

Implementation

Although processors have their own implementation of stack code, a simple implementation in C might look like this.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
thread_local char *stackPointer;

void CreateStack(size_t size) {
    // Start the stack pointer at the base of the block of memory.
    stackPointer = (char *) malloc(size);
}

void Push(void *data, size_t size) {
    // Copy the data onto the stack.
    memcpy(stackPointer, data, size);

    // Move the stack pointer past the data.
    // This means the next time we try to push data we won't overwrite this data!
    stackPointer += size;

    // TODO: Check we haven't gone over the end of the memory block.
}

void Pop(void *buffer, size_t size) {
    // Move the stack pointer to the start of the data we're about to read.
    stackPointer -= size;

    // ..and read the data into the buffer.
    memcpy(buffer, stackPointer, size);
}

...

int a = 3, b = 4, c = 7;
int out;

Push(a, sizeof(int));
Push(b, sizeof(int));
Push(c, sizeof(int));

Pop(&out, sizeof(int));
printf("%d\n", out); // Prints '7'.

Pop(&out, sizeof(int));
printf("%d\n", out); // Prints '4'.

Pop(&out, sizeof(int));
printf("%d\n", out); // Prints '3'.

Hands-On with 6502 Assembly

As noted above, many processors feature built-in support for a thread-local stack. The equivalent of the stackPointer from the example above, is stored in a register called SP. This makes sense, since registers are essentially the lowest-level form of thread-local storage.

Here we're take a look at how the primitive stack operations push and pop are handled on the 6502.

Setting SP

The stack pointer, SP, can be set using the TXS instruction (transfer the value of the X register to the stack pointer).

It's worth noting that the stack pointer register is only 8-bits wide - it can only store values between 0 and 255 - while the 6502 can access 64KB of memory. Since the most significant 8-bits of the pointer aren't stored, they have to be locked to a specific value. This means the stack on the 6502 has to reside in the memory block between 0x100 and 0x200.

1
2
LDX #8    ; Load 8 into the X register.
TXS       ; ..and store in the stack pointer.

PHA and PLA

The PHA instructions pushes the value of the accumulator register onto the stack.

Because the stack on the 6502 "grows down" the stack pointer will actually be decremented, rather than incremented, when a value is pushed onto it.

1
2
3
4
5
LDA #05   ; Store the integer '5' in the accumulator 
PHA       ; Push the accumulator onto the stack.
          ; SP is decremented from 8 to 7.
          ; The value of the accumulator, 5, is then stored at 0x0107.
          ; (Remember - the top 8 bits of the stack pointer's address are locked to 0x01!)

We are now free to modify the accumulator without worrying about the contents being lost.

We can then retrieve the value with the PLA instruction - which pops the most recently value pushed onto the stack into the accumulator.

1
2
PLA       ; The value at 0x0107 (SP | 0x0100) is loaded into the accumulator. A = 5.
          ; SP is incremented from 7 to 8.

One minor thing to note - if the stack pointer were to be 0 when the PHA instruction is executed, it would wrap around to 0xFF, causing the value to written to 0x01FF. But don't worry! As long as the memory there isn't already being used, all the values on the stack can still be popped off as usual, since when the pop instruction is executed with SP = 0xFF, it will overflow back to 0.

Subroutines

The stack is very useful for subroutines (functions/procedures).

Let's say the subroutine wants to return a value in the accumulator - but you've got a value in the accumulator you'd rather not have overwritten. Just push it onto the stack! Even if the subroutine uses the stack, your value will be safe (unless the stack size grows over 256 bytes).

1
2
3
4
5
LDA my_super_important_value
PHA
JSR evil_function ; Call the subroutine.
PLA
; The accumulator is set to my_super_important_value again!

Furthermore, the JSR (jump to subroutine) instruction uses the stack itself.

When the instruction is executed, the value of the program counter is pushed onto the stack before the processor jumps to the subroutine. Then, when the subroutine is finished, it executes the RTS (return from subroutine) instruction. This pops the old value of the program counter off the stack, returning to the calling location.

Use by High-Level Languages

Whenever you declare a variable as part of a function in C, the variable will actually be stored on the stack - only read into the CPU's registers when necessary.

Compilers will usually manipulate the stack pointer directly. At the start of a function, the stack pointer will be decremented (remember - stacks grow down on most processors) by the total size of all the variables the function needs. The variables on the stack are then read and written using memory accesses relative to the stack pointer. When the function exits, the stack pointer is incremented by the amount that was subtracted from it when the function was entered.

The parameters of a function are also read from the stack. They are pushed onto the stack before the return address.

Let's look at an example.

1
2
3
4
5
int RecursiveFactorial(int x) {
    if (x == 0) return 1;
    int y = x * RecursiveFactorial(x - 1);
    return y;
} 

Each time this function calls itself, space on the stack will be made for the x and y variables. And each time the function returns, the stack pointer will be incremented, so that the stack pointer is where it was before the function call started.

Call Stack

In a debugger, you're probably used to seeing a list of the functions that have been called to get to the position when you currently are. This "call stack" is being read from the processor's actual stack! As described above, the return addresses, function parameters and function variables are all stored on the stack. This is how the debugger knows where you are.