prog6.tar

Makefile0000644000076400007640000000113512130042025013331 0ustar  crazylylecrazylyle#
#   Makefile for building the cache simulator
#
CFLAGS = -O1 -Wall
#CFLAGS = -O0 -ggdb3


all:   cachesim

cachesim: cds.o main.o read_cds.o simulate.o utils.o
	gcc $(CFLAGS) cds.o main.o read_cds.o simulate.o utils.o -o cachesim

cds.o: cds.c global.h cds.h
	gcc $(CFLAGS) cds.c -c

main.o: main.c global.h caches.h
	gcc $(CFLAGS) main.c -c

read_cds.o: read_cds.c global.h cds.h caches.h utils.h
	gcc $(CFLAGS) read_cds.c -c

simulate.o: simulate.c global.h cds.h caches.h utils.h
	gcc $(CFLAGS) simulate.c -c

utils.o: utils.c global.h utils.h
	gcc $(CFLAGS) utils.c -c

clean: 
	rm -f *.o cachesim

caches.h0000644000076400007640000000200412130042025013264 0ustar  crazylylecrazylyle
/* ***************************************************************** */
/*                                                                   */
/*                                                                   */
/* ***************************************************************** */

#include "global.h"
#include "cds.h"

/* ***************************************************************** */
/*                                                                   */
/*                                                                   */
/* ***************************************************************** */

void Read_Cache_Descriptions(String CDS_file_name);

/* ***************************************************************** */
            
void debug_print_cds(CDS *cds);

void Print_Cache_Statistics(void);
void Init_Caches(void);
void Init_caches_for_trace(void);
void Delete_Caches(void);

/* ***************************************************************** */

void Simulate_Caches(String trace_file_name);

cds.h0000644000076400007640000000657612130042025012631 0ustar  crazylylecrazylyle#ifndef _CDS_H_
#define _CDS_H_

/* ***************************************************************** */
/*                                                                   */
/*                                                                   */
/* ***************************************************************** */

/* The Cache Description Structure */
/* The description of a cache. */

/* define the Cache Replacement Policy */
enum CRP
{
    CRP_FIFO,
    CRP_LFU,
    CRP_RANDOM
};



/* ***************************************************************** */
/*                                                                   */
/*                                                                   */
/* ***************************************************************** */
/* Each cache is defined by a number of integers:

   1. The number of entries.
   2. The number of ways.  If we have n entries and m ways, we have n/m sets.
   3. The cache line size.
   4. If the cache is write-back, or write-thru.

   Not that adjusting the number of ways allows us to get the three
   main types (assume the number of entries is n):

   1. Fully-associative -- number of ways = n.
   2. Direct-mapped  -- number of ways = 1.
   3. Set associative -- any other value of n.

   Note that we have to have (number of entries) be evenly divisible by the 
   number of ways.  We can't have 15 lines and 4 ways.

   And we need the cache line size as a power of two.
   And the number of ways must be a power of two.
*/

/* With this description, a cache is then a dynamically allocated
   array of "number of entries" cache lines.  Each cache line is
   (a) an array of bytes (the cache line),
   (b) an address tag (let's just keep the full address of the first byte),
   (c) a dirty bit
   (d) maybe some info for the replacement policy.
*/

struct cache_line
{
    Boolean valid;
    memory_address tag;
    Boolean dirty;
    int     replacement_data;
    byte   *actual_data;
};
typedef struct cache_line cache_line;




/* ***************************************************************** */
/*                                                                   */
/*                                                                   */
/* ***************************************************************** */
/* The actual cache description structure */       

struct CDS
{
    struct CDS *next;  /* linked list of all the CDS */

    String      name;
    int         cache_line_size;
    int         number_of_cache_entries;
    int         number_of_ways;
    Boolean     write_back;
    enum CRP    replacement_policy;

    /* how often to decrease the counts for LFU */
    int         LFU_Decay_Interval;   

    /* array of cache lines */
    cache_line *c;

    /* statistics for each cache policy */
    counter_t number_of_memory_reference;
    counter_t number_of_type[NUMBER_OF_MEMORY_ACCESS_TYPE];

    counter_t number_cache_hits;
    counter_t number_cache_misses;
    counter_t number_memory_reads;
    counter_t number_memory_writes;
};
typedef struct CDS CDS;



/* ***************************************************************** */
/*                                                                   */
/*                                                                   */
/* ***************************************************************** */

/* a linked list of all the cache descriptors */
struct CDS *CDS_root;

#endif
global.h0000644000076400007640000000233512130042025013305 0ustar  crazylylecrazylyle#ifndef _GLOBAL_H_
#define _GLOBAL_H_

/* ***************************************************************** */
/*                                                                   */
/*                                                                   */
/* ***************************************************************** */

/* The global declarations that every C file should have */
#define _GNU_SOURCE  /* for strcasestr */

#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include <string.h>

#define CAST(t,v)  ((t)(v))

