2
\$\begingroup\$

This is an assignment known as a Cachelab from CMU 15-213. The full writeup for the lab can be found here, the handout I'm working against - here. All in all, the task is to emulate a cache, given the amount of block bits, set bits and associativity, run it against a sample valgrind-generated input, output the statistics on hits, misses and evictions. For evictions, LRU should be used. We don't care about actual memory contents in this lab, so we're not doing anything with them. We also don't care about instruction cache, so all the operations with it are ignored.

The code functions correctly. As it's my first C program longer than 20 lines, I'm wondering how bad it is in terms of splitting responsibilities between functions, making code easy to read and understand, making the program flow easy enough to follow, following general practices of writing in C, subtle bugs, usage of calloc, free, naming, etc. The trick is that as I don't know much of good coding practices in C, I don't really know what to ask specifically. Basically, I'm asking if you'd do anything different, and if so, what, how and why?

Code (csim.c):

#include <stdbool.h>
#include <stdlib.h>
#include <stdio.h>
#include <errno.h>
#include <stddef.h>
#include <getopt.h>
#include <limits.h>
// #include "cachelab.h"

extern int errno;

typedef enum {
    LOAD,
    STORE,
    MODIFY,
    INSTRUCTION,
    UNKNOWN,
    END,  // special value to indicate that we reached the end of tracefile
} access_mode_t;

enum lookup_result {
    HIT = 1,
    MISS = 2,
    EVICTION = 4,
};

typedef struct options_t {
    bool help;
    bool verbose;
    unsigned long s;
    unsigned long E;
    unsigned long b;
    char *tracefile;
} options_t;


typedef struct cache_stats_t {
    int misses;
    int hits;
    int evictions;
} cache_stats_t;

typedef struct operation_t {
    unsigned long address;
    access_mode_t access_mode;
    unsigned long size;
} operation_t;

access_mode_t mode_char_to_access_mode(char mode) {
    switch (mode) {
        case 'M':
            return MODIFY;
        case 'L':
            return LOAD;
        case 'S':
            return STORE;
        case 'I':
            return INSTRUCTION;
        default:
            return UNKNOWN;
    }
}

char access_mode_to_mode_char(access_mode_t mode) {
    switch (mode) {
        case MODIFY:
            return 'M';
        case LOAD:
            return 'L';
        case STORE:
            return 'S';
        case INSTRUCTION:
            return 'I';
        default:
            return 0;
    }
}

void parse_options(int argc, char *argv[], options_t *options) {
    int ch;
    while ((ch = getopt(argc, argv, "hvs:E:b:t:")) != -1) {
        switch (ch) {
            case 'h':
                options->help = true;
                break;
            case 'v':
                options->verbose = true;
                break;
                // no error handling in cases below
            case 's':
                options->s = strtoul(optarg, NULL, 16);
                break;
            case 'E':
                options->E = strtoul(optarg, NULL, 16);
                break;
            case 'b':
                options->b = strtoul(optarg, NULL, 16);
                break;
            case 't':
                options->tracefile = optarg;
                break;
            default:
                printf("Invalid option!\n");
                exit(1);
        }
    }
};

void usage() {
    printf("Usage: csim [-hv] -s <num> -E <num> -b <num> -t <file>\n");
    printf("Options:\n");
    printf("  -h         Print this help message.\n");
    printf("  -v         Optional verbose flag.\n");
    printf("  -s <num>   Number of set index bits.\n");
    printf("  -E <num>   Number of lines per set.\n");
    printf("  -b <num>   Number of block offset bits.\n");
    printf("  -t <file>  Trace file.\n");
    printf("\n");
    printf("Example:\n");
    printf("  linux>  csim -s 4 -E 1 -b 4 -t traces/yi.trace\n");

    exit(1);
}

void file_open_r(FILE **f, char* filename) {
    *f = fopen(filename, "r");
    if (errno != 0) {
        perror("");
        exit(errno);
    }
}

void file_close(FILE *f) {
    fclose(f);
}

void load_next_operation(FILE *f, operation_t *operation) {
    char mode;
    unsigned long address;
    unsigned long size;

    // fixme: no error handling here
    if (fscanf(f, " %c %lx,%lx\n", &mode, &address, &size) == EOF) {
        operation->access_mode = END;
        return;
    };

    access_mode_t access_mode = mode_char_to_access_mode(mode);

    operation->address = address;
    operation->access_mode = access_mode;
    operation->size = size;
}

typedef struct cache_line_t {
    bool valid;
    unsigned long tag;
    unsigned long last_accessed;
} cache_line_t;

// returns either a cache_line_t* if value is found in cache, or NULL if it's a cache miss
cache_line_t* cache_hit_line(cache_line_t *set, unsigned long associativity, unsigned long tag) {
    for (unsigned long i = 0; i < associativity; i++) {
        if ((set[i].tag == tag) && set[i].valid) return &set[i];
    }
    return NULL;
}

// returns a cache_line_t* pointing to line to be evicted
cache_line_t *cache_get_eviction_candidate(cache_line_t *set, unsigned long associativity) {
    cache_line_t *result = &set[0];
    unsigned long least_last_accessed = ULONG_MAX;
    for (unsigned long i = 0; i < associativity; i++) {
        if (set[i].last_accessed < least_last_accessed) {
            least_last_accessed = set[i].last_accessed;
            result = &set[i];
        }
    }
    return result;
}

