What does the linux stack mean?

Designed for programming, automatic code writing robot, free to open. Today, Xiaobian will share with you the relevant knowledge points of what linux stack refers to. The content is detailed and the logic is clear. I believe most people still know this knowledge too well, so I share this article for your reference. I hope you will gain something after reading this article. Let's take a look at it together.

In linux, stack is a serial data structure; This data structure is characterized by last-in, first-out, and data can only be pushed and popped at one end of the series. The stacks in linux can be divided into process stack, thread stack, kernel stack and interrupt stack.

Operating environment of this tutorial: linux7.3 system and Dell G3 computer.

Linux stack is a serial data structure. This data structure is characterized by LIFO, Last In First Out), and the data can only be push and popped at one end of the series (called the top of the stack).

Process stack

Thread stack

Kernel stack

Interrupt stack

Most processor architectures have an implementation hardware stack. There are special stack pointer registers and specific hardware instructions to complete the operation of entering/exiting the stack. For example, in the ARM architecture, R13 (SP) pointer is a stack pointer register, while PUSH is an assembly instruction for pushing the stack, and POP is an assembly instruction for popping the stack.

[Extended reading] Introduction to ARM registers

The ARM processor has 37 registers. These registers are arranged in partially overlapping groups. Each processor mode has a different set of registers. Grouped registers provide fast context switching for handling processor exceptions and privileged operations.

The following registers are provided:

Thirty 32-bit general-purpose registers:

There are fifteen general registers, which are r0-r12, sp and lr.

Sp (r13) is a stack pointer. The C/C++ compiler always uses sp as a stack pointer.

Lr (r14) is used to store the return address when calling the subroutine. If the return address is stored on the stack, lr can be used as a general register.

Program counter (pc): instruction register

Application Status Register (APSR): A copy of the status flag of the arithmetic logic unit (ALU) is stored.

Current program status register (CPSR): it stores APSR flag, current processor mode, interrupt disable flag, etc.

Saved Program Status Register (SPSR): When an exception occurs, use SPSR to store CPSR.

The above is the principle and implementation of the stack. Let's take a look at what the stack does. The function of stack can be embodied in two aspects: function call and multi-task support.

First, function call We know that a function call has the following three basic processes:

Call the incoming parameters.

Spatial management of local variables

Function return

Function calls must be efficient, and storing data in CPU general registers or RAM memory is undoubtedly the best choice. Taking the transfer of call parameters as an example, we can choose to use CPU general registers to store parameters. However, the number of general registers is limited, and when there is a nested function call, the reuse of the original general registers by sub-functions will inevitably lead to conflicts. Therefore, if you want to use it to pass parameters, you must save the value of the original register before calling the sub-function, and then restore the value of the original register when the sub-function exits.

Generally, the number of call parameters of functions is relatively small, so general registers can meet certain requirements. However, the number and occupied space of local variables are relatively large, and it is hard to rely on limited general registers, so we can use some RAM memory areas to store local variables. But where is the appropriate storage? There should be no conflict when nested functions are called, and attention should be paid to efficiency.

In this case, stack undoubtedly provides a good solution. First, for the conflict of general register passing parameters, we can temporarily push the general register into the stack before calling the sub-function; After the sub-function is called, the saved register will pop up again and be restored. Second, the space application of local variables only needs to move down the top pointer of the lower stack; Move the pointer at the top of the stack back to complete the space release of local variables; 3. For the return of the function, only the return address needs to be pushed into the stack before calling the sub-function, and the return address of the function will be popped up to the PC pointer after calling the sub-function, that is, the return of the function call is completed;

So the three basic processes of the above function call evolved into the process of recording a stack pointer. Every time a function is called, it is accompanied by a stack pointer. Even if the calling function is nested circularly, as long as the corresponding function stack pointers are different, there will be no conflict.

[Extended reading]: function Stack Frame

Function calls are often nested, and at the same time, there will be information of multiple functions in the stack. Each unfinished function occupies an independent continuous area, called a Stack Frame. The stack frame contains function parameters, local variables and data needed to restore the previous stack frame, etc. The order of function calling into the stack is:

Argument N~1 → Return address of the main tone function → Frame base pointer EBP of the main tone function → Local variable 1~N of the tuned function.

