ceph/src/test/ObjectMap/test_keyvaluedb_iterators.cc

   1 // -*- mode:C++; tab-width:8; c-basic-offset:2; indent-tabs-mode:t -*-
   2 // vim: ts=8 sw=2 smarttab
   3 /*
   4 * Ceph - scalable distributed file system
   5 *
   6 * Copyright (C) 2012 Inktank, Inc.
   7 *
   8 * This is free software; you can redistribute it and/or
   9 * modify it under the terms of the GNU Lesser General Public
  10 * License version 2.1, as published by the Free Software
  11 * Foundation. See file COPYING.
  12 */
  13 #include <map>
  14 #include <set>
  15 #include <deque>
  16 #include <boost/scoped_ptr.hpp>
  17
  18 #include "test/ObjectMap/KeyValueDBMemory.h"
  19 #include "kv/KeyValueDB.h"
  20 #include <sys/types.h>
  21 #include "global/global_init.h"
  22 #include "common/ceph_argparse.h"
  23 #include "gtest/gtest.h"
  24
  25 using namespace std;
  26
  27 string store_path;
  28
  29 class IteratorTest : public ::testing::Test
  30 {
  31 public:
  32   boost::scoped_ptr<KeyValueDB> db;
  33   boost::scoped_ptr<KeyValueDBMemory> mock;
  34
  35   void SetUp() override {
  36     ceph_assert(!store_path.empty());
  37
  38     KeyValueDB *db_ptr = KeyValueDB::create(g_ceph_context, "leveldb", store_path);
  39     ceph_assert(!db_ptr->create_and_open(std::cerr));
  40     db.reset(db_ptr);
  41     mock.reset(new KeyValueDBMemory());
  42   }
  43
  44   void TearDown() override { }
  45
  46   ::testing::AssertionResult validate_db_clear(KeyValueDB *store) {
  47     KeyValueDB::WholeSpaceIterator it = store->get_wholespace_iterator();
  48     it->seek_to_first();
  49     while (it->valid()) {
  50       pair<string,string> k = it->raw_key();
  51       if (mock->db.count(k)) {
  52         return ::testing::AssertionFailure()
  53                 << __func__
  54                 << " mock store count " << mock->db.count(k)
  55                 << " key(" << k.first << "," << k.second << ")";
  56       }
  57       it->next();
  58     }
  59     return ::testing::AssertionSuccess();
  60   }
  61
  62   ::testing::AssertionResult validate_db_match() {
  63     KeyValueDB::WholeSpaceIterator it = db->get_wholespace_iterator();
  64     it->seek_to_first();
  65     while (it->valid()) {
  66       pair<string, string> k = it->raw_key();
  67       if (!mock->db.count(k)) {
  68         return ::testing::AssertionFailure()
  69                 << __func__
  70                 << " mock db.count() " << mock->db.count(k)
  71                 << " key(" << k.first << "," << k.second << ")";
  72       }
  73
  74       bufferlist it_bl = it->value();
  75       bufferlist mock_bl = mock->db[k];
  76
  77       string it_val = _bl_to_str(it_bl);
  78       string mock_val = _bl_to_str(mock_bl);
  79
  80       if (it_val != mock_val) {
  81         return ::testing::AssertionFailure()
  82                 << __func__
  83                 << " key(" << k.first << "," << k.second << ")"
  84                 << " mismatch db value(" << it_val << ")"
  85                 << " mock value(" << mock_val << ")";
  86       }
  87       it->next();
  88     }
  89     return ::testing::AssertionSuccess();
  90   }
  91
  92   ::testing::AssertionResult validate_iterator(
  93                                 KeyValueDB::WholeSpaceIterator it,
  94                                 string expected_prefix,
  95                                 const string &expected_key,
  96                                 const string &expected_value) {
  97     if (!it->valid()) {
  98       return ::testing::AssertionFailure()
  99               << __func__
 100               << " iterator not valid";
 101     }
 102
 103     if (!it->raw_key_is_prefixed(expected_prefix)) {
 104       return ::testing::AssertionFailure()
 105               << __func__
 106               << " expected raw_key_is_prefixed() == TRUE"
 107               << " got FALSE";
 108     }
 109
 110     if (it->raw_key_is_prefixed("??__SomeUnexpectedValue__??")) {
 111       return ::testing::AssertionFailure()
 112               << __func__
 113               << " expected raw_key_is_prefixed() == FALSE"
 114               << " got TRUE";
 115     }
 116
 117     pair<string,string> key = it->raw_key();
 118
 119     if (expected_prefix != key.first) {
 120       return ::testing::AssertionFailure()
 121               << __func__
 122               << " expected prefix '" << expected_prefix << "'"
 123               << " got prefix '" << key.first << "'";
 124     }
 125
 126     if (expected_key != it->key()) {
 127       return ::testing::AssertionFailure()
 128               << __func__
 129               << " expected key '" << expected_key << "'"
 130               << " got key '" << it->key() << "'";
 131     }
 132
 133     if (it->key() != key.second) {
 134       return ::testing::AssertionFailure()
 135               << __func__
 136               << " key '" << it->key() << "'"
 137               << " does not match"
 138               << " pair key '" << key.second << "'";
 139     }
 140
 141     if (_bl_to_str(it->value()) != expected_value) {
 142       return ::testing::AssertionFailure()
 143         << __func__
 144         << " key '(" << key.first << "," << key.second << ")''"
 145         << " expected value '" << expected_value << "'"
 146         << " got value '" << _bl_to_str(it->value()) << "'";
 147     }
 148
 149     return ::testing::AssertionSuccess();
 150   }
 151
 152   /**
 153    * Checks if each key in the queue can be forward sequentially read from
 154    * the iterator iter. All keys must be present and be prefixed with prefix,
 155    * otherwise the validation will fail.
 156    *
 157    * Assumes that each key value must be based on the key name and generated
 158    * by _gen_val().
 159    */
 160   void validate_prefix(KeyValueDB::WholeSpaceIterator iter,
 161       string &prefix, deque<string> &keys) {
 162
 163     while (!keys.empty()) {
 164       ASSERT_TRUE(iter->valid());
 165       string expected_key = keys.front();
 166       keys.pop_front();
 167       string expected_value = _gen_val_str(expected_key);
 168
 169       ASSERT_TRUE(validate_iterator(iter, prefix,
 170                   expected_key, expected_value));
 171
 172       iter->next();
 173     }
 174   }
 175   /**
 176    * Checks if each key in the queue can be backward sequentially read from
 177    * the iterator iter. All keys must be present and be prefixed with prefix,
 178    * otherwise the validation will fail.
 179    *
 180    * Assumes that each key value must be based on the key name and generated
 181    * by _gen_val().
 182    */
 183   void validate_prefix_backwards(KeyValueDB::WholeSpaceIterator iter,
 184       string &prefix, deque<string> &keys) {
 185
 186     while (!keys.empty()) {
 187       ASSERT_TRUE(iter->valid());
 188       string expected_key = keys.front();
 189       keys.pop_front();
 190       string expected_value = _gen_val_str(expected_key);
 191
 192       ASSERT_TRUE(validate_iterator(iter, prefix,
 193                   expected_key, expected_value));
 194
 195       iter->prev();
 196     }
 197   }
 198
 199   void clear(KeyValueDB *store) {
 200     KeyValueDB::WholeSpaceIterator it = store->get_wholespace_iterator();
 201     it->seek_to_first();
 202     KeyValueDB::Transaction t = store->get_transaction();
 203     while (it->valid()) {
 204       pair<string,string> k = it->raw_key();
 205       t->rmkey(k.first, k.second);
 206       it->next();
 207     }
 208     store->submit_transaction_sync(t);
 209   }
 210
 211   string _bl_to_str(bufferlist val) {
 212     string str(val.c_str(), val.length());
 213     return str;
 214   }
 215
 216   string _gen_val_str(const string &key) {
 217     ostringstream ss;
 218     ss << "##value##" << key << "##";
 219     return ss.str();
 220  }
 221
 222   bufferlist _gen_val(const string &key) {
 223     bufferlist bl;
 224     bl.append(_gen_val_str(key));
 225     return bl;
 226   }
 227
 228   void print_iterator(KeyValueDB::WholeSpaceIterator iter) {
 229     if (!iter->valid()) {
 230       std::cerr << __func__ << " iterator is not valid; stop." << std::endl;
 231       return;
 232     }
 233
 234     int i = 0;
 235     while (iter->valid()) {
 236       pair<string,string> k = iter->raw_key();
 237       std::cerr << __func__
 238                 << " pos " << (++i)
 239                 << " key (" << k.first << "," << k.second << ")"
 240                 << " value(" << _bl_to_str(iter->value()) << ")" << std::endl;
 241       iter->next();
 242     }
 243   }
 244
 245   void print_db(KeyValueDB *store) {
 246     KeyValueDB::WholeSpaceIterator it = store->get_wholespace_iterator();
 247     it->seek_to_first();
 248     print_iterator(it);
 249   }
 250 };
 251
 252 // ------- Remove Keys / Remove Keys By Prefix -------
 253 class RmKeysTest : public IteratorTest
 254 {
 255 public:
 256   string prefix1;
 257   string prefix2;
 258   string prefix3;
 259
 260   void init(KeyValueDB *db) {
 261     KeyValueDB::Transaction tx = db->get_transaction();
 262
 263     tx->set(prefix1, "11", _gen_val("11"));
 264     tx->set(prefix1, "12", _gen_val("12"));
 265     tx->set(prefix1, "13", _gen_val("13"));
 266     tx->set(prefix2, "21", _gen_val("21"));
 267     tx->set(prefix2, "22", _gen_val("22"));
 268     tx->set(prefix2, "23", _gen_val("23"));
 269     tx->set(prefix3, "31", _gen_val("31"));
 270     tx->set(prefix3, "32", _gen_val("32"));
 271     tx->set(prefix3, "33", _gen_val("33"));
 272
 273     db->submit_transaction_sync(tx);
 274   }
 275
 276   void SetUp() override {
 277     IteratorTest::SetUp();
 278
 279     prefix1 = "_PREFIX_1_";
 280     prefix2 = "_PREFIX_2_";
 281     prefix3 = "_PREFIX_3_";
 282
 283     clear(db.get());
 284     ASSERT_TRUE(validate_db_clear(db.get()));
 285     clear(mock.get());
 286     ASSERT_TRUE(validate_db_match());
 287
 288     init(db.get());
 289     init(mock.get());
 290
 291     ASSERT_TRUE(validate_db_match());
 292   }
 293
 294   void TearDown() override {
 295     IteratorTest::TearDown();
 296   }
 297
 298
 299   /**
 300    * Test the transaction's rmkeys behavior when we remove a given prefix
 301    * from the beginning of the key space, or from the end of the key space,
 302    * or even simply in the middle.
 303    */
 304   void RmKeysByPrefix(KeyValueDB *store) {
 305     // remove prefix2 ; check if prefix1 remains, and then prefix3
 306     KeyValueDB::Transaction tx = store->get_transaction();
 307     // remove the prefix in the middle of the key space
 308     tx->rmkeys_by_prefix(prefix2);
 309     store->submit_transaction_sync(tx);
 310
 311     deque<string> key_deque;
 312     KeyValueDB::WholeSpaceIterator iter = store->get_wholespace_iterator();
 313     iter->seek_to_first();
 314
 315     // check for prefix1
 316     key_deque.push_back("11");
 317     key_deque.push_back("12");
 318     key_deque.push_back("13");
 319     validate_prefix(iter, prefix1, key_deque);
 320     ASSERT_FALSE(HasFatalFailure());
 321
 322     // check for prefix3
 323     ASSERT_TRUE(iter->valid());
 324     key_deque.clear();
 325     key_deque.push_back("31");
 326     key_deque.push_back("32");
 327     key_deque.push_back("33");
 328     validate_prefix(iter, prefix3, key_deque);
 329     ASSERT_FALSE(HasFatalFailure());
 330
 331     ASSERT_FALSE(iter->valid());
 332
 333     clear(store);
 334     ASSERT_TRUE(validate_db_clear(store));
 335     init(store);
 336
 337     // remove prefix1 ; check if prefix2 and then prefix3 remain
 338     tx = store->get_transaction();
 339     // remove the prefix at the beginning of the key space
 340     tx->rmkeys_by_prefix(prefix1);
 341     store->submit_transaction_sync(tx);
 342
 343     iter = store->get_wholespace_iterator();
 344     iter->seek_to_first();
 345
 346     // check for prefix2
 347     key_deque.clear();
 348     key_deque.push_back("21");
 349     key_deque.push_back("22");
 350     key_deque.push_back("23");
 351     validate_prefix(iter, prefix2, key_deque);
 352     ASSERT_FALSE(HasFatalFailure());
 353
 354     // check for prefix3
 355     ASSERT_TRUE(iter->valid());
 356     key_deque.clear();
 357     key_deque.push_back("31");
 358     key_deque.push_back("32");
 359     key_deque.push_back("33");
 360     validate_prefix(iter, prefix3, key_deque);
 361     ASSERT_FALSE(HasFatalFailure());
 362
 363     ASSERT_FALSE(iter->valid());
 364
 365     clear(store);
 366     ASSERT_TRUE(validate_db_clear(store));
 367     init(store);
 368
 369     // remove prefix3 ; check if prefix1 and then prefix2 remain
 370     tx = store->get_transaction();
 371     // remove the prefix at the end of the key space
 372     tx->rmkeys_by_prefix(prefix3);
 373     store->submit_transaction_sync(tx);
 374
 375     iter = store->get_wholespace_iterator();
 376     iter->seek_to_first();
 377
 378     // check for prefix1
 379     key_deque.clear();
 380     key_deque.push_back("11");
 381     key_deque.push_back("12");
 382     key_deque.push_back("13");
 383     validate_prefix(iter, prefix1, key_deque);
 384     ASSERT_FALSE(HasFatalFailure());
 385
 386     // check for prefix2
 387     ASSERT_TRUE(iter->valid());
 388     key_deque.clear();
 389     key_deque.push_back("21");
 390     key_deque.push_back("22");
 391     key_deque.push_back("23");
 392     validate_prefix(iter, prefix2, key_deque);
 393     ASSERT_FALSE(HasFatalFailure());
 394
 395     ASSERT_FALSE(iter->valid());
 396   }
 397
 398   /**
 399    * Test how the leveldb's whole-space iterator behaves when we remove
 400    * keys from the store while iterating over them.
 401    */
 402   void RmKeysWhileIteratingSnapshot(KeyValueDB *store,
 403                                     KeyValueDB::WholeSpaceIterator iter) {
 404
 405     SCOPED_TRACE("RmKeysWhileIteratingSnapshot");
 406
 407     iter->seek_to_first();
 408     ASSERT_TRUE(iter->valid());
 409
 410     KeyValueDB::Transaction t = store->get_transaction();
 411     t->rmkey(prefix1, "11");
 412     t->rmkey(prefix1, "12");
 413     t->rmkey(prefix2, "23");
 414     t->rmkey(prefix3, "33");
 415     store->submit_transaction_sync(t);
 416
 417     deque<string> key_deque;
 418
 419     // check for prefix1
 420     key_deque.push_back("11");
 421     key_deque.push_back("12");
 422     key_deque.push_back("13");
 423     validate_prefix(iter, prefix1, key_deque);
 424     ASSERT_FALSE(HasFatalFailure());
 425
 426     // check for prefix2
 427     key_deque.clear();
 428     key_deque.push_back("21");
 429     key_deque.push_back("22");
 430     key_deque.push_back("23");
 431     validate_prefix(iter, prefix2, key_deque);
 432     ASSERT_FALSE(HasFatalFailure());
 433
 434     // check for prefix3
 435     key_deque.clear();
 436     key_deque.push_back("31");
 437     key_deque.push_back("32");
 438     key_deque.push_back("33");
 439     validate_prefix(iter, prefix3, key_deque);
 440     ASSERT_FALSE(HasFatalFailure());
 441
 442     iter->next();
 443     ASSERT_FALSE(iter->valid());
 444
 445     // make sure those keys were removed from the store
 446     KeyValueDB::WholeSpaceIterator tmp_it = store->get_wholespace_iterator();
 447     tmp_it->seek_to_first();
 448     ASSERT_TRUE(tmp_it->valid());
 449
 450     key_deque.clear();
 451     key_deque.push_back("13");
 452     validate_prefix(tmp_it, prefix1, key_deque);
 453     ASSERT_FALSE(HasFatalFailure());
 454
 455     ASSERT_TRUE(tmp_it->valid());
 456     key_deque.clear();
 457     key_deque.push_back("21");
 458     key_deque.push_back("22");
 459     validate_prefix(tmp_it, prefix2, key_deque);
 460     ASSERT_FALSE(HasFatalFailure());
 461
 462     ASSERT_TRUE(tmp_it->valid());
 463     key_deque.clear();
 464     key_deque.push_back("31");
 465     key_deque.push_back("32");
 466     validate_prefix(tmp_it, prefix3, key_deque);
 467     ASSERT_FALSE(HasFatalFailure());
 468
 469     ASSERT_FALSE(tmp_it->valid());
 470   }
 471 };
 472
 473 TEST_F(RmKeysTest, RmKeysByPrefixLevelDB)
 474 {
 475   SCOPED_TRACE("LevelDB");
 476   RmKeysByPrefix(db.get());
 477   ASSERT_FALSE(HasFatalFailure());
 478 }
 479
 480 TEST_F(RmKeysTest, RmKeysByPrefixMockDB)
 481 {
 482   SCOPED_TRACE("Mock DB");
 483   RmKeysByPrefix(mock.get());
 484   ASSERT_FALSE(HasFatalFailure());
 485 }
 486
 487 /**
 488  * If you refer to function RmKeysTest::RmKeysWhileIteratingSnapshot(),
 489  * you will notice that we seek the iterator to the first key, and then
 490  * we go on to remove several keys from the underlying store, including
 491  * the first couple keys.
 492  *
 493  * We would expect that during this test, as soon as we removed the keys
 494  * from the store, the iterator would get invalid, or cause some sort of
 495  * unexpected mess.
 496  *
 497  * Instead, the current version of leveldb handles it perfectly, by making
 498  * the iterator to use a snapshot instead of the store's real state. This
 499  * way, LevelDBStore's whole-space iterator will behave much like its own
 500  * whole-space snapshot iterator.
 501  *
 502  * However, this particular behavior of the iterator hasn't been documented
 503  * on leveldb, and we should assume that it can be changed at any point in
 504  * time.
 505  *
 506  * Therefore, we keep this test, being exactly the same as the one for the
 507  * whole-space snapshot iterator, as we currently assume they should behave
 508  * identically. If this test fails, at some point, and the whole-space
 509  * snapshot iterator passes, then it probably means that leveldb changed
 510  * how its iterator behaves.
 511  */
 512 TEST_F(RmKeysTest, RmKeysWhileIteratingLevelDB)
 513 {
 514   SCOPED_TRACE("LevelDB -- WholeSpaceIterator");
 515   RmKeysWhileIteratingSnapshot(db.get(), db->get_wholespace_iterator());
 516   ASSERT_FALSE(HasFatalFailure());
 517 }
 518
 519 TEST_F(RmKeysTest, RmKeysWhileIteratingMockDB)
 520 {
 521   std::cout << "There is no safe way to test key removal while iterating\n"
 522             << "over the mock store without using snapshots" << std::endl;
 523 }
 524
 525 // ------- Set Keys / Update Values -------
 526 class SetKeysTest : public IteratorTest
 527 {
 528 public:
 529   string prefix1;
 530   string prefix2;
 531
 532   void init(KeyValueDB *db) {
 533     KeyValueDB::Transaction tx = db->get_transaction();
 534
 535     tx->set(prefix1, "aaa", _gen_val("aaa"));
 536     tx->set(prefix1, "ccc", _gen_val("ccc"));
 537     tx->set(prefix1, "eee", _gen_val("eee"));
 538     tx->set(prefix2, "vvv", _gen_val("vvv"));
 539     tx->set(prefix2, "xxx", _gen_val("xxx"));
 540     tx->set(prefix2, "zzz", _gen_val("zzz"));
 541
 542     db->submit_transaction_sync(tx);
 543   }
 544
 545   void SetUp() override {
 546     IteratorTest::SetUp();
 547
 548     prefix1 = "_PREFIX_1_";
 549     prefix2 = "_PREFIX_2_";
 550
 551     clear(db.get());
 552     ASSERT_TRUE(validate_db_clear(db.get()));
 553     clear(mock.get());
 554     ASSERT_TRUE(validate_db_match());
 555
 556     init(db.get());
 557     init(mock.get());
 558
 559     ASSERT_TRUE(validate_db_match());
 560   }
 561
 562   void TearDown() override {
 563     IteratorTest::TearDown();
 564   }
 565
 566   /**
 567    * Make sure that the iterator picks on new keys added if it hasn't yet
 568    * iterated away from that position.
 569    *
 570    * This should only happen for the whole-space iterator when not using
 571    * the snapshot version.
 572    *
 573    * We don't need to test the validity of all elements, but we do test
 574    * inserting while moving from the first element to the last, using next()
 575    * to move forward, and then we test the same behavior while iterating
 576    * from the last element to the first, using prev() to move backwards.
 577    */
 578   void SetKeysWhileIterating(KeyValueDB *store,
 579                              KeyValueDB::WholeSpaceIterator iter) {
 580     iter->seek_to_first();
 581     ASSERT_TRUE(iter->valid());
 582     ASSERT_TRUE(validate_iterator(iter, prefix1, "aaa",
 583                 _gen_val_str("aaa")));
 584     iter->next();
 585     ASSERT_TRUE(iter->valid());
 586     ASSERT_TRUE(validate_iterator(iter, prefix1, "ccc",
 587                 _bl_to_str(_gen_val("ccc"))));
 588
 589     // insert new key 'ddd' after 'ccc' and before 'eee'
 590     KeyValueDB::Transaction tx = store->get_transaction();
 591     tx->set(prefix1, "ddd", _gen_val("ddd"));
 592     store->submit_transaction_sync(tx);
 593
 594     iter->next();
 595     ASSERT_TRUE(iter->valid());
 596     ASSERT_TRUE(validate_iterator(iter, prefix1, "ddd",
 597                 _gen_val_str("ddd")));
 598
 599     iter->seek_to_last();
 600     ASSERT_TRUE(iter->valid());
 601     tx = store->get_transaction();
 602     tx->set(prefix2, "yyy", _gen_val("yyy"));
 603     store->submit_transaction_sync(tx);
 604
 605     iter->prev();
 606     ASSERT_TRUE(iter->valid());
 607     ASSERT_TRUE(validate_iterator(iter, prefix2,
 608                                   "yyy", _gen_val_str("yyy")));
 609   }
 610
 611   /**
 612    * Make sure that the whole-space snapshot iterator does not pick on new keys
 613    * added to the store since we created the iterator, thus guaranteeing
 614    * read-consistency.
 615    *
 616    * We don't need to test the validity of all elements, but we do test
 617    * inserting while moving from the first element to the last, using next()
 618    * to move forward, and then we test the same behavior while iterating
 619    * from the last element to the first, using prev() to move backwards.
 620    */
 621   void SetKeysWhileIteratingSnapshot(KeyValueDB *store,
 622                                      KeyValueDB::WholeSpaceIterator iter) {
 623     iter->seek_to_first();
 624     ASSERT_TRUE(iter->valid());
 625     ASSERT_TRUE(validate_iterator(iter, prefix1, "aaa",
 626                 _gen_val_str("aaa")));
 627     iter->next();
 628     ASSERT_TRUE(iter->valid());
 629     ASSERT_TRUE(validate_iterator(iter, prefix1, "ccc",
 630                 _bl_to_str(_gen_val("ccc"))));
 631
 632     // insert new key 'ddd' after 'ccc' and before 'eee'
 633     KeyValueDB::Transaction tx = store->get_transaction();
 634     tx->set(prefix1, "ddd", _gen_val("ddd"));
 635     store->submit_transaction_sync(tx);
 636
 637     iter->next();
 638     ASSERT_TRUE(iter->valid());
 639     ASSERT_TRUE(validate_iterator(iter, prefix1, "eee",
 640                 _gen_val_str("eee")));
 641
 642     iter->seek_to_last();
 643     ASSERT_TRUE(iter->valid());
 644     tx = store->get_transaction();
 645     tx->set(prefix2, "yyy", _gen_val("yyy"));
 646     store->submit_transaction_sync(tx);
 647
 648     iter->prev();
 649     ASSERT_TRUE(iter->valid());
 650     ASSERT_TRUE(validate_iterator(iter, prefix2,
 651                                   "xxx", _gen_val_str("xxx")));
 652   }
 653
 654   /**
 655    * Make sure that the whole-space iterator is able to read values changed on
 656    * the store, even after we moved to the updated position.
 657    *
 658    * This should only be possible when not using the whole-space snapshot
 659    * version of the iterator.
 660    */
 661   void UpdateValuesWhileIterating(KeyValueDB *store,
 662                                   KeyValueDB::WholeSpaceIterator iter) {
 663     iter->seek_to_first();
 664     ASSERT_TRUE(iter->valid());
 665     ASSERT_TRUE(validate_iterator(iter, prefix1,
 666                                   "aaa", _gen_val_str("aaa")));
 667
 668     KeyValueDB::Transaction tx = store->get_transaction();
 669     tx->set(prefix1, "aaa", _gen_val("aaa_1"));
 670     store->submit_transaction_sync(tx);
 671
 672     ASSERT_TRUE(validate_iterator(iter, prefix1,
 673                                   "aaa", _gen_val_str("aaa_1")));
 674
 675     iter->seek_to_last();
 676     ASSERT_TRUE(iter->valid());
 677     ASSERT_TRUE(validate_iterator(iter, prefix2,
 678                                   "zzz", _gen_val_str("zzz")));
 679
 680     tx = store->get_transaction();
 681     tx->set(prefix2, "zzz", _gen_val("zzz_1"));
 682     store->submit_transaction_sync(tx);
 683
 684     ASSERT_TRUE(validate_iterator(iter, prefix2,
 685                                   "zzz", _gen_val_str("zzz_1")));
 686   }
 687
 688   /**
 689    * Make sure that the whole-space iterator is able to read values changed on
 690    * the store, even after we moved to the updated position.
 691    *
 692    * This should only be possible when not using the whole-space snapshot
 693    * version of the iterator.
 694    */
 695   void UpdateValuesWhileIteratingSnapshot(
 696                                   KeyValueDB *store,
 697                                   KeyValueDB::WholeSpaceIterator iter) {
 698     iter->seek_to_first();
 699     ASSERT_TRUE(iter->valid());
 700     ASSERT_TRUE(validate_iterator(iter, prefix1,
 701                                   "aaa", _gen_val_str("aaa")));
 702
 703     KeyValueDB::Transaction tx = store->get_transaction();
 704     tx->set(prefix1, "aaa", _gen_val("aaa_1"));
 705     store->submit_transaction_sync(tx);
 706
 707     ASSERT_TRUE(validate_iterator(iter, prefix1,
 708                                   "aaa", _gen_val_str("aaa")));
 709
 710     iter->seek_to_last();
 711     ASSERT_TRUE(iter->valid());
 712     ASSERT_TRUE(validate_iterator(iter, prefix2,
 713                                   "zzz", _gen_val_str("zzz")));
 714
 715     tx = store->get_transaction();
 716     tx->set(prefix2, "zzz", _gen_val("zzz_1"));
 717     store->submit_transaction_sync(tx);
 718
 719     ASSERT_TRUE(validate_iterator(iter, prefix2,
 720                                   "zzz", _gen_val_str("zzz")));
 721
 722     // check those values were really changed in the store
 723     KeyValueDB::WholeSpaceIterator tmp_iter = store->get_wholespace_iterator();
 724     tmp_iter->seek_to_first();
 725     ASSERT_TRUE(tmp_iter->valid());
 726     ASSERT_TRUE(validate_iterator(tmp_iter, prefix1,
 727                                   "aaa", _gen_val_str("aaa_1")));
 728     tmp_iter->seek_to_last();
 729     ASSERT_TRUE(tmp_iter->valid());
 730     ASSERT_TRUE(validate_iterator(tmp_iter, prefix2,
 731                                   "zzz", _gen_val_str("zzz_1")));
 732   }
 733
 734
 735 };
 736
 737 TEST_F(SetKeysTest, DISABLED_SetKeysWhileIteratingLevelDB)
 738 {
 739   SCOPED_TRACE("LevelDB: SetKeysWhileIteratingLevelDB");
 740   SetKeysWhileIterating(db.get(), db->get_wholespace_iterator());
 741   ASSERT_TRUE(HasFatalFailure());
 742 }
 743
 744 TEST_F(SetKeysTest, SetKeysWhileIteratingMockDB)
 745 {
 746   SCOPED_TRACE("Mock DB: SetKeysWhileIteratingMockDB");
 747   SetKeysWhileIterating(mock.get(), mock->get_wholespace_iterator());
 748   ASSERT_FALSE(HasFatalFailure());
 749 }
 750
 751 TEST_F(SetKeysTest, DISABLED_UpdateValuesWhileIteratingLevelDB)
 752 {
 753   SCOPED_TRACE("LevelDB: UpdateValuesWhileIteratingLevelDB");
 754   UpdateValuesWhileIterating(db.get(), db->get_wholespace_iterator());
 755   ASSERT_FALSE(HasFatalFailure());
 756 }
 757
 758 TEST_F(SetKeysTest, UpdateValuesWhileIteratingMockDB)
 759 {
 760   SCOPED_TRACE("MockDB: UpdateValuesWhileIteratingMockDB");
 761   UpdateValuesWhileIterating(mock.get(), mock->get_wholespace_iterator());
 762   ASSERT_FALSE(HasFatalFailure());
 763 }
 764
 765 class BoundsTest : public IteratorTest
 766 {
 767 public:
 768   string prefix1;
 769   string prefix2;
 770   string prefix3;
 771
 772   void init(KeyValueDB *store) {
 773     KeyValueDB::Transaction tx = store->get_transaction();
 774
 775     tx->set(prefix1, "aaa", _gen_val("aaa"));
 776     tx->set(prefix1, "ccc", _gen_val("ccc"));
 777     tx->set(prefix1, "eee", _gen_val("eee"));
 778     tx->set(prefix2, "vvv", _gen_val("vvv"));
 779     tx->set(prefix2, "xxx", _gen_val("xxx"));
 780     tx->set(prefix2, "zzz", _gen_val("zzz"));
 781     tx->set(prefix3, "aaa", _gen_val("aaa"));
 782     tx->set(prefix3, "mmm", _gen_val("mmm"));
 783     tx->set(prefix3, "yyy", _gen_val("yyy"));
 784
 785     store->submit_transaction_sync(tx);
 786   }
 787
 788   void SetUp() override {
 789     IteratorTest::SetUp();
 790
 791     prefix1 = "_PREFIX_1_";
 792     prefix2 = "_PREFIX_2_";
 793     prefix3 = "_PREFIX_4_";
 794
 795     clear(db.get());
 796     ASSERT_TRUE(validate_db_clear(db.get()));
 797     clear(mock.get());
 798     ASSERT_TRUE(validate_db_match());
 799
 800     init(db.get());
 801     init(mock.get());
 802
 803     ASSERT_TRUE(validate_db_match());
 804   }
 805
 806   void TearDown() override {
 807     IteratorTest::TearDown();
 808   }
 809
 810   void LowerBoundWithEmptyKeyOnWholeSpaceIterator(
 811                             KeyValueDB::WholeSpaceIterator iter) {
 812     deque<string> key_deque;
 813     // see what happens when we have an empty key and try to get to the
 814     // first available prefix
 815     iter->lower_bound(prefix1, "");
 816     ASSERT_TRUE(iter->valid());
 817
 818     key_deque.push_back("aaa");
 819     key_deque.push_back("ccc");
 820     key_deque.push_back("eee");
 821     validate_prefix(iter, prefix1, key_deque);
 822     ASSERT_FALSE(HasFatalFailure());
 823     ASSERT_TRUE(iter->valid());
 824     // if we got here without problems, then it is safe to assume the
 825     // remaining prefixes are intact.
 826
 827     // see what happens when we have an empty key and try to get to the
 828     // middle of the key-space
 829     iter->lower_bound(prefix2, "");
 830     ASSERT_TRUE(iter->valid());
 831     key_deque.clear();
 832
 833     key_deque.push_back("vvv");
 834     key_deque.push_back("xxx");
 835     key_deque.push_back("zzz");
 836     validate_prefix(iter, prefix2, key_deque);
 837     ASSERT_FALSE(HasFatalFailure());
 838     ASSERT_TRUE(iter->valid());
 839     // if we got here without problems, then it is safe to assume the
 840     // remaining prefixes are intact.
 841
 842     // see what happens when we have an empty key and try to get to the
 843     // last prefix on the key-space
 844     iter->lower_bound(prefix3, "");
 845     ASSERT_TRUE(iter->valid());
 846     key_deque.clear();
 847
 848     key_deque.push_back("aaa");
 849     key_deque.push_back("mmm");
 850     key_deque.push_back("yyy");
 851     validate_prefix(iter, prefix3, key_deque);
 852     ASSERT_FALSE(HasFatalFailure());
 853     ASSERT_FALSE(iter->valid());
 854     // we reached the end of the key_space, so the iterator should no longer
 855     // be valid
 856
 857     // see what happens when we look for an inexistent prefix, that will
 858     // compare higher than the existing prefixes, with an empty key
 859     // expected: reach the store's end; iterator becomes invalid
 860     iter->lower_bound("_PREFIX_9_", "");
 861     ASSERT_FALSE(iter->valid());
 862
 863     // see what happens when we look for an inexistent prefix, that will
 864     // compare lower than the existing prefixes, with an empty key
 865     // expected: find the first prefix; iterator is valid
 866     iter->lower_bound("_PREFIX_0_", "");
 867     ASSERT_TRUE(iter->valid());
 868     key_deque.clear();
 869     key_deque.push_back("aaa");
 870     key_deque.push_back("ccc");
 871     key_deque.push_back("eee");
 872     validate_prefix(iter, prefix1, key_deque);
 873     ASSERT_FALSE(HasFatalFailure());
 874     ASSERT_TRUE(iter->valid());
 875
 876     // see what happens when we look for an empty prefix (that should compare
 877     // lower than any existing prefixes)
 878     // expected: find the first prefix; iterator is valid
 879     iter->lower_bound("", "");
 880     ASSERT_TRUE(iter->valid());
 881     key_deque.push_back("aaa");
 882     key_deque.push_back("ccc");
 883     key_deque.push_back("eee");
 884     validate_prefix(iter, prefix1, key_deque);
 885     ASSERT_FALSE(HasFatalFailure());
 886     ASSERT_TRUE(iter->valid());
 887   }
 888
 889   void LowerBoundWithEmptyPrefixOnWholeSpaceIterator(
 890                           KeyValueDB::WholeSpaceIterator iter) {
 891     deque<string> key_deque;
 892     // check for an empty prefix, with key 'aaa'. Since this key is shared
 893     // among two different prefixes, it is relevant to check which will be
 894     // found first.
 895     // expected: find key (prefix1, aaa); iterator is valid
 896     iter->lower_bound("", "aaa");
 897     ASSERT_TRUE(iter->valid());
 898
 899     key_deque.push_back("aaa");
 900     key_deque.push_back("ccc");
 901     key_deque.push_back("eee");
 902     validate_prefix(iter, prefix1, key_deque);
 903     ASSERT_FALSE(HasFatalFailure());
 904     ASSERT_TRUE(iter->valid());
 905     // since we found prefix1, it is safe to assume that the remaining
 906     // prefixes (prefix2 and prefix3) will follow
 907
 908     // any lower_bound operation with an empty prefix should always put the
 909     // iterator in the first key in the key-space, despite what key is
 910     // specified. This means that looking for ("","AAAAAAAAAA") should
 911     // also position the iterator on (prefix1, aaa).
 912     // expected: find key (prefix1, aaa); iterator is valid
 913     iter->lower_bound("", "AAAAAAAAAA");
 914     ASSERT_TRUE(iter->valid());
 915     key_deque.clear();
 916     key_deque.push_back("aaa");
 917     key_deque.push_back("ccc");
 918     key_deque.push_back("eee");
 919     validate_prefix(iter, prefix1, key_deque);
 920     ASSERT_FALSE(HasFatalFailure());
 921     ASSERT_TRUE(iter->valid());
 922
 923     // note: this test is a duplicate of the one in the function above. Why?
 924     // Well, because it also fits here (being its prefix empty), and one could
 925     // very well run solely this test (instead of the whole battery) and would
 926     // certainly expect this case to be tested.
 927
 928     // see what happens when we look for an empty prefix (that should compare
 929     // lower than any existing prefixes)
 930     // expected: find the first prefix; iterator is valid
 931     iter->lower_bound("", "");
 932     ASSERT_TRUE(iter->valid());
 933     key_deque.push_back("aaa");
 934     key_deque.push_back("ccc");
 935     key_deque.push_back("eee");
 936     validate_prefix(iter, prefix1, key_deque);
 937     ASSERT_FALSE(HasFatalFailure());
 938     ASSERT_TRUE(iter->valid());
 939   }
 940
 941   void LowerBoundOnWholeSpaceIterator(
 942                           KeyValueDB::WholeSpaceIterator iter) {
 943     deque<string> key_deque;
 944     // check that we find the first key in the store
 945     // expected: find (prefix1, aaa); iterator is valid
 946     iter->lower_bound(prefix1, "aaa");
 947     ASSERT_TRUE(iter->valid());
 948     key_deque.push_back("aaa");
 949     validate_prefix(iter, prefix1, key_deque);
 950     ASSERT_FALSE(HasFatalFailure());
 951     ASSERT_TRUE(iter->valid());
 952
 953     // check that we find the last key in the store
 954     // expected: find (prefix3, yyy); iterator is valid
 955     iter->lower_bound(prefix3, "yyy");
 956     ASSERT_TRUE(iter->valid());
 957     key_deque.clear();
 958     key_deque.push_back("yyy");
 959     validate_prefix(iter, prefix3, key_deque);
 960     ASSERT_FALSE(HasFatalFailure());
 961     ASSERT_FALSE(iter->valid());
 962
 963     // check that looking for non-existent prefix '_PREFIX_0_' will
 964     // always result in the first value of prefix1 (prefix1,"aaa")
 965     // expected: find (prefix1, aaa); iterator is valid
 966     iter->lower_bound("_PREFIX_0_", "AAAAA");
 967     ASSERT_TRUE(iter->valid());
 968     key_deque.clear();
 969     key_deque.push_back("aaa");
 970     validate_prefix(iter, prefix1, key_deque);
 971     ASSERT_FALSE(HasFatalFailure());
 972     ASSERT_TRUE(iter->valid());
 973
 974     // check that looking for non-existent prefix '_PREFIX_3_' will
 975     // always result in the first value of prefix3 (prefix4,"aaa")
 976     // expected: find (prefix3, aaa); iterator is valid
 977     iter->lower_bound("_PREFIX_3_", "AAAAA");
 978     ASSERT_TRUE(iter->valid());
 979     key_deque.clear();
 980     key_deque.push_back("aaa");
 981     validate_prefix(iter, prefix3, key_deque);
 982     ASSERT_FALSE(HasFatalFailure());
 983     ASSERT_TRUE(iter->valid());
 984
 985     // check that looking for non-existent prefix '_PREFIX_9_' will
 986     // always result in an invalid iterator.
 987     // expected: iterator is invalid
 988     iter->lower_bound("_PREFIX_9_", "AAAAA");
 989     ASSERT_FALSE(iter->valid());
 990   }
 991
 992   void UpperBoundWithEmptyKeyOnWholeSpaceIterator(
 993                           KeyValueDB::WholeSpaceIterator iter) {
 994     deque<string> key_deque;
 995     // check that looking for (prefix1, "") will result in finding
 996     // the first key in prefix1 (prefix1, "aaa")
 997     // expected: find (prefix1, aaa); iterator is valid
 998     iter->upper_bound(prefix1, "");
 999     key_deque.push_back("aaa");
1000     validate_prefix(iter, prefix1, key_deque);
1001     ASSERT_FALSE(HasFatalFailure());
1002     ASSERT_TRUE(iter->valid());
1003
1004     // check that looking for (prefix2, "") will result in finding
1005     // the first key in prefix2 (prefix2, vvv)
1006     // expected: find (prefix2, aaa); iterator is valid
1007     iter->upper_bound(prefix2, "");
1008     key_deque.push_back("vvv");
1009     validate_prefix(iter, prefix2, key_deque);
1010     ASSERT_FALSE(HasFatalFailure());
1011     ASSERT_TRUE(iter->valid());
1012
1013
1014     // check that looking for (prefix3, "") will result in finding
1015     // the first key in prefix3 (prefix3, aaa)
1016     // expected: find (prefix3, aaa); iterator is valid
1017     iter->upper_bound(prefix3, "");
1018     key_deque.push_back("aaa");
1019     validate_prefix(iter, prefix3, key_deque);
1020     ASSERT_FALSE(HasFatalFailure());
1021     ASSERT_TRUE(iter->valid());
1022
1023     // see what happens when we look for an inexistent prefix, that will
1024     // compare higher than the existing prefixes, with an empty key
1025     // expected: reach the store's end; iterator becomes invalid
1026     iter->upper_bound("_PREFIX_9_", "");
1027     ASSERT_FALSE(iter->valid());
1028
1029     // see what happens when we look for an inexistent prefix, that will
1030     // compare lower than the existing prefixes, with an empty key
1031     // expected: find the first prefix; iterator is valid
1032     iter->upper_bound("_PREFIX_0_", "");
1033     ASSERT_TRUE(iter->valid());
1034     key_deque.clear();
1035     key_deque.push_back("aaa");
1036     validate_prefix(iter, prefix1, key_deque);
1037     ASSERT_FALSE(HasFatalFailure());
1038     ASSERT_TRUE(iter->valid());
1039
1040     // see what happens when we look for an empty prefix (that should compare
1041     // lower than any existing prefixes)
1042     // expected: find the first prefix; iterator is valid
1043     iter->upper_bound("", "");
1044     ASSERT_TRUE(iter->valid());
1045     key_deque.push_back("aaa");
1046     validate_prefix(iter, prefix1, key_deque);
1047     ASSERT_FALSE(HasFatalFailure());
1048     ASSERT_TRUE(iter->valid());
1049   }
1050
1051   void UpperBoundWithEmptyPrefixOnWholeSpaceIterator(
1052                           KeyValueDB::WholeSpaceIterator iter) {
1053     deque<string> key_deque;
1054     // check for an empty prefix, with key 'aaa'. Since this key is shared
1055     // among two different prefixes, it is relevant to check which will be
1056     // found first.
1057     // expected: find key (prefix1, aaa); iterator is valid
1058     iter->upper_bound("", "aaa");
1059     ASSERT_TRUE(iter->valid());
1060     key_deque.push_back("aaa");
1061     key_deque.push_back("ccc");
1062     key_deque.push_back("eee");
1063     validate_prefix(iter, prefix1, key_deque);
1064     ASSERT_FALSE(HasFatalFailure());
1065     ASSERT_TRUE(iter->valid());
1066
1067     // any upper_bound operation with an empty prefix should always put the
1068     // iterator in the first key whose prefix compares greater, despite the
1069     // key that is specified. This means that looking for ("","AAAAAAAAAA")
1070     // should position the iterator on (prefix1, aaa).
1071     // expected: find key (prefix1, aaa); iterator is valid
1072     iter->upper_bound("", "AAAAAAAAAA");
1073     ASSERT_TRUE(iter->valid());
1074     key_deque.clear();
1075     key_deque.push_back("aaa");
1076     validate_prefix(iter, prefix1, key_deque);
1077     ASSERT_FALSE(HasFatalFailure());
1078     ASSERT_TRUE(iter->valid());
1079
1080     // note: this test is a duplicate of the one in the function above. Why?
1081     // Well, because it also fits here (being its prefix empty), and one could
1082     // very well run solely this test (instead of the whole battery) and would
1083     // certainly expect this case to be tested.
1084
1085     // see what happens when we look for an empty prefix (that should compare
1086     // lower than any existing prefixes)
1087     // expected: find the first prefix; iterator is valid
1088     iter->upper_bound("", "");
1089     ASSERT_TRUE(iter->valid());
1090     key_deque.push_back("aaa");
1091     validate_prefix(iter, prefix1, key_deque);
1092     ASSERT_FALSE(HasFatalFailure());
1093     ASSERT_TRUE(iter->valid());
1094   }
1095
1096   void UpperBoundOnWholeSpaceIterator(
1097                           KeyValueDB::WholeSpaceIterator iter) {
1098     deque<string> key_deque;
1099     // check that we find the second key in the store
1100     // expected: find (prefix1, ccc); iterator is valid
1101     iter->upper_bound(prefix1, "bbb");
1102     ASSERT_TRUE(iter->valid());
1103     key_deque.push_back("ccc");
1104     validate_prefix(iter, prefix1, key_deque);
1105     ASSERT_FALSE(HasFatalFailure());
1106     ASSERT_TRUE(iter->valid());
1107
1108     // check that we find the last key in the store
1109     // expected: find (prefix3, yyy); iterator is valid
1110     iter->upper_bound(prefix3, "xxx");
1111     ASSERT_TRUE(iter->valid());
1112     key_deque.clear();
1113     key_deque.push_back("yyy");
1114     validate_prefix(iter, prefix3, key_deque);
1115     ASSERT_FALSE(HasFatalFailure());
1116     ASSERT_FALSE(iter->valid());
1117
1118     // check that looking for non-existent prefix '_PREFIX_0_' will
1119     // always result in the first value of prefix1 (prefix1,"aaa")
1120     // expected: find (prefix1, aaa); iterator is valid
1121     iter->upper_bound("_PREFIX_0_", "AAAAA");
1122     ASSERT_TRUE(iter->valid());
1123     key_deque.clear();
1124     key_deque.push_back("aaa");
1125     validate_prefix(iter, prefix1, key_deque);
1126     ASSERT_FALSE(HasFatalFailure());
1127     ASSERT_TRUE(iter->valid());
1128
1129     // check that looking for non-existent prefix '_PREFIX_3_' will
1130     // always result in the first value of prefix3 (prefix3,"aaa")
1131     // expected: find (prefix3, aaa); iterator is valid
1132     iter->upper_bound("_PREFIX_3_", "AAAAA");
1133     ASSERT_TRUE(iter->valid());
1134     key_deque.clear();
1135     key_deque.push_back("aaa");
1136     validate_prefix(iter, prefix3, key_deque);
1137     ASSERT_FALSE(HasFatalFailure());
1138     ASSERT_TRUE(iter->valid());
1139
1140     // check that looking for non-existent prefix '_PREFIX_9_' will
1141     // always result in an invalid iterator.
1142     // expected: iterator is invalid
1143     iter->upper_bound("_PREFIX_9_", "AAAAA");
1144     ASSERT_FALSE(iter->valid());
1145   }
1146 };
1147
1148 TEST_F(BoundsTest, LowerBoundWithEmptyKeyOnWholeSpaceIteratorLevelDB)
1149 {
1150   SCOPED_TRACE("LevelDB: Lower Bound, Empty Key, Whole-Space Iterator");
1151   LowerBoundWithEmptyKeyOnWholeSpaceIterator(db->get_wholespace_iterator());
1152   ASSERT_FALSE(HasFatalFailure());
1153 }
1154
1155 TEST_F(BoundsTest, LowerBoundWithEmptyKeyOnWholeSpaceIteratorMockDB)
1156 {
1157   SCOPED_TRACE("MockDB: Lower Bound, Empty Key, Whole-Space Iterator");
1158   LowerBoundWithEmptyKeyOnWholeSpaceIterator(mock->get_wholespace_iterator());
1159   ASSERT_FALSE(HasFatalFailure());
1160 }
1161
1162 TEST_F(BoundsTest, LowerBoundWithEmptyPrefixOnWholeSpaceIteratorLevelDB)
1163 {
1164   SCOPED_TRACE("LevelDB: Lower Bound, Empty Prefix, Whole-Space Iterator");
1165   LowerBoundWithEmptyPrefixOnWholeSpaceIterator(db->get_wholespace_iterator());
1166   ASSERT_FALSE(HasFatalFailure());
1167 }
1168
1169 TEST_F(BoundsTest, LowerBoundWithEmptyPrefixOnWholeSpaceIteratorMockDB)
1170 {
1171   SCOPED_TRACE("MockDB: Lower Bound, Empty Prefix, Whole-Space Iterator");
1172   LowerBoundWithEmptyPrefixOnWholeSpaceIterator(mock->get_wholespace_iterator());
1173   ASSERT_FALSE(HasFatalFailure());
1174 }
1175
1176 TEST_F(BoundsTest, LowerBoundOnWholeSpaceIteratorLevelDB)
1177 {
1178   SCOPED_TRACE("LevelDB: Lower Bound, Whole-Space Iterator");
1179   LowerBoundOnWholeSpaceIterator(db->get_wholespace_iterator());
1180   ASSERT_FALSE(HasFatalFailure());
1181 }
1182
1183 TEST_F(BoundsTest, LowerBoundOnWholeSpaceIteratorMockDB)
1184 {
1185   SCOPED_TRACE("MockDB: Lower Bound, Whole-Space Iterator");
1186   LowerBoundOnWholeSpaceIterator(mock->get_wholespace_iterator());
1187   ASSERT_FALSE(HasFatalFailure());
1188 }
1189
1190 TEST_F(BoundsTest, UpperBoundWithEmptyKeyOnWholeSpaceIteratorLevelDB)
1191 {
1192   SCOPED_TRACE("LevelDB: Upper Bound, Empty Key, Whole-Space Iterator");
1193   UpperBoundWithEmptyKeyOnWholeSpaceIterator(db->get_wholespace_iterator());
1194   ASSERT_FALSE(HasFatalFailure());
1195 }
1196
1197 TEST_F(BoundsTest, UpperBoundWithEmptyKeyOnWholeSpaceIteratorMockDB)
1198 {
1199   SCOPED_TRACE("MockDB: Upper Bound, Empty Key, Whole-Space Iterator");
1200   UpperBoundWithEmptyKeyOnWholeSpaceIterator(mock->get_wholespace_iterator());
1201   ASSERT_FALSE(HasFatalFailure());
1202 }
1203
1204 TEST_F(BoundsTest, UpperBoundWithEmptyPrefixOnWholeSpaceIteratorLevelDB)
1205 {
1206   SCOPED_TRACE("LevelDB: Upper Bound, Empty Prefix, Whole-Space Iterator");
1207   UpperBoundWithEmptyPrefixOnWholeSpaceIterator(db->get_wholespace_iterator());
1208   ASSERT_FALSE(HasFatalFailure());
1209 }
1210
1211 TEST_F(BoundsTest, UpperBoundWithEmptyPrefixOnWholeSpaceIteratorMockDB)
1212 {
1213   SCOPED_TRACE("MockDB: Upper Bound, Empty Prefix, Whole-Space Iterator");
1214   UpperBoundWithEmptyPrefixOnWholeSpaceIterator(mock->get_wholespace_iterator());
1215   ASSERT_FALSE(HasFatalFailure());
1216 }
1217
1218 TEST_F(BoundsTest, UpperBoundOnWholeSpaceIteratorLevelDB)
1219 {
1220   SCOPED_TRACE("LevelDB: Upper Bound, Whole-Space Iterator");
1221   UpperBoundOnWholeSpaceIterator(db->get_wholespace_iterator());
1222   ASSERT_FALSE(HasFatalFailure());
1223 }
1224
1225 TEST_F(BoundsTest, UpperBoundOnWholeSpaceIteratorMockDB)
1226 {
1227   SCOPED_TRACE("MockDB: Upper Bound, Whole-Space Iterator");
1228   UpperBoundOnWholeSpaceIterator(mock->get_wholespace_iterator());
1229   ASSERT_FALSE(HasFatalFailure());
1230 }
1231
1232
1233 class SeeksTest : public IteratorTest
1234 {
1235 public:
1236   string prefix0;
1237   string prefix1;
1238   string prefix2;
1239   string prefix3;
1240   string prefix4;
1241   string prefix5;
1242
1243   void init(KeyValueDB *store) {
1244     KeyValueDB::Transaction tx = store->get_transaction();
1245
1246     tx->set(prefix1, "aaa", _gen_val("aaa"));
1247     tx->set(prefix1, "ccc", _gen_val("ccc"));
1248     tx->set(prefix1, "eee", _gen_val("eee"));
1249     tx->set(prefix2, "vvv", _gen_val("vvv"));
1250     tx->set(prefix2, "xxx", _gen_val("xxx"));
1251     tx->set(prefix2, "zzz", _gen_val("zzz"));
1252     tx->set(prefix4, "aaa", _gen_val("aaa"));
1253     tx->set(prefix4, "mmm", _gen_val("mmm"));
1254     tx->set(prefix4, "yyy", _gen_val("yyy"));
1255
1256     store->submit_transaction_sync(tx);
1257   }
1258
1259   void SetUp() override {
1260     IteratorTest::SetUp();
1261
1262     prefix0 = "_PREFIX_0_";
1263     prefix1 = "_PREFIX_1_";
1264     prefix2 = "_PREFIX_2_";
1265     prefix3 = "_PREFIX_3_";
1266     prefix4 = "_PREFIX_4_";
1267     prefix5 = "_PREFIX_5_";
1268
1269     clear(db.get());
1270     ASSERT_TRUE(validate_db_clear(db.get()));
1271     clear(mock.get());
1272     ASSERT_TRUE(validate_db_match());
1273
1274     init(db.get());
1275     init(mock.get());
1276
1277     ASSERT_TRUE(validate_db_match());
1278   }
1279
1280   void TearDown() override {
1281     IteratorTest::TearDown();
1282   }
1283
1284
1285   void SeekToFirstOnWholeSpaceIterator(
1286                           KeyValueDB::WholeSpaceIterator iter) {
1287     iter->seek_to_first();
1288     ASSERT_TRUE(iter->valid());
1289     deque<string> key_deque;
1290     key_deque.push_back("aaa");
1291     key_deque.push_back("ccc");
1292     key_deque.push_back("eee");
1293     validate_prefix(iter, prefix1, key_deque);
1294     ASSERT_FALSE(HasFatalFailure());
1295     ASSERT_TRUE(iter->valid());
1296   }
1297
1298   void SeekToFirstWithPrefixOnWholeSpaceIterator(
1299                           KeyValueDB::WholeSpaceIterator iter) {
1300     deque<string> key_deque;
1301
1302     // if the prefix is empty, we must end up seeking to the first key.
1303     // expected: seek to (prefix1, aaa); iterator is valid
1304     iter->seek_to_first("");
1305     ASSERT_TRUE(iter->valid());
1306     key_deque.push_back("aaa");
1307     validate_prefix(iter, prefix1, key_deque);
1308     ASSERT_FALSE(HasFatalFailure());
1309     ASSERT_TRUE(iter->valid());
1310
1311     // try seeking to non-existent prefix that compares lower than the
1312     // first available prefix
1313     // expected: seek to (prefix1, aaa); iterator is valid
1314     iter->seek_to_first(prefix0);
1315     ASSERT_TRUE(iter->valid());
1316     key_deque.clear();
1317     key_deque.push_back("aaa");
1318     validate_prefix(iter, prefix1, key_deque);
1319     ASSERT_FALSE(HasFatalFailure());
1320     ASSERT_TRUE(iter->valid());
1321
1322     // try seeking to non-existent prefix
1323     // expected: seek to (prefix4, aaa); iterator is valid
1324     iter->seek_to_first(prefix3);
1325     ASSERT_TRUE(iter->valid());
1326     key_deque.clear();
1327     key_deque.push_back("aaa");
1328     validate_prefix(iter, prefix4, key_deque);
1329     ASSERT_FALSE(HasFatalFailure());
1330     ASSERT_TRUE(iter->valid());
1331
1332     // try seeking to non-existent prefix that compares greater than the
1333     // last available prefix
1334     // expected: iterator is invalid
1335     iter->seek_to_first(prefix5);
1336     ASSERT_FALSE(iter->valid());
1337
1338     // try seeking to the first prefix and make sure we end up in its first
1339     // position
1340     // expected: seek to (prefix1,aaa); iterator is valid
1341     iter->seek_to_first(prefix1);
1342     ASSERT_TRUE(iter->valid());
1343     key_deque.clear();
1344     key_deque.push_back("aaa");
1345     validate_prefix(iter, prefix1, key_deque);
1346     ASSERT_FALSE(HasFatalFailure());
1347     ASSERT_TRUE(iter->valid());
1348
1349     // try seeking to the second prefix and make sure we end up in its
1350     // first position
1351     // expected: seek to (prefix2,vvv); iterator is valid
1352     iter->seek_to_first(prefix2);
1353     ASSERT_TRUE(iter->valid());
1354     key_deque.clear();
1355     key_deque.push_back("vvv");
1356     validate_prefix(iter, prefix2, key_deque);
1357     ASSERT_FALSE(HasFatalFailure());
1358     ASSERT_TRUE(iter->valid());
1359
1360     // try seeking to the last prefix and make sure we end up in its
1361     // first position
1362     // expected: seek to (prefix4,aaa); iterator is valid
1363     iter->seek_to_first(prefix4);
1364     ASSERT_TRUE(iter->valid());
1365     key_deque.clear();
1366     key_deque.push_back("aaa");
1367     validate_prefix(iter, prefix4, key_deque);
1368     ASSERT_FALSE(HasFatalFailure());
1369     ASSERT_TRUE(iter->valid());
1370   }
1371
1372   void SeekToLastOnWholeSpaceIterator(
1373                           KeyValueDB::WholeSpaceIterator iter) {
1374     deque<string> key_deque;
1375     iter->seek_to_last();
1376     key_deque.push_back("yyy");
1377     validate_prefix(iter, prefix4, key_deque);
1378     ASSERT_FALSE(HasFatalFailure());
1379     ASSERT_FALSE(iter->valid());
1380   }
1381
1382   void SeekToLastWithPrefixOnWholeSpaceIterator(
1383                           KeyValueDB::WholeSpaceIterator iter) {
1384     deque<string> key_deque;
1385
1386     // if the prefix is empty, we must end up seeking to last position
1387     // that has an empty prefix, or to the previous position to the first
1388     // position whose prefix compares higher than empty.
1389     // expected: iterator is invalid (because (prefix1,aaa) is the first
1390     //           position that compared higher than an empty prefix)
1391     iter->seek_to_last("");
1392     ASSERT_FALSE(iter->valid());
1393
1394     // try seeking to non-existent prefix that compares lower than the
1395     // first available prefix
1396     // expected: iterator is invalid (because (prefix1,aaa) is the first
1397     //           position that compared higher than prefix0)
1398     iter->seek_to_last(prefix0);
1399     ASSERT_FALSE(iter->valid());
1400
1401     // try seeking to non-existent prefix
1402     // expected: seek to (prefix2, zzz); iterator is valid
1403     iter->seek_to_last(prefix3);
1404     ASSERT_TRUE(iter->valid());
1405     key_deque.clear();
1406     key_deque.push_back("zzz");
1407     validate_prefix(iter, prefix2, key_deque);
1408     ASSERT_FALSE(HasFatalFailure());
1409     ASSERT_TRUE(iter->valid());
1410
1411     // try seeking to non-existent prefix that compares greater than the
1412     // last available prefix
1413     // expected: iterator is in the last position of the store;
1414     //           i.e., (prefix4,yyy)
1415     iter->seek_to_last(prefix5);
1416     ASSERT_TRUE(iter->valid());
1417     key_deque.clear();
1418     key_deque.push_back("yyy");
1419     validate_prefix(iter, prefix4, key_deque);
1420     ASSERT_FALSE(HasFatalFailure());
1421     ASSERT_FALSE(iter->valid());
1422
1423     // try seeking to the first prefix and make sure we end up in its last
1424     // position
1425     // expected: seek to (prefix1,eee); iterator is valid
1426     iter->seek_to_last(prefix1);
1427     ASSERT_TRUE(iter->valid());
1428     key_deque.clear();
1429     key_deque.push_back("eee");
1430     validate_prefix(iter, prefix1, key_deque);
1431     ASSERT_FALSE(HasFatalFailure());
1432     ASSERT_TRUE(iter->valid());
1433
1434     // try seeking to the second prefix and make sure we end up in its
1435     // last position
1436     // expected: seek to (prefix2,vvv); iterator is valid
1437     iter->seek_to_last(prefix2);
1438     ASSERT_TRUE(iter->valid());
1439     key_deque.clear();
1440     key_deque.push_back("zzz");
1441     validate_prefix(iter, prefix2, key_deque);
1442     ASSERT_FALSE(HasFatalFailure());
1443     ASSERT_TRUE(iter->valid());
1444
1445     // try seeking to the last prefix and make sure we end up in its
1446     // last position
1447     // expected: seek to (prefix4,aaa); iterator is valid
1448     iter->seek_to_last(prefix4);
1449     ASSERT_TRUE(iter->valid());
1450     key_deque.clear();
1451     key_deque.push_back("yyy");
1452     validate_prefix(iter, prefix4, key_deque);
1453     ASSERT_FALSE(HasFatalFailure());
1454     ASSERT_FALSE(iter->valid());
1455   }
1456 };
1457
1458 TEST_F(SeeksTest, SeekToFirstOnWholeSpaceIteratorLevelDB) {
1459   SCOPED_TRACE("LevelDB: Seek To First, Whole Space Iterator");
1460   SeekToFirstOnWholeSpaceIterator(db->get_wholespace_iterator());
1461   ASSERT_FALSE(HasFatalFailure());
1462 }
1463
1464 TEST_F(SeeksTest, SeekToFirstOnWholeSpaceIteratorMockDB) {
1465   SCOPED_TRACE("MockDB: Seek To First, Whole Space Iterator");
1466   SeekToFirstOnWholeSpaceIterator(mock->get_wholespace_iterator());
1467   ASSERT_FALSE(HasFatalFailure());
1468 }
1469
1470 TEST_F(SeeksTest, SeekToFirstWithPrefixOnWholeSpaceIteratorLevelDB) {
1471   SCOPED_TRACE("LevelDB: Seek To First, With Prefix, Whole Space Iterator");
1472   SeekToFirstWithPrefixOnWholeSpaceIterator(db->get_wholespace_iterator());
1473   ASSERT_FALSE(HasFatalFailure());
1474 }
1475
1476 TEST_F(SeeksTest, SeekToFirstWithPrefixOnWholeSpaceIteratorMockDB) {
1477   SCOPED_TRACE("MockDB: Seek To First, With Prefix, Whole Space Iterator");
1478   SeekToFirstWithPrefixOnWholeSpaceIterator(mock->get_wholespace_iterator());
1479   ASSERT_FALSE(HasFatalFailure());
1480 }
1481
1482 TEST_F(SeeksTest, SeekToLastOnWholeSpaceIteratorLevelDB) {
1483   SCOPED_TRACE("LevelDB: Seek To Last, Whole Space Iterator");
1484   SeekToLastOnWholeSpaceIterator(db->get_wholespace_iterator());
1485   ASSERT_FALSE(HasFatalFailure());
1486 }
1487
1488 TEST_F(SeeksTest, SeekToLastOnWholeSpaceIteratorMockDB) {
1489   SCOPED_TRACE("MockDB: Seek To Last, Whole Space Iterator");
1490   SeekToLastOnWholeSpaceIterator(mock->get_wholespace_iterator());
1491   ASSERT_FALSE(HasFatalFailure());
1492 }
1493
1494 TEST_F(SeeksTest, SeekToLastWithPrefixOnWholeSpaceIteratorLevelDB) {
1495   SCOPED_TRACE("LevelDB: Seek To Last, With Prefix, Whole Space Iterator");
1496   SeekToLastWithPrefixOnWholeSpaceIterator(db->get_wholespace_iterator());
1497   ASSERT_FALSE(HasFatalFailure());
1498 }
1499
1500 TEST_F(SeeksTest, SeekToLastWithPrefixOnWholeSpaceIteratorMockDB) {
1501   SCOPED_TRACE("MockDB: Seek To Last, With Prefix, Whole Space Iterator");
1502   SeekToLastWithPrefixOnWholeSpaceIterator(mock->get_wholespace_iterator());
1503   ASSERT_FALSE(HasFatalFailure());
1504 }
1505
1506 class KeySpaceIteration : public IteratorTest
1507 {
1508 public:
1509   string prefix1;
1510
1511   void init(KeyValueDB *store) {
1512     KeyValueDB::Transaction tx = store->get_transaction();
1513
1514     tx->set(prefix1, "aaa", _gen_val("aaa"));
1515     tx->set(prefix1, "vvv", _gen_val("vvv"));
1516     tx->set(prefix1, "zzz", _gen_val("zzz"));
1517
1518     store->submit_transaction_sync(tx);
1519   }
1520
1521   void SetUp() override {
1522     IteratorTest::SetUp();
1523
1524     prefix1 = "_PREFIX_1_";
1525
1526     clear(db.get());
1527     ASSERT_TRUE(validate_db_clear(db.get()));
1528     clear(mock.get());
1529     ASSERT_TRUE(validate_db_match());
1530
1531     init(db.get());
1532     init(mock.get());
1533
1534     ASSERT_TRUE(validate_db_match());
1535   }
1536
1537   void TearDown() override {
1538     IteratorTest::TearDown();
1539   }
1540
1541   void ForwardIteration(KeyValueDB::WholeSpaceIterator iter) {
1542     deque<string> key_deque;
1543     iter->seek_to_first();
1544     key_deque.push_back("aaa");
1545     key_deque.push_back("vvv");
1546     key_deque.push_back("zzz");
1547     validate_prefix(iter, prefix1, key_deque);
1548     ASSERT_FALSE(HasFatalFailure());
1549     ASSERT_FALSE(iter->valid());
1550   }
1551
1552   void BackwardIteration(KeyValueDB::WholeSpaceIterator iter) {
1553     deque<string> key_deque;
1554     iter->seek_to_last();
1555     key_deque.push_back("zzz");
1556     key_deque.push_back("vvv");
1557     key_deque.push_back("aaa");
1558     validate_prefix_backwards(iter, prefix1, key_deque);
1559     ASSERT_FALSE(HasFatalFailure());
1560     ASSERT_FALSE(iter->valid());
1561   }
1562 };
1563
1564 TEST_F(KeySpaceIteration, ForwardIterationLevelDB)
1565 {
1566   SCOPED_TRACE("LevelDB: Forward Iteration, Whole Space Iterator");
1567   ForwardIteration(db->get_wholespace_iterator());
1568   ASSERT_FALSE(HasFatalFailure());
1569 }
1570
1571 TEST_F(KeySpaceIteration, ForwardIterationMockDB) {
1572   SCOPED_TRACE("MockDB: Forward Iteration, Whole Space Iterator");
1573   ForwardIteration(mock->get_wholespace_iterator());
1574   ASSERT_FALSE(HasFatalFailure());
1575 }
1576
1577 TEST_F(KeySpaceIteration, BackwardIterationLevelDB)
1578 {
1579   SCOPED_TRACE("LevelDB: Backward Iteration, Whole Space Iterator");
1580   BackwardIteration(db->get_wholespace_iterator());
1581   ASSERT_FALSE(HasFatalFailure());
1582 }
1583
1584 TEST_F(KeySpaceIteration, BackwardIterationMockDB) {
1585   SCOPED_TRACE("MockDB: Backward Iteration, Whole Space Iterator");
1586   BackwardIteration(mock->get_wholespace_iterator());
1587   ASSERT_FALSE(HasFatalFailure());
1588 }
1589
1590 class EmptyStore : public IteratorTest
1591 {
1592 public:
1593   void SetUp() override {
1594     IteratorTest::SetUp();
1595
1596     clear(db.get());
1597     ASSERT_TRUE(validate_db_clear(db.get()));
1598     clear(mock.get());
1599     ASSERT_TRUE(validate_db_match());
1600   }
1601
1602   void SeekToFirst(KeyValueDB::WholeSpaceIterator iter) {
1603     // expected: iterator is invalid
1604     iter->seek_to_first();
1605     ASSERT_FALSE(iter->valid());
1606   }
1607
1608   void SeekToFirstWithPrefix(KeyValueDB::WholeSpaceIterator iter) {
1609     // expected: iterator is invalid
1610     iter->seek_to_first("prefix");
1611     ASSERT_FALSE(iter->valid());
1612   }
1613
1614   void SeekToLast(KeyValueDB::WholeSpaceIterator iter) {
1615     // expected: iterator is invalid
1616     iter->seek_to_last();
1617     ASSERT_FALSE(iter->valid());
1618   }
1619
1620   void SeekToLastWithPrefix(KeyValueDB::WholeSpaceIterator iter) {
1621     // expected: iterator is invalid
1622     iter->seek_to_last("prefix");
1623     ASSERT_FALSE(iter->valid());
1624   }
1625
1626   void LowerBound(KeyValueDB::WholeSpaceIterator iter) {
1627     // expected: iterator is invalid
1628     iter->lower_bound("prefix", "");
1629     ASSERT_FALSE(iter->valid());
1630
1631     // expected: iterator is invalid
1632     iter->lower_bound("", "key");
1633     ASSERT_FALSE(iter->valid());
1634
1635     // expected: iterator is invalid
1636     iter->lower_bound("prefix", "key");
1637     ASSERT_FALSE(iter->valid());
1638   }
1639
1640   void UpperBound(KeyValueDB::WholeSpaceIterator iter) {
1641     // expected: iterator is invalid
1642     iter->upper_bound("prefix", "");
1643     ASSERT_FALSE(iter->valid());
1644
1645     // expected: iterator is invalid
1646     iter->upper_bound("", "key");
1647     ASSERT_FALSE(iter->valid());
1648
1649     // expected: iterator is invalid
1650     iter->upper_bound("prefix", "key");
1651     ASSERT_FALSE(iter->valid());
1652   }
1653 };
1654
1655 TEST_F(EmptyStore, SeekToFirstLevelDB)
1656 {
1657   SCOPED_TRACE("LevelDB: Empty Store, Seek To First");
1658   SeekToFirst(db->get_wholespace_iterator());
1659   ASSERT_FALSE(HasFatalFailure());
1660 }
1661
1662 TEST_F(EmptyStore, SeekToFirstMockDB)
1663 {
1664   SCOPED_TRACE("MockDB: Empty Store, Seek To First");
1665   SeekToFirst(mock->get_wholespace_iterator());
1666   ASSERT_FALSE(HasFatalFailure());
1667 }
1668
1669 TEST_F(EmptyStore, SeekToFirstWithPrefixLevelDB)
1670 {
1671   SCOPED_TRACE("LevelDB: Empty Store, Seek To First With Prefix");
1672   SeekToFirstWithPrefix(db->get_wholespace_iterator());
1673   ASSERT_FALSE(HasFatalFailure());
1674 }
1675
1676 TEST_F(EmptyStore, SeekToFirstWithPrefixMockDB)
1677 {
1678   SCOPED_TRACE("MockDB: Empty Store, Seek To First With Prefix");
1679   SeekToFirstWithPrefix(mock->get_wholespace_iterator());
1680   ASSERT_FALSE(HasFatalFailure());
1681 }
1682
1683 TEST_F(EmptyStore, SeekToLastLevelDB)
1684 {
1685   SCOPED_TRACE("LevelDB: Empty Store, Seek To Last");
1686   SeekToLast(db->get_wholespace_iterator());
1687   ASSERT_FALSE(HasFatalFailure());
1688 }
1689
1690 TEST_F(EmptyStore, SeekToLastMockDB)
1691 {
1692   SCOPED_TRACE("MockDB: Empty Store, Seek To Last");
1693   SeekToLast(mock->get_wholespace_iterator());
1694   ASSERT_FALSE(HasFatalFailure());
1695 }
1696
1697 TEST_F(EmptyStore, SeekToLastWithPrefixLevelDB)
1698 {
1699   SCOPED_TRACE("LevelDB: Empty Store, Seek To Last With Prefix");
1700   SeekToLastWithPrefix(db->get_wholespace_iterator());
1701   ASSERT_FALSE(HasFatalFailure());
1702 }
1703
1704 TEST_F(EmptyStore, SeekToLastWithPrefixMockDB)
1705 {
1706   SCOPED_TRACE("MockDB: Empty Store, Seek To Last With Prefix");
1707   SeekToLastWithPrefix(mock->get_wholespace_iterator());
1708   ASSERT_FALSE(HasFatalFailure());
1709 }
1710
1711 TEST_F(EmptyStore, LowerBoundLevelDB)
1712 {
1713   SCOPED_TRACE("LevelDB: Empty Store, Lower Bound");
1714   LowerBound(db->get_wholespace_iterator());
1715   ASSERT_FALSE(HasFatalFailure());
1716 }
1717
1718 TEST_F(EmptyStore, LowerBoundMockDB)
1719 {
1720   SCOPED_TRACE("MockDB: Empty Store, Lower Bound");
1721   LowerBound(mock->get_wholespace_iterator());
1722   ASSERT_FALSE(HasFatalFailure());
1723 }
1724
1725 TEST_F(EmptyStore, UpperBoundLevelDB)
1726 {
1727   SCOPED_TRACE("LevelDB: Empty Store, Upper Bound");
1728   UpperBound(db->get_wholespace_iterator());
1729   ASSERT_FALSE(HasFatalFailure());
1730 }
1731
1732 TEST_F(EmptyStore, UpperBoundMockDB)
1733 {
1734   SCOPED_TRACE("MockDB: Empty Store, Upper Bound");
1735   UpperBound(mock->get_wholespace_iterator());
1736   ASSERT_FALSE(HasFatalFailure());
1737 }
1738
1739
1740 int main(int argc, char *argv[])
1741 {
1742   auto args = argv_to_vec(argc, argv);
1743
1744   auto cct = global_init(NULL, args, CEPH_ENTITY_TYPE_CLIENT, CODE_ENVIRONMENT_UTILITY, CINIT_FLAG_NO_DEFAULT_CONFIG_FILE);
1745   common_init_finish(g_ceph_context);
1746   ::testing::InitGoogleTest(&argc, argv);
1747
1748   if (argc < 2) {
1749     std::cerr << "Usage: " << argv[0]
1750               << "[ceph_options] [gtest_options] <store_path>" << std::endl;
1751     return 1;
1752   }
1753   store_path = string(argv[1]);
1754
1755   return RUN_ALL_TESTS();
1756 }