1 // -*- mode:C++; tab-width:8; c-basic-offset:2; indent-tabs-mode:t -*-
2 // vim: ts=8 sw=2 smarttab
4 * Ceph - scalable distributed file system
6 * Copyright (C) 2014 Red Hat <contact@redhat.com>
8 * LGPL2.1 (see COPYING-LGPL2.1) or later
11 #include <gtest/gtest.h>
13 #include "common/bit_vector.hpp"
14 #include <boost/assign/list_of.hpp>
18 template <uint8_t _bit_count>
21 static const uint8_t BIT_COUNT = _bit_count;
25 class BitVectorTest : public ::testing::Test {
27 typedef BitVector<T::BIT_COUNT> bit_vector_t;
30 typedef ::testing::Types<TestParams<2> > BitVectorTypes;
31 TYPED_TEST_CASE(BitVectorTest, BitVectorTypes);
33 TYPED_TEST(BitVectorTest, resize) {
34 typename TestFixture::bit_vector_t bit_vector;
38 double elements_per_byte = 8 / bit_vector.BIT_COUNT;
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)));
46 TYPED_TEST(BitVectorTest, clear) {
47 typename TestFixture::bit_vector_t bit_vector;
49 bit_vector.resize(123);
51 ASSERT_EQ(0ull, bit_vector.size());
52 ASSERT_EQ(0ull, bit_vector.get_data().length());
55 TYPED_TEST(BitVectorTest, bit_order) {
56 typename TestFixture::bit_vector_t bit_vector;
60 bit_vector[0] = value;
62 value <<= (8 - bit_vector.BIT_COUNT);
63 ASSERT_EQ(value, bit_vector.get_data()[0]);
66 TYPED_TEST(BitVectorTest, get_set) {
67 typename TestFixture::bit_vector_t bit_vector;
68 std::vector<uint64_t> ref;
70 uint64_t radix = 1 << bit_vector.BIT_COUNT;
73 bit_vector.resize(size);
75 for (size_t i = 0; i < size; ++i) {
76 uint64_t v = rand() % radix;
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]);
88 TYPED_TEST(BitVectorTest, get_buffer_extents) {
89 typename TestFixture::bit_vector_t bit_vector;
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);
95 uint64_t offset = (bit_vector.BLOCK_SIZE + 11) * elements_per_byte;
96 uint64_t length = (bit_vector.BLOCK_SIZE + 31) * elements_per_byte;
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),
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);
109 TYPED_TEST(BitVectorTest, get_header_length) {
110 typename TestFixture::bit_vector_t bit_vector;
113 bit_vector.encode_header(bl);
114 ASSERT_EQ(bl.length(), bit_vector.get_header_length());
117 TYPED_TEST(BitVectorTest, get_footer_offset) {
118 typename TestFixture::bit_vector_t bit_vector;
120 bit_vector.resize(5111);
122 uint64_t byte_offset;
123 uint64_t byte_length;
124 bit_vector.get_data_extents(0, bit_vector.size(), &byte_offset, &byte_length);
126 ASSERT_EQ(bit_vector.get_header_length() + byte_length,
127 bit_vector.get_footer_offset());
130 TYPED_TEST(BitVectorTest, partial_decode_encode) {
131 typename TestFixture::bit_vector_t bit_vector;
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;
140 ::encode(bit_vector, bl);
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);
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);
154 typedef std::pair<uint64_t, uint64_t> Extent;
155 typedef std::list<Extent> Extents;
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,
173 data_bl.substr_of(bl, bit_vector.get_header_length() + byte_offset,
175 bufferlist::iterator data_it = data_bl.begin();
176 bit_vector.decode_data(data_it, byte_offset);
179 bit_vector.encode_data(data_bl, byte_offset, byte_length);
182 bit_vector.encode_footer(footer_bl);
184 bufferlist updated_bl;
185 updated_bl.substr_of(bl, 0, bit_vector.get_header_length() + byte_offset);
186 updated_bl.append(data_bl);
188 if (byte_offset + byte_length < bit_vector.get_footer_offset()) {
189 uint64_t tail_data_offset = bit_vector.get_header_length() + byte_offset +
191 data_bl.substr_of(bl, tail_data_offset,
192 bit_vector.get_footer_offset() - tail_data_offset);
193 updated_bl.append(data_bl);
196 updated_bl.append(footer_bl);
197 ASSERT_EQ(bl, updated_bl);
199 bufferlist::iterator updated_it = updated_bl.begin();
200 ::decode(bit_vector, updated_it);
204 TYPED_TEST(BitVectorTest, header_crc) {
205 typename TestFixture::bit_vector_t bit_vector;
208 bit_vector.encode_header(header);
211 bit_vector.encode_footer(footer);
213 bufferlist::iterator it = footer.begin();
214 bit_vector.decode_footer(it);
216 bit_vector.resize(1);
217 bit_vector.encode_header(header);
220 ASSERT_THROW(bit_vector.decode_footer(it), buffer::malformed_input);
223 TYPED_TEST(BitVectorTest, data_crc) {
224 typename TestFixture::bit_vector_t bit_vector1;
225 typename TestFixture::bit_vector_t bit_vector2;
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);
231 uint64_t byte_offset;
232 uint64_t byte_length;
233 bit_vector1.get_data_extents(0, bit_vector1.size(), &byte_offset,
237 bit_vector1.encode_data(data, byte_offset, byte_length);
239 bufferlist::iterator data_it = data.begin();
240 bit_vector1.decode_data(data_it, byte_offset);
242 bit_vector2[bit_vector2.size() - 1] = 1;
244 bufferlist dummy_data;
245 bit_vector2.encode_data(dummy_data, byte_offset, byte_length);
247 data_it = data.begin();
248 ASSERT_THROW(bit_vector2.decode_data(data_it, byte_offset),
249 buffer::malformed_input);
252 TYPED_TEST(BitVectorTest, iterator) {
253 typename TestFixture::bit_vector_t bit_vector;
255 uint64_t radix = 1 << bit_vector.BIT_COUNT;
256 uint64_t size = 25 * (1ULL << 20);
259 // create fragmented in-memory bufferlist layout
261 while (resize < size) {
266 bit_vector.resize(resize);
269 for (auto it = bit_vector.begin(); it != bit_vector.end(); ++it, ++offset) {
270 *it = offset % radix;
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);