typedef short Boolean;
#define TRUE 1
#define FALSE 0

typedef char *String;

Boolean debug;
FILE *debug_file;

/* A byte is just 8 bits */
typedef unsigned char byte;

/* A memory address is a 32-bit integer */
typedef int memory_address;


enum memory_access_type  { MAT_LOAD, MAT_STORE, MAT_FETCH };
#define NUMBER_OF_MEMORY_ACCESS_TYPE 3

/* The type of the statistics counters */
typedef int counter_t;


/* ***************************************************************** */
/*                                                                   */
/*                                                                   */
/* ***************************************************************** */

#endif
utils.h0000644000076400007640000000146412130042025013207 0ustar  crazylylecrazylyle
/* ***************************************************************** */
/*                                                                   */
/*                                                                   */
/* ***************************************************************** */

#include "global.h"

String remember_string(const String name);

/* ***************************************************************** */
/*                                                                   */
/*                                                                   */
/* ***************************************************************** */

int which_power(int n);
unsigned int mask_of(int n);


Boolean ishex(int c);
int hexvalue(int c);
int decvalue(int c);

int skip_line(FILE *file);
int skip_blanks(FILE *file);
cds.c0000644000076400007640000001406012130042025012607 0ustar  crazylylecrazylyle/* ***************************************************************** */
/*                                                                   */
/*                                                                   */
/* ***************************************************************** */

/* cache description support code */

#include "global.h"
#include "cds.h"



/* ***************************************************************** */
/*                                                                   */
/*                                                                   */
/* ***************************************************************** */

String print_sets_and_ways(CDS *cds)
{
    if (cds->number_of_ways == 1) return("direct-mapped");
    if (cds->number_of_ways == cds->number_of_cache_entries) return("fully associative");

    static char buffer[64];
    sprintf (buffer, "%d sets of %d ways", 
             cds->number_of_cache_entries/cds->number_of_ways, cds->number_of_ways);
    return(buffer);
}


/* ***************************************************************** */
/*                                                                   */
/*                                                                   */
/* ***************************************************************** */

String memory_reference_type_name(enum memory_access_type type)
{
    switch(type)
        {
        case MAT_FETCH: return("Fetch");
        case MAT_LOAD:  return("Load");
        case MAT_STORE: return("Store");
        }
    return("invalid");
}


/* ***************************************************************** */
/*                                                                   */
/*                                                                   */
/* ***************************************************************** */

String CRP_name(CDS *cds)
{
    switch(cds->replacement_policy)
        {
        case CRP_FIFO:   return("FIFO");
        case CRP_RANDOM: return("RANDOM");

        case CRP_LFU: 
            {
                static char buffer[64];
                sprintf(buffer, "LFU (decay=%d)", cds->LFU_Decay_Interval);
                return(buffer);
            }

        };
    return("Invalid policy");
}



void debug_print_cds(CDS *cds)
{
    fprintf(debug_file, "%s: Total number of entries: %d\n", cds->name,  cds->number_of_cache_entries);
    fprintf(debug_file, "%s: %s\n", cds->name,  print_sets_and_ways(cds));
    fprintf(debug_file, "%s: Each cache line is %d bytes\n", cds->name,  cds->cache_line_size);
    fprintf(debug_file, "%s: Cache is %s\n", cds->name,  cds->write_back ? "write-back" : "write-thru");
    fprintf(debug_file, "%s: With a %s replacement policy\n", cds->name, CRP_name(cds));
}


/* ***************************************************************** */
/*                                                                   */
/*                                                                   */
/* ***************************************************************** */

void Print_Cache_Statistics_for_one_cache(CDS *cds)
{
    fprintf(stdout, "%s: %d entries of lines of %d bytes; %s, %s, %s\n",
            cds->name, cds->number_of_cache_entries, cds->cache_line_size,
            print_sets_and_ways(cds),
            cds->write_back ? "write-back" : "write-thru",
            CRP_name(cds));
            
    fprintf(stdout, "      %d addresses (%d %s, %d %s, %d %s)\n",
            cds->number_of_memory_reference, 
            cds->number_of_type[MAT_FETCH], memory_reference_type_name(MAT_FETCH), 
            cds->number_of_type[MAT_LOAD], memory_reference_type_name(MAT_LOAD), 
            cds->number_of_type[MAT_STORE], memory_reference_type_name(MAT_STORE));
    
    fprintf(stdout, "      %d hits, %d misses, %d memory reads, %d memory writes\n",
            cds->number_cache_hits, cds->number_cache_misses,
            cds->number_memory_reads, cds->number_memory_writes);

    fprintf(stdout, "\n");
}


void Print_Cache_Statistics(void)
{
    CDS *cds = CDS_root;
    while (cds != NULL)
        {
            Print_Cache_Statistics_for_one_cache(cds);
            cds = cds->next;
        }
}


/* ***************************************************************** */
/*                                                                   */
/*                                                                   */
/* ***************************************************************** */


