src/ceph/src/test/osd/hitset.cc

   1 // -*- mode:C++; tab-width:8; c-basic-offset:2; indent-tabs-mode:t -*-
   2 // vim: ts=8 sw=2 smarttab
   3 /*
   4  * Ceph - scalable distributed file system
   5  *
   6  * This is free software; you can redistribute it and/or
   7  * modify it under the terms of the GNU Lesser General Public
   8  * License version 2.1, as published by the Free Software
   9  * Foundation.  See file COPYING.
  10  * Copyright 2013 Inktank
  11  */
  12
  13 #include "gtest/gtest.h"
  14 #include "osd/HitSet.h"
  15 #include <iostream>
  16
  17 class HitSetTestStrap {
  18 public:
  19   HitSet *hitset;
  20
  21   explicit HitSetTestStrap(HitSet *h) : hitset(h) {}
  22
  23   void fill(unsigned count) {
  24     char buf[50];
  25     for (unsigned i = 0; i < count; ++i) {
  26       sprintf(buf, "hitsettest_%u", i);
  27       hobject_t obj(object_t(buf), "", 0, i, 0, "");
  28       hitset->insert(obj);
  29     }
  30     EXPECT_EQ(count, hitset->insert_count());
  31   }
  32   void verify_fill(unsigned count) {
  33     char buf[50];
  34     for (unsigned i = 0; i < count; ++i) {
  35       sprintf(buf, "hitsettest_%u", i);
  36       hobject_t obj(object_t(buf), "", 0, i, 0, "");
  37       EXPECT_TRUE(hitset->contains(obj));
  38     }
  39   }
  40
  41 };
  42
  43 class BloomHitSetTest : public testing::Test, public HitSetTestStrap {
  44 public:
  45
  46   BloomHitSetTest() : HitSetTestStrap(new HitSet(new BloomHitSet)) {}
  47
  48   void rebuild(double fp, uint64_t target, uint64_t seed) {
  49     BloomHitSet::Params *bparams = new BloomHitSet::Params(fp, target, seed);
  50     HitSet::Params param(bparams);
  51     HitSet new_set(param);
  52     *hitset = new_set;
  53   }
  54
  55   BloomHitSet *get_hitset() { return static_cast<BloomHitSet*>(hitset->impl.get()); }
  56 };
  57
  58 TEST_F(BloomHitSetTest, Params) {
  59   BloomHitSet::Params params(0.01, 100, 5);
  60   EXPECT_EQ(.01, params.get_fpp());
  61   EXPECT_EQ((unsigned)100, params.target_size);
  62   EXPECT_EQ((unsigned)5, params.seed);
  63   params.set_fpp(0.1);
  64   EXPECT_EQ(0.1, params.get_fpp());
  65
  66   bufferlist bl;
  67   params.encode(bl);
  68   BloomHitSet::Params p2;
  69   bufferlist::iterator iter = bl.begin();
  70   p2.decode(iter);
  71   EXPECT_EQ(0.1, p2.get_fpp());
  72   EXPECT_EQ((unsigned)100, p2.target_size);
  73   EXPECT_EQ((unsigned)5, p2.seed);
  74 }
  75
  76 TEST_F(BloomHitSetTest, Construct) {
  77   ASSERT_EQ(hitset->impl->get_type(), HitSet::TYPE_BLOOM);
  78   // success!
  79 }
  80
  81 TEST_F(BloomHitSetTest, Rebuild) {
  82   rebuild(0.1, 100, 1);
  83   ASSERT_EQ(hitset->impl->get_type(), HitSet::TYPE_BLOOM);
  84 }
  85
  86 TEST_F(BloomHitSetTest, InsertsMatch) {
  87   rebuild(0.1, 100, 1);
  88   fill(50);
  89   /*
  90    *  the approx unique count is atrocious on bloom filters. Empirical
  91    *  evidence suggests the current test will produce a value of 62
  92    *  regardless of hitset size
  93    */
  94   EXPECT_TRUE(hitset->approx_unique_insert_count() >= 50 &&
  95               hitset->approx_unique_insert_count() <= 62);
  96   verify_fill(50);
  97   EXPECT_FALSE(hitset->is_full());
  98 }
  99
 100 TEST_F(BloomHitSetTest, FillsUp) {
 101   rebuild(0.1, 20, 1);
 102   fill(20);
 103   verify_fill(20);
 104   EXPECT_TRUE(hitset->is_full());
 105 }
 106
 107 TEST_F(BloomHitSetTest, RejectsNoMatch) {
 108   rebuild(0.001, 100, 1);
 109   fill(100);
 110   verify_fill(100);
 111   EXPECT_TRUE(hitset->is_full());
 112
 113   char buf[50];
 114   int matches = 0;
 115   for (int i = 100; i < 200; ++i) {
 116     sprintf(buf, "hitsettest_%d", i);
 117     hobject_t obj(object_t(buf), "", 0, i, 0, "");
 118     if (hitset->contains(obj))
 119       ++matches;
 120   }
 121   // we set a 1 in 1000 false positive; allow one in our 100
 122   EXPECT_LT(matches, 2);
 123 }
 124
 125 class ExplicitHashHitSetTest : public testing::Test, public HitSetTestStrap {
 126 public:
 127
 128   ExplicitHashHitSetTest() : HitSetTestStrap(new HitSet(new ExplicitHashHitSet)) {}
 129
 130   ExplicitHashHitSet *get_hitset() { return static_cast<ExplicitHashHitSet*>(hitset->impl.get()); }
 131 };
 132
 133 TEST_F(ExplicitHashHitSetTest, Construct) {
 134   ASSERT_EQ(hitset->impl->get_type(), HitSet::TYPE_EXPLICIT_HASH);
 135   // success!
 136 }
 137
 138 TEST_F(ExplicitHashHitSetTest, InsertsMatch) {
 139   fill(50);
 140   verify_fill(50);
 141   EXPECT_EQ((unsigned)50, hitset->approx_unique_insert_count());
 142   EXPECT_FALSE(hitset->is_full());
 143 }
 144
 145 TEST_F(ExplicitHashHitSetTest, RejectsNoMatch) {
 146   fill(100);
 147   verify_fill(100);
 148   EXPECT_FALSE(hitset->is_full());
 149
 150   char buf[50];
 151   int matches = 0;
 152   for (int i = 100; i < 200; ++i) {
 153     sprintf(buf, "hitsettest_%d", i);
 154     hobject_t obj(object_t(buf), "", 0, i, 0, "");
 155     if (hitset->contains(obj)) {
 156       ++matches;
 157     }
 158   }
 159   EXPECT_EQ(matches, 0);
 160 }
 161
 162 class ExplicitObjectHitSetTest : public testing::Test, public HitSetTestStrap {
 163 public:
 164
 165   ExplicitObjectHitSetTest() : HitSetTestStrap(new HitSet(new ExplicitObjectHitSet)) {}
 166
 167   ExplicitObjectHitSet *get_hitset() { return static_cast<ExplicitObjectHitSet*>(hitset->impl.get()); }
 168 };
 169
 170 TEST_F(ExplicitObjectHitSetTest, Construct) {
 171   ASSERT_EQ(hitset->impl->get_type(), HitSet::TYPE_EXPLICIT_OBJECT);
 172   // success!
 173 }
 174
 175 TEST_F(ExplicitObjectHitSetTest, InsertsMatch) {
 176   fill(50);
 177   verify_fill(50);
 178   EXPECT_EQ((unsigned)50, hitset->approx_unique_insert_count());
 179   EXPECT_FALSE(hitset->is_full());
 180 }
 181
 182 TEST_F(ExplicitObjectHitSetTest, RejectsNoMatch) {
 183   fill(100);
 184   verify_fill(100);
 185   EXPECT_FALSE(hitset->is_full());
 186
 187   char buf[50];
 188   int matches = 0;
 189   for (int i = 100; i < 200; ++i) {
 190     sprintf(buf, "hitsettest_%d", i);
 191     hobject_t obj(object_t(buf), "", 0, i, 0, "");
 192     if (hitset->contains(obj)) {
 193       ++matches;
 194     }
 195   }
 196   EXPECT_EQ(matches, 0);
 197 }