path: root/src/test/osd/Object.h

// -*- mode:C++; tab-width:8; c-basic-offset:2; indent-tabs-mode:t -*- 
#include "include/interval_set.h"
#include "include/buffer.h"
#include "include/encoding.h"
#include <list>
#include <map>
#include <set>
#include <stack>
#include <random>

#ifndef OBJECT_H
#define OBJECT_H

/// describes an object
class ContDesc {
public:
  int objnum;
  int cursnap;
  unsigned seqnum;
  std::string prefix;
  std::string oid;

  ContDesc() :
    objnum(0), cursnap(0),
    seqnum(0), prefix("") {}

  ContDesc(int objnum,
	   int cursnap,
	   unsigned seqnum,
	   const std::string &prefix) :
    objnum(objnum), cursnap(cursnap),
    seqnum(seqnum), prefix(prefix) {}

  bool operator==(const ContDesc &rhs) {
    return (rhs.objnum == objnum &&
	    rhs.cursnap == cursnap &&
	    rhs.seqnum == seqnum &&
	    rhs.prefix == prefix &&
	    rhs.oid == oid);
  }

  bool operator<(const ContDesc &rhs) const {
    return seqnum < rhs.seqnum;
  }

  bool operator!=(const ContDesc &rhs) {
    return !((*this) == rhs);
  }
  void encode(bufferlist &bl) const;
  void decode(bufferlist::const_iterator &bp);
};
WRITE_CLASS_ENCODER(ContDesc)

std::ostream &operator<<(std::ostream &out, const ContDesc &rhs);

class ChunkDesc {
public:
  uint32_t offset;
  uint32_t length;
  std::string oid;
};

class ContentsGenerator {
public:

  class iterator_impl {
  public:
    virtual char operator*() = 0;
    virtual iterator_impl &operator++() = 0;
    virtual void seek(uint64_t pos) = 0;
    virtual bool end() = 0;
    virtual ContDesc get_cont() const = 0;
    virtual uint64_t get_pos() const = 0;
    virtual bufferlist gen_bl_advance(uint64_t s) {
      bufferptr ret = buffer::create(s);
      for (uint64_t i = 0; i < s; ++i, ++(*this)) {
	ret[i] = **this;
      }
      bufferlist _ret;
      _ret.push_back(ret);
      return _ret;
    }
    /// walk through given @c bl
    ///
    /// @param[out] off the offset of the first byte which does not match
    /// @returns true if @c bl matches with the content, false otherwise
    virtual bool check_bl_advance(bufferlist &bl, uint64_t *off = nullptr) {
      uint64_t _off = 0;
      for (bufferlist::iterator i = bl.begin();
	   !i.end();
	   ++i, ++_off, ++(*this)) {
	if (*i != **this) {
	  if (off)
	    *off = _off;
	  return false;
	}
      }
      return true;
    }
    virtual ~iterator_impl() {};
  };

  class iterator {
  public:
    ContentsGenerator *parent;
    iterator_impl *impl;
    char operator *() { return **impl; }
    iterator &operator++() { ++(*impl); return *this; };
    void seek(uint64_t pos) { impl->seek(pos); }
    bool end() { return impl->end(); }
    ~iterator() { parent->put_iterator_impl(impl); }
    iterator(const iterator &rhs) : parent(rhs.parent) {
      impl = parent->dup_iterator_impl(rhs.impl);
    }
    iterator &operator=(const iterator &rhs) {
      iterator new_iter(rhs);
      swap(new_iter);
      return *this;
    }
    void swap(iterator &other) {
      ContentsGenerator *otherparent = other.parent;
      other.parent = parent;
      parent = otherparent;

      iterator_impl *otherimpl = other.impl;
      other.impl = impl;
      impl = otherimpl;
    }
    bufferlist gen_bl_advance(uint64_t s) {
      return impl->gen_bl_advance(s);
    }
    bool check_bl_advance(bufferlist &bl, uint64_t *off = nullptr) {
      return impl->check_bl_advance(bl, off);
    }
    iterator(ContentsGenerator *parent, iterator_impl *impl) :
      parent(parent), impl(impl) {}
  };

