maria-developers team mailing list archive

[Vladislav Vaintroub <wlad@xxxxxxxxxxx>]

Hi Serg,

Thanks for looking

>> +public:
>>   uint32 buffer[(width+31)/32];
> Why is it public?

No reason, an oversight. Leftover from previous testing,
I fixed it.

> +  Bitmap():buffer()
zero initialization of member variable ,here of the type array (s https://stackoverflow.com/a/23987926/547065)
I removed it by replacing with clear_all(), so it is better understandable.

>I wonder whether init() method is still needed.
>You've removed it from the constructor. And if there's any other
>code that uses it, I'd rather it'd be using clear_all().

Done.

>> +  void set_all()
>> +  {
>> +    set_prefix(width);
>
>may be better to optimize it?
> memset(buffer, 0xff, sizeof(buffer) - 1);
> ((uchar*)buffer)[sizeof(buffer)-1] = last_byte_mask(width);

I’m not really convinced this would be an optimization 😊
My claim is that, since “width” is constant at compile time (128), and it is divisible by 32, any decent  C++ compiler must be able to figure out, at compile time, that set_all() == set_prefix(width)==set_prefix(128) trivially reduces to a shorter

  memset(buffer, 0xff, 32)

>> +  {
>> +    compile_time_assert(sizeof(ulonglong) == 8);
>> +    uint32 tmp[2];
>> +    int8store(tmp, map2buff);
>> +    if (array_elements(buffer) > 2 && pad_with_ones)
>> +      set_all();

>really? I'd expect that if pad_with_ones==true,
>you simply don't need to do anything to the
>rest of the buffer.

The original implementation does padding  with 0xff  or 0x00  , depending on the highest order bit of map2buff, with bitmap_set_above(). retained that property

>> +  bool is_set_all() const
>> +  {
>> +    if (width == sizeof(buffer) * 8)
>> +    {
>> +      for (size_t i = 0; i < array_elements(buffer); i++)
>> +        if (buffer[i] != 0xFFFFFFFFU)
>> +          return false;
>> +      return true;
>> +    }
>> +    else
>> +      return is_prefix(width);
>
>this can also be optimized to not use complex is_prefix(),
>but I don't think is_set_all() is used as often as set_all(), so it
>shouldn't matter as much.

In fact, it is optimized 😊
If this condition    if (width == sizeof(buffer) * 8) us true, s optimized version is used. This condition can be evaluated at compile time, and is true for width which is divisible by 32. the code for is_prefix should not be even generated by the compile

Thanks again for looking,
Wlad

From: Sergei Golubchik<mailto:serg@xxxxxxxxxxx>
Sent: Wednesday, 8 May 2019 22:49
Subject: Re: a4be420c920: MDEV-19235 MariaDB Server compiled for 128 Indexes crashes at startup

Hi, Vladislav!

Thanks. That's pretty much the solution I had in mind too :)

A couple of comments on details below.

I've only commented on sql_bitmap.h, everything else is fine.

On May 08, Vladislav Vaintroub wrote:
> revision-id: a4be420c920 (mariadb-10.4.4-25-ga4be420c920)
> parent(s): ee4a2fef181
> author: Vladislav Vaintroub <wlad@xxxxxxxxxxx>
> committer: Vladislav Vaintroub <wlad@xxxxxxxxxxx>
> timestamp: 2019-04-17 17:17:06 +0100
> message:
>
> MDEV-19235 MariaDB Server compiled for 128 Indexes crashes at startup
>
> With MAX_INDEXIES=64(default), key_map=Bitmap<64> is just a wrapper around
> ulonglong and thus "trivial" (can be bzero-ed, or memcpy-ed, and stays
> valid still)
>
> With MAX_INDEXES=128, key_map = Bitmap<128> is not a "trivial" type
> anymore. The implementation uses MY_BITMAP, and MY_BITMAP contains pointers
> which make Bitmap invalid, when it is memcpy-ed/bzero-ed.
>
> The problem in 10.4 is that there are many new key_map members, inside TABLE
> or KEY, and those are often memcopied and bzeroed
>
> The fix makes Bitmap "trivial", by inlining most of MY_BITMAP functionality.
> pointers/heap allocations are not used anymore.


> diff --git a/sql/sql_bitmap.h b/sql/sql_bitmap.h
> index 705a8d169e1..74866336a1a 100644
> --- a/sql/sql_bitmap.h
> +++ b/sql/sql_bitmap.h
> @@ -25,73 +25,184 @@
>
>  #include <my_sys.h>
>  #include <my_bitmap.h>
> +#include <my_bit.h>
>
>  template <uint width> class Bitmap
>  {
> -  MY_BITMAP map;
> +public:
>    uint32 buffer[(width+31)/32];

Why is it public?

>  public:
> -  Bitmap() { init(); }
> +  Bitmap():buffer()

What does that do?

> +  {
> +  }
> -  Bitmap(const Bitmap& from) { *this=from; }
> -  explicit Bitmap(uint prefix_to_set) { init(prefix_to_set); }
> +  explicit Bitmap(uint prefix_to_set):buffer()
> +  {
> +    set_prefix(prefix_to_set);
> +  }
> -  void init() { my_bitmap_init(&map, buffer, width, 0); }
> -  void init(uint prefix_to_set) { init(); set_prefix(prefix_to_set); }
>    uint length() const { return width; }
> -  Bitmap& operator=(const Bitmap& map2)
> -  {
> +  void init()
> +  {
> +    clear_all();
> +  }
> +  void init(uint prefix_to_set)
> +  {
>      init();
> -    memcpy(buffer, map2.buffer, sizeof(buffer));
> -    return *this;
> +    set_prefix(prefix_to_set);

I wonder whether init() method is still needed.
You've removed it from the constructor. And if there's any other
code that uses it, I'd rather it'd be using clear_all().

>    }
> -  void set_bit(uint n) { bitmap_set_bit(&map, n); }
> +  void set_bit(uint n)
> +  {
> +    DBUG_ASSERT(n < width);
> +    ((uchar*)buffer)[n / 8] |= (1 << (n & 7));
> +  }
> -  void clear_bit(uint n) { bitmap_clear_bit(&map, n); }
> +  void clear_bit(uint n)
> +  {
> +    DBUG_ASSERT(n < width);
> +    ((uchar*)buffer)[n / 8] &= ~(1 << (n & 7));
> +  }
> -  void set_prefix(uint n) { bitmap_set_prefix(&map, n); }
> +  void set_prefix(uint prefix_size)
> +  {
> +    set_if_smaller(prefix_size, width);
> +    uint prefix_bytes, prefix_bits, d;
> +    uchar* m = (uchar*)buffer;
> +
> +    if ((prefix_bytes = prefix_size / 8))
> +      memset(m, 0xff, prefix_bytes);
> +    m += prefix_bytes;
> +    if ((prefix_bits = prefix_size & 7))
> +    {
> +      *(m++) = (1 << prefix_bits) - 1;
> +      // As the prefix bits are set, lets count this byte too as a prefix byte.
> +      prefix_bytes++;
> +    }
> +    if ((d = (width + 7) / 8 - prefix_bytes))
> +      memset(m, 0, d);
> +  }
> -  void set_all() { bitmap_set_all(&map); }
> +  void set_all()
> +  {
> +    set_prefix(width);

may be better to optimize it?

  memset(buffer, 0xff, sizeof(buffer) - 1);
  ((uchar*)buffer)[sizeof(buffer)-1] = last_byte_mask(width);

> +  }
> -  void clear_all() { bitmap_clear_all(&map); }
> +  void clear_all()
> +  {
> +    memset(buffer, 0x00, sizeof(buffer));
> +  }
> -  void intersect(Bitmap& map2) { bitmap_intersect(&map, &map2.map); }
> +  void intersect(Bitmap & map2)
> +  {
> +    for (uint i = 0; i < array_elements(buffer); i++)
> +      buffer[i] &= map2.buffer[i];
> +  }
> -  void intersect(ulonglong map2buff)
> -  {
> -    // Use a spearate temporary buffer, as bitmap_init() clears all the bits.
> -    ulonglong buf2;
> -    MY_BITMAP map2;
> -
> -    my_bitmap_init(&map2, (uint32 *) &buf2, sizeof(ulonglong) * 8, 0);
> -
> -    // Store the original bits.
> -    if (sizeof(ulonglong) >= 8)
> -    {
> -      int8store(const_cast<uchar *>(static_cast<uchar *>
> -                                    (static_cast<void *>(&buf2))),
> -                map2buff);
> -    }
> -    else
> -    {
> -      DBUG_ASSERT(sizeof(buffer) >= 4);
> -      int4store(const_cast<uchar *>(static_cast<uchar *>
> -                                    (static_cast<void *>(&buf2))),
> -                static_cast<uint32>(map2buff));
> -    }
> -    bitmap_intersect(&map, &map2);
> -  }
> +  void intersect_and_pad(ulonglong map2buff, bool pad_with_ones)

make it private?

> +  {
> +    compile_time_assert(sizeof(ulonglong) == 8);
> +    uint32 tmp[2];
> +    int8store(tmp, map2buff);
> +    if (array_elements(buffer) > 2 && pad_with_ones)
> +      set_all();

really? I'd expect that if pad_with_ones==true,
you simply don't need to do anything to the
rest of the buffer.

> +
> +    buffer[0] &= tmp[0];
> +    if (array_elements(buffer) > 1)
> +      buffer[1] &= tmp[1];
> +
> +    if (array_elements(buffer) > 2 && !pad_with_ones)
> +        memset((char*)buffer + 8, 0 , sizeof(buffer) - 8);
> +  }
> +  void intersect(ulonglong map2buff)
> +  {
> +    intersect_and_pad(map2buff, 0);
> +  }
>    /* Use highest bit for all bits above sizeof(ulonglong)*8. */
>    void intersect_extended(ulonglong map2buff)
>    {
> -    intersect(map2buff);
> -    if (map.n_bits > sizeof(ulonglong) * 8)
> -      bitmap_set_above(&map, sizeof(ulonglong),
> -                       MY_TEST(map2buff & (1LL << (sizeof(ulonglong) * 8 - 1))));
> +    intersect_and_pad(map2buff, (map2buff & (1ULL << 63)));
>    }
> -  void subtract(Bitmap& map2) { bitmap_subtract(&map, &map2.map); }
> +  void subtract(Bitmap & map2)
> +  {
> +    for (size_t i = 0; i < array_elements(buffer); i++)
> +      buffer[i] &= ~(map2.buffer[i]);
> +  }
> -  void merge(Bitmap& map2) { bitmap_union(&map, &map2.map); }
> +  void merge(Bitmap & map2)
> +  {
> +    for (size_t i = 0; i < array_elements(buffer); i++)
> +      buffer[i] |= map2.buffer[i];
> +  }
> -  bool is_set(uint n) const { return bitmap_is_set(&map, n); }
> +  bool is_set(uint n) const
> +  {
> +    DBUG_ASSERT(n < width);
> +    return ((uchar*)buffer)[n / 8] & (1 << (n & 7));
> +  }
> -  bool is_prefix(uint n) const { return bitmap_is_prefix(&map, n); }
> +  bool is_prefix(uint prefix_size) const
> +  {
> +    uint prefix_mask = last_byte_mask(prefix_size);
> +    uchar* m = (uchar*)buffer;
> +    uchar* end_prefix = m + (prefix_size - 1) / 8;
> +    uchar* end;
> +    DBUG_ASSERT(prefix_size <= width);
> +
> +    /* Empty prefix is always true */
> +    if (!prefix_size)
> +      return true;
> +
> +    while (m < end_prefix)
> +      if (*m++ != 0xff)
> +        return false;
> +
> +    end = ((uchar*)buffer) + (width + 7) / 8 - 1;
> +    if (m == end)
> +      return ((*m & last_byte_mask(width)) == prefix_mask);
> +
> +    if (*m != prefix_mask)
> +      return false;
> +
> +    while (++m < end)
> +      if (*m != 0)
> +        return false;
> +    return ((*m & last_byte_mask(width)) == 0);
> +  }
> -  bool is_clear_all() const { return bitmap_is_clear_all(&map); }
> +  bool is_clear_all() const
> +  {
> +    for (size_t i= 0; i < array_elements(buffer); i++)
> +      if (buffer[i])
> +        return false;
> +    return true;
> +  }
> -  bool is_set_all() const { return bitmap_is_set_all(&map); }
> +  bool is_set_all() const
> +  {
> +    if (width == sizeof(buffer) * 8)
> +    {
> +      for (size_t i = 0; i < array_elements(buffer); i++)
> +        if (buffer[i] != 0xFFFFFFFFU)
> +          return false;
> +      return true;
> +    }
> +    else
> +      return is_prefix(width);

this can also be optimized to not use complex is_prefix(),
but I don't think is_set_all() is used as often as set_all(), so it
shouldn't matter as much.

> +  }
> -  bool is_subset(const Bitmap& map2) const { return bitmap_is_subset(&map, &map2.map); }
> +  bool is_subset(const Bitmap & map2) const
> +  {
> +    for (size_t i= 0; i < array_elements(buffer); i++)
> +      if (buffer[i] & ~(map2.buffer[i]))
> +        return false;
> +    return true;
> +  }
> -  bool is_overlapping(const Bitmap& map2) const { return bitmap_is_overlapping(&map, &map2.map); }
> +  bool is_overlapping(const Bitmap & map2) const
> +  {
> +    for (size_t i = 0; i < array_elements(buffer); i++)
> +      if (buffer[i] & map2.buffer[i])
> +        return true;
> +    return false;
> +  }
> -  bool operator==(const Bitmap& map2) const { return bitmap_cmp(&map, &map2.map); }
> +  bool operator==(const Bitmap & map2) const
> +  {
> +    return memcmp(buffer, map2.buffer, sizeof(buffer)) == 0;
> +  }
> -  bool operator!=(const Bitmap& map2) const { return !(*this == map2); }
> +  bool operator!=(const Bitmap & map2) const
> +  {
> +    return !(*this == map2);
> +  }
>    char *print(char *buf) const
>    {
>      char *s=buf;

Regards,
Sergei
Chief Architect MariaDB
and security@xxxxxxxxxxx