From patchwork Mon Nov 26 13:05:06 2012 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: =?utf-8?q?Beno=C3=AEt_Canet?= X-Patchwork-Id: 201671 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Received: from lists.gnu.org (lists.gnu.org [208.118.235.17]) (using TLSv1 with cipher AES256-SHA (256/256 bits)) (Client did not present a certificate) by ozlabs.org (Postfix) with ESMTPS id DF7592C008A for ; Tue, 27 Nov 2012 00:16:10 +1100 (EST) Received: from localhost ([::1]:43001 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1TcyXh-0008Cu-18 for incoming@patchwork.ozlabs.org; Mon, 26 Nov 2012 08:16:09 -0500 Received: from eggs.gnu.org ([208.118.235.92]:49150) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1TcyO6-0004ME-7b for qemu-devel@nongnu.org; Mon, 26 Nov 2012 08:06:23 -0500 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1TcyO1-00059k-QZ for qemu-devel@nongnu.org; Mon, 26 Nov 2012 08:06:14 -0500 Received: from nodalink.pck.nerim.net ([62.212.105.220]:44833 helo=paradis.irqsave.net) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1TcyO1-00059H-By for qemu-devel@nongnu.org; Mon, 26 Nov 2012 08:06:09 -0500 Received: by paradis.irqsave.net (Postfix, from userid 1002) id C6FA48742FA; Mon, 26 Nov 2012 14:19:06 +0100 (CET) Received: from localhost.localdomain (unknown [192.168.77.1]) by paradis.irqsave.net (Postfix) with ESMTP id 314DB874301; Mon, 26 Nov 2012 14:18:14 +0100 (CET) From: =?UTF-8?q?Beno=C3=AEt=20Canet?= To: qemu-devel@nongnu.org Date: Mon, 26 Nov 2012 14:05:06 +0100 Message-Id: <1353935123-24199-8-git-send-email-benoit@irqsave.net> X-Mailer: git-send-email 1.7.10.4 In-Reply-To: <1353935123-24199-1-git-send-email-benoit@irqsave.net> References: <1353935123-24199-1-git-send-email-benoit@irqsave.net> X-detected-operating-system: by eggs.gnu.org: GNU/Linux 2.2.x-3.x [generic] X-Received-From: 62.212.105.220 Cc: kwolf@redhat.com, =?UTF-8?q?Beno=C3=AEt=20Canet?= , stefanha@redhat.com Subject: [Qemu-devel] [RFC V3 07/24] qcow2: Add qcow2_dedup_write_new_hashes. X-BeenThere: qemu-devel@nongnu.org X-Mailman-Version: 2.1.14 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: qemu-devel-bounces+incoming=patchwork.ozlabs.org@nongnu.org Sender: qemu-devel-bounces+incoming=patchwork.ozlabs.org@nongnu.org Signed-off-by: Benoit Canet --- 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