1/*
2 * Copyright (c) 2018 Inria
3 * Copyright (c) 2013,2016-2018 ARM Limited
4 * All rights reserved.
5 *
6 * The license below extends only to copyright in the software and shall
7 * not be construed as granting a license to any other intellectual
8 * property including but not limited to intellectual property relating
9 * to a hardware implementation of the functionality of the software
10 * licensed hereunder. You may use the software subject to the license
11 * terms below provided that you ensure that this notice is replicated
12 * unmodified and in its entirety in all distributions of the software,
13 * modified or unmodified, in source code or in binary form.
14 *
15 * Copyright (c) 2003-2005 The Regents of The University of Michigan
16 * All rights reserved.
17 *
18 * Redistribution and use in source and binary forms, with or without
19 * modification, are permitted provided that the following conditions are
20 * met: redistributions of source code must retain the above copyright
21 * notice, this list of conditions and the following disclaimer;
22 * redistributions in binary form must reproduce the above copyright
23 * notice, this list of conditions and the following disclaimer in the
24 * documentation and/or other materials provided with the distribution;
25 * neither the name of the copyright holders nor the names of its
26 * contributors may be used to endorse or promote products derived from
27 * this software without specific prior written permission.
28 *
29 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
30 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
31 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
32 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
33 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
34 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
35 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
36 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
37 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
38 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
39 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
40 *
41 * Authors: Erik Hallnor
42 * Nikos Nikoleris
43 * Daniel Carvalho
44 */
45
46/**
47 * @file
48 * Definitions a fully associative LRU tagstore.
49 */
50
51#include "mem/cache/tags/fa_lru.hh"
52
53#include <cassert>
54#include <sstream>
55
56#include "base/intmath.hh"
57#include "base/logging.hh"
58#include "mem/cache/base.hh"
| 1/*
2 * Copyright (c) 2018 Inria
3 * Copyright (c) 2013,2016-2018 ARM Limited
4 * All rights reserved.
5 *
6 * The license below extends only to copyright in the software and shall
7 * not be construed as granting a license to any other intellectual
8 * property including but not limited to intellectual property relating
9 * to a hardware implementation of the functionality of the software
10 * licensed hereunder. You may use the software subject to the license
11 * terms below provided that you ensure that this notice is replicated
12 * unmodified and in its entirety in all distributions of the software,
13 * modified or unmodified, in source code or in binary form.
14 *
15 * Copyright (c) 2003-2005 The Regents of The University of Michigan
16 * All rights reserved.
17 *
18 * Redistribution and use in source and binary forms, with or without
19 * modification, are permitted provided that the following conditions are
20 * met: redistributions of source code must retain the above copyright
21 * notice, this list of conditions and the following disclaimer;
22 * redistributions in binary form must reproduce the above copyright
23 * notice, this list of conditions and the following disclaimer in the
24 * documentation and/or other materials provided with the distribution;
25 * neither the name of the copyright holders nor the names of its
26 * contributors may be used to endorse or promote products derived from
27 * this software without specific prior written permission.
28 *
29 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
30 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
31 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
32 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
33 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
34 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
35 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
36 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
37 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
38 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
39 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
40 *
41 * Authors: Erik Hallnor
42 * Nikos Nikoleris
43 * Daniel Carvalho
44 */
45
46/**
47 * @file
48 * Definitions a fully associative LRU tagstore.
49 */
50
51#include "mem/cache/tags/fa_lru.hh"
52
53#include <cassert>
54#include <sstream>
55
56#include "base/intmath.hh"
57#include "base/logging.hh"
58#include "mem/cache/base.hh"
|
59
60std::string
61FALRUBlk::print() const
62{
63 return csprintf("%s inCachesMask: %#x", CacheBlk::print(), inCachesMask);
64}
65
66FALRU::FALRU(const Params *p)
67 : BaseTags(p),
68
69 cacheTracking(p->min_tracked_cache_size, size, blkSize)
70{
71 if (!isPowerOf2(blkSize))
72 fatal("cache block size (in bytes) `%d' must be a power of two",
73 blkSize);
74 if (!isPowerOf2(size))
75 fatal("Cache Size must be power of 2 for now");
76
77 blks = new FALRUBlk[numBlocks];
78}
79
80FALRU::~FALRU()
81{
82 delete[] blks;
83}
84
85void
86FALRU::init(BaseCache* cache)
87{
88 // Set parent cache
89 setCache(cache);
90
91 head = &(blks[0]);
92 head->prev = nullptr;
93 head->next = &(blks[1]);
94 head->setPosition(0, 0);
95 head->data = &dataBlks[0];
96
97 for (unsigned i = 1; i < numBlocks - 1; i++) {
98 blks[i].prev = &(blks[i-1]);
99 blks[i].next = &(blks[i+1]);
100 blks[i].setPosition(0, i);
101
102 // Associate a data chunk to the block
103 blks[i].data = &dataBlks[blkSize*i];
104 }
105
106 tail = &(blks[numBlocks - 1]);
107 tail->prev = &(blks[numBlocks - 2]);
108 tail->next = nullptr;
109 tail->setPosition(0, numBlocks - 1);
110 tail->data = &dataBlks[(numBlocks - 1) * blkSize];
111
112 cacheTracking.init(head, tail);
113}
114
115void
116FALRU::regStats()
117{
118 BaseTags::regStats();
119 cacheTracking.regStats(name());
120}
121
122void
123FALRU::invalidate(CacheBlk *blk)
124{
125 // Erase block entry reference in the hash table
126 auto num_erased = tagHash.erase(std::make_pair(blk->tag, blk->isSecure()));
127
128 // Sanity check; only one block reference should be erased
129 assert(num_erased == 1);
130
131 // Invalidate block entry. Must be done after the hash is erased
132 BaseTags::invalidate(blk);
133
134 // Decrease the number of tags in use
135 tagsInUse--;
136
137 // Move the block to the tail to make it the next victim
138 moveToTail((FALRUBlk*)blk);
139}
140
141CacheBlk*
142FALRU::accessBlock(Addr addr, bool is_secure, Cycles &lat)
143{
144 return accessBlock(addr, is_secure, lat, 0);
145}
146
147CacheBlk*
148FALRU::accessBlock(Addr addr, bool is_secure, Cycles &lat,
149 CachesMask *in_caches_mask)
150{
151 CachesMask mask = 0;
152 FALRUBlk* blk = static_cast<FALRUBlk*>(findBlock(addr, is_secure));
153
154 if (blk && blk->isValid()) {
155 // If a cache hit
156 lat = accessLatency;
157 // Check if the block to be accessed is available. If not,
158 // apply the accessLatency on top of block->whenReady.
159 if (blk->whenReady > curTick() &&
160 cache->ticksToCycles(blk->whenReady - curTick()) >
161 accessLatency) {
162 lat = cache->ticksToCycles(blk->whenReady - curTick()) +
163 accessLatency;
164 }
165 mask = blk->inCachesMask;
166
167 moveToHead(blk);
168 } else {
169 // If a cache miss
170 lat = lookupLatency;
171 }
172 if (in_caches_mask) {
173 *in_caches_mask = mask;
174 }
175
176 cacheTracking.recordAccess(blk);
177
178 return blk;
179}
180
181CacheBlk*
182FALRU::findBlock(Addr addr, bool is_secure) const
183{
184 FALRUBlk* blk = nullptr;
185
186 Addr tag = extractTag(addr);
187 auto iter = tagHash.find(std::make_pair(tag, is_secure));
188 if (iter != tagHash.end()) {
189 blk = (*iter).second;
190 }
191
192 if (blk && blk->isValid()) {
193 assert(blk->tag == tag);
194 assert(blk->isSecure() == is_secure);
195 }
196
197 return blk;
198}
199
200ReplaceableEntry*
201FALRU::findBlockBySetAndWay(int set, int way) const
202{
203 assert(set == 0);
204 return &blks[way];
205}
206
207CacheBlk*
208FALRU::findVictim(Addr addr, const bool is_secure,
209 std::vector<CacheBlk*>& evict_blks) const
210{
211 // The victim is always stored on the tail for the FALRU
212 FALRUBlk* victim = tail;
213
214 // There is only one eviction for this replacement
215 evict_blks.push_back(victim);
216
217 return victim;
218}
219
220void
221FALRU::insertBlock(const Addr addr, const bool is_secure,
222 const int src_master_ID, const uint32_t task_ID,
223 CacheBlk *blk)
224{
225 FALRUBlk* falruBlk = static_cast<FALRUBlk*>(blk);
226
227 // Make sure block is not present in the cache
228 assert(falruBlk->inCachesMask == 0);
229
230 // Do common block insertion functionality
231 BaseTags::insertBlock(addr, is_secure, src_master_ID, task_ID, blk);
232
233 // Increment tag counter
234 tagsInUse++;
235
236 // New block is the MRU
237 moveToHead(falruBlk);
238
239 // Insert new block in the hash table
240 tagHash[std::make_pair(blk->tag, blk->isSecure())] = falruBlk;
241}
242
243void
244FALRU::moveToHead(FALRUBlk *blk)
245{
246 // If block is not already head, do the moving
247 if (blk != head) {
248 cacheTracking.moveBlockToHead(blk);
249 // If block is tail, set previous block as new tail
250 if (blk == tail){
251 assert(blk->next == nullptr);
252 tail = blk->prev;
253 tail->next = nullptr;
254 // Inform block's surrounding blocks that it has been moved
255 } else {
256 blk->prev->next = blk->next;
257 blk->next->prev = blk->prev;
258 }
259
260 // Swap pointers
261 blk->next = head;
262 blk->prev = nullptr;
263 head->prev = blk;
264 head = blk;
265
266 cacheTracking.check(head, tail);
267 }
268}
269
270void
271FALRU::moveToTail(FALRUBlk *blk)
272{
273 // If block is not already tail, do the moving
274 if (blk != tail) {
275 cacheTracking.moveBlockToTail(blk);
276 // If block is head, set next block as new head
277 if (blk == head){
278 assert(blk->prev == nullptr);
279 head = blk->next;
280 head->prev = nullptr;
281 // Inform block's surrounding blocks that it has been moved
282 } else {
283 blk->prev->next = blk->next;
284 blk->next->prev = blk->prev;
285 }
286
287 // Swap pointers
288 blk->prev = tail;
289 blk->next = nullptr;
290 tail->next = blk;
291 tail = blk;
292
293 cacheTracking.check(head, tail);
294 }
295}
296
297FALRU *
298FALRUParams::create()
299{
300 return new FALRU(this);
301}
302
303void
304FALRU::CacheTracking::check(const FALRUBlk *head, const FALRUBlk *tail) const
305{
306#ifdef FALRU_DEBUG
307 const FALRUBlk* blk = head;
308 unsigned curr_size = 0;
309 unsigned tracked_cache_size = minTrackedSize;
310 CachesMask in_caches_mask = inAllCachesMask;
311 int j = 0;
312
313 while (blk) {
314 panic_if(blk->inCachesMask != in_caches_mask, "Expected cache mask "
315 "%x found %x", blk->inCachesMask, in_caches_mask);
316
317 curr_size += blkSize;
318 if (curr_size == tracked_cache_size && blk != tail) {
319 panic_if(boundaries[j] != blk, "Unexpected boundary for the %d-th "
320 "cache", j);
321 tracked_cache_size <<= 1;
322 // from this point, blocks fit only in the larger caches
323 in_caches_mask &= ~(1U << j);
324 ++j;
325 }
326 blk = blk->next;
327 }
328#endif // FALRU_DEBUG
329}
330
331void
332FALRU::CacheTracking::init(FALRUBlk *head, FALRUBlk *tail)
333{
334 // early exit if we are not tracking any extra caches
335 FALRUBlk* blk = numTrackedCaches ? head : nullptr;
336 unsigned curr_size = 0;
337 unsigned tracked_cache_size = minTrackedSize;
338 CachesMask in_caches_mask = inAllCachesMask;
339 int j = 0;
340
341 while (blk) {
342 blk->inCachesMask = in_caches_mask;
343
344 curr_size += blkSize;
345 if (curr_size == tracked_cache_size && blk != tail) {
346 boundaries[j] = blk;
347
348 tracked_cache_size <<= 1;
349 // from this point, blocks fit only in the larger caches
350 in_caches_mask &= ~(1U << j);
351 ++j;
352 }
353 blk = blk->next;
354 }
355}
356
357
358void
359FALRU::CacheTracking::moveBlockToHead(FALRUBlk *blk)
360{
361 // Get the mask of all caches, in which the block didn't fit
362 // before moving it to the head
363 CachesMask update_caches_mask = inAllCachesMask ^ blk->inCachesMask;
364
365 for (int i = 0; i < numTrackedCaches; i++) {
366 CachesMask current_cache_mask = 1U << i;
367 if (current_cache_mask & update_caches_mask) {
368 // if the ith cache didn't fit the block (before it is moved to
369 // the head), move the ith boundary 1 block closer to the
370 // MRU
371 boundaries[i]->inCachesMask &= ~current_cache_mask;
372 boundaries[i] = boundaries[i]->prev;
373 } else if (boundaries[i] == blk) {
374 // Make sure the boundary doesn't point to the block
375 // we are about to move
376 boundaries[i] = blk->prev;
377 }
378 }
379
380 // Make block reside in all caches
381 blk->inCachesMask = inAllCachesMask;
382}
383
384void
385FALRU::CacheTracking::moveBlockToTail(FALRUBlk *blk)
386{
387 CachesMask update_caches_mask = blk->inCachesMask;
388
389 for (int i = 0; i < numTrackedCaches; i++) {
390 CachesMask current_cache_mask = 1U << i;
391 if (current_cache_mask & update_caches_mask) {
392 // if the ith cache fitted the block (before it is moved to
393 // the tail), move the ith boundary 1 block closer to the
394 // LRU
395 boundaries[i] = boundaries[i]->next;
396 if (boundaries[i] == blk) {
397 // Make sure the boundary doesn't point to the block
398 // we are about to move
399 boundaries[i] = blk->next;
400 }
401 boundaries[i]->inCachesMask |= current_cache_mask;
402 }
403 }
404
405 // The block now fits only in the actual cache
406 blk->inCachesMask = 0;
407}
408
409void
410FALRU::CacheTracking::recordAccess(FALRUBlk *blk)
411{
412 for (int i = 0; i < numTrackedCaches; i++) {
413 if (blk && ((1U << i) & blk->inCachesMask)) {
414 hits[i]++;
415 } else {
416 misses[i]++;
417 }
418 }
419
420 // Record stats for the actual cache too
421 if (blk && blk->isValid()) {
422 hits[numTrackedCaches]++;
423 } else {
424 misses[numTrackedCaches]++;
425 }
426
427 accesses++;
428}
429
430void
431printSize(std::ostream &stream, size_t size)
432{
433 static const char *SIZES[] = { "B", "kB", "MB", "GB", "TB", "ZB" };
434 int div = 0;
435 while (size >= 1024 && div < (sizeof SIZES / sizeof *SIZES)) {
436 div++;
437 size >>= 10;
438 }
439 stream << size << SIZES[div];
440}
441
442void
443FALRU::CacheTracking::regStats(std::string name)
444{
445 hits
446 .init(numTrackedCaches + 1)
447 .name(name + ".falru_hits")
448 .desc("The number of hits in each cache size.")
449 ;
450 misses
451 .init(numTrackedCaches + 1)
452 .name(name + ".falru_misses")
453 .desc("The number of misses in each cache size.")
454 ;
455 accesses
456 .name(name + ".falru_accesses")
457 .desc("The number of accesses to the FA LRU cache.")
458 ;
459
460 for (unsigned i = 0; i < numTrackedCaches + 1; ++i) {
461 std::stringstream size_str;
462 printSize(size_str, minTrackedSize << i);
463 hits.subname(i, size_str.str());
464 hits.subdesc(i, "Hits in a " + size_str.str() + " cache");
465 misses.subname(i, size_str.str());
466 misses.subdesc(i, "Misses in a " + size_str.str() + " cache");
467 }
468}
| 60
61std::string
62FALRUBlk::print() const
63{
64 return csprintf("%s inCachesMask: %#x", CacheBlk::print(), inCachesMask);
65}
66
67FALRU::FALRU(const Params *p)
68 : BaseTags(p),
69
70 cacheTracking(p->min_tracked_cache_size, size, blkSize)
71{
72 if (!isPowerOf2(blkSize))
73 fatal("cache block size (in bytes) `%d' must be a power of two",
74 blkSize);
75 if (!isPowerOf2(size))
76 fatal("Cache Size must be power of 2 for now");
77
78 blks = new FALRUBlk[numBlocks];
79}
80
81FALRU::~FALRU()
82{
83 delete[] blks;
84}
85
86void
87FALRU::init(BaseCache* cache)
88{
89 // Set parent cache
90 setCache(cache);
91
92 head = &(blks[0]);
93 head->prev = nullptr;
94 head->next = &(blks[1]);
95 head->setPosition(0, 0);
96 head->data = &dataBlks[0];
97
98 for (unsigned i = 1; i < numBlocks - 1; i++) {
99 blks[i].prev = &(blks[i-1]);
100 blks[i].next = &(blks[i+1]);
101 blks[i].setPosition(0, i);
102
103 // Associate a data chunk to the block
104 blks[i].data = &dataBlks[blkSize*i];
105 }
106
107 tail = &(blks[numBlocks - 1]);
108 tail->prev = &(blks[numBlocks - 2]);
109 tail->next = nullptr;
110 tail->setPosition(0, numBlocks - 1);
111 tail->data = &dataBlks[(numBlocks - 1) * blkSize];
112
113 cacheTracking.init(head, tail);
114}
115
116void
117FALRU::regStats()
118{
119 BaseTags::regStats();
120 cacheTracking.regStats(name());
121}
122
123void
124FALRU::invalidate(CacheBlk *blk)
125{
126 // Erase block entry reference in the hash table
127 auto num_erased = tagHash.erase(std::make_pair(blk->tag, blk->isSecure()));
128
129 // Sanity check; only one block reference should be erased
130 assert(num_erased == 1);
131
132 // Invalidate block entry. Must be done after the hash is erased
133 BaseTags::invalidate(blk);
134
135 // Decrease the number of tags in use
136 tagsInUse--;
137
138 // Move the block to the tail to make it the next victim
139 moveToTail((FALRUBlk*)blk);
140}
141
142CacheBlk*
143FALRU::accessBlock(Addr addr, bool is_secure, Cycles &lat)
144{
145 return accessBlock(addr, is_secure, lat, 0);
146}
147
148CacheBlk*
149FALRU::accessBlock(Addr addr, bool is_secure, Cycles &lat,
150 CachesMask *in_caches_mask)
151{
152 CachesMask mask = 0;
153 FALRUBlk* blk = static_cast<FALRUBlk*>(findBlock(addr, is_secure));
154
155 if (blk && blk->isValid()) {
156 // If a cache hit
157 lat = accessLatency;
158 // Check if the block to be accessed is available. If not,
159 // apply the accessLatency on top of block->whenReady.
160 if (blk->whenReady > curTick() &&
161 cache->ticksToCycles(blk->whenReady - curTick()) >
162 accessLatency) {
163 lat = cache->ticksToCycles(blk->whenReady - curTick()) +
164 accessLatency;
165 }
166 mask = blk->inCachesMask;
167
168 moveToHead(blk);
169 } else {
170 // If a cache miss
171 lat = lookupLatency;
172 }
173 if (in_caches_mask) {
174 *in_caches_mask = mask;
175 }
176
177 cacheTracking.recordAccess(blk);
178
179 return blk;
180}
181
182CacheBlk*
183FALRU::findBlock(Addr addr, bool is_secure) const
184{
185 FALRUBlk* blk = nullptr;
186
187 Addr tag = extractTag(addr);
188 auto iter = tagHash.find(std::make_pair(tag, is_secure));
189 if (iter != tagHash.end()) {
190 blk = (*iter).second;
191 }
192
193 if (blk && blk->isValid()) {
194 assert(blk->tag == tag);
195 assert(blk->isSecure() == is_secure);
196 }
197
198 return blk;
199}
200
201ReplaceableEntry*
202FALRU::findBlockBySetAndWay(int set, int way) const
203{
204 assert(set == 0);
205 return &blks[way];
206}
207
208CacheBlk*
209FALRU::findVictim(Addr addr, const bool is_secure,
210 std::vector<CacheBlk*>& evict_blks) const
211{
212 // The victim is always stored on the tail for the FALRU
213 FALRUBlk* victim = tail;
214
215 // There is only one eviction for this replacement
216 evict_blks.push_back(victim);
217
218 return victim;
219}
220
221void
222FALRU::insertBlock(const Addr addr, const bool is_secure,
223 const int src_master_ID, const uint32_t task_ID,
224 CacheBlk *blk)
225{
226 FALRUBlk* falruBlk = static_cast<FALRUBlk*>(blk);
227
228 // Make sure block is not present in the cache
229 assert(falruBlk->inCachesMask == 0);
230
231 // Do common block insertion functionality
232 BaseTags::insertBlock(addr, is_secure, src_master_ID, task_ID, blk);
233
234 // Increment tag counter
235 tagsInUse++;
236
237 // New block is the MRU
238 moveToHead(falruBlk);
239
240 // Insert new block in the hash table
241 tagHash[std::make_pair(blk->tag, blk->isSecure())] = falruBlk;
242}
243
244void
245FALRU::moveToHead(FALRUBlk *blk)
246{
247 // If block is not already head, do the moving
248 if (blk != head) {
249 cacheTracking.moveBlockToHead(blk);
250 // If block is tail, set previous block as new tail
251 if (blk == tail){
252 assert(blk->next == nullptr);
253 tail = blk->prev;
254 tail->next = nullptr;
255 // Inform block's surrounding blocks that it has been moved
256 } else {
257 blk->prev->next = blk->next;
258 blk->next->prev = blk->prev;
259 }
260
261 // Swap pointers
262 blk->next = head;
263 blk->prev = nullptr;
264 head->prev = blk;
265 head = blk;
266
267 cacheTracking.check(head, tail);
268 }
269}
270
271void
272FALRU::moveToTail(FALRUBlk *blk)
273{
274 // If block is not already tail, do the moving
275 if (blk != tail) {
276 cacheTracking.moveBlockToTail(blk);
277 // If block is head, set next block as new head
278 if (blk == head){
279 assert(blk->prev == nullptr);
280 head = blk->next;
281 head->prev = nullptr;
282 // Inform block's surrounding blocks that it has been moved
283 } else {
284 blk->prev->next = blk->next;
285 blk->next->prev = blk->prev;
286 }
287
288 // Swap pointers
289 blk->prev = tail;
290 blk->next = nullptr;
291 tail->next = blk;
292 tail = blk;
293
294 cacheTracking.check(head, tail);
295 }
296}
297
298FALRU *
299FALRUParams::create()
300{
301 return new FALRU(this);
302}
303
304void
305FALRU::CacheTracking::check(const FALRUBlk *head, const FALRUBlk *tail) const
306{
307#ifdef FALRU_DEBUG
308 const FALRUBlk* blk = head;
309 unsigned curr_size = 0;
310 unsigned tracked_cache_size = minTrackedSize;
311 CachesMask in_caches_mask = inAllCachesMask;
312 int j = 0;
313
314 while (blk) {
315 panic_if(blk->inCachesMask != in_caches_mask, "Expected cache mask "
316 "%x found %x", blk->inCachesMask, in_caches_mask);
317
318 curr_size += blkSize;
319 if (curr_size == tracked_cache_size && blk != tail) {
320 panic_if(boundaries[j] != blk, "Unexpected boundary for the %d-th "
321 "cache", j);
322 tracked_cache_size <<= 1;
323 // from this point, blocks fit only in the larger caches
324 in_caches_mask &= ~(1U << j);
325 ++j;
326 }
327 blk = blk->next;
328 }
329#endif // FALRU_DEBUG
330}
331
332void
333FALRU::CacheTracking::init(FALRUBlk *head, FALRUBlk *tail)
334{
335 // early exit if we are not tracking any extra caches
336 FALRUBlk* blk = numTrackedCaches ? head : nullptr;
337 unsigned curr_size = 0;
338 unsigned tracked_cache_size = minTrackedSize;
339 CachesMask in_caches_mask = inAllCachesMask;
340 int j = 0;
341
342 while (blk) {
343 blk->inCachesMask = in_caches_mask;
344
345 curr_size += blkSize;
346 if (curr_size == tracked_cache_size && blk != tail) {
347 boundaries[j] = blk;
348
349 tracked_cache_size <<= 1;
350 // from this point, blocks fit only in the larger caches
351 in_caches_mask &= ~(1U << j);
352 ++j;
353 }
354 blk = blk->next;
355 }
356}
357
358
359void
360FALRU::CacheTracking::moveBlockToHead(FALRUBlk *blk)
361{
362 // Get the mask of all caches, in which the block didn't fit
363 // before moving it to the head
364 CachesMask update_caches_mask = inAllCachesMask ^ blk->inCachesMask;
365
366 for (int i = 0; i < numTrackedCaches; i++) {
367 CachesMask current_cache_mask = 1U << i;
368 if (current_cache_mask & update_caches_mask) {
369 // if the ith cache didn't fit the block (before it is moved to
370 // the head), move the ith boundary 1 block closer to the
371 // MRU
372 boundaries[i]->inCachesMask &= ~current_cache_mask;
373 boundaries[i] = boundaries[i]->prev;
374 } else if (boundaries[i] == blk) {
375 // Make sure the boundary doesn't point to the block
376 // we are about to move
377 boundaries[i] = blk->prev;
378 }
379 }
380
381 // Make block reside in all caches
382 blk->inCachesMask = inAllCachesMask;
383}
384
385void
386FALRU::CacheTracking::moveBlockToTail(FALRUBlk *blk)
387{
388 CachesMask update_caches_mask = blk->inCachesMask;
389
390 for (int i = 0; i < numTrackedCaches; i++) {
391 CachesMask current_cache_mask = 1U << i;
392 if (current_cache_mask & update_caches_mask) {
393 // if the ith cache fitted the block (before it is moved to
394 // the tail), move the ith boundary 1 block closer to the
395 // LRU
396 boundaries[i] = boundaries[i]->next;
397 if (boundaries[i] == blk) {
398 // Make sure the boundary doesn't point to the block
399 // we are about to move
400 boundaries[i] = blk->next;
401 }
402 boundaries[i]->inCachesMask |= current_cache_mask;
403 }
404 }
405
406 // The block now fits only in the actual cache
407 blk->inCachesMask = 0;
408}
409
410void
411FALRU::CacheTracking::recordAccess(FALRUBlk *blk)
412{
413 for (int i = 0; i < numTrackedCaches; i++) {
414 if (blk && ((1U << i) & blk->inCachesMask)) {
415 hits[i]++;
416 } else {
417 misses[i]++;
418 }
419 }
420
421 // Record stats for the actual cache too
422 if (blk && blk->isValid()) {
423 hits[numTrackedCaches]++;
424 } else {
425 misses[numTrackedCaches]++;
426 }
427
428 accesses++;
429}
430
431void
432printSize(std::ostream &stream, size_t size)
433{
434 static const char *SIZES[] = { "B", "kB", "MB", "GB", "TB", "ZB" };
435 int div = 0;
436 while (size >= 1024 && div < (sizeof SIZES / sizeof *SIZES)) {
437 div++;
438 size >>= 10;
439 }
440 stream << size << SIZES[div];
441}
442
443void
444FALRU::CacheTracking::regStats(std::string name)
445{
446 hits
447 .init(numTrackedCaches + 1)
448 .name(name + ".falru_hits")
449 .desc("The number of hits in each cache size.")
450 ;
451 misses
452 .init(numTrackedCaches + 1)
453 .name(name + ".falru_misses")
454 .desc("The number of misses in each cache size.")
455 ;
456 accesses
457 .name(name + ".falru_accesses")
458 .desc("The number of accesses to the FA LRU cache.")
459 ;
460
461 for (unsigned i = 0; i < numTrackedCaches + 1; ++i) {
462 std::stringstream size_str;
463 printSize(size_str, minTrackedSize << i);
464 hits.subname(i, size_str.str());
465 hits.subdesc(i, "Hits in a " + size_str.str() + " cache");
466 misses.subname(i, size_str.str());
467 misses.subdesc(i, "Misses in a " + size_str.str() + " cache");
468 }
469}
|