title: Cache Simulator
body: <p>I am writing a cache simulator. The idea is to given an input file with commands, trace the results of that input simulating cache functions so that we can keep track of cache hits and misses. I have written the following code but seem to be having trouble getting the proper output. I am posting my whole code because I dont want to make assumptions about where the problem may lie. Can anyone tell where I am making a mistake?</p>
  
  <pre><code>#include &lt;stdlib.h&gt;
  #include &lt;stdio.h&gt;
  #include &lt;getopt.h&gt;
  #include &lt;strings.h&gt;
  
  #include "cachelab.h"
  
  /* Always use a 64-bit variable to hold memory addresses*/
  typedef unsigned long long int mem_addr_t;
  
  /* a struct that groups cache parameters together */
  typedef struct {
      int s; /* 2**s cache sets */
      int b; /* cacheline block size 2**b bytes */
      int E; /* number of cachelines per set */
      int S; /* number of sets, derived from S = 2**s */
      int B; /* cacheline block size (bytes), derived from B = 2**b */
  } cache_param_t;
  
  int verbosity;
  
  /*
   * printUsage - Print usage info
   */
  void printUsage(char* argv[])
  {
      printf("Usage: %s [-hv] -s &lt;num&gt; -E &lt;num&gt; -b &lt;num&gt; -t &lt;file&gt;\n", argv[0]);
      printf("Options:\n");
      printf("  -h         Print this help message.\n");
      printf("  -v         Optional verbose flag.\n");
      printf("  -s &lt;num&gt;   Number of set index bits.\n");
      printf("  -E &lt;num&gt;   Number of lines per set.\n");
      printf("  -b &lt;num&gt;   Number of block offset bits.\n");
      printf("  -t &lt;file&gt;  Trace file.\n");
      printf("\nExamples:\n");
      printf("  %s -s 4 -E 1 -b 4 -t traces/yi.trace\n", argv[0]);
      printf("  %s -v -s 8 -E 2 -b 4 -t traces/yi.trace\n", argv[0]);
      exit(0);
  }
  
  int main(int argc, char **argv)
  {
  
      cache_param_t par;
      bzero(&amp;par, sizeof(par));
  
      char *trace_file;
      char c;
      while( (c=getopt(argc,argv,"s:E:b:t:vh")) != -1){
          switch(c){
          case 's':
              par.s = atoi(optarg);
              break;
          case 'E':
              par.E = atoi(optarg);
              break;
          case 'b':
              par.b = atoi(optarg);
              break;
          case 't':
              trace_file = optarg;
              break;
          case 'v':
              verbosity = 1;
              break;
          case 'h':
              printUsage(argv);
              exit(0);
          default:
              printUsage(argv);
              exit(1);
          }
      }
  
      if (par.s == 0 || par.E == 0 || par.b == 0 || trace_file == NULL) {
          printf("%s: Missing required command line argument\n", argv[0]);
          printUsage(argv);
          exit(1);
      }
  
      /* TODO: Compute S and B based on information passed in */
  
      //Compute S and B, 2^s and 2^b respectively
      par.S = (1 &lt;&lt; par.s);
      par.B = (1 &lt;&lt; par.b);
  
      /* TODO: Initialize a cache */
  
      //Structure for a line
      typedef struct {
        int valid;
        mem_addr_t tag;
        int timestamp;
      } line_st;
  
      //Structure for a set; a pointer to an array of lines
      typedef struct {
        line_st *lines;
      } cache_set;
  
      //Structure for a cache; a pointer to an array of sets
      typedef struct {
        cache_set *sets;
      } cache_t;
  
      //allocate space for sets and for lines
      cache_t cache;
      cache.sets = malloc(par.S * sizeof(cache_set));
      for (int i = 0; i &lt; par.S; i++) {
        cache.sets[i].lines = malloc(sizeof(line_st) * par.E);
      }
  
      //counters
      int hit_count = 0;
      int miss_count = 0;
      int eviction_count = 0;
  
      /* TODO: Run the trace simulation */
  
      char act; //L,S,M
      int size; //size read in from file
      int TSTAMP = 0; //value for LRU
      int empty = -1; //index of empty space
      int H = 0; //is there a hit
      int E = 0; //is there an eviction
      int toEvict = 0; //keeps track of what to evict
      mem_addr_t addr;
  
      //open the file and read it in
      FILE * traceFile = fopen(trace_file, "r");
      if (traceFile != NULL) {
  
        //keep going while we have additional lines
        //while(feof(traceFile) == 0) {
          while(fscanf(traceFile, " %c %llx,%d", &amp;act, &amp;addr, &amp;size) == 3){
          if (act != 'I') {
          //read the next line and look for string formated as " %c %llx,%d"
  
          //sscanf(traceFile, " %c %llx,%d", &amp;act, &amp;addr, &amp;size);
          //fscanf(traceFile, " %c %llx,%d", &amp;act, &amp;addr, &amp;size);
  
          //calculate address tag and set index
          mem_addr_t addr_tag = addr &gt;&gt; (par.s + par.b);
          int tag_size = (64 - (par.s + par.b));
          unsigned long long temp = addr &lt;&lt; (tag_size);
          unsigned long long setid = temp &gt;&gt; (tag_size + par.b);
  
          //unsigned long long setid = ((addr &gt;&gt; par.b) &amp; (par.S - 1));
          cache_set set = cache.sets[setid];
          int low = par.E + 1;
          for(int e = 0; e &lt; par.E; e++) {
            if (set.lines[e].valid == 0) {
          empty = e;
            }
            else if (set.lines[e].valid == 1){
          if (TSTAMP &lt; low) {
            low = TSTAMP;
            toEvict = e;
          }
          if (set.lines[e].tag == addr_tag) {
            hit_count++;
            H = 1;
            set.lines[e].timestamp = TSTAMP;
            TSTAMP++;
          }
            }
          }
          //if we have a miss
          if (H != 1){
            miss_count++;
            //if we have an empty line
            if (empty &gt; -1) {
          set.lines[empty].valid = 1;
          set.lines[empty].tag = addr_tag;
          set.lines[empty].timestamp = TSTAMP;
          TSTAMP++;
            }
            //if the set is full we need to evict
            else if (empty &lt; 0) {
          E = 1;
          set.lines[toEvict].tag = addr_tag;
          set.lines[toEvict].timestamp = TSTAMP;
          eviction_count++;
            }
          }
          //if the instruction is M, we will always get a hit
          if (act == 'M') {
            hit_count++;
          }
          //if the -v flag is set print out all debug information
          if (verbosity == 1) {
            printf("%c ", act);
            //printf("%llx,%d ", addr_tag, setid);
            printf("%llx,%d ", addr, size);
            if (H == 1) {
          printf("Hit ");
            }
            else if (H != 1) {
          printf("Miss ");
            }
            if (E == 1) {
          printf("Eviction ");
            }
            if (act == 'M') {
          printf("Hit ");
            }
            printf("\n");
          }
          empty = -1;
          H = 0;
          E = 0;
        }
        }
      }
  
      /* TODO: Clean up cache resources */
  
      /* TODO: Print out real results */
      printSummary(hit_count, miss_count, eviction_count);
      return 0;
  }
  </code></pre>
  
  <p>I am running my code with the following sample input:</p>
  
  <pre><code> S 00600aa0,1
   S 7ff000384,4
   L 7ff000384,4
   L 7ff000384,4
   L 00600a20,4
   L 7ff000384,4
  </code></pre>
  
  <p>My code produces the following result:</p>
  
  <pre><code>./ -v -s 2 -E 2 -b 3 -t traces/test.trace
  S 600aa0,1 Miss 
  S 7ff000384,4 Miss 
  L 7ff000384,4 Hit 
  L 7ff000384,4 Hit 
  L 600a20,4 Miss Eviction 
  L 7ff000384,4 Miss Eviction 
  hits:2 misses:4 evictions:2
  </code></pre>
  
  <p>but this is what it should be producing:</p>
  
  <pre><code>./ -v -s 2 -E 2 -b 3 -t traces/test.trace
  S 600aa0,1 miss 
  S 7ff000384,4 miss 
  L 7ff000384,4 hit 
  L 7ff000384,4 hit 
  L 600a20,4 miss eviction 
  L 7ff000384,4 hit 
  hits:3 misses:3 evictions:1
  </code></pre>
  
  <p>Can anyone tell what I am doing wrong?</p>
  
  <p>EDIT:</p>
  
  <p>Second test file:</p>
  
  <pre><code> S 00600aa0,1
  I  004005b6,5
  I  004005bb,5
  I  004005c0,5
   S 7ff000398,8
  I  0040051e,1
   S 7ff000390,8
  I  0040051f,3
  I  00400522,4
   S 7ff000378,8
  I  00400526,4
   S 7ff000370,8
  I  0040052a,7
   S 7ff000384,4
  I  00400531,2
  I  00400581,4
   L 7ff000384,4
  I  00400585,2
  I  00400533,7
   S 7ff000388,4
  I  0040053a,2
  I  00400577,4
   L 7ff000388,4
  I  0040057b,2
  I  0040053c,3
   L 7ff000384,4
  I  0040053f,2
  I  00400541,4
  I  00400545,3
  I  00400548,4
   L 7ff000378,8
  I  0040054c,3
   L 7ff000388,4
  I  0040054f,2
  I  00400551,3
   L 00600a20,4
  I  00400554,3
   S 7ff00038c,4
  I  00400557,3
   L 7ff000388,4
  I  0040055a,2
  I  0040055c,4
  I  00400560,3
  I  00400563,4
   L 7ff000370,8
  I  00400567,3
   L 7ff000384,4
  I  0040056a,3
  I  0040056d,3
   L 7ff00038c,4
  I  00400570,3
   S 00600a60,4
  I  00400573,4
   M 7ff000388,4
  I  00400577,4
   L 7ff000388,4
  I  0040057b,2
  I  0040053c,3
   L 7ff000384,4
  I  0040053f,2
  I  00400541,4
  I  00400545,3
  I  00400548,4
   L 7ff000378,8
  I  0040054c,3
   L 7ff000388,4
  I  0040054f,2
  I  00400551,3
   L 00600a24,4
  I  00400554,3
   S 7ff00038c,4
  I  00400557,3
   L 7ff000388,4
  I  0040055a,2
  I  0040055c,4
  I  00400560,3
  I  00400563,4
   L 7ff000370,8
  I  00400567,3
   L 7ff000384,4
  I  0040056a,3
  I  0040056d,3
   L 7ff00038c,4
  I  00400570,3
   S 00600a70,4
  I  00400573,4
   M 7ff000388,4
  I  00400577,4
   L 7ff000388,4
  I  0040057b,2
  I  0040053c,3
   L 7ff000384,4
  I  0040053f,2
  I  00400541,4
  I  00400545,3
  I  00400548,4
   L 7ff000378,8
  I  0040054c,3
   L 7ff000388,4
  I  0040054f,2
  I  00400551,3
   L 00600a28,4
  I  00400554,3
   S 7ff00038c,4
  I  00400557,3
   L 7ff000388,4
  I  0040055a,2
  I  0040055c,4
  I  00400560,3
  I  00400563,4
   L 7ff000370,8
  I  00400567,3
   L 7ff000384,4
  I  0040056a,3
  I  0040056d,3
   L 7ff00038c,4
  I  00400570,3
   S 00600a80,4
  I  00400573,4
   M 7ff000388,4
  I  00400577,4
   L 7ff000388,4
  I  0040057b,2
  I  0040053c,3
   L 7ff000384,4
  I  0040053f,2
  I  00400541,4
  I  00400545,3
  I  00400548,4
   L 7ff000378,8
  I  0040054c,3
   L 7ff000388,4
  I  0040054f,2
  I  00400551,3
   L 00600a2c,4
  I  00400554,3
   S 7ff00038c,4
  I  00400557,3
   L 7ff000388,4
  I  0040055a,2
  I  0040055c,4
  I  00400560,3
  I  00400563,4
   L 7ff000370,8
  I  00400567,3
   L 7ff000384,4
  I  0040056a,3
  I  0040056d,3
   L 7ff00038c,4
  I  00400570,3
   S 00600a90,4
  I  00400573,4
   M 7ff000388,4
  I  00400577,4
   L 7ff000388,4
  I  0040057b,2
  I  0040057d,4
   M 7ff000384,4
  I  00400581,4
   L 7ff000384,4
  I  00400585,2
  I  00400533,7
   S 7ff000388,4
  I  0040053a,2
  I  00400577,4
   L 7ff000388,4
  I  0040057b,2
  I  0040053c,3
   L 7ff000384,4
  I  0040053f,2
  I  00400541,4
  I  00400545,3
  I  00400548,4
   L 7ff000378,8
  I  0040054c,3
   L 7ff000388,4
  I  0040054f,2
  I  00400551,3
   L 00600a30,4
  I  00400554,3
   S 7ff00038c,4
  I  00400557,3
   L 7ff000388,4
  I  0040055a,2
  I  0040055c,4
  I  00400560,3
  I  00400563,4
   L 7ff000370,8
  I  00400567,3
   L 7ff000384,4
  I  0040056a,3
  I  0040056d,3
   L 7ff00038c,4
  I  00400570,3
   S 00600a64,4
  I  00400573,4
   M 7ff000388,4
  I  00400577,4
   L 7ff000388,4
  I  0040057b,2
  I  0040053c,3
   L 7ff000384,4
  I  0040053f,2
  I  00400541,4
  I  00400545,3
  I  00400548,4
   L 7ff000378,8
  I  0040054c,3
   L 7ff000388,4
  I  0040054f,2
  I  00400551,3
   L 00600a34,4
  I  00400554,3
   S 7ff00038c,4
  I  00400557,3
   L 7ff000388,4
  I  0040055a,2
  I  0040055c,4
  I  00400560,3
  I  00400563,4
   L 7ff000370,8
  I  00400567,3
   L 7ff000384,4
  I  0040056a,3
  I  0040056d,3
   L 7ff00038c,4
  I  00400570,3
   S 00600a74,4
  I  00400573,4
   M 7ff000388,4
  I  00400577,4
   L 7ff000388,4
  I  0040057b,2
  I  0040053c,3
   L 7ff000384,4
  I  0040053f,2
  I  00400541,4
  I  00400545,3
  I  00400548,4
   L 7ff000378,8
  I  0040054c,3
   L 7ff000388,4
  I  0040054f,2
  I  00400551,3
   L 00600a38,4
  I  00400554,3
   S 7ff00038c,4
  I  00400557,3
   L 7ff000388,4
  I  0040055a,2
  I  0040055c,4
  I  00400560,3
  I  00400563,4
   L 7ff000370,8
  I  00400567,3
   L 7ff000384,4
  I  0040056a,3
  I  0040056d,3
   L 7ff00038c,4
  I  00400570,3
   S 00600a84,4
  I  00400573,4
   M 7ff000388,4
  I  00400577,4
   L 7ff000388,4
  I  0040057b,2
  I  0040053c,3
   L 7ff000384,4
  I  0040053f,2
  I  00400541,4
  I  00400545,3
  I  00400548,4
   L 7ff000378,8
  I  0040054c,3
   L 7ff000388,4
  I  0040054f,2
  I  00400551,3
   L 00600a3c,4
  I  00400554,3
   S 7ff00038c,4
  I  00400557,3
   L 7ff000388,4
  I  0040055a,2
  I  0040055c,4
  I  00400560,3
  I  00400563,4
   L 7ff000370,8
  I  00400567,3
   L 7ff000384,4
  I  0040056a,3
  I  0040056d,3
   L 7ff00038c,4
  I  00400570,3
   S 00600a94,4
  I  00400573,4
   M 7ff000388,4
  I  00400577,4
   L 7ff000388,4
  I  0040057b,2
  I  0040057d,4
   M 7ff000384,4
  I  00400581,4
   L 7ff000384,4
  I  00400585,2
  I  00400533,7
   S 7ff000388,4
  I  0040053a,2
  I  00400577,4
   L 7ff000388,4
  I  0040057b,2
  I  0040053c,3
   L 7ff000384,4
  I  0040053f,2
  I  00400541,4
  I  00400545,3
  I  00400548,4
   L 7ff000378,8
  I  0040054c,3
   L 7ff000388,4
  I  0040054f,2
  I  00400551,3
   L 00600a40,4
  I  00400554,3
   S 7ff00038c,4
  I  00400557,3
   L 7ff000388,4
  I  0040055a,2
  I  0040055c,4
  I  00400560,3
  I  00400563,4
   L 7ff000370,8
  I  00400567,3
   L 7ff000384,4
  I  0040056a,3
  I  0040056d,3
   L 7ff00038c,4
  I  00400570,3
   S 00600a68,4
  I  00400573,4
   M 7ff000388,4
  I  00400577,4
   L 7ff000388,4
  I  0040057b,2
  I  0040053c,3
   L 7ff000384,4
  I  0040053f,2
  I  00400541,4
  I  00400545,3
  I  00400548,4
   L 7ff000378,8
  I  0040054c,3
   L 7ff000388,4
  I  0040054f,2
  I  00400551,3
   L 00600a44,4
  I  00400554,3
   S 7ff00038c,4
  I  00400557,3
   L 7ff000388,4
  I  0040055a,2
  I  0040055c,4
  I  00400560,3
  I  00400563,4
   L 7ff000370,8
  I  00400567,3
   L 7ff000384,4
  I  0040056a,3
  I  0040056d,3
   L 7ff00038c,4
  I  00400570,3
   S 00600a78,4
  I  00400573,4
   M 7ff000388,4
  I  00400577,4
   L 7ff000388,4
  I  0040057b,2
  I  0040053c,3
   L 7ff000384,4
  I  0040053f,2
  I  00400541,4
  I  00400545,3
  I  00400548,4
   L 7ff000378,8
  I  0040054c,3
   L 7ff000388,4
  I  0040054f,2
  I  00400551,3
   L 00600a48,4
  I  00400554,3
   S 7ff00038c,4
  I  00400557,3
   L 7ff000388,4
  I  0040055a,2
  I  0040055c,4
  I  00400560,3
  I  00400563,4
   L 7ff000370,8
  I  00400567,3
   L 7ff000384,4
  I  0040056a,3
  I  0040056d,3
   L 7ff00038c,4
  I  00400570,3
   S 00600a88,4
  I  00400573,4
   M 7ff000388,4
  I  00400577,4
   L 7ff000388,4
  I  0040057b,2
  I  0040053c,3
   L 7ff000384,4
  I  0040053f,2
  I  00400541,4
  I  00400545,3
  I  00400548,4
   L 7ff000378,8
  I  0040054c,3
   L 7ff000388,4
  I  0040054f,2
  I  00400551,3
   L 00600a4c,4
  I  00400554,3
   S 7ff00038c,4
  I  00400557,3
   L 7ff000388,4
  I  0040055a,2
  I  0040055c,4
  I  00400560,3
  I  00400563,4
   L 7ff000370,8
  I  00400567,3
   L 7ff000384,4
  I  0040056a,3
  I  0040056d,3
   L 7ff00038c,4
  I  00400570,3
   S 00600a98,4
  I  00400573,4
   M 7ff000388,4
  I  00400577,4
   L 7ff000388,4
  I  0040057b,2
  I  0040057d,4
   M 7ff000384,4
  I  00400581,4
   L 7ff000384,4
  I  00400585,2
  I  00400533,7
   S 7ff000388,4
  I  0040053a,2
  I  00400577,4
   L 7ff000388,4
  I  0040057b,2
  I  0040053c,3
   L 7ff000384,4
  I  0040053f,2
  I  00400541,4
  I  00400545,3
  I  00400548,4
   L 7ff000378,8
  I  0040054c,3
   L 7ff000388,4
  I  0040054f,2
  I  00400551,3
   L 00600a50,4
  I  00400554,3
   S 7ff00038c,4
  I  00400557,3
   L 7ff000388,4
  I  0040055a,2
  I  0040055c,4
  I  00400560,3
  I  00400563,4
   L 7ff000370,8
  I  00400567,3
   L 7ff000384,4
  I  0040056a,3
  I  0040056d,3
   L 7ff00038c,4
  I  00400570,3
   S 00600a6c,4
  I  00400573,4
   M 7ff000388,4
  I  00400577,4
   L 7ff000388,4
  I  0040057b,2
  I  0040053c,3
   L 7ff000384,4
  I  0040053f,2
  I  00400541,4
  I  00400545,3
  I  00400548,4
   L 7ff000378,8
  I  0040054c,3
   L 7ff000388,4
  I  0040054f,2
  I  00400551,3
   L 00600a54,4
  I  00400554,3
   S 7ff00038c,4
  I  00400557,3
   L 7ff000388,4
  I  0040055a,2
  I  0040055c,4
  I  00400560,3
  I  00400563,4
   L 7ff000370,8
  I  00400567,3
   L 7ff000384,4
  I  0040056a,3
  I  0040056d,3
   L 7ff00038c,4
  I  00400570,3
   S 00600a7c,4
  I  00400573,4
   M 7ff000388,4
  I  00400577,4
   L 7ff000388,4
  I  0040057b,2
  I  0040053c,3
   L 7ff000384,4
  I  0040053f,2
  I  00400541,4
  I  00400545,3
  I  00400548,4
   L 7ff000378,8
  I  0040054c,3
   L 7ff000388,4
  I  0040054f,2
  I  00400551,3
   L 00600a58,4
  I  00400554,3
   S 7ff00038c,4
  I  00400557,3
   L 7ff000388,4
  I  0040055a,2
  I  0040055c,4
  I  00400560,3
  I  00400563,4
   L 7ff000370,8
  I  00400567,3
   L 7ff000384,4
  I  0040056a,3
  I  0040056d,3
   L 7ff00038c,4
  I  00400570,3
   S 00600a8c,4
  I  00400573,4
   M 7ff000388,4
  I  00400577,4
   L 7ff000388,4
  I  0040057b,2
  I  0040053c,3
   L 7ff000384,4
  I  0040053f,2
  I  00400541,4
  I  00400545,3
  I  00400548,4
   L 7ff000378,8
  I  0040054c,3
   L 7ff000388,4
  I  0040054f,2
  I  00400551,3
   L 00600a5c,4
  I  00400554,3
   S 7ff00038c,4
  I  00400557,3
   L 7ff000388,4
  I  0040055a,2
  I  0040055c,4
  I  00400560,3
  I  00400563,4
   L 7ff000370,8
  I  00400567,3
   L 7ff000384,4
  I  0040056a,3
  I  0040056d,3
   L 7ff00038c,4
  I  00400570,3
   S 00600a9c,4
  I  00400573,4
   M 7ff000388,4
  I  00400577,4
   L 7ff000388,4
  I  0040057b,2
  I  0040057d,4
   M 7ff000384,4
  I  00400581,4
   L 7ff000384,4
  I  00400585,2
  I  00400587,1
   L 7ff000390,8
  I  00400588,1
   L 7ff000398,8
  I  004005c5,7
   L 00600aa0,1
  </code></pre>
  
  <p>Expected Values:</p>
  
  <pre><code>              My simulator       Reference simulator
  (s,E,b)    Hits  Misses  Evicts    Hits  Misses  Evicts
  (2,2,3)     196      42      34     201      37      29  
  (2,4,3)     208      30      14     212      26      10
  </code></pre>