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),
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 uint64_t StupidAllocator::_aligned_len(
75 StupidAllocator::interval_set_t::iterator p
,
78 uint64_t skew
= p
.get_start() % alloc_unit
;
80 skew
= alloc_unit
- skew
;
81 if (skew
> p
.get_len())
84 return p
.get_len() - skew
;
87 int64_t StupidAllocator::allocate_int(
88 uint64_t want_size
, uint64_t alloc_unit
, int64_t hint
,
89 uint64_t *offset
, uint32_t *length
)
91 std::lock_guard
<std::mutex
> l(lock
);
92 dout(10) << __func__
<< " want_size 0x" << std::hex
<< want_size
93 << " alloc_unit 0x" << alloc_unit
94 << " hint 0x" << hint
<< std::dec
96 uint64_t want
= MAX(alloc_unit
, want_size
);
97 int bin
= _choose_bin(want
);
100 auto p
= free
[0].begin();
105 // search up (from hint)
107 for (bin
= orig_bin
; bin
< (int)free
.size(); ++bin
) {
108 p
= free
[bin
].lower_bound(hint
);
109 while (p
!= free
[bin
].end()) {
110 if (_aligned_len(p
, alloc_unit
) >= want_size
) {
118 // search up (from origin, and skip searched extents by hint)
119 for (bin
= orig_bin
; bin
< (int)free
.size(); ++bin
) {
120 p
= free
[bin
].begin();
121 auto end
= hint
? free
[bin
].lower_bound(hint
) : free
[bin
].end();
123 if (_aligned_len(p
, alloc_unit
) >= want_size
) {
130 // search down (hint)
132 for (bin
= orig_bin
; bin
>= 0; --bin
) {
133 p
= free
[bin
].lower_bound(hint
);
134 while (p
!= free
[bin
].end()) {
135 if (_aligned_len(p
, alloc_unit
) >= alloc_unit
) {
143 // search down (from origin, and skip searched extents by hint)
144 for (bin
= orig_bin
; bin
>= 0; --bin
) {
145 p
= free
[bin
].begin();
146 auto end
= hint
? free
[bin
].lower_bound(hint
) : free
[bin
].end();
148 if (_aligned_len(p
, alloc_unit
) >= alloc_unit
) {
158 uint64_t skew
= p
.get_start() % alloc_unit
;
160 skew
= alloc_unit
- skew
;
161 *offset
= p
.get_start() + skew
;
162 *length
= MIN(MAX(alloc_unit
, want_size
), P2ALIGN((p
.get_len() - skew
), alloc_unit
));
163 if (cct
->_conf
->bluestore_debug_small_allocations
) {
165 alloc_unit
* (rand() % cct
->_conf
->bluestore_debug_small_allocations
);
166 if (max
&& *length
> max
) {
167 dout(10) << __func__
<< " shortening allocation of 0x" << std::hex
168 << *length
<< " -> 0x"
169 << max
<< " due to debug_small_allocations" << std::dec
<< dendl
;
173 dout(30) << __func__
<< " got 0x" << std::hex
<< *offset
<< "~" << *length
174 << " from bin " << std::dec
<< bin
<< dendl
;
176 free
[bin
].erase(*offset
, *length
);
178 if (*offset
&& free
[bin
].contains(*offset
- skew
- 1, &off
, &len
)) {
179 int newbin
= _choose_bin(len
);
181 dout(30) << __func__
<< " demoting 0x" << std::hex
<< off
<< "~" << len
182 << std::dec
<< " to bin " << newbin
<< dendl
;
183 free
[bin
].erase(off
, len
);
184 _insert_free(off
, len
);
187 if (free
[bin
].contains(*offset
+ *length
, &off
, &len
)) {
188 int newbin
= _choose_bin(len
);
190 dout(30) << __func__
<< " demoting 0x" << std::hex
<< off
<< "~" << len
191 << std::dec
<< " to bin " << newbin
<< dendl
;
192 free
[bin
].erase(off
, len
);
193 _insert_free(off
, len
);
198 num_reserved
-= *length
;
199 assert(num_free
>= 0);
200 assert(num_reserved
>= 0);
201 last_alloc
= *offset
+ *length
;
205 int64_t StupidAllocator::allocate(
208 uint64_t max_alloc_size
,
210 mempool::bluestore_alloc::vector
<AllocExtent
> *extents
)
212 uint64_t allocated_size
= 0;
217 if (max_alloc_size
== 0) {
218 max_alloc_size
= want_size
;
221 ExtentList block_list
= ExtentList(extents
, 1, max_alloc_size
);
223 while (allocated_size
< want_size
) {
224 res
= allocate_int(MIN(max_alloc_size
, (want_size
- allocated_size
)),
225 alloc_unit
, hint
, &offset
, &length
);
232 block_list
.add_extents(offset
, length
);
233 allocated_size
+= length
;
234 hint
= offset
+ length
;
237 if (allocated_size
== 0) {
240 return allocated_size
;
243 void StupidAllocator::release(
244 uint64_t offset
, uint64_t length
)
246 std::lock_guard
<std::mutex
> l(lock
);
247 dout(10) << __func__
<< " 0x" << std::hex
<< offset
<< "~" << length
248 << std::dec
<< dendl
;
249 _insert_free(offset
, length
);
253 uint64_t StupidAllocator::get_free()
255 std::lock_guard
<std::mutex
> l(lock
);
259 void StupidAllocator::dump()
261 std::lock_guard
<std::mutex
> l(lock
);
262 for (unsigned bin
= 0; bin
< free
.size(); ++bin
) {
263 dout(0) << __func__
<< " free bin " << bin
<< ": "
264 << free
[bin
].num_intervals() << " extents" << dendl
;
265 for (auto p
= free
[bin
].begin();
266 p
!= free
[bin
].end();
268 dout(0) << __func__
<< " 0x" << std::hex
<< p
.get_start() << "~"
269 << p
.get_len() << std::dec
<< dendl
;
274 void StupidAllocator::init_add_free(uint64_t offset
, uint64_t length
)
276 std::lock_guard
<std::mutex
> l(lock
);
277 dout(10) << __func__
<< " 0x" << std::hex
<< offset
<< "~" << length
278 << std::dec
<< dendl
;
279 _insert_free(offset
, length
);
283 void StupidAllocator::init_rm_free(uint64_t offset
, uint64_t length
)
285 std::lock_guard
<std::mutex
> l(lock
);
286 dout(10) << __func__
<< " 0x" << std::hex
<< offset
<< "~" << length
287 << std::dec
<< dendl
;
289 rm
.insert(offset
, length
);
290 for (unsigned i
= 0; i
< free
.size() && !rm
.empty(); ++i
) {
291 interval_set_t overlap
;
292 overlap
.intersection_of(rm
, free
[i
]);
293 if (!overlap
.empty()) {
294 dout(20) << __func__
<< " bin " << i
<< " rm 0x" << std::hex
<< overlap
295 << std::dec
<< dendl
;
296 auto it
= overlap
.begin();
297 auto it_end
= overlap
.end();
298 while (it
!= it_end
) {
299 auto o
= it
.get_start();
300 auto l
= it
.get_len();
303 [&](uint64_t off
, uint64_t len
) {
304 unsigned newbin
= _choose_bin(len
);
306 ldout(cct
, 30) << __func__
<< " demoting1 0x" << std::hex
<< off
<< "~" << len
307 << std::dec
<< " to bin " << newbin
<< dendl
;
308 _insert_free(off
, len
);
316 rm
.subtract(overlap
);
321 assert(num_free
>= 0);
325 void StupidAllocator::shutdown()
327 dout(1) << __func__
<< dendl
;