1 // -*- mode:C++; tab-width:8; c-basic-offset:2; indent-tabs-mode:t -*-
2 #include "include/memory.h"
5 #include <boost/scoped_ptr.hpp>
9 #include "include/buffer.h"
10 #include "common/map_cacher.hpp"
11 #include "osd/SnapMapper.h"
13 #include "gtest/gtest.h"
18 typename T::iterator rand_choose(T &cont) {
19 if (cont.size() == 0) {
22 int index = rand() % cont.size();
23 typename T::iterator retval = cont.begin();
25 for (; index > 0; --index) ++retval;
29 string random_string(size_t size)
32 for (size_t j = 0; j < size; ++j) {
33 name.push_back('a' + (rand() % 26));
38 class PausyAsyncMap : public MapCacher::StoreDriver<string, bufferlist> {
40 virtual void operate(map<string, bufferlist> *store) = 0;
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();
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();
62 store->erase(i->first);
67 struct Callback : public _Op {
69 explicit Callback(Context *c) : context(c) {}
70 void operate(map<string, bufferlist> *store) override {
75 class Transaction : public MapCacher::Transaction<string, bufferlist> {
76 friend class PausyAsyncMap;
80 void set_keys(const map<string, bufferlist> &i) override {
81 ops.push_back(Op(new Insert(i)));
83 void remove_keys(const set<string> &r) override {
84 ops.push_back(Op(new Remove(r)));
86 void add_callback(Context *c) override {
87 callbacks.push_back(Op(new Callback(c)));
93 map<string, bufferlist> store;
95 class Doer : public Thread {
96 static const size_t MAX_SIZE = 100;
97 PausyAsyncMap *parent;
104 explicit Doer(PausyAsyncMap *parent) :
105 parent(parent), lock("Doer lock"), stopping(0), paused(false) {}
106 void *entry() override {
110 Mutex::Locker l(lock);
111 while (!stopping && (queue.empty() || paused))
113 if (stopping && queue.empty()) {
118 assert(!queue.empty());
123 assert(!ops.empty());
125 for (list<Op>::iterator i = ops.begin();
129 usleep(1+(rand() % 5000));
130 Mutex::Locker l(parent->lock);
131 (*i)->operate(&(parent->store));
137 Mutex::Locker l(lock);
143 Mutex::Locker l(lock);
148 void submit(list<Op> &in) {
149 Mutex::Locker l(lock);
150 while (queue.size() >= MAX_SIZE)
152 queue.splice(queue.end(), in, in.begin(), in.end());
157 Mutex::Locker l(lock);
160 while (stopping != 2)
167 PausyAsyncMap() : lock("PausyAsyncMap"), doer(this) {
170 ~PausyAsyncMap() override {
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();
180 map<string, bufferlist>::iterator j = store.find(*i);
181 if (j != store.end())
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()) {
199 void submit(Transaction *t) {
201 doer.submit(t->callbacks);
205 Mutex lock("flush lock");
209 class OnFinish : public Context {
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);
223 t.add_callback(new OnFinish(&lock, &cond, &done));
226 Mutex::Locker l(lock);
244 class MapCacherTest : public ::testing::Test {
246 boost::scoped_ptr< PausyAsyncMap > driver;
247 boost::scoped_ptr<MapCacher::MapCacher<string, bufferlist> > cache;
248 map<string, bufferlist> truth;
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();
257 ASSERT_TRUE(!j.end());
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();
268 ASSERT_TRUE(j != m2.end());
269 ASSERT_EQ(i->first, j->first);
270 assert_bl_eq(i->second, j->second);
274 size_t random_num() {
275 return random() % 10;
277 size_t random_size() {
278 return random() % 1000;
280 void random_bl(size_t size, bufferlist *bl) {
281 for (size_t i = 0; i < size; ++i) {
286 size_t set_size = random_num();
287 map<string, bufferlist> to_set;
288 for (size_t i = 0; i < set_size; ++i) {
290 random_bl(random_size(), &bl);
291 string key = *rand_choose(names);
295 for (map<string, bufferlist>::iterator i = to_set.begin();
298 truth.erase(i->first);
302 PausyAsyncMap::Transaction t;
303 cache->set_keys(to_set, &t);
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));
313 for (set<string>::iterator i = to_remove.begin();
314 i != to_remove.end();
319 PausyAsyncMap::Transaction t;
320 cache->remove_keys(to_remove, &t);
326 size_t get_size = random_num();
327 for (size_t i = 0; i < get_size; ++i) {
328 to_get.insert(*rand_choose(names));
331 map<string, bufferlist> got_truth;
332 for (set<string>::iterator i = to_get.begin();
335 map<string, bufferlist>::iterator j = truth.find(*i);
336 if (j != truth.end())
337 got_truth.insert(*j);
340 map<string, bufferlist> got;
341 cache->get_keys(to_get, &got);
343 assert_bl_map_eq(got, got_truth);
349 pair<string, bufferlist> next;
350 int r = cache->get_next(cur, &next);
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())
358 ASSERT_EQ(r, r_truth);
362 ASSERT_EQ(next.first, next_truth.first);
363 assert_bl_eq(next.second, next_truth.second);
367 void SetUp() override {
368 driver.reset(new PausyAsyncMap());
369 cache.reset(new MapCacher::MapCacher<string, bufferlist>(driver.get()));
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)));
377 void TearDown() override {
385 TEST_F(MapCacherTest, Simple)
388 map<string, bufferlist> truth;
389 set<string> truth_keys;
393 truth[string("asdf")] = bl;
394 truth_keys.insert(truth.begin()->first);
396 PausyAsyncMap::Transaction t;
397 cache->set_keys(truth, &t);
399 cache->set_keys(truth, &t);
403 map<string, bufferlist> got;
404 cache->get_keys(truth_keys, &got);
405 assert_bl_map_eq(got, truth);
411 cache->get_keys(truth_keys, &got);
412 assert_bl_map_eq(got, truth);
415 TEST_F(MapCacherTest, Random)
417 for (size_t i = 0; i < 5000; ++i) {
419 std::cout << "On iteration " << i << std::endl;
421 switch (rand() % 4) {
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;
450 PausyAsyncMap *driver,
454 mapper(new SnapMapper(g_ceph_context, driver, mask, bits, 0, shard_id_t(1))),
455 mask(mask), bits(bits),
458 hobject_t random_hobject() {
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));
467 void choose_random_snaps(int num, set<snapid_t> *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);
476 snap_to_hobject[next];
480 void create_object() {
481 Mutex::Locker l(lock);
482 if (snap_to_hobject.empty())
486 obj = random_hobject();
487 } while (hobject_to_snap.count(obj));
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();
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);
499 PausyAsyncMap::Transaction t;
500 mapper->add_oid(obj, snaps, &t);
506 Mutex::Locker l(lock);
507 if (snap_to_hobject.empty())
509 map<snapid_t, set<hobject_t> >::iterator snap =
510 rand_choose(snap_to_hobject);
511 set<hobject_t> hobjects = snap->second;
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);
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);
528 PausyAsyncMap::Transaction t;
529 mapper->update_snaps(
536 if (j->second.empty()) {
537 hobject_to_snap.erase(j);
539 hoid = hobject_t::get_max();
543 assert(hobjects.empty());
544 snap_to_hobject.erase(snap);
548 Mutex::Locker l(lock);
549 if (hobject_to_snap.empty())
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();
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);
562 PausyAsyncMap::Transaction t;
568 hobject_to_snap.erase(obj);
572 Mutex::Locker l(lock);
573 if (hobject_to_snap.empty())
575 map<hobject_t, set<snapid_t>>::iterator obj =
576 rand_choose(hobject_to_snap);
578 int r = mapper->get_snaps(obj->first, &snaps);
580 ASSERT_EQ(snaps, obj->second);
584 class SnapMapperTest : public ::testing::Test {
586 boost::scoped_ptr< PausyAsyncMap > driver;
587 map<pg_t, ceph::shared_ptr<MapperVerifier> > mappers;
590 void SetUp() override {
591 driver.reset(new PausyAsyncMap());
595 void TearDown() override {
601 MapperVerifier &get_tester() {
602 //return *(mappers.begin()->second);
603 return *(rand_choose(mappers)->second);
606 void init(uint32_t to_set) {
608 for (uint32_t i = 0; i < pgnum; ++i) {
614 pgid.get_split_bits(pgnum)
621 for (int i = 0; i < 5000; ++i) {
623 std::cout << i << std::endl;
624 switch (rand() % 5) {
626 get_tester().create_snap();
629 get_tester().create_object();
632 get_tester().trim_snap();
635 get_tester().check_oid();
638 get_tester().remove_oid();
645 TEST_F(SnapMapperTest, Simple) {
647 get_tester().create_snap();
648 get_tester().create_object();
649 get_tester().trim_snap();
652 TEST_F(SnapMapperTest, More) {
657 TEST_F(SnapMapperTest, MultiPG) {