This is the mail archive of the gcc-patches@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]

[PATCH]: Fix nasty little bitmap.c bug


This is a bug that we are very lucky hasn't affected anything.
In fact, it only hasn't because of a single select operator, but i'll 
get to that.

There is an evil little bug in bitmap.c i noticed today.

The head->indx isn't always equal to head->current->indx, even though it 
should be.

For those not familiar with the bitmap structure:
head->indx == Index of last element we looked at.
head->current == Last element we looked at.

This bug is that  we set head->current in bitmap_element_free without 
setting head->indx, causing the head->indx to not match 
head->current->indx right after an element free.

In order to have ever been able to trigger this, you'd have to either 
have added an assert, or added code bitmap_find_bit that depended on the 
head->indx being correct.
First I did the second, then added the assert to prove i wasn't on crack 
after i spent a day trying to find a bug in my own simple code, which 
really had no bug.

The real reason it never triggers is actually twofold.
1. bitmap_element_free isn't used in bitmap_operation (It's only used in 
bitmap_clear_bit, even though we do the equivalent in bitmap_operation).
2. By chance, bitmap_element_free happens to choose to set current to 
next, rather than prev, unless next is 0.  Thus, even though we end up 
testing against the wrong value in a subsequence bitmap_find_bit, we 
never get the wrong test result.  Provably.
Watch: Say you had a bitmap with elements 0, 3, 5, each with one bit set.
You clear the bit in 3, causing it to deallocate.
head->indx will now be 3
head->current will now be element 5
In order to affect the result of the next bit find operation, you'd have 
to ask for a bit that *was* set in an element between 3 and 5.  If you 
did, we'd look forward from 5, and never find the element, since it 
would be backwards from 5.
But there is no element between 3 and 5 in this bitmap, so even though 
the search looks the wrong way, it correctly says it can't find the 
element.
If there *was* an element between 3 and 5 that had a bit set,  it would 
have to have been element 4, which would have had to been pointed to by 
3's next pointer, and thus, would have been chosen as the new 
head->current, instead of element 5, also relieving us of the problem.
This of course, extends to arbitrarily long ranges. The only elements we 
could ever effect, can't exist, because it chooses next over prev.
A similar proof can be shown for the other possible case, which would be 
if the bit you clear causes the last element in the list to be 
deallocated (thus causing bitmap_element_free to choose prev as the new 
current, making the index value too low, rather than too high).

Of course, I could be wrong about never being able to affect the result, 
since it's late. But i'm pretty darn sure, and also sure it would have 
been noticed by now.
I noticed this bug while adding some code to bitmap_find_bit to short 
circuit two trivial cases (not do the rest of the search if 
head->indx == indx, and not do the rest of the search if we can show the 
bit will be out of range for the bitmap), both of which, of course, are 
affected by this bug.

Because of the way this bug works, it's not possible to come up with a 
test case.
However, you can easily prove it exists.
#include <assert.h> in bitmap.c

add the line "assert (head->indx == head->current->indx);" right after 
line 300 in bitmap.c (the "return 0;" after "if (head->current == 0)" in 
bitmap_find_bit).

Now compile something at -O2 (I use a preprocessed expr.c), and it'll 
abort because ot the assertion.

Here's the fix.  Okay to apply?

2001-10-22  Daniel Berlin  <dan@cgsoftware.com>

          * bitmap.c (bitmap_element_free): Fix head->indx not being set
	when we set current.

Index: bitmap.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/bitmap.c,v
retrieving revision 1.32
diff -c -3 -p -w -B -b -r1.32 bitmap.c
*** bitmap.c	2001/08/22 14:34:42	1.32
--- bitmap.c	2001/10/22 06:36:54
*************** bitmap_element_free (head, elt)
*** 70,76 ****
--- 70,80 ----
     /* Since the first thing we try is to insert before current,
        make current the next entry in preference to the previous.  */
     if (head->current == elt)
+     {
         head->current = next != 0 ? next : prev;
+       if (head->current)
+ 	  head->indx = head->current->indx;
+     }

     elt->next = bitmap_free;
     bitmap_free = elt;



Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]