fa_lru.cc revision 9086 
1/*
2 * Copyright (c) 2003-2005 The Regents of The University of Michigan
3 * All rights reserved.
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions are
7 * met: redistributions of source code must retain the above copyright
8 * notice, this list of conditions and the following disclaimer;
9 * redistributions in binary form must reproduce the above copyright
10 * notice, this list of conditions and the following disclaimer in the
11 * documentation and/or other materials provided with the distribution;
12 * neither the name of the copyright holders nor the names of its
13 * contributors may be used to endorse or promote products derived from
14 * this software without specific prior written permission.
15 *
16 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
17 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
18 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
19 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
20 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
21 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
22 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
23 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
24 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
25 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
26 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
27 *
28 * Authors: Erik Hallnor
29 */
30
31/**
32 * @file
33 * Definitions a fully associative LRU tagstore.
34 */
35
36#include <cassert>
37#include <sstream>
38
39#include "base/intmath.hh"
40#include "base/misc.hh"
41#include "mem/cache/tags/fa_lru.hh"
42
43using namespace std;
44
45FALRU::FALRU(unsigned _blkSize, unsigned _size, unsigned hit_latency)
46    : blkSize(_blkSize), size(_size), hitLatency(hit_latency)
47{
48    if (!isPowerOf2(blkSize))
49        fatal("cache block size (in bytes) `%d' must be a power of two",
50              blkSize);
51    if (!(hitLatency > 0))
52        fatal("Access latency in cycles must be at least one cycle");
53    if (!isPowerOf2(size))
54        fatal("Cache Size must be power of 2 for now");
55
56    // Track all cache sizes from 128K up by powers of 2
57    numCaches = floorLog2(size) - 17;
58    if (numCaches >0){
59        cacheBoundaries = new FALRUBlk *[numCaches];
60        cacheMask = (1 << numCaches) - 1;
61    } else {
62        cacheMask = 0;
63    }
64
65    warmedUp = false;
66    warmupBound = size/blkSize;
67    numBlocks = size/blkSize;
68
69    blks = new FALRUBlk[numBlocks];
70    head = &(blks[0]);
71    tail = &(blks[numBlocks-1]);
72
73    head->prev = NULL;
74    head->next = &(blks[1]);
75    head->inCache = cacheMask;
76
77    tail->prev = &(blks[numBlocks-2]);
78    tail->next = NULL;
79    tail->inCache = 0;
80
81    unsigned index = (1 << 17) / blkSize;
82    unsigned j = 0;
83    int flags = cacheMask;
84    for (unsigned i = 1; i < numBlocks - 1; i++) {
85        blks[i].inCache = flags;
86        if (i == index - 1){
87            cacheBoundaries[j] = &(blks[i]);
88            flags &= ~ (1<<j);
89            ++j;
90            index = index << 1;
91        }
92        blks[i].prev = &(blks[i-1]);
93        blks[i].next = &(blks[i+1]);
94        blks[i].isTouched = false;
95    }
96    assert(j == numCaches);
97    assert(index == numBlocks);
98    //assert(check());
99}
100
101FALRU::~FALRU()
102{
103    if (numCaches)
104        delete[] cacheBoundaries;
105
106    delete[] blks;
107}
108
109void
110FALRU::regStats(const string &name)
111{
112    using namespace Stats;
113    BaseTags::regStats(name);
114    hits
115        .init(numCaches+1)
116        .name(name + ".falru_hits")
117        .desc("The number of hits in each cache size.")
118        ;
119    misses
120        .init(numCaches+1)
121        .name(name + ".falru_misses")
122        .desc("The number of misses in each cache size.")
123        ;
124    accesses
125        .name(name + ".falru_accesses")
126        .desc("The number of accesses to the FA LRU cache.")
127        ;
128
129    for (unsigned i = 0; i <= numCaches; ++i) {
130        stringstream size_str;
131        if (i < 3){
132            size_str << (1<<(i+7)) <<"K";
133        } else {
134            size_str << (1<<(i-3)) <<"M";
135        }
136
137        hits.subname(i, size_str.str());
138        hits.subdesc(i, "Hits in a " + size_str.str() +" cache");
139        misses.subname(i, size_str.str());
140        misses.subdesc(i, "Misses in a " + size_str.str() +" cache");
141    }
142}
143
144FALRUBlk *
145FALRU::hashLookup(Addr addr) const
146{
147    tagIterator iter = tagHash.find(addr);
148    if (iter != tagHash.end()) {
149        return (*iter).second;
150    }
151    return NULL;
152}
153
154void
155FALRU::invalidateBlk(FALRU::BlkType *blk)
156{
157    if (blk) {
158        blk->status = 0;
159        blk->isTouched = false;
160        tagsInUse--;
161    }
162}
163
164FALRUBlk*
165FALRU::accessBlock(Addr addr, int &lat, int context_src, int *inCache)
166{
167    accesses++;
168    int tmp_in_cache = 0;
169    Addr blkAddr = blkAlign(addr);
170    FALRUBlk* blk = hashLookup(blkAddr);
171
172    if (blk && blk->isValid()) {
173        assert(blk->tag == blkAddr);
174        tmp_in_cache = blk->inCache;
175        for (unsigned i = 0; i < numCaches; i++) {
176            if (1<<i & blk->inCache) {
177                hits[i]++;
178            } else {
179                misses[i]++;
180            }
181        }
182        hits[numCaches]++;
183        if (blk != head){
184            moveToHead(blk);
185        }
186    } else {
187        blk = NULL;
188        for (unsigned i = 0; i <= numCaches; ++i) {
189            misses[i]++;
190        }
191    }
192    if (inCache) {
193        *inCache = tmp_in_cache;
194    }
195
196    lat = hitLatency;
197    //assert(check());
198    return blk;
199}
200
201
202FALRUBlk*
203FALRU::findBlock(Addr addr) const
204{
205    Addr blkAddr = blkAlign(addr);
206    FALRUBlk* blk = hashLookup(blkAddr);
207
208    if (blk && blk->isValid()) {
209        assert(blk->tag == blkAddr);
210    } else {
211        blk = NULL;
212    }
213    return blk;
214}
215
216FALRUBlk*
217FALRU::findVictim(Addr addr, PacketList &writebacks)
218{
219    FALRUBlk * blk = tail;
220    assert(blk->inCache == 0);
221    moveToHead(blk);
222    tagHash.erase(blk->tag);
223    tagHash[blkAlign(addr)] = blk;
224    if (blk->isValid()) {
225        replacements[0]++;
226    } else {
227        tagsInUse++;
228        blk->isTouched = true;
229        if (!warmedUp && tagsInUse.value() >= warmupBound) {
230            warmedUp = true;
231            warmupCycle = curTick();
232        }
233    }
234    //assert(check());
235    return blk;
236}
237
238void
239FALRU::insertBlock(Addr addr, FALRU::BlkType *blk, int context_src)
240{
241}
242
243void
244FALRU::moveToHead(FALRUBlk *blk)
245{
246    int updateMask = blk->inCache ^ cacheMask;
247    for (unsigned i = 0; i < numCaches; i++){
248        if ((1<<i) & updateMask) {
249            cacheBoundaries[i]->inCache &= ~(1<<i);
250            cacheBoundaries[i] = cacheBoundaries[i]->prev;
251        } else if (cacheBoundaries[i] == blk) {
252            cacheBoundaries[i] = blk->prev;
253        }
254    }
255    blk->inCache = cacheMask;
256    if (blk != head) {
257        if (blk == tail){
258            assert(blk->next == NULL);
259            tail = blk->prev;
260            tail->next = NULL;
261        } else {
262            blk->prev->next = blk->next;
263            blk->next->prev = blk->prev;
264        }
265        blk->next = head;
266        blk->prev = NULL;
267        head->prev = blk;
268        head = blk;
269    }
270}
271
272bool
273FALRU::check()
274{
275    FALRUBlk* blk = head;
276    int size = 0;
277    int boundary = 1<<17;
278    int j = 0;
279    int flags = cacheMask;
280    while (blk) {
281        size += blkSize;
282        if (blk->inCache != flags) {
283            return false;
284        }
285        if (size == boundary && blk != tail) {
286            if (cacheBoundaries[j] != blk) {
287                return false;
288            }
289            flags &=~(1 << j);
290            boundary = boundary<<1;
291            ++j;
292        }
293        blk = blk->next;
294    }
295    return true;
296}
297
298void
299FALRU::clearLocks()
300{
301    for (int i = 0; i < numBlocks; i++){
302        blks[i].clearLoadLocks();
303    }
304}
305