CSAPP Cache Lab I: Let's simulate a cache memory!

For the CSAPP Cache Lab, the students are asked to write a small C program (200~300 lines) that simulates a cache memory.

The full code is here on GitHub.

Understanding a Cache

1. The Anatomy of a Cache ($S$, $E$, $B$, $m$)

A cache can be described with the following four parameters:

• $S = 2^s$ (Cache Sets): The cache is divided into sets.
• $E$ (Cache Lines per set): This is the “associativity.”
  • If $E=1$, it’s a direct-mapped cache. If $E>1$, it’s set-associative.
  • Each line contains a valid bit, a tag, and the actual data block.
• $B = 2^b$ (Block Size): The number of bytes stored in each line.
  • The $b$ bits at the end of an address tell the cache the offset within that block.
• $m$: The bits of the machine memory address.

2. Address Decomposition

When the CPU wants to access a 64-bit address, the cache doesn’t look at the whole number at once. It slices the address into three distinct fields:

Field	Purpose
Tag	Used to uniquely identify the memory block within a specific set. t = m - b - s
Set Index	Determines which set the address maps to.
Block Offset	Identifies the specific byte within the cache line.

3. The “Search and Match” Process

When our simulator receives an address (e.g., from an L or S operation in the trace file), it follows these steps:

1. Find the Set: Use the set index bits to jump to the correct set in our cache structure.
2. Search the Lines: Look through all the lines in that set.

• Hit: If a line has valid == true AND the tag matches the address tag.
• Miss: If no line matches.

3. Handle the Miss:

• Cold Start: If there is an empty line (valid == false), fill it with the new tag and set valid = true.
• Eviction: If all lines are full, we must kick one out. This is where the LRU (Least Recently Used) policy comes in: we find the line that hasn’t been touched for the longest time and replace it.

Lab Requirements

For this Lab Project, we will write a cache simulator that takes a valgrind memory trace as an input.

Input

The input looks like:

I 0400d7d4,8
 M 0421c7f0,4
 L 04f6b868,8
 S 7ff0005c8,8

Each line denotes one or two memory accesses. The format of each line is

[space]operation address,size

The operation field denotes the type of memory access:

• “I” denotes an instruction load, “L” a data load,
• “S” a data store
• “M” a data modify (i.e., a data load followed by a data store).

Mind you: There is never a space before each “I”. There is always a space before each “M”, “L”, and “S”.

The address field specifies a 64-bit hexadecimal memory address. The size field specifies the number of bytes accessed by the operation.

CLI

Our program should take the following command line arguments:

Usage: ./csim-ref [-hv] -s <s> -E <E> -b <b> -t <tracefile>

• -h: Optional help flag that prints usage info
• -v: Optional verbose flag that displays trace info
• -s <s>: Number of set index bits (S = 2s is the number of sets)
• -E <E>: Associativity (number of lines per set)
• -b <b>: Number of block bits (B = 2b is the block size)
• -t <tracefile>: Name of the valgrind trace to replay

Caveats

For this lab, we ignore all Is (the instruction cache accesses).

We assume that memory accesses are aligned properly, such that a single memory access never crosses block boundaries.

The Codes

We basically start from scratch, given an almost blank csim.c file to fill in. The file comes with only a main function and no header files.

Data Models

// Data Model
char* fileName = NULL;
int set_bit = -1;
long long sets = -1;
int associativity = -1;
int block_bit = -1;
long long block_size = -1;
bool verboseMode = false;

int global_timer = 0; // For LRU

int memory_bit = 64; // Assuming 64-bit addresses
int tag_bit = 0; // Tag bits

Handling Command-Line Arguments

First, we add the int argc, char** argv parameters to the main function. argc stands for argument count, while argv stands for argument values.

We use getopt to parse arguments.

void handleArgs(int argc, char** argv){
    int opt;

    while ((opt = getopt(argc, argv, "hvs:E:b:t:")) != -1) {
        switch(opt) {
            case 'h':
                printUsage(argv);
                exit(0);
            case 'v':
                verboseMode = true;
                break;
            case 't':
                fileName = optarg;
                break;
            case 's':
                set_bit = atoi(optarg);
                break;
            case 'E':
                associativity = atoi(optarg);
                break;
            case 'b':
                block_bit = atoi(optarg);
                break;
            case '?':
                printUsage(argv);
                exit(1);
            default:
                exit(1); 
        }
    }

    if(fileName == NULL || set_bit == -1 || associativity == -1 || block_bit == -1) {
        printf("Missing required command line argument");
        printUsage(argv);
        exit(1);
    }

    sets = 1LL << set_bit;
    block_size = 1LL << block_bit;
    
    tag_bit = memory_bit - (set_bit + block_bit);
}

getopt comes in unistd.h, but the compiler option is set to -std=c99, which hides all POSIX extensions. GNU systems provide a standalone <getopt.h> header. So we include getopt.h instead.

opt = getopt(argc, argv, "hvs:E:b:t:")

• h and v: These are boolean flags.
• s:, E:, b:, and t:: These are required arguments. The colon tells getopt that these flags must be followed by a value (e.g., -s 4).

After parsing the arguments, we set the initial value of our Cache Data Model.

sets = 1LL << set_bit;
block_size = 1LL << block_bit;

tag_bit = memory_bit - (set_bit + block_bit);

Initialize Cache

// Cache Line Structure
typedef struct CacheLine {
    bool valid;
    long long tag;
    /*
        Need LRU stamp to implement LRU eviction policy
    */
    int lru_counter;
} CacheLine;

CacheLine** cache = NULL;

void initCache() {
    // Initialize cache data structures
    cache = (CacheLine**) malloc(sizeof(CacheLine*) * sets);
    for(int i = 0; i<sets; i++){
        cache[i] = (CacheLine*) calloc(associativity, sizeof(CacheLine));
    }   
}

Caution: malloc has to be initialized. Or the data might contain garbage values.

So we use calloc. The calloc (stands for contiguous allocation) function is similar to malloc but it initializes the allocated memory to zero.

And don’t forget to free the allocated memory!

void freeCache() {
    // Free allocated memory for cache
    for(int i = 0; i<sets; i++) free(cache[i]);
    free(cache);
}

Handling File Input

  // Handle trace file
  FILE *traceFile = fopen(fileName, "r");
  if (traceFile == NULL) {
      printf("Error opening file: %s\n", fileName);
      exit(1);
  }
  char operation;
  long long address;
  int size;
  while (fscanf(traceFile, " %c %llx,%d", &operation, &address, &size) == 3) {
      switch (operation) {
          case 'L':
              // Handle load operation
              loadData(address, size);
              break;
          case 'S':
              // Handle store operation
              storeData(address, size);
              break;
          case 'M':
              // Handle modify operation
              modifyData(address, size);
              break;
          default:
              // Ignore other operations
              break;
      }
  }
  // Close trace file
fclose(traceFile);

Caution:

1. fscanf does not skip spaces before %c, so we add a space before %c in the format string.
2. !feof(traceFile) does not work correctly here.It only returns true after a read operation has already attempted to go past the end of the file and failed. Using it as a loop condition (e.g., while (!feof(p))) causes an “off-by-one” error, where the loop executes one extra time with garbage data from the last successful read.

Parsing Addresses

// Parse Line Structure
long long getTag(long long address) {
    return address >> (set_bit + block_bit);
}

long long getSetIndex(long long address) {
    long long mask = (1LL << set_bit) - 1;
    return (address >> block_bit) & mask;
}

long long getBlockOffset(long long address) {
    long long mask = (1LL << block_bit) - 1;
    return address & mask;
}

We use bit masks to parse the addresses.

Loading Cache

void loadData(long long address, int size) {
    // Simulate accessing data at the given address
    int s = getSetIndex(address);
    long long t = getTag(address);
    global_timer++;

    for (int i = 0; i < associativity; i++) {
        if (cache[s][i].valid && cache[s][i].tag == t) {
            hit_count++;
            cache[s][i].lru_counter = global_timer;
            if (verboseMode) printf(" hit");
            return;
        }
    }

    miss_count++;
    if (verboseMode) printf(" miss");

    for (int i = 0; i < associativity; i++) {
        if (!cache[s][i].valid) {
            cache[s][i].valid = true;
            cache[s][i].tag = t;
            cache[s][i].lru_counter = global_timer; 
            return;
        }
    }

    eviction_count++;
    if (verboseMode) printf(" eviction");

    int victim_index = 0;
    int min_lru = cache[s][0].lru_counter;

    for (int i = 1; i < associativity; i++) {
        if (cache[s][i].lru_counter < min_lru) {
            min_lru = cache[s][i].lru_counter;
            victim_index = i;
        }
    }

    cache[s][victim_index].tag = t;
    cache[s][victim_index].lru_counter = global_timer;
}

The code simulates the process of loading cache.

We first check if the data already exists in the cache.

If it doesn’t exist, we have to scan for blank lines to load the data.

If blank lines don’t exist, we need to evict a line using the LRU strategy. We replace the victim line with the new line.

Other Operations

void storeData(long long address, int size) {
    // Simulate storing data at the given address
    loadData(address, size);
}

void modifyData(long long address, int size) {
    // Simulate modifying data at the given address
    loadData(address, size);
    hit_count++;
    if (verboseMode) printf(" hit\n");
}

For this simulator, storing data and modifying data are basically the same thing as loading data.

Print Summary

We are asked to output the answer using the printSummary function.

// Print Summary
printSummary(hit_count, miss_count, eviction_count);

And Voila!

                        Your simulator     Reference simulator
Points (s,E,b)    Hits  Misses  Evicts    Hits  Misses  Evicts
     3 (1,1,1)       9       8       6       9       8       6  traces/yi2.trace
     3 (4,2,4)       4       5       2       4       5       2  traces/yi.trace
     3 (2,1,4)       2       3       1       2       3       1  traces/dave.trace
     3 (2,1,3)     167      71      67     167      71      67  traces/trans.trace
     3 (2,2,3)     201      37      29     201      37      29  traces/trans.trace
     3 (2,4,3)     212      26      10     212      26      10  traces/trans.trace
     3 (5,1,5)     231       7       0     231       7       0  traces/trans.trace
     6 (5,1,5)  265189   21775   21743  265189   21775   21743  traces/long.trace
    27

Summary

In this project, we moved from the theory of hierarchy to the practical reality of memory management. By building this simulator, we reinforced several core concepts of computer systems.

With our simulator passing all the trace tests, we’ve effectively mirrored how a CPU “thinks” about memory. The next step is applying these insights to optimize actual code, ensuring our algorithms play nicely with the hardware we’ve just simulated.