Branch data Line data Source code
1 : : // Copyright (c) 2012-2021 The Bitcoin Core 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 [ + - + - : 7 : BOOST_AUTO_TEST_CASE(test_cuckoocache_no_fakes)
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- ]
39 : : {
40 : 1 : SeedRandomForTest(SeedRand::ZEROS);
41 : 1 : CuckooCache::cache<uint256, SignatureCacheHasher> cc{};
42 : 1 : size_t megabytes = 4;
43 [ + - ]: 1 : cc.setup_bytes(megabytes << 20);
44 [ + + ]: 100001 : for (int x = 0; x < 100000; ++x) {
45 : 100000 : cc.insert(m_rng.rand256());
46 : : }
47 [ + + ]: 100001 : for (int x = 0; x < 100000; ++x) {
48 [ + - + - ]: 200000 : BOOST_CHECK(!cc.contains(m_rng.rand256(), false));
49 : : }
50 : 1 : };
51 : :
52 : 2 : 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 : 5 : double test_cache(size_t megabytes, double load)
58 : : {
59 : 5 : SeedRandomForTest(SeedRand::ZEROS);
60 : 5 : std::vector<uint256> hashes;
61 [ + - ]: 5 : Cache set{};
62 : 5 : size_t bytes = megabytes * (1 << 20);
63 [ + - ]: 5 : set.setup_bytes(bytes);
64 : 5 : uint32_t n_insert = static_cast<uint32_t>(load * (bytes / sizeof(uint256)));
65 [ + - ]: 5 : hashes.resize(n_insert);
66 [ + + ]: 406326 : for (uint32_t i = 0; i < n_insert; ++i) {
67 : 406321 : uint32_t* ptr = (uint32_t*)hashes[i].begin();
68 [ + + ]: 3656889 : for (uint8_t j = 0; j < 8; ++j)
69 : 3250568 : *(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 [ + - ]: 5 : std::vector<uint256> hashes_insert_copy = hashes;
76 : : /** Do the insert */
77 [ + + ]: 406326 : for (const uint256& h : hashes_insert_copy)
78 : 406321 : set.insert(h);
79 : : /** Count the hits */
80 : 5 : uint32_t count = 0;
81 [ + + ]: 406326 : for (const uint256& h : hashes)
82 : 406321 : count += set.contains(h, false);
83 : 5 : double hit_rate = ((double)count) / ((double)n_insert);
84 : 5 : return hit_rate;
85 : 5 : }
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 : 5 : static double normalize_hit_rate(double hits, double load)
105 : : {
106 [ + + ]: 5 : 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 [ + - + - : 7 : 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 : 1 : double HitRateThresh = 0.98;
117 : 1 : size_t megabytes = 4;
118 [ + + ]: 6 : for (double load = 0.1; load < 2; load *= 2) {
119 : 5 : double hits = test_cache<CuckooCache::cache<uint256, SignatureCacheHasher>>(megabytes, load);
120 [ + + + - ]: 11 : BOOST_CHECK(normalize_hit_rate(hits, load) > HitRateThresh);
121 : : }
122 : 1 : }
123 : :
124 : :
125 : 2 : 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 : 1 : void test_cache_erase(size_t megabytes)
130 : : {
131 : 1 : double load = 1;
132 : 1 : SeedRandomForTest(SeedRand::ZEROS);
133 : 1 : std::vector<uint256> hashes;
134 [ + - ]: 1 : Cache set{};
135 : 1 : size_t bytes = megabytes * (1 << 20);
136 [ + - ]: 1 : set.setup_bytes(bytes);
137 : 1 : uint32_t n_insert = static_cast<uint32_t>(load * (bytes / sizeof(uint256)));
138 [ + - ]: 1 : hashes.resize(n_insert);
139 [ + + ]: 131073 : for (uint32_t i = 0; i < n_insert; ++i) {
140 : 131072 : uint32_t* ptr = (uint32_t*)hashes[i].begin();
141 [ + + ]: 1179648 : for (uint8_t j = 0; j < 8; ++j)
142 : 1048576 : *(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 [ + - ]: 1 : std::vector<uint256> hashes_insert_copy = hashes;
149 : :
150 : : /** Insert the first half */
151 [ + + ]: 65537 : for (uint32_t i = 0; i < (n_insert / 2); ++i)
152 : 65536 : set.insert(hashes_insert_copy[i]);
153 : : /** Erase the first quarter */
154 [ + + ]: 32769 : for (uint32_t i = 0; i < (n_insert / 4); ++i)
155 [ + - + - ]: 65536 : BOOST_CHECK(set.contains(hashes[i], true));
156 : : /** Insert the second half */
157 [ + + ]: 65537 : for (uint32_t i = (n_insert / 2); i < n_insert; ++i)
158 : 65536 : 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 : 32769 : size_t count_stale = 0;
164 : : /** elements that were most recently inserted */
165 : 32769 : size_t count_fresh = 0;
166 : :
167 [ + + ]: 32769 : for (uint32_t i = 0; i < (n_insert / 4); ++i)
168 : 32768 : count_erased_but_contained += set.contains(hashes[i], false);
169 [ + + ]: 32769 : for (uint32_t i = (n_insert / 4); i < (n_insert / 2); ++i)
170 : 32768 : count_stale += set.contains(hashes[i], false);
171 [ + + ]: 65537 : for (uint32_t i = (n_insert / 2); i < n_insert; ++i)
172 : 65536 : count_fresh += set.contains(hashes[i], false);
173 : :
174 : 1 : double hit_rate_erased_but_contained = double(count_erased_but_contained) / (double(n_insert) / 4.0);
175 : 1 : double hit_rate_stale = double(count_stale) / (double(n_insert) / 4.0);
176 : 1 : double hit_rate_fresh = double(count_fresh) / (double(n_insert) / 2.0);
177 : :
178 : : // Check that our hit_rate_fresh is perfect
179 [ + - + - ]: 1 : 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 [ + - + - ]: 2 : BOOST_CHECK(hit_rate_stale > 2 * hit_rate_erased_but_contained);
183 : 1 : }
184 : : }; // struct EraseTest
185 : :
186 [ + - + - : 7 : BOOST_FIXTURE_TEST_CASE(cuckoocache_erase_ok, EraseTest)
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- ]
187 : : {
188 : 1 : size_t megabytes = 4;
189 : 1 : test_cache_erase<CuckooCache::cache<uint256, SignatureCacheHasher>>(megabytes);
190 : 1 : }
191 : :
192 : 2 : struct EraseParallelTest : BasicTestingSetup {
193 : : template <typename Cache>
194 : 1 : void test_cache_erase_parallel(size_t megabytes)
195 : : {
196 : 1 : double load = 1;
197 : 1 : SeedRandomForTest(SeedRand::ZEROS);
198 : 1 : std::vector<uint256> hashes;
199 [ + - ]: 1 : Cache set{};
200 : 1 : size_t bytes = megabytes * (1 << 20);
201 [ + - ]: 1 : set.setup_bytes(bytes);
202 : 1 : uint32_t n_insert = static_cast<uint32_t>(load * (bytes / sizeof(uint256)));
203 [ + - ]: 1 : hashes.resize(n_insert);
204 [ + + ]: 131073 : for (uint32_t i = 0; i < n_insert; ++i) {
205 : 131072 : uint32_t* ptr = (uint32_t*)hashes[i].begin();
206 [ + + ]: 1179648 : for (uint8_t j = 0; j < 8; ++j)
207 : 1048576 : *(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 [ + - ]: 1 : std::vector<uint256> hashes_insert_copy = hashes;
214 [ + - ]: 1 : std::shared_mutex mtx;
215 : :
216 : : {
217 : : /** Grab lock to make sure we release inserts */
218 : 1 : std::unique_lock<std::shared_mutex> l(mtx);
219 : : /** Insert the first half */
220 [ + + ]: 65537 : for (uint32_t i = 0; i < (n_insert / 2); ++i)
221 : 65536 : set.insert(hashes_insert_copy[i]);
222 : 1 : }
223 : :
224 : : /** Spin up 3 threads to run contains with erase.
225 : : */
226 : 1 : std::vector<std::thread> threads;
227 [ + - ]: 1 : threads.reserve(3);
228 : : /** Erase the first quarter */
229 [ + + ]: 4 : for (uint32_t x = 0; x < 3; ++x)
230 : : /** Each thread is emplaced with x copy-by-value
231 : : */
232 [ + - ]: 3 : threads.emplace_back([&, x] {
233 : 3 : std::shared_lock<std::shared_mutex> l(mtx);
234 : 3 : size_t ntodo = (n_insert/4)/3;
235 : 3 : size_t start = ntodo*x;
236 : 3 : size_t end = ntodo*(x+1);
237 [ + + ]: 32769 : for (uint32_t i = start; i < end; ++i) {
238 : 32766 : bool contains = set.contains(hashes[i], true);
239 [ - + ]: 32766 : assert(contains);
240 : : }
241 : 3 : });
242 : :
243 : : /** Wait for all threads to finish
244 : : */
245 [ + + ]: 4 : for (std::thread& t : threads)
246 [ + - ]: 3 : t.join();
247 : : /** Grab lock to make sure we observe erases */
248 : 1 : std::unique_lock<std::shared_mutex> l(mtx);
249 : : /** Insert the second half */
250 [ + + ]: 65537 : for (uint32_t i = (n_insert / 2); i < n_insert; ++i)
251 : 65536 : 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 : 32769 : size_t count_stale = 0;
257 : : /** elements that were most recently inserted */
258 : 32769 : size_t count_fresh = 0;
259 : :
260 [ + + ]: 32769 : for (uint32_t i = 0; i < (n_insert / 4); ++i)
261 : 32768 : count_erased_but_contained += set.contains(hashes[i], false);
262 [ + + ]: 32769 : for (uint32_t i = (n_insert / 4); i < (n_insert / 2); ++i)
263 : 32768 : count_stale += set.contains(hashes[i], false);
264 [ + + ]: 65537 : for (uint32_t i = (n_insert / 2); i < n_insert; ++i)
265 : 65536 : count_fresh += set.contains(hashes[i], false);
266 : :
267 : 1 : double hit_rate_erased_but_contained = double(count_erased_but_contained) / (double(n_insert) / 4.0);
268 : 1 : double hit_rate_stale = double(count_stale) / (double(n_insert) / 4.0);
269 : 1 : double hit_rate_fresh = double(count_fresh) / (double(n_insert) / 2.0);
270 : :
271 : : // Check that our hit_rate_fresh is perfect
272 [ + - + - ]: 1 : 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 [ + - + - : 2 : BOOST_CHECK(hit_rate_stale > 2 * hit_rate_erased_but_contained);
+ - ]
276 : 1 : }
277 : : }; // struct EraseParallelTest
278 [ + - + - : 7 : BOOST_FIXTURE_TEST_CASE(cuckoocache_erase_parallel_ok, EraseParallelTest)
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- ]
279 : : {
280 : 1 : size_t megabytes = 4;
281 : 1 : test_cache_erase_parallel<CuckooCache::cache<uint256, SignatureCacheHasher>>(megabytes);
282 : 1 : }
283 : :
284 : :
285 : 2 : struct GenerationsTest : BasicTestingSetup {
286 : : template <typename Cache>
287 : 1 : 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 : 1 : double min_hit_rate = 0.99;
293 : 1 : double tight_hit_rate = 0.999;
294 : 1 : 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 : 1 : 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 : 1310 : struct block_activity {
312 : : std::vector<uint256> reads;
313 : 1310 : block_activity(uint32_t n_insert, FastRandomContext& rng, Cache& c)
314 [ + - ]: 1310 : {
315 : 1310 : std::vector<uint256> inserts;
316 [ + - ]: 1310 : inserts.resize(n_insert);
317 [ + - ]: 1310 : reads.reserve(n_insert / 2);
318 [ + + ]: 1311310 : for (uint32_t i = 0; i < n_insert; ++i) {
319 : 1310000 : uint32_t* ptr = (uint32_t*)inserts[i].begin();
320 [ + + ]: 11790000 : for (uint8_t j = 0; j < 8; ++j)
321 : 10480000 : *(ptr++) = rng.rand32();
322 : : }
323 [ + + ]: 328810 : for (uint32_t i = 0; i < n_insert / 4; ++i)
324 [ + - ]: 327500 : reads.push_back(inserts[i]);
325 [ + + ]: 328810 : for (uint32_t i = n_insert - (n_insert / 4); i < n_insert; ++i)
326 [ + - ]: 327500 : reads.push_back(inserts[i]);
327 [ + + ]: 1311310 : for (const auto& h : inserts)
328 : 1310000 : c.insert(h);
329 : 1310 : }
330 : : };
331 : :
332 : 1 : 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 : 1 : const uint32_t WINDOW_SIZE = 60;
336 : 1 : const uint32_t POP_AMOUNT = (BLOCK_SIZE / WINDOW_SIZE) / 2;
337 : 1 : const double load = 10;
338 : 1 : const size_t megabytes = 4;
339 : 1 : const size_t bytes = megabytes * (1 << 20);
340 : 1 : const uint32_t n_insert = static_cast<uint32_t>(load * (bytes / sizeof(uint256)));
341 : :
342 : 1 : std::vector<block_activity> hashes;
343 [ + - ]: 1 : Cache set{};
344 [ + - ]: 1 : set.setup_bytes(bytes);
345 [ + - ]: 1 : hashes.reserve(n_insert / BLOCK_SIZE);
346 : 1311 : 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 [ + + ]: 1311 : for (uint32_t i = 0; i < total; ++i) {
353 [ + + ]: 1310 : if (last_few.size() == WINDOW_SIZE)
354 : 1250 : last_few.pop_front();
355 [ + - ]: 1310 : last_few.emplace_back(BLOCK_SIZE, m_rng, set);
356 : 1310 : uint32_t count = 0;
357 [ + + ]: 78140 : for (auto& act : last_few)
358 [ + + ]: 691470 : for (uint32_t k = 0; k < POP_AMOUNT; ++k) {
359 : 614640 : count += set.contains(act.reads.back(), true);
360 : 614640 : 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 [ + - ]: 1310 : double hit = (double(count)) / (last_few.size() * POP_AMOUNT);
366 : : // Loose Check that hit rate is above min_hit_rate
367 [ + - + - ]: 2620 : 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 : 1310 : 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 [ + - + - ]: 2 : BOOST_CHECK(double(out_of_tight_tolerance) / double(total) < max_rate_less_than_tight_hit_rate);
375 : 1 : }
376 : : }; // struct GenerationsTest
377 [ + - + - : 7 : BOOST_FIXTURE_TEST_CASE(cuckoocache_generations, GenerationsTest)
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- ]
378 : : {
379 : 1 : test_cache_generations<CuckooCache::cache<uint256, SignatureCacheHasher>>();
380 : 1 : }
381 : :
382 : : BOOST_AUTO_TEST_SUITE_END();
|
