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