// returns either a pointer to a valid line, or a NULL if an eviction has to happen
cache_line_t *cache_get_write_candidate(cache_line_t *set, unsigned long associativity) {
    for (unsigned long i = 0; i < associativity; i++) {
        if (!set[i].valid) {
            return &set[i];
        }
    }
    return NULL;
}

void cache_write_line(cache_line_t *line, unsigned long tag, unsigned long epoch) {
    line->last_accessed = epoch;
    line->valid = true;
    line->tag = tag;
}

int cache_lookup(cache_line_t *set, unsigned long associativity, unsigned long tag, unsigned long epoch) {
    int result = 0;
    cache_line_t *target_line;
    if ((target_line = cache_hit_line(set, associativity, tag)) != NULL) {
        result |= HIT;
        cache_write_line(target_line, tag, epoch);  // refresh the epoch for correct LRU functioning
    } else {
        result |= MISS;
        if ((target_line = cache_get_write_candidate(set, associativity)) == NULL) {
            target_line = cache_get_eviction_candidate(set, associativity);
            result |= EVICTION;
        }
        cache_write_line(target_line, tag, epoch);
    }
    return result;
}

void verbose_output_operation(operation_t *operation) {
    printf("%c %lx,%lx", access_mode_to_mode_char(operation->access_mode), operation->address, operation->size);
}

void verbose_output_lookup_result(int lookup_result) {
    if ((lookup_result & MISS) == MISS) printf(" miss");
    if ((lookup_result & EVICTION) == EVICTION) printf(" eviction");
    if ((lookup_result & HIT) == HIT) printf(" hit");
}

void verbose_output_end() {
    printf("\n");
}

void store_lookup_result_stats(cache_stats_t *cache_stats, int lookup_result) {
    if ((lookup_result & MISS) == MISS) cache_stats->misses++;
    if ((lookup_result & EVICTION) == EVICTION) cache_stats->evictions++;
    if ((lookup_result & HIT) == HIT) cache_stats->hits++;
}

void calculate_cache_stats(cache_stats_t *cache_stats, char *tracefile, unsigned long set_bits,
                           unsigned long associativity, unsigned long block_bits, bool verbose) {
    unsigned long set_count = 1u << set_bits;

    cache_line_t cache[set_count][associativity];
    for (unsigned long i = 0; i < set_count; i++)
        for (unsigned long j = 0; j < associativity; j++)
            cache[i][j] = (cache_line_t) {0, 0};

    unsigned long block_mask = (1u << block_bits) - 1;
    unsigned long set_mask = ((1u << set_bits << block_bits) - 1) ^block_mask;
    unsigned long tag_mask = ~0u ^block_mask ^set_mask;
    unsigned long epoch = 0;
    operation_t *operation = malloc(sizeof(operation_t));

    unsigned long operation_set;
    unsigned long operation_tag;
    FILE *fp;
    file_open_r(&fp, tracefile);

    load_next_operation(fp, operation);
    while (operation->access_mode != END) {
        operation_set = (operation->address & set_mask) >> block_bits;
        operation_tag = (operation->address & tag_mask) >> set_bits >> block_bits;

        // workhorse
        cache_line_t *set = cache[operation_set];

        int last_lookup_result;
        if (verbose) verbose_output_operation(operation);

        switch (operation->access_mode) {
            case LOAD:
            case STORE:
                last_lookup_result = cache_lookup(set, associativity, operation_tag, epoch);
                if (verbose) verbose_output_lookup_result(last_lookup_result);
                store_lookup_result_stats(cache_stats, last_lookup_result);
                break;
            case MODIFY:
                // modify is essentially load+store
                for (int i = 0; i < 2; i++) {
                    last_lookup_result = cache_lookup(set, associativity, operation_tag, epoch);
                    if (verbose) verbose_output_lookup_result(last_lookup_result);
                    store_lookup_result_stats(cache_stats, last_lookup_result);
                }
                break;
            case INSTRUCTION:
                break;
            case UNKNOWN:
            default:
                printf("Unknown operation, aborting...\n");
                file_close(fp);
                free(operation);
                exit(1);
        }
        if (verbose) verbose_output_end();

        epoch++;
        load_next_operation(fp, operation);
    };

    file_close(fp);
    free(operation);
}

int main(int argc, char *argv[]) {
    options_t *options = calloc(1, sizeof(options_t));
    parse_options(argc, argv, options);
    if (options->help) usage();
    cache_stats_t *cache_stats = calloc(1, sizeof(cache_stats_t));
    calculate_cache_stats(cache_stats, options->tracefile, options->s, options->E, options->b, options->verbose);

    // below function is included from cachelab.h, but it's rather uninteresting.
    //    printSummary(cache_stats->hits, cache_stats->misses, cache_stats->evictions);
    printf("hits:%d misses:%d evictions:%d\n", cache_stats->hits, cache_stats->misses, cache_stats->evictions);

    free(options);
    free(cache_stats);
    return 0;
}

Sample input file (traces/yi.trace):

 L 10,1
 M 20,1
 L 22,1
 S 18,1
 L 110,1
 L 210,1
 M 12,1

Sample run:

./csim -s 2 -E 2 -b 3 -t traces/yi.trace
hits:3 misses:6 evictions:2

CMakeLists.txt:

cmake_minimum_required(VERSION 3.10)

project(cachelab)

set(SOURCES csim.c)
set(TARGET csim)

add_executable(${TARGET} ${SOURCES})

target_include_directories(${TARGET} PRIVATE .)
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.