CacheMemory.cc revision 8937 
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 "mem/protocol/AccessPermission.hh"
33#include "mem/ruby/system/CacheMemory.hh"
34#include "mem/ruby/system/System.hh"
35
36using namespace std;
37
38ostream&
39operator<<(ostream& out, const CacheMemory& obj)
40{
41    obj.print(out);
42    out << flush;
43    return out;
44}
45
46CacheMemory *
47RubyCacheParams::create()
48{
49    return new CacheMemory(this);
50}
51
52CacheMemory::CacheMemory(const Params *p)
53    : SimObject(p)
54{
55    m_cache_size = p->size;
56    m_latency = p->latency;
57    m_cache_assoc = p->assoc;
58    m_policy = p->replacement_policy;
59    m_profiler_ptr = new CacheProfiler(name());
60    m_start_index_bit = p->start_index_bit;
61    m_is_instruction_only_cache = p->is_icache;
62}
63
64void
65CacheMemory::init()
66{
67    m_cache_num_sets = (m_cache_size / m_cache_assoc) /
68        RubySystem::getBlockSizeBytes();
69    assert(m_cache_num_sets > 1);
70    m_cache_num_set_bits = floorLog2(m_cache_num_sets);
71    assert(m_cache_num_set_bits > 0);
72
73    if (m_policy == "PSEUDO_LRU")
74        m_replacementPolicy_ptr =
75            new PseudoLRUPolicy(m_cache_num_sets, m_cache_assoc);
76    else if (m_policy == "LRU")
77        m_replacementPolicy_ptr =
78            new LRUPolicy(m_cache_num_sets, m_cache_assoc);
79    else
80        assert(false);
81
82    m_cache.resize(m_cache_num_sets);
83    for (int i = 0; i < m_cache_num_sets; i++) {
84        m_cache[i].resize(m_cache_assoc);
85        for (int j = 0; j < m_cache_assoc; j++) {
86            m_cache[i][j] = NULL;
87        }
88    }
89}
90
91CacheMemory::~CacheMemory()
92{
93    if (m_replacementPolicy_ptr != NULL)
94        delete m_replacementPolicy_ptr;
95    delete m_profiler_ptr;
96    for (int i = 0; i < m_cache_num_sets; i++) {
97        for (int j = 0; j < m_cache_assoc; j++) {
98            delete m_cache[i][j];
99        }
100    }
101}
102
103void
104CacheMemory::printConfig(ostream& out)
105{
106    int block_size = RubySystem::getBlockSizeBytes();
107
108    out << "Cache config: " << m_cache_name << endl;
109    out << "  cache_associativity: " << m_cache_assoc << endl;
110    out << "  num_cache_sets_bits: " << m_cache_num_set_bits << endl;
111    const int cache_num_sets = 1 << m_cache_num_set_bits;
112    out << "  num_cache_sets: " << cache_num_sets << endl;
113    out << "  cache_set_size_bytes: " << cache_num_sets * block_size << endl;
114    out << "  cache_set_size_Kbytes: "
115        << double(cache_num_sets * block_size) / (1<<10) << endl;
116    out << "  cache_set_size_Mbytes: "
117        << double(cache_num_sets * block_size) / (1<<20) << endl;
118    out << "  cache_size_bytes: "
119        << cache_num_sets * block_size * m_cache_assoc << endl;
120    out << "  cache_size_Kbytes: "
121        << double(cache_num_sets * block_size * m_cache_assoc) / (1<<10)
122        << endl;
123    out << "  cache_size_Mbytes: "
124        << double(cache_num_sets * block_size * m_cache_assoc) / (1<<20)
125        << endl;
126}
127
128// convert a Address to its location in the cache
129Index
130CacheMemory::addressToCacheSet(const Address& address) const
131{
132    assert(address == line_address(address));
133    return address.bitSelect(m_start_index_bit,
134                             m_start_index_bit + m_cache_num_set_bits - 1);
135}
136
137// Given a cache index: returns the index of the tag in a set.
138// returns -1 if the tag is not found.
139int
140CacheMemory::findTagInSet(Index cacheSet, const Address& tag) const
141{
142    assert(tag == line_address(tag));
143    // search the set for the tags
144    m5::hash_map<Address, int>::const_iterator it = m_tag_index.find(tag);
145    if (it != m_tag_index.end())
146        if (m_cache[cacheSet][it->second]->m_Permission !=
147            AccessPermission_NotPresent)
148            return it->second;
149    return -1; // Not found
150}
151
152// Given a cache index: returns the index of the tag in a set.
153// returns -1 if the tag is not found.
154int
155CacheMemory::findTagInSetIgnorePermissions(Index cacheSet,
156                                           const Address& tag) const
157{
158    assert(tag == line_address(tag));
159    // search the set for the tags
160    m5::hash_map<Address, int>::const_iterator it = m_tag_index.find(tag);
161    if (it != m_tag_index.end())
162        return it->second;
163    return -1; // Not found
164}
165
166bool
167CacheMemory::tryCacheAccess(const Address& address, RubyRequestType type,
168                            DataBlock*& data_ptr)
169{
170    assert(address == line_address(address));
171    DPRINTF(RubyCache, "address: %s\n", address);
172    Index cacheSet = addressToCacheSet(address);
173    int loc = findTagInSet(cacheSet, address);
174    if (loc != -1) {
175        // Do we even have a tag match?
176        AbstractCacheEntry* entry = m_cache[cacheSet][loc];
177        m_replacementPolicy_ptr->
178            touch(cacheSet, loc, g_eventQueue_ptr->getTime());
179        data_ptr = &(entry->getDataBlk());
180
181        if (entry->m_Permission == AccessPermission_Read_Write) {
182            return true;
183        }
184        if ((entry->m_Permission == AccessPermission_Read_Only) &&
185            (type == RubyRequestType_LD || type == RubyRequestType_IFETCH)) {
186            return true;
187        }
188        // The line must not be accessible
189    }
190    data_ptr = NULL;
191    return false;
192}
193
194bool
195CacheMemory::testCacheAccess(const Address& address, RubyRequestType type,
196                             DataBlock*& data_ptr)
197{
198    assert(address == line_address(address));
199    DPRINTF(RubyCache, "address: %s\n", address);
200    Index cacheSet = addressToCacheSet(address);
201    int loc = findTagInSet(cacheSet, address);
202
203    if (loc != -1) {
204        // Do we even have a tag match?
205        AbstractCacheEntry* entry = m_cache[cacheSet][loc];
206        m_replacementPolicy_ptr->
207            touch(cacheSet, loc, g_eventQueue_ptr->getTime());
208        data_ptr = &(entry->getDataBlk());
209
210        return m_cache[cacheSet][loc]->m_Permission !=
211            AccessPermission_NotPresent;
212    }
213
214    data_ptr = NULL;
215    return false;
216}
217
218// tests to see if an address is present in the cache
219bool
220CacheMemory::isTagPresent(const Address& address) const
221{
222    assert(address == line_address(address));
223    Index cacheSet = addressToCacheSet(address);
224    int loc = findTagInSet(cacheSet, address);
225
226    if (loc == -1) {
227        // We didn't find the tag
228        DPRINTF(RubyCache, "No tag match for address: %s\n", address);
229        return false;
230    }
231    DPRINTF(RubyCache, "address: %s found\n", address);
232    return true;
233}
234
235// Returns true if there is:
236//   a) a tag match on this address or there is
237//   b) an unused line in the same cache "way"
238bool
239CacheMemory::cacheAvail(const Address& address) const
240{
241    assert(address == line_address(address));
242
243    Index cacheSet = addressToCacheSet(address);
244
245    for (int i = 0; i < m_cache_assoc; i++) {
246        AbstractCacheEntry* entry = m_cache[cacheSet][i];
247        if (entry != NULL) {
248            if (entry->m_Address == address ||
249                entry->m_Permission == AccessPermission_NotPresent) {
250                // Already in the cache or we found an empty entry
251                return true;
252            }
253        } else {
254            return true;
255        }
256    }
257    return false;
258}
259
260AbstractCacheEntry*
261CacheMemory::allocate(const Address& address, AbstractCacheEntry* entry)
262{
263    assert(address == line_address(address));
264    assert(!isTagPresent(address));
265    assert(cacheAvail(address));
266    DPRINTF(RubyCache, "address: %s\n", address);
267
268    // Find the first open slot
269    Index cacheSet = addressToCacheSet(address);
270    std::vector<AbstractCacheEntry*> &set = m_cache[cacheSet];
271    for (int i = 0; i < m_cache_assoc; i++) {
272        if (!set[i] || set[i]->m_Permission == AccessPermission_NotPresent) {
273            set[i] = entry;  // Init entry
274            set[i]->m_Address = address;
275            set[i]->m_Permission = AccessPermission_Invalid;
276            DPRINTF(RubyCache, "Allocate clearing lock for addr: %x\n",
277                    address);
278            set[i]->m_locked = -1;
279            m_tag_index[address] = i;
280
281            m_replacementPolicy_ptr->
282                touch(cacheSet, i, g_eventQueue_ptr->getTime());
283
284            return entry;
285        }
286    }
287    panic("Allocate didn't find an available entry");
288}
289
290void
291CacheMemory::deallocate(const Address& address)
292{
293    assert(address == line_address(address));
294    assert(isTagPresent(address));
295    DPRINTF(RubyCache, "address: %s\n", address);
296    Index cacheSet = addressToCacheSet(address);
297    int loc = findTagInSet(cacheSet, address);
298    if (loc != -1) {
299        delete m_cache[cacheSet][loc];
300        m_cache[cacheSet][loc] = NULL;
301        m_tag_index.erase(address);
302    }
303}
304
305// Returns with the physical address of the conflicting cache line
306Address
307CacheMemory::cacheProbe(const Address& address) const
308{
309    assert(address == line_address(address));
310    assert(!cacheAvail(address));
311
312    Index cacheSet = addressToCacheSet(address);
313    return m_cache[cacheSet][m_replacementPolicy_ptr->getVictim(cacheSet)]->
314        m_Address;
315}
316
317// looks an address up in the cache
318AbstractCacheEntry*
319CacheMemory::lookup(const Address& address)
320{
321    assert(address == line_address(address));
322    Index cacheSet = addressToCacheSet(address);
323    int loc = findTagInSet(cacheSet, address);
324    if(loc == -1) return NULL;
325    return m_cache[cacheSet][loc];
326}
327
328// looks an address up in the cache
329const AbstractCacheEntry*
330CacheMemory::lookup(const Address& address) const
331{
332    assert(address == line_address(address));
333    Index cacheSet = addressToCacheSet(address);
334    int loc = findTagInSet(cacheSet, address);
335    if(loc == -1) return NULL;
336    return m_cache[cacheSet][loc];
337}
338
339// Sets the most recently used bit for a cache block
340void
341CacheMemory::setMRU(const Address& address)
342{
343    Index cacheSet = addressToCacheSet(address);
344    int loc = findTagInSet(cacheSet, address);
345
346    if(loc != -1)
347        m_replacementPolicy_ptr->
348             touch(cacheSet, loc, g_eventQueue_ptr->getTime());
349}
350
351void
352CacheMemory::profileMiss(const RubyRequest& msg)
353{
354    m_profiler_ptr->addCacheStatSample(msg.getType(),
355                                       msg.getAccessMode(),
356                                       msg.getPrefetch());
357}
358
359void
360CacheMemory::profileGenericRequest(GenericRequestType requestType,
361                                   RubyAccessMode accessType,
362                                   PrefetchBit pfBit)
363{
364    m_profiler_ptr->addGenericStatSample(requestType,
365                                         accessType,
366                                         pfBit);
367}
368
369void
370CacheMemory::recordCacheContents(int cntrl, CacheRecorder* tr) const
371{
372    uint64 warmedUpBlocks = 0;
373    uint64 totalBlocks M5_VAR_USED = (uint64)m_cache_num_sets
374                                                  * (uint64)m_cache_assoc;
375
376    for (int i = 0; i < m_cache_num_sets; i++) {
377        for (int j = 0; j < m_cache_assoc; j++) {
378            if (m_cache[i][j] != NULL) {
379                AccessPermission perm = m_cache[i][j]->m_Permission;
380                RubyRequestType request_type = RubyRequestType_NULL;
381                if (perm == AccessPermission_Read_Only) {
382                    if (m_is_instruction_only_cache) {
383                        request_type = RubyRequestType_IFETCH;
384                    } else {
385                        request_type = RubyRequestType_LD;
386                    }
387                } else if (perm == AccessPermission_Read_Write) {
388                    request_type = RubyRequestType_ST;
389                }
390
391                if (request_type != RubyRequestType_NULL) {
392                    tr->addRecord(cntrl, m_cache[i][j]->m_Address.getAddress(),
393                                  0, request_type,
394                                  m_replacementPolicy_ptr->getLastAccess(i, j),
395                                  m_cache[i][j]->getDataBlk());
396                    warmedUpBlocks++;
397                }
398            }
399        }
400    }
401
402    DPRINTF(RubyCacheTrace, "%s: %lli blocks of %lli total blocks"
403            "recorded %.2f%% \n", name().c_str(), warmedUpBlocks,
404            (uint64)m_cache_num_sets * (uint64)m_cache_assoc,
405            (float(warmedUpBlocks)/float(totalBlocks))*100.0);
406}
407
408void
409CacheMemory::print(ostream& out) const
410{
411    out << "Cache dump: " << m_cache_name << endl;
412    for (int i = 0; i < m_cache_num_sets; i++) {
413        for (int j = 0; j < m_cache_assoc; j++) {
414            if (m_cache[i][j] != NULL) {
415                out << "  Index: " << i
416                    << " way: " << j
417                    << " entry: " << *m_cache[i][j] << endl;
418            } else {
419                out << "  Index: " << i
420                    << " way: " << j
421                    << " entry: NULL" << endl;
422            }
423        }
424    }
425}
426
427void
428CacheMemory::printData(ostream& out) const
429{
430    out << "printData() not supported" << endl;
431}
432
433void
434CacheMemory::clearStats() const
435{
436    m_profiler_ptr->clearStats();
437}
438
439void
440CacheMemory::printStats(ostream& out) const
441{
442    m_profiler_ptr->printStats(out);
443}
444
445void
446CacheMemory::setLocked(const Address& address, int context)
447{
448    DPRINTF(RubyCache, "Setting Lock for addr: %x to %d\n", address, context);
449    assert(address == line_address(address));
450    Index cacheSet = addressToCacheSet(address);
451    int loc = findTagInSet(cacheSet, address);
452    assert(loc != -1);
453    m_cache[cacheSet][loc]->m_locked = context;
454}
455
456void
457CacheMemory::clearLocked(const Address& address)
458{
459    DPRINTF(RubyCache, "Clear Lock for addr: %x\n", address);
460    assert(address == line_address(address));
461    Index cacheSet = addressToCacheSet(address);
462    int loc = findTagInSet(cacheSet, address);
463    assert(loc != -1);
464    m_cache[cacheSet][loc]->m_locked = -1;
465}
466
467bool
468CacheMemory::isLocked(const Address& address, int context)
469{
470    assert(address == line_address(address));
471    Index cacheSet = addressToCacheSet(address);
472    int loc = findTagInSet(cacheSet, address);
473    assert(loc != -1);
474    DPRINTF(RubyCache, "Testing Lock for addr: %llx cur %d con %d\n",
475            address, m_cache[cacheSet][loc]->m_locked, context);
476    return m_cache[cacheSet][loc]->m_locked == context;
477}
478
479