The boundary of the stack frame is defined by the stack frame base address pointer EBP and the stack pointer ESP. EBP points to the bottom (high address) of the current stack frame and has a fixed position in the current stack frame. ESP points to the top (low address) of the current stack frame. When the program is executed, ESP will move with the data entering and exiting the stack. Therefore, the access to most data in the function is based on EBP. The typical memory layout of the function call stack is shown in the following figure:

Second, multi-tasking support However, the meaning of stack is not just function call. With its existence, the multi-tasking mode of operating system can be constructed. Let's take the call of the main function as an example. The main function contains an infinite loop body, in which the function A is called first and then the function B is called.

func B():   return; func A():   B(); func main():   while (1)     A();

Imagine that in the case of a single processor, the program will stay in this main function forever. Even if another task is waiting, the program can't jump to another task from this main function. Because if it is a function call relationship, it is still a task of the main function in essence, and it cannot be considered as multi-task switching. At this moment, the main function task itself is actually bound to its stack. No matter how nested the calling function is, the stack pointer moves within the stack.

It can be seen that a task can be characterized by the following information:

Main function body code

Main function stack pointer

Current CPU register information

If we can save the above information, we can force the CPU to handle other tasks. As long as you want to continue to perform this main task in the future, you can restore the above information. With such a prerequisite, multitasking has a foundation for existence, and another meaning of stack existence can be seen. In the multi-task mode, when the scheduler thinks it is necessary to switch tasks, it only needs to save the task information (that is, the above three contents). Restore the state of another task, and then jump to the last running position, and you can resume running.

It can be seen that each task has its own stack space. It is with an independent stack space that different tasks can even mix the function body of the task for code reuse. For example, a main function can have two task instances. Since then, the framework of the operating system has also been formed. For example, when a task calls sleep () to wait, it can voluntarily give up the CPU for other tasks, or the time-sharing operating system task will be forced to give up the CPU when the time slice runs out. Either way, just try to switch the context space of the task and switch the stack.

[Extended reading]: The relationship among tasks, threads and processes

Task is an abstract concept, that is, an activity completed by software; Threads are the actions needed to complete tasks; Process refers to the collective name of the resources needed to complete this action; About the relationship between the three, there is an image metaphor:

Task = Delivery

Thread = driving a delivery truck

System scheduling = deciding which delivery truck is suitable to drive.

Process = road+gas station+delivery vehicle+garage

How many stacks are there in Linux? Memory locations of various stacks? After introducing the working principle and function of the stack, we return to the Linux kernel. The kernel divides the stack into four types:

Process stack

Thread stack

Kernel stack

Interrupt stack

1. Process Stack The process stack belongs to the user mode stack and is closely related to the Virtual Address Space of the process. Then let's first understand what a virtual address space is: under a 32-bit machine, the virtual address space is 4G. These virtual addresses are mapped to physical memory through a Page Table, which is maintained by the operating system and referenced by the memory management unit (MMU) hardware of the processor. Each process has its own set of page tables, so it seems that each process has the whole virtual address space.

The Linux kernel divides this 4G byte space into two parts, and the highest 1G byte (0xC0000000-0xFFFFFFFF) is used by the kernel, which is called kernel space. The lower 3G bytes (0x00000000-0xBFFFFFFF) are used by each process, which is called user space. Each process can fall into the kernel state through system calls, so the kernel space is shared by all processes. Although the kernel and user-mode processes occupy such a large address space, it does not mean that they use so much physical memory, only that they can dominate such a large address space. They are used by mapping physical memory into virtual address space as needed.

Linux has a standard layout for the process address space, which consists of different memory segments. The main memory segments are as follows:

Text Segment: memory mapping of executable file code.

Data Segment: Memory mapping of initialized global variables of executable files.

BSS Segment: uninitialized global variable or static variable (initialized with zero pages).

Heap: Store dynamic memory allocation and anonymous memory mapping.

Stack: the process user space stack, which is automatically allocated and released by the compiler and stores the parameter values of functions and the values of local variables.

Memory Mapping Segment: any memory mapping file.

And the stack area in the above process virtual address space refers to what we call the process stack. The initialization size of the process stack is calculated by the compiler and linker, but the real-time size of the stack is not fixed, and the Linux kernel will dynamically grow the stack area according to the stack entry (in fact, adding new page tables). However, it doesn't mean that the stack area can grow indefinitely, but it also has a maximum limit of RLIMIT_STACK (generally 8M). We can view or change the value of RLIMIT_STACK through ulimit.

