/**
 * Copyright (c) 2019 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.
 *
 * Authors: Javier Bueno
 */

#include "mem/cache/prefetch/spatio_temporal_memory_streaming.hh"

#include "debug/HWPrefetch.hh"
#include "mem/cache/prefetch/associative_set_impl.hh"
#include "params/STeMSPrefetcher.hh"

STeMSPrefetcher::STeMSPrefetcher(const STeMSPrefetcherParams *p)
  : QueuedPrefetcher(p), spatialRegionSize(p->spatial_region_size),
    spatialRegionSizeBits(floorLog2(p->spatial_region_size)),
    reconstructionEntries(p->reconstruction_entries),
    activeGenerationTable(p->active_generation_table_assoc,
                          p->active_generation_table_entries,
                          p->active_generation_table_indexing_policy,
                          p->active_generation_table_replacement_policy,
                          ActiveGenerationTableEntry(
                              spatialRegionSize / blkSize)),
    patternSequenceTable(p->pattern_sequence_table_assoc,
                         p->pattern_sequence_table_entries,
                         p->pattern_sequence_table_indexing_policy,
                         p->pattern_sequence_table_replacement_policy,
                         ActiveGenerationTableEntry(
                             spatialRegionSize / blkSize)),
    rmob(p->region_miss_order_buffer_entries), rmobHead(0)
{
    fatal_if(!isPowerOf2(spatialRegionSize),
        "The spatial region size must be a power of 2.");
}

void
STeMSPrefetcher::checkForActiveGenerationsEnd() {
    // This prefetcher operates attached to the L1 and it observes all
    // accesses, this guarantees that no evictions are missed

    // Iterate over all entries, if any recorded cacheline has been evicted,
    // the generation finishes, move the entry to the PST
    for (auto &agt_entry : activeGenerationTable) {
        if (agt_entry.isValid()) {
            bool generation_ended = false;
            bool sr_is_secure = agt_entry.isSecure();
            for (auto &seq_entry : agt_entry.sequence) {
                if (seq_entry.counter > 0) {
                    Addr cache_addr =
                        agt_entry.paddress + seq_entry.offset * blkSize;
                    if (!inCache(cache_addr, sr_is_secure) &&
                            !inMissQueue(cache_addr, sr_is_secure)) {
                        generation_ended = true;
                        break;
                    }
                }
            }
            if (generation_ended) {
                // PST is indexed using the PC (secure bit is unused)
                ActiveGenerationTableEntry *pst_entry =
                    patternSequenceTable.findEntry(agt_entry.pc,
                                                   false /*unused*/);
                if (pst_entry == nullptr) {
                    // Tipically an entry will not exist
                    pst_entry = patternSequenceTable.findVictim(agt_entry.pc);
                    assert(pst_entry != nullptr);
                    patternSequenceTable.insertEntry(agt_entry.pc,
                            false /*unused*/, pst_entry);
                } else {
                    patternSequenceTable.accessEntry(pst_entry);
                }
                // If the entry existed, this will update the values, if not,
                // this also sets the values of the entry
                pst_entry->update(agt_entry);
                // Free the AGT entry
                agt_entry.setInvalid();
            }
        }
    }
}

void
STeMSPrefetcher::addToRMOB(Addr sr_addr, Addr pst_addr, unsigned int delta)
{
    RegionMissOrderBufferEntry &rmob_entry = rmob[rmobHead];
    rmobHead = (rmobHead + 1) % rmob.size();

    rmob_entry.srAddress = sr_addr;
    rmob_entry.pstAddress = pst_addr;
    rmob_entry.delta = delta;
    rmob_entry.valid = true;
}

