cache_simulator.c

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

// Config:
int cacheSize, blockSize, associativity, offsetBits, addressBits, isWriteThrough,replacementPolicy,maxAddressBits;
#define MEMORY_SIZE (32 * 1024 * 1024)  // 32 MB

typedef struct Block Block;
typedef struct Cache Cache;
Block* memory;


// Basic structures
struct Block {
    char* data;
    unsigned long tag;
    int valid;
    int dirty;
    int uses;

};

struct Cache {
    Block** blocks;
    int size;
    int blockSize;
    int associativity;
};


// Arthemetic/conversion functions

int log2n(int x) {
    int result = 0;
    while (x >>= 1) result++;
    return result;
}

void decimalToBinary(int decimal, char binaryString[maxAddressBits+1]) {
    binaryString[0] = '\0';

    if (decimal == 0) {
        strncpy(binaryString, "00000000000000000000", maxAddressBits);
        binaryString[maxAddressBits] = '\0';
        return;
    }

    char temp[maxAddressBits];
    int index = 0;

    while (decimal > 0 && index < maxAddressBits) {
        temp[index] = (decimal % 2) + '0';
        decimal /= 2;
        index++;
    }

    while (index < maxAddressBits) {
        temp[index] = '0';
        index++;
    }

    for (int i = 0; i < (maxAddressBits/2); i++) {
        char tempChar = temp[i];
        temp[i] = temp[maxAddressBits-1 - i];
        temp[maxAddressBits-1 - i] = tempChar;
    }

    strncpy(binaryString, temp, maxAddressBits);
    binaryString[maxAddressBits] = '\0';
}

int binaryToDecimal(const char *binaryString) {
    int decimal = 0;
    int len = strlen(binaryString);

    for (int i = 0; i < len; i++) {
        if (binaryString[i] == '0') {
            decimal = (decimal << 1) | 0;
        } else if (binaryString[i] == '1') {
            decimal = (decimal << 1) | 1;
        } else {
            printf("Error: Invalid character '%c' in binary string.\n", binaryString[i]);
            return -1; 
        }
    }

    return decimal;
}

int hexToDecimal(const char *hexString) {
    int decimal = 0;
    for (int i = 0; i < (int)strlen(hexString); ++i) {
        char hexChar = hexString[i];
        if (hexChar >= '0' && hexChar <= '9') {
            decimal = decimal * 16 + (hexChar - '0');
        } else if (hexChar >= 'A' && hexChar <= 'F') {
            decimal = decimal * 16 + (hexChar - 'A' + 10);
        } else if (hexChar >= 'a' && hexChar <= 'f') {
            decimal = decimal * 16 + (hexChar - 'a' + 10);
        } else {
            printf("Invalid hexadecimal character: %c\n", hexChar);
            return -1;  
        }
    }
    return decimal;
}

void hexToBinary(char* hex, char* binary) {
    char* hexDigits = "0123456789ABCDEF";
    char* smallHexDigits = "0123456789abcdef";

    char* binaryDigits[] = {"0000", "0001", "0010", "0011", "0100", "0101", "0110", "0111","1000", "1001", "1010", "1011", "1100", "1101", "1110", "1111"};

    int hexLength = strlen(hex);
    int paddingLength = maxAddressBits - (hexLength*4);

    for (int i = 0; i < paddingLength; i++) {
        strcat(binary, "0"); 
    }

    for (int i = 0; i < hexLength; i++) {

        for (int j = 0; j < 16; j++) {
            if (hexDigits[j] == hex[i] || smallHexDigits[j] == hex[i]) {
                strcat(binary, binaryDigits[j]);
                break;
            }
        }
    }
}

void removePrefix(char *input) {
    if (strncmp(input, "0x", 2) == 0) {
        memmove(input, input + 2, strlen(input) - 1);
    }
}


// Program initialization


Cache* initializeCache(int cacheSize, int blockSize, int associativity) {
    Cache* cache = (Cache*)malloc(sizeof(Cache));

    cache->size = cacheSize;
    cache->blockSize = blockSize;
    cache->associativity = associativity;
    
    addressBits = log2n(cacheSize / (blockSize * associativity));
    int numSets = cacheSize / (blockSize * associativity);

    cache->blocks = (Block**)malloc(numSets * sizeof(Block*));

    for (int i = 0; i < numSets; ++i) {

        cache->blocks[i] = (Block*)malloc(associativity * sizeof(Block)); //(need log2(blocksize) offset maxAddressBits) 
        
        for (int j = 0; j < associativity; ++j) {
            cache->blocks[i][j].data = (char*)malloc(blockSize);
            cache->blocks[i][j].valid = 0;
            cache->blocks[i][j].uses = 0;
            cache->blocks[i][j].dirty = 0;
            cache->blocks[i][j].tag = 9;

        }
    }

    return cache;
}


