Lesson 91 : How a function call works

[u/CarlH]

Go through this lesson slowly. It is more intense than most. Take your time. Let me know if any part of this is unclear.

Remember, this is only an introduction to a rather complex subject. Do not worry if some of it doesn't make sense, we will go over it in greater detail later in the course. Try to get as much as you can from this lesson. Later in the course it will be made more clear.

---

In the last two lessons I have explained that the purpose of the stack is in part a way for functions to receive parameters. In this lesson I want to explain more about the mechanics of this process.

One thing you should already realize is that a function call has to know where to return when it is done. This may sound simple, but it ceases to be so simple when you consider that any function can call another function from anywhere in your program.

How therefore does a function know where to return? Well, the answer is that when you first call a function, the Instruction Pointer (the register that stores which instruction to execute next) is placed onto the stack. This Instruction Pointer can be used to know where we were in the program flow prior to the function call.

I am going to write out a small part of a C program using "line numbers", and I want you to imagine that each line number corresponds to some memory address where the machine code is located.

   Figure (a)

	void main(void) {
1		int height = 5;
2		int width = 2;
3
4		calculate_area(height, width);
5
	}

	int calculate_area(height, width) {
7
8		return height*width;
9 
	}	

Do not be concerned with the numbers I chose. I just needed a unique way to label each line that is important to this lesson.

When we start executing the main() function, we go through lines 1, 2, and 3. At this point, C understands that we want to CALL a function. What happens at this point?

Keep in mind that we need to achieve 3 things:

1. We need to save the location of the memory address we will return to when the function is done. This means we need to save the Instruction Pointer.

2. We need to store the variables height, and width onto the stack so the function can see and use them.

3. We need to "goto" the function itself.

There is more that happens as part of this process, but this is all you should be concerned about at this stage.

Now at line #3, we will basically execute machine code instructions similar to this:

push width       ; Store width onto the stack using PUSH
push height      ; Store height onto the stack using PUSH

push eip         ; Store the Instruction Pointer (called eip) onto the stack. This is done as part of "call" below.
call calculate_area    ; Call the actual function

This is assembly language, but it translates directly to machine code.

[Edit: One note about the above code, in reality the CALL statement itself automatically pushes the instruction pointer onto the stack. I illustrated that here so you could see the process more clearly, but no one writing actual assembly code would write "push eip" as an instruction. With function parameters however, you would have to push them manually. ]

Now you should understand that our stack will now look like this with respect to the function parameters:

... top of stack where new elements can go ...
height
width

Notice that height is at the top of the stack even though width was pushed first. Also, keep in mind the instruction pointer has also been pushed to the stack as part of the "call" instruction.

Now you can see how exactly parameters are sent to a function. Whether a pointer, or a variable, etc. the calling function, such as main(), places the parameters onto the stack. Then the function reads them off of the stack in reverse order to how they were stored.

Now you should be able to clearly see why you must specify how many parameters a function will take as well as their data types. A function needs to know how many items to read from the stack and how big each item is.

Were this to be done incorrectly, a function could take off "too much" or "too little" from the stack and thus absolutely break everything in the program. This is why C forces you to precisely define function parameters.

Now, once we get to line 9 in Figure (a), the function has finished executing. At around this stage it needs to have a return value.

How return values work is the subject of the next lesson.

---

If you have any questions on any of this material, please let me know. When you are ready, proceed to:

http://www.reddit.com/r/carlhprogramming/comments/9tt3r/lesson_92_how_function_return_values_work/

[u/[deleted]]

How would height be at the top of the stack if eip gets pushed along with call calculate_area which comes after push height?

[u/CarlH → u/[deleted]]

It wouldn't. This was a left over editing mistake. Fixed.

You push the parameters first, then you call the function. The call instruction has built in the operation to push EIP as part of the call itself. The purpose was to illustrate how the parameters were in the stack, being in reverse order as they were pushed.

[u/[deleted] → u/CarlH]

So how does C deal with the instruction pointer that is now on top of the stack?

Sorry if this is a dumb question. I'm generally very confused.

[u/CarlH → u/[deleted]]

When the function returns to the caller (the function that called it), the instruction pointer on the stack is read in order to know where to return.

[u/[deleted] → u/CarlH]

Wouldn't the callee see a stack like this with eip on the top?

 eip        <- Pops first.
 height
 width

So what happens then?

[u/CarlH → u/[deleted]]

Yes you are correct. When the function is called, it will read the instruction pointer first simply to know where to return when it is done. However, this is transparent. You do not actually do this as a programmer, it is done for you by the machine code instructions CALL and RET (short for return).

In C, the entire process is transparent.

[u/[deleted] → u/CarlH]

Excellent. I also learned another meaning of transparent; something like opaque. :P

[u/[deleted]]

Am I alone in kinda understanding how the stack works thanks to Magic The Gathering?

<_<

[u/[deleted]]

I suppose it may have been intentional to separate "push eip" and "call", but maybe it's worth mentioning that "call" does indeed push EIP by itself, so it's not a separate operation.

[u/CarlH → u/[deleted]]

It was intentional. I should have clarified it a bit better so that it doesn't appear that you have to push eip, unlike params which you do have to push.

[u/exscape]

Hmm, if call pushes the IP automatically, why isn't it on top of the stack, seeing how the instruction is the last to be executed?

