1/**
2 * Copyright (c) 2018 Inria
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 * Authors: Daniel Carvalho
29 */
30
31/**
32 * @file
33 * Declaration of a Pseudo-Least Recently Used replacement policy.
34 * The victim is chosen using a tree of bit timestamps.
35 *
36 * A tree contains consists of leafs that represent the direction to take when
37 * searching for the LRU entry.
38 *
39 * Let's assume each tree contains 8 replacement data entries. For example, if
40 * these entries are named from A to H, and the tree's bits are:
41 * ____1____
42 * __0__ __1__
43 * _0_ _1_ _1_ _0_
44 * A B C D E F G H
45 *
46 * Then the current PLRU entry is given by the sequence:
47 * 1 (get right child) -> 1 (get right child) -> 0 (get left child) -> G
48 *
49 * When an entry is touched the bits of the parent nodes are iteratively
50 * updated to point away from it. Therefore, if entry B is touched, its parent,
51 * grandparents, etc would be updated, and we'd end up with the following tree:
52 * ____1____
53 * __1__ __1__
54 * _0_ _1_ _1_ _0_
55 * A B C D E F G H
56 *
57 * Explanation: The parent of B must point away from it, that is, to the left
58 * child, but it is already doing so, so it is left unmodified (0). Then the
59 * grandparent must point to the right subtree, as B belongs to its left
60 * subtree (0 becomes 1). Lastly, the root must point away from the
61 * grandparent, so it is left unmodified (0).
62 *
63 * For invalidations the process is similar to touches, but instead of pointing
64 * away, the bits point toward the entry.
65 *
66 * Consecutive calls to instantiateEntry() use the same tree up to numLeaves.
67 * When numLeaves replacement datas have been created, a new tree is generated,
68 * and the counter is reset.
69 */
70
71#ifndef __MEM_CACHE_REPLACEMENT_POLICIES_TREE_PLRU_RP_HH__
72#define __MEM_CACHE_REPLACEMENT_POLICIES_TREE_PLRU_RP_HH__
73
74#include <cstdint>
75#include <memory>
76#include <vector>
77
78#include "mem/cache/replacement_policies/base.hh"
79
80struct TreePLRURPParams;
81
82class TreePLRURP : public BaseReplacementPolicy
83{
84 private:
85 /**
86 * Instead of implementing the tree itself with pointers, it is implemented
87 * as an array of bits. The index of the node defines its position in the
88 * tree, and its parent. Index 0 represents the root, 1 is its left node,
89 * and 2 is its right node. Then, in a BFS fashion this is expanded to the
90 * following nodes (3 and 4 are respectively 1's left and right nodes, and
91 * 5 and 6 are 2's left and right nodes, and so on).
92 *
93 * i.e., the following trees are equivalent in this representation:
94 * ____1____
95 * __0__ __1__
96 * _0_ _1_ _1_ _0_
97 * A B C D E F G H
98 *
99 * 1 0 1 0 1 1 0
100 *
101 * Notice that the replacement data entries are not represented in the tree
102 * to avoid unnecessary storage costs.
103 */
104 typedef std::vector<bool> PLRUTree;
105
106 /**
107 * Number of leaves that share a single replacement data.
108 */
109 const uint64_t numLeaves;
110
111 /**
112 * Count of the number of sharers of a replacement data. It is used when
113 * instantiating entries to share a replacement data among many replaceable
114 * entries.
115 */
116 uint64_t count;
117
118 /**
119 * Holds the latest temporary tree instance created by instantiateEntry().
120 */
121 PLRUTree* treeInstance;
122
123 protected:
124 /**
125 * Tree-PLRU-specific implementation of replacement data. Each replacement
126 * data shares its tree with other entries.
127 */
128 struct TreePLRUReplData : ReplacementData
129 {
130 /**
131 * Theoretical index of this replacement data in the tree. In practice,
132 * the corresponding node does not exist, as the tree stores only the
133 * nodes that are not leaves.
134 */
135 const uint64_t index;
136
137 /**
138 * Shared tree pointer. A tree is shared between numLeaves nodes, so
139 * that accesses to a replacement data entry updates the PLRU bits of
140 * all other replacement data entries in its set.
141 */
142 std::shared_ptr<PLRUTree> tree;
143
144 /**
145 * Default constructor. Invalidate data.
146 *
147 * @param index Index of the corresponding entry in the tree.
148 * @param tree The shared tree pointer.
149 */
150 TreePLRUReplData(const uint64_t index, std::shared_ptr<PLRUTree> tree);
151 };
152
153 public:
154 /** Convenience typedef. */
155 typedef TreePLRURPParams Params;
156
157 /**
158 * Construct and initiliaze this replacement policy.
159 */
160 TreePLRURP(const Params *p);
161
162 /**
163 * Destructor.
164 */
165 ~TreePLRURP() {}
166
167 /**
168 * Invalidate replacement data to set it as the next probable victim.
169 * Makes tree leaf of replacement data the LRU (tree bits point to it).
170 *
171 * @param replacement_data Replacement data to be invalidated.
172 */
173 void invalidate(const std::shared_ptr<ReplacementData>& replacement_data)
174 const override;
175
176 /**
177 * Touch an entry to update its replacement data.
178 * Makes tree leaf of replacement data the MRU.
179 *
180 * @param replacement_data Replacement data to be touched.
181 */
182 void touch(const std::shared_ptr<ReplacementData>& replacement_data) const
183 override;
184
185 /**
186 * Reset replacement data. Used when an entry is inserted. Provides the
187 * same functionality as touch().
188 *
189 * @param replacement_data Replacement data to be reset.
190 */
191 void reset(const std::shared_ptr<ReplacementData>& replacement_data) const
192 override;
193
194 /**
195 * Find replacement victim using TreePLRU bits. It is assumed that all
196 * candidates share the same replacement data tree.
197 *
198 * @param candidates Replacement candidates, selected by indexing policy.
199 * @return Replacement entry to be replaced.
200 */
201 ReplaceableEntry* getVictim(const ReplacementCandidates& candidates) const
202 override;
203
204 /**
205 * Instantiate a replacement data entry. Consecutive calls to this
206 * function use the same tree up to numLeaves. When numLeaves replacement
207 * data have been created, a new tree is generated, and the counter is
208 * reset.
209 * Therefore, it is essential that entries that share the same replacement
210 * data call this function consecutively.
211 *
212 * @return A shared pointer to the new replacement data.
213 */
214 std::shared_ptr<ReplacementData> instantiateEntry() override;
215};
216
217#endif // __MEM_CACHE_REPLACEMENT_POLICIES_TREE_PLRU_RP_HH__