List:Falcon Storage Engine« Previous MessageNext Message »
From:Jim Starkey Date:October 14 2008 9:17pm
Subject:Bug in Bitmap
View as plain text  
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;)

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 

So, Kevin 1, Chris 1, Jim 0.

(Kevin, can I drop this on you?)

Jim Starkey
President, NimbusDB, Inc.
978 526-1376

Bug in BitmapJim Starkey14 Oct
  • Re: Bug in BitmapKevin Lewis15 Oct
  • Re: Bug in BitmapChristopher Powers17 Oct