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 "
13 StupidAllocator::StupidAllocator(CephContext
* cct
)
14 : cct(cct
), num_free(0),
21 StupidAllocator::~StupidAllocator()
25 unsigned StupidAllocator::_choose_bin(uint64_t orig_len
)
27 uint64_t len
= orig_len
/ cct
->_conf
->bdev_block_size
;
28 int bin
= std::min((int)cbits(len
), (int)free
.size() - 1);
29 dout(30) << __func__
<< " len 0x" << std::hex
<< orig_len
<< std::dec
30 << " -> " << bin
<< dendl
;
34 void StupidAllocator::_insert_free(uint64_t off
, uint64_t len
)
36 unsigned bin
= _choose_bin(len
);
37 dout(30) << __func__
<< " 0x" << std::hex
<< off
<< "~" << len
<< std::dec
38 << " in bin " << bin
<< dendl
;
40 free
[bin
].insert(off
, len
, &off
, &len
);
41 unsigned newbin
= _choose_bin(len
);
44 dout(30) << __func__
<< " promoting 0x" << std::hex
<< off
<< "~" << len
45 << std::dec
<< " to bin " << newbin
<< dendl
;
46 free
[bin
].erase(off
, len
);
51 int StupidAllocator::reserve(uint64_t need
)
53 std::lock_guard
<std::mutex
> l(lock
);
54 dout(10) << __func__
<< " need 0x" << std::hex
<< need
55 << " num_free 0x" << num_free
56 << " num_reserved 0x" << num_reserved
<< std::dec
<< dendl
;
57 if ((int64_t)need
> num_free
- num_reserved
)
63 void StupidAllocator::unreserve(uint64_t unused
)
65 std::lock_guard
<std::mutex
> l(lock
);
66 dout(10) << __func__
<< " unused 0x" << std::hex
<< unused
67 << " num_free 0x" << num_free
68 << " num_reserved 0x" << num_reserved
<< std::dec
<< dendl
;
69 assert(num_reserved
>= (int64_t)unused
);
70 num_reserved
-= unused
;
73 /// return the effective length of the extent if we align to alloc_unit
74 static uint64_t aligned_len(btree_interval_set
<uint64_t>::iterator p
,
77 uint64_t skew
= p
.get_start() % alloc_unit
;
79 skew
= alloc_unit
- skew
;
80 if (skew
> p
.get_len())
83 return p
.get_len() - skew
;
86 int64_t StupidAllocator::allocate_int(
87 uint64_t want_size
, uint64_t alloc_unit
, int64_t hint
,
88 uint64_t *offset
, uint32_t *length
)
90 std::lock_guard
<std::mutex
> l(lock
);
91 dout(10) << __func__
<< " want_size 0x" << std::hex
<< want_size
92 << " alloc_unit 0x" << alloc_unit
93 << " hint 0x" << hint
<< std::dec
95 uint64_t want
= MAX(alloc_unit
, want_size
);
96 int bin
= _choose_bin(want
);
99 auto p
= free
[0].begin();
104 // search up (from hint)
106 for (bin
= orig_bin
; bin
< (int)free
.size(); ++bin
) {
107 p
= free
[bin
].lower_bound(hint
);
108 while (p
!= free
[bin
].end()) {
109 if (aligned_len(p
, alloc_unit
) >= want_size
) {
117 // search up (from origin, and skip searched extents by hint)
118 for (bin
= orig_bin
; bin
< (int)free
.size(); ++bin
) {
119 p
= free
[bin
].begin();
120 auto end
= hint
? free
[bin
].lower_bound(hint
) : free
[bin
].end();
122 if (aligned_len(p
, alloc_unit
) >= want_size
) {
129 // search down (hint)
131 for (bin
= orig_bin
; bin
>= 0; --bin
) {
132 p
= free
[bin
].lower_bound(hint
);
133 while (p
!= free
[bin
].end()) {
134 if (aligned_len(p
, alloc_unit
) >= alloc_unit
) {
142 // search down (from origin, and skip searched extents by hint)
143 for (bin
= orig_bin
; bin
>= 0; --bin
) {
144 p
= free
[bin
].begin();
145 auto end
= hint
? free
[bin
].lower_bound(hint
) : free
[bin
].end();
147 if (aligned_len(p
, alloc_unit
) >= alloc_unit
) {
157 uint64_t skew
= p
.get_start() % alloc_unit
;
159 skew
= alloc_unit
- skew
;
160 *offset
= p
.get_start() + skew
;
161 *length
= MIN(MAX(alloc_unit
, want_size
), P2ALIGN((p
.get_len() - skew
), alloc_unit
));
162 if (cct
->_conf
->bluestore_debug_small_allocations
) {
164 alloc_unit
* (rand() % cct
->_conf
->bluestore_debug_small_allocations
);
165 if (max
&& *length
> max
) {
166 dout(10) << __func__
<< " shortening allocation of 0x" << std::hex
167 << *length
<< " -> 0x"
168 << max
<< " due to debug_small_allocations" << std::dec
<< dendl
;
172 dout(30) << __func__
<< " got 0x" << std::hex
<< *offset
<< "~" << *length
173 << " from bin " << std::dec
<< bin
<< dendl
;
175 free
[bin
].erase(*offset
, *length
);
177 if (*offset
&& free
[bin
].contains(*offset
- skew
- 1, &off
, &len
)) {
178 int newbin
= _choose_bin(len
);
180 dout(30) << __func__
<< " demoting 0x" << std::hex
<< off
<< "~" << len
181 << std::dec
<< " to bin " << newbin
<< dendl
;
182 free
[bin
].erase(off
, len
);
183 _insert_free(off
, len
);
186 if (free
[bin
].contains(*offset
+ *length
, &off
, &len
)) {
187 int newbin
= _choose_bin(len
);
189 dout(30) << __func__
<< " demoting 0x" << std::hex
<< off
<< "~" << len
190 << std::dec
<< " to bin " << newbin
<< dendl
;
191 free
[bin
].erase(off
, len
);
192 _insert_free(off
, len
);
197 num_reserved
-= *length
;
198 assert(num_free
>= 0);
199 assert(num_reserved
>= 0);
200 last_alloc
= *offset
+ *length
;
204 int64_t StupidAllocator::allocate(
207 uint64_t max_alloc_size
,
209 mempool::bluestore_alloc::vector
<AllocExtent
> *extents
)
211 uint64_t allocated_size
= 0;
216 if (max_alloc_size
== 0) {
217 max_alloc_size
= want_size
;
220 ExtentList block_list
= ExtentList(extents
, 1, max_alloc_size
);
222 while (allocated_size
< want_size
) {
223 res
= allocate_int(MIN(max_alloc_size
, (want_size
- allocated_size
)),
224 alloc_unit
, hint
, &offset
, &length
);
231 block_list
.add_extents(offset
, length
);
232 allocated_size
+= length
;
233 hint
= offset
+ length
;
236 if (allocated_size
== 0) {
239 return allocated_size
;
242 void StupidAllocator::release(
243 uint64_t offset
, uint64_t length
)
245 std::lock_guard
<std::mutex
> l(lock
);
246 dout(10) << __func__
<< " 0x" << std::hex
<< offset
<< "~" << length
247 << std::dec
<< dendl
;
248 _insert_free(offset
, length
);
252 uint64_t StupidAllocator::get_free()
254 std::lock_guard
<std::mutex
> l(lock
);
258 void StupidAllocator::dump()
260 std::lock_guard
<std::mutex
> l(lock
);
261 for (unsigned bin
= 0; bin
< free
.size(); ++bin
) {
262 dout(0) << __func__
<< " free bin " << bin
<< ": "
263 << free
[bin
].num_intervals() << " extents" << dendl
;
264 for (auto p
= free
[bin
].begin();
265 p
!= free
[bin
].end();
267 dout(0) << __func__
<< " 0x" << std::hex
<< p
.get_start() << "~"
268 << p
.get_len() << std::dec
<< dendl
;
273 void StupidAllocator::init_add_free(uint64_t offset
, uint64_t length
)
275 std::lock_guard
<std::mutex
> l(lock
);
276 dout(10) << __func__
<< " 0x" << std::hex
<< offset
<< "~" << length
277 << std::dec
<< dendl
;
278 _insert_free(offset
, length
);
282 void StupidAllocator::init_rm_free(uint64_t offset
, uint64_t length
)
284 std::lock_guard
<std::mutex
> l(lock
);
285 dout(10) << __func__
<< " 0x" << std::hex
<< offset
<< "~" << length
286 << std::dec
<< dendl
;
287 btree_interval_set
<uint64_t> rm
;
288 rm
.insert(offset
, length
);
289 for (unsigned i
= 0; i
< free
.size() && !rm
.empty(); ++i
) {
290 btree_interval_set
<uint64_t> overlap
;
291 overlap
.intersection_of(rm
, free
[i
]);
292 if (!overlap
.empty()) {
293 dout(20) << __func__
<< " bin " << i
<< " rm 0x" << std::hex
<< overlap
294 << std::dec
<< dendl
;
295 free
[i
].subtract(overlap
);
296 rm
.subtract(overlap
);
301 assert(num_free
>= 0);
305 void StupidAllocator::shutdown()
307 dout(1) << __func__
<< dendl
;