[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[Qemu-devel] [RFC V7 07/32] qcow2: Add qcow2_dedup and related functions
From: |
Benoît Canet |
Subject: |
[Qemu-devel] [RFC V7 07/32] qcow2: Add qcow2_dedup and related functions |
Date: |
Fri, 15 Mar 2013 15:49:21 +0100 |
Signed-off-by: Benoit Canet <address@hidden>
---
block/qcow2-dedup.c | 432 +++++++++++++++++++++++++++++++++++++++++++++++++++
block/qcow2.h | 5 +
2 files changed, 437 insertions(+)
diff --git a/block/qcow2-dedup.c b/block/qcow2-dedup.c
index bc6e2c2..3ef34a9 100644
--- a/block/qcow2-dedup.c
+++ b/block/qcow2-dedup.c
@@ -119,3 +119,435 @@ fail:
*data = NULL;
return ret;
}
+
+/*
+ * Build a QCowHashNode structure
+ *
+ * @hash: the given hash
+ * @physical_sect: the cluster offset in the QCOW2 file
+ * @first_logical_sect: the first logical cluster offset written
+ * @ret: the build QCowHashNode
+ */
+static QCowHashNode *qcow2_hash_node_new(QCowHash *hash,
+ uint64_t physical_sect,
+ uint64_t first_logical_sect)
+{
+ QCowHashNode *hash_node;
+
+ hash_node = g_new0(QCowHashNode, 1);
+ memcpy(hash_node->hash.data, hash->data, HASH_LENGTH);
+ hash_node->physical_sect = physical_sect;
+ hash_node->first_logical_sect = first_logical_sect;
+
+ return hash_node;
+}
+
+/*
+ * Compute the hash of a given cluster
+ *
+ * @data: a buffer containing the cluster data
+ * @hash: a QCowHash where to store the computed hash
+ * @ret: 0 on success, negative on error
+ */
+static int qcow2_compute_cluster_hash(BlockDriverState *bs,
+ QCowHash *hash,
+ uint8_t *data)
+{
+ return 0;
+}
+
+/*
+ * Get a QCowHashNode corresponding to a cluster data
+ *
+ * @phash: if phash can be used no hash is computed
+ * @data: a buffer containing the cluster
+ * @err: Error code if any
+ * @ret: QCowHashNode of the duplicated cluster or NULL if not
found
+ */
+static QCowHashNode *qcow2_get_hash_node_for_cluster(BlockDriverState *bs,
+ QcowPersistentHash *phash,
+ uint8_t *data,
+ int *err)
+{
+ BDRVQcowState *s = bs->opaque;
+ int ret = 0;
+ *err = 0;
+
+ /* no hash has been provided compute it and store it for later usage */
+ if (!phash->reuse) {
+ ret = qcow2_compute_cluster_hash(bs,
+ &phash->hash,
+ data);
+ }
+
+ /* do not reuse the hash anymore if it was precomputed */
+ phash->reuse = false;
+
+ if (ret < 0) {
+ *err = ret;
+ return NULL;
+ }
+
+ return g_tree_lookup(s->dedup_tree_by_hash, &phash->hash);
+}
+
+/*
+ * Build a QCowHashNode from a given QCowHash and insert it into the tree
+ *
+ * @hash: the given QCowHash
+ */
+static void qcow2_build_and_insert_hash_node(BlockDriverState *bs,
+ QCowHash *hash)
+{
+ BDRVQcowState *s = bs->opaque;
+ QCowHashNode *hash_node;
+
+ /* build the hash node with QCOW_DEDUP_FLAG_EMPTY as offsets so we will
remember
+ * to fill these field later with real values.
+ */
+ hash_node = qcow2_hash_node_new(hash,
+ QCOW_DEDUP_FLAG_EMPTY,
+ QCOW_DEDUP_FLAG_EMPTY);
+ g_tree_insert(s->dedup_tree_by_hash, &hash_node->hash, hash_node);
+}
+
+/*
+ * Helper used to build a QCowHashElement
+ *
+ * @hash: the QCowHash to use
+ * @ret: a newly allocated QCowHashElement containing the given hash
+ */
+static QCowHashElement *qcow2_dedup_hash_new(QCowHash *hash)
+{
+ QCowHashElement *dedup_hash;
+ dedup_hash = g_new0(QCowHashElement, 1);
+ memcpy(dedup_hash->hash.data, hash->data, HASH_LENGTH);
+ return dedup_hash;
+}
+
+/*
+ * Helper used to link a deduplicated cluster in the l2
+ *
+ * @logical_sect: the cluster sector seen by the guest
+ * @physical_sect: the cluster sector in the QCOW2 file
+ * @overwrite: true if we must overwrite the L2 table entry
+ * @ret:
+ */
+static int qcow2_dedup_link_l2(BlockDriverState *bs,
+ uint64_t logical_sect,
+ uint64_t physical_sect,
+ bool overwrite)
+{
+ QCowL2Meta m = {
+ .alloc_offset = physical_sect << 9,
+ .offset = logical_sect << 9,
+ .nb_clusters = 1,
+ .nb_available = 0,
+ .cow_start = {
+ .offset = 0,
+ .nb_sectors = 0,
+ },
+ .cow_end = {
+ .offset = 0,
+ .nb_sectors = 0,
+ },
+ .l2_entry_flags = 0,
+ .overwrite = overwrite,
+ };
+ return qcow2_alloc_cluster_link_l2(bs, &m);
+}
+
+/* Clear the QCOW_OFLAG_COPIED from the first L2 entry written for a physical
+ * cluster.
+ *
+ * @hash_node: the duplicated hash node
+ * @ret: 0 on success, negative on error
+ */
+static int qcow2_clear_l2_copied_flag_if_needed(BlockDriverState *bs,
+ QCowHashNode *hash_node)
+{
+ int ret = 0;
+ uint64_t first_logical_sect = hash_node->first_logical_sect;
+
+ /* QCOW_OFLAG_COPIED already cleared -> do nothing */
+ if (!(first_logical_sect & QCOW_OFLAG_COPIED)) {
+ return 0;
+ }
+
+ first_logical_sect &= ~QCOW_OFLAG_COPIED;
+
+ /* overwrite first L2 entry to clear QCOW_FLAG_COPIED */
+ ret = qcow2_dedup_link_l2(bs, first_logical_sect,
+ hash_node->physical_sect,
+ true);
+
+ if (ret < 0) {
+ return ret;
+ }
+
+ /* remember that we don't need to clear QCOW_OFLAG_COPIED again */
+ hash_node->first_logical_sect = first_logical_sect;
+
+ return 0;
+}
+
+/* This function deduplicate a cluster
+ *
+ * @logical_sect: The logical sector of the write
+ * @hash_node: The duplicated cluster hash node
+ * @ret: 0 on success, negative on error
+ */
+static int qcow2_deduplicate_cluster(BlockDriverState *bs,
+ uint64_t logical_sect,
+ QCowHashNode *hash_node)
+{
+ BDRVQcowState *s = bs->opaque;
+ uint64_t cluster_index = hash_node->physical_sect / s->cluster_sectors;
+ int ret = 0;
+
+ /* Increment the refcount of the cluster */
+ ret = qcow2_update_cluster_refcount(bs,
+ cluster_index,
+ 1,
+ false);
+
+ if (ret < 0) {
+ return ret;
+ }
+
+ /* create new L2 entry */
+ return qcow2_dedup_link_l2(bs, logical_sect,
+ hash_node->physical_sect,
+ false);
+}
+
+/* This function tries to deduplicate a given cluster.
+ *
+ * @sector_num: the logical sector number we are trying to
deduplicate
+ * @phash: Used instead of computing the hash if provided
+ * @data: the buffer in which to look for a duplicated cluster
+ * @ret: ret < 0 on error, 1 on deduplication else 0
+ */
+static int qcow2_try_dedup_cluster(BlockDriverState *bs,
+ QcowPersistentHash *phash,
+ uint64_t sector_num,
+ uint8_t *data)
+{
+ BDRVQcowState *s = bs->opaque;
+ int ret = 0;
+ QCowHashNode *hash_node;
+ uint64_t logical_sect;
+ uint64_t existing_physical_offset;
+ int pnum = s->cluster_sectors;
+
+ /* search the tree for duplicated cluster */
+ hash_node = qcow2_get_hash_node_for_cluster(bs,
+ phash,
+ data,
+ &ret);
+
+ /* we won't reuse the hash on error */
+ if (ret < 0) {
+ return ret;
+ }
+
+ /* if cluster is not duplicated store hash for later usage */
+ if (!hash_node) {
+ qcow2_build_and_insert_hash_node(bs, &phash->hash);
+ return 0;
+ }
+
+ logical_sect = sector_num & ~(s->cluster_sectors - 1);
+ ret = qcow2_get_cluster_offset(bs, logical_sect << 9,
+ &pnum, &existing_physical_offset);
+
+ if (ret < 0) {
+ return ret;
+ }
+
+ /* if we are rewriting the same cluster at the same place do nothing */
+ if (existing_physical_offset == hash_node->physical_sect << 9) {
+ return 1;
+ }
+
+ /* take care of not having refcount > 1 and QCOW_OFLAG_COPIED at once */
+ ret = qcow2_clear_l2_copied_flag_if_needed(bs, hash_node);
+
+ if (ret < 0) {
+ return ret;
+ }
+
+ /* do the deduplication */
+ ret = qcow2_deduplicate_cluster(bs, logical_sect,
+ hash_node);
+
+ if (ret < 0) {
+ return ret;
+ }
+
+ return 1;
+}
+
+
+static void add_hash_to_undedupable_list(BlockDriverState *bs,
+ QCowDedupState *ds)
+{
+ /* memorise hash for later storage in gtree and disk */
+ QCowHashElement *dedup_hash = qcow2_dedup_hash_new(&ds->phash.hash);
+ QTAILQ_INSERT_TAIL(&ds->undedupables, dedup_hash, next);
+}
+
+static int qcow2_dedup_starting_from_begining(BlockDriverState *bs,
+ QCowDedupState *ds,
+ uint64_t sector_num,
+ uint8_t *data,
+ int left_to_process)
+{
+ BDRVQcowState *s = bs->opaque;
+ int i;
+ int ret = 0;
+
+ for (i = 0; i < left_to_process; i++) {
+ ret = qcow2_try_dedup_cluster(bs,
+ &ds->phash,
+ sector_num + i * s->cluster_sectors,
+ data + i * s->cluster_size);
+
+ if (ret < 0) {
+ return ret;
+ }
+
+ /* stop if a cluster has not been deduplicated */
+ if (ret != 1) {
+ break;
+ }
+ }
+
+ return i;
+}
+
+static int qcow2_count_next_non_dedupable_clusters(BlockDriverState *bs,
+ QCowDedupState *ds,
+ uint8_t *data,
+ int left_to_process)
+{
+ BDRVQcowState *s = bs->opaque;
+ int i;
+ int ret = 0;
+ QCowHashNode *hash_node;
+
+ for (i = 0; i < left_to_process; i++) {
+ hash_node = qcow2_get_hash_node_for_cluster(bs,
+ &ds->phash,
+ data + i * s->cluster_size,
+ &ret);
+
+ if (ret < 0) {
+ return ret;
+ }
+
+ /* found a duplicated cluster : stop here */
+ if (hash_node) {
+ break;
+ }
+
+ qcow2_build_and_insert_hash_node(bs, &ds->phash.hash);
+ add_hash_to_undedupable_list(bs, ds);
+ }
+
+ return i;
+}
+
+
+/* Deduplicate all the cluster that can be deduplicated.
+ *
+ * Next it computes the number of non deduplicable sectors to come while
storing
+ * the hashes of these sectors in a linked list for later usage.
+ * Then it computes the first duplicated cluster hash that comes after non
+ * deduplicable cluster, this hash will be used at next call of the function
+ *
+ * @ds: a structure containing the state of the deduplication
+ * for this write request
+ * @sector_num: The logical sector
+ * @data: the buffer containing the data to deduplicate
+ * @data_nr: the size of the buffer in sectors
+ *
+ */
+int qcow2_dedup(BlockDriverState *bs,
+ QCowDedupState *ds,
+ uint64_t sector_num,
+ uint8_t *data,
+ int data_nr)
+{
+ BDRVQcowState *s = bs->opaque;
+ int ret = 0;
+ int deduped_clusters_nr = 0;
+ int left_to_process;
+ int start_index;
+
+ start_index = sector_num & (s->cluster_sectors - 1);
+
+ left_to_process = (data_nr / s->cluster_sectors) -
+ ds->nb_clusters_processed;
+
+ data += ds->nb_clusters_processed * s->cluster_size;
+
+ /* start deduplicating all that can be cluster after cluster */
+ ret = qcow2_dedup_starting_from_begining(bs,
+ ds,
+ sector_num,
+ data,
+ left_to_process);
+
+ if (ret < 0) {
+ return ret;
+ }
+
+ deduped_clusters_nr = ret;
+
+ left_to_process -= ret;
+ ds->nb_clusters_processed += ret;
+ data += ret * s->cluster_size;
+
+ /* We deduped everything till the end */
+ if (!left_to_process) {
+ ds->nb_undedupable_sectors = 0;
+ goto exit;
+ }
+
+ /* skip and account the first undedupable cluster found */
+ left_to_process--;
+ ds->nb_clusters_processed++;
+ data += s->cluster_size;
+ ds->nb_undedupable_sectors += s->cluster_sectors;
+
+ add_hash_to_undedupable_list(bs, ds);
+
+ /* Count how many non duplicated sector can be written and memorize hashes
+ * to write them after data has reached disk.
+ */
+ ret = qcow2_count_next_non_dedupable_clusters(bs,
+ ds,
+ data,
+ left_to_process);
+
+ if (ret < 0) {
+ return ret;
+ }
+
+ left_to_process -= ret;
+ ds->nb_clusters_processed += ret;
+ ds->nb_undedupable_sectors += ret * s->cluster_sectors;
+
+ /* remember to reuse the last hash computed at new qcow2_dedup call */
+ if (left_to_process) {
+ ds->phash.reuse = true;
+ }
+
+exit:
+ if (!deduped_clusters_nr) {
+ return 0;
+ }
+
+ return deduped_clusters_nr * s->cluster_sectors - start_index;
+}
diff --git a/block/qcow2.h b/block/qcow2.h
index 3dc9834..6194030 100644
--- a/block/qcow2.h
+++ b/block/qcow2.h
@@ -470,5 +470,10 @@ int
qcow2_dedup_read_missing_and_concatenate(BlockDriverState *bs,
int sectors_nr,
uint8_t **dedup_cluster_data,
int *dedup_cluster_data_nr);
+int qcow2_dedup(BlockDriverState *bs,
+ QCowDedupState *ds,
+ uint64_t sector_num,
+ uint8_t *data,
+ int data_nr);
#endif
--
1.7.10.4
- [Qemu-devel] [RFC V7 00/32] QCOW2 deduplication core functionality, Benoît Canet, 2013/03/15
- [Qemu-devel] [RFC V7 02/32] qmp: Add DedupStatus enum., Benoît Canet, 2013/03/15
- [Qemu-devel] [RFC V7 01/32] qcow2: Add deduplication to the qcow2 specification., Benoît Canet, 2013/03/15
- [Qemu-devel] [RFC V7 03/32] qcow2: Add deduplication structures and fields., Benoît Canet, 2013/03/15
- [Qemu-devel] [RFC V7 04/32] qcow2: Add qcow2_de dup_read_missing_and_concatenate, Benoît Canet, 2013/03/15
- [Qemu-devel] [RFC V7 05/32] qcow2: Create a way to link to l2 tables when deduplicating., Benoît Canet, 2013/03/15
- [Qemu-devel] [RFC V7 06/32] qcow2: Make qcow2_update_cluster_refcount public., Benoît Canet, 2013/03/15
- [Qemu-devel] [RFC V7 09/32] qcow2: Do allocate on rewrite on the dedup case., Benoît Canet, 2013/03/15
- [Qemu-devel] [RFC V7 07/32] qcow2: Add qcow2_dedup and related functions,
Benoît Canet <=
- [Qemu-devel] [RFC V7 08/32] qcow2: Add qcow2_dedup_store_new_hashes., Benoît Canet, 2013/03/15
- [Qemu-devel] [RFC V7 10/32] qcow2: Implement qcow2_compute_cluster_hash., Benoît Canet, 2013/03/15
- [Qemu-devel] [RFC V7 12/32] qcow2: Makes qcow2_alloc_cluster_link_l2 mark to deduplicate clusters., Benoît Canet, 2013/03/15
- [Qemu-devel] [RFC V7 11/32] qcow2: Add qcow2_dedup_grow_table and use it., Benoît Canet, 2013/03/15
- [Qemu-devel] [RFC V7 13/32] qcow2: make the deduplication forget a cluster hash when a cluster is to dedupe, Benoît Canet, 2013/03/15
- [Qemu-devel] [RFC V7 14/32] qcow2: Create qcow2_is_cluster_to_dedup., Benoît Canet, 2013/03/15
- [Qemu-devel] [RFC V7 16/32] qcow2: Extract qcow2_do_table_init., Benoît Canet, 2013/03/15
- [Qemu-devel] [RFC V7 15/32] qcow2: Load and save deduplication table header extension., Benoît Canet, 2013/03/15
- [Qemu-devel] [RFC V7 17/32] qcow2-cache: Allow to choose table size at creation., Benoît Canet, 2013/03/15
- [Qemu-devel] [RFC V7 18/32] qcow2: Extract qcow2_set_incompat_feature and qcow2_clear_incompat_feature., Benoît Canet, 2013/03/15