bulk_bloom_filter.cc revision 14262 
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 * 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"
39#include "params/BloomFilterBulk.hh"
40
41namespace BloomFilter {
42
43Bulk::Bulk(const BloomFilterBulkParams* p)
44    : Base(p), sectorBits(sizeBits - 1)
45{
46}
47
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