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