List:Commits« Previous MessageNext Message »
From:Dmitry Lenev Date:February 11 2011 7:05am
Subject:Re: bzr commit into mysql-5.5 branch (jon.hauglid:3321) Bug#43152
View as plain text  
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
Thread
bzr commit into mysql-5.5 branch (jon.hauglid:3321) Bug#43152Jon Olav Hauglid10 Feb
  • Re: bzr commit into mysql-5.5 branch (jon.hauglid:3321) Bug#43152Dmitry Lenev11 Feb