cs2011-cachelab/csim.c

/* asgoldsmith-jikomissar */
/**
   @file csim.c
   @author Adam Goldsmith
   @author Jacob Komissar
   @date 2016-04-25, 2016-04-26, 2016-04-27, 2016-04-28

   Cachelab: csim.c
   Simulates a cache with arbitrary sets, associativity, and block size.
   Reads from a valgrind trace, and outputs the number of hits, misses, and evictions.
   With the verbose option (-v), outputs details for each operation.

   Exit statuses:
    0 - success
    1 - usage error
   -1 - file error
    2 - memory error
*/

/**** Headers ****/
#include <stdlib.h>
#include <stdio.h>
#include <getopt.h>
#include "cachelab.h"


/******** Typedefs and structs ********/
typedef unsigned char uint8_t;

typedef struct {
	int hits;
	int misses;
	int evictions;
} results;

/* Linked Line and related prototypes */
typedef struct linked_line_s linked_line;
struct linked_line_s {
	uint8_t validity;
	long tag;
	linked_line* newer;
	linked_line* older;
};


/******** Macros ********/
#define mprintf(...) if (VERBOSE) printf(__VA_ARGS__)


/******** Global variables ********/
static uint8_t VERBOSE = 0; /**< If nonzero, mprintf will not print. Set in main() if -v flag is given. */

/******** General Prototypes ********/

/* Option-parsing functions */
void print_usage(void);
void bad_usage_error(void);
long parse_int_arg(char *arg, char opt);
long bits_to_size(int bits);

/* Sub-main functions */
void increment_result_counters(char result, results* score);

/* Cache creation/deletion functions */
linked_line** make_cache(long num_sets, long num_lines);
linked_line* make_set(linked_line* newer, long num_lines);
void free_cache(linked_line** cache, long num_sets);
void free_set(linked_line* line);
/* Cache-viewing functions */
void print_cache(linked_line** cache, long num_sets);
void print_set(linked_line* line);

/* Cache access functions */
char cache_access(linked_line** cache, long address, int set_bits, int block_offset_bits, long num_lines);
linked_line* find_line(linked_line* set_head, long tag);
linked_line* update_set(linked_line* old_head, linked_line* new_head);
//linked_line* move_to_head(linked_line* new_head, linked_line* old_head);


/** MAIN **/
int main(int argc, char* argv[])
{
	results score;
	char buffer[20];
	int set_index_bits = 0, block_offset_bits = 0; // Not-useful input variables.
	long num_sets = 0, num_lines = 0, block_size = 0; //Useful variables
	char *filename = NULL;
	int opt = 0;

	score.hits = 0;
	score.misses = 0;
	score.evictions = 0;

	while ((opt=getopt(argc, argv, "hvs:E:b:t:")) != -1) {
		switch (opt) {
			/* TODO: maybe add checking for optarg swallowing actual arguments. */
		case 'v':
			VERBOSE = 1;
			break;
		case 's': // 2^s = number of sets
			set_index_bits = (int)parse_int_arg(optarg, 's');
			num_sets = bits_to_size(set_index_bits);
			break;
		case 'E': // associativity - lines per set
			num_lines = parse_int_arg(optarg, 'E');
			break;
		case 'b': // 2^b = block size
			block_offset_bits = (int)parse_int_arg(optarg, 'b');
			block_size = bits_to_size(block_offset_bits);
			break;
		case 't':
			filename = optarg;
			break;
		case 'h':
			print_usage();
			return 0;
		default:
			bad_usage_error();
		}
	}
	/* If any required arguments were not provided. (argflags != 0b1111) */
	if (!num_sets || !num_lines || !block_size || !filename) {
		bad_usage_error();
	}
	/* End of argument parsing. */

	linked_line** cache = make_cache(num_sets, num_lines);

	/* FILE READING */
	FILE* f = fopen(filename, "r");
	if(!f) {
		printf("Invalid file name: %s", filename);
		exit(-1);
	}

	//char buffer[20];
	while (fgets(buffer, 20, f)) {
		if (buffer[0] == 'I') {
			continue;
		}

		char* end;
		char op = buffer[1];
		long address = strtol(buffer+3, &end, 16);
		long size = strtol(end+1, NULL, 16);

		if (*end != ',' || !(op == 'S' || op == 'L' || op == 'M')) {
			printf("Invalid input file, last line:\n%s\n", buffer);
			return -1;
		}

		/* if(VERBOSE) */
		/* 	print_cache(cache, num_sets); */

		mprintf(" %c %lx,%lx", op, address, size);

		char r = cache_access(cache, address, set_index_bits, block_offset_bits, num_lines);
		increment_result_counters(r, &score);
		if (op == 'M') { //Access again if modifying
		    r = cache_access(cache, address, set_index_bits, block_offset_bits, num_lines);
			increment_result_counters(r, &score);
		}

		mprintf("\n");
	}

	printSummary(score.hits, score.misses, score.evictions);

	fclose(f);
	free_cache(cache, set_index_bits);

	return 0;
}



