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