src/mem/ruby/filters/MultiBitSelBloomFilter.cc

   1 /*
   2  * Copyright (c) 1999-2008 Mark D. Hill and David A. Wood
   3  * All rights reserved.
   4  *
   5  * Redistribution and use in source and binary forms, with or without
   6  * modification, are permitted provided that the following conditions are
   7  * met: redistributions of source code must retain the above copyright
   8  * notice, this list of conditions and the following disclaimer;
   9  * redistributions in binary form must reproduce the above copyright
  10  * notice, this list of conditions and the following disclaimer in the
  11  * documentation and/or other materials provided with the distribution;
  12  * neither the name of the copyright holders nor the names of its
  13  * contributors may be used to endorse or promote products derived from
  14  * this software without specific prior written permission.
  15  *
  16  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  17  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  18  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
  19  * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
  20  * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  21  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
  22  * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  23  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  24  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  25  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  26  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  27  */
  28
  29 #include <vector>
  30
  31 #include "base/intmath.hh"
  32 #include "base/str.hh"
  33 #include "mem/ruby/filters/MultiBitSelBloomFilter.hh"
  34
  35 using namespace std;
  36
  37 MultiBitSelBloomFilter::MultiBitSelBloomFilter(string str)
  38 {
  39     vector<string> items;
  40     tokenize(items, str, '_');
  41     assert(items.size() == 4);
  42
  43     // head contains filter size, tail contains bit offset from block number
  44     m_filter_size = atoi(items[0].c_str());
  45     m_num_hashes = atoi(items[1].c_str());
  46     m_skip_bits = atoi(items[2].c_str());
  47
  48     if (items[3] == "Regular") {
  49         isParallel = false;
  50     } else if (items[3] == "Parallel") {
  51         isParallel = true;
  52     } else {
  53         panic("ERROR: Incorrect config string for MultiBitSel Bloom! :%s",
  54               str);
  55     }
  56
  57     m_filter_size_bits = floorLog2(m_filter_size);
  58
  59     m_par_filter_size = m_filter_size / m_num_hashes;
  60     m_par_filter_size_bits = floorLog2(m_par_filter_size);
  61
  62     m_filter.resize(m_filter_size);
  63     clear();
  64 }
  65
  66 MultiBitSelBloomFilter::~MultiBitSelBloomFilter()
  67 {
  68 }
  69
  70 void
  71 MultiBitSelBloomFilter::clear()
  72 {
  73     for (int i = 0; i < m_filter_size; i++) {
  74         m_filter[i] = 0;
  75     }
  76 }
  77
  78 void
  79 MultiBitSelBloomFilter::increment(Addr addr)
  80 {
  81     // Not used
  82 }
  83
  84
  85 void
  86 MultiBitSelBloomFilter::decrement(Addr addr)
  87 {
  88     // Not used
  89 }
  90
  91 void
  92 MultiBitSelBloomFilter::merge(AbstractBloomFilter *other_filter)
  93 {
  94     // assumes both filters are the same size!
  95     MultiBitSelBloomFilter * temp = (MultiBitSelBloomFilter*) other_filter;
  96     for(int i = 0; i < m_filter_size; ++i){
  97         m_filter[i] |= (*temp)[i];
  98     }
  99 }
 100
 101 void
 102 MultiBitSelBloomFilter::set(Addr addr)
 103 {
 104     for (int i = 0; i < m_num_hashes; i++) {
 105         int idx = get_index(addr, i);
 106         m_filter[idx] = 1;
 107     }
 108 }
 109
 110 void
 111 MultiBitSelBloomFilter::unset(Addr addr)
 112 {
 113     cout << "ERROR: Unset should never be called in a Bloom filter";
 114     assert(0);
 115 }
 116
 117 bool
 118 MultiBitSelBloomFilter::isSet(Addr addr)
 119 {
 120     bool res = true;
 121
 122     for (int i=0; i < m_num_hashes; i++) {
 123         int idx = get_index(addr, i);
 124         res = res && m_filter[idx];
 125     }
 126     return res;
 127 }
 128
 129 int
 130 MultiBitSelBloomFilter::getCount(Addr addr)
 131 {
 132     return isSet(addr)? 1: 0;
 133 }
 134
 135 int
 136 MultiBitSelBloomFilter::getIndex(Addr addr)
 137 {
 138     return 0;
 139 }
 140
 141 int
 142 MultiBitSelBloomFilter::readBit(const int index)
 143 {
 144     return 0;
 145 }
 146
 147 void
 148 MultiBitSelBloomFilter::writeBit(const int index, const int value)
 149 {
 150 }
 151
 152 int
 153 MultiBitSelBloomFilter::getTotalCount()
 154 {
 155     int count = 0;
 156
 157     for (int i = 0; i < m_filter_size; i++) {
 158         count += m_filter[i];
 159     }
 160     return count;
 161 }
 162
 163 void
 164 MultiBitSelBloomFilter::print(ostream& out) const
 165 {
 166 }
 167
 168 int
 169 MultiBitSelBloomFilter::get_index(Addr addr, int i)
 170 {
 171     // m_skip_bits is used to perform BitSelect after skipping some
 172     // bits. Used to simulate BitSel hashing on larger than cache-line
 173     // granularities
 174     uint64 x = (makeLineAddress(addr) >> m_skip_bits);
 175     int y = hash_bitsel(x, i, m_num_hashes, 30, m_filter_size_bits);
 176     //36-bit addresses, 6-bit cache lines
 177
 178     if (isParallel) {
 179         return (y % m_par_filter_size) + i*m_par_filter_size;
 180     } else {
 181         return y % m_filter_size;
 182     }
 183 }
 184
 185 int
 186 MultiBitSelBloomFilter::hash_bitsel(uint64 value, int index, int jump,
 187                                     int maxBits, int numBits)
 188 {
 189     uint64 mask = 1;
 190     int result = 0;
 191     int bit, i;
 192
 193     for (i = 0; i < numBits; i++) {
 194         bit = (index + jump*i) % maxBits;
 195         if (value & (mask << bit)) result += mask << i;
 196     }
 197     return result;
 198 }