first.c

//
//  first.c
//  pa4
//
//  Alexander Goodkind
//  amg540
//

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


typedef struct _QueueNode {
    unsigned long tag_index;
    struct _QueueNode * next, * previous;
} QueueNode;

typedef struct _CacheQueue {
    unsigned count;  // Number of filled frames
    QueueNode * head, * tail;
} CacheQueue;

CacheQueue * create_cache (CacheQueue * cache);
void increment_counter (char counter);
void read_cache (CacheQueue * cache, unsigned long address);
void free_cache (CacheQueue * cache);
void write_cache (CacheQueue * cache, unsigned long address);
int is_power_of_two (double num);
int is_queue_available (CacheQueue * queue);
int is_queue_full (CacheQueue * queue);
int is_queue_empty (CacheQueue * queue);
void dequeue (CacheQueue * queue);
QueueNode * new_node (unsigned long tag_index);
void enqueue (CacheQueue * queue, unsigned long tag_index);
int is_in_queue (CacheQueue * queue, unsigned long tag_index);
void prefetch_block(CacheQueue * queue, unsigned long address);

unsigned long B, C, E, S;
int b, c, s, e, /*t,*/ prefetch, cache_misses, cache_hits, memory_reads, memory_writes, pf_cache_misses, pf_cache_hits, pf_memory_reads, pf_memory_writes;

int main(int argc, char * argv[]) {
    
    // ./first <cache size> <associativity> <cache policy> <block size> <trace file>
    
    if (argc != 6) {
        printf("error");
        return 0;
    }
    
    /*block size*/
    B = atoi(argv[4]); // b ex 4 so 2^4=16, b = 4
    
    /*cache size*/
    C = atoi(argv[1]); // ex: 32 * 1024 = 32KB = 2^15, c = 15
    
    if (is_power_of_two(B) && is_power_of_two(C)) {
        b = log2(B);
        c = log2(C);
    } else {
        printf("error");
        return 0;
    }
    
    char * associativity = argv[2]; // assoc:n, largest being 32, ex. 4
    char * cache_policy = argv[3]; // lru
    
    if (strcmp(associativity, "direct") == 0) { // direct mapped
        E = 1; // E = 2^0 = 1
        S = C / B;
    } else if (associativity[5] == ':' && associativity[0] == 'a') { // assoc:n
        sscanf(associativity, "assoc:%ld", &E); // E = assoc level
        if (is_power_of_two(E)) {
            e = log2(E);
        } else {
            printf("error");
            return 0;
        }
        
        S = C / B / E;
    } else if (associativity[5] != ':' && associativity[0] == 'a') {
        // full assoc
        // S = 1
        // S*E = C / B
        // S = 1 = 1*E = C/B
        // E = C / B
        S = 1;
        E = C / B;
    }
    
    FILE * trace_file = fopen(argv[5], "r");
    
    s = (int) log2(S);
    e = (int) log2(E);
//    t = 48 - b - s;
    
//    printf("%d", strcmp(cache_policy, "lru"));
    
    if (trace_file == NULL || e < 0 || e > 48 || c < 0 || c > 48 || b < 0 || b > 48 || s < 0 || s > 48 || strcmp(cache_policy, "lru")) { // input validation
        printf("error");
        return 0;
    }
    
    CacheQueue * cache = NULL;  // the cache to be used
    CacheQueue * pf_cache = NULL;
    cache = create_cache(cache);
    pf_cache = create_cache(pf_cache);
    

    // printf("\nprefetch: %d\n", prefetch);
    // read
    // write
    
    unsigned long address;
    char mode;
    char input[48];
    
    while (fgets(input, 40, trace_file)) {

        if (input[0] == '#') {
            break;
        } else {
            sscanf(input,"%*x: %c %lx\n", &mode, &address);
            
            if (mode == 'R') {
                prefetch = 0;
                read_cache(cache, address); // no prefetch
                prefetch = 1;
                read_cache(pf_cache, address); // with prefetch
            } else if (mode == 'W') {
                prefetch = 0;
                write_cache(cache, address);
                prefetch = 1;
                write_cache(pf_cache, address);
            }
        }
    
    }

    fclose(trace_file);

    printf("no-prefetch\n");
    printf("Memory reads: %d\n", memory_reads);
    printf("Memory writes: %d\n", memory_writes);
    printf("Cache hits: %d\n", cache_hits);
    printf("Cache misses: %d\n", cache_misses);
    printf("with-prefetch\n");
    printf("Memory reads: %d\n", pf_memory_reads);
    printf("Memory writes: %d\n", pf_memory_writes);
    printf("Cache hits: %d\n", pf_cache_hits);
    printf("Cache misses: %d\n", pf_cache_misses);

    
    free_cache(cache); // needed
    free_cache(pf_cache);
    
    return 0;
}

CacheQueue * create_cache(CacheQueue * cache) {
    cache = (CacheQueue *) malloc(S * sizeof(CacheQueue));
    
    int i;

    for (i = 0; i < S; i++) {
        cache[i].head = NULL;
        cache[i].tail = NULL;
        cache[i].count = 0;
    }
    
    return cache;
}

