associative_cache.hh

Go to the documentation of this file.

/*
 * Copyright (c) 2024 Pranith Kumar
 * Copyright (c) 2018 Metempsy Technology Consulting
 * All rights reserved
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are
 * met: redistributions of source code must retain the above copyright
 * notice, this list of conditions and the following disclaimer;
 * redistributions in binary form must reproduce the above copyright
 * notice, this list of conditions and the following disclaimer in the
 * documentation and/or other materials provided with the distribution;
 * neither the name of the copyright holders nor the names of its
 * contributors may be used to endorse or promote products derived from
 * this software without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */
 
#ifndef __BASE_CACHE_ASSOCIATIVE_CACHE_HH__
#define __BASE_CACHE_ASSOCIATIVE_CACHE_HH__
 
#include <type_traits>
#include <vector>
 
#include "base/cache/cache_entry.hh"
#include "base/intmath.hh"
#include "base/logging.hh"
#include "base/named.hh"
#include "base/types.hh"
#include "mem/cache/replacement_policies/base.hh"
#include "mem/cache/replacement_policies/replaceable_entry.hh"
#include "mem/cache/tags/indexing_policies/base.hh"
 
namespace gem5
{
 
template <typename Entry>
class AssociativeCache : public Named
{
    static_assert(std::is_base_of_v<CacheEntry, Entry>,
                  "Entry should be derived from CacheEntry");
 
    typedef replacement_policy::Base BaseReplacementPolicy;
 
  protected:
 
    size_t associativity;
 
    BaseReplacementPolicy *replPolicy;
 
    BaseIndexingPolicy *indexingPolicy;
 
    std::vector<Entry> entries;
 
  private:
 
    void
    initParams(size_t _num_entries, size_t _assoc)
    {
        fatal_if((_num_entries % _assoc) != 0, "The number of entries of an "
                 "AssociativeCache<> must be a multiple of its associativity");
        for (auto entry_idx = 0; entry_idx < _num_entries; entry_idx++) {
            Entry *entry = &entries[entry_idx];
            indexingPolicy->setEntry(entry, entry_idx);
            entry->replacementData = replPolicy->instantiateEntry();
        }
    }
 
  public:
 
    AssociativeCache(const char *name) : Named(std::string(name)) {}
 
    AssociativeCache(const char *name, const size_t num_entries,
                     const size_t associativity_,
                     BaseReplacementPolicy *repl_policy,
                     BaseIndexingPolicy *indexing_policy,
                     Entry const &init_val = Entry())
        : Named(std::string(name)),
          associativity(associativity_),
          replPolicy(repl_policy),
          indexingPolicy(indexing_policy),
          entries(num_entries, init_val)
    {
        initParams(num_entries, associativity);
    }
 
    ~AssociativeCache()  = default;
 
    AssociativeCache(const AssociativeCache&) = delete;
    AssociativeCache& operator=(const AssociativeCache&) = delete;
 
    void
    clear()
    {
        for (auto &entry : entries) {
            invalidate(&entry);
        }
    }
 
    void
    init(const size_t num_entries,
         const size_t associativity_,
         BaseReplacementPolicy *_repl_policy,
         BaseIndexingPolicy *_indexing_policy,
         Entry const &init_val = Entry())
    {
        associativity = associativity_;
        replPolicy = _repl_policy;
        indexingPolicy = _indexing_policy;
        entries.resize(num_entries, init_val);
 
        initParams(num_entries, associativity);
    }
 
    virtual Addr
    getTag(const Addr addr) const
    {
        return indexingPolicy->extractTag(addr);
    }
 
    virtual Entry*
    accessEntryByAddr(const Addr addr)
    {
        auto entry = findEntry(addr);
 
        if (entry) {
            accessEntry(entry);
        }
 
        return entry;
    }
 
    virtual void
    accessEntry(Entry *entry)
    {
        replPolicy->touch(entry->replacementData);
    }
 
    virtual Entry*
    findEntry(const Addr addr) const
    {
        auto tag = getTag(addr);
 
        auto candidates = indexingPolicy->getPossibleEntries(addr);
 
        for (auto candidate : candidates) {
            Entry *entry = static_cast<Entry*>(candidate);
            if (entry->matchTag(tag)) {
                return entry;
            }
        }
 
        return nullptr;
    }
 
    virtual Entry*
    findVictim(const Addr addr)
    {
        auto candidates = indexingPolicy->getPossibleEntries(addr);
 
        auto victim = static_cast<Entry*>(replPolicy->getVictim(candidates));
 
        invalidate(victim);
 
        return victim;
    }
 
    virtual void
    invalidate(Entry *entry)
    {
        entry->invalidate();
        replPolicy->invalidate(entry->replacementData);
    }
 
    virtual void
    insertEntry(const Addr addr, Entry *entry)
    {
        entry->insert(indexingPolicy->extractTag(addr));
        replPolicy->reset(entry->replacementData);
    }
 
    std::vector<Entry *>
    getPossibleEntries(const Addr addr) const
    {
        std::vector<ReplaceableEntry *> selected_entries =
            indexingPolicy->getPossibleEntries(addr);
 
        std::vector<Entry *> entries;
 
        std::transform(selected_entries.begin(), selected_entries.end(),
                       std::back_inserter(entries), [](auto &entry) {
                           return static_cast<Entry *>(entry);
                       });
 
        return entries;
    }
 
    using const_iterator = typename std::vector<Entry>::const_iterator;
    using iterator = typename std::vector<Entry>::iterator;
 
    iterator
    begin()
    {
        return entries.begin();
    }
 
    iterator
    end()
    {
        return entries.end();
    }
 
    const_iterator
    begin() const
    {
        return entries.begin();
    }
 
    const_iterator
    end() const
    {
        return entries.end();
    }
};
 
}
 
#endif