gem5 [DEVELOP-FOR-25.1]
Loading...
Searching...
No Matches
base.test.cc
Go to the documentation of this file.
1/*
2 * Copyright (c) 2021 Daniel R. Carvalho
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 <gtest/gtest-spi.h>
30#include <gtest/gtest.h>
31
32#include <cassert>
33
34#include "base/filters/base.hh"
35
36#define GEM5_DECLARE_FILTER_PARAMS(name) \
37 BloomFilterBaseParams name; \
38 name.eventq_index = 0; \
39 name.size = 3; \
40 name.offset_bits = 6; \
41 name.num_bits = 1; \
42 name.threshold = 1
43
44using namespace gem5;
45
47class TestFilter : public bloom_filter::Base
48{
49 public:
50 using bloom_filter::Base::Base;
51
52 void
53 set(Addr addr) override
54 {
55 assert(addr < filter.size());
56 filter[addr]++;
57 }
58
59 int
60 getCount(Addr addr) const override
61 {
62 assert(addr < filter.size());
63 return filter[addr];
64 }
65};
66
68TEST(BloomFilterBaseTest, Construct)
69{
70 GEM5_DECLARE_FILTER_PARAMS(params);
71 TestFilter filter(params);
72 ASSERT_EQ(filter.getTotalCount(), 0);
73 for (int i = 0; i < params.size; i++) {
74 ASSERT_FALSE(filter.isSet(i));
75 }
76}
77
82TEST(BloomFilterBaseTest, SingleIsSet)
83{
84 GEM5_DECLARE_FILTER_PARAMS(params);
85 TestFilter filter(params);
86 ASSERT_EQ(filter.getTotalCount(), 0);
87
88 filter.set(0);
89 ASSERT_EQ(filter.getTotalCount(), 1);
90 ASSERT_TRUE(filter.isSet(0));
91 ASSERT_FALSE(filter.isSet(1));
92 ASSERT_FALSE(filter.isSet(2));
93
94 filter.clear();
95 ASSERT_EQ(filter.getTotalCount(), 0);
96 filter.set(1);
97 ASSERT_EQ(filter.getTotalCount(), 1);
98 ASSERT_FALSE(filter.isSet(0));
99 ASSERT_TRUE(filter.isSet(1));
100 ASSERT_FALSE(filter.isSet(2));
101
102 filter.clear();
103 ASSERT_EQ(filter.getTotalCount(), 0);
104 filter.set(2);
105 ASSERT_EQ(filter.getTotalCount(), 1);
106 ASSERT_FALSE(filter.isSet(0));
107 ASSERT_FALSE(filter.isSet(1));
108 ASSERT_TRUE(filter.isSet(2));
109}
110
115TEST(BloomFilterBaseTest, MultipleIsSet)
116{
117 GEM5_DECLARE_FILTER_PARAMS(params);
118 TestFilter filter(params);
119 ASSERT_EQ(filter.getTotalCount(), 0);
120
121 filter.set(0);
122 ASSERT_EQ(filter.getTotalCount(), 1);
123 filter.set(1);
124 ASSERT_EQ(filter.getTotalCount(), 2);
125 ASSERT_TRUE(filter.isSet(0));
126 ASSERT_TRUE(filter.isSet(1));
127 ASSERT_FALSE(filter.isSet(2));
128
129 filter.clear();
130 ASSERT_EQ(filter.getTotalCount(), 0);
131 filter.set(1);
132 ASSERT_EQ(filter.getTotalCount(), 1);
133 filter.set(2);
134 ASSERT_EQ(filter.getTotalCount(), 2);
135 ASSERT_FALSE(filter.isSet(0));
136 ASSERT_TRUE(filter.isSet(1));
137 ASSERT_TRUE(filter.isSet(2));
138
139 filter.clear();
140 ASSERT_EQ(filter.getTotalCount(), 0);
141 filter.set(0);
142 ASSERT_EQ(filter.getTotalCount(), 1);
143 filter.set(2);
144 ASSERT_EQ(filter.getTotalCount(), 2);
145 ASSERT_TRUE(filter.isSet(0));
146 ASSERT_FALSE(filter.isSet(1));
147 ASSERT_TRUE(filter.isSet(2));
148
149 filter.clear();
150 ASSERT_EQ(filter.getTotalCount(), 0);
151 filter.set(0);
152 ASSERT_EQ(filter.getTotalCount(), 1);
153 filter.set(1);
154 ASSERT_EQ(filter.getTotalCount(), 2);
155 filter.set(2);
156 ASSERT_EQ(filter.getTotalCount(), 3);
157 ASSERT_TRUE(filter.isSet(0));
158 ASSERT_TRUE(filter.isSet(1));
159 ASSERT_TRUE(filter.isSet(2));
160}
161
167TEST(BloomFilterBaseTest, SingleIsSetThreshold)
168{
169 GEM5_DECLARE_FILTER_PARAMS(params);
170 params.num_bits = 2;
171 params.threshold = 2;
172 TestFilter filter(params);
173 ASSERT_EQ(filter.getTotalCount(), 0);
174
175 filter.set(0);
176 ASSERT_EQ(filter.getTotalCount(), 1);
177 ASSERT_FALSE(filter.isSet(0));
178 ASSERT_FALSE(filter.isSet(1));
179 ASSERT_FALSE(filter.isSet(2));
180 filter.set(0);
181 ASSERT_EQ(filter.getTotalCount(), 2);
182 ASSERT_TRUE(filter.isSet(0));
183 ASSERT_FALSE(filter.isSet(1));
184 ASSERT_FALSE(filter.isSet(2));
185
186 filter.clear();
187 filter.set(1);
188 ASSERT_EQ(filter.getTotalCount(), 1);
189 ASSERT_FALSE(filter.isSet(0));
190 ASSERT_FALSE(filter.isSet(1));
191 ASSERT_FALSE(filter.isSet(2));
192 filter.set(1);
193 ASSERT_EQ(filter.getTotalCount(), 2);
194 ASSERT_FALSE(filter.isSet(0));
195 ASSERT_TRUE(filter.isSet(1));
196 ASSERT_FALSE(filter.isSet(2));
197
198 filter.clear();
199 filter.set(2);
200 ASSERT_EQ(filter.getTotalCount(), 1);
201 ASSERT_FALSE(filter.isSet(0));
202 ASSERT_FALSE(filter.isSet(1));
203 ASSERT_FALSE(filter.isSet(2));
204 filter.set(2);
205 ASSERT_EQ(filter.getTotalCount(), 2);
206 ASSERT_FALSE(filter.isSet(0));
207 ASSERT_FALSE(filter.isSet(1));
208 ASSERT_TRUE(filter.isSet(2));
209
210 // Setting different entries once should not make any of them
211 // reach the threshold
212 filter.clear();
213 filter.set(0);
214 filter.set(1);
215 filter.set(2);
216 ASSERT_EQ(filter.getTotalCount(), 3);
217 ASSERT_FALSE(filter.isSet(0));
218 ASSERT_FALSE(filter.isSet(1));
219 ASSERT_FALSE(filter.isSet(2));
220}
221
223TEST(BloomFilterBaseTest, MergeBothEmpty)
224{
225 GEM5_DECLARE_FILTER_PARAMS(params);
226 TestFilter filter(params);
227 TestFilter filter2(params);
228
229 filter.merge(&filter2);
230 ASSERT_EQ(filter.getTotalCount(), 0);
231 ASSERT_EQ(filter2.getTotalCount(), 0);
232}
233
238TEST(BloomFilterBaseTest, MergeWithEmpty)
239{
240 GEM5_DECLARE_FILTER_PARAMS(params);
241 TestFilter filter(params);
242 filter.set(1);
243
244 TestFilter filter2(params);
245
246 filter.merge(&filter2);
247 ASSERT_EQ(filter.getTotalCount(), 1);
248 ASSERT_TRUE(filter.isSet(1));
249 ASSERT_EQ(filter2.getTotalCount(), 0);
250}
251
256TEST(BloomFilterBaseTest, MergeWithEmpty2)
257{
258 GEM5_DECLARE_FILTER_PARAMS(params);
259 TestFilter filter(params);
260
261 TestFilter filter2(params);
262 filter2.set(1);
263
264 filter.merge(&filter2);
265 ASSERT_EQ(filter.getTotalCount(), 1);
266 ASSERT_TRUE(filter.isSet(1));
267 ASSERT_EQ(filter2.getTotalCount(), 1);
268 ASSERT_TRUE(filter.isSet(1));
269}
270
275TEST(BloomFilterBaseTest, MergeNoIntersection)
276{
277 GEM5_DECLARE_FILTER_PARAMS(params);
278 params.size = 10;
279
280 TestFilter filter(params);
281 filter.set(1);
282 filter.set(2);
283 filter.set(5);
284 filter.set(8);
285
286 TestFilter filter2(params);
287 filter2.set(3);
288 filter2.set(4);
289 filter2.set(9);
290
291 filter.merge(&filter2);
292 ASSERT_EQ(filter.getTotalCount(), 7);
293 ASSERT_TRUE(filter.isSet(1));
294 ASSERT_TRUE(filter.isSet(2));
295 ASSERT_TRUE(filter.isSet(3));
296 ASSERT_TRUE(filter.isSet(4));
297 ASSERT_TRUE(filter.isSet(5));
298 ASSERT_TRUE(filter.isSet(8));
299 ASSERT_TRUE(filter.isSet(9));
300 ASSERT_EQ(filter2.getTotalCount(), 3);
301 ASSERT_TRUE(filter2.isSet(3));
302 ASSERT_TRUE(filter2.isSet(4));
303 ASSERT_TRUE(filter2.isSet(9));
304}
305
307TEST(BloomFilterBaseTest, MergeIntersectionThreshold1)
308{
309 GEM5_DECLARE_FILTER_PARAMS(params);
310 params.size = 10;
311
312 TestFilter filter(params);
313 filter.set(1);
314 filter.set(2);
315 filter.set(5);
316 filter.set(8);
317
318 TestFilter filter2(params);
319 filter2.set(3);
320 filter2.set(5);
321 filter2.set(9);
322
323 filter.merge(&filter2);
324 ASSERT_EQ(filter.getTotalCount(), 6);
325 ASSERT_TRUE(filter.isSet(1));
326 ASSERT_TRUE(filter.isSet(2));
327 ASSERT_TRUE(filter.isSet(3));
328 ASSERT_TRUE(filter.isSet(5));
329 ASSERT_TRUE(filter.isSet(8));
330 ASSERT_TRUE(filter.isSet(9));
331 ASSERT_EQ(filter2.getTotalCount(), 3);
332 ASSERT_TRUE(filter2.isSet(3));
333 ASSERT_TRUE(filter2.isSet(5));
334 ASSERT_TRUE(filter2.isSet(9));
335}
336
342TEST(BloomFilterBaseTest, MergeIntersectionThreshold2)
343{
344 GEM5_DECLARE_FILTER_PARAMS(params);
345 params.size = 10;
346 params.num_bits = 2;
347 params.threshold = 2;
348
349 TestFilter filter(params);
350 filter.set(1);
351 filter.set(2);
352 filter.set(5);
353 filter.set(5);
354 filter.set(8);
355
356 TestFilter filter2(params);
357 filter2.set(2);
358 filter2.set(5);
359 filter2.set(5);
360 filter2.set(5);
361 filter2.set(9);
362
363 filter.merge(&filter2);
364 // 1 one, 2 twos, 3 fives (saturated), 1 eight, 1 nine
365 ASSERT_EQ(filter.getTotalCount(), 8);
366 ASSERT_TRUE(filter.isSet(2));
367 ASSERT_TRUE(filter.isSet(5));
368 ASSERT_EQ(filter2.getTotalCount(), 5);
369 ASSERT_FALSE(filter2.isSet(2));
370 ASSERT_TRUE(filter2.isSet(5));
371}
372
374TEST(BloomFilterBaseDeathTest, MergeDifferent)
375{
376#ifdef NDEBUG
377 GTEST_SKIP() << "Skipping as assertions are "
378 "stripped out of fast builds";
379#endif
380 GEM5_DECLARE_FILTER_PARAMS(params);
381 TestFilter filter(params);
382
383 BloomFilterBaseParams params2;
384 params2.eventq_index = params.eventq_index;
385 params2.size = params.size + 1;
386 params2.offset_bits = params.offset_bits;
387 params2.num_bits = params.num_bits;
388 params2.threshold = params.threshold;
389 TestFilter filter2(params2);
390
391 ASSERT_DEATH(filter.merge(&filter2), "");
392}
393
394#undef GEM5_DECLARE_FILTER_PARAMS
TEST
TEST(BloomFilterBaseTest, Construct)
Test that a filter is initialized in a cleared state.
Definition base.test.cc:68
GEM5_DECLARE_FILTER_PARAMS
#define GEM5_DECLARE_FILTER_PARAMS(name)
Definition base.test.cc:36
TestFilter
Simulates basic behavior of a bloom filter.
Definition base.test.cc:48
TestFilter::set
void set(Addr addr) override
Perform the filter specific function to set the corresponding entries (can be multiple) of an address...
Definition base.test.cc:53
TestFilter::getCount
int getCount(Addr addr) const override
Get the value stored in the corresponding filter entry of an address.
Definition base.test.cc:60
gem5::bloom_filter::Base
Definition base.hh:49
gem5::bloom_filter::Base::isSet
virtual bool isSet(Addr addr) const
Check if the corresponding filter entries of an address should be considered as set.
Definition base.hh:126
gem5::bloom_filter::Base::filter
std::vector< SatCounter8 > filter
The filter itself.
Definition base.hh:55
gem5::bloom_filter::Base::getTotalCount
virtual int getTotalCount() const
Get the total value stored in the filter entries.
Definition base.hh:144
gem5::bloom_filter::Base::clear
virtual void clear()
Clear the filter by resetting all values.
Definition base.hh:79
gem5::bloom_filter::Base::Base
Base(const BloomFilterBaseParams &p)
Create and clear the filter.
Definition base.hh:67
gem5::bloom_filter::Base::merge
virtual void merge(const Base *other)
Merges the contents of both filters into this' (Bloom Filter union).
Definition base.hh:93
gem5::ArmISA::i
Bitfield< 7 > i
Definition misc_types.hh:67
gem5::X86ISA::addr
Bitfield< 3 > addr
Definition types.hh:84
gem5
Copyright (c) 2024 Arm Limited All rights reserved.
Definition binary32.hh:36
gem5::Addr
uint64_t Addr
Address type This will probably be moved somewhere else in the near future.
Definition types.hh:147
Generated on Mon Oct 27 2025 04:12:59 for gem5 by doxygen 1.14.0