8
\$\begingroup\$

This is my attempt to build a simple simulation of a direct mapped cache, I'm new to C and trying to learn some low level concepts. I had some difficulties with the design, because I'm used to program in a object-oriented style.

#include <stdio.h>

int create_mask(int num_of_bits, int pos) {
    return (1 << num_of_bits)-1 << pos;
}

int get_window_bits(int num, int window_size, int pos) {
    return (create_mask(window_size, pos) & num) >> pos;
}

int is_valid(char cache[4][4], int set, int tag) {
    return cache[set][0] && (cache[set][1] == tag);
}

void load_to_cache(int address, char memory[8][2], char cache[4][4], int set, int tag, int offset) {
    int memory_index = get_window_bits(address, 3, 1);

    cache[set][0] = 1;
    cache[set][1] = tag;
    cache[set][2] = memory[memory_index][0];
    cache[set][3] = memory[memory_index][1];
}


int fetch_from_cache(int address, char cache[4][4], char memory[8][2]) {
    int set = get_window_bits(address, 2, 1);
    int offset = get_window_bits(address, 1, 0);
    int tag = get_window_bits(address, 1, 3);

    if (!is_valid(cache, set, tag)) {
        printf("cache miss\n");
        load_to_cache(address, memory, cache, set, tag, offset);
    } else {
        printf("cache hit\n");
    }

    return cache[set][2+offset];
}


int main() {

    /* init memory - 8 blocks of 2 bytes */
    char memory[8][2] = {{'A','B'},
                        {'C','D'},
                        {'E','F'},
                        {'G','H'},
                        {'I','J'},
                        {'K','L'},
                        {'M','N'},
                        {'O','P'}};

    /* init cache - 4 lines of 2 bytes storage*/
    char cache[4][4] = {{0,0,0,0},
                        {0,0,0,0},
                        {0,0,0,0},
                        {0,0,0,0}};

    fetch_from_cache(0, cache, memory); 
    fetch_from_cache(1, cache, memory); 

    return 0;
}

Structure:

The program consists of a 2d array that represents the memory, it's size is 16 bytes:

char memory[8][2] = {{'A','B'},
                    {'C','D'},
                    {'E','F'},
                    {'G','H'},
                    {'I','J'},
                    {'K','L'},
                    {'M','N'},
                    {'O','P'}};

another array which represents the cache of 4 lines, each line can store 2 bytes the first byte of the line is for the valid bit, the second is for the tag, and the rest are for the data.

char cache[4][4] = {{0,0,0,0},
                    {0,0,0,0},
                    {0,0,0,0},
                    {0,0,0,0}};

The function get_window_bits is used to extract the tag, set and offset of a memory address.

int get_window_bits(int num, int window_size, int pos) {
    return (create_mask(window_size, pos) & num) >> pos;
}

I hope everything else is clear.

\$\endgroup\$
2
  • 1
    \$\begingroup\$ There is nothing about memory that needs signed types. Are you required to use int vs. unsigned for example? \$\endgroup\$ Nov 29, 2019 at 22:14
  • \$\begingroup\$ @chux - Reinstate Monica good point, it should be unsigned. \$\endgroup\$
    – din96b18
    Dec 2, 2019 at 8:02

1 Answer 1

1
\$\begingroup\$

Here are some things that may help you improve your program.

Use parentheses to clarify expressions

The code contains this line:

return (1 << num_of_bits)-1 << pos;

A programmer reading it might wonder which of the following is the correct interpretation:

return ((1 << num_of_bits)-1) << pos;
return (1 << num_of_bits)-(1 << pos);

To interpret correctly (the first one), one would have to remember that according to C operator precedence, the - operator has higher precedence than the << operator. We can easily avoid this potential confusion by simply writing the code with parentheses, even though, technically, they're redunandant.

Eliminate unused variables

The load_to_cache function includes unused parameter offset. If it's not used, it probably should be removed.

Be wary of plain char

Whether char is signed or unsigned is implementation defined. I'd suggest instead using uint8_t from <stdint.h> to make sure that there aren't any surprises when doing right shifts. A short example shows the difference:

#include <stdio.h>
int main() {
    signed char a = -1;
    unsigned char b = -1;
    printf("%x\n", a>>2);    // prints ffffffff 
    printf("%x\n", b>>2);    // prints 3f
}

For similar reasons, most of the places the code is using int should probably be either unsigned or size_t.

Use a struct where appropriate

The cache is just memory, of course, but with a simulation, the bytes have structure and meaning. The code has these three lines:

cache[set][0] = 1;
cache[set][1] = tag;
cache[set][2] = memory[memory_index][0];
cache[set][3] = memory[memory_index][1];

This suggests the following struct definition:

#define CACHESIZE 2
typedef struct cacheline_s {
    uint8_t valid;
    uint8_t tag;
    uint8_t mem[CACHESIZE];
} cacheline;

Now the lines above become this:

cache[set].valid = 1;
cache[set].tag = tag;
cache[set].mem[0] = memory[memory_index][0];
cache[set].mem[1] = memory[memory_index][1];

Reconsider the interfaces

Instead of this:

if (!is_valid(cache, set, tag)) {

I think it might make more sense to pass only a single cache line. Using the struct defined above, the function now looks like this:

int is_valid(const cacheline *cache, int tag) {
    return cache->valid && (cache->tag == tag);
}

Note too that we're passing a const pointer, advertising the fact that the underlying cacheline will not be changed by this function. A similar interface change could be made to load_to_cache.

Eliminate "magic numbers"

This code has a number of inscrutable "magic numbers," that is, unnamed constants such as 2, 4, 8, etc. Generally it's better to avoid that and give such constants meaningful names. That way, if anything ever needs to be changed, you won't have to go hunting through the code for all instances of "2" and then trying to determine if this particular 2 is relevant to the desired change or if it is some other constant that happens to have the same value. This is especially beneficial in cases like this in which some numbers depend on others. For example, we can use these to make sure that the two constants are easily changed and kept consistent. Only the first variable needs to be touched.

#define CACHESIZE_BITS 1
#define CACHESIZE (1u << CACHESIZE_BITS)
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.