The concept of stack

The concept of stack, heap and stack

Heap: The heap can be viewed as a tree. The heap is a storage space of a certain size requested when the program is running. That is, memory is dynamically allocated, and access to it is no different from access to general memory.

Stack: A stack is a linear table with restricted operations. Insertion and deletion operations are only allowed at one end of the stack. This end is called the top of the stack, and the other end is called the bottom of the stack. It follows the first-in, last-out principle.

Stack: The stack itself is a stack, but because modern Chinese likes to use two words to represent one thing, the term "stack" is used instead of stack.

Why is the stack mechanism introduced in the CPU?

When the program is executed, the corresponding change is the PC pointer, which always points to the next instruction to be executed. However, the PC pointer does not always increase one by one. When there is a nested function call or a function jump (such as an if...else statement), the PC pointer will jump.

When a function call occurs, the CPU needs to return to its original position when the function call ends, that is, the PC pointer needs to jump. The jump of the PC pointer also requires the PC pointer to be assigned a value. The value assigned to the PC pointer is the return address of the function. So where should the CPU get this return address? Early CPU designs designed a return address register.

The function of the return address register is to store the return address when the function is called, so that when the function call ends, the value of this register is assigned to the PC pointer register to complete the function return. However, function calls may be nested in several layers. The return address of the first call needs to be stored, and the return address of the second call still needs to be stored. When using C language, library functions will be used. In the process of using library functions, multiple layers of function calls may occur, which will cause the return address register to be insufficient. Therefore, a more intelligent mechanism is introduced, that is, the stack.

Characteristics and functions of stack

characteristic

The stack is a continuous storage space

The stack works in a first-in-last-out manner.

Data can only be added to or removed from the top of the stack

The stack can save the order of data

Supplement: The stack memory is used from bottom to top, the so-called "top" is the location where the data was last placed

And for most CPUs, "top" refers to the low-level storage space

Basic operation

PUSH: Add content to the top of the stack

Pop: Take the contents at the top of the stack out

Three functions of the stack

The C language compiler uses the stack to complete parameter passing and return value passing - C language function call

The assembler can use the stack to save the values ​​of local variables and registers.

The CPU hardware uses a stack to save return addresses and register context

Solution to the problem of storing the return address of a function call

With a mechanism like the stack, we can handle the problems of function jumping and nested function calls very well.

When nested function calls occur, when a first-level function call occurs, the current PC pointer register value is pushed into the stack. When the function call has not returned yet, when a function call occurs again, the current PC pointer register value of the second function call needs to be pushed into the stack. When the second-level function call needs to return, it only needs to take out the data from the top of the stack. This value is the return address of the second function call. Assign it to the PC pointer register to complete the return of the second-level function. When the first-level function returns, it only needs to take out a value from the stack again and assign it to the PC pointer register, so that the first-level function can return.

To sum up, this is the entire process of function calling, which perfectly utilizes the first-in-last-out mechanism of the stack.

The relationship between local variables and stack

In C language, the parameters and return values ​​of functions are passed using the stack. Local variables in C language will also occupy a certain amount of storage space in the stack according to the compiler. Therefore, the stack will be gradually consumed according to the use of C language. The fact that local variables are stored in the stack also proves that local variables have a life cycle, because when the function call ends and the function returns, the storage space of local variables will be released one by one, popped out one by one, and no longer used, and the value of the local variable will be released.

Stack Overflow

The location of the stack

The above describes the role of the stack, but where is the stack? For the CPU, the CPU uses a continuous off-chip storage space as a stack, but how does the CPU find this storage space? Here the concept of the stack pointer register is introduced. The stack pointer register specifies the top position of the stack, that is, the top of the off-chip memory used for the stack storage space.

How Stack Overflow Works

Before introducing the principle of stack overflow, let me point out that the storage location of the heap and global variables is on the heap.

The stack storage space and variable space (heap) use the same end memory space, and have the following characteristics:

Variable space is divided from low address to high address (global variables used in C language programming)

The stack space grows from high address to low address

The following figure is a schematic diagram of the variable space and stack space in the memory

Therefore, when the program is running, along with the calls of various functions, the stack space is in a state of ups and downs, and the heap also uses memory on it. Considering the extreme case, when there are too many global variables defined and the functions are nested too deeply, the heap space and the stack space may intersect, causing the PC pointer to take a value from the stack as the return address, but the value taken is not the return address, but a global variable, causing the program to run away. This is the principle of stack overflow.

Stack running example

S12MCU

The assembly instructions involved in the example are:

NOP: Do not perform any operation

LDS: Assign a value to the stack pointer

PSHx: put the value in register x into the stack

JSR: Jump to sub-branch

RTS: Return from sub-branch

The following figure shows a section of CPU memory:

The following figure shows several instructions to be executed:

The first step of instruction execution

The blue arrow points to the instruction that has been executed in the previous step.

After the execution of the previous instruction, we can see that the variables involved in the instruction have changed as follows:

SP = undefined

PC = 0x3006

A = 0X34

B = 0X56

In the above variables, we can see that the value of SP is undefined, and the value of PC pointer is 0x3006, that is, the blue arrow points to the next instruction, which also confirms that the function of PC pointer is to point to the address of the instruction to be executed. A and B are general registers of CPU, which store the operands to be sent to the CPU logic unit.

The second step of instruction execution

After executing the second instruction, the CPU's memory space has changed. A red arrow appears at the bottom, pointing to the next address from 1FFFF to 2000. Looking at the instructions being run, we find that the instruction pointed to by the blue arrow at this time means assigning a value of 2000 to the stack pointer. Therefore, the red arrow points to the value of the stack pointer register, which means that the memory space above the red arrow is the memory space that can be used by the stack. Therefore, this instruction means: the stack initialization is completed, and the memory space that can be used from address 2000 upwards is specified and used as a stack. From this statement on, the program has a stack available.

The variables involved in the above instructions have changed as follows:

SP = 0x2000

PC = 0x3008

A = 0x34

B = 0x56

As analyzed above, the stack pointer SP = 0x2000, the PC pointer points to the address of the next instruction to be executed in the instruction set, which is 3008, and the values ​​of the A and B registers remain unchanged.

The third step of instruction execution

After the third instruction is executed, the value of register A is pushed into the stack. After the instruction is executed, some changes occur in the CPU's memory space, as follows:

After executing the instruction, the relevant variables change as follows:

SP = 0x1FFF

PC = 0x3009

A = 0x34

B = 0x56

That is to say, the stack space has been used, and now the available stack space is the space above 0x1FFF, and the PC pointer points to the next instruction to be executed.

The third step of the instruction

The purpose of this instruction is to push the value of register B onto the stack. After pushing the value onto the stack, the CPU memory space becomes:

The variables involved become:

SP = 0x1FFFE

PC = 0x300A

A = 0x34

B = 0x56

The fourth step of instruction execution

The function of this instruction is to jump to the sub-function for execution. After executing this instruction, many changes occur, and the related variables involved have the following changes:

SP = 0x1FFC

PC = 0x4050

A = 0x34

B = 0x56

The SP stack pointer changes to 0x1FFC, and the PC pointer points to 0x4050. From the value of the PC pointer, we can clearly see that the next instruction will jump to the sub-function to execute the sub-function. 4050 is the first executable instruction corresponding to the sub-function. Accordingly, after the sub-function is executed, that is, a function call occurs, the function return address needs to be stored so that it can return from the sub-function correctly.

Therefore, the following changes occur in the CPU memory space: