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
  18 namespace ceph {
  19
  20 template <uint8_t _bit_count>
  21 class BitVector
  22 {
  23 private:
  24   static const uint8_t BITS_PER_BYTE = 8;
  25   static const uint32_t ELEMENTS_PER_BLOCK = BITS_PER_BYTE / _bit_count;
  26   static const uint8_t MASK = static_cast<uint8_t>((1 << _bit_count) - 1);
  27
  28   // must be power of 2
  29   BOOST_STATIC_ASSERT((_bit_count != 0) && !(_bit_count & (_bit_count - 1)));
  30   BOOST_STATIC_ASSERT(_bit_count <= BITS_PER_BYTE);
  31 public:
  32   static const uint32_t BLOCK_SIZE;
  33
  34   class ConstReference {
  35   public:
  36     operator uint8_t() const;
  37   private:
  38     friend class BitVector;
  39     const BitVector &m_bit_vector;
  40     uint64_t m_offset;
  41
  42     ConstReference(const BitVector &bit_vector, uint64_t offset);
  43   };
  44
  45   class Reference {
  46   public:
  47     operator uint8_t() const;
  48     Reference& operator=(uint8_t v);
  49   private:
  50     friend class BitVector;
  51     BitVector &m_bit_vector;
  52     uint64_t m_offset;
  53
  54     Reference(BitVector &bit_vector, uint64_t offset);
  55   };
  56
  57   static const uint8_t BIT_COUNT = _bit_count;
  58
  59   BitVector();
  60
  61   void set_crc_enabled(bool enabled) {
  62     m_crc_enabled = enabled;
  63   }
  64   void clear();
  65
  66   void resize(uint64_t elements);
  67   uint64_t size() const;
  68
  69   const bufferlist& get_data() const;
  70
  71   Reference operator[](uint64_t offset);
  72   ConstReference operator[](uint64_t offset) const;
  73
  74   void encode_header(bufferlist& bl) const;
  75   void decode_header(bufferlist::iterator& it);
  76   uint64_t get_header_length() const;
  77
  78   void encode_data(bufferlist& bl, uint64_t byte_offset,
  79                    uint64_t byte_length) const;
  80   void decode_data(bufferlist::iterator& it, uint64_t byte_offset);
  81   void get_data_extents(uint64_t offset, uint64_t length,
  82                         uint64_t *byte_offset, uint64_t *byte_length) const;
  83
  84   void encode_footer(bufferlist& bl) const;
  85   void decode_footer(bufferlist::iterator& it);
  86   uint64_t get_footer_offset() const;
  87
  88   void encode(bufferlist& bl) const;
  89   void decode(bufferlist::iterator& it);
  90   void dump(Formatter *f) const;
  91
  92   bool operator==(const BitVector &b) const;
  93
  94   static void generate_test_instances(std::list<BitVector *> &o);
  95 private:
  96
  97   bufferlist m_data;
  98   uint64_t m_size;
  99   bool m_crc_enabled;
 100
 101   mutable __u32 m_header_crc;
 102   mutable std::vector<__u32> m_data_crcs;
 103
 104   static void compute_index(uint64_t offset, uint64_t *index, uint64_t *shift);
 105
 106 };
 107
 108 template <uint8_t _b>
 109 const uint32_t BitVector<_b>::BLOCK_SIZE = 4096;
 110
 111 template <uint8_t _b>
 112 BitVector<_b>::BitVector() : m_size(0), m_crc_enabled(true), m_header_crc(0)
 113 {
 114 }
 115
 116 template <uint8_t _b>
 117 void BitVector<_b>::clear() {
 118   m_data.clear();
 119   m_data_crcs.clear();
 120   m_size = 0;
 121   m_header_crc = 0;
 122 }
 123
 124 template <uint8_t _b>
 125 void BitVector<_b>::resize(uint64_t size) {
 126   uint64_t buffer_size = (size + ELEMENTS_PER_BLOCK - 1) / ELEMENTS_PER_BLOCK;
 127   if (buffer_size > m_data.length()) {
 128     m_data.append_zero(buffer_size - m_data.length());
 129   } else if (buffer_size < m_data.length()) {
 130     bufferlist bl;
 131     bl.substr_of(m_data, 0, buffer_size);
 132     bl.swap(m_data);
 133   }
 134   m_size = size;
 135
 136   uint64_t block_count = (buffer_size + BLOCK_SIZE - 1) / BLOCK_SIZE;
 137   m_data_crcs.resize(block_count);
 138 }
 139
 140 template <uint8_t _b>
 141 uint64_t BitVector<_b>::size() const {
 142   return m_size;
 143 }
 144
 145 template <uint8_t _b>
 146 const bufferlist& BitVector<_b>::get_data() const {
 147   return m_data;
 148 }
 149
 150 template <uint8_t _b>
 151 void BitVector<_b>::compute_index(uint64_t offset, uint64_t *index, uint64_t *shift) {
 152   *index = offset / ELEMENTS_PER_BLOCK;
 153   *shift = ((ELEMENTS_PER_BLOCK - 1) - (offset % ELEMENTS_PER_BLOCK)) * _b;
 154 }
 155
 156 template <uint8_t _b>
 157 void BitVector<_b>::encode_header(bufferlist& bl) const {
 158   bufferlist header_bl;
 159   ENCODE_START(1, 1, header_bl);
 160   ::encode(m_size, header_bl);
 161   ENCODE_FINISH(header_bl);
 162   m_header_crc = header_bl.crc32c(0);
 163
 164   ::encode(header_bl, bl);
 165 }
 166
 167 template <uint8_t _b>
 168 void BitVector<_b>::decode_header(bufferlist::iterator& it) {
 169   bufferlist header_bl;
 170   ::decode(header_bl, it);
 171
 172   bufferlist::iterator header_it = header_bl.begin();
 173   uint64_t size;
 174   DECODE_START(1, header_it);
 175   ::decode(size, header_it);
 176   DECODE_FINISH(header_it);
 177
 178   resize(size);
 179   m_header_crc = header_bl.crc32c(0);
 180 }
 181
 182 template <uint8_t _b>
 183 uint64_t BitVector<_b>::get_header_length() const {
 184   // 4 byte bl length, 6 byte encoding header, 8 byte size
 185   return 18;
 186 }
 187
 188 template <uint8_t _b>
 189 void BitVector<_b>::encode_data(bufferlist& bl, uint64_t byte_offset,
 190                                 uint64_t byte_length) const {
 191   assert(byte_offset % BLOCK_SIZE == 0);
 192   assert(byte_offset + byte_length == m_data.length() ||
 193          byte_length % BLOCK_SIZE == 0);
 194
 195   uint64_t end_offset = byte_offset + byte_length;
 196   while (byte_offset < end_offset) {
 197     uint64_t len = MIN(BLOCK_SIZE, end_offset - byte_offset);
 198
 199     bufferlist bit;
 200     bit.substr_of(m_data, byte_offset, len);
 201     m_data_crcs[byte_offset / BLOCK_SIZE] = bit.crc32c(0);
 202
 203     bl.claim_append(bit);
 204     byte_offset += BLOCK_SIZE;
 205   }
 206 }
 207
 208 template <uint8_t _b>
 209 void BitVector<_b>::decode_data(bufferlist::iterator& it, uint64_t byte_offset) {
 210   assert(byte_offset % BLOCK_SIZE == 0);
 211   if (it.end()) {
 212     return;
 213   }
 214
 215   uint64_t end_offset = byte_offset + it.get_remaining();
 216   if (end_offset > m_data.length()) {
 217     throw buffer::end_of_buffer();
 218   }
 219
 220   bufferlist data;
 221   if (byte_offset > 0) {
 222     data.substr_of(m_data, 0, byte_offset);
 223   }
 224
 225   while (byte_offset < end_offset) {
 226     uint64_t len = MIN(BLOCK_SIZE, end_offset - byte_offset);
 227
 228     bufferptr ptr;
 229     it.copy_deep(len, ptr);
 230
 231     bufferlist bit;
 232     bit.append(ptr);
 233     if (m_crc_enabled &&
 234         m_data_crcs[byte_offset / BLOCK_SIZE] != bit.crc32c(0)) {
 235       throw buffer::malformed_input("invalid data block CRC");
 236     }
 237     data.append(bit);
 238     byte_offset += bit.length();
 239   }
 240
 241   if (m_data.length() > end_offset) {
 242     bufferlist tail;
 243     tail.substr_of(m_data, end_offset, m_data.length() - end_offset);
 244     data.append(tail);
 245   }
 246   assert(data.length() == m_data.length());
 247   data.swap(m_data);
 248 }
 249
 250 template <uint8_t _b>
 251 void BitVector<_b>::get_data_extents(uint64_t offset, uint64_t length,
 252                                      uint64_t *byte_offset,
 253                                      uint64_t *byte_length) const {
 254   // read BLOCK_SIZE-aligned chunks
 255   assert(length > 0 && offset + length <= m_size);
 256   uint64_t shift;
 257   compute_index(offset, byte_offset, &shift);
 258   *byte_offset -= (*byte_offset % BLOCK_SIZE);
 259
 260   uint64_t end_offset;
 261   compute_index(offset + length - 1, &end_offset, &shift);
 262   end_offset += (BLOCK_SIZE - (end_offset % BLOCK_SIZE));
 263   assert(*byte_offset <= end_offset);
 264
 265   *byte_length = end_offset - *byte_offset;
 266   if (*byte_offset + *byte_length > m_data.length()) {
 267     *byte_length = m_data.length() - *byte_offset;
 268   }
 269 }
 270
 271 template <uint8_t _b>
 272 void BitVector<_b>::encode_footer(bufferlist& bl) const {
 273   bufferlist footer_bl;
 274   if (m_crc_enabled) {
 275     ::encode(m_header_crc, footer_bl);
 276     ::encode(m_data_crcs, footer_bl);
 277   }
 278   ::encode(footer_bl, bl);
 279 }
 280
 281 template <uint8_t _b>
 282 void BitVector<_b>::decode_footer(bufferlist::iterator& it) {
 283   bufferlist footer_bl;
 284   ::decode(footer_bl, it);
 285
 286   m_crc_enabled = (footer_bl.length() > 0);
 287   if (m_crc_enabled) {
 288     bufferlist::iterator footer_it = footer_bl.begin();
 289
 290     __u32 header_crc;
 291     ::decode(header_crc, footer_it);
 292     if (m_header_crc != header_crc) {
 293       throw buffer::malformed_input("incorrect header CRC");
 294     }
 295
 296     uint64_t block_count = (m_data.length() + BLOCK_SIZE - 1) / BLOCK_SIZE;
 297     ::decode(m_data_crcs, footer_it);
 298     if (m_data_crcs.size() != block_count) {
 299       throw buffer::malformed_input("invalid data block CRCs");
 300     }
 301   }
 302 }
 303
 304 template <uint8_t _b>
 305 uint64_t BitVector<_b>::get_footer_offset() const {
 306   return get_header_length() + m_data.length();
 307 }
 308
 309 template <uint8_t _b>
 310 void BitVector<_b>::encode(bufferlist& bl) const {
 311   encode_header(bl);
 312   encode_data(bl, 0, m_data.length());
 313   encode_footer(bl);
 314 }
 315
 316 template <uint8_t _b>
 317 void BitVector<_b>::decode(bufferlist::iterator& it) {
 318   decode_header(it);
 319
 320   bufferlist data_bl;
 321   if (m_data.length() > 0) {
 322     it.copy(m_data.length(), data_bl);
 323   }
 324
 325   decode_footer(it);
 326
 327   bufferlist::iterator data_it = data_bl.begin();
 328   decode_data(data_it, 0);
 329 }
 330
 331 template <uint8_t _b>
 332 void BitVector<_b>::dump(Formatter *f) const {
 333   f->dump_unsigned("size", m_size);
 334   f->open_array_section("bit_table");
 335   for (unsigned i = 0; i < m_data.length(); ++i) {
 336     f->dump_format("byte", "0x%02hhX", m_data[i]);
 337   }
 338   f->close_section();
 339 }
 340
 341 template <uint8_t _b>
 342 bool BitVector<_b>::operator==(const BitVector &b) const {
 343   return (this->m_size == b.m_size && this->m_data == b.m_data);
 344 }
 345
 346 template <uint8_t _b>
 347 typename BitVector<_b>::Reference BitVector<_b>::operator[](uint64_t offset) {
 348   return Reference(*this, offset);
 349 }
 350
 351 template <uint8_t _b>
 352 typename BitVector<_b>::ConstReference BitVector<_b>::operator[](uint64_t offset) const {
 353   return ConstReference(*this, offset);
 354 }
 355
 356 template <uint8_t _b>
 357 BitVector<_b>::ConstReference::ConstReference(const BitVector<_b> &bit_vector,
 358                                               uint64_t offset)
 359   : m_bit_vector(bit_vector), m_offset(offset)
 360 {
 361 }
 362
 363 template <uint8_t _b>
 364 BitVector<_b>::ConstReference::operator uint8_t() const {
 365   uint64_t index;
 366   uint64_t shift;
 367   this->m_bit_vector.compute_index(this->m_offset, &index, &shift);
 368
 369   return (this->m_bit_vector.m_data[index] >> shift) & MASK;
 370 }
 371
 372 template <uint8_t _b>
 373 BitVector<_b>::Reference::Reference(BitVector<_b> &bit_vector, uint64_t offset)
 374   : m_bit_vector(bit_vector), m_offset(offset)
 375 {
 376 }
 377
 378 template <uint8_t _b>
 379 BitVector<_b>::Reference::operator uint8_t() const {
 380   uint64_t index;
 381   uint64_t shift;
 382   this->m_bit_vector.compute_index(this->m_offset, &index, &shift);
 383
 384   return (this->m_bit_vector.m_data[index] >> shift) & MASK;
 385 }
 386
 387 template <uint8_t _b>
 388 typename BitVector<_b>::Reference& BitVector<_b>::Reference::operator=(uint8_t v) {
 389   uint64_t index;
 390   uint64_t shift;
 391   this->m_bit_vector.compute_index(this->m_offset, &index, &shift);
 392
 393   uint8_t mask = MASK << shift;
 394   char packed_value = (this->m_bit_vector.m_data[index] & ~mask) |
 395                       ((v << shift) & mask);
 396   this->m_bit_vector.m_data.copy_in(index, 1, &packed_value);
 397   return *this;
 398 }
 399
 400 template <uint8_t _b>
 401 void BitVector<_b>::generate_test_instances(std::list<BitVector *> &o) {
 402   o.push_back(new BitVector());
 403
 404   BitVector *b = new BitVector();
 405   const uint64_t radix = 1 << b->BIT_COUNT;
 406   const uint64_t size = 1024;
 407
 408   b->resize(size);
 409   for (uint64_t i = 0; i < size; ++i) {
 410     (*b)[i] = rand() % radix;
 411   }
 412   o.push_back(b);
 413 }
 414
 415 }
 416
 417 WRITE_CLASS_ENCODER(ceph::BitVector<2>)
 418
 419 template <uint8_t _b>
 420 inline std::ostream& operator<<(std::ostream& out, const ceph::BitVector<_b> &b)
 421 {
 422   out << "ceph::BitVector<" << _b << ">(size=" << b.size() << ", data="
 423       << b.get_data() << ")";
 424   return out;
 425 }
 426
 427 #endif // BIT_VECTOR_HPP