1/*
2 * Copyright (c) 1999-2012 Mark D. Hill and David A. Wood
3 * Copyright (c) 2013 Advanced Micro Devices, Inc.
4 * All rights reserved.
5 *
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.
16 *
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.
28 */
29
30#include "mem/ruby/structures/CacheMemory.hh"
31
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/ruby/protocol/AccessPermission.hh"
39#include "mem/ruby/system/RubySystem.hh"
40#include "mem/ruby/system/WeightedLRUPolicy.hh"
41
42using namespace std;
43
44ostream&
45operator<<(ostream& out, const CacheMemory& obj)
46{
47    obj.print(out);
48    out << flush;
49    return out;
50}
51
52CacheMemory *
53RubyCacheParams::create()
54{
55    return new CacheMemory(this);
56}
57
58CacheMemory::CacheMemory(const Params *p)
59    : SimObject(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)
64{
65    m_cache_size = p->size;
66    m_cache_assoc = p->assoc;
67    m_replacementPolicy_ptr = p->replacement_policy;
68    m_replacementPolicy_ptr->setCache(this);
69    m_start_index_bit = p->start_index_bit;
70    m_is_instruction_only_cache = p->is_icache;
71    m_resource_stalls = p->resourceStalls;
72    m_block_size = p->block_size;  // may be 0 at this point. Updated in init()
73}
74
75void
76CacheMemory::init()
77{
78    if (m_block_size == 0) {
79        m_block_size = RubySystem::getBlockSizeBytes();
80    }
81    m_cache_num_sets = (m_cache_size / m_cache_assoc) / m_block_size;
82    assert(m_cache_num_sets > 1);
83    m_cache_num_set_bits = floorLog2(m_cache_num_sets);
84    assert(m_cache_num_set_bits > 0);
85
86    m_cache.resize(m_cache_num_sets,
87                    std::vector<AbstractCacheEntry*>(m_cache_assoc, nullptr));
88}
89
90CacheMemory::~CacheMemory()
91{
92    if (m_replacementPolicy_ptr)
93        delete m_replacementPolicy_ptr;
94    for (int i = 0; i < m_cache_num_sets; i++) {
95        for (int j = 0; j < m_cache_assoc; j++) {
96            delete m_cache[i][j];
97        }
98    }
99}
100
101// convert a Address to its location in the cache
102int64_t
103CacheMemory::addressToCacheSet(Addr address) const
104{
105    assert(address == makeLineAddress(address));
106    return bitSelect(address, m_start_index_bit,
107                     m_start_index_bit + m_cache_num_set_bits - 1);
108}
109
110// Given a cache index: returns the index of the tag in a set.
111// returns -1 if the tag is not found.
112int
113CacheMemory::findTagInSet(int64_t cacheSet, Addr tag) const
114{
115    assert(tag == makeLineAddress(tag));
116    // search the set for the tags
117    auto it = m_tag_index.find(tag);
118    if (it != m_tag_index.end())
119        if (m_cache[cacheSet][it->second]->m_Permission !=
120            AccessPermission_NotPresent)
121            return it->second;
122    return -1; // Not found
123}
124
125// Given a cache index: returns the index of the tag in a set.
126// returns -1 if the tag is not found.
127int
128CacheMemory::findTagInSetIgnorePermissions(int64_t cacheSet,
129                                           Addr tag) const
130{
131    assert(tag == makeLineAddress(tag));
132    // search the set for the tags
133    auto it = m_tag_index.find(tag);
134    if (it != m_tag_index.end())
135        return it->second;
136    return -1; // Not found
137}
138
139// Given an unique cache block identifier (idx): return the valid address
140// stored by the cache block.  If the block is invalid/notpresent, the
141// function returns the 0 address
142Addr
143CacheMemory::getAddressAtIdx(int idx) const
144{
145    Addr tmp(0);
146
147    int set = idx / m_cache_assoc;
148    assert(set < m_cache_num_sets);
149
150    int way = idx - set * m_cache_assoc;
151    assert (way < m_cache_assoc);
152
153    AbstractCacheEntry* entry = m_cache[set][way];
154    if (entry == NULL ||
155        entry->m_Permission == AccessPermission_Invalid ||
156        entry->m_Permission == AccessPermission_NotPresent) {
157        return tmp;
158    }
159    return entry->m_Address;
160}
161
162bool
163CacheMemory::tryCacheAccess(Addr address, RubyRequestType type,
164                            DataBlock*& data_ptr)
165{
166    assert(address == makeLineAddress(address));
167    DPRINTF(RubyCache, "address: %#x\n", address);
168    int64_t cacheSet = addressToCacheSet(address);
169    int loc = findTagInSet(cacheSet, address);
170    if (loc != -1) {
171        // Do we even have a tag match?
172        AbstractCacheEntry* entry = m_cache[cacheSet][loc];
173        m_replacementPolicy_ptr->touch(cacheSet, loc, curTick());
174        data_ptr = &(entry->getDataBlk());
175
176        if (entry->m_Permission == AccessPermission_Read_Write) {
177            return true;
178        }
179        if ((entry->m_Permission == AccessPermission_Read_Only) &&
180            (type == RubyRequestType_LD || type == RubyRequestType_IFETCH)) {
181            return true;
182        }
183        // The line must not be accessible
184    }
185    data_ptr = NULL;
186    return false;
187}
188
189bool
190CacheMemory::testCacheAccess(Addr address, RubyRequestType type,
191                             DataBlock*& data_ptr)
192{
193    assert(address == makeLineAddress(address));
194    DPRINTF(RubyCache, "address: %#x\n", address);
195    int64_t cacheSet = addressToCacheSet(address);
196    int loc = findTagInSet(cacheSet, address);
197
198    if (loc != -1) {
199        // Do we even have a tag match?
200        AbstractCacheEntry* entry = m_cache[cacheSet][loc];
201        m_replacementPolicy_ptr->touch(cacheSet, loc, curTick());
202        data_ptr = &(entry->getDataBlk());
203
204        return m_cache[cacheSet][loc]->m_Permission !=
205            AccessPermission_NotPresent;
206    }
207
208    data_ptr = NULL;
209    return false;
210}
211
212// tests to see if an address is present in the cache
213bool
214CacheMemory::isTagPresent(Addr address) const
215{
216    assert(address == makeLineAddress(address));
217    int64_t cacheSet = addressToCacheSet(address);
218    int loc = findTagInSet(cacheSet, address);
219
220    if (loc == -1) {
221        // We didn't find the tag
222        DPRINTF(RubyCache, "No tag match for address: %#x\n", address);
223        return false;
224    }
225    DPRINTF(RubyCache, "address: %#x found\n", address);
226    return true;
227}
228
229// Returns true if there is:
230//   a) a tag match on this address or there is
231//   b) an unused line in the same cache "way"
232bool
233CacheMemory::cacheAvail(Addr address) const
234{
235    assert(address == makeLineAddress(address));
236
237    int64_t cacheSet = addressToCacheSet(address);
238
239    for (int i = 0; i < m_cache_assoc; i++) {
240        AbstractCacheEntry* entry = m_cache[cacheSet][i];
241        if (entry != NULL) {
242            if (entry->m_Address == address ||
243                entry->m_Permission == AccessPermission_NotPresent) {
244                // Already in the cache or we found an empty entry
245                return true;
246            }
247        } else {
248            return true;
249        }
250    }
251    return false;
252}
253
254AbstractCacheEntry*
255CacheMemory::allocate(Addr address, AbstractCacheEntry *entry, bool touch)
256{
257    assert(address == makeLineAddress(address));
258    assert(!isTagPresent(address));
259    assert(cacheAvail(address));
260    DPRINTF(RubyCache, "address: %#x\n", address);
261
262    // Find the first open slot
263    int64_t cacheSet = addressToCacheSet(address);
264    std::vector<AbstractCacheEntry*> &set = m_cache[cacheSet];
265    for (int i = 0; i < m_cache_assoc; i++) {
266        if (!set[i] || set[i]->m_Permission == AccessPermission_NotPresent) {
267            if (set[i] && (set[i] != entry)) {
268                warn_once("This protocol contains a cache entry handling bug: "
269                    "Entries in the cache should never be NotPresent! If\n"
270                    "this entry (%#x) is not tracked elsewhere, it will memory "
271                    "leak here. Fix your protocol to eliminate these!",
272                    address);
273            }
274            set[i] = entry;  // Init entry
275            set[i]->m_Address = address;
276            set[i]->m_Permission = AccessPermission_Invalid;
277            DPRINTF(RubyCache, "Allocate clearing lock for addr: %x\n",
278                    address);
279            set[i]->m_locked = -1;
280            m_tag_index[address] = i;
281            entry->setSetIndex(cacheSet);
282            entry->setWayIndex(i);
283
284            if (touch) {
285                m_replacementPolicy_ptr->touch(cacheSet, i, curTick());
286            }
287
288            return entry;
289        }
290    }
291    panic("Allocate didn't find an available entry");
292}
293
294void
295CacheMemory::deallocate(Addr address)
296{
297    assert(address == makeLineAddress(address));
298    assert(isTagPresent(address));
299    DPRINTF(RubyCache, "address: %#x\n", address);
300    int64_t cacheSet = addressToCacheSet(address);
301    int loc = findTagInSet(cacheSet, address);
302    if (loc != -1) {
303        delete m_cache[cacheSet][loc];
304        m_cache[cacheSet][loc] = NULL;
305        m_tag_index.erase(address);
306    }
307}
308
309// Returns with the physical address of the conflicting cache line
310Addr
311CacheMemory::cacheProbe(Addr address) const
312{
313    assert(address == makeLineAddress(address));
314    assert(!cacheAvail(address));
315
316    int64_t cacheSet = addressToCacheSet(address);
317    return m_cache[cacheSet][m_replacementPolicy_ptr->getVictim(cacheSet)]->
318        m_Address;
319}
320
321// looks an address up in the cache
322AbstractCacheEntry*
323CacheMemory::lookup(Addr address)
324{
325    assert(address == makeLineAddress(address));
326    int64_t cacheSet = addressToCacheSet(address);
327    int loc = findTagInSet(cacheSet, address);
328    if (loc == -1) return NULL;
329    return m_cache[cacheSet][loc];
330}
331
332// looks an address up in the cache
333const AbstractCacheEntry*
334CacheMemory::lookup(Addr address) const
335{
336    assert(address == makeLineAddress(address));
337    int64_t cacheSet = addressToCacheSet(address);
338    int loc = findTagInSet(cacheSet, address);
339    if (loc == -1) return NULL;
340    return m_cache[cacheSet][loc];
341}
342
343// Sets the most recently used bit for a cache block
344void
345CacheMemory::setMRU(Addr address)
346{
347    int64_t cacheSet = addressToCacheSet(address);
348    int loc = findTagInSet(cacheSet, address);
349
350    if (loc != -1)
351        m_replacementPolicy_ptr->touch(cacheSet, loc, curTick());
352}
353
354void
355CacheMemory::setMRU(const AbstractCacheEntry *e)
356{
357    uint32_t cacheSet = e->getSetIndex();
358    uint32_t loc = e->getWayIndex();
359    m_replacementPolicy_ptr->touch(cacheSet, loc, curTick());
360}
361
362void
363CacheMemory::setMRU(Addr address, int occupancy)
364{
365    int64_t cacheSet = addressToCacheSet(address);
366    int loc = findTagInSet(cacheSet, address);
367
368    if (loc != -1) {
369        if (m_replacementPolicy_ptr->useOccupancy()) {
370            (static_cast<WeightedLRUPolicy*>(m_replacementPolicy_ptr))->
371                touch(cacheSet, loc, curTick(), occupancy);
372        } else {
373            m_replacementPolicy_ptr->
374                touch(cacheSet, loc, curTick());
375        }
376    }
377}
378
379int
380CacheMemory::getReplacementWeight(int64_t set, int64_t loc)
381{
382    assert(set < m_cache_num_sets);
383    assert(loc < m_cache_assoc);
384    int ret = 0;
385    if (m_cache[set][loc] != NULL) {
386        ret = m_cache[set][loc]->getNumValidBlocks();
387        assert(ret >= 0);
388    }
389
390    return ret;
391}
392
393void
394CacheMemory::recordCacheContents(int cntrl, CacheRecorder* tr) const
395{
396    uint64_t warmedUpBlocks = 0;
397    uint64_t totalBlocks M5_VAR_USED = (uint64_t)m_cache_num_sets *
398                                       (uint64_t)m_cache_assoc;
399
400    for (int i = 0; i < m_cache_num_sets; i++) {
401        for (int j = 0; j < m_cache_assoc; j++) {
402            if (m_cache[i][j] != NULL) {
403                AccessPermission perm = m_cache[i][j]->m_Permission;
404                RubyRequestType request_type = RubyRequestType_NULL;
405                if (perm == AccessPermission_Read_Only) {
406                    if (m_is_instruction_only_cache) {
407                        request_type = RubyRequestType_IFETCH;
408                    } else {
409                        request_type = RubyRequestType_LD;
410                    }
411                } else if (perm == AccessPermission_Read_Write) {
412                    request_type = RubyRequestType_ST;
413                }
414
415                if (request_type != RubyRequestType_NULL) {
416                    tr->addRecord(cntrl, m_cache[i][j]->m_Address,
417                                  0, request_type,
418                                  m_replacementPolicy_ptr->getLastAccess(i, j),
419                                  m_cache[i][j]->getDataBlk());
420                    warmedUpBlocks++;
421                }
422            }
423        }
424    }
425
426    DPRINTF(RubyCacheTrace, "%s: %lli blocks of %lli total blocks"
427            "recorded %.2f%% \n", name().c_str(), warmedUpBlocks,
428            totalBlocks, (float(warmedUpBlocks) / float(totalBlocks)) * 100.0);
429}
430
431void
432CacheMemory::print(ostream& out) const
433{
434    out << "Cache dump: " << name() << endl;
435    for (int i = 0; i < m_cache_num_sets; i++) {
436        for (int j = 0; j < m_cache_assoc; j++) {
437            if (m_cache[i][j] != NULL) {
438                out << "  Index: " << i
439                    << " way: " << j
440                    << " entry: " << *m_cache[i][j] << endl;
441            } else {
442                out << "  Index: " << i
443                    << " way: " << j
444                    << " entry: NULL" << endl;
445            }
446        }
447    }
448}
449
450void
451CacheMemory::printData(ostream& out) const
452{
453    out << "printData() not supported" << endl;
454}
455
456void
457CacheMemory::setLocked(Addr address, int context)
458{
459    DPRINTF(RubyCache, "Setting Lock for addr: %#x to %d\n", address, context);
460    assert(address == makeLineAddress(address));
461    int64_t cacheSet = addressToCacheSet(address);
462    int loc = findTagInSet(cacheSet, address);
463    assert(loc != -1);
464    m_cache[cacheSet][loc]->setLocked(context);
465}
466
467void
468CacheMemory::clearLocked(Addr address)
469{
470    DPRINTF(RubyCache, "Clear Lock for addr: %#x\n", address);
471    assert(address == makeLineAddress(address));
472    int64_t cacheSet = addressToCacheSet(address);
473    int loc = findTagInSet(cacheSet, address);
474    assert(loc != -1);
475    m_cache[cacheSet][loc]->clearLocked();
476}
477
478bool
479CacheMemory::isLocked(Addr address, int context)
480{
481    assert(address == makeLineAddress(address));
482    int64_t cacheSet = addressToCacheSet(address);
483    int loc = findTagInSet(cacheSet, address);
484    assert(loc != -1);
485    DPRINTF(RubyCache, "Testing Lock for addr: %#llx cur %d con %d\n",
486            address, m_cache[cacheSet][loc]->m_locked, context);
487    return m_cache[cacheSet][loc]->isLocked(context);
488}
489
490void
491CacheMemory::regStats()
492{
493    SimObject::regStats();
494
495    m_demand_hits
496        .name(name() + ".demand_hits")
497        .desc("Number of cache demand hits")
498        ;
499
500    m_demand_misses
501        .name(name() + ".demand_misses")
502        .desc("Number of cache demand misses")
503        ;
504
505    m_demand_accesses
506        .name(name() + ".demand_accesses")
507        .desc("Number of cache demand accesses")
508        ;
509
510    m_demand_accesses = m_demand_hits + m_demand_misses;
511
512    m_sw_prefetches
513        .name(name() + ".total_sw_prefetches")
514        .desc("Number of software prefetches")
515        .flags(Stats::nozero)
516        ;
517
518    m_hw_prefetches
519        .name(name() + ".total_hw_prefetches")
520        .desc("Number of hardware prefetches")
521        .flags(Stats::nozero)
522        ;
523
524    m_prefetches
525        .name(name() + ".total_prefetches")
526        .desc("Number of prefetches")
527        .flags(Stats::nozero)
528        ;
529
530    m_prefetches = m_sw_prefetches + m_hw_prefetches;
531
532    m_accessModeType
533        .init(RubyRequestType_NUM)
534        .name(name() + ".access_mode")
535        .flags(Stats::pdf | Stats::total)
536        ;
537    for (int i = 0; i < RubyAccessMode_NUM; i++) {
538        m_accessModeType
539            .subname(i, RubyAccessMode_to_string(RubyAccessMode(i)))
540            .flags(Stats::nozero)
541            ;
542    }
543
544    numDataArrayReads
545        .name(name() + ".num_data_array_reads")
546        .desc("number of data array reads")
547        .flags(Stats::nozero)
548        ;
549
550    numDataArrayWrites
551        .name(name() + ".num_data_array_writes")
552        .desc("number of data array writes")
553        .flags(Stats::nozero)
554        ;
555
556    numTagArrayReads
557        .name(name() + ".num_tag_array_reads")
558        .desc("number of tag array reads")
559        .flags(Stats::nozero)
560        ;
561
562    numTagArrayWrites
563        .name(name() + ".num_tag_array_writes")
564        .desc("number of tag array writes")
565        .flags(Stats::nozero)
566        ;
567
568    numTagArrayStalls
569        .name(name() + ".num_tag_array_stalls")
570        .desc("number of stalls caused by tag array")
571        .flags(Stats::nozero)
572        ;
573
574    numDataArrayStalls
575        .name(name() + ".num_data_array_stalls")
576        .desc("number of stalls caused by data array")
577        .flags(Stats::nozero)
578        ;
579}
580
581// assumption: SLICC generated files will only call this function
582// once **all** resources are granted
583void
584CacheMemory::recordRequestType(CacheRequestType requestType, Addr addr)
585{
586    DPRINTF(RubyStats, "Recorded statistic: %s\n",
587            CacheRequestType_to_string(requestType));
588    switch(requestType) {
589    case CacheRequestType_DataArrayRead:
590        if (m_resource_stalls)
591            dataArray.reserve(addressToCacheSet(addr));
592        numDataArrayReads++;
593        return;
594    case CacheRequestType_DataArrayWrite:
595        if (m_resource_stalls)
596            dataArray.reserve(addressToCacheSet(addr));
597        numDataArrayWrites++;
598        return;
599    case CacheRequestType_TagArrayRead:
600        if (m_resource_stalls)
601            tagArray.reserve(addressToCacheSet(addr));
602        numTagArrayReads++;
603        return;
604    case CacheRequestType_TagArrayWrite:
605        if (m_resource_stalls)
606            tagArray.reserve(addressToCacheSet(addr));
607        numTagArrayWrites++;
608        return;
609    default:
610        warn("CacheMemory access_type not found: %s",
611             CacheRequestType_to_string(requestType));
612    }
613}
614
615bool
616CacheMemory::checkResourceAvailable(CacheResourceType res, Addr addr)
617{
618    if (!m_resource_stalls) {
619        return true;
620    }
621
622    if (res == CacheResourceType_TagArray) {
623        if (tagArray.tryAccess(addressToCacheSet(addr))) return true;
624        else {
625            DPRINTF(RubyResourceStalls,
626                    "Tag array stall on addr %#x in set %d\n",
627                    addr, addressToCacheSet(addr));
628            numTagArrayStalls++;
629            return false;
630        }
631    } else if (res == CacheResourceType_DataArray) {
632        if (dataArray.tryAccess(addressToCacheSet(addr))) return true;
633        else {
634            DPRINTF(RubyResourceStalls,
635                    "Data array stall on addr %#x in set %d\n",
636                    addr, addressToCacheSet(addr));
637            numDataArrayStalls++;
638            return false;
639        }
640    } else {
641        panic("Unrecognized cache resource type.");
642    }
643}
644
645bool
646CacheMemory::isBlockInvalid(int64_t cache_set, int64_t loc)
647{
648  return (m_cache[cache_set][loc]->m_Permission == AccessPermission_Invalid);
649}
650
651bool
652CacheMemory::isBlockNotBusy(int64_t cache_set, int64_t loc)
653{
654  return (m_cache[cache_set][loc]->m_Permission != AccessPermission_Busy);
655}
656