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 (!(hitLatency > 0))
64 fatal("Access latency in cycles must be at least one cycle");
65 if (!isPowerOf2(size))
66 fatal("Cache Size must be power of 2 for now");
67
68 // Track all cache sizes from 128K up by powers of 2
69 numCaches = floorLog2(size) - 17;
70 if (numCaches >0){
71 cacheBoundaries = new FALRUBlk *[numCaches];
72 cacheMask = (1 << numCaches) - 1;
73 } else {
74 cacheMask = 0;
75 }
76
77 warmupBound = size/blkSize;
78 numBlocks = size/blkSize;
79
80 blks = new FALRUBlk[numBlocks];
81 head = &(blks[0]);
82 tail = &(blks[numBlocks-1]);
83
84 head->prev = NULL;
85 head->next = &(blks[1]);
86 head->inCache = cacheMask;
87
88 tail->prev = &(blks[numBlocks-2]);
89 tail->next = NULL;
90 tail->inCache = 0;
91
92 unsigned index = (1 << 17) / blkSize;
93 unsigned j = 0;
94 int flags = cacheMask;
95 for (unsigned i = 1; i < numBlocks - 1; i++) {
96 blks[i].inCache = flags;
97 if (i == index - 1){
98 cacheBoundaries[j] = &(blks[i]);
99 flags &= ~ (1<<j);
100 ++j;
101 index = index << 1;
102 }
103 blks[i].prev = &(blks[i-1]);
104 blks[i].next = &(blks[i+1]);
105 blks[i].isTouched = false;
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 using namespace Stats;
124 BaseTags::regStats();
125 hits
126 .init(numCaches+1)
127 .name(name() + ".falru_hits")
128 .desc("The number of hits in each cache size.")
129 ;
130 misses
131 .init(numCaches+1)
132 .name(name() + ".falru_misses")
133 .desc("The number of misses in each cache size.")
134 ;
135 accesses
136 .name(name() + ".falru_accesses")
137 .desc("The number of accesses to the FA LRU cache.")
138 ;
139
140 for (unsigned i = 0; i <= numCaches; ++i) {
141 stringstream size_str;
142 if (i < 3){
143 size_str << (1<<(i+7)) <<"K";
144 } else {
145 size_str << (1<<(i-3)) <<"M";
146 }
147
148 hits.subname(i, size_str.str());
149 hits.subdesc(i, "Hits in a " + size_str.str() +" cache");
150 misses.subname(i, size_str.str());
151 misses.subdesc(i, "Misses in a " + size_str.str() +" cache");
152 }
153}
154
155FALRUBlk *
156FALRU::hashLookup(Addr addr) const
157{
158 tagIterator iter = tagHash.find(addr);
159 if (iter != tagHash.end()) {
160 return (*iter).second;
161 }
162 return NULL;
163}
164
165void
166FALRU::invalidate(FALRU::BlkType *blk)
167{
168 assert(blk);
169 tagsInUse--;
170}
171
172FALRUBlk*
173FALRU::accessBlock(Addr addr, bool is_secure, Cycles &lat, int context_src,
174 int *inCache)
175{
176 accesses++;
177 int tmp_in_cache = 0;
178 Addr blkAddr = blkAlign(addr);
179 FALRUBlk* blk = hashLookup(blkAddr);
180
181 if (blk && blk->isValid()) {
182 assert(blk->tag == blkAddr);
183 tmp_in_cache = blk->inCache;
184 for (unsigned i = 0; i < numCaches; i++) {
185 if (1<<i & blk->inCache) {
186 hits[i]++;
187 } else {
188 misses[i]++;
189 }
190 }
191 hits[numCaches]++;
192 if (blk != head){
193 moveToHead(blk);
194 }
195 } else {
196 blk = NULL;
197 for (unsigned i = 0; i <= numCaches; ++i) {
198 misses[i]++;
199 }
200 }
201 if (inCache) {
202 *inCache = tmp_in_cache;
203 }
204
205 lat = hitLatency;
206 //assert(check());
207 return blk;
208}
209
210
211FALRUBlk*
212FALRU::findBlock(Addr addr, bool is_secure) const
213{
214 Addr blkAddr = blkAlign(addr);
215 FALRUBlk* blk = hashLookup(blkAddr);
216
217 if (blk && blk->isValid()) {
218 assert(blk->tag == blkAddr);
219 } else {
220 blk = NULL;
221 }
222 return blk;
223}
224
225FALRUBlk*
226FALRU::findVictim(Addr addr)
227{
228 FALRUBlk * blk = tail;
229 assert(blk->inCache == 0);
230 moveToHead(blk);
231 tagHash.erase(blk->tag);
232 tagHash[blkAlign(addr)] = blk;
233 if (blk->isValid()) {
234 replacements[0]++;
235 } else {
236 tagsInUse++;
237 blk->isTouched = true;
238 if (!warmedUp && tagsInUse.value() >= warmupBound) {
239 warmedUp = true;
240 warmupCycle = curTick();
241 }
242 }
243 //assert(check());
244 return blk;
245}
246
247void
248FALRU::insertBlock(PacketPtr pkt, FALRU::BlkType *blk)
249{
250}
251
252void
253FALRU::moveToHead(FALRUBlk *blk)
254{
255 int updateMask = blk->inCache ^ cacheMask;
256 for (unsigned i = 0; i < numCaches; i++){
257 if ((1<<i) & updateMask) {
258 cacheBoundaries[i]->inCache &= ~(1<<i);
259 cacheBoundaries[i] = cacheBoundaries[i]->prev;
260 } else if (cacheBoundaries[i] == blk) {
261 cacheBoundaries[i] = blk->prev;
262 }
263 }
264 blk->inCache = cacheMask;
265 if (blk != head) {
266 if (blk == tail){
267 assert(blk->next == NULL);
268 tail = blk->prev;
269 tail->next = NULL;
270 } else {
271 blk->prev->next = blk->next;
272 blk->next->prev = blk->prev;
273 }
274 blk->next = head;
275 blk->prev = NULL;
276 head->prev = blk;
277 head = blk;
278 }
279}
280
281bool
282FALRU::check()
283{
284 FALRUBlk* blk = head;
285 int tot_size = 0;
286 int boundary = 1<<17;
287 int j = 0;
288 int flags = cacheMask;
289 while (blk) {
290 tot_size += blkSize;
291 if (blk->inCache != flags) {
292 return false;
293 }
294 if (tot_size == boundary && blk != tail) {
295 if (cacheBoundaries[j] != blk) {
296 return false;
297 }
298 flags &=~(1 << j);
299 boundary = boundary<<1;
300 ++j;
301 }
302 blk = blk->next;
303 }
304 return true;
305}
306
307void
308FALRU::clearLocks()
309{
310 for (int i = 0; i < numBlocks; i++){
311 blks[i].clearLoadLocks();
312 }
313}
314
315FALRU *
316FALRUParams::create()
317{
318 return new FALRU(this);
319}
320