/************************** OPTION-PARSING FUNCTIONS **************************/

void print_usage(void)
{
	printf("Usage: ./csim [-hv] -s <number> -E <number> -b <number> -t <file>\n"
		   "Options:\n"
		   "  -h  Print this help.\n"
		   "  -v  Display trace info.\n"
		   "  -s <number>  The number of set index bits. Must be a positive integer.\n"
		   "  -E <number>  Associativity (lines per set). Must be a positive integer.\n"
		   "  -b <number>  The number of block bits. Must be a positive integer.\n"
		   "  -t <file>    Name of the file to read a valgrind trace from.");
}

/**
   Prints the summarized usage and exits with status 1.
*/
void bad_usage_error(void)
{
	printf("Usage: ./csim [-hv] -s <number> -E <number> -b <number> -t <file>\n");
	exit(1);
}

/**
   Parses a string into a an positive integer; error if not possible.
   @param arg The string to parse.
   @param opt The option being parsed. If 'E', the output can not be 0.
          Otherwise, used only for helpful error messages.
   @return The parsed long integer if the argument was valid .
   @note Exits if argument is invalid.
 */
long parse_int_arg(char* arg, char opt)
{
	char* end;
	long i = strtol(arg, &end, 0);

	if (*end != '\0') { // associativity can not be zero
		printf("Invalid argument \"%s\" for option -%c\n", arg, opt);
		bad_usage_error();
	}
	else if (i < 0) {
		printf("Argument %s for option -%c too small (must be greater than 0)", arg, opt);
		exit(1);
	}
	else if (opt == 'E') {
		long long_max = (~0UL)>>1;
		if (i==0) {
			printf("Argument for option -E can not be 0\n");
			exit(1);
		}
		else if (i == long_max) {
			printf("Argument %s for option -E too large (must be less than %ld)\n", arg, long_max);
			exit(1);
		}
	}
	return i;
}

/**
   Calculates a size using a given number of bits.
   @param bits The power of 2 to use.
   @return 2^bits if it does not overflow.
   @note Exits if number of bits is larger than a signed int.
 */
long bits_to_size(int bits)
{
	int max_shift = 8*sizeof(int)-1;
	if (bits > max_shift-1) {
		printf("Argument %d too large (-s and -b must be less than %d)", bits, max_shift);
		exit(1);
	}
	return (long)1 << bits;
}


/***************************** SUB-MAIN FUNCTIONS *****************************/

/**
   Increments the cgiven ache operation counters based on the given result code.
   @param result The cache operation result code to parse (H, M, or E).
   @param score The score struct to increment.
   @TODO Fix this into a total of 3 conditionals.
 */
void increment_result_counters(char result, results* score)
{
	if (result == 'H') {
		score->hits++;
		mprintf(" hit");
	}
	else if (result == 'M') {
		score->misses++;
		mprintf(" miss");
	}
	else if (result == 'E') {
		score->misses++;
		score->evictions++;
		mprintf(" miss eviction");
	}
}



/********************* CACHE CREATION/DELETION FUNCTIONS  *********************/

/**
   @param num_sets The number of sets in the cache.
   @param num_lines The number of lines in each set.
   @return A pointer to the allocated cache's set list.
   @TODO Handle cases where not enough space can be allocated.
 */
linked_line** make_cache(long num_sets, long num_lines)
{
	linked_line** cache = (linked_line**)calloc(num_sets, sizeof(linked_line*));
	if (! cache) {
		printf("Error: calloc failed\n");
		exit(2);
	}
	long ii;
	for (ii = 0; ii < num_sets; ii++) {
		cache[ii] = make_set(NULL, num_lines);
	}
	return cache;
}

