cacheSim.cpp

#include <cstdlib>
#include <iostream>
#include <fstream>
#include <sstream>
#include <string>
#include <vector>

using std::string;
using std::cout;
using std::endl;
using std::cerr;
using std::ifstream;
using std::stringstream;
using std::vector;

struct CacheLine {
    bool valid = false;
    bool dirty = false;
    unsigned long tag = 0;
    unsigned long long lastUsed = 0; // for LRU
};

class CacheLevel {
public:
    CacheLevel(unsigned sizeLog2,
               unsigned bSizeLog2,
               unsigned assocLog2,
               unsigned cycles)
        : sizeLog2(sizeLog2),
          bSizeLog2(bSizeLog2),
          assocLog2(assocLog2),
          cycles(cycles)
    {
        blockSize = 1u << bSizeLog2;
        ways      = 1u << assocLog2;
        unsigned cacheSizeBytes = 1u << sizeLog2;
        numSets   = cacheSizeBytes / (blockSize * ways);

        offsetBits = bSizeLog2;
        indexBits  = 0;
        while ((1u << indexBits) < numSets) {
            ++indexBits;
        }

        sets.assign(numSets, vector<CacheLine>(ways));
        useCounter = 0;
    }

    unsigned getCycles() const { return cycles; }

    struct DecodeResult {
        unsigned long tag;
        unsigned index;
    };

    DecodeResult decode(unsigned long address) const {
        unsigned indexMask = (1u << indexBits) - 1u;
        unsigned index = (address >> offsetBits) & indexMask;
        unsigned long tag = address >> (offsetBits + indexBits);
        return {tag, index};
    }

    // Reconstruct the block's "base" address (offset bits = 0)
    unsigned long blockBaseAddress(unsigned long tag, unsigned index) const {
        unsigned long addr = (tag << (indexBits + offsetBits)) |
                             ((unsigned long)index << offsetBits);
        return addr;
    }

    // access:
    //  - returns true if hit, false if miss
    //  - if an existing line is evicted during allocation:
    //      *evictedValid = true
    //      *evictedBlockAddr = base address of evicted block (offset = 0)
    //      *evictedDirty = old line's dirty bit
    bool access(unsigned long address,
                bool isWrite,
                bool allocateOnMiss,
                unsigned long* evictedBlockAddr,
                bool* evictedValid,
                bool* evictedDirty)
    {
        if (evictedBlockAddr) *evictedBlockAddr = 0;
        if (evictedValid)     *evictedValid     = false;
        if (evictedDirty)     *evictedDirty     = false;

        useCounter++;

        DecodeResult d = decode(address);
        unsigned idx = d.index;
        unsigned long tag = d.tag;

        vector<CacheLine>& set = sets[idx];

        // 1. search for hit
        for (unsigned w = 0; w < ways; ++w) {
            CacheLine &line = set[w];
            if (line.valid && line.tag == tag) {
                // HIT
                line.lastUsed = useCounter;
                if (isWrite) {
                    line.dirty = true; // write-back
                }
                return true;
            }
        }

        // 2. MISS
        if (!allocateOnMiss) {
            // no allocation on miss -> nothing else to do
            return false;
        }

        // 3. choose victim (invalid preferred, else LRU)
        int victim = -1;
        for (unsigned w = 0; w < ways; ++w) {
            if (!set[w].valid) {
                victim = (int)w;
                break;
            }
        }
        if (victim == -1) {
            // all valid -> LRU
            unsigned long long bestTime = set[0].lastUsed;
            victim = 0;
            for (unsigned w = 1; w < ways; ++w) {
                if (set[w].lastUsed < bestTime) {
                    bestTime = set[w].lastUsed;
                    victim = (int)w;
                }
            }
        }

        CacheLine &v = set[victim];

        // report eviction info (if any)
        if (v.valid) {
            if (evictedBlockAddr) {
                *evictedBlockAddr = blockBaseAddress(v.tag, idx);
            }
            if (evictedValid) {
                *evictedValid = true;
            }
            if (evictedDirty) {
                *evictedDirty = v.dirty;
            }
        }

        // overwrite with new block
        v.valid    = true;
        v.dirty    = isWrite;
        v.tag      = tag;
        v.lastUsed = useCounter;

        return false; // miss
    }

