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