Personal understanding of the stack in function calls

This is my first blog. Due to the needs of the company project, I will temporarily say goodbye to C language for a while. So I will record some of my previous experiences in learning C language here, hoping to share it with everyone, and also record the problems and doubts I encountered during the learning process (actually, the areas that I don’t understand during the learning process). Okay, without further ado, let’s start the microblog content, O(∩_∩)O haha~

Next, we will analyze the understanding of the stack in function calls through the following questions:

• How is the stack structured in memory during a function call?
• How to perform specific operations such as call, ret, leave, etc. in assembly language?
• How is the task stack and data stored in Linux?

1. How is the stack structured in memory during a function call?

Computers, embedded devices, smart devices, etc. are actually composed of two parts: software and hardware. The specific implementation may be complicated, but the overall structure is like this. Software runs on hardware and tells the hardware what to do. The operating system software is loaded from the disk to the memory during the startup process through BIOS, bootloader, etc. (if there are such processes), while custom software is written and stored on the disk, and only runs in the memory after being loaded.

First, let’s take a look at what a heap, stack, and stack are. We often say that the stack is actually equivalent to the concept of a stack.

In a popular sense, the heap is a very large memory space from which different programmers can take out a section for their own use. After use, the programmer must release it. If it is not released, this part of the storage space will not be available for other programs. The storage space of the heap is discontinuous because it will be discontinuous due to the application of different sizes of heap space at different times. The growth of the heap is from low address to high address.

The understanding of stack is that stack is a storage space used by the system or operating system. It is generally invisible to programmers, unless the programmer builds the stack by himself through assembly from the beginning. The stack will be released by the system management unit. The stack grows from high address to low address, that is, the bottom of the stack is at a high address and the top of the stack is at a low address.

Next, let's look at the loading of the application. After the application is loaded into the memory, the operating system allocates a stack for it, and the entry function of the program will be the main function. However, the main function is not the first function called. Let's explain it through a simple example.

#include <stdio.h>
#include <string.h>

int function(int arg)
{
    return arg;
}
int main(void)
{
    int i = 10;
    int j;
    j = function(i);
    printf("%d\n",j);
    return 0;
}

Use gcc -S main.c to generate the assembly file main.s, where the assembly code of function is as follows:

function:
.LFB0:
    .cfi_startproc
    pushq %rbp
    .cfi_def_cfa_offset 16
    .cfi_offset 6, -16
    movq %rsp, %rbp
    .cfi_def_cfa_register 6
    movl %edi, -4(%rbp)
    movl -4(%rbp), %eax
    popq %rbp
    .cfi_def_cfa 7, 8
    ret
    .cfi_endproc

It can be seen that when a function is called, the bottom of the stack of the calling function is first pushed into the stack of its own function (pushq %rbp), and then the top of the original function stack rsp is used as the bottom of the stack of the current function (movq %rsp, %rbp). When the function is finished, the rbp pushed into the stack is popped back into rbp (popq %rbp). The current function assembly function does not show the changes in the top of the stack (the changes in rsp). We can see the changes in the top of the stack through the main function. The assembly code is as follows:

main:
.LFB1:
    .cfi_startproc
    pushq %rbp
    .cfi_def_cfa_offset 16
    .cfi_offset 6, -16
    movq %rsp, %rbp
    .cfi_def_cfa_register 6
    subq $16, %rsp
    movl $10, -4(%rbp)
    movl -4(%rbp), %eax
    movl %eax, %edi
    call function
    movl %eax, -8(%rbp)
    movl -8(%rbp), %eax
    movl %eax, %esi
    movl $.LC0, %edi
    movl $0, %eax
    call printf
    movl $0, %eax
    leave
    .cfi_def_cfa 7, 8
    ret
    .cfi_endproc

From the above assembly code, we can see that the first step is to push the stack and set the new stack bottom. From this, we can see that the main function is also a called function, not the first calling function. The yellow part in the code is the change of the current stack top. From the subq used, we can know that the address of the stack top is smaller than the address of the stack bottom, so the stack grows from high address to low address.

The following may be a bit confusing, so read it slowly. The function call process will be described in words. The calling function will push the actual parameters of the called function into the stack of the calling function from right to left. The called function is called by the call instruction. First, the return address (that is, the address of the instruction after the call instruction) is pushed into the stack of the calling function. At this time, the address stored in the rsp register is the next address value of the memory address storing the return address. At this time, the stack structure of the calling function is formed, and then it will enter the scope of the called function. The called function first pushes the rbp of the calling function into the stack of the called function (in fact, this address is the address stored in the rsp register). Next, this address will be used as the rbp address of the called function, and then there will be a movq %rsp, %rbp instruction to set the bottom of the stack of the called function. The stack structure of the function call described above is shown in the figure below.

