csim.c

#include "cachelab.h"
#include <unistd.h>
#include <getopt.h>
#include <stdio.h>
#include <string.h>
#include "csim.h"
#include <stdlib.h>

int tBit = 0, sBit = 0, bBit = 0;
struct params args;

int main(int argc, char **argv)
{
    // parse command line options
    args = parseOpt(argc, argv);

    // init the cache
    struct cache cache = initTheCache(args.numOfSetIndexBits, args.numOfLinesPerSet);

    // init the bits
    initLineBit(args.numOfSetIndexBits, args.numberOfBlockBits);

    // parse trace file content
    int opSize = 0;
    struct operation *operatios = parseTraceFile(args.pathOfTraceFile, &opSize);

    int totalHitCount = 0, totalMissCount = 0, totalEvictionCount = 0;
    for (int i = 0; i < opSize; i++)
    {
        struct operationStats stats = dealTheOperation(operatios[i], cache);
        totalHitCount += stats.hitCount;
        totalMissCount += stats.missCount;
        totalEvictionCount += stats.evictionCount;
    }

    printSummary(totalHitCount, totalMissCount, totalEvictionCount);

    // free memory
    for (int i = 0; i < cache.numOfSet; i++)
    {
        free(cache.sets[i].lines);
    }
    free(cache.sets);

    return 0;
}

// core logic of cache lab
struct operationStats dealTheOperation(struct operation operation, struct cache cache)
{
    struct operationStats stats =
        {
            hitCount : 0,
            missCount : 0,
            evictionCount : 0
        };
    LOGF("%c %0x,%d", operation.op, operation.address, operation.blockSize)

    if (operation.op == DataLoad)
    {
        stats = dealLoadOperations(operation, cache);
    }
    else if (operation.op == DataStore)
    {
        stats = dealStoreOperations(operation, cache);
    }
    else if (operation.op == DataModify)
    {
        stats = dealLoadOperations(operation, cache);
        struct operationStats stats1 = dealStoreOperations(operation, cache);
        stats.hitCount += stats1.hitCount;
        stats.missCount += stats1.missCount;
        stats.evictionCount += stats1.evictionCount;
    }
    LOG("\n")
    return stats;
}

struct operationStats dealLoadOperations(struct operation operation, struct cache cache)
{
    struct operationStats stats =
        {
            hitCount : 0,
            missCount : 0,
            evictionCount : 0
        };
    struct cacheSet cacheSet = cache.sets[(operation.address & sBit) >> args.numberOfBlockBits];

    int tagBit = operation.address & tBit;
    int hitLineIndex = -1;
    int invalidLineIndex = -1;
    for (int i = 0; i < cacheSet.numOfLinePerSet; i++)
    {
        struct cacheLine line = cacheSet.lines[i];
        if (invalidLineIndex == -1 && line.valid == 0)
        {
            invalidLineIndex = i;
        }
        if (line.valid == 1 && ((line.address & tBit) == tagBit))
        {
            hitLineIndex = i;
            break;
        }
    }
    if (hitLineIndex != -1)
    {
        statHit(&stats);
        useCacheSetAtLine(&cacheSet, hitLineIndex);
        return stats;
    }

    statMiss(&stats);

    if (invalidLineIndex != -1)
    {
        cacheSet.lines[invalidLineIndex].valid = 1;
        cacheSet.lines[invalidLineIndex].address = operation.address;
        useCacheSetAtLine(&cacheSet, invalidLineIndex);
        return stats;
    }

    statEviction(&stats);
    int evictionIndex = cacheSet.numOfLinePerSet - 1;
    cacheSet.lines[evictionIndex].valid = 1;
    cacheSet.lines[evictionIndex].address = operation.address;
    useCacheSetAtLine(&cacheSet, evictionIndex);

    return stats;
}

// very simple lru
void useCacheSetAtLine(struct cacheSet *cacheSet, int index)
{
    struct cacheLine tmp = cacheSet->lines[index];

    for (int i = index; i > 0; i--)
    {
        cacheSet->lines[i] = cacheSet->lines[i - 1];
    }
    cacheSet->lines[0] = tmp;
}

void statEviction(struct operationStats *stat)
{

    LOG(" eviction")
    stat->evictionCount++;
}

void statMiss(struct operationStats *stat)
{
    LOG(" miss")
    stat->missCount++;
}

void statHit(struct operationStats *stat)
{
    LOG(" hit")
    stat->hitCount++;
}

struct operationStats dealStoreOperations(struct operation operation, struct cache cache)
{
    struct operationStats stats =
        {
            hitCount : 0,
            missCount : 0,
            evictionCount : 0
        };
    stats = dealLoadOperations(operation,cache);
    return stats;
}

void initLineBit(int s, int b)
{
    bBit = 1;
    for (int i = 1; i < b; i++)
    {
        bBit = (bBit << 1) | bBit;
    }

    sBit = bBit;
    for (int i = 0; i < s; i++)
    {
        sBit = (sBit << 1) | sBit;
    }
    sBit = (~bBit) & sBit;

    tBit = ~(sBit | bBit);

    // printf("tBit: ");
    // printBits(sizeof(tBit), &tBit);
    // printf("sBit: ");
    // printBits(sizeof(sBit), &sBit);
    // printf("bBit: ");
    // printBits(sizeof(bBit), &bBit);
}

