ceph/src/test/osd/Object.h

   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;
  48   void decode(bufferlist::iterator &bp);
  49 };
  50 WRITE_CLASS_ENCODER(ContDesc)
  51
  52 std::ostream &operator<<(std::ostream &out, const ContDesc &rhs);
  53
  54 class ContentsGenerator {
  55 public:
  56
  57   class iterator_impl {
  58   public:
  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)) {
  68         ret[i] = **this;
  69       }
  70       bufferlist _ret;
  71       _ret.push_back(ret);
  72       return _ret;
  73     }
  74     virtual bool check_bl_advance(bufferlist &bl, uint64_t *off = nullptr) {
  75       uint64_t _off = 0;
  76       for (bufferlist::iterator i = bl.begin();
  77            !i.end();
  78            ++i, ++_off, ++(*this)) {
  79         if (*i != **this) {
  80           if (off)
  81             *off = _off;
  82           return false;
  83         }
  84       }
  85       return true;
  86     }
  87     virtual ~iterator_impl() {};
  88   };
  89
  90   class iterator {
  91   public:
  92     ContentsGenerator *parent;
  93     iterator_impl *impl;
  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);
 101     }
 102     iterator &operator=(const iterator &rhs) {
 103       iterator new_iter(rhs);
 104       swap(new_iter);
 105       return *this;
 106     }
 107     void swap(iterator &other) {
 108       ContentsGenerator *otherparent = other.parent;
 109       other.parent = parent;
 110       parent = otherparent;
 111
 112       iterator_impl *otherimpl = other.impl;
 113       other.impl = impl;
 114       impl = otherimpl;
 115     }
 116     bufferlist gen_bl_advance(uint64_t s) {
 117       return impl->gen_bl_advance(s);
 118     }
 119     bool check_bl_advance(bufferlist &bl, uint64_t *off = nullptr) {
 120       return impl->check_bl_advance(bl, off);
 121     }
 122     iterator(ContentsGenerator *parent, iterator_impl *impl) :
 123       parent(parent), impl(impl) {}
 124   };
 125
 126   virtual uint64_t get_length(const ContDesc &in) = 0;
 127
 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();
 134          i != ranges.end();
 135          ++i) {
 136       out.insert(i->first, i->second);
 137     }
 138   }
 139
 140
 141   virtual iterator_impl *get_iterator_impl(const ContDesc &in) = 0;
 142
 143   virtual iterator_impl *dup_iterator_impl(const iterator_impl *in) = 0;
 144
 145   virtual void put_iterator_impl(iterator_impl *in) = 0;
 146
 147   virtual ~ContentsGenerator() {};
 148
 149   iterator get_iterator(const ContDesc &in) {
 150     return iterator(this, get_iterator_impl(in));
 151   }
 152 };
 153
 154 class RandGenerator : public ContentsGenerator {
 155 public:
 156   typedef std::minstd_rand0 RandWrap;
 157
 158   class iterator_impl : public ContentsGenerator::iterator_impl {
 159   public:
 160     uint64_t pos;
 161     ContDesc cont;
 162     RandWrap rand;
 163     RandGenerator *cont_gen;
 164     char current;
 165     iterator_impl(const ContDesc &cont, RandGenerator *cont_gen) :
 166       pos(0), cont(cont), rand(cont.seqnum), cont_gen(cont_gen) {
 167       current = rand();
 168     }
 169
 170     ContDesc get_cont() const override { return cont; }
 171     uint64_t get_pos() const override { return pos; }
 172
 173     iterator_impl &operator++() override {
 174       pos++;
 175       current = rand();
 176       return *this;
 177     }
 178
 179     char operator*() override {
 180       return current;
 181     }
 182
 183     void seek(uint64_t _pos) override {
 184       if (_pos < pos) {
 185         iterator_impl begin = iterator_impl(cont, cont_gen);
 186         begin.seek(_pos);
 187         *this = begin;
 188       }
 189       while (pos < _pos) {
 190         ++(*this);
 191       }
 192     }
 193
 194     bool end() override {
 195       return pos >= cont_gen->get_length(cont);
 196     }
 197   };
 198
 199   ContentsGenerator::iterator_impl *get_iterator_impl(const ContDesc &in) override {
 200     RandGenerator::iterator_impl *i = new iterator_impl(in, this);
 201     return i;
 202   }
 203
 204   void put_iterator_impl(ContentsGenerator::iterator_impl *in) override {
 205     delete in;
 206   }
 207
 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());
 212     return retval;
 213   }
 214 };
 215
 216 class VarLenGenerator : public RandGenerator {
 217   uint64_t max_length;
 218   uint64_t min_stride_size;
 219   uint64_t max_stride_size;
 220 public:
 221   VarLenGenerator(
 222     uint64_t length, uint64_t min_stride_size, uint64_t max_stride_size) :
 223     max_length(length),
 224     min_stride_size(min_stride_size),
 225     max_stride_size(max_stride_size) {}
 226   void get_ranges_map(
 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);
 230     if (max_length == 0)
 231       return 0;
 232     return (rand() % (max_length/2)) + ((max_length - 1)/2) + 1;
 233   }
 234 };
 235
 236 class AttrGenerator : public RandGenerator {
 237   uint64_t max_len;
 238   uint64_t big_max_len;
 239 public:
 240   AttrGenerator(uint64_t max_len, uint64_t big_max_len)
 241     : max_len(max_len), big_max_len(big_max_len) {}
 242   void get_ranges_map(
 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)));
 245   }
 246   uint64_t get_length(const ContDesc &in) override {
 247     RandWrap rand(in.seqnum);
 248     // make some attrs big
 249     if (in.seqnum & 3)
 250       return (rand() % max_len);
 251     else
 252       return (rand() % big_max_len);
 253   }
 254   bufferlist gen_bl(const ContDesc &in) {
 255     bufferlist bl;
 256     for (iterator i = get_iterator(in); !i.end(); ++i) {
 257       bl.append(*i);
 258     }
 259     assert(bl.length() < big_max_len);
 260     return bl;
 261   }
 262 };
 263
 264 class AppendGenerator : public RandGenerator {
 265   uint64_t off;
 266   uint64_t alignment;
 267   uint64_t min_append_size;
 268   uint64_t max_append_size;
 269   uint64_t max_append_total;
 270
 271   uint64_t round_up(uint64_t in, uint64_t by) {
 272     if (by)
 273       in += (by - (in % by));
 274     return in;
 275   }
 276
 277 public:
 278   AppendGenerator(
 279     uint64_t off,
 280     uint64_t alignment,
 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;
 290   }
 291   uint64_t get_append_size(const ContDesc &in) {
 292     RandWrap rand(in.seqnum);
 293     return round_up(rand() % max_append_total, alignment);
 294   }
 295   uint64_t get_length(const ContDesc &in) override {
 296     return off + get_append_size(in);
 297   }
 298   void get_ranges_map(
 299     const ContDesc &cont, std::map<uint64_t, uint64_t> &out) override;
 300 };
 301
 302 class ObjectDesc {
 303 public:
 304   ObjectDesc()
 305     : exists(false), dirty(false),
 306       version(0) {}
 307   ObjectDesc(const ContDesc &init, ContentsGenerator *cont_gen)
 308     : exists(false), dirty(false),
 309       version(0) {
 310     layers.push_front(std::pair<ceph::shared_ptr<ContentsGenerator>, ContDesc>(ceph::shared_ptr<ContentsGenerator>(cont_gen), init));
 311   }
 312
 313   class iterator {
 314   public:
 315     uint64_t pos;
 316     uint64_t size;
 317     uint64_t cur_valid_till;
 318
 319     class ContState {
 320       interval_set<uint64_t> ranges;
 321       const uint64_t size;
 322
 323     public:
 324       ContDesc cont;
 325       ceph::shared_ptr<ContentsGenerator> gen;
 326       ContentsGenerator::iterator iter;
 327
 328       ContState(
 329         ContDesc _cont,
 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);
 334       }
 335
 336       const interval_set<uint64_t> &get_ranges() {
 337         return ranges;
 338       }
 339
 340       uint64_t get_size() {
 341         return gen->get_length(cont);
 342       }
 343
 344       bool covers(uint64_t pos) {
 345         return ranges.contains(pos) || (!ranges.starts_after(pos) && pos >= size);
 346       }
 347
 348       uint64_t next(uint64_t pos) {
 349         assert(!covers(pos));
 350         return ranges.starts_after(pos) ? ranges.start_after(pos) : size;
 351       }
 352
 353       uint64_t valid_till(uint64_t pos) {
 354         assert(covers(pos));
 355         return ranges.contains(pos) ?
 356           ranges.end_after(pos) :
 357           std::numeric_limits<uint64_t>::max();
 358       }
 359     };
 360     std::list<ContState> layers;
 361
 362     struct StackState {
 363       const uint64_t next;
 364       const uint64_t size;
 365     };
 366     std::list<std::pair<std::list<ContState>::iterator, StackState> > stack;
 367     std::list<ContState>::iterator current;
 368
 369     explicit iterator(ObjectDesc &obj) :
 370       pos(0),
 371       size(obj.layers.begin()->first->get_length(obj.layers.begin()->second)),
 372       cur_valid_till(0) {
 373       for (auto &&i : obj.layers) {
 374         layers.push_back({i.second, i.first, i.first->get_iterator(i.second)});
 375       }
 376       current = layers.begin();
 377
 378       adjust_stack();
 379     }
 380
 381     void adjust_stack();
 382     iterator &operator++() {
 383       assert(cur_valid_till >= pos);
 384       ++pos;
 385       if (pos >= cur_valid_till) {
 386         adjust_stack();
 387       }
 388       return *this;
 389     }
 390
 391     char operator*() {
 392       if (current == layers.end()) {
 393         return '\0';
 394       } else {
 395         return pos >= size ? '\0' : *(current->iter);
 396       }
 397     }
 398
 399     bool end() {
 400       return pos >= size;
 401     }
 402
 403     void seek(uint64_t _pos) {
 404       if (_pos < pos) {
 405         ceph_abort();
 406       }
 407       while (pos < _pos) {
 408         assert(cur_valid_till >= pos);
 409         uint64_t next = std::min(_pos - pos, cur_valid_till - pos);
 410         pos += next;
 411
 412         if (pos >= cur_valid_till) {
 413           assert(pos == cur_valid_till);
 414           adjust_stack();
 415         }
 416       }
 417       assert(pos == _pos);
 418     }
 419
 420     bufferlist gen_bl_advance(uint64_t s) {
 421       bufferlist ret;
 422       while (s > 0) {
 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));
 427         } else {
 428           ret.append_zero(next);
 429         }
 430
 431         pos += next;
 432         assert(next <= s);
 433         s -= next;
 434
 435         if (pos >= cur_valid_till) {
 436           assert(cur_valid_till == pos);
 437           adjust_stack();
 438         }
 439       }
 440       return ret;
 441     }
 442
 443     bool check_bl_advance(bufferlist &bl, uint64_t *error_at = nullptr) {
 444       uint64_t off = 0;
 445       while (off < bl.length()) {
 446         assert(cur_valid_till >= pos);
 447         uint64_t next = std::min(bl.length() - off, cur_valid_till - pos);
 448
 449         bufferlist to_check;
 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)) {
 453             if (error_at)
 454               *error_at += off;
 455             return false;
 456           }
 457         } else {
 458           uint64_t at = pos;
 459           for (auto i = to_check.begin(); !i.end(); ++i, ++at) {
 460             if (*i) {
 461               if (error_at)
 462                 *error_at = at;
 463               return false;
 464             }
 465           }
 466         }
 467
 468         pos += next;
 469         off += next;
 470         assert(off <= bl.length());
 471
 472         if (pos >= cur_valid_till) {
 473           assert(cur_valid_till == pos);
 474           adjust_stack();
 475         }
 476       }
 477       assert(off == bl.length());
 478       return true;
 479     }
 480   };
 481
 482   iterator begin() {
 483     return iterator(*this);
 484   }
 485
 486   bool deleted() {
 487     return !exists;
 488   }
 489
 490   bool has_contents() {
 491     return layers.size();
 492   }
 493
 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();
 502   }
 503   std::map<std::string, ContDesc> attrs; // Both omap and xattrs
 504   bufferlist header;
 505   bool exists;
 506   bool dirty;
 507
 508   uint64_t version;
 509   std::string redirect_target;
 510 private:
 511   std::list<std::pair<ceph::shared_ptr<ContentsGenerator>, ContDesc> > layers;
 512 };
 513
 514 #endif