[Extended reading]: How to confirm the size of the process stack

If we want to know the size of the stack, we must know the starting address and ending address of the stack. Getting the start address of the stack is very simple, just embedding the assembly instruction to get the esp address of the stack pointer. Getting the end address of the stack is a bit troublesome. We need to overflow the stack by recursive function first, and then print out the stack pointer esp when the stack overflows in GDB. The code is as follows:

/* file name: stacksize.c */ void *orig_stack_pointer; void blow_stack() {     blow_stack(); } int main() {     __asm__("movl %esp, orig_stack_pointer");     blow_stack();     return 0; }

$ g++ -g stacksize.c -o ./stacksize $ gdb ./stacksize (gdb) r Starting program: /home/home/misc-code/setrlimit Program received signal SIGSEGV, Segmentation fault. blow_stack () at setrlimit.c:4 4       blow_stack(); (gdb) print (void *)$esp $1 = (void *) 0xffffffffff7ff000 (gdb) print (void *)orig_stack_pointer $2 = (void *) 0xffffc800 (gdb) print 0xffffc800-0xff7ff000 $3 = 8378368    // Current Process Stack Size is 8M

There is a global introduction to the address space of the process, so let's take a look at how the above memory layout is reflected in the Linux kernel. The kernel uses a memory descriptor to represent the address space of the process, which represents the information of all the address spaces of the process. The memory descriptor is represented by the mm_struct structure. The descriptions of each field in the memory descriptor structure are given below. Please look at it together with the layout diagram of the previous process memory segment:

struct mm_struct {     struct vm_area_struct *mmap; /* memory area linked list */     struct rb_root mm_rb; /* Red and black tree formed by VMA */      ...     struct list_head mmlist; /* Linked list formed by all mm_struct */      ...     unsigned long total_vm; /* Number of all pages */     unsigned long locked_vm; /* Locked page data */     unsigned long pinned_vm;                /* Refcount permanently increased */     unsigned long shared_vm; /* Number of Shared pages (files) */     unsigned long exec_vm; /* Number of executable pages VM_EXEC & ~VM_WRITE */     unsigned long stack_vm; /* Number of pages in stack area VM _ growup/down */     unsigned long def_flags;     unsigned long start_code, end_code, start_data, end_data; /* code segment, data segment start address and end address */     unsigned long start_brk, brk, start_stack; /* Start address of stack area, start address and end address of heap area */     unsigned long arg_start, arg_end, env_start, env_end; /* Start address and end address of command line parameters and environment variables */      ...     /* Architecture-specific MM context */     mm_context_t context; /* Architecture specific data */     /* Must use atomic bitops to access the bits */     unsigned long flags; /* Status flag bit */      ... /* coredumping and numa and hugepage related structures */ };

[Extended reading]: Dynamic growth of process stack

In the process of running, by constantly pushing data into the stack area, when the capacity of the stack area is exceeded, the memory area corresponding to the stack will be exhausted, which will trigger a page fault. After the exception falls into the kernel state, the exception will be handled by the expand_stack () function of the kernel, and then acct_stack_growth () will be called to check whether there is any suitable place for the stack growth.

If the size of the stack is lower than RLIMIT_STACK (usually 8MB), the stack will be lengthened, the program will continue to execute, and nothing will happen. This is a conventional mechanism to expand the stack to the required size. However, if the maximum stack space is reached, stack overflow will occur and the process will receive a segmentation fault signal from the kernel.

Dynamic stack growth is the only situation where access to unmapped memory areas is allowed, and any other access to unmapped memory areas will trigger page faults, resulting in segment errors. Some mapped areas are read-only, so trying to write these areas will also lead to segment errors.

Second, the thread stack from the perspective of the Linux kernel, in fact, it does not have the concept of thread. Linux treats all threads as processes, and it unifies threads and processes into task_struct without distinction. A thread is only regarded as a process that shares some resources with other processes, and whether or not to share the address space is almost the only difference between a process and the so-called thread in Linux. When the thread is created, the CLONE_VM tag is added, so that the memory descriptor of the thread will directly point to the memory descriptor of the parent process.

if (clone_flags & CLONE_VM) {     /* * current is the parent process and tsk is the shared child process during fork () execution.      */     atomic_inc(¤t->mm->mm_users);     tsk->mm = current->mm;   }

