[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [RFC PATCH v2 3/3] plugins: cache: Added FIFO and LRU eviction polic
From: |
Alex Bennée |
Subject: |
Re: [RFC PATCH v2 3/3] plugins: cache: Added FIFO and LRU eviction policies. |
Date: |
Tue, 01 Jun 2021 13:43:14 +0100 |
User-agent: |
mu4e 1.5.13; emacs 28.0.50 |
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);
--
Alex Bennée
- Re: [RFC PATCH v2 3/3] plugins: cache: Added FIFO and LRU eviction policies.,
Alex Bennée <=