csim.c

#include <assert.h>
#include <errno.h> // for `strerror()`
#include <getopt.h>
#include <inttypes.h> // for `PRIuFAST32`, etc
#include <limits.h>   // for `CHAR_BIT`
#include <stdbool.h>  // for `bool`
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>

#include "cachelab.h"

#ifndef NDEBUG
#define _PRINT_DEBUG true
#else
#define _PRINT_DEBUG false
#endif

#define D(fmt, ...)                                                                                \
   do {                                                                                            \
      if (_PRINT_DEBUG)                                                                            \
         fprintf(stderr, "%c[%dm%s:%d:%s(): " fmt "%c[39m", 0x1B, 31, __FILE__, __LINE__,          \
                 __func__, __VA_ARGS__, 0x1B);                                                     \
   } while (0)

#define BYTE_TO_BINARY_PATTERN "%c%c%c%c%c%c%c%c"
#define BYTE_TO_BINARY(byte)                                                                       \
   (byte & 0x80 ? '1' : '0'), (byte & 0x40 ? '1' : '0'), (byte & 0x20 ? '1' : '0'),                \
       (byte & 0x10 ? '1' : '0'), (byte & 0x08 ? '1' : '0'), (byte & 0x04 ? '1' : '0'),            \
       (byte & 0x02 ? '1' : '0'), (byte & 0x01 ? '1' : '0')

#define WORD_TO_BINARY_PATTERN                                                                     \
   BYTE_TO_BINARY_PATTERN " " BYTE_TO_BINARY_PATTERN " " BYTE_TO_BINARY_PATTERN                    \
                          " " BYTE_TO_BINARY_PATTERN
#define WORD_TO_BINARY(word)                                                                       \
   BYTE_TO_BINARY((word) >> 24)                                                                    \
   , BYTE_TO_BINARY((word) >> 16), BYTE_TO_BINARY((word) >> 8), BYTE_TO_BINARY((word))

// This constructs a mask from bit-index `from`, to bit-index `to`.
// i.e. `MASK_FOR_BITS(3,7)` --> `...00
#define MASK_FOR_BITS(from, to) (((1 << ((from) - (to) + 1)) - 1) << (to))

typedef uint_fast8_t bitCount_t;
typedef uint8_t byte_t;     // somebody stop me
typedef uint64_t mask_t;    // please
typedef uint64_t address_t; // send help
typedef byte_t* line_p;
typedef byte_t* set_p;

#define PRIuBITS PRIuFAST8
#define PRIuBYTE PRIu8
#define PRIuMASK PRIu64
#define PRIuADDRESS PRIu64
#define SCNuADDRESS SCNu64
#define PRIxADDRESS PRIx64
#define SCNxADDRESS SCNx64
#define PRIXADDRESS PRIX64
#define SCNXADDRESS SCNX64

#define VERBOSE_FMT "%c %" PRIxADDRESS ",%zx"

// Stores the set-index size (seti), lines-per-set, and block-index size
// (blocki) information for a cache
typedef struct cacheConfig {
   struct {
      bitCount_t bits;
      mask_t mask;
   } seti;
   struct {
      bitCount_t bits;
      mask_t mask;
   } blocki;
   uint_fast16_t lines_per_set; // this is a somewhat arbitrary restriction?
} cacheConfig_t;

#define CFG_NUM_SETS(cfg) ((uintmax_t)1 << ((cfg).seti.bits))
#define CFG_NUM_BYTES(cfg) ((uintmax_t)1 << ((cfg).blocki.bits))

#define ADDRESS_NUM_BITS ((bitCount_t)(sizeof(address_t) * CHAR_BIT))

typedef struct cache {
   cacheConfig_t config;
   set_p sets;
} cache_t;

typedef struct query {
   address_t tag; // ... does this need to support ≥32-bit addresses?
   address_t seti;
   address_t blocki;
} query_t;

typedef uint_fast8_t opResult_t;
#define maskFAIL ~(~(opResult_t)0 >> 1)   // 0b10000000
#define maskHIT ((opResult_t)1)           // 0b00000001
#define maskMISS ((opResult_t)1 << 1)     // 0b00000010
#define maskEVICTION ((opResult_t)1 << 2) // 0b00000100

cache_t* initCache(cacheConfig_t);
query_t deconstructQuery(cache_t*, address_t);
opResult_t performLoadOp(cache_t*, query_t);
opResult_t performSaveOp(cache_t*, query_t);
void processFile(cache_t*, FILE*);

bool isVerbose = false;

#define USAGE(x)                                                                                   \
   do {                                                                                            \
      fprintf(stdout, "Usage: %s [-hv] -s <s> -E <E> -b <b> -t <tracefile>\n", argv[0]);           \
      exit(EXIT_FAILURE);                                                                          \
   } while (0)

static char string_null[]     = "";
static char string_hit[]      = " hit";
static char string_miss[]     = " miss";
static char string_eviction[] = " eviction";

int main(int argc, char* argv[]) {
   uintmax_t seti_bits = 0, lines_per_set = 1, blocki_bits = 0;
   char* tracefile = NULL; // haha

   int opt;
   char* endptr;
   while ((opt = getopt(argc, argv, "hvs:E:b:t:")) != -1) {
      errno  = 0;
      endptr = string_null; // FIXME: There's gotta be a better way to do this.

      switch (opt) {
      case 't':
         tracefile = optarg;
         break;

      case 's':
         seti_bits = strtoumax(optarg, &endptr, 10);
         break;

      case 'E':
         lines_per_set = strtoumax(optarg, &endptr, 10);
         break;

      case 'b':
         blocki_bits = strtoumax(optarg, &endptr, 10);
         break;

      case 'v':
         isVerbose = true;
         break;

      case 'h':
      default:
         USAGE();
      }

      if (*endptr != '\0') {
         fprintf(stderr, "FATAL: Invalid input in command-line arguments where integer values were "
                         "expected.\n");
         exit(EXIT_FAILURE);
      }
      if (errno) {
         fprintf(stderr, "FATAL: Couldn't parse ‘%s’ as an integer:\n", optarg);
         fprintf(stderr, "   “%s”\n", strerror(errno));
         exit(EXIT_FAILURE);
      }
   }

   assert(seti_bits < ADDRESS_NUM_BITS);
   assert(seti_bits >= 0);
   assert(lines_per_set <= (1 << 16)); // This is probably unnecessarily small
   assert(lines_per_set >= 1);
   assert(blocki_bits < ADDRESS_NUM_BITS);
   assert(blocki_bits >= 0);
   assert((size_t)(seti_bits + blocki_bits) < (sizeof(address_t) * CHAR_BIT)); // FIXME: Should this be `<=`?
   if (tracefile == NULL) {
      fprintf(stderr, "FATAL: A tracefile must be provided!\n");
      USAGE();
   }

   D("Tracefile: %s\n", tracefile);
   if (isVerbose) {
      D("%s\n", "Verbose mode!");
   }

   D("Configuring cache w/ %" PRIuMAX ", %" PRIuMAX ", %" PRIuMAX "\n", seti_bits, lines_per_set,
     blocki_bits);
   cache_t* c = initCache((cacheConfig_t){.seti = {.bits = (bitCount_t)seti_bits},
                                          .blocki = {.bits = (bitCount_t)blocki_bits},
                                          lines_per_set});

   FILE* fp = fopen(tracefile, "r");
   if (fp == NULL) {
      fprintf(stderr, "FATAL: Can't open ‘%s’ for reading:\n", tracefile);
      fprintf(stderr, "   “%s”\n", strerror(errno));
      exit(EXIT_FAILURE);
   }

   processFile(c, fp);

   printSummary(0, 0, 0);
   return 0;
}

inline query_t deconstructQuery(cache_t* c, address_t address) {
   return (query_t){.tag    = address >> (c->config.seti.bits + c->config.blocki.bits),
                    .seti   = (address & c->config.seti.mask) >> c->config.seti.bits,
                    .blocki = (address & c->config.blocki.mask)};
}

// This allocates an entire contiguous chunk of memory to hold what is,
// effectively, a three-dimensional array: sets × lines per set × bytes per line
//
// I make no attempt to be memory-leak avoidant. (Why bother?)
//
// (I hate *everything* about what `clang-format` does to this function.)
cache_t* initCache(cacheConfig_t cfg) {
   cfg.seti.mask =
       cfg.seti.bits ? MASK_FOR_BITS(cfg.seti.bits + cfg.blocki.bits - 1, cfg.blocki.bits) : 0;
   cfg.blocki.mask = cfg.blocki.bits ? MASK_FOR_BITS(cfg.blocki.bits - 1, 0) : 0;

   cache_t* it = calloc(1, sizeof(cache_t));
   it->config  = cfg;

   uintmax_t bytes_per_set = cfg.lines_per_set * CFG_NUM_BYTES(cfg);
   it->sets                = calloc(CFG_NUM_SETS(cfg), bytes_per_set);

   // ... and a fuckton of debugging output:
   D("CACHE CONFIGURED; total size: %" PRIuMAX " bytes\n", CFG_NUM_SETS(cfg) * bytes_per_set);
   D("-- Set bits: %" PRIuBITS " (%" PRIuMAX " total sets)\n", cfg.seti.bits, CFG_NUM_SETS(cfg));
   D("      (bitmask, %" PRIuBITS " through %" PRIuBITS ": " WORD_TO_BINARY_PATTERN ")\n",
     (bitCount_t)(cfg.seti.bits + cfg.blocki.bits - 1), cfg.blocki.bits,
     WORD_TO_BINARY(cfg.seti.mask));

   D("-- Lines per set: %" PRIuFAST16 "\n", cfg.lines_per_set); // FIXME: D.R.Y. this type-choice

   D("-- Block-index bits: %" PRIuBITS " (%" PRIuMAX " total bytes per block)\n", cfg.blocki.bits,
     CFG_NUM_BYTES(cfg));
   D("      (bitmask, %" PRIuBITS " through %" PRIuBITS ": " WORD_TO_BINARY_PATTERN ")\n",
     (bitCount_t)(cfg.blocki.bits - 1), (bitCount_t)0, WORD_TO_BINARY(cfg.blocki.mask));

   return it;
}

