text: /*
   * Copyright (c) 2012-2013 ARM Limited
   * All rights reserved.
   *
   * The license below extends only to copyright in the software and shall
   * not be construed as granting a license to any other intellectual
   * property including but not limited to intellectual property relating
   * to a hardware implementation of the functionality of the software
   * licensed hereunder.  You may use the software subject to the license
   * terms below provided that you ensure that this notice is replicated
   * unmodified and in its entirety in all distributions of the software,
   * modified or unmodified, in source code or in binary form.
   *
   * Copyright (c) 2003-2005,2014 The Regents of The University of Michigan
   * 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: Erik Hallnor
   */
  
  /**
   * @file
   * Definitions of a LRU tag store.
   */
  
  #include "debug/CacheRepl.hh"
  #include "mem/cache/tags/lru.hh"
  #include "mem/cache/base.hh"
  
  LRU::LRU(const Params *p)
      : BaseSetAssoc(p)
  {
  }
  
  BaseSetAssoc::BlkType*
  LRU::accessBlock(Addr addr, bool is_secure, Cycles &lat, int master_id, PacketPtr pkt)
  {
      BlkType *blk = BaseSetAssoc::accessBlock(addr, is_secure, lat, master_id, pkt);
  
      if (blk != NULL) {
          // move this block to head of the MRU list
          sets[blk->set].moveToHead(blk);
          DPRINTF(CacheRepl, "set %x: moving blk %x (%s) to MRU\n",
                  blk->set, regenerateBlkAddr(blk->tag, blk->set),
                  is_secure ? "s" : "ns");
  
      }
  
      return blk;
  }
  
  BaseSetAssoc::BlkType*
  LRU::findVictim(Addr addr) const
  {
      int set = extractSet(addr);
      // grab a replacement candidate
      BlkType *blk = NULL;
      
      // return the LRU block if it is L1 cache or neither partitioning nor DM are enabled
      if (cache->getIsTopLevel() || cache->system->getWayPartMode() == 0)
          blk = sets[set].blks[assoc - 1];
      else if (cache->system->getWayPartMode() == 1) {
          goto way_part;
      }
      else {
          for (int i = assoc - 1; i >= 0; i--) {
              BlkType *b = sets[set].blks[i];
              if (((dmAssoc && b->way >= lowerWayNum && b->way <= upperWayNum) || !dmAssoc ) && !b->isDeterministic()) {
                  blk = b;
                  break;
              }
          }
          if (dmAssoc && blk == NULL) {
  way_part:
              for (int i = assoc - 1; i >= 0; i--) {
                  BlkType *b = sets[set].blks[i];
                  if (b->way >= lowerWayNum && b->way <= upperWayNum) {
                      blk = b;
                      break;
                  }
              }
          }
      }
  
      // assert(!blk || blk->way < allocAssoc);
      assert(blk != NULL);
  
      if (blk && blk->isValid() && !cache->getIsTopLevel()) {
          DPRINTF(CacheRepl, "set:%x way:%d DM:%d: selecting blk %x for replacement dmAssoc:%d L:%d U:%d\n",
                  set, blk->way, blk->isDeterministic(), regenerateBlkAddr(blk->tag, set), dmAssoc, lowerWayNum, upperWayNum);
      }
  
      /* if ( blk && blk->isDeterministic() && !cache->getIsTopLevel() )
      {
          DPRINTF(CacheRepl, "DM Repl:");
          for (int i = assoc - 1; i >= 0; i--) {
              BlkType *b = sets[set].blks[i];
              DPRINTF(CacheRepl, "%d:%d,%d ", i, b->way, b->isDeterministic());
          }
          DPRINTF(CacheRepl, "\n");
      } */
  
  
      return blk;
  }
  
  void
  LRU::insertBlock(PacketPtr pkt, BlkType *blk)
  {
      BaseSetAssoc::insertBlock(pkt, blk);
  
      int set = extractSet(pkt->getAddr());
      sets[set].moveToHead(blk);
  }
  
  void
  LRU::invalidate(BlkType *blk)
  {
      BaseSetAssoc::invalidate(blk);
  
      // should be evicted before valid blocks
      int set = blk->set;
      sets[set].moveToTail(blk);
  }
  
  LRU*
  LRUParams::create()
  {
      return new LRU(this);
  }
  