associative_cache.hh

Go to the documentation of this file.

/*
 * Copyright (c) 2024-2025 Arm Limited
 * All rights reserved
 *
 * The license below extends only to copyright in the software and shall
 * not be construed as granting a license to any other intellectual
 * property including but not limited to intellectual property relating
 * to a hardware implementation of the functionality of the software
 * licensed hereunder.  You may use the software subject to the license
 * terms below provided that you ensure that this notice is replicated
 * unmodified and in its entirety in all distributions of the software,
 * modified or unmodified, in source code or in binary form.
 *
 * 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 <string_view>
#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
{
  protected:
 
    static_assert(std::is_base_of_v<ReplaceableEntry, Entry>,
                  "Entry should be derived from ReplaceableEntry");
 
    typedef replacement_policy::Base BaseReplacementPolicy;
    typedef typename Entry::IndexingPolicy IndexingPolicy;
    typedef typename Entry::KeyType KeyType;

    size_t associativity;

    BaseReplacementPolicy *replPolicy;

    IndexingPolicy *indexingPolicy;

    std::vector<Entry> entries;
 
    const ::gem5::debug::SimpleFlag* debugFlag = nullptr;
 
  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(std::string_view name) : Named(name) {}

    AssociativeCache(std::string_view name, const size_t num_entries,
                     const size_t associativity_,
                     BaseReplacementPolicy *repl_policy,
                     IndexingPolicy *indexing_policy,
                     Entry const &init_val = Entry())
        : Named(name),
          associativity(associativity_),
          replPolicy(repl_policy),
          indexingPolicy(indexing_policy),
          entries(num_entries, init_val),
          debugFlag(nullptr)
    {
        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,
         IndexingPolicy *_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);
    }
 
    void
    setDebugFlag(const ::gem5::debug::SimpleFlag& flag)
    {
        debugFlag = &flag;
    }

    virtual Entry*
    accessEntry(const KeyType &key)
    {
        auto entry = findEntry(key);
 
        if (entry) {
            accessEntry(entry);
        }
 
        return entry;
    }

    virtual void
    accessEntry(Entry *entry)
    {
         if (debugFlag && debugFlag->tracing()) {
            ::gem5::trace::getDebugLogger()->dprintf_flag(
                curTick(), name(), debugFlag->name(),
                "Accessing entry: %s\n", entry->print());
        }
 
 
        replPolicy->touch(entry->replacementData);
    }

    virtual Entry*
    findEntry(const KeyType &key) const
    {
        auto candidates = indexingPolicy->getPossibleEntries(key);
 
        for (auto candidate : candidates) {
            Entry *entry = static_cast<Entry*>(candidate);
            if (entry->match(key)) {
                return entry;
            }
        }
 
        return nullptr;
    }

    virtual Entry*
    findVictim(const KeyType &key)
    {
        auto candidates = indexingPolicy->getPossibleEntries(key);
 
        auto victim = static_cast<Entry*>(replPolicy->getVictim(candidates));
 
        if (debugFlag && debugFlag->tracing() && victim->isValid()) {
            ::gem5::trace::getDebugLogger()->dprintf_flag(
                curTick(), name(), debugFlag->name(),
                "Replacing entry: %s\n", victim->print());
        }
 
        invalidate(victim);
 
        return victim;
    }

    virtual void
    invalidate(Entry *entry)
    {
        entry->invalidate();
        replPolicy->invalidate(entry->replacementData);
    }

    virtual void
    insertEntry(const KeyType &key, Entry *entry)
    {
        if (debugFlag && debugFlag->tracing()) {
            ::gem5::trace::getDebugLogger()->dprintf_flag(
                curTick(), name(), debugFlag->name(),
                "Inserting entry: %s\n", entry->print());
        }
 
        entry->insert(key);
        replPolicy->reset(entry->replacementData);
    }

    std::vector<Entry *>
    getPossibleEntries(const KeyType &key) const
    {
        std::vector<ReplaceableEntry *> selected_entries =
            indexingPolicy->getPossibleEntries(key);
 
        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