fa_lru.cc (12513:4dfc54394b5a) fa_lru.cc (12553:514f2e4fb751)
1/*
2 * Copyright (c) 2013,2016 ARM Limited
3 * All rights reserved.
4 *
5 * The license below extends only to copyright in the software and shall
6 * not be construed as granting a license to any other intellectual
7 * property including but not limited to intellectual property relating
8 * to a hardware implementation of the functionality of the software
9 * licensed hereunder. You may use the software subject to the license
10 * terms below provided that you ensure that this notice is replicated
11 * unmodified and in its entirety in all distributions of the software,
12 * modified or unmodified, in source code or in binary form.
13 *
14 * Copyright (c) 2003-2005 The Regents of The University of Michigan
15 * All rights reserved.
16 *
17 * Redistribution and use in source and binary forms, with or without
18 * modification, are permitted provided that the following conditions are
19 * met: redistributions of source code must retain the above copyright
20 * notice, this list of conditions and the following disclaimer;
21 * redistributions in binary form must reproduce the above copyright
22 * notice, this list of conditions and the following disclaimer in the
23 * documentation and/or other materials provided with the distribution;
24 * neither the name of the copyright holders nor the names of its
25 * contributors may be used to endorse or promote products derived from
26 * this software without specific prior written permission.
27 *
28 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
29 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
30 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
31 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
32 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
33 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
34 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
35 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
36 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
37 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
38 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
39 *
40 * Authors: Erik Hallnor
41 */
42
43/**
44 * @file
45 * Definitions a fully associative LRU tagstore.
46 */
47
48#include "mem/cache/tags/fa_lru.hh"
49
50#include <cassert>
51#include <sstream>
52
53#include "base/intmath.hh"
54#include "base/logging.hh"
55
56using namespace std;
57
58FALRU::FALRU(const Params *p)
59 : BaseTags(p), cacheBoundaries(nullptr)
60{
61 if (!isPowerOf2(blkSize))
62 fatal("cache block size (in bytes) `%d' must be a power of two",
63 blkSize);
64 if (!isPowerOf2(size))
65 fatal("Cache Size must be power of 2 for now");
66
67 // Track all cache sizes from 128K up by powers of 2
68 numCaches = floorLog2(size) - 17;
69 if (numCaches >0){
70 cacheBoundaries = new FALRUBlk *[numCaches];
71 cacheMask = (ULL(1) << numCaches) - 1;
72 } else {
73 cacheMask = 0;
74 }
75
1/*
2 * Copyright (c) 2013,2016 ARM Limited
3 * All rights reserved.
4 *
5 * The license below extends only to copyright in the software and shall
6 * not be construed as granting a license to any other intellectual
7 * property including but not limited to intellectual property relating
8 * to a hardware implementation of the functionality of the software
9 * licensed hereunder. You may use the software subject to the license
10 * terms below provided that you ensure that this notice is replicated
11 * unmodified and in its entirety in all distributions of the software,
12 * modified or unmodified, in source code or in binary form.
13 *
14 * Copyright (c) 2003-2005 The Regents of The University of Michigan
15 * All rights reserved.
16 *
17 * Redistribution and use in source and binary forms, with or without
18 * modification, are permitted provided that the following conditions are
19 * met: redistributions of source code must retain the above copyright
20 * notice, this list of conditions and the following disclaimer;
21 * redistributions in binary form must reproduce the above copyright
22 * notice, this list of conditions and the following disclaimer in the
23 * documentation and/or other materials provided with the distribution;
24 * neither the name of the copyright holders nor the names of its
25 * contributors may be used to endorse or promote products derived from
26 * this software without specific prior written permission.
27 *
28 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
29 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
30 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
31 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
32 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
33 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
34 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
35 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
36 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
37 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
38 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
39 *
40 * Authors: Erik Hallnor
41 */
42
43/**
44 * @file
45 * Definitions a fully associative LRU tagstore.
46 */
47
48#include "mem/cache/tags/fa_lru.hh"
49
50#include <cassert>
51#include <sstream>
52
53#include "base/intmath.hh"
54#include "base/logging.hh"
55
56using namespace std;
57
58FALRU::FALRU(const Params *p)
59 : BaseTags(p), cacheBoundaries(nullptr)
60{
61 if (!isPowerOf2(blkSize))
62 fatal("cache block size (in bytes) `%d' must be a power of two",
63 blkSize);
64 if (!isPowerOf2(size))
65 fatal("Cache Size must be power of 2 for now");
66
67 // Track all cache sizes from 128K up by powers of 2
68 numCaches = floorLog2(size) - 17;
69 if (numCaches >0){
70 cacheBoundaries = new FALRUBlk *[numCaches];
71 cacheMask = (ULL(1) << numCaches) - 1;
72 } else {
73 cacheMask = 0;
74 }
75
76 numBlocks = size/blkSize;
77
78 blks = new FALRUBlk[numBlocks];
79 head = &(blks[0]);
80 tail = &(blks[numBlocks-1]);
81
82 head->prev = nullptr;
83 head->next = &(blks[1]);
84 head->inCache = cacheMask;
85
86 tail->prev = &(blks[numBlocks-2]);
87 tail->next = nullptr;
88 tail->inCache = 0;
89
90 unsigned index = (1 << 17) / blkSize;
91 unsigned j = 0;
92 int flags = cacheMask;
93 for (unsigned i = 1; i < numBlocks - 1; i++) {
94 blks[i].inCache = flags;
95 if (i == index - 1){
96 cacheBoundaries[j] = &(blks[i]);
97 flags &= ~ (1<<j);
98 ++j;
99 index = index << 1;
100 }
101 blks[i].prev = &(blks[i-1]);
102 blks[i].next = &(blks[i+1]);
103 blks[i].isTouched = false;
104 blks[i].set = 0;
105 blks[i].way = i;
106 }
107 assert(j == numCaches);
108 assert(index == numBlocks);
109 //assert(check());
110}
111
112FALRU::~FALRU()
113{
114 if (numCaches)
115 delete[] cacheBoundaries;
116
117 delete[] blks;
118}
119
120void
121FALRU::regStats()
122{
123 using namespace Stats;
124 BaseTags::regStats();
125 hits
126 .init(numCaches+1)
127 .name(name() + ".falru_hits")
128 .desc("The number of hits in each cache size.")
129 ;
130 misses
131 .init(numCaches+1)
132 .name(name() + ".falru_misses")
133 .desc("The number of misses in each cache size.")
134 ;
135 accesses
136 .name(name() + ".falru_accesses")
137 .desc("The number of accesses to the FA LRU cache.")
138 ;
139
140 for (unsigned i = 0; i <= numCaches; ++i) {
141 stringstream size_str;
142 if (i < 3){
143 size_str << (1<<(i+7)) <<"K";
144 } else {
145 size_str << (1<<(i-3)) <<"M";
146 }
147
148 hits.subname(i, size_str.str());
149 hits.subdesc(i, "Hits in a " + size_str.str() +" cache");
150 misses.subname(i, size_str.str());
151 misses.subdesc(i, "Misses in a " + size_str.str() +" cache");
152 }
153}
154
155FALRUBlk *
156FALRU::hashLookup(Addr addr) const
157{
158 tagIterator iter = tagHash.find(addr);
159 if (iter != tagHash.end()) {
160 return (*iter).second;
161 }
162 return nullptr;
163}
164
165void
166FALRU::invalidate(CacheBlk *blk)
167{
168 assert(blk);
169 tagsInUse--;
170}
171
172CacheBlk*
173FALRU::accessBlock(Addr addr, bool is_secure, Cycles &lat)
174{
175 return accessBlock(addr, is_secure, lat, 0);
176}
177
178CacheBlk*
179FALRU::accessBlock(Addr addr, bool is_secure, Cycles &lat, int *inCache)
180{
181 accesses++;
182 int tmp_in_cache = 0;
183 Addr blkAddr = blkAlign(addr);
184 FALRUBlk* blk = hashLookup(blkAddr);
185
186 if (blk && blk->isValid()) {
187 // If a cache hit
188 lat = accessLatency;
189 // Check if the block to be accessed is available. If not,
190 // apply the accessLatency on top of block->whenReady.
191 if (blk->whenReady > curTick() &&
192 cache->ticksToCycles(blk->whenReady - curTick()) >
193 accessLatency) {
194 lat = cache->ticksToCycles(blk->whenReady - curTick()) +
195 accessLatency;
196 }
197 assert(blk->tag == blkAddr);
198 tmp_in_cache = blk->inCache;
199 for (unsigned i = 0; i < numCaches; i++) {
200 if (1<<i & blk->inCache) {
201 hits[i]++;
202 } else {
203 misses[i]++;
204 }
205 }
206 hits[numCaches]++;
207 if (blk != head){
208 moveToHead(blk);
209 }
210 } else {
211 // If a cache miss
212 lat = lookupLatency;
213 blk = nullptr;
214 for (unsigned i = 0; i <= numCaches; ++i) {
215 misses[i]++;
216 }
217 }
218 if (inCache) {
219 *inCache = tmp_in_cache;
220 }
221
222 //assert(check());
223 return blk;
224}
225
226
227CacheBlk*
228FALRU::findBlock(Addr addr, bool is_secure) const
229{
230 Addr blkAddr = blkAlign(addr);
231 FALRUBlk* blk = hashLookup(blkAddr);
232
233 if (blk && blk->isValid()) {
234 assert(blk->tag == blkAddr);
235 } else {
236 blk = nullptr;
237 }
238 return blk;
239}
240
241CacheBlk*
242FALRU::findBlockBySetAndWay(int set, int way) const
243{
244 assert(set == 0);
245 return &blks[way];
246}
247
248CacheBlk*
249FALRU::findVictim(Addr addr)
250{
251 FALRUBlk * blk = tail;
252 assert(blk->inCache == 0);
253 moveToHead(blk);
254 tagHash.erase(blk->tag);
255 tagHash[blkAlign(addr)] = blk;
256 if (blk->isValid()) {
257 replacements[0]++;
258 } else {
259 tagsInUse++;
260 blk->isTouched = true;
261 if (!warmedUp && tagsInUse.value() >= warmupBound) {
262 warmedUp = true;
263 warmupCycle = curTick();
264 }
265 }
266 //assert(check());
267 return blk;
268}
269
270void
271FALRU::insertBlock(PacketPtr pkt, CacheBlk *blk)
272{
273}
274
275void
276FALRU::moveToHead(FALRUBlk *blk)
277{
278 int updateMask = blk->inCache ^ cacheMask;
279 for (unsigned i = 0; i < numCaches; i++){
280 if ((1<<i) & updateMask) {
281 cacheBoundaries[i]->inCache &= ~(1<<i);
282 cacheBoundaries[i] = cacheBoundaries[i]->prev;
283 } else if (cacheBoundaries[i] == blk) {
284 cacheBoundaries[i] = blk->prev;
285 }
286 }
287 blk->inCache = cacheMask;
288 if (blk != head) {
289 if (blk == tail){
290 assert(blk->next == nullptr);
291 tail = blk->prev;
292 tail->next = nullptr;
293 } else {
294 blk->prev->next = blk->next;
295 blk->next->prev = blk->prev;
296 }
297 blk->next = head;
298 blk->prev = nullptr;
299 head->prev = blk;
300 head = blk;
301 }
302}
303
304bool
305FALRU::check()
306{
307 FALRUBlk* blk = head;
308 int tot_size = 0;
309 int boundary = 1<<17;
310 int j = 0;
311 int flags = cacheMask;
312 while (blk) {
313 tot_size += blkSize;
314 if (blk->inCache != flags) {
315 return false;
316 }
317 if (tot_size == boundary && blk != tail) {
318 if (cacheBoundaries[j] != blk) {
319 return false;
320 }
321 flags &=~(1 << j);
322 boundary = boundary<<1;
323 ++j;
324 }
325 blk = blk->next;
326 }
327 return true;
328}
329
330FALRU *
331FALRUParams::create()
332{
333 return new FALRU(this);
334}
335
76 blks = new FALRUBlk[numBlocks];
77 head = &(blks[0]);
78 tail = &(blks[numBlocks-1]);
79
80 head->prev = nullptr;
81 head->next = &(blks[1]);
82 head->inCache = cacheMask;
83
84 tail->prev = &(blks[numBlocks-2]);
85 tail->next = nullptr;
86 tail->inCache = 0;
87
88 unsigned index = (1 << 17) / blkSize;
89 unsigned j = 0;
90 int flags = cacheMask;
91 for (unsigned i = 1; i < numBlocks - 1; i++) {
92 blks[i].inCache = flags;
93 if (i == index - 1){
94 cacheBoundaries[j] = &(blks[i]);
95 flags &= ~ (1<<j);
96 ++j;
97 index = index << 1;
98 }
99 blks[i].prev = &(blks[i-1]);
100 blks[i].next = &(blks[i+1]);
101 blks[i].isTouched = false;
102 blks[i].set = 0;
103 blks[i].way = i;
104 }
105 assert(j == numCaches);
106 assert(index == numBlocks);
107 //assert(check());
108}
109
110FALRU::~FALRU()
111{
112 if (numCaches)
113 delete[] cacheBoundaries;
114
115 delete[] blks;
116}
117
118void
119FALRU::regStats()
120{
121 using namespace Stats;
122 BaseTags::regStats();
123 hits
124 .init(numCaches+1)
125 .name(name() + ".falru_hits")
126 .desc("The number of hits in each cache size.")
127 ;
128 misses
129 .init(numCaches+1)
130 .name(name() + ".falru_misses")
131 .desc("The number of misses in each cache size.")
132 ;
133 accesses
134 .name(name() + ".falru_accesses")
135 .desc("The number of accesses to the FA LRU cache.")
136 ;
137
138 for (unsigned i = 0; i <= numCaches; ++i) {
139 stringstream size_str;
140 if (i < 3){
141 size_str << (1<<(i+7)) <<"K";
142 } else {
143 size_str << (1<<(i-3)) <<"M";
144 }
145
146 hits.subname(i, size_str.str());
147 hits.subdesc(i, "Hits in a " + size_str.str() +" cache");
148 misses.subname(i, size_str.str());
149 misses.subdesc(i, "Misses in a " + size_str.str() +" cache");
150 }
151}
152
153FALRUBlk *
154FALRU::hashLookup(Addr addr) const
155{
156 tagIterator iter = tagHash.find(addr);
157 if (iter != tagHash.end()) {
158 return (*iter).second;
159 }
160 return nullptr;
161}
162
163void
164FALRU::invalidate(CacheBlk *blk)
165{
166 assert(blk);
167 tagsInUse--;
168}
169
170CacheBlk*
171FALRU::accessBlock(Addr addr, bool is_secure, Cycles &lat)
172{
173 return accessBlock(addr, is_secure, lat, 0);
174}
175
176CacheBlk*
177FALRU::accessBlock(Addr addr, bool is_secure, Cycles &lat, int *inCache)
178{
179 accesses++;
180 int tmp_in_cache = 0;
181 Addr blkAddr = blkAlign(addr);
182 FALRUBlk* blk = hashLookup(blkAddr);
183
184 if (blk && blk->isValid()) {
185 // If a cache hit
186 lat = accessLatency;
187 // Check if the block to be accessed is available. If not,
188 // apply the accessLatency on top of block->whenReady.
189 if (blk->whenReady > curTick() &&
190 cache->ticksToCycles(blk->whenReady - curTick()) >
191 accessLatency) {
192 lat = cache->ticksToCycles(blk->whenReady - curTick()) +
193 accessLatency;
194 }
195 assert(blk->tag == blkAddr);
196 tmp_in_cache = blk->inCache;
197 for (unsigned i = 0; i < numCaches; i++) {
198 if (1<<i & blk->inCache) {
199 hits[i]++;
200 } else {
201 misses[i]++;
202 }
203 }
204 hits[numCaches]++;
205 if (blk != head){
206 moveToHead(blk);
207 }
208 } else {
209 // If a cache miss
210 lat = lookupLatency;
211 blk = nullptr;
212 for (unsigned i = 0; i <= numCaches; ++i) {
213 misses[i]++;
214 }
215 }
216 if (inCache) {
217 *inCache = tmp_in_cache;
218 }
219
220 //assert(check());
221 return blk;
222}
223
224
225CacheBlk*
226FALRU::findBlock(Addr addr, bool is_secure) const
227{
228 Addr blkAddr = blkAlign(addr);
229 FALRUBlk* blk = hashLookup(blkAddr);
230
231 if (blk && blk->isValid()) {
232 assert(blk->tag == blkAddr);
233 } else {
234 blk = nullptr;
235 }
236 return blk;
237}
238
239CacheBlk*
240FALRU::findBlockBySetAndWay(int set, int way) const
241{
242 assert(set == 0);
243 return &blks[way];
244}
245
246CacheBlk*
247FALRU::findVictim(Addr addr)
248{
249 FALRUBlk * blk = tail;
250 assert(blk->inCache == 0);
251 moveToHead(blk);
252 tagHash.erase(blk->tag);
253 tagHash[blkAlign(addr)] = blk;
254 if (blk->isValid()) {
255 replacements[0]++;
256 } else {
257 tagsInUse++;
258 blk->isTouched = true;
259 if (!warmedUp && tagsInUse.value() >= warmupBound) {
260 warmedUp = true;
261 warmupCycle = curTick();
262 }
263 }
264 //assert(check());
265 return blk;
266}
267
268void
269FALRU::insertBlock(PacketPtr pkt, CacheBlk *blk)
270{
271}
272
273void
274FALRU::moveToHead(FALRUBlk *blk)
275{
276 int updateMask = blk->inCache ^ cacheMask;
277 for (unsigned i = 0; i < numCaches; i++){
278 if ((1<<i) & updateMask) {
279 cacheBoundaries[i]->inCache &= ~(1<<i);
280 cacheBoundaries[i] = cacheBoundaries[i]->prev;
281 } else if (cacheBoundaries[i] == blk) {
282 cacheBoundaries[i] = blk->prev;
283 }
284 }
285 blk->inCache = cacheMask;
286 if (blk != head) {
287 if (blk == tail){
288 assert(blk->next == nullptr);
289 tail = blk->prev;
290 tail->next = nullptr;
291 } else {
292 blk->prev->next = blk->next;
293 blk->next->prev = blk->prev;
294 }
295 blk->next = head;
296 blk->prev = nullptr;
297 head->prev = blk;
298 head = blk;
299 }
300}
301
302bool
303FALRU::check()
304{
305 FALRUBlk* blk = head;
306 int tot_size = 0;
307 int boundary = 1<<17;
308 int j = 0;
309 int flags = cacheMask;
310 while (blk) {
311 tot_size += blkSize;
312 if (blk->inCache != flags) {
313 return false;
314 }
315 if (tot_size == boundary && blk != tail) {
316 if (cacheBoundaries[j] != blk) {
317 return false;
318 }
319 flags &=~(1 << j);
320 boundary = boundary<<1;
321 ++j;
322 }
323 blk = blk->next;
324 }
325 return true;
326}
327
328FALRU *
329FALRUParams::create()
330{
331 return new FALRU(this);
332}
333