1 // -*- mode:C++; tab-width:8; c-basic-offset:2; indent-tabs-mode:t -*-
2 // vim: ts=8 sw=2 smarttab
4 #include "StupidAllocator.h"
5 #include "bluestore_types.h"
6 #include "common/debug.h"
8 #define dout_context cct
9 #define dout_subsys ceph_subsys_bluestore
11 #define dout_prefix *_dout << "stupidalloc 0x" << this << " "
13 StupidAllocator::StupidAllocator(CephContext
* cct
)
14 : cct(cct
), num_free(0),
20 StupidAllocator::~StupidAllocator()
24 unsigned StupidAllocator::_choose_bin(uint64_t orig_len
)
26 uint64_t len
= orig_len
/ cct
->_conf
->bdev_block_size
;
27 int bin
= std::min((int)cbits(len
), (int)free
.size() - 1);
28 ldout(cct
, 30) << __func__
<< " len 0x" << std::hex
<< orig_len
29 << std::dec
<< " -> " << bin
<< dendl
;
33 void StupidAllocator::_insert_free(uint64_t off
, uint64_t len
)
35 unsigned bin
= _choose_bin(len
);
36 ldout(cct
, 30) << __func__
<< " 0x" << std::hex
<< off
<< "~" << len
37 << std::dec
<< " in bin " << bin
<< dendl
;
39 free
[bin
].insert(off
, len
, &off
, &len
);
40 unsigned newbin
= _choose_bin(len
);
43 ldout(cct
, 30) << __func__
<< " promoting 0x" << std::hex
<< off
<< "~" << len
44 << std::dec
<< " to bin " << newbin
<< dendl
;
45 free
[bin
].erase(off
, len
);
50 /// return the effective length of the extent if we align to alloc_unit
51 uint64_t StupidAllocator::_aligned_len(
52 StupidAllocator::interval_set_t::iterator p
,
55 uint64_t skew
= p
.get_start() % alloc_unit
;
57 skew
= alloc_unit
- skew
;
58 if (skew
> p
.get_len())
61 return p
.get_len() - skew
;
64 int64_t StupidAllocator::allocate_int(
65 uint64_t want_size
, uint64_t alloc_unit
, int64_t hint
,
66 uint64_t *offset
, uint32_t *length
)
68 std::lock_guard
l(lock
);
69 ldout(cct
, 10) << __func__
<< " want_size 0x" << std::hex
<< want_size
70 << " alloc_unit 0x" << alloc_unit
71 << " hint 0x" << hint
<< std::dec
73 uint64_t want
= std::max(alloc_unit
, want_size
);
74 int bin
= _choose_bin(want
);
77 auto p
= free
[0].begin();
82 // search up (from hint)
84 for (bin
= orig_bin
; bin
< (int)free
.size(); ++bin
) {
85 p
= free
[bin
].lower_bound(hint
);
86 while (p
!= free
[bin
].end()) {
87 if (_aligned_len(p
, alloc_unit
) >= want_size
) {
95 // search up (from origin, and skip searched extents by hint)
96 for (bin
= orig_bin
; bin
< (int)free
.size(); ++bin
) {
97 p
= free
[bin
].begin();
98 auto end
= hint
? free
[bin
].lower_bound(hint
) : free
[bin
].end();
100 if (_aligned_len(p
, alloc_unit
) >= want_size
) {
107 // search down (hint)
109 for (bin
= orig_bin
; bin
>= 0; --bin
) {
110 p
= free
[bin
].lower_bound(hint
);
111 while (p
!= free
[bin
].end()) {
112 if (_aligned_len(p
, alloc_unit
) >= alloc_unit
) {
120 // search down (from origin, and skip searched extents by hint)
121 for (bin
= orig_bin
; bin
>= 0; --bin
) {
122 p
= free
[bin
].begin();
123 auto end
= hint
? free
[bin
].lower_bound(hint
) : free
[bin
].end();
125 if (_aligned_len(p
, alloc_unit
) >= alloc_unit
) {
135 uint64_t skew
= p
.get_start() % alloc_unit
;
137 skew
= alloc_unit
- skew
;
138 *offset
= p
.get_start() + skew
;
139 *length
= std::min(std::max(alloc_unit
, want_size
), p2align((p
.get_len() - skew
), alloc_unit
));
140 if (cct
->_conf
->bluestore_debug_small_allocations
) {
142 alloc_unit
* (rand() % cct
->_conf
->bluestore_debug_small_allocations
);
143 if (max
&& *length
> max
) {
144 ldout(cct
, 10) << __func__
<< " shortening allocation of 0x" << std::hex
145 << *length
<< " -> 0x"
146 << max
<< " due to debug_small_allocations" << std::dec
151 ldout(cct
, 30) << __func__
<< " got 0x" << std::hex
<< *offset
<< "~" << *length
152 << " from bin " << std::dec
<< bin
<< dendl
;
154 free
[bin
].erase(*offset
, *length
);
156 if (*offset
&& free
[bin
].contains(*offset
- skew
- 1, &off
, &len
)) {
157 int newbin
= _choose_bin(len
);
159 ldout(cct
, 30) << __func__
<< " demoting 0x" << std::hex
<< off
<< "~" << len
160 << std::dec
<< " to bin " << newbin
<< dendl
;
161 free
[bin
].erase(off
, len
);
162 _insert_free(off
, len
);
165 if (free
[bin
].contains(*offset
+ *length
, &off
, &len
)) {
166 int newbin
= _choose_bin(len
);
168 ldout(cct
, 30) << __func__
<< " demoting 0x" << std::hex
<< off
<< "~" << len
169 << std::dec
<< " to bin " << newbin
<< dendl
;
170 free
[bin
].erase(off
, len
);
171 _insert_free(off
, len
);
176 ceph_assert(num_free
>= 0);
177 last_alloc
= *offset
+ *length
;
181 int64_t StupidAllocator::allocate(
184 uint64_t max_alloc_size
,
186 PExtentVector
*extents
)
188 uint64_t allocated_size
= 0;
193 if (max_alloc_size
== 0) {
194 max_alloc_size
= want_size
;
197 while (allocated_size
< want_size
) {
198 res
= allocate_int(std::min(max_alloc_size
, (want_size
- allocated_size
)),
199 alloc_unit
, hint
, &offset
, &length
);
206 bool can_append
= true;
207 if (!extents
->empty()) {
208 bluestore_pextent_t
&last_extent
= extents
->back();
209 if ((last_extent
.end() == offset
) &&
210 ((last_extent
.length
+ length
) <= max_alloc_size
)) {
212 last_extent
.length
+= length
;
216 extents
->emplace_back(bluestore_pextent_t(offset
, length
));
219 allocated_size
+= length
;
220 hint
= offset
+ length
;
223 if (allocated_size
== 0) {
226 return allocated_size
;
229 void StupidAllocator::release(
230 const interval_set
<uint64_t>& release_set
)
232 std::lock_guard
l(lock
);
233 for (interval_set
<uint64_t>::const_iterator p
= release_set
.begin();
234 p
!= release_set
.end();
236 const auto offset
= p
.get_start();
237 const auto length
= p
.get_len();
238 ldout(cct
, 10) << __func__
<< " 0x" << std::hex
<< offset
<< "~" << length
239 << std::dec
<< dendl
;
240 _insert_free(offset
, length
);
245 uint64_t StupidAllocator::get_free()
247 std::lock_guard
l(lock
);
251 double StupidAllocator::get_fragmentation(uint64_t alloc_unit
)
253 ceph_assert(alloc_unit
);
255 uint64_t max_intervals
= 0;
256 uint64_t intervals
= 0;
258 std::lock_guard
l(lock
);
259 max_intervals
= p2roundup
<uint64_t>(num_free
, alloc_unit
) / alloc_unit
;
260 for (unsigned bin
= 0; bin
< free
.size(); ++bin
) {
261 intervals
+= free
[bin
].num_intervals();
264 ldout(cct
, 30) << __func__
<< " " << intervals
<< "/" << max_intervals
266 ceph_assert(intervals
<= max_intervals
);
267 if (!intervals
|| max_intervals
<= 1) {
272 res
= (double)intervals
/ max_intervals
;
276 void StupidAllocator::dump()
278 std::lock_guard
l(lock
);
279 for (unsigned bin
= 0; bin
< free
.size(); ++bin
) {
280 ldout(cct
, 0) << __func__
<< " free bin " << bin
<< ": "
281 << free
[bin
].num_intervals() << " extents" << dendl
;
282 for (auto p
= free
[bin
].begin();
283 p
!= free
[bin
].end();
285 ldout(cct
, 0) << __func__
<< " 0x" << std::hex
<< p
.get_start() << "~"
286 << p
.get_len() << std::dec
<< dendl
;
291 void StupidAllocator::init_add_free(uint64_t offset
, uint64_t length
)
293 std::lock_guard
l(lock
);
294 ldout(cct
, 10) << __func__
<< " 0x" << std::hex
<< offset
<< "~" << length
295 << std::dec
<< dendl
;
296 _insert_free(offset
, length
);
300 void StupidAllocator::init_rm_free(uint64_t offset
, uint64_t length
)
302 std::lock_guard
l(lock
);
303 ldout(cct
, 10) << __func__
<< " 0x" << std::hex
<< offset
<< "~" << length
304 << std::dec
<< dendl
;
306 rm
.insert(offset
, length
);
307 for (unsigned i
= 0; i
< free
.size() && !rm
.empty(); ++i
) {
308 interval_set_t overlap
;
309 overlap
.intersection_of(rm
, free
[i
]);
310 if (!overlap
.empty()) {
311 ldout(cct
, 20) << __func__
<< " bin " << i
<< " rm 0x" << std::hex
<< overlap
312 << std::dec
<< dendl
;
313 auto it
= overlap
.begin();
314 auto it_end
= overlap
.end();
315 while (it
!= it_end
) {
316 auto o
= it
.get_start();
317 auto l
= it
.get_len();
320 [&](uint64_t off
, uint64_t len
) {
321 unsigned newbin
= _choose_bin(len
);
323 ldout(cct
, 30) << __func__
<< " demoting1 0x" << std::hex
<< off
<< "~" << len
324 << std::dec
<< " to bin " << newbin
<< dendl
;
325 _insert_free(off
, len
);
333 rm
.subtract(overlap
);
336 ceph_assert(rm
.empty());
338 ceph_assert(num_free
>= 0);
342 void StupidAllocator::shutdown()
344 ldout(cct
, 1) << __func__
<< dendl
;