Re: [PATCH gcc/ebitmap] fix for ebitmap_clear_bit()

[Nicolas BENOIT <nbenoit at tuxfamily dot org>]

Steven Bosscher wrote:
> On Thu, Sep 3, 2009 at 8:35 PM, Diego Novillo<dnovillo@google.com> wrote:
> > On Fri, Aug 28, 2009 at 09:43, <nbenoit@tuxfamily.org> wrote:
> > > This patch fixes the reset of the cache in a ebitmap structure after
> > > a clear_bit operation. The map->cacheindex contains wordindex values,
> > > and not eltwordindex values which belong to the wordmask space.
> > >
> > >
> > > 2009-08-28  Nicolas Benoit  <nbenoit@tuxfamily.org>
> > >
> > >        * ebitmap.c (ebitmap_clear_bit): Fixed map->cacheindex test.
> > This looks OK in principle, but it needs a test case.  Could you add one?
>
> Is any pass even using ebitmaps right now?
>
> Ciao!
> Steven


I could not find any pass which is using it in trunk. However, I am 
developing one (for my PhD thesis) which does, that's how I found this 
issue.

I attached to this email the code path which is triggering the bug in my 
code. It is pretty raw, but removing random lines from it prevents the 
bug from happening (as the latter is activated by a specific memory setup).

Please note that it is probably architecture dependent as ebitmap 
elements have unsigned HOST_WIDEST_FAST_INT type.
The test fails on my workstations, which have x86_64 processors, with 
the trunk revision of ebitmap.c.

About the test execution, after the guarded ebitmap_clear_bit() 
operation, the cache of map1 is not reset to NULL because the 
map->cacheindex is compared against the wrong wordindex. As 1252 was the 
last bit set of its element though, the element is freed, so the cache 
points to an invalid memory cell. Then, the bit 1253 is reported set, 
because the ebitmap_bit_p() operation reads an invalid cached element.

I hope you'll be able to reproduce the bug by calling the test from any 
GCC function. I do not know how to set up a testcase externally, sorry.

Best regards,
Nicolas BENOIT.


void
test_ebitmap_clear_bit ( void )
{
  ebitmap map1, map2;
  map1 = ebitmap_alloc ( 1 );
  map2 = ebitmap_alloc ( 1 );

  ebitmap_set_bit ( map1, 1247 );
  ebitmap_set_bit ( map1, 1248 );
  ebitmap_set_bit ( map1, 1249 );
  ebitmap_set_bit ( map1, 1250 );
  ebitmap_set_bit ( map1, 1251 );
  ebitmap_set_bit ( map1, 1252 );
  ebitmap_set_bit ( map1, 1293 );
  ebitmap_set_bit ( map1, 1294 );
  ebitmap_set_bit ( map1, 1295 );
  ebitmap_set_bit ( map1, 1296 );
  ebitmap_set_bit ( map1, 1301 );
  ebitmap_set_bit ( map1, 1302 );
  ebitmap_set_bit ( map1, 1303 );
  ebitmap_set_bit ( map1, 1304 );
  ebitmap_set_bit ( map1, 1313 );
  ebitmap_set_bit ( map1, 1314 );
  ebitmap_set_bit ( map1, 1315 );
  ebitmap_set_bit ( map1, 1316 );
  ebitmap_set_bit ( map1, 1317 );
  ebitmap_set_bit ( map1, 1318 );
  ebitmap_set_bit ( map1, 1319 );
  ebitmap_set_bit ( map1, 1320 );
  ebitmap_set_bit ( map2, 1285 );
  ebitmap_clear_bit ( map1, 1285 );
  ebitmap_set_bit ( map2, 1286 );
  ebitmap_clear_bit ( map1, 1286 );
  ebitmap_set_bit ( map2, 1287 );
  ebitmap_clear_bit ( map1, 1287 );
  ebitmap_set_bit ( map2, 1288 );
  ebitmap_clear_bit ( map1, 1288 );
  ebitmap_clear_bit ( map1, 1233 );
  ebitmap_set_bit ( map2, 1234 );
  ebitmap_clear_bit ( map1, 1234 );
  ebitmap_set_bit ( map2, 1235 );
  ebitmap_clear_bit ( map1, 1235 );
  ebitmap_set_bit ( map2, 1236 );
  ebitmap_clear_bit ( map1, 1236 );
  ebitmap_set_bit ( map2, 1237 );
  ebitmap_clear_bit ( map1, 1237 );
  ebitmap_set_bit ( map2, 1238 );
  ebitmap_clear_bit ( map1, 1238 );
  ebitmap_set_bit ( map2, 1239 );
  ebitmap_clear_bit ( map1, 1239 );
  ebitmap_set_bit ( map2, 1240 );
  ebitmap_clear_bit ( map1, 1240 );
  ebitmap_set_bit ( map2, 1245 );
  ebitmap_clear_bit ( map1, 1245 );
  ebitmap_set_bit ( map2, 1246 );
  ebitmap_clear_bit ( map1, 1246 );
  ebitmap_set_bit ( map2, 1247 );
  ebitmap_clear_bit ( map1, 1247 );
  ebitmap_set_bit ( map2, 1248 );
  ebitmap_clear_bit ( map1, 1248 );
  ebitmap_set_bit ( map2, 1249 );
  ebitmap_clear_bit ( map1, 1249 );
  ebitmap_set_bit ( map2, 1250 );
  ebitmap_clear_bit ( map1, 1250 );
  ebitmap_set_bit ( map2, 1251 );
  ebitmap_clear_bit ( map1, 1251 );

  if ( !ebitmap_bit_p(map2,1252) )
    {
      if ( ebitmap_bit_p(map1,1252) )
        {
          ebitmap_set_bit ( map2, 1252 );
          ebitmap_clear_bit ( map1, 1252 );
        }
    }

  gcc_assert ( !ebitmap_bit_p(map1,1253) );

  fprintf ( stderr, "ebitmap_clear_bit() test passed\n" );
}