void initializeMemory(int blockSize) {
    int numBlocks = MEMORY_SIZE / blockSize;
    char binaryAddress[maxAddressBits+1];

    memory = (Block*)malloc(numBlocks * sizeof(Block));
    for (int i = 0; i < numBlocks; ++i) {
        decimalToBinary(i, binaryAddress);
       
        int tagLength = strlen(binaryAddress) - (addressBits + offsetBits);
        char tag[tagLength + 1];      

        strncpy(tag, binaryAddress, tagLength);
        tag[tagLength] = '\0';

        memory[i].data = (char*)malloc(blockSize);
        strcpy(memory[i].data, "");
        memory[i].tag = strtoul(tag, NULL, 2); //to long
        memory[i].valid = 0;
        memory[i].uses = 0;
        memory[i].dirty = 0;

    }
}

// Cache functions

int readCache(Cache* cache, char* addressHex) {
    char binaryAddress[maxAddressBits+1];
    strcpy(binaryAddress, "");
    hexToBinary(addressHex, binaryAddress);

    char address[addressBits + 1];  
    char offset[offsetBits + 1];   
    int tagLength = strlen(binaryAddress) - (addressBits + offsetBits);
    char tag[tagLength + 1];      

    strncpy(tag, binaryAddress, tagLength);
    tag[tagLength] = '\0';
    strncpy(address, binaryAddress + tagLength, addressBits);
    address[addressBits] = '\0';
    strncpy(offset, binaryAddress + tagLength + addressBits, offsetBits);
    offset[offsetBits] = '\0';
    
    int addressIndex;
    int memAddress;
    int offsetIndex;
    memAddress = binaryToDecimal(binaryAddress);
    addressIndex = binaryToDecimal(address);
    offsetIndex = binaryToDecimal(offset);

    int hit = 0;
    int emptyBlockIndex = -1;
    unsigned long tagLong;
    tagLong = strtoul(tag, NULL, 2);
    for (int i = 0; i < associativity; i++) {

        if(emptyBlockIndex == -1 && cache->blocks[addressIndex][i].valid == 0){
            emptyBlockIndex = i;
        }

        if (cache->blocks[addressIndex][i].valid && cache->blocks[addressIndex][i].tag == tagLong) {
            hit = 1;
            cache->blocks[addressIndex][i].uses+=1;
            printf("[Hit]\n[Data] %c\n", cache->blocks[addressIndex][i].data[offsetIndex]);
            return(1);
        }
    }

    if (!hit) {
    printf("[MISS]\n");
        int blockIndex;
        int leastUsed = __INT_MAX__;

        if(emptyBlockIndex!=-1){
            blockIndex = emptyBlockIndex;
            //printf("Found an empty block");
        }
        else{
            if(replacementPolicy==0){
                blockIndex = rand() % cache->associativity; // Random replacement policy
                printf(" -> [rand] Replaced random block\n");

            }

            else if(replacementPolicy==1){ //LFU policy
                for (int i = 0; i < associativity; i++) {
                    if(cache->blocks[addressIndex][i].uses < leastUsed){
                        leastUsed = cache->blocks[addressIndex][i].uses;
                        blockIndex = i;
                    }
                }
                printf(" -> [LFU] Replaced the least used block\n");

            }
        }

        if (cache->blocks[addressIndex][blockIndex].dirty) {

            cache->blocks[addressIndex][blockIndex].dirty = 0;
            char dirtyMemAddress[maxAddressBits+1];
            strcpy(dirtyMemAddress, tag);
            strcat(dirtyMemAddress, address);

            for (int i = 0; i < offsetBits; ++i) {
                strcat(dirtyMemAddress, "0");
            }
            dirtyMemAddress[maxAddressBits] = '\0';
            int dirtyMemIndex;
            dirtyMemIndex = binaryToDecimal(dirtyMemAddress);
            //write it to tag+index+(offsetbits0s) in memory
            memory[dirtyMemIndex] = cache->blocks[addressIndex][blockIndex];
            printf(" -> [WB] Evicted block was dirty, written to memory\n");
            }

        cache->blocks[addressIndex][blockIndex] = memory[memAddress];
        cache->blocks[addressIndex][blockIndex].uses+=1;
        cache->blocks[addressIndex][blockIndex].valid=1;
        cache->blocks[addressIndex][blockIndex].dirty = 0;
        printf(" -> [Block] memory->cache\n[Data] %c\n", cache->blocks[addressIndex][blockIndex].data[offsetIndex]);

    }
    return(0);

}

