Saturday, August 28, 2010

Mechanism of function calls what does a processor do when function call is made

A question on Kernel Newbies mailing list related to function calls in timer.c
prompted me to right this here.
The original thread can be seen here
http://www.spinics.net/lists/newbies/msg40013.html



To make a function call CPU has to save registers and pass on ret
instructions when ever the function call ends
if we have a small fucntion which is used in a file and a function
call via CPU then over head of saving flag registers ,saving stack and
making the called function return to the location where the call was
made is so much that it is preferred to replace that call via the
actual function itself hence if some one has such a function which has
is of very less number of lines and has been called once or twice then
it is good to declare it inline.

The overhead that CPU has to undergo if the function is not inline is saving the current context ,flag,stack,heap ,(what ever is)the state of code in execution and then load the called function from a specific memory location.
Doing this for small subroutines is resource consuming.So it is a good practise among kernel developers do declare functions inline when it is used once or twice and saves the CPU the over head involved in saving the stack,program counter flag registers and other registers which are being related to the program in execution.

By using the word in laymans language I will say that part of code (function ) is actually written where ever the function call is made.

For example following program

example1.c
#include<stdio.h>
inline function ingen (X1,X2)
{
does some thing some thing
return c;
}

function b( )
{
step = function ingen ();
}
main()
{
b ();
}
If you were to execute above code

call to function ingen () via function b() would replace the function ingen() by the code inside function ingen().



If you would not have declared function ingen as inline function then the CPU would jumped to some memory location where function ingen() is actually residing and then executed.

In this case CPU just have to insert that code what ever function ingen() does when ever a call to function ingen() is made via function b().

Or which ever function in the code calls function ingen().

If the keyword static is added so that if the same function has been used at any other place then it should not affect the other files.Meaning the word static before a function makes its scope limited to that file only.

If you have another program example2.c and compile

cc example1.c example2.c
then functions in exampl1.c would be available to example2.c and vice versa but use of word static restricts the function in their respective files.
i.e. if example1.c has a static function then it will not be available to example2.c


What static does is to create a label for a certain global memory chunk and give that a value at compile time, plus not making it available to the linker.

Look at these examples
static int mystatic = 6;

int main(void)
{
return 0;
}
Generated ASM is as follows:
Code:

.file "static2.c"
.data
.align 4
.type mystatic, @object
.size mystatic, 4
mystatic:
.long 6
.text
.globl main
.type main, @function
main:
pushl %ebp
movl %esp, %ebp
movl $0, %eax
popl %ebp
ret
.size main, .-main
.ident "GCC: (Debian 4.4.4-8) 4.4.5 20100728 (prerelease)"
.section .note.GNU-stack,"",@progbits
Compare that with declaring the global variable as non-static:
Code:

int mynonstatic = 6;

int main(void)
{
return 0;
}

Code:

.file "nonstatic2.c"
.globl mynonstatic
.data
.align 4
.type mynonstatic, @object
.size mynonstatic, 4
mynonstatic:
.long 6
.text
.globl main
.type main, @function
main:
pushl %ebp
movl %esp, %ebp
movl $0, %eax
popl %ebp
ret
.size main, .-main
.ident "GCC: (Debian 4.4.4-8) 4.4.5 20100728 (prerelease)"
.section .note.GNU-stack,"",@progbits
The only difference is that in the non-static case, there's the .globl mynonstatic that makes that symbol available to the linker.
Now, careful observation will make you notice that both global variables are declared as labels, exactly the same way as main is. ASM doesn't really distinguish between functions and variables (the @function and @object thing is just an optimization gcc does): all there is memory addresses that you conveniently can refer to with a label. So, when you declare a function static, what will happen is exactly the same: the function is given a value (its code) and make it unavailable to the linker... exactly what was done to the variable.

Here you have the C and ASM for a static function:
Code:

.file "stat_func.c"
.text
.type something, @function
something:
pushl %ebp
movl %esp, %ebp
movl $0, %eax
popl %ebp
ret
.size something, .-something
.ident "GCC: (Debian 4.4.4-8) 4.4.5 20100728 (prerelease)"
.section .note.GNU-stack,"",@progbits
Again, the value for something is its code, it's a global value but not available to the linker because there's no .globl something.

What about local static variables? Actually, the idea of local variables is lost when compiling C to ASM. What you have is a global stack that each function is in charge to clean up when returning... therefore making its local values no longer available outside the function... but place a jmp and the value will be available. What happens with static variables is that the static again sets up a value at compile time and makes the symbol unavailable for the linker... as you'll see here:
Code:

int main(void)
{
static int mystatic = 6;

return 0;
}
Code:

.file "static.c"
.text
.globl main
.type main, @function
main:
pushl %ebp
movl %esp, %ebp
movl $0, %eax
popl %ebp
ret
.size main, .-main
.data
.align 4
.type mystatic.1248, @object
.size mystatic.1248, 4
mystatic.1248:
.long 6
.ident "GCC: (Debian 4.4.4-8) 4.4.5 20100728 (prerelease)"
.section .note.GNU-stack,"",@progbits
The only difference here is that the .data section has been placed *after* the main "rets" (a kind of return you have in ASM...)... ASM indentation is awful here, but actually main ends at the ret, not at the mystatic.1248 label. Ok, I'm not sure why the name is "mangled" but it's clear that the variable is declared as global even when we declared it as local in C. What will happen is that the C compiler will restrict the usage of that symbol to the main function, but you clearly see that it's just a way to create the illusion of locality... It's actually a global and that's why its value is persistent across the program's execution.

So, in summary, it seems that the real effective meaning (I don't care what the standard says) of static is "Make a global memory address not be available to the linker"... therefore we can explain why is it used both for functions and variables.

Of course, tutorials are doing fine to explain this the way they do... As you see, you have to step down to ASM in order to make some sense of this. Also, this is another great reason of why C is such a pain to use: in the end you still have to understand the basics of ASM... while to use bash, Perl, Python you don't need to know C (or the language the implementation is written in).



Since Linux kernel is made up of C and to make sure functions with similar names(if any) exist then they are not conflicting it is a good practice to declare a function as static.

Declaring it inline reduces the overhead that CPU would have to do in actually calling a function.


To have more digging about this you need to understand mechanism of function call as what does
processor do when a function call is made.

Clearly if you have a large code to execute the
instruction is in memory and it has to come to cache so if you have
large code and you declare that as inline it has disadvantage that
cache miss will more.

What I wanted to
say is if you have a function is used at 10 places and you declare it
inline 10 times then there would be cache miss more (because that inline part of code would not be in cache) and this will
have disadvantage.

Some good links worth mentioning are if you want to dig into

1) http://www.tenouk.com/cncplusplusbufferoverflow.html
2)http://www.tenouk.com/Bufferoverflowc/Bufferoverflow1.html
3)http://www.intel.com/products/processor/manuals/index.htm
4) http://www.tenouk.com/cnlinuxsockettutorials.html
5)http://www.drpaulcarter.com/pcasm/
6)http://asm.sourceforge.net/
7)http://www.amazon.com/Linux-Kernel-Development-Robert-Love/dp/0672327201
Linux Kernel Development by Robert Love, page 18 ,Chapter2, 2nd edition of book has discussed about it.
By the time you will read this blog third edition of book would have released.
8)  http://www.spinics.net/lists/newbies/msg40032.html

No comments: