(known?) Issue with bitmap iterators

(known?) Issue with bitmap iterators

[Jeff Law]

Imagine a loop like this

EXECUTE_IF_SET_IN_BITMAP (something, 0, i, bi)
  {
    bitmap_clear_bit (something, i)
    [ ... whatever code we want to process i, ... ]
  }

This code is unsafe.

If bit I happens to be the only bit set in the current bitmap word, then 
bitmap_clear_bit will free the current element and return it to the 
element free list where it can be recycled.

So assume the bitmap element gets recycled for some other bitmap...  We 
then come around to the top of the loop where EXECUTE_IF_SET_IN_BITMAP 
will call bmp_iter_set which can reference the recycled element when it 
tries to advance to the next element via bi->elt1 = bi->elt1->next.  So 
we start iterating on elements of a completely different bitmap.  You 
can assume this is not good.

Our documentation clearly states that I is to remain unchanged, but ISTM 
that the bitmap we're iterating over needs to remain unchanged as well. 

Is this a known issue, or am I just the lucky bastard who tripped over 
it and now gets to audit all the EXECUTE_IF_SET_IN_BITMAP loops?

Jeff

Re: (known?) Issue with bitmap iterators

[Richard Guenther]

On Sat, Jun 20, 2009 at 4:54 PM, Jeff Law<law@redhat.com> wrote:
>
> Imagine a loop like this
>
> EXECUTE_IF_SET_IN_BITMAP (something, 0, i, bi)
>  {
>   bitmap_clear_bit (something, i)
>   [ ... whatever code we want to process i, ... ]
>  }
>
> This code is unsafe.
>
> If bit I happens to be the only bit set in the current bitmap word, then
> bitmap_clear_bit will free the current element and return it to the element
> free list where it can be recycled.
>
> So assume the bitmap element gets recycled for some other bitmap...  We then
> come around to the top of the loop where EXECUTE_IF_SET_IN_BITMAP will call
> bmp_iter_set which can reference the recycled element when it tries to
> advance to the next element via bi->elt1 = bi->elt1->next.  So we start
> iterating on elements of a completely different bitmap.  You can assume this
> is not good.
>
> Our documentation clearly states that I is to remain unchanged, but ISTM
> that the bitmap we're iterating over needs to remain unchanged as well.
> Is this a known issue, or am I just the lucky bastard who tripped over it
> and now gets to audit all the EXECUTE_IF_SET_IN_BITMAP loops?

It is known (but maybe not appropriately documented) that deleting
bits in the bitmap you iterate over is not safe.  If it would be me I would
see if I could make it safe though.

Richard.

> Jeff
>

Re: (known?) Issue with bitmap iterators

[Peter Bergner]

On Sat, 2009-06-20 at 17:01 +0200, Richard Guenther wrote:
> On Sat, Jun 20, 2009 at 4:54 PM, Jeff Law<law@redhat.com> wrote:
> >
> > Imagine a loop like this
> >
> > EXECUTE_IF_SET_IN_BITMAP (something, 0, i, bi)
> >  {
> >   bitmap_clear_bit (something, i)
> >   [ ... whatever code we want to process i, ... ]
> >  }
> >
> > This code is unsafe.

[snip]

> It is known (but maybe not appropriately documented) that deleting
> bits in the bitmap you iterate over is not safe.  If it would be me I would
> see if I could make it safe though.

FYI, that's what I did with the sparseset implementation, so:

  EXECUTE_IF_SET_IN_SPARSESET (something, i)
    {
      sparseset_clear_bit (something, i);
      [ ... whatever code we want to process i, ... ]
    }

is safe.  In fact, we use it for one of the special cases in
sparseset_and() and sparseset_and_compl().


Peter

Re: (known?) Issue with bitmap iterators

[Jeff Law]

