From 04d236e5687ba11d71ced0a37044fdd55aa5bb42 Mon Sep 17 00:00:00 2001
From: "Daniel R. Carvalho" <odanrc@yahoo.com.br>
Date: Fri, 23 Mar 2018 16:08:51 +0100
Subject: mem-cache: Create Second-Chance replacement policy

Implementation of a Second-Chance replacement policy. Similar to FIFO,
but every block is given a second chance if it has been touched.

Change-Id: Id4d52b698d0045a4914a4d848fdf9c3c00a28508
Reviewed-on: https://gem5-review.googlesource.com/9441
Reviewed-by: Nikos Nikoleris <nikos.nikoleris@arm.com>
Maintainer: Nikos Nikoleris <nikos.nikoleris@arm.com>
---
 .../cache/replacement_policies/second_chance_rp.cc | 134 +++++++++++++++++++++
 1 file changed, 134 insertions(+)
 create mode 100644 src/mem/cache/replacement_policies/second_chance_rp.cc

(limited to 'src/mem/cache/replacement_policies/second_chance_rp.cc')

diff --git a/src/mem/cache/replacement_policies/second_chance_rp.cc b/src/mem/cache/replacement_policies/second_chance_rp.cc
new file mode 100644
index 000000000..2560a9846
--- /dev/null
+++ b/src/mem/cache/replacement_policies/second_chance_rp.cc
@@ -0,0 +1,134 @@
+/**
+ * Copyright (c) 2018 Inria
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions are
+ * met: redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer;
+ * redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in the
+ * documentation and/or other materials provided with the distribution;
+ * neither the name of the copyright holders nor the names of its
+ * contributors may be used to endorse or promote products derived from
+ * this software without specific prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+ * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+ * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
+ * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
+ * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+ * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
+ * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+ * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+ * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ *
+ * Authors: Daniel Carvalho
+ */
+
+#include "mem/cache/replacement_policies/second_chance_rp.hh"
+
+SecondChanceRP::SecondChanceRP(const Params *p)
+    : FIFORP(p)
+{
+}
+
+void
+SecondChanceRP::useSecondChance(
+    const std::shared_ptr<SecondChanceReplData>& replacement_data) const
+{
+    // Reset FIFO data
+    FIFORP::reset(replacement_data);
+
+    // Use second chance
+    replacement_data->hasSecondChance = false;
+}
+
+void
+SecondChanceRP::invalidate(
+    const std::shared_ptr<ReplacementData>& replacement_data) const
+{
+    FIFORP::invalidate(replacement_data);
+
+    // Do not give a second chance to invalid entries
+    std::static_pointer_cast<SecondChanceReplData>(
+        replacement_data)->hasSecondChance = false;
+}
+
+void
+SecondChanceRP::touch(const std::shared_ptr<ReplacementData>& replacement_data) const
+{
+    FIFORP::touch(replacement_data);
+
+    // Whenever an entry is touched, it is given a second chance
+    std::static_pointer_cast<SecondChanceReplData>(
+        replacement_data)->hasSecondChance = true;
+}
+
+void
+SecondChanceRP::reset(const std::shared_ptr<ReplacementData>& replacement_data) const
+{
+    FIFORP::reset(replacement_data);
+
+    // Entries are inserted with a second chance
+    std::static_pointer_cast<SecondChanceReplData>(
+        replacement_data)->hasSecondChance = true;
+}
+
+ReplaceableEntry*
+SecondChanceRP::getVictim(const ReplacementCandidates& candidates) const
+{
+    // There must be at least one replacement candidate
+    assert(candidates.size() > 0);
+
+    // Search for invalid entries, as they have the eviction priority
+    for (const auto& candidate : candidates) {
+        // Cast candidate's replacement data
+        std::shared_ptr<SecondChanceReplData> candidate_replacement_data =
+            std::static_pointer_cast<SecondChanceReplData>(
+                candidate->replacementData);
+
+        // Stop iteration if found an invalid entry
+        if ((candidate_replacement_data->tickInserted == Tick(0)) &&
+            !candidate_replacement_data->hasSecondChance) {
+            return candidate;
+        }
+    }
+
+    // Visit all candidates to find victim
+    ReplaceableEntry* victim = candidates[0];
+    bool search_victim = true;
+    while (search_victim) {
+        // Do a FIFO victim search
+        victim = FIFORP::getVictim(candidates);
+
+        // Cast victim's replacement data for code readability
+        std::shared_ptr<SecondChanceReplData> victim_replacement_data =
+            std::static_pointer_cast<SecondChanceReplData>(
+                victim->replacementData);
+
+        // If victim has a second chance, use it and repeat search
+        if (victim_replacement_data->hasSecondChance) {
+            useSecondChance(victim_replacement_data);
+        } else {
+            // Found victim
+            search_victim = false;
+        }
+    }
+
+    return victim;
+}
+
+std::shared_ptr<ReplacementData>
+SecondChanceRP::instantiateEntry()
+{
+    return std::shared_ptr<ReplacementData>(new SecondChanceReplData());
+}
+
+SecondChanceRP*
+SecondChanceRPParams::create()
+{
+    return new SecondChanceRP(this);
+}
-- 
cgit v1.2.3