Re: [Qemu-devel] [Qemu-block] [PATCH 3/7] qcow2: use an LRU algorithm to replace entries from the L2 cache

[Max Reitz <mreitz@redhat.com>]

On 06.05.2015 15:39, Alberto Garcia wrote:
> The current algorithm to evict entries from the cache gives always
> preference to those in the lowest positions. As the size of the cache
> increases, the chances of the later elements of being removed decrease
> exponentially.
>
> In a scenario with random I/O and lots of cache misses, entries in
> positions 8 and higher are rarely (if ever) evicted. This can be seen
> even with the default cache size, but with larger caches the problem
> becomes more obvious.
>
> Using an LRU algorithm makes the chances of being removed from the
> cache independent from the position.
>
> Signed-off-by: Alberto Garcia <berto@igalia.com>
> ---
>   block/qcow2-cache.c | 31 +++++++++++++++----------------
>   1 file changed, 15 insertions(+), 16 deletions(-)
>
> diff --git a/block/qcow2-cache.c b/block/qcow2-cache.c
> index 6e78c8f..786c10a 100644
> --- a/block/qcow2-cache.c
> +++ b/block/qcow2-cache.c
> @@ -28,10 +28,10 @@
>   #include "trace.h"
>   
>   typedef struct Qcow2CachedTable {
> -    int64_t offset;
> -    bool    dirty;
> -    int     cache_hits;
> -    int     ref;
> +    int64_t  offset;
> +    bool     dirty;
> +    uint64_t lru_counter;
> +    int      ref;
>   } Qcow2CachedTable;
>   
>   struct Qcow2Cache {
> @@ -40,6 +40,7 @@ struct Qcow2Cache {
>       int                     size;
>       bool                    depends_on_flush;
>       void                   *table_array;
> +    uint64_t                lru_counter;
>   };
>   
>   static inline void *qcow2_cache_get_table_addr(BlockDriverState *bs,
> @@ -233,16 +234,18 @@ int qcow2_cache_empty(BlockDriverState *bs, Qcow2Cache *c)
>       for (i = 0; i < c->size; i++) {
>           assert(c->entries[i].ref == 0);
>           c->entries[i].offset = 0;
> -        c->entries[i].cache_hits = 0;
> +        c->entries[i].lru_counter = 0;
>       }
>   
> +    c->lru_counter = 0;
> +
>       return 0;
>   }
>   
>   static int qcow2_cache_find_entry_to_replace(Qcow2Cache *c)
>   {
>       int i;
> -    int min_count = INT_MAX;
> +    uint64_t min_lru_counter = UINT64_MAX;
>       int min_index = -1;
>   
>   
> @@ -251,15 +254,9 @@ static int qcow2_cache_find_entry_to_replace(Qcow2Cache *c)
>               continue;
>           }
>   
> -        if (c->entries[i].cache_hits < min_count) {
> +        if (c->entries[i].lru_counter < min_lru_counter) {
>               min_index = i;
> -            min_count = c->entries[i].cache_hits;
> -        }
> -
> -        /* Give newer hits priority */
> -        /* TODO Check how to optimize the replacement strategy */
> -        if (c->entries[i].cache_hits > 1) {
> -            c->entries[i].cache_hits /= 2;
> +            min_lru_counter = c->entries[i].lru_counter;
>           }
>       }
>   
> @@ -318,12 +315,10 @@ static int qcow2_cache_do_get(BlockDriverState *bs, Qcow2Cache *c,
>   
>       /* Give the table some hits for the start so that it won't be replaced
>        * immediately. The number 32 is completely arbitrary. */
> -    c->entries[i].cache_hits = 32;
>       c->entries[i].offset = offset;

With the coment removed:

Reviewed-by: Max Reitz <mreitz@redhat.com>

>       /* And return the right table */
>   found:
> -    c->entries[i].cache_hits++;
>       c->entries[i].ref++;
>       *table = qcow2_cache_get_table_addr(bs, c, i);
>   
> @@ -356,6 +351,10 @@ int qcow2_cache_put(BlockDriverState *bs, Qcow2Cache *c, void **table)
>       c->entries[i].ref--;
>       *table = NULL;
>   
> +    if (c->entries[i].ref == 0) {
> +        c->entries[i].lru_counter = ++c->lru_counter;
> +    }
> +
>       assert(c->entries[i].ref >= 0);
>       return 0;
>   }