ceph/src/test/test_snap_mapper.cc

   1 // -*- mode:C++; tab-width:8; c-basic-offset:2; indent-tabs-mode:t -*-
   2 #include <iterator>
   3 #include <map>
   4 #include <set>
   5 #include <boost/scoped_ptr.hpp>
   6 #include <sys/types.h>
   7 #include <cstdlib>
   8
   9 #include "include/buffer.h"
  10 #include "common/map_cacher.hpp"
  11 #include "osd/SnapMapper.h"
  12 #include "common/Cond.h"
  13
  14 #include "gtest/gtest.h"
  15
  16 using namespace std;
  17
  18 template <typename T>
  19 typename T::iterator rand_choose(T &cont) {
  20   if (std::empty(cont)) {
  21     return std::end(cont);
  22   }
  23   return std::next(std::begin(cont), rand() % cont.size());
  24 }
  25
  26 string random_string(size_t size)
  27 {
  28   string name;
  29   for (size_t j = 0; j < size; ++j) {
  30     name.push_back('a' + (rand() % 26));
  31   }
  32   return name;
  33 }
  34
  35 class PausyAsyncMap : public MapCacher::StoreDriver<string, bufferlist> {
  36   struct _Op {
  37     virtual void operate(map<string, bufferlist> *store) = 0;
  38     virtual ~_Op() {}
  39   };
  40   typedef std::shared_ptr<_Op> Op;
  41   struct Remove : public _Op {
  42     set<string> to_remove;
  43     explicit Remove(const set<string> &to_remove) : to_remove(to_remove) {}
  44     void operate(map<string, bufferlist> *store) override {
  45       for (set<string>::iterator i = to_remove.begin();
  46            i != to_remove.end();
  47            ++i) {
  48         store->erase(*i);
  49       }
  50     }
  51   };
  52   struct Insert : public _Op {
  53     map<string, bufferlist> to_insert;
  54     explicit Insert(const map<string, bufferlist> &to_insert) : to_insert(to_insert) {}
  55     void operate(map<string, bufferlist> *store) override {
  56       for (map<string, bufferlist>::iterator i = to_insert.begin();
  57            i != to_insert.end();
  58            ++i) {
  59         store->erase(i->first);
  60         store->insert(*i);
  61       }
  62     }
  63   };
  64   struct Callback : public _Op {
  65     Context *context;
  66     explicit Callback(Context *c) : context(c) {}
  67     void operate(map<string, bufferlist> *store) override {
  68       context->complete(0);
  69     }
  70   };
  71 public:
  72   class Transaction : public MapCacher::Transaction<string, bufferlist> {
  73     friend class PausyAsyncMap;
  74     list<Op> ops;
  75     list<Op> callbacks;
  76   public:
  77     void set_keys(const map<string, bufferlist> &i) override {
  78       ops.push_back(Op(new Insert(i)));
  79     }
  80     void remove_keys(const set<string> &r) override {
  81       ops.push_back(Op(new Remove(r)));
  82     }
  83     void add_callback(Context *c) override {
  84       callbacks.push_back(Op(new Callback(c)));
  85     }
  86   };
  87 private:
  88
  89   ceph::mutex lock = ceph::make_mutex("PausyAsyncMap");
  90   map<string, bufferlist> store;
  91
  92   class Doer : public Thread {
  93     static const size_t MAX_SIZE = 100;
  94     PausyAsyncMap *parent;
  95     ceph::mutex lock = ceph::make_mutex("Doer lock");
  96     ceph::condition_variable cond;
  97     int stopping;
  98     bool paused;
  99     list<Op> queue;
 100   public:
 101     explicit Doer(PausyAsyncMap *parent) :
 102       parent(parent), stopping(0), paused(false) {}
 103     void *entry() override {
 104       while (1) {
 105         list<Op> ops;
 106         {
 107           std::unique_lock l{lock};
 108           cond.wait(l, [this] {
 109             return stopping || (!queue.empty() && !paused);
 110           });
 111           if (stopping && queue.empty()) {
 112             stopping = 2;
 113             cond.notify_all();
 114             return 0;
 115           }
 116           ceph_assert(!queue.empty());
 117           ceph_assert(!paused);
 118           ops.swap(queue);
 119           cond.notify_all();
 120         }
 121         ceph_assert(!ops.empty());
 122
 123         for (list<Op>::iterator i = ops.begin();
 124              i != ops.end();
 125              ops.erase(i++)) {
 126           if (!(rand()%3))
 127             usleep(1+(rand() % 5000));
 128           std::lock_guard l{parent->lock};
 129           (*i)->operate(&(parent->store));
 130         }
 131       }
 132     }
 133
 134     void pause() {
 135       std::lock_guard l{lock};
 136       paused = true;
 137       cond.notify_all();
 138     }
 139
 140     void resume() {
 141       std::lock_guard l{lock};
 142       paused = false;
 143       cond.notify_all();
 144     }
 145
 146     void submit(list<Op> &in) {
 147       std::unique_lock l{lock};
 148       cond.wait(l, [this] { return queue.size() < MAX_SIZE;});
 149       queue.splice(queue.end(), in, in.begin(), in.end());
 150       cond.notify_all();
 151     }
 152
 153     void stop() {
 154       std::unique_lock l{lock};
 155       stopping = 1;
 156       cond.notify_all();
 157       cond.wait(l, [this] { return stopping == 2; });
 158       cond.notify_all();
 159     }
 160   } doer;
 161
 162 public:
 163   PausyAsyncMap() : doer(this) {
 164     doer.create("doer");
 165   }
 166   ~PausyAsyncMap() override {
 167     doer.join();
 168   }
 169   int get_keys(
 170     const set<string> &keys,
 171     map<string, bufferlist> *out) override {
 172     std::lock_guard l{lock};
 173     for (set<string>::const_iterator i = keys.begin();
 174          i != keys.end();
 175          ++i) {
 176       map<string, bufferlist>::iterator j = store.find(*i);
 177       if (j != store.end())
 178         out->insert(*j);
 179     }
 180     return 0;
 181   }
 182   int get_next(
 183     const string &key,
 184     pair<string, bufferlist> *next) override {
 185     std::lock_guard l{lock};
 186     map<string, bufferlist>::iterator j = store.upper_bound(key);
 187     if (j != store.end()) {
 188       if (next)
 189         *next = *j;
 190       return 0;
 191     } else {
 192       return -ENOENT;
 193     }
 194   }
 195   void submit(Transaction *t) {
 196     doer.submit(t->ops);
 197     doer.submit(t->callbacks);
 198   }
 199
 200   void flush() {
 201     ceph::mutex lock = ceph::make_mutex("flush lock");
 202     ceph::condition_variable cond;
 203     bool done = false;
 204
 205     class OnFinish : public Context {
 206       ceph::mutex *lock;
 207       ceph::condition_variable *cond;
 208       bool *done;
 209     public:
 210       OnFinish(ceph::mutex *lock, ceph::condition_variable *cond, bool *done)
 211         : lock(lock), cond(cond), done(done) {}
 212       void finish(int) override {
 213         std::lock_guard l{*lock};
 214         *done = true;
 215         cond->notify_all();
 216       }
 217     };
 218     Transaction t;
 219     t.add_callback(new OnFinish(&lock, &cond, &done));
 220     submit(&t);
 221     {
 222       std::unique_lock l{lock};
 223       cond.wait(l, [&] { return done; });
 224     }
 225   }
 226
 227   void pause() {
 228     doer.pause();
 229   }
 230   void resume() {
 231     doer.resume();
 232   }
 233   void stop() {
 234     doer.stop();
 235   }
 236
 237 };
 238
 239 class MapCacherTest : public ::testing::Test {
 240 protected:
 241   boost::scoped_ptr< PausyAsyncMap > driver;
 242   boost::scoped_ptr<MapCacher::MapCacher<string, bufferlist> > cache;
 243   map<string, bufferlist> truth;
 244   set<string> names;
 245 public:
 246   void assert_bl_eq(bufferlist &bl1, bufferlist &bl2) {
 247     ASSERT_EQ(bl1.length(), bl2.length());
 248     bufferlist::iterator j = bl2.begin();
 249     for (bufferlist::iterator i = bl1.begin();
 250          !i.end();
 251          ++i, ++j) {
 252       ASSERT_TRUE(!j.end());
 253       ASSERT_EQ(*i, *j);
 254     }
 255   }
 256   void assert_bl_map_eq(map<string, bufferlist> &m1,
 257                         map<string, bufferlist> &m2) {
 258     ASSERT_EQ(m1.size(), m2.size());
 259     map<string, bufferlist>::iterator j = m2.begin();
 260     for (map<string, bufferlist>::iterator i = m1.begin();
 261          i != m1.end();
 262          ++i, ++j) {
 263       ASSERT_TRUE(j != m2.end());
 264       ASSERT_EQ(i->first, j->first);
 265       assert_bl_eq(i->second, j->second);
 266     }
 267
 268   }
 269   size_t random_num() {
 270     return random() % 10;
 271   }
 272   size_t random_size() {
 273     return random() % 1000;
 274   }
 275   void random_bl(size_t size, bufferlist *bl) {
 276     for (size_t i = 0; i < size; ++i) {
 277       bl->append(rand());
 278     }
 279   }
 280   void do_set() {
 281     size_t set_size = random_num();
 282     map<string, bufferlist> to_set;
 283     for (size_t i = 0; i < set_size; ++i) {
 284       bufferlist bl;
 285       random_bl(random_size(), &bl);
 286       string key = *rand_choose(names);
 287       to_set.insert(
 288         make_pair(key, bl));
 289     }
 290     for (map<string, bufferlist>::iterator i = to_set.begin();
 291          i != to_set.end();
 292          ++i) {
 293       truth.erase(i->first);
 294       truth.insert(*i);
 295     }
 296     {
 297       PausyAsyncMap::Transaction t;
 298       cache->set_keys(to_set, &t);
 299       driver->submit(&t);
 300     }
 301   }
 302   void remove() {
 303     size_t remove_size = random_num();
 304     set<string> to_remove;
 305     for (size_t i = 0; i < remove_size ; ++i) {
 306       to_remove.insert(*rand_choose(names));
 307     }
 308     for (set<string>::iterator i = to_remove.begin();
 309          i != to_remove.end();
 310          ++i) {
 311       truth.erase(*i);
 312     }
 313     {
 314       PausyAsyncMap::Transaction t;
 315       cache->remove_keys(to_remove, &t);
 316       driver->submit(&t);
 317     }
 318   }
 319   void get() {
 320     set<string> to_get;
 321     size_t get_size = random_num();
 322     for (size_t i = 0; i < get_size; ++i) {
 323       to_get.insert(*rand_choose(names));
 324     }
 325
 326     map<string, bufferlist> got_truth;
 327     for (set<string>::iterator i = to_get.begin();
 328          i != to_get.end();
 329          ++i) {
 330       map<string, bufferlist>::iterator j = truth.find(*i);
 331       if (j != truth.end())
 332         got_truth.insert(*j);
 333     }
 334
 335     map<string, bufferlist> got;
 336     cache->get_keys(to_get, &got);
 337
 338     assert_bl_map_eq(got, got_truth);
 339   }
 340
 341   void get_next() {
 342     string cur;
 343     while (true) {
 344       pair<string, bufferlist> next;
 345       int r = cache->get_next(cur, &next);
 346
 347       pair<string, bufferlist> next_truth;
 348       map<string, bufferlist>::iterator i = truth.upper_bound(cur);
 349       int r_truth = (i == truth.end()) ? -ENOENT : 0;
 350       if (i != truth.end())
 351         next_truth = *i;
 352
 353       ASSERT_EQ(r, r_truth);
 354       if (r == -ENOENT)
 355         break;
 356
 357       ASSERT_EQ(next.first, next_truth.first);
 358       assert_bl_eq(next.second, next_truth.second);
 359       cur = next.first;
 360     }
 361   }
 362   void SetUp() override {
 363     driver.reset(new PausyAsyncMap());
 364     cache.reset(new MapCacher::MapCacher<string, bufferlist>(driver.get()));
 365     names.clear();
 366     truth.clear();
 367     size_t names_size(random_num() + 10);
 368     for (size_t i = 0; i < names_size; ++i) {
 369       names.insert(random_string(1 + (random_size() % 10)));
 370     }
 371   }
 372   void TearDown() override {
 373     driver->stop();
 374     cache.reset();
 375     driver.reset();
 376   }
 377
 378 };
 379
 380 TEST_F(MapCacherTest, Simple)
 381 {
 382   driver->pause();
 383   map<string, bufferlist> truth;
 384   set<string> truth_keys;
 385   string blah("asdf");
 386   bufferlist bl;
 387   encode(blah, bl);
 388   truth[string("asdf")] = bl;
 389   truth_keys.insert(truth.begin()->first);
 390   {
 391     PausyAsyncMap::Transaction t;
 392     cache->set_keys(truth, &t);
 393     driver->submit(&t);
 394     cache->set_keys(truth, &t);
 395     driver->submit(&t);
 396   }
 397
 398   map<string, bufferlist> got;
 399   cache->get_keys(truth_keys, &got);
 400   assert_bl_map_eq(got, truth);
 401
 402   driver->resume();
 403   sleep(1);
 404
 405   got.clear();
 406   cache->get_keys(truth_keys, &got);
 407   assert_bl_map_eq(got, truth);
 408 }
 409
 410 TEST_F(MapCacherTest, Random)
 411 {
 412   for (size_t i = 0; i < 5000; ++i) {
 413     if (!(i % 50)) {
 414       std::cout << "On iteration " << i << std::endl;
 415     }
 416     switch (rand() % 4) {
 417     case 0:
 418       get();
 419       break;
 420     case 1:
 421       do_set();
 422       break;
 423     case 2:
 424       get_next();
 425       break;
 426     case 3:
 427       remove();
 428       break;
 429     }
 430   }
 431 }
 432
 433 class MapperVerifier {
 434   PausyAsyncMap *driver;
 435   boost::scoped_ptr< SnapMapper > mapper;
 436   map<snapid_t, set<hobject_t> > snap_to_hobject;
 437   map<hobject_t, set<snapid_t>> hobject_to_snap;
 438   snapid_t next;
 439   uint32_t mask;
 440   uint32_t bits;
 441   ceph::mutex lock = ceph::make_mutex("lock");
 442 public:
 443
 444   MapperVerifier(
 445     PausyAsyncMap *driver,
 446     uint32_t mask,
 447     uint32_t bits)
 448     : driver(driver),
 449       mapper(new SnapMapper(g_ceph_context, driver, mask, bits, 0, shard_id_t(1))),
 450              mask(mask), bits(bits) {}
 451
 452   hobject_t random_hobject() {
 453     return hobject_t(
 454       random_string(1+(rand() % 16)),
 455       random_string(1+(rand() % 16)),
 456       snapid_t(rand() % 1000),
 457       (rand() & ((~0)<<bits)) | (mask & ~((~0)<<bits)),
 458       0, random_string(rand() % 16));
 459   }
 460
 461   void choose_random_snaps(int num, set<snapid_t> *snaps) {
 462     ceph_assert(snaps);
 463     ceph_assert(!snap_to_hobject.empty());
 464     for (int i = 0; i < num || snaps->empty(); ++i) {
 465       snaps->insert(rand_choose(snap_to_hobject)->first);
 466     }
 467   }
 468
 469   void create_snap() {
 470     snap_to_hobject[next];
 471     ++next;
 472   }
 473
 474   void create_object() {
 475     std::lock_guard l{lock};
 476     if (snap_to_hobject.empty())
 477       return;
 478     hobject_t obj;
 479     do {
 480       obj = random_hobject();
 481     } while (hobject_to_snap.count(obj));
 482
 483     set<snapid_t> &snaps = hobject_to_snap[obj];
 484     choose_random_snaps(1 + (rand() % 20), &snaps);
 485     for (set<snapid_t>::iterator i = snaps.begin();
 486          i != snaps.end();
 487          ++i) {
 488       map<snapid_t, set<hobject_t> >::iterator j = snap_to_hobject.find(*i);
 489       ceph_assert(j != snap_to_hobject.end());
 490       j->second.insert(obj);
 491     }
 492     {
 493       PausyAsyncMap::Transaction t;
 494       mapper->add_oid(obj, snaps, &t);
 495       driver->submit(&t);
 496     }
 497   }
 498
 499   std::pair<std::string, ceph::buffer::list> to_raw(
 500     const std::pair<snapid_t, hobject_t> &to_map) {
 501     return mapper->to_raw(to_map);
 502   }
 503
 504   std::string to_legacy_raw_key(
 505     const std::pair<snapid_t, hobject_t> &to_map) {
 506     return mapper->to_legacy_raw_key(to_map);
 507   }
 508
 509   std::string to_raw_key(
 510     const std::pair<snapid_t, hobject_t> &to_map) {
 511     return mapper->to_raw_key(to_map);
 512   }
 513
 514   void trim_snap() {
 515     std::lock_guard l{lock};
 516     if (snap_to_hobject.empty())
 517       return;
 518     map<snapid_t, set<hobject_t> >::iterator snap =
 519       rand_choose(snap_to_hobject);
 520     set<hobject_t> hobjects = snap->second;
 521
 522     vector<hobject_t> hoids;
 523     while (mapper->get_next_objects_to_trim(
 524              snap->first, rand() % 5 + 1, &hoids) == 0) {
 525       for (auto &&hoid: hoids) {
 526         ceph_assert(!hoid.is_max());
 527         ceph_assert(hobjects.count(hoid));
 528         hobjects.erase(hoid);
 529
 530         map<hobject_t, set<snapid_t>>::iterator j =
 531           hobject_to_snap.find(hoid);
 532         ceph_assert(j->second.count(snap->first));
 533         set<snapid_t> old_snaps(j->second);
 534         j->second.erase(snap->first);
 535
 536         {
 537           PausyAsyncMap::Transaction t;
 538           mapper->update_snaps(
 539             hoid,
 540             j->second,
 541             &old_snaps,
 542             &t);
 543           driver->submit(&t);
 544         }
 545         if (j->second.empty()) {
 546           hobject_to_snap.erase(j);
 547         }
 548         hoid = hobject_t::get_max();
 549       }
 550       hoids.clear();
 551     }
 552     ceph_assert(hobjects.empty());
 553     snap_to_hobject.erase(snap);
 554   }
 555
 556   void remove_oid() {
 557     std::lock_guard l{lock};
 558     if (hobject_to_snap.empty())
 559       return;
 560     map<hobject_t, set<snapid_t>>::iterator obj =
 561       rand_choose(hobject_to_snap);
 562     for (set<snapid_t>::iterator i = obj->second.begin();
 563          i != obj->second.end();
 564          ++i) {
 565       map<snapid_t, set<hobject_t> >::iterator j =
 566         snap_to_hobject.find(*i);
 567       ceph_assert(j->second.count(obj->first));
 568       j->second.erase(obj->first);
 569     }
 570     {
 571       PausyAsyncMap::Transaction t;
 572       mapper->remove_oid(
 573         obj->first,
 574         &t);
 575       driver->submit(&t);
 576     }
 577     hobject_to_snap.erase(obj);
 578   }
 579
 580   void check_oid() {
 581     std::lock_guard l{lock};
 582     if (hobject_to_snap.empty())
 583       return;
 584     map<hobject_t, set<snapid_t>>::iterator obj =
 585       rand_choose(hobject_to_snap);
 586     set<snapid_t> snaps;
 587     int r = mapper->get_snaps(obj->first, &snaps);
 588     ceph_assert(r == 0);
 589     ASSERT_EQ(snaps, obj->second);
 590   }
 591 };
 592
 593 class SnapMapperTest : public ::testing::Test {
 594 protected:
 595   boost::scoped_ptr< PausyAsyncMap > driver;
 596   map<pg_t, std::shared_ptr<MapperVerifier> > mappers;
 597   uint32_t pgnum;
 598
 599   void SetUp() override {
 600     driver.reset(new PausyAsyncMap());
 601     pgnum = 0;
 602   }
 603
 604   void TearDown() override {
 605     driver->stop();
 606     mappers.clear();
 607     driver.reset();
 608   }
 609
 610   MapperVerifier &get_tester() {
 611     //return *(mappers.begin()->second);
 612     return *(rand_choose(mappers)->second);
 613   }
 614
 615   void init(uint32_t to_set) {
 616     pgnum = to_set;
 617     for (uint32_t i = 0; i < pgnum; ++i) {
 618       pg_t pgid(i, 0);
 619       mappers[pgid].reset(
 620         new MapperVerifier(
 621           driver.get(),
 622           i,
 623           pgid.get_split_bits(pgnum)
 624           )
 625         );
 626     }
 627   }
 628
 629   void run() {
 630     for (int i = 0; i < 5000; ++i) {
 631       if (!(i % 50))
 632         std::cout << i << std::endl;
 633       switch (rand() % 5) {
 634       case 0:
 635         get_tester().create_snap();
 636         break;
 637       case 1:
 638         get_tester().create_object();
 639         break;
 640       case 2:
 641         get_tester().trim_snap();
 642         break;
 643       case 3:
 644         get_tester().check_oid();
 645         break;
 646       case 4:
 647         get_tester().remove_oid();
 648         break;
 649       }
 650     }
 651   }
 652 };
 653
 654 TEST_F(SnapMapperTest, Simple) {
 655   init(1);
 656   get_tester().create_snap();
 657   get_tester().create_object();
 658   get_tester().trim_snap();
 659 }
 660
 661 TEST_F(SnapMapperTest, More) {
 662   init(1);
 663   run();
 664 }
 665
 666 TEST_F(SnapMapperTest, MultiPG) {
 667   init(50);
 668   run();
 669 }
 670
 671 TEST_F(SnapMapperTest, LegacyKeyConvertion) {
 672     init(1);
 673     auto obj = get_tester().random_hobject();
 674     snapid_t snapid = random() % 10;
 675     auto snap_obj = make_pair(snapid, obj);
 676     auto raw = get_tester().to_raw(snap_obj);
 677     std::string old_key = get_tester().to_legacy_raw_key(snap_obj);
 678     std::string converted_key =
 679       SnapMapper::convert_legacy_key(old_key, raw.second);
 680     std::string new_key = get_tester().to_raw_key(snap_obj);
 681     std::cout << "Converted: " << old_key << "\nTo:        " << converted_key
 682               << "\nNew key:   " << new_key << std::endl;
 683     ASSERT_EQ(converted_key, new_key);
 684 }
 685