src/mem/cache/tags/repl/gen.hh

   1 /*
   2  * Copyright (c) 2002-2005 The Regents of The University of Michigan
   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: Erik Hallnor
  29  */
  30
  31 /**
  32  * @file
  33  * Declarations of generational replacement policy
  34  */
  35
  36 #ifndef ___GEN_HH__
  37 #define __GEN_HH__
  38
  39 #include <list>
  40
  41 #include "base/statistics.hh"
  42 #include "mem/cache/tags/repl/repl.hh"
  43
  44 /**
  45  * Generational Replacement entry.
  46  */
  47 class GenReplEntry
  48 {
  49   public:
  50     /** Valid flag, used to quickly invalidate bogus entries. */
  51     bool valid;
  52     /** The difference between this entry and the previous in the pool. */
  53     int delta;
  54     /** Pointer to the corresponding tag in the IIC. */
  55     unsigned long tag_ptr;
  56 };
  57
  58 /**
  59  * Generational replacement pool
  60  */
  61 class GenPool
  62 {
  63   public:
  64     /** The time the last entry was added. */
  65     Tick newest;
  66     /** The time the oldest entry was added. */
  67     Tick oldest;
  68     /** List of the replacement entries in this pool. */
  69     std::list<GenReplEntry*> entries;
  70
  71     /** The number of entries in this pool. */
  72     int size;
  73
  74     /**
  75      * Simple constructor.
  76      */
  77     GenPool() {
  78         newest = 0;
  79         oldest = 0;
  80         size = 0;
  81     }
  82
  83     /**
  84      * Add an entry to this pool.
  85      * @param re The entry to add.
  86      * @param now The current time.
  87      */
  88     void push(GenReplEntry *re, Tick now) {
  89         ++size;
  90         if (!entries.empty()) {
  91             re->delta = now - newest;
  92             newest = now;
  93         } else {
  94             re->delta = 0;
  95             newest = oldest = now;
  96         }
  97         entries.push_back(re);
  98     }
  99
 100     /**
 101      * Remove an entry from the pool.
 102      * @return The entry at the front of the list.
 103      */
 104     GenReplEntry* pop() {
 105         GenReplEntry *tmp = NULL;
 106         if (!entries.empty()) {
 107             --size;
 108             tmp = entries.front();
 109             entries.pop_front();
 110             oldest += tmp->delta;
 111         }
 112         return tmp;
 113     }
 114
 115     /**
 116      * Return the entry at the front of the list.
 117      * @return the entry at the front of the list.
 118      */
 119     GenReplEntry* top() {
 120         return entries.front();
 121     }
 122
 123     /**
 124      * Destructor.
 125      */
 126     ~GenPool() {
 127         while (!entries.empty()) {
 128             GenReplEntry *tmp = entries.front();
 129             entries.pop_front();
 130             delete tmp;
 131         }
 132     }
 133 };
 134
 135 /**
 136  * Generational replacement policy for use with the IIC.
 137  * @todo update to use STL and for efficiency
 138  */
 139 class GenRepl : public Repl
 140 {
 141   public:
 142     /** The array of pools. */
 143     GenPool *pools;
 144     /** The number of pools. */
 145     int num_pools;
 146     /** The amount of time to stay in the fresh pool. */
 147     int fresh_res;
 148     /** The amount of time to stay in the normal pools. */
 149     int pool_res;
 150     /** The maximum number of entries */
 151     int num_entries;
 152     /** The number of entries currently in the pools. */
 153     int num_pool_entries;
 154     /** The number of misses. Used as the internal time. */
 155     Tick misses;
 156
 157     // Statistics
 158
 159     /**
 160      * @addtogroup CacheStatistics
 161      * @{
 162      */
 163     /** The number of replacements from each pool. */
 164     Stats::Distribution<> repl_pool;
 165     /** The number of advances out of each pool. */
 166     Stats::Distribution<> advance_pool;
 167     /** The number of demotions from each pool. */
 168     Stats::Distribution<> demote_pool;
 169     /**
 170      * @}
 171      */
 172
 173     /**
 174      * Constructs and initializes this replacement policy.
 175      * @param name The name of the policy.
 176      * @param num_pools The number of pools to use.
 177      * @param fresh_res The amount of time to wait in the fresh pool.
 178      * @param pool_res The amount of time to wait in the normal pools.
 179      */
 180     GenRepl(const std::string &name, int num_pools,
 181             int fresh_res, int pool_res);
 182
 183     /**
 184      * Destructor.
 185      */
 186     ~GenRepl();
 187
 188     /**
 189      * Returns the tag pointer of the cache block to replace.
 190      * @return The tag to replace.
 191      */
 192     virtual unsigned long getRepl();
 193
 194     /**
 195      * Return an array of N tag pointers to replace.
 196      * @param n The number of tag pointer to return.
 197      * @return An array of tag pointers to replace.
 198      */
 199     virtual unsigned long *getNRepl(int n);
 200
 201     /**
 202      * Update replacement data
 203      */
 204     virtual void doAdvance(std::list<unsigned long> &demoted);
 205
 206     /**
 207      * Add a tag to the replacement policy and return a pointer to the
 208      * replacement entry.
 209      * @param tag_index The tag to add.
 210      * @return The replacement entry.
 211      */
 212     virtual void* add(unsigned long tag_index);
 213
 214     /**
 215      * Register statistics.
 216      * @param name The name to prepend to statistic descriptions.
 217      */
 218     virtual void regStats(const std::string name);
 219
 220     /**
 221      * Update the tag pointer to when the tag moves.
 222      * @param re The replacement entry of the tag.
 223      * @param old_index The old tag pointer.
 224      * @param new_index The new tag pointer.
 225      * @return 1 if successful, 0 otherwise.
 226      */
 227     virtual int fixTag(void *re, unsigned long old_index,
 228                        unsigned long new_index);
 229
 230     /**
 231      * Remove this entry from the replacement policy.
 232      * @param re The replacement entry to remove
 233      */
 234     virtual void removeEntry(void *re)
 235     {
 236         ((GenReplEntry*)re)->valid = false;
 237     }
 238
 239   protected:
 240     /**
 241      * Debug function to verify that there is only one repl entry per tag.
 242      * @param index The tag index to check.
 243      */
 244     bool findTagPtr(unsigned long index);
 245 };
 246
 247 #endif /* __GEN_HH__ */