From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 31069 invoked by alias); 22 Jun 2009 14:27:10 -0000 Received: (qmail 31061 invoked by uid 22791); 22 Jun 2009 14:27:09 -0000 X-SWARE-Spam-Status: No, hits=-2.6 required=5.0 tests=AWL,BAYES_00,SPF_HELO_PASS,SPF_PASS X-Spam-Check-By: sourceware.org Received: from mx2.redhat.com (HELO mx2.redhat.com) (66.187.237.31) by sourceware.org (qpsmtpd/0.43rc1) with ESMTP; Mon, 22 Jun 2009 14:27:01 +0000 Received: from int-mx2.corp.redhat.com (int-mx2.corp.redhat.com [172.16.27.26]) by mx2.redhat.com (8.13.8/8.13.8) with ESMTP id n5MEQxnn008786; Mon, 22 Jun 2009 10:26:59 -0400 Received: from ns3.rdu.redhat.com (ns3.rdu.redhat.com [10.11.255.199]) by int-mx2.corp.redhat.com (8.13.1/8.13.1) with ESMTP id n5MEQwOi025448; Mon, 22 Jun 2009 10:26:58 -0400 Received: from [10.11.12.191] (vpn-12-191.rdu.redhat.com [10.11.12.191]) by ns3.rdu.redhat.com (8.13.8/8.13.8) with ESMTP id n5MEQuku014676; Mon, 22 Jun 2009 10:26:57 -0400 Message-ID: <4A3F94B0.7020308@redhat.com> Date: Mon, 22 Jun 2009 14:27:00 -0000 From: Andrew MacLeod User-Agent: Thunderbird 2.0.0.21 (X11/20090320) MIME-Version: 1.0 To: Daniel Berlin CC: Jeff Law , GCC Subject: Re: (known?) Issue with bitmap iterators References: <4A3CF81C.7050406@redhat.com> <4aca3dc20906211944hb27a3day21bc22c8a9f58aee@mail.gmail.com> In-Reply-To: <4aca3dc20906211944hb27a3day21bc22c8a9f58aee@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/msg00509.txt.bz2 Daniel Berlin wrote: > 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) >> { >> 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