/**
   Creates a set by creating and linking a given number of lines.
   @param newer A pointer to the previously-created element of the set.
   @param num_lines The number of lines remaining to be added.
   @return A pointer to the created line.
   @bug Large values for num_lines result in a segfault in the call to calloc.
   @TODO Free already-allocated space in event of allocation failure.
*/
linked_line* make_set(linked_line* newer, long num_lines) {
	linked_line* current = (linked_line*)calloc(1, sizeof(linked_line));
	if (! current) {
		printf("Error: calloc failed\n");
		exit(2);
	}
	current->newer = newer;
	num_lines--;
	if (num_lines) { // If not on the last line
		current->older = make_set(current, num_lines);
	}
	else {
		current->older = NULL;
	}
	return current;
}

/**
   @param cache A pointer to the cache to free.
   @param num_sets The number of sets in the cache.
 */
void free_cache(linked_line** cache, long num_sets)
{
	int ii;
	for (ii = 0; ii < num_sets; ii++) {
		free_set(cache[ii]);
	}
	free(cache);
}

/**
   Frees a set by recursing through it, then freeing each element from oldest to newest.
   @param line A pointer to the next line in the set.
   @param num_lines The number
 */
void free_set(linked_line* line) {
	if (line != NULL) {
		free_set(line->older);
		free(line);
	}
}

/************************** CACHE VIEWING FUNCTIONS  **************************/

/**
   @cache The cache to print.
   @cache num_sets The number of sets in the cache.
 */
void print_cache(linked_line** cache, long num_sets)
{
	int ii;
	for (ii = 0; ii < num_sets; ii++) {
		print_set(cache[ii]);
	}
}

/**
   Prints a cache line and all lines modified less recently than it in its set.<br />
   The format is: <br />
   address validity.tag		address of newer:address of older
   @param line The set/line to print, or NULL. If null, does nothing.
 */
void print_set(linked_line* line)
{
	if (line != NULL) {
		print_set(line->older);
		printf("%p %x.%lx\t\t%p:%p\n", (void *) line, line->validity,
			   line->tag, (void *) line->newer, (void *) line->older);
	}
}



/*************************** CACHE ACCESS FUNCTIONS ***************************/

/**
   Simulates a cache access operation.
   @param cache The cache to access.
   @param address The address to access in the cache.
   @param set_bits The number of set bits in the address.
   @param block_offset_bits The number of block offset bits in the address.
   @param num_lines The number of lines per set.
   @return 'H' if a hit, 'M' if a miss, 'E' if a miss and eviction

   @TODO Pass set and tag into cache_access instead of an address and sizes.
   @TODO Make the tag and set retrieval a function?
   @TODO Make the re-linking of the set into its own function.
 */
char cache_access(linked_line** cache, long address,
				  int set_bits, int block_offset_bits, long num_lines)
{
	char operation;
	long tag = address >> set_bits >> block_offset_bits;
	long set = (address >> block_offset_bits) & ((1 << set_bits) - 1);
	linked_line* set_head = cache[set];
	linked_line* line = find_line(set_head, tag);

	if (!line->validity) {
		operation = 'M';
	}
	else if (line->tag == tag) {
		operation = 'H';
	}
	else {
		operation = 'E';
	}

	line->tag = tag;
	line->validity = 1;

	cache[set] = update_set(set_head, line);

	return operation;
}

/**
   Finds a line in the given set that holds the given tag, or the least-recently
   used line if the tag is not in the set, or the next invalid line if not all
   of the lines have been used.
   @param line Initially, the most-recently-used line in the set. In the
               recursion, iterates through the lines in the set.
   @returns The first line with a matching tag, the first invalid line,
            or the first line without an older (i.e. the end of the set).
 */
linked_line* find_line(linked_line* line, long tag)
{
	if (line->tag == tag || !line->validity || !line->older) {
		return line;
	}
	else {
		return find_line(line->older, tag);
	}
}

/**
   Updates the use order of a set by moving the line being accessed in front of
   the previously-accessed line and linking the neighbors of the new head.
   @param old_head The previous most-recently modified line of the set.
   @param new_head The line of the set being accessed.
   @return new_head
 */
linked_line* update_set(linked_line* old_head, linked_line* new_head) {
	if(!(new_head == old_head)) {
		new_head->newer->older = new_head->older;
		if(new_head->older) {
			new_head->older->newer = new_head->newer;
		}
		new_head->newer = NULL;
		new_head->older = old_head;
		old_head->newer = new_head;
	}
	return new_head;
}