1/*
2 * Copyright (c) 2013,2016-2017 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
56FALRU::FALRU(const Params *p)
57 : BaseTags(p), cacheBoundaries(nullptr)
58{
59 if (!isPowerOf2(blkSize))
60 fatal("cache block size (in bytes) `%d' must be a power of two",
61 blkSize);
62 if (!isPowerOf2(size))
63 fatal("Cache Size must be power of 2 for now");
64
65 // Track all cache sizes from 128K up by powers of 2
66 numCaches = floorLog2(size) - 17;
| 1/*
2 * Copyright (c) 2013,2016-2017 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
56FALRU::FALRU(const Params *p)
57 : BaseTags(p), cacheBoundaries(nullptr)
58{
59 if (!isPowerOf2(blkSize))
60 fatal("cache block size (in bytes) `%d' must be a power of two",
61 blkSize);
62 if (!isPowerOf2(size))
63 fatal("Cache Size must be power of 2 for now");
64
65 // Track all cache sizes from 128K up by powers of 2
66 numCaches = floorLog2(size) - 17;
|
67 if (numCaches >0){
| 67 if (numCaches > 0){
|
68 cacheBoundaries = new FALRUBlk *[numCaches];
69 cacheMask = (ULL(1) << numCaches) - 1;
70 } else {
71 cacheMask = 0;
72 }
73
74 blks = new FALRUBlk[numBlocks];
75 head = &(blks[0]);
76 tail = &(blks[numBlocks-1]);
77
78 head->prev = nullptr;
79 head->next = &(blks[1]);
80 head->inCache = cacheMask;
81 head->data = &dataBlks[0];
82
83 tail->prev = &(blks[numBlocks-2]);
84 tail->next = nullptr;
85 tail->inCache = 0;
86 tail->data = &dataBlks[(numBlocks-1)*blkSize];
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].set = 0;
102 blks[i].way = i;
103
104 // Associate a data chunk to the block
105 blks[i].data = &dataBlks[blkSize*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 BaseTags::regStats();
124 hits
125 .init(numCaches+1)
126 .name(name() + ".falru_hits")
127 .desc("The number of hits in each cache size.")
128 ;
129 misses
130 .init(numCaches+1)
131 .name(name() + ".falru_misses")
132 .desc("The number of misses in each cache size.")
133 ;
134 accesses
135 .name(name() + ".falru_accesses")
136 .desc("The number of accesses to the FA LRU cache.")
137 ;
138
139 for (unsigned i = 0; i <= numCaches; ++i) {
140 std::stringstream size_str;
141 if (i < 3){
142 size_str << (1<<(i+7)) <<"K";
143 } else {
144 size_str << (1<<(i-3)) <<"M";
145 }
146
147 hits.subname(i, size_str.str());
148 hits.subdesc(i, "Hits in a " + size_str.str() +" cache");
149 misses.subname(i, size_str.str());
150 misses.subdesc(i, "Misses in a " + size_str.str() +" cache");
151 }
152}
153
154FALRUBlk *
155FALRU::hashLookup(Addr addr) const
156{
157 tagIterator iter = tagHash.find(addr);
158 if (iter != tagHash.end()) {
159 return (*iter).second;
160 }
161 return nullptr;
162}
163
164void
165FALRU::invalidate(CacheBlk *blk)
166{
| 68 cacheBoundaries = new FALRUBlk *[numCaches];
69 cacheMask = (ULL(1) << numCaches) - 1;
70 } else {
71 cacheMask = 0;
72 }
73
74 blks = new FALRUBlk[numBlocks];
75 head = &(blks[0]);
76 tail = &(blks[numBlocks-1]);
77
78 head->prev = nullptr;
79 head->next = &(blks[1]);
80 head->inCache = cacheMask;
81 head->data = &dataBlks[0];
82
83 tail->prev = &(blks[numBlocks-2]);
84 tail->next = nullptr;
85 tail->inCache = 0;
86 tail->data = &dataBlks[(numBlocks-1)*blkSize];
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].set = 0;
102 blks[i].way = i;
103
104 // Associate a data chunk to the block
105 blks[i].data = &dataBlks[blkSize*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 BaseTags::regStats();
124 hits
125 .init(numCaches+1)
126 .name(name() + ".falru_hits")
127 .desc("The number of hits in each cache size.")
128 ;
129 misses
130 .init(numCaches+1)
131 .name(name() + ".falru_misses")
132 .desc("The number of misses in each cache size.")
133 ;
134 accesses
135 .name(name() + ".falru_accesses")
136 .desc("The number of accesses to the FA LRU cache.")
137 ;
138
139 for (unsigned i = 0; i <= numCaches; ++i) {
140 std::stringstream size_str;
141 if (i < 3){
142 size_str << (1<<(i+7)) <<"K";
143 } else {
144 size_str << (1<<(i-3)) <<"M";
145 }
146
147 hits.subname(i, size_str.str());
148 hits.subdesc(i, "Hits in a " + size_str.str() +" cache");
149 misses.subname(i, size_str.str());
150 misses.subdesc(i, "Misses in a " + size_str.str() +" cache");
151 }
152}
153
154FALRUBlk *
155FALRU::hashLookup(Addr addr) const
156{
157 tagIterator iter = tagHash.find(addr);
158 if (iter != tagHash.end()) {
159 return (*iter).second;
160 }
161 return nullptr;
162}
163
164void
165FALRU::invalidate(CacheBlk *blk)
166{
|
167 // TODO: We need to move the block to the tail to make it the next victim
| |
168 BaseTags::invalidate(blk);
169
| 167 BaseTags::invalidate(blk);
168
|
| 169 // Move the block to the tail to make it the next victim
170 moveToTail((FALRUBlk*)blk);
171
|
170 // Erase block entry in the hash table
171 tagHash.erase(blk->tag);
172}
173
174CacheBlk*
175FALRU::accessBlock(Addr addr, bool is_secure, Cycles &lat)
176{
177 return accessBlock(addr, is_secure, lat, 0);
178}
179
180CacheBlk*
181FALRU::accessBlock(Addr addr, bool is_secure, Cycles &lat, int *inCache)
182{
183 accesses++;
184 int tmp_in_cache = 0;
185 Addr blkAddr = blkAlign(addr);
186 FALRUBlk* blk = hashLookup(blkAddr);
187
188 if (blk && blk->isValid()) {
189 // If a cache hit
190 lat = accessLatency;
191 // Check if the block to be accessed is available. If not,
192 // apply the accessLatency on top of block->whenReady.
193 if (blk->whenReady > curTick() &&
194 cache->ticksToCycles(blk->whenReady - curTick()) >
195 accessLatency) {
196 lat = cache->ticksToCycles(blk->whenReady - curTick()) +
197 accessLatency;
198 }
199 assert(blk->tag == blkAddr);
200 tmp_in_cache = blk->inCache;
201 for (unsigned i = 0; i < numCaches; i++) {
202 if (1<<i & blk->inCache) {
203 hits[i]++;
204 } else {
205 misses[i]++;
206 }
207 }
208 hits[numCaches]++;
209 if (blk != head){
210 moveToHead(blk);
211 }
212 } else {
213 // If a cache miss
214 lat = lookupLatency;
215 blk = nullptr;
216 for (unsigned i = 0; i <= numCaches; ++i) {
217 misses[i]++;
218 }
219 }
220 if (inCache) {
221 *inCache = tmp_in_cache;
222 }
223
224 //assert(check());
225 return blk;
226}
227
228
229CacheBlk*
230FALRU::findBlock(Addr addr, bool is_secure) const
231{
232 Addr blkAddr = blkAlign(addr);
233 FALRUBlk* blk = hashLookup(blkAddr);
234
235 if (blk && blk->isValid()) {
236 assert(blk->tag == blkAddr);
237 } else {
238 blk = nullptr;
239 }
240 return blk;
241}
242
243CacheBlk*
244FALRU::findBlockBySetAndWay(int set, int way) const
245{
246 assert(set == 0);
247 return &blks[way];
248}
249
250CacheBlk*
251FALRU::findVictim(Addr addr)
252{
253 return tail;
254}
255
256void
257FALRU::insertBlock(PacketPtr pkt, CacheBlk *blk)
258{
259 FALRUBlk* falruBlk = static_cast<FALRUBlk*>(blk);
260
261 // Make sure block is not present in the cache
262 assert(falruBlk->inCache == 0);
263
264 // Do common block insertion functionality
265 BaseTags::insertBlock(pkt, blk);
266
267 // New block is the MRU
268 moveToHead(falruBlk);
269
270 // Insert new block in the hash table
271 tagHash[falruBlk->tag] = falruBlk;
272
273 //assert(check());
274}
275
276void
277FALRU::moveToHead(FALRUBlk *blk)
278{
| 172 // Erase block entry in the hash table
173 tagHash.erase(blk->tag);
174}
175
176CacheBlk*
177FALRU::accessBlock(Addr addr, bool is_secure, Cycles &lat)
178{
179 return accessBlock(addr, is_secure, lat, 0);
180}
181
182CacheBlk*
183FALRU::accessBlock(Addr addr, bool is_secure, Cycles &lat, int *inCache)
184{
185 accesses++;
186 int tmp_in_cache = 0;
187 Addr blkAddr = blkAlign(addr);
188 FALRUBlk* blk = hashLookup(blkAddr);
189
190 if (blk && blk->isValid()) {
191 // If a cache hit
192 lat = accessLatency;
193 // Check if the block to be accessed is available. If not,
194 // apply the accessLatency on top of block->whenReady.
195 if (blk->whenReady > curTick() &&
196 cache->ticksToCycles(blk->whenReady - curTick()) >
197 accessLatency) {
198 lat = cache->ticksToCycles(blk->whenReady - curTick()) +
199 accessLatency;
200 }
201 assert(blk->tag == blkAddr);
202 tmp_in_cache = blk->inCache;
203 for (unsigned i = 0; i < numCaches; i++) {
204 if (1<<i & blk->inCache) {
205 hits[i]++;
206 } else {
207 misses[i]++;
208 }
209 }
210 hits[numCaches]++;
211 if (blk != head){
212 moveToHead(blk);
213 }
214 } else {
215 // If a cache miss
216 lat = lookupLatency;
217 blk = nullptr;
218 for (unsigned i = 0; i <= numCaches; ++i) {
219 misses[i]++;
220 }
221 }
222 if (inCache) {
223 *inCache = tmp_in_cache;
224 }
225
226 //assert(check());
227 return blk;
228}
229
230
231CacheBlk*
232FALRU::findBlock(Addr addr, bool is_secure) const
233{
234 Addr blkAddr = blkAlign(addr);
235 FALRUBlk* blk = hashLookup(blkAddr);
236
237 if (blk && blk->isValid()) {
238 assert(blk->tag == blkAddr);
239 } else {
240 blk = nullptr;
241 }
242 return blk;
243}
244
245CacheBlk*
246FALRU::findBlockBySetAndWay(int set, int way) const
247{
248 assert(set == 0);
249 return &blks[way];
250}
251
252CacheBlk*
253FALRU::findVictim(Addr addr)
254{
255 return tail;
256}
257
258void
259FALRU::insertBlock(PacketPtr pkt, CacheBlk *blk)
260{
261 FALRUBlk* falruBlk = static_cast<FALRUBlk*>(blk);
262
263 // Make sure block is not present in the cache
264 assert(falruBlk->inCache == 0);
265
266 // Do common block insertion functionality
267 BaseTags::insertBlock(pkt, blk);
268
269 // New block is the MRU
270 moveToHead(falruBlk);
271
272 // Insert new block in the hash table
273 tagHash[falruBlk->tag] = falruBlk;
274
275 //assert(check());
276}
277
278void
279FALRU::moveToHead(FALRUBlk *blk)
280{
|
279 int updateMask = blk->inCache ^ cacheMask;
280 for (unsigned i = 0; i < numCaches; i++){
281 if ((1<<i) & updateMask) {
282 cacheBoundaries[i]->inCache &= ~(1<<i);
283 cacheBoundaries[i] = cacheBoundaries[i]->prev;
284 } else if (cacheBoundaries[i] == blk) {
285 cacheBoundaries[i] = blk->prev;
286 }
287 }
288 blk->inCache = cacheMask;
| 281 // If block is not already head, do the moving
|
289 if (blk != head) {
| 282 if (blk != head) {
|
| 283 // Get all caches that this block does not reside in
284 int updateMask = blk->inCache ^ cacheMask;
285
286 // Update boundaries for all cache sizes
287 for (unsigned i = 0; i < numCaches; i++){
288 // If block has been moved to a place before this boundary,
289 // all blocks in it will be pushed towards the LRU position,
290 // making one leave the boundary
291 if ((1U<<i) & updateMask) {
292 cacheBoundaries[i]->inCache &= ~(1U<<i);
293 cacheBoundaries[i] = cacheBoundaries[i]->prev;
294 // If the block resides exactly at this boundary, the previous
295 // block is pushed to its position
296 } else if (cacheBoundaries[i] == blk) {
297 cacheBoundaries[i] = blk->prev;
298 }
299 }
300
301 // Make block reside in all caches
302 blk->inCache = cacheMask;
303
304 // If block is tail, set previous block as new tail
|
290 if (blk == tail){
291 assert(blk->next == nullptr);
292 tail = blk->prev;
293 tail->next = nullptr;
| 305 if (blk == tail){
306 assert(blk->next == nullptr);
307 tail = blk->prev;
308 tail->next = nullptr;
|
| 309 // Inform block's surrounding blocks that it has been moved
|
294 } else {
295 blk->prev->next = blk->next;
296 blk->next->prev = blk->prev;
297 }
| 310 } else {
311 blk->prev->next = blk->next;
312 blk->next->prev = blk->prev;
313 }
|
| 314
315 // Swap pointers
|
298 blk->next = head;
299 blk->prev = nullptr;
300 head->prev = blk;
301 head = blk;
302 }
303}
304
| 316 blk->next = head;
317 blk->prev = nullptr;
318 head->prev = blk;
319 head = blk;
320 }
321}
322
|
| 323void
324FALRU::moveToTail(FALRUBlk *blk)
325{
326 // If block is not already tail, do the moving
327 if (blk != tail) {
328 // Update boundaries for all cache sizes
329 for (unsigned i = 0; i < numCaches; i++){
330 // If block has been moved to a place after this boundary,
331 // all blocks in it will be pushed towards the MRU position,
332 // making one enter the boundary
333 if ((1U<<i) & blk->inCache) {
334 // If the first block after the boundary is the block,
335 // get its successor
336 if (cacheBoundaries[i]->next == blk){
337 cacheBoundaries[i] = cacheBoundaries[i]->next->next;
338 } else {
339 cacheBoundaries[i] = cacheBoundaries[i]->next;
340 }
341 cacheBoundaries[i]->inCache |= (1U<<i);
342 }
343 }
344
345 // Make block reside in the last cache only
346 blk->inCache = 0;
347
348 // If block is head, set next block as new head
349 if (blk == head){
350 assert(blk->prev == nullptr);
351 head = blk->next;
352 head->prev = nullptr;
353 // Inform block's surrounding blocks that it has been moved
354 } else {
355 blk->prev->next = blk->next;
356 blk->next->prev = blk->prev;
357 }
358
359 // Swap pointers
360 blk->prev = tail;
361 blk->next = nullptr;
362 tail->next = blk;
363 tail = blk;
364 }
365}
366
|
305bool
306FALRU::check()
307{
308 FALRUBlk* blk = head;
309 int tot_size = 0;
310 int boundary = 1<<17;
311 int j = 0;
312 int flags = cacheMask;
313 while (blk) {
314 tot_size += blkSize;
315 if (blk->inCache != flags) {
316 return false;
317 }
318 if (tot_size == boundary && blk != tail) {
319 if (cacheBoundaries[j] != blk) {
320 return false;
321 }
322 flags &=~(1 << j);
323 boundary = boundary<<1;
324 ++j;
325 }
326 blk = blk->next;
327 }
328 return true;
329}
330
331FALRU *
332FALRUParams::create()
333{
334 return new FALRU(this);
335}
336
| 367bool
368FALRU::check()
369{
370 FALRUBlk* blk = head;
371 int tot_size = 0;
372 int boundary = 1<<17;
373 int j = 0;
374 int flags = cacheMask;
375 while (blk) {
376 tot_size += blkSize;
377 if (blk->inCache != flags) {
378 return false;
379 }
380 if (tot_size == boundary && blk != tail) {
381 if (cacheBoundaries[j] != blk) {
382 return false;
383 }
384 flags &=~(1 << j);
385 boundary = boundary<<1;
386 ++j;
387 }
388 blk = blk->next;
389 }
390 return true;
391}
392
393FALRU *
394FALRUParams::create()
395{
396 return new FALRU(this);
397}
398
|