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"
21 template <uint8_t _bit_count>
25 static const uint8_t BITS_PER_BYTE = 8;
26 static const uint32_t ELEMENTS_PER_BLOCK = BITS_PER_BYTE / _bit_count;
27 static const uint8_t MASK = static_cast<uint8_t>((1 << _bit_count) - 1);
30 BOOST_STATIC_ASSERT((_bit_count != 0) && !(_bit_count & (_bit_count - 1)));
31 BOOST_STATIC_ASSERT(_bit_count <= BITS_PER_BYTE);
33 template <typename DataIterator>
36 DataIterator m_data_iterator;
39 ReferenceImpl(const DataIterator& data_iterator, uint64_t shift)
40 : m_data_iterator(data_iterator), m_shift(shift) {
42 ReferenceImpl(DataIterator&& data_iterator, uint64_t shift)
43 : m_data_iterator(std::move(data_iterator)), m_shift(shift) {
47 inline operator uint8_t() const {
48 return (*m_data_iterator >> m_shift) & MASK;
54 class ConstReference : public ReferenceImpl<bufferlist::const_iterator> {
56 friend class BitVector;
58 ConstReference(const bufferlist::const_iterator& data_iterator,
60 : ReferenceImpl<bufferlist::const_iterator>(data_iterator, shift) {
62 ConstReference(bufferlist::const_iterator&& data_iterator, uint64_t shift)
63 : ReferenceImpl<bufferlist::const_iterator>(std::move(data_iterator),
68 class Reference : public ReferenceImpl<bufferlist::iterator> {
70 Reference& operator=(uint8_t v);
73 friend class BitVector;
75 Reference(const bufferlist::iterator& data_iterator, uint64_t shift)
76 : ReferenceImpl<bufferlist::iterator>(data_iterator, shift) {
78 Reference(bufferlist::iterator&& data_iterator, uint64_t shift)
79 : ReferenceImpl<bufferlist::iterator>(std::move(data_iterator), shift) {
84 template <typename BitVectorT, typename DataIterator>
87 friend class BitVector;
89 uint64_t m_offset = 0;
90 BitVectorT *m_bit_vector;
92 // cached derived values
95 DataIterator m_data_iterator;
97 IteratorImpl(BitVectorT *bit_vector, uint64_t offset)
98 : m_bit_vector(bit_vector),
99 m_data_iterator(bit_vector->m_data.begin()) {
104 inline IteratorImpl& operator++() {
108 compute_index(m_offset, &index, &m_shift);
110 assert(index == m_index || index == m_index + 1);
111 if (index > m_index) {
117 inline IteratorImpl& operator+=(uint64_t offset) {
119 compute_index(m_offset, &m_index, &m_shift);
120 if (m_offset < m_bit_vector->size()) {
121 m_data_iterator.seek(m_index);
123 m_data_iterator = m_bit_vector->m_data.end();
128 inline IteratorImpl operator++(int) {
129 IteratorImpl iterator_impl(*this);
131 return iterator_impl;
133 inline IteratorImpl operator+(uint64_t offset) {
134 IteratorImpl iterator_impl(*this);
135 iterator_impl += offset;
136 return iterator_impl;
139 inline bool operator==(const IteratorImpl& rhs) const {
140 return (m_offset == rhs.m_offset && m_bit_vector == rhs.m_bit_vector);
142 inline bool operator!=(const IteratorImpl& rhs) const {
143 return (m_offset != rhs.m_offset || m_bit_vector != rhs.m_bit_vector);
146 inline ConstReference operator*() const {
147 return ConstReference(m_data_iterator, m_shift);
149 inline Reference operator*() {
150 return Reference(m_data_iterator, m_shift);
154 typedef IteratorImpl<const BitVector,
155 bufferlist::const_iterator> ConstIterator;
156 typedef IteratorImpl<BitVector, bufferlist::iterator> Iterator;
158 static const uint32_t BLOCK_SIZE;
159 static const uint8_t BIT_COUNT = _bit_count;
163 inline ConstIterator begin() const {
164 return ConstIterator(this, 0);
166 inline ConstIterator end() const {
167 return ConstIterator(this, m_size);
169 inline Iterator begin() {
170 return Iterator(this, 0);
172 inline Iterator end() {
173 return Iterator(this, m_size);
176 void set_crc_enabled(bool enabled) {
177 m_crc_enabled = enabled;
181 void resize(uint64_t elements);
182 uint64_t size() const;
184 const bufferlist& get_data() const;
186 Reference operator[](uint64_t offset);
187 ConstReference operator[](uint64_t offset) const;
189 void encode_header(bufferlist& bl) const;
190 void decode_header(bufferlist::iterator& it);
191 uint64_t get_header_length() const;
193 void encode_data(bufferlist& bl, uint64_t byte_offset,
194 uint64_t byte_length) const;
195 void decode_data(bufferlist::iterator& it, uint64_t byte_offset);
196 void get_data_extents(uint64_t offset, uint64_t length,
197 uint64_t *byte_offset, uint64_t *byte_length) const;
199 void encode_footer(bufferlist& bl) const;
200 void decode_footer(bufferlist::iterator& it);
201 uint64_t get_footer_offset() const;
203 void encode(bufferlist& bl) const;
204 void decode(bufferlist::iterator& it);
205 void dump(Formatter *f) const;
207 bool operator==(const BitVector &b) const;
209 static void generate_test_instances(std::list<BitVector *> &o);
216 mutable __u32 m_header_crc;
217 mutable std::vector<__u32> m_data_crcs;
219 static void compute_index(uint64_t offset, uint64_t *index, uint64_t *shift);
223 template <uint8_t _b>
224 const uint32_t BitVector<_b>::BLOCK_SIZE = 4096;
226 template <uint8_t _b>
227 BitVector<_b>::BitVector() : m_size(0), m_crc_enabled(true), m_header_crc(0)
231 template <uint8_t _b>
232 void BitVector<_b>::clear() {
239 template <uint8_t _b>
240 void BitVector<_b>::resize(uint64_t size) {
241 uint64_t buffer_size = (size + ELEMENTS_PER_BLOCK - 1) / ELEMENTS_PER_BLOCK;
242 if (buffer_size > m_data.length()) {
243 m_data.append_zero(buffer_size - m_data.length());
244 } else if (buffer_size < m_data.length()) {
246 bl.substr_of(m_data, 0, buffer_size);
251 uint64_t block_count = (buffer_size + BLOCK_SIZE - 1) / BLOCK_SIZE;
252 m_data_crcs.resize(block_count);
255 template <uint8_t _b>
256 uint64_t BitVector<_b>::size() const {
260 template <uint8_t _b>
261 const bufferlist& BitVector<_b>::get_data() const {
265 template <uint8_t _b>
266 void BitVector<_b>::compute_index(uint64_t offset, uint64_t *index, uint64_t *shift) {
267 *index = offset / ELEMENTS_PER_BLOCK;
268 *shift = ((ELEMENTS_PER_BLOCK - 1) - (offset % ELEMENTS_PER_BLOCK)) * _b;
271 template <uint8_t _b>
272 void BitVector<_b>::encode_header(bufferlist& bl) const {
273 bufferlist header_bl;
274 ENCODE_START(1, 1, header_bl);
275 ::encode(m_size, header_bl);
276 ENCODE_FINISH(header_bl);
277 m_header_crc = header_bl.crc32c(0);
279 ::encode(header_bl, bl);
282 template <uint8_t _b>
283 void BitVector<_b>::decode_header(bufferlist::iterator& it) {
284 bufferlist header_bl;
285 ::decode(header_bl, it);
287 bufferlist::iterator header_it = header_bl.begin();
289 DECODE_START(1, header_it);
290 ::decode(size, header_it);
291 DECODE_FINISH(header_it);
294 m_header_crc = header_bl.crc32c(0);
297 template <uint8_t _b>
298 uint64_t BitVector<_b>::get_header_length() const {
299 // 4 byte bl length, 6 byte encoding header, 8 byte size
303 template <uint8_t _b>
304 void BitVector<_b>::encode_data(bufferlist& bl, uint64_t byte_offset,
305 uint64_t byte_length) const {
306 assert(byte_offset % BLOCK_SIZE == 0);
307 assert(byte_offset + byte_length == m_data.length() ||
308 byte_length % BLOCK_SIZE == 0);
310 uint64_t end_offset = byte_offset + byte_length;
311 while (byte_offset < end_offset) {
312 uint64_t len = MIN(BLOCK_SIZE, end_offset - byte_offset);
315 bit.substr_of(m_data, byte_offset, len);
316 m_data_crcs[byte_offset / BLOCK_SIZE] = bit.crc32c(0);
318 bl.claim_append(bit);
319 byte_offset += BLOCK_SIZE;
323 template <uint8_t _b>
324 void BitVector<_b>::decode_data(bufferlist::iterator& it, uint64_t byte_offset) {
325 assert(byte_offset % BLOCK_SIZE == 0);
330 uint64_t end_offset = byte_offset + it.get_remaining();
331 if (end_offset > m_data.length()) {
332 throw buffer::end_of_buffer();
336 if (byte_offset > 0) {
337 data.substr_of(m_data, 0, byte_offset);
340 while (byte_offset < end_offset) {
341 uint64_t len = MIN(BLOCK_SIZE, end_offset - byte_offset);
344 it.copy_deep(len, ptr);
349 m_data_crcs[byte_offset / BLOCK_SIZE] != bit.crc32c(0)) {
350 throw buffer::malformed_input("invalid data block CRC");
353 byte_offset += bit.length();
356 if (m_data.length() > end_offset) {
358 tail.substr_of(m_data, end_offset, m_data.length() - end_offset);
361 assert(data.length() == m_data.length());
365 template <uint8_t _b>
366 void BitVector<_b>::get_data_extents(uint64_t offset, uint64_t length,
367 uint64_t *byte_offset,
368 uint64_t *byte_length) const {
369 // read BLOCK_SIZE-aligned chunks
370 assert(length > 0 && offset + length <= m_size);
372 compute_index(offset, byte_offset, &shift);
373 *byte_offset -= (*byte_offset % BLOCK_SIZE);
376 compute_index(offset + length - 1, &end_offset, &shift);
377 end_offset += (BLOCK_SIZE - (end_offset % BLOCK_SIZE));
378 assert(*byte_offset <= end_offset);
380 *byte_length = end_offset - *byte_offset;
381 if (*byte_offset + *byte_length > m_data.length()) {
382 *byte_length = m_data.length() - *byte_offset;
386 template <uint8_t _b>
387 void BitVector<_b>::encode_footer(bufferlist& bl) const {
388 bufferlist footer_bl;
390 ::encode(m_header_crc, footer_bl);
391 ::encode(m_data_crcs, footer_bl);
393 ::encode(footer_bl, bl);
396 template <uint8_t _b>
397 void BitVector<_b>::decode_footer(bufferlist::iterator& it) {
398 bufferlist footer_bl;
399 ::decode(footer_bl, it);
401 m_crc_enabled = (footer_bl.length() > 0);
403 bufferlist::iterator footer_it = footer_bl.begin();
406 ::decode(header_crc, footer_it);
407 if (m_header_crc != header_crc) {
408 throw buffer::malformed_input("incorrect header CRC");
411 uint64_t block_count = (m_data.length() + BLOCK_SIZE - 1) / BLOCK_SIZE;
412 ::decode(m_data_crcs, footer_it);
413 if (m_data_crcs.size() != block_count) {
414 throw buffer::malformed_input("invalid data block CRCs");
419 template <uint8_t _b>
420 uint64_t BitVector<_b>::get_footer_offset() const {
421 return get_header_length() + m_data.length();
424 template <uint8_t _b>
425 void BitVector<_b>::encode(bufferlist& bl) const {
427 encode_data(bl, 0, m_data.length());
431 template <uint8_t _b>
432 void BitVector<_b>::decode(bufferlist::iterator& it) {
436 if (m_data.length() > 0) {
437 it.copy(m_data.length(), data_bl);
442 bufferlist::iterator data_it = data_bl.begin();
443 decode_data(data_it, 0);
446 template <uint8_t _b>
447 void BitVector<_b>::dump(Formatter *f) const {
448 f->dump_unsigned("size", m_size);
449 f->open_array_section("bit_table");
450 for (unsigned i = 0; i < m_data.length(); ++i) {
451 f->dump_format("byte", "0x%02hhX", m_data[i]);
456 template <uint8_t _b>
457 bool BitVector<_b>::operator==(const BitVector &b) const {
458 return (this->m_size == b.m_size && this->m_data == b.m_data);
461 template <uint8_t _b>
462 typename BitVector<_b>::Reference BitVector<_b>::operator[](uint64_t offset) {
465 compute_index(offset, &index, &shift);
467 bufferlist::iterator data_iterator(m_data.begin());
468 data_iterator.seek(index);
469 return Reference(std::move(data_iterator), shift);
472 template <uint8_t _b>
473 typename BitVector<_b>::ConstReference BitVector<_b>::operator[](uint64_t offset) const {
476 compute_index(offset, &index, &shift);
478 bufferlist::const_iterator data_iterator(m_data.begin());
479 data_iterator.seek(index);
480 return ConstReference(std::move(data_iterator), shift);
483 template <uint8_t _b>
484 typename BitVector<_b>::Reference& BitVector<_b>::Reference::operator=(uint8_t v) {
485 uint8_t mask = MASK << this->m_shift;
486 char packed_value = (*this->m_data_iterator & ~mask) |
487 ((v << this->m_shift) & mask);
488 bufferlist::iterator it(this->m_data_iterator);
489 it.copy_in(1, &packed_value, true);
493 template <uint8_t _b>
494 void BitVector<_b>::generate_test_instances(std::list<BitVector *> &o) {
495 o.push_back(new BitVector());
497 BitVector *b = new BitVector();
498 const uint64_t radix = 1 << b->BIT_COUNT;
499 const uint64_t size = 1024;
502 for (uint64_t i = 0; i < size; ++i) {
503 (*b)[i] = rand() % radix;
510 WRITE_CLASS_ENCODER(ceph::BitVector<2>)
512 template <uint8_t _b>
513 inline std::ostream& operator<<(std::ostream& out, const ceph::BitVector<_b> &b)
515 out << "ceph::BitVector<" << _b << ">(size=" << b.size() << ", data="
516 << b.get_data() << ")";
520 #endif // BIT_VECTOR_HPP