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