void
STeMSPrefetcher::calculatePrefetch(const PrefetchInfo &pfi,
                                   std::vector<AddrPriority> &addresses)
{
    if (!pfi.hasPC()) {
        DPRINTF(HWPrefetch, "Ignoring request with no PC.\n");
        return;
    }

    Addr pc = pfi.getPC();
    bool is_secure = pfi.isSecure();
    // Spatial region address
    Addr sr_addr = pfi.getAddr() / spatialRegionSize;
    Addr paddr = pfi.getPaddr();

    // Offset in cachelines within the spatial region
    Addr sr_offset = (pfi.getAddr() % spatialRegionSize) / blkSize;

    // Check if any active generation has ended
    checkForActiveGenerationsEnd();

    ActiveGenerationTableEntry *agt_entry =
        activeGenerationTable.findEntry(sr_addr, is_secure);
    if (agt_entry != nullptr) {
        // found an entry in the AGT, entry is currently being recorded,
        // add the offset
        activeGenerationTable.accessEntry(agt_entry);
        agt_entry->addOffset(sr_offset);
        lastTriggerCounter += 1;
    } else {
        // Not found, this is the first access (Trigger access)

        // Add entry to RMOB
        Addr pst_addr = (pc << spatialRegionSizeBits) + sr_offset;
        addToRMOB(sr_addr, pst_addr, lastTriggerCounter);
        // Reset last trigger counter
        lastTriggerCounter = 0;

        // allocate a new AGT entry
        agt_entry = activeGenerationTable.findVictim(sr_addr);
        assert(agt_entry != nullptr);
        activeGenerationTable.insertEntry(sr_addr, is_secure, agt_entry);
        agt_entry->pc = pc;
        agt_entry->paddress = paddr;
        agt_entry->addOffset(sr_offset);
    }
    // increase the seq Counter for other entries
    for (auto &agt_e : activeGenerationTable) {
        if (agt_e.isValid() && agt_entry != &agt_e) {
            agt_e.seqCounter += 1;
        }
    }

    // Prefetch generation: if this is a miss, search for the most recent
    // entry in the RMOB, and reconstruct the registered access sequence
    if (pfi.isCacheMiss()) {
        for (unsigned int idx = (rmobHead - 1) % rmob.size();
             idx != rmobHead && rmob[idx].valid;
             idx = (idx - 1) % rmob.size())
        {
            if (rmob[idx].srAddress == sr_addr) {
                // reconstruct the access sequence
                reconstructSequence(idx, addresses);
                break;
            }
        }
    }
}

void
STeMSPrefetcher::reconstructSequence(unsigned int rmob_idx,
    std::vector<AddrPriority> &addresses)
{
    std::vector<Addr> reconstruction(reconstructionEntries, MaxAddr);
    unsigned int idx = 0;
    // process rmob entries from rmob_idx (most recent with
    // address = sr_addr) to the last one (rmobHead)
    for (int i = rmob_idx;
         i != rmobHead && idx < reconstructionEntries;
         i = (i + 1) % rmob.size())
    {
        reconstruction[idx] = rmob[i].srAddress * spatialRegionSize;
        unsigned int next_i = (i + 1) % rmob.size();
        idx += rmob[next_i].delta + 1;
    }
    // Now query the PST with the PC of each RMOB entry
    idx = 0;
    for (int i = rmob_idx;
         i != rmobHead && idx < reconstructionEntries;
         i = (i + 1) % rmob.size())
    {
        ActiveGenerationTableEntry *pst_entry =
            patternSequenceTable.findEntry(rmob[i].pstAddress,
                                           false /* unused */);
        if (pst_entry != nullptr) {
            patternSequenceTable.accessEntry(pst_entry);
            for (auto &seq_entry : pst_entry->sequence) {
                if (seq_entry.counter > 1) {
                    // 3-bit counter: high enough confidence with a
                    // value greater than 1
                    Addr rec_addr = rmob[i].srAddress * spatialRegionSize +
                        seq_entry.offset;
                    unsigned ridx = idx + seq_entry.delta;
                    // Try to use the corresponding position, if it has been
                    // already used, look the surrounding positions
                    if (ridx < reconstructionEntries &&
                        reconstruction[ridx] == MaxAddr) {
                        reconstruction[ridx] = rec_addr;
                    } else if ((ridx + 1) < reconstructionEntries &&
                        reconstruction[ridx + 1] == MaxAddr) {
                        reconstruction[ridx + 1] = rec_addr;
                    } else if ((ridx + 2) < reconstructionEntries &&
                        reconstruction[ridx + 2] == MaxAddr) {
                        reconstruction[ridx + 2] = rec_addr;
                    } else if ((ridx > 0) &&
                        ((ridx - 1) < reconstructionEntries) &&
                        reconstruction[ridx - 1] == MaxAddr) {
                        reconstruction[ridx - 1] = rec_addr;
                    } else if ((ridx > 1) &&
                        ((ridx - 2) < reconstructionEntries) &&
                        reconstruction[ridx - 2] == MaxAddr) {
                        reconstruction[ridx - 2] = rec_addr;
                    }
                }
            }
        }
        unsigned int next_i = (i + 1) % rmob.size();
        idx += rmob[next_i].delta + 1;
    }
    for (Addr pf_addr : reconstruction) {
        if (pf_addr != MaxAddr) {
            addresses.push_back(AddrPriority(pf_addr, 0));
        }
    }
}

STeMSPrefetcher *
STeMSPrefetcherParams::create()
{
   return new STeMSPrefetcher(this);
}