1/*
2 * Copyright (c) 2018 Inria
3 * Copyright (c) 2012-2014,2017 ARM Limited
4 * All rights reserved.
5 *
6 * The license below extends only to copyright in the software and shall
7 * not be construed as granting a license to any other intellectual
8 * property including but not limited to intellectual property relating
9 * to a hardware implementation of the functionality of the software
10 * licensed hereunder.  You may use the software subject to the license
11 * terms below provided that you ensure that this notice is replicated
12 * unmodified and in its entirety in all distributions of the software,
13 * modified or unmodified, in source code or in binary form.
14 *
15 * Copyright (c) 2003-2005,2014 The Regents of The University of Michigan
16 * All rights reserved.
17 *
18 * Redistribution and use in source and binary forms, with or without
19 * modification, are permitted provided that the following conditions are
20 * met: redistributions of source code must retain the above copyright
21 * notice, this list of conditions and the following disclaimer;
22 * redistributions in binary form must reproduce the above copyright
23 * notice, this list of conditions and the following disclaimer in the
24 * documentation and/or other materials provided with the distribution;
25 * neither the name of the copyright holders nor the names of its
26 * contributors may be used to endorse or promote products derived from
27 * this software without specific prior written permission.
28 *
29 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
30 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
31 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
32 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
33 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
34 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
35 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
36 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
37 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
38 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
39 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
40 *
41 * Authors: Daniel Carvalho
42 *          Erik Hallnor
43 */
44
45/**
46 * @file
47 * Declaration of a set associative indexing policy.
48 */
49
50#ifndef __MEM_CACHE_INDEXING_POLICIES_SET_ASSOCIATIVE_HH__
51#define __MEM_CACHE_INDEXING_POLICIES_SET_ASSOCIATIVE_HH__
52
53#include <vector>
54
55#include "mem/cache/tags/indexing_policies/base.hh"
56#include "params/SetAssociative.hh"
57
58class ReplaceableEntry;
59
60/**
61 * A set associative indexing policy.
62 * @sa  \ref gem5MemorySystem "gem5 Memory System"
63 *
64 * The set associative indexing policy has an immutable/identity mapping, so a
65 * value x is always mapped to set x, independent of the way, that is,
66 * Hash(A, 0) = Hash(A, 1) = Hash(A, N-1), where N is the number of ways.
67 *
68 * For example, let's assume address A maps to set 3 on way 0. This policy
69 * makes so that A is also mappable to set 3 on every other way. Visually, the
70 * possible locations of A are, for a table with 4 ways and 8 sets:
71 *    Way 0   1   2   3
72 *  Set   _   _   _   _
73 *    0  |_| |_| |_| |_|
74 *    1  |_| |_| |_| |_|
75 *    2  |_| |_| |_| |_|
76 *    3  |X| |X| |X| |X|
77 *    4  |_| |_| |_| |_|
78 *    5  |_| |_| |_| |_|
79 *    6  |_| |_| |_| |_|
80 *    7  |_| |_| |_| |_|
81 */
82class SetAssociative : public BaseIndexingPolicy
83{
84  private:
85    /**
86     * Apply a hash function to calculate address set.
87     *
88     * @param addr The address to calculate the set for.
89     * @return The set index for given combination of address and way.
90     */
91    uint32_t extractSet(const Addr addr) const;
92
93  public:
94    /**
95     * Convenience typedef.
96     */
97    typedef SetAssociativeParams Params;
98
99    /**
100     * Construct and initialize this policy.
101     */
102    SetAssociative(const Params *p);
103
104    /**
105     * Destructor.
106     */
107    ~SetAssociative() {};
108
109    /**
110     * Find all possible entries for insertion and replacement of an address.
111     * Should be called immediately before ReplacementPolicy's findVictim()
112     * not to break cache resizing.
113     * Returns entries in all ways belonging to the set of the address.
114     *
115     * @param addr The addr to a find possible entries for.
116     * @return The possible entries.
117     */
118    std::vector<ReplaceableEntry*> getPossibleEntries(const Addr addr) const
119                                                                     override;
120
121    /**
122     * Regenerate an entry's address from its tag and assigned set and way.
123     *
124     * @param tag The tag bits.
125     * @param entry The entry.
126     * @return the entry's original addr value.
127     */
128    Addr regenerateAddr(const Addr tag, const ReplaceableEntry* entry) const
129                                                                   override;
130};
131
132#endif //__MEM_CACHE_INDEXING_POLICIES_SET_ASSOCIATIVE_HH__
133