new_cache.tar

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


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.h0000644000076400007640000000214512242032503013276 0ustar  crazylylecrazylyle
/* ***************************************************************** */
/*                                                                   */
/*                                                                   */
/* ***************************************************************** */

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

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

extern void Read_Cache_Descriptions(String CDS_file_name);

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

extern void Print_Cache_Statistics(void);
extern int number_dirty_lines(struct cache *c);
extern void Init_Caches(void);
extern void Init_caches_for_trace(void);
extern void Delete_Caches(void);

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

extern void Simulate_Caches(String trace_file_name);

cds.h0000644000076400007640000000707612242032503012631 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_LRU,
    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;


struct cache
{
    String      name;

    int         cache_line_size;
    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_line;
    int         number_of_cache_entries;

    counter_t number_total_cache_access;
    counter_t number_cache_hits;
    counter_t number_cache_misses;

    counter_t number_miss_reads;
    counter_t number_miss_writes;
};


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

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

    String      name;

    struct cache *c;

    /* statistics for each cache policy */
    counter_t number_of_memory_reference;
    counter_t number_of_type[NUMBER_OF_MEMORY_ACCESS_TYPE];
};
typedef struct CDS CDS;



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

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

extern String memory_reference_type_name(enum memory_access_type type);

#endif
global.h0000644000076400007640000000233512242032503013311 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.h0000644000076400007640000000155712242032503013216 0ustar  crazylylecrazylyle
/* ***************************************************************** */
/*                                                                   */
/*                                                                   */
/* ***************************************************************** */

#include "global.h"

String remember_string(const String name);
String augment_name(const String name, const String plus);

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

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.c0000644000076400007640000001542412242032503012620 0ustar  crazylylecrazylyle/* ***************************************************************** */
/*                                                                   */
/*                                                                   */
/* ***************************************************************** */

/* cache description support code */

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


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

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

    static char buffer[64];
    sprintf (buffer, "%d sets of %d ways", 
             c->number_of_cache_entries/c->number_of_ways, c->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(struct cache *c)
{
    switch(c->replacement_policy)
        {
        case CRP_FIFO:   return("FIFO");
        case CRP_LRU:    return("LRU");
        case CRP_RANDOM: return("RANDOM");

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

        };
    return("Invalid policy");
}



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


void debug_print_cds(CDS *cds)
{
    debug_print_cache(cds->c);
}


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

int percent(int a, int b)
{
    if (b == 0) return(0);
    int n = (a*100/b);
    return(n);
}


void Print_Cache_Statistics_for_one_cache(struct cache *c)
{
    fprintf(stdout, "%s: %d entries of lines of %d bytes; %s, %s, %s\n",
            c->name, c->number_of_cache_entries, c->cache_line_size,
            print_sets_and_ways(c),
            c->write_back ? "write-back" : "write-thru",
            CRP_name(c));
    
    fprintf(stdout, "%s: %d accesses, %d hits (%d%%), %d misses, %d miss reads, %d miss writes\n",
            c->name, c->number_total_cache_access,
            c->number_cache_hits, percent(c->number_cache_hits, c->number_total_cache_access),
            c->number_cache_misses, c->number_miss_reads, c->number_miss_writes);
    
    if (c->write_back)
        fprintf(stdout, "%s: %d dirty cache lines remain\n", c->name, number_dirty_lines(c));
}


void Print_Cache_Statistics_for_one_cds(CDS *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));
    
    Print_Cache_Statistics_for_one_cache(cds->c);
    
    fprintf(stdout, "\n");
}


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


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


