qcow2 L2/refcount cache improvements
PATCH v2 6/7 qcow2: make qcow2_cache_put() a void function
In reply to Alberto GarciaThis function never receives an invalid table pointer, so we can make it void and remove all the error checking code.
--- block/qcow2-cache.c | 7 +------ block/qcow2-cluster.c | 50 ++++++++++---------------------------------------- block/qcow2-refcount.c | 29 +++++------------------------ block/qcow2.h | 2 +- 4 files changed, 17 insertions(+), 71 deletions(-)
block/qcow2-cache.c +1 -6
@@ -332,14 +332,10 @@ int qcow2_cache_get_empty(BlockDriverState *bs, Qcow2Cache *c, uint64_t offset,return qcow2_cache_do_get (bs, c, offset, table, false); } -int qcow2_cache_put (BlockDriverState *bs,Qcow2Cache *c,void **table) +void qcow2_cache_put (BlockDriverState *bs,Qcow2Cache *c,void **table) {int i =qcow2_cache_get_table_idx (bs, c, *table); -if (c->entries[i].offset ==0 ) { -return -ENOENT ; - } - c->entries[i].ref--; *table =NULL ;
@@ -348,7 +344,6 @@ int qcow2_cache_put(BlockDriverState *bs, Qcow2Cache *c, void **table) }assert (c->entries[i].ref >=0 ); -return 0 ; } void qcow2_cache_entry_mark_dirty(BlockDriverState *bs, Qcow2Cache *c,
block/qcow2-cluster.c +10 -40
110 lines not on this page · raw message
block/qcow2-refcount.c +5 -24
@@ -265,10 +265,7 @@ int qcow2_get_refcount(BlockDriverState *bs, int64_t cluster_index, block_index = cluster_index & (s->refcount_block_size -1 ); *refcount = s->get_refcount (refcount_block, block_index); - ret =qcow2_cache_put (bs, s->refcount_block_cache, &refcount_block); -if (ret <0 ) { -return ret; - } +qcow2_cache_put (bs, s->refcount_block_cache, &refcount_block);return 0 ; }
@@ -448,10 +445,7 @@ static int alloc_refcount_block(BlockDriverState *bs,return -EAGAIN ; } - ret =qcow2_cache_put (bs, s->refcount_block_cache, refcount_block); -if (ret <0 ) { - goto fail_block; - } +qcow2_cache_put (bs, s->refcount_block_cache, refcount_block);/* * If we come here, we need to grow the refcount table. Again, a new
@@ -723,13 +717,8 @@ static int QEMU_WARN_UNUSED_RESULT update_refcount(BlockDriverState *bs,/* Load the refcount block and allocate it if needed */ if (table_index != old_table_index) {if (refcount_block) { - ret =qcow2_cache_put (bs, s->refcount_block_cache, - &refcount_block); -if (ret <0 ) { - goto fail; - } +qcow2_cache_put (bs, s->refcount_block_cache, &refcount_block); } - ret =alloc_refcount_block (bs, cluster_index, &refcount_block);if (ret <0 ) { goto fail;
@@ -774,11 +763,7 @@ fail:/* Write last changed block to disk */ if (refcount_block) { -int wret; - wret =qcow2_cache_put (bs, s->refcount_block_cache, &refcount_block); -if (wret <0 ) { -return ret <0 ? ret : wret; - } +qcow2_cache_put (bs, s->refcount_block_cache, &refcount_block); }/*
@@ -1183,11 +1168,7 @@ int qcow2_update_snapshot_refcount(BlockDriverState *bs, } } - ret =qcow2_cache_put (bs, s->l2_table_cache, (void **) &l2_table); -if (ret <0 ) { - goto fail; - } - +qcow2_cache_put (bs, s->l2_table_cache, (void **) &l2_table);if (addend !=0 ) { ret = qcow2_update_cluster_refcount(bs, l2_offset >>
block/qcow2.h +1 -1
@@ -587,6 +587,6 @@ int qcow2_cache_get(BlockDriverState *bs, Qcow2Cache *c, uint64_t offset, void **table);int qcow2_cache_get_empty (BlockDriverState *bs,Qcow2Cache *c,uint64_t offset,void **table); -int qcow2_cache_put (BlockDriverState *bs,Qcow2Cache *c,void **table); +void qcow2_cache_put (BlockDriverState *bs,Qcow2Cache *c,void **table);#endif
Signature · 1 line
2.1.4
PATCH v2 4/7 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
@@ -242,51 +242,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 v2 2/7 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 | 32 +++++++++++++++----------------- 1 file changed, 15 insertions(+), 17 deletions(-)
block/qcow2-cache.c +15 -17
@@ -49,6 +49,16 @@ static inline void *qcow2_cache_get_table_addr(BlockDriverState *bs,return (uint8_t *) c->table_array + (size_t ) table * s->cluster_size; } +static inline int qcow2_cache_get_table_idx (BlockDriverState *bs, +Qcow2Cache *c,void *table) +{ +BDRVQcowState *s = bs->opaque; +ptrdiff_t table_offset = (uint8_t *) table - (uint8_t *) c->table_array; +int idx = table_offset / s->cluster_size; +assert (idx >=0 && idx < c->size && table_offset % s->cluster_size ==0 ); +return idx; +} +Qcow2Cache *qcow2_cache_create (BlockDriverState *bs,int num_tables) {BDRVQcowState *s = bs->opaque;
@@ -337,16 +347,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 =qcow2_cache_get_table_idx (bs, c, *table); -for (i =0 ; i < c->size; i++) { -if (qcow2_cache_get_table_addr (bs, c, i) == *table) { - goto found; - } +if (c->entries[i].offset ==0 ) { +return -ENOENT ; } -return -ENOENT ; -found: c->entries[i].ref--; *table =NULL ;
@@ -357,15 +363,7 @@ found:void qcow2_cache_entry_mark_dirty (BlockDriverState *bs,Qcow2Cache *c,void *table) { -int i; - -for (i =0 ; i < c->size; i++) { -if (qcow2_cache_get_table_addr (bs, c, i) == table) { - goto found; - } - } -abort (); - -found: +int i =qcow2_cache_get_table_idx (bs, c, table); +assert (c->entries[i].offset !=0 ); c->entries[i].dirty = true; }
Signature · 1 line
2.1.4
PATCH v2 5/7 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
@@ -248,6 +248,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 ;
@@ -255,7 +256,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 / s->cluster_size *4 ) % c->size; + do { const Qcow2CachedTable *t = &c->entries[i]; if (t->offset == offset) { goto found;
@@ -264,7 +266,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
PATCH v2 7/7 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;
@@ -81,7 +81,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
v2 cover qcow2 L2/refcount cache improvements
New version of the qcow2 cache patches:
v2:
- Don't do pointer arithmetic on void *
- Rename table_addr() to qcow2_cache_get_table_addr()
- Add qcow2_cache_get_table_idx()
- Cast cache size to size_t to prevent overflows
- Make qcow2_cache_put() a void function
- Don't store the cluster size in the cache, get it from the BDS instead
v1: https://lists.nongnu.org/archive/html/qemu-devel/2015-04/msg04355.html
Regards,
Berto
Alberto Garcia (7):
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: make qcow2_cache_put() a void function
qcow2: style fixes in qcow2-cache.c
block/qcow2-cache.c | 169 ++++++++++++++++++++++--------------------------- block/qcow2-cluster.c | 62 +++++------------- block/qcow2-refcount.c | 37 +++-------- block/qcow2.h | 5 +- 4 files changed, 104 insertions(+), 169 deletions(-)
Signature · 1 line
2.1.4
PATCH v2 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.
--- 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 {
@@ -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;/* 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 ; }
Signature · 1 line
2.1.4
PATCH v2 1/7 qcow2: use one single memory block for the L2/refcount cache tables
In reply to Alberto GarciaThe 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 | 55 ++++++++++++++++++++++++-------------------------- block/qcow2-cluster.c | 12 +++++------ block/qcow2-refcount.c | 8 +++++--- block/qcow2.h | 3 ++- 4 files changed, 39 insertions(+), 39 deletions(-)
block/qcow2-cache.c +26 -29
@@ -28,7 +28,6 @@#include "trace.h" typedef struct Qcow2CachedTable { - void* table; int64_t offset; bool dirty; int cache_hits;
@@ -40,39 +39,35 @@ struct Qcow2Cache {struct Qcow2Cache * depends;int size;bool depends_on_flush; +void *table_array; }; +static inline void *qcow2_cache_get_table_addr (BlockDriverState *bs, +Qcow2Cache *c,int table) +{ +BDRVQcowState *s = bs->opaque; +return (uint8_t *) c->table_array + (size_t ) table * s->cluster_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->entries =g_try_new0 (Qcow2CachedTable, num_tables); -if (!c->entries) { - goto fail; - } - -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; - } + c->table_array =qemu_try_blockalign (bs->file, + (size_t ) num_tables * s->cluster_size); + +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 +76,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 +146,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, +qcow2_cache_get_table_addr (bs, c, i), s->cluster_size);if (ret <0 ) {return ret; }
@@ -304,7 +299,8 @@ 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,qcow2_cache_get_table_addr (bs, c, i), + s->cluster_size);if (ret <0 ) {return ret; }
@@ -319,7 +315,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 =qcow2_cache_get_table_addr (bs, c, i);trace_qcow2_cache_get_done (qemu_coroutine_self (), c == s->l2_table_cache, i);
@@ -344,7 +340,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 (qcow2_cache_get_table_addr (bs, c, i) == *table) { goto found; } }
@@ -358,12 +354,13 @@ found:return 0 ; } -void qcow2_cache_entry_mark_dirty (Qcow2Cache *c,void *table) +void qcow2_cache_entry_mark_dirty (BlockDriverState *bs,Qcow2Cache *c, +void *table) {int i;for (i =0 ; i < c->size; i++) { -if (c->entries[i].table == table) { +if (qcow2_cache_get_table_addr (bs, c, i) == table) { goto found; } }
block/qcow2-cluster.c +6 -6
@@ -263,7 +263,7 @@ static int l2_allocate(BlockDriverState *bs, int l1_index, uint64_t **table)BLKDBG_EVENT (bs->file,BLKDBG_L2_ALLOC_WRITE );trace_qcow2_l2_allocate_write_l2 (bs, l1_index); -qcow2_cache_entry_mark_dirty (s->l2_table_cache, l2_table); +qcow2_cache_entry_mark_dirty (bs, s->l2_table_cache, l2_table); ret =qcow2_cache_flush (bs, s->l2_table_cache);if (ret <0 ) { goto fail;
@@ -692,7 +692,7 @@ uint64_t qcow2_alloc_compressed_cluster_offset(BlockDriverState *bs,/* compressed clusters never have the copied flag */ BLKDBG_EVENT (bs->file,BLKDBG_L2_UPDATE_COMPRESSED ); -qcow2_cache_entry_mark_dirty (s->l2_table_cache, l2_table); +qcow2_cache_entry_mark_dirty (bs, s->l2_table_cache, l2_table); l2_table[l2_index] =cpu_to_be64 (cluster_offset); ret =qcow2_cache_put (bs, s->l2_table_cache, (void **) &l2_table);if (ret <0 ) {
@@ -771,7 +771,7 @@ int qcow2_alloc_cluster_link_l2(BlockDriverState *bs, QCowL2Meta *m)if (ret <0 ) { goto err; } -qcow2_cache_entry_mark_dirty (s->l2_table_cache, l2_table); +qcow2_cache_entry_mark_dirty (bs, s->l2_table_cache, l2_table);assert (l2_index + m->nb_clusters <= s->l2_size);for (i =0 ; i < m->nb_clusters; i++) {
@@ -1470,7 +1470,7 @@ static int discard_single_l2(BlockDriverState *bs, uint64_t offset, }/* First remove L2 entries */ -qcow2_cache_entry_mark_dirty (s->l2_table_cache, l2_table); +qcow2_cache_entry_mark_dirty (bs, s->l2_table_cache, l2_table);if (!full_discard && s->qcow_version >=3 ) { l2_table[l2_index + i] =cpu_to_be64 (QCOW_OFLAG_ZERO ); }else {
@@ -1558,7 +1558,7 @@ static int zero_single_l2(BlockDriverState *bs, uint64_t offset, old_offset =be64_to_cpu (l2_table[l2_index + i]);/* Update L2 entries */ -qcow2_cache_entry_mark_dirty (s->l2_table_cache, l2_table); +qcow2_cache_entry_mark_dirty (bs, s->l2_table_cache, l2_table);if (old_offset &QCOW_OFLAG_COMPRESSED ) { l2_table[l2_index + i] =cpu_to_be64 (QCOW_OFLAG_ZERO );qcow2_free_any_clusters (bs, old_offset,1 ,QCOW2_DISCARD_REQUEST );
@@ -1760,7 +1760,7 @@ static int expand_zero_clusters_in_l1(BlockDriverState *bs, uint64_t *l1_table,if (is_active_l1) {if (l2_dirty) { -qcow2_cache_entry_mark_dirty (s->l2_table_cache, l2_table); +qcow2_cache_entry_mark_dirty (bs, s->l2_table_cache, l2_table);qcow2_cache_depends_on_flush (s->l2_table_cache); } ret =qcow2_cache_put (bs, s->l2_table_cache, (void **)&l2_table);
block/qcow2-refcount.c +5 -3
@@ -424,7 +424,7 @@ static int alloc_refcount_block(BlockDriverState *bs,/* Now the new refcount block needs to be written to disk */ BLKDBG_EVENT (bs->file,BLKDBG_REFBLOCK_ALLOC_WRITE ); -qcow2_cache_entry_mark_dirty (s->refcount_block_cache, *refcount_block); +qcow2_cache_entry_mark_dirty (bs, s->refcount_block_cache, *refcount_block); ret =qcow2_cache_flush (bs, s->refcount_block_cache);if (ret <0 ) { goto fail_block;
@@ -737,7 +737,8 @@ static int QEMU_WARN_UNUSED_RESULT update_refcount(BlockDriverState *bs, } old_table_index = table_index; -qcow2_cache_entry_mark_dirty (s->refcount_block_cache, refcount_block); +qcow2_cache_entry_mark_dirty (bs, s->refcount_block_cache, + refcount_block);/* we can update the count and save it */ block_index = cluster_index & (s->refcount_block_size -1 );
@@ -1177,7 +1178,8 @@ int qcow2_update_snapshot_refcount(BlockDriverState *bs, s->refcount_block_cache); } l2_table[j] =cpu_to_be64 (offset); -qcow2_cache_entry_mark_dirty (s->l2_table_cache, l2_table); +qcow2_cache_entry_mark_dirty (bs, s->l2_table_cache, + l2_table); } }
block/qcow2.h +2 -1
@@ -574,7 +574,8 @@ int qcow2_read_snapshots(BlockDriverState *bs);Qcow2Cache *qcow2_cache_create (BlockDriverState *bs,int num_tables);int qcow2_cache_destroy (BlockDriverState * bs,Qcow2Cache *c); -void qcow2_cache_entry_mark_dirty (Qcow2Cache *c,void *table); +void qcow2_cache_entry_mark_dirty (BlockDriverState *bs,Qcow2Cache *c, +void *table);int qcow2_cache_flush (BlockDriverState *bs,Qcow2Cache *c);int qcow2_cache_set_dependency (BlockDriverState *bs,Qcow2Cache *c,Qcow2Cache *dependency);
Signature · 1 line
2.1.4
Re: [Qemu-devel] [PATCH 1/7] qcow2: use one single memory block for the L2/refcount cache tables
Quoted 11 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.
Quoted 7 lines
Signed-off-by Alberto Garcia <[email protected]>--- block/qcow2-cache.c | 55 ++++++++++++++++++++++++-------------------------- block/qcow2-cluster.c | 12 +++++------ block/qcow2-refcount.c | 8 +++++--- block/qcow2.h | 3 ++- 4 files changed, 39 insertions(+), 39 deletions(-)
Re: [Qemu-devel] [Qemu-block] [PATCH 2/7] qcow2: simplify qcow2_cache_put() and qcow2_cache_entry_mark_dirty()
In reply to Alberto GarciaQuoted 8 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 | 32 +++++++++++++++----------------- 1 file changed, 15 insertions(+), 17 deletions(-)
Re: [Qemu-devel] [Qemu-block] [PATCH 3/7] qcow2: use an LRU algorithm to replace entries from the L2 cache
In reply to Alberto GarciaQuoted 10 lines · Alberto Garcia
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.
Quoted 7 lines
Using an LRU algorithm makes the chances of being removed from the cache independent from the position.
Signed-off-by Alberto Garcia <[email protected]>--- block/qcow2-cache.c | 31 +++++++++++++++---------------- 1 file changed, 15 insertions(+), 16 deletions(-)
Re: [Qemu-devel] [PATCH 4/7] qcow2: remove qcow2_cache_find_entry_to_replace()
In reply to Alberto GarciaQuoted 8 lines · Alberto Garcia
A 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.
Signed-off-by Alberto Garcia <[email protected]>--- block/qcow2-cache.c | 45 ++++++++++++++++----------------------------- 1 file changed, 16 insertions(+), 29 deletions(-)
Re: [Qemu-devel] [Qemu-block] [PATCH 5/7] qcow2: use a hash to look for entries in the L2 cache
In reply to Alberto GarciaQuoted 10 lines · Alberto Garcia
The 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.
Quoted 7 lines
In my tests, using a cache with 2048 entries, this reduces the average number of comparisons per lookup from 430 to 2.5.
Signed-off-by Alberto Garcia <[email protected]>--- block/qcow2-cache.c | 9 +++++++-- 1 file changed, 7 insertions(+), 2 deletions(-)
Re: [Qemu-devel] [PATCH 6/7] qcow2: make qcow2_cache_put() a void function
In reply to Alberto GarciaQuoted 10 lines · Alberto Garcia
This function never receives an invalid table pointer, so we can make it void and remove all the error checking code.
Signed-off-by Alberto Garcia <[email protected]>--- block/qcow2-cache.c | 7 +------ block/qcow2-cluster.c | 50 ++++++++++---------------------------------------- block/qcow2-refcount.c | 29 +++++------------------------ block/qcow2.h | 2 +- 4 files changed, 17 insertions(+), 71 deletions(-)
Re: [Qemu-devel] [PATCH 7/7] qcow2: style fixes in qcow2-cache.c
In reply to Alberto GarciaQuoted 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(-)
Re: [Qemu-devel] [PATCH 3/7] qcow2: use an LRU algorithm to replace entries from the L2 cache
In reply to Alberto GarciaQuoted 20 lines · Alberto Garcia
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 <[email protected]>--- block/qcow2-cache.c | 31 +++++++++++++++---------------- 1 file changed, 15 insertions(+), 16 deletions(-)
block/qcow2-cache.c static int qcow2_cache_do_get(BlockDriverState *bs, Qcow2Cache *c, · line 318
Quoted 5 lines
block/qcow2-cache.c +0
-1@@ -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.
Signature · 2 lines
Eric Blake eblake redhat com +1-919-301-3266 Libvirt virtualization library http://libvirt.org
Re: [Qemu-devel] [PATCH 3/7] qcow2: use an LRU algorithm to replace entries from the L2 cache
Quoted 6 lines · Eric Blake
Quoted 4 lines
/* 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
Re: [Qemu-devel] [Qemu-block] [PATCH 1/7] qcow2: use one single memory block for the L2/refcount cache tables
In reply to Alberto GarciaQuoted 11 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.
Quoted 7 lines
Signed-off-by Alberto Garcia <[email protected]>--- block/qcow2-cache.c | 55 ++++++++++++++++++++++++-------------------------- block/qcow2-cluster.c | 12 +++++------ block/qcow2-refcount.c | 8 +++++--- block/qcow2.h | 3 ++- 4 files changed, 39 insertions(+), 39 deletions(-)
Re: [Qemu-devel] [Qemu-block] [PATCH 2/7] qcow2: simplify qcow2_cache_put() and qcow2_cache_entry_mark_dirty()
In reply to Alberto GarciaQuoted 8 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 | 32 +++++++++++++++----------------- 1 file changed, 15 insertions(+), 17 deletions(-)
Re: [Qemu-devel] [Qemu-block] [PATCH 3/7] qcow2: use an LRU algorithm to replace entries from the L2 cache
In reply to Alberto GarciaQuoted 85 lines · Alberto Garcia
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 <[email protected]>--- block/qcow2-cache.c | 31 +++++++++++++++---------------- 1 file changed, 15 insertions(+), 16 deletions(-)block/qcow2-cache.c +11
-14@@ -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; } }
block/qcow2-cache.c static int qcow2_cache_do_get(BlockDriverState *bs, Qcow2Cache *c, · line 318
Quoted 5 lines
block/qcow2-cache.c +0
-1@@ -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:
Quoted 17 lines
block/qcow2-cache.c +4
-1/* 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 ; }
Re: [Qemu-devel] [Qemu-block] [PATCH 4/7] qcow2: remove qcow2_cache_find_entry_to_replace()
In reply to Alberto GarciaQuoted 8 lines · Alberto Garcia
A 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.
Signed-off-by Alberto Garcia <[email protected]>--- block/qcow2-cache.c | 45 ++++++++++++++++----------------------------- 1 file changed, 16 insertions(+), 29 deletions(-)
Re: [Qemu-devel] [Qemu-block] [PATCH 5/7] qcow2: use a hash to look for entries in the L2 cache
In reply to Alberto GarciaQuoted 10 lines · Alberto Garcia
The 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.
Quoted 7 lines
In my tests, using a cache with 2048 entries, this reduces the average number of comparisons per lookup from 430 to 2.5.
Signed-off-by Alberto Garcia <[email protected]>--- block/qcow2-cache.c | 9 +++++++-- 1 file changed, 7 insertions(+), 2 deletions(-)
So it's a direct-mapped cache, unless the entry has been used, in which case it becomes a fully associative cache...
Let's assume the cache is full. Now this hash algorithm (direct mapped cache) basically becomes futile, because the LRU algorithm (fully associative cache) takes over, and any entry (the LRU entry) is replaced, independently of the cache. Thus, the entry will most probably not be placed at its hashed position. So once the cache is full, I guess this algorithm doesn't help a lot, does it?
(I'm sorry if you had this discussion before...)
Max
Re: [Qemu-devel] [Qemu-block] [PATCH 6/7] qcow2: make qcow2_cache_put() a void function
In reply to Alberto GarciaQuoted 18 lines · Alberto Garcia
This function never receives an invalid table pointer, so we can make it void and remove all the error checking code.
Signed-off-by Alberto Garcia <[email protected]>--- block/qcow2-cache.c | 7 +------ block/qcow2-cluster.c | 50 ++++++++++---------------------------------------- block/qcow2-refcount.c | 29 +++++------------------------ block/qcow2.h | 2 +- 4 files changed, 17 insertions(+), 71 deletions(-)block/qcow2-cache.c +0
-0@@ -332,14 +332,10 @@ int qcow2_cache_get_empty(BlockDriverState *bs, Qcow2Cache *c, uint64_t offset,return qcow2_cache_do_get (bs, c, offset, table, false); }
block/qcow2-cache.c int qcow2_cache_get_empty(BlockDriverState *bs, Qcow2Cache *c, uint64_t offset, · line 342
Quoted 10 lines
block/qcow2-cache.c +1
-5-int qcow2_cache_put (BlockDriverState *bs,Qcow2Cache *c,void **table) +void qcow2_cache_put (BlockDriverState *bs,Qcow2Cache *c,void **table) {int i =qcow2_cache_get_table_idx (bs, c, *table); -if (c->entries[i].offset ==0 ) { -return -ENOENT ; - } -
Maybe you could replace it by assert(c->entries[i].offset != 0) just like in qcow2_cache_entry_mark_dirty() and similar to the assert() in qcow2_cache_get_table_idx()?
Max
Re: [Qemu-devel] [Qemu-block] [PATCH 7/7] qcow2: style fixes in qcow2-cache.c
In reply to Alberto GarciaQuoted 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(-)
Re: [Qemu-devel] [Qemu-block] [PATCH 5/7] qcow2: use a hash to look for entries in the L2 cache
In reply to Max ReitzQuoted 3 lines · Max Reitz
Let's assume the cache is full. Now this hash algorithm (direct mapped cache) basically becomes futile, because the LRU algorithm (fully associative cache) takes over
That's right, although in that scenario I guess there's no good algorithm.
Anyway and summarizing that I wrote in a different e-mail, I just thought that starting the lookup always from the beginning was the worst alternative and it was very easy to improve it a bit, but I don't think it has a big impact on the performance. Otherwise I would have evaluated a different data structure.
Berto
Re: [Qemu-devel] [Qemu-block] [PATCH 6/7] qcow2: make qcow2_cache_put() a void function
In reply to Max ReitzQuoted 5 lines · Max Reitz
Quoted 5 lines
block/qcow2-cache.c +1
-1-int qcow2_cache_put (BlockDriverState *bs,Qcow2Cache *c,void **table) +void qcow2_cache_put (BlockDriverState *bs,Qcow2Cache *c,void **table) {int i =qcow2_cache_get_table_idx (bs, c, *table);
Quoted 8 lines
block/qcow2-cache.c int qcow2_cache_get_empty(BlockDriverState *bs, Qcow2Cache *c, uint64_t offset, · line 342
Quoted 4 lines
block/qcow2-cache.c +0
-4-if (c->entries[i].offset ==0 ) { -return -ENOENT ; - } -Maybe you could replace it by
assert(c->entries[i].offset != 0)just like inqcow2_cache_entry_mark_dirty()and similar to theassert()inqcow2_cache_get_table_idx()?
I guess the assert(c->entries[i].ref >= 0) at the end of the function already covers that case (if offset == 0 then ref == 0 as well, so it will be -1 by then).
Berto