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 uint64_t StupidAllocator::_aligned_len(
75 btree_interval_set<uint64_t,allocator>::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;
288 btree_interval_set<uint64_t,allocator> rm;
289 rm.insert(offset, length);
290 for (unsigned i = 0; i < free.size() && !rm.empty(); ++i) {
291 btree_interval_set<uint64_t,allocator> 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 free[i].subtract(overlap);
297 rm.subtract(overlap);
302 assert(num_free >= 0);
306 void StupidAllocator::shutdown()
308 dout(1) << __func__ << dendl;