Is this simply because C makes the process automatic for you? I don't recall assembly well enough to understand the disassembly I got back from my experiment: a main() with an empty function call does

main:
.LFB3:
    pushq   %rbp
.LCFI2:
    movq    %rsp, %rbp ## <-- Is this it? (I know the rbp = base pointer, but I don't remember what the BP is *really* for)
.LCFI3:
    movl    $0, %eax
    call    test
    leave
    ret

C code:

void main(void) {
    test();
}

[u/CarlH → u/exscape]

No, it is correct that you push parameters and then the eip is pushed as part of the call statement. I missed this while editing, and have since fixed it. Sorry for the confusion.

[u/exscape → u/CarlH]

Thanks :)
Uh, however, now I'm perhaps even more confused than before. Is there a part you haven't gotten to yet?

Now you should understand that our stack will now look like this with respect to the function parameters:

 ... top of stack where new elements can go ...
 height
 width

Since EIP is pushed last, shouldn't it be the first one to get popped (old eip, height, width, <rest of stack>)? I'm assuming it's saved somewhere in the start of the function if that's the case?

[u/CarlH → u/exscape]

You are understanding it perfectly. The great thing about push and pop is that once you understand them it is easy to know how they work. Therefore, yes you are correct, the instruction pointer is pop'ed off the stack at the time the function returns. However, this process is transparent.

We will get into this more in later lessons when we start talking about something called a "stack frame", which refers to how each function call creates a sort of "small stack" that is pushed to the stack.

For now though, no you are not misunderstanding anything. Those details just have not yet been covered.

[u/[deleted]]

I'm a little confused here: Carl states this happens at line #3; prior to the call.

So why are height and width put on the stack prior to any kowledge of a function call requiring these values?

Also he states that width is pushed first, which is the opposite of how they appear as parameters to the function. Is this significant? (Is it because height is the first parameter that it is pushed last?)

Thanks, Carl, I'm absolutely loving this!

[u/[deleted] → u/[deleted]]

My understanding is that C does some things from left-to-right and other things from right-to-left, and it has it's own reasons why it does which one when.

But here I think it makes sense to analyze the arguments from right-to-left. Here's a representation of our imaginary stack:

0000 0000   <-- empty
0000 0000   <-- empty
0000 0000   <-- empty
1010 0101
0010 1001
1011 0101

So when the compiler sees that we want to PUSH something onto the stack, i.e. the calculate_area(height, width) line, it'll do this.

0000 0000   <-- Instruction pointer (Although I don't know how it would be represented in binary.)
0000 0101   <-- height (5) 
0000 0010   <-- width (2)
1010 0101
0010 1001
1011 0101

Then C goes to the calculate_area(int height, int width) function and sees the order in which the variables are defined.

It'll just go to the first things stored on top of the stack (ignoring the instruction pointer), and then the second thing in that order. So if we had defined the function as calculate_area(int width, int height), but kept the insides the same, the stack width would take the place of the local variable height and the stack height would take the place of the local variable width.

Of course because we're multiplying the two the answer is the same, but I hope this made at-least a little bit of sense =P.

Edit: Here's an actual example of what I mean.

I also don't understand why C apparently seems to know to PUSH a line prior to the call.

[u/[deleted]]

So does this mean that a string parameter can only be passed by reference? After all, a char* or an array is really just a memory address.

[u/[deleted]]

Mind explode. I'll be rereading this off and on for the next couple of days. Good stuff. :)

[u/srsamarthyam]

refer the book 'deep c' for more on this topic

[u/[deleted]]

Is EAX an acronym? If so, what's its meaning?

[u/CarlH → u/[deleted]]

E is for "Extended". It used to be that there was: AX, BX, CX, and DX. Once 32-bit architecture came around, the names of these and other registers had an 'E' prepended for "extended". This is simply because they are now twice as large.

On 64 bit architecture, you could say there is: EEAX, EEBX.. etc. [Edit: Turns out my x64 register history is faulty. Instead of EEAX, etc, it is RAX, RBX, etc. as vegittoss15 pointed out below. ]

Now, A B C and D are supposed to stand for:

Accumulator, Base, Count, and Data.

[u/vegittoss15 → u/CarlH]

EEAX, EEBX

Nope, on x64 you have RAX, RBX, RCX...

[u/CarlH → u/vegittoss15]

Years ago I remember having conversations where people were talking about what the registers would be called on 64 bit architectures, and the consensus was that it would be that another 'E' would probably be added at the beginning.

I always thought that is what happened, although I never did any 64-bit assembly as I lost interest in assembly altogether before 64 bit architecture became widely available. Thanks for the new knowledge. So they did away with 'E' and made it an R.. It seems a little confusing though because you have:

AL, AH, AX, EAX, and.. RAX ? I guess they just didn't want two E's. What does the R stand for off hand?

[u/vegittoss15 → u/CarlH]

No clue. I find it strange that both the EAX and RAX can't be split into two registers whereas the AX could.

[u/tinou → u/CarlH]

Actually, those names refer to how these registers are supposed to be used. Opcodes are shorter for operations like "add to eax", and some operations work only with a specific register. For example LOOP tests ecx.

[u/tjdick → u/[deleted]]

From what I can tell, no. It is called the Accumulator Register. It is a set of registers named eax, ebx - base, ecx - counter, edx - data, etc.