Can't find valgrind error on program which terminates and returns the right output correctly

Question

Even though the program terminates correctly and gives me the right output, and there are no memory leaks, valgrind gives me some errors of this kind:

Invalid read of size 1
==910==    at 0x108DD4: fnv_hash_function (user.c:24)
==910==    by 0x108E17: hash (user.c:29)
==910==    by 0x109A50: icl_hash_find (icl_hash.c:114)
==910==    by 0x1094DB: db_request (user.c:197)
==910==    by 0x108D2E: main (tuser.c:65)
==910==  Address 0x5416f50 is 0 bytes inside a block of size 15 free'd
==910==    at 0x4C2E10B: free (vg_replace_malloc.c:530)
==910==    by 0x109152: freeKey (user.c:138)
==910==    by 0x109CF2: icl_hash_delete (icl_hash.c:192)
==910==    by 0x109796: db_request (user.c:222)
==910==    by 0x108CF8: main (tuser.c:59)
==910==  Block was alloc'd at
==910==    at 0x4C2CEDF: malloc (vg_replace_malloc.c:299)
==910==    by 0x108BDC: main (tuser.c:35)

The hash and fnv_hash_function are defined in this way

static inline unsigned int fnv_hash_function( void *key, int len ) {
    unsigned char *p = (unsigned char*)key;
    unsigned int h = 2166136261u;
    int i;
    for ( i = 0; i < len; i++ )
        h = ( h * 16777619 ) ^ p[i]; //this is the line 24
    return h;
}


unsigned int hash(void *key){
    return fnv_hash_function(key, strlen(key));
}

I guess the problem is the ^ operator, but I can't figure out what the problem is, since the program terminates with the right output and without segmentation faults.

The icl_hash_find is not a function written by me, but is inside a library I'm using and is defined in this way

void *
icl_hash_find(icl_hash_t *ht, void* key)
{
    icl_entry_t* curr;
    unsigned int hash_val;

    if(!ht || !key) return NULL;

    hash_val = (* ht->hash_function)(key) % ht->nbuckets;

    for (curr=ht->buckets[hash_val]; curr != NULL; curr=curr->next)
        if ( ht->hash_key_compare(curr->key, key))
            return(curr->data);

    return NULL;
}

I tried valgrind on the test suite of that library and no errors were found so I doubt the problem is there.

EDIT: The key is allocated in this for loop:

