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