ceph/src/test/test_snap_mapper.cc

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