  virtual uint64_t get_length(const ContDesc &in) = 0;

  virtual void get_ranges_map(
    const ContDesc &cont, std::map<uint64_t, uint64_t> &out) = 0;
  void get_ranges(const ContDesc &cont, interval_set<uint64_t> &out) {
    std::map<uint64_t, uint64_t> ranges;
    get_ranges_map(cont, ranges);
    for (std::map<uint64_t, uint64_t>::iterator i = ranges.begin();
	 i != ranges.end();
	 ++i) {
      out.insert(i->first, i->second);
    }
  }


  virtual iterator_impl *get_iterator_impl(const ContDesc &in) = 0;

  virtual iterator_impl *dup_iterator_impl(const iterator_impl *in) = 0;

  virtual void put_iterator_impl(iterator_impl *in) = 0;

  virtual ~ContentsGenerator() {};

  iterator get_iterator(const ContDesc &in) {
    return iterator(this, get_iterator_impl(in));
  }
};

class RandGenerator : public ContentsGenerator {
public:
  typedef std::minstd_rand0 RandWrap;

  class iterator_impl : public ContentsGenerator::iterator_impl {
  public:
    uint64_t pos;
    ContDesc cont;
    RandWrap rand;
    RandGenerator *cont_gen;
    char current;
    iterator_impl(const ContDesc &cont, RandGenerator *cont_gen) : 
      pos(0), cont(cont), rand(cont.seqnum), cont_gen(cont_gen) {
      current = rand();
    }

    ContDesc get_cont() const override { return cont; }
    uint64_t get_pos() const override { return pos; }

    iterator_impl &operator++() override {
      pos++;
      current = rand();
      return *this;
    }

    char operator*() override {
      return current;
    }

    void seek(uint64_t _pos) override {
      if (_pos < pos) {
	iterator_impl begin = iterator_impl(cont, cont_gen);
	begin.seek(_pos);
	*this = begin;
      }
      while (pos < _pos) {
	++(*this);
      }
    }

    bool end() override {
      return pos >= cont_gen->get_length(cont);
    }
  };

  ContentsGenerator::iterator_impl *get_iterator_impl(const ContDesc &in) override {
    RandGenerator::iterator_impl *i = new iterator_impl(in, this);
    return i;
  }

  void put_iterator_impl(ContentsGenerator::iterator_impl *in) override {
    delete in;
  }

  ContentsGenerator::iterator_impl *dup_iterator_impl(
    const ContentsGenerator::iterator_impl *in) override {
    ContentsGenerator::iterator_impl *retval = get_iterator_impl(in->get_cont());
    retval->seek(in->get_pos());
    return retval;
  }
};

class VarLenGenerator : public RandGenerator {
  uint64_t max_length;
  uint64_t min_stride_size;
  uint64_t max_stride_size;
public:
  VarLenGenerator(
    uint64_t length, uint64_t min_stride_size, uint64_t max_stride_size) :
    max_length(length),
    min_stride_size(min_stride_size),
    max_stride_size(max_stride_size) {}
  void get_ranges_map(
    const ContDesc &cont, std::map<uint64_t, uint64_t> &out) override;
  uint64_t get_length(const ContDesc &in) override {
    RandWrap rand(in.seqnum);
    if (max_length == 0)
      return 0;
    return (rand() % (max_length/2)) + ((max_length - 1)/2) + 1;
  }
};

