[RFC,v2,3/3] plugins: cache: Added FIFO and LRU eviction policies.

Now one of the three eviction policies can be chosen as an argument. On
not specifying an argument, LRU is used by default.

Signed-off-by: Mahmoud Mandour <ma.mandourr@gmail.com>
---
 contrib/plugins/cache.c | 159 ++++++++++++++++++++++++++++++++++++----
 1 file changed, 146 insertions(+), 13 deletions(-)

Mahmoud Mandour <ma.mandourr@gmail.com> writes:

> Now one of the three eviction policies can be chosen as an argument. On
> not specifying an argument, LRU is used by default.
>
> Signed-off-by: Mahmoud Mandour <ma.mandourr@gmail.com>
> ---
>  contrib/plugins/cache.c | 159 ++++++++++++++++++++++++++++++++++++----
>  1 file changed, 146 insertions(+), 13 deletions(-)
>
> diff --git a/contrib/plugins/cache.c b/contrib/plugins/cache.c
> index fa0bf1dd40..1e323494bf 100644
> --- a/contrib/plugins/cache.c
> +++ b/contrib/plugins/cache.c
> @@ -18,6 +18,8 @@
>  
>  QEMU_PLUGIN_EXPORT int qemu_plugin_version = QEMU_PLUGIN_VERSION;
>  
> +static bool fifo, lru, rnd;
> +

Ironically this would be a good use for a single variable with an enum,
or alternatively a function pointer which can be set on initialisation.