void read_cache(CacheQueue * cache, unsigned long address) {
    // need tag, set index, block index
    // use bit operations to get and store them
    unsigned long set_index = 0;
    //unsigned long block_index = 0;
    unsigned long tag_index = 0;
    
    //block_index = address & ((1 << b) - 1);
    tag_index = address >> (s + b);
    
//    printf("%llu %llu %llu %llu", set_index, block_index, tag_index, i);
    
    if (s) {
        set_index = (address & ((1 << (s + b)) - 1)) >> b;
    }
    
    CacheQueue * line_queue = &cache[set_index];
//
    if (is_in_queue(line_queue, tag_index)) {
        increment_counter('h');
//        printf("%d", pf_cache_hits);
    } else { // miss
        
        increment_counter('m');
        increment_counter('r');
        
        enqueue(line_queue, tag_index);

        if (prefetch) {
            prefetch_block(cache, address);
        }
    }
    
    printf("==========================\n");
    printf("tag_match: %d\n", is_in_queue(line_queue, tag_index));
    printf("address: %lx\n", address);
    printf("set: %lx\n", set_index);
    printf("tag: %lx\n", tag_index);
    printf("full set: %d\n", is_queue_full(line_queue));
    printf("empty set: %d\n", is_queue_empty(line_queue));
    printf("non-full set: %d\n", is_queue_available(line_queue));
    printf("set count: %d\n", line_queue->count);
    printf("hit: %d\n", cache_hits);
    printf("miss: %d\n", cache_misses);
    printf("==========================\n");
}

void write_cache(CacheQueue * cache, unsigned long address) {
    // if write miss: the block is first read from memory (one memory read), and then followed by a memory write.
    increment_counter('w');
    read_cache(cache, address);
}

void free_cache(CacheQueue * cache) {
    int i;
   
    for (i = 0; i < S; i++) {
        if (is_queue_empty(&cache[i])) {
            break;
        } else {
            QueueNode * current = cache[i].head; // just start at head and go until NULL
            QueueNode * next = NULL;
            while (current->next != NULL) {
                next = current->next;
                free(current);
                current = next;
            }
        }
    }
    
    free(cache);
}

int is_power_of_two(double num) { // returns int cast of num if proper power of 2, else returns 0
    return round(log2(num)) == log2(num);
}

void increment_counter(char counter) {
    switch(counter) {
        case 'w':
            if (prefetch) {
                pf_memory_writes++;
            } else {
                memory_writes++;
            }
            break;
        case 'r':
            if (prefetch) {
                pf_memory_reads++;
            } else {
                memory_reads++;
            }
            break;
        case 'h':
            if (prefetch) {
                pf_cache_hits++;
            } else {
                cache_hits++;
            }
            break;
        case 'm':
            if (prefetch) {
                pf_cache_misses++;
            } else {
                cache_misses++;
            }
            break;
        default:
            break;
    }
}


int is_queue_available(CacheQueue * queue) {
    // checks if queue has space in it
    return queue->count < E;
}

int is_queue_empty(CacheQueue * queue) {
    // checks if queue is completely empty
    if (queue->count == 0) {
        return 1;
    } else {
        return 0;
    }
}

int is_queue_full(CacheQueue * queue) {
    return queue->count == E;
}

void dequeue (CacheQueue * queue) {
    if (is_queue_empty(queue)) {
        return;
    }
    
    // If this is the only node in list, then change head
    if (queue->head == queue->tail) {
        queue->head = NULL;
    }
    
    // Change tail and remove the previous tail
    QueueNode * temp_node = queue->tail;
    queue->tail = queue->tail->previous;
    
    if (queue->tail) {
        queue->tail->next = NULL;
    }
    
    free(temp_node);
    
    queue->count--;
    
}

QueueNode * new_node (unsigned long tag_index) {
    QueueNode * temp_node = (QueueNode *) malloc(sizeof(QueueNode));
    temp_node->tag_index = tag_index;
    
    // Initialize prev and next as NULL
    temp_node->previous = NULL;
    temp_node->next = NULL;
    
    return temp_node;
}

void enqueue (CacheQueue * queue, unsigned long tag_index) {
    QueueNode * temp = new_node(tag_index);

    if (is_queue_empty(queue)) {
        // when empty queue change both head and tail pointers
        queue->head = temp;
        queue->tail = temp;
    } else if (is_queue_available(queue)){ // when the queue has space but isnt completely full
        temp->next = queue->head;
        queue->head->previous = temp;
//        queue->head->next stays the same
        queue->head = temp;
    } else if (is_queue_full(queue)){ // when queue is completely full, we need to evict
//        printf("here\n");
        // LRU
        dequeue(queue); // make some space
        temp->next = queue->head;
        queue->head->previous = temp;
        //        queue->head->next stays the same
        queue->head = temp;
    }
    
    queue->count++;
}

int is_in_queue (CacheQueue * queue, unsigned long tag_index) {
    if (is_queue_empty(queue)) {
        return 0;
    } else {
        QueueNode * current = queue->head; // just start at head and go until NULL

        while (current != NULL) {
            if (current->tag_index == tag_index) {
    //            printf("tag from queue: %llx\n", current->tag_index);
                return 1;
            }
             current = current->next;
        }
    }
    
    return 0;
}


void prefetch_block(CacheQueue * queue, unsigned long address) {

//    printf("prefetching a %lu byte offset of %lx\n", B, address);
    
    unsigned long pf_tag_index = (address + B) >> (s + b);
    unsigned long pf_set_index = 0;
    
//    printf("pf_set: %lx\n", pf_set_index);
//    printf("pf_tag: %lx\n", pf_tag_index);
    
    if (s) {
        pf_set_index = ((address + B) & ((1 << (s + b)) - 1)) >> b;
    }
    
    CacheQueue * line_queue = &queue[pf_set_index];
    
    if (!is_in_queue(line_queue, pf_tag_index)) { // no need to prefetch if already in queue
        enqueue(line_queue, pf_tag_index);
        increment_counter('r');
    }
}