From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 11383 invoked by alias); 22 Jun 2009 02:44:15 -0000 Received: (qmail 11375 invoked by uid 22791); 22 Jun 2009 02:44:14 -0000 X-SWARE-Spam-Status: No, hits=-1.7 required=5.0 tests=AWL,BAYES_00,SARE_MSGID_LONG40,SPF_PASS X-Spam-Check-By: sourceware.org Received: from mail-qy0-f194.google.com (HELO mail-qy0-f194.google.com) (209.85.221.194) by sourceware.org (qpsmtpd/0.43rc1) with ESMTP; Mon, 22 Jun 2009 02:44:09 +0000 Received: by qyk32 with SMTP id 32so3448801qyk.0 for ; Sun, 21 Jun 2009 19:44:07 -0700 (PDT) MIME-Version: 1.0 Received: by 10.229.84.72 with SMTP id i8mr969122qcl.63.1245638647072; Sun, 21 Jun 2009 19:44:07 -0700 (PDT) In-Reply-To: <4A3CF81C.7050406@redhat.com> References: <4A3CF81C.7050406@redhat.com> Date: Mon, 22 Jun 2009 02:44:00 -0000 Message-ID: <4aca3dc20906211944hb27a3day21bc22c8a9f58aee@mail.gmail.com> Subject: Re: (known?) Issue with bitmap iterators From: Daniel Berlin To: Jeff Law Cc: GCC Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable 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/msg00499.txt.bz2 On Sat, Jun 20, 2009 at 10:54 AM, Jeff Law wrote: > > Imagine a loop like this > > EXECUTE_IF_SET_IN_BITMAP (something, 0, i, bi) > =A0{ > =A0 bitmap_clear_bit (something, i) > =A0 [ ... whatever code we want to process i, ... ] > =A0} > > 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 eleme= nt > free list where it can be recycled. > > So assume the bitmap element gets recycled for some other bitmap... =A0We= then > come around to the top of the loop where EXECUTE_IF_SET_IN_BITMAP will ca= ll > bmp_iter_set which can reference the recycled element when it tries to > advance to the next element via bi->elt1 =3D bi->elt1->next. =A0So we sta= rt > iterating on elements of a completely different bitmap. =A0You 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?