1/*
2 * Copyright (c) 2013 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 <cassert>
49#include <sstream>
50
51#include "base/intmath.hh"
52#include "base/misc.hh"
53#include "mem/cache/tags/fa_lru.hh"
54
55using namespace std;
56
57FALRU::FALRU(const Params *p)
58 : BaseTags(p), cacheBoundaries(nullptr)
59{
60 if (!isPowerOf2(blkSize))
61 fatal("cache block size (in bytes) `%d' must be a power of two",
62 blkSize);
63 if (!isPowerOf2(size))
64 fatal("Cache Size must be power of 2 for now");
65
66 // Track all cache sizes from 128K up by powers of 2
67 numCaches = floorLog2(size) - 17;
68 if (numCaches >0){
69 cacheBoundaries = new FALRUBlk *[numCaches];
70 cacheMask = (1 << numCaches) - 1;
71 } else {
72 cacheMask = 0;
73 }
74
75 warmupBound = size/blkSize;
76 numBlocks = size/blkSize;
77
78 blks = new FALRUBlk[numBlocks];
79 head = &(blks[0]);
80 tail = &(blks[numBlocks-1]);
81
82 head->prev = NULL;
83 head->next = &(blks[1]);
84 head->inCache = cacheMask;
85
86 tail->prev = &(blks[numBlocks-2]);
87 tail->next = NULL;
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 }
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 NULL;
161}
162
163void
| 1/*
2 * Copyright (c) 2013 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 <cassert>
49#include <sstream>
50
51#include "base/intmath.hh"
52#include "base/misc.hh"
53#include "mem/cache/tags/fa_lru.hh"
54
55using namespace std;
56
57FALRU::FALRU(const Params *p)
58 : BaseTags(p), cacheBoundaries(nullptr)
59{
60 if (!isPowerOf2(blkSize))
61 fatal("cache block size (in bytes) `%d' must be a power of two",
62 blkSize);
63 if (!isPowerOf2(size))
64 fatal("Cache Size must be power of 2 for now");
65
66 // Track all cache sizes from 128K up by powers of 2
67 numCaches = floorLog2(size) - 17;
68 if (numCaches >0){
69 cacheBoundaries = new FALRUBlk *[numCaches];
70 cacheMask = (1 << numCaches) - 1;
71 } else {
72 cacheMask = 0;
73 }
74
75 warmupBound = size/blkSize;
76 numBlocks = size/blkSize;
77
78 blks = new FALRUBlk[numBlocks];
79 head = &(blks[0]);
80 tail = &(blks[numBlocks-1]);
81
82 head->prev = NULL;
83 head->next = &(blks[1]);
84 head->inCache = cacheMask;
85
86 tail->prev = &(blks[numBlocks-2]);
87 tail->next = NULL;
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 }
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 NULL;
161}
162
163void
|
164FALRU::invalidate(FALRU::BlkType *blk)
| 164FALRU::invalidate(CacheBlk *blk)
|
165{
166 assert(blk);
167 tagsInUse--;
168}
169
| 165{
166 assert(blk);
167 tagsInUse--;
168}
169
|
170FALRUBlk*
| 170CacheBlk*
171FALRU::accessBlock(Addr addr, bool is_secure, Cycles &lat, int context_src)
172{
173 return accessBlock(addr, is_secure, lat, context_src, 0);
174}
175
176CacheBlk*
|
171FALRU::accessBlock(Addr addr, bool is_secure, Cycles &lat, int context_src,
172 int *inCache)
173{
174 accesses++;
175 int tmp_in_cache = 0;
176 Addr blkAddr = blkAlign(addr);
177 FALRUBlk* blk = hashLookup(blkAddr);
178
179 if (blk && blk->isValid()) {
180 assert(blk->tag == blkAddr);
181 tmp_in_cache = blk->inCache;
182 for (unsigned i = 0; i < numCaches; i++) {
183 if (1<<i & blk->inCache) {
184 hits[i]++;
185 } else {
186 misses[i]++;
187 }
188 }
189 hits[numCaches]++;
190 if (blk != head){
191 moveToHead(blk);
192 }
193 } else {
194 blk = NULL;
195 for (unsigned i = 0; i <= numCaches; ++i) {
196 misses[i]++;
197 }
198 }
199 if (inCache) {
200 *inCache = tmp_in_cache;
201 }
202
203 lat = accessLatency;
204 //assert(check());
205 return blk;
206}
207
208
| 177FALRU::accessBlock(Addr addr, bool is_secure, Cycles &lat, int context_src,
178 int *inCache)
179{
180 accesses++;
181 int tmp_in_cache = 0;
182 Addr blkAddr = blkAlign(addr);
183 FALRUBlk* blk = hashLookup(blkAddr);
184
185 if (blk && blk->isValid()) {
186 assert(blk->tag == blkAddr);
187 tmp_in_cache = blk->inCache;
188 for (unsigned i = 0; i < numCaches; i++) {
189 if (1<<i & blk->inCache) {
190 hits[i]++;
191 } else {
192 misses[i]++;
193 }
194 }
195 hits[numCaches]++;
196 if (blk != head){
197 moveToHead(blk);
198 }
199 } else {
200 blk = NULL;
201 for (unsigned i = 0; i <= numCaches; ++i) {
202 misses[i]++;
203 }
204 }
205 if (inCache) {
206 *inCache = tmp_in_cache;
207 }
208
209 lat = accessLatency;
210 //assert(check());
211 return blk;
212}
213
214
|
209FALRUBlk*
| 215CacheBlk*
|
210FALRU::findBlock(Addr addr, bool is_secure) const
211{
212 Addr blkAddr = blkAlign(addr);
213 FALRUBlk* blk = hashLookup(blkAddr);
214
215 if (blk && blk->isValid()) {
216 assert(blk->tag == blkAddr);
217 } else {
218 blk = NULL;
219 }
220 return blk;
221}
222
| 216FALRU::findBlock(Addr addr, bool is_secure) const
217{
218 Addr blkAddr = blkAlign(addr);
219 FALRUBlk* blk = hashLookup(blkAddr);
220
221 if (blk && blk->isValid()) {
222 assert(blk->tag == blkAddr);
223 } else {
224 blk = NULL;
225 }
226 return blk;
227}
228
|
223FALRUBlk*
| 229CacheBlk*
|
224FALRU::findVictim(Addr addr)
225{
226 FALRUBlk * blk = tail;
227 assert(blk->inCache == 0);
228 moveToHead(blk);
229 tagHash.erase(blk->tag);
230 tagHash[blkAlign(addr)] = blk;
231 if (blk->isValid()) {
232 replacements[0]++;
233 } else {
234 tagsInUse++;
235 blk->isTouched = true;
236 if (!warmedUp && tagsInUse.value() >= warmupBound) {
237 warmedUp = true;
238 warmupCycle = curTick();
239 }
240 }
241 //assert(check());
242 return blk;
243}
244
245void
| 230FALRU::findVictim(Addr addr)
231{
232 FALRUBlk * blk = tail;
233 assert(blk->inCache == 0);
234 moveToHead(blk);
235 tagHash.erase(blk->tag);
236 tagHash[blkAlign(addr)] = blk;
237 if (blk->isValid()) {
238 replacements[0]++;
239 } else {
240 tagsInUse++;
241 blk->isTouched = true;
242 if (!warmedUp && tagsInUse.value() >= warmupBound) {
243 warmedUp = true;
244 warmupCycle = curTick();
245 }
246 }
247 //assert(check());
248 return blk;
249}
250
251void
|
246FALRU::insertBlock(PacketPtr pkt, FALRU::BlkType *blk)
| 252FALRU::insertBlock(PacketPtr pkt, CacheBlk *blk)
|
247{
248}
249
250void
251FALRU::moveToHead(FALRUBlk *blk)
252{
253 int updateMask = blk->inCache ^ cacheMask;
254 for (unsigned i = 0; i < numCaches; i++){
255 if ((1<<i) & updateMask) {
256 cacheBoundaries[i]->inCache &= ~(1<<i);
257 cacheBoundaries[i] = cacheBoundaries[i]->prev;
258 } else if (cacheBoundaries[i] == blk) {
259 cacheBoundaries[i] = blk->prev;
260 }
261 }
262 blk->inCache = cacheMask;
263 if (blk != head) {
264 if (blk == tail){
265 assert(blk->next == NULL);
266 tail = blk->prev;
267 tail->next = NULL;
268 } else {
269 blk->prev->next = blk->next;
270 blk->next->prev = blk->prev;
271 }
272 blk->next = head;
273 blk->prev = NULL;
274 head->prev = blk;
275 head = blk;
276 }
277}
278
279bool
280FALRU::check()
281{
282 FALRUBlk* blk = head;
283 int tot_size = 0;
284 int boundary = 1<<17;
285 int j = 0;
286 int flags = cacheMask;
287 while (blk) {
288 tot_size += blkSize;
289 if (blk->inCache != flags) {
290 return false;
291 }
292 if (tot_size == boundary && blk != tail) {
293 if (cacheBoundaries[j] != blk) {
294 return false;
295 }
296 flags &=~(1 << j);
297 boundary = boundary<<1;
298 ++j;
299 }
300 blk = blk->next;
301 }
302 return true;
303}
304
305void
306FALRU::clearLocks()
307{
308 for (int i = 0; i < numBlocks; i++){
309 blks[i].clearLoadLocks();
310 }
311}
312
313FALRU *
314FALRUParams::create()
315{
316 return new FALRU(this);
317}
318
| 253{
254}
255
256void
257FALRU::moveToHead(FALRUBlk *blk)
258{
259 int updateMask = blk->inCache ^ cacheMask;
260 for (unsigned i = 0; i < numCaches; i++){
261 if ((1<<i) & updateMask) {
262 cacheBoundaries[i]->inCache &= ~(1<<i);
263 cacheBoundaries[i] = cacheBoundaries[i]->prev;
264 } else if (cacheBoundaries[i] == blk) {
265 cacheBoundaries[i] = blk->prev;
266 }
267 }
268 blk->inCache = cacheMask;
269 if (blk != head) {
270 if (blk == tail){
271 assert(blk->next == NULL);
272 tail = blk->prev;
273 tail->next = NULL;
274 } else {
275 blk->prev->next = blk->next;
276 blk->next->prev = blk->prev;
277 }
278 blk->next = head;
279 blk->prev = NULL;
280 head->prev = blk;
281 head = blk;
282 }
283}
284
285bool
286FALRU::check()
287{
288 FALRUBlk* blk = head;
289 int tot_size = 0;
290 int boundary = 1<<17;
291 int j = 0;
292 int flags = cacheMask;
293 while (blk) {
294 tot_size += blkSize;
295 if (blk->inCache != flags) {
296 return false;
297 }
298 if (tot_size == boundary && blk != tail) {
299 if (cacheBoundaries[j] != blk) {
300 return false;
301 }
302 flags &=~(1 << j);
303 boundary = boundary<<1;
304 ++j;
305 }
306 blk = blk->next;
307 }
308 return true;
309}
310
311void
312FALRU::clearLocks()
313{
314 for (int i = 0; i < numBlocks; i++){
315 blks[i].clearLoadLocks();
316 }
317}
318
319FALRU *
320FALRUParams::create()
321{
322 return new FALRU(this);
323}
324
|