CS 240 Lab 9: x86 Stack

Peter Mawhorter

x86 Stack

Address Calculation

  • Syntax is offset ( base, index, stride ), e.g.: 8(%rdi, %rsi, 4)
    • base and index are registers
    • offset must be number
    • stride is a number (only 1, 2, 4, or 8)
  • The computed address is base + offset + (index × stride)
    • base → pointer
    • offset → fixed offset from pointer
    • index → index within array = variable offset from pointer
    • stride → how big each index is = pointer scaling
  • C code ≈ base[index + offset]

scanf

  • Reads formatted input from the user
  • Format declares what we expect them to type, scanf converts text into other types accordingly
    • Can read characters with %c, integers with %d, floats with %f, and strings with %s.
    • When reading strings, you must* specify the max size.
  • You provide one additional argument per format specifier which is a pointer to write the result into
    • This is how all multi-output functions work in C
  • Return value specifies how many values were converted (or error if it’s negative)

scanf

int x, y;
printf("Enter two numbers separated by a comma: ");
scanf("%d,%d\n", &x, &y);
printf("Their sum is: %d\n", x + y);

Calls Scramble Registers

#include <stdio.h>

int doSomething(int a) {
    int x = a + 8;
    printf("My x is: %d\n", x);
    return x;
}

Explorer link (look at %ebx)

int main(int argc, char** av) {
    int x = argc;
    printf("x is: %d\n", x);
    int y = doSomething(x);
    printf("x is: %d\n", x);
    printf("y is: %d\n", y);
    return x;
}

Calls Scramble Registers

  • Each function uses the same 16 registers
    • Could be 1000s of functions in a program…
    • Using stack to save info is slow…
  • Convention:
    • Clean up after yourself in some cases (callee saved)
      • %rbx, %rsp, %rbp, plus %r12-15
    • Do whatever in other cases (caller saved)
      • Any other register

%rbp

long getAndSumValues() {
    long x;
    printf("Enter an integer: ");
    scanf(" %ld",&x);
    if (x == 0) {
        return 0;
    } else {
        return x + getAndSumValues();
    }
}

Explorer link

%rbp

  • The stack “base” pointer
    • Callee-saved, so we need to save it
    • Points to base (top) of our stack frame
  • Useful for accessing stuff we store on the stack, even when the stack pointer is moving up and down
    • You’ll see things like -4(%rbp) a lot
    • Optimization sometimes avoids it

Stack instructions

  • push → Move stack pointer %rsp down & store value
  • pop → Load value & move stack pointer %rsp up
  • call → Move %rsp down, store return address, and jump
  • ret → Load return address into %rip and move %rsp up
  • leave → Copies %rbp into %rsp and then pops into %rbp
  • sub, mov, etc. (Anything that stores to %rsp directly)

Stack Equivalences

Assembly code Equivalent Comments
push %rbx sub $8,%rsp
mov %rbx,(%rsp)
Create slot & store
pop %rbx mov (%rsp),%rbx
add $8,%rsp
Load & relinquish slot
call 0x401123 sub $8,%rsp
mov $0x405007,(%rsp)
Create slot & store address of next instruction
ret mov (%rsp),%rip add $8,%rsp Load return address into %rip “instruction pointer” register & relinquish slot

A full memory diagram focused on a region of the stack. 10 8-byte slots are shown with abbreviated addresses starting at address 0x7f…d9b8 and ending at address 0x7f…da00. Below that block, addresses 0x401818 and 0x401820 are shown, as well as addresses 0x4010c8 and 0x4010d0. Below all of the memory blocks, registers %rsp and %pc are shown. On the left are columns for Segment and Frame. In the Segment column, the first block of addresses in the 0x7f range are marked as “Stack” while the other two blocks are in the “Code” segment. For the Frame column, the bottom address 0x7f…d9b8 is marked as belonging to trip_alarm. Then all but one of the rest of that block (addresses 0x7f…d9c0 through 0x7f…d9f8) belongs to frame phase_2, after which the final slot at 0x7f…da00 and more memory not shown above belongs to main. The values displayed, along with their arrows and comments are: at 0x7f…da00 value 0 with comment “%rsp before phase_2 call.” In the phase_2 frame from the top, at 0x7f…d9f8, value 0x400f32 with a short gray arrow to the right (destination not shown) and comment “return addr. for phase_2 call.” At 0x7f…d9f0, value 2, with comment “pushed %rbp.” At 0x7f…d9e8, value 0 with comment “pushed %rbx.” At 0x7f…d9e0, value 0 with comment “unused/leftover,” and below that at 0x7f…d9d8 value 0x401601 with the same comment. At the next three slots 0x7f…d9d0 through 0x7f…d9c0, the numbers 6, 5, 4, 3, 2, 1 are present, two to a slot dividing it horizontally. Comment for this group is “six numbers from user.” Last line of those at 0x7f…d9c0 also has the comment “%rsp before trip_alarm call.” Finally for this block, address 0x7f…d9b8 is in red, and contains the purple value 0x4010c8, which is the base of a purple arrow pointing to the bottom of the second code block, which has purple address 0x4010c8. Comment is “return addr. for trip_alarm call.” This is the destination of a red arrow that comes from the %rsp register value. Proceeding downward, the first code segment block shows only partial values for addresses 0x401820 and 0x401818 (second address is in light blue). Values shown are bytes starting at 0x40181c (left half of bottom slot) and ending at 0x401821 (second byte from the right of top slot). Bytes in increasing address order are 0x53 alone, then 0xbf, 0x27, 0x27, 0x40, 0x00 together wrapping upwards from the bottom into the top slot. Comments indicate bottom slot starts at trip_alarm-4 (so bytes shown start at trip_alarm+0) and top slot starts at trip_alarm+4. Comments also indicate these bytes correspond to push and move instructions in that order (without details on full assembly). The second memory block has a similar layout with groups of bytes, although both of its memory slots at purple 0x4010c8 and 0x4010d0 are full. Byte groups are 0x48 0x83 0xc3 0x04, then 0x48 0x39 0xeb, then 0x75 0xe8 wrapping up between slots, then 0x48 0x83 0xc4 0x28, then 0x5b, thne 0x5d, then 0xc3. Comments indicate these byte groups are add, cmp, jne (split), add, pop, pop, and ret instructions. Comments also indicate the first slot starts at phase_2+39 and the second at phase_2+47. As noted before the bottom slot is the destination of the purple arrow. Finally for the register values, %rsp has value 0x7f…d9b8 in red, which is the origin of the red arrow mentioned previously pointing to the bottom of the stack. Comment is “stack pointer register.” %pc has value 0x40281c in light blue, with comment “program counter.” This is the origin of a not-previously-mentioned light blue arrow that points to the start of the values on the 0x401818 line, halfway through the slot (the 0x53 byte there). 

