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 #ifndef BIT_VECTOR_HPP
12 #define BIT_VECTOR_HPP
14 #include "common/Formatter.h"
15 #include "include/assert.h"
16 #include "include/encoding.h"
20 template <uint8_t _bit_count>
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);
29 BOOST_STATIC_ASSERT((_bit_count != 0) && !(_bit_count & (_bit_count - 1)));
30 BOOST_STATIC_ASSERT(_bit_count <= BITS_PER_BYTE);
32 static const uint32_t BLOCK_SIZE;
34 class ConstReference {
36 operator uint8_t() const;
38 friend class BitVector;
39 const BitVector &m_bit_vector;
42 ConstReference(const BitVector &bit_vector, uint64_t offset);
47 operator uint8_t() const;
48 Reference& operator=(uint8_t v);
50 friend class BitVector;
51 BitVector &m_bit_vector;
54 Reference(BitVector &bit_vector, uint64_t offset);
57 static const uint8_t BIT_COUNT = _bit_count;
61 void set_crc_enabled(bool enabled) {
62 m_crc_enabled = enabled;
66 void resize(uint64_t elements);
67 uint64_t size() const;
69 const bufferlist& get_data() const;
71 Reference operator[](uint64_t offset);
72 ConstReference operator[](uint64_t offset) const;
74 void encode_header(bufferlist& bl) const;
75 void decode_header(bufferlist::iterator& it);
76 uint64_t get_header_length() const;
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;
84 void encode_footer(bufferlist& bl) const;
85 void decode_footer(bufferlist::iterator& it);
86 uint64_t get_footer_offset() const;
88 void encode(bufferlist& bl) const;
89 void decode(bufferlist::iterator& it);
90 void dump(Formatter *f) const;
92 bool operator==(const BitVector &b) const;
94 static void generate_test_instances(std::list<BitVector *> &o);
101 mutable __u32 m_header_crc;
102 mutable std::vector<__u32> m_data_crcs;
104 static void compute_index(uint64_t offset, uint64_t *index, uint64_t *shift);
108 template <uint8_t _b>
109 const uint32_t BitVector<_b>::BLOCK_SIZE = 4096;
111 template <uint8_t _b>
112 BitVector<_b>::BitVector() : m_size(0), m_crc_enabled(true), m_header_crc(0)
116 template <uint8_t _b>
117 void BitVector<_b>::clear() {
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()) {
131 bl.substr_of(m_data, 0, buffer_size);
136 uint64_t block_count = (buffer_size + BLOCK_SIZE - 1) / BLOCK_SIZE;
137 m_data_crcs.resize(block_count);
140 template <uint8_t _b>
141 uint64_t BitVector<_b>::size() const {
145 template <uint8_t _b>
146 const bufferlist& BitVector<_b>::get_data() const {
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;
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);
164 ::encode(header_bl, bl);
167 template <uint8_t _b>
168 void BitVector<_b>::decode_header(bufferlist::iterator& it) {
169 bufferlist header_bl;
170 ::decode(header_bl, it);
172 bufferlist::iterator header_it = header_bl.begin();
174 DECODE_START(1, header_it);
175 ::decode(size, header_it);
176 DECODE_FINISH(header_it);
179 m_header_crc = header_bl.crc32c(0);
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
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);
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);
200 bit.substr_of(m_data, byte_offset, len);
201 m_data_crcs[byte_offset / BLOCK_SIZE] = bit.crc32c(0);
203 bl.claim_append(bit);
204 byte_offset += BLOCK_SIZE;
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);
215 uint64_t end_offset = byte_offset + it.get_remaining();
216 if (end_offset > m_data.length()) {
217 throw buffer::end_of_buffer();
221 if (byte_offset > 0) {
222 data.substr_of(m_data, 0, byte_offset);
225 while (byte_offset < end_offset) {
226 uint64_t len = MIN(BLOCK_SIZE, end_offset - byte_offset);
229 it.copy_deep(len, ptr);
234 m_data_crcs[byte_offset / BLOCK_SIZE] != bit.crc32c(0)) {
235 throw buffer::malformed_input("invalid data block CRC");
238 byte_offset += bit.length();
241 if (m_data.length() > end_offset) {
243 tail.substr_of(m_data, end_offset, m_data.length() - end_offset);
246 assert(data.length() == m_data.length());
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);
257 compute_index(offset, byte_offset, &shift);
258 *byte_offset -= (*byte_offset % BLOCK_SIZE);
261 compute_index(offset + length - 1, &end_offset, &shift);
262 end_offset += (BLOCK_SIZE - (end_offset % BLOCK_SIZE));
263 assert(*byte_offset <= end_offset);
265 *byte_length = end_offset - *byte_offset;
266 if (*byte_offset + *byte_length > m_data.length()) {
267 *byte_length = m_data.length() - *byte_offset;
271 template <uint8_t _b>
272 void BitVector<_b>::encode_footer(bufferlist& bl) const {
273 bufferlist footer_bl;
275 ::encode(m_header_crc, footer_bl);
276 ::encode(m_data_crcs, footer_bl);
278 ::encode(footer_bl, bl);
281 template <uint8_t _b>
282 void BitVector<_b>::decode_footer(bufferlist::iterator& it) {
283 bufferlist footer_bl;
284 ::decode(footer_bl, it);
286 m_crc_enabled = (footer_bl.length() > 0);
288 bufferlist::iterator footer_it = footer_bl.begin();
291 ::decode(header_crc, footer_it);
292 if (m_header_crc != header_crc) {
293 throw buffer::malformed_input("incorrect header CRC");
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");
304 template <uint8_t _b>
305 uint64_t BitVector<_b>::get_footer_offset() const {
306 return get_header_length() + m_data.length();
309 template <uint8_t _b>
310 void BitVector<_b>::encode(bufferlist& bl) const {
312 encode_data(bl, 0, m_data.length());
316 template <uint8_t _b>
317 void BitVector<_b>::decode(bufferlist::iterator& it) {
321 if (m_data.length() > 0) {
322 it.copy(m_data.length(), data_bl);
327 bufferlist::iterator data_it = data_bl.begin();
328 decode_data(data_it, 0);
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]);
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);
346 template <uint8_t _b>
347 typename BitVector<_b>::Reference BitVector<_b>::operator[](uint64_t offset) {
348 return Reference(*this, offset);
351 template <uint8_t _b>
352 typename BitVector<_b>::ConstReference BitVector<_b>::operator[](uint64_t offset) const {
353 return ConstReference(*this, offset);
356 template <uint8_t _b>
357 BitVector<_b>::ConstReference::ConstReference(const BitVector<_b> &bit_vector,
359 : m_bit_vector(bit_vector), m_offset(offset)
363 template <uint8_t _b>
364 BitVector<_b>::ConstReference::operator uint8_t() const {
367 this->m_bit_vector.compute_index(this->m_offset, &index, &shift);
369 return (this->m_bit_vector.m_data[index] >> shift) & MASK;
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)
378 template <uint8_t _b>
379 BitVector<_b>::Reference::operator uint8_t() const {
382 this->m_bit_vector.compute_index(this->m_offset, &index, &shift);
384 return (this->m_bit_vector.m_data[index] >> shift) & MASK;
387 template <uint8_t _b>
388 typename BitVector<_b>::Reference& BitVector<_b>::Reference::operator=(uint8_t v) {
391 this->m_bit_vector.compute_index(this->m_offset, &index, &shift);
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);
400 template <uint8_t _b>
401 void BitVector<_b>::generate_test_instances(std::list<BitVector *> &o) {
402 o.push_back(new BitVector());
404 BitVector *b = new BitVector();
405 const uint64_t radix = 1 << b->BIT_COUNT;
406 const uint64_t size = 1024;
409 for (uint64_t i = 0; i < size; ++i) {
410 (*b)[i] = rand() % radix;
417 WRITE_CLASS_ENCODER(ceph::BitVector<2>)
419 template <uint8_t _b>
420 inline std::ostream& operator<<(std::ostream& out, const ceph::BitVector<_b> &b)
422 out << "ceph::BitVector<" << _b << ">(size=" << b.size() << ", data="
423 << b.get_data() << ")";
427 #endif // BIT_VECTOR_HPP