]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | // -*- mode:C++; tab-width:8; c-basic-offset:2; indent-tabs-mode:t -*- |
2 | // vim: ts=8 sw=2 smarttab | |
3 | ||
4 | #include "StupidAllocator.h" | |
5 | #include "bluestore_types.h" | |
6 | #include "common/debug.h" | |
7 | ||
8 | #define dout_context cct | |
9 | #define dout_subsys ceph_subsys_bluestore | |
10 | #undef dout_prefix | |
b32b8144 | 11 | #define dout_prefix *_dout << "stupidalloc 0x" << this << " " |
7c673cae | 12 | |
9f95a23c | 13 | StupidAllocator::StupidAllocator(CephContext* cct, |
20effc67 TL |
14 | int64_t capacity, |
15 | int64_t _block_size, | |
16 | std::string_view name) | |
17 | : Allocator(name, capacity, _block_size), | |
18 | cct(cct), num_free(0), | |
9f95a23c | 19 | free(10) |
7c673cae | 20 | { |
f67539c2 | 21 | ceph_assert(cct != nullptr); |
20effc67 | 22 | ceph_assert(block_size > 0); |
7c673cae FG |
23 | } |
24 | ||
25 | StupidAllocator::~StupidAllocator() | |
26 | { | |
27 | } | |
28 | ||
29 | unsigned StupidAllocator::_choose_bin(uint64_t orig_len) | |
30 | { | |
20effc67 | 31 | uint64_t len = orig_len / block_size; |
7c673cae | 32 | int bin = std::min((int)cbits(len), (int)free.size() - 1); |
11fdf7f2 TL |
33 | ldout(cct, 30) << __func__ << " len 0x" << std::hex << orig_len |
34 | << std::dec << " -> " << bin << dendl; | |
7c673cae FG |
35 | return bin; |
36 | } | |
37 | ||
38 | void StupidAllocator::_insert_free(uint64_t off, uint64_t len) | |
39 | { | |
40 | unsigned bin = _choose_bin(len); | |
11fdf7f2 TL |
41 | ldout(cct, 30) << __func__ << " 0x" << std::hex << off << "~" << len |
42 | << std::dec << " in bin " << bin << dendl; | |
7c673cae FG |
43 | while (true) { |
44 | free[bin].insert(off, len, &off, &len); | |
45 | unsigned newbin = _choose_bin(len); | |
46 | if (newbin == bin) | |
47 | break; | |
11fdf7f2 TL |
48 | ldout(cct, 30) << __func__ << " promoting 0x" << std::hex << off << "~" << len |
49 | << std::dec << " to bin " << newbin << dendl; | |
7c673cae FG |
50 | free[bin].erase(off, len); |
51 | bin = newbin; | |
52 | } | |
53 | } | |
54 | ||
7c673cae FG |
55 | int64_t StupidAllocator::allocate_int( |
56 | uint64_t want_size, uint64_t alloc_unit, int64_t hint, | |
57 | uint64_t *offset, uint32_t *length) | |
58 | { | |
11fdf7f2 TL |
59 | std::lock_guard l(lock); |
60 | ldout(cct, 10) << __func__ << " want_size 0x" << std::hex << want_size | |
61 | << " alloc_unit 0x" << alloc_unit | |
62 | << " hint 0x" << hint << std::dec | |
63 | << dendl; | |
64 | uint64_t want = std::max(alloc_unit, want_size); | |
7c673cae FG |
65 | int bin = _choose_bin(want); |
66 | int orig_bin = bin; | |
67 | ||
68 | auto p = free[0].begin(); | |
69 | ||
70 | if (!hint) | |
71 | hint = last_alloc; | |
72 | ||
73 | // search up (from hint) | |
74 | if (hint) { | |
75 | for (bin = orig_bin; bin < (int)free.size(); ++bin) { | |
76 | p = free[bin].lower_bound(hint); | |
77 | while (p != free[bin].end()) { | |
aee94f69 | 78 | if (p.get_len() >= want_size) { |
7c673cae FG |
79 | goto found; |
80 | } | |
81 | ++p; | |
82 | } | |
83 | } | |
84 | } | |
85 | ||
86 | // search up (from origin, and skip searched extents by hint) | |
87 | for (bin = orig_bin; bin < (int)free.size(); ++bin) { | |
88 | p = free[bin].begin(); | |
89 | auto end = hint ? free[bin].lower_bound(hint) : free[bin].end(); | |
90 | while (p != end) { | |
aee94f69 | 91 | if (p.get_len() >= want_size) { |
7c673cae FG |
92 | goto found; |
93 | } | |
94 | ++p; | |
95 | } | |
96 | } | |
97 | ||
98 | // search down (hint) | |
99 | if (hint) { | |
100 | for (bin = orig_bin; bin >= 0; --bin) { | |
101 | p = free[bin].lower_bound(hint); | |
102 | while (p != free[bin].end()) { | |
aee94f69 | 103 | if (p.get_len() >= alloc_unit) { |
7c673cae FG |
104 | goto found; |
105 | } | |
106 | ++p; | |
107 | } | |
108 | } | |
109 | } | |
110 | ||
111 | // search down (from origin, and skip searched extents by hint) | |
112 | for (bin = orig_bin; bin >= 0; --bin) { | |
113 | p = free[bin].begin(); | |
114 | auto end = hint ? free[bin].lower_bound(hint) : free[bin].end(); | |
115 | while (p != end) { | |
aee94f69 | 116 | if (p.get_len() >= alloc_unit) { |
7c673cae FG |
117 | goto found; |
118 | } | |
119 | ++p; | |
120 | } | |
121 | } | |
122 | ||
123 | return -ENOSPC; | |
124 | ||
125 | found: | |
aee94f69 TL |
126 | *offset = p.get_start(); |
127 | *length = std::min(std::max(alloc_unit, want_size), p2align(p.get_len(), alloc_unit)); | |
128 | ||
7c673cae FG |
129 | if (cct->_conf->bluestore_debug_small_allocations) { |
130 | uint64_t max = | |
131 | alloc_unit * (rand() % cct->_conf->bluestore_debug_small_allocations); | |
132 | if (max && *length > max) { | |
11fdf7f2 TL |
133 | ldout(cct, 10) << __func__ << " shortening allocation of 0x" << std::hex |
134 | << *length << " -> 0x" | |
135 | << max << " due to debug_small_allocations" << std::dec | |
136 | << dendl; | |
7c673cae FG |
137 | *length = max; |
138 | } | |
139 | } | |
11fdf7f2 TL |
140 | ldout(cct, 30) << __func__ << " got 0x" << std::hex << *offset << "~" << *length |
141 | << " from bin " << std::dec << bin << dendl; | |
7c673cae FG |
142 | |
143 | free[bin].erase(*offset, *length); | |
144 | uint64_t off, len; | |
aee94f69 | 145 | if (*offset && free[bin].contains(*offset - 1, &off, &len)) { |
7c673cae FG |
146 | int newbin = _choose_bin(len); |
147 | if (newbin != bin) { | |
11fdf7f2 TL |
148 | ldout(cct, 30) << __func__ << " demoting 0x" << std::hex << off << "~" << len |
149 | << std::dec << " to bin " << newbin << dendl; | |
7c673cae FG |
150 | free[bin].erase(off, len); |
151 | _insert_free(off, len); | |
152 | } | |
153 | } | |
154 | if (free[bin].contains(*offset + *length, &off, &len)) { | |
155 | int newbin = _choose_bin(len); | |
156 | if (newbin != bin) { | |
11fdf7f2 TL |
157 | ldout(cct, 30) << __func__ << " demoting 0x" << std::hex << off << "~" << len |
158 | << std::dec << " to bin " << newbin << dendl; | |
7c673cae FG |
159 | free[bin].erase(off, len); |
160 | _insert_free(off, len); | |
161 | } | |
162 | } | |
163 | ||
164 | num_free -= *length; | |
11fdf7f2 | 165 | ceph_assert(num_free >= 0); |
7c673cae FG |
166 | last_alloc = *offset + *length; |
167 | return 0; | |
168 | } | |
169 | ||
170 | int64_t StupidAllocator::allocate( | |
171 | uint64_t want_size, | |
172 | uint64_t alloc_unit, | |
173 | uint64_t max_alloc_size, | |
174 | int64_t hint, | |
a8e16298 | 175 | PExtentVector *extents) |
7c673cae FG |
176 | { |
177 | uint64_t allocated_size = 0; | |
178 | uint64_t offset = 0; | |
179 | uint32_t length = 0; | |
180 | int res = 0; | |
181 | ||
182 | if (max_alloc_size == 0) { | |
183 | max_alloc_size = want_size; | |
184 | } | |
9f95a23c TL |
185 | // cap with 32-bit val |
186 | max_alloc_size = std::min(max_alloc_size, 0x10000000 - alloc_unit); | |
7c673cae | 187 | |
7c673cae | 188 | while (allocated_size < want_size) { |
11fdf7f2 | 189 | res = allocate_int(std::min(max_alloc_size, (want_size - allocated_size)), |
7c673cae FG |
190 | alloc_unit, hint, &offset, &length); |
191 | if (res != 0) { | |
192 | /* | |
193 | * Allocation failed. | |
194 | */ | |
195 | break; | |
196 | } | |
a8e16298 TL |
197 | bool can_append = true; |
198 | if (!extents->empty()) { | |
199 | bluestore_pextent_t &last_extent = extents->back(); | |
494da23a TL |
200 | if (last_extent.end() == offset) { |
201 | uint64_t l64 = last_extent.length; | |
202 | l64 += length; | |
203 | if (l64 < 0x100000000 && l64 <= max_alloc_size) { | |
204 | can_append = false; | |
205 | last_extent.length += length; | |
206 | } | |
a8e16298 TL |
207 | } |
208 | } | |
209 | if (can_append) { | |
210 | extents->emplace_back(bluestore_pextent_t(offset, length)); | |
211 | } | |
212 | ||
7c673cae FG |
213 | allocated_size += length; |
214 | hint = offset + length; | |
215 | } | |
216 | ||
217 | if (allocated_size == 0) { | |
218 | return -ENOSPC; | |
219 | } | |
220 | return allocated_size; | |
221 | } | |
222 | ||
223 | void StupidAllocator::release( | |
a8e16298 | 224 | const interval_set<uint64_t>& release_set) |
7c673cae | 225 | { |
11fdf7f2 | 226 | std::lock_guard l(lock); |
a8e16298 TL |
227 | for (interval_set<uint64_t>::const_iterator p = release_set.begin(); |
228 | p != release_set.end(); | |
229 | ++p) { | |
230 | const auto offset = p.get_start(); | |
231 | const auto length = p.get_len(); | |
232 | ldout(cct, 10) << __func__ << " 0x" << std::hex << offset << "~" << length | |
233 | << std::dec << dendl; | |
234 | _insert_free(offset, length); | |
235 | num_free += length; | |
236 | } | |
7c673cae FG |
237 | } |
238 | ||
239 | uint64_t StupidAllocator::get_free() | |
240 | { | |
11fdf7f2 | 241 | std::lock_guard l(lock); |
7c673cae FG |
242 | return num_free; |
243 | } | |
244 | ||
9f95a23c | 245 | double StupidAllocator::get_fragmentation() |
a8e16298 | 246 | { |
f67539c2 | 247 | ceph_assert(get_block_size()); |
a8e16298 TL |
248 | double res; |
249 | uint64_t max_intervals = 0; | |
250 | uint64_t intervals = 0; | |
251 | { | |
11fdf7f2 | 252 | std::lock_guard l(lock); |
f67539c2 TL |
253 | max_intervals = p2roundup<uint64_t>(num_free, |
254 | get_block_size()) / get_block_size(); | |
a8e16298 TL |
255 | for (unsigned bin = 0; bin < free.size(); ++bin) { |
256 | intervals += free[bin].num_intervals(); | |
257 | } | |
258 | } | |
259 | ldout(cct, 30) << __func__ << " " << intervals << "/" << max_intervals | |
260 | << dendl; | |
11fdf7f2 | 261 | ceph_assert(intervals <= max_intervals); |
a8e16298 TL |
262 | if (!intervals || max_intervals <= 1) { |
263 | return 0.0; | |
264 | } | |
265 | intervals--; | |
266 | max_intervals--; | |
267 | res = (double)intervals / max_intervals; | |
268 | return res; | |
269 | } | |
270 | ||
7c673cae FG |
271 | void StupidAllocator::dump() |
272 | { | |
11fdf7f2 | 273 | std::lock_guard l(lock); |
7c673cae | 274 | for (unsigned bin = 0; bin < free.size(); ++bin) { |
11fdf7f2 TL |
275 | ldout(cct, 0) << __func__ << " free bin " << bin << ": " |
276 | << free[bin].num_intervals() << " extents" << dendl; | |
7c673cae FG |
277 | for (auto p = free[bin].begin(); |
278 | p != free[bin].end(); | |
279 | ++p) { | |
11fdf7f2 TL |
280 | ldout(cct, 0) << __func__ << " 0x" << std::hex << p.get_start() << "~" |
281 | << p.get_len() << std::dec << dendl; | |
7c673cae FG |
282 | } |
283 | } | |
284 | } | |
285 | ||
1e59de90 | 286 | void StupidAllocator::foreach(std::function<void(uint64_t offset, uint64_t length)> notify) |
eafe8130 TL |
287 | { |
288 | std::lock_guard l(lock); | |
289 | for (unsigned bin = 0; bin < free.size(); ++bin) { | |
290 | for (auto p = free[bin].begin(); p != free[bin].end(); ++p) { | |
291 | notify(p.get_start(), p.get_len()); | |
292 | } | |
293 | } | |
294 | } | |
295 | ||
7c673cae FG |
296 | void StupidAllocator::init_add_free(uint64_t offset, uint64_t length) |
297 | { | |
b3b6e05e TL |
298 | if (!length) |
299 | return; | |
11fdf7f2 TL |
300 | std::lock_guard l(lock); |
301 | ldout(cct, 10) << __func__ << " 0x" << std::hex << offset << "~" << length | |
302 | << std::dec << dendl; | |
7c673cae FG |
303 | _insert_free(offset, length); |
304 | num_free += length; | |
305 | } | |
306 | ||
307 | void StupidAllocator::init_rm_free(uint64_t offset, uint64_t length) | |
308 | { | |
b3b6e05e TL |
309 | if (!length) |
310 | return; | |
11fdf7f2 TL |
311 | std::lock_guard l(lock); |
312 | ldout(cct, 10) << __func__ << " 0x" << std::hex << offset << "~" << length | |
313 | << std::dec << dendl; | |
94b18763 | 314 | interval_set_t rm; |
7c673cae FG |
315 | rm.insert(offset, length); |
316 | for (unsigned i = 0; i < free.size() && !rm.empty(); ++i) { | |
94b18763 | 317 | interval_set_t overlap; |
7c673cae FG |
318 | overlap.intersection_of(rm, free[i]); |
319 | if (!overlap.empty()) { | |
11fdf7f2 TL |
320 | ldout(cct, 20) << __func__ << " bin " << i << " rm 0x" << std::hex << overlap |
321 | << std::dec << dendl; | |
94b18763 FG |
322 | auto it = overlap.begin(); |
323 | auto it_end = overlap.end(); | |
324 | while (it != it_end) { | |
325 | auto o = it.get_start(); | |
326 | auto l = it.get_len(); | |
327 | ||
328 | free[i].erase(o, l, | |
329 | [&](uint64_t off, uint64_t len) { | |
330 | unsigned newbin = _choose_bin(len); | |
331 | if (newbin != i) { | |
332 | ldout(cct, 30) << __func__ << " demoting1 0x" << std::hex << off << "~" << len | |
333 | << std::dec << " to bin " << newbin << dendl; | |
334 | _insert_free(off, len); | |
28e407b8 | 335 | return true; |
94b18763 | 336 | } |
28e407b8 | 337 | return false; |
94b18763 FG |
338 | }); |
339 | ++it; | |
340 | } | |
341 | ||
7c673cae FG |
342 | rm.subtract(overlap); |
343 | } | |
344 | } | |
11fdf7f2 | 345 | ceph_assert(rm.empty()); |
7c673cae | 346 | num_free -= length; |
11fdf7f2 | 347 | ceph_assert(num_free >= 0); |
7c673cae FG |
348 | } |
349 | ||
350 | ||
351 | void StupidAllocator::shutdown() | |
352 | { | |
11fdf7f2 | 353 | ldout(cct, 1) << __func__ << dendl; |
7c673cae FG |
354 | } |
355 |