src/mem/ruby/filters/BulkBloomFilter.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 <cassert>
  30
  31 #include "base/intmath.hh"
  32 #include "base/str.hh"
  33 #include "mem/ruby/filters/BulkBloomFilter.hh"
  34 #include "mem/ruby/system/System.hh"
  35
  36 using namespace std;
  37
  38 BulkBloomFilter::BulkBloomFilter(string str)
  39 {
  40     string head, tail;
  41
  42 #ifndef NDEBUG
  43     bool success =
  44 #endif
  45         split_first(str, head, tail, '_');
  46     assert(success);
  47
  48     m_filter_size = atoi(head.c_str());
  49     m_filter_size_bits = floorLog2(m_filter_size);
  50     // split the filter bits in half, c0 and c1
  51     m_sector_bits = m_filter_size_bits - 1;
  52
  53     m_temp_filter.resize(m_filter_size);
  54     m_filter.resize(m_filter_size);
  55     clear();
  56
  57     // clear temp filter
  58     for (int i = 0; i < m_filter_size; ++i) {
  59         m_temp_filter[i] = 0;
  60     }
  61 }
  62
  63 BulkBloomFilter::~BulkBloomFilter()
  64 {
  65 }
  66
  67 void
  68 BulkBloomFilter::clear()
  69 {
  70     for (int i = 0; i < m_filter_size; i++) {
  71         m_filter[i] = 0;
  72     }
  73 }
  74
  75 void
  76 BulkBloomFilter::increment(const Address& addr)
  77 {
  78     // Not used
  79 }
  80
  81 void
  82 BulkBloomFilter::decrement(const Address& addr)
  83 {
  84     // Not used
  85 }
  86
  87 void
  88 BulkBloomFilter::merge(AbstractBloomFilter * other_filter)
  89 {
  90     // TODO
  91 }
  92
  93 void
  94 BulkBloomFilter::set(const Address& addr)
  95 {
  96     // c0 contains the cache index bits
  97     int set_bits = m_sector_bits;
  98     int block_bits = RubySystem::getBlockSizeBits();
  99     int c0 = addr.bitSelect( block_bits, block_bits + set_bits - 1);
 100     // c1 contains the lower m_sector_bits permuted bits
 101     //Address permuted_bits = permute(addr);
 102     //int c1 = permuted_bits.bitSelect(0, set_bits-1);
 103     int c1 = addr.bitSelect( block_bits+set_bits, (block_bits+2*set_bits) - 1);
 104     //assert(c0 < (m_filter_size/2));
 105     //assert(c0 + (m_filter_size/2) < m_filter_size);
 106     //assert(c1 < (m_filter_size/2));
 107     // set v0 bit
 108     m_filter[c0 + (m_filter_size/2)] = 1;
 109     // set v1 bit
 110     m_filter[c1] = 1;
 111 }
 112
 113 void
 114 BulkBloomFilter::unset(const Address& addr)
 115 {
 116     // not used
 117 }
 118
 119 bool
 120 BulkBloomFilter::isSet(const Address& addr)
 121 {
 122     // c0 contains the cache index bits
 123     int set_bits = m_sector_bits;
 124     int block_bits = RubySystem::getBlockSizeBits();
 125     int c0 = addr.bitSelect( block_bits, block_bits + set_bits - 1);
 126     // c1 contains the lower 10 permuted bits
 127     //Address permuted_bits = permute(addr);
 128     //int c1 = permuted_bits.bitSelect(0, set_bits-1);
 129     int c1 = addr.bitSelect( block_bits+set_bits, (block_bits+2*set_bits) - 1);
 130     //assert(c0 < (m_filter_size/2));
 131     //assert(c0 + (m_filter_size/2) < m_filter_size);
 132     //assert(c1 < (m_filter_size/2));
 133     // set v0 bit
 134     m_temp_filter[c0 + (m_filter_size/2)] = 1;
 135     // set v1 bit
 136     m_temp_filter[c1] = 1;
 137
 138     // perform filter intersection. If any c part is 0, no possibility
 139     // of address being in signature.  get first c intersection part
 140     bool zero = false;
 141     for (int i = 0; i < m_filter_size/2; ++i){
 142         // get intersection of signatures
 143         m_temp_filter[i] = m_temp_filter[i] && m_filter[i];
 144         zero = zero || m_temp_filter[i];
 145     }
 146     zero = !zero;
 147     if (zero) {
 148         // one section is zero, no possiblility of address in signature
 149         // reset bits we just set
 150         m_temp_filter[c0 + (m_filter_size / 2)] = 0;
 151         m_temp_filter[c1] = 0;
 152         return false;
 153     }
 154
 155     // check second section
 156     zero = false;
 157     for(int i = m_filter_size / 2; i < m_filter_size; ++i) {
 158         // get intersection of signatures
 159         m_temp_filter[i] =  m_temp_filter[i] && m_filter[i];
 160         zero = zero || m_temp_filter[i];
 161     }
 162     zero = !zero;
 163     if (zero) {
 164         // one section is zero, no possiblility of address in signature
 165         m_temp_filter[c0 + (m_filter_size / 2)] = 0;
 166         m_temp_filter[c1] = 0;
 167         return false;
 168     }
 169     // one section has at least one bit set
 170     m_temp_filter[c0 + (m_filter_size / 2)] = 0;
 171     m_temp_filter[c1] = 0;
 172     return true;
 173 }
 174
 175 int
 176 BulkBloomFilter::getCount(const Address& addr)
 177 {
 178     // not used
 179     return 0;
 180 }
 181
 182 int
 183 BulkBloomFilter::getTotalCount()
 184 {
 185     int count = 0;
 186     for (int i = 0; i < m_filter_size; i++) {
 187         if (m_filter[i]) {
 188             count++;
 189         }
 190     }
 191     return count;
 192 }
 193
 194 int
 195 BulkBloomFilter::getIndex(const Address& addr)
 196 {
 197     return get_index(addr);
 198 }
 199
 200 int
 201 BulkBloomFilter::readBit(const int index)
 202 {
 203     return 0;
 204     // TODO
 205 }
 206
 207 void
 208 BulkBloomFilter::writeBit(const int index, const int value)
 209 {
 210     // TODO
 211 }
 212
 213 void
 214 BulkBloomFilter::print(ostream& out) const
 215 {
 216 }
 217
 218 int
 219 BulkBloomFilter::get_index(const Address& addr)
 220 {
 221     return addr.bitSelect(RubySystem::getBlockSizeBits(),
 222                           RubySystem::getBlockSizeBits() +
 223                           m_filter_size_bits - 1);
 224 }
 225
 226 Address
 227 BulkBloomFilter::permute(const Address & addr)
 228 {
 229     // permutes the original address bits according to Table 5
 230     int block_offset = RubySystem::getBlockSizeBits();
 231     physical_address_t part1 = addr.bitSelect(block_offset, block_offset + 6),
 232         part2 = addr.bitSelect(block_offset + 9, block_offset + 9),
 233         part3 = addr.bitSelect(block_offset + 11, block_offset + 11),
 234         part4 = addr.bitSelect(block_offset + 17, block_offset + 17),
 235         part5 = addr.bitSelect(block_offset + 7, block_offset + 8),
 236         part6 = addr.bitSelect(block_offset + 10, block_offset + 10),
 237         part7 = addr.bitSelect(block_offset + 12, block_offset + 12),
 238         part8 = addr.bitSelect(block_offset + 13, block_offset + 13),
 239         part9 = addr.bitSelect(block_offset + 15, block_offset + 16),
 240         part10 = addr.bitSelect(block_offset + 18, block_offset + 20),
 241         part11 = addr.bitSelect(block_offset + 14, block_offset + 14);
 242
 243     physical_address_t result =
 244         (part1 << 14) | (part2 << 13) | (part3 << 12) | (part4 << 11) |
 245         (part5 << 9)  | (part6 << 8)  | (part7 << 7)  | (part8 << 6)  |
 246         (part9 << 4)  | (part10 << 1) | (part11);
 247
 248     // assume 32 bit addresses (both virtual and physical)
 249     // select the remaining high-order 11 bits
 250     physical_address_t remaining_bits =
 251         addr.bitSelect(block_offset + 21, 31) << 21;
 252     result = result | remaining_bits;
 253
 254     return Address(result);
 255 }