cache.c

用C语言来实现虚拟cache的操作

#include <stdio.h>
#include <stdlib.h>

#include "cache.h"
#include "config.h"
#include "misc.h"


char *
cache_policy(cache_t *cache)
{
   switch (cache->policy)
   {
      case LRU:    return "lru";
      case Random: return "rand";
      case FIFO:   return "fifo";
      default:     fatal("Unknown cache replacement policy");
                   break;
   }
}


enum cache_policy
cache_char2policy(char c)
{
  switch (c) 
  {
     case 'l': return LRU;
     case 'r': return Random;
     case 'f': return FIFO;
     default:  fatal("Bogus replacement policy, `%c'", c);
               break;
  }
}


void
cache_print_config(cache_t *cache)
{
   printf("Name:                  %s\n", cache->name);
   printf("Number of sets:        %d\n", cache->nsets);
   printf("Associativity:         %d\n", cache->assoc);
   printf("Block size:            %d\n", 1 << cache->log2_block_size);
   printf("Replacement policy:    %s\n", cache_policy(cache));
   printf("Miss penalty:          %d\n", MISS_PENALTY(1<<cache->log2_block_size));
   printf("\n");
}


void
cache_print_stats(cache_t *cache, double nrefs, double nhits, double nmisses, double time)
{
   double hit_rate = nhits/nrefs;
   double miss_rate = nmisses/nrefs;

   printf("Number of references: %.0f\n", nrefs);
   printf("Number of hits:       %.0f (%.3f%%)\n", nhits, 100*hit_rate);
   printf("Number of misses:     %.0f (%.3f%%)\n", nmisses, 100*miss_rate);
   printf("Total time:           %.0f cycles\n", time);
   printf("AMAT:                 %.3f cycles\n", time/nrefs);
   printf("\n");
}


void
cache_dump(cache_t *cache)
{
   cache_set_t          *set;
   cache_block_t        *blk;
   int                  i, j;

   printf("Set");
   for (i=0; i<cache->assoc; i++)
      printf(" Valid      Tag");
   printf("\n");
   
   for (i=0; i<cache->nsets; i++)
   {
      printf("%3d", i);
      set = &(cache->set[i]);
      blk = &(set->block[0]);
      for (j=0; j<cache->assoc; j++)
      {
         printf("%6d%9x", blk->valid, blk->tag);
         blk++;
      }
      printf("\n");
   }
}


cache_t *
cache_create(char *name, int nsets, int assoc, int block_size, enum cache_policy policy)
{
   cache_t		*cache;
   cache_set_t		*set;
   cache_block_t	*blk;
   int			i, j;

   cache = (cache_t *)malloc(sizeof(cache_t)); /*initialize the cache arguments*/

   cache->name = name;
   cache->nsets = nsets;
   cache->log2_nsets = log2(nsets);
   cache->assoc = assoc;
   cache->log2_block_size = log2(block_size);
   cache->policy = policy;
   cache->victim = NULL;

   cache->set = (cache_set_t *)malloc(nsets*sizeof(cache_set_t));  /*allocate space for 'nsets' sets*/
   for (i=0; i<nsets; i++)										/*in a cache*/	
   {
      set = &(cache->set[i]);	/*address of the first set*/
      set->block = (cache_block_t *)malloc(assoc*sizeof(cache_block_t)); /*allocate sapces for*/
      blk = &(set->block[0]);	/*address of the first block*/			/*'assoc' blocks in a set*/	
      for (j=0; j<assoc; j++)
      {
         blk->valid = FALSE;
         blk++;
      }
   }

   return cache;
}

   
/*
 * cache_locate returns a pointer to the block that contains
 * the data, or NULL if the requested block is not present
 */
cache_block_t *
cache_locate(cache_t *cache, unsigned address)
{
   cache_block_t 	*blk;
   cache_set_t 		*set;
   unsigned		idx, tag;
   int			i;

   idx = CACHE_IDX(cache, address);
   tag = CACHE_TAG(cache, address);

   set = &(cache->set[idx]);
   blk = &(set->block[0]);
   for (i=0; i<cache->assoc; i++)
   {
      if (blk->valid && blk->tag==tag)
      {
         return blk;
      }
      blk++;
   }

   /* not found */
   return NULL;
}


/*
 * cache_get_repl_block returns a pointer to the block that needs to
 * be replaced. This is where the replacement strategy is implemented.
 */
cache_block_t *
cache_get_repl_block(cache_t *cache, unsigned address)
{
   cache_set_t        	*set;
   cache_block_t      *blk, *min_blk;
   unsigned             	idx, tag;
   int				i;

   idx = CACHE_IDX(cache, address);
   tag = CACHE_TAG(cache, address);
   set = &(cache->set[idx]);

   /* First scan the cache set to see if there is an invalid block  */
   /* Simultaneously, find the blk with the smallest time attribute */
   min_blk = blk = &(set->block[0]);
   for (i=0; i<cache->assoc; i++, blk++)
   {
      if (!blk->valid)
      {
         return blk;
      }
      if (blk->time < min_blk->time)
         min_blk = blk;
   }

   /* all entries are valid */
   if (cache->policy == Random)
   {
      /* Note: associativity should be a power of 2 */
      i = rand() & (cache->assoc - 1);
      min_blk = &(set->block[i]);
   }

   return min_blk;
}


/*
 * Update the time stamp of a block
 */
void
cache_update_time(cache_t *cache, cache_block_t *blk, int current_time)
{
   switch (cache->policy)
   {
      case Random:
      case FIFO: /* nop */
                 break;
      case LRU:  blk->time = current_time;
                 break;
      default:   fatal("cache_update_time, unknown cache policy %d", cache->policy);
                 break;
   }
}


void
cache_sim(cache_t *cache, FILE *input)
{
   unsigned		nhits, nmisses, nrefs, cycle;
   unsigned		addr;
   cache_block_t	*blk;
   int				block_size = 1 << cache->log2_block_size;

   nhits = nmisses = nrefs = cycle = 0;

   while (fread(&addr, sizeof(unsigned), 1, input))
   {
         nrefs++;

         blk = cache_locate(cache, addr); /*returns a pointer to the block that contains the data*/

         if (blk) /* Hit */
         {
            nhits++;
            cache_update_time(cache, blk, cycle);
            cycle += HIT_TIME;
         }
         else /* Miss */
         {
            nmisses++;

            blk = cache_get_repl_block(cache, addr); /*returns a pointer to the block that needs to be repalced*/
            blk->valid 	= TRUE;
            blk->tag 	= CACHE_TAG(cache, addr);
            blk->time 	= cycle;					/* time brought to cache */

            cycle += MISS_PENALTY(block_size);
         }

#ifdef DEBUG
         cache_dump(cache);
#endif
   }			 /* end while */

   printf("CONVENTIONAL CACHE:\n");
   printf("Cache configuration:\n");
   cache_print_config(cache);
   cache_print_stats(cache, nrefs, nhits, nmisses, cycle);
   newline(2);
}