void init_cache(CDS *cds)
{
    /* we need one cache line for every entry */
    cds->c = calloc(cds->number_of_cache_entries, sizeof(cache_line));
}


void Init_Caches(void)
{
    CDS *cds = CDS_root;
    while (cds != NULL)
        {
            init_cache(cds);
            cds = cds->next;
        }
}


/* ***************************************************************** */
/*                                                                   */
/*                                                                   */
/* ***************************************************************** */

void init_cache_for_trace(CDS *cds)
{
    int i;
    for (i = 0; i < NUMBER_OF_MEMORY_ACCESS_TYPE; i++) cds->number_of_type[i] = 0;
    cds->number_of_memory_reference = 0;

    cds->number_cache_hits = 0;
    cds->number_cache_misses = 0;
    cds->number_memory_reads = 0;
    cds->number_memory_writes = 0;
}

void Init_caches_for_trace(void)
{
    CDS *cds = CDS_root;
    while (cds != NULL)
        {
            init_cache_for_trace(cds);
            cds = cds->next;
        }
}



/* ***************************************************************** */
/*                                                                   */
/*                                                                   */
/* ***************************************************************** */


void delete_cache(CDS *cds)
{
    /* we need one cache line for every entry */
    free(cds->c);
    free(cds->name);
    free(cds);
}


void Delete_Caches(void)
{
    CDS *cds = CDS_root;
    while (cds != NULL)
        {
            CDS *old = cds;
            cds = cds->next;
            delete_cache(old);
        }
}


main.c0000644000076400007640000000514012130042025012761 0ustar  crazylylecrazylyle
/* ***************************************************************** */
/*                                                                   */
/*                                                                   */
/* ***************************************************************** */

/* A program to simulate cache behaviour on a valgrind memory trace. */

/* The input is a description of a set of caches, and a memory trace.
   We run the memory trace on each of the caches, and report statistics. */


#include "global.h"
#include "caches.h"

Boolean debug = FALSE;


/* ***************************************************************** */
/*                                                                   */
/*                                                                   */
/* ***************************************************************** */

void usage(void)
{
    fprintf (stderr,"usage: caches [-d] cache-descriptions-file  memory-trace-file\n");
}

void scanargs(String s)
{
    /* check each character of the option list for
       its meaning. */

    while (*++s != '\0')
        switch (*s)
            {

            case 'd': /* debug option */
                debug = TRUE;
                if (debug)
                    {
                        debug_file = fopen("DEBUG_LOG", "w");
                        if (debug_file == NULL)
                            {
                                fprintf(stderr, "Cannot open DEBUG_LOG\n");
                                debug = FALSE;
                            }
                    }
                break;

            default:
                fprintf (stderr,"caches: Bad option %c\n", *s);
                usage();
                exit(1);
            }
}


/* ***************************************************************** */
/*                                                                   */
/*                                                                   */
/* ***************************************************************** */

int main(int argc, String *argv)
{
    /* main driver program.  There are two input 
       files.
       1. defines the caches
       2. defines the memory trace
    */
       
    /* Process all arguments. */
    /* skip program name */
    argc--, argv++;
    while ((argc > 1) && (**argv == '-'))
        {
            scanargs(*argv);
            argc--, argv++;
        }

    if (argc != 2)
        {
            usage();
            exit(-1);
        }

    Read_Cache_Descriptions(argv[0]);
    Init_Caches();

    Simulate_Caches(argv[1]);

    Print_Cache_Statistics();
    Delete_Caches();

    exit(0);
}
read_cds.c0000644000076400007640000002204112130042025013600 0ustar  crazylylecrazylyle
/* ***************************************************************** */
/*                                                                   */
/*                                                                   */
/* ***************************************************************** */

/* Reading cache descriptions */

#include "global.h"
#include "utils.h"
#include "cds.h"
#include "caches.h"

/* ***************************************************************** */
/*                                                                   */
/*                                                                   */
/* ***************************************************************** */

/* we want to read in a string of some unknown length */
#define MIN_TOKEN_SIZE 128

struct Token
{
    String string;
    int    length;
};
typedef struct Token Token;

Token *new_token(void)
{
    Token *t = CAST(Token *, malloc(sizeof(Token)));
    t->length = MIN_TOKEN_SIZE;
    t->string = CAST(String, malloc(t->length));
    return(t);
}

void delete_token(Token *t)
{
    free(t->string);
    free(t);
}

void put_char_in_token_at(Token *t, char c, int i)
{
    if (i >= t->length)
        {
            /* need more space */
            t->length = 2 * t->length;
            t->string = realloc(t->string, t->length);
            if (t->string == NULL)
                {
                    fprintf(stderr, "Hell has frozen over!!!\n");
                    exit(-1);
                }
        }
    t->string[i] = c;
}


