Hello Jon Olav!
Here are my comments about your patch:
* Jon Olav Hauglid <jon.hauglid@stripped> [11/02/10 13:44]:
> #At file:///home/jh234568/repo/mysql-5.5/ based on
> revid:georgi.kodinov@stripped
>
> 3321 Jon Olav Hauglid 2011-02-10
> Bug #43152 Assertion `bitmap_is_set_all(&table->s->all_set)'
> failed in handler::ha_reset
>
> This assertion could be triggered if two connections simultaneously
> executed two bitmap test functions on the same bitmap. For example,
> the assertion could be triggered if one connection executed UPDATE
> while a second connection executed SELECT on the same table.
>
> Even if bitmap test functions have read-only schematics and have
^^^^^^^^^^
Probably a typo: semantics?
> const bitmaps as parameter, several of them modified the internal
> state of the bitmap. With interleaved execution of two such functions
> it was possible for one function to modify the state of the same
> bitmap that the other function had just modified. This lead to an
> inconsistent state and could trigger the assert.
>
> Internally the bitmap uses 32 bit words for storage. Since bitmaps
> can contain any number of bits, the last word in the bitmap may
> not be fully used. A 32 bit mask is maintained where a bit is set
> if the corresponding bit in the last bitmap word is unused.
> The problem was that several test functions applies this mask to
^^^^^^^
Same here: applied?
> the last word. Sometimes the mask wass negated and used to zero out
^^^^
Another typo: was?
> the remainder of the last word and sometimes the mask wass used as-is
^^^^
Same here: was?
> to fill the remainder of the last word with 1's. This meant that if
> a function first used the negated mask and another function then
> used the mask as-is (or vice-versa), the first function would then
> get the wrong result.
>
> This patch fixes the problem by changing the implementation of
> 9 bitmap functions that modified the bitmap state even if the
> bitmap was declared const. These functions now preserve the
> internal state of the bitmap. This makes it possible for
> two connections to concurrently execute two of these functions
> on the same bitmap without issues.
>
> The patch also removes dead testing code from my_bitmap.c.
> These tests have already been moved to unittest/mysys/bitmap-t.c.
> Existing test coverage of my_bitmap has been extended.
>
> No MTR test case added as this would require adding several sync
> points to the bitmap functions. The patch has been tested with
> a non-deterministic test case posted on the bug report.
Otherwise this comment looks really nice!
> === modified file 'include/my_bit.h'
> --- a/include/my_bit.h 2010-07-23 20:18:36 +0000
> +++ b/include/my_bit.h 2011-02-10 10:35:57 +0000
> @@ -44,9 +44,12 @@ static inline uint my_count_bits(ulonglo
> #endif
> }
>
> -static inline uint my_count_bits_ushort(ushort v)
> +static inline uint my_count_bits_uint32(uint32 v)
> {
> - return _my_bits_nbits[v];
> + return (uint) (uchar) (_my_bits_nbits[(uchar) v] +
> + _my_bits_nbits[(uchar) (v >> 8)] +
> + _my_bits_nbits[(uchar) (v >> 16)] +
> + _my_bits_nbits[(uchar) (v >> 24)]);
> }
>
AFAIU a comment with copyright notice should be added to this file.
...
> === modified file 'mysys/my_bitmap.c'
> --- a/mysys/my_bitmap.c 2011-01-11 09:07:37 +0000
> +++ b/mysys/my_bitmap.c 2011-02-10 10:35:57 +0000
> @@ -1,4 +1,4 @@
> -/* Copyright (C) 2000 MySQL AB, 2008-2009 Sun Microsystems, Inc
> +/* Copyright (c) 2000, 2011, Oracle and/or its affiliates. All rights reserved.
>
> This program is free software; you can redistribute it and/or modify
> it under the terms of the GNU General Public License as published by
> @@ -259,28 +259,49 @@ void bitmap_set_prefix(MY_BITMAP *map, u
>
> my_bool bitmap_is_prefix(const MY_BITMAP *map, uint prefix_size)
> {
> - uint prefix_bits= prefix_size & 0x7, res;
> - uchar *m= (uchar*)map->bitmap;
> - uchar *end_prefix= m+prefix_size/8;
> - uchar *end;
> - DBUG_ASSERT(m && prefix_size <= map->n_bits);
> - end= m+no_bytes_in_map(map);
> -
> - while (m < end_prefix)
> - if (*m++ != 0xff)
> - return 0;
> -
> - *map->last_word_ptr&= ~map->last_word_mask; /*Clear bits*/
> - res= 0;
> - if (prefix_bits && *m++ != (1 << prefix_bits)-1)
> - goto ret;
> -
> - while (m < end)
> - if (*m++ != 0)
> - goto ret;
> - res= 1;
> -ret:
> - return res;
> + uint prefix_bits= prefix_size % 8, byte_pos, prefix_bytes;
> + my_bitmap_map *word_ptr= map->bitmap, last_word;
> + my_bitmap_map *end_prefix= word_ptr + prefix_size / 32;
> + uchar *byte_ptr;
> + DBUG_ASSERT(word_ptr && prefix_size <= map->n_bits);
> +
> + // 1: Words that should be filled with 1
> + while (word_ptr < end_prefix)
> + if (*word_ptr++ != 0xFFFFFFFF)
> + return FALSE;
> +
> + // 2: Word which contains the end of the prefix (if any)
> + last_word= *map->last_word_ptr & ~map->last_word_mask;
I find the above two lines a bit confusing as they might give a
false impression that last_word always contains enf of the prefix...
Maybe it makes sense to swap them or emphasize in some other way
that this comment is not really related to last_word?
Also note that according to our coding style we should use /* ... */
for one-line comments in C files.
> + if (prefix_size % 32)
> + {
> + prefix_bytes= (prefix_size - 32 * (prefix_size / 32)) / 8;
IMO something like:
prefix_bytes= (prefix_size % 32) / 8;
looks a bit more clear (and probably easier to optimize).
> + byte_ptr= (uchar*)word_ptr;
> + if (word_ptr == map->last_word_ptr)
> + byte_ptr= (uchar*)&last_word;
Maybe it makes sense to replace the above three lines with something
like:
if (word_ptr == map->last_word_ptr)
byte_ptr= (uchar*)&last_word;
else
byte_ptr= (uchar*)word_ptr;
?
> + for (byte_pos= 0; byte_pos < prefix_bytes; byte_ptr++, byte_pos++)
> + if (*byte_ptr != 0xFF)
> + return FALSE;
> + if (prefix_bits)
> + {
> + if (*byte_ptr++ != (1 << prefix_bits)-1)
> + return FALSE;
> + byte_pos++;
> + }
> + for (; byte_pos < 4; byte_ptr++, byte_pos++)
> + if (*byte_ptr != 0)
> + return FALSE;
> + word_ptr++;
> + }
> +
> + // 3: Words that should be filled with 0
> + while (word_ptr < map->last_word_ptr)
> + if (*word_ptr++ != 0)
> + return FALSE;
> +
> + if (word_ptr == map->last_word_ptr && last_word != 0)
> + return FALSE;
IMO it makes sense to add comment for the above if-statement that will
clarify that word_ptr == mast->last_word_ptr condition will also filter
out cases when last_word contains end of the prefix.
> +
> + return TRUE;
> }
Sigh... I wonder if there is some nicer way to implement step #2 in
this function? Maybe by doing something like:
uint prefix_bits= prefix_size % 32;
...
if (prefix_bits)
{
if (word_ptr == map->last_word_ptr)
byte_ptr= (uchar*)&last_word;
else
byte_ptr= (uchar*)word_ptr;
if (uint4korr(byte_ptr) != (1 << prefix_bits) - 1)
return FALSE;
word_ptr++;
}
?
Although I am not of very happy with this version either...
What do you think?
...
> @@ -479,31 +510,44 @@ void bitmap_copy(MY_BITMAP *map, const M
> uint bitmap_get_first_set(const MY_BITMAP *map)
> {
> uchar *byte_ptr;
> - uint i,j,k;
> - my_bitmap_map *data_ptr, *end= map->last_word_ptr;
> + uint word_pos, byte_pos, bit_pos;
> + my_bitmap_map *data_ptr, *end= map->last_word_ptr, last_word;
>
> DBUG_ASSERT(map->bitmap);
> data_ptr= map->bitmap;
> - *map->last_word_ptr &= ~map->last_word_mask;
>
> - for (i=0; data_ptr <= end; data_ptr++, i++)
> + for (word_pos=0; data_ptr < end; data_ptr++, word_pos++)
> {
> if (*data_ptr)
> {
> byte_ptr= (uchar*)data_ptr;
> - for (j=0; ; j++, byte_ptr++)
> + for (byte_pos=0; byte_pos < 4; byte_ptr++, byte_pos++)
> {
> if (*byte_ptr)
> {
> - for (k=0; ; k++)
> + for (bit_pos=0; bit_pos < 8; bit_pos++)
> {
> - if (*byte_ptr & (1 << k))
> - return (i*32) + (j*8) + k;
> + if (*byte_ptr & (1 << bit_pos))
> + return (word_pos*32) + (byte_pos*8) + bit_pos;
> }
> }
> }
> }
> }
> + last_word= *map->last_word_ptr & ~map->last_word_mask;
> + byte_ptr= (uchar*)&last_word;
> + for (byte_pos=0; byte_pos < 4; byte_ptr++, byte_pos++)
> + {
> + if (*byte_ptr)
> + {
> + for (bit_pos=0; bit_pos < 8; bit_pos++)
> + {
> + if (*byte_ptr & (1 << bit_pos))
> + return (word_pos*32) + (byte_pos*8) + bit_pos;
> + }
> + }
> + }
> +
> return MY_BIT_NONE;
> }
Maybe it makes to move common code iterating through the bytes to a
static inline function? Something like:
uint get_first_set(uint32 value, uint word_pos_to_add);
?
>
> @@ -511,31 +555,44 @@ uint bitmap_get_first_set(const MY_BITMA
> uint bitmap_get_first(const MY_BITMAP *map)
> {
> uchar *byte_ptr;
> - uint i,j,k;
> - my_bitmap_map *data_ptr, *end= map->last_word_ptr;
> + uint word_pos, byte_pos, bit_pos;
> + my_bitmap_map *data_ptr, *end= map->last_word_ptr, last_word;
>
> DBUG_ASSERT(map->bitmap);
> data_ptr= map->bitmap;
> - *map->last_word_ptr|= map->last_word_mask;
>
> - for (i=0; data_ptr <= end; data_ptr++, i++)
> + for (word_pos=0; data_ptr < end; data_ptr++, word_pos++)
> {
> if (*data_ptr != 0xFFFFFFFF)
> {
> byte_ptr= (uchar*)data_ptr;
> - for (j=0; ; j++, byte_ptr++)
> + for (byte_pos=0; byte_pos < 4; byte_ptr++, byte_pos++)
> {
> if (*byte_ptr != 0xFF)
> {
> - for (k=0; ; k++)
> + for (bit_pos=0; bit_pos < 8; bit_pos++)
> {
> - if (!(*byte_ptr & (1 << k)))
> - return (i*32) + (j*8) + k;
> + if (!(*byte_ptr & (1 << bit_pos)))
> + return (word_pos*32) + (byte_pos*8) + bit_pos;
> }
> }
> }
> }
> }
> + last_word= *map->last_word_ptr | map->last_word_mask;
> + byte_ptr= (uchar*)&last_word;
> + for (byte_pos=0; byte_pos < 4; byte_ptr++, byte_pos++)
> + {
> + if (*byte_ptr != 0xFF)
> + {
> + for (bit_pos=0; bit_pos < 8; bit_pos++)
> + {
> + if (!(*byte_ptr & (1 << bit_pos)))
> + return (word_pos*32) + (byte_pos*8) + bit_pos;
> + }
> + }
> + }
> +
> return MY_BIT_NONE;
> }
>
Same question about static inline here...
...
Otherwise I am OK with your patch and think that it can be pushed
after addressing/discussing the above issues and approval from the
second reviewer.
Thanks a lot for working on this!!!
--
Dmitry Lenev, Software Developer
Oracle Development SPB/MySQL, www.mysql.com
Are you MySQL certified? http://www.mysql.com/certification
