CS 208 s21 — Memory Layout and the Stack

Table of Contents

1 Video

Here is a video lecture for the material outlined below. It covers CSPP sections 3.4.4 and 3.7 (through 3.7.2) (p. 189–191, 238–244). It contains sections on

  1. memory layout review (0:28)
  2. push and pop instructions (4:00)
  3. pop instruction quick check (13:16)
  4. Procedure call requirements (17:07)
  5. call and ret instructions (30:08)
  6. example in gdb (35:13)

The Panopto viewer has table of contents entries for these sections. Link to the Panopto viewer: https://carleton.hosted.panopto.com/Panopto/Pages/Viewer.aspx?id=8b1d339d-d1ea-480e-a375-ac500113ed5b

2 Stack Operations

mem-layoutv2.png

  • pushq and popq instructions push/pop quad words onto/off of the program stack
    • pushq has a source operand, popq has a destination
    • the stack is a region of memory used to facilitate local variables and procedure calls
    • top of the stack is the lowest memory address, and is conventionally drawn at the bottom
    • each of these instructions combine a data move (copy the source to memory location for push, copy value in memory to destination for pop) and modifying the stack pointer
      • %rsp, the stack pointer, always contains the address of the top of the stack
      • either decremented by 8 (push, stack grows down) or incremented by 8 (pop)

    stack.png

3 Procedures

3.1 Are Jumps Enough?

  • could we implement procedure calls using jumps?
  • maybe we could use jmp to go into a function call, and then return by jmp-ing to a label right after the call 
func1:
    ...
    jmp func2
back:
    ...
done:


func2:
    ...
    jmp back
done:
  • but what if func1 calls func2 twice? 
func1:
    ...
    jmp func2
back1:
    ...
    jmp func2
back2:
    ...
done:


func2:
    ...
    jmp back? // which label do we jump to?? Have to choose at compile time
done:
  • we would need to compile a different version of func2 for every call, so that we could jump back to the right place
  • there's got to be a better way…

3.2 Overview

  • mechanisms needed to facilitate procedures (e.g., procedure P calls procedure Q, then Q executes and returns back to P):
    • passing control: instruction pointer (%rip) must be set to the start of Q (call) and then set to the instruction following the call to Q in P (return)
    • passing data: P has to provide arguments to Q and Q has to return a value to P
    • allocating and deallocating memeory: Q needs to acquire space for local variables and then free that space
  • requires seperate storage per call (not just per procedure)

3.3 The Run-Time Stack

frame-general.png

  • a stack data structure (last-in, first-out) a natural fit for managing run-time procedure memory
    • only the most recent procedure call needs to allocate space for local variables or make a new procedure call
    • when a procedure returns, we want to free the memory used by this most recent call
    • hence it's a natural fit to push and pop procedure data from a stack
  • when a procedure allocates space on the stack it is called that procedure's stack frame
  • x86-64 only allocates what a procedure actually needs
    • if a procedure's local variables can all be held in registers and it calls no other procedures, no stack frame is needed

3.4 Control Transfer

  • processor needs to know where it should resume execution after a procedure call returns
    • the call instruction pushes the return address of the following instruction onto the stack (part of the calling procedure's stack frame) and sets the instruction pointer (%rip)to the start of the new procedure
      • call operand can either be direct (a label) or indirect (* followed by one of the standard operand formats)
    • the ret instruction pops the return address off the stack and copies it to %rip

3.4.1 Example in gdb

#include <stdio.h>

#define MAX_INPUT_LEN 100

long square(long x) {
    return x * x;
}

int main() {
    char input[MAX_INPUT_LEN];
    printf("enter a number: ");
    fgets(input, MAX_INPUT_LEN, stdin);  // read from the command line, store as a string in input
    long num;
    sscanf(input, "%ld", &num);  // parse input as a long, store in num
    printf("your number squared is %ld\n", square(num));
}