Daniel Carvalho has uploaded this change for review. (
https://gem5-review.googlesource.com/c/public/gem5/+/18878
Change subject: base: Make bloom filter deletability a parameter
......................................................................
base: Make bloom filter deletability a parameter
Bloom Filters do not support deletion by default to avoid having
false negatives, however some systems may not have a problem
with having false negatives, and may benefit from deleting older
entries.
As such the missing deletion functions have been added.
Change-Id: I24f3f0a16d4743e6fb3c0fa76850996f258acb8f
Signed-off-by: Daniel R. Carvalho <[email protected]>
---
M src/base/filters/BloomFilters.py
M src/base/filters/base.hh
M src/base/filters/block_bloom_filter.cc
M src/base/filters/block_bloom_filter.hh
M src/base/filters/multi_bit_sel_bloom_filter.cc
M src/base/filters/multi_bit_sel_bloom_filter.hh
M src/base/filters/multi_bloom_filter.cc
M src/base/filters/multi_bloom_filter.hh
8 files changed, 44 insertions(+), 9 deletions(-)
diff --git a/src/base/filters/BloomFilters.py
b/src/base/filters/BloomFilters.py
index 99cbb1d..967df06 100644
--- a/src/base/filters/BloomFilters.py
+++ b/src/base/filters/BloomFilters.py
@@ -45,6 +45,9 @@
num_bits = Param.Int(1, "Number of bits in a filter entry")
threshold = Param.Int(1, "Value at which an entry is considered as
set")
+ # By default bloom filters do not support deletion
+ deletable = Param.Bool(False, "Whether the filter supports deletion")
+
class BloomFilterBlock(BloomFilterBase):
type = 'BloomFilterBlock'
cxx_class = 'BloomFilter::Block'
diff --git a/src/base/filters/base.hh b/src/base/filters/base.hh
index d5935dc..e0db698 100644
--- a/src/base/filters/base.hh
+++ b/src/base/filters/base.hh
@@ -68,6 +68,19 @@
/** Threshold at which a filter entry starts being considered as set.
*/
const int setThreshold;
+ /** Whether filter entries can be deleted or not. */
+ const bool deletable;
+
+ /**
+ * Perform the filter specific function to clear the corresponding
+ * entries (can be multiple) of an address. By default a bloom filter
+ * does not support element deletion. Should be overridden by the
+ * classes that inherit from it.
+ *
+ * @param addr The address being parsed.
+ */
+ virtual void erase(Addr addr) {}
+
public:
/**
* Create and clear the filter.
@@ -75,7 +88,8 @@
Base(const BloomFilterBaseParams* p)
: SimObject(p), blkBits(p->block_bits),
filter(p->size, SatCounter(p->num_bits)),
- sizeBits(floorLog2(p->size)), setThreshold(p->threshold)
+ sizeBits(floorLog2(p->size)), setThreshold(p->threshold),
+ deletable(p->deletable)
{
clear();
}
@@ -115,13 +129,17 @@
virtual void set(Addr addr) = 0;
/**
- * Perform the filter specific function to clear the corresponding
- * entries (can be multiple) of an address. By default a bloom
- * filter does not support element deletion.
+ * Unset the corresponding filter entries, if the filter is deletable.
*
* @param addr The address being parsed.
*/
- virtual void unset(Addr addr) {};
+ void
+ unset(Addr addr)
+ {
+ if (deletable) {
+ erase(addr);
+ }
+ }
/**
* Check if the corresponding filter entries of an address should be
diff --git a/src/base/filters/block_bloom_filter.cc
b/src/base/filters/block_bloom_filter.cc
index 00d7910..e3dd64b 100644
--- a/src/base/filters/block_bloom_filter.cc
+++ b/src/base/filters/block_bloom_filter.cc
@@ -74,7 +74,7 @@
}
void
-Block::unset(Addr addr)
+Block::erase(Addr addr)
{
filter[hash(addr)]--;
}
diff --git a/src/base/filters/block_bloom_filter.hh
b/src/base/filters/block_bloom_filter.hh
index fda05c5..55de559 100644
--- a/src/base/filters/block_bloom_filter.hh
+++ b/src/base/filters/block_bloom_filter.hh
@@ -61,9 +61,11 @@
~Block();
void set(Addr addr) override;
- void unset(Addr addr) override;
int getCount(Addr addr) const override;
+ protected:
+ void erase(Addr addr) override;
+
private:
/**
* XOR hash between two bitfields of an address. The address is divided
diff --git a/src/base/filters/multi_bit_sel_bloom_filter.cc
b/src/base/filters/multi_bit_sel_bloom_filter.cc
index 873f6f7..d0dc1e6 100644
--- a/src/base/filters/multi_bit_sel_bloom_filter.cc
+++ b/src/base/filters/multi_bit_sel_bloom_filter.cc
@@ -70,6 +70,14 @@
}
}
+void
+MultiBitSel::erase(Addr addr)
+{
+ for (int i = 0; i < numHashes; i++) {
+ filter[hash(addr, i)]--;
+ }
+}
+
int
MultiBitSel::getCount(Addr addr) const
{
diff --git a/src/base/filters/multi_bit_sel_bloom_filter.hh
b/src/base/filters/multi_bit_sel_bloom_filter.hh
index 2d7402a..070ce33 100644
--- a/src/base/filters/multi_bit_sel_bloom_filter.hh
+++ b/src/base/filters/multi_bit_sel_bloom_filter.hh
@@ -80,6 +80,8 @@
/** Whether hashing should be performed in parallel. */
const bool isParallel;
+ void erase(Addr addr) override;
+
private:
/**
* Bit offset from block number. Used to simulate bit selection hashing
diff --git a/src/base/filters/multi_bloom_filter.cc
b/src/base/filters/multi_bloom_filter.cc
index a41680a..1123f09 100644
--- a/src/base/filters/multi_bloom_filter.cc
+++ b/src/base/filters/multi_bloom_filter.cc
@@ -85,7 +85,7 @@
}
void
-Multi::unset(Addr addr)
+Multi::erase(Addr addr)
{
for (auto& sub_filter : filters) {
sub_filter->unset(addr);
diff --git a/src/base/filters/multi_bloom_filter.hh
b/src/base/filters/multi_bloom_filter.hh
index 43cb94b..eaa2ca0 100644
--- a/src/base/filters/multi_bloom_filter.hh
+++ b/src/base/filters/multi_bloom_filter.hh
@@ -64,12 +64,14 @@
void clear() override;
void set(Addr addr) override;
- void unset(Addr addr) override;
void merge(const Base* other) override;
int getCount(Addr addr) const override;
int getTotalCount() const override;
+ protected:
+ void erase(Addr addr) override;
+
private:
/** Sub-filters used by this filter. */
std::vector<Base*> filters;
--
To view, visit https://gem5-review.googlesource.com/c/public/gem5/+/18878
To unsubscribe, or for help writing mail filters, visit
https://gem5-review.googlesource.com/settings
Gerrit-Project: public/gem5
Gerrit-Branch: master
Gerrit-Change-Id: I24f3f0a16d4743e6fb3c0fa76850996f258acb8f
Gerrit-Change-Number: 18878
Gerrit-PatchSet: 1
Gerrit-Owner: Daniel Carvalho <[email protected]>
Gerrit-MessageType: newchange
_______________________________________________
gem5-dev mailing list
[email protected]
http://m5sim.org/mailman/listinfo/gem5-dev
