May 8, 2012

What's wrong with this code - fun with assembly : the answer


In the previous post I presented the following program and asked what was the problem with it:
int fact(int n)
{
    if (n == 1)
        return 1;
    else
        n = n * fact(n - 1);
}

int main(int argc, char *argv[])
{
     int n = argc > 1 ? atoi(argv[1]) : 5;
     int i = fact(n);
   
     return printf("fact(%d): %d", n, i);
}
As I said in the previous post, the problem itself is not so hard to find out: take a close look in line 6 again! We are not missing any instruction, or are we? Actually we are missing a return  so line 6 should really look like

return n * fact(n - 1);
i.e, the developer forgot to include the return.
Note that the compiler tried to alert me with the following warning, but as you know, I just ignored it :) (as I said in the previous post, you should never ignore compiler warnings)
c:\temp\fact.c(7) : warning C4715: 'fact' : not all control paths return a value
So the interesting question is: why this program works even when it is clear that it is missing a return? In order to answer this question we are going to dive into the assembly generated code for this program. To get the assembly code just type the following in a command line (assuming you have cl.exe in your path):
cl fact.c /Fa fact.asm
Even if you have little knowledge of assembly, please, bear with me; I'll try to explain the important parts. Also I've simplified both functions (fact and main) assembly code removing not important (to this discussion) bits.

MESSAGE DB 'Fact(%d): %d', 00H
fact:
 push ebp
 mov ebp, esp
 
 cmp dword ptr [ebp+8], 1
 jne next_fact
 mov eax, 1
 jmp finish
 
next_fact:
 mov eax, [ebp+8]
 sub eax, 1
 push eax
 call fact
 add esp, 4
 imul eax, [ebp + 8]
 mov [ebp+8], eax
 
finish:
 pop ebp
 ret
 
main:
 call fact
 add esp, 4
 mov _i$[ebp], eax
 mov ecx, _i$[ebp]
 push ecx
 mov edx, _n$[ebp]
 push edx
 push OFFSET MESSAGE
 call _printf
 add esp, 12
 mov esp, ebp
 pop ebp
 ret 0

PS: If you want to generate an assembly source with more - actually lots of - information from the original C program use the following command line arguments:


cl fact.c /Fa fact.asm /FAscu
First let have some simple facts:
  • fact function code starts at line 2 and extends through line 22 (ret instruction).
  • Argument n is stored at address [ebp + 8]
  • main function starts at line 24 and extends through line 37.
  • main calls fact function on line 25 (again, please note that for brevity/simplicity reasons I removed parts of the main function, so it became easier to understand).
Now that we have a high level view of the code lets dig a little deep into the fact function code (and on main function when appropriate).

Lines 3 and 4 represents the standard C function prologue; the first interesting instruction is the one at line 6 which compares n (remember, [ebp + 8]) with 1 branching to label next_fact (line 11) if they are not equal.


Starting at line 12 the code loads n into register eax subtracts one from it and calls itself recursively. When fact returns from a previous recursive call (line 16) the code calculates n times eax i.e, the compiler used eax register to return the calculated factorial from fact. We can confirm this behavior inspecting line 27 (inside main function) which assigns eax to local variable i after calling fact.

But just using eax register to pass the return value from fact is not enough; this program works (accidentally) only because the compiler used the same register eax to perform the calculations and to pass the return value.

So we can conclude that in this particular program, omitting the return statement renders an executable equivalent to the one that would be generated had the return statement be present.

Note that different compilers (or even different versions of the same compiler) may choose other registers to perform the calculations / pass return values from functions; actually I have found at least one version of CL (from Visual Studio 6) that used register ecx to perform the multiplication and eax to pass the return values (rendering an incorrect program).

Note also that even the same version of a compiler may generate different versions of the code (one that uses eax for both, calculations and for the return values and another that uses a different set of registers) depending on options such optimization, debug, etc.


Best

No comments: