cachesim/tagonlycache.c

   1 //
   2 //  cache.c
   3 //  engines
   4 //
   5 //  Created by Pete Wilson on 4/18/20.
   6 //  Copyright © 2020 Kiva Design Groupe LLC. All rights reserved.
   7 //
   8
   9 #define EXTERN extern
  10
  11 #define gTraceAll       (0)
  12 #define gReport         (0)
  13
  14 #include <string.h>
  15 #include "tagonlycache.h"
  16
  17 char * title = "tagonlycache 0.1v2 [Sept 17 2020]";
  18
  19 /*
  20  Versions
  21 =========
  22
  23  - tagonlycache 0.1v2 [Sept 17 2020]
  24         - serious error in the computation of the index in the cache from tag corrcted.
  25
  26  0.1v1 - not committed; basic code from the standard cache source
  27  */
  28
  29
  30 // ----------- addrMaskForCache ------------
  31
  32 int64 addrMaskForCache(cacheData * cd) {
  33         if (gTraceAll && gReport) printf("\n--addrMaskForCache %s: l2l = %d linelength=%d; ", cd->name, cd -> log2LineLength, 1 << (cd -> log2LineLength));
  34         int64 mask = (1 << (cd -> log2Lines)) - 1;
  35         if (gTraceAll && gReport) printf(": mask = 0x%08llx", mask);
  36         return mask;
  37 }
  38
  39 // ------------ addrToLineStartAddr -------------
  40
  41 int64 addrToLineStartAddr(cacheData * cd, int64 address) {
  42         if (gTraceAll && gReport) printf("\n--addrToLineStartAddr %s: l2l = %d - address = 0x%08llx %lld; ", cd->name, cd -> log2Lines, address, address);
  43         int64 mask = addrMaskForCache(cd);
  44         if (gTraceAll && gReport) printf("\t notmask = 0x%08llx", ~mask);
  45         int64 start = address & (~mask);
  46         if (gTraceAll && gReport) printf("\t start = 0x%08llx", start);
  47         return start;
  48 }
  49
  50 // ------------- addrToTag ---------------------
  51
  52 int64 addrToTag(cacheData * cd, int64 address) {
  53         if (gTraceAll && gReport) printf("\n\taddrToTag: addr is %lld 0x%llx", address, address);
  54         int64 tag = address >> (cd -> log2LineLength);
  55         return tag;
  56 }
  57
  58 // ------------- tagToAddr ---------------------
  59
  60 int64 tagToAddr(cacheData * cd, int64 tag) {
  61         int64 addr = tag << (cd -> log2LineLength);
  62         return addr;
  63 }
  64
  65 // -------------- getIndexAndTag --------------------
  66
  67 void getIndexAndTag(int64 address, cacheData * d, int64 * index_ptr, int64 * tag_ptr) {
  68         // we have a byte address coming in
  69         // compute the tag
  70         int64 temp = addrToTag(d, address);
  71         // given a tag, decide which line that should go to. mask the tag with a mask based on number of lines
  72         int64 mask = addrMaskForCache(d);
  73         int64 index = temp & mask;
  74         int64 tag = temp;
  75         *index_ptr = index;
  76         *tag_ptr = tag;
  77         if (gTraceAll && gReport) printf("\ngetIndexAndTag 0x%08llx (%lld) : linelength = %d bytes:: index = %d temp = 0x%08x mask = 0x%08x tagval = 0x%08x\n",
  78                                                 address, address, d -> length, (int)index, (int)temp, (int)mask, (int)tag);
  79 }
  80
  81 // -------------- int64LineLength --------------
  82
  83 int int64LineLength(cacheData * cd) {
  84         int len = cd -> length;
  85         len = len >> 3;
  86         return len;
  87 }
  88
  89 // -------------- fastcachelookup -------------------
  90
  91 int fastcachelookup(int64 address, cacheData * d) {
  92         // read the address for lookup
  93         // compute index into the cache, and the matching value for the tag
  94 //      return 1;
  95         // see if the address is set in the hitvector
  96         d -> reads++;
  97         if (d -> hitvector[address]) {
  98                 d -> hits++;
  99                 d -> fasthits++;
 100                 return 1;
 101         }
 102         else {
 103                 // gotta do a real cache lookup
 104                 if (gTraceAll && gReport) printf("\nlookup address 0x%08llx ", address);
 105
 106                 // look up the address in the cache's hi
 107                 int64 index, tag;
 108                 getIndexAndTag(address, d, &index, &tag);
 109
 110                 if (gTraceAll && gReport) printf("\n\t\tindex = %lld; tag = 0x%08llx", index,  tag);
 111
 112                 for (int way = 0; way < d -> numways; way++) {
 113                         cacheWay * cw = d -> ways[way];
 114                         if ((cw -> tags[index] == tag) && (cw -> valid[index])) {
 115                                 // hit!
 116                                 if (gTraceAll && gReport) printf("\t- hit!");
 117                                 return 1;
 118                         }
 119                 }
 120
 121                 if (gTraceAll && gReport) printf("\t- MISS!");
 122                 d -> misses++;
 123                 // we missed. choose a way at random, eject the incumbent if any and install the new
 124                 int way = uniform(0, 0, d -> numways);
 125                 cacheWay * cw = d -> ways[way];
 126
 127                 if (cw -> valid[index] == 0) {
 128                         // empty
 129                         cw -> tags[index] = tag;
 130                         cw -> valid[index] = 1;
 131                         // mark the hitvector. first, get the address corresponding to the start of the cache line
 132                         // we have computed the tag before
 133                         int64 addr = tagToAddr(d, tag);
 134                         int n = d -> length;
 135                         for (int i = 0; i < n; i++) {
 136                                 d -> hitvector[addr++] = 1;
 137                         }
 138                 }
 139                 else {
 140                         // find the address for the line we're ejecting
 141                         int64 addr = tagToAddr(d, cw -> tags[index]);
 142                         int n = d -> length;
 143                         for (int i = 0; i < n; i++) {
 144                                 d -> hitvector[addr++] = 0;
 145                         }
 146                         // eject the line
 147                         d -> ejections++;
 148                         cw -> tags[index] = tag;
 149                         cw -> valid[index] = 1;
 150
 151                         // set up the hitvector
 152                         addr = tagToAddr(d, tag);
 153                         n = d -> length;
 154                         for (int i = 0; i < n; i++) {
 155                                 d -> hitvector[addr++] = 1;
 156                         }
 157
 158                 }
 159                 return 0;
 160         }
 161 }
 162
 163 // -------------- lookup -------------------
 164
 165 int lookup(char access, int64 address, cacheData * cache, cacheWay ** cway) {
 166         // read the address for lookup
 167         // compute index into the cache, and the matching value for the tag
 168
 169         // look up the address in the cache's hi
 170         int64 index, tag;
 171         getIndexAndTag(address, cache, &index, &tag);
 172         if (access == 'r') cache -> reads++;
 173         else if (access == 'w') cache -> writes++;
 174
 175         for (int way = 0; way < cache -> numways; way++) {
 176                 cacheWay * cw = cache -> ways[way];
 177                 if ((cw -> tags[index] == tag) && (cw -> valid[index])) {
 178                         // hit!
 179                         // note the hit
 180                         cache -> hits++;
 181                         // if it's a write, make it dirty
 182                         if (access == 'w') cw -> dirty[index] = 1;
 183                         *cway = cw;
 184                         return 1;
 185                 }
 186         }
 187
 188         cache -> misses++;
 189         // we missed. choose a way at random, eject the incumbent if any and install the new
 190         int way = uniform(0, 0, cache -> numways);
 191         cacheWay * cw = cache -> ways[way];
 192         if (cw -> valid[index] == 0) {
 193                 // a cacheline without validity
 194                 cw -> tags[index] = tag;
 195                 cw -> valid[index] = 1;
 196                 cw -> dirty[index] = 0;
 197         }
 198         else {
 199                 // we already have a cacheline here, so eject the line
 200                 if (cw -> dirty[index]) {
 201                         cache -> ejections++;
 202                 }
 203                 cw -> tags[index] = tag;
 204                 cw -> valid[index] = 1;
 205                 cw -> dirty[index] = 0;
 206         }
 207         *cway = cw;
 208         return 0;
 209 }
 210
 211 // -------------- newCacheData -----------
 212
 213 void * newCacheData(void) {
 214         cacheData * cd = malloc(sizeof(cacheData));
 215         if (cd) {
 216                 cd -> isACache = 0xcace;
 217                 cd -> counter = 0;
 218                 cd -> requests = 0;
 219                 cd -> owner = NULL;
 220         }
 221         return cd;
 222 }
 223
 224 // -------------- configureCache -------------
 225
 226 void configureCache(cacheData * cd, char * name, int32 numways, int32 log2LineLength, int32 log2Lines) {
 227         // sets up the specified cacheData
 228         cd -> name = strdup(name);
 229
 230         cd -> hits = 0;
 231         cd -> fasthits = 0;
 232         cd -> misses = 0;
 233         cd -> ejections = 0;
 234
 235         cd -> reads = 0;
 236         cd -> writes = 0;
 237
 238         cd -> lines =  1 << log2Lines;
 239         cd -> length = 1 << log2LineLength;             // BYTES
 240
 241         cd -> log2Lines = log2Lines;
 242         cd -> log2LineLength = log2LineLength;
 243
 244         cd -> numways = numways;
 245
 246         cd -> ejections = 0;
 247         cd -> writebacks = 0;
 248
 249         cd -> outstanding = qNewQ("outstanding misses");
 250
 251         if (gTraceAll && gReport) {
 252                 printf("\nConfiguring cache %s:", name);
 253                 printf("\n\tways         = %d", numways);
 254                 printf("\n\tline length  = %d bytes", cd -> length);
 255                 printf("\n\tlines per way= %d", cd -> lines);
 256         }
 257
 258         cd -> ways = malloc(numways * sizeof(cacheWay *));
 259
 260         // initialise all the cache ways
 261         for (int32 way = 0; way < numways; way++) {
 262                 cacheWay * cw = malloc(sizeof(cacheWay));
 263                 char * wayname = malloc(64);
 264                 sprintf(wayname, "way[%d]", way);
 265                 cw -> name = wayname;
 266                 cd -> ways[way] = cw;
 267                 cw -> tags = malloc(cd -> lines * sizeof(int64));
 268                 cw -> valid = malloc(cd -> lines * sizeof(int8));
 269                 cw -> dirty = malloc(cd -> lines * sizeof(int8));
 270                 cw -> timetag = malloc(cd -> lines * sizeof(int64));
 271
 272                 for (int line = 0; line < cd -> lines; line++) {
 273                         cw -> tags[line] = 0;
 274                         cw -> dirty[line] = 0;
 275                         cw -> valid[line] = 0;
 276                         cw -> timetag[line] = 0;
 277                 }
 278         }
 279 }
 280
 281 // ------------- intHitRate --------------------
 282
 283 int intHitRate(int width, cacheData * cd) {
 284         int v;
 285 //      printf("\nintHitRate: for cache '%s'. Reads = %lld writes = %lld", cd -> name, cd -> reads, cd -> writes);
 286         if ((cd -> reads + cd -> writes) > 0) {
 287                 float hits = ((float)cd -> hits/(float)(cd -> reads + cd -> writes)) * (float) width;
 288                 v = (int) hits;
 289                 if (v > 100) {
 290                         printf("\n--%d--", v);
 291                 }
 292         }
 293         else {
 294                 v = 0;
 295         }
 296         return v;
 297 }
 298
 299 // -------------- reportCacheStats ----------------
 300
 301 void reportCacheStats(cacheData * cache) {
 302 //      if ((cpu -> currtime != 0) && (final == 1)) {
 303         printf("\n\nConfiguration for cache '%s':", cache -> name);
 304                 printf("\n======================================================");
 305                 for (int i = 0; i < strlen(cache -> name); i++) {
 306                         putchar('=');
 307                 }
 308                 printf("\n\tways                = %d", cache -> numways);
 309                 printf("\n\tline length         = %d bytes", cache -> length);
 310                 printf("\n\tlines per way       = %d", cache -> lines);
 311                 int capacity =((cache -> numways) * cache -> lines) * (cache -> length);
 312                 if (capacity > 1024) {
 313                         printf("\n\tCapacity            = %dKB", capacity / 1024);
 314                 }
 315                 else {
 316                         printf("\n\tCapacity          = %dB", capacity);
 317                 }
 318                 printf("\n\nStatistics:");
 319                 printf("\n\treads               = %lld", cache -> reads);
 320                 printf("\n\twrites              = %lld", cache -> writes);
 321                 printf("\n\tejections           = %lld", cache -> ejections);
 322                 printf("\n\tfasthits            = %lld", cache -> fasthits);
 323                 printf("\n\thits                = %lld", cache -> hits);
 324                 printf("\n\tmisses              = %lld", cache -> misses);
 325                 printf("\n\thit rate            = %.1f%%",((float)cache -> hits/(float)(cache -> reads + cache -> writes)) * 100.0);
 326         }
 327
 328
 329 // ------------------- printWay -------------------
 330
 331 void printWay(cacheData * cd, cacheWay * way) {
 332         // prints out the cacheway
 333         int lines = cd -> lines;
 334         for (int i = 0; i < lines; i++) {
 335                 printf("\n\t");
 336                 if (way -> dirty[i]) printf("d"); else printf("-");
 337                 if (way -> valid[i]) printf("V"); else printf("-");
 338                 printf("\t0x%08llx\t", way -> tags[i]);
 339         }
 340 }
 341
 342 // ------------------- printCache -------------------
 343
 344 void printCache(cacheData * cache) {
 345         // prints out the complete contents of the specified cache
 346         printf("\nState of cache: %s", cache -> name);
 347         cacheWay ** cw = cache -> ways;
 348         for (int i = 0; i < cache -> numways; i++) {
 349                 printf("\n\nWay[%d]", i);
 350                 printWay(cache, cw[i]);
 351         }
 352 }