char * s; //string used as key
for(int i = 0; i < N; i++){

    s = (char *)malloc(NAMELEN * sizeof(char));
    sprintf(s, "Utente %d", i);
    u = create_user( s , i);

    if(!db_request(db, s, u, PUT)){
        perror("problema PUT");
        exit(EXIT_FAILURE);
    }
    .
    .
    .

EDIT 2: Here's the body of db_request:

bool db_request(userbase_t *db, char * key, user_t * u, dbop_t op ){

if(db==NULL || key == NULL ||(op!=DELETE && u==NULL)){
    errno = EINVAL;
    return false;
}
int lock_index; //indice del lock del bucket
switch(op){
    //implementazione PUT
    case PUT : 
        lock_index = db -> table -> hash_function(key) % db->nlocks;
        WLOCK(&db->locks[lock_index])
        errno = 0;
        if(icl_hash_insert(db->table, key, (void *) u)==NULL){
            RWUNLOCK(&db->locks[lock_index])
            //la chiave e' gia' associata ad un utente
            if(errno == EINVAL){
                perror("key gia' presente");
            }
            return false;
        }
        RWUNLOCK(&db->locks[lock_index])
        return true;
    //implementazione GET
    case GET :
        lock_index = db -> table -> hash_function(key) % db->nlocks;
        RLOCK(&db->locks[lock_index])

        u = icl_hash_find(db->table, (void *)key );

        RWUNLOCK(&db->locks[lock_index]);
        return true;
    //implementazione update
    case UPDATE :
        //elimina il vecchio e aggiunge il nuovo
        lock_index = db -> table -> hash_function(key) % db->nlocks;
        WLOCK(&db->locks[lock_index]);

        if(icl_hash_delete(db->table, key, freeKey, freeUser)){
            perror("problema UPDATE (icl_hash_delete) ");
            RWUNLOCK(&db->locks[lock_index]);
            return false;
        }

        if (icl_hash_insert(db->table, key, (void *) u)==NULL){
            perror("problema UPDATE (icl_hash_insert)");
            RWUNLOCK(&db->locks[lock_index]);
            return false;
        }
    case DELETE :
        lock_index = db -> table -> hash_function(key) % db->nlocks;
        WLOCK(&db->locks[lock_index]);          

        if(icl_hash_delete(db->table, key, freeKey, freeUser)){
            perror("problema DELETE");
            RWUNLOCK(&db->locks[lock_index]);
            return false;
        }

        RWUNLOCK(&db->locks[lock_index]);
        return true;
    //mai raggiunto
    default :
        errno = EINVAL;
        perror("problema switch op");
        return false;

}}

But I can't find the problem, I'm starting to think the problem is in the icl_hash lib.

The problem happens when I'm calling the GET on an element I've just DELETED in the test function.

if(!db_request(db, s , u ,DELETE)){
            perror("problema DELETE");
            exit(EXIT_FAILURE);
        };

//provo a ottenerlo di nuovo
//The error happens here
if(!db_request(db, s , u ,GET)){
    perror("GET");
    exit(EXIT_FAILURE);
};

The only thing the get does is call this function:

void *
icl_hash_find(icl_hash_t *ht, void* key)
{
icl_entry_t* curr;
unsigned int hash_val;

if(!ht || !key) return NULL;

hash_val = (* ht->hash_function)(key) % ht->nbuckets;

for (curr=ht->buckets[hash_val]; curr != NULL; curr=curr->next)
    if ( ht->hash_key_compare(curr->key, key))
        return(curr->data);

return NULL;
}

Answer 1

Your invalid access is to memory that is already freed:

Invalid read of size 1
==910==    at 0x108DD4: fnv_hash_function (user.c:24)
==910==    by 0x108E17: hash (user.c:29)
==910==    by 0x109A50: icl_hash_find (icl_hash.c:114)
==910==    by 0x1094DB: db_request (user.c:197)
==910==    by 0x108D2E: main (tuser.c:65)
==910==  Address 0x5416f50 is 0 bytes inside a block of size 15 free'd
==910==    at 0x4C2E10B: free (vg_replace_malloc.c:530)
==910==    by 0x109152: freeKey (user.c:138)
==910==    by 0x109CF2: icl_hash_delete (icl_hash.c:192)
==910==    by 0x109796: db_request (user.c:222)
==910==    by 0x108CF8: main (tuser.c:59)
==910==  Block was alloc'd at
==910==    at 0x4C2CEDF: malloc (vg_replace_malloc.c:299)
==910==    by 0x108BDC: main (tuser.c:35)

The block was freed in a call to icl_hash_delete() made at line 222 in the function db_request() in the file user.c. The invalid access was made in a call to icl_hash_find() at line 197 in db_request() in user.c. You say that the icl_hash* code is provided to you.

Without the body of the function db_request() is is difficult to be sure what's going on, but there are at least a couple of possibilities.

1. You've got a dangling pointer to the entry that was deleted, and you should not still be using that.
2. The code in the icl_hash* functions is mishandling data after a hash record is deleted.

If the provider of the icl_hash.c function is reasonably reliable, it is sensible to assume that the problem is in your code in db_request(). Look hard at lines 197 and 222 in particular, and the variables (pointers) passed to the icl_hash_find() and icl_hash_delete() functions. Look again at the manual page for those functions to see what the rules are.

If you're not sure about the quality of the code in icl_hash.c, you should create yourself a smaller MCVE that creates a hash table, adds some rows, finds some rows, deletes some entries, and does some more finding. This will help you identify whether there's a problem in your code or in the icl_hash.c code.

Since the memory was allocated in main() rather than db_request(), you might have to review what you're doing at that level, but my guess is that you passed that pointer to db_request() and handed ownership of it to the hash table when you added an entry, and the specification of icl_hash_delete() says it will free the memory you handed to the hash table, and you are accidentally still holding a pointer to the now freed memory (the argument to the db_request() function). You have to be very careful to ensure you know who owns what memory — and when that memory has been released.

Answer 2

Valgrind tells you that you have a problem in fnv_hash_function function. In this function you access memory after it has been freed (deallocated) in freeKey. It even tells you that you access it exactly at the beginning of that block of memory. You allocated that memory in main (tuser.c:35). Your program works by accident. It will continue to work as long as the block of memory in question will not end up at the beginning of a memory page and it will be the last block freed on that page - then the page will be (probably - depending on the allocator strategy) unmapped from your process space. After that unmapping if you access it (like in fnv_hash_function) your program will crash exactly at the moment you try access it.

When that block could end up as the first block on the page and be the last one to be freed ? - difficult to say it may happen after any changes that you make to your source code or underlying libraries (including system libraries that you don't control).