opResult_t performLoadOp(cache_t* c, query_t q) {
   opResult_t results = 0;

   // NYI
   results = results | maskHIT;

   return results;
}

opResult_t performSaveOp(cache_t* c, query_t q) {
   opResult_t results = 0;

   // NYI
   results = results | maskHIT;

   return results;
}

void processFile(cache_t* c, FILE* fp) {
   int scanResult;
   opResult_t opResult;
   char buffer[256];

   do {
      void* gets_p = fgets((char*)&buffer, 255, fp);

      if (feof(fp)) {
         D("%s\n", "Successfully reached EOF");
         return;
      }

      if (ferror(fp) || gets_p != buffer) {
         fprintf(stderr, "FATAL: File read error:\n");
         fprintf(stderr, "   “%s”\n", strerror(errno));
         exit(EXIT_FAILURE);
      }

      char is_instruction, op;
      address_t address;
      size_t size;

      scanResult =
          sscanf(buffer, "%c%c %" SCNxADDRESS ",%zu", &is_instruction, &op, &address, &size);

      if (is_instruction != ' ') {
         D("%s\n", "-> I: Instruction load (ignored)");
         continue;
      }

      query_t query = deconstructQuery(c, address);

      // D("-- Set bits: %" PRIuFAST8 " (%" PRIuFAST32 " total sets)\n", cfg.seti.bits,
      // CFG_NUM_SETS(cfg));
      // D("      (bitmask, %" PRIuFAST8 " through %" PRIuFAST8 ": " WORD_TO_BINARY_PATTERN ")\n",
      //  (bitCount_t)(cfg.seti.bits + cfg.blocki.bits - 1), cfg.blocki.bits,
      //  WORD_TO_BINARY(cfg.seti.mask));

      // D("-- Lines per set: %" PRIuFAST32 "\n", cfg.lines_per_set);

      // D("-- Block-index bits: %" PRIuFAST8 " (%" PRIuFAST32 " total bytes per block)\n",
      //  cfg.blocki.bits, CFG_NUM_BYTES(cfg));
      // D("      (bitmask, %" PRIuFAST8 " through %" PRIuFAST8 ": " WORD_TO_BINARY_PATTERN ")\n",
      //  (bitCount_t)(cfg.blocki.bits - 1), (bitCount_t)0, WORD_TO_BINARY(cfg.blocki.mask));

      switch (op) {
      case 'L':
         D("%s\n", "-> L: Dispatching load");
         opResult = performLoadOp(c, query);

         break;
      case 'S':
         D("%s\n", "-> S: Dispatching save");
         opResult = performSaveOp(c, query);

         break;
      case 'M':
         D("%s\n", "-> M: Dispatching load");
         opResult = performLoadOp(c, query);
         D("%s\n", "-> M: Dispatching store");
         opResult = opResult | performSaveOp(c, query);

         break;
      default:
         fprintf(stderr, "FATAL: Unknown operation ‘%c’!", op);
         exit(EXIT_FAILURE);
      }

      assert(opResult != 0);

      // FIXME: Make use of maskFAIL!
      char* didHit   = (opResult & maskHIT) ? string_hit : string_null;
      char* didMiss  = (opResult & maskMISS) ? string_miss : string_null;
      char* didEvict = (opResult & maskEVICTION) ? string_eviction : string_null;

      if (isVerbose) {
         printf(VERBOSE_FMT "%s%s%s\n", 'L', address, size, didMiss, didEvict, didHit);
      }
   } while (scanResult == 4);

   if (scanResult != EOF) {
      fprintf(stderr, "FATAL: Line-conversion error (%d fields read)\n", scanResult);
      exit(EXIT_FAILURE);
   }
}