>  static GRand *rng;
>  static GHashTable *dmiss_ht;
>  static GHashTable *imiss_ht;
> @@ -55,6 +57,8 @@ struct CacheBlock {
>  
>  struct CacheSet {
>      struct CacheBlock *blocks;
> +    uint16_t *priorities;
> +    GQueue *evict_queue;
>  };
>  
>  struct Cache {
> @@ -93,6 +97,84 @@ static inline uint64_t extract_set(struct Cache *cache, uint64_t addr)
>      return (addr & cache->set_mask) >> (pow_of_two(cache->blksize));
>  }

I think it would be useful to summarise the LRU behaviour here in a
comment and explain how the priorities are meant to change as the cache
is used.

>  
> +static void lru_priorities_init(struct Cache *cache)
> +{
> +    int i, j;
> +
> +    for (i = 0; i < cache->num_sets; i++) {
> +        cache->sets[i].priorities = g_new(uint16_t, cache->assoc);
> +        for (j = 0; j < cache->assoc; j++) {
> +            cache->sets[i].priorities[j] = cache->assoc - j - 1;
> +        }
> +    }
> +}
> +
> +static void lru_update_on_miss(struct Cache *cache,
> +                                      int set_idx,
> +                                      int blk_idx)
> +{
> +    int i;
> +
> +    for (i = 0; i < cache->assoc; i++) {
> +        cache->sets[set_idx].priorities[i]++;
> +    }
> +
> +    cache->sets[set_idx].priorities[blk_idx] = 0;

So we increment priority for all non-hit blocks and reset it for the
entry just used? This isn't totally clear to follow however see bellow:

> +}
> +
> +static void lru_update_on_hit(struct Cache *cache,
> +                                         int set_idx,
> +                                         int blk_idx)
> +{
> +    uint16_t blk_priority;
> +    int i;
> +
> +    blk_priority = cache->sets[set_idx].priorities[blk_idx];
> +    for (i = 0; i < cache->assoc; i++) {
> +        if (cache->sets[set_idx].priorities[i] < blk_priority) {
> +            cache->sets[set_idx].priorities[i]++;
> +        }
> +    }
> +    cache->sets[set_idx].priorities[blk_idx] = 0;

This seems pretty expensive depending on the number of blocks. Another
approach would be to have a generation number that is incremented on
each access and stored in the appropriate set. Then...

> +}
> +
> +static int lru_get_lru_block(struct Cache *cache, int set_idx)
> +{
> +    int i;
> +
> +    for (i = 0; i < cache->assoc; i++) {
> +        if (cache->sets[set_idx].priorities[i] == cache->assoc - 1) {
> +            return i;
> +        }
> +    }

when you get to search for a "stale" block you just look for the lowest
generation number. The eviction logic should be being called less than
the update logic right?

> +
> +    g_assert_not_reached();
> +}
> +
> +static void fifo_init(struct Cache *cache)
> +{
> +    int i;
> +
> +    for (i = 0; i < cache->num_sets; i++) {
> +        cache->sets[i].evict_queue = g_queue_new();
> +    }
> +}
> +
> +static int fifo_get_first_in_block(struct Cache *cache, int set)
> +{
> +    GQueue *q = cache->sets[set].evict_queue;
> +    return GPOINTER_TO_INT(g_queue_pop_tail(q));
> +}
> +
> +static void fifo_update_on_miss(struct Cache *cache,
> +                                int set,
> +                                int blk_idx)
> +{
> +    GQueue *q = cache->sets[set].evict_queue;
> +    g_queue_push_head(q, GINT_TO_POINTER(blk_idx));
> +}

Again some commentary would be helpful around above the fifo functions.

> +
> +
>  static struct Cache *cache_init(int blksize, int assoc, int cachesize)
>  {
>      struct Cache *cache;
> @@ -113,6 +195,12 @@ static struct Cache *cache_init(int blksize, int assoc, int cachesize)
>      cache->set_mask = ((cache->num_sets - 1) << (pow_of_two(cache->blksize)));
>      cache->tag_mask = ~(cache->set_mask | cache->blk_mask);
>  
> +    if (lru) {
> +        lru_priorities_init(cache);
> +    } else if (fifo) {
> +        fifo_init(cache);
> +    }
> +
>      return cache;
>  }
>  
> @@ -131,12 +219,20 @@ static int get_invalid_block(struct Cache *cache, uint64_t set)
>      return -1;
>  }
>  
> -static int get_replaced_block(struct Cache *cache)
> +static int get_replaced_block(struct Cache *cache, int set)
>  {
> -    return g_rand_int_range(rng, 0, cache->assoc);
> +    if (rnd) {
> +        return g_rand_int_range(rng, 0, cache->assoc);
> +    } else if (lru) {
> +        return lru_get_lru_block(cache, set);
> +    } else if (fifo) {
> +        return fifo_get_first_in_block(cache, set);
> +    }
> +
> +    g_assert_not_reached();
>  }
>  
> -static bool in_cache(struct Cache *cache, uint64_t addr)
> +static int in_cache(struct Cache *cache, uint64_t addr)
>  {
>      int i;
>      uint64_t tag, set;
> @@ -147,29 +243,39 @@ static bool in_cache(struct Cache *cache, uint64_t addr)
>      for (i = 0; i < cache->assoc; i++) {
>          if (cache->sets[set].blocks[i].tag == tag &&
>                  cache->sets[set].blocks[i].valid) {
> -            return true;
> +            return i;
>          }
>      }
>  
> -    return false;
> +    return -1;
>  }
>  
>  static enum AccessResult access_cache(struct Cache *cache, uint64_t addr)
>  {
>      uint64_t tag, set;
> -    int replaced_blk;
> -
> -    if (in_cache(cache, addr)) {
> -        return HIT;
> -    }
> +    int hit_blk, replaced_blk;
>  
>      tag = extract_tag(cache, addr);
>      set = extract_set(cache, addr);
> +    hit_blk = in_cache(cache, addr);
> +
> +    if (hit_blk != -1) {
> +        if (lru) {
> +            lru_update_on_hit(cache, set, hit_blk);
> +        }
> +        return HIT;
> +    }
>  
>      replaced_blk = get_invalid_block(cache, set);
>  
>      if (replaced_blk == -1) {
> -        replaced_blk = get_replaced_block(cache);
> +        replaced_blk = get_replaced_block(cache, set);
> +    }
> +
> +    if (lru) {
> +        lru_update_on_miss(cache, set, replaced_blk);
> +    } else if (fifo) {
> +        fifo_update_on_miss(cache, set, replaced_blk);
>      }

I wonder if just having a update_hit and update_miss function pointer
would keep things cleaner?

  if (update_hit) {
       update_hit(cache, set, hit, block)
  }

etc...

>  
>      cache->sets[set].blocks[replaced_blk].tag = tag;
> @@ -307,6 +413,11 @@ static void free_cache(struct Cache *cache)
>  {
>      for (int i = 0; i < cache->num_sets; i++) {
>          g_free(cache->sets[i].blocks);
> +        if (lru) {
> +            g_free(cache->sets[i].priorities);

Hmm I've obviously missed something about how priorities are meant to be sued.

> +        } else if (fifo) {
> +            g_queue_free(cache->sets[i].evict_queue);
> +        }
>      }
>  
>      g_free(cache->sets);
> @@ -403,8 +514,6 @@ int qemu_plugin_install(qemu_plugin_id_t id, const qemu_info_t *info,
>      iblksize = 64;
>      icachesize = iblksize * iassoc * 32;
>  
> -    rng = g_rand_new();
> -
>      for (i = 0; i < argc; i++) {
>          char *opt = argv[i];
>          if (g_str_has_prefix(opt, "I=")) {
> @@ -433,6 +542,22 @@ int qemu_plugin_install(qemu_plugin_id_t id, const qemu_info_t *info,
>              if (!tracefile) {
>                  fprintf(stderr, "could not open: %s for writing\n", file_name);
>              }
> +        } else if (g_str_has_prefix(opt, "evict=")) {
> +            if (lru || rnd || fifo) {
> +                fprintf(stderr, "eviction policy specified more than once\n");
> +                return -1;
> +            }

This is one argument for the separate bools although generally QEMU
operates on the basis of last argument wins ;-) 

> +            gchar *policy = opt + 6;
> +            if (g_strcmp0(policy, "rand") == 0) {
> +                rnd = true;
> +            } else if (g_strcmp0(policy, "lru") == 0) {
> +                lru = true;
> +            } else if (g_strcmp0(policy, "fifo") == 0) {
> +                fifo = true;
> +            } else {
> +                fprintf(stderr, "invalid eviction policy: %s\n", opt);
> +                return -1;
> +            }
>          } else {
>              fprintf(stderr, "option parsing failed: %s\n", opt);
>              return -1;
> @@ -449,6 +574,14 @@ int qemu_plugin_install(qemu_plugin_id_t id, const qemu_info_t *info,
>          return -1;
>      }
>  
> +    if (!rnd && !lru && !fifo) {
> +        lru = true;
> +    }
> +
> +    if (rnd) {
> +        rng = g_rand_new();
> +    }
> +
>      dcache = cache_init(dblksize, dassoc, dcachesize);
>      icache = cache_init(iblksize, iassoc, icachesize);

On Sun, May 30, 2021 at 8:37 AM Mahmoud Mandour <ma.mandourr@gmail.com>
wrote:

> Now one of the three eviction policies can be chosen as an argument. On
> not specifying an argument, LRU is used by default.
>
> Signed-off-by: Mahmoud Mandour <ma.mandourr@gmail.com>
> ---
>  contrib/plugins/cache.c | 159 ++++++++++++++++++++++++++++++++++++----
>  1 file changed, 146 insertions(+), 13 deletions(-)
>
> diff --git a/contrib/plugins/cache.c b/contrib/plugins/cache.c
> index fa0bf1dd40..1e323494bf 100644
> --- a/contrib/plugins/cache.c
> +++ b/contrib/plugins/cache.c
> @@ -18,6 +18,8 @@
>
>  QEMU_PLUGIN_EXPORT int qemu_plugin_version = QEMU_PLUGIN_VERSION;
>
> +static bool fifo, lru, rnd;
> +
>  static GRand *rng;
>  static GHashTable *dmiss_ht;
>  static GHashTable *imiss_ht;
> @@ -55,6 +57,8 @@ struct CacheBlock {
>
>  struct CacheSet {
>      struct CacheBlock *blocks;
> +    uint16_t *priorities;
> +    GQueue *evict_queue;
>  };
>
>  struct Cache {
> @@ -93,6 +97,84 @@ static inline uint64_t extract_set(struct Cache *cache,
> uint64_t addr)
>      return (addr & cache->set_mask) >> (pow_of_two(cache->blksize));
>  }
>
> +static void lru_priorities_init(struct Cache *cache)
> +{
> +    int i, j;
> +
> +    for (i = 0; i < cache->num_sets; i++) {
> +        cache->sets[i].priorities = g_new(uint16_t, cache->assoc);
> +        for (j = 0; j < cache->assoc; j++) {
> +            cache->sets[i].priorities[j] = cache->assoc - j - 1;
> +        }
> +    }
> +}
> +
> +static void lru_update_on_miss(struct Cache *cache,
> +                                      int set_idx,
> +                                      int blk_idx)
> +{
> +    int i;
> +
> +    for (i = 0; i < cache->assoc; i++) {
> +        cache->sets[set_idx].priorities[i]++;
> +    }
> +
> +    cache->sets[set_idx].priorities[blk_idx] = 0;
> +}
> +
> +static void lru_update_on_hit(struct Cache *cache,
> +                                         int set_idx,
> +                                         int blk_idx)
> +{
> +    uint16_t blk_priority;
> +    int i;
> +
> +    blk_priority = cache->sets[set_idx].priorities[blk_idx];
> +    for (i = 0; i < cache->assoc; i++) {
> +        if (cache->sets[set_idx].priorities[i] < blk_priority) {
> +            cache->sets[set_idx].priorities[i]++;
> +        }
> +    }
> +    cache->sets[set_idx].priorities[blk_idx] = 0;
> +}
> +
> +static int lru_get_lru_block(struct Cache *cache, int set_idx)
> +{
> +    int i;
> +
> +    for (i = 0; i < cache->assoc; i++) {
> +        if (cache->sets[set_idx].priorities[i] == cache->assoc - 1) {
> +            return i;
> +        }
> +    }
> +
> +    g_assert_not_reached();
> +}
> +
> +static void fifo_init(struct Cache *cache)
> +{
> +    int i;
> +
> +    for (i = 0; i < cache->num_sets; i++) {
> +        cache->sets[i].evict_queue = g_queue_new();
> +    }
> +}
> +
> +static int fifo_get_first_in_block(struct Cache *cache, int set)
> +{
> +    GQueue *q = cache->sets[set].evict_queue;
> +    return GPOINTER_TO_INT(g_queue_pop_tail(q));
> +}
> +
> +static void fifo_update_on_miss(struct Cache *cache,
> +                                int set,
> +                                int blk_idx)
> +{
> +    GQueue *q = cache->sets[set].evict_queue;
> +    g_queue_push_head(q, GINT_TO_POINTER(blk_idx));
> +}
> +
> +
>  static struct Cache *cache_init(int blksize, int assoc, int cachesize)
>  {
>      struct Cache *cache;
> @@ -113,6 +195,12 @@ static struct Cache *cache_init(int blksize, int
> assoc, int cachesize)
>      cache->set_mask = ((cache->num_sets - 1) <<
> (pow_of_two(cache->blksize)));
>      cache->tag_mask = ~(cache->set_mask | cache->blk_mask);
>
> +    if (lru) {
> +        lru_priorities_init(cache);
> +    } else if (fifo) {
> +        fifo_init(cache);
> +    }
> +
>      return cache;
>  }
>
> @@ -131,12 +219,20 @@ static int get_invalid_block(struct Cache *cache,
> uint64_t set)
>      return -1;
>  }
>
> -static int get_replaced_block(struct Cache *cache)
> +static int get_replaced_block(struct Cache *cache, int set)
>  {
> -    return g_rand_int_range(rng, 0, cache->assoc);
> +    if (rnd) {
> +        return g_rand_int_range(rng, 0, cache->assoc);
> +    } else if (lru) {
> +        return lru_get_lru_block(cache, set);
> +    } else if (fifo) {
> +        return fifo_get_first_in_block(cache, set);
> +    }
> +
> +    g_assert_not_reached();
>  }
>
> -static bool in_cache(struct Cache *cache, uint64_t addr)
> +static int in_cache(struct Cache *cache, uint64_t addr)
>  {
>      int i;
>      uint64_t tag, set;
> @@ -147,29 +243,39 @@ static bool in_cache(struct Cache *cache, uint64_t
> addr)
>      for (i = 0; i < cache->assoc; i++) {
>          if (cache->sets[set].blocks[i].tag == tag &&
>                  cache->sets[set].blocks[i].valid) {
> -            return true;
> +            return i;
>          }
>      }
>
> -    return false;
> +    return -1;
>  }
>
>  static enum AccessResult access_cache(struct Cache *cache, uint64_t addr)
>  {
>      uint64_t tag, set;
> -    int replaced_blk;
> -
> -    if (in_cache(cache, addr)) {
> -        return HIT;
> -    }
> +    int hit_blk, replaced_blk;
>
>      tag = extract_tag(cache, addr);
>      set = extract_set(cache, addr);
> +    hit_blk = in_cache(cache, addr);
> +
> +    if (hit_blk != -1) {
> +        if (lru) {
> +            lru_update_on_hit(cache, set, hit_blk);
> +        }
> +        return HIT;
> +    }
>
>      replaced_blk = get_invalid_block(cache, set);
>
>      if (replaced_blk == -1) {
> -        replaced_blk = get_replaced_block(cache);
> +        replaced_blk = get_replaced_block(cache, set);
> +    }
> +
> +    if (lru) {
> +        lru_update_on_miss(cache, set, replaced_blk);
> +    } else if (fifo) {
> +        fifo_update_on_miss(cache, set, replaced_blk);
>      }
>
>      cache->sets[set].blocks[replaced_blk].tag = tag;
> @@ -307,6 +413,11 @@ static void free_cache(struct Cache *cache)
>  {
>      for (int i = 0; i < cache->num_sets; i++) {
>          g_free(cache->sets[i].blocks);
> +        if (lru) {
> +            g_free(cache->sets[i].priorities);
> +        } else if (fifo) {
> +            g_queue_free(cache->sets[i].evict_queue);
> +        }
>      }
>
>      g_free(cache->sets);
> @@ -403,8 +514,6 @@ int qemu_plugin_install(qemu_plugin_id_t id, const
> qemu_info_t *info,
>      iblksize = 64;
>      icachesize = iblksize * iassoc * 32;
>
> -    rng = g_rand_new();
> -
>      for (i = 0; i < argc; i++) {
>          char *opt = argv[i];
>          if (g_str_has_prefix(opt, "I=")) {
> @@ -433,6 +542,22 @@ int qemu_plugin_install(qemu_plugin_id_t id, const
> qemu_info_t *info,
>              if (!tracefile) {
>                  fprintf(stderr, "could not open: %s for writing\n",
> file_name);
>              }
> +        } else if (g_str_has_prefix(opt, "evict=")) {
> +            if (lru || rnd || fifo) {
> +                fprintf(stderr, "eviction policy specified more than
> once\n");
> +                return -1;
> +            }
> +            gchar *policy = opt + 6;
> +            if (g_strcmp0(policy, "rand") == 0) {
> +                rnd = true;
> +            } else if (g_strcmp0(policy, "lru") == 0) {
> +                lru = true;
> +            } else if (g_strcmp0(policy, "fifo") == 0) {
> +                fifo = true;
> +            } else {
> +                fprintf(stderr, "invalid eviction policy: %s\n", opt);
> +                return -1;
> +            }
>          } else {
>              fprintf(stderr, "option parsing failed: %s\n", opt);
>              return -1;
> @@ -449,6 +574,14 @@ int qemu_plugin_install(qemu_plugin_id_t id, const
> qemu_info_t *info,
>          return -1;
>      }
>
> +    if (!rnd && !lru && !fifo) {
> +        lru = true;
> +    }
> +
> +    if (rnd) {
> +        rng = g_rand_new();
> +    }
> +
>      dcache = cache_init(dblksize, dassoc, dcachesize);
>      icache = cache_init(iblksize, iassoc, icachesize);
>
> --
> 2.25.1
>
>
CC'ing Emilio

On Tue, Jun 1, 2021 at 3:27 PM Alex Bennée <alex.bennee@linaro.org> wrote:

>
> Mahmoud Mandour <ma.mandourr@gmail.com> writes:
>
> > Now one of the three eviction policies can be chosen as an argument. On
> > not specifying an argument, LRU is used by default.
> >
> > Signed-off-by: Mahmoud Mandour <ma.mandourr@gmail.com>
> > ---
> >  contrib/plugins/cache.c | 159 ++++++++++++++++++++++++++++++++++++----
> >  1 file changed, 146 insertions(+), 13 deletions(-)
> >
> > diff --git a/contrib/plugins/cache.c b/contrib/plugins/cache.c
> > index fa0bf1dd40..1e323494bf 100644
> > --- a/contrib/plugins/cache.c
> > +++ b/contrib/plugins/cache.c
> > @@ -18,6 +18,8 @@
> >
> >  QEMU_PLUGIN_EXPORT int qemu_plugin_version = QEMU_PLUGIN_VERSION;
> >
> > +static bool fifo, lru, rnd;
> > +
>
> Ironically this would be a good use for a single variable with an enum,
> or alternatively a function pointer which can be set on initialisation.
>
> I think that I will implement the function pointers thing because as you
mention bellow it will somewhat reduce the clutter of checking the current
eviction policy each time and decide on which function to call.

>  static GRand *rng;
> >  static GHashTable *dmiss_ht;
> >  static GHashTable *imiss_ht;
> > @@ -55,6 +57,8 @@ struct CacheBlock {
> >
> >  struct CacheSet {
> >      struct CacheBlock *blocks;
> > +    uint16_t *priorities;
> > +    GQueue *evict_queue;
> >  };
> >
> >  struct Cache {
> > @@ -93,6 +97,84 @@ static inline uint64_t extract_set(struct Cache
> *cache, uint64_t addr)
> >      return (addr & cache->set_mask) >> (pow_of_two(cache->blksize));
> >  }
>
> I think it would be useful to summarise the LRU behaviour here in a
> comment and explain how the priorities are meant to change as the cache
> is used.


> >
> > +static void lru_priorities_init(struct Cache *cache)
> > +{
> > +    int i, j;
> > +
> > +    for (i = 0; i < cache->num_sets; i++) {
> > +        cache->sets[i].priorities = g_new(uint16_t, cache->assoc);
> > +        for (j = 0; j < cache->assoc; j++) {
> > +            cache->sets[i].priorities[j] = cache->assoc - j - 1;
> > +        }
> > +    }
> > +}
> > +
> > +static void lru_update_on_miss(struct Cache *cache,
> > +                                      int set_idx,
> > +                                      int blk_idx)
> > +{
> > +    int i;
> > +
> > +    for (i = 0; i < cache->assoc; i++) {
> > +        cache->sets[set_idx].priorities[i]++;
> > +    }
> > +
> > +    cache->sets[set_idx].priorities[blk_idx] = 0;
>
> So we increment priority for all non-hit blocks and reset it for the
> entry just used? This isn't totally clear to follow however see bellow:


> > +}
> > +
> > +static void lru_update_on_hit(struct Cache *cache,
> > +                                         int set_idx,
> > +                                         int blk_idx)
> > +{
> > +    uint16_t blk_priority;
> > +    int i;
> > +
> > +    blk_priority = cache->sets[set_idx].priorities[blk_idx];
> > +    for (i = 0; i < cache->assoc; i++) {
> > +        if (cache->sets[set_idx].priorities[i] < blk_priority) {
> > +            cache->sets[set_idx].priorities[i]++;
> > +        }
> > +    }
> > +    cache->sets[set_idx].priorities[blk_idx] = 0;
>
> This seems pretty expensive depending on the number of blocks. Another
> approach would be to have a generation number that is incremented on
> each access and stored in the appropriate set. Then...
>
> > +}
> > +
> > +static int lru_get_lru_block(struct Cache *cache, int set_idx)
> > +{
> > +    int i;
> > +
> > +    for (i = 0; i < cache->assoc; i++) {
> > +        if (cache->sets[set_idx].priorities[i] == cache->assoc - 1) {
> > +            return i;
> > +        }
> > +    }
>
> when you get to search for a "stale" block you just look for the lowest
> generation number. The eviction logic should be being called less than
> the update logic right?


Sorry for the confusion about LRU, so my idea is that if we have ASSOC
blocks in each set, the invariant is that I always have the least recently
used
block with a priority of ASSOC - 1. the second least recently used block
with
a priority of ASSOC - 2, etc. By incrementing every priority on miss, I
demote
other blocks and set the newly-cached block to priority 0, so we maintain
the
recency of usage sequence.

To be clear, your solution is on hit: increase the hit-block priority, and
on miss,
remove the element with the least priority (probably the new block here
will get
the highest priority which can be stored in the set itself so we don't
search for it)

If I understood something incorrectly please correct me.

The problem with that is we won't have the usage sequence anymore.
Consider a set with ASSOC = 4, and that set initially has no valid blocks
and the program generates the following accesses to the set:

MISS and replace block 3 (will increment block 3's priority to 1)
MISS and replace block 2 (will increment block 2's priority to 1)
MISS and replace block 1 (will increment block 1's priority to 1)
MISS and replace block 0 (will increment block 0's priority to 1)

LRU specifies that if we want to evict something, we'll need to evict block
3 since
the first block that was accessed and hence it's the LRU block.

But if we only choose the block with the least priority, we can evict block
0
which is in fact the most recently used block and the one with supposedly
the highest priority.

This would be an approximation for LRU and I guess that I can also
implement it
as an optional eviction algorithm since to my knowledge, numerous processors
implement an approximation for LRU. That's because it's expensive to
implement
exact LRU in hardware.


>
> > +
> > +    g_assert_not_reached();
> > +}
> > +
> > +static void fifo_init(struct Cache *cache)
> > +{
> > +    int i;
> > +
> > +    for (i = 0; i < cache->num_sets; i++) {
> > +        cache->sets[i].evict_queue = g_queue_new();
> > +    }
> > +}
> > +
> > +static int fifo_get_first_in_block(struct Cache *cache, int set)
> > +{
> > +    GQueue *q = cache->sets[set].evict_queue;
> > +    return GPOINTER_TO_INT(g_queue_pop_tail(q));
> > +}
> > +
> > +static void fifo_update_on_miss(struct Cache *cache,
> > +                                int set,
> > +                                int blk_idx)
> > +{
> > +    GQueue *q = cache->sets[set].evict_queue;
> > +    g_queue_push_head(q, GINT_TO_POINTER(blk_idx));
> > +}
>
> Again some commentary would be helpful around above the fifo functions.
>
> > +
> > +
> >  static struct Cache *cache_init(int blksize, int assoc, int cachesize)
> >  {
> >      struct Cache *cache;
> > @@ -113,6 +195,12 @@ static struct Cache *cache_init(int blksize, int
> assoc, int cachesize)
> >      cache->set_mask = ((cache->num_sets - 1) <<
> (pow_of_two(cache->blksize)));
> >      cache->tag_mask = ~(cache->set_mask | cache->blk_mask);
> >
> > +    if (lru) {
> > +        lru_priorities_init(cache);
> > +    } else if (fifo) {
> > +        fifo_init(cache);
> > +    }
> > +
> >      return cache;
> >  }
> >
> > @@ -131,12 +219,20 @@ static int get_invalid_block(struct Cache *cache,
> uint64_t set)
> >      return -1;
> >  }
> >
> > -static int get_replaced_block(struct Cache *cache)
> > +static int get_replaced_block(struct Cache *cache, int set)
> >  {
> > -    return g_rand_int_range(rng, 0, cache->assoc);
> > +    if (rnd) {
> > +        return g_rand_int_range(rng, 0, cache->assoc);
> > +    } else if (lru) {
> > +        return lru_get_lru_block(cache, set);
> > +    } else if (fifo) {
> > +        return fifo_get_first_in_block(cache, set);
> > +    }
> > +
> > +    g_assert_not_reached();
> >  }
> >
> > -static bool in_cache(struct Cache *cache, uint64_t addr)
> > +static int in_cache(struct Cache *cache, uint64_t addr)
> >  {
> >      int i;
> >      uint64_t tag, set;
> > @@ -147,29 +243,39 @@ static bool in_cache(struct Cache *cache, uint64_t
> addr)
> >      for (i = 0; i < cache->assoc; i++) {
> >          if (cache->sets[set].blocks[i].tag == tag &&
> >                  cache->sets[set].blocks[i].valid) {
> > -            return true;
> > +            return i;
> >          }
> >      }
> >
> > -    return false;
> > +    return -1;
> >  }
> >
> >  static enum AccessResult access_cache(struct Cache *cache, uint64_t
> addr)
> >  {
> >      uint64_t tag, set;
> > -    int replaced_blk;
> > -
> > -    if (in_cache(cache, addr)) {
> > -        return HIT;
> > -    }
> > +    int hit_blk, replaced_blk;
> >
> >      tag = extract_tag(cache, addr);
> >      set = extract_set(cache, addr);
> > +    hit_blk = in_cache(cache, addr);
> > +
> > +    if (hit_blk != -1) {
> > +        if (lru) {
> > +            lru_update_on_hit(cache, set, hit_blk);
> > +        }
> > +        return HIT;
> > +    }
> >
> >      replaced_blk = get_invalid_block(cache, set);
> >
> >      if (replaced_blk == -1) {
> > -        replaced_blk = get_replaced_block(cache);
> > +        replaced_blk = get_replaced_block(cache, set);
> > +    }
> > +
> > +    if (lru) {
> > +        lru_update_on_miss(cache, set, replaced_blk);
> > +    } else if (fifo) {
> > +        fifo_update_on_miss(cache, set, replaced_blk);
> >      }
>
> I wonder if just having a update_hit and update_miss function pointer
> would keep things cleaner?
>
>   if (update_hit) {
>        update_hit(cache, set, hit, block)
>   }
>
> etc...
>
> >
> >      cache->sets[set].blocks[replaced_blk].tag = tag;
> > @@ -307,6 +413,11 @@ static void free_cache(struct Cache *cache)
> >  {
> >      for (int i = 0; i < cache->num_sets; i++) {
> >          g_free(cache->sets[i].blocks);
> > +        if (lru) {
> > +            g_free(cache->sets[i].priorities);
>
> Hmm I've obviously missed something about how priorities are meant to be
> sued.
>

Can you please explain what's wrong with this? I only allocate an array of
priorities
when LRU is the chosen policy, so I only free it if `lru` is true. Am I
missing something?

>
> > +        } else if (fifo) {
> > +            g_queue_free(cache->sets[i].evict_queue);
> > +        }
> >      }
> >
> >      g_free(cache->sets);
> > @@ -403,8 +514,6 @@ int qemu_plugin_install(qemu_plugin_id_t id, const
> qemu_info_t *info,
> >      iblksize = 64;
> >      icachesize = iblksize * iassoc * 32;
> >
> > -    rng = g_rand_new();
> > -
> >      for (i = 0; i < argc; i++) {
> >          char *opt = argv[i];
> >          if (g_str_has_prefix(opt, "I=")) {
> > @@ -433,6 +542,22 @@ int qemu_plugin_install(qemu_plugin_id_t id, const
> qemu_info_t *info,
> >              if (!tracefile) {
> >                  fprintf(stderr, "could not open: %s for writing\n",
> file_name);
> >              }
> > +        } else if (g_str_has_prefix(opt, "evict=")) {
> > +            if (lru || rnd || fifo) {
> > +                fprintf(stderr, "eviction policy specified more than
> once\n");
> > +                return -1;
> > +            }
>
> This is one argument for the separate bools although generally QEMU
> operates on the basis of last argument wins ;-)


I Will do that, thanks. This seemed logical since I observed that from the
behavior of other plugins as well. It introduced some clutter since I'll
have
to turn off the other two booleans in order to only leave one policy turned
on.
But that is now not a problem since we agreed on removing the `lru`, `rnd`,
and `fifo` booleans already.

>
>
> > +            gchar *policy = opt + 6;
> > +            if (g_strcmp0(policy, "rand") == 0) {
> > +                rnd = true;
> > +            } else if (g_strcmp0(policy, "lru") == 0) {
> > +                lru = true;
> > +            } else if (g_strcmp0(policy, "fifo") == 0) {
> > +                fifo = true;
> > +            } else {
> > +                fprintf(stderr, "invalid eviction policy: %s\n", opt);
> > +                return -1;
> > +            }
> >          } else {
> >              fprintf(stderr, "option parsing failed: %s\n", opt);
> >              return -1;
> > @@ -449,6 +574,14 @@ int qemu_plugin_install(qemu_plugin_id_t id, const
> qemu_info_t *info,
> >          return -1;
> >      }
> >
> > +    if (!rnd && !lru && !fifo) {
> > +        lru = true;
> > +    }
> > +
> > +    if (rnd) {
> > +        rng = g_rand_new();
> > +    }
> > +
> >      dcache = cache_init(dblksize, dassoc, dcachesize);
> >      icache = cache_init(iblksize, iassoc, icachesize);
>
>
> --
> Alex Bennée
>