The Stack

Section 10.2 The Stack

The stack is used extensively for the interface between a calling function and called function, local variables created within a function, and saving items within a function. Before describing how these things are done, we need to understand what stacks are and how they are used.

🔗

A stack is an area of memory for storing data items together with a pointer to the “top” of the stack. Informally, you can think of a stack as being organized very much like a stack of dinner plates on a shelf. We can only access the one item at the top of the stack. (And, yes, if you pull out a plate from somewhere with the stack, you will probably break something.) There are two fundamental operations on a stack:

push data-item: This causes the data-item to be placed on the top of the stack and moves the stack pointer to point to this latest item.
pop location: The data item on the top of the stack is moved to location and the stack pointer is moved to point to the next item left on the stack.

🔗

So the stack is a “last in, first out” (LIFO) data structure. That is, the last thing to be pushed onto the stack is the first thing to be popped off.

🔗

To illustrate the stack concept let us use our dinner plate example. Say we have three differently colored dinner plates, a red one on the dining table, a green one on the kitchen counter, and a blue one on the bedside table. Now we will stack them on the shelf in the following way:

push red plate
push green plate
push blue plate

🔗

At this point, our stack looks like:

🔗

Now if we perform the operation:

pop kitchen-counter

🔗

we will have a blue plate on our kitchen counter, and our stack will look like:

🔗

A stack must be used according to a very strict discipline. Within any function:

Always push an item onto the stack before popping anything off.
Never pop more things off than you have pushed on.
Always pop everything off the stack.

🔗

If you have no use for the item(s) to be popped off, you may simply adjust the stack pointer. This is equivalent to discarding the items that are popped off. (Our dinner plate analogy breaks down here.)

🔗

A good way to maintain this discipline is to think of the use of parentheses in an algebraic expression. A push is analogous to a left parenthesis, and a pop is analogous to a right parenthesis. The pairs of parentheses can be nested, but they have to match. An attempt to push too many items onto a stack causes stack overflow. And an attempt to pop items off the stack beyond the “bottom” causes stack underflow.

🔗

A stack is typically implemented by dedicating a contiguous area of memory to it. The top of the stack is marked by a stack pointer. There are two directions a stack can grow in:

Ascending Stack: Grows toward numerically higher memory addresses.
Descending Stack: Grows toward numerically lower memory addresses.

🔗

The stack pointer is implemented in one of two ways:

Full Stack: The stack pointer points to the location of the last item that was stored on the stack. (The location is “full”.)
Empty Stack: The stack pointer points to the location where the next item will be stored on the stack. (The location is “empty”.)

🔗

This allows for four possible ways to implement a stack. The ARM manual, Procedure Call Standard for the ARM Architecture[3], specifies a full-descending stack. The program in Listing 10.2.1 shows how a full-descending stack might be implemented in C. The program allocates space in memory for storing data elements and provides both a push operation and a pop operation.

/* stack.c
 * Stack example in C.
 * 2017-09-29: Bob Plantz
 */

/* Prototype declarations for functions used in this function.
 */
#include <stdio.h>
#include "push.h"
#include "pop.h"

/* The stack and stack pointer are global variables. They
 * are accessible to all functions in the program.
 */
int theStack[500];
int *stackPointer = &theStack[500];

/* main
 * Illustrates the actions of the push and pop operations.
 */
int main(void)
{
  int x = 12;
  int y = 34;
  int z = 56;
  printf("Start with the stack pointer at %p\n",
            (void *)stackPointer);
  printf("x = %i, y = %i, and z = %i\n", x, y, z);

  push(x);
  push(y);
  push(z);
  x = 100;
  y = 200;
  z = 300;
  printf("push x\npush y\npush z\n");
  printf("Now the stack pointer is at %p\n", 
            (void *)stackPointer);
  printf("Change x, y, and z:\n");
  printf("x = %i, y = %i, and z = %i\n", x, y, z);
  pop(&z);
  pop(&y);
  pop(&x);

  printf("pop z\npop y\npop x\n");
  printf("And we end with the stack pointer at %p\n", 
            (void *)stackPointer);
  printf("x = %i, y = %i, and z = %i\n", x, y, z);

  return 0;
}

🔗

Listing 10.2.1. A C implementation of a stack. This main function uses the push and pop functions in Listings 10.2.2–10.2.5.

/* push.h
 * implementation of push operation in C
 * 2017-09-29: Bob Plantz
 */

/* The stack and stack pointer are global variables. They
 * are accessible to all functions in the program.
 */
extern int *stackPointer;

/* push operation:
 * Address in stackPointer is decremented by size
 * of int. dataValue is stored at this address, which
 * is now the top of the stack.
 */
#ifndef PUSH_H
#define PUSH_H
void push(int dataValue);
#endif

