[Qemu-devel] [RFC V3 07/24] qcow2: Add qcow2_dedup_write_new_hashes.

["Benoît Canet" <benoit@irqsave.net>]

Signed-off-by: Benoit Canet <benoit@irqsave.net>
---
 block/qcow2-dedup.c |  220 +++++++++++++++++++++++++++++++++++++++++++++++++++
 block/qcow2.h       |    5 ++
 2 files changed, 225 insertions(+)

diff --git a/block/qcow2-dedup.c b/block/qcow2-dedup.c
index a7c7202..83ad61e 100644
--- a/block/qcow2-dedup.c
+++ b/block/qcow2-dedup.c
@@ -31,6 +31,12 @@
 
 #define HASH_LENGTH 32
 
+static int qcow2_dedup_read_write_hash(BlockDriverState *bs,
+                                       uint8_t **hash,
+                                       uint64_t *first_logical_offset,
+                                       uint64_t physical_cluster_offset,
+                                       bool write);
+
 /**
  * Read some data from the QCOW2 file
  *
@@ -336,7 +342,15 @@ static int qcow2_dedup_cluster(BlockDriverState *bs,
                 if (ret < 0) {
                     goto exit;
                 }
+
                 hash_node->first_logical_offset = first_logical_offset;
+                ret = qcow2_dedup_read_write_hash(bs, precomputed_hash,
+                                                  &first_logical_offset,
+                                                  physical_cluster_offset,
+                                                  true);
+                if (ret < 0) {
+                    goto exit;
+                }
             }
         }
     }
@@ -460,3 +474,209 @@ exit:
     }
     return deduped_clusters_nr * s->cluster_sectors - begining_index;
 }
+
+/* Read a hash cluster from disk or allocate it if it doesn't exist yet
+ *
+ * @in_dedup_table_index: The index of the hash cluster in the dedup table
+ * @hash_block:           the place where the cluster will be loaded
+ * @create:               set to true if dedup table entries must be created
+ *                        when not found
+ * @ret:                  0 on success, errno on error
+ */
+static int get_hash_cluster_from_cache(BlockDriverState *bs,
+                                       int32_t in_dedup_table_index,
+                                       uint8_t **hash_block, bool create)
+{
+    BDRVQcowState *s = bs->opaque;
+    int ret = -ENOSPC;
+    int64_t hash_cluster_offset;
+
+    if (in_dedup_table_index >= (s->dedup_table_size - 1)) {
+        goto fail;
+    }
+
+    hash_cluster_offset = s->dedup_table[in_dedup_table_index];
+    if (!hash_cluster_offset && create) {
+        /* the dedup table entry doesn't exists and we must create it */
+        uint64_t data64;
+        /* allocate a new dedup table cluster */
+        hash_cluster_offset = qcow2_alloc_clusters(bs, s->cluster_size);
+        if (hash_cluster_offset < 0) {
+            return hash_cluster_offset;
+        }
+
+        ret = qcow2_cache_flush(bs, s->refcount_block_cache);
+        if (ret < 0) {
+            goto fail;
+        }
+
+        s->dedup_table[in_dedup_table_index] = hash_cluster_offset;
+        /* get an empty cluster from the dedup cache */
+        ret = qcow2_cache_get_empty(bs, s->dedup_cluster_cache,
+                                    hash_cluster_offset,
+                                    (void **) hash_block);
+        if (ret < 0) {
+            goto fail;
+        }
+        /* clear it */
+        memset(*hash_block, 0, s->cluster_size);
+        /* write the new block offset in the dedup table */
+        data64 = cpu_to_be64(hash_cluster_offset);
+        ret = bdrv_pwrite_sync(bs->file,
+                               s->dedup_table_offset +
+                               in_dedup_table_index * sizeof(uint64_t),
+                               &data64, sizeof(data64));
+        if (ret < 0) {
+            goto fail;
+        }
+    } else if (!hash_cluster_offset && !create) {
+        /* the dedup table entry doesn't exits and we must _not_ create */
+        return 1;
+    } else {
+        /* the entry exists get it */
+        hash_cluster_offset = s->dedup_table[in_dedup_table_index];
+        ret = qcow2_cache_get(bs, s->dedup_cluster_cache,
+                              hash_cluster_offset, (void **) hash_block);
+        if (ret < 0) {
+            return ret;
+        }
+    }
+
+    return 0;
+
+fail:
+    qcow2_free_clusters(bs, hash_cluster_offset, s->cluster_size);
+    return ret;
+}
+
+/* Read/write a given hash and cluster_offset from/to the dedup table
+ *
+ * This function doesn't flush the dedup cache to disk
+ *
+ * @hash:                     the hash to read or store
+ * @first_logical_offset:     logical offset of the QCOW_FLAG_OCOPIED cluster
+ * @physical_cluster_offset:  offset of the cluster in QCOW2 file (in sectors)
+ * @write:                    true to write, false to read
+ * @ret:                      0 on succes, errno on error
+ */
+static int qcow2_dedup_read_write_hash(BlockDriverState *bs,
+                                       uint8_t **hash,
+                                       uint64_t *first_logical_offset,
+                                       uint64_t physical_cluster_offset,
+                                       bool write)
+{
+    BDRVQcowState *s = bs->opaque;
+    uint8_t *hash_block = NULL;
+    int ret;
+    int64_t cluster_number;
+    int64_t in_dedup_table_index;
+    int hash_block_offset;
+    int nb_hash_in_dedup_cluster = s->cluster_size / (HASH_LENGTH + 8);
+    uint64_t first;
+
+    cluster_number = physical_cluster_offset / s->cluster_sectors;
+    in_dedup_table_index = cluster_number / nb_hash_in_dedup_cluster;
+
+    /* if we are doing a write this will create missing dedup table entries */
+    ret = get_hash_cluster_from_cache(bs, in_dedup_table_index,
+                                      &hash_block, write);
+    if (ret < 0) {
+        return ret;
+    }
+
+    hash_block_offset = (cluster_number % nb_hash_in_dedup_cluster) *
+                        (HASH_LENGTH + 8);
+    if (ret == 1) {
+        /* dedup cache is not used */
+        *hash = g_malloc0(HASH_LENGTH);
+        *first_logical_offset = 0;
+    } else if (write)  {
+        first = cpu_to_be64(*first_logical_offset);
+        memcpy(hash_block + hash_block_offset , *hash, HASH_LENGTH);
+        memcpy(hash_block + hash_block_offset + HASH_LENGTH, &first, 8);
+        qcow2_cache_entry_mark_dirty(s->dedup_cluster_cache, hash_block);
+    } else  {
+        *hash = g_malloc(HASH_LENGTH);
+        memcpy(*hash, hash_block + hash_block_offset, HASH_LENGTH);
+        memcpy(&first, hash_block + hash_block_offset + HASH_LENGTH, 8);
+        *first_logical_offset = be64_to_cpu(first);
+    }
+
+    if (!ret) {
+        qcow2_cache_put(bs, s->dedup_cluster_cache, (void **) &hash_block);
+    }
+
+    return ret;
+}
+
+static void qcow2_dedup_remove_old_hash_by_offset(BlockDriverState *bs,
+                                                  uint64_t offset)
+{
+    BDRVQcowState *s = bs->opaque;
+    QCowHashNode *hash_node;
+
+    hash_node = g_tree_lookup(s->dedup_tree_by_offset, &offset);
+
+    if (hash_node) {
+        g_tree_remove(s->dedup_tree_by_offset, &hash_node->offset);
+        g_tree_remove(s->dedup_tree_by_hash, hash_node->hash);
+    }
+}
+
+/* This function write the hashes of the clusters which are not duplicated
+ *
+ * @u:                       the list of undedupable hashes
+ * @logical_cluster_offset:  logical offset of the first cluster (in sectors)
+ * @physical_cluster_offset: offset of the first cluster (in sectors)
+ * @ret:                     0 on succes, errno on error
+ */
+int qcow2_dedup_write_new_hashes(BlockDriverState *bs,
+                                 UndedupableHashes *u,
+                                 int hash_count,
+                                 uint64_t logical_cluster_offset,
+                                 uint64_t physical_cluster_offset)
+{
+    int ret;
+    BDRVQcowState *s = bs->opaque;
+    QCowHashElement *dedup_hash, *next_dedup_hash;
+    QCowHashNode *hash_node;
+
+    int i = 0;
+
+    QTAILQ_FOREACH_SAFE(dedup_hash, &u->undedupable_hashes,
+                        next, next_dedup_hash) {
+        uint64_t physical = physical_cluster_offset + i * s->cluster_sectors;
+        uint64_t logical = logical_cluster_offset + i * s->cluster_sectors;
+
+        hash_node = g_tree_lookup(s->dedup_tree_by_hash, dedup_hash->hash);
+
+        if (hash_node && hash_node->offset & QCOW_FLAG_EMPTY) {
+            logical = logical | QCOW_FLAG_FIRST;
+            hash_node->offset = physical;
+            hash_node->first_logical_offset = logical &
+                                              ~(s->cluster_sectors - 1);
+            qcow2_dedup_remove_old_hash_by_offset(bs, hash_node->offset);
+            g_tree_insert(s->dedup_tree_by_offset, &hash_node->offset,
+                          hash_node);
+
+            ret = qcow2_dedup_read_write_hash(bs, &dedup_hash->hash,
+                                              &logical,
+                                              physical,
+                                              true);
+            if (ret < 0) {
+                goto fail;
+            }
+        }
+
+        QTAILQ_REMOVE(&u->undedupable_hashes, dedup_hash, next);
+        g_free(dedup_hash);
+        i++;
+        if (i == hash_count) {
+            break;
+        }
+    }
+
+    ret = qcow2_cache_flush(bs, s->dedup_cluster_cache);
+fail:
+    return ret;
+}
diff --git a/block/qcow2.h b/block/qcow2.h
index 5c18425..3e05a8c 100644
--- a/block/qcow2.h
+++ b/block/qcow2.h
@@ -385,5 +385,10 @@ int qcow2_dedup(BlockDriverState *bs,
                 int *skip_clusters_nr,
                 int *next_non_dedupable_sectors_nr,
                 uint8_t **next_call_first_hash);
+int qcow2_dedup_write_new_hashes(BlockDriverState *bs,
+                                 UndedupableHashes *u,
+                                 int hash_count,
+                                 uint64_t logical_cluster_offset,
+                                 uint64_t physical_cluster_offset);
 
 #endif
-- 
1.7.10.4