Profiling Tools : Valgrind & co

VALGRIND
============
We will use valgrind with following tools :-

> memcheck  [default]
> callgrind
> cachegrind
> massif
> helgrind

valgrind --tool=memcheck [prog-name] [prog-argumements]
a simple example is valgrind --tool=memcheck ls -al
===================================================
nemesis@nemesis-laptop:~$ valgrind --tool=memcheck ls -al
==3497== Memcheck, a memory error detector              
==3497== Copyright (C) 2002-2009, and GNU GPL'd, by Julian Seward et al.
==3497== Using Valgrind-3.5.0-Debian and LibVEX; rerun with -h for copyright info
==3497== Command: ls -al                                                        
==3497==                                                                        
total 13300
==3497==
==3497== HEAP SUMMARY:
==3497==     in use at exit: 14,671 bytes in 95 blocks
==3497==   total heap usage: 1,902 allocs, 1,807 frees, 150,632 bytes allocated
==3497==
==3497== LEAK SUMMARY:
==3497==    definitely lost: 200 bytes in 3 blocks
==3497==    indirectly lost: 240 bytes in 20 blocks
==3497==      possibly lost: 0 bytes in 0 blocks
==3497==    still reachable: 14,231 bytes in 72 blocks
==3497==         suppressed: 0 bytes in 0 blocks
==3497== Rerun with --leak-check=full to see details of leaked memory
==3497==
==3497== For counts of detected and suppressed errors, rerun with: -v
==3497== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 33 from 10)
===================================================
[NOTE]: In the above trace "3497" which precedes every line of Valgrind output is the pid of the program being run under valgrind i.e. ls -al in this case.

PRE-REQUISITES
==============

1. Strongly recommended to run the program with -g (with debug symbols) option. It is generally true of all profiling tools.

2. Use no optimization or as a compromise -0

Bitfields

-- Used for saving space
-- NOT portable across platforms
-- bitfield declaration cannot use const and volatile qualifiers
-- Max bit field length is 64 bits. Using more than 32 bits is likely to be non portable

-- CANNOT take the address of a bitfield
-- CANNOT have a pointer to a bitfield
-- CANNOT define an array of bitfields

-- A bitfield of size 0 will force alignment to the nearest word boundary [depends actually on compiler behaviour -- some compilers may pad to the size of the base type...some to the word boundary]

-- A structure containing bitfields is suitably/appropriately padded.

Cool Compile time check

If only we could evaluate a condition at compile time instead of link or run time. Well there is a way ...
Picked up this nifty trick from the linux kernel code.

#define BUILD_BUG_ON(condition) ((void)sizeof(char[1 - 2 *!!(condition)]))

Awesome piece of code ....It's a beauty...

