diff mbox

bitmap fix for current

Message ID 151D0846-0B4C-4447-8A31-DBC51C82F1FD@comcast.net
State New
Headers show

Commit Message

Mike Stump Nov. 20, 2014, 12:18 a.m. UTC 
On Nov 14, 2014, at 2:26 AM, Richard Biener <richard.guenther@gmail.com> wrote:
> On Fri, Nov 14, 2014 at 2:10 AM, Jeff Law <law@redhat.com> wrote:
>> On 11/13/14 12:37, Mike Stump wrote:
>>> 
>>> I was doing a merge, and it failed to even compile the runtime
>>> libraries due to checking in bitmap.  bitmap goes to remove set bits
>>> from the bitmap (the second hunk in a two hunk set), and it fails to
>>> update the current pointer.  That memory is freed and then
>>> reallocated and a new index is put into it, and then we fail a
>>> consistency check later on due to the mismatch between head->index
>>> and head->current->indx, because current was not properly maintained.
>>> This patch removes the old value of current when we remove what it
>>> points to from the bitmap.
>> 
>> Was the calling code iterating through the bit with a form like
>> 
>> EXECUTE_IF_SET_IN_BITMAP (something, 0, i, bi)
>> {
>>   bitmap_clear_bit (something, i)
>>   [ ... whatever code we want to process i, ... ]
>> }
>> 
>> If so, that's the real issue and we'd really like to identify & fix any code
>> that has that kind of structure.

Nope, that doesn’t appear to be the problem.

