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;
}
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.
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.