[PATCH] dkhash: memory leak and possible loss of objects in dkhash_remove

[Max Sikström]

The change applied is not enough. It might pass through the test though, because the fill-bucket and remove-from-bucket doesn't use key2.

If key1 differs in dkhash_remove, the continue-statment is triggered, which skips the prev=bkt-statement.

I haven't synced the code with svn yet, but just updating with the changes applied in commit 2612, the test actually failes. (same as before)

The only time this patch helps is if you add all values with equal k1, but k2 differs, then the second if statement in the loop exits and prev=bkt runs.

-- 
Max Sikström
developer - op5 AB

max.sikstrom at op5.com
http://www.op5.com/

On Feb 20, 2013, at 7:03 PM, Andreas Ericsson <ae at op5.se> wrote:

> Nice catch. I'll remove the unrelated changes and apply.
> 
> Thanks.
> 
> On 02/20/2013 05:48 PM, max.sikstrom at op5.com wrote:
>> From: Max Sikström <msikstrom at op5.com>
>> 
>> Pointer to previous in dkhash_remove was only set for first element in a given
>> bucket. So when finding for example third object for removal, setting
>> prev->next=obj->next looses the reference to the old prev->next, which is the
>> second object in the list.
>> 
>> This can be tested by creating a hash map of one bucket (practically a linked
>> list), and fill and remove all, both forward and backward.
>> 
>> Signed-off-by: Max Sikström <msikstrom at op5.com>
>> ---
>>  lib/dkhash.c      |    5 ++---
>>  lib/test-dkhash.c |   36 +++++++++++++++++++++++++++++++++++-
>>  2 files changed, 37 insertions(+), 4 deletions(-)
>> 
>> diff --git a/lib/dkhash.c b/lib/dkhash.c
>> index cab3d66..74a9a76 100644
>> --- a/lib/dkhash.c
>> +++ b/lib/dkhash.c
>> @@ -209,9 +209,7 @@ void *dkhash_remove(dkhash_table *t, const char *k1, const char *k2)
>> 
>>  	prev = bkt; /* pay attention */
>>  	for (; bkt; bkt = bkt->next) {
>> -		if (strcmp(k1, bkt->key))
>> -			continue;
>> -		if ((!k2 && !bkt->key2) || !strcmp(k2, bkt->key2)) {
>> +		if (!strcmp(k1, bkt->key) && ((!k2 && !bkt->key2) || !strcmp(k2, bkt->key2)) ) {
>>  			if (prev == bkt) {
>>  				/* first entry deleted */
>>  				t->buckets[slot] = bkt->next;
>> @@ -223,6 +221,7 @@ void *dkhash_remove(dkhash_table *t, const char *k1, const char *k2)
>>  			t->removed++;
>>  			return dkhash_destroy_bucket(bkt);
>>  		}
>> +		prev = bkt;
>>  	}
>> 
>>  	return NULL;
>> diff --git a/lib/test-dkhash.c b/lib/test-dkhash.c
>> index 02accba..313b361 100644
>> --- a/lib/test-dkhash.c
>> +++ b/lib/test-dkhash.c
>> @@ -87,10 +87,13 @@ static int del_matching(void *data)
>>  int main(int argc, char **argv)
>>  {
>>  	dkhash_table *tx, *t;
>> -	unsigned int x;
>> +	int x;
>>  	struct test_data s;
>>  	char *p1, *p2;
>> 
>> +	char *strs[10];
>> +	char tmp[32];
>> +
>>  	t_set_colors(0);
>>  	t_start("dkhash basic test");
>>  	t = dkhash_create(512);
>> @@ -143,6 +146,37 @@ int main(int argc, char **argv)
>>  	test(0 == dkhash_num_entries(tx), "x table post all ops");
>>  	test(0 == dkhash_check_table(tx), "x table consistency post all ops");
>>  	dkhash_debug_table(tx, 0);
>> +	t_end();
>> +
>> +	for(x=0;x<10;x++) {
>> +		sprintf(tmp, "string %d", x);
>> +		strs[x] = strdup(tmp);
>> +	}
>> +
>> +	t_start("dkhash single bucket add remove forward");
>> +
>> +	t = dkhash_create(1);
>> +	for(x=0;x<10;x++) {
>> +		dkhash_insert( t, strs[x], NULL, strs[x] );
>> +	}
>> +	for(x=0;x<10;x++) {
>> +		p1 = strs[x];
>> +		p2 = dkhash_remove( t, p1, NULL );
>> +		test( p1 == p2, "remove should return a value" );
>> +	}
>> +	t_end();
>> +
>> +	t_start("dkhash single bucket add remove backward");
>> +
>> +	t = dkhash_create(1);
>> +	for(x=0;x<10;x++) {
>> +		dkhash_insert( t, strs[x], NULL, strs[x] );
>> +	}
>> +	for(x=9;x>=0;x--) {
>> +		p1 = strs[x];
>> +		p2 = dkhash_remove( t, p1, NULL );
>> +		test( p1 == p2, "remove should return a value" );
>> +	}
>> 
>>  	return t_end();
>>  }
>> 
> 
> 
> -- 
> Andreas Ericsson                   andreas.ericsson at op5.se
> OP5 AB                             www.op5.se
> Tel: +46 8-230225                  Fax: +46 8-230231
> 
> Considering the successes of the wars on alcohol, poverty, drugs and
> terror, I think we should give some serious thought to declaring war
> on peace.


------------------------------------------------------------------------------
Everyone hates slow websites. So do we.
Make your web apps faster with AppDynamics
Download AppDynamics Lite for free today:
http://p.sf.net/sfu/appdyn_d2d_feb