bulk_bloom_filter.cc revision 14262:991410960fdb
16145SN/A/* 26386SN/A * Copyright (c) 2019 Inria 37553SN/A * Copyright (c) 1999-2008 Mark D. Hill and David A. Wood 46386SN/A * All rights reserved. 56386SN/A * 66386SN/A * Redistribution and use in source and binary forms, with or without 76386SN/A * modification, are permitted provided that the following conditions are 86386SN/A * met: redistributions of source code must retain the above copyright 96386SN/A * notice, this list of conditions and the following disclaimer; 106386SN/A * redistributions in binary form must reproduce the above copyright 116386SN/A * notice, this list of conditions and the following disclaimer in the 126386SN/A * documentation and/or other materials provided with the distribution; 136386SN/A * neither the name of the copyright holders nor the names of its 146386SN/A * contributors may be used to endorse or promote products derived from 156386SN/A * this software without specific prior written permission. 166386SN/A * 176386SN/A * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 186386SN/A * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 196386SN/A * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 206386SN/A * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 216386SN/A * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 226386SN/A * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 236386SN/A * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 246386SN/A * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 256386SN/A * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 266386SN/A * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 276386SN/A * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 286386SN/A * 296145SN/A * Authors: Daniel Carvalho 307632SBrad.Beckmann@amd.com */ 3111793Sbrandon.potter@amd.com 328832SAli.Saidi@ARM.com#include "base/filters/bulk_bloom_filter.hh" 336145SN/A 347553SN/A#include <vector> 358832SAli.Saidi@ARM.com 3612680Sgiacomo.travaglini@arm.com#include <limits> 376145SN/A 387553SN/A#include "base/bitfield.hh" 397553SN/A#include "params/BloomFilterBulk.hh" 406145SN/A 416145SN/Anamespace BloomFilter { 4211320Ssteve.reinhardt@amd.com 437553SN/ABulk::Bulk(const BloomFilterBulkParams* p) 446145SN/A : Base(p), sectorBits(sizeBits - 1) 457553SN/A{ 467553SN/A} 476145SN/A 48Bulk::~Bulk() 49{ 50} 51 52void 53Bulk::set(Addr addr) 54{ 55 // c0 contains the cache index bits 56 int c0 = bits(addr, offsetBits + sectorBits - 1, offsetBits); 57 // c1 contains the lower sectorBits permuted bits 58 //Address permuted_bits = permute(addr); 59 int c1 = bits(addr, (offsetBits + 2 * sectorBits) - 1, 60 offsetBits + sectorBits); 61 //assert(c0 < (filter_size/2)); 62 //assert(c0 + (filter_size/2) < filter_size); 63 //assert(c1 < (filter_size/2)); 64 // set v0 bit 65 filter[c0 + (filter.size()/2)] = 1; 66 // set v1 bit 67 filter[c1] = 1; 68} 69 70bool 71Bulk::isSet(Addr addr) const 72{ 73 // c0 contains the cache index bits 74 const int filter_size = filter.size(); 75 int c0 = bits(addr, offsetBits + sectorBits - 1, offsetBits); 76 // c1 contains the lower 10 permuted bits 77 //Address permuted_bits = permute(addr); 78 int c1 = bits(addr, (offsetBits + 2 * sectorBits) - 1, 79 offsetBits + sectorBits); 80 //assert(c0 < (filter_size/2)); 81 //assert(c0 + (filter_size/2) < filter_size); 82 //assert(c1 < (filter_size/2)); 83 // set v0 bit 84 std::vector<int> temp_filter(filter.size(), 0); 85 temp_filter[c0 + (filter_size/2)] = 1; 86 // set v1 bit 87 temp_filter[c1] = 1; 88 89 // perform filter intersection. If any c part is 0, no possibility 90 // of address being in signature. get first c intersection part 91 bool zero = false; 92 for (int i = 0; i < filter_size/2; ++i){ 93 // get intersection of signatures 94 temp_filter[i] = temp_filter[i] && filter[i]; 95 zero = zero || temp_filter[i]; 96 } 97 zero = !zero; 98 if (zero) { 99 // one section is zero, no possiblility of address in signature 100 // reset bits we just set 101 temp_filter[c0 + (filter_size / 2)] = 0; 102 temp_filter[c1] = 0; 103 return false; 104 } 105 106 // check second section 107 zero = false; 108 for (int i = filter_size / 2; i < filter_size; ++i) { 109 // get intersection of signatures 110 temp_filter[i] = temp_filter[i] && filter[i]; 111 zero = zero || temp_filter[i]; 112 } 113 zero = !zero; 114 if (zero) { 115 // one section is zero, no possiblility of address in signature 116 temp_filter[c0 + (filter_size / 2)] = 0; 117 temp_filter[c1] = 0; 118 return false; 119 } 120 // one section has at least one bit set 121 temp_filter[c0 + (filter_size / 2)] = 0; 122 temp_filter[c1] = 0; 123 return true; 124} 125 126int 127Bulk::getCount(Addr addr) const 128{ 129 // TODO as in the multi-hashed filters 130 return 0; 131} 132 133Addr 134Bulk::hash(Addr addr) const 135{ 136 // permutes the original address bits according to Table 5 137 Addr part1 = bits(addr, offsetBits + 6, offsetBits), 138 part2 = bits(addr, offsetBits + 9), 139 part3 = bits(addr, offsetBits + 11), 140 part4 = bits(addr, offsetBits + 17), 141 part5 = bits(addr, offsetBits + 8, offsetBits + 7), 142 part6 = bits(addr, offsetBits + 10), 143 part7 = bits(addr, offsetBits + 12), 144 part8 = bits(addr, offsetBits + 13), 145 part9 = bits(addr, offsetBits + 16, offsetBits + 15), 146 part10 = bits(addr, offsetBits + 20, offsetBits + 18), 147 part11 = bits(addr, offsetBits + 14); 148 149 Addr result = 150 (part1 << 14) | (part2 << 13) | (part3 << 12) | (part4 << 11) | 151 (part5 << 9) | (part6 << 8) | (part7 << 7) | (part8 << 6) | 152 (part9 << 4) | (part10 << 1) | (part11); 153 154 // Select the remaining high-order bits 155 Addr remaining_bits = bits(addr, std::numeric_limits<Addr>::digits - 1, 156 offsetBits + 21) << 21; 157 result = result | remaining_bits; 158 159 return result; 160} 161 162} // namespace BloomFilter 163 164BloomFilter::Bulk* 165BloomFilterBulkParams::create() 166{ 167 return new BloomFilter::Bulk(this); 168} 169 170