qcow2 L2/refcount cache improvements
cover qcow2 L2/refcount cache improvements
Here are some improvements to the qcow2 L2/refcount cache code.
The first one is that all cache tables are now allocated using a single memory block, as we discussed last week.
Apart from a more efficient use of memory, this allows some additional optimizations so I took the chance to make other changes.
- qcow2_cache_put() and qcow2_cache_entry_mark_dirty() are now O(1)
- The eviction algorithm is now LRU. The previous one only works well with very small cache sizes.
- qcow2_cache_find_entry_to_replace() is no longer necessary.
- Lookups are faster now.
In my tests with a preallocated 128MB L2 cache in an empty drive the new code is ~13% faster than the previous one (~43% if compiled without optimizations). This is a best-case scenario, if the cache is smaller or the drive is full of data the improvements are not so visible, but I believe the code is simpler now so I hope you find the changes worthwhile.
Regards,
Berto
Alberto Garcia (6):
qcow2: use one single memory block for the L2/refcount cache tables
qcow2: simplify qcow2_cache_put() and qcow2_cache_entry_mark_dirty()
qcow2: use an LRU algorithm to replace entries from the L2 cache
qcow2: remove qcow2_cache_find_entry_to_replace()
qcow2: use a hash to look for entries in the L2 cache
qcow2: style fixes in qcow2-cache.c
block/qcow2-cache.c | 149 +++++++++++++++++++++------------------------------- 1 file changed, 61 insertions(+), 88 deletions(-)
Signature · 1 line
2.1.4
PATCH 1/6 qcow2: use one single memory block for the L2/refcount cache tables
The qcow2 L2/refcount cache contains one separate table for each cache entry. Doing one allocation per table adds unnecessary overhead and it also requires us to store the address of each table separately.
Since the size of the cache is constant during its lifetime, it's better to have an array that contains all the tables using one single allocation.
In my tests measuring freshly created caches with sizes 128MB (L2) and 32MB (refcount) this uses around 10MB of RAM less.
--- block/qcow2-cache.c | 48 +++++++++++++++++++++--------------------------- 1 file changed, 21 insertions(+), 27 deletions(-)
block/qcow2-cache.c +21 -27
@@ -28,7 +28,6 @@#include "trace.h" typedef struct Qcow2CachedTable { - void* table; int64_t offset; bool dirty; int cache_hits;
@@ -40,39 +39,34 @@ struct Qcow2Cache {struct Qcow2Cache * depends;int size;bool depends_on_flush; +void *table_array; +int table_size; }; +static inline void *table_addr (Qcow2Cache *c,int table) +{ +return c->table_array + table * c->table_size; +} +Qcow2Cache *qcow2_cache_create (BlockDriverState *bs,int num_tables) {BDRVQcowState *s = bs->opaque;Qcow2Cache *c; -int i; c =g_new0 (Qcow2Cache,1 ); c->size = num_tables; + c->table_size = s->cluster_size; c->entries =g_try_new0 (Qcow2CachedTable, num_tables); -if (!c->entries) { - goto fail; - } + c->table_array =qemu_try_blockalign (bs->file, num_tables * c->table_size); -for (i =0 ; i < c->size; i++) { - c->entries[i].table =qemu_try_blockalign (bs->file, s->cluster_size); -if (c->entries[i].table ==NULL ) { - goto fail; - } +if (!c->entries || !c->table_array) { +qemu_vfree (c->table_array); +g_free (c->entries); +g_free (c); + c =NULL ; }return c; - -fail: -if (c->entries) { -for (i =0 ; i < c->size; i++) { -qemu_vfree (c->entries[i].table); - } - } -g_free (c->entries); -g_free (c); -return NULL ; }int qcow2_cache_destroy (BlockDriverState * bs,Qcow2Cache *c)
@@ -81,9 +75,9 @@ int qcow2_cache_destroy(BlockDriverState* bs, Qcow2Cache *c)for (i =0 ; i < c->size; i++) {assert (c->entries[i].ref ==0 ); -qemu_vfree (c->entries[i].table); } +qemu_vfree (c->table_array);g_free (c->entries);g_free (c);
@@ -151,8 +145,8 @@ static int qcow2_cache_entry_flush(BlockDriverState *bs, Qcow2Cache *c, int i)BLKDBG_EVENT (bs->file,BLKDBG_L2_UPDATE ); } - ret =bdrv_pwrite (bs->file, c->entries[i].offset, c->entries[i].table, - s->cluster_size); + ret =bdrv_pwrite (bs->file, c->entries[i].offset,table_addr (c, i), + s->cluster_size);if (ret <0 ) {return ret; }
@@ -304,7 +298,7 @@ static int qcow2_cache_do_get(BlockDriverState *bs, Qcow2Cache *c,BLKDBG_EVENT (bs->file,BLKDBG_L2_LOAD ); } - ret =bdrv_pread (bs->file, offset, c->entries[i].table, s->cluster_size); + ret =bdrv_pread (bs->file, offset,table_addr (c, i), s->cluster_size);if (ret <0 ) {return ret; }
@@ -319,7 +313,7 @@ static int qcow2_cache_do_get(BlockDriverState *bs, Qcow2Cache *c, found: c->entries[i].cache_hits++; c->entries[i].ref++; - *table = c->entries[i].table; + *table =table_addr (c, i);trace_qcow2_cache_get_done (qemu_coroutine_self (), c == s->l2_table_cache, i);
@@ -344,7 +338,7 @@ int qcow2_cache_put(BlockDriverState *bs, Qcow2Cache *c, void **table)int i;for (i =0 ; i < c->size; i++) { -if (c->entries[i].table == *table) { +if (table_addr (c, i) == *table) { goto found; } }
@@ -363,7 +357,7 @@ void qcow2_cache_entry_mark_dirty(Qcow2Cache *c, void *table)int i;for (i =0 ; i < c->size; i++) { -if (c->entries[i].table == table) { +if (table_addr (c, i) == table) { goto found; } }
Signature · 1 line
2.1.4
Re: [Qemu-devel] [PATCH 1/6] qcow2: use one single memory block for the L2/refcount cache tables
Quoted 24 lines · Alberto Garcia
The qcow2 L2/refcount cache contains one separate table for each cache entry. Doing one allocation per table adds unnecessary overhead and it also requires us to store the address of each table separately.
Since the size of the cache is constant during its lifetime, it's better to have an array that contains all the tables using one single allocation.
In my tests measuring freshly created caches with sizes 128MB (L2) and 32MB (refcount) this uses around 10MB of RAM less.
Signed-off-by Alberto Garcia <[email protected]>--- block/qcow2-cache.c | 48 +++++++++++++++++++++--------------------------- 1 file changed, 21 insertions(+), 27 deletions(-)typedef struct Qcow2CachedTable {
block/qcow2-cache.c +0
-1-void * table;int64_t offset;bool dirty;int cache_hits;
block/qcow2-cache.c struct Qcow2Cache { · line 43
Quoted 5 lines
block/qcow2-cache.c +2
-0@@ -40,39 +39,34 @@ struct Qcow2Cache {struct Qcow2Cache * depends;int size;bool depends_on_flush; +void *table_array; +int table_size;
Should this be size_t? [1]
block/qcow2-cache.c struct Qcow2Cache { · line 48
Quoted 5 lines
block/qcow2-cache.c +3
-0}; +static inline void *table_addr (Qcow2Cache *c,int table) +{ +return c->table_array + table * c->table_size;
Addition on void* is not portable.
block/qcow2-cache.c struct Qcow2Cache { · line 58
Quoted 11 lines
block/qcow2-cache.c +3
-1+} +Qcow2Cache *qcow2_cache_create (BlockDriverState *bs,int num_tables) {BDRVQcowState *s = bs->opaque;Qcow2Cache *c; -int i; c =g_new0 (Qcow2Cache,1 ); c->size = num_tables; + c->table_size = s->cluster_size;
[1] Oh, maybe not, since BDRVQcowState declares cluster_size as int.
block/qcow2-cache.c struct Qcow2Cache { · line 60
Quoted 5 lines
block/qcow2-cache.c +1
-3c->entries =g_try_new0 (Qcow2CachedTable, num_tables); -if (!c->entries) { - goto fail; - } + c->table_array =qemu_try_blockalign (bs->file, num_tables * c->table_size);
Are we sure this won't overflow?
Signature · 2 lines
Eric Blake eblake redhat com +1-919-301-3266 Libvirt virtualization library http://libvirt.org
Re: [Qemu-devel] [PATCH 1/6] qcow2: use one single memory block for the L2/refcount cache tables
Quoted 5 lines · Eric Blake
Quoted 5 lines
typedef struct Qcow2CachedTable {
- void* table; int64_t offset; bool dirty; int cache_hits;
Quoted 8 lines
block/qcow2-cache.c struct Qcow2Cache { · line 43
Quoted 6 lines
block/qcow2-cache.c +2
-0@@ -40,39 +39,34 @@ struct Qcow2Cache {struct Qcow2Cache * depends;int size;bool depends_on_flush; +void *table_array; +int table_size;Should this be
size_t? [1]
The maximum supported table size is 2MB (MAX_CLUSTER_BITS == 21).
Quoted 7 lines
block/qcow2-cache.c struct Qcow2Cache { · line 60
Quoted 5 lines
block/qcow2-cache.c +1
-3c->entries =g_try_new0 (Qcow2CachedTable, num_tables); -if (!c->entries) { - goto fail; - } + c->table_array =qemu_try_blockalign (bs->file, num_tables * c->table_size);Are we sure this won't overflow?
That's a good catch. I was making some numbers and I doubt that scenario would happen in practice, but I think it's possible so I'll fix it.
Berto
Re: [Qemu-devel] [Qemu-block] [PATCH 1/6] qcow2: use one single memory block for the L2/refcount cache tables
In reply to Alberto Garciablock/qcow2-cache.c struct Qcow2Cache { · line 58
Quoted 9 lines · Alberto Garcia
Qcow2Cache *qcow2_cache_create(BlockDriverState *bs, int
num_tables){ BDRVQcowState *s = bs->opaque; Qcow2Cache *c;block/qcow2-cache.c +1
-1-int i; c =g_new0 (Qcow2Cache,1 ); c->size = num_tables; + c->table_size = s->cluster_size;
This assumes c->table_size meets bs' memory alignment requirements. The following would be safer:
c->table_size = QEMU_ALIGN_UP(c->table_size, bdrv_opt_mem_align(bs->file));
Re: [Qemu-devel] [Qemu-block] [PATCH 1/6] qcow2: use one single memory block for the L2/refcount cache tables
Am 01.05.2015 um 16:23 hat Stefan Hajnoczi geschrieben:
Quoted 7 lines · Alberto Garcia
Quoted 6 lines
Qcow2Cache *qcow2_cache_create(BlockDriverState *bs, int
num_tables){ BDRVQcowState *s = bs->opaque; Qcow2Cache *c;- int i;
Quoted 8 lines
Quoted 3 lines
c = g_new0(Qcow2Cache, 1); c->size = num_tables;+
c->table_size=s->cluster_size;This assumes
c->table_sizemeets bs' memory alignment requirements. The following would be safer:
c->table_size=QEMU_ALIGN_UP(c->table_size, bdrv_opt_mem_align(bs->file));
You can't just access more than one cluster. You might be caching data and later write it back when it's stale.
If you can't do I/O in chunks as small as the cluster size (which is rather unlikely), relying on bdrv_pwrite(), like Berto's patch does, is the correct solution.
Kevin
Re: [Qemu-devel] [Qemu-block] [PATCH 1/6] qcow2: use one single memory block for the L2/refcount cache tables
Quoted 12 lines · Kevin Wolf
Am 01.05.2015 um 16:23 hat Stefan Hajnoczi geschrieben:
Quoted 11 lines · Alberto Garcia
Quoted 9 lines
Qcow2Cache *qcow2_cache_create(BlockDriverState *bs, int
num_tables){ BDRVQcowState *s = bs->opaque; Qcow2Cache *c;block/qcow2-cache.c +1
-1-int i; c =g_new0 (Qcow2Cache,1 ); c->size = num_tables; + c->table_size = s->cluster_size;
Quoted 7 lines
Quoted 4 lines
This assumes
c->table_sizemeets bs' memory alignment requirements. The following would be safer:
c->table_size=QEMU_ALIGN_UP(c->table_size, bdrv_opt_mem_align(bs->file));You can't just access more than one cluster. You might be caching data and later write it back when it's stale.
I don't mean I/O alignment, just memory alignment (i.e. the start address of the data buffer in memory).
Stefan
Re: [Qemu-devel] [Qemu-block] [PATCH 1/6] qcow2: use one single memory block for the L2/refcount cache tables
Am 05.05.2015 um 12:28 hat Stefan Hajnoczi geschrieben:
Quoted 16 lines · Kevin Wolf
Quoted 15 lines
Am 01.05.2015 um 16:23 hat Stefan Hajnoczi geschrieben:
Quoted 14 lines · Alberto Garcia
block/qcow2-cache.c struct Qcow2Cache { · line 58
Quoted 9 lines
Qcow2Cache *qcow2_cache_create(BlockDriverState *bs, int
num_tables){ BDRVQcowState *s = bs->opaque; Qcow2Cache *c;block/qcow2-cache.c +1
-1-int i; c =g_new0 (Qcow2Cache,1 ); c->size = num_tables; + c->table_size = s->cluster_size;This assumes
c->table_sizemeets bs' memory alignment requirements. The following would be safer:
Quoted 7 lines
Quoted 4 lines
Quoted 1 line
c->table_size=QEMU_ALIGN_UP(c->table_size, bdrv_opt_mem_align(bs->file));You can't just access more than one cluster. You might be caching data and later write it back when it's stale.
I don't mean I/O alignment, just memory alignment (i.e. the start address of the data buffer in memory).
The start address is already taken care of by qemu_blockalign(). With rounding c->table_size, you'd align the length, and that would be wrong.
Though looking at the code again I see now that c->table_size isn't consistently used. The I/O requests still use s->cluster_size. We should either use it everywhere or not introduce it at all.
Kevin
Re: [Qemu-devel] [Qemu-block] [PATCH 1/6] qcow2: use one single memory block for the L2/refcount cache tables
Quoted 3 lines · Kevin Wolf
Though looking at the code again I see now that
c->table_sizeisn't consistently used. The I/O requests still uses->cluster_size. We should either use it everywhere or not introduce it at all.
c->table_size is necessary in order to calculate the offset of a particular table, because s->cluster_size is not always available (e.g. qcow2_cache_entry_mark_dirty()). We could make it a requirement of the API, though.
Alternatively we could have c->bs instead of c->table_size. That would spare us from passing the BlockDriverState pointer to all qcow2_cache_ functions.
The assumption would be that the BlockDriverState pointer is the same for the whole lifetime of the cache, but that's always guaranteed to be like that, right?
Berto
Re: [Qemu-devel] [Qemu-block] [PATCH 1/6] qcow2: use one single memory block for the L2/refcount cache tables
In reply to Kevin WolfQuoted 19 lines · Kevin Wolf
Am 05.05.2015 um 12:28 hat Stefan Hajnoczi geschrieben:
Quoted 18 lines · Kevin Wolf
Quoted 17 lines
Am 01.05.2015 um 16:23 hat Stefan Hajnoczi geschrieben:
Quoted 15 lines · Alberto Garcia
block/qcow2-cache.c struct Qcow2Cache { · line 58
Quoted 9 lines
Qcow2Cache *qcow2_cache_create(BlockDriverState *bs, int
num_tables){ BDRVQcowState *s = bs->opaque; Qcow2Cache *c;block/qcow2-cache.c +1
-1-int i; c =g_new0 (Qcow2Cache,1 ); c->size = num_tables; + c->table_size = s->cluster_size;This assumes
c->table_sizemeets bs' memory alignment requirements. The following would be safer:
c->table_size=QEMU_ALIGN_UP(c->table_size, bdrv_opt_mem_align(bs->file));
Quoted 8 lines
Quoted 5 lines
Quoted 2 lines
You can't just access more than one cluster. You might be caching data and later write it back when it's stale.
I don't mean I/O alignment, just memory alignment (i.e. the start address of the data buffer in memory).
The start address is already taken care of by
qemu_blockalign(). With roundingc->table_size, you'd align the length, and that would be wrong.
It wasn't clear to me that c->table + n * c->table_size for all n is aligned, but I agree with you now:
bdrv_qiov_is_aligned() checks both address and size against memory alignment. This means that if the I/O is memory aligned for table_size, then all multiples of table_size are also aligned.
Stefan
PATCH 2/6 qcow2: simplify qcow2_cache_put() and qcow2_cache_entry_mark_dirty()
In reply to Alberto GarciaSince all tables are now stored together, it is possible to obtain the position of a particular table directly from its address, so the operation becomes O(1).
--- block/qcow2-cache.c | 22 +++++----------------- 1 file changed, 5 insertions(+), 17 deletions(-)
block/qcow2-cache.c +5 -17
@@ -335,16 +335,12 @@ int qcow2_cache_get_empty(BlockDriverState *bs, Qcow2Cache *c, uint64_t offset,int qcow2_cache_put (BlockDriverState *bs,Qcow2Cache *c,void **table) { -int i; +int i = (*table - c->table_array) / c->table_size; -for (i =0 ; i < c->size; i++) { -if (table_addr (c, i) == *table) { - goto found; - } +if (c->entries[i].offset ==0 ) { +return -ENOENT ; } -return -ENOENT ; -found: c->entries[i].ref--; *table =NULL ;
@@ -354,15 +350,7 @@ found:void qcow2_cache_entry_mark_dirty (Qcow2Cache *c,void *table) { -int i; - -for (i =0 ; i < c->size; i++) { -if (table_addr (c, i) == table) { - goto found; - } - } -abort (); - -found: +int i = (table - c->table_array) / c->table_size; +assert (c->entries[i].offset !=0 ); c->entries[i].dirty = true; }
Signature · 1 line
2.1.4
Re: [Qemu-devel] [PATCH 2/6] qcow2: simplify qcow2_cache_put() and qcow2_cache_entry_mark_dirty()
Quoted 8 lines · Alberto Garcia
int
qcow2_cache_put(BlockDriverState *bs, Qcow2Cache *c, void **table){block/qcow2-cache.c +1
-3-int i; +int i = (*table - c->table_array) / c->table_size; -for (i =0 ; i < c->size; i++) { -if (table_addr (c, i) == *table) {
block/qcow2-cache.c int qcow2_cache_get_empty(BlockDriverState *bs, Qcow2Cache *c, uint64_t offset, · line 345
Quoted 10 lines
block/qcow2-cache.c +2
-4- goto found; - } +if (c->entries[i].offset ==0 ) { +return -ENOENT ; } -return -ENOENT ; -found: c->entries[i].ref--; *table =NULL ;
When is this function called with a bogus table pointer?
My hunch is there are no callers like that. I might be wrong.
If there are no callers like that, then you can extract this and include an assertion instead:
static int qcow2_cache_get_table_idx(Qcow2Cache *c, void *table)
{
assert(table >= c->table_array &&);
table < c->table_array + c->size * c->table_size);
return (table - c->table_array) / c->table_size;
}Functions that go from void *table to int i should use this helper.
And the qcow2_cache_put() users can drop their error handling code. A lot of them ignore the return value anyway, so it simplifies things even more.
Stefan
Re: [Qemu-devel] [PATCH 2/6] qcow2: simplify qcow2_cache_put() and qcow2_cache_entry_mark_dirty()
Quoted 14 lines · Stefan Hajnoczi
Quoted 14 lines
int
qcow2_cache_put(BlockDriverState *bs, Qcow2Cache *c, void **table){block/qcow2-cache.c +3
-6-int i; +int i = (*table - c->table_array) / c->table_size; -for (i =0 ; i < c->size; i++) { -if (table_addr (c, i) == *table) { - goto found; - } +if (c->entries[i].offset ==0 ) { +return -ENOENT ; } -return -ENOENT ;
Quoted 6 lines
Quoted 4 lines
-found:
c->entries[i].ref--; *table = NULL;When is this function called with a bogus table pointer?
I also could not image any such scenario, but I decided to be conservative and keep the error handling code. I'll double check all places where it's used and remove the relevant code.
Berto
Re: [Qemu-devel] [PATCH 2/6] qcow2: simplify qcow2_cache_put() and qcow2_cache_entry_mark_dirty()
Quoted 21 lines · Alberto Garcia
Quoted 19 lines · Stefan Hajnoczi
Quoted 18 lines
int
qcow2_cache_put(BlockDriverState *bs, Qcow2Cache *c, void **table){block/qcow2-cache.c +3
-7-int i; +int i = (*table - c->table_array) / c->table_size; -for (i =0 ; i < c->size; i++) { -if (table_addr (c, i) == *table) { - goto found; - } +if (c->entries[i].offset ==0 ) { +return -ENOENT ; } -return -ENOENT ; -found: c->entries[i].ref--; *table =NULL ;
Quoted 5 lines
Quoted 1 line
When is this function called with a bogus table pointer?
I also could not image any such scenario, but I decided to be conservative and keep the error handling code. I'll double check all places where it's used and remove the relevant code.
The reason why I'd think this is worth looking into is:
The new qcow2_cache_put() code indexes outside the array bounds if table is a bogus value. The old code would return -ENOENT. So I am a little nervous about the change, although I suspect the function is never called with invalid inputs at all.
Stefan
Re: [Qemu-devel] [PATCH 2/6] qcow2: simplify qcow2_cache_put() and qcow2_cache_entry_mark_dirty()
Quoted 25 lines · Stefan Hajnoczi
Quoted 19 lines
Quoted 19 lines
Quoted 18 lines
int
qcow2_cache_put(BlockDriverState *bs, Qcow2Cache *c, void **table){block/qcow2-cache.c +3
-7-int i; +int i = (*table - c->table_array) / c->table_size; -for (i =0 ; i < c->size; i++) { -if (table_addr (c, i) == *table) { - goto found; - } +if (c->entries[i].offset ==0 ) { +return -ENOENT ; } -return -ENOENT ; -found: c->entries[i].ref--; *table =NULL ;Quoted 5 lines
Quoted 1 line
When is this function called with a bogus table pointer?
I also could not image any such scenario, but I decided to be conservative and keep the error handling code. I'll double check all places where it's used and remove the relevant code.
Quoted 6 lines
The reason why I'd think this is worth looking into is:
The new
qcow2_cache_put()code indexes outside the array bounds if table is a bogus value. The old code would return-ENOENT. So I am a little nervous about the change, although I suspect the function is never called with invalid inputs at all.
I checked again all callers of qcow2_cache_put() and I didn't notice anything unusual.
In some cases it even goes after qcow2_cache_entry_mark_dirty(), and that one directly aborts if the table pointer is bogus.
Berto
Re: [Qemu-devel] [PATCH 2/6] qcow2: simplify qcow2_cache_put() and qcow2_cache_entry_mark_dirty()
In reply to Alberto GarciaQuoted 14 lines · Alberto Garcia
Since all tables are now stored together, it is possible to obtain the position of a particular table directly from its address, so the operation becomes O(1).
Signed-off-by Alberto Garcia <[email protected]>--- block/qcow2-cache.c | 22 +++++----------------- 1 file changed, 5 insertions(+), 17 deletions(-)block/qcow2-cache.c +0
-0
block/qcow2-cache.c int qcow2_cache_get_empty(BlockDriverState *bs, Qcow2Cache *c, uint64_t offset, · line 338
Quoted 5 lines
block/qcow2-cache.c +1
-1@@ -335,16 +335,12 @@ int qcow2_cache_get_empty(BlockDriverState *bs, Qcow2Cache *c, uint64_t offset,int qcow2_cache_put (BlockDriverState *bs,Qcow2Cache *c,void **table) { -int i; +int i = (*table - c->table_array) / c->table_size;
Arithmetic on void* is not portable.
block/qcow2-cache.c found: · line 353
Quoted 13 lines
block/qcow2-cache.c +1
-10void qcow2_cache_entry_mark_dirty (Qcow2Cache *c,void *table) { -int i; - -for (i =0 ; i < c->size; i++) { -if (table_addr (c, i) == table) { - goto found; - } - } -abort (); - -found: +int i = (table - c->table_array) / c->table_size;
and again.
Quoted 4 lines
block/qcow2-cache.c +1
-0+assert (c->entries[i].offset !=0 ); c->entries[i].dirty = true; }
Signature · 2 lines
Eric Blake eblake redhat com +1-919-301-3266 Libvirt virtualization library http://libvirt.org
PATCH 3/6 qcow2: use an LRU algorithm to replace entries from the L2 cache
In reply to Alberto GarciaThe 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.
--- block/qcow2-cache.c | 31 +++++++++++++++---------------- 1 file changed, 15 insertions(+), 16 deletions(-)
block/qcow2-cache.c +15 -16
@@ -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 {
@@ -41,6 +41,7 @@ struct Qcow2Cache {bool depends_on_flush;void *table_array;int table_size; +uint64_t lru_counter; };static inline void *table_addr (Qcow2Cache *c,int table)
@@ -222,16 +223,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 ;
@@ -240,15 +243,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; } }
@@ -306,12 +303,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;/* And return the right table */ found: - c->entries[i].cache_hits++; c->entries[i].ref++; *table =table_addr (c, i);
@@ -344,6 +339,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 ; }
Signature · 1 line
2.1.4
PATCH 4/6 qcow2: remove qcow2_cache_find_entry_to_replace()
In reply to Alberto GarciaA cache miss means that the whole array was traversed and the entry we were looking for was not found, so there's no need to traverse it again in order to select an entry to replace.
--- block/qcow2-cache.c | 45 ++++++++++++++++----------------------------- 1 file changed, 16 insertions(+), 29 deletions(-)
block/qcow2-cache.c +16 -29
@@ -231,51 +231,38 @@ int qcow2_cache_empty(BlockDriverState *bs, Qcow2Cache *c)return 0 ; } -static int qcow2_cache_find_entry_to_replace (Qcow2Cache *c) -{ -int i; -uint64_t min_lru_counter =UINT64_MAX ; -int min_index =-1 ; - - -for (i =0 ; i < c->size; i++) { -if (c->entries[i].ref) { -continue ; - } - -if (c->entries[i].lru_counter < min_lru_counter) { - min_index = i; - min_lru_counter = c->entries[i].lru_counter; - } - } - -if (min_index ==-1 ) { -/* This can't happen in current synchronous code, but leave the check -* here as a reminder for whoever starts using AIO with the cache */ -abort (); - } -return min_index; -} -static int qcow2_cache_do_get (BlockDriverState *bs,Qcow2Cache *c,uint64_t offset,void **table,bool read_from_disk) {BDRVQcowState *s = bs->opaque;int i;int ret; +uint64_t min_lru_counter =UINT64_MAX ; +int min_lru_index =-1 ;trace_qcow2_cache_get (qemu_coroutine_self (), c == s->l2_table_cache, offset, read_from_disk);/* Check if the table is already cached */ for (i =0 ; i < c->size; i++) { -if (c->entries[i].offset == offset) { +const Qcow2CachedTable *t = &c->entries[i]; +if (t->offset == offset) { goto found; } +if (t->ref ==0 && t->lru_counter < min_lru_counter) { + min_lru_counter = t->lru_counter; + min_lru_index = i; + } + } + +if (min_lru_index ==-1 ) { +/* This can't happen in current synchronous code, but leave the check +* here as a reminder for whoever starts using AIO with the cache */ +abort (); } -/* If not, write a table back and replace it */ - i =qcow2_cache_find_entry_to_replace (c); +/* Cache miss: write a table back and replace it */ + i = min_lru_index;trace_qcow2_cache_get_replace_entry (qemu_coroutine_self (), c == s->l2_table_cache, i);if (i <0 ) {
Signature · 1 line
2.1.4
PATCH 5/6 qcow2: use a hash to look for entries in the L2 cache
In reply to Alberto GarciaThe current cache algorithm traverses the array starting always from the beginning, so the average number of comparisons needed to perform a lookup is proportional to the size of the array.
By using a hash of the offset as the starting point, lookups are faster and independent from the array size.
The hash is computed using the cluster number of the table, multiplied by 4 to make it perform better when there are collisions.
In my tests, using a cache with 2048 entries, this reduces the average number of comparisons per lookup from 430 to 2.5.
--- block/qcow2-cache.c | 9 +++++++-- 1 file changed, 7 insertions(+), 2 deletions(-)
block/qcow2-cache.c +7 -2
@@ -237,6 +237,7 @@ static int qcow2_cache_do_get(BlockDriverState *bs, Qcow2Cache *c,BDRVQcowState *s = bs->opaque;int i;int ret; +int lookup_index;uint64_t min_lru_counter =UINT64_MAX ;int min_lru_index =-1 ;
@@ -244,7 +245,8 @@ static int qcow2_cache_do_get(BlockDriverState *bs, Qcow2Cache *c, offset, read_from_disk);/* Check if the table is already cached */ -for (i =0 ; i < c->size; i++) { + i = lookup_index = (offset / c->table_size *4 ) % c->size; + do { const Qcow2CachedTable *t = &c->entries[i]; if (t->offset == offset) { goto found;
@@ -253,7 +255,10 @@ static int qcow2_cache_do_get(BlockDriverState *bs, Qcow2Cache *c, min_lru_counter = t->lru_counter; min_lru_index = i; } - } +if (++i == c->size) { + i =0 ; + } + }while (i != lookup_index);if (min_lru_index ==-1 ) {/* This can't happen in current synchronous code, but leave the check
Signature · 1 line
2.1.4
Re: [Qemu-devel] [Qemu-block] [PATCH 5/6] qcow2: use a hash to look for entries in the L2 cache
Quoted 5 lines · Alberto Garcia
By using a hash of the offset as the starting point, lookups are faster and independent from the array size.
The hash is computed using the cluster number of the table, multiplied by 4 to make it perform better when there are collisions.
...
Quoted 1 line
+ i =
lookup_index= (offset /c->table_size* 4) %c->size;
The hash function is very weak. It's better than always starting with i=0 but mixes input bits very poorly. Have you considered an integer hash function so that more input bits affect the output?
http://burtleburtle.net/bob/hash/integer.html
Regarding collisions, the multiply-by-4 effectively reduces the hash space by a factor of 4. This *increases* the chance of collisions in the hope that the extra slots will prevent chains from forming.
Using an integer hash function ought to be more resistant to input value patterns and eliminate the need for multiply-by-4, because chains only form when the table load is high.
Finally, the hash optimizes for the sparsely occupied table scenario. If the table is loaded (dense) then there will be chains in any case. A full search will be necessary.
Feel free to leave the hash function as-is, I don't think it's a huge issue either way.
Stefan
Re: [Qemu-devel] [Qemu-block] [PATCH 5/6] qcow2: use a hash to look for entries in the L2 cache
Quoted 5 lines · Stefan Hajnoczi
Quoted 5 lines
By using a hash of the offset as the starting point, lookups are faster and independent from the array size.
The hash is computed using the cluster number of the table, multiplied by 4 to make it perform better when there are collisions.
Quoted 7 lines
...
Quoted 1 line
+ i =
lookup_index= (offset /c->table_size* 4) %c->size;The hash function is very weak. It's better than always starting with i=0 but mixes input bits very poorly. Have you considered an integer hash function so that more input bits affect the output?
http://burtleburtle.net/bob/hash/integer.html
I didn't try very hard to optimize the hash function because it doesn't have a big impact, I just wanted something simple and a bit better than i=0.
I did my tests with a disk image with preallocated metadata and a cache size big enough for the whole disk. In that scenario I managed an average of 2.5 comparisons per lookup with this function.
Quoted 3 lines
Regarding collisions, the multiply-by-4 effectively reduces the hash space by a factor of 4. This *increases* the chance of collisions in the hope that the extra slots will prevent chains from forming.
It does, but it keeps the average much lower (in my tests at least), it went down from >100 to 2.5.
Quoted 2 lines
Feel free to leave the hash function as-is, I don't think it's a huge issue either way.
I think I'll just leave it as-is for the time being, but thanks a lot for your comments.
Berto
PATCH 6/6 qcow2: style fixes in qcow2-cache.c
In reply to Alberto GarciaFix pointer declaration to make it consistent with the rest of the code.
--- block/qcow2-cache.c | 6 +++--- 1 file changed, 3 insertions(+), 3 deletions(-)
block/qcow2-cache.c +3 -3
@@ -35,8 +35,8 @@ typedef struct Qcow2CachedTable { } Qcow2CachedTable;struct Qcow2Cache { -Qcow2CachedTable * entries; -struct Qcow2Cache * depends; +Qcow2CachedTable *entries; +struct Qcow2Cache *depends;int size;bool depends_on_flush;void *table_array;
@@ -70,7 +70,7 @@ Qcow2Cache *qcow2_cache_create(BlockDriverState *bs, int num_tables)return c; } -int qcow2_cache_destroy (BlockDriverState * bs,Qcow2Cache *c) +int qcow2_cache_destroy (BlockDriverState *bs,Qcow2Cache *c) {int i;
Signature · 1 line
2.1.4
Re: [Qemu-devel] [PATCH 6/6] qcow2: style fixes in qcow2-cache.c
Quoted 7 lines · Alberto Garcia
Fix pointer declaration to make it consistent with the rest of the code.
Signed-off-by Alberto Garcia <[email protected]>--- block/qcow2-cache.c | 6 +++--- 1 file changed, 3 insertions(+), 3 deletions(-)
:)
Quoted 14 lines · Alberto Garcia
Here are some improvements to the qcow2 L2/refcount cache code.
The first one is that all cache tables are now allocated using a single memory block, as we discussed last week.
Apart from a more efficient use of memory, this allows some additional optimizations so I took the chance to make other changes.
-
qcow2_cache_put()andqcow2_cache_entry_mark_dirty()are now O(1)
- The eviction algorithm is now LRU. The previous one only works well with very small cache sizes.
-qcow2_cache_find_entry_to_replace()is no longer necessary.
- Lookups are faster now.
Quoted 6 lines
In my tests with a preallocated 128MB L2 cache in an empty drive the new code is ~13% faster than the previous one (~43% if compiled without optimizations). This is a best-case scenario, if the cache is smaller or the drive is full of data the improvements are not so visible, but I believe the code is simpler now so I hope you find the changes worthwhile.
Overall I'm happy with this approach. Looking forward to the next revision.
Stefan