Lecture 3: Memory, the Stack, Recursion

Introduction

Today, we’ll discuss:
1. How memory is laid out when our program is resident
2. What are the different segments of our program space
3. What is a call stack and how we use it
4. How to write functions & the assembly design recipe

Memory and addressing modes

Working with arrays

Working with consecutive chunks of the same size (i.e., arrays) is made easier using a so-called base-index-scale syntax
This addressing mode uses a base register (the beginning of the array), an index register (the element index) and scale (the size of each element in bytes)

A Program’s Address Space

When our program is loaded into memory, some of the things that go there are directly in the executable: the code (.text), global variables (.data)
Some things are created while the program is running

A program’s memory space (that is, the portion of memory that a program can access and use) is partitioned into a few chunks (segments):

+-----------------------------------+ <- High address
| Environment vars + args           |
+-----------------------------------+
|         STACK                     |
|           |                       |
|           v                       |
|...................................|
|                                   |
|                                   |
|                                   |
|                                   |
|                                   |
|                                   |
|                                   |
|                                   |
|                                   |
|                                   |
|...................................|
|             ^                     |
|             |                     | Dynamically allocated memory
|            HEAP                   |
+-----------------------------------+
| Uninitialized globals (.bss)      |
+-----------------------------------+
| Initialized globals (.data)       |   .text, .data, .bss come from the executable
+-----------------------------------+
|                                   |
| Code (.text)                      |
+-----------------------------------+
| OS stuff                          |
+-----------------------------------+ <- low address

The Stack (and the Heap)

The stack and the heap are 2 areas where a program can allocate memory during its lifetime
Heap-allocated memory is managed using library function which pass requests to the OS
Lifetime of data on the heap can vary - memory needs to be allocated and deallocated explicitly
We’ll talk more about the heap when we start working in C next week
The stack is used for “automatic” local allocation - it is very easy and quick to allocate memory
Memory is released when a function returns
The stack is organized in stack frames which are managed using the registers %rsp (the stack pointer) and %rbp (the base pointer)
The other thing to note is that while heap grows upward - “new” memory will have a higher address than “old” memory, the stack grows downward - from higher addresses to lower addresses

Stack Frames

A stack frame is an area of the stack delimited by the registers %rbp and %rsp
Normally, everytime a function is called, it sets up a stack frame for itself for storing local information
Once the function exits, the stack frame is released
Setting up the stack frame is exactly what the instruction enter does
On the other hand, releasing the stack frame is the job of leave - this cleans up whatever the function might have stored on the stack

Setting up the stack frame can be also achieved using the following pair of instructions:

pushq %rbp      # save the previous stack frame base to the stack
movq %rsp, %rbp # copy the current stack pointer into the base pointer, creating a stack of size 0

leave can be then replaced by the following instructions

movq %rbp, %rsp # drop the current stack frame by resetting %rsp to the base of the frame
popq %rbp       # restore the previous frame base

As mentioned above, stack frames are useful for storing local information a function needs during its lifetime
This can be either using push/pop or by using offsets from %(rbp) as local variables

How does this work?

First we need to allocate some number of bytes on the stack
Let’s say that we want to store two long variables (let’s call them a and b) on the stack
That’s a total of 16 bytes
We’ll tell enter that we want an initial stack frame of size 16 bytes instead of 0:
```
enter $16, $0
...
```

Now we can map a to -8(%rbp) and -16(%rbp) (remember that the stack grows downward!)

...
movq $42, -8(%rbp)    # a = 42
movq $1, -16(%rbp)    # b = 1
addq $12, -16(%rbp)   # b += 12

# return b;
movq -16(%rbp), %rax
leave
ret

We’ll need to use local variables if:
1. we have more locals than available registers
2. we write recursive functions

Writing Functions

Writing Recursive Functions

After reading the assembly design recipe, let’s try to write a recursive factorial function in assembly

Signature
- Our function will take a long and will return a long
```
# long fact(unsigned long n)
```

Pseudocode

As “pseudocode”, we’ll write the usual recursive C implementation of factorial:

long fact(long n) {
  if (n < 2) 
    return 1;
  else
    return n * fact(n - 1);
}

Variable mappings
- We only have one variable right now, and it will come in the rsi register, so we’ll keep it there.
```
# n -> %rsi
```

Skeleton

fact:
    # Prologue:
    enter $0, $0

    # Body:

    # Epilogue:
    leave
    ret

Body

fact:
...
   # if (n < 2) 
   #   return 1;
   # else
   #   return n * fact(n - 1);
...

To be continued…