Cache Simulator in C - Why am I getting a 'hit' every time?

Question

I am writing a simple cache simulation in c. I'm somewhat of a noob when it comes to c but I have the program almost entirely working I think. For some reason it indicates a hit for every value even when the cache is empty.

I think the problem lies within the queryCache function but I'm not sure what's wrong. The full code is below as well as an example output.

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <unistd.h>
#include <assert.h>
#include <time.h>
#include <math.h>
#include <getopt.h>
#include <ctype.h>

typedef struct Line{
    const int b_size; //block size in bits
    unsigned long long block,tag;
    short v; //valid flag bit
    int l_rate; //use rate
}Line;

typedef struct Set{
    Line *lines;
    int s_rate;
}Set;

typedef struct Cache{
    Set *sets;
    int hit_c,miss_c,evic_c;
    int set_b,block_b,line_per_set;
}Cache;

//initialize cache with user input 
void cacheInit(Cache *cache){
    printf("Initializing Cache...\n");
    //init counters
    cache->hit_c = 0;
    cache->miss_c = 0;
    cache->evic_c = 0;

    unsigned long long n_sets = pow(2,cache->set_b); // number of sets in cache = 2^s
    cache->sets = (Set *)malloc(sizeof(Set)*n_sets); //allocate mem for sets
    printf("Mem for sets allocated.\n");

    //Allocate mem for cache lines within each set.
    for(unsigned long long i=0;i<n_sets;i++){
        cache->sets[i].s_rate = 0;
        cache->sets[i].lines = (Line *)malloc(sizeof(Line)*cache->line_per_set);
        //printf("Mem allocated for lines within set: %llu\n",i);
        for(unsigned long long k=0;k<cache->line_per_set;k++){
            cache->sets[i].lines[k].v = 0;
        }
    }
    printf("Cache initialization complete.\n");
}

//DEALLOCATION OF MEM
void dealloc(Cache *cache){
    printf("Deallocating mem...\n");
    unsigned long long n_sets = pow(2,cache->set_b); // number of sets in cache = 2^s
    for(unsigned long long i=0;i<n_sets;i++){
        free(cache->sets[i].lines); //free lines within set
        //printf("Lines in set: %llu deallocated.\n",i);
    }
    free(cache->sets); //free sets after the lines
    printf("Mem deallocation completed.\n");
}

//Query cache for an address (found in cache = 1, not found but has free space = -1, not found and no free space = 0)
int queryCache(const unsigned long long address, const Cache *cache){
    signed int result = 0;
    unsigned long long index = 0;
    unsigned long long tag_b = 64 - (cache->set_b + cache->block_b);
    unsigned long long tag = address >> (cache->set_b + cache->block_b); //extract tag
    unsigned long long set = (address << tag_b) >> (tag_b + cache->set_b);

    //search through cache
    for(unsigned long long i = 0; i < cache->line_per_set; i++){
        if(cache->sets[set].lines[i].v && cache->sets[set].lines[i].tag == tag){ //already in cache 'hit'
            cache->sets[set].lines[i].l_rate = ++cache->sets[set].s_rate;
            //printf("result = 1\n");
            return 1;
        }else if(!cache->sets[set].lines[i].v){ //valid flag unset, so free space is available
            index = i;
            cache->sets[set].lines[index].tag = tag;
            cache->sets[set].lines[index].v = 1;
            cache->sets[set].lines[index].l_rate = ++cache->sets[set].s_rate;
            return -1;
            //printf("result = -1\n");
        }else{
            //printf("result = 0\n");
            return 0;  // no empty spot, not found in cache 'miss'
        }
    }
    //return result;
}

//EVICT SPOT
void evictData(const unsigned long long address, Cache *cache){
    unsigned long long index = 0;
    unsigned long long tag_b = 64 - (cache->set_b + cache->block_b);
    unsigned long long tag = address >> (cache->set_b + cache->block_b);
    unsigned long long set = (address << tag_b) >> (tag_b + cache->set_b);

    unsigned long long min_r;
    min_r = cache->sets[set].lines[0].l_rate;

    for(unsigned long long i = 0; i < cache->line_per_set; i++){
        unsigned long long this_r;
        if(min_r > this_r){
            min_r = this_r;
            index = i;
        }
    }
    cache->sets[set].lines[index].tag = tag;
    cache->sets[set].lines[index].l_rate = ++cache->sets[set].s_rate;
}

//CHECK DATA AND REPLACE IF NECESSARY
void cacheData(const unsigned long long address, Cache *cache){
    //query cache for address

    //printf("queryResult = %i\n", queryResult);
    
    if(!queryCache(address, cache)){ //not found, cache full
        printf(" Miss, evict\n");
        evictData(address, cache);
        cache->miss_c++;
        cache->evic_c++;

    }else if(queryCache(address, cache)){// found 'hit'
        cache->hit_c++;
        printf(" hit\n");

    }else{//not found, free space
        cache->miss_c++;
        printf(" Miss, no evict\n");
    }

}

//SIMULATE CACHE WITH INPUT LIST OF ADDRESSES
void simulateCache(char *fileName, Cache *cache){
    FILE *input = fopen(fileName, "rt");
    unsigned long long address;

    while(fscanf(input, "%llu", &address) == 1){
        printf("%llu", address);
        cacheData(address, cache);
    }
    fclose(input);
}