Although the address space of a thread is the same as that of a process, there are some differences in the stack of its address space. For Linux process or main thread, its stack is generated at fork time, which is actually to copy the stack space address of the father, and then copy on write (cow) and dynamically grow. However, for the sub-thread generated by the main thread, its stack will no longer be like this, but will be fixed in advance, using mmap system call, which does not have VM_STACK_FLAGS tag. This can be seen from the allocate_stack () function in glibc's nptl/allocatestack.c:

mem = mmap (NULL, size, prot, MAP_PRIVATE|MAP_ANONYMOUS|MAP_STACK, -1, 0);

Because the mm->start_stackaddress of the thread is the same as the process to which it belongs, the start address of the thread stack is not stored in task_struct, and the stack addr in pthread_attr_t should be used to initialize task_struct->thread->sp(sp points to the struct pt_regs object, which is used to save the register site of the user process or thread). None of this matters. What matters is that the thread stack cannot grow dynamically, and once it is exhausted, it will be gone, which is different from the fork of the generation process. Because the thread stack is a memory area mapped from the address space of the process, it is private to the thread in principle. However, when all threads of the same process are generated, many fields of the generator's task_struct, including all vma, can still be accessed by other threads if they want, so we must pay attention to it.

Third, the process kernel stack will inevitably fall into the kernel through system calls in the life cycle of each process. After the execution system calls fall into the kernel, the stack used by these kernel codes is not the stack in the original process user space, but a stack in a separate kernel space, which is called the process kernel stack. When the process is created, the process kernel stack is allocated from the thread_info_cache cache pool through slab allocator, and its size is THREAD_SIZE, which is generally a page size of 4k;

union thread_union {                                            struct thread_info thread_info;                          unsigned long stack[THREAD_SIZE/sizeof(long)]; };

Thread_union process kernel stack is closely related to task_struct process descriptor. Because the kernel often accesses task_struct, it is very important to get the descriptor of the current process efficiently. Therefore, the kernel uses a space at the head of the process kernel stack to store the thread_info structure, and the descriptor of the corresponding process is recorded in this structure. The relationship between them is as follows (the corresponding kernel function is dup_task_struct ()):

With the above association structure, the kernel can first get the stack top pointer esp, and then get the thread_info through esp. Here's a trick. You can directly get the address of thread_info by adding the address of esp to ~(THREAD_SIZE-1). Because the thread_union structure is applied from the Slab cache pool of the thread_info_cache, and the thread_info_cache ensures that the address is aligned with the THREAD_SIZE when kmem_cache_create is created. Therefore, the address of thread_union can be obtained only by aligning the stack pointer with THREAD_SIZE, and the address of thread_union can also be obtained. After thread_info is successfully obtained, the task_struct is successfully obtained by directly taking out its task member. In fact, the above description, that is, the implementation method of current macro:

register unsigned long current_stack_pointer asm ("sp"); static inline struct thread_info *current_thread_info(void)   {                                                                     return (struct thread_info *)                                         (current_stack_pointer & ~(THREAD_SIZE - 1)); }                                                             #define get_current() (current_thread_info()->task) #define current get_current()

4. When the interrupt stack process falls into the kernel state, the kernel stack is needed to support kernel function calls. The same is true for interrupts. When the system receives an interrupt event, it also needs an interrupt stack to support function calls. Because the system is in the kernel state when it is interrupted, the interrupt stack can be shared with the kernel stack. But whether it is shared or not is closely related to the specific processing architecture.

The interrupt stack on X86 is independent of the kernel stack. The allocation of the memory space where the independent interrupt stack is located occurs in the irq_ctx_init () function of arch/x86/kernel/irq_32.c (if it is a multiprocessor system, then each processor will have an independent interrupt stack), and the function uses __alloc_pages to allocate two physical pages in the low-end memory area, that is, 8KB in size. Interestingly, this function will also allocate an independent stack of the same size for softirq. In this way, softirq will not be executed on hardirq's interrupt stack, but in its own context.

The interrupt stack and kernel stack on ARM are shared; There is a negative factor in sharing interrupt stack and kernel stack. If interrupts are nested, it may cause stack overflow, which may destroy some important data of kernel stack, so the stack space will inevitably be stretched.

That's what the linux stack refers to. Thank you for reading! I believe that everyone has gained a lot after reading this article. Xiaobian will update different knowledge for everyone every day. If you want to learn more knowledge, please pay attention to the Yisu cloud industry information channel.

Ask AI for details