mem-ruby: Generalize use of bloom filters' isSet

In general the corresponding entries of an address are considered
to be set when the sum of all of them reach their maximum value
(i.e., they are all set), so generalize that into the base class.

Change-Id: If50b8c56065ad339b4ff2322ddc3c077a3bfc518
Signed-off-by: Daniel R. Carvalho <odanrc@yahoo.com.br>
Reviewed-on: https://gem5-review.googlesource.com/c/public/gem5/+/18735
Maintainer: Nikos Nikoleris <nikos.nikoleris@arm.com>
Tested-by: kokoro <noreply+kokoro@google.com>
Reviewed-by: Nikos Nikoleris <nikos.nikoleris@arm.com>

15 files changed, 52 insertions, 91 deletions

diff --git a/src/mem/ruby/filters/AbstractBloomFilter.hh b/src/mem/ruby/filters/AbstractBloomFilter.hh
index 851e5d9be..672236527 100644
--- a/src/mem/ruby/filters/AbstractBloomFilter.hh
+++ b/src/mem/ruby/filters/AbstractBloomFilter.hh
@@ -46,12 +46,18 @@ class AbstractBloomFilter
     /** Number of bits needed to represent the size of the filter. */
     const int sizeBits;
 
+    /** Threshold at which a filter entry starts being considered as set. */
+    const int setThreshold;
+
   public:
     /**
      * Create and clear the filter.
+     *
+     * @param size The number of filter entries.
+     * @param threshold The threshold that limits a set entry.
      */
-    AbstractBloomFilter(std::size_t size)
-        : filter(size), sizeBits(floorLog2(size))
+    AbstractBloomFilter(std::size_t size, int threshold)
+        : filter(size), sizeBits(floorLog2(size)), setThreshold(threshold)
     {
         clear();
     }
@@ -94,7 +100,11 @@ class AbstractBloomFilter
      * @param addr The address being parsed.
      * @return Whether the respective filter entry is set.
      */
-    virtual bool isSet(Addr addr) = 0;
+    virtual bool
+    isSet(Addr addr) const
+    {
+        return getCount(addr) >= setThreshold;
+    }
 
     /**
      * Get the value stored in the corresponding filter entry of an address.
@@ -102,7 +112,7 @@ class AbstractBloomFilter
      * @param addr The address being parsed.
      * @param Get the value stored in the respective filter entry.
      */