Richard Guenther wrote:
> On Sat, Jun 20, 2009 at 4:54 PM, Jeff Law<law@redhat.com> wrote:
>   
>> Imagine a loop like this
>>
>> EXECUTE_IF_SET_IN_BITMAP (something, 0, i, bi)
>>  {
>>   bitmap_clear_bit (something, i)
>>   [ ... whatever code we want to process i, ... ]
>>  }
>>
>> This code is unsafe.
>>
>> If bit I happens to be the only bit set in the current bitmap word, then
>> bitmap_clear_bit will free the current element and return it to the element
>> free list where it can be recycled.
>>
>> So assume the bitmap element gets recycled for some other bitmap...  We then
>> come around to the top of the loop where EXECUTE_IF_SET_IN_BITMAP will call
>> bmp_iter_set which can reference the recycled element when it tries to
>> advance to the next element via bi->elt1 = bi->elt1->next.  So we start
>> iterating on elements of a completely different bitmap.  You can assume this
>> is not good.
>>
>> Our documentation clearly states that I is to remain unchanged, but ISTM
>> that the bitmap we're iterating over needs to remain unchanged as well.
>> Is this a known issue, or am I just the lucky bastard who tripped over it
>> and now gets to audit all the EXECUTE_IF_SET_IN_BITMAP loops?
>>     
>
> It is known (but maybe not appropriately documented) that deleting
> bits in the bitmap you iterate over is not safe.  If it would be me I would
> see if I could make it safe though.
>   
It's not a huge deal -- what bothers me is that it's not documented.  
Someone thought enough to document that the loop index shouldn't be 
modified in the loop, but didn't bother to mention that the bitmap 
itself shouldn't be modified in the loop.

I'd lean towards the idea of making the bitmap readonly -- hopefully 
everyone already knows they can't set bits in the bitmap and expect the 
iterator to work, so let's keep things consistent with clearing bits.  
If we can back that up with some checking code, then I think we'd be in 
good shape.

jeff

Re: (known?) Issue with bitmap iterators

[Joe Buck]

Richard Guenther wrote:
> > It is known (but maybe not appropriately documented) that deleting
> > bits in the bitmap you iterate over is not safe.  If it would be me I would
> > see if I could make it safe though.

On Mon, Jun 22, 2009 at 10:06:38AM -0700, Jeff Law wrote:
> It's not a huge deal -- what bothers me is that it's not documented.
> Someone thought enough to document that the loop index shouldn't be
> modified in the loop, but didn't bother to mention that the bitmap
> itself shouldn't be modified in the loop.

As a general rule there is a performance cost for making iterators
on a data structure safe with respect to modifications of that data
structure.  I'm not in a position to say what the right solution is
in this case, but passes that iterate over bitmaps without modifying
those bitmaps shouldn't be penalized.  One solution sometimes used is
two sets of iterators, with a slower version that's safe under
modification.

Re: (known?) Issue with bitmap iterators

[Dave Korn]

Joe Buck wrote:

> As a general rule there is a performance cost for making iterators
> on a data structure safe with respect to modifications of that data
> structure.  I'm not in a position to say what the right solution is
> in this case, but passes that iterate over bitmaps without modifying
> those bitmaps shouldn't be penalized.  One solution sometimes used is
> two sets of iterators, with a slower version that's safe under
> modification.

  But then we'll run into the same bug again when someone uses the wrong kind,
or changes the usage of a bitmap without changing which type it is.  I think
making them all safe, but under --enable-checking only, with the safety code
compiled out when it's disabled might be a nice solution.

    cheers,
      DaveK

Re: (known?) Issue with bitmap iterators

[Daniel Berlin]

On Mon, Jun 22, 2009 at 3:19 PM, Dave
Korn<dave.korn.cygwin@googlemail.com> wrote:
> Joe Buck wrote:
>
>> As a general rule there is a performance cost for making iterators
>> on a data structure safe with respect to modifications of that data
>> structure.  I'm not in a position to say what the right solution is
>> in this case, but passes that iterate over bitmaps without modifying
>> those bitmaps shouldn't be penalized.  One solution sometimes used is
>> two sets of iterators, with a slower version that's safe under
>> modification.
>
>  But then we'll run into the same bug again when someone uses the wrong kind,
> or changes the usage of a bitmap without changing which type it is.

We have this situation with, for example, the immediate use iterators,
and at least as far as anyone knows, it hasn't been broken yet ;)
So i don't think we should be too worried about it happening if we
were to create two types of iterators.

Re: (known?) Issue with bitmap iterators

[Jeff Law]

Joe Buck wrote:
> As a general rule there is a performance cost for making iterators
> on a data structure safe with respect to modifications of that data
> structure.  
Absolutely true. 