void get_token(FILE *CDS_file, Token *t)
{
    int c;

    /* get the next token in the input stream */
    int i = 0;

    /* token is empty to start */
    put_char_in_token_at(t, '\0', i);

    /* skip spacing, look for first character */
    c = skip_blanks(CDS_file);
    if (c == EOF) return;

    while (isalnum(c) || (c == '_'))
        {
            put_char_in_token_at(t, c, i);
            i = i + 1;
            put_char_in_token_at(t, '\0', i);
            c = getc(CDS_file);
        }

    /* went one too far, put it back */
    ungetc(c, CDS_file);
}


/* ***************************************************************** */
/*                                                                   */
/*                                                                   */
/* ***************************************************************** */

/* Syntax for Cache Descriptions:  { key=value, key=value, ... } */
/* So, we read a key and a value and define the field of the
   cds defined by the key to have the given value. */

int get_key_value_pair(FILE *CDS_file, Token *key, Token *value)
{
    int c;

    /* skip initial spaces */
    c = skip_blanks(CDS_file);
    if (c == EOF) return(EOF);
    if (c == '}') return(EOF);

    /* went one too far, put it back */
    ungetc(c, CDS_file);

    /* we want a string for the key */
    get_token(CDS_file, key);

    /* skip spacing, look for "=" */
    c = skip_blanks(CDS_file);
    if (c == EOF) return(EOF);
    if ((c != '=') && (c != ':') && (c != '-'))
        {
            fprintf(stderr, "not key=value pair: %s %c\n", key->string, c);
            return(EOF);
        }

    /* we want a second string for the value */
    get_token(CDS_file, value);

    /* skip spacing, look for "," */
    c = skip_blanks(CDS_file);
    if (c == EOF) return(EOF);
    if ((c != ',') && (c != ';') && (c != '}'))
        {
            fprintf(stderr, "not key=value pair: %s %c\n", key->string, c);
            return(EOF);
        }
    if (c == '}')
        {
            /* we have the last pair, terminated by a '}'.
               put it back, so that this last pair is processed */
            ungetc(c, CDS_file);
            return(',');
        }

    return(c);
}


void define_key_value_pair(CDS *cds, Token *key, Token *value)
{
    if (debug) fprintf(debug_file, "define %s = %s \n", key->string, value->string);

    /* look for the name */
    if (strcasestr(key->string, "name") != NULL)
        {
            if (cds->name != NULL) free(cds->name);
            cds->name = remember_string(value->string);
            return;
        }

    /* look for line size */
    if ((strcasestr(key->string, "line") != NULL) && (strcasestr(key->string, "size") != NULL))
        {
            int n = atoi(value->string);
            cds->cache_line_size = n;
            return;
        }

    /* look for number of cache entries */
    if (strcasestr(key->string, "entries") != NULL)
        {
            int n = atoi(value->string);
            cds->number_of_cache_entries = n;
            return;
        }

    /* look for the number of ways */
    if (strcasestr(key->string, "ways") != NULL)
        {
            int n = atoi(value->string);
            cds->number_of_ways = n;
            return;
        }

    /* look for write-back */
    if ((strcasestr(key->string, "write") != NULL) && (strcasestr(key->string, "back") != NULL))
        {
            if (strcasestr(value->string, "true") != NULL)
                {
                    cds->write_back = TRUE;
                    return;
                }
            if (strcasestr(value->string, "false") != NULL)
                {
                    cds->write_back = FALSE;
                    return;
                }
        }

    /* look for write-thru */
    if ((strcasestr(key->string, "write") != NULL) && (strcasestr(key->string, "thru") != NULL))
        {
            if (strcasestr(value->string, "true") != NULL)
                {
                    cds->write_back = FALSE;
                    return;
                }
            if (strcasestr(value->string, "false") != NULL)
                {
                    cds->write_back = TRUE;
                    return;
                }
        }

    /* look for the replacement policy */
    if ((strcasestr(key->string, "policy") != NULL) || (strcasestr(key->string, "replace") != NULL))
        {
            if (strcasestr(value->string, "LFU") != NULL)
                {
                    cds->replacement_policy = CRP_LFU;
                    return;
                }
            if (strcasestr(value->string, "random") != NULL)
                {
                    cds->replacement_policy = CRP_RANDOM;
                    return;
                }
            if (strcasestr(value->string, "FIFO") != NULL)
                {
                    cds->replacement_policy = CRP_FIFO;
                    return;
                }
        }

    /* look for line size */
    if ((strcasestr(key->string, "decay") != NULL) && (strcasestr(key->string, "interval") != NULL))
        {
            int n = atoi(value->string);
            cds->LFU_Decay_Interval = n;
            return;
        }

    fprintf(stderr, "don't understand %s = %s\n",key->string, value->string);
} 


