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