What does a function look like when it runs in memory?

Before we start this article, let’s think about a few questions.

1. Let’s start with a simple piece of code:

void func(int a) {

    if (a > 100000000) return;



    int arr[100] = {0};

    func(a + 1);

}

Copy the code

Can you see what might be wrong with this code?

2. In our previous article, “How to implement High Performance and High Concurrency Servers”, we mentioned a key technology called coroutines. Do you know what the essence of coroutines is? Some of you might say user thread, but what is user mode thread and how is it implemented?
3. What does the function look like when it runs?

This question may seem unrelated, but there is one thing you need to understand behind it, and that is the so-called run time stack of functions.

Let’s take a closer look at what a function runtime stack is and why it’s important for programmers to understand it thoroughly.

From processes and threads to function calls

There is a lot of information when a car runs on high speed, such as speed, position and so on. Through these information, we can intuitively feel the running state of the car.

Similarly, the program also has a lot of information when it is running, such as what programs are running, where these programs are executed and so on. Through these information, we can intuitively feel the state of the program running in the system.

Among other things, we created the concept of processes and threads to keep track of what programs are running. For the concept of processes and threads, see “Hit me after reading this article”.

The execution of processes and threads is reflected in the execution of functions. The execution of functions is not only the sequential execution of internal functions, but also the transfer of control over the call of sub-functions and the return after the execution of sub-functions. The sequential execution inside the function is unremarkable; the focus is on the function invocation.

So let’s move from macro processes and threads to micro function calls and focus on how function calls are implemented.

Activity trace of a function call: stack

Those of you who have played the game know that sometimes you have to play side quests in order to complete a main quest. There may be side quests, and when one side quest is completed, you will see what it means to go back to the previous one.

It is assumed that the main task of Collecting Sutra from West Heaven (A) depends on the secondary task of collecting Sun Wukong (B) and Pig (C), that is to say, the main task of Collecting Sutra from West Heaven (A) can be continued only after completing the secondary task of collecting Sun Wukong (B) and Pig (C).

Sun Wukong B relies on the mission to get the magic Spell D, and can only return to the mission B after the mission D is completed.

The dependencies of the entire task are shown in the figure below:

Now let’s simulate the task completion process.

First we go to task A, which executes the main task:

During the execution of task A, we find that task A depends on task B, and then we suspend task A to execute task B:

When executing task B, we also find that task D is dependent:

When we perform task D, we find that the task is no longer dependent on any other task, so we can fall back to the previous task, which is B:

Task B no longer depends on task C, so that task B can return to task A after completion:

Now we are back to the main task A, dependent task B is completed, and then task C:

Like task D, C does not depend on any other task. After task C is completed, it can return to task A again. After task A is completed, the whole task is completed.

Let’s take a look at the trajectory of the mission:

If you look closely, you’ll actually see that this is a First In Last Out order that works naturally with data structures like stacks.

If you take A closer look at the track at the top of the stack, which is A, B, D, B, A, C, A, you can actually see that the track here is A task-dependent tree traversal, isn’t that amazing, and that’s why traversal of data structures like trees can be done not only recursively but also by stacks.

A box

The same goes for function calls, where you replace ABCD with ABCD, essentially the same thing.

So now we know that the stack structure can be used to hold function call information.

Like every task in the game, when a function is running, each function has its own “small box”, which holds various information about the function when it is running. These small boxes are organized by the stack structure, which is called stack frames, or call stack. Whatever you call it, it’s the little box here, and the little box is how much memory the function takes up when it runs, and these little boxes make up what we call the stack area. For a detailed explanation of the stack area, see Understanding Operating Systems: How Programmers Understand Memory.

So what information does a function call have?

Function call and return information

We know that when function A calls function B, control is transferred from A to B. The so-called control actually means that the CPU executes the machine instructions belonging to which function. The CPU switches from executing the instructions belonging to function A to executing the instructions belonging to function B, so we say that control is transferred from function A to function B.

Control is transferred from function A to function B, so we need to have two pieces of information:

• Where do I come from (back)

• Where to go (jump)

Isn’t it simple, like when you go on a trip, you need to know where to go and remember the way home?

