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"
22 objnum(0), cursnap(0),
23 seqnum(0), prefix("") {}
28 const std::string &prefix) :
29 objnum(objnum), cursnap(cursnap),
30 seqnum(seqnum), prefix(prefix) {}
32 bool operator==(const ContDesc &rhs) {
33 return (rhs.objnum == objnum &&
34 rhs.cursnap == cursnap &&
35 rhs.seqnum == seqnum &&
36 rhs.prefix == prefix &&
40 bool operator<(const ContDesc &rhs) const {
41 return seqnum < rhs.seqnum;
44 bool operator!=(const ContDesc &rhs) {
45 return !((*this) == rhs);
47 void encode(bufferlist &bl) const;
48 void decode(bufferlist::iterator &bp);
50 WRITE_CLASS_ENCODER(ContDesc)
52 std::ostream &operator<<(std::ostream &out, const ContDesc &rhs);
54 class ContentsGenerator {
59 virtual char operator*() = 0;
60 virtual iterator_impl &operator++() = 0;
61 virtual void seek(uint64_t pos) = 0;
62 virtual bool end() = 0;
63 virtual ContDesc get_cont() const = 0;
64 virtual uint64_t get_pos() const = 0;
65 virtual bufferlist gen_bl_advance(uint64_t s) {
66 bufferptr ret = buffer::create(s);
67 for (uint64_t i = 0; i < s; ++i, ++(*this)) {
74 virtual bool check_bl_advance(bufferlist &bl, uint64_t *off = nullptr) {
76 for (bufferlist::iterator i = bl.begin();
78 ++i, ++_off, ++(*this)) {
87 virtual ~iterator_impl() {};
92 ContentsGenerator *parent;
94 char operator *() { return **impl; }
95 iterator &operator++() { ++(*impl); return *this; };
96 void seek(uint64_t pos) { impl->seek(pos); }
97 bool end() { return impl->end(); }
98 ~iterator() { parent->put_iterator_impl(impl); }
99 iterator(const iterator &rhs) : parent(rhs.parent) {
100 impl = parent->dup_iterator_impl(rhs.impl);
102 iterator &operator=(const iterator &rhs) {
103 iterator new_iter(rhs);
107 void swap(iterator &other) {
108 ContentsGenerator *otherparent = other.parent;
109 other.parent = parent;
110 parent = otherparent;
112 iterator_impl *otherimpl = other.impl;
116 bufferlist gen_bl_advance(uint64_t s) {
117 return impl->gen_bl_advance(s);
119 bool check_bl_advance(bufferlist &bl, uint64_t *off = nullptr) {
120 return impl->check_bl_advance(bl, off);
122 iterator(ContentsGenerator *parent, iterator_impl *impl) :
123 parent(parent), impl(impl) {}
126 virtual uint64_t get_length(const ContDesc &in) = 0;
128 virtual void get_ranges_map(
129 const ContDesc &cont, std::map<uint64_t, uint64_t> &out) = 0;
130 void get_ranges(const ContDesc &cont, interval_set<uint64_t> &out) {
131 std::map<uint64_t, uint64_t> ranges;
132 get_ranges_map(cont, ranges);
133 for (std::map<uint64_t, uint64_t>::iterator i = ranges.begin();
136 out.insert(i->first, i->second);
141 virtual iterator_impl *get_iterator_impl(const ContDesc &in) = 0;
143 virtual iterator_impl *dup_iterator_impl(const iterator_impl *in) = 0;
145 virtual void put_iterator_impl(iterator_impl *in) = 0;
147 virtual ~ContentsGenerator() {};
149 iterator get_iterator(const ContDesc &in) {
150 return iterator(this, get_iterator_impl(in));
154 class RandGenerator : public ContentsGenerator {
156 typedef std::minstd_rand0 RandWrap;
158 class iterator_impl : public ContentsGenerator::iterator_impl {
163 RandGenerator *cont_gen;
165 iterator_impl(const ContDesc &cont, RandGenerator *cont_gen) :
166 pos(0), cont(cont), rand(cont.seqnum), cont_gen(cont_gen) {
170 ContDesc get_cont() const override { return cont; }
171 uint64_t get_pos() const override { return pos; }
173 iterator_impl &operator++() override {
179 char operator*() override {
183 void seek(uint64_t _pos) override {
185 iterator_impl begin = iterator_impl(cont, cont_gen);
194 bool end() override {
195 return pos >= cont_gen->get_length(cont);
199 ContentsGenerator::iterator_impl *get_iterator_impl(const ContDesc &in) override {
200 RandGenerator::iterator_impl *i = new iterator_impl(in, this);
204 void put_iterator_impl(ContentsGenerator::iterator_impl *in) override {
208 ContentsGenerator::iterator_impl *dup_iterator_impl(
209 const ContentsGenerator::iterator_impl *in) override {
210 ContentsGenerator::iterator_impl *retval = get_iterator_impl(in->get_cont());
211 retval->seek(in->get_pos());
216 class VarLenGenerator : public RandGenerator {
218 uint64_t min_stride_size;
219 uint64_t max_stride_size;
222 uint64_t length, uint64_t min_stride_size, uint64_t max_stride_size) :
224 min_stride_size(min_stride_size),
225 max_stride_size(max_stride_size) {}
227 const ContDesc &cont, std::map<uint64_t, uint64_t> &out) override;
228 uint64_t get_length(const ContDesc &in) override {
229 RandWrap rand(in.seqnum);
232 return (rand() % (max_length/2)) + ((max_length - 1)/2) + 1;
236 class AttrGenerator : public RandGenerator {
238 uint64_t big_max_len;
240 AttrGenerator(uint64_t max_len, uint64_t big_max_len)
241 : max_len(max_len), big_max_len(big_max_len) {}
243 const ContDesc &cont, std::map<uint64_t, uint64_t> &out) override {
244 out.insert(std::pair<uint64_t, uint64_t>(0, get_length(cont)));
246 uint64_t get_length(const ContDesc &in) override {
247 RandWrap rand(in.seqnum);
248 // make some attrs big
250 return (rand() % max_len);
252 return (rand() % big_max_len);
254 bufferlist gen_bl(const ContDesc &in) {
256 for (iterator i = get_iterator(in); !i.end(); ++i) {
259 assert(bl.length() < big_max_len);
264 class AppendGenerator : public RandGenerator {
267 uint64_t min_append_size;
268 uint64_t max_append_size;
269 uint64_t max_append_total;
271 uint64_t round_up(uint64_t in, uint64_t by) {
273 in += (by - (in % by));
281 uint64_t min_append_size,
282 uint64_t _max_append_size,
283 uint64_t max_append_multiple) :
284 off(off), alignment(alignment),
285 min_append_size(round_up(min_append_size, alignment)),
286 max_append_size(round_up(_max_append_size, alignment)) {
287 if (_max_append_size == min_append_size)
288 max_append_size += alignment;
289 max_append_total = max_append_multiple * max_append_size;
291 uint64_t get_append_size(const ContDesc &in) {
292 RandWrap rand(in.seqnum);
293 return round_up(rand() % max_append_total, alignment);
295 uint64_t get_length(const ContDesc &in) override {
296 return off + get_append_size(in);
299 const ContDesc &cont, std::map<uint64_t, uint64_t> &out) override;
305 : exists(false), dirty(false),
307 ObjectDesc(const ContDesc &init, ContentsGenerator *cont_gen)
308 : exists(false), dirty(false),
310 layers.push_front(std::pair<ceph::shared_ptr<ContentsGenerator>, ContDesc>(ceph::shared_ptr<ContentsGenerator>(cont_gen), init));
317 uint64_t cur_valid_till;
320 interval_set<uint64_t> ranges;
325 ceph::shared_ptr<ContentsGenerator> gen;
326 ContentsGenerator::iterator iter;
330 ceph::shared_ptr<ContentsGenerator> _gen,
331 ContentsGenerator::iterator _iter)
332 : size(_gen->get_length(_cont)), cont(_cont), gen(_gen), iter(_iter) {
333 gen->get_ranges(cont, ranges);
336 const interval_set<uint64_t> &get_ranges() {
340 uint64_t get_size() {
341 return gen->get_length(cont);
344 bool covers(uint64_t pos) {
345 return ranges.contains(pos) || (!ranges.starts_after(pos) && pos >= size);
348 uint64_t next(uint64_t pos) {
349 assert(!covers(pos));
350 return ranges.starts_after(pos) ? ranges.start_after(pos) : size;
353 uint64_t valid_till(uint64_t pos) {
355 return ranges.contains(pos) ?
356 ranges.end_after(pos) :
357 std::numeric_limits<uint64_t>::max();
360 std::list<ContState> layers;
366 std::list<std::pair<std::list<ContState>::iterator, StackState> > stack;
367 std::list<ContState>::iterator current;
369 explicit iterator(ObjectDesc &obj) :
371 size(obj.layers.begin()->first->get_length(obj.layers.begin()->second)),
373 for (auto &&i : obj.layers) {
374 layers.push_back({i.second, i.first, i.first->get_iterator(i.second)});
376 current = layers.begin();
382 iterator &operator++() {
383 assert(cur_valid_till >= pos);
385 if (pos >= cur_valid_till) {
392 if (current == layers.end()) {
395 return pos >= size ? '\0' : *(current->iter);
403 void seek(uint64_t _pos) {
408 assert(cur_valid_till >= pos);
409 uint64_t next = std::min(_pos - pos, cur_valid_till - pos);
412 if (pos >= cur_valid_till) {
413 assert(pos == cur_valid_till);
420 bufferlist gen_bl_advance(uint64_t s) {
423 assert(cur_valid_till >= pos);
424 uint64_t next = std::min(s, cur_valid_till - pos);
425 if (current != layers.end() && pos < size) {
426 ret.append(current->iter.gen_bl_advance(next));
428 ret.append_zero(next);
435 if (pos >= cur_valid_till) {
436 assert(cur_valid_till == pos);
443 bool check_bl_advance(bufferlist &bl, uint64_t *error_at = nullptr) {
445 while (off < bl.length()) {
446 assert(cur_valid_till >= pos);
447 uint64_t next = std::min(bl.length() - off, cur_valid_till - pos);
450 to_check.substr_of(bl, off, next);
451 if (current != layers.end() && pos < size) {
452 if (!current->iter.check_bl_advance(to_check, error_at)) {
459 for (auto i = to_check.begin(); !i.end(); ++i, ++at) {
470 assert(off <= bl.length());
472 if (pos >= cur_valid_till) {
473 assert(cur_valid_till == pos);
477 assert(off == bl.length());
483 return iterator(*this);
490 bool has_contents() {
491 return layers.size();
494 // takes ownership of gen
495 void update(ContentsGenerator *gen, const ContDesc &next);
496 bool check(bufferlist &to_check);
497 bool check_sparse(const std::map<uint64_t, uint64_t>& extends,
498 bufferlist &to_check);
499 const ContDesc &most_recent();
500 ContentsGenerator *most_recent_gen() {
501 return layers.begin()->first.get();
503 std::map<std::string, ContDesc> attrs; // Both omap and xattrs
509 std::string redirect_target;
511 std::list<std::pair<ceph::shared_ptr<ContentsGenerator>, ContDesc> > layers;