[Qemu-devel] [PATCH v2 0/7] qcow2 L2/refcount cache improvements

[Qemu-devel] [PATCH v2 0/7] qcow2 L2/refcount cache improvements

[Alberto Garcia]

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

-- 
2.1.4

[Qemu-devel] [PATCH 1/7] qcow2: use one single memory block for the L2/refcount cache tables

[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 <berto@igalia.com>
---
 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(-)

diff --git a/block/qcow2-cache.c b/block/qcow2-cache.c
index b115549..f0dfb69 100644
--- a/block/qcow2-cache.c
+++ b/block/qcow2-cache.c
@@ -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;
         }
     }
diff --git a/block/qcow2-cluster.c b/block/qcow2-cluster.c
index ed2b44d..5cd418a 100644
--- a/block/qcow2-cluster.c
+++ b/block/qcow2-cluster.c
@@ -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);
diff --git a/block/qcow2-refcount.c b/block/qcow2-refcount.c
index f47260b..35a6a35 100644
--- a/block/qcow2-refcount.c
+++ b/block/qcow2-refcount.c
@@ -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);
                 }
             }
 
diff --git a/block/qcow2.h b/block/qcow2.h
index 422b825..5d0995f 100644
--- a/block/qcow2.h
+++ b/block/qcow2.h
@@ -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);
-- 
2.1.4

[Qemu-devel] [PATCH 2/7] qcow2: simplify qcow2_cache_put() and qcow2_cache_entry_mark_dirty()

[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 <berto@igalia.com>
---
 block/qcow2-cache.c | 32 +++++++++++++++-----------------
 1 file changed, 15 insertions(+), 17 deletions(-)

diff --git a/block/qcow2-cache.c b/block/qcow2-cache.c
index f0dfb69..6e78c8f 100644
--- a/block/qcow2-cache.c
+++ b/block/qcow2-cache.c
@@ -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;
 }
-- 
2.1.4

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

[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 <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;
 
     /* 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;
 }
-- 
2.1.4

[Qemu-devel] [PATCH 4/7] qcow2: remove qcow2_cache_find_entry_to_replace()

[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 <berto@igalia.com>
---
 block/qcow2-cache.c | 45 ++++++++++++++++-----------------------------
 1 file changed, 16 insertions(+), 29 deletions(-)

diff --git a/block/qcow2-cache.c b/block/qcow2-cache.c
index 786c10a..dffb887 100644
--- a/block/qcow2-cache.c
+++ b/block/qcow2-cache.c
@@ -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) {
-- 
2.1.4

[Qemu-devel] [PATCH 5/7] qcow2: use a hash to look for entries in the L2 cache

[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.

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 <berto@igalia.com>
---
 block/qcow2-cache.c | 9 +++++++--
 1 file changed, 7 insertions(+), 2 deletions(-)

diff --git a/block/qcow2-cache.c b/block/qcow2-cache.c
index dffb887..3137ba8 100644
--- a/block/qcow2-cache.c
+++ b/block/qcow2-cache.c
@@ -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
-- 
2.1.4

[Qemu-devel] [PATCH 6/7] qcow2: make qcow2_cache_put() a void function

[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 <berto@igalia.com>
---
 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(-)

diff --git a/block/qcow2-cache.c b/block/qcow2-cache.c
index 3137ba8..0f629c4 100644
--- a/block/qcow2-cache.c
+++ b/block/qcow2-cache.c
@@ -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,
diff --git a/block/qcow2-cluster.c b/block/qcow2-cluster.c
index 5cd418a..d74426c 100644
--- a/block/qcow2-cluster.c
+++ b/block/qcow2-cluster.c
@@ -253,10 +253,7 @@ static int l2_allocate(BlockDriverState *bs, int l1_index, uint64_t **table)
 
         memcpy(l2_table, old_table, s->cluster_size);
 
-        ret = qcow2_cache_put(bs, s->l2_table_cache, (void**) &old_table);
-        if (ret < 0) {
-            goto fail;
-        }
+        qcow2_cache_put(bs, s->l2_table_cache, (void **) &old_table);
     }
 
     /* write the l2 table to the file */
@@ -694,10 +691,7 @@ uint64_t qcow2_alloc_compressed_cluster_offset(BlockDriverState *bs,
     BLKDBG_EVENT(bs->file, BLKDBG_L2_UPDATE_COMPRESSED);
     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) {
-        return 0;
-    }
+    qcow2_cache_put(bs, s->l2_table_cache, (void **) &l2_table);
 
     return cluster_offset;
 }