CDS *Read_CDS_file_entry(FILE *CDS_file)
{
    int c;

    c = skip_blanks(CDS_file);
    while (c == '#')
        {
            c = skip_line(CDS_file);
        }
    if (c == EOF) return(NULL);

    /* Syntax for Cache Descriptions:  { key=value, key=value, ... } */
    /* So, we read a key and a value and define the field of the
       cds defined by the key to have the given value. */

    if (c != '{')
        {
            fprintf(stderr, "Cache description should start with {, not %c\n", c);
            return(NULL);
        }

    /* starting a new cache description.  Get a structure,
       and fill in default values. */
    CDS *cds = (CDS *)calloc(1,sizeof(CDS));
    cds->name = remember_string("dummy");
    cds->cache_line_size = 64;
    cds->number_of_cache_entries = 1024;
    cds->number_of_ways = 2;
    cds->write_back = TRUE;
    cds->replacement_policy = CRP_FIFO;
    cds->LFU_Decay_Interval = 200000;

    Token *key = new_token();
    Token *value = new_token();
    while (((c = get_key_value_pair(CDS_file, key, value)) != EOF) && (c != '}'))
        {
            define_key_value_pair(cds, key, value);
        }
    delete_token(key);
    delete_token(value);

    if (debug) debug_print_cds(cds);
    
    return(cds);
}


/* ***************************************************************** */
/*                                                                   */
/*                                                                   */
/* ***************************************************************** */

void Read_Cache_Descriptions(String CDS_file_name)
{
    FILE *CDS_file;
    CDS *cds;

    /* open input file */
    CDS_file = fopen(CDS_file_name, "r");
    if (CDS_file == NULL)
        {
            fprintf (stderr,"Cannot open CDS file %s\n", CDS_file_name);
        }
    while ((cds = Read_CDS_file_entry(CDS_file)) != NULL)
        {
            /* we use a linked list for all the cache descriptions,
               but we want to keep the list in the same order that
               we read them in.  Bummer. */
            if (CDS_root == NULL)
                {
                    CDS_root = cds;
                }
            else
                {
                    CDS *q = CDS_root;
                    while (q->next != NULL) q = q->next;
                    q->next = cds;
                }
            cds->next = NULL;
        }
    fclose(CDS_file);
}
simulate.c0000644000076400007640000003447012130100360013665 0ustar  crazylylecrazylyle
/* ***************************************************************** */
/*                                                                   */
/*                                                                   */
/* ***************************************************************** */

/* The code to read a memory trace and simulate it on the various
   caches. */

#include "global.h"
#include "utils.h"        // utility functions
#include "cds.h"          // Cache Description Structures
#include "caches.h"       // cache manipulation code


struct memory_reference
{
    enum memory_access_type  type;
    memory_address           address;
    unsigned int             length;
};
typedef struct memory_reference memory_reference;

static int trace_line_number;



/* ***************************************************************** */
/*                                                                   */
/*                                                                   */
/* ***************************************************************** */

/* read on input line */

void read_reference(FILE *trace_file, memory_reference *reference)
{
    int c;
    /* we have the first character; it defined the
       memory access type.  Skip any blanks, get the
       hexadecimal address, skip the comma and get the length */

    /* skip any leading blanks */
    c = skip_blanks(trace_file);
    
    memory_address a = 0;
    while (ishex(c))
        {
            a = (a << 4) | hexvalue(c);
            c = getc(trace_file);
        }
    if (c != ',')
        {
            fprintf(stderr, "bad trace file input at line %d: %c\n", trace_line_number, c);
            exit(-1);
        }
  
    /* skip the comma */
    /* and get the length */
    int n = 0;
    c = getc(trace_file);    
    while (isdigit(c))
        {
            n = n * 10 + decvalue(c);
            c = getc(trace_file);
        }

    /* skip to end of line */
    while ((c != '\n') && (c != EOF)) c = getc(trace_file);

    /* define reference fields */
    reference->address = a;
    reference->length = n;
}



/* ***************************************************************** */
/*                                                                   */
/*                                                                   */
/* ***************************************************************** */


int Read_trace_file_line(FILE *trace_file, memory_reference *reference)
{
    int c;

    trace_line_number = 0;

    while ((c = getc(trace_file)) != EOF)
        {
            /* start the next line */
            trace_line_number += 1;

            /* skip any leading blanks */
            while (isspace(c) && (c != EOF)) c = getc(trace_file);

            /* what is the character ? */
            switch (c)
                {
                case 'I': /* instruction trace */
                    {
                        reference->type = MAT_FETCH;
                        read_reference(trace_file, reference);
                        return('I');
                    }

                case 'S': /* store */
                    {
                        reference->type = MAT_STORE;
                        read_reference(trace_file, reference);
                        return('S');
                    }

                case 'L': /* load */
                    {
                        reference->type = MAT_LOAD;
                        read_reference(trace_file, reference);
                        return('L');
                    }
                }

            /* apparently not a reference line.  There are a bunch
               of other lines that valgrind puts out.  They start
               with  ====, or --, or such.  Skip the entire line. */
            /* skip to end of line */
            while ((c != '\n') && (c != EOF)) c = getc(trace_file);
        }
    return(EOF);
}


/* ***************************************************************** */
/*                                                                   */
/*                                                                   */
/* ***************************************************************** */

