bulk_bloom_filter.cc (14262:991410960fdb) bulk_bloom_filter.cc (14263:4a6d5c4a0813)
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

--- 17 unchanged lines hidden (view full) ---

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 * Authors: Daniel Carvalho
30 */
31
32#include "base/filters/bulk_bloom_filter.hh"
33
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

--- 17 unchanged lines hidden (view full) ---

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 * Authors: Daniel Carvalho
30 */
31
32#include "base/filters/bulk_bloom_filter.hh"
33
34#include <vector>
35
36#include <limits>
37
38#include "base/bitfield.hh"
34#include <limits>
35
36#include "base/bitfield.hh"
37#include "base/logging.hh"
39#include "params/BloomFilterBulk.hh"
40
41namespace BloomFilter {
42
43Bulk::Bulk(const BloomFilterBulkParams* p)
38#include "params/BloomFilterBulk.hh"
39
40namespace BloomFilter {
41
42Bulk::Bulk(const BloomFilterBulkParams* p)
44 : Base(p), sectorBits(sizeBits - 1)
43 : MultiBitSel(p), sectorBits(floorLog2(parFilterSize))
45{
44{
45 fatal_if((numHashes * sectorBits) >
46 (std::numeric_limits<Addr>::digits - offsetBits),
47 "Sectors need more bits than available");
46}
47
48Bulk::~Bulk()
49{
50}
51
48}
49
50Bulk::~Bulk()
51{
52}
53
52void
53Bulk::set(Addr addr)
54int
55Bulk::hash(Addr addr, int hash_number) const
54{
56{
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}
57 addr = permute(addr);
69
58
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;
59 // Get the sector-based c index
60 int c = bits(addr, (offsetBits + (hash_number + 1) * sectorBits) - 1,
61 offsetBits + hash_number * sectorBits);
62 assert(c < filter.size()/numHashes);
88
63
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 }
64 // Transform the sector-based c index into a filder index (v)
65 c += (numHashes - 1 - hash_number) * (filter.size()/numHashes);
66 assert(c < filter.size());
105
67
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;
68 return c;
124}
125
69}
70
126int
127Bulk::getCount(Addr addr) const
128{
129 // TODO as in the multi-hashed filters
130 return 0;
131}
132
133Addr
71Addr
134Bulk::hash(Addr addr) const
72Bulk::permute(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),

--- 27 unchanged lines hidden --- 		73{
74 // permutes the original address bits according to Table 5
75 Addr part1 = bits(addr, offsetBits + 6, offsetBits),
76 part2 = bits(addr, offsetBits + 9),
77 part3 = bits(addr, offsetBits + 11),
78 part4 = bits(addr, offsetBits + 17),
79 part5 = bits(addr, offsetBits + 8, offsetBits + 7),
80 part6 = bits(addr, offsetBits + 10),

--- 27 unchanged lines hidden ---