]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
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" | |
11fdf7f2 | 15 | #include "include/ceph_assert.h" |
7c673cae | 16 | #include "include/encoding.h" |
11fdf7f2 | 17 | #include <memory> |
3efd9988 | 18 | #include <utility> |
11fdf7f2 | 19 | #include <vector> |
7c673cae FG |
20 | |
21 | namespace ceph { | |
22 | ||
23 | template <uint8_t _bit_count> | |
24 | class BitVector | |
25 | { | |
26 | private: | |
27 | static const uint8_t BITS_PER_BYTE = 8; | |
28 | static const uint32_t ELEMENTS_PER_BLOCK = BITS_PER_BYTE / _bit_count; | |
29 | static const uint8_t MASK = static_cast<uint8_t>((1 << _bit_count) - 1); | |
30 | ||
31 | // must be power of 2 | |
32 | BOOST_STATIC_ASSERT((_bit_count != 0) && !(_bit_count & (_bit_count - 1))); | |
33 | BOOST_STATIC_ASSERT(_bit_count <= BITS_PER_BYTE); | |
7c673cae | 34 | |
3efd9988 FG |
35 | template <typename DataIterator> |
36 | class ReferenceImpl { | |
37 | protected: | |
38 | DataIterator m_data_iterator; | |
39 | uint64_t m_shift; | |
40 | ||
41 | ReferenceImpl(const DataIterator& data_iterator, uint64_t shift) | |
42 | : m_data_iterator(data_iterator), m_shift(shift) { | |
43 | } | |
44 | ReferenceImpl(DataIterator&& data_iterator, uint64_t shift) | |
45 | : m_data_iterator(std::move(data_iterator)), m_shift(shift) { | |
46 | } | |
47 | ||
7c673cae | 48 | public: |
3efd9988 FG |
49 | inline operator uint8_t() const { |
50 | return (*m_data_iterator >> m_shift) & MASK; | |
51 | } | |
52 | }; | |
53 | ||
54 | public: | |
55 | ||
56 | class ConstReference : public ReferenceImpl<bufferlist::const_iterator> { | |
7c673cae FG |
57 | private: |
58 | friend class BitVector; | |
7c673cae | 59 | |
3efd9988 FG |
60 | ConstReference(const bufferlist::const_iterator& data_iterator, |
61 | uint64_t shift) | |
62 | : ReferenceImpl<bufferlist::const_iterator>(data_iterator, shift) { | |
63 | } | |
64 | ConstReference(bufferlist::const_iterator&& data_iterator, uint64_t shift) | |
65 | : ReferenceImpl<bufferlist::const_iterator>(std::move(data_iterator), | |
66 | shift) { | |
67 | } | |
7c673cae FG |
68 | }; |
69 | ||
3efd9988 | 70 | class Reference : public ReferenceImpl<bufferlist::iterator> { |
7c673cae | 71 | public: |
7c673cae | 72 | Reference& operator=(uint8_t v); |
3efd9988 FG |
73 | |
74 | private: | |
75 | friend class BitVector; | |
76 | ||
77 | Reference(const bufferlist::iterator& data_iterator, uint64_t shift) | |
78 | : ReferenceImpl<bufferlist::iterator>(data_iterator, shift) { | |
79 | } | |
80 | Reference(bufferlist::iterator&& data_iterator, uint64_t shift) | |
81 | : ReferenceImpl<bufferlist::iterator>(std::move(data_iterator), shift) { | |
82 | } | |
83 | }; | |
84 | ||
85 | public: | |
86 | template <typename BitVectorT, typename DataIterator> | |
87 | class IteratorImpl { | |
7c673cae FG |
88 | private: |
89 | friend class BitVector; | |
7c673cae | 90 | |
3efd9988 FG |
91 | uint64_t m_offset = 0; |
92 | BitVectorT *m_bit_vector; | |
93 | ||
94 | // cached derived values | |
95 | uint64_t m_index = 0; | |
96 | uint64_t m_shift = 0; | |
97 | DataIterator m_data_iterator; | |
98 | ||
99 | IteratorImpl(BitVectorT *bit_vector, uint64_t offset) | |
100 | : m_bit_vector(bit_vector), | |
101 | m_data_iterator(bit_vector->m_data.begin()) { | |
102 | *this += offset; | |
103 | } | |
104 | ||
105 | public: | |
106 | inline IteratorImpl& operator++() { | |
107 | ++m_offset; | |
108 | ||
109 | uint64_t index; | |
110 | compute_index(m_offset, &index, &m_shift); | |
111 | ||
11fdf7f2 | 112 | ceph_assert(index == m_index || index == m_index + 1); |
3efd9988 FG |
113 | if (index > m_index) { |
114 | m_index = index; | |
115 | ++m_data_iterator; | |
116 | } | |
117 | return *this; | |
118 | } | |
119 | inline IteratorImpl& operator+=(uint64_t offset) { | |
120 | m_offset += offset; | |
121 | compute_index(m_offset, &m_index, &m_shift); | |
122 | if (m_offset < m_bit_vector->size()) { | |
123 | m_data_iterator.seek(m_index); | |
124 | } else { | |
125 | m_data_iterator = m_bit_vector->m_data.end(); | |
126 | } | |
127 | return *this; | |
128 | } | |
129 | ||
130 | inline IteratorImpl operator++(int) { | |
131 | IteratorImpl iterator_impl(*this); | |
132 | ++iterator_impl; | |
133 | return iterator_impl; | |
134 | } | |
135 | inline IteratorImpl operator+(uint64_t offset) { | |
136 | IteratorImpl iterator_impl(*this); | |
137 | iterator_impl += offset; | |
138 | return iterator_impl; | |
139 | } | |
140 | ||
141 | inline bool operator==(const IteratorImpl& rhs) const { | |
142 | return (m_offset == rhs.m_offset && m_bit_vector == rhs.m_bit_vector); | |
143 | } | |
144 | inline bool operator!=(const IteratorImpl& rhs) const { | |
145 | return (m_offset != rhs.m_offset || m_bit_vector != rhs.m_bit_vector); | |
146 | } | |
147 | ||
148 | inline ConstReference operator*() const { | |
149 | return ConstReference(m_data_iterator, m_shift); | |
150 | } | |
151 | inline Reference operator*() { | |
152 | return Reference(m_data_iterator, m_shift); | |
153 | } | |
7c673cae FG |
154 | }; |
155 | ||
3efd9988 FG |
156 | typedef IteratorImpl<const BitVector, |
157 | bufferlist::const_iterator> ConstIterator; | |
158 | typedef IteratorImpl<BitVector, bufferlist::iterator> Iterator; | |
159 | ||
160 | static const uint32_t BLOCK_SIZE; | |
7c673cae FG |
161 | static const uint8_t BIT_COUNT = _bit_count; |
162 | ||
163 | BitVector(); | |
164 | ||
3efd9988 FG |
165 | inline ConstIterator begin() const { |
166 | return ConstIterator(this, 0); | |
167 | } | |
168 | inline ConstIterator end() const { | |
169 | return ConstIterator(this, m_size); | |
170 | } | |
171 | inline Iterator begin() { | |
172 | return Iterator(this, 0); | |
173 | } | |
174 | inline Iterator end() { | |
175 | return Iterator(this, m_size); | |
176 | } | |
177 | ||
7c673cae FG |
178 | void set_crc_enabled(bool enabled) { |
179 | m_crc_enabled = enabled; | |
180 | } | |
181 | void clear(); | |
182 | ||
183 | void resize(uint64_t elements); | |
184 | uint64_t size() const; | |
185 | ||
186 | const bufferlist& get_data() const; | |
187 | ||
188 | Reference operator[](uint64_t offset); | |
189 | ConstReference operator[](uint64_t offset) const; | |
190 | ||
191 | void encode_header(bufferlist& bl) const; | |
11fdf7f2 | 192 | void decode_header(bufferlist::const_iterator& it); |
7c673cae FG |
193 | uint64_t get_header_length() const; |
194 | ||
11fdf7f2 | 195 | void encode_data(bufferlist& bl, uint64_t data_byte_offset, |
7c673cae | 196 | uint64_t byte_length) const; |
11fdf7f2 | 197 | void decode_data(bufferlist::const_iterator& it, uint64_t data_byte_offset); |
7c673cae | 198 | void get_data_extents(uint64_t offset, uint64_t length, |
11fdf7f2 TL |
199 | uint64_t *data_byte_offset, |
200 | uint64_t *object_byte_offset, | |
201 | uint64_t *byte_length) const; | |
7c673cae FG |
202 | |
203 | void encode_footer(bufferlist& bl) const; | |
11fdf7f2 | 204 | void decode_footer(bufferlist::const_iterator& it); |
7c673cae FG |
205 | uint64_t get_footer_offset() const; |
206 | ||
11fdf7f2 TL |
207 | void decode_header_crc(bufferlist::const_iterator& it); |
208 | void get_header_crc_extents(uint64_t *byte_offset, | |
209 | uint64_t *byte_length) const; | |
210 | ||
211 | void encode_data_crcs(bufferlist& bl, uint64_t offset, | |
212 | uint64_t length) const; | |
213 | void decode_data_crcs(bufferlist::const_iterator& it, uint64_t offset); | |
214 | void get_data_crcs_extents(uint64_t offset, uint64_t length, | |
215 | uint64_t *byte_offset, | |
216 | uint64_t *byte_length) const; | |
217 | ||
7c673cae | 218 | void encode(bufferlist& bl) const; |
11fdf7f2 | 219 | void decode(bufferlist::const_iterator& it); |
7c673cae FG |
220 | void dump(Formatter *f) const; |
221 | ||
222 | bool operator==(const BitVector &b) const; | |
223 | ||
224 | static void generate_test_instances(std::list<BitVector *> &o); | |
225 | private: | |
7c673cae FG |
226 | bufferlist m_data; |
227 | uint64_t m_size; | |
228 | bool m_crc_enabled; | |
229 | ||
230 | mutable __u32 m_header_crc; | |
20effc67 TL |
231 | |
232 | // inhibit value-initialization when used in std::vector | |
233 | struct u32_struct { | |
234 | u32_struct() {} | |
235 | __u32 val; | |
236 | }; | |
237 | mutable std::vector<u32_struct> m_data_crcs; | |
11fdf7f2 TL |
238 | |
239 | void resize(uint64_t elements, bool zero); | |
7c673cae FG |
240 | |
241 | static void compute_index(uint64_t offset, uint64_t *index, uint64_t *shift); | |
242 | ||
243 | }; | |
244 | ||
245 | template <uint8_t _b> | |
246 | const uint32_t BitVector<_b>::BLOCK_SIZE = 4096; | |
247 | ||
248 | template <uint8_t _b> | |
249 | BitVector<_b>::BitVector() : m_size(0), m_crc_enabled(true), m_header_crc(0) | |
250 | { | |
251 | } | |
252 | ||
253 | template <uint8_t _b> | |
254 | void BitVector<_b>::clear() { | |
255 | m_data.clear(); | |
256 | m_data_crcs.clear(); | |
257 | m_size = 0; | |
258 | m_header_crc = 0; | |
259 | } | |
260 | ||
261 | template <uint8_t _b> | |
262 | void BitVector<_b>::resize(uint64_t size) { | |
11fdf7f2 TL |
263 | resize(size, true); |
264 | } | |
265 | ||
266 | template <uint8_t _b> | |
267 | void BitVector<_b>::resize(uint64_t size, bool zero) { | |
7c673cae FG |
268 | uint64_t buffer_size = (size + ELEMENTS_PER_BLOCK - 1) / ELEMENTS_PER_BLOCK; |
269 | if (buffer_size > m_data.length()) { | |
11fdf7f2 TL |
270 | if (zero) { |
271 | m_data.append_zero(buffer_size - m_data.length()); | |
272 | } else { | |
9f95a23c | 273 | m_data.append(buffer::ptr(buffer_size - m_data.length())); |
11fdf7f2 | 274 | } |
7c673cae FG |
275 | } else if (buffer_size < m_data.length()) { |
276 | bufferlist bl; | |
277 | bl.substr_of(m_data, 0, buffer_size); | |
278 | bl.swap(m_data); | |
279 | } | |
280 | m_size = size; | |
281 | ||
282 | uint64_t block_count = (buffer_size + BLOCK_SIZE - 1) / BLOCK_SIZE; | |
283 | m_data_crcs.resize(block_count); | |
284 | } | |
285 | ||
286 | template <uint8_t _b> | |
287 | uint64_t BitVector<_b>::size() const { | |
288 | return m_size; | |
289 | } | |
290 | ||
291 | template <uint8_t _b> | |
292 | const bufferlist& BitVector<_b>::get_data() const { | |
293 | return m_data; | |
294 | } | |
295 | ||
296 | template <uint8_t _b> | |
297 | void BitVector<_b>::compute_index(uint64_t offset, uint64_t *index, uint64_t *shift) { | |
298 | *index = offset / ELEMENTS_PER_BLOCK; | |
299 | *shift = ((ELEMENTS_PER_BLOCK - 1) - (offset % ELEMENTS_PER_BLOCK)) * _b; | |
300 | } | |
301 | ||
302 | template <uint8_t _b> | |
303 | void BitVector<_b>::encode_header(bufferlist& bl) const { | |
304 | bufferlist header_bl; | |
305 | ENCODE_START(1, 1, header_bl); | |
11fdf7f2 | 306 | encode(m_size, header_bl); |
7c673cae FG |
307 | ENCODE_FINISH(header_bl); |
308 | m_header_crc = header_bl.crc32c(0); | |
309 | ||
11fdf7f2 | 310 | encode(header_bl, bl); |
7c673cae FG |
311 | } |
312 | ||
313 | template <uint8_t _b> | |
11fdf7f2 TL |
314 | void BitVector<_b>::decode_header(bufferlist::const_iterator& it) { |
315 | using ceph::decode; | |
7c673cae | 316 | bufferlist header_bl; |
11fdf7f2 | 317 | decode(header_bl, it); |
7c673cae | 318 | |
11fdf7f2 | 319 | auto header_it = header_bl.cbegin(); |
7c673cae FG |
320 | uint64_t size; |
321 | DECODE_START(1, header_it); | |
11fdf7f2 | 322 | decode(size, header_it); |
7c673cae FG |
323 | DECODE_FINISH(header_it); |
324 | ||
11fdf7f2 | 325 | resize(size, false); |
7c673cae FG |
326 | m_header_crc = header_bl.crc32c(0); |
327 | } | |
328 | ||
329 | template <uint8_t _b> | |
330 | uint64_t BitVector<_b>::get_header_length() const { | |
331 | // 4 byte bl length, 6 byte encoding header, 8 byte size | |
332 | return 18; | |
333 | } | |
334 | ||
335 | template <uint8_t _b> | |
11fdf7f2 | 336 | void BitVector<_b>::encode_data(bufferlist& bl, uint64_t data_byte_offset, |
7c673cae | 337 | uint64_t byte_length) const { |
11fdf7f2 TL |
338 | ceph_assert(data_byte_offset % BLOCK_SIZE == 0); |
339 | ceph_assert(data_byte_offset + byte_length == m_data.length() || | |
340 | byte_length % BLOCK_SIZE == 0); | |
7c673cae | 341 | |
11fdf7f2 TL |
342 | uint64_t end_offset = data_byte_offset + byte_length; |
343 | while (data_byte_offset < end_offset) { | |
344 | uint64_t len = std::min<uint64_t>(BLOCK_SIZE, | |
345 | end_offset - data_byte_offset); | |
7c673cae FG |
346 | |
347 | bufferlist bit; | |
11fdf7f2 | 348 | bit.substr_of(m_data, data_byte_offset, len); |
20effc67 | 349 | m_data_crcs[data_byte_offset / BLOCK_SIZE].val = bit.crc32c(0); |
7c673cae FG |
350 | |
351 | bl.claim_append(bit); | |
11fdf7f2 | 352 | data_byte_offset += BLOCK_SIZE; |
7c673cae FG |
353 | } |
354 | } | |
355 | ||
356 | template <uint8_t _b> | |
11fdf7f2 TL |
357 | void BitVector<_b>::decode_data(bufferlist::const_iterator& it, |
358 | uint64_t data_byte_offset) { | |
359 | ceph_assert(data_byte_offset % BLOCK_SIZE == 0); | |
7c673cae FG |
360 | if (it.end()) { |
361 | return; | |
362 | } | |
363 | ||
11fdf7f2 | 364 | uint64_t end_offset = data_byte_offset + it.get_remaining(); |
7c673cae FG |
365 | if (end_offset > m_data.length()) { |
366 | throw buffer::end_of_buffer(); | |
367 | } | |
368 | ||
369 | bufferlist data; | |
11fdf7f2 TL |
370 | if (data_byte_offset > 0) { |
371 | data.substr_of(m_data, 0, data_byte_offset); | |
7c673cae FG |
372 | } |
373 | ||
11fdf7f2 TL |
374 | while (data_byte_offset < end_offset) { |
375 | uint64_t len = std::min<uint64_t>(BLOCK_SIZE, end_offset - data_byte_offset); | |
7c673cae FG |
376 | |
377 | bufferptr ptr; | |
378 | it.copy_deep(len, ptr); | |
379 | ||
380 | bufferlist bit; | |
381 | bit.append(ptr); | |
382 | if (m_crc_enabled && | |
20effc67 | 383 | m_data_crcs[data_byte_offset / BLOCK_SIZE].val != bit.crc32c(0)) { |
7c673cae FG |
384 | throw buffer::malformed_input("invalid data block CRC"); |
385 | } | |
386 | data.append(bit); | |
11fdf7f2 | 387 | data_byte_offset += bit.length(); |
7c673cae FG |
388 | } |
389 | ||
390 | if (m_data.length() > end_offset) { | |
391 | bufferlist tail; | |
392 | tail.substr_of(m_data, end_offset, m_data.length() - end_offset); | |
393 | data.append(tail); | |
394 | } | |
11fdf7f2 | 395 | ceph_assert(data.length() == m_data.length()); |
7c673cae FG |
396 | data.swap(m_data); |
397 | } | |
398 | ||
399 | template <uint8_t _b> | |
400 | void BitVector<_b>::get_data_extents(uint64_t offset, uint64_t length, | |
11fdf7f2 TL |
401 | uint64_t *data_byte_offset, |
402 | uint64_t *object_byte_offset, | |
403 | uint64_t *byte_length) const { | |
7c673cae | 404 | // read BLOCK_SIZE-aligned chunks |
11fdf7f2 | 405 | ceph_assert(length > 0 && offset + length <= m_size); |
7c673cae | 406 | uint64_t shift; |
11fdf7f2 TL |
407 | compute_index(offset, data_byte_offset, &shift); |
408 | *data_byte_offset -= (*data_byte_offset % BLOCK_SIZE); | |
7c673cae FG |
409 | |
410 | uint64_t end_offset; | |
411 | compute_index(offset + length - 1, &end_offset, &shift); | |
412 | end_offset += (BLOCK_SIZE - (end_offset % BLOCK_SIZE)); | |
11fdf7f2 | 413 | ceph_assert(*data_byte_offset <= end_offset); |
7c673cae | 414 | |
11fdf7f2 TL |
415 | *object_byte_offset = get_header_length() + *data_byte_offset; |
416 | *byte_length = end_offset - *data_byte_offset; | |
417 | if (*data_byte_offset + *byte_length > m_data.length()) { | |
418 | *byte_length = m_data.length() - *data_byte_offset; | |
7c673cae FG |
419 | } |
420 | } | |
421 | ||
422 | template <uint8_t _b> | |
423 | void BitVector<_b>::encode_footer(bufferlist& bl) const { | |
11fdf7f2 | 424 | using ceph::encode; |
7c673cae FG |
425 | bufferlist footer_bl; |
426 | if (m_crc_enabled) { | |
11fdf7f2 TL |
427 | encode(m_header_crc, footer_bl); |
428 | ||
429 | __u32 size = m_data_crcs.size(); | |
430 | encode(size, footer_bl); | |
431 | encode_data_crcs(footer_bl, 0, m_size); | |
7c673cae | 432 | } |
11fdf7f2 | 433 | encode(footer_bl, bl); |
7c673cae FG |
434 | } |
435 | ||
436 | template <uint8_t _b> | |
11fdf7f2 TL |
437 | void BitVector<_b>::decode_footer(bufferlist::const_iterator& it) { |
438 | using ceph::decode; | |
7c673cae | 439 | bufferlist footer_bl; |
11fdf7f2 | 440 | decode(footer_bl, it); |
7c673cae FG |
441 | |
442 | m_crc_enabled = (footer_bl.length() > 0); | |
443 | if (m_crc_enabled) { | |
11fdf7f2 TL |
444 | auto footer_it = footer_bl.cbegin(); |
445 | decode_header_crc(footer_it); | |
7c673cae | 446 | |
11fdf7f2 TL |
447 | __u32 data_src_size; |
448 | decode(data_src_size, footer_it); | |
449 | decode_data_crcs(footer_it, 0); | |
7c673cae FG |
450 | |
451 | uint64_t block_count = (m_data.length() + BLOCK_SIZE - 1) / BLOCK_SIZE; | |
7c673cae FG |
452 | if (m_data_crcs.size() != block_count) { |
453 | throw buffer::malformed_input("invalid data block CRCs"); | |
454 | } | |
455 | } | |
456 | } | |
457 | ||
458 | template <uint8_t _b> | |
459 | uint64_t BitVector<_b>::get_footer_offset() const { | |
460 | return get_header_length() + m_data.length(); | |
461 | } | |
462 | ||
11fdf7f2 TL |
463 | template <uint8_t _b> |
464 | void BitVector<_b>::decode_header_crc(bufferlist::const_iterator& it) { | |
465 | if (it.get_remaining() > 0) { | |
466 | __u32 header_crc; | |
467 | ceph::decode(header_crc, it); | |
468 | if (m_header_crc != header_crc) { | |
469 | throw buffer::malformed_input("incorrect header CRC"); | |
470 | } | |
471 | } | |
472 | } | |
473 | ||
474 | template <uint8_t _b> | |
475 | void BitVector<_b>::get_header_crc_extents(uint64_t *byte_offset, | |
476 | uint64_t *byte_length) const { | |
477 | // footer is prefixed with a bufferlist length | |
478 | *byte_offset = get_footer_offset() + sizeof(__u32); | |
479 | *byte_length = sizeof(__u32); | |
480 | } | |
481 | ||
482 | template <uint8_t _b> | |
483 | void BitVector<_b>::encode_data_crcs(bufferlist& bl, uint64_t offset, | |
484 | uint64_t length) const { | |
485 | if (length == 0) { | |
486 | return; | |
487 | } | |
488 | ||
489 | uint64_t index; | |
490 | uint64_t shift; | |
491 | compute_index(offset, &index, &shift); | |
492 | uint64_t crc_index = index / BLOCK_SIZE; | |
493 | ||
494 | compute_index(offset + length - 1, &index, &shift); | |
495 | uint64_t end_crc_index = index / BLOCK_SIZE; | |
496 | while (crc_index <= end_crc_index) { | |
20effc67 | 497 | __u32 crc = m_data_crcs[crc_index++].val; |
11fdf7f2 TL |
498 | ceph::encode(crc, bl); |
499 | } | |
500 | } | |
501 | ||
502 | template <uint8_t _b> | |
503 | void BitVector<_b>::decode_data_crcs(bufferlist::const_iterator& it, | |
504 | uint64_t offset) { | |
505 | if (it.end()) { | |
506 | return; | |
507 | } | |
508 | ||
509 | uint64_t index; | |
510 | uint64_t shift; | |
511 | compute_index(offset, &index, &shift); | |
512 | ||
513 | uint64_t crc_index = index / BLOCK_SIZE; | |
514 | uint64_t remaining = it.get_remaining() / sizeof(__u32); | |
515 | while (remaining > 0) { | |
516 | __u32 crc; | |
517 | ceph::decode(crc, it); | |
20effc67 | 518 | m_data_crcs[crc_index++].val = crc; |
11fdf7f2 TL |
519 | --remaining; |
520 | } | |
521 | } | |
522 | ||
523 | template <uint8_t _b> | |
524 | void BitVector<_b>::get_data_crcs_extents(uint64_t offset, uint64_t length, | |
525 | uint64_t *byte_offset, | |
526 | uint64_t *byte_length) const { | |
527 | // data CRCs immediately follow the header CRC | |
528 | get_header_crc_extents(byte_offset, byte_length); | |
529 | *byte_offset += *byte_length; | |
530 | ||
531 | // skip past data CRC vector size | |
532 | *byte_offset += sizeof(__u32); | |
533 | ||
534 | // CRCs are computed over BLOCK_SIZE chunks | |
535 | ceph_assert(length > 0 && offset + length <= m_size); | |
536 | uint64_t index; | |
537 | uint64_t shift; | |
538 | compute_index(offset, &index, &shift); | |
539 | uint64_t start_byte_offset = | |
540 | *byte_offset + ((index / BLOCK_SIZE) * sizeof(__u32)); | |
541 | ||
542 | compute_index(offset + length, &index, &shift); | |
543 | uint64_t end_byte_offset = | |
544 | *byte_offset + (((index / BLOCK_SIZE) + 1) * sizeof(__u32)); | |
545 | ceph_assert(start_byte_offset < end_byte_offset); | |
546 | ||
547 | *byte_offset = start_byte_offset; | |
548 | *byte_length = end_byte_offset - start_byte_offset; | |
549 | } | |
550 | ||
7c673cae FG |
551 | template <uint8_t _b> |
552 | void BitVector<_b>::encode(bufferlist& bl) const { | |
553 | encode_header(bl); | |
554 | encode_data(bl, 0, m_data.length()); | |
555 | encode_footer(bl); | |
556 | } | |
557 | ||
558 | template <uint8_t _b> | |
11fdf7f2 | 559 | void BitVector<_b>::decode(bufferlist::const_iterator& it) { |
7c673cae FG |
560 | decode_header(it); |
561 | ||
562 | bufferlist data_bl; | |
563 | if (m_data.length() > 0) { | |
564 | it.copy(m_data.length(), data_bl); | |
565 | } | |
566 | ||
567 | decode_footer(it); | |
568 | ||
11fdf7f2 | 569 | auto data_it = data_bl.cbegin(); |
7c673cae FG |
570 | decode_data(data_it, 0); |
571 | } | |
572 | ||
573 | template <uint8_t _b> | |
574 | void BitVector<_b>::dump(Formatter *f) const { | |
575 | f->dump_unsigned("size", m_size); | |
576 | f->open_array_section("bit_table"); | |
577 | for (unsigned i = 0; i < m_data.length(); ++i) { | |
578 | f->dump_format("byte", "0x%02hhX", m_data[i]); | |
579 | } | |
580 | f->close_section(); | |
581 | } | |
582 | ||
583 | template <uint8_t _b> | |
584 | bool BitVector<_b>::operator==(const BitVector &b) const { | |
585 | return (this->m_size == b.m_size && this->m_data == b.m_data); | |
586 | } | |
587 | ||
588 | template <uint8_t _b> | |
589 | typename BitVector<_b>::Reference BitVector<_b>::operator[](uint64_t offset) { | |
7c673cae FG |
590 | uint64_t index; |
591 | uint64_t shift; | |
3efd9988 | 592 | compute_index(offset, &index, &shift); |
7c673cae | 593 | |
3efd9988 FG |
594 | bufferlist::iterator data_iterator(m_data.begin()); |
595 | data_iterator.seek(index); | |
596 | return Reference(std::move(data_iterator), shift); | |
7c673cae FG |
597 | } |
598 | ||
599 | template <uint8_t _b> | |
3efd9988 | 600 | typename BitVector<_b>::ConstReference BitVector<_b>::operator[](uint64_t offset) const { |
7c673cae FG |
601 | uint64_t index; |
602 | uint64_t shift; | |
3efd9988 | 603 | compute_index(offset, &index, &shift); |
7c673cae | 604 | |
3efd9988 FG |
605 | bufferlist::const_iterator data_iterator(m_data.begin()); |
606 | data_iterator.seek(index); | |
607 | return ConstReference(std::move(data_iterator), shift); | |
7c673cae FG |
608 | } |
609 | ||
610 | template <uint8_t _b> | |
611 | typename BitVector<_b>::Reference& BitVector<_b>::Reference::operator=(uint8_t v) { | |
3efd9988 FG |
612 | uint8_t mask = MASK << this->m_shift; |
613 | char packed_value = (*this->m_data_iterator & ~mask) | | |
614 | ((v << this->m_shift) & mask); | |
615 | bufferlist::iterator it(this->m_data_iterator); | |
616 | it.copy_in(1, &packed_value, true); | |
7c673cae FG |
617 | return *this; |
618 | } | |
619 | ||
620 | template <uint8_t _b> | |
621 | void BitVector<_b>::generate_test_instances(std::list<BitVector *> &o) { | |
622 | o.push_back(new BitVector()); | |
623 | ||
624 | BitVector *b = new BitVector(); | |
625 | const uint64_t radix = 1 << b->BIT_COUNT; | |
626 | const uint64_t size = 1024; | |
627 | ||
11fdf7f2 | 628 | b->resize(size, false); |
7c673cae FG |
629 | for (uint64_t i = 0; i < size; ++i) { |
630 | (*b)[i] = rand() % radix; | |
631 | } | |
632 | o.push_back(b); | |
633 | } | |
634 | ||
7c673cae FG |
635 | |
636 | WRITE_CLASS_ENCODER(ceph::BitVector<2>) | |
637 | ||
638 | template <uint8_t _b> | |
639 | inline std::ostream& operator<<(std::ostream& out, const ceph::BitVector<_b> &b) | |
640 | { | |
641 | out << "ceph::BitVector<" << _b << ">(size=" << b.size() << ", data=" | |
642 | << b.get_data() << ")"; | |
643 | return out; | |
644 | } | |
11fdf7f2 | 645 | } |
7c673cae FG |
646 | |
647 | #endif // BIT_VECTOR_HPP |