ceph/src/common/hobject.cc

   1 // -*- mode:C++; tab-width:8; c-basic-offset:2; indent-tabs-mode:t -*-
   2 // vim: ts=8 sw=2 smarttab
   3
   4 #include <charconv>
   5
   6 #include "hobject.h"
   7 #include "common/Formatter.h"
   8
   9 using std::list;
  10 using std::ostream;
  11 using std::set;
  12 using std::string;
  13
  14 using ceph::bufferlist;
  15 using ceph::Formatter;
  16
  17 static void append_escaped(const string &in, string *out)
  18 {
  19   for (string::const_iterator i = in.begin(); i != in.end(); ++i) {
  20     if (*i == '%') {
  21       out->push_back('%');
  22       out->push_back('p');
  23     } else if (*i == '.') {
  24       out->push_back('%');
  25       out->push_back('e');
  26     } else if (*i == '_') {
  27       out->push_back('%');
  28       out->push_back('u');
  29     } else {
  30       out->push_back(*i);
  31     }
  32   }
  33 }
  34
  35 set<string> hobject_t::get_prefixes(
  36   uint32_t bits,
  37   uint32_t mask,
  38   int64_t pool)
  39 {
  40   uint32_t len = bits;
  41   while (len % 4 /* nibbles */) len++;
  42
  43   set<uint32_t> from;
  44   if (bits < 32)
  45     from.insert(mask & ~((uint32_t)(~0) << bits));
  46   else if (bits == 32)
  47     from.insert(mask);
  48   else
  49     ceph_abort();
  50
  51
  52   set<uint32_t> to;
  53   for (uint32_t i = bits; i < len; ++i) {
  54     for (set<uint32_t>::iterator j = from.begin();
  55          j != from.end();
  56          ++j) {
  57       to.insert(*j | (1U << i));
  58       to.insert(*j);
  59     }
  60     to.swap(from);
  61     to.clear();
  62   }
  63
  64   char buf[20];
  65   char *t = buf;
  66   uint64_t poolid(pool);
  67   t += snprintf(t, sizeof(buf), "%.*llX", 16, (long long unsigned)poolid);
  68   *(t++) = '.';
  69   string poolstr(buf, t - buf);
  70   set<string> ret;
  71   for (set<uint32_t>::iterator i = from.begin();
  72        i != from.end();
  73        ++i) {
  74     uint32_t revhash(hobject_t::_reverse_nibbles(*i));
  75     snprintf(buf, sizeof(buf), "%.*X", (int)(sizeof(revhash))*2, revhash);
  76     ret.insert(poolstr + string(buf, len/4));
  77   }
  78   return ret;
  79 }
  80
  81 string hobject_t::to_str() const
  82 {
  83   string out;
  84
  85   char snap_with_hash[1000];
  86   char *t = snap_with_hash;
  87   const char *end = t + sizeof(snap_with_hash);
  88
  89   uint64_t poolid(pool);
  90   t += snprintf(t, end - t, "%.*llX", 16, (long long unsigned)poolid);
  91
  92   uint32_t revhash(get_nibblewise_key_u32());
  93   t += snprintf(t, end - t, ".%.*X", 8, revhash);
  94
  95   if (snap == CEPH_NOSNAP)
  96     t += snprintf(t, end - t, ".head");
  97   else if (snap == CEPH_SNAPDIR)
  98     t += snprintf(t, end - t, ".snapdir");
  99   else
 100     t += snprintf(t, end - t, ".%llx", (long long unsigned)snap);
 101
 102   out.append(snap_with_hash, t);
 103
 104   out.push_back('.');
 105   append_escaped(oid.name, &out);
 106   out.push_back('.');
 107   append_escaped(get_key(), &out);
 108   out.push_back('.');
 109   append_escaped(nspace, &out);
 110
 111   return out;
 112 }
 113
 114 void hobject_t::encode(bufferlist& bl) const
 115 {
 116   ENCODE_START(4, 3, bl);
 117   encode(key, bl);
 118   encode(oid, bl);
 119   encode(snap, bl);
 120   encode(hash, bl);
 121   encode(max, bl);
 122   encode(nspace, bl);
 123   encode(pool, bl);
 124   ceph_assert(!max || (*this == hobject_t(hobject_t::get_max())));
 125   ENCODE_FINISH(bl);
 126 }
 127
 128 void hobject_t::decode(bufferlist::const_iterator& bl)
 129 {
 130   DECODE_START_LEGACY_COMPAT_LEN(4, 3, 3, bl);
 131   if (struct_v >= 1)
 132     decode(key, bl);
 133   decode(oid, bl);
 134   decode(snap, bl);
 135   decode(hash, bl);
 136   if (struct_v >= 2)
 137     decode(max, bl);
 138   else
 139     max = false;
 140   if (struct_v >= 4) {
 141     decode(nspace, bl);
 142     decode(pool, bl);
 143     // for compat with hammer, which did not handle the transition
 144     // from pool -1 -> pool INT64_MIN for MIN properly.  this object
 145     // name looks a bit like a pgmeta object for the meta collection,
 146     // but those do not ever exist (and is_pgmeta() pool >= 0).
 147     if (pool == -1 &&
 148         snap == 0 &&
 149         hash == 0 &&
 150         !max &&
 151         oid.name.empty()) {
 152       pool = INT64_MIN;
 153       ceph_assert(is_min());
 154     }
 155
 156     // for compatibility with some earlier verisons which might encoded
 157     // a non-canonical max object
 158     if (max) {
 159       *this = hobject_t::get_max();
 160     }
 161   }
 162   DECODE_FINISH(bl);
 163   build_hash_cache();
 164 }
 165
 166 void hobject_t::decode(json_spirit::Value& v)
 167 {
 168   using namespace json_spirit;
 169   Object& o = v.get_obj();
 170   for (Object::size_type i=0; i<o.size(); i++) {
 171     Pair& p = o[i];
 172     if (p.name_ == "oid")
 173       oid.name = p.value_.get_str();
 174     else if (p.name_ == "key")
 175       key = p.value_.get_str();
 176     else if (p.name_ == "snapid")
 177       snap = p.value_.get_uint64();
 178     else if (p.name_ == "hash")
 179       hash = p.value_.get_int();
 180     else if (p.name_ == "max")
 181       max = p.value_.get_int();
 182     else if (p.name_ == "pool")
 183       pool = p.value_.get_int();
 184     else if (p.name_ == "namespace")
 185       nspace = p.value_.get_str();
 186   }
 187   build_hash_cache();
 188 }
 189
 190 void hobject_t::dump(Formatter *f) const
 191 {
 192   f->dump_string("oid", oid.name);
 193   f->dump_string("key", key);
 194   f->dump_int("snapid", snap);
 195   f->dump_int("hash", hash);
 196   f->dump_int("max", (int)max);
 197   f->dump_int("pool", pool);
 198   f->dump_string("namespace", nspace);
 199 }
 200
 201 void hobject_t::generate_test_instances(list<hobject_t*>& o)
 202 {
 203   o.push_back(new hobject_t);
 204   o.push_back(new hobject_t);
 205   o.back()->max = true;
 206   o.push_back(new hobject_t(object_t("oname"), string(), 1, 234, -1, ""));
 207   o.push_back(new hobject_t(object_t("oname2"), string("okey"), CEPH_NOSNAP,
 208         67, 0, "n1"));
 209   o.push_back(new hobject_t(object_t("oname3"), string("oname3"),
 210         CEPH_SNAPDIR, 910, 1, "n2"));
 211 }
 212
 213 static void append_out_escaped(const string &in, string *out)
 214 {
 215   for (auto c : in) {
 216     int i = (int)(unsigned char)(c);
 217     if (i <= 0x0f) {
 218       char buf[4] = {'%', '0'};
 219       std::to_chars(buf + 2, buf + 3, i, 16);
 220       out->append(buf);
 221     } else if (i < 32 || i >= 127 || i == '%' || i == ':' || i == '/') {
 222       char buf[4] = {'%'};
 223       std::to_chars(buf + 1, buf + 3, i, 16);
 224       out->append(buf);
 225     } else {
 226       out->push_back(c);
 227     }
 228   }
 229 }
 230
 231 static const char *decode_out_escaped(const char *in, string *out)
 232 {
 233   while (*in && *in != ':') {
 234     if (*in == '%') {
 235       ++in;
 236       char buf[3];
 237       buf[0] = *in;
 238       ++in;
 239       buf[1] = *in;
 240       buf[2] = 0;
 241       int v = strtol(buf, NULL, 16);
 242       out->push_back(v);
 243     } else {
 244       out->push_back(*in);
 245     }
 246     ++in;
 247   }
 248   return in;
 249 }
 250
 251 ostream& operator<<(ostream& out, const hobject_t& o)
 252 {
 253   if (o == hobject_t())
 254     return out << "MIN";
 255   if (o.is_max())
 256     return out << "MAX";
 257   out << o.pool << ':';
 258   out << std::hex;
 259   out.width(8);
 260   out.fill('0');
 261   out << o.get_bitwise_key_u32(); // << '~' << o.get_hash();
 262   out.width(0);
 263   out.fill(' ');
 264   out << std::dec;
 265   out << ':';
 266   string v;
 267   append_out_escaped(o.nspace, &v);
 268   v.push_back(':');
 269   append_out_escaped(o.get_key(), &v);
 270   v.push_back(':');
 271   append_out_escaped(o.oid.name, &v);
 272   out << v << ':' << o.snap;
 273   return out;
 274 }
 275
 276 bool hobject_t::parse(const string &s)
 277 {
 278   if (s == "MIN") {
 279     *this = hobject_t();
 280     return true;
 281   }
 282   if (s == "MAX") {
 283     *this = hobject_t::get_max();
 284     return true;
 285   }
 286
 287   const char *start = s.c_str();
 288   long long po;
 289   unsigned h;
 290   int r = sscanf(start, "%lld:%x:", &po, &h);
 291   if (r != 2)
 292     return false;
 293   for (; *start && *start != ':'; ++start) ;
 294   for (++start; *start && isxdigit(*start); ++start) ;
 295   if (*start != ':')
 296     return false;
 297
 298   string ns, k, name;
 299   const char *p = decode_out_escaped(start + 1, &ns);
 300   if (*p != ':')
 301     return false;
 302   p = decode_out_escaped(p + 1, &k);
 303   if (*p != ':')
 304     return false;
 305   p = decode_out_escaped(p + 1, &name);
 306   if (*p != ':')
 307     return false;
 308   start = p + 1;
 309
 310   unsigned long long sn;
 311   if (strncmp(start, "head", 4) == 0) {
 312     sn = CEPH_NOSNAP;
 313     start += 4;
 314     if (*start != 0)
 315       return false;
 316   } else {
 317     r = sscanf(start, "%llx", &sn);
 318     if (r != 1)
 319       return false;
 320     for (++start; *start && isxdigit(*start); ++start) ;
 321     if (*start)
 322       return false;
 323   }
 324
 325   max = false;
 326   pool = po;
 327   set_hash(_reverse_bits(h));
 328   nspace = ns;
 329   oid.name = name;
 330   set_key(k);
 331   snap = sn;
 332   return true;
 333 }
 334
 335 int cmp(const hobject_t& l, const hobject_t& r)
 336 {
 337   if (l.max < r.max)
 338     return -1;
 339   if (l.max > r.max)
 340     return 1;
 341   if (l.pool < r.pool)
 342     return -1;
 343   if (l.pool > r.pool)
 344     return 1;
 345   if (l.get_bitwise_key() < r.get_bitwise_key())
 346     return -1;
 347   if (l.get_bitwise_key() > r.get_bitwise_key())
 348     return 1;
 349   if (l.nspace < r.nspace)
 350     return -1;
 351   if (l.nspace > r.nspace)
 352     return 1;
 353   if (!(l.get_key().empty() && r.get_key().empty())) {
 354     if (l.get_effective_key() < r.get_effective_key()) {
 355       return -1;
 356     }
 357     if (l.get_effective_key() > r.get_effective_key()) {
 358       return 1;
 359     }
 360   }
 361   if (l.oid < r.oid)
 362     return -1;
 363   if (l.oid > r.oid)
 364     return 1;
 365   if (l.snap < r.snap)
 366     return -1;
 367   if (l.snap > r.snap)
 368     return 1;
 369   return 0;
 370 }
 371
 372
 373
 374 // This is compatible with decode for hobject_t prior to
 375 // version 5.
 376 void ghobject_t::encode(bufferlist& bl) const
 377 {
 378   // when changing this, remember to update encoded_size() too.
 379   ENCODE_START(6, 3, bl);
 380   encode(hobj.key, bl);
 381   encode(hobj.oid, bl);
 382   encode(hobj.snap, bl);
 383   encode(hobj.hash, bl);
 384   encode(hobj.max, bl);
 385   encode(hobj.nspace, bl);
 386   encode(hobj.pool, bl);
 387   encode(generation, bl);
 388   encode(shard_id, bl);
 389   encode(max, bl);
 390   ENCODE_FINISH(bl);
 391 }
 392
 393 size_t ghobject_t::encoded_size() const
 394 {
 395   // this is not in order of encoding or appearance, but rather
 396   // in order of known constants first, so it can be (mostly) computed
 397   // at compile time.
 398   //  - encoding header + 3 string lengths
 399   size_t r = sizeof(ceph_le32) + 2 * sizeof(__u8) + 3 * sizeof(__u32);
 400
 401   // hobj.snap
 402   r += sizeof(uint64_t);
 403
 404   // hobj.hash
 405   r += sizeof(uint32_t);
 406
 407   // hobj.max
 408   r += sizeof(bool);
 409
 410   // hobj.pool
 411   r += sizeof(uint64_t);
 412
 413   // hobj.generation
 414   r += sizeof(uint64_t);
 415
 416   // hobj.shard_id
 417   r += sizeof(int8_t);
 418
 419   // max
 420   r += sizeof(bool);
 421
 422   // hobj.key
 423   r += hobj.key.size();
 424
 425   // hobj.oid
 426   r += hobj.oid.name.size();
 427
 428   // hobj.nspace
 429   r += hobj.nspace.size();
 430
 431   return r;
 432 }
 433
 434 void ghobject_t::decode(bufferlist::const_iterator& bl)
 435 {
 436   DECODE_START_LEGACY_COMPAT_LEN(6, 3, 3, bl);
 437   if (struct_v >= 1)
 438     decode(hobj.key, bl);
 439   decode(hobj.oid, bl);
 440   decode(hobj.snap, bl);
 441   decode(hobj.hash, bl);
 442   if (struct_v >= 2)
 443     decode(hobj.max, bl);
 444   else
 445     hobj.max = false;
 446   if (struct_v >= 4) {
 447     decode(hobj.nspace, bl);
 448     decode(hobj.pool, bl);
 449     // for compat with hammer, which did not handle the transition from
 450     // pool -1 -> pool INT64_MIN for MIN properly (see hobject_t::decode()).
 451     if (hobj.pool == -1 &&
 452         hobj.snap == 0 &&
 453         hobj.hash == 0 &&
 454         !hobj.max &&
 455         hobj.oid.name.empty()) {
 456       hobj.pool = INT64_MIN;
 457       ceph_assert(hobj.is_min());
 458     }
 459   }
 460   if (struct_v >= 5) {
 461     decode(generation, bl);
 462     decode(shard_id, bl);
 463   } else {
 464     generation = ghobject_t::NO_GEN;
 465     shard_id = shard_id_t::NO_SHARD;
 466   }
 467   if (struct_v >= 6) {
 468     decode(max, bl);
 469   } else {
 470     max = false;
 471   }
 472   DECODE_FINISH(bl);
 473   hobj.build_hash_cache();
 474 }
 475
 476 void ghobject_t::decode(json_spirit::Value& v)
 477 {
 478   hobj.decode(v);
 479   using namespace json_spirit;
 480   Object& o = v.get_obj();
 481   for (Object::size_type i=0; i<o.size(); i++) {
 482     Pair& p = o[i];
 483     if (p.name_ == "generation")
 484       generation = p.value_.get_uint64();
 485     else if (p.name_ == "shard_id")
 486       shard_id.id = p.value_.get_int();
 487     else if (p.name_ == "max")
 488       max = p.value_.get_int();
 489   }
 490 }
 491
 492 void ghobject_t::dump(Formatter *f) const
 493 {
 494   hobj.dump(f);
 495   if (generation != NO_GEN)
 496     f->dump_int("generation", generation);
 497   if (shard_id != shard_id_t::NO_SHARD)
 498     f->dump_int("shard_id", shard_id);
 499   f->dump_int("max", (int)max);
 500 }
 501
 502 void ghobject_t::generate_test_instances(list<ghobject_t*>& o)
 503 {
 504   o.push_back(new ghobject_t);
 505   o.push_back(new ghobject_t);
 506   o.back()->hobj.max = true;
 507   o.push_back(new ghobject_t(hobject_t(object_t("oname"), string(), 1, 234, -1, "")));
 508
 509   o.push_back(new ghobject_t(hobject_t(object_t("oname2"), string("okey"), CEPH_NOSNAP,
 510         67, 0, "n1"), 1, shard_id_t(0)));
 511   o.push_back(new ghobject_t(hobject_t(object_t("oname2"), string("okey"), CEPH_NOSNAP,
 512         67, 0, "n1"), 1, shard_id_t(1)));
 513   o.push_back(new ghobject_t(hobject_t(object_t("oname2"), string("okey"), CEPH_NOSNAP,
 514         67, 0, "n1"), 1, shard_id_t(2)));
 515   o.push_back(new ghobject_t(hobject_t(object_t("oname3"), string("oname3"),
 516         CEPH_SNAPDIR, 910, 1, "n2"), 1, shard_id_t(0)));
 517   o.push_back(new ghobject_t(hobject_t(object_t("oname3"), string("oname3"),
 518         CEPH_SNAPDIR, 910, 1, "n2"), 2, shard_id_t(0)));
 519   o.push_back(new ghobject_t(hobject_t(object_t("oname3"), string("oname3"),
 520         CEPH_SNAPDIR, 910, 1, "n2"), 3, shard_id_t(0)));
 521   o.push_back(new ghobject_t(hobject_t(object_t("oname3"), string("oname3"),
 522         CEPH_SNAPDIR, 910, 1, "n2"), 3, shard_id_t(1)));
 523   o.push_back(new ghobject_t(hobject_t(object_t("oname3"), string("oname3"),
 524         CEPH_SNAPDIR, 910, 1, "n2"), 3, shard_id_t(2)));
 525 }
 526
 527 ostream& operator<<(ostream& out, const ghobject_t& o)
 528 {
 529   if (o == ghobject_t())
 530     return out << "GHMIN";
 531   if (o.is_max())
 532     return out << "GHMAX";
 533   if (o.shard_id != shard_id_t::NO_SHARD)
 534     out << std::hex << o.shard_id << std::dec;
 535   out << '#' << o.hobj << '#';
 536   if (o.generation != ghobject_t::NO_GEN)
 537     out << std::hex << (unsigned long long)(o.generation) << std::dec;
 538   return out;
 539 }
 540
 541 bool ghobject_t::parse(const string& s)
 542 {
 543   if (s == "GHMIN") {
 544     *this = ghobject_t();
 545     return true;
 546   }
 547   if (s == "GHMAX") {
 548     *this = ghobject_t::get_max();
 549     return true;
 550   }
 551
 552   // look for shard# prefix
 553   const char *start = s.c_str();
 554   const char *p;
 555   int sh = shard_id_t::NO_SHARD;
 556   for (p = start; *p && isxdigit(*p); ++p) ;
 557   if (!*p && *p != '#')
 558     return false;
 559   if (p > start) {
 560     int r = sscanf(s.c_str(), "%x", &sh);
 561     if (r < 1)
 562       return false;
 563     start = p + 1;
 564   } else {
 565     ++start;
 566   }
 567
 568   // look for #generation suffix
 569   long long unsigned g = NO_GEN;
 570   const char *last = start + strlen(start) - 1;
 571   p = last;
 572   while (isxdigit(*p))
 573     p--;
 574   if (*p != '#')
 575     return false;
 576   if (p < last) {
 577     sscanf(p + 1, "%llx", &g);
 578   }
 579
 580   string inner(start, p - start);
 581   hobject_t h;
 582   if (!h.parse(inner)) {
 583     return false;
 584   }
 585
 586   shard_id = shard_id_t(sh);
 587   hobj = h;
 588   generation = g;
 589   max = false;
 590   return true;
 591 }
 592
 593 int cmp(const ghobject_t& l, const ghobject_t& r)
 594 {
 595   if (l.max < r.max)
 596     return -1;
 597   if (l.max > r.max)
 598     return 1;
 599   if (l.shard_id < r.shard_id)
 600     return -1;
 601   if (l.shard_id > r.shard_id)
 602     return 1;
 603   int ret = cmp(l.hobj, r.hobj);
 604   if (ret != 0)
 605     return ret;
 606   if (l.generation < r.generation)
 607     return -1;
 608   if (l.generation > r.generation)
 609     return 1;
 610   return 0;
 611 }