CS 208 s20 — 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:00)
  2. push and pop instructions (4:00)
  3. pop instruction quick check (13:22)
  4. Can we do procedure calls with jmp? (15:48)
  5. Procedure call requirements (19:45)
  6. call and ret instructions (33:11)
  7. example in gdb (38:30)
  8. end notes (43:35)

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=6f10dd31-b406-4f9d-a758-abb300ff0c1c

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

2.1 Quick Check

Top of the stack at 0x200, 8 bytes stored there contain 0x20. What changes about registers or memory as a result of popq %r8?1

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));
}

4 Homework

  1. CSPP practice problem 3.32 (p. 244)
  2. Work on lab 2. Post in the lab 2 check-in forum. Your post should be something surprising or difficult that you've learned that you think would help others, a point of confusion, something you're stuck on, a deeper question sparked by the lab, or a response to someone else's post.

Footnotes:

1

popq copies the top 8 bytes of the stack to %r8, so %r8 will now contain 0x20. This also "pops" these 8 bytes off the stack, so 8 is added to %rsp, making it 0x208 (remember, the stack grows down to lower memory addresses, so moving %rsp up in memory shrinks the stack). Nothing changes in terms of values stored in memory---%rsp tracks the top of the stack, but the system doesn't zero-out popped values or anything like that.