List:Commits« Previous MessageNext Message »
From:Jon Olav Hauglid Date:January 14 2011 2:06pm
Subject:bzr commit into mysql-5.5 branch (jon.hauglid:3244) Bug#43152
View as plain text  
#At file:///export/home/x/mysql-5.5-bug43152/ based on revid:georgi.kodinov@stripped

 3244 Jon Olav Hauglid	2011-01-14
      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. Even if these
      functions have read-only schematics and have const bitmaps as
      parameters, 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
      the last word. Some used bitwise AND and some used bitwise OR.
      This meant that if a function first used bitwise AND and another
      function then used bitwise OR before the first function tested
      the result, the result would be invalid.
      
      This patch fixes the problem by changing the implementation of
      8 bitmap functions that modified the bitmap state even if the 
      bitmap was declared const. These functions now preserves 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 reactivates the built-in test of my_bitmap.
      
      No 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.

    modified:
      .bzrignore
      include/my_bit.h
      mysys/CMakeLists.txt
      mysys/my_bitmap.c
=== modified file '.bzrignore'
--- a/.bzrignore	2010-12-17 11:11:34 +0000
+++ b/.bzrignore	2011-01-14 14:06:36 +0000
@@ -3115,4 +3115,5 @@ libmysqld/mysqlserver_depends.c
 libmysqld/examples/mysql_embedded
 sql/.empty
 mysys/thr_lock
+mysys/my_bitmap
 VERSION.dep

=== modified file 'include/my_bit.h'
--- a/include/my_bit.h	2010-07-23 20:18:36 +0000
+++ b/include/my_bit.h	2011-01-14 14:06:36 +0000
@@ -49,6 +49,13 @@ static inline uint my_count_bits_ushort(
   return _my_bits_nbits[v];
 }
 
+static inline uint my_count_bits_uint32(uint32 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)]);
+}
 
 /*
   Next highest power of two

=== modified file 'mysys/CMakeLists.txt'
--- a/mysys/CMakeLists.txt	2010-08-12 15:19:57 +0000
+++ b/mysys/CMakeLists.txt	2011-01-14 14:06:36 +0000
@@ -77,3 +77,7 @@ DTRACE_INSTRUMENT(mysys)
 ADD_EXECUTABLE(thr_lock thr_lock.c)
 TARGET_LINK_LIBRARIES(thr_lock mysys)
 SET_TARGET_PROPERTIES(thr_lock PROPERTIES COMPILE_FLAGS "-DMAIN")
+
+ADD_EXECUTABLE(my_bitmap my_bitmap.c)
+TARGET_LINK_LIBRARIES(my_bitmap mysys)
+SET_TARGET_PROPERTIES(my_bitmap PROPERTIES COMPILE_FLAGS "-DMAIN")

=== modified file 'mysys/my_bitmap.c'
--- a/mysys/my_bitmap.c	2011-01-11 09:07:37 +0000
+++ b/mysys/my_bitmap.c	2011-01-14 14:06:36 +0000
@@ -259,39 +259,42 @@ 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; 
+  my_bitmap_map prefix_bits= prefix_size & 0x7FFF;
+  my_bitmap_map *data_ptr= map->bitmap;
+  my_bitmap_map *end_prefix= data_ptr+prefix_size/32;
+  DBUG_ASSERT(data_ptr && prefix_size <= map->n_bits);
+
+  for (; data_ptr < end_prefix; data_ptr++)
+    if (*data_ptr != 0xFFFFFFFF)
+      return FALSE;
+
+  if (prefix_bits)
+  {
+    my_bitmap_map word= *data_ptr;
+    if (data_ptr++ == map->last_word_ptr)
+      word &= ~map->last_word_mask;
+    if (word != (my_bitmap_map)((1 << prefix_bits)-1))
+      return FALSE;
+  }
+
+  for (; data_ptr < map->last_word_ptr; data_ptr++)
+    if (*data_ptr != 0)
+      return FALSE;
+  if (data_ptr == map->last_word_ptr &&
+      (*map->last_word_ptr & ~map->last_word_mask) != 0)
+    return FALSE;
+  return TRUE;
 }
 
 
 my_bool bitmap_is_set_all(const MY_BITMAP *map)
 {
   my_bitmap_map *data_ptr= map->bitmap;
-  my_bitmap_map *end= map->last_word_ptr;
-  *map->last_word_ptr |= map->last_word_mask;
-  for (; data_ptr <= end; data_ptr++)
+  for (; data_ptr < map->last_word_ptr; data_ptr++)
     if (*data_ptr != 0xFFFFFFFF)
       return FALSE;
+  if ((*map->last_word_ptr | map->last_word_mask) != 0xFFFFFFFF)
+    return FALSE;
   return TRUE;
 }
 
@@ -313,40 +316,44 @@ my_bool bitmap_is_clear_all(const MY_BIT
 
 my_bool bitmap_is_subset(const MY_BITMAP *map1, const MY_BITMAP *map2)
 {
-  my_bitmap_map *m1= map1->bitmap, *m2= map2->bitmap, *end;
+  my_bitmap_map *m1= map1->bitmap, *m2= map2->bitmap;
 
   DBUG_ASSERT(map1->bitmap && map2->bitmap &&
               map1->n_bits==map2->n_bits);
 
-  end= map1->last_word_ptr;
-  *map1->last_word_ptr &= ~map1->last_word_mask;
-  *map2->last_word_ptr &= ~map2->last_word_mask;
-  while (m1 <= end)
+  while (m1 < map1->last_word_ptr)
   {
     if ((*m1++) & ~(*m2++))
-      return 0;
+      return FALSE;
   }
-  return 1;
+
+  if ((*map1->last_word_ptr & ~map1->last_word_mask) &
+      ~(*map2->last_word_ptr & ~map2->last_word_mask))
+    return FALSE;
+
+  return TRUE;
 }
 
 /* True if bitmaps has any common bits */
 
 my_bool bitmap_is_overlapping(const MY_BITMAP *map1, const MY_BITMAP *map2)
 {
-  my_bitmap_map *m1= map1->bitmap, *m2= map2->bitmap, *end;
+  my_bitmap_map *m1= map1->bitmap, *m2= map2->bitmap;
 
   DBUG_ASSERT(map1->bitmap && map2->bitmap &&
               map1->n_bits==map2->n_bits);
 
-  end= map1->last_word_ptr;
-  *map1->last_word_ptr &= ~map1->last_word_mask;
-  *map2->last_word_ptr &= ~map2->last_word_mask;
-  while (m1 <= end)
+  while (m1 < map1->last_word_ptr)
   {
     if ((*m1++) & (*m2++))
-      return 1;
+      return TRUE;
   }
-  return 0;
+
+  if ((*map1->last_word_ptr & ~map1->last_word_mask) &
+      (*map2->last_word_ptr & ~map2->last_word_mask))
+    return TRUE;
+
+  return FALSE;
 }
 
 
