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 #include "mem/cache/prefetch/indirect_memory.hh"
32
33 #include "mem/cache/base.hh"
34 #include "mem/cache/prefetch/associative_set_impl.hh"
35 #include "params/IndirectMemoryPrefetcher.hh"
36
37IndirectMemoryPrefetcher::IndirectMemoryPrefetcher(
38    const IndirectMemoryPrefetcherParams *p) : QueuedPrefetcher(p),
39    maxPrefetchDistance(p->max_prefetch_distance),
40    shiftValues(p->shift_values), prefetchThreshold(p->prefetch_threshold),
41    streamCounterThreshold(p->stream_counter_threshold),
42    streamingDistance(p->streaming_distance),
43    prefetchTable(p->pt_table_assoc, p->pt_table_entries,
44                  p->pt_table_indexing_policy, p->pt_table_replacement_policy,
45                  PrefetchTableEntry(p->num_indirect_counter_bits)),
46    ipd(p->ipd_table_assoc, p->ipd_table_entries, p->ipd_table_indexing_policy,
47        p->ipd_table_replacement_policy,
48        IndirectPatternDetectorEntry(p->addr_array_len, shiftValues.size())),
49    ipdEntryTrackingMisses(nullptr),
50#if THE_ISA != NULL_ISA
51    byteOrder(TheISA::GuestByteOrder)
52#else
53    byteOrder((ByteOrder) -1)
54#endif
55{
56    fatal_if(byteOrder == static_cast<ByteOrder>(-1),
57            "This prefetcher requires a defined ISA\n");
58}
59
60void
61IndirectMemoryPrefetcher::calculatePrefetch(const PrefetchInfo &pfi,
62    std::vector<AddrPriority> &addresses)
63{
64    // This prefetcher requires a PC
65    if (!pfi.hasPC()) {
66        return;
67    }
68
69    bool is_secure = pfi.isSecure();
70    Addr pc = pfi.getPC();
71    Addr addr = pfi.getAddr();
72    bool miss = pfi.isCacheMiss();
73
74    checkAccessMatchOnActiveEntries(addr);
75
76    // First check if this is a miss, if the prefetcher is tracking misses
77    if (ipdEntryTrackingMisses != nullptr && miss) {
78        // Check if the entry tracking misses has already set its second index
79        if (!ipdEntryTrackingMisses->secondIndexSet) {
80            trackMissIndex1(addr);
81        } else {
82            trackMissIndex2(addr);
83        }
84    } else {
85        // if misses are not being tracked, attempt to detect stream accesses
86        PrefetchTableEntry *pt_entry =
87            prefetchTable.findEntry(pc, false /* unused */);
88        if (pt_entry != nullptr) {
89            prefetchTable.accessEntry(pt_entry);
90
91            if (pt_entry->address != addr) {
92                // Streaming access found
93                pt_entry->streamCounter += 1;
94                if (pt_entry->streamCounter >= streamCounterThreshold) {
95                    int64_t delta = addr - pt_entry->address;
96                    for (unsigned int i = 1; i <= streamingDistance; i += 1) {
97                        addresses.push_back(AddrPriority(addr + delta * i, 0));
98                    }
99                }
100                pt_entry->address = addr;
101                pt_entry->secure = is_secure;
102
103
104                // if this is a read, read the data from the cache and assume
105                // it is an index (this is only possible if the data is already
106                // in the cache), also, only indexes up to 8 bytes are
107                // considered
108
109                if (!miss && !pfi.isWrite() && pfi.getSize() <= 8) {
110                    int64_t index = 0;
111                    bool read_index = true;
112                    switch(pfi.getSize()) {
113                        case sizeof(uint8_t):
114                            index = pfi.get<uint8_t>(byteOrder);
115                            break;
116                        case sizeof(uint16_t):
117                            index = pfi.get<uint16_t>(byteOrder);
118                            break;
119                        case sizeof(uint32_t):
120                            index = pfi.get<uint32_t>(byteOrder);
121                            break;
122                        case sizeof(uint64_t):
123                            index = pfi.get<uint64_t>(byteOrder);
124                            break;
125                        default:
126                            // Ignore non-power-of-two sizes
127                            read_index = false;
128                    }
129                    if (read_index && !pt_entry->enabled) {
130                        // Not enabled (no pattern detected in this stream),
131                        // add or update an entry in the pattern detector and
132                        // start tracking misses
133                        allocateOrUpdateIPDEntry(pt_entry, index);
134                    } else if (read_index) {
135                        // Enabled entry, update the index
136                        pt_entry->index = index;
137                        if (!pt_entry->increasedIndirectCounter) {
138                            pt_entry->indirectCounter--;
139                        } else {
140                            // Set this to false, to see if the new index
141                            // has any match
142                            pt_entry->increasedIndirectCounter = false;
143                        }
144
145                        // If the counter is high enough, start prefetching
146                        if (pt_entry->indirectCounter > prefetchThreshold) {
147                            unsigned distance = maxPrefetchDistance *
148                                pt_entry->indirectCounter.calcSaturation();
149                            for (int delta = 1; delta < distance; delta += 1) {
150                                Addr pf_addr = pt_entry->baseAddr +
151                                    (pt_entry->index << pt_entry->shift);
152                                addresses.push_back(AddrPriority(pf_addr, 0));
153                            }
154                        }
155                    }
156                }
157            }
158        } else {
159            pt_entry = prefetchTable.findVictim(pc);
160            assert(pt_entry != nullptr);
161            prefetchTable.insertEntry(pc, false /* unused */, pt_entry);
162            pt_entry->address = addr;
163            pt_entry->secure = is_secure;
164        }
165    }
166}
167
168void
169IndirectMemoryPrefetcher::allocateOrUpdateIPDEntry(
170    const PrefetchTableEntry *pt_entry, int64_t index)
171{
172    // The address of the pt_entry is used to index the IPD
173    Addr ipd_entry_addr = (Addr) pt_entry;
174    IndirectPatternDetectorEntry *ipd_entry = ipd.findEntry(ipd_entry_addr,
175                                                            false/* unused */);
176    if (ipd_entry != nullptr) {
177        ipd.accessEntry(ipd_entry);
178        if (!ipd_entry->secondIndexSet) {
179            // Second time we see an index, fill idx2
180            ipd_entry->idx2 = index;
181            ipd_entry->secondIndexSet = true;
182            ipdEntryTrackingMisses = ipd_entry;
183        } else {
184            // Third access! no pattern has been found so far,
185            // release the IPD entry
186            ipd_entry->reset();
187            ipdEntryTrackingMisses = nullptr;
188        }
189    } else {
190        ipd_entry = ipd.findVictim(ipd_entry_addr);
191        assert(ipd_entry != nullptr);
192        ipd.insertEntry(ipd_entry_addr, false /* unused */, ipd_entry);
193        ipd_entry->idx1 = index;
194        ipdEntryTrackingMisses = ipd_entry;
195    }
196}
197
198void
199IndirectMemoryPrefetcher::trackMissIndex1(Addr miss_addr)
200{
201    IndirectPatternDetectorEntry *entry = ipdEntryTrackingMisses;
202    // If the second index is not set, we are just filling the baseAddr
203    // vector
204    assert(entry->numMisses < entry->baseAddr.size());
205    std::vector<Addr> &ba_array = entry->baseAddr[entry->numMisses];
206    int idx = 0;
207    for (int shift : shiftValues) {
208        ba_array[idx] = miss_addr - (entry->idx1 << shift);
209        idx += 1;
210    }
211    entry->numMisses += 1;
212    if (entry->numMisses == entry->baseAddr.size()) {
213        // stop tracking misses once we have tracked enough
214        ipdEntryTrackingMisses = nullptr;
215    }
216}
217void
218IndirectMemoryPrefetcher::trackMissIndex2(Addr miss_addr)
219{
220    IndirectPatternDetectorEntry *entry = ipdEntryTrackingMisses;
221    // Second index is filled, compare the addresses generated during
222    // the previous misses (using idx1) against newly generated values
223    // using idx2, if a match is found, fill the additional fields
224    // of the PT entry
225    for (int midx = 0; midx < entry->numMisses; midx += 1)
226    {
227        std::vector<Addr> &ba_array = entry->baseAddr[midx];
228        int idx = 0;
229        for (int shift : shiftValues) {
230            if (ba_array[idx] == (miss_addr - (entry->idx2 << shift))) {
231                // Match found!
232                // Fill the corresponding pt_entry
233                PrefetchTableEntry *pt_entry =
234                    (PrefetchTableEntry *) entry->getTag();
235                pt_entry->baseAddr = ba_array[idx];
236                pt_entry->shift = shift;
237                pt_entry->enabled = true;
238                pt_entry->indirectCounter.reset();
239                // Release the current IPD Entry
240                entry->reset();
241                // Do not track more misses
242                ipdEntryTrackingMisses = nullptr;
243                return;
244            }
245            idx += 1;
246        }
247    }
248}
249
250void
251IndirectMemoryPrefetcher::checkAccessMatchOnActiveEntries(Addr addr)
252{
253    for (auto &pt_entry : prefetchTable) {
254        if (pt_entry.enabled) {
255            if (addr == pt_entry.baseAddr +
256                       (pt_entry.index << pt_entry.shift)) {
257                pt_entry.indirectCounter++;
258                pt_entry.increasedIndirectCounter = true;
259            }
260        }
261    }
262}
263
264IndirectMemoryPrefetcher*
265IndirectMemoryPrefetcherParams::create()
266{
267    return new IndirectMemoryPrefetcher(this);
268}
269