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

   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  *          Steve Reinhardt
  30  */
  31
  32 /**
  33  * @file
  34  * Definitions of the Generational replacement policy.
  35  */
  36
  37 #include <string>
  38
  39 #include "base/misc.hh"
  40 #include "mem/cache/tags/iic.hh"
  41 #include "mem/cache/tags/repl/gen.hh"
  42 #include "params/GenRepl.hh"
  43 #include "sim/host.hh"
  44
  45 using namespace std;
  46
  47 GenRepl::GenRepl(const string &_name,
  48                  int _num_pools,
  49                  int _fresh_res,
  50                  int _pool_res) // fix this, should be set by cache
  51     : Repl(_name)
  52 {
  53     num_pools = _num_pools;
  54     fresh_res = _fresh_res;
  55     pool_res = _pool_res;
  56     num_entries = 0;
  57     num_pool_entries = 0;
  58     misses = 0;
  59     pools = new GenPool[num_pools+1];
  60 }
  61
  62 GenRepl::~GenRepl()
  63 {
  64     delete [] pools;
  65 }
  66
  67 unsigned long
  68 GenRepl::getRepl()
  69 {
  70     unsigned long tmp;
  71     GenReplEntry *re;
  72     int i;
  73     int num_seen = 0;
  74     if (!(num_pool_entries>0)) {
  75         fatal("No blks available to replace");
  76     }
  77     num_entries--;
  78     num_pool_entries--;
  79     for (i = 0; i < num_pools; i++) {
  80         while ((re = pools[i].pop())) {
  81             num_seen++;
  82             // Remove invalidated entries
  83             if (!re->valid) {
  84                 delete re;
  85                 continue;
  86             }
  87             if (iic->clearRef(re->tag_ptr)) {
  88                 pools[(((i+1)== num_pools)? i :i+1)].push(re, misses);
  89             }
  90             else {
  91                 tmp = re->tag_ptr;
  92                 delete re;
  93
  94                 repl_pool.sample(i);
  95
  96                 return tmp;
  97             }
  98         }
  99     }
 100     fatal("No replacement found");
 101     return 0xffffffff;
 102 }
 103
 104 unsigned long *
 105 GenRepl::getNRepl(int n)
 106 {
 107     unsigned long *tmp;
 108     GenReplEntry *re;
 109     int i;
 110     if (!(num_pool_entries>(n-1))) {
 111         fatal("Not enough blks available to replace");
 112     }
 113     num_entries -= n;
 114     num_pool_entries -= n;
 115     tmp = new unsigned long[n]; /* array of cache_blk pointers */
 116     int blk_index = 0;
 117     for (i = 0; i < num_pools && blk_index < n; i++) {
 118         while (blk_index < n && (re = pools[i].pop())) {
 119             // Remove invalidated entries
 120             if (!re->valid) {
 121                 delete re;
 122                 continue;
 123             }
 124             if (iic->clearRef(re->tag_ptr)) {
 125                 pools[(((i+1)== num_pools)? i :i+1)].push(re, misses);
 126             }
 127             else {
 128                 tmp[blk_index] = re->tag_ptr;
 129                 blk_index++;
 130                 delete re;
 131                 repl_pool.sample(i);
 132             }
 133         }
 134     }
 135     if (blk_index >= n)
 136         return tmp;
 137     /* search the fresh pool */
 138
 139     fatal("No N  replacements found");
 140     return NULL;
 141 }
 142
 143 void
 144 GenRepl::doAdvance(std::list<unsigned long> &demoted)
 145 {
 146     int i;
 147     int num_seen = 0;
 148     GenReplEntry *re;
 149     misses++;
 150     for (i=0; i<num_pools; i++) {
 151         while (misses-pools[i].oldest > pool_res && (re = pools[i].pop())!=NULL) {
 152             if (iic->clearRef(re->tag_ptr)) {
 153                 pools[(((i+1)== num_pools)? i :i+1)].push(re, misses);
 154                 /** @todo Not really demoted, but use it for now. */
 155                 demoted.push_back(re->tag_ptr);
 156                 advance_pool.sample(i);
 157             }
 158             else {
 159                 pools[(((i-1)<0)?i:i-1)].push(re, misses);
 160                 demoted.push_back(re->tag_ptr);
 161                 demote_pool.sample(i);
 162             }
 163         }
 164         num_seen += pools[i].size;
 165     }
 166     while (misses-pools[num_pools].oldest > fresh_res
 167           && (re = pools[num_pools].pop())!=NULL) {
 168         num_pool_entries++;
 169         if (iic->clearRef(re->tag_ptr)) {
 170             pools[num_pools/2].push(re, misses);
 171             /** @todo Not really demoted, but use it for now. */
 172             demoted.push_back(re->tag_ptr);
 173             advance_pool.sample(num_pools);
 174         }
 175         else {
 176             pools[num_pools/2-1].push(re, misses);
 177             demoted.push_back(re->tag_ptr);
 178             demote_pool.sample(num_pools);
 179         }
 180     }
 181 }
 182
 183 void*
 184 GenRepl::add(unsigned long tag_index)
 185 {
 186     GenReplEntry *re = new GenReplEntry;
 187     re->tag_ptr = tag_index;
 188     re->valid = true;
 189     pools[num_pools].push(re, misses);
 190     num_entries++;
 191     return (void*)re;
 192 }
 193
 194 void
 195 GenRepl::regStats(const string name)
 196 {
 197     using namespace Stats;
 198
 199     /** GEN statistics */
 200     repl_pool
 201         .init(0, 16, 1)
 202         .name(name + ".repl_pool_dist")
 203         .desc("Dist. of Repl. across pools")
 204         .flags(pdf)
 205         ;
 206
 207     advance_pool
 208         .init(0, 16, 1)
 209         .name(name + ".advance_pool_dist")
 210         .desc("Dist. of Repl. across pools")
 211         .flags(pdf)
 212         ;
 213
 214     demote_pool
 215         .init(0, 16, 1)
 216         .name(name + ".demote_pool_dist")
 217         .desc("Dist. of Repl. across pools")
 218         .flags(pdf)
 219         ;
 220 }
 221
 222 int
 223 GenRepl::fixTag(void* _re, unsigned long old_index, unsigned long new_index)
 224 {
 225     GenReplEntry *re = (GenReplEntry*)_re;
 226     assert(re->valid);
 227     if (re->tag_ptr == old_index) {
 228         re->tag_ptr = new_index;
 229         return 1;
 230     }
 231     fatal("Repl entry: tag ptrs do not match");
 232     return 0;
 233 }
 234
 235 bool
 236 GenRepl::findTagPtr(unsigned long index)
 237 {
 238     for (int i = 0; i < num_pools + 1; ++i) {
 239         list<GenReplEntry*>::const_iterator iter = pools[i].entries.begin();
 240         list<GenReplEntry*>::const_iterator end = pools[i].entries.end();
 241         for (; iter != end; ++iter) {
 242             if ((*iter)->valid && (*iter)->tag_ptr == index) {
 243                 return true;
 244             }
 245         }
 246     }
 247     return false;
 248 }
 249
 250 GenRepl *
 251 GenReplParams::create()
 252 {
 253     return new GenRepl(name, num_pools, fresh_res, pool_res);
 254 }