List:Falcon Storage Engine« Previous MessageNext Message »
From:Kevin Lewis Date:October 14 2008 11:41pm
Subject:Re: Bug in Bitmap
View as plain text  
Jim,

I tested your fix and it works.  Now I am going to spend a little time 
figuring out why! :)  And then I will check it in with the little unit 
test I made that runs when you do "set global falcon_debug_trace=64;"

Just a comment on unit tests.  This is indeed an edge case and most 
likely would not have been found by just HAVING a unit test.  It had to 
be the right kind of bitmap access, a method only used in 
Table::retireRecords();  (Chris did some re-working of the scavenger 
last year and may be the clever bloak that tried it this way, he can 
confirm or deny it).  And the test also had to cross the 1024 bit 
boundary.  So there is a very good chance that a unit test would not 
have discovered this.  However, I now have a test embedded in the code 
that includes several scenarios and can be expanded in the future.  It 
can also catch regressions.  And it could be hooked into the unit test 
harness that Hakan was working with.  (Hakan, you are welcome to try 
it.  Look for Bitmap::unitTest() once I check it in).

Kevin

Jim Starkey wrote:
> Last week Kevin claimed he saw a bug in Bitmap.cpp.  He did, but his 
> description missed the edge case.  This raises two questions.  One is 
> what was the bug.  The other is why it went undiscovered for so long.
>
> The actual bug is in Bitmap::nextSet.  The bitmap is actually a fixed 
> width, variable depth free of bitmap segments, each containing 32 
> words of 32 bit.  The operating starts by decomposing the start bit 
> number into a vector of indexes, where index[0] is the bit number, 
> index[1] is clump (i.e. word) number, index[2] is the slot into a 
> first level vector of bitmap segments pointers, etc.  The bug is 
> around line 247:
>
>                for (index = indexes[lvl]; index < BITMAP_VECTOR_SIZE &&
>    !vec [index]; ++index)
>                    ;
>
> where the method is looking for a non-null pointer to a bitmap 
> segment.  In specific, the bug is the failure to reset the bit number 
> and clump number to zero before checking the next bitmap segment.  The 
> code should have been something like:
>
>                for (index = indexes[lvl]; index < BITMAP_VECTOR_SIZE &&
>    !vec [index]; ++index)
>                    for (int n = 0; n < lvl; ++n)
>                        indexes[n] = 0;
>
> The reason why this ugliness hasn't reared it head in the past is a 
> slight different in bitmap searching code.  Other code has typically 
> been of the form:
>
>    for (int n = 0; (n = bitmap->nextSet(n)) >= 0; ++n)
>        yada yada yada
>
> where next bit number of bumped to avoid a wasted nano-second skipped 
> over an already processed number (also to avoid infinite loop in the 
> non-destructive case).  Chris, I believe, code his loop something like:
>
>    for (int n = 0; (n = bitmap->nextSet(n)) >= 0;)
>        ...
>        bitmap->clear(n);
>
> Now, if Chris had done a minisculy more efficient coding and / or 
> Kevin had been less diligent in running bugs to earth, we wouldn't 
> have caught this.
>
> So, Kevin 1, Chris 1, Jim 0.
>
> (Kevin, can I drop this on you?)
>
Thread
Bug in BitmapJim Starkey14 Oct
  • Re: Bug in BitmapKevin Lewis15 Oct
  • Re: Bug in BitmapChristopher Powers17 Oct