fa_lru.cc revision 12636:9859213e2662 
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];
84
85    tail->prev = &(blks[numBlocks-2]);
86    tail->next = nullptr;
87    tail->inCache = 0;
88    tail->data = &dataBlks[(numBlocks-1)*blkSize];
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];
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    // Erase block entry in the hash table
174    tagHash.erase(blk->tag);
175}
176
177CacheBlk*
178FALRU::accessBlock(Addr addr, bool is_secure, Cycles &lat)
179{
180    return accessBlock(addr, is_secure, lat, 0);
181}
182
183CacheBlk*
184FALRU::accessBlock(Addr addr, bool is_secure, Cycles &lat, int *inCache)
185{
186    accesses++;
187    int tmp_in_cache = 0;
188    Addr blkAddr = blkAlign(addr);
189    FALRUBlk* blk = hashLookup(blkAddr);
190
191    if (blk && blk->isValid()) {
192        // If a cache hit
193        lat = accessLatency;
194        // Check if the block to be accessed is available. If not,
195        // apply the accessLatency on top of block->whenReady.
196        if (blk->whenReady > curTick() &&
197            cache->ticksToCycles(blk->whenReady - curTick()) >
198            accessLatency) {
199            lat = cache->ticksToCycles(blk->whenReady - curTick()) +
200            accessLatency;
201        }
202        assert(blk->tag == blkAddr);
203        tmp_in_cache = blk->inCache;
204        for (unsigned i = 0; i < numCaches; i++) {
205            if (1<<i & blk->inCache) {
206                hits[i]++;
207            } else {
208                misses[i]++;
209            }
210        }
211        hits[numCaches]++;
212        if (blk != head){
213            moveToHead(blk);
214        }
215    } else {
216        // If a cache miss
217        lat = lookupLatency;
218        blk = nullptr;
219        for (unsigned i = 0; i <= numCaches; ++i) {
220            misses[i]++;
221        }
222    }
223    if (inCache) {
224        *inCache = tmp_in_cache;
225    }
226
227    //assert(check());
228    return blk;
229}
230
231
232CacheBlk*
233FALRU::findBlock(Addr addr, bool is_secure) const
234{
235    Addr blkAddr = blkAlign(addr);
236    FALRUBlk* blk = hashLookup(blkAddr);
237
238    if (blk && blk->isValid()) {
239        assert(blk->tag == blkAddr);
240    } else {
241        blk = nullptr;
242    }
243    return blk;
244}
245
246CacheBlk*
247FALRU::findBlockBySetAndWay(int set, int way) const
248{
249    assert(set == 0);
250    return &blks[way];
251}
252
253CacheBlk*
254FALRU::findVictim(Addr addr)
255{
256    return tail;
257}
258
259void
260FALRU::insertBlock(PacketPtr pkt, CacheBlk *blk)
261{
262    FALRUBlk* falruBlk = static_cast<FALRUBlk*>(blk);
263
264    // Make sure block is not present in the cache
265    assert(falruBlk->inCache == 0);
266
267    // Do common block insertion functionality
268    BaseTags::insertBlock(pkt, blk);
269
270    // New block is the MRU
271    moveToHead(falruBlk);
272
273    // Insert new block in the hash table
274    tagHash[falruBlk->tag] = falruBlk;
275
276    //assert(check());
277}
278
279void
280FALRU::moveToHead(FALRUBlk *blk)
281{
282    int updateMask = blk->inCache ^ cacheMask;
283    for (unsigned i = 0; i < numCaches; i++){
284        if ((1<<i) & updateMask) {
285            cacheBoundaries[i]->inCache &= ~(1<<i);
286            cacheBoundaries[i] = cacheBoundaries[i]->prev;
287        } else if (cacheBoundaries[i] == blk) {
288            cacheBoundaries[i] = blk->prev;
289        }
290    }
291    blk->inCache = cacheMask;
292    if (blk != head) {
293        if (blk == tail){
294            assert(blk->next == nullptr);
295            tail = blk->prev;
296            tail->next = nullptr;
297        } else {
298            blk->prev->next = blk->next;
299            blk->next->prev = blk->prev;
300        }
301        blk->next = head;
302        blk->prev = nullptr;
303        head->prev = blk;
304        head = blk;
305    }
306}
307
308bool
309FALRU::check()
310{
311    FALRUBlk* blk = head;
312    int tot_size = 0;
313    int boundary = 1<<17;
314    int j = 0;
315    int flags = cacheMask;
316    while (blk) {
317        tot_size += blkSize;
318        if (blk->inCache != flags) {
319            return false;
320        }
321        if (tot_size == boundary && blk != tail) {
322            if (cacheBoundaries[j] != blk) {
323                return false;
324            }
325            flags &=~(1 << j);
326            boundary = boundary<<1;
327            ++j;
328        }
329        blk = blk->next;
330    }
331    return true;
332}
333
334FALRU *
335FALRUParams::create()
336{
337    return new FALRU(this);
338}
339
340