]>
Commit | Line | Data |
---|---|---|
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 | |
11 | #define dout_prefix *_dout << "stupidalloc 0x" << this << " " | |
12 | ||
13 | StupidAllocator::StupidAllocator(CephContext* cct) | |
14 | : cct(cct), num_free(0), | |
15 | num_reserved(0), | |
16 | free(10), | |
17 | last_alloc(0) | |
18 | { | |
19 | } | |
20 | ||
21 | StupidAllocator::~StupidAllocator() | |
22 | { | |
23 | } | |
24 | ||
25 | unsigned StupidAllocator::_choose_bin(uint64_t orig_len) | |
26 | { | |
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; | |
31 | return bin; | |
32 | } | |
33 | ||
34 | void StupidAllocator::_insert_free(uint64_t off, uint64_t len) | |
35 | { | |
36 | unsigned bin = _choose_bin(len); | |
37 | dout(30) << __func__ << " 0x" << std::hex << off << "~" << len << std::dec | |
38 | << " in bin " << bin << dendl; | |
39 | while (true) { | |
40 | free[bin].insert(off, len, &off, &len); | |
41 | unsigned newbin = _choose_bin(len); | |
42 | if (newbin == bin) | |
43 | break; | |
44 | dout(30) << __func__ << " promoting 0x" << std::hex << off << "~" << len | |
45 | << std::dec << " to bin " << newbin << dendl; | |
46 | free[bin].erase(off, len); | |
47 | bin = newbin; | |
48 | } | |
49 | } | |
50 | ||
51 | int StupidAllocator::reserve(uint64_t need) | |
52 | { | |
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) | |
58 | return -ENOSPC; | |
59 | num_reserved += need; | |
60 | return 0; | |
61 | } | |
62 | ||
63 | void StupidAllocator::unreserve(uint64_t unused) | |
64 | { | |
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; | |
71 | } | |
72 | ||
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, | |
76 | uint64_t alloc_unit) | |
77 | { | |
78 | uint64_t skew = p.get_start() % alloc_unit; | |
79 | if (skew) | |
80 | skew = alloc_unit - skew; | |
81 | if (skew > p.get_len()) | |
82 | return 0; | |
83 | else | |
84 | return p.get_len() - skew; | |
85 | } | |
86 | ||
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) | |
90 | { | |
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 | |
95 | << dendl; | |
96 | uint64_t want = MAX(alloc_unit, want_size); | |
97 | int bin = _choose_bin(want); | |
98 | int orig_bin = bin; | |
99 | ||
100 | auto p = free[0].begin(); | |
101 | ||
102 | if (!hint) | |
103 | hint = last_alloc; | |
104 | ||
105 | // search up (from hint) | |
106 | if (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) { | |
111 | goto found; | |
112 | } | |
113 | ++p; | |
114 | } | |
115 | } | |
116 | } | |
117 | ||
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(); | |
122 | while (p != end) { | |
123 | if (_aligned_len(p, alloc_unit) >= want_size) { | |
124 | goto found; | |
125 | } | |
126 | ++p; | |
127 | } | |
128 | } | |
129 | ||
130 | // search down (hint) | |
131 | if (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) { | |
136 | goto found; | |
137 | } | |
138 | ++p; | |
139 | } | |
140 | } | |
141 | } | |
142 | ||
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(); | |
147 | while (p != end) { | |
148 | if (_aligned_len(p, alloc_unit) >= alloc_unit) { | |
149 | goto found; | |
150 | } | |
151 | ++p; | |
152 | } | |
153 | } | |
154 | ||
155 | return -ENOSPC; | |
156 | ||
157 | found: | |
158 | uint64_t skew = p.get_start() % alloc_unit; | |
159 | if (skew) | |
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) { | |
164 | uint64_t max = | |
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; | |
170 | *length = max; | |
171 | } | |
172 | } | |
173 | dout(30) << __func__ << " got 0x" << std::hex << *offset << "~" << *length | |
174 | << " from bin " << std::dec << bin << dendl; | |
175 | ||
176 | free[bin].erase(*offset, *length); | |
177 | uint64_t off, len; | |
178 | if (*offset && free[bin].contains(*offset - skew - 1, &off, &len)) { | |
179 | int newbin = _choose_bin(len); | |
180 | if (newbin != bin) { | |
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); | |
185 | } | |
186 | } | |
187 | if (free[bin].contains(*offset + *length, &off, &len)) { | |
188 | int newbin = _choose_bin(len); | |
189 | if (newbin != bin) { | |
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); | |
194 | } | |
195 | } | |
196 | ||
197 | num_free -= *length; | |
198 | num_reserved -= *length; | |
199 | assert(num_free >= 0); | |
200 | assert(num_reserved >= 0); | |
201 | last_alloc = *offset + *length; | |
202 | return 0; | |
203 | } | |
204 | ||
205 | int64_t StupidAllocator::allocate( | |
206 | uint64_t want_size, | |
207 | uint64_t alloc_unit, | |
208 | uint64_t max_alloc_size, | |
209 | int64_t hint, | |
210 | mempool::bluestore_alloc::vector<AllocExtent> *extents) | |
211 | { | |
212 | uint64_t allocated_size = 0; | |
213 | uint64_t offset = 0; | |
214 | uint32_t length = 0; | |
215 | int res = 0; | |
216 | ||
217 | if (max_alloc_size == 0) { | |
218 | max_alloc_size = want_size; | |
219 | } | |
220 | ||
221 | ExtentList block_list = ExtentList(extents, 1, max_alloc_size); | |
222 | ||
223 | while (allocated_size < want_size) { | |
224 | res = allocate_int(MIN(max_alloc_size, (want_size - allocated_size)), | |
225 | alloc_unit, hint, &offset, &length); | |
226 | if (res != 0) { | |
227 | /* | |
228 | * Allocation failed. | |
229 | */ | |
230 | break; | |
231 | } | |
232 | block_list.add_extents(offset, length); | |
233 | allocated_size += length; | |
234 | hint = offset + length; | |
235 | } | |
236 | ||
237 | if (allocated_size == 0) { | |
238 | return -ENOSPC; | |
239 | } | |
240 | return allocated_size; | |
241 | } | |
242 | ||
243 | void StupidAllocator::release( | |
244 | uint64_t offset, uint64_t length) | |
245 | { | |
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); | |
250 | num_free += length; | |
251 | } | |
252 | ||
253 | uint64_t StupidAllocator::get_free() | |
254 | { | |
255 | std::lock_guard<std::mutex> l(lock); | |
256 | return num_free; | |
257 | } | |
258 | ||
259 | void StupidAllocator::dump() | |
260 | { | |
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(); | |
267 | ++p) { | |
268 | dout(0) << __func__ << " 0x" << std::hex << p.get_start() << "~" | |
269 | << p.get_len() << std::dec << dendl; | |
270 | } | |
271 | } | |
272 | } | |
273 | ||
274 | void StupidAllocator::init_add_free(uint64_t offset, uint64_t length) | |
275 | { | |
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); | |
280 | num_free += length; | |
281 | } | |
282 | ||
283 | void StupidAllocator::init_rm_free(uint64_t offset, uint64_t length) | |
284 | { | |
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); | |
298 | } | |
299 | } | |
300 | assert(rm.empty()); | |
301 | num_free -= length; | |
302 | assert(num_free >= 0); | |
303 | } | |
304 | ||
305 | ||
306 | void StupidAllocator::shutdown() | |
307 | { | |
308 | dout(1) << __func__ << dendl; | |
309 | } | |
310 |