Concept : Array of negative size is illegal. Remember array of size 0 is possible
Therefore if a condition evaluates to true we have :-
void(sizeof(NEGATIVE ARRAY) which would trigger a compile time error

If the condition is false, we have :-

void (sizeof(char[1 - 2 * !!(0))])
==> void(sizeof(char[1-2* !1])
====>void(sizeof(char[1-0])
======>void(sizeof(char[1])
========> void(const number) ====> This has no impact on C code although it is a valid expression.
you could have 1; anywhere in the code but to be "gcc warning free" it is better to have (void) 1 .


Here is a simple example, don't worry about the logic as I just needed a condition and do NOT mean to say that size of int should be smaller than that of a char :)

#define ADY_BUILD_BUG_ON(condition) ((void)sizeof(char[1 - 2 * !!(condition)]))

int main(int argc, char *argv [])
{
   /* will not compile */
   ADY_BUILD_BUG_ON(sizeof(char) <  sizeof(int));
}

and here is what we get :--

nemesis@nemesis-laptop:~/test_code$ gcc build_bug_on_example.c
build_bug_on_example.c: In function ‘main’:
build_bug_on_example.c:9: error: size of array ‘type name’ is negative

Mod Utils

Package name : module-init-tools
sudo apt-get install module-init-tools

Use :-
lsmod
modprobe
depmod
rmmod


Modprobe : Intelligent enough to figure out the dependencies.
                   [it is just a depmod -a combined with insmod of the necessary modules]

Default location of the modules :
   /lib/modules/`uname -r`

Module dependency
 File : /lib/modules/`uname -r`/modules.dep

e.g from the modules.dep file :-
 -------------x--------------------------x---------------------------x--------------------------------

kernel/fs/freevxfs/freevxfs.ko:
kernel/fs/nfs/nfs.ko: kernel/fs/lockd/lockd.ko kernel/fs/nfs_common/nfs_acl.ko kernel/net/sunrpc/auth_gss/auth_rpcgss.ko kernel/net/sunrpc/sunrpc.ko
kernel/fs/exportfs/exportfs.ko:
kernel/fs/nfsd/nfsd.ko: kernel/fs/lockd/lockd.ko kernel/fs/nfs_common/nfs_acl.ko kernel/net/sunrpc/auth_gss/auth_rpcgss.ko kernel/net/sunrpc/sunrpc.ko kernel/fs/exportfs/exp
ortfs.ko
kernel/fs/lockd/lockd.ko: kernel/net/sunrpc/sunrpc.ko

-------------x--------------------------x---------------------------x--------------------------------

Therefore, nfs.ko requires nfs_acl.ko to be already installed. This dependency is build by depmod -a

qsort: Using array

1. The realloc operation can be expensive if the the operation is carried out for a large number of times AND/OR if the memory is already fragmented.

2. A malloc operation could be considered but it would require a flag to indicate the first instance of executing the function

if ( FLAG == TRUE)
   Memory already allocated. Don't allocate any memory
else  { /* Flag = FALSE */
   Allocate Memory
   Set Flag = TRUE
}


--------------------------------------x------------------x-------------------x-----------------------------
#define ARRAY_SIZE 10

typedef struct adi_data_t_ {
    unsigned int number;
} adi_data_t;

typedef struct adi_delete_list_t_ {
    adi_data_t ** first;
    unsigned int count;
} adi_delete_list_t;

int adi_compare_data (const void * a, const void *b)
{
   const adi_data_t ** one = (const adi_data_t **) a;
   const adi_data_t ** two = (const adi_data_t **) b;

   printf("Number one : [%d] Number two : [%d]  ret [%d]\n", (*one)->number, (*two)->number, (*one)->number - (*two)->number);
   //return (*one)->number - (*two)->number ;
    return (*two)->number - (*one)->number ;

}

int adi_delete_walker(adi_delete_list_t * delete, adi_data_t * data)
{
    static adi_data_t* array[ARRAY_SIZE];
    void *temp = NULL;

    delete->first = array;
    memcpy(&array[delete->count], &data, sizeof(adi_data_t *));
    delete->count++;


}

int main (int argc, char* argv[])
{
    adi_delete_list_t delete;
    adi_data_t data_array[ARRAY_SIZE];
    unsigned int i = 0;

    memset(&delete, 0, sizeof(adi_delete_list_t));

    /* Fill the array and pass it to the delete function */
    for (i=0; i < ARRAY_SIZE ; i++) {
        data_array[i].number = rand()/1000000;
        printf(" Data Array filled with %d \n", data_array[i].number);
        adi_delete_walker(&delete, &data_array[i]);
    }

    printf("qsort parameters: first [%p] count [%d]", delete.first, delete.count);
    /* qsort the array */
    qsort(delete.first, delete.count, sizeof(adi_data_t *), adi_compare_data);

     for (i=0; i < ARRAY_SIZE ; i++) {
        printf(" POST SORT: Data Array filled with %d \n", (*(delete.first)[i]).number);
     }
 }

qsort Example

1. This example will demonstrate how to sort a given list in ascending or descending order

2. Many a times the structures are quite big and allocating such structures could be resource intensive exercise. Therefore I allocate a list of pointers to pointers (double pointer) to the original data structure.

3. QSORT sorts only arrays or data stored in contiguous memory locations. Therefore can't be directly used to sort linked lists.

Workaround : Walk the Linked List
                       Store the pointers to these nodes in an array/allocated memory location
                       Call Qsort to sort this array based on a comparison function that you define.

###include files : stdio.h -- stdlib.h -- string .h ####

--  This function will read the contents of a linked-list/array and copy into an "array" of pointers to the data. Qsort will sort this array.

#define ARRAY_SIZE 10

typedef struct adi_data_t_ {
    unsigned int number;
} adi_data_t;

typedef struct adi_delete_list_t_ {
    adi_data_t ** first;
    unsigned int count;
} adi_delete_list_t;

/* compare function to sort in ASCENDING order */
int adi_compare_data (const void * a, const void *b)
{
   const adi_data_t ** one = (const adi_data_t **) a;
   const adi_data_t ** two = (const adi_data_t **) b;

   printf("Number one : [%d] Number two : [%d]  ret [%d]\n", (*one)->number, (*two)->number, (*one)->number - (*two)->number);
   return (*one)->number - (*two)->number ;

}

/* compare function to sort in DESCENDING order */

int adi_compare_data (const void * a, const void *b)

{

   const adi_data_t ** one = (const adi_data_t **) a;

   const adi_data_t ** two = (const adi_data_t **) b;

   printf("Number one : [%d] Number two : [%d]  ret [%d]\n", (*one)->number, (*two)->number, (*one)->number - (*two)->number);

   return (*two)->number - (*one)->number ;

}

int adi_delete_walker(adi_delete_list_t * delete, adi_data_t * data)
{
    static adi_data_t ** list = NULL;
    void *temp = NULL;

    /* allocate memory for the list */
    temp = realloc(list, (delete->count + 1) * sizeof (adi_data_t *));
    if(temp == NULL) {
        printf("###!Ady: Hell Freezes over: Realloc failed \n");
    } else {
        list = (adi_data_t **) temp;
        delete->first = list;
        memcpy(&list[delete->count], &data, sizeof(adi_data_t *));
        printf(" First [%p] List [%p] Current element:[%p] \n", delete->first, list, &list[delete->count]);
        delete->count++;
    }
}

int main (int argc, char* argv[])

{

    adi_delete_list_t delete;

    adi_data_t data_array[10];

    unsigned int i = 0;

    memset(&delete, 0, sizeof(adi_delete_list_t));

    /* Fill the array and pass it to the delete function */

    for (i=0; i < 10 ; i++) {

        data_array[i].number = rand()/1000000;

        printf(" Data Array filled with %d \n", data_array[i].number);

        adi_delete_walker(&delete, &data_array[i]);

    }

    printf("qsort parameters: first [%p] count [%d]", delete.first, delete.count);

    /* qsort the array */

    qsort(delete.first, delete.count, sizeof(adi_data_t *), adi_compare_data);

     for (i=0; i < 10 ; i++) {

        printf(" POST SORT: Data Array filled with %d \n", (*(delete.first)[i]).number);

     }

    free(delete.first);

}