fa_lru.cc revision 10815:169af9a2779f 
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(CacheBlk *blk)
165{
166    assert(blk);
167    tagsInUse--;
168}
169
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*
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
215CacheBlk*
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
229CacheBlk*
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
252FALRU::insertBlock(PacketPtr pkt, CacheBlk *blk)
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
325