@@ -358,9 +365,13 @@ void bitmap_intersect(MY_BITMAP *map, co
   DBUG_ASSERT(map->bitmap && map2->bitmap);
 
   end= to+min(len,len2);
-  *map2->last_word_ptr&= ~map2->last_word_mask; /*Clear last bits in map2*/
   while (to < end)
-    *to++ &= *from++;
+  {
+    if (from == map2->last_word_ptr)
+      *to++ &= (*from & ~map2->last_word_mask); /*Clear last bits in map2*/
+    else
+      *to++ &= *from++;
+  }
 
   if (len2 < len)
   {
@@ -451,15 +462,15 @@ void bitmap_invert(MY_BITMAP *map)
 
 
 uint bitmap_bits_set(const MY_BITMAP *map)
-{  
-  uchar *m= (uchar*)map->bitmap;
-  uchar *end= m + no_bytes_in_map(map);
+{
+  my_bitmap_map *data_ptr= map->bitmap;
   uint res= 0;
 
   DBUG_ASSERT(map->bitmap);
-  *map->last_word_ptr&= ~map->last_word_mask; /*Reset last bits to zero*/
-  while (m < end)
-    res+= my_count_bits_ushort(*m++);
+  while (data_ptr < map->last_word_ptr)
+    res+= my_count_bits_uint32(*data_ptr++);
+  /*Reset last bits to zero*/
+  res+= my_count_bits_uint32(*map->last_word_ptr & ~map->last_word_mask);
   return res;
 }
 
@@ -479,26 +490,29 @@ 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, last_word;
 
   DBUG_ASSERT(map->bitmap);
   data_ptr= map->bitmap;
-  *map->last_word_ptr &= ~map->last_word_mask;
+  last_word= *map->last_word_ptr & ~map->last_word_mask;
 
-  for (i=0; data_ptr <= end; data_ptr++, i++)
+  for (word_pos=0; data_ptr <= map->last_word_ptr; data_ptr++, word_pos++)
   {
     if (*data_ptr)
     {
-      byte_ptr= (uchar*)data_ptr;
-      for (j=0; ; j++, byte_ptr++)
+      if (data_ptr == map->last_word_ptr)
+        byte_ptr= (uchar*)&last_word;
+      else
+        byte_ptr= (uchar*)data_ptr;
+      for (byte_pos=0; ; byte_pos++, byte_ptr++)
       {
         if (*byte_ptr)
         {
-          for (k=0; ; k++)
+          for (bit_pos=0; ; 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;
           }
         }
       }
@@ -511,26 +525,29 @@ 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, last_word;
 
   DBUG_ASSERT(map->bitmap);
   data_ptr= map->bitmap;
-  *map->last_word_ptr|= map->last_word_mask;
+  last_word= *map->last_word_ptr | map->last_word_mask;
 
-  for (i=0; data_ptr <= end; data_ptr++, i++)
+  for (word_pos=0; data_ptr <= map->last_word_ptr; data_ptr++, word_pos++)
   {
     if (*data_ptr != 0xFFFFFFFF)
     {
-      byte_ptr= (uchar*)data_ptr;
-      for (j=0; ; j++, byte_ptr++)
+      if (data_ptr == map->last_word_ptr)
+        byte_ptr= (uchar*)&last_word;
+      else
+        byte_ptr= (uchar*)data_ptr;
+      for (byte_pos=0; ; byte_pos++, byte_ptr++)
       {
         if (*byte_ptr != 0xFF)
         {
-          for (k=0; ; k++)
+          for (bit_pos=0; ; 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;
           }
         }
       }
@@ -565,7 +582,7 @@ uint get_rand_bit(uint bitsize)
   return (rand() % bitsize);
 }
 
-bool test_set_get_clear_bit(MY_BITMAP *map, uint bitsize)
+my_bool test_set_get_clear_bit(MY_BITMAP *map, uint bitsize)
 {
   uint i, test_bit;
   uint no_loops= bitsize > 128 ? 128 : bitsize;
@@ -588,7 +605,7 @@ error2:
   return TRUE;
 }
 
-bool test_flip_bit(MY_BITMAP *map, uint bitsize)
+my_bool test_flip_bit(MY_BITMAP *map, uint bitsize)
 {
   uint i, test_bit;
   uint no_loops= bitsize > 128 ? 128 : bitsize;
@@ -611,13 +628,13 @@ error2:
   return TRUE;
 }
 
-bool test_operators(MY_BITMAP *map __attribute__((unused)),
+my_bool test_operators(MY_BITMAP *map __attribute__((unused)),
                     uint bitsize __attribute__((unused)))
 {
   return FALSE;
 }
 
-bool test_get_all_bits(MY_BITMAP *map, uint bitsize)
+my_bool test_get_all_bits(MY_BITMAP *map, uint bitsize)
 {
   uint i;
   bitmap_set_all(map);
@@ -659,7 +676,7 @@ error6:
   return TRUE;
 }
 
-bool test_compare_operators(MY_BITMAP *map, uint bitsize)
+my_bool test_compare_operators(MY_BITMAP *map, uint bitsize)
 {
   uint i, j, test_bit1, test_bit2, test_bit3,test_bit4;
   uint no_loops= bitsize > 128 ? 128 : bitsize;
@@ -765,7 +782,7 @@ error5:
   return TRUE;
 }
 
-bool test_count_bits_set(MY_BITMAP *map, uint bitsize)
+my_bool test_count_bits_set(MY_BITMAP *map, uint bitsize)
 {
   uint i, bit_count=0, test_bit;
   uint no_loops= bitsize > 128 ? 128 : bitsize;
@@ -791,7 +808,7 @@ error2:
   return TRUE;
 }
 
-bool test_get_first_bit(MY_BITMAP *map, uint bitsize)
+my_bool test_get_first_bit(MY_BITMAP *map, uint bitsize)
 {
   uint i, test_bit;
   uint no_loops= bitsize > 128 ? 128 : bitsize;
@@ -816,7 +833,7 @@ error2:
   return TRUE;
 }
 
-bool test_get_next_bit(MY_BITMAP *map, uint bitsize)
+my_bool test_get_next_bit(MY_BITMAP *map, uint bitsize)
 {
   uint i, j, test_bit;
   uint no_loops= bitsize > 128 ? 128 : bitsize;
@@ -835,7 +852,7 @@ error1:
   return TRUE;
 }
 
-bool test_prefix(MY_BITMAP *map, uint bitsize)
+my_bool test_prefix(MY_BITMAP *map, uint bitsize)
 {
   uint i, j, test_bit;
   uint no_loops= bitsize > 128 ? 128 : bitsize;
@@ -870,7 +887,7 @@ error3:
 }
 
 
-bool do_test(uint bitsize)
+my_bool do_test(uint bitsize)
 {
   MY_BITMAP map;
   my_bitmap_map buf[1024];


Attachment: [text/bzr-bundle] bzr/jon.hauglid@oracle.com-20110114140636-gwhngoxj76o9nyfq.bundle
Thread
bzr commit into mysql-5.5 branch (jon.hauglid:3244) Bug#43152Jon Olav Hauglid14 Jan