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  * Authors: Daniel Carvalho
  30  */
  31
  32 #ifndef __BASE_FILTERS_BASE_HH__
  33 #define __BASE_FILTERS_BASE_HH__
  34
  35 #include <vector>
  36
  37 #include "base/intmath.hh"
  38 #include "base/sat_counter.hh"
  39 #include "base/types.hh"
  40 #include "params/BloomFilterBase.hh"
  41 #include "sim/sim_object.hh"
  42
  43 namespace BloomFilter {
  44
  45 class Base : public SimObject
  46 {
  47   protected:
  48     /** Number of LSB bits to ignore from the the addresses. */
  49     const unsigned offsetBits;
  50
  51     /** The filter itself. */
  52     std::vector<SatCounter> filter;
  53
  54     /** Number of bits needed to represent the size of the filter. */
  55     const int sizeBits;
  56
  57     /** Threshold at which a filter entry starts being considered as set. */
  58     const int setThreshold;
  59
  60   public:
  61     /**
  62      * Create and clear the filter.
  63      */
  64     Base(const BloomFilterBaseParams* p)
  65         : SimObject(p), offsetBits(p->offset_bits),
  66           filter(p->size, SatCounter(p->num_bits)),
  67           sizeBits(floorLog2(p->size)), setThreshold(p->threshold)
  68     {
  69         clear();
  70     }
  71     virtual ~Base() {};
  72
  73     /**
  74      * Clear the filter by resetting all values.
  75      */
  76     virtual void clear()
  77     {
  78         for (auto& entry : filter) {
  79             entry.reset();
  80         }
  81     }
  82
  83     /**
  84      * Merges the contents of both filters into this' (Bloom Filter union).
  85      * Both must have the same number of entries.
  86      *
  87      * @param other The other bloom filter to merge with.
  88      */
  89     virtual void
  90     merge(const Base* other)
  91     {
  92         assert(filter.size() == other->filter.size());
  93         for (int i = 0; i < filter.size(); ++i){
  94             filter[i] += other->filter[i];
  95         }
  96     }
  97
  98     /**
  99      * Perform the filter specific function to set the corresponding
 100      * entries (can be multiple) of an address.
 101      *
 102      * @param addr The address being parsed.
 103      */
 104     virtual void set(Addr addr) = 0;
 105
 106     /**
 107      * Perform the filter specific function to clear the corresponding
 108      * entries (can be multiple) of an address. By default a bloom
 109      * filter does not support element deletion.
 110      *
 111      * @param addr The address being parsed.
 112      */
 113     virtual void unset(Addr addr) {};
 114
 115     /**
 116      * Check if the corresponding filter entries of an address should be
 117      * considered as set.
 118      *
 119      * @param addr The address being parsed.
 120      * @return Whether the respective filter entry is set.
 121      */
 122     virtual bool
 123     isSet(Addr addr) const
 124     {
 125         return getCount(addr) >= setThreshold;
 126     }
 127
 128     /**
 129      * Get the value stored in the corresponding filter entry of an address.
 130      *
 131      * @param addr The address being parsed.
 132      * @param Get the value stored in the respective filter entry.
 133      */
 134     virtual int getCount(Addr addr) const { return 0; }
 135
 136     /**
 137      * Get the total value stored in the filter entries.
 138      *
 139      * @return The sum of all filter entries.
 140      */
 141     virtual int getTotalCount() const
 142     {
 143         int count = 0;
 144         for (const auto& entry : filter) {
 145             count += entry;
 146         }
 147         return count;
 148     }
 149 };
 150
 151 } // namespace BloomFilter
 152
 153 #endif // __BASE_FILTERS_BASE_HH__