* (known?) Issue with bitmap iterators @ 2009-06-20 14:53 Jeff Law 2009-06-20 15:01 ` Richard Guenther 2009-06-22 2:44 ` Daniel Berlin 0 siblings, 2 replies; 22+ messages in thread From: Jeff Law @ 2009-06-20 14:53 UTC (permalink / raw) To: GCC 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 ^ permalink raw reply [flat|nested] 22+ messages in thread
* Re: (known?) Issue with bitmap iterators 2009-06-20 14:53 (known?) Issue with bitmap iterators Jeff Law @ 2009-06-20 15:01 ` Richard Guenther 2009-06-21 3:27 ` Peter Bergner 2009-06-22 17:06 ` Jeff Law 2009-06-22 2:44 ` Daniel Berlin 1 sibling, 2 replies; 22+ messages in thread From: Richard Guenther @ 2009-06-20 15:01 UTC (permalink / raw) To: Jeff Law; +Cc: GCC 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 > ^ permalink raw reply [flat|nested] 22+ messages in thread
* Re: (known?) Issue with bitmap iterators 2009-06-20 15:01 ` Richard Guenther @ 2009-06-21 3:27 ` Peter Bergner 2009-06-22 17:06 ` Jeff Law 1 sibling, 0 replies; 22+ messages in thread From: Peter Bergner @ 2009-06-21 3:27 UTC (permalink / raw) To: Richard Guenther; +Cc: Jeff Law, GCC 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 ^ permalink raw reply [flat|nested] 22+ messages in thread
* Re: (known?) Issue with bitmap iterators 2009-06-20 15:01 ` Richard Guenther 2009-06-21 3:27 ` Peter Bergner @ 2009-06-22 17:06 ` Jeff Law 2009-06-22 17:46 ` Joe Buck 1 sibling, 1 reply; 22+ messages in thread From: Jeff Law @ 2009-06-22 17:06 UTC (permalink / raw) To: Richard Guenther; +Cc: GCC 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 ^ permalink raw reply [flat|nested] 22+ messages in thread
* Re: (known?) Issue with bitmap iterators 2009-06-22 17:06 ` Jeff Law @ 2009-06-22 17:46 ` Joe Buck 2009-06-22 19:07 ` Dave Korn 2009-06-25 18:37 ` Jeff Law 0 siblings, 2 replies; 22+ messages in thread From: Joe Buck @ 2009-06-22 17:46 UTC (permalink / raw) To: Jeff Law; +Cc: Richard Guenther, GCC 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. ^ permalink raw reply [flat|nested] 22+ messages in thread
* Re: (known?) Issue with bitmap iterators 2009-06-22 17:46 ` Joe Buck @ 2009-06-22 19:07 ` Dave Korn 2009-06-25 18:11 ` Daniel Berlin 2009-06-25 18:37 ` Jeff Law 1 sibling, 1 reply; 22+ messages in thread From: Dave Korn @ 2009-06-22 19:07 UTC (permalink / raw) To: Joe Buck; +Cc: Jeff Law, Richard Guenther, GCC 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 ^ permalink raw reply [flat|nested] 22+ messages in thread
* Re: (known?) Issue with bitmap iterators 2009-06-22 19:07 ` Dave Korn @ 2009-06-25 18:11 ` Daniel Berlin 0 siblings, 0 replies; 22+ messages in thread From: Daniel Berlin @ 2009-06-25 18:11 UTC (permalink / raw) To: Dave Korn; +Cc: Joe Buck, Jeff Law, Richard Guenther, GCC 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. ^ permalink raw reply [flat|nested] 22+ messages in thread
* Re: (known?) Issue with bitmap iterators 2009-06-22 17:46 ` Joe Buck 2009-06-22 19:07 ` Dave Korn @ 2009-06-25 18:37 ` Jeff Law 2009-06-25 22:39 ` Dave Korn 2009-06-26 10:47 ` Alexander Monakov 1 sibling, 2 replies; 22+ messages in thread From: Jeff Law @ 2009-06-25 18:37 UTC (permalink / raw) To: Joe Buck; +Cc: Richard Guenther, GCC 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 ^ permalink raw reply [flat|nested] 22+ messages in thread
* Re: (known?) Issue with bitmap iterators 2009-06-25 18:37 ` Jeff Law @ 2009-06-25 22:39 ` Dave Korn 2009-07-01 2:14 ` Jeff Law 2009-06-26 10:47 ` Alexander Monakov 1 sibling, 1 reply; 22+ messages in thread From: Dave Korn @ 2009-06-25 22:39 UTC (permalink / raw) To: Jeff Law; +Cc: Joe Buck, Richard Guenther, GCC 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 ^ permalink raw reply [flat|nested] 22+ messages in thread
* Re: (known?) Issue with bitmap iterators 2009-06-25 22:39 ` Dave Korn @ 2009-07-01 2:14 ` Jeff Law 0 siblings, 0 replies; 22+ messages in thread From: Jeff Law @ 2009-07-01 2:14 UTC (permalink / raw) To: Dave Korn; +Cc: Joe Buck, Richard Guenther, gcc@gcc.gnu.org >> GCC 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 ^ permalink raw reply [flat|nested] 22+ messages in thread
* Re: (known?) Issue with bitmap iterators 2009-06-25 18:37 ` Jeff Law 2009-06-25 22:39 ` Dave Korn @ 2009-06-26 10:47 ` Alexander Monakov 2009-06-26 16:51 ` Joe Buck 1 sibling, 1 reply; 22+ messages in thread From: Alexander Monakov @ 2009-06-26 10:47 UTC (permalink / raw) To: Jeff Law; +Cc: Joe Buck, Richard Guenther, GCC 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 ^ permalink raw reply [flat|nested] 22+ messages in thread
* Re: (known?) Issue with bitmap iterators 2009-06-26 10:47 ` Alexander Monakov @ 2009-06-26 16:51 ` Joe Buck 2009-06-26 19:28 ` Alexander Monakov 0 siblings, 1 reply; 22+ messages in thread From: Joe Buck @ 2009-06-26 16:51 UTC (permalink / raw) To: Alexander Monakov; +Cc: Jeff Law, Richard Guenther, GCC 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. ^ permalink raw reply [flat|nested] 22+ messages in thread
* Re: (known?) Issue with bitmap iterators 2009-06-26 16:51 ` Joe Buck @ 2009-06-26 19:28 ` Alexander Monakov 2009-07-01 2:21 ` Jeff Law 0 siblings, 1 reply; 22+ messages in thread From: Alexander Monakov @ 2009-06-26 19:28 UTC (permalink / raw) To: Joe Buck; +Cc: Jeff Law, Richard Guenther, GCC 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. ^ permalink raw reply [flat|nested] 22+ messages in thread
* Re: (known?) Issue with bitmap iterators 2009-06-26 19:28 ` Alexander Monakov @ 2009-07-01 2:21 ` Jeff Law 2009-07-01 6:48 ` Dave Korn 0 siblings, 1 reply; 22+ messages in thread From: Jeff Law @ 2009-07-01 2:21 UTC (permalink / raw) To: Alexander Monakov; +Cc: Joe Buck, Richard Guenther, GCC 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. ^ permalink raw reply [flat|nested] 22+ messages in thread
* Re: (known?) Issue with bitmap iterators 2009-07-01 2:21 ` Jeff Law @ 2009-07-01 6:48 ` Dave Korn 0 siblings, 0 replies; 22+ messages in thread From: Dave Korn @ 2009-07-01 6:48 UTC (permalink / raw) To: Jeff Law; +Cc: Alexander Monakov, Joe Buck, Richard Guenther, GCC 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 ^ permalink raw reply [flat|nested] 22+ messages in thread
* Re: (known?) Issue with bitmap iterators 2009-06-20 14:53 (known?) Issue with bitmap iterators Jeff Law 2009-06-20 15:01 ` Richard Guenther @ 2009-06-22 2:44 ` Daniel Berlin 2009-06-22 11:33 ` Dave Korn 2009-06-22 14:27 ` Andrew MacLeod 1 sibling, 2 replies; 22+ messages in thread From: Daniel Berlin @ 2009-06-22 2:44 UTC (permalink / raw) To: Jeff Law; +Cc: GCC 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? ^ permalink raw reply [flat|nested] 22+ messages in thread
* Re: (known?) Issue with bitmap iterators 2009-06-22 2:44 ` Daniel Berlin @ 2009-06-22 11:33 ` Dave Korn 2009-06-22 11:37 ` Richard Guenther 2009-06-22 14:27 ` Andrew MacLeod 1 sibling, 1 reply; 22+ messages in thread From: Dave Korn @ 2009-06-22 11:33 UTC (permalink / raw) To: Daniel Berlin; +Cc: Jeff Law, GCC 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 ^ permalink raw reply [flat|nested] 22+ messages in thread
* Re: (known?) Issue with bitmap iterators 2009-06-22 11:33 ` Dave Korn @ 2009-06-22 11:37 ` Richard Guenther 2009-06-22 13:06 ` Dave Korn 0 siblings, 1 reply; 22+ messages in thread From: Richard Guenther @ 2009-06-22 11:37 UTC (permalink / raw) To: Dave Korn; +Cc: Daniel Berlin, Jeff Law, GCC 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 > > ^ permalink raw reply [flat|nested] 22+ messages in thread
* Re: (known?) Issue with bitmap iterators 2009-06-22 11:37 ` Richard Guenther @ 2009-06-22 13:06 ` Dave Korn 2009-06-22 13:38 ` Paolo Bonzini 0 siblings, 1 reply; 22+ messages in thread From: Dave Korn @ 2009-06-22 13:06 UTC (permalink / raw) To: Richard Guenther; +Cc: Dave Korn, Daniel Berlin, Jeff Law, GCC 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 ^ permalink raw reply [flat|nested] 22+ messages in thread
* Re: (known?) Issue with bitmap iterators 2009-06-22 13:06 ` Dave Korn @ 2009-06-22 13:38 ` Paolo Bonzini 2009-06-22 19:03 ` Dave Korn 0 siblings, 1 reply; 22+ messages in thread From: Paolo Bonzini @ 2009-06-22 13:38 UTC (permalink / raw) To: Dave Korn; +Cc: Richard Guenther, Daniel Berlin, Jeff Law, GCC > 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 ^ permalink raw reply [flat|nested] 22+ messages in thread
* Re: (known?) Issue with bitmap iterators 2009-06-22 13:38 ` Paolo Bonzini @ 2009-06-22 19:03 ` Dave Korn 0 siblings, 0 replies; 22+ messages in thread From: Dave Korn @ 2009-06-22 19:03 UTC (permalink / raw) To: Paolo Bonzini; +Cc: Dave Korn, Richard Guenther, Daniel Berlin, Jeff Law, GCC 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 ^ permalink raw reply [flat|nested] 22+ messages in thread
* Re: (known?) Issue with bitmap iterators 2009-06-22 2:44 ` Daniel Berlin 2009-06-22 11:33 ` Dave Korn @ 2009-06-22 14:27 ` Andrew MacLeod 1 sibling, 0 replies; 22+ messages in thread From: Andrew MacLeod @ 2009-06-22 14:27 UTC (permalink / raw) To: Daniel Berlin; +Cc: Jeff Law, GCC 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 ^ permalink raw reply [flat|nested] 22+ messages in thread
end of thread, other threads:[~2009-07-01 6:48 UTC | newest] Thread overview: 22+ messages (download: mbox.gz / follow: Atom feed) -- links below jump to the message on this page -- 2009-06-20 14:53 (known?) Issue with bitmap iterators Jeff Law 2009-06-20 15:01 ` Richard Guenther 2009-06-21 3:27 ` Peter Bergner 2009-06-22 17:06 ` Jeff Law 2009-06-22 17:46 ` Joe Buck 2009-06-22 19:07 ` Dave Korn 2009-06-25 18:11 ` Daniel Berlin 2009-06-25 18:37 ` Jeff Law 2009-06-25 22:39 ` Dave Korn 2009-07-01 2:14 ` Jeff Law 2009-06-26 10:47 ` Alexander Monakov 2009-06-26 16:51 ` Joe Buck 2009-06-26 19:28 ` Alexander Monakov 2009-07-01 2:21 ` Jeff Law 2009-07-01 6:48 ` Dave Korn 2009-06-22 2:44 ` Daniel Berlin 2009-06-22 11:33 ` Dave Korn 2009-06-22 11:37 ` Richard Guenther 2009-06-22 13:06 ` Dave Korn 2009-06-22 13:38 ` Paolo Bonzini 2009-06-22 19:03 ` Dave Korn 2009-06-22 14:27 ` Andrew MacLeod
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox; as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).