int writeCache(Cache* cache, char* addressHex, char inputData) {
    char binaryAddress[maxAddressBits+1];
    strcpy(binaryAddress, "");
    hexToBinary(addressHex, binaryAddress);

    char address[addressBits + 1];  
    char offset[offsetBits + 1];   
    int tagLength = strlen(binaryAddress) - (addressBits + offsetBits);
    char tag[tagLength + 1];      

    strncpy(tag, binaryAddress, tagLength);
    tag[tagLength] = '\0';
    strncpy(address, binaryAddress + tagLength, addressBits);
    address[addressBits] = '\0';
    strncpy(offset, binaryAddress + tagLength + addressBits, offsetBits);
    offset[offsetBits] = '\0';
    
    int addressIndex;
    int memAddress;
    int offsetIndex;
    memAddress = binaryToDecimal(binaryAddress);
    addressIndex = binaryToDecimal(address);
    offsetIndex = binaryToDecimal(offset);

    int hit = 0;
    int emptyBlockIndex = -1;
    unsigned long tagLong;
    tagLong = strtoul(tag, NULL, 2);
    for (int i = 0; i < associativity; i++) {
        if(emptyBlockIndex == -1 && cache->blocks[addressIndex][i].valid == 0){
            emptyBlockIndex = i;
        }
        if (cache->blocks[addressIndex][i].tag == tagLong) {
            printf("[HIT]\n");
            hit = 1;
            cache->blocks[addressIndex][i].data[offsetIndex] = inputData;
            cache->blocks[addressIndex][i].valid = 1;
            cache->blocks[addressIndex][i].uses+=1;

            if(!isWriteThrough){
              printf(" -> [WB] Dirty bit set to 1\n");
              cache->blocks[addressIndex][i].dirty = 1;  
            }
            else{
                printf(" -> [WT] Written to memory\n");
                memory[memAddress] = cache->blocks[addressIndex][i];
            }

            printf("[Data] %c\n", cache->blocks[addressIndex][i].data[offsetIndex]);
            return(1);
        }
    }

    if (!hit) {
        printf("[MISS]\n");
        int blockIndex;
        int leastUsed = __INT_MAX__;

        if(emptyBlockIndex!=-1){
            blockIndex = emptyBlockIndex;
            //printf("Found an empty block");
        }
        else{
            if(replacementPolicy==0 ){
                blockIndex = rand() % cache->associativity; // Random replacement policy
                printf(" -> [rand] Replaced random block\n");
            }

            else if(replacementPolicy==1){ //LFU policy
                for (int i = 0; i < associativity; i++) {
                    if(cache->blocks[addressIndex][i].uses < leastUsed){
                        leastUsed = cache->blocks[addressIndex][i].uses;
                        blockIndex = i;
                    }
                }
                printf(" -> [LFU] Replaced the least used block\n");
            }
        }

        printf(" -> [Block] memory->cache\n");

        cache->blocks[addressIndex][blockIndex].uses+=1;

        if (cache->blocks[addressIndex][blockIndex].dirty) {

            cache->blocks[addressIndex][blockIndex].dirty = 0;
            char dirtyMemAddress[maxAddressBits+1];
            strcpy(dirtyMemAddress, tag);
            strcat(dirtyMemAddress, address);

            for (int i = 0; i < offsetBits; ++i) {
                strcat(dirtyMemAddress, "0");
            }
            dirtyMemAddress[maxAddressBits] = '\0';
            int dirtyMemIndex;
            dirtyMemIndex = binaryToDecimal(dirtyMemAddress);
            //write it to tag+index+(offsetbits0s) in memory
            memory[dirtyMemIndex] = cache->blocks[addressIndex][blockIndex];
            printf(" -> [WB] Evicted block was dirty, written to memory\n");

            }
        
        cache->blocks[addressIndex][blockIndex] = memory[memAddress];
        cache->blocks[addressIndex][blockIndex].valid=1;
        cache->blocks[addressIndex][blockIndex].data[offsetIndex] = inputData;
        printf(" -> [Data] Written in cache\n");


        if(!isWriteThrough){
            printf(" -> [WB] Dirty bit set to 1\n");
            cache->blocks[addressIndex][blockIndex].dirty = 1;  
            }
        else{
            memory[memAddress] = cache->blocks[addressIndex][blockIndex];
            printf(" -> [WT] Written to memory\n");
            }

        printf("[Data]: %c\n", cache->blocks[addressIndex][blockIndex].data[offsetIndex]);
   
    }
    return(0);

}

