src/mem/cache/replacement_policies/tree_plru_rp.hh

/**
 * Copyright (c) 2018 Inria
 * 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.
 *
 * Authors: Daniel Carvalho
 */

/**
 * @file
 * Declaration of a Pseudo-Least Recently Used replacement policy.
 * The victim is chosen using a tree of bit timestamps.
 *
 * A tree contains consists of leafs that represent the direction to take when
 * searching for the LRU entry.
 *
 * Let's assume each tree contains 8 replacement data entries. For example, if
 * these entries are named from A to H, and the tree's bits are:
 *    ____1____
 *  __0__   __1__
 * _0_ _1_ _1_ _0_
 * A B C D E F G H
 *
 * Then the current PLRU entry is given by the sequence:
 *     1 (get right child) -> 1 (get right child) -> 0 (get left child) -> G
 *
 * When an entry is touched the bits of the parent nodes are iteratively
 * updated to point away from it. Therefore, if entry B is touched, its parent,
 * grandparents, etc would be updated, and we'd end up with the following tree:
 *    ____1____
 *  __1__   __1__
 * _0_ _1_ _1_ _0_
 * A B C D E F G H
 *
 * Explanation: The parent of B must point away from it, that is, to the left
 * child, but it is already doing so, so it is left unmodified (0). Then the
 * grandparent must point to the right subtree, as B belongs to its left
 * subtree (0 becomes 1). Lastly, the root must point away from the
 * grandparent, so it is left unmodified (0).
 *
 * For invalidations the process is similar to touches, but instead of pointing
 * away, the bits point toward the entry.
 *
 * Consecutive calls to instantiateEntry() use the same tree up to numLeaves.
 * When numLeaves replacement datas have been created, a new tree is generated,
 * and the counter is reset.
 */

#ifndef __MEM_CACHE_REPLACEMENT_POLICIES_TREE_PLRU_RP_HH__
#define __MEM_CACHE_REPLACEMENT_POLICIES_TREE_PLRU_RP_HH__

#include <cstdint>
#include <memory>
#include <vector>

#include "mem/cache/replacement_policies/base.hh"

struct TreePLRURPParams;

class TreePLRURP : public BaseReplacementPolicy
{
  private:
    /**
     * Instead of implementing the tree itself with pointers, it is implemented
     * as an array of bits. The index of the node defines its position in the
     * tree, and its parent. Index 0 represents the root, 1 is its left node,
     * and 2 is its right node. Then, in a BFS fashion this is expanded to the
     * following nodes (3 and 4 are respectively 1's left and right nodes, and
     * 5 and 6 are 2's left and right nodes, and so on).
     *
     * i.e., the following trees are equivalent in this representation:
     *    ____1____
     *  __0__   __1__
     * _0_ _1_ _1_ _0_
     * A B C D E F G H
     *
     * 1 0 1 0 1 1 0
     *
     * Notice that the replacement data entries are not represented in the tree
     * to avoid unnecessary storage costs.
     */
    typedef std::vector<bool> PLRUTree;

    /**
     * Number of leaves that share a single replacement data.
     */
    const uint64_t numLeaves;

    /**
     * Count of the number of sharers of a replacement data. It is used when
     * instantiating entries to share a replacement data among many replaceable
     * entries.
     */
    uint64_t count;

    /**
     * Holds the latest temporary tree instance created by instantiateEntry().
     */
    PLRUTree* treeInstance;

  protected:
    /**
     * Tree-PLRU-specific implementation of replacement data. Each replacement
     * data shares its tree with other entries.
     */
    struct TreePLRUReplData : ReplacementData
    {
        /**
         * Theoretical index of this replacement data in the tree. In practice,
         * the corresponding node does not exist, as the tree stores only the
         * nodes that are not leaves.
         */
        const uint64_t index;

        /**
         * Shared tree pointer. A tree is shared between numLeaves nodes, so
         * that accesses to a replacement data entry updates the PLRU bits of
         * all other replacement data entries in its set.
         */
        std::shared_ptr<PLRUTree> tree;

        /**
         * Default constructor. Invalidate data.
         *
         * @param index Index of the corresponding entry in the tree.
         * @param tree The shared tree pointer.
         */
        TreePLRUReplData(const uint64_t index, std::shared_ptr<PLRUTree> tree);
    };

  public:
    /** Convenience typedef. */
    typedef TreePLRURPParams Params;

    /**
     * Construct and initiliaze this replacement policy.
     */
    TreePLRURP(const Params *p);

    /**
     * Destructor.
     */
    ~TreePLRURP() {}

    /**
     * Invalidate replacement data to set it as the next probable victim.
     * Makes tree leaf of replacement data the LRU (tree bits point to it).
     *
     * @param replacement_data Replacement data to be invalidated.
     */
    void invalidate(const std::shared_ptr<ReplacementData>& replacement_data)
                                                              const override;

    /**
     * Touch an entry to update its replacement data.
     * Makes tree leaf of replacement data the MRU.
     *
     * @param replacement_data Replacement data to be touched.
     */
    void touch(const std::shared_ptr<ReplacementData>& replacement_data) const
                                                                     override;

    /**
     * Reset replacement data. Used when an entry is inserted. Provides the
     * same functionality as touch().
     *
     * @param replacement_data Replacement data to be reset.
     */
    void reset(const std::shared_ptr<ReplacementData>& replacement_data) const
                                                                     override;

    /**
     * Find replacement victim using TreePLRU bits. It is assumed that all
     * candidates share the same replacement data tree.
     *
     * @param candidates Replacement candidates, selected by indexing policy.
     * @return Replacement entry to be replaced.
     */
    ReplaceableEntry* getVictim(const ReplacementCandidates& candidates) const
                                                                     override;

    /**
     * Instantiate a replacement data entry. Consecutive calls to this
     * function use the same tree up to numLeaves. When numLeaves replacement
     * data have been created, a new tree is generated, and the counter is
     * reset.
     * Therefore, it is essential that entries that share the same replacement
     * data call this function consecutively.
     *
     * @return A shared pointer to the new replacement data.
     */
    std::shared_ptr<ReplacementData> instantiateEntry() override;
};

#endif // __MEM_CACHE_REPLACEMENT_POLICIES_TREE_PLRU_RP_HH__