[3/7] qcow2: use an LRU algorithm to replace entries from the L2 cache

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(-)

On Wed, May 06, 2015 at 04:39:27PM +0300, 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(-)

Reviewed-by: Stefan Hajnoczi <stefanha@redhat.com>

On 05/06/2015 07:39 AM, 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(-)
> 

> @@ -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;

The comment is now dead.

On Thu 07 May 2015 04:55:21 PM CEST, Eric Blake wrote:

>>      /* 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;
>
> The comment is now dead.

Oh! Feel free to remove it when committing the patch, otherwise I can
send a new series.

Berto

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;
>   }