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 dout(30) << __func__
<< " len 0x" << std::hex
<< orig_len
<< std::dec
29 << " -> " << bin
<< dendl
;
33 void StupidAllocator::_insert_free(uint64_t off
, uint64_t len
)
35 unsigned bin
= _choose_bin(len
);
36 dout(30) << __func__
<< " 0x" << std::hex
<< off
<< "~" << len
<< std::dec
37 << " in bin " << bin
<< dendl
;
39 free
[bin
].insert(off
, len
, &off
, &len
);
40 unsigned newbin
= _choose_bin(len
);
43 dout(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
<std::mutex
> l(lock
);
69 dout(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
= 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
= MIN(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 dout(10) << __func__
<< " shortening allocation of 0x" << std::hex
145 << *length
<< " -> 0x"
146 << max
<< " due to debug_small_allocations" << std::dec
<< dendl
;
150 dout(30) << __func__
<< " got 0x" << std::hex
<< *offset
<< "~" << *length
151 << " from bin " << std::dec
<< bin
<< dendl
;
153 free
[bin
].erase(*offset
, *length
);
155 if (*offset
&& free
[bin
].contains(*offset
- skew
- 1, &off
, &len
)) {
156 int newbin
= _choose_bin(len
);
158 dout(30) << __func__
<< " demoting 0x" << std::hex
<< off
<< "~" << len
159 << std::dec
<< " to bin " << newbin
<< dendl
;
160 free
[bin
].erase(off
, len
);
161 _insert_free(off
, len
);
164 if (free
[bin
].contains(*offset
+ *length
, &off
, &len
)) {
165 int newbin
= _choose_bin(len
);
167 dout(30) << __func__
<< " demoting 0x" << std::hex
<< off
<< "~" << len
168 << std::dec
<< " to bin " << newbin
<< dendl
;
169 free
[bin
].erase(off
, len
);
170 _insert_free(off
, len
);
175 assert(num_free
>= 0);
176 last_alloc
= *offset
+ *length
;
180 int64_t StupidAllocator::allocate(
183 uint64_t max_alloc_size
,
185 PExtentVector
*extents
)
187 uint64_t allocated_size
= 0;
192 if (max_alloc_size
== 0) {
193 max_alloc_size
= want_size
;
196 while (allocated_size
< want_size
) {
197 res
= allocate_int(MIN(max_alloc_size
, (want_size
- allocated_size
)),
198 alloc_unit
, hint
, &offset
, &length
);
205 bool can_append
= true;
206 if (!extents
->empty()) {
207 bluestore_pextent_t
&last_extent
= extents
->back();
208 if ((last_extent
.end() == offset
) &&
209 ((last_extent
.length
+ length
) <= max_alloc_size
)) {
211 last_extent
.length
+= length
;
215 extents
->emplace_back(bluestore_pextent_t(offset
, length
));
218 allocated_size
+= length
;
219 hint
= offset
+ length
;
222 if (allocated_size
== 0) {
225 return allocated_size
;
228 void StupidAllocator::release(
229 const interval_set
<uint64_t>& release_set
)
231 std::lock_guard
<std::mutex
> l(lock
);
232 for (interval_set
<uint64_t>::const_iterator p
= release_set
.begin();
233 p
!= release_set
.end();
235 const auto offset
= p
.get_start();
236 const auto length
= p
.get_len();
237 ldout(cct
, 10) << __func__
<< " 0x" << std::hex
<< offset
<< "~" << length
238 << std::dec
<< dendl
;
239 _insert_free(offset
, length
);
244 uint64_t StupidAllocator::get_free()
246 std::lock_guard
<std::mutex
> l(lock
);
250 double StupidAllocator::get_fragmentation(uint64_t alloc_unit
)
254 uint64_t max_intervals
= 0;
255 uint64_t intervals
= 0;
257 std::lock_guard
<std::mutex
> l(lock
);
258 max_intervals
= num_free
/ alloc_unit
;
259 for (unsigned bin
= 0; bin
< free
.size(); ++bin
) {
260 intervals
+= free
[bin
].num_intervals();
263 ldout(cct
, 30) << __func__
<< " " << intervals
<< "/" << max_intervals
265 assert(intervals
<= max_intervals
);
266 if (!intervals
|| max_intervals
<= 1) {
271 res
= (double)intervals
/ max_intervals
;
275 void StupidAllocator::dump()
277 std::lock_guard
<std::mutex
> l(lock
);
278 for (unsigned bin
= 0; bin
< free
.size(); ++bin
) {
279 dout(0) << __func__
<< " free bin " << bin
<< ": "
280 << free
[bin
].num_intervals() << " extents" << dendl
;
281 for (auto p
= free
[bin
].begin();
282 p
!= free
[bin
].end();
284 dout(0) << __func__
<< " 0x" << std::hex
<< p
.get_start() << "~"
285 << p
.get_len() << std::dec
<< dendl
;
290 void StupidAllocator::init_add_free(uint64_t offset
, uint64_t length
)
292 std::lock_guard
<std::mutex
> l(lock
);
293 dout(10) << __func__
<< " 0x" << std::hex
<< offset
<< "~" << length
294 << std::dec
<< dendl
;
295 _insert_free(offset
, length
);
299 void StupidAllocator::init_rm_free(uint64_t offset
, uint64_t length
)
301 std::lock_guard
<std::mutex
> l(lock
);
302 dout(10) << __func__
<< " 0x" << std::hex
<< offset
<< "~" << length
303 << std::dec
<< dendl
;
305 rm
.insert(offset
, length
);
306 for (unsigned i
= 0; i
< free
.size() && !rm
.empty(); ++i
) {
307 interval_set_t overlap
;
308 overlap
.intersection_of(rm
, free
[i
]);
309 if (!overlap
.empty()) {
310 dout(20) << __func__
<< " bin " << i
<< " rm 0x" << std::hex
<< overlap
311 << std::dec
<< dendl
;
312 auto it
= overlap
.begin();
313 auto it_end
= overlap
.end();
314 while (it
!= it_end
) {
315 auto o
= it
.get_start();
316 auto l
= it
.get_len();
319 [&](uint64_t off
, uint64_t len
) {
320 unsigned newbin
= _choose_bin(len
);
322 ldout(cct
, 30) << __func__
<< " demoting1 0x" << std::hex
<< off
<< "~" << len
323 << std::dec
<< " to bin " << newbin
<< dendl
;
324 _insert_free(off
, len
);
332 rm
.subtract(overlap
);
337 assert(num_free
>= 0);
341 void StupidAllocator::shutdown()
343 dout(1) << __func__
<< dendl
;