1 // Copyright (c) 2012-2021 The Limenka developers
2 // Distributed under the MIT software license, see the accompanying
3 // file COPYING or http://www.opensource.org/licenses/mit-license.php.
4 5 #include <cuckoocache.h>
6 #include <random.h>
7 #include <script/sigcache.h>
8 #include <test/util/random.h>
9 #include <test/util/setup_common.h>
10 11 #include <boost/test/unit_test.hpp>
12 13 #include <deque>
14 #include <mutex>
15 #include <shared_mutex>
16 #include <thread>
17 #include <vector>
18 19 /** Test Suite for CuckooCache
20 *
21 * 1. All tests should have a deterministic result (using insecure rand
22 * with deterministic seeds)
23 * 2. Some test methods are templated to allow for easier testing
24 * against new versions / comparing
25 * 3. Results should be treated as a regression test, i.e., did the behavior
26 * change significantly from what was expected. This can be OK, depending on
27 * the nature of the change, but requires updating the tests to reflect the new
28 * expected behavior. For example improving the hit rate may cause some tests
29 * using BOOST_CHECK_CLOSE to fail.
30 *
31 */
32 BOOST_FIXTURE_TEST_SUITE(cuckoocache_tests, BasicTestingSetup);
33 34 /* Test that no values not inserted into the cache are read out of it.
35 *
36 * There are no repeats in the first 200000 m_rng.rand256() calls
37 */
38 BOOST_AUTO_TEST_CASE(test_cuckoocache_no_fakes)
39 {
40 SeedRandomForTest(SeedRand::ZEROS);
41 CuckooCache::cache<uint256, SignatureCacheHasher> cc{};
42 size_t megabytes = 4;
43 cc.setup_bytes(megabytes << 20);
44 for (int x = 0; x < 100000; ++x) {
45 cc.insert(m_rng.rand256());
46 }
47 for (int x = 0; x < 100000; ++x) {
48 BOOST_CHECK(!cc.contains(m_rng.rand256(), false));
49 }
50 };
51 52 struct HitRateTest : BasicTestingSetup {
53 /** This helper returns the hit rate when megabytes*load worth of entries are
54 * inserted into a megabytes sized cache
55 */
56 template <typename Cache>
57 double test_cache(size_t megabytes, double load)
58 {
59 SeedRandomForTest(SeedRand::ZEROS);
60 std::vector<uint256> hashes;
61 Cache set{};
62 size_t bytes = megabytes * (1 << 20);
63 set.setup_bytes(bytes);
64 uint32_t n_insert = static_cast<uint32_t>(load * (bytes / sizeof(uint256)));
65 hashes.resize(n_insert);
66 for (uint32_t i = 0; i < n_insert; ++i) {
67 uint32_t* ptr = (uint32_t*)hashes[i].begin();
68 for (uint8_t j = 0; j < 8; ++j)
69 *(ptr++) = m_rng.rand32();
70 }
71 /** We make a copy of the hashes because future optimizations of the
72 * cuckoocache may overwrite the inserted element, so the test is
73 * "future proofed".
74 */
75 std::vector<uint256> hashes_insert_copy = hashes;
76 /** Do the insert */
77 for (const uint256& h : hashes_insert_copy)
78 set.insert(h);
79 /** Count the hits */
80 uint32_t count = 0;
81 for (const uint256& h : hashes)
82 count += set.contains(h, false);
83 double hit_rate = ((double)count) / ((double)n_insert);
84 return hit_rate;
85 }
86 87 /** The normalized hit rate for a given load.
88 *
89 * The semantics are a little confusing, so please see the below
90 * explanation.
91 *
92 * Examples:
93 *
94 * 1. at load 0.5, we expect a perfect hit rate, so we multiply by
95 * 1.0
96 * 2. at load 2.0, we expect to see half the entries, so a perfect hit rate
97 * would be 0.5. Therefore, if we see a hit rate of 0.4, 0.4*2.0 = 0.8 is the
98 * normalized hit rate.
99 *
100 * This is basically the right semantics, but has a bit of a glitch depending on
101 * how you measure around load 1.0 as after load 1.0 your normalized hit rate
102 * becomes effectively perfect, ignoring freshness.
103 */
104 static double normalize_hit_rate(double hits, double load)
105 {
106 return hits * std::max(load, 1.0);
107 }
108 }; // struct HitRateTest
109 110 /** Check the hit rate on loads ranging from 0.1 to 1.6 */
111 BOOST_FIXTURE_TEST_CASE(cuckoocache_hit_rate_ok, HitRateTest)
112 {
113 /** Arbitrarily selected Hit Rate threshold that happens to work for this test
114 * as a lower bound on performance.
115 */
116 double HitRateThresh = 0.98;
117 size_t megabytes = 4;
118 for (double load = 0.1; load < 2; load *= 2) {
119 double hits = test_cache<CuckooCache::cache<uint256, SignatureCacheHasher>>(megabytes, load);
120 BOOST_CHECK(normalize_hit_rate(hits, load) > HitRateThresh);
121 }
122 }
123 124 125 struct EraseTest : BasicTestingSetup {
126 /** This helper checks that erased elements are preferentially inserted onto and
127 * that the hit rate of "fresher" keys is reasonable*/
128 template <typename Cache>
129 void test_cache_erase(size_t megabytes)
130 {
131 double load = 1;
132 SeedRandomForTest(SeedRand::ZEROS);
133 std::vector<uint256> hashes;
134 Cache set{};
135 size_t bytes = megabytes * (1 << 20);
136 set.setup_bytes(bytes);
137 uint32_t n_insert = static_cast<uint32_t>(load * (bytes / sizeof(uint256)));
138 hashes.resize(n_insert);
139 for (uint32_t i = 0; i < n_insert; ++i) {
140 uint32_t* ptr = (uint32_t*)hashes[i].begin();
141 for (uint8_t j = 0; j < 8; ++j)
142 *(ptr++) = m_rng.rand32();
143 }
144 /** We make a copy of the hashes because future optimizations of the
145 * cuckoocache may overwrite the inserted element, so the test is
146 * "future proofed".
147 */
148 std::vector<uint256> hashes_insert_copy = hashes;
149 150 /** Insert the first half */
151 for (uint32_t i = 0; i < (n_insert / 2); ++i)
152 set.insert(hashes_insert_copy[i]);
153 /** Erase the first quarter */
154 for (uint32_t i = 0; i < (n_insert / 4); ++i)
155 BOOST_CHECK(set.contains(hashes[i], true));
156 /** Insert the second half */
157 for (uint32_t i = (n_insert / 2); i < n_insert; ++i)
158 set.insert(hashes_insert_copy[i]);
159 160 /** elements that we marked as erased but are still there */
161 size_t count_erased_but_contained = 0;
162 /** elements that we did not erase but are older */
163 size_t count_stale = 0;
164 /** elements that were most recently inserted */
165 size_t count_fresh = 0;
166 167 for (uint32_t i = 0; i < (n_insert / 4); ++i)
168 count_erased_but_contained += set.contains(hashes[i], false);
169 for (uint32_t i = (n_insert / 4); i < (n_insert / 2); ++i)
170 count_stale += set.contains(hashes[i], false);
171 for (uint32_t i = (n_insert / 2); i < n_insert; ++i)
172 count_fresh += set.contains(hashes[i], false);
173 174 double hit_rate_erased_but_contained = double(count_erased_but_contained) / (double(n_insert) / 4.0);
175 double hit_rate_stale = double(count_stale) / (double(n_insert) / 4.0);
176 double hit_rate_fresh = double(count_fresh) / (double(n_insert) / 2.0);
177 178 // Check that our hit_rate_fresh is perfect
179 BOOST_CHECK_EQUAL(hit_rate_fresh, 1.0);
180 // Check that we have a more than 2x better hit rate on stale elements than
181 // erased elements.
182 BOOST_CHECK(hit_rate_stale > 2 * hit_rate_erased_but_contained);
183 }
184 }; // struct EraseTest
185 186 BOOST_FIXTURE_TEST_CASE(cuckoocache_erase_ok, EraseTest)
187 {
188 size_t megabytes = 4;
189 test_cache_erase<CuckooCache::cache<uint256, SignatureCacheHasher>>(megabytes);
190 }
191 192 struct EraseParallelTest : BasicTestingSetup {
193 template <typename Cache>
194 void test_cache_erase_parallel(size_t megabytes)
195 {
196 double load = 1;
197 SeedRandomForTest(SeedRand::ZEROS);
198 std::vector<uint256> hashes;
199 Cache set{};
200 size_t bytes = megabytes * (1 << 20);
201 set.setup_bytes(bytes);
202 uint32_t n_insert = static_cast<uint32_t>(load * (bytes / sizeof(uint256)));
203 hashes.resize(n_insert);
204 for (uint32_t i = 0; i < n_insert; ++i) {
205 uint32_t* ptr = (uint32_t*)hashes[i].begin();
206 for (uint8_t j = 0; j < 8; ++j)
207 *(ptr++) = m_rng.rand32();
208 }
209 /** We make a copy of the hashes because future optimizations of the
210 * cuckoocache may overwrite the inserted element, so the test is
211 * "future proofed".
212 */
213 std::vector<uint256> hashes_insert_copy = hashes;
214 std::shared_mutex mtx;
215 216 {
217 /** Grab lock to make sure we release inserts */
218 std::unique_lock<std::shared_mutex> l(mtx);
219 /** Insert the first half */
220 for (uint32_t i = 0; i < (n_insert / 2); ++i)
221 set.insert(hashes_insert_copy[i]);
222 }
223 224 /** Spin up 3 threads to run contains with erase.
225 */
226 std::vector<std::thread> threads;
227 threads.reserve(3);
228 /** Erase the first quarter */
229 for (uint32_t x = 0; x < 3; ++x)
230 /** Each thread is emplaced with x copy-by-value
231 */
232 threads.emplace_back([&, x] {
233 std::shared_lock<std::shared_mutex> l(mtx);
234 size_t ntodo = (n_insert/4)/3;
235 size_t start = ntodo*x;
236 size_t end = ntodo*(x+1);
237 for (uint32_t i = start; i < end; ++i) {
238 bool contains = set.contains(hashes[i], true);
239 assert(contains);
240 }
241 });
242 243 /** Wait for all threads to finish
244 */
245 for (std::thread& t : threads)
246 t.join();
247 /** Grab lock to make sure we observe erases */
248 std::unique_lock<std::shared_mutex> l(mtx);
249 /** Insert the second half */
250 for (uint32_t i = (n_insert / 2); i < n_insert; ++i)
251 set.insert(hashes_insert_copy[i]);
252 253 /** elements that we marked erased but that are still there */
254 size_t count_erased_but_contained = 0;
255 /** elements that we did not erase but are older */
256 size_t count_stale = 0;
257 /** elements that were most recently inserted */
258 size_t count_fresh = 0;
259 260 for (uint32_t i = 0; i < (n_insert / 4); ++i)
261 count_erased_but_contained += set.contains(hashes[i], false);
262 for (uint32_t i = (n_insert / 4); i < (n_insert / 2); ++i)
263 count_stale += set.contains(hashes[i], false);
264 for (uint32_t i = (n_insert / 2); i < n_insert; ++i)
265 count_fresh += set.contains(hashes[i], false);
266 267 double hit_rate_erased_but_contained = double(count_erased_but_contained) / (double(n_insert) / 4.0);
268 double hit_rate_stale = double(count_stale) / (double(n_insert) / 4.0);
269 double hit_rate_fresh = double(count_fresh) / (double(n_insert) / 2.0);
270 271 // Check that our hit_rate_fresh is perfect
272 BOOST_CHECK_EQUAL(hit_rate_fresh, 1.0);
273 // Check that we have a more than 2x better hit rate on stale elements than
274 // erased elements.
275 BOOST_CHECK(hit_rate_stale > 2 * hit_rate_erased_but_contained);
276 }
277 }; // struct EraseParallelTest
278 BOOST_FIXTURE_TEST_CASE(cuckoocache_erase_parallel_ok, EraseParallelTest)
279 {
280 size_t megabytes = 4;
281 test_cache_erase_parallel<CuckooCache::cache<uint256, SignatureCacheHasher>>(megabytes);
282 }
283 284 285 struct GenerationsTest : BasicTestingSetup {
286 template <typename Cache>
287 void test_cache_generations()
288 {
289 // This test checks that for a simulation of network activity, the fresh hit
290 // rate is never below 99%, and the number of times that it is worse than
291 // 99.9% are less than 1% of the time.
292 double min_hit_rate = 0.99;
293 double tight_hit_rate = 0.999;
294 double max_rate_less_than_tight_hit_rate = 0.01;
295 // A cache that meets this specification is therefore shown to have a hit
296 // rate of at least tight_hit_rate * (1 - max_rate_less_than_tight_hit_rate) +
297 // min_hit_rate*max_rate_less_than_tight_hit_rate = 0.999*99%+0.99*1% == 99.89%
298 // hit rate with low variance.
299 300 // We use deterministic values, but this test has also passed on many
301 // iterations with non-deterministic values, so it isn't "overfit" to the
302 // specific entropy in FastRandomContext(true) and implementation of the
303 // cache.
304 SeedRandomForTest(SeedRand::ZEROS);
305 306 // block_activity models a chunk of network activity. n_insert elements are
307 // added to the cache. The first and last n/4 are stored for removal later
308 // and the middle n/2 are not stored. This models a network which uses half
309 // the signatures of recently (since the last block) added transactions
310 // immediately and never uses the other half.
311 struct block_activity {
312 std::vector<uint256> reads;
313 block_activity(uint32_t n_insert, FastRandomContext& rng, Cache& c)
314 {
315 std::vector<uint256> inserts;
316 inserts.resize(n_insert);
317 reads.reserve(n_insert / 2);
318 for (uint32_t i = 0; i < n_insert; ++i) {
319 uint32_t* ptr = (uint32_t*)inserts[i].begin();
320 for (uint8_t j = 0; j < 8; ++j)
321 *(ptr++) = rng.rand32();
322 }
323 for (uint32_t i = 0; i < n_insert / 4; ++i)
324 reads.push_back(inserts[i]);
325 for (uint32_t i = n_insert - (n_insert / 4); i < n_insert; ++i)
326 reads.push_back(inserts[i]);
327 for (const auto& h : inserts)
328 c.insert(h);
329 }
330 };
331 332 const uint32_t BLOCK_SIZE = 1000;
333 // We expect window size 60 to perform reasonably given that each epoch
334 // stores 45% of the cache size (~472k).
335 const uint32_t WINDOW_SIZE = 60;
336 const uint32_t POP_AMOUNT = (BLOCK_SIZE / WINDOW_SIZE) / 2;
337 const double load = 10;
338 const size_t megabytes = 4;
339 const size_t bytes = megabytes * (1 << 20);
340 const uint32_t n_insert = static_cast<uint32_t>(load * (bytes / sizeof(uint256)));
341 342 std::vector<block_activity> hashes;
343 Cache set{};
344 set.setup_bytes(bytes);
345 hashes.reserve(n_insert / BLOCK_SIZE);
346 std::deque<block_activity> last_few;
347 uint32_t out_of_tight_tolerance = 0;
348 uint32_t total = n_insert / BLOCK_SIZE;
349 // we use the deque last_few to model a sliding window of blocks. at each
350 // step, each of the last WINDOW_SIZE block_activities checks the cache for
351 // POP_AMOUNT of the hashes that they inserted, and marks these erased.
352 for (uint32_t i = 0; i < total; ++i) {
353 if (last_few.size() == WINDOW_SIZE)
354 last_few.pop_front();
355 last_few.emplace_back(BLOCK_SIZE, m_rng, set);
356 uint32_t count = 0;
357 for (auto& act : last_few)
358 for (uint32_t k = 0; k < POP_AMOUNT; ++k) {
359 count += set.contains(act.reads.back(), true);
360 act.reads.pop_back();
361 }
362 // We use last_few.size() rather than WINDOW_SIZE for the correct
363 // behavior on the first WINDOW_SIZE iterations where the deque is not
364 // full yet.
365 double hit = (double(count)) / (last_few.size() * POP_AMOUNT);
366 // Loose Check that hit rate is above min_hit_rate
367 BOOST_CHECK(hit > min_hit_rate);
368 // Tighter check, count number of times we are less than tight_hit_rate
369 // (and implicitly, greater than min_hit_rate)
370 out_of_tight_tolerance += hit < tight_hit_rate;
371 }
372 // Check that being out of tolerance happens less than
373 // max_rate_less_than_tight_hit_rate of the time
374 BOOST_CHECK(double(out_of_tight_tolerance) / double(total) < max_rate_less_than_tight_hit_rate);
375 }
376 }; // struct GenerationsTest
377 BOOST_FIXTURE_TEST_CASE(cuckoocache_generations, GenerationsTest)
378 {
379 test_cache_generations<CuckooCache::cache<uint256, SignatureCacheHasher>>();
380 }
381 382 BOOST_AUTO_TEST_SUITE_END();
383