ceph/src/common/bit_vector.hpp

   1 // -*- mode:C++; tab-width:8; c-basic-offset:2; indent-tabs-mode:t -*-
   2 // vim: ts=8 sw=2 smarttab
   3 /*
   4  * Ceph - scalable distributed file system
   5  *
   6  * Copyright (C) 2014 Red Hat <contact@redhat.com>
   7  *
   8  * LGPL2.1 (see COPYING-LGPL2.1) or later
   9  */
  10
  11 #ifndef BIT_VECTOR_HPP
  12 #define BIT_VECTOR_HPP
  13
  14 #include "common/Formatter.h"
  15 #include "include/assert.h"
  16 #include "include/encoding.h"
  17 #include <utility>
  18
  19 namespace ceph {
  20
  21 template <uint8_t _bit_count>
  22 class BitVector
  23 {
  24 private:
  25   static const uint8_t BITS_PER_BYTE = 8;
  26   static const uint32_t ELEMENTS_PER_BLOCK = BITS_PER_BYTE / _bit_count;
  27   static const uint8_t MASK = static_cast<uint8_t>((1 << _bit_count) - 1);
  28
  29   // must be power of 2
  30   BOOST_STATIC_ASSERT((_bit_count != 0) && !(_bit_count & (_bit_count - 1)));
  31   BOOST_STATIC_ASSERT(_bit_count <= BITS_PER_BYTE);
  32
  33   template <typename DataIterator>
  34   class ReferenceImpl {
  35   protected:
  36     DataIterator m_data_iterator;
  37     uint64_t m_shift;
  38
  39     ReferenceImpl(const DataIterator& data_iterator, uint64_t shift)
  40       : m_data_iterator(data_iterator), m_shift(shift) {
  41     }
  42     ReferenceImpl(DataIterator&& data_iterator, uint64_t shift)
  43       : m_data_iterator(std::move(data_iterator)), m_shift(shift) {
  44     }
  45
  46   public:
  47     inline operator uint8_t() const {
  48       return (*m_data_iterator >> m_shift) & MASK;
  49     }
  50   };
  51
  52 public:
  53
  54   class ConstReference : public ReferenceImpl<bufferlist::const_iterator> {
  55   private:
  56     friend class BitVector;
  57
  58     ConstReference(const bufferlist::const_iterator& data_iterator,
  59                    uint64_t shift)
  60       : ReferenceImpl<bufferlist::const_iterator>(data_iterator, shift) {
  61     }
  62     ConstReference(bufferlist::const_iterator&& data_iterator, uint64_t shift)
  63       : ReferenceImpl<bufferlist::const_iterator>(std::move(data_iterator),
  64                                                   shift) {
  65     }
  66   };
  67
  68   class Reference : public ReferenceImpl<bufferlist::iterator> {
  69   public:
  70     Reference& operator=(uint8_t v);
  71
  72   private:
  73     friend class BitVector;
  74
  75     Reference(const bufferlist::iterator& data_iterator, uint64_t shift)
  76       : ReferenceImpl<bufferlist::iterator>(data_iterator, shift) {
  77     }
  78     Reference(bufferlist::iterator&& data_iterator, uint64_t shift)
  79       : ReferenceImpl<bufferlist::iterator>(std::move(data_iterator), shift) {
  80     }
  81   };
  82
  83 public:
  84   template <typename BitVectorT, typename DataIterator>
  85   class IteratorImpl {
  86   private:
  87     friend class BitVector;
  88
  89     uint64_t m_offset = 0;
  90     BitVectorT *m_bit_vector;
  91
  92     // cached derived values
  93     uint64_t m_index = 0;
  94     uint64_t m_shift = 0;
  95     DataIterator m_data_iterator;
  96
  97     IteratorImpl(BitVectorT *bit_vector, uint64_t offset)
  98       : m_bit_vector(bit_vector),
  99         m_data_iterator(bit_vector->m_data.begin()) {
 100       *this += offset;
 101     }
 102
 103   public:
 104     inline IteratorImpl& operator++() {
 105       ++m_offset;
 106
 107       uint64_t index;
 108       compute_index(m_offset, &index, &m_shift);
 109
 110       assert(index == m_index || index == m_index + 1);
 111       if (index > m_index) {
 112         m_index = index;
 113         ++m_data_iterator;
 114       }
 115       return *this;
 116     }
 117     inline IteratorImpl& operator+=(uint64_t offset) {
 118       m_offset += offset;
 119       compute_index(m_offset, &m_index, &m_shift);
 120       if (m_offset < m_bit_vector->size()) {
 121         m_data_iterator.seek(m_index);
 122       } else {
 123         m_data_iterator = m_bit_vector->m_data.end();
 124       }
 125       return *this;
 126     }
 127
 128     inline IteratorImpl operator++(int) {
 129       IteratorImpl iterator_impl(*this);
 130       ++iterator_impl;
 131       return iterator_impl;
 132     }
 133     inline IteratorImpl operator+(uint64_t offset) {
 134       IteratorImpl iterator_impl(*this);
 135       iterator_impl += offset;
 136       return iterator_impl;
 137     }
 138
 139     inline bool operator==(const IteratorImpl& rhs) const {
 140       return (m_offset == rhs.m_offset && m_bit_vector == rhs.m_bit_vector);
 141     }
 142     inline bool operator!=(const IteratorImpl& rhs) const {
 143       return (m_offset != rhs.m_offset || m_bit_vector != rhs.m_bit_vector);
 144     }
 145
 146     inline ConstReference operator*() const {
 147       return ConstReference(m_data_iterator, m_shift);
 148     }
 149     inline Reference operator*() {
 150       return Reference(m_data_iterator, m_shift);
 151     }
 152   };
 153
 154   typedef IteratorImpl<const BitVector,
 155                        bufferlist::const_iterator> ConstIterator;
 156   typedef IteratorImpl<BitVector, bufferlist::iterator> Iterator;
 157
 158   static const uint32_t BLOCK_SIZE;
 159   static const uint8_t BIT_COUNT = _bit_count;
 160
 161   BitVector();
 162
 163   inline ConstIterator begin() const {
 164     return ConstIterator(this, 0);
 165   }
 166   inline ConstIterator end() const {
 167     return ConstIterator(this, m_size);
 168   }
 169   inline Iterator begin() {
 170     return Iterator(this, 0);
 171   }
 172   inline Iterator end() {
 173     return Iterator(this, m_size);
 174   }
 175
 176   void set_crc_enabled(bool enabled) {
 177     m_crc_enabled = enabled;
 178   }
 179   void clear();
 180
 181   void resize(uint64_t elements);
 182   uint64_t size() const;
 183
 184   const bufferlist& get_data() const;
 185
 186   Reference operator[](uint64_t offset);
 187   ConstReference operator[](uint64_t offset) const;
 188
 189   void encode_header(bufferlist& bl) const;
 190   void decode_header(bufferlist::iterator& it);
 191   uint64_t get_header_length() const;
 192
 193   void encode_data(bufferlist& bl, uint64_t byte_offset,
 194                    uint64_t byte_length) const;
 195   void decode_data(bufferlist::iterator& it, uint64_t byte_offset);
 196   void get_data_extents(uint64_t offset, uint64_t length,
 197                         uint64_t *byte_offset, uint64_t *byte_length) const;
 198
 199   void encode_footer(bufferlist& bl) const;
 200   void decode_footer(bufferlist::iterator& it);
 201   uint64_t get_footer_offset() const;
 202
 203   void encode(bufferlist& bl) const;
 204   void decode(bufferlist::iterator& it);
 205   void dump(Formatter *f) const;
 206
 207   bool operator==(const BitVector &b) const;
 208
 209   static void generate_test_instances(std::list<BitVector *> &o);
 210 private:
 211
 212   bufferlist m_data;
 213   uint64_t m_size;
 214   bool m_crc_enabled;
 215
 216   mutable __u32 m_header_crc;
 217   mutable std::vector<__u32> m_data_crcs;
 218
 219   static void compute_index(uint64_t offset, uint64_t *index, uint64_t *shift);
 220
 221 };
 222
 223 template <uint8_t _b>
 224 const uint32_t BitVector<_b>::BLOCK_SIZE = 4096;
 225
 226 template <uint8_t _b>
 227 BitVector<_b>::BitVector() : m_size(0), m_crc_enabled(true), m_header_crc(0)
 228 {
 229 }
 230
 231 template <uint8_t _b>
 232 void BitVector<_b>::clear() {
 233   m_data.clear();
 234   m_data_crcs.clear();
 235   m_size = 0;
 236   m_header_crc = 0;
 237 }
 238
 239 template <uint8_t _b>
 240 void BitVector<_b>::resize(uint64_t size) {
 241   uint64_t buffer_size = (size + ELEMENTS_PER_BLOCK - 1) / ELEMENTS_PER_BLOCK;
 242   if (buffer_size > m_data.length()) {
 243     m_data.append_zero(buffer_size - m_data.length());
 244   } else if (buffer_size < m_data.length()) {
 245     bufferlist bl;
 246     bl.substr_of(m_data, 0, buffer_size);
 247     bl.swap(m_data);
 248   }
 249   m_size = size;
 250
 251   uint64_t block_count = (buffer_size + BLOCK_SIZE - 1) / BLOCK_SIZE;
 252   m_data_crcs.resize(block_count);
 253 }
 254
 255 template <uint8_t _b>
 256 uint64_t BitVector<_b>::size() const {
 257   return m_size;
 258 }
 259
 260 template <uint8_t _b>
 261 const bufferlist& BitVector<_b>::get_data() const {
 262   return m_data;
 263 }
 264
 265 template <uint8_t _b>
 266 void BitVector<_b>::compute_index(uint64_t offset, uint64_t *index, uint64_t *shift) {
 267   *index = offset / ELEMENTS_PER_BLOCK;
 268   *shift = ((ELEMENTS_PER_BLOCK - 1) - (offset % ELEMENTS_PER_BLOCK)) * _b;
 269 }
 270
 271 template <uint8_t _b>
 272 void BitVector<_b>::encode_header(bufferlist& bl) const {
 273   bufferlist header_bl;
 274   ENCODE_START(1, 1, header_bl);
 275   ::encode(m_size, header_bl);
 276   ENCODE_FINISH(header_bl);
 277   m_header_crc = header_bl.crc32c(0);
 278
 279   ::encode(header_bl, bl);
 280 }
 281
 282 template <uint8_t _b>
 283 void BitVector<_b>::decode_header(bufferlist::iterator& it) {
 284   bufferlist header_bl;
 285   ::decode(header_bl, it);
 286
 287   bufferlist::iterator header_it = header_bl.begin();
 288   uint64_t size;
 289   DECODE_START(1, header_it);
 290   ::decode(size, header_it);
 291   DECODE_FINISH(header_it);
 292
 293   resize(size);
 294   m_header_crc = header_bl.crc32c(0);
 295 }
 296
 297 template <uint8_t _b>
 298 uint64_t BitVector<_b>::get_header_length() const {
 299   // 4 byte bl length, 6 byte encoding header, 8 byte size
 300   return 18;
 301 }
 302
 303 template <uint8_t _b>
 304 void BitVector<_b>::encode_data(bufferlist& bl, uint64_t byte_offset,
 305                                 uint64_t byte_length) const {
 306   assert(byte_offset % BLOCK_SIZE == 0);
 307   assert(byte_offset + byte_length == m_data.length() ||
 308          byte_length % BLOCK_SIZE == 0);
 309
 310   uint64_t end_offset = byte_offset + byte_length;
 311   while (byte_offset < end_offset) {
 312     uint64_t len = MIN(BLOCK_SIZE, end_offset - byte_offset);
 313
 314     bufferlist bit;
 315     bit.substr_of(m_data, byte_offset, len);
 316     m_data_crcs[byte_offset / BLOCK_SIZE] = bit.crc32c(0);
 317
 318     bl.claim_append(bit);
 319     byte_offset += BLOCK_SIZE;
 320   }
 321 }
 322
 323 template <uint8_t _b>
 324 void BitVector<_b>::decode_data(bufferlist::iterator& it, uint64_t byte_offset) {
 325   assert(byte_offset % BLOCK_SIZE == 0);
 326   if (it.end()) {
 327     return;
 328   }
 329
 330   uint64_t end_offset = byte_offset + it.get_remaining();
 331   if (end_offset > m_data.length()) {
 332     throw buffer::end_of_buffer();
 333   }
 334
 335   bufferlist data;
 336   if (byte_offset > 0) {
 337     data.substr_of(m_data, 0, byte_offset);
 338   }
 339
 340   while (byte_offset < end_offset) {
 341     uint64_t len = MIN(BLOCK_SIZE, end_offset - byte_offset);
 342
 343     bufferptr ptr;
 344     it.copy_deep(len, ptr);
 345
 346     bufferlist bit;
 347     bit.append(ptr);
 348     if (m_crc_enabled &&
 349         m_data_crcs[byte_offset / BLOCK_SIZE] != bit.crc32c(0)) {
 350       throw buffer::malformed_input("invalid data block CRC");
 351     }
 352     data.append(bit);
 353     byte_offset += bit.length();
 354   }
 355
 356   if (m_data.length() > end_offset) {
 357     bufferlist tail;
 358     tail.substr_of(m_data, end_offset, m_data.length() - end_offset);
 359     data.append(tail);
 360   }
 361   assert(data.length() == m_data.length());
 362   data.swap(m_data);
 363 }
 364
 365 template <uint8_t _b>
 366 void BitVector<_b>::get_data_extents(uint64_t offset, uint64_t length,
 367                                      uint64_t *byte_offset,
 368                                      uint64_t *byte_length) const {
 369   // read BLOCK_SIZE-aligned chunks
 370   assert(length > 0 && offset + length <= m_size);
 371   uint64_t shift;
 372   compute_index(offset, byte_offset, &shift);
 373   *byte_offset -= (*byte_offset % BLOCK_SIZE);
 374
 375   uint64_t end_offset;
 376   compute_index(offset + length - 1, &end_offset, &shift);
 377   end_offset += (BLOCK_SIZE - (end_offset % BLOCK_SIZE));
 378   assert(*byte_offset <= end_offset);
 379
 380   *byte_length = end_offset - *byte_offset;
 381   if (*byte_offset + *byte_length > m_data.length()) {
 382     *byte_length = m_data.length() - *byte_offset;
 383   }
 384 }
 385
 386 template <uint8_t _b>
 387 void BitVector<_b>::encode_footer(bufferlist& bl) const {
 388   bufferlist footer_bl;
 389   if (m_crc_enabled) {
 390     ::encode(m_header_crc, footer_bl);
 391     ::encode(m_data_crcs, footer_bl);
 392   }
 393   ::encode(footer_bl, bl);
 394 }
 395
 396 template <uint8_t _b>
 397 void BitVector<_b>::decode_footer(bufferlist::iterator& it) {
 398   bufferlist footer_bl;
 399   ::decode(footer_bl, it);
 400
 401   m_crc_enabled = (footer_bl.length() > 0);
 402   if (m_crc_enabled) {
 403     bufferlist::iterator footer_it = footer_bl.begin();
 404
 405     __u32 header_crc;
 406     ::decode(header_crc, footer_it);
 407     if (m_header_crc != header_crc) {
 408       throw buffer::malformed_input("incorrect header CRC");
 409     }
 410
 411     uint64_t block_count = (m_data.length() + BLOCK_SIZE - 1) / BLOCK_SIZE;
 412     ::decode(m_data_crcs, footer_it);
 413     if (m_data_crcs.size() != block_count) {
 414       throw buffer::malformed_input("invalid data block CRCs");
 415     }
 416   }
 417 }
 418
 419 template <uint8_t _b>
 420 uint64_t BitVector<_b>::get_footer_offset() const {
 421   return get_header_length() + m_data.length();
 422 }
 423
 424 template <uint8_t _b>
 425 void BitVector<_b>::encode(bufferlist& bl) const {
 426   encode_header(bl);
 427   encode_data(bl, 0, m_data.length());
 428   encode_footer(bl);
 429 }
 430
 431 template <uint8_t _b>
 432 void BitVector<_b>::decode(bufferlist::iterator& it) {
 433   decode_header(it);
 434
 435   bufferlist data_bl;
 436   if (m_data.length() > 0) {
 437     it.copy(m_data.length(), data_bl);
 438   }
 439
 440   decode_footer(it);
 441
 442   bufferlist::iterator data_it = data_bl.begin();
 443   decode_data(data_it, 0);
 444 }
 445
 446 template <uint8_t _b>
 447 void BitVector<_b>::dump(Formatter *f) const {
 448   f->dump_unsigned("size", m_size);
 449   f->open_array_section("bit_table");
 450   for (unsigned i = 0; i < m_data.length(); ++i) {
 451     f->dump_format("byte", "0x%02hhX", m_data[i]);
 452   }
 453   f->close_section();
 454 }
 455
 456 template <uint8_t _b>
 457 bool BitVector<_b>::operator==(const BitVector &b) const {
 458   return (this->m_size == b.m_size && this->m_data == b.m_data);
 459 }
 460
 461 template <uint8_t _b>
 462 typename BitVector<_b>::Reference BitVector<_b>::operator[](uint64_t offset) {
 463   uint64_t index;
 464   uint64_t shift;
 465   compute_index(offset, &index, &shift);
 466
 467   bufferlist::iterator data_iterator(m_data.begin());
 468   data_iterator.seek(index);
 469   return Reference(std::move(data_iterator), shift);
 470 }
 471
 472 template <uint8_t _b>
 473 typename BitVector<_b>::ConstReference BitVector<_b>::operator[](uint64_t offset) const {
 474   uint64_t index;
 475   uint64_t shift;
 476   compute_index(offset, &index, &shift);
 477
 478   bufferlist::const_iterator data_iterator(m_data.begin());
 479   data_iterator.seek(index);
 480   return ConstReference(std::move(data_iterator), shift);
 481 }
 482
 483 template <uint8_t _b>
 484 typename BitVector<_b>::Reference& BitVector<_b>::Reference::operator=(uint8_t v) {
 485   uint8_t mask = MASK << this->m_shift;
 486   char packed_value = (*this->m_data_iterator & ~mask) |
 487                       ((v << this->m_shift) & mask);
 488   bufferlist::iterator it(this->m_data_iterator);
 489   it.copy_in(1, &packed_value, true);
 490   return *this;
 491 }
 492
 493 template <uint8_t _b>
 494 void BitVector<_b>::generate_test_instances(std::list<BitVector *> &o) {
 495   o.push_back(new BitVector());
 496
 497   BitVector *b = new BitVector();
 498   const uint64_t radix = 1 << b->BIT_COUNT;
 499   const uint64_t size = 1024;
 500
 501   b->resize(size);
 502   for (uint64_t i = 0; i < size; ++i) {
 503     (*b)[i] = rand() % radix;
 504   }
 505   o.push_back(b);
 506 }
 507
 508 }
 509
 510 WRITE_CLASS_ENCODER(ceph::BitVector<2>)
 511
 512 template <uint8_t _b>
 513 inline std::ostream& operator<<(std::ostream& out, const ceph::BitVector<_b> &b)
 514 {
 515   out << "ceph::BitVector<" << _b << ">(size=" << b.size() << ", data="
 516       << b.get_data() << ")";
 517   return out;
 518 }
 519
 520 #endif // BIT_VECTOR_HPP