> I'm not in a position to say what the right solution is
> in this case, but passes that iterate over bitmaps without modifying
> those bitmaps shouldn't be penalized.  One solution sometimes used is
> two sets of iterators, with a slower version that's safe under
> modification.
>   
I wasn't suggesting we make them "safe" in the sense that one could 
modify the bitmap and everything would just work.  Instead I was 
suggesting we make the bitmap readonly for the duration of the iterator 
and catch attempts to modify the bitmap -- under the control of 
ENABLE_CHECKING of course.  If that turns out to still be too expensive, 
it could be conditional on ENABLE_BITMAP_ITERATOR_CHECKING or whatever, 
which would normally be off.

My biggest concern would be catching all the exit paths from the 
gazillion iterators we use and making sure they all reset the readonly 
flag.  Ick...


jeff

Re: (known?) Issue with bitmap iterators

[Dave Korn]

Jeff Law wrote:

> My biggest concern would be catching all the exit paths from the
> gazillion iterators we use and making sure they all reset the readonly
> flag.  Ick...


  Heh.  GCC-in-CXX would solve that for us :) or we could implement
try...finally clauses ....

    cheers,
      DaveK

Re: (known?) Issue with bitmap iterators

[Jeff Law]

Dave Korn wrote:
> Jeff Law wrote:
>
>   
>> My biggest concern would be catching all the exit paths from the
>> gazillion iterators we use and making sure they all reset the readonly
>> flag.  Ick...
>>     
>
>
>   Heh.  GCC-in-CXX would solve that for us :) or we could implement
> try...finally clauses ....
>   
One of the cases where C++ makes sense. 

jeff

Re: (known?) Issue with bitmap iterators

[Alexander Monakov]

On Thu, 25 Jun 2009, Jeff Law wrote:
> I wasn't suggesting we make them "safe" in the sense that one could modify 
> the bitmap and everything would just work.  Instead I was suggesting we make 
> the bitmap readonly for the duration of the iterator and catch attempts to 
> modify the bitmap -- under the control of ENABLE_CHECKING of course.  If that 
> turns out to still be too expensive, it could be conditional on 
> ENABLE_BITMAP_ITERATOR_CHECKING or whatever, which would normally be off.
>
> My biggest concern would be catching all the exit paths from the gazillion 
> iterators we use and making sure they all reset the readonly flag.  Ick...

Unless I'm missing something, one can avoid that by checking whether the 
bitmap has been modified in the iterator increment function.  To be 
precise, what I have in mind is:

1. Add bool field `modified_p' in bitmap structure.
2. Make iterator setup functions (e.g. bmp_iter_set_init) reset it to 
false.
3. Make functions that modify the bitmap set it to true.
4. Make iterator increment function (e.g. bmp_iter_next) assert 
!modified_p.

This approach would also allow to modify the bitmap on the iteration 
ending with break, which IMHO is fine.

-- 
Alexander Monakov

Re: (known?) Issue with bitmap iterators

[Joe Buck]

On Fri, Jun 26, 2009 at 03:38:31AM -0700, Alexander Monakov wrote:
> 1. Add bool field `modified_p' in bitmap structure.
> 2. Make iterator setup functions (e.g. bmp_iter_set_init) reset it to
> false.
> 3. Make functions that modify the bitmap set it to true.
> 4. Make iterator increment function (e.g. bmp_iter_next) assert
> !modified_p.

Sorry, it doesn't work.  Function foo has a loop that iterates
over a bitmap.  During the iteration, it calls a function bar.  bar
modifies the bitmap, then iterates over the bitmap.  It then returns
to foo, which is in the middle of an iteration, which it continues.
The bitmap has been modified (by bar), but modified_p was reset to
false by the iteration that happened at the end of bar.

Re: (known?) Issue with bitmap iterators

[Alexander Monakov]

On Fri, 26 Jun 2009, Joe Buck wrote:

