Program execution can be understood as a series of function calls. Every user-mode process (where user-mode refers to CPU instruction set privilege ring 3, where applications run) corresponds to a call stack structure. When a function finishes executing, it automatically returns to the next instruction of the calling function (via the call instruction) and continues execution. The stack structure is used to store return addresses, pass function parameters, store local variables, and temporarily save the function context (i.e., the information needed to execute the function).

Registers

Register Allocation

Registers are important carriers for the processor to process data and run programs. During program execution, registers are responsible for storing data and instructions, so function calls have an important relationship with registers.

The registers contained in a 32-bit CPU include:

• 8 32-bit general-purpose registers, including 4 data registers (EAX, EBX, ECX, EDX), 2 index registers (ESI and EDI), and 2 pointer registers (ESP and EBP)
• 6 segment registers (ES, CS, SS, DS, FS, GS)
• 1 instruction pointer register (EIP)
• 1 flags register (EFLAGS)

The original 8086 platform used 16-bit registers, each with specific purposes. With the advent of 32-bit registers, they use a flat addressing mode, so there are fewer constraints on special registers. However, due to historical reasons, the names of the 16-bit registers are retained. EAX, EBX, ECX, EDX, ESI, and EDI are usually used as general-purpose registers, but some instructions have specific source or destination registers (e.g., %eax is usually used to store function return values). To avoid compatibility issues, ABI (Application Binary Interface) defines the roles of registers: EAX is commonly used for function return values, EBX for base addresses, ECX as a counter (used implicitly by REP prefix and LOOP instruction, with loop count in cx), and EDX is typically used to store the remainder in integer division (when the function body contains division, EAX holds the integer part, and EDX holds the remainder; multiplication and division often involve EAX and EDX). EDI and ESI are usually used to store function parameters.

The EIP (instruction pointer) register usually points to the address of the next instruction to be executed (offset within the code segment). After each assembly instruction completes, the value of EIP increases. ESP points to the top of the current function's stack frame, while EBP always points to the bottom of the current function's stack frame. Note that the EIP register cannot be accessed in the usual way (its opcode cannot be obtained).

In Intel CPUs, EBP is often used as the stack frame pointer register, storing the base address. For function parameters, offsets are positive; for local variables, offsets are negative.

Register Usage Principles

The calling function refers to the function that calls another function, and the called function is the one being called.

The calling function typically uses %eax, %ecx, and %edx as caler-saved registers. When calling a function, if the calling function wants to preserve these registers, it must explicitly save them on the stack before the call. The called function can overwrite these registers without corrupting the calling function's data. The called function typicaly uses %ebx, %edi, and %esi as callee-saved registers. The called function must save the original values of these registers on the stack before overwriting them and restore them before returning, because the calling function may also be using them. Additionally, the called function must preserve registers %ebp and %esp and restore them to their pre-call values upon return, i.e., it must restore the calling function's stack frame.

Stack Frame Structure

Function calls are usually nested. At any given time, information about multiple functions exists on the stack. Each unfinished function has a contiguous independent area called a stack frame. A stack frame is a logical segment of the stack. When a function is called, a logical stack frame is pushed onto the stack; when it returns, the stack frame is popped off. The stack frame mainly stores function parameters, local variables within the function, and the information needed to return to the previous stack frame.

The roles of a stack frame are:

1. Save the local variables of the calling function
2. Pass parameters to the called function
3. Return the return value of the called function
4. Store the return address (the next instruction to execute after the called function completes)

The boundaries of a stack frame are defined by the stack frame base pointer register EBP and the stack pointer register ESP. EBP is at the bottom (high address) and has a fixed position within the stack frame. ESP is at the top (low address) and its position changes with push and pop operations. Therefore, data access is typically done via EBP (using offsets).

ESP points to the top of the stack, and EBP generally points to the beginning of the stack frame.

Consider a program: A() → B() → C()

• A's stack frame includes: A's local variables, parameters passed to B, B's return value, and the address of the next instruction after B completes.
• B's stack frame includes: B's local variables, parameters passed to C, C's return value, and the address of the next instruction after C completes.
• C's stack frame includes: C's local variables.

Therefore:

1. The parameters and return value of the called function are stored in the calling function's stack frame.
2. In terms of stack frames, C's stack frame is at the top. ESP points to the top of C's stack frame (the top of the entire stack), and EBP points to the beginning of C's stack frame.
3. Since the calling function has not yet finished executing, the called function's stack frame cannot overwrite the calling function's stack frame. It can only be managed through push and pop instructions.
4. The stack grows from high addresses to low addresses, while data is filled from low addresses to high addresses.

Key Assembly Instructions

• call instruction: When executed, pushes the current value of EIP onto the stack (because EIP holds the address of the next instruction to be executed, this corresponds to saving the return adddress, which is why the return address is stored in the calling function's stack frame). Then it modifies EIP to the address of the called function, so after call completes, the target function is automatically invoked.
• ret instruction: Pops the value (return address) that was pushed by call back into EIP. After ret completes, execution continues with the next instruction of the calling function.
• push instruction: Decrements ESP by 8 (on x86-64) to create space, then copies the operand to the location pointed to by ESP. In AT&T syntax: sub $8, %esp then mov source, (%esp).
• pop instruction: Moves the value at the location pointed to by ESP to the destination operand, then increments ESP by 8. In AT&T syntax: mov (%esp), dest then add $8, %esp.
• leave instruction: Often follows ret. It restores the stack frame by setting ESP to EBP and then popping the old EBP value.

Example: Function Call Walkthrough

Consider the following C program:

#include <stdio.h>

int sum(int a, int b)
{
    int s = a + b;
    return s;
}

int main(int argc, char *argv[])
{
    int n = sum(1, 2);
    return 0;
}

Using GDB, the disassembly of main is (in AT&T syntax):

0x0000000000400540 <+0>:  push   %rbp
0x0000000000400541 <+1>:  mov    %rsp,%rbp
0x0000000000400544 <+4>:  sub    $0x20,%rsp
0x0000000000400548 <+8>:  mov    %edi,-0x14(%rbp)
0x000000000040054b <+11>: mov    %rsi,-0x20(%rbp)
0x000000000040054f <+15>: mov    $0x2,%esi
0x0000000000400554 <+20>: mov    $0x1,%edi
0x0000000000400559 <+25>: callq  0x400526 <sum>
0x000000000040055e <+30>: mov    %eax,-0x4(%rbp)
0x0000000000400561 <+33>: mov    -0x4(%rbp),%eax
0x0000000000400564 <+36>: mov    %eax,%esi
0x0000000000400566 <+38>: mov    $0x400604,%edi
...
0x0000000000400575 <+53>: mov    $0x0,%eax
0x000000000040057a <+58>: leaveq
0x000000000040057b <+59>: retq

And the disassembly of sum:

0x0000000000400526 <+0>:  push   %rbp
0x0000000000400527 <+1>:  mov    %rsp,%rbp
0x000000000040052a <+4>:  mov    %edi,-0x14(%rbp)
0x000000000040052d <+7>:  mov    %esi,-0x18(%rbp)
0x0000000000400530 <+10>: mov    -0x14(%rbp),%edx
0x0000000000400533 <+13>: mov    -0x18(%rbp),%eax
0x0000000000400536 <+16>: add    %edx,%eax
0x0000000000400538 <+18>: mov    %eax,-0x4(%rbp)
0x000000000040053b <+21>: mov    -0x4(%rbp),%eax
0x000000000040053e <+24>: pop    %rbp
0x000000000040053f <+25>: retq

Now, let's step through the execution:

1. push %rbp (0x400540): The push instruction subtracts 8 from RSP to open up space, then pushes the old value of RBP onto the stack. At this point, RBP holds the frame address of the function that called main. The reason for saving RBP is that main needs to use RBP for its own frame base, but it must not overwrite the caller's value. So it saves the old value via push. After this instruction, main's stack frame contains only the saved RBP value. This is the entry point of main.

2. mov %rsp,%rbp (0x400541): Assign the current RSP to RBP. Now both RBP and RSP point to the same location, which is the start of main's stack frame.

3. sub $0x20,%rsp (0x400544): Subtract 32 (0x20) from RSP, moving it to a lower address. This reserves 32 bytes for main's local and temporary variables. Note that the operating system typically allocates some stack space for the program, but the actual amount used is determined by how much RSP is adjusted. After this instruction, main's stack space is fully allocated: 8 bytes for the saved caller's RBP and 32 reserved bytes.

4. mov %edi,-0x14(%rbp) (0x400548): Save the first parameter (argc) from EDI into main's stack frame at RBP-0x14.

5. mov %rsi,-0x20(%rbp) (0x40054b): Save the second parameter (argv) from RSI at RBP-0x20.

6. mov $0x2,%esi (0x40054f): Set ESI to 2 (the second argument for sum).

7. mov $0x1,%edi (0x400554): Set EDI to 1 (the first argument for sum).

   Instructions 4-7 demonstrate saving the original parameters of main (because they are in RDI and RSI, which will be overwritten) and then setting up the arguments for the call to sum. By convention, function arguments are passed in registers in the order: RDI, RSI, RDX, etc.

8. callq 0x400526 <sum> (0x400559): The call instruction first pushes the return address (the address of the next instruction, which is 0x40055e) onto the stack. It subtracts 8 from RSP to make space and stores the return address. Then it sets RIP to the address of sum (0x400526). Execution jumps to sum.

9. Inside sum:

   • push %rbp: Save main's RBP value (which is the current RBP) onto the stack (RSP decremented by 8).
   • mov %rsp,%rbp: Set RBP to the current RSP, establishing sum's frame base.
   • mov %edi,-0x14(%rbp): Save the first parameter (1) at RBP-0x14.
   • mov %esi,-0x18(%rbp): Save the second parameter (2) at RBP-0x18.
   • mov -0x14(%rbp),%edx: Load the first parameter into EDX.
   • mov -0x18(%rbp),%eax: Load the second parameter into EAX.
   • add %edx,%eax: Add EDX and EAX, result in EAX (now EAX = 3).
   • mov %eax,-0x4(%rbp): Store the result (3) into a local variable at RBP-0x4.
   • mov -0x4(%rbp),%eax: Load the result back into EAX (to prepare for return).
   • pop %rbp: Pop the saved main's RBP value back into RBP (RSP incremented by 8). This restores main's frame pointer.
   • retq: Pops the return address (0x40055e) into RIP and increments RSP by 8. Execution returns to main.

   Note: sum does not adjust RSP to reserve space because it is the last function called in this chain and does not call any other functions. It uses the stack space that was already allocated by the caller (main) for its local variables.

10. Back in main (at 0x40055e): mov %eax,-0x4(%rbp): Move the return value of sum (which is in EAX) to the local variable n (at RBP-0x4).

11. The program continues with other instructions (printing, etc.) and eventually executes leaveq and retq to return to the original caller.

This walkthrough illustrates the mechanics of function call and return using the stack.