void runRandomOperations(Cache* cache, int numOperations,int* cacheHits, int* cacheMisses) {
    srand(time(NULL)); 

    for (int i = 0; i < numOperations; ++i) {
        char operation = (rand() % 2 == 0) ? 'r' : 'w';
        char addressHex[8];
        sprintf(addressHex, "0x%04X", rand() % (1 << maxAddressBits));

        if (operation == 'r') {
            removePrefix(addressHex);
            if(readCache(cache, addressHex)){
                (*cacheHits)++;
            }
            else{
                (*cacheMisses)++;
            }
        } else if (operation == 'w') {
            char data = (char)('A' + rand() % 26); 
            removePrefix(addressHex);
            if(writeCache(cache, addressHex, data)){
                (*cacheHits)++;
            }
            else{
                (*cacheMisses)++;
            }
        }
    }
}

// User interface

int main() {
    printf("--------------------------------------------------------\n");
    printf("Cache Simulator\n");
    printf("--------------------------------------------------------\n");
    printf("Current memory size: %d (%d MB) (default: 32MB to be lightweight). Please choose appropriate cache size and address inputs.\nYou can edit memory size by changing `MEMORY_SIZE`.\nAdditional commands:\n-> t = Test (runs 10,000 random values in the cache simulator for the entered config)\n-> e = End (ends the program)\n\n", MEMORY_SIZE, MEMORY_SIZE/(1024*1024));


    printf("Enter Cache Size (Kb), Block Size (b):\n");
    scanf(" %d %d", &cacheSize, &blockSize);
    printf("Enter Associativity [0=FA, 1=DM]:, Coherency (WT=1,WB=0), Replacement Policy (0=Rand,1=LFU):\n");
    scanf(" %d %d %d", &associativity, &isWriteThrough, &replacementPolicy);

    cacheSize = cacheSize*1024;
    offsetBits = log2n(blockSize);
    maxAddressBits = log2n(MEMORY_SIZE);

    if (associativity == 0) {
        associativity = cacheSize/blockSize;
    }

    Cache* cache = initializeCache(cacheSize, blockSize, associativity);
    printf("Initialized Cache\n");
    initializeMemory(blockSize);
    printf("Initialized Memory\n");


    char operation, addressHex[8], data;

    //1MB memory, max address = FFFFF + 0x + null terminator = 8 maxAddressBits
    while (1) {
        printf("--------------------------------------------------------\n");
        printf("Enter operation (r/w/e/t), address (ex: 0x0000): ");
        scanf(" %c", &operation);

        if (operation == 't') {
            int numOperations = 10000;
            clock_t start = clock();
            int cacheHits = 0;
            int cacheMisses = 0;

            runRandomOperations(cache, numOperations, &cacheHits, &cacheMisses);

            clock_t end = clock();
            double elapsedSeconds = ((double)(end - start)) / CLOCKS_PER_SEC;
            printf("\n[Simulation Results]\n");
            printf("Hit Rate: %.2f%%\n", ((double)cacheHits / numOperations) * 100);
            printf("Miss Rate: %.2f%%\n", ((double)cacheMisses / numOperations) * 100);
            printf("Total Operation Access Time: %.4f seconds\n", elapsedSeconds);
        } 
        if (operation == 'e') {
            break;
        }

        scanf(" %s", addressHex);
        removePrefix(addressHex);
        int tempCompare = hexToDecimal(addressHex);
        if(tempCompare >= (MEMORY_SIZE/blockSize)){
            printf("Address exceeds main memory capacity. You can either:\n - Increase memory size\n - Choose a smaller address\n - Reduce the Block size\n");
            continue;
        }

        if (operation == 'r') {
            readCache(cache, addressHex);

        } else if (operation == 'w') {
            printf("Enter data (1 byte)");
            scanf(" %c", &data);
            writeCache(cache, addressHex, data);
        }
    }


}