🔗

Listing 10.2.2. Header file for the push function.

/* push.c
 * implementation of push operation in C
 * 2017-09-29: Bob Plantz
 */

#include "push.h"

void push(int dataValue)
{
  stackPointer--;
  *stackPointer = dataValue;
}

🔗

Listing 10.2.3. Implementation file for the push function.

/* pop.h
 * pop stack operation in C
 * 2017-09-29: Bob Plantz
 */

/* The stack and stack pointer are global variables. They
 * are accessible to all functions in the program.
 */
extern int *stackPointer;

/* pop operation:
 * Copies int at current location of stack pointer
 * to *dataLocation; address in stackPointer is
 * incremented by size of int.
 */
#ifndef POP_H
#define POP_H
void pop(int *dataLocation);
#endif

🔗

Listing 10.2.4. Header file for the pop function.

/* pop.c
 * pop stack operation in C
 * 2017-09-29: Bob Plantz
 */

#include "pop.h"

void pop(int *dataLocation)
{
  *dataLocation = *stackPointer;
  stackPointer++;
}

🔗

Listing 10.2.5. Implementation file for the pop function.

🔗

This program illustrates the following points:

Both the stack and the stack pointer are global variables. This mimics the situation with the stack you will use in your assembly language programs. The memory for the stack and the stack pointer register, sp, are globally accessible from any function in your program.
The stack pointer always points to the item that is currently at the top of the stack.
A push operation pre-decrements the stack pointer before storing an item on the stack. Hence the program initializes the stack pointer to point one item beyond the highest numbered element in the array that makes up the stack. The stack “grows” from higher addresses to lower addresses as items are pushed onto it.
A pop operation post-increments the stack pointer after retrieving an item from the stack, thus mirroring the effect of a push operation.

🔗

Figure 10.2.6 shows the states of the variables in the program in Listing 10.2.1 just after the stack is initialized. The stack pointer is pointing beyond the end of the array as a result of the C statement:

int *stackPointer = &theStack[500];

Figure 10.2.6. The stack in Listing 10.2.1 when it is first initialized. “????” means that the value in the array element is undefined.

🔗

The stack is “empty” at this point.

🔗

After pushing one value onto the stack:

push(x);

🔗

the stack appears as shown in Figure 10.2.7. Here you can see that because the push operation pre-decrements the stack pointer, the first data item to be placed on the stack is stored in a valid portion of the array.

Figure 10.2.7. The stack with one data item on it.

🔗

After all three data items—x, y, and z—are pushed onto the stack, it appears as shown in Figure 10.2.8. The stack pointer always points to the data item that is at the top of the stack.

Figure 10.2.8. The stack with three data items on it.

🔗

After changing the values in the variables, the original values in the variables are restored by popping from the stack in reverse order. The state of the stack after all three pops are shown in Figure 10.2.9. Even though we know that the values are still stored in the array, the permissible stack operations—push and pop—will not allow us to access these values. Thus, from a programming point of view, the values are gone.

Figure 10.2.9. The stack after all three data items have been popped off. Even though the values are still stored in the array, it is considered a programming error to access them. The stack must be considered as “empty” when it is in this state.

🔗

Our very simple stack in this program does not protect against stack overflow or stack underflow. Most software stack implementations also include operations to check for an empty stack and for a full stack. And many implementations include an operation for looking at, but not removing, the top element. But these are not the main features of a stack data structure, so we will not be concerned with them here.

🔗

In GNU/Linux, as with most operating systems, the stack has already been set up for us. We do not need to worry about allocating the memory or initializing a stack pointer. When the operating system transfers control to our program, the stack is ready for us to use.

🔗

The push and pop instructions in the AARCH32 architecture use the sp (r13) register for the stack pointer. A push causes the address in this register to decrease, and a pop causes the address to increase. Thus the stack grows from high addresses to low. Although this addressing scheme may seem a bit odd at first, there are some good reasons for doing it this way.

🔗

Think about how you might organize things in memory. Recall that the program counter is automatically incremented by the control unit as your program is executed. Programs come in vastly different sizes, so it makes sense to store the program instructions at low memory addresses. This allows maximum flexibility with respect to program size.

🔗

The stack is a dynamic structure. You do not know ahead of time how much stack space will be required by any given program as it executes. It is impossible to know how much space to allocate for the stack. So you would like to allocate as much space as possible, while preventing it from colliding with program instructions. The solution is to start the stack at the highest address and have it grow toward lower addresses.

🔗

This is a highly simplified rationalization for implementing stacks such that they grow “downward” in memory. The organization of various program elements in memory is much more complex than the simple description given here. But this may help you to understand that there are some good reasons for what may seem to be a rather odd implementation.