Loop-detection in assoc_find..

[Miguel DeAvila]

On Friday 18 April 2008 13:25:38 Trond Norbye wrote:

> We have had some discussions lately about a loop in assoc_find, and  
> since we currently haven't been able to reproduce this problem in our  
> test environment I think that we should add loop detection into the  
> assoc_find routine.
> 
> The following is a patch (for the binary branch) that implements this.

I don't think the patch is sufficient. The loop that I encountered involved three
items (A -> B -> C -> A) ... the patch only detects loops between adjacent items. 

Also, the 'expanding' variable was false (at least in the core file that I have). 

Lastly ... not sure if this is  related, but we also seem to have a out-of-memory/refcount-leak
(see this thread http://www.mail-archive.com/memcached@lists.danga.com/msg02871.html )

We definitely have servers though that suffer from the out-of-memory errors that don't hang
in assoc_find, so I'm not sure if they are related.

Let me know if there is anything I can do to help.

regards,

Miguel


> Trond
> 
> Index: assoc.c
> ===================================================================
> --- assoc.c     (revision 778)
> +++ assoc.c     (working copy)
> @@ -489,7 +489,10 @@
>       uint32_t hv = hash(key, nkey, 0);
>       item *it;
>       unsigned int oldbucket;
> -
> +#ifndef NDEBUG
> +    item *lookahead;
> +#endif
> +
>       if (expanding &&
>           (oldbucket = (hv & hashmask(hashpower - 1))) >= expand_bucket)
>       {
> @@ -498,7 +501,22 @@
>           it = primary_hashtable[hv & hashmask(hashpower)];
>       }
> 
> +#ifndef NDEBUG
> +    lookahead = it;
> +#endif
> +
>       while (it) {
> +#ifndef NDEBUG
> +        if (lookahead && lookahead->h_next) {
> +            lookahead = lookahead->h_next->h_next;
> +            if (lookahead == it) {
> +                fprintf(stderr,
> +                        "ERROR: Loop detected inside the assoc table! 
> %s\n",
> +                        expanding ? " during expansion of the  
> hashtable" : "");
> +                assert(false);
> +            }
> +        }
> +#endif
>           if ((nkey == it->nkey) &&
>               (memcmp(key, ITEM_key(it), nkey) == 0)) {
>               return it;
> 
>