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