]>
Commit | Line | Data |
---|---|---|
20effc67 TL |
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 | * Author: Gabriel BenHanokh <gbenhano@redhat.com> | |
7 | * | |
8 | * This is free software; you can redistribute it and/or | |
9 | * modify it under the terms of the GNU Lesser General Public | |
10 | * License version 2.1, as published by the Free Software | |
11 | * Foundation. See file COPYING. | |
12 | * | |
13 | */ | |
14 | #pragma once | |
15 | #include <cstdint> | |
16 | #include <iostream> | |
17 | #include <string> | |
18 | #include <cstring> | |
19 | #include <cmath> | |
20 | #include <iomanip> | |
21 | ||
22 | #include "include/ceph_assert.h" | |
23 | ||
24 | struct extent_t { | |
25 | uint64_t offset; | |
26 | uint64_t length; | |
1d09f67e TL |
27 | bool operator==(const extent_t& other) const { |
28 | return (this->offset == other.offset && this->length == other.length); | |
29 | } | |
20effc67 TL |
30 | }; |
31 | ||
32 | class SimpleBitmap { | |
33 | public: | |
34 | SimpleBitmap(CephContext *_cct, uint64_t num_bits); | |
35 | ~SimpleBitmap(); | |
36 | ||
37 | SimpleBitmap(const SimpleBitmap&) = delete; | |
38 | SimpleBitmap& operator=(const SimpleBitmap&) = delete; | |
39 | ||
40 | ||
41 | // set a bit range range of @length starting at @offset | |
42 | bool set(uint64_t offset, uint64_t length); | |
43 | // clear a bit range range of @length starting at @offset | |
44 | bool clr(uint64_t offset, uint64_t length); | |
45 | ||
46 | // returns a copy of the next set extent starting at @offset | |
47 | extent_t get_next_set_extent(uint64_t offset); | |
48 | ||
49 | // returns a copy of the next clear extent starting at @offset | |
50 | extent_t get_next_clr_extent(uint64_t offset); | |
51 | ||
52 | //---------------------------------------------------------------------------- | |
53 | inline uint64_t get_size() { | |
54 | return m_num_bits; | |
55 | } | |
56 | ||
57 | //---------------------------------------------------------------------------- | |
58 | // clears all bits in the bitmap | |
59 | inline void clear_all() { | |
60 | std::memset(m_arr, 0, words_to_bytes(m_word_count)); | |
61 | } | |
62 | ||
63 | //---------------------------------------------------------------------------- | |
64 | // sets all bits in the bitmap | |
65 | inline void set_all() { | |
66 | std::memset(m_arr, 0xFF, words_to_bytes(m_word_count)); | |
67 | // clear bits in the last word past the last legal bit | |
68 | uint64_t incomplete_word_bit_offset = (m_num_bits & BITS_IN_WORD_MASK); | |
69 | if (incomplete_word_bit_offset) { | |
70 | uint64_t clr_mask = ~(FULL_MASK << incomplete_word_bit_offset); | |
71 | m_arr[m_word_count - 1] &= clr_mask; | |
72 | } | |
73 | } | |
74 | ||
75 | //---------------------------------------------------------------------------- | |
76 | bool bit_is_set(uint64_t offset) { | |
77 | if (offset < m_num_bits) { | |
78 | auto [word_index, bit_offset] = split(offset); | |
79 | uint64_t mask = 1ULL << bit_offset; | |
80 | return (m_arr[word_index] & mask); | |
81 | } else { | |
82 | ceph_assert(offset < m_num_bits); | |
83 | return false; | |
84 | } | |
85 | } | |
86 | ||
87 | //---------------------------------------------------------------------------- | |
88 | bool bit_is_clr(uint64_t offset) { | |
89 | if (offset < m_num_bits) { | |
90 | auto [word_index, bit_offset] = split(offset); | |
91 | uint64_t mask = 1ULL << bit_offset; | |
92 | return ( (m_arr[word_index] & mask) == 0 ); | |
93 | } else { | |
94 | ceph_assert(offset < m_num_bits); | |
95 | return false; | |
96 | } | |
97 | } | |
98 | ||
99 | private: | |
100 | //---------------------------------------------------------------------------- | |
101 | static inline std::pair<uint64_t, uint64_t> split(uint64_t offset) { | |
102 | return { offset_to_index(offset), (offset & BITS_IN_WORD_MASK) }; | |
103 | } | |
104 | ||
105 | //--------------------------------------------------------------------------- | |
106 | static inline uint64_t offset_to_index(uint64_t offset) { | |
107 | return offset >> BITS_IN_WORD_SHIFT; | |
108 | } | |
109 | ||
110 | //--------------------------------------------------------------------------- | |
111 | static inline uint64_t index_to_offset(uint64_t index) { | |
112 | return index << BITS_IN_WORD_SHIFT; | |
113 | } | |
114 | ||
115 | //--------------------------------------------------------------------------- | |
116 | static inline uint64_t bits_to_words(uint64_t bit_count) { | |
117 | return bit_count >> BITS_IN_WORD_SHIFT; | |
118 | } | |
119 | ||
120 | //--------------------------------------------------------------------------- | |
121 | static inline uint64_t words_to_bits(uint64_t words_count) { | |
122 | return words_count << BITS_IN_WORD_SHIFT; | |
123 | } | |
124 | ||
125 | //--------------------------------------------------------------------------- | |
126 | static inline uint64_t bytes_to_words(uint64_t byte_count) { | |
127 | return byte_count >> BYTES_IN_WORD_SHIFT; | |
128 | } | |
129 | ||
130 | //--------------------------------------------------------------------------- | |
131 | static inline uint64_t words_to_bytes(uint64_t words_count) { | |
132 | return (words_count << BYTES_IN_WORD_SHIFT); | |
133 | } | |
134 | ||
135 | constexpr static uint64_t BYTES_IN_WORD = sizeof(uint64_t); | |
136 | constexpr static uint64_t BYTES_IN_WORD_SHIFT = 3; | |
137 | constexpr static uint64_t BITS_IN_WORD = (BYTES_IN_WORD * 8); | |
138 | constexpr static uint64_t BITS_IN_WORD_MASK = (BITS_IN_WORD - 1); | |
139 | constexpr static uint64_t BITS_IN_WORD_SHIFT = 6; | |
140 | constexpr static uint64_t FULL_MASK = (~((uint64_t)0)); | |
141 | ||
142 | CephContext *cct; | |
143 | uint64_t *m_arr; | |
144 | uint64_t m_num_bits; | |
145 | uint64_t m_word_count; | |
146 | }; |