Branch data Line data Source code
1 : : // Copyright (c) 2012-present 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 : : #include <util/byte_units.h>
11 : :
12 : : #include <boost/test/unit_test.hpp>
13 : :
14 : : #include <deque>
15 : : #include <mutex>
16 : : #include <shared_mutex>
17 : : #include <thread>
18 : : #include <vector>
19 : :
20 : : /** Test Suite for CuckooCache
21 : : *
22 : : * 1. All tests should have a deterministic result (using insecure rand
23 : : * with deterministic seeds)
24 : : * 2. Some test methods are templated to allow for easier testing
25 : : * against new versions / comparing
26 : : * 3. Results should be treated as a regression test, i.e., did the behavior
27 : : * change significantly from what was expected. This can be OK, depending on
28 : : * the nature of the change, but requires updating the tests to reflect the new
29 : : * expected behavior. For example improving the hit rate may cause some tests
30 : : * using BOOST_CHECK_CLOSE to fail.
31 : : *
32 : : */
33 : : BOOST_FIXTURE_TEST_SUITE(cuckoocache_tests, BasicTestingSetup);
34 : :
35 : : /* Test that no values not inserted into the cache are read out of it.
36 : : *
37 : : * There are no repeats in the first 200000 m_rng.rand256() calls
38 : : */
39 [ + - + - : 7 : BOOST_AUTO_TEST_CASE(test_cuckoocache_no_fakes)
+ - + - -
+ + - + -
+ - + - +
- + - - +
+ - + - +
- + - + -
+ - - + +
- + - + -
+ - + - +
- + - - +
+ - + - +
- + - + -
+ - - + +
- ]
40 : : {
41 : 1 : SeedRandomForTest(SeedRand::ZEROS);
42 : 1 : CuckooCache::cache<uint256, SignatureCacheHasher> cc{};
43 [ + - ]: 1 : cc.setup_bytes(4_MiB);
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 bytes*load worth of entries are
54 : : * inserted into a bytes sized cache
55 : : */
56 : : template <typename Cache>
57 : 5 : double test_cache(size_t bytes, double load)
58 : : {
59 : 5 : SeedRandomForTest(SeedRand::ZEROS);
60 : 5 : std::vector<uint256> hashes;
61 [ + - ]: 5 : Cache set{};
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++) = m_rng.rand32();
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 : : }; // struct HitRateTest
108 : :
109 : : /** Check the hit rate on loads ranging from 0.1 to 1.6 */
110 [ + - + - : 7 : BOOST_FIXTURE_TEST_CASE(cuckoocache_hit_rate_ok, HitRateTest)
+ - + - -
+ + - + -
+ - + - +
- + - - +
+ - + - +
- + - + -
+ - - + +
- + - + -
+ - + - +
- + - - +
+ - + - +
- + - + -
+ - - + +
- ]
111 : : {
112 : : /** Arbitrarily selected Hit Rate threshold that happens to work for this test
113 : : * as a lower bound on performance.
114 : : */
115 : 1 : double HitRateThresh = 0.98;
116 [ + + ]: 6 : for (double load = 0.1; load < 2; load *= 2) {
117 : 5 : double hits = test_cache<CuckooCache::cache<uint256, SignatureCacheHasher>>(4_MiB, load);
118 [ + + + - ]: 11 : BOOST_CHECK(normalize_hit_rate(hits, load) > HitRateThresh);
119 : : }
120 : 1 : }
121 : :
122 : :
123 : 2 : struct EraseTest : BasicTestingSetup {
124 : : /** This helper checks that erased elements are preferentially inserted onto and
125 : : * that the hit rate of "fresher" keys is reasonable*/
126 : : template <typename Cache>
127 : 1 : void test_cache_erase(size_t bytes)
128 : : {
129 : 1 : double load = 1;
130 : 1 : SeedRandomForTest(SeedRand::ZEROS);
131 : 1 : std::vector<uint256> hashes;
132 [ + - ]: 1 : Cache set{};
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++) = m_rng.rand32();
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 : : }; // struct EraseTest
182 : :
183 [ + - + - : 7 : BOOST_FIXTURE_TEST_CASE(cuckoocache_erase_ok, EraseTest)
+ - + - -
+ + - + -
+ - + - +
- + - - +
+ - + - +
- + - + -
+ - - + +
- + - + -
+ - + - +
- + - - +
+ - + - +
- + - + -
+ - - + +
- ]
184 : : {
185 : 1 : test_cache_erase<CuckooCache::cache<uint256, SignatureCacheHasher>>(4_MiB);
186 : 1 : }
187 : :
188 : 2 : struct EraseParallelTest : BasicTestingSetup {
189 : : template <typename Cache>
190 : 1 : void test_cache_erase_parallel(size_t bytes)
191 : : {
192 : 1 : double load = 1;
193 : 1 : SeedRandomForTest(SeedRand::ZEROS);
194 : 1 : std::vector<uint256> hashes;
195 [ + - ]: 1 : Cache set{};
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++) = m_rng.rand32();
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 [ + - ]: 1 : threads.reserve(3);
223 : : /** Erase the first quarter */
224 [ + + ]: 4 : for (uint32_t x = 0; x < 3; ++x)
225 : : /** Each thread is emplaced with x copy-by-value
226 : : */
227 [ + - ]: 3 : threads.emplace_back([&, x] {
228 : 3 : std::shared_lock<std::shared_mutex> l(mtx);
229 : 3 : size_t ntodo = (n_insert/4)/3;
230 : 3 : size_t start = ntodo*x;
231 : 3 : size_t end = ntodo*(x+1);
232 [ + + ]: 32769 : for (uint32_t i = start; i < end; ++i) {
233 : 32766 : bool contains = set.contains(hashes[i], true);
234 [ - + ]: 32766 : assert(contains);
235 : : }
236 : 3 : });
237 : :
238 : : /** Wait for all threads to finish
239 : : */
240 [ + + ]: 4 : for (std::thread& t : threads)
241 [ + - ]: 3 : t.join();
242 : : /** Grab lock to make sure we observe erases */
243 : 1 : std::unique_lock<std::shared_mutex> l(mtx);
244 : : /** Insert the second half */
245 [ + + ]: 65537 : for (uint32_t i = (n_insert / 2); i < n_insert; ++i)
246 : 65536 : set.insert(hashes_insert_copy[i]);
247 : :
248 : : /** elements that we marked erased but that are still there */
249 : : size_t count_erased_but_contained = 0;
250 : : /** elements that we did not erase but are older */
251 : 32769 : size_t count_stale = 0;
252 : : /** elements that were most recently inserted */
253 : 32769 : size_t count_fresh = 0;
254 : :
255 [ + + ]: 32769 : for (uint32_t i = 0; i < (n_insert / 4); ++i)
256 : 32768 : count_erased_but_contained += set.contains(hashes[i], false);
257 [ + + ]: 32769 : for (uint32_t i = (n_insert / 4); i < (n_insert / 2); ++i)
258 : 32768 : count_stale += set.contains(hashes[i], false);
259 [ + + ]: 65537 : for (uint32_t i = (n_insert / 2); i < n_insert; ++i)
260 : 65536 : count_fresh += set.contains(hashes[i], false);
261 : :
262 : 1 : double hit_rate_erased_but_contained = double(count_erased_but_contained) / (double(n_insert) / 4.0);
263 : 1 : double hit_rate_stale = double(count_stale) / (double(n_insert) / 4.0);
264 : 1 : double hit_rate_fresh = double(count_fresh) / (double(n_insert) / 2.0);
265 : :
266 : : // Check that our hit_rate_fresh is perfect
267 [ + - + - ]: 1 : BOOST_CHECK_EQUAL(hit_rate_fresh, 1.0);
268 : : // Check that we have a more than 2x better hit rate on stale elements than
269 : : // erased elements.
270 [ + - + - : 2 : BOOST_CHECK(hit_rate_stale > 2 * hit_rate_erased_but_contained);
+ - ]
271 : 1 : }
272 : : }; // struct EraseParallelTest
273 [ + - + - : 7 : BOOST_FIXTURE_TEST_CASE(cuckoocache_erase_parallel_ok, EraseParallelTest)
+ - + - -
+ + - + -
+ - + - +
- + - - +
+ - + - +
- + - + -
+ - - + +
- + - + -
+ - + - +
- + - - +
+ - + - +
- + - + -
+ - - + +
- ]
274 : : {
275 : 1 : test_cache_erase_parallel<CuckooCache::cache<uint256, SignatureCacheHasher>>(4_MiB);
276 : 1 : }
277 : :
278 : :
279 : 2 : struct GenerationsTest : BasicTestingSetup {
280 : : template <typename Cache>
281 : 1 : void test_cache_generations()
282 : : {
283 : : // This test checks that for a simulation of network activity, the fresh hit
284 : : // rate is never below 99%, and the number of times that it is worse than
285 : : // 99.9% are less than 1% of the time.
286 : 1 : double min_hit_rate = 0.99;
287 : 1 : double tight_hit_rate = 0.999;
288 : 1 : double max_rate_less_than_tight_hit_rate = 0.01;
289 : : // A cache that meets this specification is therefore shown to have a hit
290 : : // rate of at least tight_hit_rate * (1 - max_rate_less_than_tight_hit_rate) +
291 : : // min_hit_rate*max_rate_less_than_tight_hit_rate = 0.999*99%+0.99*1% == 99.89%
292 : : // hit rate with low variance.
293 : :
294 : : // We use deterministic values, but this test has also passed on many
295 : : // iterations with non-deterministic values, so it isn't "overfit" to the
296 : : // specific entropy in FastRandomContext(true) and implementation of the
297 : : // cache.
298 : 1 : SeedRandomForTest(SeedRand::ZEROS);
299 : :
300 : : // block_activity models a chunk of network activity. n_insert elements are
301 : : // added to the cache. The first and last n/4 are stored for removal later
302 : : // and the middle n/2 are not stored. This models a network which uses half
303 : : // the signatures of recently (since the last block) added transactions
304 : : // immediately and never uses the other half.
305 : 1310 : struct block_activity {
306 : : std::vector<uint256> reads;
307 : 1310 : block_activity(uint32_t n_insert, FastRandomContext& rng, Cache& c)
308 [ + - ]: 1310 : {
309 : 1310 : std::vector<uint256> inserts;
310 [ + - ]: 1310 : inserts.resize(n_insert);
311 [ + - ]: 1310 : reads.reserve(n_insert / 2);
312 [ + + ]: 1311310 : for (uint32_t i = 0; i < n_insert; ++i) {
313 : 1310000 : uint32_t* ptr = (uint32_t*)inserts[i].begin();
314 [ + + ]: 11790000 : for (uint8_t j = 0; j < 8; ++j)
315 : 10480000 : *(ptr++) = rng.rand32();
316 : : }
317 [ + + ]: 328810 : for (uint32_t i = 0; i < n_insert / 4; ++i)
318 [ + - ]: 327500 : reads.push_back(inserts[i]);
319 [ + + ]: 328810 : for (uint32_t i = n_insert - (n_insert / 4); i < n_insert; ++i)
320 [ + - ]: 327500 : reads.push_back(inserts[i]);
321 [ + + ]: 1311310 : for (const auto& h : inserts)
322 : 1310000 : c.insert(h);
323 : 1310 : }
324 : : };
325 : :
326 : 1 : const uint32_t BLOCK_SIZE = 1000;
327 : : // We expect window size 60 to perform reasonably given that each epoch
328 : : // stores 45% of the cache size (~472k).
329 : 1 : const uint32_t WINDOW_SIZE = 60;
330 : 1 : const uint32_t POP_AMOUNT = (BLOCK_SIZE / WINDOW_SIZE) / 2;
331 : 1 : const double load = 10;
332 : 1 : const size_t bytes{4_MiB};
333 : 1 : const uint32_t n_insert = static_cast<uint32_t>(load * (bytes / sizeof(uint256)));
334 : :
335 : 1 : std::vector<block_activity> hashes;
336 [ + - ]: 1 : Cache set{};
337 [ + - ]: 1 : set.setup_bytes(bytes);
338 [ + - ]: 1 : hashes.reserve(n_insert / BLOCK_SIZE);
339 : 1311 : std::deque<block_activity> last_few;
340 : : uint32_t out_of_tight_tolerance = 0;
341 : : uint32_t total = n_insert / BLOCK_SIZE;
342 : : // we use the deque last_few to model a sliding window of blocks. at each
343 : : // step, each of the last WINDOW_SIZE block_activities checks the cache for
344 : : // POP_AMOUNT of the hashes that they inserted, and marks these erased.
345 [ + + ]: 1311 : for (uint32_t i = 0; i < total; ++i) {
346 [ + + ]: 1310 : if (last_few.size() == WINDOW_SIZE)
347 : 1250 : last_few.pop_front();
348 [ + - ]: 1310 : last_few.emplace_back(BLOCK_SIZE, m_rng, set);
349 : 1310 : uint32_t count = 0;
350 [ + + ]: 78140 : for (auto& act : last_few)
351 [ + + ]: 691470 : for (uint32_t k = 0; k < POP_AMOUNT; ++k) {
352 : 614640 : count += set.contains(act.reads.back(), true);
353 : 614640 : act.reads.pop_back();
354 : : }
355 : : // We use last_few.size() rather than WINDOW_SIZE for the correct
356 : : // behavior on the first WINDOW_SIZE iterations where the deque is not
357 : : // full yet.
358 [ - + ]: 1310 : double hit = (double(count)) / (last_few.size() * POP_AMOUNT);
359 : : // Loose Check that hit rate is above min_hit_rate
360 [ + - + - ]: 2620 : BOOST_CHECK(hit > min_hit_rate);
361 : : // Tighter check, count number of times we are less than tight_hit_rate
362 : : // (and implicitly, greater than min_hit_rate)
363 : 1310 : out_of_tight_tolerance += hit < tight_hit_rate;
364 : : }
365 : : // Check that being out of tolerance happens less than
366 : : // max_rate_less_than_tight_hit_rate of the time
367 [ + - + - ]: 2 : BOOST_CHECK(double(out_of_tight_tolerance) / double(total) < max_rate_less_than_tight_hit_rate);
368 : 1 : }
369 : : }; // struct GenerationsTest
370 [ + - + - : 7 : BOOST_FIXTURE_TEST_CASE(cuckoocache_generations, GenerationsTest)
+ - + - -
+ + - + -
+ - + - +
- + - - +
+ - + - +
- + - + -
+ - - + +
- + - + -
+ - + - +
- + - - +
+ - + - +
- + - + -
+ - - + +
- ]
371 : : {
372 : 1 : test_cache_generations<CuckooCache::cache<uint256, SignatureCacheHasher>>();
373 : 1 : }
374 : :
375 : : BOOST_AUTO_TEST_SUITE_END();
|
