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