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
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 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;
| 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
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 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 head->data = &dataBlks[0];
|
83
84 tail->prev = &(blks[numBlocks-2]);
85 tail->next = nullptr;
86 tail->inCache = 0;
| 84
85 tail->prev = &(blks[numBlocks-2]);
86 tail->next = nullptr;
87 tail->inCache = 0;
|
| 88 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;
| 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].set = 0;
104 blks[i].way = i;
|
| 105
106 // Associate a data chunk to the block
107 blks[i].data = &dataBlks[blkSize*i];
|
103 }
104 assert(j == numCaches);
105 assert(index == numBlocks);
106 //assert(check());
107}
108
109FALRU::~FALRU()
110{
111 if (numCaches)
112 delete[] cacheBoundaries;
113
114 delete[] blks;
115}
116
117void
118FALRU::regStats()
119{
120 using namespace Stats;
121 BaseTags::regStats();
122 hits
123 .init(numCaches+1)
124 .name(name() + ".falru_hits")
125 .desc("The number of hits in each cache size.")
126 ;
127 misses
128 .init(numCaches+1)
129 .name(name() + ".falru_misses")
130 .desc("The number of misses in each cache size.")
131 ;
132 accesses
133 .name(name() + ".falru_accesses")
134 .desc("The number of accesses to the FA LRU cache.")
135 ;
136
137 for (unsigned i = 0; i <= numCaches; ++i) {
138 stringstream size_str;
139 if (i < 3){
140 size_str << (1<<(i+7)) <<"K";
141 } else {
142 size_str << (1<<(i-3)) <<"M";
143 }
144
145 hits.subname(i, size_str.str());
146 hits.subdesc(i, "Hits in a " + size_str.str() +" cache");
147 misses.subname(i, size_str.str());
148 misses.subdesc(i, "Misses in a " + size_str.str() +" cache");
149 }
150}
151
152FALRUBlk *
153FALRU::hashLookup(Addr addr) const
154{
155 tagIterator iter = tagHash.find(addr);
156 if (iter != tagHash.end()) {
157 return (*iter).second;
158 }
159 return nullptr;
160}
161
162void
163FALRU::invalidate(CacheBlk *blk)
164{
165 // TODO: We need to move the block to the tail to make it the next victim
166 BaseTags::invalidate(blk);
167}
168
169CacheBlk*
170FALRU::accessBlock(Addr addr, bool is_secure, Cycles &lat)
171{
172 return accessBlock(addr, is_secure, lat, 0);
173}
174
175CacheBlk*
176FALRU::accessBlock(Addr addr, bool is_secure, Cycles &lat, int *inCache)
177{
178 accesses++;
179 int tmp_in_cache = 0;
180 Addr blkAddr = blkAlign(addr);
181 FALRUBlk* blk = hashLookup(blkAddr);
182
183 if (blk && blk->isValid()) {
184 // If a cache hit
185 lat = accessLatency;
186 // Check if the block to be accessed is available. If not,
187 // apply the accessLatency on top of block->whenReady.
188 if (blk->whenReady > curTick() &&
189 cache->ticksToCycles(blk->whenReady - curTick()) >
190 accessLatency) {
191 lat = cache->ticksToCycles(blk->whenReady - curTick()) +
192 accessLatency;
193 }
194 assert(blk->tag == blkAddr);
195 tmp_in_cache = blk->inCache;
196 for (unsigned i = 0; i < numCaches; i++) {
197 if (1<<i & blk->inCache) {
198 hits[i]++;
199 } else {
200 misses[i]++;
201 }
202 }
203 hits[numCaches]++;
204 if (blk != head){
205 moveToHead(blk);
206 }
207 } else {
208 // If a cache miss
209 lat = lookupLatency;
210 blk = nullptr;
211 for (unsigned i = 0; i <= numCaches; ++i) {
212 misses[i]++;
213 }
214 }
215 if (inCache) {
216 *inCache = tmp_in_cache;
217 }
218
219 //assert(check());
220 return blk;
221}
222
223
224CacheBlk*
225FALRU::findBlock(Addr addr, bool is_secure) const
226{
227 Addr blkAddr = blkAlign(addr);
228 FALRUBlk* blk = hashLookup(blkAddr);
229
230 if (blk && blk->isValid()) {
231 assert(blk->tag == blkAddr);
232 } else {
233 blk = nullptr;
234 }
235 return blk;
236}
237
238CacheBlk*
239FALRU::findBlockBySetAndWay(int set, int way) const
240{
241 assert(set == 0);
242 return &blks[way];
243}
244
245CacheBlk*
246FALRU::findVictim(Addr addr)
247{
248 FALRUBlk * blk = tail;
249 assert(blk->inCache == 0);
250 moveToHead(blk);
251 tagHash.erase(blk->tag);
252 tagHash[blkAlign(addr)] = blk;
253 if (blk->isValid()) {
254 replacements[0]++;
255 } else {
256 tagsInUse++;
257 if (!warmedUp && tagsInUse.value() >= warmupBound) {
258 warmedUp = true;
259 warmupCycle = curTick();
260 }
261 }
262 //assert(check());
263
264 return blk;
265}
266
267void
268FALRU::insertBlock(PacketPtr pkt, CacheBlk *blk)
269{
270}
271
272void
273FALRU::moveToHead(FALRUBlk *blk)
274{
275 int updateMask = blk->inCache ^ cacheMask;
276 for (unsigned i = 0; i < numCaches; i++){
277 if ((1<<i) & updateMask) {
278 cacheBoundaries[i]->inCache &= ~(1<<i);
279 cacheBoundaries[i] = cacheBoundaries[i]->prev;
280 } else if (cacheBoundaries[i] == blk) {
281 cacheBoundaries[i] = blk->prev;
282 }
283 }
284 blk->inCache = cacheMask;
285 if (blk != head) {
286 if (blk == tail){
287 assert(blk->next == nullptr);
288 tail = blk->prev;
289 tail->next = nullptr;
290 } else {
291 blk->prev->next = blk->next;
292 blk->next->prev = blk->prev;
293 }
294 blk->next = head;
295 blk->prev = nullptr;
296 head->prev = blk;
297 head = blk;
298 }
299}
300
301bool
302FALRU::check()
303{
304 FALRUBlk* blk = head;
305 int tot_size = 0;
306 int boundary = 1<<17;
307 int j = 0;
308 int flags = cacheMask;
309 while (blk) {
310 tot_size += blkSize;
311 if (blk->inCache != flags) {
312 return false;
313 }
314 if (tot_size == boundary && blk != tail) {
315 if (cacheBoundaries[j] != blk) {
316 return false;
317 }
318 flags &=~(1 << j);
319 boundary = boundary<<1;
320 ++j;
321 }
322 blk = blk->next;
323 }
324 return true;
325}
326
327FALRU *
328FALRUParams::create()
329{
330 return new FALRU(this);
331}
332
| 108 }
109 assert(j == numCaches);
110 assert(index == numBlocks);
111 //assert(check());
112}
113
114FALRU::~FALRU()
115{
116 if (numCaches)
117 delete[] cacheBoundaries;
118
119 delete[] blks;
120}
121
122void
123FALRU::regStats()
124{
125 using namespace Stats;
126 BaseTags::regStats();
127 hits
128 .init(numCaches+1)
129 .name(name() + ".falru_hits")
130 .desc("The number of hits in each cache size.")
131 ;
132 misses
133 .init(numCaches+1)
134 .name(name() + ".falru_misses")
135 .desc("The number of misses in each cache size.")
136 ;
137 accesses
138 .name(name() + ".falru_accesses")
139 .desc("The number of accesses to the FA LRU cache.")
140 ;
141
142 for (unsigned i = 0; i <= numCaches; ++i) {
143 stringstream size_str;
144 if (i < 3){
145 size_str << (1<<(i+7)) <<"K";
146 } else {
147 size_str << (1<<(i-3)) <<"M";
148 }
149
150 hits.subname(i, size_str.str());
151 hits.subdesc(i, "Hits in a " + size_str.str() +" cache");
152 misses.subname(i, size_str.str());
153 misses.subdesc(i, "Misses in a " + size_str.str() +" cache");
154 }
155}
156
157FALRUBlk *
158FALRU::hashLookup(Addr addr) const
159{
160 tagIterator iter = tagHash.find(addr);
161 if (iter != tagHash.end()) {
162 return (*iter).second;
163 }
164 return nullptr;
165}
166
167void
168FALRU::invalidate(CacheBlk *blk)
169{
170 // TODO: We need to move the block to the tail to make it the next victim
171 BaseTags::invalidate(blk);
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 FALRUBlk * blk = tail;
254 assert(blk->inCache == 0);
255 moveToHead(blk);
256 tagHash.erase(blk->tag);
257 tagHash[blkAlign(addr)] = blk;
258 if (blk->isValid()) {
259 replacements[0]++;
260 } else {
261 tagsInUse++;
262 if (!warmedUp && tagsInUse.value() >= warmupBound) {
263 warmedUp = true;
264 warmupCycle = curTick();
265 }
266 }
267 //assert(check());
268
269 return blk;
270}
271
272void
273FALRU::insertBlock(PacketPtr pkt, CacheBlk *blk)
274{
275}
276
277void
278FALRU::moveToHead(FALRUBlk *blk)
279{
280 int updateMask = blk->inCache ^ cacheMask;
281 for (unsigned i = 0; i < numCaches; i++){
282 if ((1<<i) & updateMask) {
283 cacheBoundaries[i]->inCache &= ~(1<<i);
284 cacheBoundaries[i] = cacheBoundaries[i]->prev;
285 } else if (cacheBoundaries[i] == blk) {
286 cacheBoundaries[i] = blk->prev;
287 }
288 }
289 blk->inCache = cacheMask;
290 if (blk != head) {
291 if (blk == tail){
292 assert(blk->next == nullptr);
293 tail = blk->prev;
294 tail->next = nullptr;
295 } else {
296 blk->prev->next = blk->next;
297 blk->next->prev = blk->prev;
298 }
299 blk->next = head;
300 blk->prev = nullptr;
301 head->prev = blk;
302 head = blk;
303 }
304}
305
306bool
307FALRU::check()
308{
309 FALRUBlk* blk = head;
310 int tot_size = 0;
311 int boundary = 1<<17;
312 int j = 0;
313 int flags = cacheMask;
314 while (blk) {
315 tot_size += blkSize;
316 if (blk->inCache != flags) {
317 return false;
318 }
319 if (tot_size == boundary && blk != tail) {
320 if (cacheBoundaries[j] != blk) {
321 return false;
322 }
323 flags &=~(1 << j);
324 boundary = boundary<<1;
325 ++j;
326 }
327 blk = blk->next;
328 }
329 return true;
330}
331
332FALRU *
333FALRUParams::create()
334{
335 return new FALRU(this);
336}
337
|