ceph/src/common/hobject.h

   1 // -*- mode:C++; tab-width:8; c-basic-offset:2; indent-tabs-mode:t -*-
   2 // vim: ts=8 sw=2 smarttab
   3 /*
   4  * Ceph - scalable distributed file system
   5  *
   6  * Copyright (C) 2004-2006 Sage Weil <sage@newdream.net>
   7  *
   8  * This is free software; you can redistribute it and/or
   9  * modify it under the terms of the GNU Lesser General Public
  10  * License version 2.1, as published by the Free Software
  11  * Foundation.  See file COPYING.
  12  *
  13  */
  14
  15 #ifndef __CEPH_OS_HOBJECT_H
  16 #define __CEPH_OS_HOBJECT_H
  17
  18 #include "include/types.h"
  19 #include "include/cmp.h"
  20
  21 #include "json_spirit/json_spirit_value.h"
  22 #include "include/assert.h"   // spirit clobbers it!
  23
  24 #include "reverse.h"
  25
  26 namespace ceph {
  27   class Formatter;
  28 }
  29
  30 #ifndef UINT64_MAX
  31 #define UINT64_MAX (18446744073709551615ULL)
  32 #endif
  33 #ifndef INT64_MIN
  34 #define INT64_MIN ((int64_t)0x8000000000000000ll)
  35 #endif
  36
  37 struct hobject_t {
  38   object_t oid;
  39   snapid_t snap;
  40 private:
  41   uint32_t hash;
  42   bool max;
  43   uint32_t nibblewise_key_cache;
  44   uint32_t hash_reverse_bits;
  45   static const int64_t POOL_META = -1;
  46   static const int64_t POOL_TEMP_START = -2; // and then negative
  47   friend class spg_t;  // for POOL_TEMP_START
  48 public:
  49   int64_t pool;
  50   string nspace;
  51
  52 private:
  53   string key;
  54
  55   class hobject_t_max {};
  56
  57 public:
  58   const string &get_key() const {
  59     return key;
  60   }
  61
  62   void set_key(const std::string &key_) {
  63     if (key_ == oid.name)
  64       key.clear();
  65     else
  66       key = key_;
  67   }
  68
  69   string to_str() const;
  70
  71   uint32_t get_hash() const {
  72     return hash;
  73   }
  74   void set_hash(uint32_t value) {
  75     hash = value;
  76     build_hash_cache();
  77   }
  78
  79   static bool match_hash(uint32_t to_check, uint32_t bits, uint32_t match) {
  80     return (match & ~((~0)<<bits)) == (to_check & ~((~0)<<bits));
  81   }
  82   bool match(uint32_t bits, uint32_t match) const {
  83     return match_hash(hash, bits, match);
  84   }
  85
  86   bool is_temp() const {
  87     return pool <= POOL_TEMP_START && pool != INT64_MIN;
  88   }
  89   bool is_meta() const {
  90     return pool == POOL_META;
  91   }
  92
  93   hobject_t() : snap(0), hash(0), max(false), pool(INT64_MIN) {
  94     build_hash_cache();
  95   }
  96
  97   hobject_t(const hobject_t &rhs) = default;
  98   hobject_t(hobject_t &&rhs) = default;
  99   hobject_t(hobject_t_max &&singleton) : hobject_t() {
 100     max = true;
 101   }
 102   hobject_t &operator=(const hobject_t &rhs) = default;
 103   hobject_t &operator=(hobject_t &&rhs) = default;
 104   hobject_t &operator=(hobject_t_max &&singleton) {
 105     *this = hobject_t();
 106     max = true;
 107     return *this;
 108   }
 109
 110   // maximum sorted value.
 111   static hobject_t_max get_max() {
 112     return hobject_t_max();
 113   }
 114
 115   hobject_t(object_t oid, const string& key, snapid_t snap, uint32_t hash,
 116             int64_t pool, string nspace)
 117     : oid(oid), snap(snap), hash(hash), max(false),
 118       pool(pool), nspace(nspace),
 119       key(oid.name == key ? string() : key) {
 120     build_hash_cache();
 121   }
 122
 123   hobject_t(const sobject_t &soid, const string &key, uint32_t hash,
 124             int64_t pool, string nspace)
 125     : oid(soid.oid), snap(soid.snap), hash(hash), max(false),
 126       pool(pool), nspace(nspace),
 127       key(soid.oid.name == key ? string() : key) {
 128     build_hash_cache();
 129   }
 130
 131   /// @return min hobject_t ret s.t. ret.hash == this->hash
 132   hobject_t get_boundary() const {
 133     if (is_max())
 134       return *this;
 135     hobject_t ret;
 136     ret.set_hash(hash);
 137     ret.pool = pool;
 138     return ret;
 139   }
 140
 141   hobject_t get_object_boundary() const {
 142     if (is_max())
 143       return *this;
 144     hobject_t ret = *this;
 145     ret.snap = 0;
 146     return ret;
 147   }
 148
 149   /// @return head version of this hobject_t
 150   hobject_t get_head() const {
 151     hobject_t ret(*this);
 152     ret.snap = CEPH_NOSNAP;
 153     return ret;
 154   }
 155
 156   /// @return snapdir version of this hobject_t
 157   hobject_t get_snapdir() const {
 158     hobject_t ret(*this);
 159     ret.snap = CEPH_SNAPDIR;
 160     return ret;
 161   }
 162
 163   /// @return true if object is snapdir
 164   bool is_snapdir() const {
 165     return snap == CEPH_SNAPDIR;
 166   }
 167
 168   /// @return true if object is head
 169   bool is_head() const {
 170     return snap == CEPH_NOSNAP;
 171   }
 172
 173   /// @return true if object is neither head nor snapdir nor max
 174   bool is_snap() const {
 175     return !is_max() && !is_head() && !is_snapdir();
 176   }
 177
 178   /// @return true iff the object should have a snapset in it's attrs
 179   bool has_snapset() const {
 180     return is_head() || is_snapdir();
 181   }
 182
 183   /* Do not use when a particular hash function is needed */
 184   explicit hobject_t(const sobject_t &o) :
 185     oid(o.oid), snap(o.snap), max(false), pool(POOL_META) {
 186     set_hash(std::hash<sobject_t>()(o));
 187   }
 188
 189   bool is_max() const {
 190     assert(!max || (*this == hobject_t(hobject_t::get_max())));
 191     return max;
 192   }
 193   bool is_min() const {
 194     // this needs to match how it's constructed
 195     return snap == 0 &&
 196            hash == 0 &&
 197            !max &&
 198            pool == INT64_MIN;
 199   }
 200
 201   static uint32_t _reverse_bits(uint32_t v) {
 202     return reverse_bits(v);
 203   }
 204   static uint32_t _reverse_nibbles(uint32_t retval) {
 205     return reverse_nibbles(retval);
 206   }
 207
 208   /**
 209    * Returns set S of strings such that for any object
 210    * h where h.match(bits, mask), there is some string
 211    * s \f$\in\f$ S such that s is a prefix of h.to_str().
 212    * Furthermore, for any s $f\in\f$ S, s is a prefix of
 213    * h.str() implies that h.match(bits, mask).
 214    */
 215   static set<string> get_prefixes(
 216     uint32_t bits,
 217     uint32_t mask,
 218     int64_t pool);
 219
 220   // filestore nibble-based key
 221   uint32_t get_nibblewise_key_u32() const {
 222     assert(!max);
 223     return nibblewise_key_cache;
 224   }
 225   uint64_t get_nibblewise_key() const {
 226     return max ? 0x100000000ull : nibblewise_key_cache;
 227   }
 228
 229   // newer bit-reversed key
 230   uint32_t get_bitwise_key_u32() const {
 231     assert(!max);
 232     return hash_reverse_bits;
 233   }
 234   uint64_t get_bitwise_key() const {
 235     return max ? 0x100000000ull : hash_reverse_bits;
 236   }
 237
 238   // please remember to update set_bitwise_key_u32() also
 239   // once you change build_hash_cache()
 240   void build_hash_cache() {
 241     nibblewise_key_cache = _reverse_nibbles(hash);
 242     hash_reverse_bits = _reverse_bits(hash);
 243   }
 244   void set_bitwise_key_u32(uint32_t value) {
 245     hash = _reverse_bits(value);
 246     // below is identical to build_hash_cache() and shall be
 247     // updated correspondingly if you change build_hash_cache()
 248     nibblewise_key_cache = _reverse_nibbles(hash);
 249     hash_reverse_bits = value;
 250   }
 251
 252   const string& get_effective_key() const {
 253     if (key.length())
 254       return key;
 255     return oid.name;
 256   }
 257
 258   hobject_t make_temp_hobject(const string& name) const {
 259     return hobject_t(object_t(name), "", CEPH_NOSNAP,
 260                      hash,
 261                      hobject_t::POOL_TEMP_START - pool, "");
 262   }
 263
 264   void swap(hobject_t &o) {
 265     hobject_t temp(o);
 266     o = (*this);
 267     (*this) = temp;
 268   }
 269
 270   const string &get_namespace() const {
 271     return nspace;
 272   }
 273
 274   bool parse(const string& s);
 275
 276   void encode(bufferlist& bl) const;
 277   void decode(bufferlist::iterator& bl);
 278   void decode(json_spirit::Value& v);
 279   void dump(Formatter *f) const;
 280   static void generate_test_instances(list<hobject_t*>& o);
 281   friend int cmp(const hobject_t& l, const hobject_t& r);
 282   friend bool operator>(const hobject_t& l, const hobject_t& r) {
 283     return cmp(l, r) > 0;
 284   }
 285   friend bool operator>=(const hobject_t& l, const hobject_t& r) {
 286     return cmp(l, r) >= 0;
 287   }
 288   friend bool operator<(const hobject_t& l, const hobject_t& r) {
 289     return cmp(l, r) < 0;
 290   }
 291   friend bool operator<=(const hobject_t& l, const hobject_t& r) {
 292     return cmp(l, r) <= 0;
 293   }
 294   friend bool operator==(const hobject_t&, const hobject_t&);
 295   friend bool operator!=(const hobject_t&, const hobject_t&);
 296   friend struct ghobject_t;
 297 };
 298 WRITE_CLASS_ENCODER(hobject_t)
 299
 300 namespace std {
 301   template<> struct hash<hobject_t> {
 302     size_t operator()(const hobject_t &r) const {
 303       static rjhash<uint64_t> I;
 304       return r.get_hash() ^ I(r.snap);
 305     }
 306   };
 307 } // namespace std
 308
 309 ostream& operator<<(ostream& out, const hobject_t& o);
 310
 311 WRITE_EQ_OPERATORS_7(hobject_t, hash, oid, get_key(), snap, pool, max, nspace)
 312
 313 template <typename T>
 314 struct always_false {
 315   using value = std::false_type;
 316 };
 317
 318 template <typename T>
 319 inline bool operator==(const hobject_t &lhs, const T&) {
 320   static_assert(always_false<T>::value::value, "Do not compare to get_max()");
 321   return lhs.is_max();
 322 }
 323 template <typename T>
 324 inline bool operator==(const T&, const hobject_t &rhs) {
 325   static_assert(always_false<T>::value::value, "Do not compare to get_max()");
 326   return rhs.is_max();
 327 }
 328 template <typename T>
 329 inline bool operator!=(const hobject_t &lhs, const T&) {
 330   static_assert(always_false<T>::value::value, "Do not compare to get_max()");
 331   return !lhs.is_max();
 332 }
 333 template <typename T>
 334 inline bool operator!=(const T&, const hobject_t &rhs) {
 335   static_assert(always_false<T>::value::value, "Do not compare to get_max()");
 336   return !rhs.is_max();
 337 }
 338
 339 extern int cmp(const hobject_t& l, const hobject_t& r);
 340 template <typename T>
 341 static inline int cmp(const hobject_t &l, const T&) {
 342   static_assert(always_false<T>::value::value, "Do not compare to get_max()");
 343   return l.is_max() ? 0 : -1;
 344 }
 345 template <typename T>
 346 static inline int cmp(const T&, const hobject_t&r) {
 347   static_assert(always_false<T>::value::value, "Do not compare to get_max()");
 348   return r.is_max() ? 0 : 1;
 349 }
 350
 351
 352
 353 typedef version_t gen_t;
 354
 355 struct ghobject_t {
 356   hobject_t hobj;
 357   gen_t generation;
 358   shard_id_t shard_id;
 359   bool max;
 360
 361 public:
 362   static const gen_t NO_GEN = UINT64_MAX;
 363
 364   ghobject_t()
 365     : generation(NO_GEN),
 366       shard_id(shard_id_t::NO_SHARD),
 367       max(false) {}
 368
 369   explicit ghobject_t(const hobject_t &obj)
 370     : hobj(obj),
 371       generation(NO_GEN),
 372       shard_id(shard_id_t::NO_SHARD),
 373       max(false) {}
 374
 375   ghobject_t(const hobject_t &obj, gen_t gen, shard_id_t shard)
 376     : hobj(obj),
 377       generation(gen),
 378       shard_id(shard),
 379       max(false) {}
 380
 381   static ghobject_t make_pgmeta(int64_t pool, uint32_t hash, shard_id_t shard) {
 382     hobject_t h(object_t(), string(), CEPH_NOSNAP, hash, pool, string());
 383     return ghobject_t(h, NO_GEN, shard);
 384   }
 385   bool is_pgmeta() const {
 386     // make sure we are distinct from hobject_t(), which has pool INT64_MIN
 387     return hobj.pool >= 0 && hobj.oid.name.empty();
 388   }
 389
 390   bool match(uint32_t bits, uint32_t match) const {
 391     return hobj.match_hash(hobj.hash, bits, match);
 392   }
 393   /// @return min ghobject_t ret s.t. ret.hash == this->hash
 394   ghobject_t get_boundary() const {
 395     if (hobj.is_max())
 396       return *this;
 397     ghobject_t ret;
 398     ret.hobj.set_hash(hobj.hash);
 399     ret.shard_id = shard_id;
 400     ret.hobj.pool = hobj.pool;
 401     return ret;
 402   }
 403   uint32_t get_nibblewise_key_u32() const {
 404     return hobj.get_nibblewise_key_u32();
 405   }
 406   uint32_t get_nibblewise_key() const {
 407     return hobj.get_nibblewise_key();
 408   }
 409
 410   bool is_degenerate() const {
 411     return generation == NO_GEN && shard_id == shard_id_t::NO_SHARD;
 412   }
 413
 414   bool is_no_gen() const {
 415     return generation == NO_GEN;
 416   }
 417
 418   bool is_no_shard() const {
 419     return shard_id == shard_id_t::NO_SHARD;
 420   }
 421
 422   void set_shard(shard_id_t s) {
 423     shard_id = s;
 424   }
 425
 426   bool parse(const string& s);
 427
 428   // maximum sorted value.
 429   static ghobject_t get_max() {
 430     ghobject_t h;
 431     h.max = true;
 432     h.hobj = hobject_t::get_max();  // so that is_max() => hobj.is_max()
 433     return h;
 434   }
 435   bool is_max() const {
 436     return max;
 437   }
 438   bool is_min() const {
 439     return *this == ghobject_t();
 440   }
 441
 442   void swap(ghobject_t &o) {
 443     ghobject_t temp(o);
 444     o = (*this);
 445     (*this) = temp;
 446   }
 447
 448   void encode(bufferlist& bl) const;
 449   void decode(bufferlist::iterator& bl);
 450   void decode(json_spirit::Value& v);
 451   size_t encoded_size() const;
 452   void dump(Formatter *f) const;
 453   static void generate_test_instances(list<ghobject_t*>& o);
 454   friend int cmp(const ghobject_t& l, const ghobject_t& r);
 455   friend bool operator>(const ghobject_t& l, const ghobject_t& r) {
 456     return cmp(l, r) > 0;
 457   }
 458   friend bool operator>=(const ghobject_t& l, const ghobject_t& r) {
 459     return cmp(l, r) >= 0;
 460   }
 461   friend bool operator<(const ghobject_t& l, const ghobject_t& r) {
 462     return cmp(l, r) < 0;
 463   }
 464   friend bool operator<=(const ghobject_t& l, const ghobject_t& r) {
 465     return cmp(l, r) <= 0;
 466   }
 467   friend bool operator==(const ghobject_t&, const ghobject_t&);
 468   friend bool operator!=(const ghobject_t&, const ghobject_t&);
 469
 470 };
 471 WRITE_CLASS_ENCODER(ghobject_t)
 472
 473 namespace std {
 474   template<> struct hash<ghobject_t> {
 475     size_t operator()(const ghobject_t &r) const {
 476       static rjhash<uint64_t> I;
 477       return r.hobj.get_hash() ^ I(r.hobj.snap);
 478     }
 479   };
 480 } // namespace std
 481
 482 ostream& operator<<(ostream& out, const ghobject_t& o);
 483
 484 WRITE_EQ_OPERATORS_4(ghobject_t, max, shard_id, hobj, generation)
 485
 486 extern int cmp(const ghobject_t& l, const ghobject_t& r);
 487
 488
 489 #endif