]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | // -*- mode:C++; tab-width:8; c-basic-offset:2; indent-tabs-mode:t -*- |
2 | #include "include/interval_set.h" | |
3 | #include "include/buffer.h" | |
4 | #include "include/encoding.h" | |
5 | #include <list> | |
6 | #include <map> | |
7 | #include <set> | |
8 | #include <random> | |
9 | ||
10 | #ifndef OBJECT_H | |
11 | #define OBJECT_H | |
12 | ||
13 | class ContDesc { | |
14 | public: | |
15 | int objnum; | |
16 | int cursnap; | |
17 | unsigned seqnum; | |
18 | std::string prefix; | |
19 | std::string oid; | |
20 | ||
21 | ContDesc() : | |
22 | objnum(0), cursnap(0), | |
23 | seqnum(0), prefix("") {} | |
24 | ||
25 | ContDesc(int objnum, | |
26 | int cursnap, | |
27 | unsigned seqnum, | |
28 | const std::string &prefix) : | |
29 | objnum(objnum), cursnap(cursnap), | |
30 | seqnum(seqnum), prefix(prefix) {} | |
31 | ||
32 | bool operator==(const ContDesc &rhs) { | |
33 | return (rhs.objnum == objnum && | |
34 | rhs.cursnap == cursnap && | |
35 | rhs.seqnum == seqnum && | |
36 | rhs.prefix == prefix && | |
37 | rhs.oid == oid); | |
38 | } | |
39 | ||
40 | bool operator<(const ContDesc &rhs) const { | |
41 | return seqnum < rhs.seqnum; | |
42 | } | |
43 | ||
44 | bool operator!=(const ContDesc &rhs) { | |
45 | return !((*this) == rhs); | |
46 | } | |
47 | void encode(bufferlist &bl) const; | |
11fdf7f2 | 48 | void decode(bufferlist::const_iterator &bp); |
7c673cae FG |
49 | }; |
50 | WRITE_CLASS_ENCODER(ContDesc) | |
51 | ||
52 | std::ostream &operator<<(std::ostream &out, const ContDesc &rhs); | |
53 | ||
11fdf7f2 TL |
54 | class ChunkDesc { |
55 | public: | |
56 | uint32_t offset; | |
57 | uint32_t length; | |
58 | std::string oid; | |
59 | }; | |
60 | ||
7c673cae FG |
61 | class ContentsGenerator { |
62 | public: | |
63 | ||
64 | class iterator_impl { | |
65 | public: | |
66 | virtual char operator*() = 0; | |
67 | virtual iterator_impl &operator++() = 0; | |
68 | virtual void seek(uint64_t pos) = 0; | |
69 | virtual bool end() = 0; | |
70 | virtual ContDesc get_cont() const = 0; | |
71 | virtual uint64_t get_pos() const = 0; | |
72 | virtual bufferlist gen_bl_advance(uint64_t s) { | |
73 | bufferptr ret = buffer::create(s); | |
74 | for (uint64_t i = 0; i < s; ++i, ++(*this)) { | |
75 | ret[i] = **this; | |
76 | } | |
77 | bufferlist _ret; | |
78 | _ret.push_back(ret); | |
79 | return _ret; | |
80 | } | |
81 | virtual bool check_bl_advance(bufferlist &bl, uint64_t *off = nullptr) { | |
82 | uint64_t _off = 0; | |
83 | for (bufferlist::iterator i = bl.begin(); | |
84 | !i.end(); | |
85 | ++i, ++_off, ++(*this)) { | |
86 | if (*i != **this) { | |
87 | if (off) | |
88 | *off = _off; | |
89 | return false; | |
90 | } | |
91 | } | |
92 | return true; | |
93 | } | |
94 | virtual ~iterator_impl() {}; | |
95 | }; | |
96 | ||
97 | class iterator { | |
98 | public: | |
99 | ContentsGenerator *parent; | |
100 | iterator_impl *impl; | |
101 | char operator *() { return **impl; } | |
102 | iterator &operator++() { ++(*impl); return *this; }; | |
103 | void seek(uint64_t pos) { impl->seek(pos); } | |
104 | bool end() { return impl->end(); } | |
105 | ~iterator() { parent->put_iterator_impl(impl); } | |
106 | iterator(const iterator &rhs) : parent(rhs.parent) { | |
107 | impl = parent->dup_iterator_impl(rhs.impl); | |
108 | } | |
109 | iterator &operator=(const iterator &rhs) { | |
110 | iterator new_iter(rhs); | |
111 | swap(new_iter); | |
112 | return *this; | |
113 | } | |
114 | void swap(iterator &other) { | |
115 | ContentsGenerator *otherparent = other.parent; | |
116 | other.parent = parent; | |
117 | parent = otherparent; | |
118 | ||
119 | iterator_impl *otherimpl = other.impl; | |
120 | other.impl = impl; | |
121 | impl = otherimpl; | |
122 | } | |
123 | bufferlist gen_bl_advance(uint64_t s) { | |
124 | return impl->gen_bl_advance(s); | |
125 | } | |
126 | bool check_bl_advance(bufferlist &bl, uint64_t *off = nullptr) { | |
127 | return impl->check_bl_advance(bl, off); | |
128 | } | |
129 | iterator(ContentsGenerator *parent, iterator_impl *impl) : | |
130 | parent(parent), impl(impl) {} | |
131 | }; | |
132 | ||
133 | virtual uint64_t get_length(const ContDesc &in) = 0; | |
134 | ||
135 | virtual void get_ranges_map( | |
136 | const ContDesc &cont, std::map<uint64_t, uint64_t> &out) = 0; | |
137 | void get_ranges(const ContDesc &cont, interval_set<uint64_t> &out) { | |
138 | std::map<uint64_t, uint64_t> ranges; | |
139 | get_ranges_map(cont, ranges); | |
140 | for (std::map<uint64_t, uint64_t>::iterator i = ranges.begin(); | |
141 | i != ranges.end(); | |
142 | ++i) { | |
143 | out.insert(i->first, i->second); | |
144 | } | |
145 | } | |
146 | ||
147 | ||
148 | virtual iterator_impl *get_iterator_impl(const ContDesc &in) = 0; | |
149 | ||
150 | virtual iterator_impl *dup_iterator_impl(const iterator_impl *in) = 0; | |
151 | ||
152 | virtual void put_iterator_impl(iterator_impl *in) = 0; | |
153 | ||
154 | virtual ~ContentsGenerator() {}; | |
155 | ||
156 | iterator get_iterator(const ContDesc &in) { | |
157 | return iterator(this, get_iterator_impl(in)); | |
158 | } | |
159 | }; | |
160 | ||
161 | class RandGenerator : public ContentsGenerator { | |
162 | public: | |
163 | typedef std::minstd_rand0 RandWrap; | |
164 | ||
165 | class iterator_impl : public ContentsGenerator::iterator_impl { | |
166 | public: | |
167 | uint64_t pos; | |
168 | ContDesc cont; | |
169 | RandWrap rand; | |
170 | RandGenerator *cont_gen; | |
171 | char current; | |
172 | iterator_impl(const ContDesc &cont, RandGenerator *cont_gen) : | |
173 | pos(0), cont(cont), rand(cont.seqnum), cont_gen(cont_gen) { | |
174 | current = rand(); | |
175 | } | |
176 | ||
177 | ContDesc get_cont() const override { return cont; } | |
178 | uint64_t get_pos() const override { return pos; } | |
179 | ||
180 | iterator_impl &operator++() override { | |
181 | pos++; | |
182 | current = rand(); | |
183 | return *this; | |
184 | } | |
185 | ||
186 | char operator*() override { | |
187 | return current; | |
188 | } | |
189 | ||
190 | void seek(uint64_t _pos) override { | |
191 | if (_pos < pos) { | |
192 | iterator_impl begin = iterator_impl(cont, cont_gen); | |
193 | begin.seek(_pos); | |
194 | *this = begin; | |
195 | } | |
196 | while (pos < _pos) { | |
197 | ++(*this); | |
198 | } | |
199 | } | |
200 | ||
201 | bool end() override { | |
202 | return pos >= cont_gen->get_length(cont); | |
203 | } | |
204 | }; | |
205 | ||
206 | ContentsGenerator::iterator_impl *get_iterator_impl(const ContDesc &in) override { | |
207 | RandGenerator::iterator_impl *i = new iterator_impl(in, this); | |
208 | return i; | |
209 | } | |
210 | ||
211 | void put_iterator_impl(ContentsGenerator::iterator_impl *in) override { | |
212 | delete in; | |
213 | } | |
214 | ||
215 | ContentsGenerator::iterator_impl *dup_iterator_impl( | |
216 | const ContentsGenerator::iterator_impl *in) override { | |
217 | ContentsGenerator::iterator_impl *retval = get_iterator_impl(in->get_cont()); | |
218 | retval->seek(in->get_pos()); | |
219 | return retval; | |
220 | } | |
221 | }; | |
222 | ||
223 | class VarLenGenerator : public RandGenerator { | |
224 | uint64_t max_length; | |
225 | uint64_t min_stride_size; | |
226 | uint64_t max_stride_size; | |
227 | public: | |
228 | VarLenGenerator( | |
229 | uint64_t length, uint64_t min_stride_size, uint64_t max_stride_size) : | |
230 | max_length(length), | |
231 | min_stride_size(min_stride_size), | |
232 | max_stride_size(max_stride_size) {} | |
233 | void get_ranges_map( | |
234 | const ContDesc &cont, std::map<uint64_t, uint64_t> &out) override; | |
235 | uint64_t get_length(const ContDesc &in) override { | |
236 | RandWrap rand(in.seqnum); | |
237 | if (max_length == 0) | |
238 | return 0; | |
239 | return (rand() % (max_length/2)) + ((max_length - 1)/2) + 1; | |
240 | } | |
241 | }; | |
242 | ||
243 | class AttrGenerator : public RandGenerator { | |
244 | uint64_t max_len; | |
245 | uint64_t big_max_len; | |
246 | public: | |
247 | AttrGenerator(uint64_t max_len, uint64_t big_max_len) | |
248 | : max_len(max_len), big_max_len(big_max_len) {} | |
249 | void get_ranges_map( | |
250 | const ContDesc &cont, std::map<uint64_t, uint64_t> &out) override { | |
251 | out.insert(std::pair<uint64_t, uint64_t>(0, get_length(cont))); | |
252 | } | |
253 | uint64_t get_length(const ContDesc &in) override { | |
254 | RandWrap rand(in.seqnum); | |
255 | // make some attrs big | |
256 | if (in.seqnum & 3) | |
257 | return (rand() % max_len); | |
258 | else | |
259 | return (rand() % big_max_len); | |
260 | } | |
261 | bufferlist gen_bl(const ContDesc &in) { | |
262 | bufferlist bl; | |
263 | for (iterator i = get_iterator(in); !i.end(); ++i) { | |
264 | bl.append(*i); | |
265 | } | |
11fdf7f2 | 266 | ceph_assert(bl.length() < big_max_len); |
7c673cae FG |
267 | return bl; |
268 | } | |
269 | }; | |
270 | ||
271 | class AppendGenerator : public RandGenerator { | |
272 | uint64_t off; | |
273 | uint64_t alignment; | |
274 | uint64_t min_append_size; | |
275 | uint64_t max_append_size; | |
276 | uint64_t max_append_total; | |
277 | ||
278 | uint64_t round_up(uint64_t in, uint64_t by) { | |
279 | if (by) | |
280 | in += (by - (in % by)); | |
281 | return in; | |
282 | } | |
283 | ||
284 | public: | |
285 | AppendGenerator( | |
286 | uint64_t off, | |
287 | uint64_t alignment, | |
288 | uint64_t min_append_size, | |
289 | uint64_t _max_append_size, | |
290 | uint64_t max_append_multiple) : | |
291 | off(off), alignment(alignment), | |
292 | min_append_size(round_up(min_append_size, alignment)), | |
293 | max_append_size(round_up(_max_append_size, alignment)) { | |
294 | if (_max_append_size == min_append_size) | |
295 | max_append_size += alignment; | |
296 | max_append_total = max_append_multiple * max_append_size; | |
297 | } | |
298 | uint64_t get_append_size(const ContDesc &in) { | |
299 | RandWrap rand(in.seqnum); | |
300 | return round_up(rand() % max_append_total, alignment); | |
301 | } | |
302 | uint64_t get_length(const ContDesc &in) override { | |
303 | return off + get_append_size(in); | |
304 | } | |
305 | void get_ranges_map( | |
306 | const ContDesc &cont, std::map<uint64_t, uint64_t> &out) override; | |
307 | }; | |
308 | ||
309 | class ObjectDesc { | |
310 | public: | |
311 | ObjectDesc() | |
312 | : exists(false), dirty(false), | |
313 | version(0) {} | |
314 | ObjectDesc(const ContDesc &init, ContentsGenerator *cont_gen) | |
315 | : exists(false), dirty(false), | |
316 | version(0) { | |
11fdf7f2 | 317 | layers.push_front(std::pair<std::shared_ptr<ContentsGenerator>, ContDesc>(std::shared_ptr<ContentsGenerator>(cont_gen), init)); |
7c673cae FG |
318 | } |
319 | ||
320 | class iterator { | |
321 | public: | |
322 | uint64_t pos; | |
323 | uint64_t size; | |
324 | uint64_t cur_valid_till; | |
325 | ||
326 | class ContState { | |
327 | interval_set<uint64_t> ranges; | |
328 | const uint64_t size; | |
329 | ||
330 | public: | |
331 | ContDesc cont; | |
11fdf7f2 | 332 | std::shared_ptr<ContentsGenerator> gen; |
7c673cae FG |
333 | ContentsGenerator::iterator iter; |
334 | ||
335 | ContState( | |
11fdf7f2 TL |
336 | const ContDesc &_cont, |
337 | std::shared_ptr<ContentsGenerator> _gen, | |
7c673cae FG |
338 | ContentsGenerator::iterator _iter) |
339 | : size(_gen->get_length(_cont)), cont(_cont), gen(_gen), iter(_iter) { | |
340 | gen->get_ranges(cont, ranges); | |
341 | } | |
342 | ||
343 | const interval_set<uint64_t> &get_ranges() { | |
344 | return ranges; | |
345 | } | |
346 | ||
347 | uint64_t get_size() { | |
348 | return gen->get_length(cont); | |
349 | } | |
350 | ||
351 | bool covers(uint64_t pos) { | |
352 | return ranges.contains(pos) || (!ranges.starts_after(pos) && pos >= size); | |
353 | } | |
354 | ||
355 | uint64_t next(uint64_t pos) { | |
11fdf7f2 | 356 | ceph_assert(!covers(pos)); |
7c673cae FG |
357 | return ranges.starts_after(pos) ? ranges.start_after(pos) : size; |
358 | } | |
359 | ||
360 | uint64_t valid_till(uint64_t pos) { | |
11fdf7f2 | 361 | ceph_assert(covers(pos)); |
7c673cae FG |
362 | return ranges.contains(pos) ? |
363 | ranges.end_after(pos) : | |
364 | std::numeric_limits<uint64_t>::max(); | |
365 | } | |
366 | }; | |
367 | std::list<ContState> layers; | |
368 | ||
369 | struct StackState { | |
370 | const uint64_t next; | |
371 | const uint64_t size; | |
372 | }; | |
373 | std::list<std::pair<std::list<ContState>::iterator, StackState> > stack; | |
374 | std::list<ContState>::iterator current; | |
375 | ||
376 | explicit iterator(ObjectDesc &obj) : | |
377 | pos(0), | |
378 | size(obj.layers.begin()->first->get_length(obj.layers.begin()->second)), | |
379 | cur_valid_till(0) { | |
380 | for (auto &&i : obj.layers) { | |
381 | layers.push_back({i.second, i.first, i.first->get_iterator(i.second)}); | |
382 | } | |
383 | current = layers.begin(); | |
384 | ||
385 | adjust_stack(); | |
386 | } | |
387 | ||
388 | void adjust_stack(); | |
389 | iterator &operator++() { | |
11fdf7f2 | 390 | ceph_assert(cur_valid_till >= pos); |
7c673cae FG |
391 | ++pos; |
392 | if (pos >= cur_valid_till) { | |
393 | adjust_stack(); | |
394 | } | |
395 | return *this; | |
396 | } | |
397 | ||
398 | char operator*() { | |
399 | if (current == layers.end()) { | |
400 | return '\0'; | |
401 | } else { | |
402 | return pos >= size ? '\0' : *(current->iter); | |
403 | } | |
404 | } | |
405 | ||
406 | bool end() { | |
407 | return pos >= size; | |
408 | } | |
409 | ||
410 | void seek(uint64_t _pos) { | |
411 | if (_pos < pos) { | |
412 | ceph_abort(); | |
413 | } | |
414 | while (pos < _pos) { | |
11fdf7f2 | 415 | ceph_assert(cur_valid_till >= pos); |
7c673cae FG |
416 | uint64_t next = std::min(_pos - pos, cur_valid_till - pos); |
417 | pos += next; | |
418 | ||
419 | if (pos >= cur_valid_till) { | |
11fdf7f2 | 420 | ceph_assert(pos == cur_valid_till); |
7c673cae FG |
421 | adjust_stack(); |
422 | } | |
423 | } | |
11fdf7f2 | 424 | ceph_assert(pos == _pos); |
7c673cae FG |
425 | } |
426 | ||
427 | bufferlist gen_bl_advance(uint64_t s) { | |
428 | bufferlist ret; | |
429 | while (s > 0) { | |
11fdf7f2 | 430 | ceph_assert(cur_valid_till >= pos); |
7c673cae FG |
431 | uint64_t next = std::min(s, cur_valid_till - pos); |
432 | if (current != layers.end() && pos < size) { | |
433 | ret.append(current->iter.gen_bl_advance(next)); | |
434 | } else { | |
435 | ret.append_zero(next); | |
436 | } | |
437 | ||
438 | pos += next; | |
11fdf7f2 | 439 | ceph_assert(next <= s); |
7c673cae FG |
440 | s -= next; |
441 | ||
442 | if (pos >= cur_valid_till) { | |
11fdf7f2 | 443 | ceph_assert(cur_valid_till == pos); |
7c673cae FG |
444 | adjust_stack(); |
445 | } | |
446 | } | |
447 | return ret; | |
448 | } | |
449 | ||
450 | bool check_bl_advance(bufferlist &bl, uint64_t *error_at = nullptr) { | |
451 | uint64_t off = 0; | |
452 | while (off < bl.length()) { | |
11fdf7f2 | 453 | ceph_assert(cur_valid_till >= pos); |
7c673cae FG |
454 | uint64_t next = std::min(bl.length() - off, cur_valid_till - pos); |
455 | ||
456 | bufferlist to_check; | |
457 | to_check.substr_of(bl, off, next); | |
458 | if (current != layers.end() && pos < size) { | |
459 | if (!current->iter.check_bl_advance(to_check, error_at)) { | |
460 | if (error_at) | |
461 | *error_at += off; | |
462 | return false; | |
463 | } | |
464 | } else { | |
465 | uint64_t at = pos; | |
466 | for (auto i = to_check.begin(); !i.end(); ++i, ++at) { | |
467 | if (*i) { | |
468 | if (error_at) | |
469 | *error_at = at; | |
470 | return false; | |
471 | } | |
472 | } | |
473 | } | |
474 | ||
475 | pos += next; | |
476 | off += next; | |
11fdf7f2 | 477 | ceph_assert(off <= bl.length()); |
7c673cae FG |
478 | |
479 | if (pos >= cur_valid_till) { | |
11fdf7f2 | 480 | ceph_assert(cur_valid_till == pos); |
7c673cae FG |
481 | adjust_stack(); |
482 | } | |
483 | } | |
11fdf7f2 | 484 | ceph_assert(off == bl.length()); |
7c673cae FG |
485 | return true; |
486 | } | |
487 | }; | |
488 | ||
489 | iterator begin() { | |
490 | return iterator(*this); | |
491 | } | |
492 | ||
493 | bool deleted() { | |
494 | return !exists; | |
495 | } | |
496 | ||
497 | bool has_contents() { | |
498 | return layers.size(); | |
499 | } | |
500 | ||
501 | // takes ownership of gen | |
502 | void update(ContentsGenerator *gen, const ContDesc &next); | |
503 | bool check(bufferlist &to_check); | |
504 | bool check_sparse(const std::map<uint64_t, uint64_t>& extends, | |
505 | bufferlist &to_check); | |
506 | const ContDesc &most_recent(); | |
507 | ContentsGenerator *most_recent_gen() { | |
508 | return layers.begin()->first.get(); | |
509 | } | |
510 | std::map<std::string, ContDesc> attrs; // Both omap and xattrs | |
511 | bufferlist header; | |
512 | bool exists; | |
513 | bool dirty; | |
514 | ||
515 | uint64_t version; | |
31f18b77 | 516 | std::string redirect_target; |
11fdf7f2 | 517 | std::map<uint64_t, ChunkDesc> chunk_info; |
7c673cae | 518 | private: |
11fdf7f2 | 519 | std::list<std::pair<std::shared_ptr<ContentsGenerator>, ContDesc> > layers; |
7c673cae FG |
520 | }; |
521 | ||
522 | #endif |