class AttrGenerator : public RandGenerator {
  uint64_t max_len;
  uint64_t big_max_len;
public:
  AttrGenerator(uint64_t max_len, uint64_t big_max_len)
    : max_len(max_len), big_max_len(big_max_len) {}
  void get_ranges_map(
    const ContDesc &cont, std::map<uint64_t, uint64_t> &out) override {
    out.insert(std::pair<uint64_t, uint64_t>(0, get_length(cont)));
  }
  uint64_t get_length(const ContDesc &in) override {
    RandWrap rand(in.seqnum);
    // make some attrs big
    if (in.seqnum & 3)
      return (rand() % max_len);
    else
      return (rand() % big_max_len);
  }
  bufferlist gen_bl(const ContDesc &in) {
    bufferlist bl;
    for (iterator i = get_iterator(in); !i.end(); ++i) {
      bl.append(*i);
    }
    ceph_assert(bl.length() < big_max_len);
    return bl;
  }
};

class AppendGenerator : public RandGenerator {
  uint64_t off;
  uint64_t alignment;
  uint64_t min_append_size;
  uint64_t max_append_size;
  uint64_t max_append_total;

  uint64_t round_up(uint64_t in, uint64_t by) {
    if (by)
      in += (by - (in % by));
    return in;
  }

public:
  AppendGenerator(
    uint64_t off,
    uint64_t alignment,
    uint64_t min_append_size,
    uint64_t _max_append_size,
    uint64_t max_append_multiple) :
    off(off), alignment(alignment),
    min_append_size(round_up(min_append_size, alignment)),
    max_append_size(round_up(_max_append_size, alignment)) {
    if (_max_append_size == min_append_size)
      max_append_size += alignment;
    max_append_total = max_append_multiple * max_append_size;
  }
  uint64_t get_append_size(const ContDesc &in) {
    RandWrap rand(in.seqnum);
    return round_up(rand() % max_append_total, alignment);
  }
  uint64_t get_length(const ContDesc &in) override {
    return off + get_append_size(in);
  }
  void get_ranges_map(
    const ContDesc &cont, std::map<uint64_t, uint64_t> &out) override;
};

class ObjectDesc {
public:
  ObjectDesc()
    : exists(false), dirty(false),
      version(0) {}
  ObjectDesc(const ContDesc &init, ContentsGenerator *cont_gen)
    : exists(false), dirty(false),
      version(0) {
    layers.push_front(std::pair<std::shared_ptr<ContentsGenerator>, ContDesc>(std::shared_ptr<ContentsGenerator>(cont_gen), init));
  }

  class iterator {
  public:
    uint64_t pos;
    uint64_t size;
    uint64_t cur_valid_till;

    class ContState {
      interval_set<uint64_t> ranges;
      const uint64_t size;

    public:
      ContDesc cont;
      std::shared_ptr<ContentsGenerator> gen;
      ContentsGenerator::iterator iter;

      ContState(
	const ContDesc &_cont,
	std::shared_ptr<ContentsGenerator> _gen,
	ContentsGenerator::iterator _iter)
	: size(_gen->get_length(_cont)), cont(_cont), gen(_gen), iter(_iter) {
	gen->get_ranges(cont, ranges);
      }

      const interval_set<uint64_t> &get_ranges() {
	return ranges;
      }

      uint64_t get_size() {
	return gen->get_length(cont);
      }

      bool covers(uint64_t pos) {
	return ranges.contains(pos) || (!ranges.starts_after(pos) && pos >= size);
      }

      uint64_t next(uint64_t pos) {
	ceph_assert(!covers(pos));
	return ranges.starts_after(pos) ? ranges.start_after(pos) : size;
      }

      uint64_t valid_till(uint64_t pos) {
	ceph_assert(covers(pos));
	return ranges.contains(pos) ?
	  ranges.end_after(pos) :
	  std::numeric_limits<uint64_t>::max();
      }
    };
    // from latest to earliest
    using layers_t = std::vector<ContState>;
    layers_t layers;

    struct StackState {
      const uint64_t next;
      const uint64_t size;
    };
    std::stack<std::pair<layers_t::iterator, StackState> > stack;
    layers_t::iterator current;

    explicit iterator(ObjectDesc &obj) :
      pos(0),
      size(obj.layers.begin()->first->get_length(obj.layers.begin()->second)),
      cur_valid_till(0) {
      for (auto &&i : obj.layers) {
	layers.push_back({i.second, i.first, i.first->get_iterator(i.second)});
      }
      current = layers.begin();

      adjust_stack();
    }