> On Fri, Jun 26, 2009 at 03:38:31AM -0700, Alexander Monakov wrote:
>> 1. Add bool field `modified_p' in bitmap structure.
>> 2. Make iterator setup functions (e.g. bmp_iter_set_init) reset it to
>> false.
>> 3. Make functions that modify the bitmap set it to true.
>> 4. Make iterator increment function (e.g. bmp_iter_next) assert
>> !modified_p.
>
> Sorry, it doesn't work.  Function foo has a loop that iterates
> over a bitmap.  During the iteration, it calls a function bar.  bar
> modifies the bitmap, then iterates over the bitmap.  It then returns
> to foo, which is in the middle of an iteration, which it continues.
> The bitmap has been modified (by bar), but modified_p was reset to
> false by the iteration that happened at the end of bar.

Good catch, thanks!  Let me patch that up a bit:

1. Add int field `generation' in bitmap structure, initialized arbitrarily 
at bitmap creation time.
2. Make iterator setup functions save initial generation count in the 
iterator (or generation counts for two bitmaps, if needed).
3. Modify generation count when bitmap is modified (e.g. increment it).
4. Verify that saved and current generations match when incrementing the 
iterator.

Re: (known?) Issue with bitmap iterators

[Jeff Law]

Alexander Monakov wrote:
>
>
> On Fri, 26 Jun 2009, Joe Buck wrote:
>
>> On Fri, Jun 26, 2009 at 03:38:31AM -0700, Alexander Monakov wrote:
>>> 1. Add bool field `modified_p' in bitmap structure.
>>> 2. Make iterator setup functions (e.g. bmp_iter_set_init) reset it to
>>> false.
>>> 3. Make functions that modify the bitmap set it to true.
>>> 4. Make iterator increment function (e.g. bmp_iter_next) assert
>>> !modified_p.
>>
>> Sorry, it doesn't work.  Function foo has a loop that iterates
>> over a bitmap.  During the iteration, it calls a function bar.  bar
>> modifies the bitmap, then iterates over the bitmap.  It then returns
>> to foo, which is in the middle of an iteration, which it continues.
>> The bitmap has been modified (by bar), but modified_p was reset to
>> false by the iteration that happened at the end of bar.
>
> Good catch, thanks!  Let me patch that up a bit:
>
> 1. Add int field `generation' in bitmap structure, initialized 
> arbitrarily at bitmap creation time.
> 2. Make iterator setup functions save initial generation count in the 
> iterator (or generation counts for two bitmaps, if needed).
> 3. Modify generation count when bitmap is modified (e.g. increment it).
> 4. Verify that saved and current generations match when incrementing 
> the iterator.
It's not bad -- we don't catch the offending modification when it 
occurs, but I guess if we trigger the check, then it's not terribly 
difficult to use conditional breakpoint under the debugger to get a 
better idea of when/how we tried to modify a bitmap while iterating over 
it.  I can probably break this with some ugly exit code from an iterator 
(*), but it'd be a big step forward.



Jeff

(*) Imagine something like this (and related variants)

EXECUTE_IF_SET_IN_BITMAP (bitmap, 0, i, bi)
{
  blah blah blah

  if (bitmap_empty_p (bitmap))
    {
      modify bitmap
      break;
    }
  more blah blah
}

We exit without iterating BI and thus miss your check. 

Re: (known?) Issue with bitmap iterators

[Dave Korn]

Jeff Law wrote:

> (*) Imagine something like this (and related variants)
> 
> EXECUTE_IF_SET_IN_BITMAP (bitmap, 0, i, bi)
> {
>  blah blah blah
> 
>  if (bitmap_empty_p (bitmap))
>    {
>      modify bitmap
>      break;
>    }
>  more blah blah
> }
> 
> We exit without iterating BI and thus miss your check.

  That's OK; there's no problem if you don't use the iterator again after you
modify the bitmap.

    cheers,
      DaveK

Re: (known?) Issue with bitmap iterators

[Daniel Berlin]

