csapp/cache_sim.c

配套源码，运行方法见同目录 README。返回实验总览。

/* A small LRU simulator. Cross-block requests are split, unlike Cache Lab's
 * simplifying input assumption. A modify runs the whole load, then the store. */
#include <ctype.h>
#include <errno.h>
#include <inttypes.h>
#include <stdbool.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct { bool valid; uint64_t tag, stamp; } Line;
typedef struct {
    unsigned s, b;
    size_t ways, sets;
    Line *lines;
    uint64_t clock, hits, misses, evictions;
} Cache;

static bool number(const char *text, uint64_t *value) {
    if (!*text || *text == '-') return false;
    char *end;
    errno = 0;
    unsigned long long n = strtoull(text, &end, 10);
    if (errno || *end) return false;
    *value = (uint64_t)n;
    return true;
}

static void access_block(Cache *c, uint64_t address) {
    uint64_t set = (address >> c->b) & (c->sets - 1);
    uint64_t tag = address >> (c->s + c->b);
    Line *lines = c->lines + set * c->ways;
    size_t victim = 0;
    bool found_empty = false;
    ++c->clock;
    for (size_t i = 0; i < c->ways; ++i) {
        if (lines[i].valid && lines[i].tag == tag) {
            ++c->hits;
            lines[i].stamp = c->clock;
            return;
        }
        if (!lines[i].valid) {
            if (!found_empty) victim = i;
            found_empty = true;
        } else if (!found_empty && lines[i].stamp < lines[victim].stamp) {
            victim = i;
        }
    }
    ++c->misses;
    if (lines[victim].valid) ++c->evictions;
    lines[victim] = (Line){true, tag, c->clock};
}

static void access_range(Cache *c, uint64_t address, uint64_t size) {
    uint64_t block = address >> c->b;
    uint64_t last = (address + size - 1) >> c->b;
    for (;;) {
        access_block(c, block << c->b);
        if (block == last) break;
        ++block;
    }
}

int main(int argc, char **argv) {
    uint64_t s, ways, b;
    if (argc != 5 || !number(argv[1], &s) || !number(argv[2], &ways) ||
        !number(argv[3], &b) || s > 20 || b > 63 || s + b > 63 ||
        ways == 0 || ways > (UINT64_C(1) << 22) / (UINT64_C(1) << s)) {
        fprintf(stderr, "usage: %s s E b trace (s<=20, s+b<=63, 1<=E, <=2^22 lines)\n", argv[0]);
        return 2;
    }
    Cache c = {(unsigned)s, (unsigned)b, (size_t)ways, (size_t)1 << s, NULL, 0, 0, 0, 0};
    c.lines = calloc(c.sets * c.ways, sizeof *c.lines);
    if (!c.lines) { perror("calloc"); return 1; }
    FILE *input = fopen(argv[4], "r");
    if (!input) { perror(argv[4]); free(c.lines); return 1; }
    char *line = NULL;
    size_t capacity = 0, lineno = 0;
    int result = 0;
    while (getline(&line, &capacity, input) >= 0) {
        ++lineno;
        char *start = line;
        while (isspace((unsigned char)*start)) ++start;
        if (!*start || *start == '#') continue;
        char op;
        uint64_t address, size;
        int end = 0;
        if (sscanf(start, " %c %" SCNx64 ",%" SCNu64 " %n", &op, &address, &size, &end) != 3 ||
            !end || start[end] || !strchr("ILSM", op) || !size || size > (UINT64_C(1) << 20) ||
            address > UINT64_MAX - (size - 1)) {
            fprintf(stderr, "invalid trace at line %zu\n", lineno);
            result = 2;
            break;
        }
        if (op == 'I') continue;
        access_range(&c, address, size);
        if (op == 'M') access_range(&c, address, size);
    }
    if (ferror(input)) { perror("trace read"); result = 1; }
    if (!result)
        printf("hits:%" PRIu64 " misses:%" PRIu64 " evictions:%" PRIu64 "\n", c.hits, c.misses, c.evictions);
    free(line);
    fclose(input);
    free(c.lines);
    return result;
}