fa_lru.cc revision 11722:f15f02d8c79e 
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 "mem/cache/tags/fa_lru.hh"
49
50#include <cassert>
51#include <sstream>
52
53#include "base/intmath.hh"
54#include "base/misc.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    warmupBound = size/blkSize;
77    numBlocks = size/blkSize;
78
79    blks = new FALRUBlk[numBlocks];
80    head = &(blks[0]);
81    tail = &(blks[numBlocks-1]);
82
83    head->prev = nullptr;
84    head->next = &(blks[1]);
85    head->inCache = cacheMask;
86
87    tail->prev = &(blks[numBlocks-2]);
88    tail->next = nullptr;
89    tail->inCache = 0;
90
91    unsigned index = (1 << 17) / blkSize;
92    unsigned j = 0;
93    int flags = cacheMask;
94    for (unsigned i = 1; i < numBlocks - 1; i++) {
95        blks[i].inCache = flags;
96        if (i == index - 1){
97            cacheBoundaries[j] = &(blks[i]);
98            flags &= ~ (1<<j);
99            ++j;
100            index = index << 1;
101        }
102        blks[i].prev = &(blks[i-1]);
103        blks[i].next = &(blks[i+1]);
104        blks[i].isTouched = false;
105        blks[i].set = 0;
106        blks[i].way = i;
107    }
108    assert(j == numCaches);
109    assert(index == numBlocks);
110    //assert(check());
111}
112
113FALRU::~FALRU()
114{
115    if (numCaches)
116        delete[] cacheBoundaries;
117
118    delete[] blks;
119}
120
121void
122FALRU::regStats()
123{
124    using namespace Stats;
125    BaseTags::regStats();
126    hits
127        .init(numCaches+1)
128        .name(name() + ".falru_hits")
129        .desc("The number of hits in each cache size.")
130        ;
131    misses
132        .init(numCaches+1)
133        .name(name() + ".falru_misses")
134        .desc("The number of misses in each cache size.")
135        ;
136    accesses
137        .name(name() + ".falru_accesses")
138        .desc("The number of accesses to the FA LRU cache.")
139        ;
140
141    for (unsigned i = 0; i <= numCaches; ++i) {
142        stringstream size_str;
143        if (i < 3){
144            size_str << (1<<(i+7)) <<"K";
145        } else {
146            size_str << (1<<(i-3)) <<"M";
147        }
148
149        hits.subname(i, size_str.str());
150        hits.subdesc(i, "Hits in a " + size_str.str() +" cache");
151        misses.subname(i, size_str.str());
152        misses.subdesc(i, "Misses in a " + size_str.str() +" cache");
153    }
154}
155
156FALRUBlk *
157FALRU::hashLookup(Addr addr) const
158{
159    tagIterator iter = tagHash.find(addr);
160    if (iter != tagHash.end()) {
161        return (*iter).second;
162    }
163    return nullptr;
164}
165
166void
167FALRU::invalidate(CacheBlk *blk)
168{
169    assert(blk);
170    tagsInUse--;
171}
172
173CacheBlk*
174FALRU::accessBlock(Addr addr, bool is_secure, Cycles &lat, int context_src)
175{
176    return accessBlock(addr, is_secure, lat, context_src, 0);
177}
178
179CacheBlk*
180FALRU::accessBlock(Addr addr, bool is_secure, Cycles &lat, int context_src,
181                   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        blk->isTouched = true;
263        if (!warmedUp && tagsInUse.value() >= warmupBound) {
264            warmedUp = true;
265            warmupCycle = curTick();
266        }
267    }
268    //assert(check());
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
338