We all know that the function call is realized through the stack, and we know that the local variables of the function are stored in the stack. However, the implementation details of the stack may not be clear. This article will introduce how to implement function stack on Linux platform.
Stack frame structure
When a function is called, a space is opened in the stack space for the function to use. Therefore, let's first understand the structure of the general stack frame.
As shown in the figure, the stack grows from the high address to the ground address, and the stack has its top and bottom. The place where the stack goes in and out is called the top of the stack.
In the CPU of x86 system, rsp is the stack pointer register, which stores the address of the top of the stack. rbp stores the address at the bottom of the stack. The function stack space is mainly determined by these two registers.
When the program is running, the stack pointer RSP can move, and the stack pointer and frame pointer rbp can only store one address at a time. Therefore, at any time, this pair of pointers point to the stack frame structure of the same function.
The frame pointer rbp does not move. To access the elements in the stack, you can use - 4(%rbp) or 8(%rbp) to access the elements below or above the% rbp pointer.
After understanding these, let's take a specific example:
#include <stdio.h>
int sum (int a,int b)
{
int c = a + b;
return c;
}
int main()
{
int x = 5,y = 10,z = 0;
z = sum(x,y);
printf("%d\r\n",z);
return 0;
}
The disassembly is as follows. Next, we will analyze the stack changes during the function call step by step compared with the assembly code.
0000000000000000 <sum>: 0: 55 push %rbp 1: 48 89 e5 mov %rsp,%rbp 4: 89 7d ec mov %edi,-0x14(%rbp) # Parameter transfer 7: 89 75 e8 mov %esi,-0x18(%rbp) # Parameter transfer a: 8b 55 ec mov -0x14(%rbp),%edx d: 8b 45 e8 mov -0x18(%rbp),%eax 10: 01 d0 add %edx,%eax 12: 89 45 fc mov %eax,-0x4(%rbp) # local variable 15: 8b 45 fc mov -0x4(%rbp),%eax # Store results 18: 5d pop %rbp 19: c3 retq 000000000000001a <main>: 1a: 55 push %rbp # Save% rbp. rbp, the address at the bottom of the stack 1b: 48 89 e5 mov %rsp,%rbp # Set the new stack pointer. rsp stack pointer, pointing to the address of the top of the stack 1e: 48 83 ec 10 sub $0x10,%rsp # Allocate 16 bytes of stack space.% n rsp = %rsp-16 22: c7 45 f4 05 00 00 00 movl $0x5,-0xc(%rbp) # assignment 29: c7 45 f8 0a 00 00 00 movl $0xa,-0x8(%rbp) # assignment 30: c7 45 fc 00 00 00 00 movl $0x0,-0x4(%rbp) # assignment 37: 8b 55 f8 mov -0x8(%rbp),%edx 3a: 8b 45 f4 mov -0xc(%rbp),%eax 3d: 89 d6 mov %edx,%esi # Parameter passing, right to left 3f: 89 c7 mov %eax,%edi # Parameter transfer 41: e8 00 00 00 00 callq 46 <main+0x2c> # Call sum 46: 89 45 fc mov %eax,-0x4(%rbp) 49: 8b 45 fc mov -0x4(%rbp),%eax # Store calculation results 4c: 89 c6 mov %eax,%esi 4e: 48 8d 3d 00 00 00 00 lea 0x0(%rip),%rdi # 55 <main+0x3b> 55: b8 00 00 00 00 mov $0x0,%eax 5a: e8 00 00 00 00 callq 5f <main+0x45> 5f: b8 00 00 00 00 mov $0x0,%eax 64: c9 leaveq 65: c3 retq
Before function call
Before the function is invoked, the caller will prepare the calling function. Firstly, a 16 byte space is opened on the function stack to store the three int variables defined, and the stack of main function is established.
Next, three variables are assigned values.
The following four lines of code are used to pass parameters. We can see that the function parameters are passed in reverse order: the nth parameter is passed in first, and then the nth-1st parameter (CDECL Convention).
mov -0x8(%rbp),%edx mov -0xc(%rbp),%eax mov %edx,%esi # Parameter passing, right to left mov %eax,%edi # Parameter transfer
Finally, it will execute the call instruction and call the sum function.
callq 46 <main+0x2c> # Call sum
In fact, the CALL instruction also implies an action of pressing the return address (that is, the address of the next instruction of the CALL instruction) on the stack (completed by hardware).
Specifically, when the call instruction is executed, first put the address of the next instruction on the stack, and then jump to the beginning of the corresponding function execution.
Function call
After entering the sum function, we see the first two lines of the function:
push %rbp mov %rsp,%rbp
The meaning of these two assembly instructions is: first put the rbp register on the stack, and then assign the stack top pointer rsp to rbp.
The "mov rbp rsp" instruction seemingly overwrites the original value of rbp with rsp, but it is not.
Because before assigning a value to rbp, the original rbp value has been pressed on the stack (at the top of the stack), and the new rbp just points to the top of the stack. At this time, the rbp register is already in a very important position.
The register stores an address in the stack (the top of the stack after the original rbp is put into the stack). Based on this address, the return address and parameter value can be obtained upward (the bottom direction of the stack), and the function local variable value can be obtained downward (the top direction of the stack), and the rbp value of the function call of the previous layer is stored at this address.
Generally speaking, the return address is at% rbp+4, the first parameter value is at% rbp+8 (the last stacked parameter value is assumed to occupy 4 bytes of memory here), the first local variable is at% rbp-4, and the rbp value of the previous layer is at% rbp-4.
Because the address in rbp is always "the rbp value of the previous function call", in each function call, the return address and parameter value can be obtained through the current% rbp value "up (stack bottom direction)" and "down (stack top direction)".
The following four instructions are executed.
mov %edi,-0x14(%rbp) # Parameter transfer mov %esi,-0x18(%rbp) # Parameter transfer mov -0x14(%rbp),%edx mov -0x18(%rbp),%eax add %edx,%eax mov %eax,-0x4(%rbp)
The above instruction saves the two parameters passed from main to sum in the appropriate position of the current stack frame by rbp plus offset, and then takes them out and puts them into the register. It seems a bit superfluous. This is because the optimization level is not specified for GCC during compilation, and no optimization is done by default during gcc compiler, so it looks verbose.
It should be noted that the two parameters and return values of sum are int, accounting for only 4 bytes in memory. In the figure, each stack memory unit is aligned according to the 8-byte address boundary, so it is like this in the following figure.
Let's look at the next three instructions.
add %edx,%eax mov %eax,-0x4(%rbp) # local variable mov -0x4(%rbp),%eax # Store results
The first instruction above is responsible for performing the addition operation and storing the result in eax. The second instruction stores the value in eax in the memory where the local variable c is located. The third instruction reads the value of the local variable c into eax. It can be seen that the local variable c is arranged in the memory corresponding to the address% rbp -0x4 by the compiler.
Next, continue
pop %rbp retq
The functions of these two instructions are equivalent to the following instructions:
mov %rbp,%rsp pop %rbp pop %rip
That is, when operating the above two instructions, first assign the rsp, whose value is the address where the rbp value of the calling function is stored. Therefore, you can assign the value to the rbp through the out of stack operation to retrieve the rbp of the calling function.
Through the stack structure, we can know that rbp is the execution address of the next instruction of the calling function calling the called function, so it needs to be assigned to rip to retrieve the instruction execution address in the calling function.
Therefore, when the whole function jumps back to main, its RSP and RBP will change back to the stack pointer of the original main function. C language programs use this way to ensure that after the function is called, they can continue to execute the original program.
After function call
When the function finally returns, continue to execute the following instruction:
mov %eax,-0x4(%rbp) # Assign the return value of the sum function to the variable z
The above instruction puts the result in eax into the memory indicated by RBP - 0x4, where the local variable z of main is also located.
Further instructions are as follows:
mov %eax,-0x4(%rbp) mov -0x4(%rbp),%eax # Calculation results mov %eax,%esi mov %eax,%esi lea 0x0(%rip),%rdi mov $0x0,%eax callq 5f <main+0x45>
The above instructions first prepare parameters for printf, then call printf, which is similar to the process of calling sum, so that CPU can be directly executed to the second countdown leave instructions of main.
mov $0x0,%eax
The instruction function is to return main value 0 to register eax, and so on when main returns, main can get the value.
Executing the leave instruction is equivalent to executing the following two instructions:
mov %rbp, %rsp pop %rbp
The leave instruction first copies the value of rbp to rsp, so that rsp points to the stack unit referred to by rbp, and then the leave instruction pop s the value of the stack unit to rbp, so that rsp and rbp return to the state when they just entered main.