From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from eggs.gnu.org ([2001:4830:134:3::10]:38150) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1Yqk7A-0007z1-DR for qemu-devel@nongnu.org; Fri, 08 May 2015 11:23:06 -0400 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1Yqk79-0000vR-DE for qemu-devel@nongnu.org; Fri, 08 May 2015 11:23:00 -0400 Message-ID: <554CD4BA.2020805@redhat.com> Date: Fri, 08 May 2015 17:22:34 +0200 From: Max Reitz MIME-Version: 1.0 References: <97f3d8a1ff7cbb2922a1d1c2007d7ccf44859294.1430919406.git.berto@igalia.com> In-Reply-To: <97f3d8a1ff7cbb2922a1d1c2007d7ccf44859294.1430919406.git.berto@igalia.com> Content-Type: text/plain; charset=iso-8859-15; format=flowed Content-Transfer-Encoding: 7bit Subject: Re: [Qemu-devel] [Qemu-block] [PATCH 3/7] qcow2: use an LRU algorithm to replace entries from the L2 cache List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , To: Alberto Garcia , qemu-devel@nongnu.org Cc: Stefan Hajnoczi , qemu-block@nongnu.org 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 > --- > 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 > /* 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; > }