int main(int argc, char *argv[]){
    int opt,m, s, e, b;
    char *i;
    char *r;

    Cache cache0;

    int n_hits,n_miss;

    //ensure correct num of arguments before parsing
    if(!(argc == 13)){
        printf("Error: Invalid number of arguments. Arg count: %d\n",argc);
        exit(-1);
    }

    while(-1 != (opt = getopt(argc,argv,"m:s:e:b:i:r"))){
        switch(opt){
            case 'm':
                m = atoi(optarg);
                break;
            case 's':
                s = atoi(optarg);
                cache0.set_b = s;
                break;
            case 'e':
                e = atoi(optarg);
                cache0.line_per_set = e;
                break;
            case 'b':
                b = atoi(optarg);
                cache0.block_b = b;
                break;
            case 'i':
                i = optarg;
                break;
            case 'r':
                r = optarg;
                break;
            default:
                printf("Invalid argument\n");
                break;
        }
    }
    printf("addr size %d, index bits: %d, line bits: %d, block size: %d\n",m,s,e,b);
    //printf("Filename: %c, Mode: %c\n", i, r);

    cacheInit(&cache0);

    simulateCache(i,&cache0);
    unsigned long long r_miss = cache0.miss_c/(cache0.miss_c+cache0.hit_c); //calculate miss rate
    unsigned long long avg_access_t = 1 + (r_miss * 100); //calulate avg access time in cycles
    unsigned long long total_run_t = (cache0.miss_c+cache0.hit_c)*avg_access_t;
    printf("Avg access time: %0.2d\n", avg_access_t);
    printf("Total run time: %0.2d\n", total_run_t);


    printf("Hits: %d, Misses: %d\n",cache0.hit_c,cache0.miss_c);

    dealloc(&cache0);

    return 0;
}

Output Example

./cachesim -m 64 -s 4 -e 1 -b 4 -i adresses.txt -r lfu
addr size 64, index bits: 4, line bits: 1, block size: 4
Initializing Cache...
Mem for sets allocated.
Cache initialization complete.
10 hit
20 hit
10 hit
22 hit
Avg access time: 01
Total run time: 04
Hits: 4, Misses: 0
Deallocating mem...
Mem deallocation completed.

where

m           address size in bits
s           number if index bits
e           number of line bits 
b           size of block bits
file        name of file containing a list of addresses
option      method used (lfu, fifo, opt)

Answer 1

I found several issues with the program today when looking at it with fresh eyes. The changes that fixed the issues are as follows: -The return statements were prematurely exiting the loop that scans through the cache. -The format specifiers for the addresses needed to be %llX to handle a 64 bit hex value -The section that separates the tags and the set IDs needed to be changed as follows

unsigned long long tag_b = 64 - ((cache->s) + (cache->block_b));
unsigned long long tag = address >> (cache->set_b + cache->block_b); //extract tag
unsigned long long set = (address << (tag_b)) >> (tag_b + cache->set_b);//extract set idx

The program now produces the output:

./cachesim -m 64 -s 4 -e 0 -b 4 -i addresses.txt -r lfu
addr size 64, sets: 16, lines: 1, block size: 16
Initializing Cache...
Mem for sets allocated.
Cache initialization complete.
123456789ABCDEF
Tag: 1234567  Set: B  Miss, no evict
23F0FFFA003464F
Tag: 23F0FFF  Set: 3  Miss, no evict
DC2387002FAFF
Tag: DC238  Set: 2  Miss, no evict
10F0F00FAC4A34F
Tag: 10F0F00  Set: 4  Miss, no evict
DC2387002FAFF
Tag: DC238  Set: 2  hit
602598F3AF2C12F
Tag: 602598F  Set: 2  Miss, evict
81F2319543FC32C
Tag: 81F2319  Set: F  Miss, no evict
10F0F00FAC4A34F
Tag: 10F0F00  Set: 4  hit
40F0F00FAC4A34F
Tag: 40F0F00  Set: 4  Miss, evict
602598F3AF2C12F
Tag: 602598F  Set: 2  hit
DC2387002FAFF
Tag: DC238  Set: 2  Miss, evict
123456789ABCDEF
Tag: 1234567  Set: B  hit
23F0FFFA003464F
Tag: 23F0FFF  Set: 3  hit
40F0F00FAC4A34F
Tag: 40F0F00  Set: 4  hit
602598F3AF2C12F
Tag: 602598F  Set: 2  Miss, evict
81F2319543FC32C
Tag: 81F2319  Set: F  hit
10F0F00FAC4A34F
Tag: 10F0F00  Set: 4  Miss, evict
10F0F00FAC4A34F
Tag: 10F0F00  Set: 4  hit
40F0F00FAC4A34F
Tag: 40F0F00  Set: 4  Miss, evict
602598F3AF2C12F
Tag: 602598F  Set: 2  hit
81F2319543FC32C
Tag: 81F2319  Set: F  hit
10F0F00FAC4A34F
Tag: 10F0F00  Set: 4  Miss, evict
40F0F00FAC4A34F
Tag: 40F0F00  Set: 4  Miss, evict
602598F3AF2C12F
Tag: 602598F  Set: 2  hit
Hits: 11, Misses: 13, Evictions: 8
Total transfers: 24
Miss Rate: 54.17
Avg access time: 55 clk cycles
Total run time: 1320 clk cycles
Deallocating mem...
Mem deallocation completed.

I will add a github link to the full code for reference when I get the chance

(If you are coming here for help on a similar program and there is no link still feel free to comment or pm. I likely forgot to add it as I am going to make some final changes before I commit)