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