    // Invalidate a block if present (for inclusiveness handling)
    void invalidate(unsigned long address) {
        DecodeResult d = decode(address);
        unsigned idx = d.index;
        unsigned long tag = d.tag;

        vector<CacheLine>& set = sets[idx];
        for (unsigned w = 0; w < ways; ++w) {
            CacheLine &line = set[w];
            if (line.valid && line.tag == tag) {
                line.valid = false;
                line.dirty = false;
                // we can stop after first match
                break;
            }
        }
    }

private:
    unsigned sizeLog2;
    unsigned bSizeLog2;
    unsigned assocLog2;
    unsigned cycles;

    unsigned blockSize;
    unsigned numSets;
    unsigned ways;

    unsigned offsetBits;
    unsigned indexBits;

    unsigned long long useCounter;
    vector<vector<CacheLine>> sets; // sets[setIndex][way]
};

class CacheSystem {
public:
    CacheSystem(unsigned bSizeLog2,
                unsigned l1SizeLog2, unsigned l1AssocLog2, unsigned l1Cyc,
                unsigned l2SizeLog2, unsigned l2AssocLog2, unsigned l2Cyc,
                unsigned memCyc, unsigned wrAlloc)
        : BSizeLog2(bSizeLog2),
          L1SizeLog2(l1SizeLog2), L1AssocLog2(l1AssocLog2), L1Cyc(l1Cyc),
          L2SizeLog2(l2SizeLog2), L2AssocLog2(l2AssocLog2), L2Cyc(l2Cyc),
          MemCyc(memCyc), WrAlloc(wrAlloc),
          l1(l1SizeLog2, bSizeLog2, l1AssocLog2, l1Cyc),
          l2(l2SizeLog2, bSizeLog2, l2AssocLog2, l2Cyc),
          totalAccesses(0), L1Misses(0), L2Misses(0),
          totalCycles(0), L2Accesses(0)
    {}

    void access(char op, unsigned long address) {
        bool isWrite = (op == 'w' || op == 'W');

        // We cache on:
        //  - all READs
        //  - write-misses only if WrAlloc == 1 (write-allocate)
        bool shouldCache = (!isWrite) || (WrAlloc == 1);

        totalAccesses++;

        // -------- 1) L1 lookup (NO allocation on miss) --------
        totalCycles += L1Cyc;
        bool hitL1 = l1.access(address, isWrite,
                               /*allocateOnMiss=*/false,
                               nullptr, nullptr, nullptr);
        if (hitL1) {
            return;
        }

        // -------- 2) L1 miss -> L2 lookup --------
        L1Misses++;
        L2Accesses++;  // only main accesses that miss L1 count for L2 miss-rate

        unsigned long evBlockL2 = 0;
        bool evValidL2 = false;
        bool evDirtyL2 = false;

        totalCycles += L2Cyc;
        bool hitL2 = l2.access(address, isWrite,
                               /*allocateOnMiss=*/shouldCache,
                               &evBlockL2, &evValidL2, &evDirtyL2);

        // If L2 evicted a block, enforce inclusiveness:
        if (evValidL2) {
            // inclusive: if that block existed in L1, invalidate it there
            l1.invalidate(evBlockL2);
            // if evDirtyL2 == true, conceptually write back to memory
            // (no extra cycles per assignment instructions).
        }

        if (!hitL2) {
            // -------- 3) L2 miss -> main memory --------
            L2Misses++;
            totalCycles += MemCyc;
            // If shouldCache == true, l2.access (with allocateOnMiss) already
            // inserted the new block when it missed.
            // If shouldCache == false (no-write-allocate write),
            // L2 didn't keep the block; write goes to memory only.
        }

        // -------- 4) Fill into L1 if we should cache --------
        if (shouldCache) {
            unsigned long evBlockL1 = 0;
            bool evValidL1 = false;
            bool evDirtyL1 = false;

            // L1 fill (no extra cycles counted here; part of miss cost)
            l1.access(address, isWrite,
                      /*allocateOnMiss=*/true,
                      &evBlockL1, &evValidL1, &evDirtyL1);

            // If L1 evicted a dirty block, write it back to L2
            if (evValidL1 && evDirtyL1) {
                unsigned long evBlockFromL1 = evBlockL1;

                unsigned long evBlock2b = 0;
                bool evValid2b = false;
                bool evDirty2b = false;

                // write-back to L2; this is NOT a "user" L2 access,
                // so it should not affect L2Accesses or L2Misses
                l2.access(evBlockFromL1,
                          /*isWrite=*/true,
                          /*allocateOnMiss=*/true,
                          &evBlock2b, &evValid2b, &evDirty2b);

                if (evValid2b) {
                    // L2 evicted another line: enforce inclusiveness again
                    l1.invalidate(evBlock2b);
                    // if evDirty2b == true, that victim goes to memory
                    // (no extra time).
                }
            }
        }
    }

