2 * Copyright (c) 2004-2005 The Regents of The University of Michigan
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.
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.
33 * Definitions of LRU tag store for a partitioned cache.
38 #include "mem/cache/base_cache.hh"
39 #include "base/intmath.hh"
40 #include "mem/cache/tags/split_lru.hh"
41 #include "sim/root.hh"
46 SplitCacheSet::findBlk(Addr tag
) const
48 for (int i
= 0; i
< assoc
; ++i
) {
49 if (blks
[i
]->tag
== tag
&& blks
[i
]->isValid()) {
58 SplitCacheSet::moveToHead(SplitBlk
*blk
)
60 // nothing to do if blk is already head
64 // write 'next' block into blks[i], moving up from MRU toward LRU
65 // until we overwrite the block we moved to head.
67 // start by setting up to write 'blk' into blks[0]
73 // swap blks[i] and next
74 SplitBlk
*tmp
= blks
[i
];
78 } while (next
!= blk
);
82 // create and initialize a LRU/MRU cache structure
83 SplitLRU::SplitLRU(int _numSets
, int _blkSize
, int _assoc
, int _hit_latency
, int _part
) :
84 numSets(_numSets
), blkSize(_blkSize
), assoc(_assoc
), hitLatency(_hit_latency
), part(_part
)
87 if (blkSize
< 4 || !isPowerOf2(blkSize
)) {
88 fatal("Block size must be at least 4 and a power of 2");
90 if (numSets
<= 0 || !isPowerOf2(numSets
)) {
91 fatal("# of sets must be non-zero and a power of 2");
94 fatal("associativity must be greater than zero");
96 if (hitLatency
<= 0) {
97 fatal("access latency must be greater than zero");
103 blkMask
= blkSize
- 1;
104 setShift
= floorLog2(blkSize
);
105 setMask
= numSets
- 1;
106 tagShift
= setShift
+ floorLog2(numSets
);
108 /** @todo Make warmup percentage a parameter. */
109 warmupBound
= numSets
* assoc
;
111 sets
= new SplitCacheSet
[numSets
];
112 blks
= new SplitBlk
[numSets
* assoc
];
113 // allocate data storage in one big chunk
114 dataBlks
= new uint8_t[numSets
*assoc
*blkSize
];
116 blkIndex
= 0; // index into blks array
117 for (i
= 0; i
< numSets
; ++i
) {
118 sets
[i
].assoc
= assoc
;
120 sets
[i
].blks
= new SplitBlk
*[assoc
];
122 // link in the data blocks
123 for (j
= 0; j
< assoc
; ++j
) {
124 // locate next cache block
125 blk
= &blks
[blkIndex
];
126 blk
->data
= &dataBlks
[blkSize
*blkIndex
];
129 // invalidate new cache block
132 //EGH Fix Me : do we need to initialize blk?
134 // Setting the tag to j is just to prevent long chains in the hash
135 // table; won't matter because the block is invalid
138 blk
->isTouched
= false;
147 SplitLRU::~SplitLRU()
155 SplitLRU::regStats(const std::string
&name
)
157 BaseTags::regStats(name
);
160 .name(name
+ ".hits")
161 .desc("number of hits on this partition")
166 .name(name
+ ".misses")
167 .desc("number of misses in this partition")
172 // probe cache for presence of given block.
174 SplitLRU::probe(Addr addr
) const
176 // return(findBlock(Read, addr, asid) != 0);
177 Addr tag
= extractTag(addr
);
178 unsigned myset
= extractSet(addr
);
180 SplitBlk
*blk
= sets
[myset
].findBlk(tag
);
182 return (blk
!= NULL
); // true if in cache
186 SplitLRU::findBlock(Addr addr
, int &lat
)
188 Addr tag
= extractTag(addr
);
189 unsigned set
= extractSet(addr
);
190 SplitBlk
*blk
= sets
[set
].findBlk(tag
);
193 // move this block to head of the MRU list
194 sets
[set
].moveToHead(blk
);
195 if (blk
->whenReady
> curTick
&& blk
->whenReady
- curTick
> hitLatency
){
196 lat
= blk
->whenReady
- curTick
;
206 SplitLRU::findBlock(Packet
* &pkt
, int &lat
)
208 Addr addr
= pkt
->getAddr();
210 Addr tag
= extractTag(addr
);
211 unsigned set
= extractSet(addr
);
212 SplitBlk
*blk
= sets
[set
].findBlk(tag
);
215 // move this block to head of the MRU list
216 sets
[set
].moveToHead(blk
);
217 if (blk
->whenReady
> curTick
&& blk
->whenReady
- curTick
> hitLatency
){
218 lat
= blk
->whenReady
- curTick
;
228 SplitLRU::findBlock(Addr addr
) const
230 Addr tag
= extractTag(addr
);
231 unsigned set
= extractSet(addr
);
232 SplitBlk
*blk
= sets
[set
].findBlk(tag
);
237 SplitLRU::findReplacement(Packet
* &pkt
, PacketList
&writebacks
,
238 BlkList
&compress_blocks
)
240 unsigned set
= extractSet(pkt
->getAddr());
241 // grab a replacement candidate
242 SplitBlk
*blk
= sets
[set
].blks
[assoc
-1];
243 sets
[set
].moveToHead(blk
);
244 if (blk
->isValid()) {
246 totalRefs
+= blk
->refCount
;
249 } else if (!blk
->isTouched
) {
251 blk
->isTouched
= true;
252 if (!warmedUp
&& tagsInUse
.value() >= warmupBound
) {
254 warmupCycle
= curTick
;
264 SplitLRU::invalidateBlk(Addr addr
)
266 SplitBlk
*blk
= findBlock(addr
);
269 blk
->isTouched
= false;
275 SplitLRU::doCopy(Addr source
, Addr dest
, PacketList
&writebacks
)
277 //Copy not supported for now
279 assert(source
== blkAlign(source
));
280 assert(dest
== blkAlign(dest
));
281 SplitBlk
*source_blk
= findBlock(source
);
283 SplitBlk
*dest_blk
= findBlock(dest
);
284 if (dest_blk
== NULL
) {
285 // Need to do a replacement
286 Packet
* pkt
= new Packet();
289 dest_blk
= findReplacement(pkt
, writebacks
, dummy_list
);
290 if (dest_blk
->isValid() && dest_blk
->isModified()) {
291 // Need to writeback data.
292 pkt
= buildWritebackReq(regenerateBlkAddr(dest_blk
->tag
,
296 (cache
->doData())?dest_blk
->data
:0,
298 writebacks
.push_back(pkt
);
300 dest_blk
->tag
= extractTag(dest
);
302 * @todo Do we need to pass in the execution context, or can we
303 * assume its the same?
305 assert(source_blk
->xc
);
306 dest_blk
->xc
= source_blk
->xc
;
309 * @todo Can't assume the status once we have coherence on copies.
312 // Set this block as readable, writeable, and dirty.
313 dest_blk
->status
= 7;
314 if (cache
->doData()) {
315 memcpy(dest_blk
->data
, source_blk
->data
, blkSize
);
321 SplitLRU::cleanupRefs()
323 for (int i
= 0; i
< numSets
*assoc
; ++i
) {
324 if (blks
[i
].isValid()) {
325 totalRefs
+= blks
[i
].refCount
;