2. x86 Assembly and Call Stack¶

Number Representation¶

A nibble is 4 bits, a byte is 8 bits, and a word is 32 bits (on 32b architectures). The word is the size of a pointer. Real-world 64-bit architectures include stronger defenses against memory safety exploits.

Take a look at 1. Number Representation for information on how to represent numbers.

Compiler, Assembler, Linker, Loader (CALL)¶

There are 4 main steps to running a C program: 1. Compiler: translates C code into assembly instructions. We will use x86 Assembly, where 61C uses RISC-V ISA 2. Assembler: Translates assembly instructions into machine code (raw bits). 3. Linker: Resolves dependencies on external libraries. After the linker is finished linking external libraries, it outputs a binary executable of the program that you can run. 4. Loader: set up an address space in memory and runs the machine code instructions in the executable.

Learn more about CALL in detail in 8. Compiler, Assembler, Linker, Loader (CALL) from 61C notes.

C Memory Layout¶

We can draw the memory layout as one long array with \(2^{32}\) elements, where each element is one byte. The leftmost element has address \(0x00000000\) andads the rightmost element is \(0xFFFFFFFF\). We visually see this as a grid of bytes, where the bottom-left element is \(0x00000000\) and the top-right element has \(0xFFFFFFFF\).

We further separate the address space into four sections. From lowest to highest address, they are: - Code: Contains the executable instructions of the program (the code itself). Here, the assembler and linker output raw bytes that are stored in the code section.

• Static: Contains constants and static variables that never change during program execution, and are usually allocated when the program is started

• Heap: Stores dynamically allocated data. We do this with malloc and free in C. The heap starts at lower addresses and grows up to higher addresses as more memory is allocated.

• Stack: Stores local variables and other information associated with function calls. The stack starts at higher addresses and grows down as more functions are called.

Little-Endian Words¶

x86 is Little-Endian, meaning that when storing a word in memory, the least significant byte is stored at the lowest address, and the most significant byte is stored at the highest address. To store the word \(0x44332211\), we stored them in bytes as

You see that the least significant byte \(0x11\) is stored at the lowest address, and the most significant bytes \(0x44\) is stored at the highest address.

Registers¶

There are also registers, which store memory directly on the CPU. Each register can store one word. Registers do not have addresses, but we refer to registers using names. x86 has three special registers:

1. eip: instruction pointer, which stores the address of the machine instruction currently being executed. RISC-V equivalent: PC (program counter)
2. ebp: base pointer, which stores the address of the top of the current stack frame. RISC-V equivalent: FP (frame pointer)
3. esp: stack pointer, stores the address of the bottom of the current stack frame. RISC-V equivalent: SP (stack pointer)

The "e" in the register abbreviations stands for "extended" and indicates we are using a 32-bit system (extended from 16-bit system).

Sometimes, the registers can point somewhere in memory. We can store the address of a pointer that goes to another part of memory.

Stack: Pushing and Popping¶

If we want to remember a value, we save it on the stack. We do the following 2-step procedure to add a value on a stack 1. Allocate additional space on the stack by decrementing the esp 2. Store the value in the newly allocated space

The x86 push instruction does both of these steps to add a value to the stack.

When we pop a value off the stack, the value is not wiped away from memory. Instead esp is incremented tso that the popped value is now below esp. Since esp points to the bottom of the stack, the popped value below esp is now in undefined memory.

x86 Colling Convention¶

Some syntactical differences between x86 syntax and RISC-V syntax: 1. destination register comes last in x86 2. references to registers are preceded with a percent sign. To reference eax, we would do %eax. 3. immediates are preceded with a dollar sign (such as $1, $0x4). 4. Memory references use parenthesis and can have immediate offsets, such as 12(%esp), which dereferences memory 12 bytes above the address contained in esp. If parentheses are used without an immediate offset, the offset can be through of as an implicit 0.

Here is an example. The assembly instruction xorl 4(%esi), $eax will be interpreted as the following. Here, the opcode is xorl, the source is 4(%esi), and the destination is %eax. As such, the pseudocode might be written as EAX = EAX ^ *(ESI + 4). We dereference the value 4 bytes above the address stored in esi.

x86 Function Calls¶

To call a function, the stack allocates extra space to store local variables and other information relevant to the function. Since the stack grows down, the extra space is at a lower address. Once the function returns, the space on the stack is freed up for future function calls.

The caller calls the callee. Program execution starts in the caller, moves to the callee as a result of the function call, and then returns to the caller after the function call completes.

In x86, we need to update the values in all three registers we've discussed: 1. eip, the instruction pointer needs to be changed to point to the instructions of the callee 2. ebp and esp need to be updated to point to the top and bottom of a new stack frame for the callee

There are 11 steps to call an x86 function and returning. 1. Push arguments onto the stack. Since esp gets decremented as we push arguments onto the stack, we should push arguments in reverse order. 2. Push the old eip (rip) on the stack. rip is the (return instruction pointer). 3. Move eip to point to the instructions for the callee function 4. Push the old ebp (called sfp) on the stack. This is the saved frame pointer. We do this since we are about to change the value in the ebp register. 5. Move ebp down. We can safely change ebp to point to the top of the new stack frame. The top of the new stack frame is where esp is currently pointing, since we are about to allocate new space below esp for the new stack frame. 6. Move esp down. We allocate new space for the new stack frame by decrementing esp. The compiler looks at the function to determine how far esp should be decremented. 7. Execute the function. Arguments will be located starting at the address stored in ebp plus 8 8. Move esp up. When the function is ready to return, increment esp to point to the top of the stack frame (ebp). This effectively erases the stack frame. 9. Restore the old ebp (called sfp). 10. Restore the old eip (called rip) 11. Remove arguments from the stack by incrementing the esp

x86 Function Call in Assembly¶

Let's play the role of the compiler:

int main(void) {
    foo(1, 2)
}

void foo(int a, int b) {
    int bar[4];
}

The compiler would turn the foo functioninto the following x86:

main:
    # Step 1. Push arguments on the stack in reverse order
    push $2
    push $1

    # Steps 2-3. Save old eip (rip) on the stack and change eip
    call foo

    # Execution changes to foo now. After returning from foo:

    # Step 11: Remove arguments from stack
    add $8, %esp

foo:
    # Step 4. Push old ebp (sfp) on the stack
    push %ebp

    # Step 5. Move ebp down to esp
    mov %esp, %ebp

    # Step 6. Move esp down
    sub $16, %esp

    # Step 7. Execute the function (omitted here)

    # Step 8. Move esp
    mov %ebp, %esp

    # Step 9. Restore old ebp (sfp)
    pop %ebp

    # Step 10. Restore old eip (rip)
    pop %eip

Steps 1-3 happens in the caller function. Step 3 changes the eip to point to the callee. Once eip is changed, steps 4-10 happen in the calee function. Step 10 changes the eip to point back to the caller. And then now step 11 takes place.

We use shorthand to write function returns. Step 8 and 9 are abbreviated as the leave instruction, and step 10 is abbreviated as the ret instruction. Maybe we can just write leave ret after each function

We call steps 4-6 the function prologue, and steps 8-10 the function epilogue.