Page MenuHomePhabricator
Differential D4510 Diff 14328 src/test/bloom_tests.cpp

Changeset View

Standalone View

View Options

src/test/bloom_tests.cpp

Show First 20 Lines • Show All 1,189 Lines • ▼ Show 20 Lines
} }
static std::vector<uint8_t> RandomData() { static std::vector<uint8_t> RandomData() {
uint256 r = InsecureRand256(); uint256 r = InsecureRand256();
return std::vector<uint8_t>(r.begin(), r.end()); return std::vector<uint8_t>(r.begin(), r.end());
} }
BOOST_AUTO_TEST_CASE(rolling_bloom) { BOOST_AUTO_TEST_CASE(rolling_bloom) {
SeedInsecureRand(/* deterministic */ true);
g_mock_deterministic_tests = true;
// last-100-entry, 1% false positive: // last-100-entry, 1% false positive:
CRollingBloomFilter rb1(100, 0.01); CRollingBloomFilter rb1(100, 0.01);
// Overfill: // Overfill:
static const int DATASIZE = 399; static const int DATASIZE = 399;
std::vector<uint8_t> data[DATASIZE]; std::vector<uint8_t> data[DATASIZE];
for (int i = 0; i < DATASIZE; i++) { for (int i = 0; i < DATASIZE; i++) {
data[i] = RandomData(); data[i] = RandomData();
rb1.insert(data[i]); rb1.insert(data[i]);
} }
// Last 100 guaranteed to be remembered: // Last 100 guaranteed to be remembered:
for (int i = 299; i < DATASIZE; i++) { for (int i = 299; i < DATASIZE; i++) {
BOOST_CHECK(rb1.contains(data[i])); BOOST_CHECK(rb1.contains(data[i]));
} }
// false positive rate is 1%, so we should get about 100 hits if // false positive rate is 1%, so we should get about 100 hits if
// testing 10,000 random keys. We get worst-case false positive // testing 10,000 random keys. We get worst-case false positive
// behavior when the filter is as full as possible, which is // behavior when the filter is as full as possible, which is
// when we've inserted one minus an integer multiple of nElement*2. // when we've inserted one minus an integer multiple of nElement*2.
unsigned int nHits = 0; unsigned int nHits = 0;
for (int i = 0; i < 10000; i++) { for (int i = 0; i < 10000; i++) {
if (rb1.contains(RandomData())) ++nHits; if (rb1.contains(RandomData())) ++nHits;
} }
// Run test_bitcoin with --log_level=message to see BOOST_TEST_MESSAGEs: // Expect about 100 hits
BOOST_TEST_MESSAGE("RollingBloomFilter got " BOOST_CHECK_EQUAL(nHits, 75);
<< nHits << " false positives (~100 expected)");
// Insanely unlikely to get a fp count outside this range:
BOOST_CHECK(nHits > 25);
BOOST_CHECK(nHits < 175);
BOOST_CHECK(rb1.contains(data[DATASIZE - 1])); BOOST_CHECK(rb1.contains(data[DATASIZE - 1]));
rb1.reset(); rb1.reset();
BOOST_CHECK(!rb1.contains(data[DATASIZE - 1])); BOOST_CHECK(!rb1.contains(data[DATASIZE - 1]));
// Now roll through data, make sure last 100 entries // Now roll through data, make sure last 100 entries
// are always remembered: // are always remembered:
for (int i = 0; i < DATASIZE; i++) { for (int i = 0; i < DATASIZE; i++) {
if (i >= 100) BOOST_CHECK(rb1.contains(data[i - 100])); if (i >= 100) BOOST_CHECK(rb1.contains(data[i - 100]));
rb1.insert(data[i]); rb1.insert(data[i]);
BOOST_CHECK(rb1.contains(data[i])); BOOST_CHECK(rb1.contains(data[i]));
} }
// Insert 999 more random entries: // Insert 999 more random entries:
for (int i = 0; i < 999; i++) { for (int i = 0; i < 999; i++) {
std::vector<uint8_t> d = RandomData(); std::vector<uint8_t> d = RandomData();
rb1.insert(d); rb1.insert(d);
BOOST_CHECK(rb1.contains(d)); BOOST_CHECK(rb1.contains(d));
} }
// Sanity check to make sure the filter isn't just filling up: // Sanity check to make sure the filter isn't just filling up:
nHits = 0; nHits = 0;
for (int i = 0; i < DATASIZE; i++) { for (int i = 0; i < DATASIZE; i++) {
if (rb1.contains(data[i])) ++nHits; if (rb1.contains(data[i])) ++nHits;
} }
// Expect about 5 false positives, more than 100 means // Expect about 5 false positives
// something is definitely broken. BOOST_CHECK_EQUAL(nHits, 6);
BOOST_TEST_MESSAGE("RollingBloomFilter got "
<< nHits << " false positives (~5 expected)");
BOOST_CHECK(nHits < 100);
// last-1000-entry, 0.01% false positive: // last-1000-entry, 0.01% false positive:
CRollingBloomFilter rb2(1000, 0.001); CRollingBloomFilter rb2(1000, 0.001);
for (int i = 0; i < DATASIZE; i++) { for (int i = 0; i < DATASIZE; i++) {
rb2.insert(data[i]); rb2.insert(data[i]);
} }
// ... room for all of them: // ... room for all of them:
for (int i = 0; i < DATASIZE; i++) { for (int i = 0; i < DATASIZE; i++) {
BOOST_CHECK(rb2.contains(data[i])); BOOST_CHECK(rb2.contains(data[i]));
} }
g_mock_deterministic_tests = false;
} }
BOOST_AUTO_TEST_SUITE_END() BOOST_AUTO_TEST_SUITE_END()