What is a stack?

A stack is a data structure that follows a LIFO (last in, first out) element adding order.

• This means that when you remove an element from the stack, the most recently added one will be removed first.
• Likewise, the first added element, is the last one to go.

How is a stack used?

There are many different uses for the stack data structure, but the one focused on here is the hardware stack.

This is what your computer uses for memory that is allocated towards applications.

There is also the heap, which is similar but has different uses in the software context.

How is memory in the hardware stack allocated?

That depends!

Lets take an example from C.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

#include <stdio.h>
	
int function(int y)
{
	int x = 1;
	return x + y;
}

int main(void)
{
	int y = 1;
	printf("%d\n", function(y));

	return 0;
}

What’s happening here?

Well, it’s simple, each time a function is called, (let’s start with main()), a stack frame is created.

This is a chunk of memory that contains everything required in the function, within this stack frame is every variable in the function.

Entering the main function, here is what a simplified view of the stack would look like:

Next we go into printf which calls function(), and the stack would look like:

What does this matter?

Knowing how the stack works is very important when working in embedded, and low-level development.

It’s important that you know exactly how your computer is doing things in the background, so you can code accordingly, and diagnose issues when they come up.

What else?

Well, there are two different ways that a processor will handle a stack.

• Growing upwards
• Growing downards

What does it mean if a stack is growing upwards?

• Well it’s simple.
• This means that the address of the first element (or the lowest element) in the stack is the lowest possible memory address.
• For this example, lets say that the address is 0x0000
• Anything else that will be added to the stack will increase the memory address.
• The second element would be at 0x0001, the third would be at 0x0002, etc.
• This is a gross oversimplification, however it is a good representation.

What about downwards?

• Similar to growing upwards, however the address of the first (or lowest) element in the stack is at the highest possible memory addrses.
• Let’s say the address of the first element is 0xFFFF.
• Anything else that will be added to the stack will lower the memory address.
• The second element would be 0xFFFE, the third would be at 0xFFFD, etc.

Now that we know this. Let’s find out whether my system’s stack grows up down.

The code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

#include <stdio.h>
#include <stdbool.h>

bool upordown(int* other)
{
	int x = 0;
	if (!other)
		return upordown(&x);
	else
		return &x > other;
}

int main(void)
{
	printf("%s\n", upordown(NULL) ? "Up" : "Down");

	return 0;
}

Download: code

How does this code work?

You might be asking, why don’t you just declare two variables and check their addresses in a single function.

• Firstly, you would need to specify those variables with volatile so signify to the compiler that these variables shouldn’t be optimized by the compiler.
  • GCC (or any C compiler) will optimize everything to the best of its ability, which includes the positions of variables on the stack.
• Secondly, the addresses and position of these variables on the stack are not guaranteed.
• By using a recursive function, we create a new stack frame which guarantees a push onto the stack.

This code looks a little complex, so let’s dissect what’s happening here.

In main() we have a simple ternary expression that evaluates to “Up” if upordown returns true, and “Down”, if it returns false.

We’re passing NULL to upordown because it expects a pointer.

As we move into upordown, we can see we check if other is NULL. Since it is, we call it recursively, while passing the address of x along with it.

Now we compare &x > other, and it returns false. Which means the stack grows downwards.

Why does this work?

The first call to upordown generates a stack frame with int x in it.

Down:

Up:

Then we recursively call upordown and pass in &x. So now we have ANOTHER stack frame, with a new x, and the address of the last x.

Down:

Up:

If the stack grows down:

• Let’s say that the first stackframe is at address 0xFFFE, and the x is at address 0xFFFD.
• In the second call, the stackframe is at address 0xFFFC, and the x is at address 0XFFFB.
• The comparison evalutes out to 0xFFFB > 0xFFFD. This is false, so we know that the stack grows downwards.

If the stack grows up:

• The first stackframe is at address 0x0001, and the x is at address 0x0002.
• In the second call, the stackframe is at address 0x0003, and the x is at address 0x0004.
• The comparison evaluates out to 0x0004 > 0x0002. This is true, so we know that the stack grows upwards.

In my case (and really for everyone’s case), this will come out to show that the stack in fact, grows downwards.