void init_cache(CDS *cds)
{
    /* we need one cache line for every entry */
    cds->c->c_line = CAST(cache_line *, calloc(cds->c->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->c->number_miss_reads = 0;
    cds->c->number_miss_writes = 0;

    cds->c->number_total_cache_access = 0;
    cds->c->number_cache_hits = 0;
    cds->c->number_cache_misses = 0;
}

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



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


void delete_one_cache(struct cache *c)
{
    free(c->c_line);
    free(c->name);
}

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

    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.c0000644000076400007640000000514012242032503012765 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.c0000644000076400007640000002334212242032503013611 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 = CAST(char *,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->c->cache_line_size = n;
            return;
        }

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

    /* look for the number of ways */
    if (strcasestr(key->string, "ways") != NULL)
        {
            int n = atoi(value->string);
            cds->c->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->c->write_back = TRUE;
                    return;
                }
            if (strcasestr(value->string, "false") != NULL)
                {
                    cds->c->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->c->write_back = FALSE;
                    return;
                }
            if (strcasestr(value->string, "false") != NULL)
                {
                    cds->c->write_back = TRUE;
                    return;
                }
        }

    /* look for the replacement policy */
    if ((strcasestr(key->string, "policy") != NULL) || (strcasestr(key->string, "replace") != NULL))
        {
            if (strcasestr(value->string, "LRU") != NULL)
                {
                    cds->c->replacement_policy = CRP_LRU;
                    return;
                }
            if (strcasestr(value->string, "LFU") != NULL)
                {
                    cds->c->replacement_policy = CRP_LFU;
                    return;
                }
            if (strcasestr(value->string, "random") != NULL)
                {
                    cds->c->replacement_policy = CRP_RANDOM;
                    return;
                }
            if (strcasestr(value->string, "FIFO") != NULL)
                {
                    cds->c->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->c->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 = CAST(CDS *,calloc(1,sizeof(CDS)));
    cds->name = remember_string("dummy");
    cds->c = CAST(struct cache *,calloc(1,sizeof(struct cache)));

    /* default values */
    cds->c->cache_line_size = 64;
    cds->c->number_of_cache_entries = 1024;
    cds->c->number_of_ways = 2;
    cds->c->write_back = TRUE;
    cds->c->replacement_policy = CRP_FIFO;
    cds->c->LFU_Decay_Interval = 200000;
    cds->c->c_line = NULL;

    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);

    cds->c->name = remember_string(cds->name);

    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.c0000644000076400007640000004507612242032503013700 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 'M': /* read/modify/write -- treat as a store */
                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(counter_t time, struct cache *c)
{
    if (c->replacement_policy != CRP_LFU) return;

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

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

memory_address Base_Cache_Address(struct cache *c, 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(c->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);
}

int Compute_Set_Index(struct cache *c, memory_address cache_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(c->cache_line_size);
    int number_of_sets = c->number_of_cache_entries/c->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 * c->number_of_ways;
    return(cache_entry_index);
}


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

/* search in the cache for the particular cache address we want */
int Search_Cache_For(struct cache *c, memory_address cache_address)
{
    int cache_entry_index = Compute_Set_Index(c, cache_address);
    
    if (debug) fprintf(debug_file, "%s: search cache lines %d to %d for 0x%08X\n",
                       c->name, cache_entry_index, 
                       cache_entry_index+c->number_of_ways-1, cache_address);

    /* index into cache table and search the number of ways to
       try to find cache line. */
    int i;
    for (i = 0; i < c->number_of_ways; i++)
        {
            if (c->c_line[cache_entry_index+i].valid 
                && (cache_address == c->c_line[cache_entry_index+i].tag))
                {
                    c->number_cache_hits += 1;
                    return(cache_entry_index+i);
                }
        }
    c->number_cache_misses += 1;    
    return(-1);
}


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

int Find_Victim_by_Replacement_Policy(struct cache *c, memory_address cache_address)
{
    int i;
    int victim;
    
    int first_index = Compute_Set_Index(c, cache_address);
    int set_size = c->number_of_ways;
    if (debug) fprintf(debug_file, "%s: look for victim in %d lines starting at %d\n", c->name,  set_size, first_index);
    
    /* first look to see if any entry is empty */
    for (i = 0; i < set_size; i++)
        {
            if (!(c->c_line[first_index+i].valid))
                {
                    victim = first_index+i;
                    if (debug) fprintf(debug_file, "%s: found empty cache entry at %d\n", c->name,  victim);
                    return(victim);
                }
        }
    
    /* No empty cache line entry */
    victim = first_index; /* default victim */
    switch (c->replacement_policy)
        {
        case CRP_FIFO:  /* replacement data is the order we were brought in: 1, 2, 3, ... */
                    /* choose the smallest */
            
        case CRP_LRU:  /* replacement data is the time we were last hit */
                    /* choose the smallest */

        case CRP_LFU:  /* replacement data is the number of uses, so
                      choose the smallest */
            {
                int min = c->c_line[first_index].replacement_data;
                if (debug) fprintf(debug_file, "%s: replacement data: [%d, 0x%08X]: %d", c->name, victim, c->c_line[victim].tag, min);
                for (i = 1; i < set_size; i++)
                    {
                        if (debug) fprintf(debug_file, ", [%d, 0x%08X]: %d", first_index+i, c->c_line[first_index+i].tag, c->c_line[first_index+i].replacement_data);
                        if (c->c_line[first_index+i].replacement_data < min)
                            {
                                victim = first_index+i;
                                min = c->c_line[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", c->name,  victim);
    return(victim);
}


void evict_dirty_line_from_cache(struct cache *c, cache_line *victim_line)
{
    if (debug) fprintf(debug_file, "%s: Write dirty victim 0x%08X\n", 
                       c->name,  victim_line->tag);
    c->number_miss_writes += 1;
}


void Set_Replacement_Policy_Data(counter_t time, struct cache *c, cache_line *cache_entry)
{
    switch (c->replacement_policy)
        {
        case CRP_FIFO:  /* replacement data is the order we were brought in: 1, 2, 3, ... */
            cache_entry->replacement_data = time;
            break;
            
        case CRP_LRU:  /* replacement data is the time we were last hit */
            cache_entry->replacement_data = time;
            break;
            
        case CRP_LFU:  /* replacement data is a count; starts at zero */
            cache_entry->replacement_data = 0;
            Check_For_Decay(time, c);
            
        case CRP_RANDOM:  
            break;
        }
}

void Update_Replacement_Policy_Data(counter_t time, struct cache *c, cache_line *cache_entry)
{
    switch (c->replacement_policy)
        {
        case CRP_FIFO:  /* replacement data is the order we were brought in: 1, 2, 3, ... */
            break;
            
        case CRP_LRU:  /* replacement data is the time we were last hit */
            cache_entry->replacement_data = time;
            break;
            
        case CRP_LFU:  /* replacement data is the count of the number of uses */
            cache_entry->replacement_data += 1;
            Check_For_Decay(time, c);
            
        case CRP_RANDOM:  
            break;
        }
}


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

#define swap1(a,b) { int t = a; a = b; b = t; }

void swap_cache_lines(cache_line *a, cache_line *b)
{
    swap1(a->tag, b->tag);
    swap1(a->dirty, b->dirty);
}


Boolean evict_from_cache(CDS *cds, cache_line *victim_line, memory_address cache_address)
{
    /* if victim is dirty, note that this dirty line is being evicted */
    if (victim_line->dirty)
        {
            evict_dirty_line_from_cache(cds->c, victim_line);
        }
            
    return(FALSE);
}


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

void Simulate_Reference_to_Cache_Line(CDS *cds, memory_reference *reference)
{
    Boolean Found = FALSE;
    cache_line *cache_entry = NULL;

    if (debug) fprintf(debug_file, "%s: %s Reference 0x%08X of length %d\n",
                       cds->name, memory_reference_type_name(reference->type),
                       reference->address, reference->length);
    
    cds->c->number_total_cache_access += 1;
    
    /* 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->c, reference->address);
    
    int cache_entry_index = Search_Cache_For(cds->c, cache_address);
    if (cache_entry_index >= 0)
        {
            /* found it -- record cache hit */
            Found = TRUE;
            if (debug) fprintf(debug_file, "%s: Found address 0x%08X in cache line %d\n", cds->name, 
                               reference->address, cache_entry_index);
            cache_entry = &(cds->c->c_line[cache_entry_index]);
        }
    else
        {
            /* Did not find it. */
            Found = FALSE;
            
            /* Choose a victim from the set */
            cache_entry_index = Find_Victim_by_Replacement_Policy(cds->c, cache_address);
            cache_entry = &(cds->c->c_line[cache_entry_index]);
            if (debug) fprintf(debug_file, "%s: Pick victim %d to replace\n", cds->name,  cache_entry_index);
            
            /* evict victim */
            if (cache_entry->valid)
                Found = evict_from_cache(cds, cache_entry, cache_address);
            
            if (!Found)
                {
                    /* fill in evicted cache line for this new line */
                    cache_entry->valid = TRUE;
                    cache_entry->tag = cache_address;
                    cache_entry->dirty = FALSE;
                    
                    /* read cache line from memory into cache table */
                    if (debug) fprintf(debug_file, "%s: Read cache line 0x%08X into entry %d\n", cds->name,  cache_entry->tag, cache_entry_index);
                    cds->c->number_miss_reads += 1;
                }
        }

    /* update reference specific info */
    if (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. */
            if (!cds->c->write_back)
                {
                    cds->c->number_miss_writes += 1;
                    if (debug) fprintf(debug_file, "%s: Write cache line 0x%08X thru to memory\n", cds->name,  cache_entry->tag);
                }
            else
                /* For write-back, if it's a write, it's dirty. */
                cache_entry->dirty = TRUE;
        }
    
    if (!Found)
        Set_Replacement_Policy_Data(cds->number_of_memory_reference, cds->c, cache_entry);
    else
        Update_Replacement_Policy_Data(cds->number_of_memory_reference, cds->c, cache_entry);
}


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

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->c, reference->address) == Base_Cache_Address(cds->c, 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->c, 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);
            exit(1);
        }

    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);
}


int number_dirty_lines(struct cache *c)
{
    int n = 0;
    int i;
    for (i = 0; i < c->number_of_cache_entries; i++)
        {
            if (c->c_line[i].dirty)
                {
                    n += 1;
                    if (debug) fprintf(debug_file, "%s: Cache Line 0x%08X is dirty\n", c->name, c->c_line[i].tag);
                }
        }
    return(n);
}
utils.c0000644000076400007640000000641412242032503013206 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);
}

String augment_name(const String name, const String plus)
{
    int n = strlen(name) + 1 + strlen(plus) + 1;
    String p = CAST(String, malloc(n));
    sprintf(p, "%s %s", name, plus);
    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_definition0000644000076400007640000000364512242032123014624 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 }
lru_definition0000644000076400007640000000010212242032123014621 0ustar  crazylylecrazylyle{ name=lru, line_size = 128, entries = 1024, ways=4, policy=lru }
lruv_definition0000644000076400007640000000011412242032123015012 0ustar  crazylylecrazylyle{ name=lru, line_size = 128, entries = 1024, ways=4, policy=lru, victim=4 }
test1_definition0000644000076400007640000000063212242032123015067 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=8, policy=lfu }
{ name=fifo, line_size = 128, entries = 1024, ways=4, policy=FIFO }
{ name=random, line_size = 128, entries = 1024, ways=4, policy=random}
test2_definition0000644000076400007640000000053312242032123015070 0ustar  crazylylecrazylyle{ name=direct, line_size = 128, entries = 1024, ways=1, policy=FIFO }
{ name=full, line_size = 128, entries = 1024, ways=1024, policy=lfu }
{ name=lfu, line_size = 128, entries = 1024, ways=4, policy=lfu }
{ name=fifo, line_size = 128, entries = 1024, ways=4, policy=FIFO }
{ name=random, line_size = 128, entries = 1024, ways=32, policy=random }
test_definition0000644000076400007640000000063412242032123015010 0ustar  crazylylecrazylyle{ name=direct, line_size = 64, entries = 256, ways=1, policy=lru }
{ name=full, line_size = 64, entries = 256, ways=256, policy=lru }
{ name=lru, line_size = 64, entries = 256, ways=4, policy=lru }
{ name=lfu, line_size = 64, entries = 256, ways=4, policy=lfu }
{ name=fifo, line_size = 64, entries = 256, ways=4, policy=FIFO }
{ name=fifo, line_size = 64, entries = 256, ways=4, policy=FIFO, writethru = true }