ceph/src/test/common/test_bit_vector.cc

   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 #include <gtest/gtest.h>
  12 #include <cmath>
  13 #include "common/bit_vector.hpp"
  14 #include <boost/assign/list_of.hpp>
  15
  16 using namespace ceph;
  17
  18 template <uint8_t _bit_count>
  19 class TestParams {
  20 public:
  21   static const uint8_t BIT_COUNT = _bit_count;
  22 };
  23
  24 template <typename T>
  25 class BitVectorTest : public ::testing::Test {
  26 public:
  27   typedef BitVector<T::BIT_COUNT> bit_vector_t;
  28 };
  29
  30 typedef ::testing::Types<TestParams<2> > BitVectorTypes;
  31 TYPED_TEST_CASE(BitVectorTest, BitVectorTypes);
  32
  33 TYPED_TEST(BitVectorTest, resize) {
  34   typename TestFixture::bit_vector_t bit_vector;
  35
  36   size_t size = 2357;
  37
  38   double elements_per_byte = 8 / bit_vector.BIT_COUNT;
  39
  40   bit_vector.resize(size);
  41   ASSERT_EQ(bit_vector.size(), size);
  42   ASSERT_EQ(bit_vector.get_data().length(), static_cast<uint64_t>(std::ceil(
  43     size / elements_per_byte)));
  44 }
  45
  46 TYPED_TEST(BitVectorTest, clear) {
  47   typename TestFixture::bit_vector_t bit_vector;
  48
  49   bit_vector.resize(123);
  50   bit_vector.clear();
  51   ASSERT_EQ(0ull, bit_vector.size());
  52   ASSERT_EQ(0ull, bit_vector.get_data().length());
  53 }
  54
  55 TYPED_TEST(BitVectorTest, bit_order) {
  56   typename TestFixture::bit_vector_t bit_vector;
  57   bit_vector.resize(1);
  58
  59   uint8_t value = 1;
  60   bit_vector[0] = value;
  61
  62   value <<= (8 - bit_vector.BIT_COUNT);
  63   ASSERT_EQ(value, bit_vector.get_data()[0]);
  64 }
  65
  66 TYPED_TEST(BitVectorTest, get_set) {
  67   typename TestFixture::bit_vector_t bit_vector;
  68   std::vector<uint64_t> ref;
  69
  70   uint64_t radix = 1 << bit_vector.BIT_COUNT;
  71
  72   size_t size = 1024;
  73   bit_vector.resize(size);
  74   ref.resize(size);
  75   for (size_t i = 0; i < size; ++i) {
  76     uint64_t v = rand() % radix;
  77     ref[i] = v;
  78     bit_vector[i] = v;
  79   }
  80
  81   const typename TestFixture::bit_vector_t &const_bit_vector(bit_vector);
  82   for (size_t i = 0; i < size; ++i) {
  83     ASSERT_EQ(ref[i], bit_vector[i]);
  84     ASSERT_EQ(ref[i], const_bit_vector[i]);
  85   }
  86 }
  87
  88 TYPED_TEST(BitVectorTest, get_buffer_extents) {
  89   typename TestFixture::bit_vector_t bit_vector;
  90
  91   uint64_t element_count = 2 * bit_vector.BLOCK_SIZE + 51;
  92   uint64_t elements_per_byte = 8 / bit_vector.BIT_COUNT;
  93   bit_vector.resize(element_count * elements_per_byte);
  94
  95   uint64_t offset = (bit_vector.BLOCK_SIZE + 11) * elements_per_byte;
  96   uint64_t length = (bit_vector.BLOCK_SIZE + 31) * elements_per_byte;
  97   uint64_t byte_offset;
  98   uint64_t byte_length;
  99   bit_vector.get_data_extents(offset, length, &byte_offset, &byte_length);
 100   ASSERT_EQ(bit_vector.BLOCK_SIZE, byte_offset);
 101   ASSERT_EQ(bit_vector.BLOCK_SIZE + (element_count % bit_vector.BLOCK_SIZE),
 102             byte_length);
 103
 104   bit_vector.get_data_extents(1, 1, &byte_offset, &byte_length);
 105   ASSERT_EQ(0U, byte_offset);
 106   ASSERT_EQ(bit_vector.BLOCK_SIZE, byte_length);
 107 }
 108
 109 TYPED_TEST(BitVectorTest, get_header_length) {
 110   typename TestFixture::bit_vector_t bit_vector;
 111
 112   bufferlist bl;
 113   bit_vector.encode_header(bl);
 114   ASSERT_EQ(bl.length(), bit_vector.get_header_length());
 115 }
 116
 117 TYPED_TEST(BitVectorTest, get_footer_offset) {
 118   typename TestFixture::bit_vector_t bit_vector;
 119
 120   bit_vector.resize(5111);
 121
 122   uint64_t byte_offset;
 123   uint64_t byte_length;
 124   bit_vector.get_data_extents(0, bit_vector.size(), &byte_offset, &byte_length);
 125
 126   ASSERT_EQ(bit_vector.get_header_length() + byte_length,
 127             bit_vector.get_footer_offset());
 128 }
 129
 130 TYPED_TEST(BitVectorTest, partial_decode_encode) {
 131   typename TestFixture::bit_vector_t bit_vector;
 132
 133   uint64_t elements_per_byte = 8 / bit_vector.BIT_COUNT;
 134   bit_vector.resize(9161 * elements_per_byte);
 135   for (uint64_t i = 0; i < bit_vector.size(); ++i) {
 136     bit_vector[i] = i % 4;
 137   }
 138
 139   bufferlist bl;
 140   ::encode(bit_vector, bl);
 141   bit_vector.clear();
 142
 143   bufferlist header_bl;
 144   header_bl.substr_of(bl, 0, bit_vector.get_header_length());
 145   bufferlist::iterator header_it = header_bl.begin();
 146   bit_vector.decode_header(header_it);
 147
 148   bufferlist footer_bl;
 149   footer_bl.substr_of(bl, bit_vector.get_footer_offset(),
 150                       bl.length() - bit_vector.get_footer_offset());
 151   bufferlist::iterator footer_it = footer_bl.begin();
 152   bit_vector.decode_footer(footer_it);
 153
 154   typedef std::pair<uint64_t, uint64_t> Extent;
 155   typedef std::list<Extent> Extents;
 156
 157   Extents extents = boost::assign::list_of(
 158     std::make_pair(0, 1))(
 159     std::make_pair((bit_vector.BLOCK_SIZE * elements_per_byte) - 2, 4))(
 160     std::make_pair((bit_vector.BLOCK_SIZE * elements_per_byte) + 2, 2))(
 161     std::make_pair((2 * bit_vector.BLOCK_SIZE * elements_per_byte) - 2, 4))(
 162     std::make_pair((2 * bit_vector.BLOCK_SIZE * elements_per_byte) + 2, 2))(
 163     std::make_pair(2, 2 * bit_vector.BLOCK_SIZE));
 164   for (Extents::iterator it = extents.begin(); it != extents.end(); ++it) {
 165     uint64_t element_offset = it->first;
 166     uint64_t element_length = it->second;
 167     uint64_t byte_offset;
 168     uint64_t byte_length;
 169     bit_vector.get_data_extents(element_offset, element_length, &byte_offset,
 170                                 &byte_length);
 171
 172     bufferlist data_bl;
 173     data_bl.substr_of(bl, bit_vector.get_header_length() + byte_offset,
 174                       byte_length);
 175     bufferlist::iterator data_it = data_bl.begin();
 176     bit_vector.decode_data(data_it, byte_offset);
 177
 178     data_bl.clear();
 179     bit_vector.encode_data(data_bl, byte_offset, byte_length);
 180
 181     footer_bl.clear();
 182     bit_vector.encode_footer(footer_bl);
 183
 184     bufferlist updated_bl;
 185     updated_bl.substr_of(bl, 0, bit_vector.get_header_length() + byte_offset);
 186     updated_bl.append(data_bl);
 187
 188     if (byte_offset + byte_length < bit_vector.get_footer_offset()) {
 189       uint64_t tail_data_offset = bit_vector.get_header_length() + byte_offset +
 190                                   byte_length;
 191       data_bl.substr_of(bl, tail_data_offset,
 192                         bit_vector.get_footer_offset() - tail_data_offset);
 193       updated_bl.append(data_bl);
 194     }
 195
 196     updated_bl.append(footer_bl);
 197     ASSERT_EQ(bl, updated_bl);
 198
 199     bufferlist::iterator updated_it = updated_bl.begin();
 200     ::decode(bit_vector, updated_it);
 201   }
 202 }
 203
 204 TYPED_TEST(BitVectorTest, header_crc) {
 205   typename TestFixture::bit_vector_t bit_vector;
 206
 207   bufferlist header;
 208   bit_vector.encode_header(header);
 209
 210   bufferlist footer;
 211   bit_vector.encode_footer(footer);
 212
 213   bufferlist::iterator it = footer.begin();
 214   bit_vector.decode_footer(it);
 215
 216   bit_vector.resize(1);
 217   bit_vector.encode_header(header);
 218
 219   it = footer.begin();
 220   ASSERT_THROW(bit_vector.decode_footer(it), buffer::malformed_input);
 221 }
 222
 223 TYPED_TEST(BitVectorTest, data_crc) {
 224   typename TestFixture::bit_vector_t bit_vector1;
 225   typename TestFixture::bit_vector_t bit_vector2;
 226
 227   uint64_t elements_per_byte = 8 / bit_vector1.BIT_COUNT;
 228   bit_vector1.resize((bit_vector1.BLOCK_SIZE + 1) * elements_per_byte);
 229   bit_vector2.resize((bit_vector2.BLOCK_SIZE + 1) * elements_per_byte);
 230
 231   uint64_t byte_offset;
 232   uint64_t byte_length;
 233   bit_vector1.get_data_extents(0, bit_vector1.size(), &byte_offset,
 234                                &byte_length);
 235
 236   bufferlist data;
 237   bit_vector1.encode_data(data, byte_offset, byte_length);
 238
 239   bufferlist::iterator data_it = data.begin();
 240   bit_vector1.decode_data(data_it, byte_offset);
 241
 242   bit_vector2[bit_vector2.size() - 1] = 1;
 243
 244   bufferlist dummy_data;
 245   bit_vector2.encode_data(dummy_data, byte_offset, byte_length);
 246
 247   data_it = data.begin();
 248   ASSERT_THROW(bit_vector2.decode_data(data_it, byte_offset),
 249                buffer::malformed_input);
 250 }
 251
 252 TYPED_TEST(BitVectorTest, iterator) {
 253   typename TestFixture::bit_vector_t bit_vector;
 254
 255   uint64_t radix = 1 << bit_vector.BIT_COUNT;
 256   uint64_t size = 25 * (1ULL << 20);
 257   uint64_t offset = 0;
 258
 259   // create fragmented in-memory bufferlist layout
 260   uint64_t resize = 0;
 261   while (resize < size) {
 262     resize += 4096;
 263     if (resize > size) {
 264       resize = size;
 265     }
 266     bit_vector.resize(resize);
 267   }
 268
 269   for (auto it = bit_vector.begin(); it != bit_vector.end(); ++it, ++offset) {
 270     *it = offset % radix;
 271   }
 272
 273   offset = 123;
 274   auto end_it = bit_vector.begin() + (size - 1024);
 275   for (auto it = bit_vector.begin() + offset; it != end_it; ++it, ++offset) {
 276     ASSERT_EQ(offset % radix, *it);
 277   }
 278 }