summaryrefslogtreecommitdiffstats
path: root/src/test/osd/hitset.cc
diff options
context:
space:
mode:
Diffstat (limited to '')
-rw-r--r--src/test/osd/hitset.cc197
1 files changed, 197 insertions, 0 deletions
diff --git a/src/test/osd/hitset.cc b/src/test/osd/hitset.cc
new file mode 100644
index 000000000..6234bdaba
--- /dev/null
+++ b/src/test/osd/hitset.cc
@@ -0,0 +1,197 @@
+// -*- mode:C++; tab-width:8; c-basic-offset:2; indent-tabs-mode:t -*-
+// vim: ts=8 sw=2 smarttab
+/*
+ * Ceph - scalable distributed file system
+ *
+ * This is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License version 2.1, as published by the Free Software
+ * Foundation. See file COPYING.
+ * Copyright 2013 Inktank
+ */
+
+#include "gtest/gtest.h"
+#include "osd/HitSet.h"
+#include <iostream>
+
+class HitSetTestStrap {
+public:
+ HitSet *hitset;
+
+ explicit HitSetTestStrap(HitSet *h) : hitset(h) {}
+
+ void fill(unsigned count) {
+ char buf[50];
+ for (unsigned i = 0; i < count; ++i) {
+ sprintf(buf, "hitsettest_%u", i);
+ hobject_t obj(object_t(buf), "", 0, i, 0, "");
+ hitset->insert(obj);
+ }
+ EXPECT_EQ(count, hitset->insert_count());
+ }
+ void verify_fill(unsigned count) {
+ char buf[50];
+ for (unsigned i = 0; i < count; ++i) {
+ sprintf(buf, "hitsettest_%u", i);
+ hobject_t obj(object_t(buf), "", 0, i, 0, "");
+ EXPECT_TRUE(hitset->contains(obj));
+ }
+ }
+
+};
+
+class BloomHitSetTest : public testing::Test, public HitSetTestStrap {
+public:
+
+ BloomHitSetTest() : HitSetTestStrap(new HitSet(new BloomHitSet)) {}
+
+ void rebuild(double fp, uint64_t target, uint64_t seed) {
+ BloomHitSet::Params *bparams = new BloomHitSet::Params(fp, target, seed);
+ HitSet::Params param(bparams);
+ HitSet new_set(param);
+ *hitset = new_set;
+ }
+
+ BloomHitSet *get_hitset() { return static_cast<BloomHitSet*>(hitset->impl.get()); }
+};
+
+TEST_F(BloomHitSetTest, Params) {
+ BloomHitSet::Params params(0.01, 100, 5);
+ EXPECT_EQ(.01, params.get_fpp());
+ EXPECT_EQ((unsigned)100, params.target_size);
+ EXPECT_EQ((unsigned)5, params.seed);
+ params.set_fpp(0.1);
+ EXPECT_EQ(0.1, params.get_fpp());
+
+ bufferlist bl;
+ params.encode(bl);
+ BloomHitSet::Params p2;
+ auto iter = bl.cbegin();
+ p2.decode(iter);
+ EXPECT_EQ(0.1, p2.get_fpp());
+ EXPECT_EQ((unsigned)100, p2.target_size);
+ EXPECT_EQ((unsigned)5, p2.seed);
+}
+
+TEST_F(BloomHitSetTest, Construct) {
+ ASSERT_EQ(hitset->impl->get_type(), HitSet::TYPE_BLOOM);
+ // success!
+}
+
+TEST_F(BloomHitSetTest, Rebuild) {
+ rebuild(0.1, 100, 1);
+ ASSERT_EQ(hitset->impl->get_type(), HitSet::TYPE_BLOOM);
+}
+
+TEST_F(BloomHitSetTest, InsertsMatch) {
+ rebuild(0.1, 100, 1);
+ fill(50);
+ /*
+ * the approx unique count is atrocious on bloom filters. Empirical
+ * evidence suggests the current test will produce a value of 62
+ * regardless of hitset size
+ */
+ EXPECT_TRUE(hitset->approx_unique_insert_count() >= 50 &&
+ hitset->approx_unique_insert_count() <= 62);
+ verify_fill(50);
+ EXPECT_FALSE(hitset->is_full());
+}
+
+TEST_F(BloomHitSetTest, FillsUp) {
+ rebuild(0.1, 20, 1);
+ fill(20);
+ verify_fill(20);
+ EXPECT_TRUE(hitset->is_full());
+}
+
+TEST_F(BloomHitSetTest, RejectsNoMatch) {
+ rebuild(0.001, 100, 1);
+ fill(100);
+ verify_fill(100);
+ EXPECT_TRUE(hitset->is_full());
+
+ char buf[50];
+ int matches = 0;
+ for (int i = 100; i < 200; ++i) {
+ sprintf(buf, "hitsettest_%d", i);
+ hobject_t obj(object_t(buf), "", 0, i, 0, "");
+ if (hitset->contains(obj))
+ ++matches;
+ }
+ // we set a 1 in 1000 false positive; allow one in our 100
+ EXPECT_LT(matches, 2);
+}
+
+class ExplicitHashHitSetTest : public testing::Test, public HitSetTestStrap {
+public:
+
+ ExplicitHashHitSetTest() : HitSetTestStrap(new HitSet(new ExplicitHashHitSet)) {}
+
+ ExplicitHashHitSet *get_hitset() { return static_cast<ExplicitHashHitSet*>(hitset->impl.get()); }
+};
+
+TEST_F(ExplicitHashHitSetTest, Construct) {
+ ASSERT_EQ(hitset->impl->get_type(), HitSet::TYPE_EXPLICIT_HASH);
+ // success!
+}
+
+TEST_F(ExplicitHashHitSetTest, InsertsMatch) {
+ fill(50);
+ verify_fill(50);
+ EXPECT_EQ((unsigned)50, hitset->approx_unique_insert_count());
+ EXPECT_FALSE(hitset->is_full());
+}
+
+TEST_F(ExplicitHashHitSetTest, RejectsNoMatch) {
+ fill(100);
+ verify_fill(100);
+ EXPECT_FALSE(hitset->is_full());
+
+ char buf[50];
+ int matches = 0;
+ for (int i = 100; i < 200; ++i) {
+ sprintf(buf, "hitsettest_%d", i);
+ hobject_t obj(object_t(buf), "", 0, i, 0, "");
+ if (hitset->contains(obj)) {
+ ++matches;
+ }
+ }
+ EXPECT_EQ(matches, 0);
+}
+
+class ExplicitObjectHitSetTest : public testing::Test, public HitSetTestStrap {
+public:
+
+ ExplicitObjectHitSetTest() : HitSetTestStrap(new HitSet(new ExplicitObjectHitSet)) {}
+
+ ExplicitObjectHitSet *get_hitset() { return static_cast<ExplicitObjectHitSet*>(hitset->impl.get()); }
+};
+
+TEST_F(ExplicitObjectHitSetTest, Construct) {
+ ASSERT_EQ(hitset->impl->get_type(), HitSet::TYPE_EXPLICIT_OBJECT);
+ // success!
+}
+
+TEST_F(ExplicitObjectHitSetTest, InsertsMatch) {
+ fill(50);
+ verify_fill(50);
+ EXPECT_EQ((unsigned)50, hitset->approx_unique_insert_count());
+ EXPECT_FALSE(hitset->is_full());
+}
+
+TEST_F(ExplicitObjectHitSetTest, RejectsNoMatch) {
+ fill(100);
+ verify_fill(100);
+ EXPECT_FALSE(hitset->is_full());
+
+ char buf[50];
+ int matches = 0;
+ for (int i = 100; i < 200; ++i) {
+ sprintf(buf, "hitsettest_%d", i);
+ hobject_t obj(object_t(buf), "", 0, i, 0, "");
+ if (hitset->contains(obj)) {
+ ++matches;
+ }
+ }
+ EXPECT_EQ(matches, 0);
+}