[Qemu-devel] [PATCH][RFC][1/2] qcow2: optimize refminus updates

[Frediano Ziglio <freddy77@gmail.com>]

Cache refcount decrement in an array to trade-off between
leaks and speed.

Signed-off-by: Frediano Ziglio <freddy77@gmail.com>
---
 block/qcow2-refcount.c |  142 ++++++++++++++++++++++++++++++++++++++++++++++--
 block/qcow2.c          |    1 +
 block/qcow2.h          |   14 +++++
 3 files changed, 153 insertions(+), 4 deletions(-)

diff --git a/block/qcow2-refcount.c b/block/qcow2-refcount.c
index 9605367..7d59b68 100644
--- a/block/qcow2-refcount.c
+++ b/block/qcow2-refcount.c
@@ -40,6 +40,13 @@ int qcow2_refcount_init(BlockDriverState *bs)
     BDRVQcowState *s = bs->opaque;
     int ret, refcount_table_size2, i;
 
+    s->refm_cache_index = 0;
+    s->refm_cache_len = 1024;
+    s->refm_cache = g_malloc(s->refm_cache_len * sizeof(uint64));
+    if (!s->refm_cache) {
+        goto fail;
+    }
+
     refcount_table_size2 = s->refcount_table_size * sizeof(uint64_t);
     s->refcount_table = g_malloc(refcount_table_size2);
     if (s->refcount_table_size > 0) {
@@ -53,12 +60,14 @@ int qcow2_refcount_init(BlockDriverState *bs)
     }
     return 0;
  fail:
+    g_free(s->refm_cache);
     return -ENOMEM;
 }
 
 void qcow2_refcount_close(BlockDriverState *bs)
 {
     BDRVQcowState *s = bs->opaque;
+    g_free(s->refm_cache);
     g_free(s->refcount_table);
 }
 
@@ -634,13 +643,21 @@ int64_t qcow2_alloc_bytes(BlockDriverState *bs, int size)
 void qcow2_free_clusters(BlockDriverState *bs,
                           int64_t offset, int64_t size)
 {
+    BDRVQcowState *s = bs->opaque;
     int ret;
+    int64_t start, last;
 
     BLKDBG_EVENT(bs->file, BLKDBG_CLUSTER_FREE);
-    ret = update_refcount(bs, offset, size, -1);
-    if (ret < 0) {
-        fprintf(stderr, "qcow2_free_clusters failed: %s\n", strerror(-ret));
-        /* TODO Remember the clusters to free them later and avoid leaking */
+    start = offset & ~(s->cluster_size - 1);
+    last = (offset + size - 1) & ~(s->cluster_size - 1);
+    for (; start <= last; start += s->cluster_size) {
+        ret = qcow2_refm_add(bs, start);
+        if (ret < 0) {
+            fprintf(stderr, "qcow2_free_clusters failed: %s\n", strerror(-ret));
+            /* TODO Remember the clusters to free them later
+             * and avoid leaking */
+            break;
+        }
     }
 }
 
@@ -1165,3 +1182,120 @@ fail:
     return ret;
 }
 