A simplified stack diagram based on the previous one. This one doesn’t show any code blocks, omits addresses, and retains only one arrow: the red arrow from the %rsp register to the bottom of the stack. The 0 and 0x401601 values from the middle of the phase_2 frame are also omitted, with their boxes shaded in gray and a comment “leftovers.” The top of the phase_2 stack frame has a new comment “main+261” and the 0x4010c8 value in the trip_alarm frame now has comment “phase_2+39” (its arrow is now gray and just points out to the right since that code segment isn’t displayed). Likewise, the %pc register’s 0x40281c value has a gray arrow now and comment “trip_alarm+0.” All comments besides those just described and the “six numbers from user” comment have been removed. 

Drawing the Stack

Stack grows downwards

Starting state

A stack diagram showing %rsp set to 0x7fffff8 at the top of the stack, with no values in it yet. The stack is drawn as a series of rectangles stacked on top of each other, each much wider than it is tall. A label indicates that each rectangle represents an 8-byte value. The %rsp value’s position is indicated by a horizontal arrow in the left margin pointing to the upper-left corner of the top rectangle. 

push %rdi  # 0x4353

The same diagram with the value 0x4353 in the top rectangle, and the stack pointer %rsp now has a value of 0x7ffffff0. The arrow for the stack pointers is now pointing at the bottom-left corner of the top rectangle, which is also the top-left corner of the second rectangle. 

Drawing the Stack

push %rsi  # 0xf0

A stack diagram showing %rsp set to 0x7ffffe8 which is the bottom of the 2nd rectangle from the top. The value in that rectangle is 0xf0. 

pop %rax

The same diagram as before, except the stack pointer has moved back up to 0x7ffffff0. The value 0xf0 remains in the second rectangle down which is now below the stack pointer. 

Drawing the Stack

  • Stack grows downwards from top
  • Sometimes grows in multiples of 16 for alignment
  • Represents “notes as we go” that we come back to later
    • When calling a function, the current notes get buried
    • When returning, we go back to our old notes
    • If we didn’t write something down, it may be lost

Drawing the Stack

  • stack frame: region used by one function
    • Allocated by subtracting from %rsp and/or push, etc.
  • What to show:
    • Caller’s frame above
    • Return address in first slot
    • %rsp₀ points to first slot
    • %rsp points to bottom

A stack diagram which starts with three yellow slots at the top labeled “caller’s frame” below which are three blue slots labeled “our frame” and then two white slots labeled “unused area.” The first blue slot holds the “return addr” and is pointed to by “%rsp₀”, while the second and third blue slots hold other values (0x4353 and 0xf0). The last blue slot is pointed to by %rsp. 

Recursion

long getAndSumValues() {
    long x;
    printf("Enter an integer: ");
    scanf(" %ld",&x);
    if (x == 0) {
        return 0;
    } else {
        return x + getAndSumValues();
    }
}

Explorer link

Recursion

getAndSumValues:
        subq    $24, %rsp
        movl    $.LC0, %edi
        movl    $0, %eax
        call    printf
        leaq    8(%rsp), %rsi
        movl    $.LC1, %edi
        movl    $0, %eax
        call    __isoc99_scanf
        cmpq    $0, 8(%rsp)
        je      .L3
        call    getAndSumValues
        addq    8(%rsp), %rax
        jmp     .L2
.L3:
        movl    $0, %eax
.L2:
        addq    $24, %rsp
        ret

Recursion

getAndSumValues:
        subq    $24, %rsp
        #
        #
        #
        leaq    8(%rsp), %rsi
        #
        #
        call    __isoc99_scanf
        #
        #
        call    getAndSumValues
        addq    8(%rsp), %rax
        #
.L3:
        #
.L2:
        addq    $24, %rsp
        ret

Recursion

getAndSumValues:
        subq    $24, %rsp
        #
        #
        #
        leaq    8(%rsp), %rsi
        #
        #
        call    __isoc99_scanf
        cmpq    $0, 8(%rsp)
        je      .L3
        call    getAndSumValues
        addq    8(%rsp), %rax
        jmp     .L2
.L3:
        movl    $0, %eax
.L2:
        addq    $24, %rsp
        ret

Recursion

  • Multiple frames from one function
    • Return addresses may be identical
  • Values pile up on the stack
  • Get used up as we return

(This code has weird alignment)

A stack diagram with three call frames. 

Lab Work

  • More practice for x86 assignment
  • How to start it for real? cs240 start x86