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 LIFO tag store usable in a partitioned cache.
38 #include "mem/cache/base_cache.hh"
39 #include "base/intmath.hh"
40 #include "mem/cache/tags/split_lifo.hh"
41 #include "sim/root.hh"
42 #include "base/trace.hh"
47 LIFOSet::findBlk(Addr tag
) const
49 for (SplitBlk
*blk
= firstIn
; blk
!= NULL
; blk
= blk
->next
) {
50 if (blk
->tag
== tag
&& blk
->isValid()) {
58 LIFOSet::moveToLastIn(SplitBlk
*blk
)
64 blk
->next
->prev
= NULL
;
66 blk
->prev
->next
= blk
->next
;
67 blk
->next
->prev
= blk
->prev
;
77 LIFOSet::moveToFirstIn(SplitBlk
*blk
)
83 blk
->prev
->next
= NULL
;
85 blk
->next
->prev
= blk
->prev
;
86 blk
->prev
->next
= blk
->next
;
96 // create and initialize a LIFO cache structure
97 SplitLIFO::SplitLIFO(int _blkSize
, int _size
, int _ways
, int _hit_latency
, bool two_Queue
, int _part
) :
98 blkSize(_blkSize
), size(_size
), numBlks(_size
/_blkSize
), numSets((_size
/_ways
)/_blkSize
), ways(_ways
),
99 hitLatency(_hit_latency
), twoQueue(two_Queue
), part(_part
)
101 if (!isPowerOf2(blkSize
))
102 fatal("cache block size (in bytes) must be a power of 2");
103 if (!(hitLatency
> 0))
104 fatal("access latency in cycles must be at least on cycle");
106 fatal("if instantiating a splitLIFO, needs non-zero size!");
112 setShift
= floorLog2(blkSize
);
113 blkMask
= blkSize
- 1;
114 setMask
= numSets
- 1;
115 tagShift
= setShift
+ floorLog2(numSets
);
118 /** @todo Make warmup percentage a parameter. */
119 warmupBound
= size
/blkSize
;
121 // allocate data blocks
122 blks
= new SplitBlk
[numBlks
];
123 sets
= new LIFOSet
[numSets
];
124 dataBlks
= new uint8_t[size
];
127 // these start off point to same blk
133 for (i
=0; i
< numSets
; ++i
) {
135 sets
[i
].lastIn
= &blks
[blkIndex
];
136 sets
[i
].firstIn
= &blks
[blkIndex
+ ways
- 1];
138 /* 3 cases: if there is 1 way, if there are 2 ways, or if there are 3+.
139 in the case of 1 way, last in and first out point to the same blocks,
140 and the next and prev pointers need to be assigned specially. and so on
142 /* deal with the first way */
143 blk
= &blks
[blkIndex
];
144 blk
->prev
= &blks
[blkIndex
+ 1];
146 blk
->data
= &dataBlks
[blkSize
*blkIndex
];
152 /* if there are "middle" ways, do them here */
154 for (j
=1; j
< ways
-1; ++j
) {
155 blk
= &blks
[blkIndex
];
156 blk
->data
= &dataBlks
[blkSize
*blkIndex
];
157 blk
->prev
= &blks
[blkIndex
+1];
158 blk
->next
= &blks
[blkIndex
-1];
159 blk
->data
= &(dataBlks
[blkSize
*blkIndex
]);
167 /* do the final way here, depending on whether the final way is the only
171 blk
= &blks
[blkIndex
];
173 blk
->next
= &blks
[blkIndex
- 1];
174 blk
->data
= &dataBlks
[blkSize
*blkIndex
];
183 assert(blkIndex
== numBlks
);
186 SplitLIFO::~SplitLIFO()
194 SplitLIFO::regStats(const std::string
&name
)
196 BaseTags::regStats(name
);
199 .name(name
+ ".hits")
200 .desc("number of hits on this partition")
205 .name(name
+ ".misses")
206 .desc("number of misses in this partition")
211 .name(name
+ ".invalidations")
212 .desc("number of invalidations in this partition")
217 // probe cache for presence of given block.
219 SplitLIFO::probe(Addr addr
) const
221 Addr tag
= extractTag(addr
);
222 unsigned myset
= extractSet(addr
);
224 SplitBlk
* blk
= sets
[myset
].findBlk(tag
);
225 return (blk
!= NULL
);
229 SplitLIFO::findBlock(Addr addr
, int &lat
)
231 Addr tag
= extractTag(addr
);
232 unsigned set
= extractSet(addr
);
233 SplitBlk
*blk
= sets
[set
].findBlk(tag
);
238 DPRINTF(Split
, "Found LIFO blk %#x in set %d, with tag %#x\n",
242 if (blk
->whenReady
> curTick
&& blk
->whenReady
- curTick
> hitLatency
)
243 lat
= blk
->whenReady
- curTick
;
248 sets
[set
].moveToFirstIn(blk
);
250 sets
[set
].moveToLastIn(blk
);
258 SplitLIFO::findBlock(Packet
* &pkt
, int &lat
)
260 Addr addr
= pkt
->getAddr();
262 Addr tag
= extractTag(addr
);
263 unsigned set
= extractSet(addr
);
264 SplitBlk
*blk
= sets
[set
].findBlk(tag
);
267 DPRINTF(Split
, "Found LIFO blk %#x in set %d, with tag %#x\n",
273 sets
[set
].moveToFirstIn(blk
);
275 sets
[set
].moveToLastIn(blk
);
284 SplitLIFO::findBlock(Addr addr
) const
286 Addr tag
= extractTag(addr
);
287 unsigned set
= extractSet(addr
);
288 SplitBlk
*blk
= sets
[set
].findBlk(tag
);
294 SplitLIFO::findReplacement(Packet
* &pkt
, PacketList
&writebacks
,
295 BlkList
&compress_blocks
)
297 unsigned set
= extractSet(pkt
->getAddr());
299 SplitBlk
*firstIn
= sets
[set
].firstIn
;
300 SplitBlk
*lastIn
= sets
[set
].lastIn
;
303 if (twoQueue
&& firstIn
->isUsed
) {
306 sets
[set
].moveToLastIn(blk
);
308 int withValue
= sets
[set
].withValue
;
309 if (withValue
== ways
) {
312 blk
= &(sets
[set
].firstIn
[ways
- ++withValue
]);
316 DPRINTF(Split
, "just assigned %#x addr into LIFO, replacing %#x status %#x\n",
317 pkt
->getAddr(), regenerateBlkAddr(blk
->tag
, set
), blk
->status
);
318 if (blk
->isValid()) {
320 totalRefs
+= blk
->refCount
;
325 blk
->isTouched
= true;
326 if (!warmedUp
&& tagsInUse
.value() >= warmupBound
) {
328 warmupCycle
= curTick
;
338 SplitLIFO::invalidateBlk(Addr addr
)
340 SplitBlk
*blk
= findBlock(addr
);
343 blk
->isTouched
= false;
350 SplitLIFO::doCopy(Addr source
, Addr dest
, PacketList
&writebacks
)
352 //Copy Unsuported for now
354 assert(source
== blkAlign(source
));
355 assert(dest
== blkAlign(dest
));
356 SplitBlk
*source_blk
= findBlock(source
);
358 SplitBlk
*dest_blk
= findBlock(dest
);
359 if (dest_blk
== NULL
) {
360 // Need to do a replacement
361 Packet
* pkt
= new Packet();
364 dest_blk
= findReplacement(pkt
, writebacks
, dummy_list
);
365 if (dest_blk
->isValid() && dest_blk
->isModified()) {
366 // Need to writeback data.
367 pkt
= buildWritebackReq(regenerateBlkAddr(dest_blk
->tag
,
371 (cache
->doData())?dest_blk
->data
:0,
373 writebacks
.push_back(pkt
);
375 dest_blk
->tag
= extractTag(dest
);
377 * @todo Do we need to pass in the execution context, or can we
378 * assume its the same?
380 assert(source_blk
->xc
);
381 dest_blk
->xc
= source_blk
->xc
;
384 * @todo Can't assume the status once we have coherence on copies.
387 // Set this block as readable, writeable, and dirty.
388 dest_blk
->status
= 7;
389 if (cache
->doData()) {
390 memcpy(dest_blk
->data
, source_blk
->data
, blkSize
);
396 SplitLIFO::cleanupRefs()
398 for (int i
= 0; i
< numBlks
; ++i
) {
399 if (blks
[i
].isValid()) {
400 totalRefs
+= blks
[i
].refCount
;