/* LFU counts the number of times something is used.  To prevent
   a large number from just sitting there, we cause it to decay
   over time.  Every "tick" time units, we shift left one bit,
   so that eventually a count will go to zero if it is not continuing
   to be used. */

void Check_For_Decay(CDS *cds)
{
    if (cds->replacement_policy != CRP_LFU) return;

    if ((cds->number_of_memory_reference % cds->LFU_Decay_Interval) == 0)
        {
            int i;
            if (debug) fprintf(debug_file, "%s: LFU decay for all LFU counters\n", cds->name);
            for (i = 0; i < cds->number_of_cache_entries; i++)
                {
                    cds->c[i].replacement_data = cds->c[i].replacement_data/2;
                }
        }
}

/* ***************************************************************** */
/*                                                                   */
/*                                                                   */
/* ***************************************************************** */

int Replacement_policy(CDS *cds, int first_index, int set_size)
{
    int i;
    int victim;

    if (debug) fprintf(debug_file, "%s: look for victim in %d lines starting at %d\n", cds->name,  set_size, first_index);
    /* first look to see if any entry is empty */
    for (i = 0; i < set_size; i++)
        {
            if (!(cds->c[first_index+i].valid))
                {
                    victim = first_index+i;
                    if (debug) fprintf(debug_file, "%s: found empty cache entry at %d\n", cds->name,  victim);
                    return(victim);
                }
        }
    
    victim = first_index; /* default victim */
    switch (cds->replacement_policy)
        {
        case CRP_FIFO:  /* replacement data is the order we were brought in: 1, 2, 3, ... */
                    /* choose the smallest */
            
        case CRP_LFU:  /* replacement data is the number of uses, so
                      choose the smallest */
            {
                int min = cds->c[first_index].replacement_data;
                if (debug) fprintf(debug_file, "%s: replacement data: [%d]: %d", cds->name, victim, min);
                for (i = 1; i < set_size; i++)
                    {
                        if (debug) fprintf(debug_file, ", [%d]: %d", first_index+i, cds->c[first_index+i].replacement_data);
                        if (cds->c[first_index+i].replacement_data < min)
                            {
                                victim = first_index+i;
                                min = cds->c[victim].replacement_data;
                            }
                    }
                if (debug) fprintf(debug_file, "\n");
            }
            break;
                              
        case CRP_RANDOM:  
            victim = first_index + (random() % set_size);
            break;
        }

    if (debug) fprintf(debug_file, "%s: found victim in entry %d\n", cds->name,  victim);
    return(victim);
}

void Set_Replacement_Policy_Data(CDS *cds, int first_index, int i)
{
    switch (cds->replacement_policy)
        {
        case CRP_FIFO:  /* replacement data is the order we were brought in: 1, 2, 3, ... */
            cds->c[first_index+i].replacement_data = cds->number_of_memory_reference;
            break;
            
        case CRP_LFU:  /* replacement data is a count; starts at zero */
            cds->c[first_index+i].replacement_data = 0;
            Check_For_Decay(cds);
            
        case CRP_RANDOM:  
            break;
        }
}

void Update_Replacement_Policy_Data(CDS *cds, int first_index, int i)
{
    switch (cds->replacement_policy)
        {
        case CRP_FIFO:  /* replacement data is the order we were brought in: 1, 2, 3, ... */
            break;
            
        case CRP_LFU:  /* replacement data is the count of the number of uses */
            cds->c[first_index+i].replacement_data += 1;
            Check_For_Decay(cds);
            
        case CRP_RANDOM:  
            break;
        }
}


/* ***************************************************************** */
/*                                                                   */
/*                                                                   */
/* ***************************************************************** */

memory_address Base_Cache_Address(CDS *cds, memory_address a)
{
    /* find number of low-order bits to mask off to find beginning cache
       line address */
    int number_of_low_order_bits = which_power(cds->cache_line_size);
    memory_address low_order_mask = mask_of(number_of_low_order_bits);
    memory_address cache_address = a & (~low_order_mask);
    return(cache_address);
}


