From patchwork Wed Jan 2 16:16:05 2013 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: 209074 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 26DED2C0079 for ; Thu, 3 Jan 2013 03:16:57 +1100 (EST) Received: from localhost ([::1]:53406 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1TqQzv-0008CL-2E for incoming@patchwork.ozlabs.org; Wed, 02 Jan 2013 11:16:55 -0500 Received: from eggs.gnu.org ([208.118.235.92]:53104) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1TqQzY-0007nq-Iw for qemu-devel@nongnu.org; Wed, 02 Jan 2013 11:16:36 -0500 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1TqQzU-0005wE-TB for qemu-devel@nongnu.org; Wed, 02 Jan 2013 11:16:32 -0500 Received: from nodalink.pck.nerim.net ([62.212.105.220]:56159 helo=paradis.irqsave.net) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1TqQzU-0005w9-G4 for qemu-devel@nongnu.org; Wed, 02 Jan 2013 11:16:28 -0500 Received: by paradis.irqsave.net (Postfix, from userid 1002) id D3A40874330; Wed, 2 Jan 2013 17:42:56 +0100 (CET) Received: from localhost.localdomain (unknown [192.168.77.1]) by paradis.irqsave.net (Postfix) with ESMTP id 8C611874307; Wed, 2 Jan 2013 17:42:38 +0100 (CET) From: =?UTF-8?q?Beno=C3=AEt=20Canet?= To: qemu-devel@nongnu.org Date: Wed, 2 Jan 2013 17:16:05 +0100 Message-Id: <1357143393-29832-3-git-send-email-benoit@irqsave.net> X-Mailer: git-send-email 1.7.10.4 In-Reply-To: <1357143393-29832-1-git-send-email-benoit@irqsave.net> References: <1357143393-29832-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, pbonzini@redhat.com, =?UTF-8?q?Beno=C3=AEt=20Canet?= , stefanha@redhat.com Subject: [Qemu-devel] [RFC V4 02/30] qcow2: Add deduplication structures and fields. 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.h | 57 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++- 1 file changed, 56 insertions(+), 1 deletion(-) diff --git a/block/qcow2.h b/block/qcow2.h index 718b52b..637c86a 100644 --- a/block/qcow2.h +++ b/block/qcow2.h @@ -58,6 +58,50 @@ #define DEFAULT_CLUSTER_SIZE 65536 +#define HASH_LENGTH 32 + +typedef enum { + QCOW_HASH_SHA256 = 0, + QCOW_HASH_SHA3 = 1, + QCOW_HASH_SKEIN = 2, +} QCowHashAlgo; + +typedef struct { + uint8_t data[HASH_LENGTH]; /* 32 bytes hash of a given cluster */ +} QCowHash; + +/* Used to keep a single precomputed hash between the calls of the dedup + * function + */ +typedef struct { + QCowHash hash; + bool reuse; /* The hash is precomputed reuse it */ +} QcowPersistantHash; + +/* deduplication node */ +typedef struct { + QCowHash hash; + uint64_t physical_sect; /* where the cluster is stored on disk */ + uint64_t first_logical_sect; /* logical sector of the first occurence of + * this cluster + */ +} QCowHashNode; + +/* Undedupable hashes that must be written later to disk */ +typedef struct QCowHashElement { + QCowHash hash; + QTAILQ_ENTRY(QCowHashElement) next; +} QCowHashElement; + +typedef struct { + QcowPersistantHash phash; /* contains a hash persisting between calls of + * qcow2_dedup() + */ + QTAILQ_HEAD(, QCowHashElement) undedupables; + int nb_clusters_processed; + int nb_undedupable_sectors; +} QCowDedupState; + typedef struct QCowHeader { uint32_t magic; uint32_t version; @@ -114,8 +158,10 @@ enum { enum { QCOW2_INCOMPAT_DIRTY_BITNR = 0, QCOW2_INCOMPAT_DIRTY = 1 << QCOW2_INCOMPAT_DIRTY_BITNR, + QCOW2_INCOMPAT_DEDUP_BITNR = 1, + QCOW2_INCOMPAT_DEDUP = 1 << QCOW2_INCOMPAT_DEDUP_BITNR, - QCOW2_INCOMPAT_MASK = QCOW2_INCOMPAT_DIRTY, + QCOW2_INCOMPAT_MASK = QCOW2_INCOMPAT_DIRTY | QCOW2_INCOMPAT_DEDUP, }; /* Compatible feature bits */ @@ -138,6 +184,7 @@ typedef struct BDRVQcowState { int cluster_sectors; int l2_bits; int l2_size; + int hash_block_size; int l1_size; int l1_vm_state_index; int csize_shift; @@ -148,6 +195,7 @@ typedef struct BDRVQcowState { Qcow2Cache* l2_table_cache; Qcow2Cache* refcount_block_cache; + Qcow2Cache *dedup_cluster_cache; uint8_t *cluster_cache; uint8_t *cluster_data; @@ -160,6 +208,13 @@ typedef struct BDRVQcowState { int64_t free_cluster_index; int64_t free_byte_offset; + bool has_dedup; + QCowHashAlgo dedup_hash_algo; + uint64_t *dedup_table; + uint64_t dedup_table_offset; + int32_t dedup_table_size; + GTree *dedup_tree_by_hash; + GTree *dedup_tree_by_sect; CoMutex lock; uint32_t crypt_method; /* current crypt method, 0 if no key yet */