@@ -789,10 +783,7 @@ int qcow2_alloc_cluster_link_l2(BlockDriverState *bs, QCowL2Meta *m)
      }
 
 
-    ret = qcow2_cache_put(bs, s->l2_table_cache, (void**) &l2_table);
-    if (ret < 0) {
-        goto err;
-    }
+    qcow2_cache_put(bs, s->l2_table_cache, (void **) &l2_table);
 
     /*
      * If this was a COW, we need to decrease the refcount of the old cluster.
@@ -944,7 +935,7 @@ static int handle_copied(BlockDriverState *bs, uint64_t guest_offset,
     uint64_t *l2_table;
     unsigned int nb_clusters;
     unsigned int keep_clusters;
-    int ret, pret;
+    int ret;
 
     trace_qcow2_handle_copied(qemu_coroutine_self(), guest_offset, *host_offset,
                               *bytes);
@@ -1011,10 +1002,7 @@ static int handle_copied(BlockDriverState *bs, uint64_t guest_offset,
 
     /* Cleanup */
 out:
-    pret = qcow2_cache_put(bs, s->l2_table_cache, (void**) &l2_table);
-    if (pret < 0) {
-        return pret;
-    }
+    qcow2_cache_put(bs, s->l2_table_cache, (void **) &l2_table);
 
     /* Only return a host offset if we actually made progress. Otherwise we
      * would make requirements for handle_alloc() that it can't fulfill */
@@ -1139,10 +1127,7 @@ static int handle_alloc(BlockDriverState *bs, uint64_t guest_offset,
      * wrong with our code. */
     assert(nb_clusters > 0);
 
-    ret = qcow2_cache_put(bs, s->l2_table_cache, (void**) &l2_table);
-    if (ret < 0) {
-        return ret;
-    }
+    qcow2_cache_put(bs, s->l2_table_cache, (void **) &l2_table);
 
     /* Allocate, if necessary at a given offset in the image file */
     alloc_cluster_offset = start_of_cluster(s, *host_offset);
@@ -1481,10 +1466,7 @@ static int discard_single_l2(BlockDriverState *bs, uint64_t offset,
         qcow2_free_any_clusters(bs, old_l2_entry, 1, type);
     }
 
-    ret = qcow2_cache_put(bs, s->l2_table_cache, (void**) &l2_table);
-    if (ret < 0) {
-        return ret;
-    }
+    qcow2_cache_put(bs, s->l2_table_cache, (void **) &l2_table);
 
     return nb_clusters;
 }
@@ -1567,10 +1549,7 @@ static int zero_single_l2(BlockDriverState *bs, uint64_t offset,
         }
     }
 
-    ret = qcow2_cache_put(bs, s->l2_table_cache, (void**) &l2_table);
-    if (ret < 0) {
-        return ret;
-    }
+    qcow2_cache_put(bs, s->l2_table_cache, (void **) &l2_table);
 
     return nb_clusters;
 }