void Simulate_Reference_to_Cache_Line(CDS *cds, memory_reference *reference)
{
    if (debug) fprintf(debug_file, "%s: Reference 0x%08X of length %d\n",
                       cds->name, reference->address, reference->length);

    /* find cache line for this reference */
    /* find number of low-order bits to mask off to find beginning cache
       line address */
    
    memory_address cache_address = Base_Cache_Address(cds, reference->address);

    /* shift off low-order offset bits and find bits for 
       indexing into cache table */
    /* the number of sets is the number of cache entries
       divided by the number of ways. */
    int number_of_low_order_bits = which_power(cds->cache_line_size);
    int number_of_sets = cds->number_of_cache_entries/cds->number_of_ways;
    int sets_bits = which_power(number_of_sets);
    memory_address sets_bits_mask = mask_of(sets_bits);
    int cache_set_index = (cache_address >> number_of_low_order_bits) & sets_bits_mask;
    int cache_entry_index = cache_set_index * cds->number_of_ways;
    
    /* index into cache table and search the number of ways to
       try to find cache line. */
    int i;
    for (i = 0; i < cds->number_of_ways; i++)
        {
            if (cds->c[cache_entry_index+i].valid && (cache_address == cds->c[cache_entry_index+i].tag))
                {
                    /* found it -- record cache hit and exit */
                    if (debug) fprintf(debug_file, "%s: Found address 0x%08X in cache line %d\n", cds->name, 
                                       reference->address, cache_entry_index+i);
                    cds->number_cache_hits += 1;

                    /* update reference specific info */
                    if (reference->type == MAT_STORE) 
                        cds->c[cache_entry_index+i].dirty = TRUE;
                    Update_Replacement_Policy_Data(cds, cache_entry_index, i);
                    return;
                }
        }

    /* Did not find it. */
    cds->number_cache_misses += 1;    

    /* Choose a victim from the set */
    int victim = Replacement_policy(cds, cache_entry_index, cds->number_of_ways);
    if (debug) fprintf(debug_file, "%s: Pick victim %d to replace\n", cds->name,  victim);
    
    /* evict victim */

    /* if victim is dirty, must write back to memory first */
    if (cds->c[victim].dirty)
        {
            if (debug) fprintf(debug_file, "%s: Write victim 0x%08X to memory\n", cds->name,  cds->c[victim].tag);
            cds->number_memory_writes += 1;
            cds->c[victim].dirty = FALSE;
        }

    /* fill in victim cache line for this new line */
    cds->c[victim].valid = TRUE;
    cds->c[victim].tag = cache_address;
    cds->c[victim].dirty = (reference->type == MAT_STORE);
    if (debug) fprintf(debug_file, "%s: Read cache line 0x%08X into entry %d\n", cds->name,  cds->c[victim].tag, victim);

    Set_Replacement_Policy_Data(cds, cache_entry_index, victim-cache_entry_index);

    /* read cache line from memory into cache table */
    cds->number_memory_reads += 1;

    if (!cds->write_back && (reference->type == MAT_STORE))
        {
            /* If it's not write-back, then it is write-thru.
               For write-thru, if it's a write, we write to memory. */
            cds->number_memory_writes += 1;
        }

}

void Simulate_Reference_to_Memory(CDS *cds, memory_reference *reference)
{
    cds->number_of_memory_reference += 1;
    cds->number_of_type[reference->type] += 1;

    /* check if the entire reference fits into just one cache line */
    if (Base_Cache_Address(cds, reference->address) == Base_Cache_Address(cds, reference->address + reference->length -1))
        {
            Simulate_Reference_to_Cache_Line(cds, reference);
        }
    else
        {
            /* reference spans two cache lines.  Convert it to two
               references: the first cache line, and the second cache line */
            memory_reference reference1;
            memory_reference reference2;
            /* easiest to compute the second part first */
            reference2.type = reference->type;
            reference2.address = Base_Cache_Address(cds, reference->address + reference->length -1);
            reference2.length = reference->address + reference->length - reference2.address;

            reference1.type = reference->type;
            reference1.address = reference->address;
            reference1.length = reference->length - reference2.length;

            /* but we do the references first, then second */
            Simulate_Reference_to_Cache_Line(cds, &reference1);
            Simulate_Reference_to_Cache_Line(cds, &reference2);
        }
}




/* ***************************************************************** */
/*                                                                   */
/*                                                                   */
/* ***************************************************************** */

/* read each input line, and then simulate that reference on each
   cache. */

void Simulate_Caches(String trace_file_name)
{
    FILE *trace_file;
    memory_reference reference;

    /* open input file */
    trace_file = fopen(trace_file_name, "r");
    if (trace_file == NULL)
        {
            fprintf (stderr,"Cannot open trace file %s\n", trace_file_name);
        }

    Init_caches_for_trace();

    while (Read_trace_file_line(trace_file, &reference) != EOF)
        {
            CDS *cds = CDS_root;
            while (cds != NULL)
                {
                    Simulate_Reference_to_Memory(cds, &reference);
                    cds = cds->next;
                }
        }
    fclose(trace_file);
}
utils.c0000644000076400007640000000607712130042025013207 0ustar  crazylylecrazylyle
/* ***************************************************************** */
/*                                                                   */
/*                                                                   */
/* ***************************************************************** */

/* The code to read a memory trace and simulate it on the various
   caches. */

#include "global.h"
#include "utils.h"        // utility functions


/* ***************************************************************** */
/*                                                                   */
/*                                                                   */
/* ***************************************************************** */

/* n is a power of two, which one? */
/* 1 -> 0; 2 -> 1; ... */
int which_power(int n)
{
    int i = 0;
    int t = 1;
    while (n > t)
        {
            t += t;
            i += 1;
        }
    return(i);
}

/* generate a mask of n low order bits */
/* if we want a mask of two bits, shift a 1 two
   bits over (100), and then subtract one (011). */