On Sat, Jun 20, 2009 at 10:54 AM, Jeff Law<law@redhat.com> wrote:
>
> Imagine a loop like this
>
> EXECUTE_IF_SET_IN_BITMAP (something, 0, i, bi)
>  {
>   bitmap_clear_bit (something, i)
>   [ ... whatever code we want to process i, ... ]
>  }
>
> This code is unsafe.
>
> If bit I happens to be the only bit set in the current bitmap word, then
> bitmap_clear_bit will free the current element and return it to the element
> free list where it can be recycled.
>
> So assume the bitmap element gets recycled for some other bitmap...  We then
> come around to the top of the loop where EXECUTE_IF_SET_IN_BITMAP will call
> bmp_iter_set which can reference the recycled element when it tries to
> advance to the next element via bi->elt1 = bi->elt1->next.  So we start
> iterating on elements of a completely different bitmap.  You can assume this
> is not good.
>
> Our documentation clearly states that I is to remain unchanged, but ISTM
> that the bitmap we're iterating over needs to remain unchanged as well.
> Is this a known issue, or am I just the lucky bastard who tripped over it
> and now gets to audit all the EXECUTE_IF_SET_IN_BITMAP loops?

No, this is known, and in fact, has been a source of "interesting"
bugs in the past since it doesn't segfault, but often, as you've
discovered, starts wandering into the free list happily iterating over
elements from bitmaps of dataflows past.

Making it safe is a little tricky, basically, you need to know whether
the element you are currently iterating over disappears.
At the very worst, you could make pre-delete hooks and have the
iterators register for them or something.
At best, you can probably set a bit in the bitmap saying it's being
iterated over, and then add a tombstone bit, which lets you mark
elements as deleted without actually deleting them until the end of
iteration when they are in the middle of iteration or something.



Also, what do you expect the semantics to be?
In particular, are new bits past the current index iterated over, or
do you expect to iterate over the bitmap as it existed at the time you
started iteration?

Re: (known?) Issue with bitmap iterators

[Dave Korn]

Daniel Berlin wrote:

> Also, what do you expect the semantics to be?

  Since we don't expect an iterator to return the same bit twice when
iterating in any case, the ideal would be that it shouldn't matter what
happens to bits that the iterator has already passed.

> In particular, are new bits past the current index iterated over, or
> do you expect to iterate over the bitmap as it existed at the time you
> started iteration?

  That would be an ecumenical matter!  Err, I mean ... maybe the best solution
(particularly in terms of preventing future bugs) would be for opening an
iterator to put the bitmap into a read-only mode that causes bitmap_clear_bit
or bitmap_set_bit to fail, and that automatically clears when the iterator
runs off the end?

    cheers,
      DaveK

Re: (known?) Issue with bitmap iterators

[Richard Guenther]

On Mon, Jun 22, 2009 at 1:45 PM, Dave
Korn<dave.korn.cygwin@googlemail.com> wrote:
> Daniel Berlin wrote:
>
>> Also, what do you expect the semantics to be?
>
>  Since we don't expect an iterator to return the same bit twice when
> iterating in any case, the ideal would be that it shouldn't matter what
> happens to bits that the iterator has already passed.
>
>> In particular, are new bits past the current index iterated over, or
>> do you expect to iterate over the bitmap as it existed at the time you
>> started iteration?
>
>  That would be an ecumenical matter!  Err, I mean ... maybe the best solution
> (particularly in terms of preventing future bugs) would be for opening an
> iterator to put the bitmap into a read-only mode that causes bitmap_clear_bit
> or bitmap_set_bit to fail, and that automatically clears when the iterator
> runs off the end?

Heh, that sounds useful.  Keep bitmaps forced readonly during
iterating over them but be able to actually verify it.

Might need some new exit-from-iterating magic though.

Richard.

>
>    cheers,
>      DaveK
>
>

Re: (known?) Issue with bitmap iterators

[Dave Korn]

Richard Guenther wrote:
> On Mon, Jun 22, 2009 at 1:45 PM, Dave
> Korn<dave.korn.cygwin@googlemail.com> wrote:
>> Daniel Berlin wrote:
>>
>>> Also, what do you expect the semantics to be?
>>  Since we don't expect an iterator to return the same bit twice when
>> iterating in any case, the ideal would be that it shouldn't matter what
>> happens to bits that the iterator has already passed.
>>
>>> In particular, are new bits past the current index iterated over, or
>>> do you expect to iterate over the bitmap as it existed at the time you
>>> started iteration?
>>  That would be an ecumenical matter!  Err, I mean ... maybe the best solution
>> (particularly in terms of preventing future bugs) would be for opening an
>> iterator to put the bitmap into a read-only mode that causes bitmap_clear_bit
>> or bitmap_set_bit to fail, and that automatically clears when the iterator
>> runs off the end?
> 
> Heh, that sounds useful.  Keep bitmaps forced readonly during
> iterating over them but be able to actually verify it.
> 
> Might need some new exit-from-iterating magic though.

  I took a look.  I don't think it would be hideously hacky to do something