@@ -1763,11 +1742,7 @@ static int expand_zero_clusters_in_l1(BlockDriverState *bs, uint64_t *l1_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);
-            if (ret < 0) {
-                l2_table = NULL;
-                goto fail;
-            }
+            qcow2_cache_put(bs, s->l2_table_cache, (void **) &l2_table);
         } else {
             if (l2_dirty) {
                 ret = qcow2_pre_write_overlap_check(bs,
@@ -1798,12 +1773,7 @@ fail:
         if (!is_active_l1) {
             qemu_vfree(l2_table);
         } else {
-            if (ret < 0) {
-                qcow2_cache_put(bs, s->l2_table_cache, (void **)&l2_table);
-            } else {
-                ret = qcow2_cache_put(bs, s->l2_table_cache,
-                        (void **)&l2_table);
-            }
+            qcow2_cache_put(bs, s->l2_table_cache, (void **) &l2_table);
         }
     }
     return ret;
diff --git a/block/qcow2-refcount.c b/block/qcow2-refcount.c
index 35a6a35..e3e7f3a 100644
--- a/block/qcow2-refcount.c
+++ b/block/qcow2-refcount.c
@@ -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 >>
diff --git a/block/qcow2.h b/block/qcow2.h
index 5d0995f..0076512 100644
--- a/block/qcow2.h
+++ b/block/qcow2.h
@@ -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
-- 
2.1.4

[Qemu-devel] [PATCH 7/7] qcow2: style fixes in qcow2-cache.c

[Alberto Garcia]

Fix pointer declaration to make it consistent with the rest of the
code.

Signed-off-by: Alberto Garcia <berto@igalia.com>
---
 block/qcow2-cache.c | 6 +++---
 1 file changed, 3 insertions(+), 3 deletions(-)

diff --git a/block/qcow2-cache.c b/block/qcow2-cache.c
index 0f629c4..bea43c1 100644
--- a/block/qcow2-cache.c
+++ b/block/qcow2-cache.c
@@ -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;
 
-- 
2.1.4

Re: [Qemu-devel] [PATCH 1/7] qcow2: use one single memory block for the L2/refcount cache tables

[Stefan Hajnoczi]

[-- Attachment #1: Type: text/plain, Size: 949 bytes --]

On Wed, May 06, 2015 at 04:39:25PM +0300, Alberto Garcia wrote:
> 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 <berto@igalia.com>
> ---
>  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(-)

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

[-- Attachment #2: Type: application/pgp-signature, Size: 473 bytes --]

Re: [Qemu-devel] [Qemu-block] [PATCH 2/7] qcow2: simplify qcow2_cache_put() and qcow2_cache_entry_mark_dirty()

[Stefan Hajnoczi]

[-- Attachment #1: Type: text/plain, Size: 467 bytes --]

On Wed, May 06, 2015 at 04:39:26PM +0300, Alberto Garcia wrote:
> 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 <berto@igalia.com>
> ---
>  block/qcow2-cache.c | 32 +++++++++++++++-----------------
>  1 file changed, 15 insertions(+), 17 deletions(-)

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

[-- Attachment #2: Type: application/pgp-signature, Size: 473 bytes --]

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

[Stefan Hajnoczi]

[-- Attachment #1: Type: text/plain, Size: 890 bytes --]

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>

[-- Attachment #2: Type: application/pgp-signature, Size: 473 bytes --]

Re: [Qemu-devel] [PATCH 4/7] qcow2: remove qcow2_cache_find_entry_to_replace()

[Stefan Hajnoczi]

[-- Attachment #1: Type: text/plain, Size: 503 bytes --]

On Wed, May 06, 2015 at 04:39:28PM +0300, Alberto Garcia wrote:
> 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 <berto@igalia.com>
> ---
>  block/qcow2-cache.c | 45 ++++++++++++++++-----------------------------
>  1 file changed, 16 insertions(+), 29 deletions(-)

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

[-- Attachment #2: Type: application/pgp-signature, Size: 473 bytes --]

Re: [Qemu-devel] [Qemu-block] [PATCH 5/7] qcow2: use a hash to look for entries in the L2 cache

[Stefan Hajnoczi]

[-- Attachment #1: Type: text/plain, Size: 860 bytes --]

On Wed, May 06, 2015 at 04:39:29PM +0300, Alberto Garcia wrote:
> 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.
> 
> 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 <berto@igalia.com>
> ---
>  block/qcow2-cache.c | 9 +++++++--
>  1 file changed, 7 insertions(+), 2 deletions(-)

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

[-- Attachment #2: Type: application/pgp-signature, Size: 473 bytes --]

Re: [Qemu-devel] [PATCH 6/7] qcow2: make qcow2_cache_put() a void function

[Stefan Hajnoczi]

[-- Attachment #1: Type: text/plain, Size: 581 bytes --]

On Wed, May 06, 2015 at 04:39:30PM +0300, Alberto Garcia wrote:
> 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 <berto@igalia.com>
> ---
>  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(-)

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

[-- Attachment #2: Type: application/pgp-signature, Size: 473 bytes --]

Re: [Qemu-devel] [PATCH 7/7] qcow2: style fixes in qcow2-cache.c

[Stefan Hajnoczi]

[-- Attachment #1: Type: text/plain, Size: 348 bytes --]

On Wed, May 06, 2015 at 04:39:31PM +0300, Alberto Garcia wrote:
> Fix pointer declaration to make it consistent with the rest of the
> code.
> 
> Signed-off-by: Alberto Garcia <berto@igalia.com>
> ---
>  block/qcow2-cache.c | 6 +++---
>  1 file changed, 3 insertions(+), 3 deletions(-)

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

[-- Attachment #2: Type: application/pgp-signature, Size: 473 bytes --]

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

[Eric Blake]

[-- Attachment #1: Type: text/plain, Size: 1283 bytes --]

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.

-- 
Eric Blake   eblake redhat com    +1-919-301-3266
Libvirt virtualization library http://libvirt.org


[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 604 bytes --]

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

[Alberto Garcia]

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

Re: [Qemu-devel] [Qemu-block] [PATCH 1/7] qcow2: use one single memory block for the L2/refcount cache tables

[Max Reitz]

On 06.05.2015 15:39, Alberto Garcia wrote:
> 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 <berto@igalia.com>
> ---
>   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(-)

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

Re: [Qemu-devel] [Qemu-block] [PATCH 2/7] qcow2: simplify qcow2_cache_put() and qcow2_cache_entry_mark_dirty()

[Max Reitz]

On 06.05.2015 15:39, Alberto Garcia wrote:
> 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 <berto@igalia.com>
> ---
>   block/qcow2-cache.c | 32 +++++++++++++++-----------------
>   1 file changed, 15 insertions(+), 17 deletions(-)

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

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

[Max Reitz]

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

Re: [Qemu-devel] [Qemu-block] [PATCH 4/7] qcow2: remove qcow2_cache_find_entry_to_replace()

[Max Reitz]

On 06.05.2015 15:39, Alberto Garcia wrote:
> 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 <berto@igalia.com>
> ---
>   block/qcow2-cache.c | 45 ++++++++++++++++-----------------------------
>   1 file changed, 16 insertions(+), 29 deletions(-)

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

Re: [Qemu-devel] [Qemu-block] [PATCH 5/7] qcow2: use a hash to look for entries in the L2 cache

[Max Reitz]

On 06.05.2015 15:39, Alberto Garcia wrote:
> 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.
>
> 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 <berto@igalia.com>
> ---
>   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

[Max Reitz]

On 06.05.2015 15:39, Alberto Garcia wrote:
> 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 <berto@igalia.com>
> ---
>   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(-)
>
> diff --git a/block/qcow2-cache.c b/block/qcow2-cache.c
> index 3137ba8..0f629c4 100644
> --- a/block/qcow2-cache.c
> +++ b/block/qcow2-cache.c
> @@ -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;
> -    }
> -

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

[Max Reitz]

On 06.05.2015 15:39, Alberto Garcia wrote:
> Fix pointer declaration to make it consistent with the rest of the
> code.
>
> Signed-off-by: Alberto Garcia <berto@igalia.com>
> ---
>   block/qcow2-cache.c | 6 +++---
>   1 file changed, 3 insertions(+), 3 deletions(-)

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

Re: [Qemu-devel] [Qemu-block] [PATCH 5/7] qcow2: use a hash to look for entries in the L2 cache

[Alberto Garcia]

On Fri 08 May 2015 05:46:57 PM CEST, Max Reitz wrote:

> 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

[Alberto Garcia]

On Fri 08 May 2015 05:51:30 PM CEST, Max Reitz wrote:

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

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