1/**
2 * Copyright (c) 2018 Metempsy Technology Consulting
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 * Authors: Javier Bueno
29 */
30
31#ifndef __CACHE_PREFETCH_ASSOCIATIVE_SET_HH__
32#define __CACHE_PREFETCH_ASSOCIATIVE_SET_HH__
33
34#include "mem/cache/replacement_policies/base.hh"
35#include "mem/cache/replacement_policies/replaceable_entry.hh"
36#include "mem/cache/tags/indexing_policies/base.hh"
37
38/**
39 * Entry used for set-associative tables, usable with replacement policies
40 */
41class TaggedEntry : public ReplaceableEntry {
42    /** Tag for the entry */
43    Addr tag;
44    /** Valid bit */
45    bool valid;
46    /** Whether this entry refers to a memory area in the secure space */
47    bool secure;
48  public:
49    TaggedEntry() : tag(0), valid(false), secure(false) {}
50    virtual ~TaggedEntry() {}
51
52    /**
53     * Consult the valid bit
54     * @return True if the entry is valid
55     */
56    bool isValid() const
57    {
58        return valid;
59    }
60
61    /**
62     * Sets the entry to valid
63     */
64    void setValid()
65    {
66        valid = true;
67    }
68
69    /**
70     * Sets the entry to invalid
71     */
72    void setInvalid() {
73        valid = false;
74    }
75
76    /**
77     * Obtain the entry tag
78     * @return the tag value
79     */
80    Addr getTag() const
81    {
82        return tag;
83    }
84
85    /**
86     * Sets the tag of the entry
87     * @param t the tag value
88     */
89    void setTag(Addr t)
90    {
91        tag = t;
92    }
93
94    /**
95     * Consult if this entry refers to a memory in the secure area
96     * @return True if this entry refers to secure memory area
97     */
98    bool isSecure() const
99    {
100        return secure;
101    }
102
103    /**
104     * Sets the secure value bit
105     * @param s secure bit value
106     */
107    void setSecure(bool s)
108    {
109        secure = s;
110    }
111
112    /**
113     * Resets the entry, this is called when an entry is evicted to allocate
114     * a new one. Types inheriting this class should provide its own
115     * implementation
116     */
117    virtual void reset () {
118    }
119};
120
121/**
122 * Associative container based on the previosuly defined Entry type
123 * Each element is indexed by a key of type Addr, an additional
124 * bool value is used as an additional tag data of the entry.
125 */
126template<class Entry>
127class AssociativeSet {
128    static_assert(std::is_base_of<TaggedEntry, Entry>::value,
129                  "Entry must derive from TaggedEntry");
130
131    /** Associativity of the container */
132    const int associativity;
133    /**
134     * Total number of entries, entries are organized in sets of the provided
135     * associativity. The number of associative sets is obtained by dividing
136     * numEntries by associativity.
137     */
138    const int numEntries;
139    /** Pointer to the indexing policy */
140    BaseIndexingPolicy* const indexingPolicy;
141    /** Pointer to the replacement policy */
142    BaseReplacementPolicy* const replacementPolicy;
143    /** Vector containing the entries of the container */
144    std::vector<Entry> entries;
145
146  public:
147    /**
148     * Public constructor
149     * @param assoc number of elements in each associative set
150     * @param num_entries total number of entries of the container, the number
151     *   of sets can be calculated dividing this balue by the 'assoc' value
152     * @param idx_policy indexing policy
153     * @param rpl_policy replacement policy
154     * @param initial value of the elements of the set
155     */
156    AssociativeSet(int assoc, int num_entries, BaseIndexingPolicy *idx_policy,
157                   BaseReplacementPolicy *rpl_policy, Entry const &init_value =
158                   Entry());
159
160    /**
161     * Find an entry within the set
162     * @param addr key element
163     * @param is_secure tag element
164     * @return returns a pointer to the wanted entry or nullptr if it does not
165     *  exist.
166     */
167    Entry* findEntry(Addr addr, bool is_secure) const;
168
169    /**
170     * Do an access to the entry, this is required to
171     * update the replacement information data.
172     * @param entry the accessed entry
173     */
174    void accessEntry(Entry *entry);
175
176    /**
177     * Find a victim to be replaced
178     * @param addr key to select the possible victim
179     * @result entry to be victimized
180     */
181    Entry* findVictim(Addr addr);
182
183    /**
184     * Find the set of entries that could be replaced given
185     * that we want to add a new entry with the provided key
186     * @param addr key to select the set of entries
187     * @result vector of candidates matching with the provided key
188     */
189    std::vector<Entry *> getPossibleEntries(const Addr addr) const;
190
191    /**
192     * Indicate that an entry has just been inserted
193     * @param addr key of the container
194     * @param is_secure tag component of the container
195     * @param entry pointer to the container entry to be inserted
196     */
197    void insertEntry(Addr addr, bool is_secure, Entry* entry);
198
199    /** Iterator types */
200    using const_iterator = typename std::vector<Entry>::const_iterator;
201    using iterator = typename std::vector<Entry>::iterator;
202
203    /**
204     * Returns an iterator to the first entry of the dictionary
205     * @result iterator to the first element
206     */
207    iterator begin()
208    {
209        return entries.begin();
210    }
211
212    /**
213     * Returns an iterator pointing to the end of the the dictionary
214     * (placeholder element, should not be accessed)
215     * @result iterator to the end element
216     */
217    iterator end()
218    {
219        return entries.end();
220    }
221
222    /**
223     * Returns an iterator to the first entry of the dictionary
224     * @result iterator to the first element
225     */
226    const_iterator begin() const
227    {
228        return entries.begin();
229    }
230
231    /**
232     * Returns an iterator pointing to the end of the the dictionary
233     * (placeholder element, should not be accessed)
234     * @result iterator to the end element
235     */
236    const_iterator end() const
237    {
238        return entries.end();
239    }
240};
241
242#endif//__CACHE_PREFETCH_ASSOCIATIVE_SET_HH__
243