unsigned int mask_of(int n)
{
    int m;
    if (n <= 0) return(0);
    m = (1 << n) - 1;
    return(m);
}


/* ***************************************************************** */
/*                                                                   */
/*                                                                   */
/* ***************************************************************** */

Boolean ishex(int c)
{
    if (('0' <= c) && (c <= '9')) return(TRUE);
    if (('a' <= c) && (c <= 'f')) return(TRUE);
    if (('A' <= c) && (c <= 'F')) return(TRUE);
    return(FALSE);
}

int hexvalue(int c)
{
    if (('0' <= c) && (c <= '9')) return(c - '0');
    if (('a' <= c) && (c <= 'f')) return(c - 'a' + 10);
    if (('A' <= c) && (c <= 'F')) return(c - 'A' + 10);
    return(-1);
}

int decvalue(int c)
{
    if (('0' <= c) && (c <= '9')) return(c - '0');
    return(-1);
}


/* ***************************************************************** */
/*                                                                   */
/*                                                                   */
/* ***************************************************************** */

/* MALLOC space for a string and copy it */

String remember_string(const String name)
{
    size_t n;
    String p;

    if (name == NULL) return(NULL);

    /* get memory to remember file name */
    n = strlen(name) + 1;
    p = CAST(String , malloc(n));
    strcpy(p, name);
    return(p);
}

/* ***************************************************************** */
/*                                                                   */
/*                                                                   */
/* ***************************************************************** */

int skip_blanks(FILE *file)
{
    int c;
    while (((c = getc(file)) != EOF) && isspace(c)) /* keep reading */;
    return(c);
}


int skip_line(FILE *file)
{
    int c;
    while (((c = getc(file)) != EOF) && (c != '\n')) /* keep reading */;
    c = skip_blanks(file);
    return(c);
}


lfu_definition0000644000076400007640000000364512130042025014622 0ustar  crazylylecrazylyle{ name=lfu05, line_size = 128, entries = 1024, ways=4, policy=lfu, decay_interval = 050000 }
{ name=lfu10, line_size = 128, entries = 1024, ways=4, policy=lfu, decay_interval = 100000 }
{ name=lfu15, line_size = 128, entries = 1024, ways=4, policy=lfu, decay_interval = 150000 }
{ name=lfu20, line_size = 128, entries = 1024, ways=4, policy=lfu, decay_interval = 200000 }
{ name=lfu25, line_size = 128, entries = 1024, ways=4, policy=lfu, decay_interval = 250000 }
{ name=lfu30, line_size = 128, entries = 1024, ways=4, policy=lfu, decay_interval = 300000 }
{ name=lfu35, line_size = 128, entries = 1024, ways=4, policy=lfu, decay_interval = 350000 }
{ name=lfu40, line_size = 128, entries = 1024, ways=4, policy=lfu, decay_interval = 400000 }
{ name=lfu45, line_size = 128, entries = 1024, ways=4, policy=lfu, decay_interval = 450000 }
{ name=lfu50, line_size = 128, entries = 1024, ways=4, policy=lfu, decay_interval = 500000 }
{ name=lfu55, line_size = 128, entries = 1024, ways=4, policy=lfu, decay_interval = 550000 }
{ name=lfu60, line_size = 128, entries = 1024, ways=4, policy=lfu, decay_interval = 600000 }
{ name=lfu65, line_size = 128, entries = 1024, ways=4, policy=lfu, decay_interval = 650000 }
{ name=lfu70, line_size = 128, entries = 1024, ways=4, policy=lfu, decay_interval = 700000 }
{ name=lfu75, line_size = 128, entries = 1024, ways=4, policy=lfu, decay_interval = 750000 }
{ name=lfu80, line_size = 128, entries = 1024, ways=4, policy=lfu, decay_interval = 800000 }
{ name=lfu85, line_size = 128, entries = 1024, ways=4, policy=lfu, decay_interval = 850000 }
{ name=lfu90, line_size = 128, entries = 1024, ways=4, policy=lfu, decay_interval = 900000 }
{ name=lfu95, line_size = 128, entries = 1024, ways=4, policy=lfu, decay_interval = 950000 }
{ name=lfu10, line_size = 128, entries = 1024, ways=4, policy=lfu, decay_interval = 1000000 }
{ name=lfu100, line_size = 128, entries = 1024, ways=4, policy=lfu, decay_interval = 10000000 }
test_definition0000644000076400007640000000052312130042025015003 0ustar  crazylylecrazylyle{ name=direct, line_size = 128, entries = 1024, ways=1, policy=lru }
{ name=full, line_size = 128, entries = 1024, ways=1024, policy=lru }
{ name=lru, line_size = 128, entries = 1024, ways=4, policy=lru }
{ name=lfu, line_size = 128, entries = 1024, ways=4, policy=lfu }
{ name=fifo, line_size = 128, entries = 1024, ways=4, policy=FIFO }