Invalidation of bitmap iterator by clearing bits - Intentional or not?

[Daniel Berlin <dberlin at dberlin dot org>]

Recently, I tracked down a bug in somebody else's code to the fact that 
clearing bits in a bitmap you are iterating over can fail miserably in 
some cases, and this is not documented anywhere.  In particular, the 
following loop:

EXECUTE_IF_SET_IN_BITMAP (bitmap, 0, i, bi)
{
	bitmap_clear_bit (bitmap, i);
}

will stop after going through the first element with bits set, 
regardless of whether there are other elements with bits set or not.

What happens is that when you clear the last set bit in the element, it 
frees the element (which the iterator still has a pointer to), and 
places it on the free list.

There are two possibilities as to what the iterator does at this point:

1. If the bitmap element was the only bitmap on the free list, we stop 
iterating, even though there are more set bits in the bitmap.
2. If the bitmap element wasn't the only bitmap on the free list, we 
cutely start iterating over the elements in the freelist (since that is 
where our bitmap element's next pointer now points, to the next element 
on the free list).


Neither of these are good failure modes for catching this undocumented 
behavior.


This raises the question of whether this undocumented behavior is 
intentional or not.

If so, should i make it so the iterator aborts when it starts iterating 
over an element that is now in the free list (by adding a flag to the 
element structure saying it's free when ENABLE_CHECKING is on, and 
checking that flag)?

Or should we just document it in bitmap.h and hope nobody hits this 
problem accidently?

--Dan