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