2 * Copyright (c) 1999-2012 Mark D. Hill and David A. Wood
3 * Copyright (c) 2013 Advanced Micro Devices, Inc.
6 * Redistribution and use in source and binary forms, with or without
7 * modification, are permitted provided that the following conditions are
8 * met: redistributions of source code must retain the above copyright
9 * notice, this list of conditions and the following disclaimer;
10 * redistributions in binary form must reproduce the above copyright
11 * notice, this list of conditions and the following disclaimer in the
12 * documentation and/or other materials provided with the distribution;
13 * neither the name of the copyright holders nor the names of its
14 * contributors may be used to endorse or promote products derived from
15 * this software without specific prior written permission.
17 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
18 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
19 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
20 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
21 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
22 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
23 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
24 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
25 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
26 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
27 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
30 #include "mem/ruby/structures/CacheMemory.hh"
32 #include "base/intmath.hh"
33 #include "base/logging.hh"
34 #include "debug/RubyCache.hh"
35 #include "debug/RubyCacheTrace.hh"
36 #include "debug/RubyResourceStalls.hh"
37 #include "debug/RubyStats.hh"
38 #include "mem/cache/replacement_policies/weighted_lru_rp.hh"
39 #include "mem/ruby/protocol/AccessPermission.hh"
40 #include "mem/ruby/system/RubySystem.hh"
45 operator<<(ostream
& out
, const CacheMemory
& obj
)
53 RubyCacheParams::create()
55 return new CacheMemory(this);
58 CacheMemory::CacheMemory(const Params
*p
)
60 dataArray(p
->dataArrayBanks
, p
->dataAccessLatency
,
61 p
->start_index_bit
, p
->ruby_system
),
62 tagArray(p
->tagArrayBanks
, p
->tagAccessLatency
,
63 p
->start_index_bit
, p
->ruby_system
)
65 m_cache_size
= p
->size
;
66 m_cache_assoc
= p
->assoc
;
67 m_replacementPolicy_ptr
= p
->replacement_policy
;
68 m_start_index_bit
= p
->start_index_bit
;
69 m_is_instruction_only_cache
= p
->is_icache
;
70 m_resource_stalls
= p
->resourceStalls
;
71 m_block_size
= p
->block_size
; // may be 0 at this point. Updated in init()
72 m_use_occupancy
= dynamic_cast<WeightedLRUPolicy
*>(
73 m_replacementPolicy_ptr
) ? true : false;
79 if (m_block_size
== 0) {
80 m_block_size
= RubySystem::getBlockSizeBytes();
82 m_cache_num_sets
= (m_cache_size
/ m_cache_assoc
) / m_block_size
;
83 assert(m_cache_num_sets
> 1);
84 m_cache_num_set_bits
= floorLog2(m_cache_num_sets
);
85 assert(m_cache_num_set_bits
> 0);
87 m_cache
.resize(m_cache_num_sets
,
88 std::vector
<AbstractCacheEntry
*>(m_cache_assoc
, nullptr));
89 replacement_data
.resize(m_cache_num_sets
,
90 std::vector
<ReplData
>(m_cache_assoc
, nullptr));
91 // instantiate all the replacement_data here
92 for (int i
= 0; i
< m_cache_num_sets
; i
++) {
93 for ( int j
= 0; j
< m_cache_assoc
; j
++) {
94 replacement_data
[i
][j
] =
95 m_replacementPolicy_ptr
->instantiateEntry();
100 CacheMemory::~CacheMemory()
102 if (m_replacementPolicy_ptr
)
103 delete m_replacementPolicy_ptr
;
104 for (int i
= 0; i
< m_cache_num_sets
; i
++) {
105 for (int j
= 0; j
< m_cache_assoc
; j
++) {
106 delete m_cache
[i
][j
];
111 // convert a Address to its location in the cache
113 CacheMemory::addressToCacheSet(Addr address
) const
115 assert(address
== makeLineAddress(address
));
116 return bitSelect(address
, m_start_index_bit
,
117 m_start_index_bit
+ m_cache_num_set_bits
- 1);
120 // Given a cache index: returns the index of the tag in a set.
121 // returns -1 if the tag is not found.
123 CacheMemory::findTagInSet(int64_t cacheSet
, Addr tag
) const
125 assert(tag
== makeLineAddress(tag
));
126 // search the set for the tags
127 auto it
= m_tag_index
.find(tag
);
128 if (it
!= m_tag_index
.end())
129 if (m_cache
[cacheSet
][it
->second
]->m_Permission
!=
130 AccessPermission_NotPresent
)
132 return -1; // Not found
135 // Given a cache index: returns the index of the tag in a set.
136 // returns -1 if the tag is not found.
138 CacheMemory::findTagInSetIgnorePermissions(int64_t cacheSet
,
141 assert(tag
== makeLineAddress(tag
));
142 // search the set for the tags
143 auto it
= m_tag_index
.find(tag
);
144 if (it
!= m_tag_index
.end())
146 return -1; // Not found
149 // Given an unique cache block identifier (idx): return the valid address
150 // stored by the cache block. If the block is invalid/notpresent, the
151 // function returns the 0 address
153 CacheMemory::getAddressAtIdx(int idx
) const
157 int set
= idx
/ m_cache_assoc
;
158 assert(set
< m_cache_num_sets
);
160 int way
= idx
- set
* m_cache_assoc
;
161 assert (way
< m_cache_assoc
);
163 AbstractCacheEntry
* entry
= m_cache
[set
][way
];
165 entry
->m_Permission
== AccessPermission_Invalid
||
166 entry
->m_Permission
== AccessPermission_NotPresent
) {
169 return entry
->m_Address
;
173 CacheMemory::tryCacheAccess(Addr address
, RubyRequestType type
,
174 DataBlock
*& data_ptr
)
176 assert(address
== makeLineAddress(address
));
177 DPRINTF(RubyCache
, "address: %#x\n", address
);
178 int64_t cacheSet
= addressToCacheSet(address
);
179 int loc
= findTagInSet(cacheSet
, address
);
181 // Do we even have a tag match?
182 AbstractCacheEntry
* entry
= m_cache
[cacheSet
][loc
];
183 m_replacementPolicy_ptr
->touch(entry
->replacementData
);
184 m_cache
[cacheSet
][loc
]->setLastAccess(curTick());
185 data_ptr
= &(entry
->getDataBlk());
187 if (entry
->m_Permission
== AccessPermission_Read_Write
) {
190 if ((entry
->m_Permission
== AccessPermission_Read_Only
) &&
191 (type
== RubyRequestType_LD
|| type
== RubyRequestType_IFETCH
)) {
194 // The line must not be accessible
201 CacheMemory::testCacheAccess(Addr address
, RubyRequestType type
,
202 DataBlock
*& data_ptr
)
204 assert(address
== makeLineAddress(address
));
205 DPRINTF(RubyCache
, "address: %#x\n", address
);
206 int64_t cacheSet
= addressToCacheSet(address
);
207 int loc
= findTagInSet(cacheSet
, address
);
210 // Do we even have a tag match?
211 AbstractCacheEntry
* entry
= m_cache
[cacheSet
][loc
];
212 m_replacementPolicy_ptr
->touch(entry
->replacementData
);
213 m_cache
[cacheSet
][loc
]->setLastAccess(curTick());
214 data_ptr
= &(entry
->getDataBlk());
216 return m_cache
[cacheSet
][loc
]->m_Permission
!=
217 AccessPermission_NotPresent
;
224 // tests to see if an address is present in the cache
226 CacheMemory::isTagPresent(Addr address
) const
228 assert(address
== makeLineAddress(address
));
229 int64_t cacheSet
= addressToCacheSet(address
);
230 int loc
= findTagInSet(cacheSet
, address
);
233 // We didn't find the tag
234 DPRINTF(RubyCache
, "No tag match for address: %#x\n", address
);
237 DPRINTF(RubyCache
, "address: %#x found\n", address
);
241 // Returns true if there is:
242 // a) a tag match on this address or there is
243 // b) an unused line in the same cache "way"
245 CacheMemory::cacheAvail(Addr address
) const
247 assert(address
== makeLineAddress(address
));
249 int64_t cacheSet
= addressToCacheSet(address
);
251 for (int i
= 0; i
< m_cache_assoc
; i
++) {
252 AbstractCacheEntry
* entry
= m_cache
[cacheSet
][i
];
254 if (entry
->m_Address
== address
||
255 entry
->m_Permission
== AccessPermission_NotPresent
) {
256 // Already in the cache or we found an empty entry
267 CacheMemory::allocate(Addr address
, AbstractCacheEntry
*entry
)
269 assert(address
== makeLineAddress(address
));
270 assert(!isTagPresent(address
));
271 assert(cacheAvail(address
));
272 DPRINTF(RubyCache
, "address: %#x\n", address
);
274 // Find the first open slot
275 int64_t cacheSet
= addressToCacheSet(address
);
276 std::vector
<AbstractCacheEntry
*> &set
= m_cache
[cacheSet
];
277 for (int i
= 0; i
< m_cache_assoc
; i
++) {
278 if (!set
[i
] || set
[i
]->m_Permission
== AccessPermission_NotPresent
) {
279 if (set
[i
] && (set
[i
] != entry
)) {
280 warn_once("This protocol contains a cache entry handling bug: "
281 "Entries in the cache should never be NotPresent! If\n"
282 "this entry (%#x) is not tracked elsewhere, it will memory "
283 "leak here. Fix your protocol to eliminate these!",
286 set
[i
] = entry
; // Init entry
287 set
[i
]->m_Address
= address
;
288 set
[i
]->m_Permission
= AccessPermission_Invalid
;
289 DPRINTF(RubyCache
, "Allocate clearing lock for addr: %x\n",
291 set
[i
]->m_locked
= -1;
292 m_tag_index
[address
] = i
;
293 set
[i
]->setPosition(cacheSet
, i
);
294 set
[i
]->replacementData
= replacement_data
[cacheSet
][i
];
295 set
[i
]->setLastAccess(curTick());
297 // Call reset function here to set initial value for different
298 // replacement policies.
299 m_replacementPolicy_ptr
->reset(entry
->replacementData
);
304 panic("Allocate didn't find an available entry");
308 CacheMemory::deallocate(Addr address
)
310 DPRINTF(RubyCache
, "address: %#x\n", address
);
311 AbstractCacheEntry
* entry
= lookup(address
);
312 assert(entry
!= nullptr);
313 m_replacementPolicy_ptr
->invalidate(entry
->replacementData
);
314 uint32_t cache_set
= entry
->getSet();
315 uint32_t way
= entry
->getWay();
317 m_cache
[cache_set
][way
] = NULL
;
318 m_tag_index
.erase(address
);
321 // Returns with the physical address of the conflicting cache line
323 CacheMemory::cacheProbe(Addr address
) const
325 assert(address
== makeLineAddress(address
));
326 assert(!cacheAvail(address
));
328 int64_t cacheSet
= addressToCacheSet(address
);
329 std::vector
<ReplaceableEntry
*> candidates
;
330 for (int i
= 0; i
< m_cache_assoc
; i
++) {
331 candidates
.push_back(static_cast<ReplaceableEntry
*>(
332 m_cache
[cacheSet
][i
]));
334 return m_cache
[cacheSet
][m_replacementPolicy_ptr
->
335 getVictim(candidates
)->getWay()]->m_Address
;
338 // looks an address up in the cache
340 CacheMemory::lookup(Addr address
)
342 assert(address
== makeLineAddress(address
));
343 int64_t cacheSet
= addressToCacheSet(address
);
344 int loc
= findTagInSet(cacheSet
, address
);
345 if (loc
== -1) return NULL
;
346 return m_cache
[cacheSet
][loc
];
349 // looks an address up in the cache
350 const AbstractCacheEntry
*
351 CacheMemory::lookup(Addr address
) const
353 assert(address
== makeLineAddress(address
));
354 int64_t cacheSet
= addressToCacheSet(address
);
355 int loc
= findTagInSet(cacheSet
, address
);
356 if (loc
== -1) return NULL
;
357 return m_cache
[cacheSet
][loc
];
360 // Sets the most recently used bit for a cache block
362 CacheMemory::setMRU(Addr address
)
364 AbstractCacheEntry
* entry
= lookup(makeLineAddress(address
));
365 if (entry
!= nullptr) {
366 m_replacementPolicy_ptr
->touch(entry
->replacementData
);
367 entry
->setLastAccess(curTick());
372 CacheMemory::setMRU(AbstractCacheEntry
*entry
)
374 assert(entry
!= nullptr);
375 m_replacementPolicy_ptr
->touch(entry
->replacementData
);
376 entry
->setLastAccess(curTick());
380 CacheMemory::setMRU(Addr address
, int occupancy
)
382 AbstractCacheEntry
* entry
= lookup(makeLineAddress(address
));
383 if (entry
!= nullptr) {
384 // m_use_occupancy can decide whether we are using WeightedLRU
385 // replacement policy. Depending on different replacement policies,
386 // use different touch() function.
387 if (m_use_occupancy
) {
388 static_cast<WeightedLRUPolicy
*>(m_replacementPolicy_ptr
)->touch(
389 entry
->replacementData
, occupancy
);
391 m_replacementPolicy_ptr
->touch(entry
->replacementData
);
393 entry
->setLastAccess(curTick());
398 CacheMemory::getReplacementWeight(int64_t set
, int64_t loc
)
400 assert(set
< m_cache_num_sets
);
401 assert(loc
< m_cache_assoc
);
403 if (m_cache
[set
][loc
] != NULL
) {
404 ret
= m_cache
[set
][loc
]->getNumValidBlocks();
412 CacheMemory::recordCacheContents(int cntrl
, CacheRecorder
* tr
) const
414 uint64_t warmedUpBlocks
= 0;
415 uint64_t totalBlocks M5_VAR_USED
= (uint64_t)m_cache_num_sets
*
416 (uint64_t)m_cache_assoc
;
418 for (int i
= 0; i
< m_cache_num_sets
; i
++) {
419 for (int j
= 0; j
< m_cache_assoc
; j
++) {
420 if (m_cache
[i
][j
] != NULL
) {
421 AccessPermission perm
= m_cache
[i
][j
]->m_Permission
;
422 RubyRequestType request_type
= RubyRequestType_NULL
;
423 if (perm
== AccessPermission_Read_Only
) {
424 if (m_is_instruction_only_cache
) {
425 request_type
= RubyRequestType_IFETCH
;
427 request_type
= RubyRequestType_LD
;
429 } else if (perm
== AccessPermission_Read_Write
) {
430 request_type
= RubyRequestType_ST
;
433 if (request_type
!= RubyRequestType_NULL
) {
435 lastAccessTick
= m_cache
[i
][j
]->getLastAccess();
436 tr
->addRecord(cntrl
, m_cache
[i
][j
]->m_Address
,
437 0, request_type
, lastAccessTick
,
438 m_cache
[i
][j
]->getDataBlk());
445 DPRINTF(RubyCacheTrace
, "%s: %lli blocks of %lli total blocks"
446 "recorded %.2f%% \n", name().c_str(), warmedUpBlocks
,
447 totalBlocks
, (float(warmedUpBlocks
) / float(totalBlocks
)) * 100.0);
451 CacheMemory::print(ostream
& out
) const
453 out
<< "Cache dump: " << name() << endl
;
454 for (int i
= 0; i
< m_cache_num_sets
; i
++) {
455 for (int j
= 0; j
< m_cache_assoc
; j
++) {
456 if (m_cache
[i
][j
] != NULL
) {
457 out
<< " Index: " << i
459 << " entry: " << *m_cache
[i
][j
] << endl
;
461 out
<< " Index: " << i
463 << " entry: NULL" << endl
;
470 CacheMemory::printData(ostream
& out
) const
472 out
<< "printData() not supported" << endl
;
476 CacheMemory::setLocked(Addr address
, int context
)
478 DPRINTF(RubyCache
, "Setting Lock for addr: %#x to %d\n", address
, context
);
479 assert(address
== makeLineAddress(address
));
480 int64_t cacheSet
= addressToCacheSet(address
);
481 int loc
= findTagInSet(cacheSet
, address
);
483 m_cache
[cacheSet
][loc
]->setLocked(context
);
487 CacheMemory::clearLocked(Addr address
)
489 DPRINTF(RubyCache
, "Clear Lock for addr: %#x\n", address
);
490 assert(address
== makeLineAddress(address
));
491 int64_t cacheSet
= addressToCacheSet(address
);
492 int loc
= findTagInSet(cacheSet
, address
);
494 m_cache
[cacheSet
][loc
]->clearLocked();
498 CacheMemory::isLocked(Addr address
, int context
)
500 assert(address
== makeLineAddress(address
));
501 int64_t cacheSet
= addressToCacheSet(address
);
502 int loc
= findTagInSet(cacheSet
, address
);
504 DPRINTF(RubyCache
, "Testing Lock for addr: %#llx cur %d con %d\n",
505 address
, m_cache
[cacheSet
][loc
]->m_locked
, context
);
506 return m_cache
[cacheSet
][loc
]->isLocked(context
);
510 CacheMemory::regStats()
512 SimObject::regStats();
515 .name(name() + ".demand_hits")
516 .desc("Number of cache demand hits")
520 .name(name() + ".demand_misses")
521 .desc("Number of cache demand misses")
525 .name(name() + ".demand_accesses")
526 .desc("Number of cache demand accesses")
529 m_demand_accesses
= m_demand_hits
+ m_demand_misses
;
532 .name(name() + ".total_sw_prefetches")
533 .desc("Number of software prefetches")
534 .flags(Stats::nozero
)
538 .name(name() + ".total_hw_prefetches")
539 .desc("Number of hardware prefetches")
540 .flags(Stats::nozero
)
544 .name(name() + ".total_prefetches")
545 .desc("Number of prefetches")
546 .flags(Stats::nozero
)
549 m_prefetches
= m_sw_prefetches
+ m_hw_prefetches
;
552 .init(RubyRequestType_NUM
)
553 .name(name() + ".access_mode")
554 .flags(Stats::pdf
| Stats::total
)
556 for (int i
= 0; i
< RubyAccessMode_NUM
; i
++) {
558 .subname(i
, RubyAccessMode_to_string(RubyAccessMode(i
)))
559 .flags(Stats::nozero
)
564 .name(name() + ".num_data_array_reads")
565 .desc("number of data array reads")
566 .flags(Stats::nozero
)
570 .name(name() + ".num_data_array_writes")
571 .desc("number of data array writes")
572 .flags(Stats::nozero
)
576 .name(name() + ".num_tag_array_reads")
577 .desc("number of tag array reads")
578 .flags(Stats::nozero
)
582 .name(name() + ".num_tag_array_writes")
583 .desc("number of tag array writes")
584 .flags(Stats::nozero
)
588 .name(name() + ".num_tag_array_stalls")
589 .desc("number of stalls caused by tag array")
590 .flags(Stats::nozero
)
594 .name(name() + ".num_data_array_stalls")
595 .desc("number of stalls caused by data array")
596 .flags(Stats::nozero
)
600 // assumption: SLICC generated files will only call this function
601 // once **all** resources are granted
603 CacheMemory::recordRequestType(CacheRequestType requestType
, Addr addr
)
605 DPRINTF(RubyStats
, "Recorded statistic: %s\n",
606 CacheRequestType_to_string(requestType
));
607 switch(requestType
) {
608 case CacheRequestType_DataArrayRead
:
609 if (m_resource_stalls
)
610 dataArray
.reserve(addressToCacheSet(addr
));
613 case CacheRequestType_DataArrayWrite
:
614 if (m_resource_stalls
)
615 dataArray
.reserve(addressToCacheSet(addr
));
616 numDataArrayWrites
++;
618 case CacheRequestType_TagArrayRead
:
619 if (m_resource_stalls
)
620 tagArray
.reserve(addressToCacheSet(addr
));
623 case CacheRequestType_TagArrayWrite
:
624 if (m_resource_stalls
)
625 tagArray
.reserve(addressToCacheSet(addr
));
629 warn("CacheMemory access_type not found: %s",
630 CacheRequestType_to_string(requestType
));
635 CacheMemory::checkResourceAvailable(CacheResourceType res
, Addr addr
)
637 if (!m_resource_stalls
) {
641 if (res
== CacheResourceType_TagArray
) {
642 if (tagArray
.tryAccess(addressToCacheSet(addr
))) return true;
644 DPRINTF(RubyResourceStalls
,
645 "Tag array stall on addr %#x in set %d\n",
646 addr
, addressToCacheSet(addr
));
650 } else if (res
== CacheResourceType_DataArray
) {
651 if (dataArray
.tryAccess(addressToCacheSet(addr
))) return true;
653 DPRINTF(RubyResourceStalls
,
654 "Data array stall on addr %#x in set %d\n",
655 addr
, addressToCacheSet(addr
));
656 numDataArrayStalls
++;
660 panic("Unrecognized cache resource type.");
665 CacheMemory::isBlockInvalid(int64_t cache_set
, int64_t loc
)
667 return (m_cache
[cache_set
][loc
]->m_Permission
== AccessPermission_Invalid
);
671 CacheMemory::isBlockNotBusy(int64_t cache_set
, int64_t loc
)
673 return (m_cache
[cache_set
][loc
]->m_Permission
!= AccessPermission_Busy
);