like ...

#define EXECUTE_IF_SET_IN_BITMAP(BITMAP, MIN, BITNUM, ITER)		\
  for ((BITMAP)->ro_flag = true,					\
	bmp_iter_set_init (&(ITER), (BITMAP), (MIN), &(BITNUM));	\
       (BITMAP)->ro_flag = bmp_iter_set (&(ITER), &(BITNUM));		\
       bmp_iter_next (&(ITER), &(BITNUM)))

    cheers,
      DaveK

Re: (known?) Issue with bitmap iterators

[Paolo Bonzini]

>   I took a look.  I don't think it would be hideously hacky to do something
> like ...
> 
> #define EXECUTE_IF_SET_IN_BITMAP(BITMAP, MIN, BITNUM, ITER)		\
>   for ((BITMAP)->ro_flag = true,					\
> 	bmp_iter_set_init (&(ITER), (BITMAP), (MIN), &(BITNUM));	\
>        (BITMAP)->ro_flag = bmp_iter_set (&(ITER), &(BITNUM));		\
>        bmp_iter_next (&(ITER), &(BITNUM)))

You should add a BREAK_FROM_EXECUTE_IF_SET(BITMAP) macro too, however.

Paolo

Re: (known?) Issue with bitmap iterators

[Dave Korn]

Paolo Bonzini wrote:
> 
>>   I took a look.  I don't think it would be hideously hacky to do
>> something like ...
>>
>> #define EXECUTE_IF_SET_IN_BITMAP(BITMAP, MIN, BITNUM, ITER)        \
>>   for ((BITMAP)->ro_flag = true,                    \
>>     bmp_iter_set_init (&(ITER), (BITMAP), (MIN), &(BITNUM));    \
>>        (BITMAP)->ro_flag = bmp_iter_set (&(ITER), &(BITNUM));        \
>>        bmp_iter_next (&(ITER), &(BITNUM)))
> 
> You should add a BREAK_FROM_EXECUTE_IF_SET(BITMAP) macro too, however.
> 
> Paolo

  :) I should, but I'm way too loaded at the moment to actually generate this
patch... already got two simultaneous testruns going that will tie up my PC
for a couple of days.  Sorry.

    cheers,
      DaveK

Re: (known?) Issue with bitmap iterators

[Andrew MacLeod]

Daniel Berlin wrote:
> On Sat, Jun 20, 2009 at 10:54 AM, Jeff Law<law@redhat.com> wrote:
>   
>> Imagine a loop like this
>>
>> EXECUTE_IF_SET_IN_BITMAP (something, 0, i, bi)
>>  {
>>   bitmap_clear_bit (something, i)
>>   [ ... whatever code we want to process i, ... ]
>>  }
>>
>> This code is unsafe.
>>     
> No, this is known, and in fact, has been a source of "interesting"
> bugs in the past since it doesn't segfault, but often, as you've
> discovered, starts wandering into the free list happily iterating over
> elements from bitmaps of dataflows past.
>
> Making it safe is a little tricky, basically, you need to know whether
> the element you are currently iterating over disappears.
> At the very worst, you could make pre-delete hooks and have the
> iterators register for them or something.
> At best, you can probably set a bit in the bitmap saying it's being
> iterated over, and then add a tombstone bit, which lets you mark
> elements as deleted without actually deleting them until the end of
> iteration when they are in the middle of iteration or something.
>
>
>
> Also, what do you expect the semantics to be?
> In particular, are new bits past the current index iterated over, or
> do you expect to iterate over the bitmap as it existed at the time you
> started iteration?
>   
Could we simply pre-calculate the next index early and store it in the 
iterator struct before entering the processing loop for index 'I'? .  
This would allow the current index to be deleted without impacting the 
next iteration.  The changes shouldn't be very significant.

Of course, everything falls apart if you willy nilly change other things 
in the list, especially clearing the 'next' bit, but changing the bit at 
index 'I' must be the most common case by far...

Andrew