ceph/src/os/filestore/DBObjectMap.h

   1 // -*- mode:C++; tab-width:8; c-basic-offset:2; indent-tabs-mode:t -*-
   2 #ifndef DBOBJECTMAP_DB_H
   3 #define DBOBJECTMAP_DB_H
   4
   5 #include "include/buffer_fwd.h"
   6 #include <set>
   7 #include <map>
   8 #include <string>
   9
  10 #include <vector>
  11 #include <boost/scoped_ptr.hpp>
  12
  13 #include "os/ObjectMap.h"
  14 #include "kv/KeyValueDB.h"
  15 #include "osd/osd_types.h"
  16 #include "common/Mutex.h"
  17 #include "common/Cond.h"
  18 #include "common/simple_cache.hpp"
  19 #include <boost/optional/optional_io.hpp>
  20
  21 #include "SequencerPosition.h"
  22
  23 /**
  24  * DBObjectMap: Implements ObjectMap in terms of KeyValueDB
  25  *
  26  * Prefix space structure:
  27  *
  28  * @see complete_prefix
  29  * @see user_prefix
  30  * @see sys_prefix
  31  *
  32  * - HOBJECT_TO_SEQ: Contains leaf mapping from ghobject_t->header.seq and
  33  *                   corresponding omap header
  34  * - SYS_PREFIX: GLOBAL_STATE_KEY - contains next seq number
  35  *                                  @see State
  36  *                                  @see write_state
  37  *                                  @see init
  38  *                                  @see generate_new_header
  39  * - USER_PREFIX + header_key(header->seq) + USER_PREFIX
  40  *              : key->value for header->seq
  41  * - USER_PREFIX + header_key(header->seq) + COMPLETE_PREFIX: see below
  42  * - USER_PREFIX + header_key(header->seq) + XATTR_PREFIX: xattrs
  43  * - USER_PREFIX + header_key(header->seq) + SYS_PREFIX
  44  *              : USER_HEADER_KEY - omap header for header->seq
  45  *              : HEADER_KEY - encoding of header for header->seq
  46  *
  47  * For each node (represented by a header), we
  48  * store three mappings: the key mapping, the complete mapping, and the parent.
  49  * The complete mapping (COMPLETE_PREFIX space) is key->key.  Each x->y entry in
  50  * this mapping indicates that the key mapping contains all entries on [x,y).
  51  * Note, max string is represented by "", so ""->"" indicates that the parent
  52  * is unnecessary (@see rm_keys).  When looking up a key not contained in the
  53  * the complete set, we have to check the parent if we don't find it in the
  54  * key set.  During rm_keys, we copy keys from the parent and update the
  55  * complete set to reflect the change @see rm_keys.
  56  */
  57 class DBObjectMap : public ObjectMap {
  58 public:
  59
  60   KeyValueDB *get_db() override { return db.get(); }
  61
  62   /**
  63    * Serializes access to next_seq as well as the in_use set
  64    */
  65   Mutex header_lock;
  66   Cond header_cond;
  67   Cond map_header_cond;
  68
  69   /**
  70    * Set of headers currently in use
  71    */
  72   set<uint64_t> in_use;
  73   set<ghobject_t> map_header_in_use;
  74
  75   /**
  76    * Takes the map_header_in_use entry in constructor, releases in
  77    * destructor
  78    */
  79   class MapHeaderLock {
  80     DBObjectMap *db;
  81     boost::optional<ghobject_t> locked;
  82
  83     MapHeaderLock(const MapHeaderLock &);
  84     MapHeaderLock &operator=(const MapHeaderLock &);
  85   public:
  86     explicit MapHeaderLock(DBObjectMap *db) : db(db) {}
  87     MapHeaderLock(DBObjectMap *db, const ghobject_t &oid) : db(db), locked(oid) {
  88       Mutex::Locker l(db->header_lock);
  89       while (db->map_header_in_use.count(*locked))
  90         db->map_header_cond.Wait(db->header_lock);
  91       db->map_header_in_use.insert(*locked);
  92     }
  93
  94     const ghobject_t &get_locked() const {
  95       ceph_assert(locked);
  96       return *locked;
  97     }
  98
  99     void swap(MapHeaderLock &o) {
 100       ceph_assert(db == o.db);
 101
 102       // centos6's boost optional doesn't seem to have swap :(
 103       boost::optional<ghobject_t> _locked = o.locked;
 104       o.locked = locked;
 105       locked = _locked;
 106     }
 107
 108     ~MapHeaderLock() {
 109       if (locked) {
 110         Mutex::Locker l(db->header_lock);
 111         ceph_assert(db->map_header_in_use.count(*locked));
 112         db->map_header_cond.Signal();
 113         db->map_header_in_use.erase(*locked);
 114       }
 115     }
 116   };
 117
 118   DBObjectMap(CephContext* cct, KeyValueDB *db)
 119     : ObjectMap(cct, db), header_lock("DBOBjectMap"),
 120       cache_lock("DBObjectMap::CacheLock"),
 121       caches(cct->_conf->filestore_omap_header_cache_size)
 122     {}
 123
 124   int set_keys(
 125     const ghobject_t &oid,
 126     const map<string, bufferlist> &set,
 127     const SequencerPosition *spos=0
 128     ) override;
 129
 130   int set_header(
 131     const ghobject_t &oid,
 132     const bufferlist &bl,
 133     const SequencerPosition *spos=0
 134     ) override;
 135
 136   int get_header(
 137     const ghobject_t &oid,
 138     bufferlist *bl
 139     ) override;
 140
 141   int clear(
 142     const ghobject_t &oid,
 143     const SequencerPosition *spos=0
 144     ) override;
 145
 146   int clear_keys_header(
 147     const ghobject_t &oid,
 148     const SequencerPosition *spos=0
 149     ) override;
 150
 151   int rm_keys(
 152     const ghobject_t &oid,
 153     const set<string> &to_clear,
 154     const SequencerPosition *spos=0
 155     ) override;
 156
 157   int get(
 158     const ghobject_t &oid,
 159     bufferlist *header,
 160     map<string, bufferlist> *out
 161     ) override;
 162
 163   int get_keys(
 164     const ghobject_t &oid,
 165     set<string> *keys
 166     ) override;
 167
 168   int get_values(
 169     const ghobject_t &oid,
 170     const set<string> &keys,
 171     map<string, bufferlist> *out
 172     ) override;
 173
 174   int check_keys(
 175     const ghobject_t &oid,
 176     const set<string> &keys,
 177     set<string> *out
 178     ) override;
 179
 180   int get_xattrs(
 181     const ghobject_t &oid,
 182     const set<string> &to_get,
 183     map<string, bufferlist> *out
 184     ) override;
 185
 186   int get_all_xattrs(
 187     const ghobject_t &oid,
 188     set<string> *out
 189     ) override;
 190
 191   int set_xattrs(
 192     const ghobject_t &oid,
 193     const map<string, bufferlist> &to_set,
 194     const SequencerPosition *spos=0
 195     ) override;
 196
 197   int remove_xattrs(
 198     const ghobject_t &oid,
 199     const set<string> &to_remove,
 200     const SequencerPosition *spos=0
 201     ) override;
 202
 203   int clone(
 204     const ghobject_t &oid,
 205     const ghobject_t &target,
 206     const SequencerPosition *spos=0
 207     ) override;
 208
 209   int rename(
 210     const ghobject_t &from,
 211     const ghobject_t &to,
 212     const SequencerPosition *spos=0
 213     );
 214
 215   int legacy_clone(
 216     const ghobject_t &oid,
 217     const ghobject_t &target,
 218     const SequencerPosition *spos=0
 219     );
 220
 221   /// Read initial state from backing store
 222   int get_state();
 223   /// Write current state settings to DB
 224   void set_state();
 225   /// Read initial state and upgrade or initialize state
 226   int init(bool upgrade = false);
 227
 228   /// Upgrade store to current version
 229   int upgrade_to_v2();
 230
 231   /// Consistency check, debug, there must be no parallel writes
 232   int check(std::ostream &out, bool repair = false, bool force = false) override;
 233
 234   /// Ensure that all previous operations are durable
 235   int sync(const ghobject_t *oid=0, const SequencerPosition *spos=0) override;
 236
 237   void compact() override {
 238     ceph_assert(db);
 239     db->compact();
 240   }
 241
 242   /// Util, get all objects, there must be no other concurrent access
 243   int list_objects(vector<ghobject_t> *objs ///< [out] objects
 244     );
 245
 246   struct _Header;
 247   // Util, get all object headers, there must be no other concurrent access
 248   int list_object_headers(vector<_Header> *out ///< [out] headers
 249     );
 250
 251   ObjectMapIterator get_iterator(const ghobject_t &oid) override;
 252
 253   static const string USER_PREFIX;
 254   static const string XATTR_PREFIX;
 255   static const string SYS_PREFIX;
 256   static const string COMPLETE_PREFIX;
 257   static const string HEADER_KEY;
 258   static const string USER_HEADER_KEY;
 259   static const string GLOBAL_STATE_KEY;
 260   static const string HOBJECT_TO_SEQ;
 261
 262   /// Legacy
 263   static const string LEAF_PREFIX;
 264   static const string REVERSE_LEAF_PREFIX;
 265
 266   /// persistent state for store @see generate_header
 267   struct State {
 268     static const __u8 CUR_VERSION = 3;
 269     __u8 v;
 270     uint64_t seq;
 271     // legacy is false when complete regions never used
 272     bool legacy;
 273     State() : v(0), seq(1), legacy(false) {}
 274     explicit State(uint64_t seq) : v(0), seq(seq), legacy(false) {}
 275
 276     void encode(bufferlist &bl) const {
 277       ENCODE_START(3, 1, bl);
 278       encode(v, bl);
 279       encode(seq, bl);
 280       encode(legacy, bl);
 281       ENCODE_FINISH(bl);
 282     }
 283
 284     void decode(bufferlist::const_iterator &bl) {
 285       DECODE_START(3, bl);
 286       if (struct_v >= 2)
 287         decode(v, bl);
 288       else
 289         v = 0;
 290       decode(seq, bl);
 291       if (struct_v >= 3)
 292         decode(legacy, bl);
 293       else
 294         legacy = false;
 295       DECODE_FINISH(bl);
 296     }
 297
 298     void dump(Formatter *f) const {
 299       f->dump_unsigned("v", v);
 300       f->dump_unsigned("seq", seq);
 301       f->dump_bool("legacy", legacy);
 302     }
 303
 304     static void generate_test_instances(list<State*> &o) {
 305       o.push_back(new State(0));
 306       o.push_back(new State(20));
 307     }
 308   } state;
 309
 310   struct _Header {
 311     uint64_t seq;
 312     uint64_t parent;
 313     uint64_t num_children;
 314
 315     ghobject_t oid;
 316
 317     SequencerPosition spos;
 318
 319     void encode(bufferlist &bl) const {
 320       coll_t unused;
 321       ENCODE_START(2, 1, bl);
 322       encode(seq, bl);
 323       encode(parent, bl);
 324       encode(num_children, bl);
 325       encode(unused, bl);
 326       encode(oid, bl);
 327       encode(spos, bl);
 328       ENCODE_FINISH(bl);
 329     }
 330
 331     void decode(bufferlist::const_iterator &bl) {
 332       coll_t unused;
 333       DECODE_START(2, bl);
 334       decode(seq, bl);
 335       decode(parent, bl);
 336       decode(num_children, bl);
 337       decode(unused, bl);
 338       decode(oid, bl);
 339       if (struct_v >= 2)
 340         decode(spos, bl);
 341       DECODE_FINISH(bl);
 342     }
 343
 344     void dump(Formatter *f) const {
 345       f->dump_unsigned("seq", seq);
 346       f->dump_unsigned("parent", parent);
 347       f->dump_unsigned("num_children", num_children);
 348       f->dump_stream("oid") << oid;
 349     }
 350
 351     static void generate_test_instances(list<_Header*> &o) {
 352       o.push_back(new _Header);
 353       o.push_back(new _Header);
 354       o.back()->parent = 20;
 355       o.back()->seq = 30;
 356     }
 357
 358     _Header() : seq(0), parent(0), num_children(1) {}
 359   };
 360
 361   /// String munging (public for testing)
 362   static string ghobject_key(const ghobject_t &oid);
 363   static string ghobject_key_v0(coll_t c, const ghobject_t &oid);
 364   static int is_buggy_ghobject_key_v1(CephContext* cct,
 365                                       const string &in);
 366 private:
 367   /// Implicit lock on Header->seq
 368   typedef std::shared_ptr<_Header> Header;
 369   Mutex cache_lock;
 370   SimpleLRU<ghobject_t, _Header> caches;
 371
 372   string map_header_key(const ghobject_t &oid);
 373   string header_key(uint64_t seq);
 374   string complete_prefix(Header header);
 375   string user_prefix(Header header);
 376   string sys_prefix(Header header);
 377   string xattr_prefix(Header header);
 378   string sys_parent_prefix(_Header header);
 379   string sys_parent_prefix(Header header) {
 380     return sys_parent_prefix(*header);
 381   }
 382
 383   class EmptyIteratorImpl : public ObjectMapIteratorImpl {
 384   public:
 385     int seek_to_first() override { return 0; }
 386     int seek_to_last() { return 0; }
 387     int upper_bound(const string &after) override { return 0; }
 388     int lower_bound(const string &to) override { return 0; }
 389     bool valid() override { return false; }
 390     int next() override { ceph_abort(); return 0; }
 391     string key() override { ceph_abort(); return ""; }
 392     bufferlist value() override { ceph_abort(); return bufferlist(); }
 393     int status() override { return 0; }
 394   };
 395
 396
 397   /// Iterator
 398   class DBObjectMapIteratorImpl : public ObjectMapIteratorImpl {
 399   public:
 400     DBObjectMap *map;
 401
 402     /// NOTE: implicit lock hlock->get_locked() when returned out of the class
 403     MapHeaderLock hlock;
 404     /// NOTE: implicit lock on header->seq AND for all ancestors
 405     Header header;
 406
 407     /// parent_iter == NULL iff no parent
 408     std::shared_ptr<DBObjectMapIteratorImpl> parent_iter;
 409     KeyValueDB::Iterator key_iter;
 410     KeyValueDB::Iterator complete_iter;
 411
 412     /// cur_iter points to currently valid iterator
 413     std::shared_ptr<ObjectMapIteratorImpl> cur_iter;
 414     int r;
 415
 416     /// init() called, key_iter, complete_iter, parent_iter filled in
 417     bool ready;
 418     /// past end
 419     bool invalid;
 420
 421     DBObjectMapIteratorImpl(DBObjectMap *map, Header header) :
 422       map(map), hlock(map), header(header), r(0), ready(false), invalid(true) {}
 423     int seek_to_first() override;
 424     int seek_to_last();
 425     int upper_bound(const string &after) override;
 426     int lower_bound(const string &to) override;
 427     bool valid() override;
 428     int next() override;
 429     string key() override;
 430     bufferlist value() override;
 431     int status() override;
 432
 433     bool on_parent() {
 434       return cur_iter == parent_iter;
 435     }
 436
 437     /// skips to next valid parent entry
 438     int next_parent();
 439
 440     /// first parent() >= to
 441     int lower_bound_parent(const string &to);
 442
 443     /**
 444      * Tests whether to_test is in complete region
 445      *
 446      * postcondition: complete_iter will be max s.t. complete_iter->value > to_test
 447      */
 448     int in_complete_region(const string &to_test, ///< [in] key to test
 449                            string *begin,         ///< [out] beginning of region
 450                            string *end            ///< [out] end of region
 451       ); ///< @returns true if to_test is in the complete region, else false
 452
 453   private:
 454     int init();
 455     bool valid_parent();
 456     int adjust();
 457   };
 458
 459   typedef std::shared_ptr<DBObjectMapIteratorImpl> DBObjectMapIterator;
 460   DBObjectMapIterator _get_iterator(Header header) {
 461     return std::make_shared<DBObjectMapIteratorImpl>(this, header);
 462   }
 463
 464   /// sys
 465
 466   /// Removes node corresponding to header
 467   void clear_header(Header header, KeyValueDB::Transaction t);
 468
 469   /// Set node containing input to new contents
 470   void set_header(Header input, KeyValueDB::Transaction t);
 471
 472   /// Remove leaf node corresponding to oid in c
 473   void remove_map_header(
 474     const MapHeaderLock &l,
 475     const ghobject_t &oid,
 476     Header header,
 477     KeyValueDB::Transaction t);
 478
 479   /// Set leaf node for c and oid to the value of header
 480   void set_map_header(
 481     const MapHeaderLock &l,
 482     const ghobject_t &oid, _Header header,
 483     KeyValueDB::Transaction t);
 484
 485   /// Set leaf node for c and oid to the value of header
 486   bool check_spos(const ghobject_t &oid,
 487                   Header header,
 488                   const SequencerPosition *spos);
 489
 490   /// Lookup or create header for c oid
 491   Header lookup_create_map_header(
 492     const MapHeaderLock &l,
 493     const ghobject_t &oid,
 494     KeyValueDB::Transaction t);
 495
 496   /**
 497    * Generate new header for c oid with new seq number
 498    *
 499    * Has the side effect of synchronously saving the new DBObjectMap state
 500    */
 501   Header _generate_new_header(const ghobject_t &oid, Header parent);
 502   Header generate_new_header(const ghobject_t &oid, Header parent) {
 503     Mutex::Locker l(header_lock);
 504     return _generate_new_header(oid, parent);
 505   }
 506
 507   /// Lookup leaf header for c oid
 508   Header _lookup_map_header(
 509     const MapHeaderLock &l,
 510     const ghobject_t &oid);
 511   Header lookup_map_header(
 512     const MapHeaderLock &l2,
 513     const ghobject_t &oid) {
 514     Mutex::Locker l(header_lock);
 515     return _lookup_map_header(l2, oid);
 516   }
 517
 518   /// Lookup header node for input
 519   Header lookup_parent(Header input);
 520
 521
 522   /// Helpers
 523   int _get_header(Header header, bufferlist *bl);
 524
 525   /// Scan keys in header into out_keys and out_values (if nonnull)
 526   int scan(Header header,
 527            const set<string> &in_keys,
 528            set<string> *out_keys,
 529            map<string, bufferlist> *out_values);
 530
 531   /// Remove header and all related prefixes
 532   int _clear(Header header,
 533              KeyValueDB::Transaction t);
 534
 535   /* Scan complete region bumping *begin to the beginning of any
 536    * containing region and adding all complete region keys between
 537    * the updated begin and end to the complete_keys_to_remove set */
 538   int merge_new_complete(DBObjectMapIterator &iter,
 539                          string *begin,
 540                          const string &end,
 541                          set<string> *complete_keys_to_remove);
 542
 543   /// Writes out State (mainly next_seq)
 544   int write_state(KeyValueDB::Transaction _t =
 545                   KeyValueDB::Transaction());
 546
 547   /// Copies header entry from parent @see rm_keys
 548   int copy_up_header(Header header,
 549                      KeyValueDB::Transaction t);
 550
 551   /// Sets header @see set_header
 552   void _set_header(Header header, const bufferlist &bl,
 553                    KeyValueDB::Transaction t);
 554
 555   /**
 556    * Removes header seq lock and possibly object lock
 557    * once Header is out of scope
 558    * @see lookup_parent
 559    * @see generate_new_header
 560    */
 561   class RemoveOnDelete {
 562   public:
 563     DBObjectMap *db;
 564     explicit RemoveOnDelete(DBObjectMap *db) :
 565       db(db) {}
 566     void operator() (_Header *header) {
 567       Mutex::Locker l(db->header_lock);
 568       ceph_assert(db->in_use.count(header->seq));
 569       db->in_use.erase(header->seq);
 570       db->header_cond.Signal();
 571       delete header;
 572     }
 573   };
 574   friend class RemoveOnDelete;
 575 };
 576 WRITE_CLASS_ENCODER(DBObjectMap::_Header)
 577 WRITE_CLASS_ENCODER(DBObjectMap::State)
 578
 579 ostream& operator<<(ostream& out, const DBObjectMap::_Header& h);
 580
 581 #endif