-    virtual int getCount(Addr addr) { return 0; }
+    virtual int getCount(Addr addr) const { return 0; }
 
     /**
      * Get the total value stored in the filter entries.
diff --git a/src/mem/ruby/filters/BlockBloomFilter.cc b/src/mem/ruby/filters/BlockBloomFilter.cc
index f9942fe71..f59a17547 100644
--- a/src/mem/ruby/filters/BlockBloomFilter.cc
+++ b/src/mem/ruby/filters/BlockBloomFilter.cc
@@ -32,7 +32,7 @@
 #include "mem/ruby/system/RubySystem.hh"
 
 BlockBloomFilter::BlockBloomFilter(int size)
-    : AbstractBloomFilter(size)
+    : AbstractBloomFilter(size, 1)
 {
 }
 
@@ -52,14 +52,8 @@ BlockBloomFilter::unset(Addr addr)
     filter[hash(addr)] = 0;
 }
 
-bool
-BlockBloomFilter::isSet(Addr addr)
-{
-    return filter[hash(addr)];
-}
-
 int
-BlockBloomFilter::getCount(Addr addr)
+BlockBloomFilter::getCount(Addr addr) const
 {
     return filter[hash(addr)];
 }
diff --git a/src/mem/ruby/filters/BlockBloomFilter.hh b/src/mem/ruby/filters/BlockBloomFilter.hh
index 7c8ffc19c..fd75ba890 100644
--- a/src/mem/ruby/filters/BlockBloomFilter.hh
+++ b/src/mem/ruby/filters/BlockBloomFilter.hh
@@ -39,9 +39,7 @@ class BlockBloomFilter : public AbstractBloomFilter
 
     void set(Addr addr) override;
     void unset(Addr addr) override;
-
-    bool isSet(Addr addr);
-    int getCount(Addr addr);
+    int getCount(Addr addr) const override;
 
   private:
     int hash(Addr addr) const;
diff --git a/src/mem/ruby/filters/BulkBloomFilter.cc b/src/mem/ruby/filters/BulkBloomFilter.cc
index a917a1491..251274bd6 100644
--- a/src/mem/ruby/filters/BulkBloomFilter.cc
+++ b/src/mem/ruby/filters/BulkBloomFilter.cc
@@ -32,7 +32,7 @@
 #include "mem/ruby/system/RubySystem.hh"
 
 BulkBloomFilter::BulkBloomFilter(int size)
-    : AbstractBloomFilter(size), sectorBits(sizeBits - 1)
+    : AbstractBloomFilter(size, 1), sectorBits(sizeBits - 1)
 {
 }
 
@@ -61,7 +61,7 @@ BulkBloomFilter::set(Addr addr)
 }
 
 bool
-BulkBloomFilter::isSet(Addr addr)
+BulkBloomFilter::isSet(Addr addr) const
 {
     // c0 contains the cache index bits
     const int filter_size = filter.size();
@@ -119,9 +119,9 @@ BulkBloomFilter::isSet(Addr addr)
 }
 
 int
-BulkBloomFilter::getCount(Addr addr)
+BulkBloomFilter::getCount(Addr addr) const
 {
-    // not used
+    // TODO as in the multi-hashed filters
     return 0;
 }
 
diff --git a/src/mem/ruby/filters/BulkBloomFilter.hh b/src/mem/ruby/filters/BulkBloomFilter.hh
index b6f52b960..7be00e673 100644
--- a/src/mem/ruby/filters/BulkBloomFilter.hh
+++ b/src/mem/ruby/filters/BulkBloomFilter.hh
@@ -45,8 +45,8 @@ class BulkBloomFilter : public AbstractBloomFilter
 
     void set(Addr addr) override;
 
-    bool isSet(Addr addr);
-    int getCount(Addr addr);
+    bool isSet(Addr addr) const override;
+    int getCount(Addr addr) const override;
 
   private:
     /** Permutes the address to generate its signature. */
diff --git a/src/mem/ruby/filters/H3BloomFilter.cc b/src/mem/ruby/filters/H3BloomFilter.cc
index f6ee8a168..485cc3169 100644
--- a/src/mem/ruby/filters/H3BloomFilter.cc
+++ b/src/mem/ruby/filters/H3BloomFilter.cc
@@ -354,8 +354,8 @@ static int H3[64][16] = {
 };
 
 H3BloomFilter::H3BloomFilter(int size, int num_hashes, bool parallel)
-    : AbstractBloomFilter(size), numHashes(num_hashes), isParallel(parallel),
-      parFilterSize(filter.size() / numHashes)
+    : AbstractBloomFilter(size, num_hashes), numHashes(num_hashes),
+      isParallel(parallel), parFilterSize(filter.size() / numHashes)
 {
     fatal_if(numHashes > 16, "There are only 16 hash functions implemented.");
 }
@@ -382,22 +382,14 @@ H3BloomFilter::set(Addr addr)
     }
 }
 
-bool
-H3BloomFilter::isSet(Addr addr)
-{
-    bool res = true;
-
-    for (int i = 0; i < numHashes; i++) {
-        int idx = hash(addr, i);
-        res = res && filter[idx];
-    }
-    return res;
-}
-
 int
-H3BloomFilter::getCount(Addr addr)
+H3BloomFilter::getCount(Addr addr) const
 {
-    return isSet(addr)? 1: 0;
+    int count = 0;
+    for (int i=0; i < numHashes; i++) {
+        count += filter[hash(addr, i)];
+    }
+    return count;
 }
 
 int
diff --git a/src/mem/ruby/filters/H3BloomFilter.hh b/src/mem/ruby/filters/H3BloomFilter.hh
index 6cfa29337..f92878b45 100644
--- a/src/mem/ruby/filters/H3BloomFilter.hh
+++ b/src/mem/ruby/filters/H3BloomFilter.hh
@@ -43,8 +43,7 @@ class H3BloomFilter : public AbstractBloomFilter
 
     void merge(const AbstractBloomFilter* other) override;
     void set(Addr addr) override;