    void adjust_stack();
    iterator &operator++() {
      ceph_assert(cur_valid_till >= pos);
      ++pos;
      if (pos >= cur_valid_till) {
	adjust_stack();
      }
      return *this;
    }

    char operator*() {
      if (current == layers.end()) {
	return '\0';
      } else {
	return pos >= size ? '\0' : *(current->iter);
      }
    }

    bool end() {
      return pos >= size;
    }

    // advance @c pos to given position
    void seek(uint64_t _pos) {
      if (_pos < pos) {
	ceph_abort();
      }
      while (pos < _pos) {
	ceph_assert(cur_valid_till >= pos);
	uint64_t next = std::min(_pos - pos, cur_valid_till - pos);
	pos += next;

	if (pos >= cur_valid_till) {
	  ceph_assert(pos == cur_valid_till);
	  adjust_stack();
	}
      }
      ceph_assert(pos == _pos);
    }

    // grab the bytes in the range of [pos, pos+s), and advance @c pos
    //
    // @returns the bytes in the specified range
    bufferlist gen_bl_advance(uint64_t s) {
      bufferlist ret;
      while (s > 0) {
	ceph_assert(cur_valid_till >= pos);
	uint64_t next = std::min(s, cur_valid_till - pos);
	if (current != layers.end() && pos < size) {
	  ret.append(current->iter.gen_bl_advance(next));
	} else {
	  ret.append_zero(next);
	}

	pos += next;
	ceph_assert(next <= s);
	s -= next;

	if (pos >= cur_valid_till) {
	  ceph_assert(cur_valid_till == pos);
	  adjust_stack();
	}
      }
      return ret;
    }

    // compare the range of [pos, pos+bl.length()) with given @c bl, and
    // advance @pos if all bytes in the range match
    //
    // @param error_at the offset of the first byte which does not match
    // @returns true if all bytes match, false otherwise
    bool check_bl_advance(bufferlist &bl, uint64_t *error_at = nullptr) {
      uint64_t off = 0;
      while (off < bl.length()) {
	ceph_assert(cur_valid_till >= pos);
	uint64_t next = std::min(bl.length() - off, cur_valid_till - pos);

	bufferlist to_check;
	to_check.substr_of(bl, off, next);
	if (current != layers.end() && pos < size) {
	  if (!current->iter.check_bl_advance(to_check, error_at)) {
	    if (error_at)
	      *error_at += off;
	    return false;
	  }
	} else {
	  uint64_t at = pos;
	  for (auto i = to_check.begin(); !i.end(); ++i, ++at) {
	    if (*i) {
	      if (error_at)
		*error_at = at;
	      return false;
	    }
	  }
	}

	pos += next;
	off += next;
	ceph_assert(off <= bl.length());

	if (pos >= cur_valid_till) {
	  ceph_assert(cur_valid_till == pos);
	  adjust_stack();
	}
      }
      ceph_assert(off == bl.length());
      return true;
    }
  };
    
  iterator begin() {
    return iterator(*this);
  }

  bool deleted() {
    return !exists;
  }

  bool has_contents() {
    return layers.size();
  }

  // takes ownership of gen
  void update(ContentsGenerator *gen, const ContDesc &next);
  bool check(bufferlist &to_check);
  bool check_sparse(const std::map<uint64_t, uint64_t>& extends,
		    bufferlist &to_check);
  const ContDesc &most_recent();
  ContentsGenerator *most_recent_gen() {
    return layers.begin()->first.get();
  }
  std::map<std::string, ContDesc> attrs; // Both omap and xattrs
  bufferlist header;
  bool exists;
  bool dirty;

  uint64_t version;
  std::string redirect_target;
  std::map<uint64_t, ChunkDesc> chunk_info;
private:
  std::list<std::pair<std::shared_ptr<ContentsGenerator>, ContDesc> > layers;
};

#endif