TDT4258/ex2/cache_sim.c

#include <assert.h>
#include <inttypes.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdarg.h>
#include <stdbool.h>

#define RED_START "\033[31m"
#define COLOR_END "\033[0m"

#define DEBUG

typedef enum { dm, fa } cache_map_t;
typedef enum { uc, sc } cache_org_t;
typedef enum { instruction, data } access_t;

typedef struct {
  uint32_t address;
  access_t accesstype;
} mem_access_t;

typedef struct {
  uint64_t accesses;
  uint64_t hits;
  // You can declare additional statistics if
  // you like, however you are now allowed to
  // remove the accesses or hits
} cache_stat_t;

// DECLARE CACHES AND COUNTERS FOR THE STATS HERE

typedef struct {
  bool is_initialized;
  int content;
} cache_block_t;

cache_block_t* cache;

uint32_t cache_size;
uint32_t block_size = 64;
cache_map_t cache_mapping;
cache_org_t cache_org;

// Misc

// USE THIS FOR YOUR CACHE STATISTICS
cache_stat_t cache_statistics;

/* Reads a memory access from the trace file and returns
 * 1) access type (instruction or data access
 * 2) memory address
 */
mem_access_t read_transaction(FILE* ptr_file) {
  char buf[1000];
  char* token;
  char* string = buf;
  mem_access_t access;

  if (fgets(buf, 1000, ptr_file) != NULL) {
    /* Get the access type */
    token = strsep(&string, " \n");
    if (strcmp(token, "I") == 0) {
      access.accesstype = instruction;
    } else if (strcmp(token, "D") == 0) {
      access.accesstype = data;
    } else {
      printf(
          "Could not parse access type:\n"
          "%s%s%s %s\n",
          RED_START, token, COLOR_END, strsep(&string, " \n"));
      exit(0);
    }

    /* Get the access type */
    token = strsep(&string, " \n");
    access.address = (uint32_t)strtol(token, NULL, 16);

    return access;
  }

  /* If there are no more entries in the file,
   * return an address 0 that will terminate the infinite loop in main
   */
  access.address = 0;
  return access;
}

static int cache_access(mem_access_t access) {

}

const char* usage =
  "Usage:\n"
  "cache_sim size mapping organization [file]\n"
  "\tsize: 128-4096\n"
  "\tmapping: dm | fa \n"
  "\torganization: uc | sc\n"
  "\tfile: path\n";

/* Read command-line parameters and initialize:
 * cache_size, cache_mapping and cache_org variables
 */
static void handle_arguments(int argc, char** argv) {
  if (argc < 4) perror(usage);
  /* argv[0] is program name, parameters start with argv[1] */

  /* Set cache size */
  cache_size = atoi(argv[1]);
  // if (128 < cache_size || cache_size < 4096) error(
  //     "Cache size needs to be be between 128 and 4096\n"
  //     "Please check the input: %s%s%s",
  //     RED_START, argv[1], COLOR_END
  // );

  /* Set Cache Mapping */
  if (strcmp(argv[2], "dm") == 0) {
    cache_mapping = dm;
  } else if (strcmp(argv[2], "fa") == 0) {
    cache_mapping = fa;
  } else {
    printf("Unknown cache mapping\n");
    exit(1);
  }

  /* Set Cache Organization */
  if (strcmp(argv[3], "uc") == 0) {
    cache_org = uc;
  } else if (strcmp(argv[3], "sc") == 0) {
    cache_org = sc;
  } else {
    printf("Unknown cache organization\n");
    exit(1);
  }
}

static bool access_cache_dm(int index, int tag) {
  bool foundMatch = cache[index].is_initialized
                 && cache[index].content == tag;

  if (foundMatch) return true;

  cache[index].is_initialized = true;
  cache[index].content = tag;

  #ifdef DEBUG
    // printf("Overwriting tag at cache[%d] = %x\n", index, cache + index);
  #endif

  return false;
}

static bool access_cache_fa(int tag, cache_block_t* local_cache, int* counter, int number_of_blocks) {
  for (int i = 0; i < number_of_blocks; i++)
    if (local_cache[i].is_initialized && local_cache[i].content == tag)
      return true;

  (*counter)++;
  // if (*counter == number_of_blocks) *counter = 0;
  (*counter) %= number_of_blocks;
  local_cache[*counter].is_initialized = true;
  local_cache[*counter].content = tag;

  #ifdef DEBUG
    // printf("Overwriting tag at cache[%d] = %x\n", *counter, local_cache + *counter);
  #endif

  return false;
}

