37  * A CacheSet is a set of cache blocks. A memory block that maps to a set can be
43  * whether a block is in the cache or not by searching for its tag.
45  * In order to search for memory data in the cache, the set identifier and tag
81 } Cache;  typedef
92 void (*update_hit)(Cache *cache, int set, int blk);
93 void (*update_miss)(Cache *cache, int set, int blk);
95 void (*metadata_init)(Cache *cache);
96 void (*metadata_destroy)(Cache *cache);
99 static Cache **l1_dcaches, **l1_icaches;
102 static Cache **l2_ucaches;
132  * On a cache hit: The hit-block is assigned the current generation counter,
135  * On a cache miss: The block with the least priority is searched and replaced
140 static void lru_priorities_init(Cache *cache)  in lru_priorities_init()  argument
144     for (i = 0; i < cache->num_sets; i++) {  in lru_priorities_init()
145         cache->sets[i].lru_priorities = g_new0(uint64_t, cache->assoc);  in lru_priorities_init()
146         cache->sets[i].lru_gen_counter = 0;  in lru_priorities_init()
150 static void lru_update_blk(Cache *cache, int set_idx, int blk_idx)  in lru_update_blk()  argument
152     CacheSet *set = &cache->sets[set_idx];  in lru_update_blk()
153     set->lru_priorities[blk_idx] = cache->sets[set_idx].lru_gen_counter;  in lru_update_blk()
157 static int lru_get_lru_block(Cache *cache, int set_idx)  in lru_get_lru_block()  argument
161     min_priority = cache->sets[set_idx].lru_priorities[0];  in lru_get_lru_block()
164     for (i = 1; i < cache->assoc; i++) {  in lru_get_lru_block()
165         if (cache->sets[set_idx].lru_priorities[i] < min_priority) {  in lru_get_lru_block()
166             min_priority = cache->sets[set_idx].lru_priorities[i];  in lru_get_lru_block()
173 static void lru_priorities_destroy(Cache *cache)  in lru_priorities_destroy()  argument
177     for (i = 0; i < cache->num_sets; i++) {  in lru_priorities_destroy()
178         g_free(cache->sets[i].lru_priorities);  in lru_priorities_destroy()
184  * stores accesses to the cache.
189  * On a conflict miss: The first-in block is removed from the cache and the new
193 static void fifo_init(Cache *cache)  in fifo_init()  argument
197     for (i = 0; i < cache->num_sets; i++) {  in fifo_init()
198         cache->sets[i].fifo_queue = g_queue_new();  in fifo_init()
202 static int fifo_get_first_block(Cache *cache, int set)  in fifo_get_first_block()  argument
204     GQueue *q = cache->sets[set].fifo_queue;  in fifo_get_first_block()
208 static void fifo_update_on_miss(Cache *cache, int set, int blk_idx)  in fifo_update_on_miss()  argument
210     GQueue *q = cache->sets[set].fifo_queue;  in fifo_update_on_miss()
214 static void fifo_destroy(Cache *cache)  in fifo_destroy()  argument
218     for (i = 0; i < cache->num_sets; i++) {  in fifo_destroy()
219         g_queue_free(cache->sets[i].fifo_queue);  in fifo_destroy()
223 static inline uint64_t extract_tag(Cache *cache, uint64_t addr)  in extract_tag()  argument
225     return addr & cache->tag_mask;  in extract_tag()
228 static inline uint64_t extract_set(Cache *cache, uint64_t addr)  in extract_set()  argument
230     return (addr & cache->set_mask) >> cache->blksize_shift;  in extract_set()
236         return "cache size must be divisible by block size";  in cache_config_error()
238         return "cache size must be divisible by set size (assoc * block size)";  in cache_config_error()
249 static Cache *cache_init(int blksize, int assoc, int cachesize)  in cache_init()
251     Cache *cache;  in cache_init()  local
261     cache = g_new(Cache, 1);  in cache_init()
262     cache->assoc = assoc;  in cache_init()
263     cache->cachesize = cachesize;  in cache_init()
264     cache->num_sets = cachesize / (blksize * assoc);  in cache_init()
265     cache->sets = g_new(CacheSet, cache->num_sets);  in cache_init()
266     cache->blksize_shift = pow_of_two(blksize);  in cache_init()
267     cache->accesses = 0;  in cache_init()
268     cache->misses = 0;  in cache_init()
270     for (i = 0; i < cache->num_sets; i++) {  in cache_init()
271         cache->sets[i].blocks = g_new0(CacheBlock, assoc);  in cache_init()
275     cache->set_mask = ((cache->num_sets - 1) << cache->blksize_shift);  in cache_init()
276     cache->tag_mask = ~(cache->set_mask | blk_mask);  in cache_init()
279         metadata_init(cache);  in cache_init()
282     return cache;  in cache_init()
285 static Cache **caches_init(int blksize, int assoc, int cachesize)  in caches_init()
287     Cache **caches;  in caches_init()
294     caches = g_new(Cache *, cores);  in caches_init()
303 static int get_invalid_block(Cache *cache, uint64_t set)  in get_invalid_block()  argument
307     for (i = 0; i < cache->assoc; i++) {  in get_invalid_block()
308         if (!cache->sets[set].blocks[i].valid) {  in get_invalid_block()
316 static int get_replaced_block(Cache *cache, int set)  in get_replaced_block()  argument
320         return g_rand_int_range(rng, 0, cache->assoc);  in get_replaced_block()
322         return lru_get_lru_block(cache, set);  in get_replaced_block()
324         return fifo_get_first_block(cache, set);  in get_replaced_block()
330 static int in_cache(Cache *cache, uint64_t addr)  in in_cache()  argument
335     tag = extract_tag(cache, addr);  in in_cache()
336     set = extract_set(cache, addr);  in in_cache()
338     for (i = 0; i < cache->assoc; i++) {  in in_cache()
339         if (cache->sets[set].blocks[i].tag == tag &&  in in_cache()
340                 cache->sets[set].blocks[i].valid) {  in in_cache()
349  * access_cache(): Simulate a cache access
350  * @cache: The cache under simulation
353  * Returns true if the requested data is hit in the cache and false when missed.
354  * The cache is updated on miss for the next access.
356 static bool access_cache(Cache *cache, uint64_t addr)  in access_cache()  argument
361     tag = extract_tag(cache, addr);  in access_cache()
362     set = extract_set(cache, addr);  in access_cache()
364     hit_blk = in_cache(cache, addr);  in access_cache()
367             update_hit(cache, set, hit_blk);  in access_cache()
372     replaced_blk = get_invalid_block(cache, set);  in access_cache()
375         replaced_blk = get_replaced_block(cache, set);  in access_cache()
379         update_miss(cache, set, replaced_blk);  in access_cache()
382     cache->sets[set].blocks[replaced_blk].tag = tag;  in access_cache()
383     cache->sets[set].blocks[replaced_blk].valid = true;  in access_cache()
509 static void cache_free(Cache *cache)  in cache_free()  argument
511     for (int i = 0; i < cache->num_sets; i++) {  in cache_free()
512         g_free(cache->sets[i].blocks);  in cache_free()
516         metadata_destroy(cache);  in cache_free()
519     g_free(cache->sets);  in cache_free()
520     g_free(cache);  in cache_free()
523 static void caches_free(Cache **caches)  in caches_free()
606     Cache *icache, *dcache, *l2_cache = NULL;  in log_stats()
838         fprintf(stderr, "L2 cache cannot be constructed from given parameters\n");  in qemu_plugin_install()