1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
|
/**
* 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
*/
/**
* @file
* Declaration of a Second-Chance replacement policy.
* The victim is chosen using the timestamp. The oldest entry is chosen
* to be evicted, if it hasn't been touched since its insertion. If it
* has been touched, it is given a second chance and re-inserted at the
* end of the queue.
*/
#ifndef __MEM_CACHE_REPLACEMENT_POLICIES_SECOND_CHANCE_RP_HH__
#define __MEM_CACHE_REPLACEMENT_POLICIES_SECOND_CHANCE_RP_HH__
#include "mem/cache/replacement_policies/base.hh"
#include "mem/cache/replacement_policies/fifo_rp.hh"
struct SecondChanceRPParams;
class SecondChanceRP : public FIFORP
{
protected:
/** Second-Chance-specific implementation of replacement data. */
struct SecondChanceReplData : public FIFOReplData
{
/**
* This is different from isTouched because isTouched accounts only
* for insertion, while this bit is reset every new re-insertion.
* @sa SecondChanceRP.
*/
bool hasSecondChance;
/**
* Default constructor.
*/
SecondChanceReplData() : FIFOReplData(), hasSecondChance(false) {}
};
/**
* Use replacement data's second chance.
*
* @param replacement_data Entry that will use its second chance.
*/
void useSecondChance(
const std::shared_ptr<SecondChanceReplData>& replacement_data) const;
public:
/** Convenience typedef. */
typedef SecondChanceRPParams Params;
/**
* Construct and initiliaze this replacement policy.
*/
SecondChanceRP(const Params *p);
/**
* Destructor.
*/
~SecondChanceRP() {}
/**
* Invalidate replacement data to set it as the next probable victim.
* Invalid entries do not have a second chance, and their last touch tick
* is set as the oldest possible.
*
* @param replacement_data Replacement data to be invalidated.
*/
void invalidate(const std::shared_ptr<ReplacementData>& replacement_data)
const override;
/**
* Touch an entry to update its re-insertion tick and second chance bit.
*
* @param replacement_data Replacement data to be touched.
*/
void touch(const std::shared_ptr<ReplacementData>& replacement_data) const
override;
/**
* Reset replacement data. Used when an entry is inserted or re-inserted
* in the queue.
* Sets its insertion tick and second chance bit.
*
* @param replacement_data Replacement data to be reset.
*/
void reset(const std::shared_ptr<ReplacementData>& replacement_data) const
override;
/**
* Find replacement victim using insertion timestamps and second chance
* bit.
*
* @param cands Replacement candidates, selected by indexing policy.
* @return Replacement entry to be replaced.
*/
ReplaceableEntry* getVictim(const ReplacementCandidates& candidates) const
override;
/**
* Instantiate a replacement data entry.
*
* @return A shared pointer to the new replacement data.
*/
std::shared_ptr<ReplacementData> instantiateEntry() override;
};
#endif // __MEM_CACHE_REPLACEMENT_POLICIES_SECOND_CHANCE_RP_HH__
|