int main(int argc, char** argv) {
  // Reset statistics:
  memset(&cache_statistics, 0, sizeof(cache_stat_t));

  handle_arguments(argc, argv);

  // Will truncate 0, but that should not matter if args are handled correctly.
  int number_of_blocks = cache_size / block_size;

  int bits_for_offset = 0;
  int bs = block_size;
  while (bs % 2 == 0) {
    bits_for_offset++;
    bs = bs >> 1;
  }

  int bits_for_index = 0;
  if (cache_mapping == dm) {
    int nob = number_of_blocks;
    while (nob % 2 == 0) {
      bits_for_index++;
      nob = nob >> 1;
    }

    // If the cache is half the size (split), we will need 1 less bit for the index.
    if (cache_org == sc) bits_for_index --;
  }

  int bits_for_tag = 32 - bits_for_index - bits_for_offset;

  int offset_mask = (1 << bits_for_offset) - 1;
  int index_mask = ((1 << bits_for_index) - 1) << bits_for_offset;
  int tag_mask = ((1 << bits_for_tag) - 1) << (bits_for_index + bits_for_index);

  #ifdef DEBUG
    printf("Block offset mask: %08x\n", offset_mask);
    printf("Index mask: %08x\n", index_mask);
    printf("Tag mask: %08x\n", tag_mask);
  #endif

  int fa_counter1 = 0;
  int fa_counter2 = 0;
  int* fa_counter1_p = &fa_counter1;
  int* fa_counter2_p = &fa_counter2;

  #ifdef DEBUG
    printf("Number of blocks: %d\n", number_of_blocks);
    printf("Bits for offset: %d\n", bits_for_offset);
    printf("Bits for index: %d\n", bits_for_index);
    printf("Bits for tag: %d\n", bits_for_tag);

    printf("Size of cache_block: %d\n", sizeof(cache_block_t));
    printf("Cache size: %d\n", number_of_blocks * sizeof(cache_block_t));
    printf("Half cache size: %d\n", number_of_blocks * sizeof(cache_block_t) / 2);
  #endif

  cache = (cache_block_t*) malloc(number_of_blocks * sizeof(cache_block_t));
  // Pointer arithmetic black magic compiler voodoo will ensure that this is correct
  // (I spent waaaay to long figuring out that '+' doesn't literally mean integer addition when working
  //  with pointers types...)

  cache_block_t* upper_half_cache = cache + (number_of_blocks / 2);

  #ifdef DEBUG
    printf("Cache location: %d\n", cache);
    printf("Upper half cache location: %d\n\n", upper_half_cache);
  #endif
  // exit(1);

  // The global cache memory and global args values should now have been set.

  /* Open the file mem_trace.txt to read memory accesses */
  FILE* ptr_file;
  ptr_file = fopen("mem_trace.txt", "r");
  if (!ptr_file) {
    printf("Unable to open the trace file\n");
    exit(1);
  }

  #ifdef DEBUG
    int line = 0;
  #endif

  /* Loop until whole trace file has been read */
  mem_access_t access;
  while (1) {
    access = read_transaction(ptr_file);
    // If no transactions left, break out of loop
    if (access.address == 0) break;

    /* Do a cache access */
    cache_statistics.accesses++;

    int tag = (access.address & tag_mask) >> bits_for_offset + bits_for_index;
    int index = (access.address & index_mask) >> bits_for_offset;
    bool is_data = access.accesstype == data;

    #ifdef DEBUG
      // printf("Line: %u\n", line++);
      // printf("%c %08x\n", access.accesstype == instruction ? 'I' : 'D', access.address);
      // printf("Tag: %x\n", tag);
      // printf("Index: %x\n", index);
    #endif

    if ( (cache_mapping == fa && cache_org == uc && access_cache_fa(tag, cache, fa_counter1_p, number_of_blocks))
      || (cache_mapping == fa && cache_org == sc && (!is_data
                                                      ? access_cache_fa(tag, cache,            fa_counter1_p, number_of_blocks / 2)
                                                      : access_cache_fa(tag, upper_half_cache, fa_counter2_p, number_of_blocks / 2)))
      || (cache_mapping == dm && cache_org == uc && access_cache_dm(index, tag))
      || (cache_mapping == dm && cache_org == sc && access_cache_dm(index + (number_of_blocks / 2) * is_data, tag))
    ) {
      #ifdef DEBUG
        // printf("Hit!\n");
      #endif
      cache_statistics.hits++;
    }
    #ifdef DEBUG
      // printf("\n");
    #endif
  }

  printf("\nCache Statistics\n");
  printf("-----------------\n\n");
  printf("Accesses: %ld\n", cache_statistics.accesses);
  printf("Hits:     %ld\n", cache_statistics.hits);
  printf("Hit Rate: %.4f\n",
         (double)cache_statistics.hits / cache_statistics.accesses);

  fclose(ptr_file);
  return 0;
}