Adding upstream version 16.2.11+ds.upstream/16.2.11+dsupstream

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

1 files changed, 584 insertions, 0 deletions

diff --git a/src/os/filestore/DBObjectMap.h b/src/os/filestore/DBObjectMap.h
new file mode 100644
index 000000000..444f21eb8
--- /dev/null
+++ b/src/os/filestore/DBObjectMap.h
@@ -0,0 +1,584 @@
+// -*- mode:C++; tab-width:8; c-basic-offset:2; indent-tabs-mode:t -*-
+#ifndef DBOBJECTMAP_DB_H
+#define DBOBJECTMAP_DB_H
+
+#include "include/buffer_fwd.h"
+#include <set>
+#include <map>
+#include <string>
+
+#include <vector>
+#include <boost/scoped_ptr.hpp>
+
+#include "os/ObjectMap.h"
+#include "kv/KeyValueDB.h"
+#include "osd/osd_types.h"
+#include "common/ceph_mutex.h"
+#include "common/simple_cache.hpp"
+#include <boost/optional/optional_io.hpp>
+
+#include "SequencerPosition.h"
+
+/**
+ * DBObjectMap: Implements ObjectMap in terms of KeyValueDB
+ *
+ * Prefix space structure:
+ *
+ * @see complete_prefix
+ * @see user_prefix
+ * @see sys_prefix
+ *
+ * - HOBJECT_TO_SEQ: Contains leaf mapping from ghobject_t->header.seq and
+ *                   corresponding omap header
+ * - SYS_PREFIX: GLOBAL_STATE_KEY - contains next seq number
+ *                                  @see State
+ *                                  @see write_state
+ *                                  @see init
+ *                                  @see generate_new_header
+ * - USER_PREFIX + header_key(header->seq) + USER_PREFIX
+ *              : key->value for header->seq
+ * - USER_PREFIX + header_key(header->seq) + COMPLETE_PREFIX: see below
+ * - USER_PREFIX + header_key(header->seq) + XATTR_PREFIX: xattrs
+ * - USER_PREFIX + header_key(header->seq) + SYS_PREFIX
+ *              : USER_HEADER_KEY - omap header for header->seq
+ *              : HEADER_KEY - encoding of header for header->seq
+ *
+ * For each node (represented by a header), we
+ * store three mappings: the key mapping, the complete mapping, and the parent.
+ * The complete mapping (COMPLETE_PREFIX space) is key->key.  Each x->y entry in
+ * this mapping indicates that the key mapping contains all entries on [x,y).
+ * Note, max std::string is represented by "", so ""->"" indicates that the parent
+ * is unnecessary (@see rm_keys).  When looking up a key not contained in the
+ * the complete std::set, we have to check the parent if we don't find it in the
+ * key std::set.  During rm_keys, we copy keys from the parent and update the
+ * complete std::set to reflect the change @see rm_keys.
+ */
+class DBObjectMap : public ObjectMap {
+public:
+
+  KeyValueDB *get_db() override { return db.get(); }
+
+  /**
+   * Serializes access to next_seq as well as the in_use std::set
+   */
+  ceph::mutex header_lock = ceph::make_mutex("DBOBjectMap");
+  ceph::condition_variable header_cond;
+  ceph::condition_variable map_header_cond;
+
+  /**
+   * Std::Set of headers currently in use
+   */
+  std::set<uint64_t> in_use;
+  std::set<ghobject_t> map_header_in_use;
+
+  /**
+   * Takes the map_header_in_use entry in constructor, releases in
+   * destructor
+   */
+  class MapHeaderLock {
+    DBObjectMap *db;
+    boost::optional<ghobject_t> locked;
+
+    MapHeaderLock(const MapHeaderLock &);
+    MapHeaderLock &operator=(const MapHeaderLock &);
+  public:
+    explicit MapHeaderLock(DBObjectMap *db) : db(db) {}
+    MapHeaderLock(DBObjectMap *db, const ghobject_t &oid) : db(db), locked(oid) {
+      std::unique_lock l{db->header_lock};
+      db->map_header_cond.wait(l, [db, this] {
+        return !db->map_header_in_use.count(*locked);
+      });
+      db->map_header_in_use.insert(*locked);
+    }
+
+    const ghobject_t &get_locked() const {
+      ceph_assert(locked);
+      return *locked;
+    }
+
+    void swap(MapHeaderLock &o) {
+      ceph_assert(db == o.db);
+
+      // centos6's boost optional doesn't seem to have swap :(
+      boost::optional<ghobject_t> _locked = o.locked;
+      o.locked = locked;
+      locked = _locked;
+    }
+
+    ~MapHeaderLock() {
+      if (locked) {
+	std::lock_guard l{db->header_lock};
+	ceph_assert(db->map_header_in_use.count(*locked));
+	db->map_header_cond.notify_all();
+	db->map_header_in_use.erase(*locked);
+      }
+    }
+  };
+
+  DBObjectMap(CephContext* cct, KeyValueDB *db)
+    : ObjectMap(cct, db),
+      caches(cct->_conf->filestore_omap_header_cache_size)
+    {}
+
+  int set_keys(
+    const ghobject_t &oid,
+    const std::map<std::string, ceph::buffer::list> &set,
+    const SequencerPosition *spos=0
+    ) override;
+
+  int set_header(
+    const ghobject_t &oid,
+    const ceph::buffer::list &bl,
+    const SequencerPosition *spos=0
+    ) override;
+
+  int get_header(
+    const ghobject_t &oid,
+    ceph::buffer::list *bl
+    ) override;
+
+  int clear(
+    const ghobject_t &oid,
+    const SequencerPosition *spos=0
+    ) override;
+
+  int clear_keys_header(
+    const ghobject_t &oid,
+    const SequencerPosition *spos=0
+    ) override;
+
+  int rm_keys(
+    const ghobject_t &oid,
+    const std::set<std::string> &to_clear,
+    const SequencerPosition *spos=0
+    ) override;
+
+  int get(
+    const ghobject_t &oid,
+    ceph::buffer::list *header,
+    std::map<std::string, ceph::buffer::list> *out
+    ) override;
+
+  int get_keys(
+    const ghobject_t &oid,
+    std::set<std::string> *keys
+    ) override;
+
+  int get_values(
+    const ghobject_t &oid,
+    const std::set<std::string> &keys,
+    std::map<std::string, ceph::buffer::list> *out
+    ) override;
+
+  int check_keys(
+    const ghobject_t &oid,
+    const std::set<std::string> &keys,
+    std::set<std::string> *out
+    ) override;
+
+  int get_xattrs(
+    const ghobject_t &oid,
+    const std::set<std::string> &to_get,
+    std::map<std::string, ceph::buffer::list> *out
+    ) override;
+
+  int get_all_xattrs(
+    const ghobject_t &oid,
+    std::set<std::string> *out
+    ) override;
+
+  int set_xattrs(
+    const ghobject_t &oid,
+    const std::map<std::string, ceph::buffer::list> &to_set,
+    const SequencerPosition *spos=0
+    ) override;
+
+  int remove_xattrs(
+    const ghobject_t &oid,
+    const std::set<std::string> &to_remove,
+    const SequencerPosition *spos=0
+    ) override;
+
+  int clone(
+    const ghobject_t &oid,
+    const ghobject_t &target,
+    const SequencerPosition *spos=0
+    ) override;
+
+  int rename(
+    const ghobject_t &from,
+    const ghobject_t &to,
+    const SequencerPosition *spos=0
+    ) override;
+
+  int legacy_clone(
+    const ghobject_t &oid,
+    const ghobject_t &target,
+    const SequencerPosition *spos=0
+    ) override;
+
+  /// Read initial state from backing store
+  int get_state();
+  /// Write current state settings to DB
+  void set_state();
+  /// Read initial state and upgrade or initialize state
+  int init(bool upgrade = false);
+
+  /// Upgrade store to current version
+  int upgrade_to_v2();
+
+  /// Consistency check, debug, there must be no parallel writes
+  int check(std::ostream &out, bool repair = false, bool force = false) override;
+
+  /// Ensure that all previous operations are durable
+  int sync(const ghobject_t *oid=0, const SequencerPosition *spos=0) override;
+
+  void compact() override {
+    ceph_assert(db);
+    db->compact();
+  }
+
+  /// Util, get all objects, there must be no other concurrent access
+  int list_objects(std::vector<ghobject_t> *objs ///< [out] objects
+    );
+
+  struct _Header;
+  // Util, get all object headers, there must be no other concurrent access
+  int list_object_headers(std::vector<_Header> *out ///< [out] headers
+    );
+
+  ObjectMapIterator get_iterator(const ghobject_t &oid) override;
+
+  static const std::string USER_PREFIX;
+  static const std::string XATTR_PREFIX;
+  static const std::string SYS_PREFIX;
+  static const std::string COMPLETE_PREFIX;
+  static const std::string HEADER_KEY;
+  static const std::string USER_HEADER_KEY;
+  static const std::string GLOBAL_STATE_KEY;
+  static const std::string HOBJECT_TO_SEQ;
+
+  /// Legacy
+  static const std::string LEAF_PREFIX;
+  static const std::string REVERSE_LEAF_PREFIX;
+
+  /// persistent state for store @see generate_header
+  struct State {
+    static const __u8 CUR_VERSION = 3;
+    __u8 v;
+    uint64_t seq;
+    // legacy is false when complete regions never used
+    bool legacy;
+    State() : v(0), seq(1), legacy(false) {}
+    explicit State(uint64_t seq) : v(0), seq(seq), legacy(false) {}
+
+    void encode(ceph::buffer::list &bl) const {
+      ENCODE_START(3, 1, bl);
+      encode(v, bl);
+      encode(seq, bl);
+      encode(legacy, bl);
+      ENCODE_FINISH(bl);
+    }
+
+    void decode(ceph::buffer::list::const_iterator &bl) {
+      DECODE_START(3, bl);
+      if (struct_v >= 2)
+	decode(v, bl);
+      else
+	v = 0;
+      decode(seq, bl);
+      if (struct_v >= 3)
+	decode(legacy, bl);
+      else
+	legacy = false;
+      DECODE_FINISH(bl);
+    }
+
+    void dump(ceph::Formatter *f) const {
+      f->dump_unsigned("v", v);
+      f->dump_unsigned("seq", seq);
+      f->dump_bool("legacy", legacy);
+    }
+
+    static void generate_test_instances(std::list<State*> &o) {
+      o.push_back(new State(0));
+      o.push_back(new State(20));
+    }
+  } state;
+
+  struct _Header {
+    uint64_t seq;
+    uint64_t parent;
+    uint64_t num_children;
+
+    ghobject_t oid;
+
+    SequencerPosition spos;
+
+    void encode(ceph::buffer::list &bl) const {
+      coll_t unused;
+      ENCODE_START(2, 1, bl);
+      encode(seq, bl);
+      encode(parent, bl);
+      encode(num_children, bl);
+      encode(unused, bl);
+      encode(oid, bl);
+      encode(spos, bl);
+      ENCODE_FINISH(bl);
+    }
+
+    void decode(ceph::buffer::list::const_iterator &bl) {
+      coll_t unused;
+      DECODE_START(2, bl);
+      decode(seq, bl);
+      decode(parent, bl);
+      decode(num_children, bl);
+      decode(unused, bl);
+      decode(oid, bl);
+      if (struct_v >= 2)
+	decode(spos, bl);
+      DECODE_FINISH(bl);
+    }
+
+    void dump(ceph::Formatter *f) const {
+      f->dump_unsigned("seq", seq);
+      f->dump_unsigned("parent", parent);
+      f->dump_unsigned("num_children", num_children);
+      f->dump_stream("oid") << oid;
+    }
+
+    static void generate_test_instances(std::list<_Header*> &o) {
+      o.push_back(new _Header);
+      o.push_back(new _Header);
+      o.back()->parent = 20;
+      o.back()->seq = 30;
+    }
+
+    size_t length() {
+      return sizeof(_Header);
+    }
+
+    _Header() : seq(0), parent(0), num_children(1) {}
+  };
+
+  /// Std::String munging (public for testing)
+  static std::string ghobject_key(const ghobject_t &oid);
+  static std::string ghobject_key_v0(coll_t c, const ghobject_t &oid);
+  static int is_buggy_ghobject_key_v1(CephContext* cct,
+				      const std::string &in);
+private:
+  /// Implicit lock on Header->seq
+  typedef std::shared_ptr<_Header> Header;
+  ceph::mutex cache_lock = ceph::make_mutex("DBObjectMap::CacheLock");
+  SimpleLRU<ghobject_t, _Header> caches;
+
+  std::string map_header_key(const ghobject_t &oid);
+  std::string header_key(uint64_t seq);
+  std::string complete_prefix(Header header);
+  std::string user_prefix(Header header);
+  std::string sys_prefix(Header header);
+  std::string xattr_prefix(Header header);
+  std::string sys_parent_prefix(_Header header);
+  std::string sys_parent_prefix(Header header) {
+    return sys_parent_prefix(*header);
+  }
+
+  class EmptyIteratorImpl : public ObjectMapIteratorImpl {
+  public:
+    int seek_to_first() override { return 0; }
+    int seek_to_last() { return 0; }
+    int upper_bound(const std::string &after) override { return 0; }
+    int lower_bound(const std::string &to) override { return 0; }
+    bool valid() override { return false; }
+    int next() override { ceph_abort(); return 0; }
+    std::string key() override { ceph_abort(); return ""; }
+    ceph::buffer::list value() override { ceph_abort(); return ceph::buffer::list(); }
+    int status() override { return 0; }
+  };
+
+
+  /// Iterator
+  class DBObjectMapIteratorImpl : public ObjectMapIteratorImpl {
+  public:
+    DBObjectMap *map;
+
+    /// NOTE: implicit lock hlock->get_locked() when returned out of the class
+    MapHeaderLock hlock;
+    /// NOTE: implicit lock on header->seq AND for all ancestors
+    Header header;
+
+    /// parent_iter == NULL iff no parent
+    std::shared_ptr<DBObjectMapIteratorImpl> parent_iter;
+    KeyValueDB::Iterator key_iter;
+    KeyValueDB::Iterator complete_iter;
+
+    /// cur_iter points to currently valid iterator
+    std::shared_ptr<ObjectMapIteratorImpl> cur_iter;
+    int r;
+
+    /// init() called, key_iter, complete_iter, parent_iter filled in
+    bool ready;
+    /// past end
+    bool invalid;
+
+    DBObjectMapIteratorImpl(DBObjectMap *map, Header header) :
+      map(map), hlock(map), header(header), r(0), ready(false), invalid(true) {}
+    int seek_to_first() override;
+    int seek_to_last();
+    int upper_bound(const std::string &after) override;
+    int lower_bound(const std::string &to) override;
+    bool valid() override;
+    int next() override;
+    std::string key() override;
+    ceph::buffer::list value() override;
+    int status() override;
+
+    bool on_parent() {
+      return cur_iter == parent_iter;
+    }
+
+    /// skips to next valid parent entry
+    int next_parent();
+    
+    /// first parent() >= to
+    int lower_bound_parent(const std::string &to);
+
+    /**
+     * Tests whether to_test is in complete region
+     *
+     * postcondition: complete_iter will be max s.t. complete_iter->value > to_test
+     */
+    int in_complete_region(const std::string &to_test, ///< [in] key to test
+			   std::string *begin,         ///< [out] beginning of region
+			   std::string *end            ///< [out] end of region
+      ); ///< @returns true if to_test is in the complete region, else false
+
+  private:
+    int init();
+    bool valid_parent();
+    int adjust();
+  };
+
+  typedef std::shared_ptr<DBObjectMapIteratorImpl> DBObjectMapIterator;
+  DBObjectMapIterator _get_iterator(Header header) {
+    return std::make_shared<DBObjectMapIteratorImpl>(this, header);
+  }
+
+  /// sys
+
+  /// Removes node corresponding to header
+  void clear_header(Header header, KeyValueDB::Transaction t);
+
+  /// Std::Set node containing input to new contents
+  void set_header(Header input, KeyValueDB::Transaction t);
+
+  /// Remove leaf node corresponding to oid in c
+  void remove_map_header(
+    const MapHeaderLock &l,
+    const ghobject_t &oid,
+    Header header,
+    KeyValueDB::Transaction t);
+
+  /// Std::Set leaf node for c and oid to the value of header
+  void set_map_header(
+    const MapHeaderLock &l,
+    const ghobject_t &oid, _Header header,
+    KeyValueDB::Transaction t);
+
+  /// Std::Set leaf node for c and oid to the value of header
+  bool check_spos(const ghobject_t &oid,
+		  Header header,
+		  const SequencerPosition *spos);
+
+  /// Lookup or create header for c oid
+  Header lookup_create_map_header(
+    const MapHeaderLock &l,
+    const ghobject_t &oid,
+    KeyValueDB::Transaction t);
+
+  /**
+   * Generate new header for c oid with new seq number
+   *
+   * Has the side effect of synchronously saving the new DBObjectMap state
+   */
+  Header _generate_new_header(const ghobject_t &oid, Header parent);
+  Header generate_new_header(const ghobject_t &oid, Header parent) {
+    std::lock_guard l{header_lock};
+    return _generate_new_header(oid, parent);
+  }
+
+  /// Lookup leaf header for c oid
+  Header _lookup_map_header(
+    const MapHeaderLock &l,
+    const ghobject_t &oid);
+  Header lookup_map_header(
+    const MapHeaderLock &l2,
+    const ghobject_t &oid) {
+    std::lock_guard l{header_lock};
+    return _lookup_map_header(l2, oid);
+  }
+
+  /// Lookup header node for input
+  Header lookup_parent(Header input);
+
+
+  /// Helpers
+  int _get_header(Header header, ceph::buffer::list *bl);
+
+  /// Scan keys in header into out_keys and out_values (if nonnull)
+  int scan(Header header,
+	   const std::set<std::string> &in_keys,
+	   std::set<std::string> *out_keys,
+	   std::map<std::string, ceph::buffer::list> *out_values);
+
+  /// Remove header and all related prefixes
+  int _clear(Header header,
+	     KeyValueDB::Transaction t);
+
+  /* Scan complete region bumping *begin to the beginning of any
+   * containing region and adding all complete region keys between
+   * the updated begin and end to the complete_keys_to_remove std::set */
+  int merge_new_complete(DBObjectMapIterator &iter,
+			 std::string *begin,
+			 const std::string &end,
+			 std::set<std::string> *complete_keys_to_remove);
+
+  /// Writes out State (mainly next_seq)
+  int write_state(KeyValueDB::Transaction _t =
+		  KeyValueDB::Transaction());
+
+  /// Copies header entry from parent @see rm_keys
+  int copy_up_header(Header header,
+		     KeyValueDB::Transaction t);
+
+  /// Sets header @see set_header
+  void _set_header(Header header, const ceph::buffer::list &bl,
+		   KeyValueDB::Transaction t);
+
+  /**
+   * Removes header seq lock and possibly object lock
+   * once Header is out of scope
+   * @see lookup_parent
+   * @see generate_new_header
+   */
+  class RemoveOnDelete {
+  public:
+    DBObjectMap *db;
+    explicit RemoveOnDelete(DBObjectMap *db) :
+      db(db) {}
+    void operator() (_Header *header) {
+      std::lock_guard l{db->header_lock};
+      ceph_assert(db->in_use.count(header->seq));
+      db->in_use.erase(header->seq);
+      db->header_cond.notify_all();
+      delete header;
+    }
+  };
+  friend class RemoveOnDelete;
+};
+WRITE_CLASS_ENCODER(DBObjectMap::_Header)
+WRITE_CLASS_ENCODER(DBObjectMap::State)
+
+std::ostream& operator<<(std::ostream& out, const DBObjectMap::_Header& h);
+
+#endif