+int qcow2_refm_add_any(BlockDriverState *bs, int64_t offset)
+{
+    BDRVQcowState *s = bs->opaque;
+
+    offset &= ~QCOW_OFLAG_COPIED;
+    if (s->refm_cache_index + 2 > s->refm_cache_len) {
+        int ret = qcow2_refm_flush(bs);
+        if (ret < 0) {
+            return ret;
+        }
+    }
+
+    if ((offset & QCOW_OFLAG_COMPRESSED)) {
+        int nb_csectors = ((offset >> s->csize_shift) & s->csize_mask) + 1;
+        int64_t last;
+
+        offset = (offset & s->cluster_offset_mask) & ~511;
+        last  = offset + nb_csectors * 512 - 1;
+        if (!in_same_refcount_block(s, offset, last)) {
+            s->refm_cache[s->refm_cache_index++] = last;
+        }
+    }
+    s->refm_cache[s->refm_cache_index++] = offset;
+    return 0;
+}
+
+static int uint64_cmp(const void *a, const void *b)
+{
+#define A (*((const uint64_t *)a))
+#define B (*((const uint64_t *)b))
+    if (A == B) {
+        return 0;
+    }
+    return A > B ? 1 : -1;
+#undef A
+#undef B
+}
+
+int qcow2_refm_flush(BlockDriverState *bs)
+{
+    BDRVQcowState *s = bs->opaque;
+    uint16_t *refcount_block = NULL;
+    int64_t old_table_index = -1;
+    int ret, i, saved_index = 0;
+    int len = s->refm_cache_index;
+
+    /* sort cache */
+    qsort(s->refm_cache, len, sizeof(uint64_t), uint64_cmp);
+
+    /* save */
+    for (i = 0; i < len; ++i) {
+        uint64_t cluster_offset = s->refm_cache[i];
+        int block_index, refcount;
+        int64_t cluster_index = cluster_offset >> s->cluster_bits;
+        int64_t table_index =
+            cluster_index >> (s->cluster_bits - REFCOUNT_SHIFT);
+
+        /* 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,
+                    (void **) &refcount_block);
+                if (ret < 0) {
+                    goto fail;
+                }
+                saved_index = i;
+                refcount_block = NULL;
+            }
+
+            ret = alloc_refcount_block(bs, cluster_index, &refcount_block);
+            if (ret < 0) {
+                goto fail;
+            }
+        }
+        old_table_index = table_index;
+
+        qcow2_cache_entry_mark_dirty(s->refcount_block_cache, refcount_block);
+
+        /* we can update the count and save it */
+        block_index = cluster_index &
+            ((1 << (s->cluster_bits - REFCOUNT_SHIFT)) - 1);
+
+        refcount = be16_to_cpu(refcount_block[block_index]);
+        refcount--;
+        if (refcount < 0) {
+            ret = -EINVAL;
+            goto fail;
+        }
+        if (refcount == 0 && cluster_index < s->free_cluster_index) {
+            s->free_cluster_index = cluster_index;
+        }
+        refcount_block[block_index] = cpu_to_be16(refcount);
+    }
+
+    saved_index = len = 0;
+    s->refm_cache_index = 0;
+    ret = 0;
+fail:
+    /* Write last changed block to disk */
+    if (refcount_block) {
+        int wret;
+        wret = qcow2_cache_put(bs, s->refcount_block_cache,
+            (void **) &refcount_block);
+        if (wret < 0) {
+            return ret < 0 ? ret : wret;
+        }
+    }
+
+    if (saved_index < len) {
+        memmove(s->refm_cache, s->refm_cache + saved_index,
+            (len - saved_index) * sizeof(uint64_t));
+        s->refm_cache_index = len - saved_index;
+    }
+
+    return ret;
+}
+
diff --git a/block/qcow2.c b/block/qcow2.c
index 510ff68..89ae765 100644
--- a/block/qcow2.c
+++ b/block/qcow2.c
@@ -622,6 +622,7 @@ static void qcow2_close(BlockDriverState *bs)
     g_free(s->l1_table);
 
     qcow2_cache_flush(bs, s->l2_table_cache);
+    qcow2_refm_flush(bs);
     qcow2_cache_flush(bs, s->refcount_block_cache);
 
     qcow2_cache_destroy(bs, s->l2_table_cache);
diff --git a/block/qcow2.h b/block/qcow2.h
index 531af39..49d3d55 100644
--- a/block/qcow2.h
+++ b/block/qcow2.h
@@ -103,6 +103,8 @@ typedef struct BDRVQcowState {
 
     Qcow2Cache* l2_table_cache;
     Qcow2Cache* refcount_block_cache;
+    int refm_cache_len, refm_cache_index;
+    uint64_t *refm_cache;
 
     uint8_t *cluster_cache;
     uint8_t *cluster_data;
@@ -181,6 +183,18 @@ int qcow2_backing_read1(BlockDriverState *bs, QEMUIOVector *qiov,
 int qcow2_refcount_init(BlockDriverState *bs);
 void qcow2_refcount_close(BlockDriverState *bs);
 
+int qcow2_refm_add_any(BlockDriverState *bs, int64_t offset);
+int qcow2_refm_flush(BlockDriverState *bs);
+static inline int qcow2_refm_add(BlockDriverState *bs, int64_t offset)
+{
+    BDRVQcowState *s = bs->opaque;
+    if (s->refm_cache_index < s->refm_cache_len) {
+        s->refm_cache[s->refm_cache_index++] = offset;
+        return 0;
+    }
+    return qcow2_refm_add_any(bs, offset);
+}
+
 int64_t qcow2_alloc_clusters(BlockDriverState *bs, int64_t size);
 int64_t qcow2_alloc_bytes(BlockDriverState *bs, int size);
 void qcow2_free_clusters(BlockDriverState *bs,
-- 
1.7.1