> Indeed.  I can't see how this can have triggered:
> 
>  prev = elt->prev;
>  if (prev)
>    {
>      prev->next = NULL;
>      if (head->current->indx > prev->indx)
>        {
>          head->current = prev;
>          head->indx = prev->indx;
> 
> so if there was elt->prev then if current == elt current->indx should
> better be > prev->indx.
> 
> Sth else must be wrong (and I doubt it's the above bogus use of
> bitmaps).

So bitmap_ior_and_compl has an overly cleaver optimization to overwrite an existing bitmap with the newly computed bitmap.  We write it over in place and then at the end, we do:

  if (dst_elt)
    {
      changed = true;
      bitmap_elt_clear_from (dst, dst_elt);
    }

which is all fine and good, however, notice that when we update a list with:

  0 1

with:

1 2

we get:

1 1 2

and then we want to kill from the second 1 to the end.

The problem is current points at the second 1, and because the update code for current does:

      if (head->current->indx > prev->indx)
        {
          head->current = prev;
          head->indx = prev->indx;
        }

and index is not greater (it is indeed unrelated to the other index), we don’t update current.  So, even my patch was wrong, in that the two are unrelated, so no comparison will help here.

Curious the and and xor routine do this:

  /* Ensure that dst->current is valid.  */
  dst->current = dst->first;
  bitmap_elt_clear_from (dst, dst_elt);

so, certainly the previous authors know of this type of problem.

and_into almost seems wrong:

  if (a_elt)
    {
      changed = true;
      bitmap_elt_clear_from (a, a_elt);
    }

as and can remove elements, but, they are saved by the code in bitmap_elt_clear_from:

      if (head->current->indx > prev->indx)
        {
          head->current = prev;
          head->indx = prev->indx;
        }

which kicks in since and cannot add any elements, it is purely subtractive.

and_compl works as it does:

  /* Ensure that dst->current is valid.  */
  dst->current = dst->first;

ior doesn’t reset current, and it broken.

ior_and_compl doesn’t reset current and likewise, is broken.

If these were _into varieties, they would have been ok.  But, they are not.

I added checking code to ensure the current was in the bitmap at the end of bitmap_elt_clear_from, and sure enough, it fired.

So, next up, is there anything else that is supposed to save us in this case?  If not, Ok?
* bitmap.c (bitmap_ior): Zap current as it could be deleted.
	(bitmap_ior_and_compl): Likewise.

Comments

Richard Biener Nov. 20, 2014, 1:15 p.m. UTC | #1 
On Thu, Nov 20, 2014 at 1:18 AM, Mike Stump <mikestump@comcast.net> wrote:
> On Nov 14, 2014, at 2:26 AM, Richard Biener <richard.guenther@gmail.com> wrote:
>> On Fri, Nov 14, 2014 at 2:10 AM, Jeff Law <law@redhat.com> wrote:
>>> On 11/13/14 12:37, Mike Stump wrote:
>>>>
>>>> I was doing a merge, and it failed to even compile the runtime
>>>> libraries due to checking in bitmap.  bitmap goes to remove set bits
>>>> from the bitmap (the second hunk in a two hunk set), and it fails to
>>>> update the current pointer.  That memory is freed and then
>>>> reallocated and a new index is put into it, and then we fail a
>>>> consistency check later on due to the mismatch between head->index
>>>> and head->current->indx, because current was not properly maintained.
>>>> This patch removes the old value of current when we remove what it
>>>> points to from the bitmap.
>>>
>>> Was the calling code iterating through the bit with a form like
>>>
>>> EXECUTE_IF_SET_IN_BITMAP (something, 0, i, bi)
>>> {
>>>   bitmap_clear_bit (something, i)
>>>   [ ... whatever code we want to process i, ... ]
>>> }
>>>
>>> If so, that's the real issue and we'd really like to identify & fix any code
>>> that has that kind of structure.
>
> Nope, that doesn’t appear to be the problem.
>
>> Indeed.  I can't see how this can have triggered:
>>
>>  prev = elt->prev;
>>  if (prev)
>>    {
>>      prev->next = NULL;
>>      if (head->current->indx > prev->indx)
>>        {
>>          head->current = prev;
>>          head->indx = prev->indx;
>>
>> so if there was elt->prev then if current == elt current->indx should
>> better be > prev->indx.
>>
>> Sth else must be wrong (and I doubt it's the above bogus use of
>> bitmaps).
>
> So bitmap_ior_and_compl has an overly cleaver optimization to overwrite an existing bitmap with the newly computed bitmap.  We write it over in place and then at the end, we do:
>
>   if (dst_elt)
>     {
>       changed = true;
>       bitmap_elt_clear_from (dst, dst_elt);
>     }
>
> which is all fine and good, however, notice that when we update a list with:
>
>   0 1
>
> with:
>
> 1 2
>
> we get:
>
> 1 1 2
>
> and then we want to kill from the second 1 to the end.
>
> The problem is current points at the second 1, and because the update code for current does:
>
>       if (head->current->indx > prev->indx)
>         {
>           head->current = prev;
>           head->indx = prev->indx;
>         }
>
> and index is not greater (it is indeed unrelated to the other index), we don’t update current.  So, even my patch was wrong, in that the two are unrelated, so no comparison will help here.
>
> Curious the and and xor routine do this:
>
>   /* Ensure that dst->current is valid.  */
>   dst->current = dst->first;
>   bitmap_elt_clear_from (dst, dst_elt);
>
> so, certainly the previous authors know of this type of problem.
>
> and_into almost seems wrong:
>
>   if (a_elt)
>     {
>       changed = true;
>       bitmap_elt_clear_from (a, a_elt);
>     }
>
> as and can remove elements, but, they are saved by the code in bitmap_elt_clear_from:
>
>       if (head->current->indx > prev->indx)
>         {
>           head->current = prev;
>           head->indx = prev->indx;
>         }
>
> which kicks in since and cannot add any elements, it is purely subtractive.
>
> and_compl works as it does:
>
>   /* Ensure that dst->current is valid.  */
>   dst->current = dst->first;
>
> ior doesn’t reset current, and it broken.
>
> ior_and_compl doesn’t reset current and likewise, is broken.
>
> If these were _into varieties, they would have been ok.  But, they are not.
>
> I added checking code to ensure the current was in the bitmap at the end of bitmap_elt_clear_from, and sure enough, it fired.
>
> So, next up, is there anything else that is supposed to save us in this case?  If not, Ok?

The bitmap_ior and bitmap_ior_and_compl hunks are ok.  Please leave
out the checking bits - they will be very much too expensive.

Thanks,
Richard.

>
>
>
>
>
diff mbox

Patch

diff --git a/gcc/bitmap.c b/gcc/bitmap.c
index 2550175..6400229 100644
--- a/gcc/bitmap.c
+++ b/gcc/bitmap.c
@@ -303,6 +302,20 @@  bitmap_elt_clear_from (bitmap head, bitmap_element *elt)
       elt->prev = bitmap_ggc_free;
       bitmap_ggc_free = elt;
     }
+
+#ifdef ENABLE_CHECKING
+  if (head->current)
+    {
+      for (prev = head->first; prev; prev = prev->next)
+	{
+	  if (head->current == prev)
+	    break;
+	}
+      /* If this hits, the caller should set current to first before
+	 calling us.  */
+      gcc_assert (prev);
+    }
+#endif
 }
 
 /* Clear a bitmap by freeing the linked list.  */
@@ -1596,6 +1609,8 @@  bitmap_ior (bitmap dst, const_bitmap a, const_bitmap b)
   if (dst_elt)
     {
       changed = true;
+      /* Ensure that dst->current is valid.  */
+      dst->current = dst->first;
       bitmap_elt_clear_from (dst, dst_elt);
     }
   gcc_checking_assert (!dst->current == !dst->first);
@@ -1952,6 +1967,8 @@  bitmap_ior_and_compl (bitmap dst, const_bitmap a, const_bitmap b, const_bitmap k
   if (dst_elt)
     {
       changed = true;
+      /* Ensure that dst->current is valid.  */
+      dst->current = dst->first;
       bitmap_elt_clear_from (dst, dst_elt);
     }
   gcc_checking_assert (!dst->current == !dst->first);