-    bool isSet(Addr addr);
-    int getCount(Addr addr) override;
+    int getCount(Addr addr) const override;
 
   private:
     /**
diff --git a/src/mem/ruby/filters/LSB_CountingBloomFilter.cc b/src/mem/ruby/filters/LSB_CountingBloomFilter.cc
index 06e2d4f67..a718b4344 100644
--- a/src/mem/ruby/filters/LSB_CountingBloomFilter.cc
+++ b/src/mem/ruby/filters/LSB_CountingBloomFilter.cc
@@ -33,7 +33,9 @@
 
 LSB_CountingBloomFilter::LSB_CountingBloomFilter(std::size_t filter_size,
                                                  int max_value)
-    : AbstractBloomFilter(filter_size), maxValue(max_value)
+    // Here we assume that isSet will return true only when the counter
+    // saturates
+    : AbstractBloomFilter(filter_size, max_value), maxValue(max_value)
 {
 }
 
@@ -57,15 +59,8 @@ LSB_CountingBloomFilter::unset(Addr addr)
         filter[i] -= 1;
 }
 
-bool
-LSB_CountingBloomFilter::isSet(Addr addr)
-{
-    // TODO
-    return false;
-}
-
 int
-LSB_CountingBloomFilter::getCount(Addr addr)
+LSB_CountingBloomFilter::getCount(Addr addr) const
 {
     return filter[hash(addr)];
 }
diff --git a/src/mem/ruby/filters/LSB_CountingBloomFilter.hh b/src/mem/ruby/filters/LSB_CountingBloomFilter.hh
index 4fc635581..e9ffbcbd1 100644
--- a/src/mem/ruby/filters/LSB_CountingBloomFilter.hh
+++ b/src/mem/ruby/filters/LSB_CountingBloomFilter.hh
@@ -40,8 +40,7 @@ class LSB_CountingBloomFilter : public AbstractBloomFilter
     void set(Addr addr) override;
     void unset(Addr addr) override;
 
-    bool isSet(Addr addr);
-    int getCount(Addr addr);
+    int getCount(Addr addr) const override;
 
   private:
     int hash(Addr addr) const;
diff --git a/src/mem/ruby/filters/MultiBitSelBloomFilter.cc b/src/mem/ruby/filters/MultiBitSelBloomFilter.cc
index aa1438fd3..c453d10bf 100644
--- a/src/mem/ruby/filters/MultiBitSelBloomFilter.cc
+++ b/src/mem/ruby/filters/MultiBitSelBloomFilter.cc
@@ -32,7 +32,7 @@
 
 MultiBitSelBloomFilter::MultiBitSelBloomFilter(std::size_t filter_size,
     int num_hashes, int skip_bits, bool is_parallel)
-    : AbstractBloomFilter(filter_size), numHashes(num_hashes),
+    : AbstractBloomFilter(filter_size, num_hashes), numHashes(num_hashes),
       skipBits(skip_bits),
       parFilterSize(filter_size / numHashes),
       isParallel(is_parallel)
@@ -62,22 +62,14 @@ MultiBitSelBloomFilter::set(Addr addr)
     }
 }
 
-bool
-MultiBitSelBloomFilter::isSet(Addr addr)
+int
+MultiBitSelBloomFilter::getCount(Addr addr) const
 {
-    bool res = true;
-
+    int count = 0;
     for (int i=0; i < numHashes; i++) {
-        int idx = hash(addr, i);
-        res = res && filter[idx];
+        count += filter[hash(addr, i)];
     }
-    return res;
-}
-
-int
-MultiBitSelBloomFilter::getCount(Addr addr)
-{
-    return isSet(addr)? 1: 0;
+    return count;
 }
 
 int
diff --git a/src/mem/ruby/filters/MultiBitSelBloomFilter.hh b/src/mem/ruby/filters/MultiBitSelBloomFilter.hh
index 2d6954004..914875f85 100644
--- a/src/mem/ruby/filters/MultiBitSelBloomFilter.hh
+++ b/src/mem/ruby/filters/MultiBitSelBloomFilter.hh
@@ -40,8 +40,7 @@ class MultiBitSelBloomFilter : public AbstractBloomFilter
 
     void merge(const AbstractBloomFilter* other) override;
     void set(Addr addr) override;
-    bool isSet(Addr addr);
-    int getCount(Addr addr);
+    int getCount(Addr addr) const override;
 
   private:
     int hash(Addr addr, int hash_number) const;
diff --git a/src/mem/ruby/filters/MultiGrainBloomFilter.cc b/src/mem/ruby/filters/MultiGrainBloomFilter.cc
index 76016b2ff..7bf9dfe01 100644
--- a/src/mem/ruby/filters/MultiGrainBloomFilter.cc
+++ b/src/mem/ruby/filters/MultiGrainBloomFilter.cc
@@ -32,7 +32,7 @@
 #include "mem/ruby/system/RubySystem.hh"
 
 MultiGrainBloomFilter::MultiGrainBloomFilter(int head, int tail)
-    : AbstractBloomFilter(head),
+    : AbstractBloomFilter(head, 2),
       pageFilter(tail), pageFilterSizeBits(floorLog2(tail))
 {
 }
@@ -61,21 +61,13 @@ MultiGrainBloomFilter::set(Addr addr)
 
 }
 
-bool
-MultiGrainBloomFilter::isSet(Addr addr)
+int
+MultiGrainBloomFilter::getCount(Addr addr) const
 {
     int i = hash(addr);
     assert(i < filter.size());
     assert(pageHash(addr) < pageFilter.size());
-    // we have to have both indices set
-    return (filter[i] && pageFilter[i]);
-}
-
-int
-MultiGrainBloomFilter::getCount(Addr addr)
-{
-    // not used
-    return 0;
+    return filter[i] + pageFilter[i];
 }
 
 int
diff --git a/src/mem/ruby/filters/MultiGrainBloomFilter.hh b/src/mem/ruby/filters/MultiGrainBloomFilter.hh
index 148f42df2..d45b58708 100644
--- a/src/mem/ruby/filters/MultiGrainBloomFilter.hh
+++ b/src/mem/ruby/filters/MultiGrainBloomFilter.hh
@@ -46,8 +46,7 @@ class MultiGrainBloomFilter : public AbstractBloomFilter
     void clear() override;
     void set(Addr addr) override;
 
-    bool isSet(Addr addr);
-    int getCount(Addr addr);
+    int getCount(Addr addr) const override;
     int getTotalCount() const override;
 
   private:
diff --git a/src/mem/ruby/filters/NonCountingBloomFilter.cc b/src/mem/ruby/filters/NonCountingBloomFilter.cc
index 46e74d244..3196eb64f 100644
--- a/src/mem/ruby/filters/NonCountingBloomFilter.cc
+++ b/src/mem/ruby/filters/NonCountingBloomFilter.cc
@@ -32,7 +32,7 @@
 #include "mem/ruby/system/RubySystem.hh"
 
 NonCountingBloomFilter::NonCountingBloomFilter(std::size_t size, int skip_bits)
-    : AbstractBloomFilter(size), skipBits(skip_bits)
+    : AbstractBloomFilter(size, 1), skipBits(skip_bits)
 {
 }
 
@@ -62,15 +62,8 @@ NonCountingBloomFilter::unset(Addr addr)
     filter[hash(addr)] = 0;
 }
 
-bool
-NonCountingBloomFilter::isSet(Addr addr)
-{
-    return filter[hash(addr)];
-}
-
-
 int
-NonCountingBloomFilter::getCount(Addr addr)
+NonCountingBloomFilter::getCount(Addr addr) const
 {
     return filter[hash(addr)];
 }
diff --git a/src/mem/ruby/filters/NonCountingBloomFilter.hh b/src/mem/ruby/filters/NonCountingBloomFilter.hh
index 08c84ee7c..1553bec0b 100644
--- a/src/mem/ruby/filters/NonCountingBloomFilter.hh
+++ b/src/mem/ruby/filters/NonCountingBloomFilter.hh
@@ -41,8 +41,7 @@ class NonCountingBloomFilter : public AbstractBloomFilter
     void set(Addr addr) override;
     void unset(Addr addr) override;
 
-    bool isSet(Addr addr);
-    int getCount(Addr addr);
+    int getCount(Addr addr) const override;
 
   private:
     int hash(Addr addr) const;