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

[Andreas Ericsson]

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