    double getL1MissRate() const {
        if (totalAccesses == 0) return 0.0;
        return static_cast<double>(L1Misses) / static_cast<double>(totalAccesses);
    }

    double getL2MissRate() const {
        if (L2Accesses == 0) return 0.0;
        return static_cast<double>(L2Misses) / static_cast<double>(L2Accesses);
    }

    double getAvgAccessTime() const {
        if (totalAccesses == 0) return 0.0;
        return static_cast<double>(totalCycles) / static_cast<double>(totalAccesses);
    }

private:
    // config
    unsigned BSizeLog2;
    unsigned L1SizeLog2, L1AssocLog2, L1Cyc;
    unsigned L2SizeLog2, L2AssocLog2, L2Cyc;
    unsigned MemCyc;
    unsigned WrAlloc;

    // cache levels
    CacheLevel l1;
    CacheLevel l2;

    // stats
    unsigned long long totalAccesses;
    unsigned long long L1Misses;
    unsigned long long L2Misses;
    unsigned long long totalCycles;
    unsigned long long L2Accesses;  // only main accesses (not writebacks)
};

int main(int argc, char **argv) {
    if (argc < 19) {
        cerr << "Not enough arguments" << endl;
        return 0;
    }

    // input trace file is argv[1]
    char* fileString = argv[1];
    ifstream file(fileString);
    if (!file || !file.good()) {
        cerr << "File not found" << endl;
        return 0;
    }

    // Configuration variables
    unsigned MemCyc = 0, BSize = 0, L1Size = 0, L2Size = 0, L1Assoc = 0,
             L2Assoc = 0, L1Cyc = 0, L2Cyc = 0, WrAlloc = 0;

    // Parse flags
    for (int i = 2; i + 1 < argc; i += 2) {
        string s(argv[i]);
        if (s == "--mem-cyc") {
            MemCyc = std::atoi(argv[i + 1]);
        } else if (s == "--bsize") {
            BSize = std::atoi(argv[i + 1]);
        } else if (s == "--l1-size") {
            L1Size = std::atoi(argv[i + 1]);
        } else if (s == "--l2-size") {
            L2Size = std::atoi(argv[i + 1]);
        } else if (s == "--l1-cyc") {
            L1Cyc = std::atoi(argv[i + 1]);
        } else if (s == "--l2-cyc") {
            L2Cyc = std::atoi(argv[i + 1]);
        } else if (s == "--l1-assoc") {
            L1Assoc = std::atoi(argv[i + 1]);
        } else if (s == "--l2-assoc") {
            L2Assoc = std::atoi(argv[i + 1]);
        } else if (s == "--wr-alloc") {
            WrAlloc = std::atoi(argv[i + 1]);
        } else {
            cerr << "Error in arguments" << endl;
            return 0;
        }
    }

    CacheSystem cache(BSize,
                      L1Size, L1Assoc, L1Cyc,
                      L2Size, L2Assoc, L2Cyc,
                      MemCyc, WrAlloc);

    string line;
    while (std::getline(file, line)) {
        if (line.empty()) continue;

        stringstream ss(line);
        char operation = 0;
        string address;

        if (!(ss >> operation >> address)) {
            cout << "Command Format error" << endl;
            return 0;
        }

        // address like "0x1ff91ca8"
        if (address.size() < 3 || address[0] != '0' ||
            (address[1] != 'x' && address[1] != 'X')) {
            cout << "Command Format error" << endl;
            return 0;
        }

        string cutAddress = address.substr(2); // remove "0x"
        unsigned long num = std::strtoul(cutAddress.c_str(), nullptr, 16);

        cache.access(operation, num);
    }

    double L1MissRate = cache.getL1MissRate();
    double L2MissRate = cache.getL2MissRate();
    double avgAccTime = cache.getAvgAccessTime();

    printf("L1miss=%.03f ", L1MissRate);
    printf("L2miss=%.03f ", L2MissRate);
    printf("AccTimeAvg=%.03f\n", avgAccTime);

    return 0;
}