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
| 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
|
60FALRU::FALRU(const Params *p)
61 : BaseTags(p),
62
63 cacheTracking(p->min_tracked_cache_size, size, blkSize)
64{
65 if (!isPowerOf2(blkSize))
66 fatal("cache block size (in bytes) `%d' must be a power of two",
67 blkSize);
68 if (!isPowerOf2(size))
69 fatal("Cache Size must be power of 2 for now");
70
71 blks = new FALRUBlk[numBlocks];
72}
73
74FALRU::~FALRU()
75{
76 delete[] blks;
77}
78
79void
80FALRU::init(BaseCache* cache)
81{
82 // Set parent cache
83 setCache(cache);
84
85 head = &(blks[0]);
86 head->prev = nullptr;
87 head->next = &(blks[1]);
88 head->setPosition(0, 0);
89 head->data = &dataBlks[0];
90
91 for (unsigned i = 1; i < numBlocks - 1; i++) {
92 blks[i].prev = &(blks[i-1]);
93 blks[i].next = &(blks[i+1]);
94 blks[i].setPosition(0, i);
95
96 // Associate a data chunk to the block
97 blks[i].data = &dataBlks[blkSize*i];
98 }
99
100 tail = &(blks[numBlocks - 1]);
101 tail->prev = &(blks[numBlocks - 2]);
102 tail->next = nullptr;
103 tail->setPosition(0, numBlocks - 1);
104 tail->data = &dataBlks[(numBlocks - 1) * blkSize];
105
106 cacheTracking.init(head, tail);
107}
108
109void
110FALRU::regStats()
111{
112 BaseTags::regStats();
113 cacheTracking.regStats(name());
114}
115
116void
117FALRU::invalidate(CacheBlk *blk)
118{
119 // Erase block entry reference in the hash table
120 auto num_erased = tagHash.erase(std::make_pair(blk->tag, blk->isSecure()));
121
122 // Sanity check; only one block reference should be erased
123 assert(num_erased == 1);
124
125 // Invalidate block entry. Must be done after the hash is erased
126 BaseTags::invalidate(blk);
127
128 // Decrease the number of tags in use
129 tagsInUse--;
130
131 // Move the block to the tail to make it the next victim
132 moveToTail((FALRUBlk*)blk);
133}
134
135CacheBlk*
136FALRU::accessBlock(Addr addr, bool is_secure, Cycles &lat)
137{
138 return accessBlock(addr, is_secure, lat, 0);
139}
140
141CacheBlk*
142FALRU::accessBlock(Addr addr, bool is_secure, Cycles &lat,
143 CachesMask *in_caches_mask)
144{
145 CachesMask mask = 0;
146 FALRUBlk* blk = static_cast<FALRUBlk*>(findBlock(addr, is_secure));
147
148 if (blk && blk->isValid()) {
149 // If a cache hit
150 lat = accessLatency;
151 // Check if the block to be accessed is available. If not,
152 // apply the accessLatency on top of block->whenReady.
153 if (blk->whenReady > curTick() &&
154 cache->ticksToCycles(blk->whenReady - curTick()) >
155 accessLatency) {
156 lat = cache->ticksToCycles(blk->whenReady - curTick()) +
157 accessLatency;
158 }
159 mask = blk->inCachesMask;
160
161 moveToHead(blk);
162 } else {
163 // If a cache miss
164 lat = lookupLatency;
165 }
166 if (in_caches_mask) {
167 *in_caches_mask = mask;
168 }
169
170 cacheTracking.recordAccess(blk);
171
172 return blk;
173}
174
175CacheBlk*
176FALRU::findBlock(Addr addr, bool is_secure) const
177{
178 FALRUBlk* blk = nullptr;
179
180 Addr tag = extractTag(addr);
181 auto iter = tagHash.find(std::make_pair(tag, is_secure));
182 if (iter != tagHash.end()) {
183 blk = (*iter).second;
184 }
185
186 if (blk && blk->isValid()) {
187 assert(blk->tag == tag);
188 assert(blk->isSecure() == is_secure);
189 }
190
191 return blk;
192}
193
194ReplaceableEntry*
195FALRU::findBlockBySetAndWay(int set, int way) const
196{
197 assert(set == 0);
198 return &blks[way];
199}
200
201CacheBlk*
202FALRU::findVictim(Addr addr, const bool is_secure,
203 std::vector<CacheBlk*>& evict_blks) const
204{
205 // The victim is always stored on the tail for the FALRU
206 FALRUBlk* victim = tail;
207
208 // There is only one eviction for this replacement
209 evict_blks.push_back(victim);
210
211 return victim;
212}
213
214void
215FALRU::insertBlock(const Addr addr, const bool is_secure,
216 const int src_master_ID, const uint32_t task_ID,
217 CacheBlk *blk)
218{
219 FALRUBlk* falruBlk = static_cast<FALRUBlk*>(blk);
220
221 // Make sure block is not present in the cache
222 assert(falruBlk->inCachesMask == 0);
223
224 // Do common block insertion functionality
225 BaseTags::insertBlock(addr, is_secure, src_master_ID, task_ID, blk);
226
227 // Increment tag counter
228 tagsInUse++;
229
230 // New block is the MRU
231 moveToHead(falruBlk);
232
233 // Insert new block in the hash table
234 tagHash[std::make_pair(blk->tag, blk->isSecure())] = falruBlk;
235}
236
237void
238FALRU::moveToHead(FALRUBlk *blk)
239{
240 // If block is not already head, do the moving
241 if (blk != head) {
242 cacheTracking.moveBlockToHead(blk);
243 // If block is tail, set previous block as new tail
244 if (blk == tail){
245 assert(blk->next == nullptr);
246 tail = blk->prev;
247 tail->next = nullptr;
248 // Inform block's surrounding blocks that it has been moved
249 } else {
250 blk->prev->next = blk->next;
251 blk->next->prev = blk->prev;
252 }
253
254 // Swap pointers
255 blk->next = head;
256 blk->prev = nullptr;
257 head->prev = blk;
258 head = blk;
259
260 cacheTracking.check(head, tail);
261 }
262}
263
264void
265FALRU::moveToTail(FALRUBlk *blk)
266{
267 // If block is not already tail, do the moving
268 if (blk != tail) {
269 cacheTracking.moveBlockToTail(blk);
270 // If block is head, set next block as new head
271 if (blk == head){
272 assert(blk->prev == nullptr);
273 head = blk->next;
274 head->prev = nullptr;
275 // Inform block's surrounding blocks that it has been moved
276 } else {
277 blk->prev->next = blk->next;
278 blk->next->prev = blk->prev;
279 }
280
281 // Swap pointers
282 blk->prev = tail;
283 blk->next = nullptr;
284 tail->next = blk;
285 tail = blk;
286
287 cacheTracking.check(head, tail);
288 }
289}
290
291FALRU *
292FALRUParams::create()
293{
294 return new FALRU(this);
295}
296
297void
298FALRU::CacheTracking::check(const FALRUBlk *head, const FALRUBlk *tail) const
299{
300#ifdef FALRU_DEBUG
301 const FALRUBlk* blk = head;
302 unsigned curr_size = 0;
303 unsigned tracked_cache_size = minTrackedSize;
304 CachesMask in_caches_mask = inAllCachesMask;
305 int j = 0;
306
307 while (blk) {
308 panic_if(blk->inCachesMask != in_caches_mask, "Expected cache mask "
309 "%x found %x", blk->inCachesMask, in_caches_mask);
310
311 curr_size += blkSize;
312 if (curr_size == tracked_cache_size && blk != tail) {
313 panic_if(boundaries[j] != blk, "Unexpected boundary for the %d-th "
314 "cache", j);
315 tracked_cache_size <<= 1;
316 // from this point, blocks fit only in the larger caches
317 in_caches_mask &= ~(1U << j);
318 ++j;
319 }
320 blk = blk->next;
321 }
322#endif // FALRU_DEBUG
323}
324
325void
326FALRU::CacheTracking::init(FALRUBlk *head, FALRUBlk *tail)
327{
328 // early exit if we are not tracking any extra caches
329 FALRUBlk* blk = numTrackedCaches ? head : nullptr;
330 unsigned curr_size = 0;
331 unsigned tracked_cache_size = minTrackedSize;
332 CachesMask in_caches_mask = inAllCachesMask;
333 int j = 0;
334
335 while (blk) {
336 blk->inCachesMask = in_caches_mask;
337
338 curr_size += blkSize;
339 if (curr_size == tracked_cache_size && blk != tail) {
340 boundaries[j] = blk;
341
342 tracked_cache_size <<= 1;
343 // from this point, blocks fit only in the larger caches
344 in_caches_mask &= ~(1U << j);
345 ++j;
346 }
347 blk = blk->next;
348 }
349}
350
351
352void
353FALRU::CacheTracking::moveBlockToHead(FALRUBlk *blk)
354{
355 // Get the mask of all caches, in which the block didn't fit
356 // before moving it to the head
357 CachesMask update_caches_mask = inAllCachesMask ^ blk->inCachesMask;
358
359 for (int i = 0; i < numTrackedCaches; i++) {
360 CachesMask current_cache_mask = 1U << i;
361 if (current_cache_mask & update_caches_mask) {
362 // if the ith cache didn't fit the block (before it is moved to
363 // the head), move the ith boundary 1 block closer to the
364 // MRU
365 boundaries[i]->inCachesMask &= ~current_cache_mask;
366 boundaries[i] = boundaries[i]->prev;
367 } else if (boundaries[i] == blk) {
368 // Make sure the boundary doesn't point to the block
369 // we are about to move
370 boundaries[i] = blk->prev;
371 }
372 }
373
374 // Make block reside in all caches
375 blk->inCachesMask = inAllCachesMask;
376}
377
378void
379FALRU::CacheTracking::moveBlockToTail(FALRUBlk *blk)
380{
381 CachesMask update_caches_mask = blk->inCachesMask;
382
383 for (int i = 0; i < numTrackedCaches; i++) {
384 CachesMask current_cache_mask = 1U << i;
385 if (current_cache_mask & update_caches_mask) {
386 // if the ith cache fitted the block (before it is moved to
387 // the tail), move the ith boundary 1 block closer to the
388 // LRU
389 boundaries[i] = boundaries[i]->next;
390 if (boundaries[i] == blk) {
391 // Make sure the boundary doesn't point to the block
392 // we are about to move
393 boundaries[i] = blk->next;
394 }
395 boundaries[i]->inCachesMask |= current_cache_mask;
396 }
397 }
398
399 // The block now fits only in the actual cache
400 blk->inCachesMask = 0;
401}
402
403void
404FALRU::CacheTracking::recordAccess(FALRUBlk *blk)
405{
406 for (int i = 0; i < numTrackedCaches; i++) {
407 if (blk && ((1U << i) & blk->inCachesMask)) {
408 hits[i]++;
409 } else {
410 misses[i]++;
411 }
412 }
413
414 // Record stats for the actual cache too
415 if (blk && blk->isValid()) {
416 hits[numTrackedCaches]++;
417 } else {
418 misses[numTrackedCaches]++;
419 }
420
421 accesses++;
422}
423
424void
425printSize(std::ostream &stream, size_t size)
426{
427 static const char *SIZES[] = { "B", "kB", "MB", "GB", "TB", "ZB" };
428 int div = 0;
429 while (size >= 1024 && div < (sizeof SIZES / sizeof *SIZES)) {
430 div++;
431 size >>= 10;
432 }
433 stream << size << SIZES[div];
434}
435
436void
437FALRU::CacheTracking::regStats(std::string name)
438{
439 hits
440 .init(numTrackedCaches + 1)
441 .name(name + ".falru_hits")
442 .desc("The number of hits in each cache size.")
443 ;
444 misses
445 .init(numTrackedCaches + 1)
446 .name(name + ".falru_misses")
447 .desc("The number of misses in each cache size.")
448 ;
449 accesses
450 .name(name + ".falru_accesses")
451 .desc("The number of accesses to the FA LRU cache.")
452 ;
453
454 for (unsigned i = 0; i < numTrackedCaches + 1; ++i) {
455 std::stringstream size_str;
456 printSize(size_str, minTrackedSize << i);
457 hits.subname(i, size_str.str());
458 hits.subdesc(i, "Hits in a " + size_str.str() + " cache");
459 misses.subname(i, size_str.str());
460 misses.subdesc(i, "Misses in a " + size_str.str() + " cache");
461 }
462}
| 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}
|