ceph/src/rocksdb/utilities/persistent_cache/hash_table_test.cc

   1 //  Copyright (c) 2013, Facebook, Inc.  All rights reserved.
   2 //  This source code is licensed under both the GPLv2 (found in the
   3 //  COPYING file in the root directory) and Apache 2.0 License
   4 //  (found in the LICENSE.Apache file in the root directory).
   5 //
   6 #include "utilities/persistent_cache/hash_table.h"
   7
   8 #include <stdlib.h>
   9
  10 #include <iostream>
  11 #include <set>
  12 #include <string>
  13
  14 #include "db/db_test_util.h"
  15 #include "memory/arena.h"
  16 #include "test_util/testharness.h"
  17 #include "util/random.h"
  18 #include "utilities/persistent_cache/hash_table_evictable.h"
  19
  20 #ifndef ROCKSDB_LITE
  21
  22 namespace ROCKSDB_NAMESPACE {
  23
  24 struct HashTableTest : public testing::Test {
  25   ~HashTableTest() override { map_.Clear(&HashTableTest::ClearNode); }
  26
  27   struct Node {
  28     Node() {}
  29     explicit Node(const uint64_t key, const std::string& val = std::string())
  30         : key_(key), val_(val) {}
  31
  32     uint64_t key_ = 0;
  33     std::string val_;
  34   };
  35
  36   struct Equal {
  37     bool operator()(const Node& lhs, const Node& rhs) {
  38       return lhs.key_ == rhs.key_;
  39     }
  40   };
  41
  42   struct Hash {
  43     uint64_t operator()(const Node& node) {
  44       return std::hash<uint64_t>()(node.key_);
  45     }
  46   };
  47
  48   static void ClearNode(Node /*node*/) {}
  49
  50   HashTable<Node, Hash, Equal> map_;
  51 };
  52
  53 struct EvictableHashTableTest : public testing::Test {
  54   ~EvictableHashTableTest() override {
  55     map_.Clear(&EvictableHashTableTest::ClearNode);
  56   }
  57
  58   struct Node : LRUElement<Node> {
  59     Node() {}
  60     explicit Node(const uint64_t key, const std::string& val = std::string())
  61         : key_(key), val_(val) {}
  62
  63     uint64_t key_ = 0;
  64     std::string val_;
  65     std::atomic<uint32_t> refs_{0};
  66   };
  67
  68   struct Equal {
  69     bool operator()(const Node* lhs, const Node* rhs) {
  70       return lhs->key_ == rhs->key_;
  71     }
  72   };
  73
  74   struct Hash {
  75     uint64_t operator()(const Node* node) {
  76       return std::hash<uint64_t>()(node->key_);
  77     }
  78   };
  79
  80   static void ClearNode(Node* /*node*/) {}
  81
  82   EvictableHashTable<Node, Hash, Equal> map_;
  83 };
  84
  85 TEST_F(HashTableTest, TestInsert) {
  86   const uint64_t max_keys = 1024 * 1024;
  87
  88   // insert
  89   for (uint64_t k = 0; k < max_keys; ++k) {
  90     map_.Insert(Node(k, std::string(1000, k % 255)));
  91   }
  92
  93   // verify
  94   for (uint64_t k = 0; k < max_keys; ++k) {
  95     Node val;
  96     port::RWMutex* rlock = nullptr;
  97     assert(map_.Find(Node(k), &val, &rlock));
  98     rlock->ReadUnlock();
  99     assert(val.val_ == std::string(1000, k % 255));
 100   }
 101 }
 102
 103 TEST_F(HashTableTest, TestErase) {
 104   const uint64_t max_keys = 1024 * 1024;
 105   // insert
 106   for (uint64_t k = 0; k < max_keys; ++k) {
 107     map_.Insert(Node(k, std::string(1000, k % 255)));
 108   }
 109
 110   auto rand = Random64(time(nullptr));
 111   // erase a few keys randomly
 112   std::set<uint64_t> erased;
 113   for (int i = 0; i < 1024; ++i) {
 114     uint64_t k = rand.Next() % max_keys;
 115     if (erased.find(k) != erased.end()) {
 116       continue;
 117     }
 118     assert(map_.Erase(Node(k), /*ret=*/nullptr));
 119     erased.insert(k);
 120   }
 121
 122   // verify
 123   for (uint64_t k = 0; k < max_keys; ++k) {
 124     Node val;
 125     port::RWMutex* rlock = nullptr;
 126     bool status = map_.Find(Node(k), &val, &rlock);
 127     if (erased.find(k) == erased.end()) {
 128       assert(status);
 129       rlock->ReadUnlock();
 130       assert(val.val_ == std::string(1000, k % 255));
 131     } else {
 132       assert(!status);
 133     }
 134   }
 135 }
 136
 137 TEST_F(EvictableHashTableTest, TestEvict) {
 138   const uint64_t max_keys = 1024 * 1024;
 139
 140   // insert
 141   for (uint64_t k = 0; k < max_keys; ++k) {
 142     map_.Insert(new Node(k, std::string(1000, k % 255)));
 143   }
 144
 145   // verify
 146   for (uint64_t k = 0; k < max_keys; ++k) {
 147     Node* val = map_.Evict();
 148     // unfortunately we can't predict eviction value since it is from any one of
 149     // the lock stripe
 150     assert(val);
 151     assert(val->val_ == std::string(1000, val->key_ % 255));
 152     delete val;
 153   }
 154 }
 155
 156 }  // namespace ROCKSDB_NAMESPACE
 157 #endif
 158
 159 int main(int argc, char** argv) {
 160   ROCKSDB_NAMESPACE::port::InstallStackTraceHandler();
 161   ::testing::InitGoogleTest(&argc, argv);
 162   return RUN_ALL_TESTS();
 163 }