This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
[PATCH]: Fix nasty little bitmap.c bug
- To: gcc-patches at gcc dot gnu dot org
- Subject: [PATCH]: Fix nasty little bitmap.c bug
- From: Daniel Berlin <dan at cgsoftware dot com>
- Date: Mon, 22 Oct 2001 02:47:09 -0400
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;