Search This Blog

Saturday, March 31, 2012

GCOV internals overview

Sometime back I worked on a small project to extract code coverage information created by gcc from a kernel. During that time I didn't find any good internal documentation about gcov. So here I discuss about internals of GCOV. Before jumping to the internals of GCOV here is an example from the man page.
$ gcov -b tmp.c
87.50% of 8 source lines executed in file tmp.c
80.00% of 5 branches executed in file tmp.c
80.00% of 5 branches taken  at  least  once  in  file tmp.c
50.00% of 2 calls executed in file tmp.c
Creating tmp.c.gcov.
Here is a sample of a resulting tmp.c.gcov file:

      main()
      {
    1        int i, total;
    1        total = 0;
   11        for (i = 0; i < 10; i++)
branch 0 taken = 91%
branch 1 taken = 100%
branch 2 taken = 100%
   10        total += i;
   1         if (total != 45)
branch 0 taken = 100%
  ######          printf ("Failure0);
call 0 never executed
branch 1 never executed
             else
    1             printf ("Success0);
call 0 returns = 100%
    1    }
Note - gcov has a cool graphical frontend in Linux - lcov.
As shown above gcov can show what all code path executed and how many time executed.
Want to try? Here is the quick example.
$ gcc -fprofile-arcs -ftest-coverage your_program.c
$ ./a.out
$ gcov your_program.c
During compilation with -ftest-coverage option gcc generates a ".gcno" file. It contains information about each branches in your code. While finishing execution, ./a.out creates .gcda file(s) which actually contains which all branches taken. Using these there files .c(source), .gcno(block info) and .gcda(block execution count) gcov command prints the code coverage information in a human readable format.
You might wonder how your ./a.out would create .gcda while exiting. It is because of "-fprofile-arcs" automatically includes libgcov . Libgcov registers itself to be invoked during program exit by using atexit(). (Yes - it wont generate .gcda files if you exit abnormally). And during program exit it just dumps all the branch information to one or more gcda file.
The coverage information is "just" dumped into files by libgcov. So who collects the the coverage information at run time? Actually the program itself collects the coverage information. In-fact only it can collect because only it knew which all code path it takes. The code coverage information is collected at runtime on the fly. It is accomplished by having a counter for each branch. For example consider the following program.
  int if_counter = 0, else_counter = 0;

  void dump_counters()
  {
      int fd;
      fd = open(strcat(filename, ".gcda"), "w");
      write(fd, if_counter, sizeof(if_counter));
      write(fd, else_counter, sizeof(else_counter));
  }

  int main()
  {
     int a = 1;

     atexit(dump_counters);

     a = a++ + (a * --a) + a--;
     if(a) {
        if_counter++;
        printf("not zero\n");
     } else {
        else_counter++;
        printf("zero\n");
     }
  }
In the above example if you replace the colored code with gcov equivalent then green colored code is implemented inside libgcov and red colored code is implanted inside your code by gcc. It is easy to understand how the increment operation can be implanted inside your code by gcc. It just inserts "inc x-counter" machine instruction before and after every branch. It should be noted that "inc" machine specific instruction might have side effect on some programs which uses asm inside C. For example in x86 the "inc" instruction affects carry flag. Some assembly code might depends on this and if gcc inserts "inc counter" instruction then it will result in error. I had hard time figuring this out when compiled with -fprofile-arcs a kernel was booting but not able to receive any network packets(it was discarding all packets because the network stack found the checksum was wrong).
  1 int main()
  2 {
  3     int a = 1;
  4
  5     if (a) {
  6         a++;
  7     } else {
  8         a--;
  9     }
 10
 11     return a;
 12 }
 13
Here is the disassembly (gcc -g3 test.c;objdump -S -d ./a.out)
int main()
{
  4004b4:       55                      push   %rbp
  4004b5:       48 89 e5                mov    %rsp,%rbp
    int a = 1;
  4004b8:       c7 45 fc 01 00 00 00    movl   $0x1,-0x4(%rbp)

    if (a) {
  4004bf:       83 7d fc 00             cmpl   $0x0,-0x4(%rbp)
  4004c3:       74 06                   je     4004cb <main+0x17>
        a++;
  4004c5:       83 45 fc 01             addl   $0x1,-0x4(%rbp)
  4004c9:       eb 04                   jmp    4004cf <main+0x1b>
    } else {
        a--;
  4004cb:       83 6d fc 01             subl   $0x1,-0x4(%rbp)
    }

    return a;
  4004cf:       8b 45 fc                mov    -0x4(%rbp),%eax
}
After compiling with profile-arcs, the disassembly looks like
int main()
{
  400c34:       55                      push   %rbp
  400c35:       48 89 e5                mov    %rsp,%rbp
  400c38:       48 83 ec 10             sub    $0x10,%rsp
    int a = 1;
  400c3c:       c7 45 fc 01 00 00 00    movl   $0x1,-0x4(%rbp)

    if (a) {
  400c43:       83 7d fc 00             cmpl   $0x0,-0x4(%rbp)
  400c47:       74 18                   je     400c61 <main+0x2d>
        a++;
  400c49:       83 45 fc 01             addl   $0x1,-0x4(%rbp)
  400c4d:       48 8b 05 3c 25 20 00    mov    0x20253c(%rip),%rax        # 603190 <dtor_idx.6460+0x8>
  400c54:       48 83 c0 01             add    $0x1,%rax
  400c58:       48 89 05 31 25 20 00    mov    %rax,0x202531(%rip)        # 603190 <dtor_idx.6460+0x8>
  400c5f:       eb 16                   jmp    400c77 <main+0x43>
    } else {
        a--;
  400c61:       83 6d fc 01             subl   $0x1,-0x4(%rbp)
  400c65:       48 8b 05 2c 25 20 00    mov    0x20252c(%rip),%rax        # 603198 <dtor_idx.6460+0x10>
  400c6c:       48 83 c0 01             add    $0x1,%rax
  400c70:       48 89 05 21 25 20 00    mov    %rax,0x202521(%rip)        # 603198 <dtor_idx.6460+0x10>
    }

    return a;
  400c77:       8b 45 fc                mov    -0x4(%rbp),%eax
}
  400c7a:       c9                      leaveq
  400c7b:       c3                      retq
From the above disassembly it might seem putting inc instruction while compiling is easy. But how/where storage for the counters(dtor_idx.6460 and dtor_idx.6460 in above example) are created. GCC uses statically allocated memory. Dynamically allocating space is one way but it would complicate the code(memory allocation operations during init) and might slow down execution of program(defer pointer). To avoid that gcc allocates storage as a loadable section.
The compiler keep tracks of all the counters in a single file. The data structure outlined in the below picture.


There is a single gcov_info structure for a C file. And multiple gcov_fn_info and gcov_ctr_info. During program exit() these structures are dumped into the .gcda file. For a project(with multiple C files) each C file will have a gcov_info structure. These gcov_info structures should be linked together so that during exit() the program can generate .gcda file for all the C files. This is done by using constructors and destructors.

Generic C constructor: gcc generates constructors for all program. C constructors are accomplished by using ".ctors" section of ELF file. This section contains array of function pointers. This array is iterated and each function is invoked by _init()->__do_global_ctors_aux() during program start. _init() is placed ".init" section so it will be called during program initialization. A function can be declared as constructor by using function attribute.

"-ftest-coverage" creates a constructor per file. This constructor calls __gcov_init() and passes the gcov_info as argument.
samuel@ubuntu:~$objdump  -t ./a.out  | grep -i _GLOBAL__
0000000000400c7c l     F .text  0000000000000010              _GLOBAL__sub_I_65535_0_main
And disassembly of _GLOBAL__sub_I_65535_0_main
 954 0000000000400c7c <_GLOBAL__sub_I_65535_0_main>:
 955   400c7c:       55                      push   %rbp
 956   400c7d:       48 89 e5                mov    %rsp,%rbp
 957   400c80:       bf 00 31 60 00          mov    $0x603100,%edi
 958   400c85:       e8 a6 12 00 00          callq  401f30 <__gcov_init>
 959   400c8a:       5d                      pop    %rbp
 960   400c8b:       c3                      retq
 961   400c8c:       90                      nop
 962   400c8d:       90                      nop
 963   400c8e:       90                      nop
 964   400c8f:       90                      nop
gcov_init() implemented in libgcov stores all the gcov_info() passed in a linked list. This linked list is used to walk through all the gcov_info during program termination.

2 comments:

karthik A said...

excellent post!!!!

Shahana Shafiuddin said...

Should be helpful for those who are working with it.