This article uses arm assembly, from the assembly point of view to deepen the understanding of the function call stack

The words written in the front

Although I have read a lot of articles and videos about the call stack, I still don’t understand the process of function call stack. I just left home these days and sat down to analyze the call process thoroughly. Here is a record, I would rather write it myself than watch it for thousands of times.

The code used in this article is as follows

void func3(int a, int b){
    int c = a + b;
    printf("--%d---", c);
}

void func2(a){
    int a = 1;
    int b = 2;
    func3(a, b);
    int c  = b * 2;
    printf("---%d----",c);
}

void func1(a){
    func2(a); }Copy the code

Understanding the function call stack

  1. In the process of function call, local variables, LR (X30) function return value, FP (x29) register continuously in and out of the stack process.
  2. The call stack of functions is allocated from the highest address to the lowest address, and is a contiguous block of memory.
  3. The call stack of functions is highly balanced

Arm Assembly Basics (64-bit systems)

1. Fp (X29) register

Point to the bottom of the current function call stack (high address)

2. Sp register

Point to the top (low address) of the current function call stack

3. Lr (X30) register

Store the address of the next instruction after the function returns.

4. The bl instructions

Function call instruction

5. The STP instructions

Stores the value of a register into memory

6. The LDP instructions

Stores the value of memory into a register

7. Sub commands

subtracting

8. The add instructions

add

Others (important)

Function A calls B and b calls C, so when function B calls,lr will store the address of the next instruction from A to call B; Then B calls C, and the lr will store the address of the next instruction that B calls C. At this time, LR was modified, and the correct address could not be returned after the completion of B. So at the beginning of the call to function B, the value of the LR register is stored in memory. Similarly, LR is also stored in memory when c is called to prevent the value of LR from being modified in subsequent calls. Before B completes the return, the address of the next instruction is fetched from memory and stored in the LR register.

For example, I called func3 inside func2, and when func3 is done, I go back to func2 to continue. When func3 is called, the address of the next execution is stored in the LR register.

  1. Make a breakpoint where the function func3 was called, enter assembly, type SI step, and execute to the place where bl function was called, as shown below. The address of the next instruction is found to be 0x102FE9744.

2. Input si single step to enter function func3, as shown in the following figure. The value of the LR register is 0x102FE9744, which is the address of the next instruction for func3.

Specific call procedure

1. Call func1

  1. Place a breakpoint where func1 is called and go inside func1, with the assembly code shown below

Before STP is executed

sp=0x000000016d3877a0,

lr=0x0000000102a7d794,

fp=0x000000016d387860,

These values hold the current register value when the func1 function is called. Let’s draw a diagram of the call stack at this point.2. Move sp down 16 bytes, then store the values of X29 and x30 in eight bytes each above sp. The call stack is shown below

stp x29, x30, [sp, #-0x10]! -> this [sp, #-0x10]! Followed by an exclamation mark to indicate that the value of sp will change

Sp moves down 0x10(16) bytes, while the next mov x29, SP moves x29 to the position of SP, which is directly indicated here. STP stores X29 in the first 8 bytes of SP and X30 in the last 8 bytes, as shown in the figure. LLDB can also be used to read the memory address of sp register, as shown in the following figure. Sixteen bytes are read, which are exactly x29 and X30 values.3. Perform si. Before calling func2, let’s look at the register values, as shown in the figure below. And the address of the next instruction is 0x102a7d770, so we can look at the contents of the LR register once we enter func2

2. Call func2

1. Open up the call stack of func2 and save the site

1. View the current values of FP, SP, lr, as shown in the following figure. At this point, LR is already the address of the next instruction in func1,sp, FP is still the address before entering func1.2. The first instruction moves sp down

Sub sp, sp, #0x30 -> sp = sp-0x30

  1. The second instruction stores the values of X29,x30 16 bytes above the start of sp+0x20.

STP x29, x30, [sp, #0x20] -> [sp, #0x20] , indicates that the value of sp does not change

  1. The third instruction moves X29 to the position SP +0x20. After the execution of these three instructions, the call stack at this time is shown in the figure below. 1, 2 and 3 in the figure respectively represent the state after each instruction is executed.

add x29, sp, #0x20

X29 x39 sp register x29 x39 sp register That corresponds to our call stack6. Read the value stored in sp+0x20 because we stored x29, x30 in the second instruction in step 3. You can see that the stored value is the value of FP,lr before step 1,func1

2. Local variables are pushed
  1. The first instruction stores 1 in register W8 (the lower 32 bits of X8), and the second instruction stores the value of register W8 in position X29-0x4.

mov w8, #0x1

stur w8, [x29, #-0x4]

  1. Likewise, the third fourth instruction stores the value of 2 at x29-0x8. The call stack after the execution of these four instructions is shown in the figure, and the red box changes the call stack state for these four instructions

3. Check the values of x29-0x4 and x29-0x8. Int takes 4 bytes, the first 4 bytes store 1, the last 4 bytes store 24. Then use lDUR to store 1 in W0 and 2 in W1. Then call func3. Look at the values for x29 x30 sp as follows. The value at this point is aligned with our call stack

3. Call func3 – a non-class function

1. Open up stack space and save the site

1. Now the assembly code of func3 is as follows, and the value of X29 x30 sp is shown in the figure, both are the state of the current register after the execution of func2.2. The first three instructions are the same as those of func2,sp moves down 0x30 bytes, X29,x30 is pushed, and x29 is moved. After execution, the call stack is shown below. The red box is the call stack for Func33. The value of x29 x30 sp after the first three commands is. This is consistent with the call stack we analyzed.

2. Local variables are pushed

1. The following two STUR instructions push w0, w1 (parameters). The call stack after being pushed is as follows. The red box shows the call stack state changed by these two instructions.2. Read the contents of fP-0x8, which happens to be the values of 1 and 2, which are marked by our call stack.

3. Function return, stack balance

1. Look again at the state of the call stack after Func3 has run. We know that once printf is done,func3 is done, and the middle part is calculated and printed. Let’s go straight to the last three instructions.

ldp x29, x30, [sp, #0x20]

add sp, sp, #0x30

ret

LDP assigns the value of position sp+0x20 to x29 and x30. As we know from the func assembly, the first eight bytes of sp+0x20 are the value of x29(bottom of the func2 call stack fp) and the last eight bytes of sp+0x20 are the value of x30(address of the next instruction of func2). Add means to increase SP by 0x30 bytes after the first two instructions are executed. The state of the call stack is shown below. You can see before calling RET. Sp, FP already points to func2’s call stack. This is called stack balancing, and the function will be restored to its original state after execution.2. Look at the values of x29, x30, sp after the execution of the first two instructions. This is consistent with the call stack we analyzed.3. Ret indicates return. After the execution of this instruction, the PC (address of the current instruction executed by the program) register will be executed from the LR register. We find that the value of LR is 0x102a7d730. We enter the SI step to see the address of the next instruction to be executed. The diagram below. Jump to the address of the next instruction that calls func3 inside func2. That’s what’s in LR

Func2 calls what follows func3

The rest of the content is the same, I don’t need to analyze it, but it’s also a local variable on the stack, stack recycle and so on.

conclusion

Function call stack is actually the top register FP (X29), the address of the next instruction lr(X30) register and function parameters, local variables into the stack, function call end stack balance again. The call stack is a contiguous set of addresses extending from the highest address to the lowest address.

Stack overflow

Understanding the function call stack, it is not difficult to understand the stack overflow, for example, a recursive call with no exit, the stack space will continue to extend from the high address to the ground address, and eventually run out of stack space to throw exceptions.

This article is my understanding of the call stack from the example code above, and I feel free to correct any errors.