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