From: Christopher Powers
Date: October 14 2008 9:35pm
Subject: Re: Bug in Bitmap
List-Archive: http://lists.mysql.com/falcon/51
Message-Id: <48F510A4.6080805@sun.com>
MIME-Version: 1.0
Content-Type: text/plain; format=flowed; charset=ISO-8859-1
Content-Transfer-Encoding: 7BIT

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);

I remember this! It seemed a bit 'spendy' to manually clear each bitmap. 
I should've challenged the design.

Don't we need a destructive *and* non-desctructive nextSet()?


> 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?)
>