2. How to perform specific operations such as call, ret, leave, etc. in assembly language?

push: push data into the stack. The specific operation is to first decrement rsp and then push the data into the memory address pointed to by sp. The rsp register always points to the top of the stack, but not an empty unit.

pop: pop the data from the stack, then perform rsp addition operation to ensure that the rsp register points to the top of the stack, not an empty cell.

call: Push the address of the next instruction into the stack of the currently called function (push the PC instruction into the stack because the PC instruction has been automatically increased when the call instruction is taken out from the memory), then change the PC instruction to the address of the called function, and the program pointer jumps to the new function.

ret: When the instruction points to the ret instruction line, it means that a function has ended. At this time, rsp has moved from the stack of the called function to the return address of the calling function. ret assigns the content of the top address of the stack pointed to by rsp to PC, and then executes the next instruction of the call function.

leave: equivalent to mov %esp, %ebp, pop ebp. The first instruction actually uses the bottom of the stack of the called function pointed to by ebp as the new top of the stack. The pop instruction is equivalent to popping the bottom of the stack of the called function, and rsp points to the return address.

int: By adding the interrupt number after it, the software can trigger an interrupt. Most system calls in the Linux operating system are implemented in this way. In other real-time operating systems, when the operating system is ported, there will be a tick heart function that also has this implementation.

I won't talk about other assembly instructions here, because there are many assembly instructions and the hardware CPU registers vary depending on the hardware. This section will talk about several assembly instructions used when building functions to enter and leave functions. These instructions are related to stack changes. It will be helpful to understand them when you build assembly functions yourself or read the system calls of the Linux operating system. In the hardware registers, rsp and rbp are used to indicate the top and bottom of the stack.

3. How is the task stack and data stored in Linux?

There are two types of Linux task stacks: kernel stack and user stack. Let's briefly introduce these two stacks. If there is a chance, I will introduce these two stacks in detail in the future.

1. Kernel stack

The Linux operating system is divided into kernel state and user state. User state code has many restrictions on accessing code and data. User state is mainly used by programmers to write programs. Code in user state cannot access data in Linux kernel state at will. This is mainly to set user state permissions for security considerations. However, user state can access the content of specified kernel state through system call interface, interrupt, exception, etc. Kernel state is mainly used for operating system kernel operation and management. It can access memory addresses and data without restrictions and has relatively large permissions.

The processes of the Linux operating system are dynamic and have a life cycle. The operation of a process is the same as that of an ordinary program, and requires the help of a stack. If a stack is allocated in advance in the kernel storage area, it will waste kernel memory (about 3G of space for the task address) and will not be able to flexibly build tasks. Therefore, when creating a new task, the Linux operating system allocates an 8k storage area for it to store the kernel-state stack and thread descriptors of the process. The thread descriptor is located in the low address area of ​​the allocated storage area and has a fixed size, while the kernel-state stack extends from the high address of the storage area to the low address. If the previous version allocated 4k of storage space for the kernel-state stack and thread descriptor, it is necessary to allocate additional stacks for interrupts and exceptions to prevent task stack overflow.

2. User-mode stack

For a 32-bit Linux operating system, each task will have a 4G addressing space, of which 0-3G is the user addressing space and 3G-4G is the kernel addressing space. Each task created will have a 0-3G user addressing space, but the 3G-4G kernel addressing space is shared by all tasks. These addresses are all linear addresses and need to be converted into physical addresses through address mapping. In order to prevent each task from confusing the address when accessing the 0-3G user space, the memory management unit of each task will have its own page directory pgd. A new pgd will be created at the beginning of task creation, and the task will map the physical address to the 0-3G space through address mapping. The user-state stack is allocated in this 0-3G user addressing space, just like the main function and function function to build the stack before, but the specific physical address to which it is mapped still needs the memory management unit to do the mapping operation. In short, the stack of the user state of the Linux task is allocated and released by the operating system like ordinary applications, and is invisible to programmers. However, due to the operating system, the addressing of the task user program is limited. If there is a chance, I will introduce my personal understanding of Linux memory management later.