The same is true for function calls.

When function A calls function B, we just need to know:

• Where is the machine instruction executed for function A (where did I come from, return)

• Function B the address of the first machine instruction (where to go, jump)

These two pieces of information are enough for the CPU to start executing the machine instructions corresponding to function B and jump back to function A when function B is finished executing.

So how is this information acquired and maintained?

Now we can open this little box and see how it works.

Suppose function A calls function B, as shown below:

Currently, the CPU executes the machine instruction of function A, whose address is 0x400564, and then the CPU executes the next machine instruction:

call 0x400540

Copy the code

What does this machine instruction mean?

This machine instruction corresponds to the function call that we wrote in the code. Notice that there is a machine instruction address after the call. If you look at the figure above, you will see that this address is the first machine instruction of function B. After this machine instruction, the CPU jumps to function B.

Now that we’ve solved the “where to” problem that controls the jump, how do we jump back when function B is done?

The call instruction pushes the address of the next call instruction (0x40056A) into the stack frame of function A, as shown in the figure below:

Now, function A’s little box is A little bigger because it has loaded the return address:

Now the CPU starts executing the machine instructions for function B. Notice that function B also has its own little box (stack frame) into which it can throw the necessary information.

What if another function is called from function B?

It’s the same thing as function A calling function B.

Let’s look at function B’s last machine instruction ret. This machine instruction tells the CPU to jump to function A’s return address on the stack frame, so that when function B is finished, it can jump to function A to continue.

At this point, we have solved the “where do I come from” problem in control transfer.

Parameter passing and return values

Function calls and returns allow us to write functions and make function calls. But calling a function requires passing arguments and getting the return value in addition to the name of the function. So how does this work?

In x86-64, parameters are mostly passed and returned via registers.

Suppose function A calls function B, and function A writes some parameters to the corresponding registers, from which the parameters can be fetched when the CPU executes function B.

Similarly, function B can write the return value to A register, and when function B finishes executing, function A can read the return value from the register.

We know that the number of registers is finite. What if we pass more parameters than the number of registers?

That’s when the function’s little box, the stack frame, comes into play again.

When the number of parameters exceeds the number of registers, the remaining parameters are placed directly in the stack frame, so that the called function can get the parameters from the previous function’s stack frame.

Now the stack frames can be further enriched, as shown below:

From the figure, we can see that when function B is called, some parameters are put into function A’s stack frame, and the top of function A’s stack frame is still stored with the return address.

A local variable

We know that variables defined inside a function are called local variables. Where do they go when the function runs?

Originally, these variables can also be placed in registers, but when the number of local variables exceeds the register they must be placed in the stack frame.

Therefore, our stack frame content is further enriched.

Attentive students may have this question, we know that register is Shared resources can be used by all functions, since the function of A local variable can be written to the register, so when the function is A function call B, function of the local variable B can also be written to the register, so back to function when the function B has been completed when the register values has been modified by the function B, That would be a problem.

This can be problematic, so before writing a local variable to the register, we must first save the initial value in the register and then restore the original value when the register is used up.

So where do we store the raw value in the register?

As some of you might have guessed, yes, it’s still in the stack frame of the function.

As a result, our little box looks like the one shown in the figure. When the register is used up, it can be restored according to the initial value saved in the stack frame.

Now that you know what the function looks like at runtime, that’s the answer to question 3.

Big Picture

Again, the stack frame in question is located in what is often called the stack area.

The stack area, which is part of the process’s address space, is shown in the figure below.

For a detailed explanation of the stack area, see Understanding operating Systems: How Programmers Should Understand Memory.

Finally, let’s go back to the simple code at the beginning of the article:

void func(int a) {

    if (a > 100000000) return;



    int arr[100] = {0};

    func(a + 1);

}



void main(a){

    func(0);

}

Copy the code

Think about what’s wrong with this code.

conclusion

In this chapter we explain in detail what a function runtime stack is and why we should not create too many local variables, starting with a few seemingly unrelated issues. If you’re careful, you’ll notice that we haven’t solved the second question, which we’ll talk about in the next chapter, which is coroutines.

Hopefully this article has helped you understand the function runtime stack.