From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 16627 invoked by alias); 22 Jun 2009 17:06:15 -0000 Received: (qmail 16614 invoked by uid 22791); 22 Jun 2009 17:06:13 -0000 X-SWARE-Spam-Status: No, hits=-2.5 required=5.0 tests=AWL,BAYES_00,SPF_HELO_PASS,SPF_PASS X-Spam-Check-By: sourceware.org Received: from mx1.redhat.com (HELO mx1.redhat.com) (66.187.233.31) by sourceware.org (qpsmtpd/0.43rc1) with ESMTP; Mon, 22 Jun 2009 17:06:06 +0000 Received: from int-mx1.corp.redhat.com (int-mx1.corp.redhat.com [172.16.52.254]) by mx1.redhat.com (8.13.8/8.13.8) with ESMTP id n5MH63SD015230; Mon, 22 Jun 2009 13:06:03 -0400 Received: from omfg.slc.redhat.com (vpn-14-56.rdu.redhat.com [10.11.14.56]) by int-mx1.corp.redhat.com (8.13.1/8.13.1) with ESMTP id n5MH62GB013755; Mon, 22 Jun 2009 13:06:03 -0400 Message-ID: <4A3FBA1E.6040502@redhat.com> Date: Mon, 22 Jun 2009 17:06:00 -0000 From: Jeff Law User-Agent: Thunderbird 2.0.0.21 (X11/20090320) MIME-Version: 1.0 To: Richard Guenther CC: GCC Subject: Re: (known?) Issue with bitmap iterators References: <4A3CF81C.7050406@redhat.com> <84fc9c000906200801v28f814cj3fa5327c5f3df35e@mail.gmail.com> In-Reply-To: <84fc9c000906200801v28f814cj3fa5327c5f3df35e@mail.gmail.com> Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit X-IsSubscribed: yes Mailing-List: contact gcc-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Archive: List-Post: List-Help: Sender: gcc-owner@gcc.gnu.org X-SW-Source: 2009-06/txt/msg00512.txt.bz2 Richard Guenther wrote: > On Sat, Jun 20, 2009 at 4:54 PM, Jeff Law 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