gem5  v21.1.0.2
bulk_bloom_filter.cc
Go to the documentation of this file.
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 
31 
32 #include <limits>
33 
34 #include "base/bitfield.hh"
35 #include "base/logging.hh"
36 #include "params/BloomFilterBulk.hh"
37 
38 namespace gem5
39 {
40 
41 GEM5_DEPRECATED_NAMESPACE(BloomFilter, bloom_filter);
42 namespace bloom_filter
43 {
44 
45 Bulk::Bulk(const BloomFilterBulkParams &p)
46  : MultiBitSel(p), sectorBits(floorLog2(parFilterSize))
47 {
49  (std::numeric_limits<Addr>::digits - offsetBits),
50  "Sectors need more bits than available");
51 }
52 
54 {
55 }
56 
57 int
58 Bulk::hash(Addr addr, int hash_number) const
59 {
60  addr = permute(addr);
61 
62  // Get the sector-based c index
63  int c = bits(addr, (offsetBits + (hash_number + 1) * sectorBits) - 1,
64  offsetBits + hash_number * sectorBits);
65  assert(c < filter.size()/numHashes);
66 
67  // Transform the sector-based c index into a filder index (v)
68  c += (numHashes - 1 - hash_number) * (filter.size()/numHashes);
69  assert(c < filter.size());
70 
71  return c;
72 }
73 
74 Addr
76 {
77  // permutes the original address bits according to Table 5
78  Addr part1 = bits(addr, offsetBits + 6, offsetBits),
79  part2 = bits(addr, offsetBits + 9),
80  part3 = bits(addr, offsetBits + 11),
81  part4 = bits(addr, offsetBits + 17),
82  part5 = bits(addr, offsetBits + 8, offsetBits + 7),
83  part6 = bits(addr, offsetBits + 10),
84  part7 = bits(addr, offsetBits + 12),
85  part8 = bits(addr, offsetBits + 13),
86  part9 = bits(addr, offsetBits + 16, offsetBits + 15),
87  part10 = bits(addr, offsetBits + 20, offsetBits + 18),
88  part11 = bits(addr, offsetBits + 14);
89 
90  Addr result =
91  (part1 << 14) | (part2 << 13) | (part3 << 12) | (part4 << 11) |
92  (part5 << 9) | (part6 << 8) | (part7 << 7) | (part8 << 6) |
93  (part9 << 4) | (part10 << 1) | (part11);
94 
95  // Select the remaining high-order bits
96  Addr remaining_bits = bits(addr, std::numeric_limits<Addr>::digits - 1,
97  offsetBits + 21) << 21;
98  result = result | remaining_bits;
99 
100  return result;
101 }
102 
103 } // namespace bloom_filter
104 } // namespace gem5
gem5::bloom_filter::MultiBitSel::numHashes
const int numHashes
Number of hashes.
Definition: multi_bit_sel_bloom_filter.hh:67
gem5::bloom_filter::Base::filter
std::vector< SatCounter8 > filter
The filter itself.
Definition: base.hh:56
gem5::bloom_filter::Base::offsetBits
const unsigned offsetBits
Number of LSB bits to ignore from the the addresses.
Definition: base.hh:53
gem5::bloom_filter::Bulk::sectorBits
const int sectorBits
Number of bits used per sector.
Definition: bulk_bloom_filter.hh:68
gem5::bloom_filter::Bulk::Bulk
Bulk(const BloomFilterBulkParams &p)
Definition: bulk_bloom_filter.cc:45
bitfield.hh
gem5::MipsISA::p
Bitfield< 0 > p
Definition: pra_constants.hh:326
gem5::bits
constexpr T bits(T val, unsigned first, unsigned last)
Extract the bitfield from position 'first' to 'last' (inclusive) from 'val' and right justify it.
Definition: bitfield.hh:76
gem5::ArmISA::c
Bitfield< 29 > c
Definition: misc_types.hh:53
gem5::bloom_filter::MultiBitSel
The MultiBitSel Bloom Filter associates an address to multiple entries through the use of multiple ha...
Definition: multi_bit_sel_bloom_filter.hh:48
gem5::Addr
uint64_t Addr
Address type This will probably be moved somewhere else in the near future.
Definition: types.hh:147
gem5::GEM5_DEPRECATED_NAMESPACE
GEM5_DEPRECATED_NAMESPACE(GuestABI, guest_abi)
gem5::bloom_filter::Bulk::~Bulk
~Bulk()
Definition: bulk_bloom_filter.cc:53
gem5::floorLog2
static constexpr std::enable_if_t< std::is_integral< T >::value, int > floorLog2(T x)
Definition: intmath.hh:59
logging.hh
bulk_bloom_filter.hh
gem5::bloom_filter::Bulk::permute
Addr permute(Addr addr) const
Permutes the address to generate its signature.
Definition: bulk_bloom_filter.cc:75
gem5::bloom_filter::Bulk::hash
int hash(Addr addr, int hash_number) const override
Apply the selected the hash functions to an address.
Definition: bulk_bloom_filter.cc:58
fatal_if
#define fatal_if(cond,...)
Conditional fatal macro that checks the supplied condition and only causes a fatal error if the condi...
Definition: logging.hh:225
gem5
Reference material can be found at the JEDEC website: UFS standard http://www.jedec....
Definition: decoder.cc:40
gem5::X86ISA::addr
Bitfield< 3 > addr
Definition: types.hh:84

Generated on Tue Sep 21 2021 12:24:57 for gem5 by doxygen 1.8.17