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 <string.h>
  19 #include "include/types.h"
  20 #include "include/object.h"
  21 #include "include/cmp.h"
  22
  23 #include "json_spirit/json_spirit_value.h"
  24 #include "include/assert.h"   // spirit clobbers it!
  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     if (v == 0)
 203       return v;
 204     // reverse bits
 205     // swap odd and even bits
 206     v = ((v >> 1) & 0x55555555) | ((v & 0x55555555) << 1);
 207     // swap consecutive pairs
 208     v = ((v >> 2) & 0x33333333) | ((v & 0x33333333) << 2);
 209     // swap nibbles ...
 210     v = ((v >> 4) & 0x0F0F0F0F) | ((v & 0x0F0F0F0F) << 4);
 211     // swap bytes
 212     v = ((v >> 8) & 0x00FF00FF) | ((v & 0x00FF00FF) << 8);
 213     // swap 2-byte long pairs
 214     v = ( v >> 16             ) | ( v               << 16);
 215     return v;
 216   }
 217   static uint32_t _reverse_nibbles(uint32_t retval) {
 218     // reverse nibbles
 219     retval = ((retval & 0x0f0f0f0f) << 4) | ((retval & 0xf0f0f0f0) >> 4);
 220     retval = ((retval & 0x00ff00ff) << 8) | ((retval & 0xff00ff00) >> 8);
 221     retval = ((retval & 0x0000ffff) << 16) | ((retval & 0xffff0000) >> 16);
 222     return retval;
 223   }
 224
 225   /**
 226    * Returns set S of strings such that for any object
 227    * h where h.match(bits, mask), there is some string
 228    * s \f$\in\f$ S such that s is a prefix of h.to_str().
 229    * Furthermore, for any s $f\in\f$ S, s is a prefix of
 230    * h.str() implies that h.match(bits, mask).
 231    */
 232   static set<string> get_prefixes(
 233     uint32_t bits,
 234     uint32_t mask,
 235     int64_t pool);
 236
 237   // filestore nibble-based key
 238   uint32_t get_nibblewise_key_u32() const {
 239     assert(!max);
 240     return nibblewise_key_cache;
 241   }
 242   uint64_t get_nibblewise_key() const {
 243     return max ? 0x100000000ull : nibblewise_key_cache;
 244   }
 245
 246   // newer bit-reversed key
 247   uint32_t get_bitwise_key_u32() const {
 248     assert(!max);
 249     return hash_reverse_bits;
 250   }
 251   uint64_t get_bitwise_key() const {
 252     return max ? 0x100000000ull : hash_reverse_bits;
 253   }
 254
 255   // please remember to update set_bitwise_key_u32() also
 256   // once you change build_hash_cache()
 257   void build_hash_cache() {
 258     nibblewise_key_cache = _reverse_nibbles(hash);
 259     hash_reverse_bits = _reverse_bits(hash);
 260   }
 261   void set_bitwise_key_u32(uint32_t value) {
 262     hash = _reverse_bits(value);
 263     // below is identical to build_hash_cache() and shall be
 264     // updated correspondingly if you change build_hash_cache()
 265     nibblewise_key_cache = _reverse_nibbles(hash);
 266     hash_reverse_bits = value;
 267   }
 268
 269   const string& get_effective_key() const {
 270     if (key.length())
 271       return key;
 272     return oid.name;
 273   }
 274
 275   hobject_t make_temp_hobject(const string& name) const {
 276     return hobject_t(object_t(name), "", CEPH_NOSNAP,
 277                      hash,
 278                      hobject_t::POOL_TEMP_START - pool, "");
 279   }
 280
 281   void swap(hobject_t &o) {
 282     hobject_t temp(o);
 283     o = (*this);
 284     (*this) = temp;
 285   }
 286
 287   const string &get_namespace() const {
 288     return nspace;
 289   }
 290
 291   bool parse(const string& s);
 292
 293   void encode(bufferlist& bl) const;
 294   void decode(bufferlist::iterator& bl);
 295   void decode(json_spirit::Value& v);
 296   void dump(Formatter *f) const;
 297   static void generate_test_instances(list<hobject_t*>& o);
 298   friend int cmp(const hobject_t& l, const hobject_t& r);
 299   friend bool operator>(const hobject_t& l, const hobject_t& r) {
 300     return cmp(l, r) > 0;
 301   }
 302   friend bool operator>=(const hobject_t& l, const hobject_t& r) {
 303     return cmp(l, r) >= 0;
 304   }
 305   friend bool operator<(const hobject_t& l, const hobject_t& r) {
 306     return cmp(l, r) < 0;
 307   }
 308   friend bool operator<=(const hobject_t& l, const hobject_t& r) {
 309     return cmp(l, r) <= 0;
 310   }
 311   friend bool operator==(const hobject_t&, const hobject_t&);
 312   friend bool operator!=(const hobject_t&, const hobject_t&);
 313   friend struct ghobject_t;
 314 };
 315 WRITE_CLASS_ENCODER(hobject_t)
 316
 317 namespace std {
 318   template<> struct hash<hobject_t> {
 319     size_t operator()(const hobject_t &r) const {
 320       static rjhash<uint64_t> I;
 321       return r.get_hash() ^ I(r.snap);
 322     }
 323   };
 324 } // namespace std
 325
 326 ostream& operator<<(ostream& out, const hobject_t& o);
 327
 328 WRITE_EQ_OPERATORS_7(hobject_t, hash, oid, get_key(), snap, pool, max, nspace)
 329
 330 template <typename T>
 331 struct always_false {
 332   using value = std::false_type;
 333 };
 334
 335 template <typename T>
 336 inline bool operator==(const hobject_t &lhs, const T&) {
 337   static_assert(always_false<T>::value::value, "Do not compare to get_max()");
 338   return lhs.is_max();
 339 }
 340 template <typename T>
 341 inline bool operator==(const T&, const hobject_t &rhs) {
 342   static_assert(always_false<T>::value::value, "Do not compare to get_max()");
 343   return rhs.is_max();
 344 }
 345 template <typename T>
 346 inline bool operator!=(const hobject_t &lhs, const T&) {
 347   static_assert(always_false<T>::value::value, "Do not compare to get_max()");
 348   return !lhs.is_max();
 349 }
 350 template <typename T>
 351 inline bool operator!=(const T&, const hobject_t &rhs) {
 352   static_assert(always_false<T>::value::value, "Do not compare to get_max()");
 353   return !rhs.is_max();
 354 }
 355
 356 extern int cmp(const hobject_t& l, const hobject_t& r);
 357 template <typename T>
 358 static inline int cmp(const hobject_t &l, const T&) {
 359   static_assert(always_false<T>::value::value, "Do not compare to get_max()");
 360   return l.is_max() ? 0 : -1;
 361 }
 362 template <typename T>
 363 static inline int cmp(const T&, const hobject_t&r) {
 364   static_assert(always_false<T>::value::value, "Do not compare to get_max()");
 365   return r.is_max() ? 0 : 1;
 366 }
 367
 368
 369
 370 typedef version_t gen_t;
 371
 372 struct ghobject_t {
 373   hobject_t hobj;
 374   gen_t generation;
 375   shard_id_t shard_id;
 376   bool max;
 377
 378 public:
 379   static const gen_t NO_GEN = UINT64_MAX;
 380
 381   ghobject_t()
 382     : generation(NO_GEN),
 383       shard_id(shard_id_t::NO_SHARD),
 384       max(false) {}
 385
 386   explicit ghobject_t(const hobject_t &obj)
 387     : hobj(obj),
 388       generation(NO_GEN),
 389       shard_id(shard_id_t::NO_SHARD),
 390       max(false) {}
 391
 392   ghobject_t(const hobject_t &obj, gen_t gen, shard_id_t shard)
 393     : hobj(obj),
 394       generation(gen),
 395       shard_id(shard),
 396       max(false) {}
 397
 398   static ghobject_t make_pgmeta(int64_t pool, uint32_t hash, shard_id_t shard) {
 399     hobject_t h(object_t(), string(), CEPH_NOSNAP, hash, pool, string());
 400     return ghobject_t(h, NO_GEN, shard);
 401   }
 402   bool is_pgmeta() const {
 403     // make sure we are distinct from hobject_t(), which has pool INT64_MIN
 404     return hobj.pool >= 0 && hobj.oid.name.empty();
 405   }
 406
 407   bool match(uint32_t bits, uint32_t match) const {
 408     return hobj.match_hash(hobj.hash, bits, match);
 409   }
 410   /// @return min ghobject_t ret s.t. ret.hash == this->hash
 411   ghobject_t get_boundary() const {
 412     if (hobj.is_max())
 413       return *this;
 414     ghobject_t ret;
 415     ret.hobj.set_hash(hobj.hash);
 416     ret.shard_id = shard_id;
 417     ret.hobj.pool = hobj.pool;
 418     return ret;
 419   }
 420   uint32_t get_nibblewise_key_u32() const {
 421     return hobj.get_nibblewise_key_u32();
 422   }
 423   uint32_t get_nibblewise_key() const {
 424     return hobj.get_nibblewise_key();
 425   }
 426
 427   bool is_degenerate() const {
 428     return generation == NO_GEN && shard_id == shard_id_t::NO_SHARD;
 429   }
 430
 431   bool is_no_gen() const {
 432     return generation == NO_GEN;
 433   }
 434
 435   bool is_no_shard() const {
 436     return shard_id == shard_id_t::NO_SHARD;
 437   }
 438
 439   void set_shard(shard_id_t s) {
 440     shard_id = s;
 441   }
 442
 443   bool parse(const string& s);
 444
 445   // maximum sorted value.
 446   static ghobject_t get_max() {
 447     ghobject_t h;
 448     h.max = true;
 449     h.hobj = hobject_t::get_max();  // so that is_max() => hobj.is_max()
 450     return h;
 451   }
 452   bool is_max() const {
 453     return max;
 454   }
 455   bool is_min() const {
 456     return *this == ghobject_t();
 457   }
 458
 459   void swap(ghobject_t &o) {
 460     ghobject_t temp(o);
 461     o = (*this);
 462     (*this) = temp;
 463   }
 464
 465   void encode(bufferlist& bl) const;
 466   void decode(bufferlist::iterator& bl);
 467   void decode(json_spirit::Value& v);
 468   size_t encoded_size() const;
 469   void dump(Formatter *f) const;
 470   static void generate_test_instances(list<ghobject_t*>& o);
 471   friend int cmp(const ghobject_t& l, const ghobject_t& r);
 472   friend bool operator>(const ghobject_t& l, const ghobject_t& r) {
 473     return cmp(l, r) > 0;
 474   }
 475   friend bool operator>=(const ghobject_t& l, const ghobject_t& r) {
 476     return cmp(l, r) >= 0;
 477   }
 478   friend bool operator<(const ghobject_t& l, const ghobject_t& r) {
 479     return cmp(l, r) < 0;
 480   }
 481   friend bool operator<=(const ghobject_t& l, const ghobject_t& r) {
 482     return cmp(l, r) <= 0;
 483   }
 484   friend bool operator==(const ghobject_t&, const ghobject_t&);
 485   friend bool operator!=(const ghobject_t&, const ghobject_t&);
 486
 487 };
 488 WRITE_CLASS_ENCODER(ghobject_t)
 489
 490 namespace std {
 491   template<> struct hash<ghobject_t> {
 492     size_t operator()(const ghobject_t &r) const {
 493       static rjhash<uint64_t> I;
 494       return r.hobj.get_hash() ^ I(r.hobj.snap);
 495     }
 496   };
 497 } // namespace std
 498
 499 ostream& operator<<(ostream& out, const ghobject_t& o);
 500
 501 WRITE_EQ_OPERATORS_4(ghobject_t, max, shard_id, hobj, generation)
 502
 503 extern int cmp(const ghobject_t& l, const ghobject_t& r);
 504
 505
 506 #endif