// Assumes little endian
void printBits(size_t const size, void const *const ptr)
{
    unsigned char *b = (unsigned char *)ptr;
    unsigned char byte;
    int i, j;

    for (i = size - 1; i >= 0; i--)
    {
        for (j = 7; j >= 0; j--)
        {
            byte = (b[i] >> j) & 1;
            printf("%u", byte);
        }
    }
    puts("");
}

struct cache initTheCache(int numOfSetIndexBits, int numOfLinesPerSet)
{
    int numOfset = 1;
    for (int i = 0; i < numOfSetIndexBits; i++)
    {
        numOfset = numOfset << 1;
    }

    struct cache cache = {
        numOfSet : numOfset,
        sets : (struct cacheSet *)malloc(sizeof(struct cacheSet) * numOfset)
    };

    for (int i = 0; i < numOfset; i++)
    {
        struct cacheSet c = {
            numOfLinePerSet : numOfLinesPerSet,
            lines : (struct cacheLine *)malloc(sizeof(struct cacheLine) * numOfLinesPerSet)
        };
        for (int i = 0; i < numOfLinesPerSet; i++)
        {
            c.lines[i].valid = 0;
        }
        cache.sets[i] = c;
    }
    return cache;
}

struct operation *parseTraceFile(char *filePath, int *opSize)
{
    FILE *fp = fopen(filePath, "r");
    if (fp == NULL)
    {
        return NULL;
    }

    int operationSize = 0;
    int maxOperationSize = 100;
    struct operation *result = (struct operation *)malloc(maxOperationSize * sizeof(struct operation));

    ValgrindOp op;
    int addr;
    int blockSize;
    while (fscanf(fp, " %c %x,%d\n", &op, &addr, &blockSize) != EOF)
    {
        // printf("op:%c, address:%x, blockSize:%d, end\n", op, addr, blockSize);
        if (op == InstructionLoad)
        {
            continue;
        }
        if (operationSize >= maxOperationSize)
        {
            maxOperationSize *= 2;
            struct operation *newResult = (struct operation *)malloc(maxOperationSize * sizeof(struct operation));
            for (int i = 0; i < operationSize; i++)
            {
                newResult[i] = result[i];
            }
            free(result);
            result = newResult;
        }
        struct operation p = {op : op, address : addr, blockSize : blockSize};
        result[operationSize] = p;
        operationSize++;
    }
    fclose(fp);
    *opSize = operationSize;
    return result;
}

struct params parseOpt(int argc, char **argv)
{
    struct params args;
    args.isVerbose = 0;
    int opt;
    while (-1 != (opt = getopt(argc, argv, "hvs:E:b:t:")))
    {
        switch (opt)
        {
        case 's':
            args.numOfSetIndexBits = atoi(optarg);
            break;
        case 'E':
            args.numOfLinesPerSet = atoi(optarg);
            break;
        case 'b':
            args.numberOfBlockBits = atoi(optarg);
            break;
        case 't':
            strcpy(args.pathOfTraceFile, optarg);
            break;
        case 'v':
            args.isVerbose = 1;
            break;
        default:
            printf("wrong argument\n");
            break;
        }
    }
    return args;
}

csim.h

#ifndef CSIM_H
#define CSIM_H

#define LOGF(format, ...)            \
    if (args.isVerbose)              \
    {                                \
        printf(format, __VA_ARGS__); \
    }

#define LOG(format)     \
    if (args.isVerbose) \
    {                   \
        printf(format); \
    }

struct params
{
    int numOfSetIndexBits;    // s
    int numOfLinesPerSet;     // E
    int numberOfBlockBits;    // b
    char pathOfTraceFile[30]; // t
    int isVerbose;            // v
};

struct params parseOpt(int argc, char **argv);

typedef char ValgrindOp;

const ValgrindOp DataLoad = 'L';
const ValgrindOp DataStore = 'S';
const ValgrindOp DataModify = 'M';
const ValgrindOp InstructionLoad = 'I'; // ignore this one

struct operation
{
    ValgrindOp op;
    int address;
    int blockSize;
};

struct operation *parseTraceFile(char *filePath, int *opSize);

struct cache
{
    int numOfSet;
    struct cacheSet *sets;
};

struct cacheSet
{
    int numOfLinePerSet;
    struct cacheLine *lines;
};

struct cacheLine
{
    int valid;
    int address;
};

struct cache initTheCache(int numOfSetIndexBits, int numOfLinesPerSet);

struct operationStats
{
    int hitCount;
    int missCount;
    int evictionCount;
};

struct operationStats dealTheOperation(struct operation operation, struct cache cache);
struct operationStats dealLoadOperations(struct operation operation, struct cache cache);
struct operationStats dealStoreOperations(struct operation operation, struct cache cache);

void initLineBit(int s, int b);
void printBits(size_t const size, void const *const ptr);

void statEviction(struct operationStats *stat);
void statMiss(struct operationStats *stat);
void statHit(struct operationStats *stat);

void useCacheSetAtLine(struct cacheSet *cacheSet, int index);
#endif