114262Sodanrc@yahoo.com.br/* 214262Sodanrc@yahoo.com.br * Copyright (c) 2019 Inria 314262Sodanrc@yahoo.com.br * Copyright (c) 1999-2008 Mark D. Hill and David A. Wood 414262Sodanrc@yahoo.com.br * All rights reserved. 514262Sodanrc@yahoo.com.br * 614262Sodanrc@yahoo.com.br * Redistribution and use in source and binary forms, with or without 714262Sodanrc@yahoo.com.br * modification, are permitted provided that the following conditions are 814262Sodanrc@yahoo.com.br * met: redistributions of source code must retain the above copyright 914262Sodanrc@yahoo.com.br * notice, this list of conditions and the following disclaimer; 1014262Sodanrc@yahoo.com.br * redistributions in binary form must reproduce the above copyright 1114262Sodanrc@yahoo.com.br * notice, this list of conditions and the following disclaimer in the 1214262Sodanrc@yahoo.com.br * documentation and/or other materials provided with the distribution; 1314262Sodanrc@yahoo.com.br * neither the name of the copyright holders nor the names of its 1414262Sodanrc@yahoo.com.br * contributors may be used to endorse or promote products derived from 1514262Sodanrc@yahoo.com.br * this software without specific prior written permission. 1614262Sodanrc@yahoo.com.br * 1714262Sodanrc@yahoo.com.br * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 1814262Sodanrc@yahoo.com.br * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 1914262Sodanrc@yahoo.com.br * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 2014262Sodanrc@yahoo.com.br * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 2114262Sodanrc@yahoo.com.br * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 2214262Sodanrc@yahoo.com.br * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 2314262Sodanrc@yahoo.com.br * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 2414262Sodanrc@yahoo.com.br * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 2514262Sodanrc@yahoo.com.br * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 2614262Sodanrc@yahoo.com.br * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 2714262Sodanrc@yahoo.com.br * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 2814262Sodanrc@yahoo.com.br * 2914262Sodanrc@yahoo.com.br * Authors: Daniel Carvalho 3014262Sodanrc@yahoo.com.br */ 3114262Sodanrc@yahoo.com.br 3214262Sodanrc@yahoo.com.br#ifndef __BASE_FILTERS_BASE_HH__ 3314262Sodanrc@yahoo.com.br#define __BASE_FILTERS_BASE_HH__ 3414262Sodanrc@yahoo.com.br 3514262Sodanrc@yahoo.com.br#include <vector> 3614262Sodanrc@yahoo.com.br 3714262Sodanrc@yahoo.com.br#include "base/intmath.hh" 3814264Sodanrc@yahoo.com.br#include "base/sat_counter.hh" 3914262Sodanrc@yahoo.com.br#include "base/types.hh" 4014262Sodanrc@yahoo.com.br#include "params/BloomFilterBase.hh" 4114262Sodanrc@yahoo.com.br#include "sim/sim_object.hh" 4214262Sodanrc@yahoo.com.br 4314262Sodanrc@yahoo.com.brnamespace BloomFilter { 4414262Sodanrc@yahoo.com.br 4514262Sodanrc@yahoo.com.brclass Base : public SimObject 4614262Sodanrc@yahoo.com.br{ 4714262Sodanrc@yahoo.com.br protected: 4814262Sodanrc@yahoo.com.br /** Number of LSB bits to ignore from the the addresses. */ 4914262Sodanrc@yahoo.com.br const unsigned offsetBits; 5014262Sodanrc@yahoo.com.br 5114262Sodanrc@yahoo.com.br /** The filter itself. */ 5214264Sodanrc@yahoo.com.br std::vector<SatCounter> filter; 5314262Sodanrc@yahoo.com.br 5414262Sodanrc@yahoo.com.br /** Number of bits needed to represent the size of the filter. */ 5514262Sodanrc@yahoo.com.br const int sizeBits; 5614262Sodanrc@yahoo.com.br 5714262Sodanrc@yahoo.com.br /** Threshold at which a filter entry starts being considered as set. */ 5814262Sodanrc@yahoo.com.br const int setThreshold; 5914262Sodanrc@yahoo.com.br 6014262Sodanrc@yahoo.com.br public: 6114262Sodanrc@yahoo.com.br /** 6214262Sodanrc@yahoo.com.br * Create and clear the filter. 6314262Sodanrc@yahoo.com.br */ 6414262Sodanrc@yahoo.com.br Base(const BloomFilterBaseParams* p) 6514264Sodanrc@yahoo.com.br : SimObject(p), offsetBits(p->offset_bits), 6614264Sodanrc@yahoo.com.br filter(p->size, SatCounter(p->num_bits)), 6714262Sodanrc@yahoo.com.br sizeBits(floorLog2(p->size)), setThreshold(p->threshold) 6814262Sodanrc@yahoo.com.br { 6914262Sodanrc@yahoo.com.br clear(); 7014262Sodanrc@yahoo.com.br } 7114262Sodanrc@yahoo.com.br virtual ~Base() {}; 7214262Sodanrc@yahoo.com.br 7314262Sodanrc@yahoo.com.br /** 7414262Sodanrc@yahoo.com.br * Clear the filter by resetting all values. 7514262Sodanrc@yahoo.com.br */ 7614262Sodanrc@yahoo.com.br virtual void clear() 7714262Sodanrc@yahoo.com.br { 7814262Sodanrc@yahoo.com.br for (auto& entry : filter) { 7914264Sodanrc@yahoo.com.br entry.reset(); 8014262Sodanrc@yahoo.com.br } 8114262Sodanrc@yahoo.com.br } 8214262Sodanrc@yahoo.com.br 8314262Sodanrc@yahoo.com.br /** 8414262Sodanrc@yahoo.com.br * Merges the contents of both filters into this' (Bloom Filter union). 8514262Sodanrc@yahoo.com.br * Both must have the same number of entries. 8614262Sodanrc@yahoo.com.br * 8714262Sodanrc@yahoo.com.br * @param other The other bloom filter to merge with. 8814262Sodanrc@yahoo.com.br */ 8914262Sodanrc@yahoo.com.br virtual void 9014262Sodanrc@yahoo.com.br merge(const Base* other) 9114262Sodanrc@yahoo.com.br { 9214262Sodanrc@yahoo.com.br assert(filter.size() == other->filter.size()); 9314262Sodanrc@yahoo.com.br for (int i = 0; i < filter.size(); ++i){ 9414264Sodanrc@yahoo.com.br filter[i] += other->filter[i]; 9514262Sodanrc@yahoo.com.br } 9614262Sodanrc@yahoo.com.br } 9714262Sodanrc@yahoo.com.br 9814262Sodanrc@yahoo.com.br /** 9914262Sodanrc@yahoo.com.br * Perform the filter specific function to set the corresponding 10014262Sodanrc@yahoo.com.br * entries (can be multiple) of an address. 10114262Sodanrc@yahoo.com.br * 10214262Sodanrc@yahoo.com.br * @param addr The address being parsed. 10314262Sodanrc@yahoo.com.br */ 10414262Sodanrc@yahoo.com.br virtual void set(Addr addr) = 0; 10514262Sodanrc@yahoo.com.br 10614262Sodanrc@yahoo.com.br /** 10714262Sodanrc@yahoo.com.br * Perform the filter specific function to clear the corresponding 10814262Sodanrc@yahoo.com.br * entries (can be multiple) of an address. By default a bloom 10914262Sodanrc@yahoo.com.br * filter does not support element deletion. 11014262Sodanrc@yahoo.com.br * 11114262Sodanrc@yahoo.com.br * @param addr The address being parsed. 11214262Sodanrc@yahoo.com.br */ 11314262Sodanrc@yahoo.com.br virtual void unset(Addr addr) {}; 11414262Sodanrc@yahoo.com.br 11514262Sodanrc@yahoo.com.br /** 11614262Sodanrc@yahoo.com.br * Check if the corresponding filter entries of an address should be 11714262Sodanrc@yahoo.com.br * considered as set. 11814262Sodanrc@yahoo.com.br * 11914262Sodanrc@yahoo.com.br * @param addr The address being parsed. 12014262Sodanrc@yahoo.com.br * @return Whether the respective filter entry is set. 12114262Sodanrc@yahoo.com.br */ 12214262Sodanrc@yahoo.com.br virtual bool 12314262Sodanrc@yahoo.com.br isSet(Addr addr) const 12414262Sodanrc@yahoo.com.br { 12514262Sodanrc@yahoo.com.br return getCount(addr) >= setThreshold; 12614262Sodanrc@yahoo.com.br } 12714262Sodanrc@yahoo.com.br 12814262Sodanrc@yahoo.com.br /** 12914262Sodanrc@yahoo.com.br * Get the value stored in the corresponding filter entry of an address. 13014262Sodanrc@yahoo.com.br * 13114262Sodanrc@yahoo.com.br * @param addr The address being parsed. 13214262Sodanrc@yahoo.com.br * @param Get the value stored in the respective filter entry. 13314262Sodanrc@yahoo.com.br */ 13414262Sodanrc@yahoo.com.br virtual int getCount(Addr addr) const { return 0; } 13514262Sodanrc@yahoo.com.br 13614262Sodanrc@yahoo.com.br /** 13714262Sodanrc@yahoo.com.br * Get the total value stored in the filter entries. 13814262Sodanrc@yahoo.com.br * 13914262Sodanrc@yahoo.com.br * @return The sum of all filter entries. 14014262Sodanrc@yahoo.com.br */ 14114262Sodanrc@yahoo.com.br virtual int getTotalCount() const 14214262Sodanrc@yahoo.com.br { 14314262Sodanrc@yahoo.com.br int count = 0; 14414262Sodanrc@yahoo.com.br for (const auto& entry : filter) { 14514262Sodanrc@yahoo.com.br count += entry; 14614262Sodanrc@yahoo.com.br } 14714262Sodanrc@yahoo.com.br return count; 14814262Sodanrc@yahoo.com.br } 14914262Sodanrc@yahoo.com.br}; 15014262Sodanrc@yahoo.com.br 15114262Sodanrc@yahoo.com.br} // namespace BloomFilter 15214262Sodanrc@yahoo.com.br 15314262Sodanrc@yahoo.com.br#endif // __BASE_FILTERS_BASE_HH__ 154