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
43namespace BloomFilter {
44
45class 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__
154