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