src/base/filters/base.hh

   1 /*
   2  * Copyright (c) 2019 Inria
   3  * Copyright (c) 1999-2008 Mark D. Hill and David A. Wood
   4  * All rights reserved.
   5  *
   6  * Redistribution and use in source and binary forms, with or without
   7  * modification, are permitted provided that the following conditions are
   8  * met: redistributions of source code must retain the above copyright
   9  * notice, this list of conditions and the following disclaimer;
  10  * redistributions in binary form must reproduce the above copyright
  11  * notice, this list of conditions and the following disclaimer in the
  12  * documentation and/or other materials provided with the distribution;
  13  * neither the name of the copyright holders nor the names of its
  14  * contributors may be used to endorse or promote products derived from
  15  * this software without specific prior written permission.
  16  *
  17  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  18  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  19  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
  20  * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
  21  * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  22  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
  23  * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  24  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  25  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  26  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  27  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  28  */
  29
  30 #ifndef __BASE_FILTERS_BASE_HH__
  31 #define __BASE_FILTERS_BASE_HH__
  32
  33 #include <vector>
  34
  35 #include "base/intmath.hh"
  36 #include "base/sat_counter.hh"
  37 #include "base/types.hh"
  38 #include "params/BloomFilterBase.hh"
  39 #include "sim/sim_object.hh"
  40
  41 namespace BloomFilter {
  42
  43 class Base : public SimObject
  44 {
  45   protected:
  46     /** Number of LSB bits to ignore from the the addresses. */
  47     const unsigned offsetBits;
  48
  49     /** The filter itself. */
  50     std::vector<SatCounter> filter;
  51
  52     /** Number of bits needed to represent the size of the filter. */
  53     const int sizeBits;
  54
  55     /** Threshold at which a filter entry starts being considered as set. */
  56     const int setThreshold;
  57
  58   public:
  59     /**
  60      * Create and clear the filter.
  61      */
  62     Base(const BloomFilterBaseParams &p)
  63         : SimObject(p), offsetBits(p.offset_bits),
  64           filter(p.size, SatCounter(p.num_bits)),
  65           sizeBits(floorLog2(p.size)), setThreshold(p.threshold)
  66     {
  67         clear();
  68     }
  69     virtual ~Base() {};
  70
  71     /**
  72      * Clear the filter by resetting all values.
  73      */
  74     virtual void clear()
  75     {
  76         for (auto& entry : filter) {
  77             entry.reset();
  78         }
  79     }
  80
  81     /**
  82      * Merges the contents of both filters into this' (Bloom Filter union).
  83      * Both must have the same number of entries.
  84      *
  85      * @param other The other bloom filter to merge with.
  86      */
  87     virtual void
  88     merge(const Base* other)
  89     {
  90         assert(filter.size() == other->filter.size());
  91         for (int i = 0; i < filter.size(); ++i){
  92             filter[i] += other->filter[i];
  93         }
  94     }
  95
  96     /**
  97      * Perform the filter specific function to set the corresponding
  98      * entries (can be multiple) of an address.
  99      *
 100      * @param addr The address being parsed.
 101      */
 102     virtual void set(Addr addr) = 0;
 103
 104     /**
 105      * Perform the filter specific function to clear the corresponding
 106      * entries (can be multiple) of an address. By default a bloom
 107      * filter does not support element deletion.
 108      *
 109      * @param addr The address being parsed.
 110      */
 111     virtual void unset(Addr addr) {};
 112
 113     /**
 114      * Check if the corresponding filter entries of an address should be
 115      * considered as set.
 116      *
 117      * @param addr The address being parsed.
 118      * @return Whether the respective filter entry is set.
 119      */
 120     virtual bool
 121     isSet(Addr addr) const
 122     {
 123         return getCount(addr) >= setThreshold;
 124     }
 125
 126     /**
 127      * Get the value stored in the corresponding filter entry of an address.
 128      *
 129      * @param addr The address being parsed.
 130      * @param Get the value stored in the respective filter entry.
 131      */
 132     virtual int getCount(Addr addr) const { return 0; }
 133
 134     /**
 135      * Get the total value stored in the filter entries.
 136      *
 137      * @return The sum of all filter entries.
 138      */
 139     virtual int getTotalCount() const
 140     {
 141         int count = 0;
 142         for (const auto& entry : filter) {
 143             count += entry;
 144         }
 145         return count;
 146     }
 147 };
 148
 149 } // namespace BloomFilter
 150
 151 #endif // __BASE_FILTERS_BASE_HH__