Re: [patch] libiberty/fibheap: bug when deleting nodes

[Daniel Berlin <dberlin at dberlin dot org>]

I'm okay with it, and i wrote fibheap originally, but i don't think i
can approve.


On Wed, May 27, 2009 at 3:05 PM, Michael Matz <matz@suse.de> wrote:
> Hi,
>
> this is a mean one. ?For implementing node deletion in fibonacci heaps we
> reuse extract_min, which makes sense. ?For this we have to be able to
> force the to-be-deleted node to be the new minimum.
> fibheap_replace_key_data goes to some length to ensure that this happens
> (including comments about this speciality), but those attempts sometimes
> fail because there's an early-out. ?So the wrong node is deleted and
> further downhill we become very confused in hard to analyse ways.
>
> It specifically happens when some other nodes have LONG_MIN as key, which
> is completely okay. ?But this value is used also as marker for enforcing
> the minimum and hence sometimes needs to be special cased. ?We could also
> solve this by artificially limiting the allowable set of priorities, but
> that would be harder for the callers, and isn't actually necessary if we
> don't do that early out in some cases.
>
> Martin: this will fix your segfault with pretty-ipa on tramp3d. ?I was
> too optimistic when saying that it probably isn't fibheap.c ?:-)
>
> I also added an assert to ensure this doesn't happen again. ?It seems the
> libiberty style of asserts is a fprintf/abort pair, so that's what I used.
>
> Regstrapping on x86_64-linux in progress. ?Okay if that works?
>
>
> Ciao,
> Michael.
> --
> ? ? ? ?* fibheap.c (fibheap_replace_key_data): Make sure we don't early
> ? ? ? ?out when forcing the minimum.
> ? ? ? ?(fibheap_delete_node): Assert that we managed to force the minimum.
>
> Index: fibheap.c
> ===================================================================
> --- fibheap.c ? (Revision 147931)
> +++ fibheap.c ? (Arbeitskopie)
> @@ -214,7 +214,10 @@ fibheap_replace_key_data (fibheap_t heap
> ? node->key = key;
> ? y = node->parent;
>
> - ?if (okey == key)
> + ?/* Short-circuit if the key is the same, as we then don't have to
> + ? ? do anything. ?Except if we're trying to force the new node to
> + ? ? be the new minimum for delete. ?*/
> + ?if (okey == key && okey != FIBHEAPKEY_MIN)
> ? ? return odata;
>
> ? /* These two compares are specifically <= 0 to make sure that in the case
> @@ -256,6 +259,11 @@ fibheap_delete_node (fibheap_t heap, fib
>
> ? /* To perform delete, we just make it the min key, and extract. ?*/
> ? fibheap_replace_key (heap, node, FIBHEAPKEY_MIN);
> + ?if (node != heap->min)
> + ? ?{
> + ? ? ?fprintf (stderr, "Can't force minimum on fibheap.\n");
> + ? ? ?abort ();
> + ? ?}
> ? fibheap_extract_min (heap);
>
> ? return ret;
>